1	# rule thunk: a lambda whose body is exactly a self-call of its def, and
2	# whose parameter the call does not read, when it is the one lambda among the
3	# arguments of the call it is passed to: a `Unit -> T` thunk such as
4	# `Lazy.or_else(hit, _u => go(rest, k))`. The thunk is a closure allocated on
5	# every step, and the call inside it is not a tail call of the def, so the
6	# search leaves the loop each time round (bend 2.0.34, 500 misses over 100k
7	# cells: JS 2.40 s against 0.28 s, native 1.18 s against 0.76 s). Carry the
8	# test as a Bool into the next call instead, `go(rest, k, test(h))`, and match
9	# on it first: the step is then a tail call and compiles to a loop. `Lazy.*`
10	# stays right for guarding work that does not recurse. A dispatch, a call
11	# given two or more lambdas (`Lazy.either(T, c, _u => go(a), _v => go(b))`),
12	# is left alone: one Bool carried into the next call does not replace it.
13	# Exactly: in the kids of a group opened by `(` (its arguments: the kids split
14	# at their comma leaves), exactly one argument holding, among its own nodes
15	# and not inside a group, a leaf whose text is `=>`, four nodes in a row of
16	# those kids, a leaf whose kind is a name (the parameter: `_`, `_u`, `u`), a
17	# leaf whose text is `=>`, a leaf whose text is the def's name, and a `(`
18	# group; the kids end right after the group or go on with a comma; and no
19	# name leaf in the group, at any depth, has the parameter's text or starts
20	# with it and a dot (`u.x`). Groups are found at any depth, under statements
21	# and inside other groups, and a lambda inside another lambda's body is
22	# judged by the group it is passed to. One finding per such lambda, on the
23	# def's name. A body that does more than the call (`_u => go(t) ++ x`,
24	# `_u => Some{go(t)}`), a call of another def, a lambda whose parameter the
25	# call reads (an IO continuation `a => go(f, a)`), and a lambda that is not
26	# an argument of a call (`x = _u => go(t)`) are left alone; one that ignores
27	# its value (`_ => loop(n)`) is not, since the rule reads the shape and not
28	# the type. Laws and proofs never run: a law file, a proof file and a def
29	# that is a proof are exempt.
30	import Base
31	import ../../src.bend as Src
32	import ../../finding.bend as F
33	import ../../syntax/lex.bend as Lex
34	import ../../syntax/tree.bend as Tree
35	import ../calls.bend as Calls
36	import ../../lazy/lazy.bend as Lazy
37	
38	# does a name leaf under the node read the parameter: its text, or its text
39	# then a dot?
40	def reads(nn: Tree.Node, +pp: String) -> Bool:
41	  match nn:
42	    case Tree.Leaf{Lex.Tok{k, +t, _l, _c}}:
43	      Bool.and(Lex.is_name(k), Bool.or(String.eq(t, pp), String.starts_with(t, pp ++ ".")))
44	    case Tree.Group{_o, kids, _cl}:
45	      reads(kids, pp)
46	    case Tree.Stmt{_k, kids, body}:
47	      +a = reads(kids, pp)
48	      +b = reads(body, pp)
49	      Bool.or(a, b)
50	    case Tree.NCons{h, t}:
51	      +a = reads(h, pp)
52	      +b = reads(t, pp)
53	      Bool.or(a, b)
54	    case Tree.NNil{}:
55	      False{}
56	
57	# does the lambda's body end after the call: the chain ends, or a comma?
58	def ends(nn: Tree.Node) -> Bool:
59	  match nn:
60	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, _t, _l, _c}}, _rest}:
61	      Lex.is_comma(k)
62	    case Tree.NCons{_h, _rest}:
63	      False{}
64	    case _other:
65	      True{}
66	
67	# are the parts a thunk of a self-call: the lead (a name parameter the call
68	# does not read), `=>`, the def's name, a `(` group, then the body's end?
69	def hit(+lead: Bool, +arrow: Bool, +own: Bool, +call: Bool, +end: Bool) -> Bool:
70	  Bool.and(lead, Bool.and(arrow, Bool.and(own, Bool.and(call, end))))
71	
72	# the finding at the self-call's name
73	def cite(+ll: U32, +cc: U32, +name: String, +path: String) -> F.Finding:
74	  F.Finding{path, ll, cc, U32.from_nat(String.length(name)), "thunk",
75	    name ++ " calls itself inside a thunk, which allocates a closure and leaves the loop on every step; carry the test as a Bool into the next call (`go(rest, k, test(h))`) and match on it first, so the search stays a loop."}
76	
77	# after the parameter, `=>`, the name and its `(` group: the finding when
78	# they make a thunk of a self-call
79	def site.group(
80	  kp: Lex.TokKind,
81	  +pp: String,
82	  +aa: String,
83	  +nm: String,
84	  +ll: U32,
85	  +cc: U32,
86	  r3: Tree.Node,
87	  +name: String,
88	  +path: String
89	) -> List<&2, F.Finding>:
90	  match r3:
91	    case Tree.NCons{Tree.Group{Lex.Tok{_ko, +o, _lo, _co}, kids, _cl}, after}:
92	      +lead = Bool.and(Lex.is_name(kp), Bool.not(reads(kids, pp)))
93	      Bool.pick(List<&2, F.Finding>,
94	        hit(lead, String.eq(aa, "=>"), String.eq(nm, name), String.eq(o, "("), ends(after)),
95	        [cite(ll, cc, name, path)], [])
96	    case _other:
97	      []
98	
99	# after the parameter and `=>`: the leaf that names the call
100	def site.name(
101	  kp: Lex.TokKind,
102	  +pp: String,
103	  +aa: String,
104	  r2: Tree.Node,
105	  +name: String,
106	  +path: String
107	) -> List<&2, F.Finding>:
108	  match r2:
109	    case Tree.NCons{Tree.Leaf{Lex.Tok{_kn, +n, +l, +c}}, r3}:
110	      site.group(kp, pp, aa, n, l, c, r3, name, path)
111	    case _other:
112	      []
113	
114	# after the parameter: the leaf that should be `=>`
115	def site.lam(kp: Lex.TokKind, +pp: String, rest: Tree.Node, +name: String, +path: String) -> List<&2, F.Finding>:
116	  match rest:
117	    case Tree.NCons{Tree.Leaf{Lex.Tok{_ka, +a, _la, _ca}}, r2}:
118	      site.name(kp, pp, a, r2, name, path)
119	    case _other:
120	      []
121	
122	# the finding when a node and the chain after it open a thunk of a self-call
123	def site(hh: Tree.Node, rest: Tree.Node, +name: String, +path: String) -> List<&2, F.Finding>:
124	  match hh:
125	    case Tree.Leaf{Lex.Tok{kp, +p, _l, _c}}:
126	      site.lam(kp, p, rest, name, path)
127	    case _other:
128	      []
129	
130	# how many arguments of a group's kids, from here on, hold a `=>` leaf among
131	# their own nodes; seen: the argument under way does
132	def lams(nn: Tree.Node, +seen: Bool) -> Nat:
133	  match nn:
134	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, t, _l, _c}}, rest}:
135	      +comma = Lex.is_comma(k)
136	      Nat.add(Bool.pick(Nat, Bool.and(comma, seen), 1n, 0n),
137	        lams(rest, Bool.and(Bool.not(comma), Bool.or(seen, String.eq(t, "=>")))))
138	    case Tree.NCons{_h, rest}:
139	      lams(rest, seen)
140	    case _other:
141	      Bool.pick(Nat, seen, 1n, 0n)
142	
143	# is a group with this open and these kids a call given exactly one lambda?
144	def only(+oo: String, +kids: Tree.Node) -> Bool:
145	  Bool.and(String.eq(oo, "("), Nat.is_eq(lams(kids, False{}), 1n))
146	
147	# every thunk of a self-call under the node, at any depth; lone: the node is
148	# the rest of the kids of a call given exactly one lambda
149	def walk(nn: Tree.Node, +lone: Bool, +name: String, +path: String) -> List<&2, F.Finding>:
150	  match nn:
151	    case Tree.NCons{+h, +rest}:
152	      +here = site(h, rest, name, path)
153	      List.concat(&2, F.Finding, [Bool.pick(List<&2, F.Finding>, lone, here, []),
154	        walk(h, False{}, name, path), walk(rest, lone, name, path)])
155	    case Tree.Group{Lex.Tok{_k, +o, _l, _c}, +kids, _cl}:
156	      walk(kids, only(o, kids), name, path)
157	    case Tree.Stmt{_k, kids, body}:
158	      List.concat(&2, F.Finding, [walk(kids, False{}, name, path), walk(body, False{}, name, path)])
159	    case _other:
160	      Nil{}
161	
162	def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
163	  match ds:
164	    case Nil{}:
165	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
166	    case Con{Calls.Def{+name, +sig, body}, rest}:
167	      check.go(rest, path,
168	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [], _u => walk(body, False{}, name, path)) <> acc)
169	
170	# the rule
171	def check(ss: Src.Src) -> List<&2, F.Finding>:
172	  Src.Src{path, text, toks, tree, bound, items} = ss
173	  check.go(Calls.defs(tree), path, [])