src/rules/suspicious/index.bend
bolt@1.17.0.0 · 86 lines · 0 definitions
1# rule index: a def that calls itself also calls `List.get(..)` or
2# `String.get(..)`. Both walk the cons list from the head to the index, so a
3# per-index loop is quadratic (AppSprout's sort went from 39 s to 0.9 s
4# walking the list itself). Walk the list in the recursion, or materialize
5# what the loop needs in one pass. A get anywhere in the def is reported,
6# one in a base arm that runs once included. A literal index of any size
7# (`List.get(.., xs, 0n)`, `5000n`) is exempt, as are laws and proofs (a def
8# with no type at all fills a law: it is a proof). A
9# `List.get` on a fixed table (a literal, a sized array, a constant
10# `List.replicate`) is `table`'s finding instead, so the two rules do not
11# both report that call. `String.get` is never `table`'s: it stays here. A
12# get that is the def's own self-call is exempt: the step of a def named
13# `List.get` or `String.get` itself (Base's), which walks one cell per call.
14import Base
15import bolt@1.17.0.0/src/src.bend as Src
16import bolt@1.17.0.0/src/finding.bend as F
17import bolt@1.17.0.0/src/syntax/lex.bend as Lex
18import bolt@1.17.0.0/src/syntax/tree.bend as Tree
19import bolt@1.17.0.0/src/rules/calls.bend as Calls
20import bolt@1.17.0.0/src/lazy/lazy.bend as Lazy
21import bolt@1.17.0.0/src/rules/suspicious/table.bend as Table
22
23# is the chain exactly one number?
24def literal(nn: Tree.Node) -> Bool:
25 match nn:
26 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
27 True{}
28 case other:
29 False{}
30
31# a fixed table is reported by `table`, not here
32def held(+list: Bool, coll: Tree.Node, +fixed: List<&2, String>) -> Bool:
33 match list:
34 case False{}:
35 False{}
36 case True{}:
37 Table.owns(coll, fixed)
38
39# is the call named get, and not the def's own (self)?
40def named(+tt: String, +self: String, +get: String) -> Bool:
41 Bool.and(String.eq(tt, get), Bool.not(String.eq(tt, self)))
42
43# every List.get / String.get call at a computed index, but self's own
44def walk(nn: Tree.Node, +path: String, +fixed: List<&2, String>, +self: String) -> List<&2, F.Finding>:
45 match nn:
46 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
47 +list = named(t, self, "List.get")
48 +as = Calls.args(kids)
49 +get = Bool.and(String.eq(o, "("), Bool.or(list, named(t, self, "String.get")))
50 +fire = Bool.and(get, Bool.and(Bool.not(literal(Calls.arg(as, Bool.pick(Nat, list, 3n, 1n)))),
51 Bool.not(held(list, Calls.arg(as, 2n), fixed))))
52 +more = List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(rest, path, fixed, self)])
53 Bool.pick(List<&2, F.Finding>, fire,
54 F.Finding{path, l, c, U32.from_nat(String.length(t)), "index",
55 t ++ " in a recursive def walks the list from its head on every step, which is quadratic; recurse over the list itself."} <> more,
56 more)
57 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
58 List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(rest, path, fixed, self)])
59 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
60 List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(body, path, fixed, self),
61 walk(rest, path, fixed, self)])
62 case Tree.NCons{h, rest}:
63 walk(rest, path, fixed, self)
64 case other:
65 Nil{}
66
67def check.go(
68 ds: List<&2, Calls.Def>,
69 +mods: List<&2, String>,
70 +path: String,
71 acc: List<&2, List<&2, F.Finding>>
72) -> List<&2, F.Finding>:
73 match ds:
74 case Nil{}:
75 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
76 case Con{Calls.Def{+name, +sig, +body}, rest}:
77 check.go(rest, mods, path,
78 Lazy.stop(List<&2, F.Finding>,
79 Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
80 _u => walk(body, path, Table.scope(body, mods), name)) <> acc)
81
82# the rule
83def check(ss: Src.Src) -> List<&2, F.Finding>:
84 Src.Src{path, text, toks, tree, bound, items} = ss
85 +ds = Calls.defs(tree)
86 check.go(ds, Table.modules(ds, []), path, [])