src/rules/suspicious/unused.bend
bolt@1.22.0.0 · 260 lines · 0 definitions
1# rule unused: a name bound by a let, a do-bind, a lambda, or as a parameter
2# is never used. A name read anywhere is a use, in a dependent arrow's types
3# too (`@+x: U32 -> S` reads `S`). Pattern binders are exempt: naming every
4# field of `Tok{k, t, l, c}` reads better than `_`. So are names starting
5# with `_`, erased parameters (`-x`), which exist to be unused, a law's `for`
6# names (hypotheses the proof takes by position), and every parameter of a
7# foreign def, which its C and JS bodies read: one whose body's first
8# statement is `import`, wherever its header's `->` and return type fall (a
9# header that does not end in `:` runs on through the body's statements up
10# to one that does, as `-> IO(T):` on the line after `def f(..) ->`).
11import Base
12import bolt@1.22.0.0/src/src.bend as Src
13import bolt@1.22.0.0/src/lazy/lazy.bend as Lazy
14import bolt@1.22.0.0/src/finding.bend as F
15import bolt@1.22.0.0/src/syntax/bind.bend as Bind
16import bolt@1.22.0.0/src/syntax/tree.bend as Tree
17import bolt@1.22.0.0/src/syntax/lex.bend as Lex
18
19# the lines of these tokens, onto acc
20def lines(ts: List<&2, Lex.Tok>, acc: List<&2, U32>) -> List<&2, U32>:
21 match ts:
22 case Nil{}:
23 acc
24 case Con{Lex.Tok{k, t, l, c}, rest}:
25 l <> lines(rest, acc)
26
27# is a token of this kind a `:`?
28def colon.kind(kk: Lex.TokKind) -> Bool:
29 match kk:
30 case Lex.TColon{}:
31 True{}
32 case other:
33 False{}
34
35# is the node a `:` leaf?
36def colon(nn: Tree.Node) -> Bool:
37 match nn:
38 case Tree.Leaf{Lex.Tok{k, _t, _l, _c}}:
39 colon.kind(k)
40 case other:
41 False{}
42
43# does a statement's own chain end in a `:` leaf? last: whether the node
44# before the chain did
45def foreign.ends(kids: Tree.Node, last: Bool) -> Bool:
46 match kids:
47 case Tree.NCons{h, t}:
48 foreign.ends(t, colon(h))
49 case other:
50 last
51
52# is the statement an import?
53def foreign.first(sk: Tree.StmtKind) -> Bool:
54 match sk:
55 case Tree.SImport{}:
56 True{}
57 case other:
58 False{}
59
60# does the body open with an import once the def's header is over? While the
61# header is open (its tokens so far do not end in `:`), each statement is more
62# of it: `-> IO(T):` on the line after `def f(..) ->`
63def foreign.opens(body: Tree.Node, open: Bool) -> Bool:
64 match body:
65 case Tree.NCons{Tree.Stmt{sk, kids, _b}, rest}:
66 match open:
67 case True{}:
68 foreign.opens(rest, Bool.not(foreign.ends(kids, False{})))
69 case False{}:
70 foreign.first(sk)
71 case other:
72 False{}
73
74# every header line of the defs whose body is `import "./x.c"`, wherever the
75# header's `->` and return type fall
76def foreign(root: Tree.Node) -> List<&2, U32>:
77 match root:
78 case Tree.NCons{Tree.Stmt{Tree.SDef{}, +kids, body}, rest}:
79 +more = foreign(rest)
80 +own = lines(Tree.leaves(kids), more)
81 Bool.pick(List<&2, U32>, foreign.opens(body, Bool.not(foreign.ends(kids, False{}))), own, more)
82 case Tree.NCons{other, rest}:
83 foreign(rest)
84 case other:
85 Nil{}
86
87# does a binder of this kind count? Erased and foreign parameters do not
88def reportable(kk: Bind.BindKind, +note: String, +line: U32, +foreign_lines: List<&2, U32>) -> Bool:
89 match kk:
90 case Bind.KLocal{}:
91 True{}
92 case Bind.KParam{}:
93 Bool.and(Bool.not(String.starts_with(note, "-")), Bool.not(List.contains(~U32, ~U32.is_eq, foreign_lines, line)))
94 case other:
95 False{}
96
97# is the binder at (line, col) the target of any use?
98def used(uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:
99 match uses:
100 case Nil{}:
101 False{}
102 case Con{Bind.Use{n, l, c, Bind.TLocal{+tl, +tc}}, rest}:
103 Lazy.or_else(Bool.and(U32.is_eq(tl, line), U32.is_eq(tc, col)), _u => used(rest, line, col))
104 case Con{other, rest}:
105 used(rest, line, col)
106
107# a binder's kind, for the message
108def what(kk: Bind.BindKind) -> String:
109 match kk:
110 case Bind.KParam{}:
111 "Parameter"
112 case other:
113 "Local"
114
115# a use's target, as the index holds it
116type Cell is Data:
117 Cell{line: U32, col: U32}
118
119# the targets of the uses, as a binary trie on the low bits of each target's
120# line, a leaf holding the cells that reach it. A hit in it is a use; a miss
121# is checked against the uses themselves (seen), so the index only has to be
122# sound, never complete, and a lookup is a walk down, not a scan of every use
123type Hits is Data:
124 HNone{}
125 HLeaf{cells: List<&2, Cell>}
126 HNode{lo: Hits, hi: Hits}
127
128# how many bits of a line the index branches on
129def depth() -> Nat:
130 16n
131
132# a line's way down the index: its low bits, lowest first
133def path(dd: Nat, +key: U32) -> List<&2, Bool>:
134 match dd:
135 case 0n:
136 Nil{}
137 case 1n+p:
138 U32.is_even(key) <> path(p, U32.shr(key))
139
140# the cells at a leaf, none elsewhere
141def hits.cells(hh: Hits) -> List<&2, Cell>:
142 match hh:
143 case HNone{}:
144 Nil{}
145 case HLeaf{cells}:
146 cells
147 case HNode{_lo, _hi}:
148 Nil{}
149
150# a node's low half, empty elsewhere
151def hits.lo(hh: Hits) -> Hits:
152 match hh:
153 case HNone{}:
154 HNone{}
155 case HLeaf{_cells}:
156 HNone{}
157 case HNode{lo, _hi}:
158 lo
159
160# a node's high half, empty elsewhere
161def hits.hi(hh: Hits) -> Hits:
162 match hh:
163 case HNone{}:
164 HNone{}
165 case HLeaf{_cells}:
166 HNone{}
167 case HNode{_lo, hi}:
168 hi
169
170# the half of a node a bit goes down, empty elsewhere
171def hits.near(bb: Bool, hh: Hits) -> Hits:
172 match bb:
173 case True{}:
174 hits.lo(hh)
175 case False{}:
176 hits.hi(hh)
177
178# a node whose half down a bit is sub, and the other half far
179def hits.join(bb: Bool, sub: Hits, far: Hits) -> Hits:
180 match bb:
181 case True{}:
182 HNode{sub, far}
183 case False{}:
184 HNode{far, sub}
185
186# the index with one more cell, down its path
187def put(pp: List<&2, Bool>, +hh: Hits, +cell: Cell) -> Hits:
188 match pp:
189 case Nil{}:
190 HLeaf{cell <> hits.cells(hh)}
191 case Con{+bb, rest}:
192 hits.join(bb, put(rest, hits.near(bb, hh), cell), hits.near(Bool.not(bb), hh))
193
194# is the cell at (line, col) among these?
195def hits.any(cs: List<&2, Cell>, +line: U32, +col: U32) -> Bool:
196 match cs:
197 case Nil{}:
198 False{}
199 case Con{Cell{l, c}, rest}:
200 Lazy.or_else(Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)), _u => hits.any(rest, line, col))
201
202# is the cell at (line, col) at the end of a path through the index?
203def find(pp: List<&2, Bool>, hh: Hits, +line: U32, +col: U32) -> Bool:
204 match pp:
205 case Nil{}:
206 hits.any(hits.cells(hh), line, col)
207 case Con{bb, rest}:
208 find(rest, hits.near(bb, hh), line, col)
209
210# a use's target into the index, when it is a binder of the file
211def index.one(tg: Bind.Target, +hh: Hits) -> Hits:
212 match tg:
213 case Bind.TLocal{+tl, tc}:
214 put(path(depth(), tl), hh, Cell{tl, tc})
215 case Bind.TItem{_n}:
216 hh
217 case Bind.TQual{_a, _n}:
218 hh
219 case Bind.TFree{}:
220 hh
221
222# the index of every use's target
223def index(uses: List<&2, Bind.Use>) -> Hits:
224 match uses:
225 case Nil{}:
226 HNone{}
227 case Con{Bind.Use{_n, _l, _c, tg}, rest}:
228 index.one(tg, index(rest))
229
230# is the binder at (line, col) the target of any use? The index answers a
231# hit at once; only a miss reads the uses
232def seen(hh: Hits, +uses: List<&2, Bind.Use>, +line: U32, +col: U32) -> Bool:
233 Lazy.or_else(find(path(depth(), line), hh, line, col), _u => used(uses, line, col))
234
235def check.go(
236 binds: List<&2, Bind.Bind>,
237 +hh: Hits,
238 +uses: List<&2, Bind.Use>,
239 +fl: List<&2, U32>,
240 +path: String
241) -> List<&2, F.Finding>:
242 match binds:
243 case Nil{}:
244 Nil{}
245 case Con{Bind.Bind{+name, +line, +col, +kind, note}, rest}:
246 +more = check.go(rest, hh, uses, fl, path)
247 +shown = reportable(kind, note, line, fl)
248 +hit = Bool.and(shown, Bool.not(String.starts_with(name, "_")))
249 Bool.pick(List<&2, F.Finding>, Lazy.and_then(hit, _u => Bool.not(seen(hh, uses, line, col))),
250 F.Finding{path, line, col, U32.from_nat(String.length(name)), "unused",
251 what(kind) ++ " " ++ name ++ " is never used."} <> more, more)
252
253def check.on(bb: Bind.Bound, fl: List<&2, U32>, path: String) -> List<&2, F.Finding>:
254 Bind.Bound{binds, +uses, scopes} = bb
255 check.go(binds, index(uses), uses, fl, path)
256
257# the rule
258def check(ss: Src.Src) -> List<&2, F.Finding>:
259 Src.Src{path, text, toks, tree, bound, items} = ss
260 check.on(bound, foreign(tree), path)