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