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