src/rules/suspicious/thunk.bend
bolt@1.19.0.0 · 173 lines · 0 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.19.0.0/src/src.bend as Src
32import bolt@1.19.0.0/src/finding.bend as F
33import bolt@1.19.0.0/src/syntax/lex.bend as Lex
34import bolt@1.19.0.0/src/syntax/tree.bend as Tree
35import bolt@1.19.0.0/src/rules/calls.bend as Calls
36import bolt@1.19.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, [])