performance/list_index_loop.bend
bend-lint-rules@0.2.1.0 · 340 lines · 0 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.1.0/linter/lint.bend as Lint
13import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
14import bend-lint-api@0.2.1.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}}