performance/list_index_loop.bend

bend-lint-rules@0.2.0.0 · 340 lines · 24 definitions

1# performance/list_index_loop: a loop that reads a list from its head on each step. A definition passes
2# a list parameter unchanged to a call of itself, and, in the same branch, gives it to List.get,
3# List.drop, List.take, List.last or List.length, or to a definition of the file that gives its
4# parameter to one of those.
5# Heuristics: each of those walks the list from its head, so a loop of n steps over a list of n items
6# takes O(n²) time, where walking the list takes O(n). A branch is the innermost `case` around the
7# read; the loop's call must be in it too. It looks one definition deep, not further. A read in a type
8# does not run, and is skipped. A read whose result is an argument of a call of the loop itself moves
9# the loop along the list (a step, or a split in two: bend-ml's tensor-array fills a tree of bands so),
10# and is not reported.
11import Base
12import bend-lint-api@0.2.0.0/linter/lint.bend as Lint
13import bend-lint-api@0.2.0.0/shared/lists.bend as Lists
14import bend-lint-api@0.2.0.0/shared/names.bend as Names
15
16# Types
17# =====
18
19# A function that walks a list from its head (named as the check names it): which argument is the list,
20# and the Base function that walks it.
21type Walker is Data:
22  Walker{at: Nat, through: String}
23
24# What judging the calls in one definition reads: the walkers of the file, and the definition.
25type Loop is Data:
26  Loop{walkers: List<&2, Names.Named<Walker>>, owner: Lint.Node}
27
28# Functions
29# =========
30def bases() -> List<&2, Names.Named<Walker>>:
31  [
32    Names.Named{"List.get", Walker{2n, "List.get"}},
33    Names.Named{"List.drop", Walker{2n, "List.drop"}},
34    Names.Named{"List.take", Walker{2n, "List.take"}},
35    Names.Named{"List.last", Walker{2n, "List.last"}},
36    Names.Named{"List.length", Walker{2n, "List.length"}}
37  ]
38
39# The binder of the variable `node` uses, if it is a variable.
40def binder(node: Maybe<&2, Lint.Node>) -> Maybe<&2, U32>:
41  match node:
42    case Some{Lint.Node{Lint.Variable{b}, n, s, k, f}}:
43      Some{b}
44    case _:
45      None{}
46
47def Walker.at(k: Maybe<&2, Nat>, target: String, through: String) -> List<&2, Names.Named<Walker>>:
48  match k:
49    case Some{at}:
50      [Names.Named{target, Walker{at, through}}]
51    case None{}:
52      []
53
54def Walker.helped(
55  walked: Maybe<&2, U32>,
56  through: String,
57  owner: Lint.Node
58) -> List<&2, Names.Named<Walker>>:
59  match walked owner:
60    case Some{b} Lint.Node{Lint.Definition{t, u}, n, s, kids, f}:
61      Walker.at(Lint.parameter(kids, b), t, through)
62    case _ _:
63      []
64
65# The walker `owner` is, if a call in it of a Base walker (`base`, with `args`) walks one of its parameters.
66def Walker.helper(
67  base: Maybe<&2, Walker>,
68  args: List<&2, Lint.Node>,
69  owner: Lint.Node
70) -> List<&2, Names.Named<Walker>>:
71  match base:
72    case Some{Walker{at, through}}:
73      Walker.helped(binder(List.get(&2, Lint.Node, args, at)), through, owner)
74    case None{}:
75      []
76
77def Walker.visit(
78  +owner: Lint.Node,
79  +path: List<&2, Lint.Above>,
80  +node: Lint.Node
81) -> List<&2, Names.Named<Walker>>:
82  match node:
83    case Lint.Node{
84      Lint.Application{},
85      n,
86      s,
87      Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
88      f
89    }:
90      Walker.helper(Names.lookup(Walker, t, bases()), args, owner)
91    case _:
92      []
93
94# The definitions among `nodes` that give a parameter to a Base walker, as walkers, onto `out`.
95def Walker.helpers(
96  nodes: List<&2, Lint.Node>,
97  out: List<&2, Names.Named<Walker>>
98) -> List<&2, Names.Named<Walker>>:
99  match nodes:
100    case Nil{}:
101      out
102    case Con{Lint.Node{Lint.Definition{t, u}, n, s, k, f}, rest}:
103      +owner = {Lint.Node{Lint.Definition{t, u}, n, s, k, f}: Lint.Node}
104      Walker.helpers(
105        rest,
106        Lists.onto(
107          &2,
108          Names.Named<Walker>,
109          Lint.visit(~Lint.Node, ~Names.Named<Walker>, ~Walker.visit, owner, [owner]),
110          out
111        )
112      )
113    case Con{node, rest}:
114      Walker.helpers(rest, out)
115
116# Whether a variable of the binder `b` is among `args`, or `found`.
117def is_passed(args: List<&2, Lint.Node>, +b: U32, found: Bool) -> Bool:
118  match args found:
119    case _ True{}:
120      True{}
121    case Nil{} False{}:
122      False{}
123    case Con{Lint.Node{Lint.Variable{v}, n, s, k, f}, rest} False{}:
124      is_passed(rest, b, U32.is_eq(v, b))
125    case Con{arg, rest} False{}:
126      is_passed(rest, b, False{})
127
128# Whether `args`, the arguments of a call of `target` (if `called`), pass the binder `b` unchanged.
129def is_passed.if(called: Bool, args: List<&2, Lint.Node>, b: U32) -> Bool:
130  match called:
131    case True{}:
132      is_passed(args, b, False{})
133    case False{}:
134      False{}
135
136# Whether a call of `target` among `nodes`, or under them, passes the binder `b` unchanged, or `found`.
137def passes(nodes: List<&2, Lint.Node>, +target: String, +b: U32, found: Bool) -> Bool:
138  match nodes found:
139    case _ True{}:
140      True{}
141    case Nil{} False{}:
142      False{}
143    case Con{
144      Lint.Node{
145        Lint.Application{},
146        n,
147        s,
148        Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, +args},
149        f
150      },
151      rest
152    } False{}:
153      passes(rest, target, b, passes(args, target, b, is_passed.if(String.eq(t, target), args, b)))
154    case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
155      passes(rest, target, b, passes(kids, target, b, False{}))
156
157# The innermost case above `path`, if any: a call of the loop must be in it to pass the list on in the same branch.
158def innermost(path: List<&2, Lint.Above>, owner: Lint.Node) -> Lint.Node:
159  match path:
160    case Nil{}:
161      owner
162    case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest}:
163      Lint.Node{Lint.Case{}, n, s, k, f}
164    case Con{a, rest}:
165      innermost(rest, owner)
166
167def advice(through: String, list: String) -> String:
168  Bool.pick(
169    String,
170    String.eq(through, "List.length"),
171    "Compute the length once before the loop, and pass it as a parameter.",
172    "Walk " ++ list ++ " instead: match it, use its head, and pass its tail to the next call."
173  )
174
175def message(+callee: String, +through: String, +list: String, loop: String) -> String:
176  callee
177    ++ " walks "
178    ++ list
179    ++ " from its head"
180    ++ Bool.pick(String, String.eq(callee, through), "", " (through " ++ through ++ ")")
181    ++ ", and "
182    ++ loop
183    ++ " passes "
184    ++ list
185    ++ " unchanged to each call of itself, so a loop that visits each of its n items takes O(n²) time. All lanes. Confidence: high, as each step walks the list again. "
186    ++ advice(through, list)
187    ++ " If the list stays short, expect this finding."
188
189# Whether the loop `owner`, if a parameter of it declares the binder `b` (`param`), passes it unchanged to a call of
190# itself (`target`), in the innermost case above `path`.
191def loops(
192  param: Maybe<&2, Nat>,
193  path: List<&2, Lint.Above>,
194  owner: Lint.Node,
195  target: String,
196  b: U32
197) -> Bool:
198  match param:
199    case Some{i}:
200      passes([innermost(path, owner)], target, b, False{})
201    case None{}:
202      False{}
203
204# Whether the call below `path` is an argument of a call of `target`, the loop itself.
205def feeds(path: List<&2, Lint.Above>, target: String) -> Bool:
206  match path:
207    case Con{
208      Lint.Above{
209        Lint.Node{
210          Lint.Application{},
211          n,
212          s,
213          Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
214          f
215        },
216        at
217      },
218      rest
219    }:
220      String.eq(t, target) && U32.is_gt(at, 0)
221    case _:
222      False{}
223
224# The finding about a walker's call, below `path`, of the list `list` with the binder `walked` that the loop `owner`
225# passes unchanged to a call of itself in the same branch.
226def judged.list(
227  walked: Maybe<&2, U32>,
228  list: String,
229  callee: String,
230  through: String,
231  +owner: Lint.Node,
232  +path: List<&2, Lint.Above>,
233  span: Maybe<&2, Lint.Span>
234) -> List<&2, Lint.Finding>:
235  match walked owner:
236    case Some{+b} Lint.Node{Lint.Definition{+t, u}, name, s, +kids, f}:
237      Lint.finding(
238        Lint.Warning{},
239        loops(
240          Lint.parameter(kids, b),
241          path,
242          owner,
243          t,
244          b
245        )
246          && Lint.is_live(path)
247          && Bool.not(feeds(path, t)),
248        span,
249        message(callee, through, list, name)
250      )
251    case _ _:
252      []
253
254# The finding about a call of the walker `walker`, with `args`.
255def judged(
256  walker: Maybe<&2, Walker>,
257  +args: List<&2, Lint.Node>,
258  callee: String,
259  owner: Lint.Node,
260  path: List<&2, Lint.Above>,
261  span: Maybe<&2, Lint.Span>
262) -> List<&2, Lint.Finding>:
263  match walker:
264    case Some{Walker{+at, through}}:
265      judged.list(
266        binder(List.get(&2, Lint.Node, args, at)),
267        Lint.Node.name(List.get(&2, Lint.Node, args, at)),
268        callee,
269        through,
270        owner,
271        path,
272        span
273      )
274    case None{}:
275      []
276
277def call(
278  recursive: Bool,
279  +loop: Loop,
280  path: List<&2, Lint.Above>,
281  node: Lint.Node
282) -> List<&2, Lint.Finding>:
283  match recursive loop node:
284    case False{} Loop{
285      walkers,
286      owner
287    } Lint.Node{
288      Lint.Application{},
289      n,
290      span,
291      Con{Lint.Node{Lint.Reference{t}, callee, rs, rk, rf}, args},
292      f
293    }:
294      judged(Names.lookup(Walker, t, walkers), args, callee, owner, path, span)
295    case _ _ _:
296      []
297
298def visit(+loop: Loop, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
299  call(Lint.is_recursive(path, node), loop, path, node)
300
301def defs(
302  nodes: List<&2, Lint.Node>,
303  +walkers: List<&2, Names.Named<Walker>>,
304  out: List<&2, Lint.Finding>
305) -> List<&2, Lint.Finding>:
306  match nodes:
307    case Nil{}:
308      List.reverse(&2, Lint.Finding, out)
309    case Con{Lint.Node{Lint.Definition{t, u}, n, s, k, f}, rest}:
310      +owner = {Lint.Node{Lint.Definition{t, u}, n, s, k, f}: Lint.Node}
311      defs(
312        rest,
313        walkers,
314        Lists.onto(
315          &2,
316          Lint.Finding,
317          Lint.visit(~Loop, ~Lint.Finding, ~visit, Loop{walkers, owner}, [owner]),
318          out
319        )
320      )
321    case Con{node, rest}:
322      defs(rest, walkers, out)
323
324def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
325  +nodes = Lint.Here.nodes(here)
326  Lint.done(
327    defs(
328      nodes,
329      Lists.append(
330        &2,
331        Names.Named<Walker>,
332        bases(),
333        List.reverse(&2, Names.Named<Walker>, Walker.helpers(nodes, []))
334      ),
335      []
336    )
337  )
338
339def rule() -> Lint.Rule:
340  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}