1	# rule rewalk: one straight piece of a def calls the same walk twice on the
2	# same argument, and one result is used only for a single value (a get of one
3	# index, one field, or a let whose name is only read that way) while the other
4	# result is kept whole. Take the value from that other result. The same
5	# argument is the same text with no let of any name it uses (`=` or `<-`,
6	# taking effect at the end of the let) between the two calls. A different
7	# case arm is a different path, and two narrow reads are left alone. A walk is
8	# a def of this file that loops, or a Base walk (`List.map` and the like).
9	# Laws and proofs do not run (a def with no type at all fills a law: it is a
10	# proof). This is not `twice`, which is duplicate literals in a list pattern.
11	import Base
12	import ../../src.bend as Src
13	import ../../finding.bend as F
14	import ../../syntax/lex.bend as Lex
15	import ../../syntax/tree.bend as Tree
16	import ../calls.bend as Calls
17	import ../../lazy/lazy.bend as Lazy
18	
19	# how the result of a call is used
20	type How is Data:
21	  HWide{}
22	  HSlot{}
23	  HLet{binder: String}
24	  HField{}
25	
26	# one expensive call
27	type Site is Data:
28	  Site{name: String, args: String, line: U32, col: U32, len: U32, how: How}
29	
30	# a narrow read and a wide read of one name
31	type Hit is Data:
32	  Hit{wide: Bool, slot: Bool}
33	
34	# where an accessor reads its collection
35	type Slot is Data:
36	  Slot{on: Bool, at: Nat}
37	
38	# a position a mark pass recorded
39	type Pos is Data:
40	  Pos{line: U32, col: U32}
41	
42	# the left of `=` : one name, and whether a group makes it a field
43	type Lhs is Data:
44	  Lhs{seen: Bool, extra: Bool, field: Bool, nm: String}
45	
46	# a let of one name, and where it takes effect
47	type Bind is Data:
48	  Bind{nm: String, line: U32, col: U32}
49	
50	# a let whose right-hand side is one call
51	type Note is Data:
52	  Note{line: U32, col: U32, how: How}
53	
54	# neither read
55	def none_hit() -> Hit:
56	  Hit{False{}, False{}}
57	
58	# either read from two results
59	def either(aa: Hit, +bb: Hit) -> Hit:
60	  Hit{+w1, +s1} = aa
61	  Hit{+w2, +s2} = bb
62	  Hit{Bool.or(w1, w2), Bool.or(s1, s2)}
63	
64	# a mention of the name: wide, unless this position is a narrow slot
65	def name_slot(+slot: Bool) -> Hit:
66	  match slot:
67	    case True{}:
68	      Hit{False{}, True{}}
69	    case False{}:
70	      Hit{True{}, False{}}
71	
72	# a mention of the name, or nothing when it is a different name
73	def name_hit(+same: Bool, +slot: Bool) -> Hit:
74	  match same:
75	    case False{}:
76	      none_hit()
77	    case True{}:
78	      name_slot(slot)
79	
80	# which argument a narrow accessor reads
81	def slot_pick(+list: Bool, +str: Bool, +arr: Bool) -> Slot:
82	  match list str arr:
83	    case True{} b c:
84	      Slot{True{}, 2n}
85	    case False{} True{} c:
86	      Slot{True{}, 0n}
87	    case False{} False{} True{}:
88	      Slot{True{}, 1n}
89	    case False{} False{} False{}:
90	      Slot{False{}, 0n}
91	
92	# List.get / head / last / length, String.get / length, Array.get; not List.set
93	def slot_of(+tt: String) -> Slot:
94	  slot_pick(
95	    List.contains(~String, ~String.eq, ["List.get", "List.head", "List.last", "List.length"], tt),
96	    Bool.or(String.eq(tt, "String.get"), String.eq(tt, "String.length")),
97	    String.eq(tt, "Array.get"))
98	
99	# after a comma, still inside the slot argument?
100	def step_is_zero(pp: Nat) -> Bool:
101	  match pp:
102	    case 0n:
103	      True{}
104	    case 1n+k:
105	      False{}
106	
107	# after a comma, is the next argument the slot?
108	def step_hot_live(left: Nat) -> Bool:
109	  match left:
110	    case 0n:
111	      False{}
112	    case 1n+p:
113	      step_is_zero(p)
114	
115	# the slot flag after a comma
116	def step_hot(+hot: Bool, +left: Nat, +live: Bool) -> Bool:
117	  match live:
118	    case False{}:
119	      hot
120	    case True{}:
121	      step_hot_live(left)
122	
123	# the arguments still to skip after a comma
124	def step_left_live(left: Nat) -> Nat:
125	  match left:
126	    case 0n:
127	      0n
128	    case 1n+p:
129	      p
130	
131	# the arguments still to skip after a comma
132	def step_left(+left: Nat, +live: Bool) -> Nat:
133	  match live:
134	    case False{}:
135	      left
136	    case True{}:
137	      step_left_live(left)
138	
139	# the chain is exactly one call
140	def as_open(+open: Bool, tok: Lex.Tok) -> Maybe<&2, Lex.Tok>:
141	  match open:
142	    case True{}:
143	      Some{tok}
144	    case False{}:
145	      None{}
146	
147	# the inside of one pair of parentheses, when it is exactly a call
148	def as_inside(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
149	  match nn:
150	    case Tree.NCons{Tree.Leaf{tok}, Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, Tree.NNil{}}}:
151	      as_open(String.eq(o, "("), tok)
152	    case other:
153	      None{}
154	
155	# a parenthesized call, or nothing
156	def as_wrapped(+paren: Bool, kids: Tree.Node) -> Maybe<&2, Lex.Tok>:
157	  match paren:
158	    case True{}:
159	      as_inside(kids)
160	    case False{}:
161	      None{}
162	
163	# the chain is exactly one call, or one pair of parentheses around one: its callee
164	def as_call(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
165	  match nn:
166	    case Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, +kids, close}, Tree.NNil{}}:
167	      as_wrapped(String.eq(o, "("), kids)
168	    case Tree.NCons{Tree.Leaf{tok}, Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, Tree.NNil{}}}:
169	      as_open(String.eq(o, "("), tok)
170	    case other:
171	      None{}
172	
173	# the callee, when this argument is exactly a call
174	def pos_of(mm: Maybe<&2, Lex.Tok>) -> List<&2, Pos>:
175	  match mm:
176	    case None{}:
177	      Nil{}
178	    case Some{Lex.Tok{k, t, l, c}}:
179	      [Pos{l, c}]
180	
181	# the collection argument's call, when this is a narrow accessor
182	def mark_slot(ss: Slot, +as: List<&2, Tree.Node>) -> List<&2, Pos>:
183	  Slot{on, at} = ss
184	  match on:
185	    case False{}:
186	      Nil{}
187	    case True{}:
188	      pos_of(as_call(Calls.arg(as, at)))
189	
190	# calls that sit in a narrow accessor's collection argument
191	def mark(nn: Tree.Node) -> List<&2, Pos>:
192	  match nn:
193	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
194	      +here = Lazy.stop(List<&2, Pos>, Bool.not(String.eq(o, "(")), [], _u => mark_slot(slot_of(t), Calls.args(kids)))
195	      List.concat(&2, Pos, [here, mark(kids), mark(rest)])
196	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
197	      List.concat(&2, Pos, [mark(kids), mark(rest)])
198	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, +kids, body}, rest}:
199	      List.concat(&2, Pos, [mark(kids), mark(rest)])
200	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
201	      List.concat(&2, Pos, [mark(kids), mark(body), mark(rest)])
202	    case Tree.NCons{h, rest}:
203	      mark(rest)
204	    case other:
205	      Nil{}
206	
207	# the name before a group is a narrow read, a callee, or an ordinary mention
208	def here_call(+call: Bool, +tt: String, +name: String, +hot: Bool) -> Hit:
209	  match call:
210	    case True{}:
211	      name_hit(String.eq(tt, name), False{})
212	    case False{}:
213	      name_hit(String.eq(tt, name), hot)
214	
215	# the name before a group is a narrow read, a callee, or an ordinary mention
216	def here_hit(+brack: Bool, +call: Bool, +tt: String, +name: String, +hot: Bool) -> Hit:
217	  match brack:
218	    case True{}:
219	      name_hit(String.eq(tt, name), True{})
220	    case False{}:
221	      here_call(call, tt, name, hot)
222	
223	# a bracket's inside is cold; a call's arguments start before the slot
224	def inner_hot_call(+call: Bool, +hot: Bool) -> Bool:
225	  match call:
226	    case True{}:
227	      False{}
228	    case False{}:
229	      hot
230	
231	# a bracket's inside is cold; a call's arguments start before the slot
232	def inner_hot(+brack: Bool, +call: Bool, +hot: Bool) -> Bool:
233	  match brack:
234	    case True{}:
235	      False{}
236	    case False{}:
237	      inner_hot_call(call, hot)
238	
239	# the argument index a slot reads
240	def slot_at(ss: Slot) -> Nat:
241	  Slot{on, at} = ss
242	  at
243	
244	# the slot index of a call; a bracket has none
245	def inner_left_call(+call: Bool, +tt: String) -> Nat:
246	  match call:
247	    case True{}:
248	      slot_at(slot_of(tt))
249	    case False{}:
250	      0n
251	
252	# the slot index of a call; a bracket has none
253	def inner_left(+brack: Bool, +call: Bool, +tt: String) -> Nat:
254	  match brack:
255	    case True{}:
256	      0n
257	    case False{}:
258	      inner_left_call(call, tt)
259	
260	# whether an accessor has a collection argument
261	def slot_on(ss: Slot) -> Bool:
262	  Slot{on, at} = ss
263	  on
264	
265	# only a call's arguments count commas as separators
266	def inner_live_call(+call: Bool, +tt: String) -> Bool:
267	  match call:
268	    case True{}:
269	      slot_on(slot_of(tt))
270	    case False{}:
271	      False{}
272	
273	# only a call's arguments count commas as separators
274	def inner_live(+brack: Bool, +call: Bool, +tt: String) -> Bool:
275	  match brack:
276	    case True{}:
277	      False{}
278	    case False{}:
279	      inner_live_call(call, tt)
280	
281	# does the chain bind?
282	def has_eq(nn: Tree.Node) -> Bool:
283	  match nn:
284	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
285	      True{}
286	    case Tree.NCons{h, rest}:
287	      has_eq(rest)
288	    case other:
289	      False{}
290	
291	# a read counts only once the left of `=` is over
292	def hit_keep(skip: Bool, hh: Hit) -> Hit:
293	  match skip:
294	    case True{}:
295	      none_hit()
296	    case False{}:
297	      hh
298	
299	# inside a call, unless this chain is still the left of a let
300	def pick_hot(+skip: Bool, +brack: Bool, +call: Bool, +hot: Bool) -> Bool:
301	  match skip:
302	    case True{}:
303	      False{}
304	    case False{}:
305	      inner_hot(brack, call, hot)
306	
307	# inside a call, unless this chain is still the left of a let
308	def pick_left(+skip: Bool, +brack: Bool, +call: Bool, +tt: String) -> Nat:
309	  match skip:
310	    case True{}:
311	      0n
312	    case False{}:
313	      inner_left(brack, call, tt)
314	
315	# inside a call, unless this chain is still the left of a let
316	def pick_live(+skip: Bool, +brack: Bool, +call: Bool, +tt: String) -> Bool:
317	  match skip:
318	    case True{}:
319	      False{}
320	    case False{}:
321	      inner_live(brack, call, tt)
322	
323	# reads of the name. hot: this chain is a collection argument. live/left: commas
324	# count toward that argument. skip: ignore names until `=` (the left of a let)
325	def hits(nn: Tree.Node, +name: String, +hot: Bool, +left: Nat, +live: Bool, +skip: Bool) -> Hit:
326	  match nn:
327	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
328	      hits(rest, name, hot, left, live, False{})
329	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TComma{}, t, l, c}}, rest}:
330	      hits(rest, name, step_hot(hot, left, live), step_left(left, live), live, skip)
331	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
332	      +brack = String.eq(o, "[")
333	      +call = String.eq(o, "(")
334	      +here = hit_keep(skip, here_hit(brack, call, t, name, hot))
335	      +inn = hits(kids, name, pick_hot(skip, brack, call, hot), pick_left(skip, brack, call, t),
336	        pick_live(skip, brack, call, t), skip)
337	      +aft = hits(rest, name, hot, left, live, skip)
338	      either(here, either(inn, aft))
339	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
340	      either(hit_keep(skip, name_hit(String.eq(t, name), hot)), hits(rest, name, hot, left, live, skip))
341	    case Tree.NCons{Tree.Leaf{tok}, rest}:
342	      hits(rest, name, hot, left, live, skip)
343	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
344	      either(hits(kids, name, hot, 0n, False{}, skip), hits(rest, name, hot, left, live, skip))
345	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
346	      +eq = has_eq(kids)
347	      +inn = hits(kids, name, False{}, 0n, False{}, eq)
348	      +bod = hits(body, name, False{}, 0n, False{}, False{})
349	      +aft = hits(rest, name, hot, left, live, skip)
350	      either(inn, either(bod, aft))
351	    case Tree.NCons{h, rest}:
352	      hits(rest, name, hot, left, live, skip)
353	    case other:
354	      none_hit()
355	
356	# a let of one name is narrow when that name is only read narrowly
357	def narrow_let(hh: Hit) -> Bool:
358	  Hit{wide, slot} = hh
359	  Bool.and(slot, Bool.not(wide))
360	
361	# a slot or a field is narrow; a wide use is not; a let depends on the name's reads
362	def narrow(hh: How, +body: Tree.Node) -> Bool:
363	  match hh:
364	    case HWide{}:
365	      False{}
366	    case HSlot{}:
367	      True{}
368	    case HField{}:
369	      True{}
370	    case HLet{+binder}:
371	      narrow_let(hits(body, binder, False{}, 0n, False{}, False{}))
372	
373	# every name a node calls
374	def called(nn: Tree.Node) -> List<&2, String>:
375	  match nn:
376	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
377	      +more = List.concat(&2, String, [called(kids), called(rest)])
378	      Bool.pick(List<&2, String>, String.eq(o, "("), t <> more, more)
379	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
380	      List.concat(&2, String, [called(kids), called(rest)])
381	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
382	      List.concat(&2, String, [called(kids), called(body), called(rest)])
383	    case Tree.NCons{h, rest}:
384	      called(rest)
385	    case other:
386	      Nil{}
387	
388	# does the list hold a name the set has?
389	def any_of(cs: List<&2, String>, +set: List<&2, String>) -> Bool:
390	  match cs:
391	    case Nil{}:
392	      False{}
393	    case Con{c, t}:
394	      Lazy.or_else(List.contains(~String, ~String.eq, set, c), _u => any_of(t, set))
395	
396	def loops.go(ds: List<&2, Calls.Def>, +acc: List<&2, String>) -> List<&2, String>:
397	  match ds:
398	    case Nil{}:
399	      acc
400	    case Con{Calls.Def{+name, sig, body}, rest}:
401	      +cs = called(body)
402	      +deep = Bool.or(List.contains(~String, ~String.eq, cs, name), any_of(cs, acc))
403	      loops.go(rest, Bool.pick(List<&2, String>, deep, name <> acc, acc))
404	
405	# defs of this file that loop
406	def loops(ds: List<&2, Calls.Def>) -> List<&2, String>:
407	  loops.go(ds, [])
408	
409	# Base walks a rewalk cares about
410	def heavy(+tt: String) -> Bool:
411	  List.contains(~String, ~String.eq, [
412	    "List.map", "List.filter", "List.sort", "List.foldl", "List.foldr", "List.reverse", "List.concat",
413	    "Array.map", "Array.to_list",
414	    "String.reverse", "String.to_upper", "String.to_lower", "String.to_list", "String.from_list"], tt)
415	
416	# a loop of this file, or a Base walk, and not this def itself
417	def expensive(+tt: String, +self: String, +lp: List<&2, String>) -> Bool:
418	  Bool.and(Bool.not(String.eq(tt, self)), Bool.or(heavy(tt), List.contains(~String, ~String.eq, lp, tt)))
419	
420	# the rest of the chain indexes the call
421	def indexed(rest: Tree.Node) -> Bool:
422	  match rest:
423	    case Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, tail}:
424	      String.eq(o, "[")
425	    case other:
426	      False{}
427	
428	# a slot when the call is indexed, otherwise wide, when the call is expensive
429	def how_of(+nar: Bool) -> How:
430	  match nar:
431	    case True{}:
432	      HSlot{}
433	    case False{}:
434	      HWide{}
435	
436	# a slot when the call is indexed, otherwise wide, when the call is expensive
437	def site_how(+mine: Bool, +nar: Bool) -> Maybe<&2, How>:
438	  match mine:
439	    case False{}:
440	      None{}
441	    case True{}:
442	      Some{how_of(nar)}
443	
444	# the call as a site, when it is one
445	def site_list(mm: Maybe<&2, How>, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> List<&2, Site>:
446	  match mm:
447	    case None{}:
448	      Nil{}
449	    case Some{how}:
450	      [Site{name, args, line, col, len, how}]
451	
452	# one site when this application is an expensive call
453	def open_site(
454	  +open: Bool,
455	  +indexed: Bool,
456	  +tt: String,
457	  +args: String,
458	  +line: U32,
459	  +col: U32,
460	  +len: U32,
461	  +self: String,
462	  +lp: List<&2, String>
463	) -> List<&2, Site>:
464	  match open:
465	    case False{}:
466	      Nil{}
467	    case True{}:
468	      site_list(site_how(expensive(tt, self, lp), indexed), tt, args, line, col, len)
469	
470	# every name under the node
471	def names(nn: Tree.Node, +acc: List<&2, String>) -> List<&2, String>:
472	  match nn:
473	    case Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}:
474	      t <> acc
475	    case Tree.Group{open, kids, close}:
476	      names(kids, acc)
477	    case Tree.Stmt{kind, kids, body}:
478	      names(body, names(kids, acc))
479	    case Tree.NCons{h, rest}:
480	      names(rest, names(h, acc))
481	    case other:
482	      acc
483	
484	# the names a let binds: every name left of its `=` or `<-`
485	def lhs_names(nn: Tree.Node, +acc: List<&2, String>) -> List<&2, String>:
486	  match nn:
487	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
488	      acc
489	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TBind{}, t, l, c}}, rest}:
490	      acc
491	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
492	      lhs_names(rest, t <> acc)
493	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
494	      lhs_names(rest, names(kids, acc))
495	    case Tree.NCons{h, rest}:
496	      lhs_names(rest, acc)
497	    case other:
498	      acc
499	
500	# where a let's names take effect: its last token, after the right-hand side
501	def last_pos(ts: List<&2, Lex.Tok>) -> Pos:
502	  match ts:
503	    case Nil{}:
504	      Pos{0, 0}
505	    case Con{Lex.Tok{k, t, +l, +c}, rest}:
506	      Pos{l, c}
507	
508	# one binding per name, at the let's end
509	def bind_all(ns: List<&2, String>, +line: U32, +col: U32, +acc: List<&2, Bind>) -> List<&2, Bind>:
510	  match ns:
511	    case Nil{}:
512	      acc
513	    case Con{+nm, rest}:
514	      bind_all(rest, line, col, Bind{nm, line, col} <> acc)
515	
516	# one binding per name, at this position
517	def bind_at(ns: List<&2, String>, pp: Pos, +acc: List<&2, Bind>) -> List<&2, Bind>:
518	  Pos{line, col} = pp
519	  bind_all(ns, line, col, acc)
520	
521	# the lets of one straight piece; a case arm is not part of it
522	def binds(nn: Tree.Node, +acc: List<&2, Bind>) -> List<&2, Bind>:
523	  match nn:
524	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, body}, rest}:
525	      binds(rest, acc)
526	    case Tree.NCons{Tree.Stmt{Tree.SLet{}, +kids, +body}, rest}:
527	      +here = bind_at(lhs_names(kids, []), last_pos(Tree.leaves.go(body, Tree.leaves.go(kids, []))), acc)
528	      binds(rest, binds(body, here))
529	    case Tree.NCons{Tree.Stmt{kind, kids, +body}, rest}:
530	      binds(rest, binds(body, acc))
531	    case Tree.NCons{h, rest}:
532	      binds(rest, acc)
533	    case other:
534	      acc
535	
536	# (l1, c1) comes before (l2, c2)
537	def before(+l1: U32, +c1: U32, +l2: U32, +c2: U32) -> Bool:
538	  Bool.or(U32.is_lt(l1, l2), Bool.and(U32.is_eq(l1, l2), U32.is_lt(c1, c2)))
539	
540	# how many lets of this name take effect before this position
541	def count(bs: List<&2, Bind>, +name: String, +line: U32, +col: U32) -> U32:
542	  match bs:
543	    case Nil{}:
544	      0
545	    case Con{Bind{+nm, +l, +c}, rest}:
546	      +more = count(rest, name, line, col)
547	      Bool.pick(U32, Bool.and(String.eq(nm, name), before(l, c, line, col)), (more + 1 : U32), more)
548	
549	# which binding of each name an argument reads: two calls with the same text
550	# read the same values only when no let of those names sits between them
551	def stamp(ns: List<&2, String>, +bs: List<&2, Bind>, +line: U32, +col: U32) -> String:
552	  match ns:
553	    case Nil{}:
554	      ""
555	    case Con{+nm, rest}:
556	      "|" ++ nm ++ "=" ++ U32.show(count(bs, nm, line, col)) ++ stamp(rest, bs, line, col)
557	
558	# every expensive call, wide unless the call is indexed on the spot; its
559	# arguments are their text and which let of each name they read
560	def gather(nn: Tree.Node, +self: String, +lp: List<&2, String>, +bs: List<&2, Bind>) -> List<&2, Site>:
561	  match nn:
562	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, +rest}}:
563	      +args = Tree.show(kids) ++ stamp(names(kids, []), bs, l, c)
564	      +here = open_site(String.eq(o, "("), indexed(rest), t, args, l, c,
565	        U32.from_nat(String.length(t)), self, lp)
566	      List.concat(&2, Site, [here, gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
567	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
568	      List.concat(&2, Site, [gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
569	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, +kids, body}, rest}:
570	      List.concat(&2, Site, [gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
571	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
572	      List.concat(&2, Site, [gather(kids, self, lp, bs), gather(body, self, lp, bs), gather(rest, self, lp, bs)])
573	    case Tree.NCons{h, rest}:
574	      gather(rest, self, lp, bs)
575	    case other:
576	      Nil{}
577	
578	# a second name on the left
579	def add_seen(+seen: Bool, +extra: Bool, +field: Bool, +nm: String, +tt: String) -> Lhs:
580	  match seen:
581	    case False{}:
582	      Lhs{True{}, extra, field, tt}
583	    case True{}:
584	      Lhs{True{}, True{}, field, nm}
585	
586	# names inside a field group, which makes the let a field read
587	def fold_names(nn: Tree.Node, st: Lhs) -> Lhs:
588	  match nn:
589	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
590	      Lhs{seen, extra, field, nm} = st
591	      fold_names(rest, add_seen(seen, extra, True{}, nm, t))
592	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
593	      fold_names(rest, fold_names(kids, st))
594	    case Tree.NCons{h, rest}:
595	      fold_names(rest, st)
596	    case other:
597	      st
598	
599	# the left of `=`
600	def eat(nn: Tree.Node, st: Lhs) -> Lhs:
601	  match nn:
602	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
603	      st
604	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
605	      Lhs{seen, extra, field, nm} = st
606	      eat(rest, add_seen(seen, extra, field, nm, t))
607	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
608	      eat(rest, fold_names(kids, st))
609	    case Tree.NCons{h, rest}:
610	      eat(rest, st)
611	    case other:
612	      st
613	
614	# a field when the left has a group, otherwise a let of that name
615	def note_how(+field: Bool, +nm: String) -> How:
616	  match field:
617	    case True{}:
618	      HField{}
619	    case False{}:
620	      HLet{nm}
621	
622	# nothing, and the maybe is consumed
623	def note_none(mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
624	  match mm:
625	    case other:
626	      None{}
627	
628	# the note when the right-hand side is a call
629	def note_some(+field: Bool, +nm: String, mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
630	  match mm:
631	    case Some{Lex.Tok{k, t, l, c}}:
632	      Some{Note{l, c, note_how(field, nm)}}
633	    case None{}:
634	      None{}
635	
636	# the note for a call, when the left is exactly one name
637	def note_rhs(+one: Bool, +field: Bool, +nm: String, mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
638	  match one:
639	    case False{}:
640	      note_none(mm)
641	    case True{}:
642	      note_some(field, nm, mm)
643	
644	# the tokens after `=`
645	def rhs_of(nn: Tree.Node) -> Tree.Node:
646	  match nn:
647	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
648	      rest
649	    case Tree.NCons{h, rest}:
650	      rhs_of(rest)
651	    case other:
652	      Tree.NNil{}
653	
654	# a let or a field binding of exactly one call
655	def note_from(st: Lhs, +rhs: Tree.Node) -> Maybe<&2, Note>:
656	  Lhs{seen, extra, field, +nm} = st
657	  note_rhs(Bool.and(seen, Bool.not(extra)), field, nm, as_call(rhs))
658	
659	# a let or a field binding of exactly one call
660	def note_st(+kids: Tree.Node) -> Maybe<&2, Note>:
661	  note_from(eat(kids, Lhs{False{}, False{}, False{}, ""}), rhs_of(kids))
662	
663	# one site, retagged when it is the let's call
664	def retag_one(+hit: Bool, how: How, +note: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
665	  match hit:
666	    case True{}:
667	      Site{name, args, line, col, len, note}
668	    case False{}:
669	      Site{name, args, line, col, len, how}
670	
671	# a note's line
672	def note_line(nn: Note) -> U32:
673	  Note{line, col, how} = nn
674	  line
675	
676	# a note's column
677	def note_col(nn: Note) -> U32:
678	  Note{line, col, how} = nn
679	  col
680	
681	# a note's how
682	def note_how_of(nn: Note) -> How:
683	  Note{line, col, how} = nn
684	  how
685	
686	# sites whose callee is this let's call take its how
687	def retag(sites: List<&2, Site>, +note: Note) -> List<&2, Site>:
688	  match sites:
689	    case Nil{}:
690	      Nil{}
691	    case Con{Site{+name, +args, +line, +col, +len, how}, rest}:
692	      +nl = note_line(note)
693	      +nc = note_col(note)
694	      +nh = note_how_of(note)
695	      +hit = Bool.and(U32.is_eq(line, nl), U32.is_eq(col, nc))
696	      retag_one(hit, how, nh, name, args, line, col, len) <> retag(rest, note)
697	
698	# retag when the statement is a let of a call
699	def retag_may(mm: Maybe<&2, Note>, sites: List<&2, Site>) -> List<&2, Site>:
700	  match mm:
701	    case None{}:
702	      sites
703	    case Some{note}:
704	      retag(sites, note)
705	
706	# lets of a call retag that call
707	def apply(nn: Tree.Node, sites: List<&2, Site>) -> List<&2, Site>:
708	  match nn:
709	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, body}, rest}:
710	      apply(rest, sites)
711	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
712	      apply(rest, apply(body, retag_may(note_st(kids), sites)))
713	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
714	      apply(rest, apply(kids, sites))
715	    case Tree.NCons{h, rest}:
716	      apply(rest, sites)
717	    case other:
718	      sites
719	
720	# this position was marked a collection argument
721	def pinned(+line: U32, +col: U32, ps: List<&2, Pos>) -> Bool:
722	  match ps:
723	    case Nil{}:
724	      False{}
725	    case Con{Pos{l, c}, rest}:
726	      +here = Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))
727	      +more = pinned(line, col, rest)
728	      Bool.or(here, more)
729	
730	# a wide call at a marked position becomes a slot; a let or a field stays
731	def pin_wide(how: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
732	  match how:
733	    case HWide{}:
734	      Site{name, args, line, col, len, HSlot{}}
735	    case other:
736	      Site{name, args, line, col, len, other}
737	
738	# a wide call at a marked position becomes a slot
739	def pin_how(+hit: Bool, how: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
740	  match hit:
741	    case False{}:
742	      Site{name, args, line, col, len, how}
743	    case True{}:
744	      pin_wide(how, name, args, line, col, len)
745	
746	# one site
747	def pin_one(ps: List<&2, Pos>, ss: Site) -> Site:
748	  Site{+name, +args, +line, +col, +len, how} = ss
749	  pin_how(pinned(line, col, ps), how, name, args, line, col, len)
750	
751	# marked collection arguments become slots
752	def pin(+ps: List<&2, Pos>, sites: List<&2, Site>) -> List<&2, Site>:
753	  match sites:
754	    case Nil{}:
755	      Nil{}
756	    case Con{s, rest}:
757	      pin_one(ps, s) <> pin(ps, rest)
758	
759	# a site, with whether its result is read for a single value over the piece
760	type Rated is Data:
761	  Rated{site: Site, nar: Bool}
762	
763	# one site, rated: the piece is walked for it here, once
764	def rate_one(ss: Site, +body: Tree.Node) -> Rated:
765	  Site{+name, +args, +line, +col, +len, +how} = ss
766	  Rated{Site{name, args, line, col, len, how}, narrow(how, body)}
767	
768	# each site, rated once, so the reports below compare ratings and never walk
769	# the piece again: a walk per site, not one per pair of sites
770	def rate(sites: List<&2, Site>, +body: Tree.Node) -> List<&2, Rated>:
771	  match sites:
772	    case Nil{}:
773	      Nil{}
774	    case Con{s, rest}:
775	      rate_one(s, body) <> rate(rest, body)
776	
777	# another site has the same callee and the same arguments, and keeps the whole result
778	def other_go(rs: List<&2, Rated>, +name: String, +args: String, +line: U32, +col: U32) -> Bool:
779	  match rs:
780	    case Nil{}:
781	      False{}
782	    case Con{Rated{Site{+nm, +as, +l, +c, len, how}, +nar}, rest}:
783	      +same = Bool.and(String.eq(nm, name), String.eq(as, args))
784	      +diff = Bool.not(Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)))
785	      +here = Bool.and(Bool.and(same, diff), Bool.not(nar))
786	      +more = other_go(rest, name, args, line, col)
787	      Bool.or(here, more)
788	
789	# a narrow site of this call already reported
790	def earlier(seen: List<&2, Rated>, +name: String, +args: String, +line: U32, +col: U32) -> Bool:
791	  match seen:
792	    case Nil{}:
793	      False{}
794	    case Con{Rated{Site{+nm, +as, +l, +c, len, how}, +nar}, rest}:
795	      +same = Bool.and(String.eq(nm, name), String.eq(as, args))
796	      +diff = Bool.not(Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)))
797	      +here = Bool.and(Bool.and(same, diff), nar)
798	      +more = earlier(rest, name, args, line, col)
799	      Bool.or(here, more)
800	
801	# the finding when no earlier narrow site took this call
802	def report_fresh(
803	  +prior: Bool,
804	  +name: String,
805	  +line: U32,
806	  +col: U32,
807	  +len: U32,
808	  +path: String
809	) -> List<&2, F.Finding>:
810	  match prior:
811	    case False{}:
812	      [F.Finding{path, line, col, len, "rewalk",
813	        name ++ " is called twice on the same argument, and one result is used only for a single value; take that value from the other result."}]
814	    case True{}:
815	      Nil{}
816	
817	# the finding, when this is the first narrow site of a duplicated call
818	def report_nar(
819	  +nar: Bool,
820	  +prior: Bool,
821	  +name: String,
822	  +line: U32,
823	  +col: U32,
824	  +len: U32,
825	  +path: String
826	) -> List<&2, F.Finding>:
827	  match nar:
828	    case False{}:
829	      Nil{}
830	    case True{}:
831	      report_fresh(prior, name, line, col, len, path)
832	
833	# the finding when a duplicate exists and this site is the first narrow one
834	def report_dup(
835	  +dup: Bool,
836	  +nar: Bool,
837	  +name: String,
838	  +args: String,
839	  +line: U32,
840	  +col: U32,
841	  +len: U32,
842	  +path: String,
843	  +seen: List<&2, Rated>
844	) -> List<&2, F.Finding>:
845	  match dup:
846	    case False{}:
847	      Nil{}
848	    case True{}:
849	      report_nar(nar, earlier(seen, name, args, line, col), name, line, col, len, path)
850	
851	# one site
852	def report_one(rr: Rated, +all: List<&2, Rated>, +path: String, +seen: List<&2, Rated>) -> List<&2, F.Finding>:
853	  Rated{ss, +nar} = rr
854	  Site{+name, +args, +line, +col, +len, how} = ss
855	  report_dup(other_go(all, name, args, line, col), nar, name, args, line, col, len, path, seen)
856	
857	# the first narrow site of each duplicated call
858	def report(rs: List<&2, Rated>, +all: List<&2, Rated>, +path: String, +seen: List<&2, Rated>) -> List<&2, F.Finding>:
859	  match rs:
860	    case Nil{}:
861	      Nil{}
862	    case Con{+r, rest}:
863	      +mine = report_one(r, all, path, seen)
864	      List.append(&2, F.Finding, mine, report(rest, all, path, r <> seen))
865	
866	# findings in one straight region; a case arm is not part of it
867	def local(+nn: Tree.Node, +self: String, +lp: List<&2, String>, +path: String) -> List<&2, F.Finding>:
868	  +rs = rate(pin(mark(nn), apply(nn, gather(nn, self, lp, binds(nn, [])))), nn)
869	  report(rs, rs, path, [])
870	
871	# each case arm on its own, so two arms are not one path
872	def visit(nn: Tree.Node, +self: String, +lp: List<&2, String>, +path: String) -> List<&2, F.Finding>:
873	  match nn:
874	    case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, +body}, rest}:
875	      +here = local(body, self, lp, path)
876	      List.concat(&2, F.Finding, [here, visit(body, self, lp, path), visit(rest, self, lp, path)])
877	    case Tree.NCons{Tree.Stmt{kind, +kids, +body}, rest}:
878	      List.concat(&2, F.Finding, [visit(kids, self, lp, path), visit(body, self, lp, path),
879	        visit(rest, self, lp, path)])
880	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
881	      List.concat(&2, F.Finding, [visit(kids, self, lp, path), visit(rest, self, lp, path)])
882	    case Tree.NCons{h, rest}:
883	      visit(rest, self, lp, path)
884	    case other:
885	      Nil{}
886	
887	def check.go(
888	  ds: List<&2, Calls.Def>,
889	  +lp: List<&2, String>,
890	  +path: String,
891	  acc: List<&2, List<&2, F.Finding>>
892	) -> List<&2, F.Finding>:
893	  match ds:
894	    case Nil{}:
895	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
896	    case Con{Calls.Def{+name, +sig, +body}, rest}:
897	      check.go(rest, lp, path,
898	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
899	          _u => List.concat(&2, F.Finding, [local(body, name, lp, path), visit(body, name, lp, path)])) <> acc)
900	
901	# the rule
902	def check(ss: Src.Src) -> List<&2, F.Finding>:
903	  Src.Src{path, text, toks, tree, bound, items} = ss
904	  +ds = Calls.defs(tree)
905	  check.go(ds, loops(ds), path, [])