src/rules/suspicious/concat.bend
bolt@1.21.0.0 · 235 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.
14import Base
15import bolt@1.21.0.0/src/src.bend as Src
16import bolt@1.21.0.0/src/finding.bend as F
17import bolt@1.21.0.0/src/syntax/lex.bend as Lex
18import bolt@1.21.0.0/src/syntax/tree.bend as Tree
19import bolt@1.21.0.0/src/rules/calls.bend as Calls
20import bolt@1.21.0.0/src/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
24def 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
32def 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
40def 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
46def 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
54def 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
65def 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
76type 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
80def 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
88def 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
96def 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
100def 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
108def seen(+aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:
109 either(onto(aa), via(aa, lets))
110
111# an `=`
112def 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
120def 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
128def 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
132def 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 `+`
142def 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
151def 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
159def 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)
176def 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
192def 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
200def 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
223def 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
233def 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, [])