1	# performance/append_in_loop: a loop that appends to its accumulator. A definition passes
2	# `List.append(.., acc, ..)` or `acc ++ ..` to a call of itself, where acc is one of its parameters.
3	# Heuristics: an append copies acc, so a loop of n steps copies O(n²) items, where adding at the head
4	# copies none. `++` copies only on the C lane: the JS lane joins strings natively. A loop that also
5	# keeps each value it builds, by passing acc in another argument too, needs the copies: it is not
6	# reported. It knows Base's List.append and String.append (`++`), not other functions that copy
7	# their first argument.
8	import Base
9	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
10	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
11	
12	# Types
13	# =====
14	
15	# A function that copies its first list or text to append to it.
16	type Append is Data:
17	  ListAppend{}
18	  StringAppend{}
19	
20	# What judging the calls of a loop to itself reads: the loop's parameters, and the file's text.
21	type Loop is Data:
22	  Loop{params: List<&2, Lint.Node>, text: String}
23	
24	# Functions
25	# =========
26	
27	# The append that a call of `callee` with `count` arguments is.
28	def Append.of(+callee: String, +count: Nat) -> Maybe<&2, Append>:
29	  Bool.pick(
30	    Maybe<&2, Append>,
31	    String.eq(callee, "List.append") && Nat.is_eq(count, 4n),
32	    Some{ListAppend{}},
33	    Lists.when(Append, String.eq(callee, "String.append") && Nat.is_eq(count, 2n), StringAppend{})
34	  )
35	
36	# Which argument an append copies.
37	def Append.at(a: Append) -> Nat:
38	  match a:
39	    case ListAppend{}:
40	      2n
41	    case StringAppend{}:
42	      0n
43	
44	# What a finding says about an append of `acc` in the loop `loop`. `args` are the append's arguments.
45	def Append.message(
46	  a: Append,
47	  loop: String,
48	  +acc: String,
49	  +source: String,
50	  +args: List<&2, Lint.Node>
51	) -> String:
52	  match a:
53	    case ListAppend{}:
54	      +q = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 0n)))
55	      +t = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 1n)))
56	      "List.append copies "
57	        ++ acc
58	        ++ " on each call of "
59	        ++ loop
60	        ++ ", so a loop of n steps copies O(n²) items. All lanes. Confidence: high, as the copies grow with the square of the steps. Add each item at the head instead, with `item <> "
61	        ++ acc
62	        ++ "`, and reverse "
63	        ++ acc
64	        ++ " once when the loop ends: `List.reverse("
65	        ++ q
66	        ++ ", "
67	        ++ t
68	        ++ ", "
69	        ++ acc
70	        ++ ")`; to add a list each step, collect the lists, with `piece <> pieces`, and join them once: `List.concat("
71	        ++ q
72	        ++ ", "
73	        ++ t
74	        ++ ", List.reverse("
75	        ++ q
76	        ++ ", List<"
77	        ++ q
78	        ++ ", "
79	        ++ t
80	        ++ ">, pieces))`. If the loop runs only a few steps, expect this finding."
81	    case StringAppend{}:
82	      "++ copies "
83	        ++ acc
84	        ++ " on each call of "
85	        ++ loop
86	        ++ ", so a loop of n steps copies O(n²) characters. CPU and GPU: measured 12.6 s for 20,000 lines, against 0.07 s after the fix. JS: strings join natively, at no cost. Confidence: high, as the copies grow with the square of the steps. Collect the pieces in a list instead, with `piece <> pieces`, and join them once when the loop ends: `String.concat(List.reverse(&2, String, pieces))`. If the loop runs only a few steps, expect this finding."
87	
88	# Whether a variable the file writes, of the binder `b`, is among `nodes` or under them, or `found`.
89	def has(nodes: List<&2, Lint.Node>, +b: U32, found: Bool) -> Bool:
90	  match nodes found:
91	    case _ True{}:
92	      True{}
93	    case Nil{} False{}:
94	      False{}
95	    case Con{Lint.Node{Lint.Variable{v}, n, Some{s}, k, f}, rest} False{}:
96	      has(rest, b, U32.is_eq(v, b))
97	    case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
98	      has(rest, b, has(kids, b, False{}))
99	
100	def judged(
101	  kept: Bool,
102	  a: Append,
103	  name: String,
104	  acc: String,
105	  span: Lint.Span,
106	  text: String,
107	  args: List<&2, Lint.Node>
108	) -> List<&2, Lint.Finding>:
109	  match kept:
110	    case True{}:
111	      []
112	    case False{}:
113	      [Lint.Finding{Lint.Warning{}, span, Append.message(a, name, acc, text, args), []}]
114	
115	# The finding about an append (`a`, at `span`, with `args`) to `acc`, if it is a parameter of the loop `name` that its
116	# call does not also use (in `before` and `after`, its nodes but the append): then it keeps each value the loop builds,
117	# and the copies are needed.
118	def accumulated(
119	  acc: Maybe<&2, Lint.Node>,
120	  a: Append,
121	  loop: Loop,
122	  name: String,
123	  span: Lint.Span,
124	  args: List<&2, Lint.Node>,
125	  before: List<&2, Lint.Node>,
126	  after: List<&2, Lint.Node>
127	) -> List<&2, Lint.Finding>:
128	  match acc loop:
129	    case Some{Lint.Node{Lint.Variable{+b}, var, s, k, f}} Loop{params, text}:
130	      judged(
131	        has(after, b, has(before, b, Maybe.is_none(&2, Nat, Lint.parameter(params, b)))),
132	        a,
133	        name,
134	        var,
135	        span,
136	        text,
137	        args
138	      )
139	    case _ _:
140	      []
141	
142	def appended(
143	  append: Maybe<&2, Append>,
144	  +args: List<&2, Lint.Node>,
145	  loop: Loop,
146	  name: String,
147	  span: Lint.Span,
148	  before: List<&2, Lint.Node>,
149	  after: List<&2, Lint.Node>
150	) -> List<&2, Lint.Finding>:
151	  match append:
152	    case Some{+a}:
153	      accumulated(
154	        List.get(&2, Lint.Node, args, Append.at(a)),
155	        a,
156	        loop,
157	        name,
158	        span,
159	        args,
160	        before,
161	        after
162	      )
163	    case None{}:
164	      []
165	
166	# The findings about an argument of a call of the loop `name`, if it appends; `before` and `after` are the call's other
167	# nodes.
168	def argument(
169	  arg: Lint.Node,
170	  loop: Loop,
171	  name: String,
172	  before: List<&2, Lint.Node>,
173	  after: List<&2, Lint.Node>
174	) -> List<&2, Lint.Finding>:
175	  match arg:
176	    case Lint.Node{
177	      Lint.Application{},
178	      n,
179	      Some{span},
180	      Con{Lint.Node{Lint.Reference{callee}, rn, rs, rk, rf}, +parts},
181	      f
182	    }:
183	      appended(
184	        Append.of(callee, Lists.length(&2, Lint.Node, parts)),
185	        parts,
186	        loop,
187	        name,
188	        span,
189	        before,
190	        after
191	      )
192	    case _:
193	      []
194	
195	# The findings about the arguments `args` of a call of the loop `name`, after the call's nodes `before` (last first).
196	def arguments(
197	  args: List<&2, Lint.Node>,
198	  +loop: Loop,
199	  +name: String,
200	  +before: List<&2, Lint.Node>,
201	  out: List<&2, Lint.Finding>
202	) -> List<&2, Lint.Finding>:
203	  match args:
204	    case Nil{}:
205	      List.reverse(&2, Lint.Finding, out)
206	    case Con{+arg, +rest}:
207	      arguments(
208	        rest,
209	        loop,
210	        name,
211	        arg <> before,
212	        Lists.onto(&2, Lint.Finding, argument(arg, loop, name, before, rest), out)
213	      )
214	
215	def call.of(loop: Loop, kids: List<&2, Lint.Node>) -> List<&2, Lint.Finding>:
216	  match kids:
217	    case Con{Lint.Node{s, +name, sp, k, f}, args}:
218	      arguments(args, loop, name, [Lint.Node{s, name, sp, k, f}], [])
219	    case Nil{}:
220	      []
221	
222	def call(loop: Loop, node: Lint.Node) -> List<&2, Lint.Finding>:
223	  match node:
224	    case Lint.Node{s, n, sp, kids, f}:
225	      call.of(loop, kids)
226	
227	def calls(recursive: Bool, loop: Loop, node: Lint.Node) -> List<&2, Lint.Finding>:
228	  match recursive:
229	    case True{}:
230	      call(loop, node)
231	    case False{}:
232	      []
233	
234	def visit(+loop: Loop, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
235	  calls(Lint.is_recursive(path, node), loop, node)
236	
237	def defs(
238	  nodes: List<&2, Lint.Node>,
239	  +text: String,
240	  out: List<&2, Lint.Finding>
241	) -> List<&2, Lint.Finding>:
242	  match nodes:
243	    case Nil{}:
244	      List.reverse(&2, Lint.Finding, out)
245	    case Con{Lint.Node{Lint.Definition{t, u}, n, s, +k, f}, rest}:
246	      defs(
247	        rest,
248	        text,
249	        Lists.onto(
250	          &2,
251	          Lint.Finding,
252	          Lint.visit(
253	            ~Loop,
254	            ~Lint.Finding,
255	            ~visit,
256	            Loop{k, text},
257	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
258	          ),
259	          out
260	        )
261	      )
262	    case Con{node, rest}:
263	      defs(rest, text, out)
264	
265	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
266	  Lint.done(defs(Lint.Here.nodes(here), Lint.Here.text(here), []))
267	
268	def rule() -> Lint.Rule:
269	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}