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	import Base
15	import ../../src.bend as Src
16	import ../../finding.bend as F
17	import ../../syntax/lex.bend as Lex
18	import ../../syntax/tree.bend as Tree
19	import ../calls.bend as Calls
20	import ../../lazy/lazy.bend as Lazy
21	
22	# a leaf that is a lowercase name: its token. The rule matches a leaf's kind
23	# here and in bound.is_eq only; the rest reads kinds through these
24	def lone.name(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
25	  match nn:
26	    case Tree.Leaf{Lex.Tok{Lex.TName{}, t, l, c}}:
27	      Some{Lex.Tok{Lex.TName{}, t, l, c}}
28	    case other:
29	      None{}
30	
31	# a chain that is exactly one lowercase name: its token
32	def lone(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
33	  match nn:
34	    case Tree.NCons{h, Tree.NNil{}}:
35	      lone.name(h)
36	    case other:
37	      None{}
38	
39	# the list a call appends onto: List.append's first list, String.append's first
40	def appended(+tt: String, as: List<&2, Tree.Node>) -> Maybe<&2, Lex.Tok>:
41	  +list = String.eq(tt, "List.append")
42	  +str = String.eq(tt, "String.append")
43	  Bool.pick(Maybe<&2, Lex.Tok>, Bool.or(list, str), lone(Calls.arg(as, Bool.pick(Nat, list, 2n, 0n))), None{})
44	
45	# a leaf, then a group: the call's append
46	def onto.call(hh: Tree.Node, kids: Tree.Node) -> Maybe<&2, Lex.Tok>:
47	  match hh:
48	    case Tree.Leaf{Lex.Tok{k, +t, l, c}}:
49	      appended(t, Calls.args(kids))
50	    case other:
51	      None{}
52	
53	# a first cell, then the second: a name then `++`, or a call
54	def onto.next(+hh: Tree.Node, h2: Tree.Node) -> Maybe<&2, Lex.Tok>:
55	  match h2:
56	    case Tree.Leaf{Lex.Tok{k, +o, _l, _c}}:
57	      Bool.pick(Maybe<&2, Lex.Tok>, Bool.and(Calls.kind.oper(k), String.eq(o, "++")), lone.name(hh), None{})
58	    case Tree.Group{open, kids, close}:
59	      onto.call(hh, kids)
60	    case other:
61	      None{}
62	
63	# the name an argument appends onto, `p ++ ..` or an append call, inside any
64	# number of parentheses
65	def onto(aa: Tree.Node) -> Maybe<&2, Lex.Tok>:
66	  match aa:
67	    case Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, kids, _}, Tree.NNil{}}:
68	      Lazy.stop(Maybe<&2, Lex.Tok>, Bool.not(String.eq(o, "(")), None{}, _u => onto(kids))
69	    case Tree.NCons{hh, Tree.NCons{h2, rest}}:
70	      onto.next(hh, h2)
71	    case other:
72	      None{}
73	
74	# a let of one plain name in scope: the name, and what its right side
75	# appends onto
76	type Let is Data:
77	  Let{name: String, onto: Maybe<&2, Lex.Tok>}
78	
79	# what the nearest let of the name appends onto; nothing when no let binds it
80	def find(lets: List<&2, Let>, +name: String) -> Maybe<&2, Lex.Tok>:
81	  match lets:
82	    case Nil{}:
83	      None{}
84	    case Con{Let{+nm, mm}, rest}:
85	      Lazy.stop(Maybe<&2, Lex.Tok>, String.eq(nm, name), mm, _u => find(rest, name))
86	
87	# what the let of a lone name appends onto
88	def via.of(mm: Maybe<&2, Lex.Tok>, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
89	  match mm:
90	    case None{}:
91	      None{}
92	    case Some{Lex.Tok{k, +t, l, c}}:
93	      find(lets, t)
94	
95	# the name an argument appends onto, when it is a lone name read from a let
96	def via(aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
97	  via.of(lone(aa), lets)
98	
99	# the first maybe when it holds a token, else the second
100	def either(aa: Maybe<&2, Lex.Tok>, bb: Maybe<&2, Lex.Tok>) -> Maybe<&2, Lex.Tok>:
101	  match aa:
102	    case None{}:
103	      bb
104	    case Some{tok}:
105	      Some{tok}
106	
107	# the name an argument appends onto, in place or through a let
108	def seen(+aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
109	  either(onto(aa), via(aa, lets))
110	
111	# an `=`
112	def bound.eq(kk: Lex.TokKind) -> Bool:
113	  match kk:
114	    case Lex.TEq{}:
115	      True{}
116	    case other:
117	      False{}
118	
119	# a name, then `=`, then the right side: the let
120	def bound.of(mm: Maybe<&2, Lex.Tok>, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:
121	  match mm:
122	    case None{}:
123	      None{}
124	    case Some{Lex.Tok{k, +t, l, c}}:
125	      Lazy.stop(Maybe<&2, Let>, Bool.not(Calls.kind.leaf(~bound.eq, h2)), None{}, _u => Some{Let{t, onto(rhs)}})
126	
127	# a plain name, then `=`, then the right side: the let
128	def bound.named(+hh: Tree.Node, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:
129	  bound.of(lone.name(hh), h2, rhs)
130	
131	# `+`, then a plain name, `=` and the right side: the let
132	def bound.plus(+h1: Tree.Node, +h2: Tree.Node, rest: Tree.Node) -> Maybe<&2, Let>:
133	  match rest:
134	    case Tree.NCons{h3, rhs}:
135	      Lazy.stop(Maybe<&2, Let>, Bool.not(String.eq(Calls.leaf.text(h1), "+")), None{},
136	        _u => bound.named(h2, h3, rhs))
137	    case other:
138	      None{}
139	
140	# the let a statement's own tokens make, when it binds one plain name with
141	# `=`, bare or `+`
142	def bound(kids: Tree.Node) -> Maybe<&2, Let>:
143	  match kids:
144	    case Tree.NCons{+h1, Tree.NCons{+h2, +rest}}:
145	      Lazy.either(Maybe<&2, Let>, Calls.kind.leaf(~Calls.kind.oper, h1), _u => bound.plus(h1, h2, rest),
146	        _v => bound.named(h1, h2, rest))
147	    case other:
148	      None{}
149	
150	# the lets in scope after one more, when there is one
151	def push(mm: Maybe<&2, Let>, +lets: List<&2, Let>) -> List<&2, Let>:
152	  match mm:
153	    case None{}:
154	      lets
155	    case Some{lt}:
156	      lt <> lets
157	
158	# a finding when the name is the parameter of the argument's own slot
159	def hit(
160	  mm: Maybe<&2, Lex.Tok>,
161	  +slot: String,
162	  +path: String,
163	  +acc: List<&2, F.Finding>
164	) -> List<&2, F.Finding>:
165	  match mm:
166	    case None{}:
167	      acc
168	    case Some{Lex.Tok{k, +t, l, c}}:
169	      Bool.pick(List<&2, F.Finding>, String.eq(t, slot),
170	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "concat",
171	          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,
172	        acc)
173	
174	# the findings on a self-call's arguments, each against the parameter in its
175	# position (params, from the argument's own slot on)
176	def hits(
177	  as: List<&2, Tree.Node>,
178	  +params: List<&2, String>,
179	  +lets: List<&2, Let>,
180	  +path: String,
181	  acc: List<&2, F.Finding>
182	) -> List<&2, F.Finding>:
183	  match as:
184	    case Nil{}:
185	      List.reverse(&2, F.Finding, acc)
186	    case Con{+a, rest}:
187	      +slot = Maybe.default(&2, String, List.head(&2, String, params), "")
188	      was = seen(a, lets)
189	      hits(rest, List.tail(&2, String, params), lets, path, hit(was, slot, path, acc))
190	
191	# the lets a statement leaves in scope for the statements after it
192	def after(kind: Tree.StmtKind, +kids: Tree.Node, +lets: List<&2, Let>) -> List<&2, Let>:
193	  match kind:
194	    case Tree.SLet{}:
195	      push(bound(kids), lets)
196	    case other:
197	      lets
198	
199	# every self-call's arguments, with the lets in scope
200	def walk(
201	  nn: Tree.Node,
202	  +name: String,
203	  +params: List<&2, String>,
204	  +lets: List<&2, Let>,
205	  +path: String
206	) -> List<&2, F.Finding>:
207	  match nn:
208	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
209	      +me = Bool.and(String.eq(o, "("), String.eq(t, name))
210	      List.concat(&2, F.Finding, [
211	        Lazy.stop(List<&2, F.Finding>, Bool.not(me), [], _u => hits(Calls.args(kids), params, lets, path, [])),
212	        walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])
213	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
214	      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])
215	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
216	      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(body, name, params, lets, path),
217	        walk(rest, name, params, after(kind, kids, lets), path)])
218	    case Tree.NCons{h, rest}:
219	      walk(rest, name, params, lets, path)
220	    case other:
221	      Nil{}
222	
223	def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
224	  match ds:
225	    case Nil{}:
226	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
227	    case Con{Calls.Def{+name, +sig, body}, rest}:
228	      check.go(rest, path,
229	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
230	          _u => walk(body, name, Calls.names(sig), [], path)) <> acc)
231	
232	# the rule
233	def check(ss: Src.Src) -> List<&2, F.Finding>:
234	  Src.Src{path, text, toks, tree, bound, items} = ss
235	  check.go(Calls.defs(tree), path, [])