src/rules/suspicious/thunk.bend

bolt@1.27.0.0 · 173 lines · 13 definitions

1# rule thunk: a lambda whose body is exactly a self-call of its def, and
2# whose parameter the call does not read, when it is the one lambda among the
3# arguments of the call it is passed to: a `Unit -> T` thunk such as
4# `Lazy.or_else(hit, _u => go(rest, k))`. The thunk is a closure allocated on
5# every step, and the call inside it is not a tail call of the def, so the
6# search leaves the loop each time round (bend 2.0.34, 500 misses over 100k
7# cells: JS 2.40 s against 0.28 s, native 1.18 s against 0.76 s). Carry the
8# test as a Bool into the next call instead, `go(rest, k, test(h))`, and match
9# on it first: the step is then a tail call and compiles to a loop. `Lazy.*`
10# stays right for guarding work that does not recurse. A dispatch, a call
11# given two or more lambdas (`Lazy.either(T, c, _u => go(a), _v => go(b))`),
12# is left alone: one Bool carried into the next call does not replace it.
13# Exactly: in the kids of a group opened by `(` (its arguments: the kids split
14# at their comma leaves), exactly one argument holding, among its own nodes
15# and not inside a group, a leaf whose text is `=>`, four nodes in a row of
16# those kids, a leaf whose kind is a name (the parameter: `_`, `_u`, `u`), a
17# leaf whose text is `=>`, a leaf whose text is the def's name, and a `(`
18# group; the kids end right after the group or go on with a comma; and no
19# name leaf in the group, at any depth, has the parameter's text or starts
20# with it and a dot (`u.x`). Groups are found at any depth, under statements
21# and inside other groups, and a lambda inside another lambda's body is
22# judged by the group it is passed to. One finding per such lambda, on the
23# def's name. A body that does more than the call (`_u => go(t) ++ x`,
24# `_u => Some{go(t)}`), a call of another def, a lambda whose parameter the
25# call reads (an IO continuation `a => go(f, a)`), and a lambda that is not
26# an argument of a call (`x = _u => go(t)`) are left alone; one that ignores
27# its value (`_ => loop(n)`) is not, since the rule reads the shape and not
28# the type. Laws and proofs never run: a law file, a proof file and a def
29# that is a proof are exempt.
30import Base
31import bolt@1.27.0.0/src/src.bend as Src
32import bolt@1.27.0.0/src/finding.bend as F
33import bolt@1.27.0.0/src/syntax/lex.bend as Lex
34import bolt@1.27.0.0/src/syntax/tree.bend as Tree
35import bolt@1.27.0.0/src/rules/calls.bend as Calls
36import bolt@1.27.0.0/src/lazy/lazy.bend as Lazy
37
38# does a name leaf under the node read the parameter: its text, or its text
39# then a dot?
40def reads(nn: Tree.Node, +pp: String) -> Bool:
41  match nn:
42    case Tree.Leaf{Lex.Tok{k, +t, _l, _c}}:
43      Bool.and(Lex.is_name(k), Bool.or(String.eq(t, pp), String.starts_with(t, pp ++ ".")))
44    case Tree.Group{_o, kids, _cl}:
45      reads(kids, pp)
46    case Tree.Stmt{_k, kids, body}:
47      +a = reads(kids, pp)
48      +b = reads(body, pp)
49      Bool.or(a, b)
50    case Tree.NCons{h, t}:
51      +a = reads(h, pp)
52      +b = reads(t, pp)
53      Bool.or(a, b)
54    case Tree.NNil{}:
55      False{}
56
57# does the lambda's body end after the call: the chain ends, or a comma?
58def ends(nn: Tree.Node) -> Bool:
59  match nn:
60    case Tree.NCons{Tree.Leaf{Lex.Tok{k, _t, _l, _c}}, _rest}:
61      Lex.is_comma(k)
62    case Tree.NCons{_h, _rest}:
63      False{}
64    case _other:
65      True{}
66
67# are the parts a thunk of a self-call: the lead (a name parameter the call
68# does not read), `=>`, the def's name, a `(` group, then the body's end?
69def hit(+lead: Bool, +arrow: Bool, +own: Bool, +call: Bool, +end: Bool) -> Bool:
70  Bool.and(lead, Bool.and(arrow, Bool.and(own, Bool.and(call, end))))
71
72# the finding at the self-call's name
73def cite(+ll: U32, +cc: U32, +name: String, +path: String) -> F.Finding:
74  F.Finding{path, ll, cc, U32.from_nat(String.length(name)), "thunk",
75    name ++ " calls itself inside a thunk, which allocates a closure and leaves the loop on every step; carry the test as a Bool into the next call (`go(rest, k, test(h))`) and match on it first, so the search stays a loop."}
76
77# after the parameter, `=>`, the name and its `(` group: the finding when
78# they make a thunk of a self-call
79def site.group(
80  kp: Lex.TokKind,
81  +pp: String,
82  +aa: String,
83  +nm: String,
84  +ll: U32,
85  +cc: U32,
86  r3: Tree.Node,
87  +name: String,
88  +path: String
89) -> List<&2, F.Finding>:
90  match r3:
91    case Tree.NCons{Tree.Group{Lex.Tok{_ko, +o, _lo, _co}, kids, _cl}, after}:
92      +lead = Bool.and(Lex.is_name(kp), Bool.not(reads(kids, pp)))
93      Bool.pick(List<&2, F.Finding>,
94        hit(lead, String.eq(aa, "=>"), String.eq(nm, name), String.eq(o, "("), ends(after)),
95        [cite(ll, cc, name, path)], [])
96    case _other:
97      []
98
99# after the parameter and `=>`: the leaf that names the call
100def site.name(
101  kp: Lex.TokKind,
102  +pp: String,
103  +aa: String,
104  r2: Tree.Node,
105  +name: String,
106  +path: String
107) -> List<&2, F.Finding>:
108  match r2:
109    case Tree.NCons{Tree.Leaf{Lex.Tok{_kn, +n, +l, +c}}, r3}:
110      site.group(kp, pp, aa, n, l, c, r3, name, path)
111    case _other:
112      []
113
114# after the parameter: the leaf that should be `=>`
115def site.lam(kp: Lex.TokKind, +pp: String, rest: Tree.Node, +name: String, +path: String) -> List<&2, F.Finding>:
116  match rest:
117    case Tree.NCons{Tree.Leaf{Lex.Tok{_ka, +a, _la, _ca}}, r2}:
118      site.name(kp, pp, a, r2, name, path)
119    case _other:
120      []
121
122# the finding when a node and the chain after it open a thunk of a self-call
123def site(hh: Tree.Node, rest: Tree.Node, +name: String, +path: String) -> List<&2, F.Finding>:
124  match hh:
125    case Tree.Leaf{Lex.Tok{kp, +p, _l, _c}}:
126      site.lam(kp, p, rest, name, path)
127    case _other:
128      []
129
130# how many arguments of a group's kids, from here on, hold a `=>` leaf among
131# their own nodes; seen: the argument under way does
132def lams(nn: Tree.Node, +seen: Bool) -> Nat:
133  match nn:
134    case Tree.NCons{Tree.Leaf{Lex.Tok{k, t, _l, _c}}, rest}:
135      +comma = Lex.is_comma(k)
136      Nat.add(Bool.pick(Nat, Bool.and(comma, seen), 1n, 0n),
137        lams(rest, Bool.and(Bool.not(comma), Bool.or(seen, String.eq(t, "=>")))))
138    case Tree.NCons{_h, rest}:
139      lams(rest, seen)
140    case _other:
141      Bool.pick(Nat, seen, 1n, 0n)
142
143# is a group with this open and these kids a call given exactly one lambda?
144def only(+oo: String, +kids: Tree.Node) -> Bool:
145  Bool.and(String.eq(oo, "("), Nat.is_eq(lams(kids, False{}), 1n))
146
147# every thunk of a self-call under the node, at any depth; lone: the node is
148# the rest of the kids of a call given exactly one lambda
149def walk(nn: Tree.Node, +lone: Bool, +name: String, +path: String) -> List<&2, F.Finding>:
150  match nn:
151    case Tree.NCons{+h, +rest}:
152      +here = site(h, rest, name, path)
153      List.concat(&2, F.Finding, [Bool.pick(List<&2, F.Finding>, lone, here, []),
154        walk(h, False{}, name, path), walk(rest, lone, name, path)])
155    case Tree.Group{Lex.Tok{_k, +o, _l, _c}, +kids, _cl}:
156      walk(kids, only(o, kids), name, path)
157    case Tree.Stmt{_k, kids, body}:
158      List.concat(&2, F.Finding, [walk(kids, False{}, name, path), walk(body, False{}, name, path)])
159    case _other:
160      Nil{}
161
162def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
163  match ds:
164    case Nil{}:
165      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
166    case Con{Calls.Def{+name, +sig, body}, rest}:
167      check.go(rest, path,
168        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [], _u => walk(body, False{}, name, path)) <> acc)
169
170# the rule
171def check(ss: Src.Src) -> List<&2, F.Finding>:
172  Src.Src{path, text, toks, tree, bound, items} = ss
173  check.go(Calls.defs(tree), path, [])