src/rules/suspicious/scan.bend
bolt@1.18.0.0 · 340 lines · 0 definitions
1# rule scan: a def that calls itself and, on the same step, hands a
2# parameter it carries unchanged to a walk. Every step walks that list again:
3# O(|A| * |B|), A what the def walks and B what it carries. Index it once
4# outside the loop, or merge two sorted walks. A parameter is carried when
5# every self-call passes it back as that same lone name in its own position
6# (hoist's notion). A call is a name token (plain or dotted), then a `(`
7# group, and what it walks is some of its arguments, counted from 0. A Base
8# list search walks its list: argument 2 of `List.contains`, `List.find`,
9# `List.filter` and `List.length`, 3 of `List.any` and `List.all`, 4 of
10# `List.foldl` and `List.foldr`; a Base walk that rebuilds the list
11# (`List.map`, `List.append`, ...) makes output, not a search, and is left
12# alone. A def of this file walks, when it calls itself, its first live
13# parameter that some self-call does not pass back unchanged (the one it
14# shrinks), unless that parameter is a `Nat` or a `String` (a count, such as
15# fuel, or a text); and each parameter its body, anywhere, passes as the lone
16# name of an argument a call walks, of a Base search or of a def listed
17# before it. A def of another module is not seen. A call reports when it is
18# not a self-call and an argument it walks is exactly the lone name of a
19# carried parameter: anything else there (a literal table, an expression, a
20# name the step binds) is left alone. The step is what hoist reads as hot:
21# the def's body, a case arm's body only when it calls the def, never a case
22# pattern, and never the rest of a chain after `=>` (a lambda's body, a
23# `Lazy` thunk, runs when it is called). Laws and proofs do not run (a def
24# with no type at all fills a law: it is a proof), and a law file is skipped
25# whole. One finding per call, on its callee.
26import Base
27import bolt@1.18.0.0/src/src.bend as Src
28import bolt@1.18.0.0/src/paths.bend as Paths
29import bolt@1.18.0.0/src/finding.bend as F
30import bolt@1.18.0.0/src/syntax/lex.bend as Lex
31import bolt@1.18.0.0/src/syntax/tree.bend as Tree
32import bolt@1.18.0.0/src/rules/calls.bend as Calls
33import bolt@1.18.0.0/src/lazy/lazy.bend as Lazy
34import bolt@1.18.0.0/src/rules/suspicious/hoist.bend as Hoist
35
36# a def of this file, and one argument it walks
37type Walk is Data:
38 Walk{name: String, at: Nat}
39
40# the answer as a list: none or one
41def opt(mm: Maybe<&2, Nat>) -> List<&2, Nat>:
42 match mm:
43 case None{}:
44 Nil{}
45 case Some{at}:
46 [at]
47
48# the list argument of a Base list search
49def base_at(+tt: String) -> List<&2, Nat>:
50 +two = List.contains(~String, ~String.eq, ["List.contains", "List.find", "List.filter", "List.length"], tt)
51 +three = List.contains(~String, ~String.eq, ["List.any", "List.all"], tt)
52 +four = List.contains(~String, ~String.eq, ["List.foldl", "List.foldr"], tt)
53 Bool.pick(List<&2, Nat>, two, [2n], Bool.pick(List<&2, Nat>, three, [3n], Bool.pick(List<&2, Nat>, four, [4n], [])))
54
55# the arguments the defs of this file named tt walk
56def file_at(ws: List<&2, Walk>, +tt: String) -> List<&2, Nat>:
57 match ws:
58 case Nil{}:
59 Nil{}
60 case Con{Walk{+nm, +at}, rest}:
61 +more = file_at(rest, tt)
62 Bool.pick(List<&2, Nat>, String.eq(nm, tt), at <> more, more)
63
64# the arguments a callee walks: a Base walk's list, and those the defs of this file record
65def slots(+tt: String, +ws: List<&2, Walk>) -> List<&2, Nat>:
66 List.append(&2, Nat, base_at(tt), file_at(ws, tt))
67
68# a leaf that is a plain name: its text
69def name_tok(tok: Lex.Tok) -> Maybe<&2, String>:
70 match tok:
71 case Lex.Tok{Lex.TName{}, t, l, c}:
72 Some{t}
73 case other:
74 None{}
75
76# the argument, when it is exactly one plain name
77def name_of(nn: Tree.Node) -> Maybe<&2, String>:
78 match nn:
79 case Tree.NCons{Tree.Leaf{tok}, Tree.NNil{}}:
80 name_tok(tok)
81 case other:
82 None{}
83
84# the name, when the list holds it
85def keep_in(mm: Maybe<&2, String>, +names: List<&2, String>) -> Maybe<&2, String>:
86 match mm:
87 case None{}:
88 None{}
89 case Some{+nm}:
90 Bool.pick(Maybe<&2, String>, List.contains(~String, ~String.eq, names, nm), Some{nm}, None{})
91
92# the first of two answers that has one
93def first(aa: Maybe<&2, String>, bb: Maybe<&2, String>) -> Maybe<&2, String>:
94 match aa:
95 case None{}:
96 bb
97 case Some{nm}:
98 Some{nm}
99
100# the first walked argument that is the lone name of one of the names
101def found(ss: List<&2, Nat>, +as: List<&2, Tree.Node>, +names: List<&2, String>) -> Maybe<&2, String>:
102 match ss:
103 case Nil{}:
104 None{}
105 case Con{at, rest}:
106 +more = found(rest, as, names)
107 first(keep_in(name_of(Calls.arg(as, at)), names), more)
108
109# where a name sits among the parameter names
110def index_of(ps: List<&2, String>, +nm: String, +ii: Nat) -> Maybe<&2, Nat>:
111 match ps:
112 case Nil{}:
113 None{}
114 case Con{+p, rest}:
115 Lazy.stop(Maybe<&2, Nat>, String.eq(p, nm), Some{ii}, _u => index_of(rest, nm, 1n+ii))
116
117# where the name sits among the parameter names, when there is a name
118def index_in(mm: Maybe<&2, String>, +ps: List<&2, String>) -> Maybe<&2, Nat>:
119 match mm:
120 case None{}:
121 None{}
122 case Some{+nm}:
123 index_of(ps, nm, 0n)
124
125# the parameters that sit, as lone names, at walked arguments
126def params_at(ss: List<&2, Nat>, +as: List<&2, Tree.Node>, +ps: List<&2, String>) -> List<&2, Nat>:
127 match ss:
128 case Nil{}:
129 Nil{}
130 case Con{at, rest}:
131 +more = params_at(rest, as, ps)
132 List.append(&2, Nat, opt(index_in(name_of(Calls.arg(as, at)), ps)), more)
133
134# a call's walked parameters, when its callee is a name and it is a call
135def pass_hit(
136 kk: Lex.TokKind,
137 +open: Bool,
138 +tt: String,
139 kids: Tree.Node,
140 +ps: List<&2, String>,
141 +ws: List<&2, Walk>
142) -> List<&2, Nat>:
143 match kk:
144 case Lex.TName{}:
145 Lazy.stop(List<&2, Nat>, Bool.not(open), [], _u => params_at(slots(tt, ws), Calls.args(kids), ps))
146 case Lex.TDotted{}:
147 Lazy.stop(List<&2, Nat>, Bool.not(open), [], _u => params_at(slots(tt, ws), Calls.args(kids), ps))
148 case other:
149 Nil{}
150
151# the parameters a body passes, anywhere, as an argument some call walks
152def passes(nn: Tree.Node, +ps: List<&2, String>, +ws: List<&2, Walk>) -> List<&2, Nat>:
153 match nn:
154 case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
155 +own = pass_hit(k, String.eq(o, "("), t, kids, ps, ws)
156 List.concat(&2, Nat, [own, passes(kids, ps, ws), passes(rest, ps, ws)])
157 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
158 List.concat(&2, Nat, [passes(kids, ps, ws), passes(rest, ps, ws)])
159 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
160 List.concat(&2, Nat, [passes(kids, ps, ws), passes(body, ps, ws), passes(rest, ps, ws)])
161 case Tree.NCons{h, rest}:
162 passes(rest, ps, ws)
163 case other:
164 Nil{}
165
166# a live parameter that some self-call does not pass back unchanged
167def moves(+pp: Tree.Node, +carried: List<&2, String>) -> Bool:
168 Bool.and(Calls.is_live(pp), Bool.not(List.contains(~String, ~String.eq, carried, Calls.param_name(pp))))
169
170# a count or a text: a loop down one scans no list
171def scalar(+pp: Tree.Node) -> Bool:
172 +hh = Calls.type_head(pp, False{})
173 Bool.or(String.eq(hh, "Nat"), String.eq(hh, "String"))
174
175# where the parameter a def shrinks sits, unless it is a count or a text
176def place(+pp: Tree.Node, +ii: Nat) -> Maybe<&2, Nat>:
177 Bool.pick(Maybe<&2, Nat>, scalar(pp), None{}, Some{ii})
178
179def own.go(ps: List<&2, Tree.Node>, +carried: List<&2, String>, +ii: Nat) -> Maybe<&2, Nat>:
180 match ps:
181 case Nil{}:
182 None{}
183 case Con{+p, rest}:
184 +here = moves(p, carried)
185 Lazy.stop(Maybe<&2, Nat>, here, place(p, ii), _u => own.go(rest, carried, 1n+ii))
186
187# where the parameter a def shrinks sits, when it calls itself and it is no count or text
188def own(+sig: Tree.Node, +body: Tree.Node, +name: String) -> Maybe<&2, Nat>:
189 Lazy.stop(Maybe<&2, Nat>, Bool.not(Calls.calls(body, name)), None{},
190 _u => own.go(Calls.params(sig), Hoist.carried(sig, body, name), 0n))
191
192# one walk of the def for each argument
193def tag(ns: List<&2, Nat>, +name: String, +ws: List<&2, Walk>) -> List<&2, Walk>:
194 match ns:
195 case Nil{}:
196 ws
197 case Con{at, rest}:
198 Walk{name, at} <> tag(rest, name, ws)
199
200def walks.go(ds: List<&2, Calls.Def>, +ws: List<&2, Walk>) -> List<&2, Walk>:
201 match ds:
202 case Nil{}:
203 ws
204 case Con{Calls.Def{+name, +sig, +body}, rest}:
205 +mine = List.append(&2, Nat, opt(own(sig, body, name)), passes(body, Calls.names(sig), ws))
206 walks.go(rest, tag(mine, name, ws))
207
208# the defs of this file that walk, each with an argument it walks, in order
209def walks(ds: List<&2, Calls.Def>) -> List<&2, Walk>:
210 walks.go(ds, [])
211
212# the name of the parameter a def shrinks, "" for none
213def lead.go(ps: List<&2, Tree.Node>, +carried: List<&2, String>) -> String:
214 match ps:
215 case Nil{}:
216 ""
217 case Con{+p, rest}:
218 +here = moves(p, carried)
219 Lazy.stop(String, here, Calls.param_name(p), _u => lead.go(rest, carried))
220
221# a finding on the callee, naming the carried list
222def cite(
223 mm: Maybe<&2, String>,
224 +tt: String,
225 +line: U32,
226 +col: U32,
227 +self: String,
228 +lead: String,
229 +path: String
230) -> List<&2, F.Finding>:
231 match mm:
232 case None{}:
233 Nil{}
234 case Some{+pp}:
235 [F.Finding{path, line, col, U32.from_nat(String.length(tt)), "scan",
236 tt ++ " walks " ++ pp ++ " on every step of " ++ self ++ ", which carries it unchanged: that is O(|" ++ lead
237 ++ "| * |" ++ pp ++ "|). Index it once outside the loop, or merge two sorted walks."}]
238
239# a hot call of a walk other than the def, a walked argument carried
240def on_name(
241 +hot: Bool,
242 +open: Bool,
243 +tt: String,
244 +line: U32,
245 +col: U32,
246 kids: Tree.Node,
247 +self: String,
248 +ws: List<&2, Walk>,
249 +carried: List<&2, String>,
250 +lead: String,
251 +path: String
252) -> List<&2, F.Finding>:
253 Lazy.stop(List<&2, F.Finding>, Bool.not(Bool.and(hot, Bool.and(open, Bool.not(String.eq(tt, self))))), [],
254 _u => cite(found(slots(tt, ws), Calls.args(kids), carried), tt, line, col, self, lead, path))
255
256# a call's finding, when its callee is a name
257def call_hit(
258 kk: Lex.TokKind,
259 +hot: Bool,
260 +open: Bool,
261 +tt: String,
262 +line: U32,
263 +col: U32,
264 kids: Tree.Node,
265 +self: String,
266 +ws: List<&2, Walk>,
267 +carried: List<&2, String>,
268 +lead: String,
269 +path: String
270) -> List<&2, F.Finding>:
271 match kk:
272 case Lex.TName{}:
273 on_name(hot, open, tt, line, col, kids, self, ws, carried, lead, path)
274 case Lex.TDotted{}:
275 on_name(hot, open, tt, line, col, kids, self, ws, carried, lead, path)
276 case other:
277 Nil{}
278
279# the walks of carried lists on a hot path
280def walk(
281 nn: Tree.Node,
282 +self: String,
283 +ws: List<&2, Walk>,
284 +carried: List<&2, String>,
285 +lead: String,
286 +path: String,
287 +hot: Bool
288) -> List<&2, F.Finding>:
289 match nn:
290 case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
291 +heat = Hoist.warm(hot, k)
292 +own = call_hit(k, heat, String.eq(o, "("), t, l, c, kids, self, ws, carried, lead, path)
293 +inn = walk(kids, self, ws, carried, lead, path, heat)
294 +aft = walk(rest, self, ws, carried, lead, path, heat)
295 List.concat(&2, F.Finding, [own, inn, aft])
296 case Tree.NCons{Tree.Leaf{Lex.Tok{k, t, l, c}}, rest}:
297 walk(rest, self, ws, carried, lead, path, Hoist.warm(hot, k))
298 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
299 List.concat(&2, F.Finding,
300 [walk(kids, self, ws, carried, lead, path, hot), walk(rest, self, ws, carried, lead, path, hot)])
301 case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, +body}, rest}:
302 +arm = Bool.and(hot, Calls.calls(body, self))
303 List.concat(&2, F.Finding, [walk(kids, self, ws, carried, lead, path, False{}),
304 walk(body, self, ws, carried, lead, path, arm), walk(rest, self, ws, carried, lead, path, hot)])
305 case Tree.NCons{Tree.Stmt{kind, kids, body}, rest}:
306 List.concat(&2, F.Finding, [walk(kids, self, ws, carried, lead, path, hot),
307 walk(body, self, ws, carried, lead, path, hot), walk(rest, self, ws, carried, lead, path, hot)])
308 case Tree.NCons{h, rest}:
309 walk(rest, self, ws, carried, lead, path, hot)
310 case other:
311 Nil{}
312
313# one def's walk, its carried parameters and the one it shrinks read once
314def run(+sig: Tree.Node, +body: Tree.Node, +name: String, +ws: List<&2, Walk>, +path: String) -> List<&2, F.Finding>:
315 +carried = Hoist.carried(sig, body, name)
316 walk(body, name, ws, carried, lead.go(Calls.params(sig), carried), path, True{})
317
318def check.go(
319 ds: List<&2, Calls.Def>,
320 +ws: List<&2, Walk>,
321 +path: String,
322 acc: List<&2, List<&2, F.Finding>>
323) -> List<&2, F.Finding>:
324 match ds:
325 case Nil{}:
326 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
327 case Con{Calls.Def{+name, +sig, +body}, rest}:
328 check.go(rest, ws, path,
329 Lazy.stop(List<&2, F.Finding>,
330 Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
331 _u => run(sig, body, name, ws, path)) <> acc)
332
333# the findings over a file's defs, their walks read once
334def check.on(+ds: List<&2, Calls.Def>, +path: String) -> List<&2, F.Finding>:
335 check.go(ds, walks(ds), path, [])
336
337# the rule; a law file is skipped whole, before its walks are read
338def check(ss: Src.Src) -> List<&2, F.Finding>:
339 Src.Src{+path, text, toks, tree, bound, items} = ss
340 Lazy.stop(List<&2, F.Finding>, Paths.is_law_file(path), [], _u => check.on(Calls.defs(tree), path))