src/rules/suspicious/eager.bend

bolt@1.27.0.0 · 167 lines · 10 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.27.0.0/src/src.bend as Src
25import bolt@1.27.0.0/src/finding.bend as F
26import bolt@1.27.0.0/src/syntax/lex.bend as Lex
27import bolt@1.27.0.0/src/syntax/tree.bend as Tree
28import bolt@1.27.0.0/src/lazy/lazy.bend as Lazy
29import bolt@1.27.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, [])