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. 23 import Base 24 import ../../src.bend as Src 25 import ../../finding.bend as F 26 import ../../syntax/lex.bend as Lex 27 import ../../syntax/tree.bend as Tree 28 import ../../lazy/lazy.bend as Lazy 29 import ../calls.bend as Calls 30 31 # every name a node calls, `f(..)`, at any depth 32 def 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? 47 def 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 54 def 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) 66 def 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 73 def 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 85 def 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)? 93 def 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 110 def 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 149 def 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 164 def 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, [])