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(..) ->`).
11	import Base
12	import ../../src.bend as Src
13	import ../../lazy/lazy.bend as Lazy
14	import ../../finding.bend as F
15	import ../../syntax/bind.bend as Bind
16	import ../../syntax/tree.bend as Tree
17	import ../../syntax/lex.bend as Lex
18	
19	# the lines of these tokens, onto acc
20	def 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 `:`?
28	def 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?
36	def 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
45	def 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?
53	def 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(..) ->`
63	def 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
76	def 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
88	def 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?
98	def 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
108	def 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
116	type 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
123	type 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
129	def depth() -> Nat:
130	  16n
131	
132	# a line's way down the index: its low bits, lowest first
133	def 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
141	def 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
151	def 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
161	def 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
171	def 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
179	def 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
187	def 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?
195	def 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?
203	def 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
211	def 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
223	def 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
232	def 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	
235	def 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	
253	def 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
258	def 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)