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.
8	import Base
9	import ../../src.bend as Src
10	import ../../lazy/lazy.bend as Lazy
11	import ../../finding.bend as F
12	import ../../syntax/bind.bend as Bind
13	import ../../syntax/tree.bend as Tree
14	import ../../syntax/lex.bend as Lex
15	
16	# the lines of these tokens, onto acc
17	def 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
26	def 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
36	def 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?
46	def 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
56	def 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
64	type 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
71	type 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
77	def depth() -> Nat:
78	  16n
79	
80	# a line's way down the index: its low bits, lowest first
81	def 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
89	def 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
99	def 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
109	def 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
119	def 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
127	def 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
135	def 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?
143	def 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?
151	def 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
159	def 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
171	def 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
180	def 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	
183	def 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	
200	def 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
205	def 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)