src/rules/suspicious/eager.bend
bolt@1.23.0.0 · 167 lines · 0 definitions
1# rule eager: a branch of a `Bool.pick` calls a recursive def of the same
2# file. Bool.pick is an ordinary def, so both branch arguments are evaluated
3# before the call: the work in a branch runs whatever the condition says, and
4# the condition never saves it. `pick` catches the self-call and `strict` the
5# one under Bool.and/or; a call to a neighbour is the same bug and neither
6# sees it (a game's overlap test moved out of a pick branch took a scene from
7# 31 to 55 fps; one `gaps(..)` in a branch here ran on every file the linter
8# read, 88 s of a 100 s run). Bind the call above the pick (`+x = gaps(..)`),
9# or branch with `match` on the condition. For a search that recurses, carry
10# the test as a Bool into the next call (`go(rest, k, test(h))`) and match on
11# it first: the step stays a tail call and compiles to a loop, where a thunk
12# around the recursive call (`Lazy.or_else(hit, _u => go(rest))`) allocates a
13# closure and leaves the loop on every step (`thunk`, U015). The early exits
14# of src/lazy/lazy.bend (`Lazy.stop`, `Lazy.or_else`: the last argument is a
15# `Unit -> T` thunk, applied only on the branch that needs it) stay right for
16# work that does not recurse. Two things keep it off idiomatic code: only a
17# call to a def of this file counts, and only to one that loops (it calls
18# itself, or reaches something that does), since a Base call and a one-line
19# accessor are everywhere and cost nothing; only the branch arguments count,
20# not the type and the condition, which run whatever is written; and what
21# sits after a `=>` is a lambda's body, which the call does not run. The body
22# ends at the next comma of its group, so an argument after it counts again.
23import Base
24import bolt@1.23.0.0/src/src.bend as Src
25import bolt@1.23.0.0/src/finding.bend as F
26import bolt@1.23.0.0/src/syntax/lex.bend as Lex
27import bolt@1.23.0.0/src/syntax/tree.bend as Tree
28import bolt@1.23.0.0/src/lazy/lazy.bend as Lazy
29import bolt@1.23.0.0/src/rules/calls.bend as Calls
30
31# every name a node calls, `f(..)`, at any depth
32def called(nn: Tree.Node) -> List<&2, String>:
33 match nn:
34 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
35 +more = List.concat(&2, String, [called(kids), called(rest)])
36 Bool.pick(List<&2, String>, String.eq(o, "("), t <> more, more)
37 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
38 List.concat(&2, String, [called(kids), called(rest)])
39 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
40 List.concat(&2, String, [called(kids), called(body), called(rest)])
41 case Tree.NCons{h, rest}:
42 called(rest)
43 case other:
44 Nil{}
45
46# does the list hold a name the set has?
47def any_of(cs: List<&2, String>, +set: List<&2, String>) -> Bool:
48 match cs:
49 case Nil{}:
50 False{}
51 case Con{c, t}:
52 Lazy.or_else(List.contains(~String, ~String.eq, set, c), _u => any_of(t, set))
53
54def loops.go(ds: List<&2, Calls.Def>, +acc: List<&2, String>) -> List<&2, String>:
55 match ds:
56 case Nil{}:
57 acc
58 case Con{Calls.Def{+name, sig, body}, rest}:
59 +cs = called(body)
60 +deep = Bool.or(List.contains(~String, ~String.eq, cs, name), any_of(cs, acc))
61 loops.go(rest, Bool.pick(List<&2, String>, deep, name <> acc, acc))
62
63# the defs of the file that loop: one that calls itself, or that reaches one
64# that does (a def is defined above its use and there is no mutual recursion,
65# so one pass down the file settles it)
66def loops(ds: List<&2, Calls.Def>) -> List<&2, String>:
67 loops.go(ds, [])
68
69# the hot a leaf leaves behind: a `=>` clears it for the lambda's body; a
70# comma of a pick's own group moves to its next argument, hot from the third
71# on (0 the type, 1 the condition, 2 and 3 the branches), and a comma of any
72# other group returns it to keep; any other leaf leaves it as it was
73def work.hot(kk: Lex.TokKind, +hot: Bool, +seg: U32, +keep: Bool) -> Bool:
74 match kk:
75 case Lex.TLam{}:
76 False{}
77 case Lex.TComma{}:
78 +in_pick = U32.is_lt(seg, 9)
79 +next = Bool.pick(U32, in_pick, (seg + 1 : U32), seg)
80 Bool.pick(Bool, in_pick, Bool.not(U32.is_lt(next, 2)), keep)
81 case other:
82 hot
83
84# the argument a leaf leaves behind: a comma of a pick's own group moves on
85def work.seg(kk: Lex.TokKind, +seg: U32) -> U32:
86 match kk:
87 case Lex.TComma{}:
88 Bool.pick(U32, U32.is_lt(seg, 9), (seg + 1 : U32), seg)
89 case other:
90 seg
91
92# can the leaf name a call (it is neither a `=>` nor a comma)?
93def work.name(kk: Lex.TokKind) -> Bool:
94 match kk:
95 case Lex.TLam{}:
96 False{}
97 case Lex.TComma{}:
98 False{}
99 case other:
100 True{}
101
102# the work under a def's body: hot says the node sits in a branch argument of
103# a `Bool.pick` (so it runs whatever the condition), seg counts the arguments
104# of the pick whose group this chain is (0 the type, 1 the condition, 2 and 3
105# the branches; 9 for a chain that is not a pick's), and keep is what hot
106# returns to at the next comma of a chain that is not a pick's, so a `=>`
107# clears hot for the lambda's own body and not for the arguments after it. A
108# leaf moves the state by its kind (work.hot, work.seg); a `=>` or a comma
109# before a group names no call, so that group is walked as any other
110def work(
111 nn: Tree.Node,
112 +ns: List<&2, String>,
113 +self: String,
114 +path: String,
115 +hot: Bool,
116 +seg: U32,
117 +keep: Bool
118) -> List<&2, F.Finding>:
119 match nn:
120 case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
121 +now = work.hot(k, hot, seg, keep)
122 +call = Bool.and(work.name(k), String.eq(o, "("))
123 +is_pick = Bool.and(call, String.eq(t, "Bool.pick"))
124 +known = List.contains(~String, ~String.eq, ns, t)
125 +mine = Bool.and(Bool.not(String.eq(t, self)), known)
126 +report = Bool.and(now, Bool.and(call, mine))
127 +inner = Bool.and(now, Bool.not(is_pick))
128 +more = List.concat(&2, F.Finding,
129 [work(kids, ns, self, path, inner, Bool.pick(U32, is_pick, 0, 9), inner),
130 work(rest, ns, self, path, now, work.seg(k, seg), keep)])
131 Bool.pick(List<&2, F.Finding>, report,
132 F.Finding{path, l, c, U32.from_nat(String.length(t)), "eager",
133 t ++ " is called in a branch of Bool.pick, which evaluates both branches, so it runs whatever the condition; bind it above the pick, or branch with `match` on the condition."}
134 <> more,
135 more)
136 case Tree.NCons{Tree.Leaf{Lex.Tok{+k, t, l, c}}, rest}:
137 work(rest, ns, self, path, work.hot(k, hot, seg, keep), work.seg(k, seg), keep)
138 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
139 List.concat(&2, F.Finding, [work(kids, ns, self, path, hot, 9, hot), work(rest, ns, self, path, hot, seg, keep)])
140 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
141 List.concat(&2, F.Finding, [work(kids, ns, self, path, False{}, 9, False{}),
142 work(body, ns, self, path, False{}, 9, False{}),
143 work(rest, ns, self, path, hot, seg, keep)])
144 case Tree.NCons{h, rest}:
145 work(rest, ns, self, path, hot, seg, keep)
146 case other:
147 Nil{}
148
149def check.go(
150 ds: List<&2, Calls.Def>,
151 +ns: List<&2, String>,
152 +path: String,
153 acc: List<&2, List<&2, F.Finding>>
154) -> List<&2, F.Finding>:
155 match ds:
156 case Nil{}:
157 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
158 case Con{Calls.Def{+name, +sig, body}, rest}:
159 check.go(rest, ns, path,
160 Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
161 _u => work(body, ns, name, path, False{}, 9, False{})) <> acc)
162
163# the rule
164def check(ss: Src.Src) -> List<&2, F.Finding>:
165 Src.Src{path, text, toks, tree, bound, items} = ss
166 +ds = Calls.defs(tree)
167 check.go(ds, loops(ds), path, [])