1	# rule scan: a def that calls itself and, on the same step, hands a
2	# parameter it carries unchanged to a walk. Every step walks that list again:
3	# O(|A| * |B|), A what the def walks and B what it carries. Index it once
4	# outside the loop, or merge two sorted walks. A parameter is carried when
5	# every self-call passes it back as that same lone name in its own position
6	# (hoist's notion). A call is a name token (plain or dotted), then a `(`
7	# group, and what it walks is some of its arguments, counted from 0. A Base
8	# list search walks its list: argument 2 of `List.contains`, `List.find`,
9	# `List.filter` and `List.length`, 3 of `List.any` and `List.all`, 4 of
10	# `List.foldl` and `List.foldr`; a Base walk that rebuilds the list
11	# (`List.map`, `List.append`, ...) makes output, not a search, and is left
12	# alone. A def of this file walks, when it calls itself, its first live
13	# parameter that some self-call does not pass back unchanged (the one it
14	# shrinks), unless that parameter is a `Nat` or a `String` (a count, such as
15	# fuel, or a text); and each parameter its body, anywhere, passes as the lone
16	# name of an argument a call walks, of a Base search or of a def listed
17	# before it. A def of another module is not seen. A call reports when it is
18	# not a self-call and an argument it walks is exactly the lone name of a
19	# carried parameter: anything else there (a literal table, an expression, a
20	# name the step binds) is left alone. The step is what hoist reads as hot:
21	# the def's body, a case arm's body only when it calls the def, never a case
22	# pattern, and never the rest of a chain after `=>` (a lambda's body, a
23	# `Lazy` thunk, runs when it is called). Laws and proofs do not run (a def
24	# with no type at all fills a law: it is a proof), and a law file is skipped
25	# whole. One finding per call, on its callee.
26	import Base
27	import ../../src.bend as Src
28	import ../../paths.bend as Paths
29	import ../../finding.bend as F
30	import ../../syntax/lex.bend as Lex
31	import ../../syntax/tree.bend as Tree
32	import ../calls.bend as Calls
33	import ../../lazy/lazy.bend as Lazy
34	import ./hoist.bend as Hoist
35	
36	# a def of this file, and one argument it walks
37	type Walk is Data:
38	  Walk{name: String, at: Nat}
39	
40	# the answer as a list: none or one
41	def opt(mm: Maybe<&2, Nat>) -> List<&2, Nat>:
42	  match mm:
43	    case None{}:
44	      Nil{}
45	    case Some{at}:
46	      [at]
47	
48	# the list argument of a Base list search
49	def base_at(+tt: String) -> List<&2, Nat>:
50	  +two = List.contains(~String, ~String.eq, ["List.contains", "List.find", "List.filter", "List.length"], tt)
51	  +three = List.contains(~String, ~String.eq, ["List.any", "List.all"], tt)
52	  +four = List.contains(~String, ~String.eq, ["List.foldl", "List.foldr"], tt)
53	  Bool.pick(List<&2, Nat>, two, [2n], Bool.pick(List<&2, Nat>, three, [3n], Bool.pick(List<&2, Nat>, four, [4n], [])))
54	
55	# the arguments the defs of this file named tt walk
56	def file_at(ws: List<&2, Walk>, +tt: String) -> List<&2, Nat>:
57	  match ws:
58	    case Nil{}:
59	      Nil{}
60	    case Con{Walk{+nm, +at}, rest}:
61	      +more = file_at(rest, tt)
62	      Bool.pick(List<&2, Nat>, String.eq(nm, tt), at <> more, more)
63	
64	# the arguments a callee walks: a Base walk's list, and those the defs of this file record
65	def slots(+tt: String, +ws: List<&2, Walk>) -> List<&2, Nat>:
66	  List.append(&2, Nat, base_at(tt), file_at(ws, tt))
67	
68	# a leaf that is a plain name: its text
69	def name_tok(tok: Lex.Tok) -> Maybe<&2, String>:
70	  match tok:
71	    case Lex.Tok{Lex.TName{}, t, l, c}:
72	      Some{t}
73	    case other:
74	      None{}
75	
76	# the argument, when it is exactly one plain name
77	def name_of(nn: Tree.Node) -> Maybe<&2, String>:
78	  match nn:
79	    case Tree.NCons{Tree.Leaf{tok}, Tree.NNil{}}:
80	      name_tok(tok)
81	    case other:
82	      None{}
83	
84	# the name, when the list holds it
85	def keep_in(mm: Maybe<&2, String>, +names: List<&2, String>) -> Maybe<&2, String>:
86	  match mm:
87	    case None{}:
88	      None{}
89	    case Some{+nm}:
90	      Bool.pick(Maybe<&2, String>, List.contains(~String, ~String.eq, names, nm), Some{nm}, None{})
91	
92	# the first of two answers that has one
93	def first(aa: Maybe<&2, String>, bb: Maybe<&2, String>) -> Maybe<&2, String>:
94	  match aa:
95	    case None{}:
96	      bb
97	    case Some{nm}:
98	      Some{nm}
99	
100	# the first walked argument that is the lone name of one of the names
101	def found(ss: List<&2, Nat>, +as: List<&2, Tree.Node>, +names: List<&2, String>) -> Maybe<&2, String>:
102	  match ss:
103	    case Nil{}:
104	      None{}
105	    case Con{at, rest}:
106	      +more = found(rest, as, names)
107	      first(keep_in(name_of(Calls.arg(as, at)), names), more)
108	
109	# where a name sits among the parameter names
110	def index_of(ps: List<&2, String>, +nm: String, +ii: Nat) -> Maybe<&2, Nat>:
111	  match ps:
112	    case Nil{}:
113	      None{}
114	    case Con{+p, rest}:
115	      Lazy.stop(Maybe<&2, Nat>, String.eq(p, nm), Some{ii}, _u => index_of(rest, nm, 1n+ii))
116	
117	# where the name sits among the parameter names, when there is a name
118	def index_in(mm: Maybe<&2, String>, +ps: List<&2, String>) -> Maybe<&2, Nat>:
119	  match mm:
120	    case None{}:
121	      None{}
122	    case Some{+nm}:
123	      index_of(ps, nm, 0n)
124	
125	# the parameters that sit, as lone names, at walked arguments
126	def params_at(ss: List<&2, Nat>, +as: List<&2, Tree.Node>, +ps: List<&2, String>) -> List<&2, Nat>:
127	  match ss:
128	    case Nil{}:
129	      Nil{}
130	    case Con{at, rest}:
131	      +more = params_at(rest, as, ps)
132	      List.append(&2, Nat, opt(index_in(name_of(Calls.arg(as, at)), ps)), more)
133	
134	# a call's walked parameters, when its callee is a name and it is a call
135	def pass_hit(
136	  kk: Lex.TokKind,
137	  +open: Bool,
138	  +tt: String,
139	  kids: Tree.Node,
140	  +ps: List<&2, String>,
141	  +ws: List<&2, Walk>
142	) -> List<&2, Nat>:
143	  match kk:
144	    case Lex.TName{}:
145	      Lazy.stop(List<&2, Nat>, Bool.not(open), [], _u => params_at(slots(tt, ws), Calls.args(kids), ps))
146	    case Lex.TDotted{}:
147	      Lazy.stop(List<&2, Nat>, Bool.not(open), [], _u => params_at(slots(tt, ws), Calls.args(kids), ps))
148	    case other:
149	      Nil{}
150	
151	# the parameters a body passes, anywhere, as an argument some call walks
152	def passes(nn: Tree.Node, +ps: List<&2, String>, +ws: List<&2, Walk>) -> List<&2, Nat>:
153	  match nn:
154	    case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
155	      +own = pass_hit(k, String.eq(o, "("), t, kids, ps, ws)
156	      List.concat(&2, Nat, [own, passes(kids, ps, ws), passes(rest, ps, ws)])
157	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
158	      List.concat(&2, Nat, [passes(kids, ps, ws), passes(rest, ps, ws)])
159	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
160	      List.concat(&2, Nat, [passes(kids, ps, ws), passes(body, ps, ws), passes(rest, ps, ws)])
161	    case Tree.NCons{h, rest}:
162	      passes(rest, ps, ws)
163	    case other:
164	      Nil{}
165	
166	# a live parameter that some self-call does not pass back unchanged
167	def moves(+pp: Tree.Node, +carried: List<&2, String>) -> Bool:
168	  Bool.and(Calls.is_live(pp), Bool.not(List.contains(~String, ~String.eq, carried, Calls.param_name(pp))))
169	
170	# a count or a text: a loop down one scans no list
171	def scalar(+pp: Tree.Node) -> Bool:
172	  +hh = Calls.type_head(pp, False{})
173	  Bool.or(String.eq(hh, "Nat"), String.eq(hh, "String"))
174	
175	# where the parameter a def shrinks sits, unless it is a count or a text
176	def place(+pp: Tree.Node, +ii: Nat) -> Maybe<&2, Nat>:
177	  Bool.pick(Maybe<&2, Nat>, scalar(pp), None{}, Some{ii})
178	
179	def own.go(ps: List<&2, Tree.Node>, +carried: List<&2, String>, +ii: Nat) -> Maybe<&2, Nat>:
180	  match ps:
181	    case Nil{}:
182	      None{}
183	    case Con{+p, rest}:
184	      +here = moves(p, carried)
185	      Lazy.stop(Maybe<&2, Nat>, here, place(p, ii), _u => own.go(rest, carried, 1n+ii))
186	
187	# where the parameter a def shrinks sits, when it calls itself and it is no count or text
188	def own(+sig: Tree.Node, +body: Tree.Node, +name: String) -> Maybe<&2, Nat>:
189	  Lazy.stop(Maybe<&2, Nat>, Bool.not(Calls.calls(body, name)), None{},
190	    _u => own.go(Calls.params(sig), Hoist.carried(sig, body, name), 0n))
191	
192	# one walk of the def for each argument
193	def tag(ns: List<&2, Nat>, +name: String, +ws: List<&2, Walk>) -> List<&2, Walk>:
194	  match ns:
195	    case Nil{}:
196	      ws
197	    case Con{at, rest}:
198	      Walk{name, at} <> tag(rest, name, ws)
199	
200	def walks.go(ds: List<&2, Calls.Def>, +ws: List<&2, Walk>) -> List<&2, Walk>:
201	  match ds:
202	    case Nil{}:
203	      ws
204	    case Con{Calls.Def{+name, +sig, +body}, rest}:
205	      +mine = List.append(&2, Nat, opt(own(sig, body, name)), passes(body, Calls.names(sig), ws))
206	      walks.go(rest, tag(mine, name, ws))
207	
208	# the defs of this file that walk, each with an argument it walks, in order
209	def walks(ds: List<&2, Calls.Def>) -> List<&2, Walk>:
210	  walks.go(ds, [])
211	
212	# the name of the parameter a def shrinks, "" for none
213	def lead.go(ps: List<&2, Tree.Node>, +carried: List<&2, String>) -> String:
214	  match ps:
215	    case Nil{}:
216	      ""
217	    case Con{+p, rest}:
218	      +here = moves(p, carried)
219	      Lazy.stop(String, here, Calls.param_name(p), _u => lead.go(rest, carried))
220	
221	# a finding on the callee, naming the carried list
222	def cite(
223	  mm: Maybe<&2, String>,
224	  +tt: String,
225	  +line: U32,
226	  +col: U32,
227	  +self: String,
228	  +lead: String,
229	  +path: String
230	) -> List<&2, F.Finding>:
231	  match mm:
232	    case None{}:
233	      Nil{}
234	    case Some{+pp}:
235	      [F.Finding{path, line, col, U32.from_nat(String.length(tt)), "scan",
236	        tt ++ " walks " ++ pp ++ " on every step of " ++ self ++ ", which carries it unchanged: that is O(|" ++ lead
237	          ++ "| * |" ++ pp ++ "|). Index it once outside the loop, or merge two sorted walks."}]
238	
239	# a hot call of a walk other than the def, a walked argument carried
240	def on_name(
241	  +hot: Bool,
242	  +open: Bool,
243	  +tt: String,
244	  +line: U32,
245	  +col: U32,
246	  kids: Tree.Node,
247	  +self: String,
248	  +ws: List<&2, Walk>,
249	  +carried: List<&2, String>,
250	  +lead: String,
251	  +path: String
252	) -> List<&2, F.Finding>:
253	  Lazy.stop(List<&2, F.Finding>, Bool.not(Bool.and(hot, Bool.and(open, Bool.not(String.eq(tt, self))))), [],
254	    _u => cite(found(slots(tt, ws), Calls.args(kids), carried), tt, line, col, self, lead, path))
255	
256	# a call's finding, when its callee is a name
257	def call_hit(
258	  kk: Lex.TokKind,
259	  +hot: Bool,
260	  +open: Bool,
261	  +tt: String,
262	  +line: U32,
263	  +col: U32,
264	  kids: Tree.Node,
265	  +self: String,
266	  +ws: List<&2, Walk>,
267	  +carried: List<&2, String>,
268	  +lead: String,
269	  +path: String
270	) -> List<&2, F.Finding>:
271	  match kk:
272	    case Lex.TName{}:
273	      on_name(hot, open, tt, line, col, kids, self, ws, carried, lead, path)
274	    case Lex.TDotted{}:
275	      on_name(hot, open, tt, line, col, kids, self, ws, carried, lead, path)
276	    case other:
277	      Nil{}
278	
279	# the walks of carried lists on a hot path
280	def walk(
281	  nn: Tree.Node,
282	  +self: String,
283	  +ws: List<&2, Walk>,
284	  +carried: List<&2, String>,
285	  +lead: String,
286	  +path: String,
287	  +hot: Bool
288	) -> List<&2, F.Finding>:
289	  match nn:
290	    case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
291	      +heat = Hoist.warm(hot, k)
292	      +own = call_hit(k, heat, String.eq(o, "("), t, l, c, kids, self, ws, carried, lead, path)
293	      +inn = walk(kids, self, ws, carried, lead, path, heat)
294	      +aft = walk(rest, self, ws, carried, lead, path, heat)
295	      List.concat(&2, F.Finding, [own, inn, aft])
296	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, t, l, c}}, rest}:
297	      walk(rest, self, ws, carried, lead, path, Hoist.warm(hot, k))
298	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
299	      List.concat(&2, F.Finding,
300	        [walk(kids, self, ws, carried, lead, path, hot), walk(rest, self, ws, carried, lead, path, hot)])
301	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, +body}, rest}:
302	      +arm = Bool.and(hot, Calls.calls(body, self))
303	      List.concat(&2, F.Finding, [walk(kids, self, ws, carried, lead, path, False{}),
304	        walk(body, self, ws, carried, lead, path, arm), walk(rest, self, ws, carried, lead, path, hot)])
305	    case Tree.NCons{Tree.Stmt{kind, kids, body}, rest}:
306	      List.concat(&2, F.Finding, [walk(kids, self, ws, carried, lead, path, hot),
307	        walk(body, self, ws, carried, lead, path, hot), walk(rest, self, ws, carried, lead, path, hot)])
308	    case Tree.NCons{h, rest}:
309	      walk(rest, self, ws, carried, lead, path, hot)
310	    case other:
311	      Nil{}
312	
313	# one def's walk, its carried parameters and the one it shrinks read once
314	def run(+sig: Tree.Node, +body: Tree.Node, +name: String, +ws: List<&2, Walk>, +path: String) -> List<&2, F.Finding>:
315	  +carried = Hoist.carried(sig, body, name)
316	  walk(body, name, ws, carried, lead.go(Calls.params(sig), carried), path, True{})
317	
318	def check.go(
319	  ds: List<&2, Calls.Def>,
320	  +ws: List<&2, Walk>,
321	  +path: String,
322	  acc: List<&2, List<&2, F.Finding>>
323	) -> List<&2, F.Finding>:
324	  match ds:
325	    case Nil{}:
326	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
327	    case Con{Calls.Def{+name, +sig, +body}, rest}:
328	      check.go(rest, ws, path,
329	        Lazy.stop(List<&2, F.Finding>,
330	          Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
331	          _u => run(sig, body, name, ws, path)) <> acc)
332	
333	# the findings over a file's defs, their walks read once
334	def check.on(+ds: List<&2, Calls.Def>, +path: String) -> List<&2, F.Finding>:
335	  check.go(ds, walks(ds), path, [])
336	
337	# the rule; a law file is skipped whole, before its walks are read
338	def check(ss: Src.Src) -> List<&2, F.Finding>:
339	  Src.Src{+path, text, toks, tree, bound, items} = ss
340	  Lazy.stop(List<&2, F.Finding>, Paths.is_law_file(path), [], _u => check.on(Calls.defs(tree), path))