1	# performance/dead_accumulator: a parameter of a loop that only grows and is never read: each use of it is
2	# an argument of the loop's call of itself, at its own place, with something added to it (inside a
3	# constructor, such as `x <> acc`), and the loop never matches it, returns it, or gives it to another
4	# call. It is built on every step and freed at the end.
5	# Heuristics: measured on bend-ml's BPE encode (bend-ml-bpe-tokenizer, as llama.bend uses it): its
6	# `done` keeps the rules applied so far, for its proofs, and `encode` drops it; a 48,900-entry list built
7	# and freed for each word was half of the time to tokenize 19 KB of text (26.1 s, against 11.5 s with
8	# `-done`), with the same ids and the same proofs. A parameter that the loop passes unchanged is not
9	# reported: it grows nothing. A use in a type or a proof does not count, as it does not run: the fix,
10	# an erased parameter (`-acc`), keeps it there. Only the loop's own calls are read; a call of the loop
11	# through another definition, or through a template, is not.
12	import Base
13	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
14	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
15	
16	# Types
17	# =====
18	
19	# What judging the uses of one parameter reads: its loop's name (as the check names it), the place of the parameter
20	# among the loop's parameters (as a call's arguments are), and its binder.
21	type Owner is Data:
22	  Owner{target: String, at: U32, binder: U32}
23	
24	# Functions
25	# =========
26	def message(+name: String, loop: String) -> String:
27	  name
28	    ++ " only grows: "
29	    ++ loop
30	    ++ " passes it to itself with something added, and nothing reads it, so Bend builds it on every step and frees it at the end. All lanes. Measured on the CPU, in bend-ml's BPE encode, where such a list, built per word, was half of the time: 26.1 s to tokenize 19 KB of text, against 11.5 s after the fix. Confidence: medium, as the gain is what building it costs. Erase it, with `-"
31	    ++ name
32	    ++ "`: the checker keeps it for proofs, and the compiler deletes it; or remove it. If it gets only a few small items, expect this finding."
33	
34	# How a use of the parameter below `path` ends: 0 if it is read (in anything but the loop's call of itself, at the
35	# parameter's place), 1 if it is passed there as it is, 2 if it is passed there with something added (`grown`).
36	def kind(path: List<&2, Lint.Above>, target: String, at: U32, grown: Bool) -> U32:
37	  match path:
38	    case Con{Lint.Above{Lint.Node{Lint.Construction{t}, n, s, k, f}, a}, rest}:
39	      kind(rest, target, at, True{})
40	    case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, a}, rest}:
41	      kind(rest, target, at, grown)
42	    case Con{
43	      Lint.Above{
44	        Lint.Node{
45	          Lint.Application{},
46	          n,
47	          s,
48	          Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
49	          f
50	        },
51	        a
52	      },
53	      rest
54	    }:
55	      Bool.pick(
56	        U32,
57	        String.eq(t, target) && U32.is_eq(a, (at + 1: U32)),
58	        Bool.pick(U32, grown, 2, 1),
59	        0
60	      )
61	    case _:
62	      0
63	
64	# How the parameter is used at a node, below `path`, if the node is a use of it in live code.
65	def use.visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, U32>:
66	  match owner node:
67	    case Owner{target, at, binder} Lint.Node{Lint.Variable{v}, n, s, k, f}:
68	      Bool.pick(
69	        List<&2, U32>,
70	        U32.is_eq(v, binder) && Lint.is_live(path),
71	        [kind(path, target, at, False{})],
72	        []
73	      )
74	    case _ _:
75	      []
76	
77	# Whether a parameter of quantity `q` that is used as `kinds` says is a dead accumulator: it is there at run time, it
78	# is only passed to the loop's own calls, and grows in one at least.
79	def is_dead(q: Lint.Quantity, +kinds: List<&2, U32>) -> Bool:
80	  match q:
81	    case Lint.Erased{}:
82	      False{}
83	    case Lint.Template{}:
84	      False{}
85	    case _:
86	      Bool.not(
87	        List.contains(~U32, ~U32.is_eq, kinds, 0)
88	      )
89	        && List.contains(~U32, ~U32.is_eq, kinds, 2)
90	
91	# The findings about the parameters among `nodes`, a definition's, onto `out`; `at` is the place of the first.
92	def params(
93	  nodes: List<&2, Lint.Node>,
94	  +loop: Lint.Node,
95	  +target: String,
96	  +name: String,
97	  +at: U32,
98	  out: List<&2, Lint.Finding>
99	) -> List<&2, Lint.Finding>:
100	  match nodes:
101	    case Nil{}:
102	      out
103	    case Con{Lint.Node{Lint.Parameter{b, q}, pn, ps, pk, pf}, rest}:
104	      params(
105	        rest,
106	        loop,
107	        target,
108	        name,
109	        (at + 1: U32),
110	        Lists.onto(
111	          &2,
112	          Lint.Finding,
113	          Lint.finding(
114	            Lint.Information{},
115	            is_dead(q, Lint.visit(~Owner, ~U32, ~use.visit, Owner{target, at, b}, [loop])),
116	            ps,
117	            message(pn, name)
118	          ),
119	          out
120	        )
121	      )
122	    case Con{node, rest}:
123	      params(rest, loop, target, name, at, out)
124	
125	def defs(nodes: List<&2, Lint.Node>, out: List<&2, Lint.Finding>) -> List<&2, Lint.Finding>:
126	  match nodes:
127	    case Nil{}:
128	      List.reverse(&2, Lint.Finding, out)
129	    case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, +k, f}, rest}:
130	      defs(rest, params(k, Lint.Node{Lint.Definition{t, u}, n, s, k, f}, t, n, 0, out))
131	    case Con{node, rest}:
132	      defs(rest, out)
133	
134	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
135	  Lint.done(defs(Lint.Here.nodes(here), []))
136	
137	def rule() -> Lint.Rule:
138	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}