1	# rule concat: a def passes itself a parameter grown at the end, `p ++ x` or
2	# `List.append(.., p, ys)` (String.append(p, ..) too), as the argument in p's
3	# own position, the slot it carries; p grown into another slot is not a
4	# finding. The argument is that append written in place, inside any number
5	# of parentheses (`(p ++ x)`), or a lone name read from a let: the nearest
6	# `q = ..` or `+q = ..` of that name before the call in its block or an
7	# enclosing one, whose right side is such an append (a later let of the name
8	# shadows it; other binders, a typed or destructuring let and a do-bind do
9	# not count). A String and a List are cons lists, so appending copies all of
10	# p: the loop is quadratic, with right output (night-train's text step cost
11	# three times the render; rootagi's JSON stringify). Prepend (`x <> acc`)
12	# and reverse once at the end, build with `h <> go(t)`, or gather pieces and
13	# join them once.
14	#
15	# The same append passed on through a continuation is the same loop one hop
16	# removed (`cont`): an argument of a call of a function-typed parameter
17	# (`rest(file, List.append(&2, U32, acc, b <> t))`, where rest is
18	# `fl => a => slurp(f, fl, a)`) that appends onto any parameter of the def,
19	# read the same way (in place, in parentheses, or a lone name through its
20	# let). A `+` parameter the body reads more than once is left alone: it
21	# builds a value it also uses elsewhere (`path ++ "/" ++ name`), not an
22	# accumulator. Prepend each chunk and reverse once at the end; the
23	# accumulator's type changes along the chain (ez's slurp, native: 14.75 s ->
24	# 0.36 s at 16 MB).
25	import Base
26	import ../../src.bend as Src
27	import ../../finding.bend as F
28	import ../../syntax/lex.bend as Lex
29	import ../../syntax/tree.bend as Tree
30	import ../calls.bend as Calls
31	import ../../lazy/lazy.bend as Lazy
32	
33	# a leaf that is a lowercase name: its token. The rule matches a leaf's kind
34	# here and in bound.is_eq only; the rest reads kinds through these
35	def lone.name(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
36	  match nn:
37	    case Tree.Leaf{Lex.Tok{Lex.TName{}, t, l, c}}:
38	      Some{Lex.Tok{Lex.TName{}, t, l, c}}
39	    case other:
40	      None{}
41	
42	# a chain that is exactly one lowercase name: its token
43	def lone(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
44	  match nn:
45	    case Tree.NCons{h, Tree.NNil{}}:
46	      lone.name(h)
47	    case other:
48	      None{}
49	
50	# the list a call appends onto: List.append's first list, String.append's first
51	def appended(+tt: String, as: List<&2, Tree.Node>) -> Maybe<&2, Lex.Tok>:
52	  +list = String.eq(tt, "List.append")
53	  +str = String.eq(tt, "String.append")
54	  Bool.pick(Maybe<&2, Lex.Tok>, Bool.or(list, str), lone(Calls.arg(as, Bool.pick(Nat, list, 2n, 0n))), None{})
55	
56	# a leaf, then a group: the call's append
57	def onto.call(hh: Tree.Node, kids: Tree.Node) -> Maybe<&2, Lex.Tok>:
58	  match hh:
59	    case Tree.Leaf{Lex.Tok{k, +t, l, c}}:
60	      appended(t, Calls.args(kids))
61	    case other:
62	      None{}
63	
64	# a first cell, then the second: a name then `++`, or a call
65	def onto.next(+hh: Tree.Node, h2: Tree.Node) -> Maybe<&2, Lex.Tok>:
66	  match h2:
67	    case Tree.Leaf{Lex.Tok{k, +o, _l, _c}}:
68	      Bool.pick(Maybe<&2, Lex.Tok>, Bool.and(Calls.kind.oper(k), String.eq(o, "++")), lone.name(hh), None{})
69	    case Tree.Group{open, kids, close}:
70	      onto.call(hh, kids)
71	    case other:
72	      None{}
73	
74	# the name an argument appends onto, `p ++ ..` or an append call, inside any
75	# number of parentheses
76	def onto(aa: Tree.Node) -> Maybe<&2, Lex.Tok>:
77	  match aa:
78	    case Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, kids, _}, Tree.NNil{}}:
79	      Lazy.stop(Maybe<&2, Lex.Tok>, Bool.not(String.eq(o, "(")), None{}, _u => onto(kids))
80	    case Tree.NCons{hh, Tree.NCons{h2, rest}}:
81	      onto.next(hh, h2)
82	    case other:
83	      None{}
84	
85	# a let of one plain name in scope: the name, and what its right side
86	# appends onto
87	type Let is Data:
88	  Let{name: String, onto: Maybe<&2, Lex.Tok>}
89	
90	# what the nearest let of the name appends onto; nothing when no let binds it
91	def find(lets: List<&2, Let>, +name: String) -> Maybe<&2, Lex.Tok>:
92	  match lets:
93	    case Nil{}:
94	      None{}
95	    case Con{Let{+nm, mm}, rest}:
96	      Lazy.stop(Maybe<&2, Lex.Tok>, String.eq(nm, name), mm, _u => find(rest, name))
97	
98	# what the let of a lone name appends onto
99	def via.of(mm: Maybe<&2, Lex.Tok>, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
100	  match mm:
101	    case None{}:
102	      None{}
103	    case Some{Lex.Tok{k, +t, l, c}}:
104	      find(lets, t)
105	
106	# the name an argument appends onto, when it is a lone name read from a let
107	def via(aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
108	  via.of(lone(aa), lets)
109	
110	# the first maybe when it holds a token, else the second
111	def either(aa: Maybe<&2, Lex.Tok>, bb: Maybe<&2, Lex.Tok>) -> Maybe<&2, Lex.Tok>:
112	  match aa:
113	    case None{}:
114	      bb
115	    case Some{tok}:
116	      Some{tok}
117	
118	# the name an argument appends onto, in place or through a let
119	def seen(+aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
120	  either(onto(aa), via(aa, lets))
121	
122	# an `=`
123	def bound.eq(kk: Lex.TokKind) -> Bool:
124	  match kk:
125	    case Lex.TEq{}:
126	      True{}
127	    case other:
128	      False{}
129	
130	# a name, then `=`, then the right side: the let
131	def bound.of(mm: Maybe<&2, Lex.Tok>, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:
132	  match mm:
133	    case None{}:
134	      None{}
135	    case Some{Lex.Tok{k, +t, l, c}}:
136	      Lazy.stop(Maybe<&2, Let>, Bool.not(Calls.kind.leaf(~bound.eq, h2)), None{}, _u => Some{Let{t, onto(rhs)}})
137	
138	# a plain name, then `=`, then the right side: the let
139	def bound.named(+hh: Tree.Node, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:
140	  bound.of(lone.name(hh), h2, rhs)
141	
142	# `+`, then a plain name, `=` and the right side: the let
143	def bound.plus(+h1: Tree.Node, +h2: Tree.Node, rest: Tree.Node) -> Maybe<&2, Let>:
144	  match rest:
145	    case Tree.NCons{h3, rhs}:
146	      Lazy.stop(Maybe<&2, Let>, Bool.not(String.eq(Calls.leaf.text(h1), "+")), None{},
147	        _u => bound.named(h2, h3, rhs))
148	    case other:
149	      None{}
150	
151	# the let a statement's own tokens make, when it binds one plain name with
152	# `=`, bare or `+`
153	def bound(kids: Tree.Node) -> Maybe<&2, Let>:
154	  match kids:
155	    case Tree.NCons{+h1, Tree.NCons{+h2, +rest}}:
156	      Lazy.either(Maybe<&2, Let>, Calls.kind.leaf(~Calls.kind.oper, h1), _u => bound.plus(h1, h2, rest),
157	        _v => bound.named(h1, h2, rest))
158	    case other:
159	      None{}
160	
161	# the lets in scope after one more, when there is one
162	def push(mm: Maybe<&2, Let>, +lets: List<&2, Let>) -> List<&2, Let>:
163	  match mm:
164	    case None{}:
165	      lets
166	    case Some{lt}:
167	      lt <> lets
168	
169	# a finding when the name is the parameter of the argument's own slot
170	def hit(
171	  mm: Maybe<&2, Lex.Tok>,
172	  +slot: String,
173	  +path: String,
174	  +acc: List<&2, F.Finding>
175	) -> List<&2, F.Finding>:
176	  match mm:
177	    case None{}:
178	      acc
179	    case Some{Lex.Tok{k, +t, l, c}}:
180	      Bool.pick(List<&2, F.Finding>, String.eq(t, slot),
181	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "concat",
182	          t ++ " is appended to on every step, which copies it each time and makes the loop quadratic; prepend and reverse once at the end, or build with <>."} <> acc,
183	        acc)
184	
185	# the findings on a self-call's arguments, each against the parameter in its
186	# position (params, from the argument's own slot on)
187	def hits(
188	  as: List<&2, Tree.Node>,
189	  +params: List<&2, String>,
190	  +lets: List<&2, Let>,
191	  +path: String,
192	  acc: List<&2, F.Finding>
193	) -> List<&2, F.Finding>:
194	  match as:
195	    case Nil{}:
196	      List.reverse(&2, F.Finding, acc)
197	    case Con{+a, rest}:
198	      +slot = Maybe.default(&2, String, List.head(&2, String, params), "")
199	      was = seen(a, lets)
200	      hits(rest, List.tail(&2, String, params), lets, path, hit(was, slot, path, acc))
201	
202	# the lets a statement leaves in scope for the statements after it
203	def after(kind: Tree.StmtKind, +kids: Tree.Node, +lets: List<&2, Let>) -> List<&2, Let>:
204	  match kind:
205	    case Tree.SLet{}:
206	      push(bound(kids), lets)
207	    case other:
208	      lets
209	
210	# every self-call's arguments, with the lets in scope
211	def walk(
212	  nn: Tree.Node,
213	  +name: String,
214	  +params: List<&2, String>,
215	  +lets: List<&2, Let>,
216	  +path: String
217	) -> List<&2, F.Finding>:
218	  match nn:
219	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
220	      +me = Bool.and(String.eq(o, "("), String.eq(t, name))
221	      List.concat(&2, F.Finding, [
222	        Lazy.stop(List<&2, F.Finding>, Bool.not(me), [], _u => hits(Calls.args(kids), params, lets, path, [])),
223	        walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])
224	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
225	      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])
226	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
227	      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(body, name, params, lets, path),
228	        walk(rest, name, params, after(kind, kids, lets), path)])
229	    case Tree.NCons{h, rest}:
230	      walk(rest, name, params, lets, path)
231	    case other:
232	      Nil{}
233	
234	def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
235	  match ds:
236	    case Nil{}:
237	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
238	    case Con{Calls.Def{+name, +sig, body}, rest}:
239	      check.go(rest, path,
240	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
241	          _u => walk(body, name, Calls.names(sig), [], path)) <> acc)
242	
243	# the rule
244	def check(ss: Src.Src) -> List<&2, F.Finding>:
245	  Src.Src{path, text, toks, tree, bound, items} = ss
246	  check.go(Calls.defs(tree), path, [])
247	
248	# ---------------------------------------------------------------------------
249	# through a continuation: `rest(file, List.append(.., acc, ..))`, where rest
250	# is a function-typed parameter (`fl => a => slurp(f, fl, a)`), grows acc the
251	# same way a self-call does, one hop removed
252	
253	# does a parameter's chain open with `+`?
254	def plus(pp: Tree.Node) -> Bool:
255	  match pp:
256	    case Tree.NCons{+h, rest}:
257	      Bool.and(Calls.kind.leaf(~Calls.kind.oper, h), String.eq(Calls.leaf.text(h), "+"))
258	    case other:
259	      False{}
260	
261	# how many times a plain name is read under the node
262	def uses(nn: Tree.Node, +name: String) -> Nat:
263	  match nn:
264	    case Tree.NCons{h, rest}:
265	      Nat.add(uses(h, name), uses(rest, name))
266	    case Tree.Group{open, kids, close}:
267	      uses(kids, name)
268	    case Tree.Stmt{kind, kids, body}:
269	      Nat.add(uses(kids, name), uses(body, name))
270	    case Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}:
271	      Bool.pick(Nat, String.eq(t, name), 1n, 0n)
272	    case other:
273	      0n
274	
275	# past the first read: a second one drops a `+` parameter
276	def keep.again(+isplus: Bool, more: Nat) -> Bool:
277	  match more:
278	    case 0n:
279	      True{}
280	    case 1n+m:
281	      Bool.not(isplus)
282	
283	# may an append onto the parameter be reported? Any parameter but a `+` one
284	# the body reads more than once: that one builds a value it also uses
285	# elsewhere (`path ++ "/" ++ name`), not an accumulator
286	def keep(+isplus: Bool, count: Nat) -> Bool:
287	  match count:
288	    case 0n:
289	      True{}
290	    case 1n+more:
291	      keep.again(isplus, more)
292	
293	def accs.go(ps: List<&2, Tree.Node>, +body: Tree.Node, +acc: List<&2, String>) -> List<&2, String>:
294	  match ps:
295	    case Nil{}:
296	      acc
297	    case Con{+p, rest}:
298	      +nm = Calls.param_name(p)
299	      accs.go(rest, body, Bool.pick(List<&2, String>, keep(plus(p), uses(body, nm)), nm <> acc, acc))
300	
301	# the parameters an append onto may be reported
302	def accs(sig: Tree.Node, +body: Tree.Node) -> List<&2, String>:
303	  accs.go(Calls.params(sig), body, [])
304	
305	def conts.go(ps: List<&2, Tree.Node>, +acc: List<&2, String>) -> List<&2, String>:
306	  match ps:
307	    case Nil{}:
308	      acc
309	    case Con{+p, rest}:
310	      conts.go(rest, Bool.pick(List<&2, String>, Calls.has_arrow(p), Calls.param_name(p) <> acc, acc))
311	
312	# the function-typed parameters, `rest: File -> List<&2, U32> -> IO(..)`: the
313	# continuations a call may pass an accumulator through
314	def conts(sig: Tree.Node) -> List<&2, String>:
315	  conts.go(Calls.params(sig), [])
316	
317	# a finding when the name is one of the reportable parameters
318	def hit.cont(
319	  mm: Maybe<&2, Lex.Tok>,
320	  +accs: List<&2, String>,
321	  +path: String,
322	  +acc: List<&2, F.Finding>
323	) -> List<&2, F.Finding>:
324	  match mm:
325	    case None{}:
326	      acc
327	    case Some{Lex.Tok{k, +t, l, c}}:
328	      Bool.pick(List<&2, F.Finding>, List.contains(~String, ~String.eq, accs, t),
329	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "concat",
330	          t ++ " is appended to and passed on through a continuation, which copies it on every step and makes the loop quadratic; prepend each chunk and reverse once at the end."} <> acc,
331	        acc)
332	
333	# the findings on a continuation call's arguments
334	def hits.cont(
335	  as: List<&2, Tree.Node>,
336	  +accs: List<&2, String>,
337	  +lets: List<&2, Let>,
338	  +path: String,
339	  acc: List<&2, F.Finding>
340	) -> List<&2, F.Finding>:
341	  match as:
342	    case Nil{}:
343	      List.reverse(&2, F.Finding, acc)
344	    case Con{+a, rest}:
345	      hits.cont(rest, accs, lets, path, hit.cont(seen(a, lets), accs, path, acc))
346	
347	# every continuation call's arguments, with the lets in scope
348	def cwalk(
349	  nn: Tree.Node,
350	  +conts: List<&2, String>,
351	  +accs: List<&2, String>,
352	  +lets: List<&2, Let>,
353	  +path: String
354	) -> List<&2, F.Finding>:
355	  match nn:
356	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
357	      +me = Bool.and(String.eq(o, "("), List.contains(~String, ~String.eq, conts, t))
358	      List.concat(&2, F.Finding, [
359	        Lazy.stop(List<&2, F.Finding>, Bool.not(me), [], _u => hits.cont(Calls.args(kids), accs, lets, path, [])),
360	        cwalk(kids, conts, accs, lets, path), cwalk(rest, conts, accs, lets, path)])
361	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
362	      List.concat(&2, F.Finding, [cwalk(kids, conts, accs, lets, path), cwalk(rest, conts, accs, lets, path)])
363	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
364	      List.concat(&2, F.Finding, [cwalk(kids, conts, accs, lets, path), cwalk(body, conts, accs, lets, path),
365	        cwalk(rest, conts, accs, after(kind, kids, lets), path)])
366	    case Tree.NCons{h, rest}:
367	      cwalk(rest, conts, accs, lets, path)
368	    case other:
369	      Nil{}
370	
371	def cont.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
372	  match ds:
373	    case Nil{}:
374	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
375	    case Con{Calls.Def{name, +sig, +body}, rest}:
376	      cont.go(rest, path,
377	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
378	          _u => cwalk(body, conts(sig), accs(sig, body), [], path)) <> acc)
379	
380	# the rule's other half: appends passed on through a continuation
381	def cont(ss: Src.Src) -> List<&2, F.Finding>:
382	  Src.Src{path, text, toks, tree, bound, items} = ss
383	  cont.go(Calls.defs(tree), path, [])