src/rules/suspicious/concat.bend
bolt@1.24.0.0 · 383 lines · 0 definitions
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).
25import Base
26import bolt@1.24.0.0/src/src.bend as Src
27import bolt@1.24.0.0/src/finding.bend as F
28import bolt@1.24.0.0/src/syntax/lex.bend as Lex
29import bolt@1.24.0.0/src/syntax/tree.bend as Tree
30import bolt@1.24.0.0/src/rules/calls.bend as Calls
31import bolt@1.24.0.0/src/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
35def 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
43def 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
51def 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
57def 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
65def 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
76def 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
87type 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
91def 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
99def 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
107def 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
111def 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
119def seen(+aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
120 either(onto(aa), via(aa, lets))
121
122# an `=`
123def 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
131def 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
139def 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
143def 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 `+`
153def 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
162def 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
170def 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)
187def 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
203def 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
211def 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
234def 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
244def 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 `+`?
254def 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
262def 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
276def 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
286def keep(+isplus: Bool, count: Nat) -> Bool:
287 match count:
288 case 0n:
289 True{}
290 case 1n+more:
291 keep.again(isplus, more)
292
293def 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
302def accs(sig: Tree.Node, +body: Tree.Node) -> List<&2, String>:
303 accs.go(Calls.params(sig), body, [])
304
305def 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
314def 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
318def 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
334def 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
348def 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
371def 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
381def 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, [])