src/rules/suspicious/index.bend
bolt@1.12.0.0 · 79 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.
12import Base
13import bolt@1.12.0.0/src/src.bend as Src
14import bolt@1.12.0.0/src/finding.bend as F
15import bolt@1.12.0.0/src/syntax/lex.bend as Lex
16import bolt@1.12.0.0/src/syntax/tree.bend as Tree
17import bolt@1.12.0.0/src/rules/calls.bend as Calls
18import bolt@1.12.0.0/src/lazy/lazy.bend as Lazy
19import bolt@1.12.0.0/src/rules/suspicious/table.bend as Table
20
21# is the chain exactly one number?
22def literal(nn: Tree.Node) -> Bool:
23 match nn:
24 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
25 True{}
26 case other:
27 False{}
28
29# a fixed table is reported by `table`, not here
30def held(+list: Bool, coll: Tree.Node, +fixed: List<&2, String>) -> Bool:
31 match list:
32 case False{}:
33 False{}
34 case True{}:
35 Table.owns(coll, fixed)
36
37# every List.get / String.get call at a computed index
38def walk(nn: Tree.Node, +path: String, +fixed: List<&2, String>) -> List<&2, F.Finding>:
39 match nn:
40 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
41 +list = String.eq(t, "List.get")
42 +as = Calls.args(kids)
43 +get = Bool.and(String.eq(o, "("), Bool.or(list, String.eq(t, "String.get")))
44 +fire = Bool.and(get, Bool.and(Bool.not(literal(Calls.arg(as, Bool.pick(Nat, list, 3n, 1n)))),
45 Bool.not(held(list, Calls.arg(as, 2n), fixed))))
46 +more = List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(rest, path, fixed)])
47 Bool.pick(List<&2, F.Finding>, fire,
48 F.Finding{path, l, c, U32.from_nat(String.length(t)), "index",
49 t ++ " in a recursive def walks the list from its head on every step, which is quadratic; recurse over the list itself."} <> more,
50 more)
51 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
52 List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(rest, path, fixed)])
53 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
54 List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(body, path, fixed), walk(rest, path, fixed)])
55 case Tree.NCons{h, rest}:
56 walk(rest, path, fixed)
57 case other:
58 Nil{}
59
60def check.go(
61 ds: List<&2, Calls.Def>,
62 +mods: List<&2, String>,
63 +path: String,
64 acc: List<&2, List<&2, F.Finding>>
65) -> List<&2, F.Finding>:
66 match ds:
67 case Nil{}:
68 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
69 case Con{Calls.Def{+name, +sig, +body}, rest}:
70 check.go(rest, mods, path,
71 Lazy.stop(List<&2, F.Finding>,
72 Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
73 _u => walk(body, path, Table.scope(body, mods))) <> acc)
74
75# the rule
76def check(ss: Src.Src) -> List<&2, F.Finding>:
77 Src.Src{path, text, toks, tree, bound, items} = ss
78 +ds = Calls.defs(tree)
79 check.go(ds, Table.modules(ds, []), path, [])