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.
11	import Base
12	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
13	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
14	import bend-lint-api@0.2.2.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.
21	type 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.
25	type Loop is Data:
26	  Loop{walkers: List<&2, Names.Named<Walker>>, owner: Lint.Node}
27	
28	# Functions
29	# =========
30	def 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.
40	def 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	
47	def 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	
54	def 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.
66	def 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	
77	def 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`.
95	def 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`.
117	def 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.
129	def 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`.
137	def 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.
158	def 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	
167	def 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	
175	def 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`.
191	def 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.
205	def 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.
226	def 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`.
255	def 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	
277	def 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	
298	def 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	
301	def 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	
324	def 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	
339	def rule() -> Lint.Rule:
340	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}