src/rules/suspicious/unused.bend

bolt@1.27.0.0 · 260 lines · 28 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.27.0.0/src/src.bend as Src
13import bolt@1.27.0.0/src/lazy/lazy.bend as Lazy
14import bolt@1.27.0.0/src/finding.bend as F
15import bolt@1.27.0.0/src/syntax/bind.bend as Bind
16import bolt@1.27.0.0/src/syntax/tree.bend as Tree
17import bolt@1.27.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)