1	# performance/deep_call_in_fork: a fork that calls a definition that calls itself outside a tail
2	# position. A value of a parallel let (`a b = f(x) g(y)`), or of a let just before it, calls a definition
3	# of the file whose call of itself is not the last thing it does.
4	# Heuristics: Bend gives a call of itself that is not a tail call a frame per call ("bend guide
5	# shaders"). In bend-lint's benchmark (Bend 2.0.36, on the CPU), such a call at each fork cut the speedup
6	# from 10x to 1.9x; the same definition with a tail call kept the 10x. In a raytracer that splits its
7	# rows that way at each of 9 fork levels, tail-recursive splits made it 4% to 8% faster on the CPU; in
8	# Bend's slash boss demo, the same change changed no timing, as its list was short. The JS lane is not
9	# measured. A tail position is the body of a definition, a case, or the rest of a block after its lets,
10	# through annotations. A definition with a parallel let is a fork tree: its calls of itself are the
11	# values of its forks, not frames, and it is not reported (Bend's matrix and Merkle benchmarks call such
12	# trees in their forks).
13	import Base
14	import bend-lint-api@0.2.1.0/linter/lint.bend as Lint
15	import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
16	
17	# Types
18	# =====
19	
20	# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
21	# position (as the check names them), and the definition, by the name the check gives it and as written.
22	type Owner is Data:
23	  Owner{deeps: List<&2, String>, target: String, name: String}
24	
25	# Functions
26	# =========
27	
28	# Whether `at` is the place of the last of `nodes`.
29	def is_last(nodes: List<&2, Lint.Node>, at: U32) -> Bool:
30	  U32.is_eq((at + 1: U32), U32.from_nat(Lists.length(&2, Lint.Node, nodes)))
31	
32	# Whether the node below `path` is in a tail position, if it ends the node above it (`ends`): the body of a definition
33	# or a case, or the rest of a block after its lets, through annotations.
34	def is_tail(path: List<&2, Lint.Above>, ends: Bool) -> Bool:
35	  match path ends:
36	    case _ False{}:
37	      False{}
38	    case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} True{}:
39	      True{}
40	    case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest} True{}:
41	      is_tail(rest, True{})
42	    case Con{Lint.Above{Lint.Node{Lint.Match{}, n, s, k, f}, at}, rest} True{}:
43	      is_tail(rest, True{})
44	    case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, at}, rest} True{}:
45	      is_tail(rest, True{})
46	    case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, kids, f}, at}, rest} True{}:
47	      is_tail(rest, is_last(kids, at))
48	    case Con{Lint.Above{Lint.Node{Lint.Let{}, n, s, kids, f}, at}, rest} True{}:
49	      is_tail(rest, is_last(kids, at))
50	    case _ _:
51	      False{}
52	
53	# Whether a call of its definition to itself below `path` is outside a tail position.
54	def deep.of(recursive: Bool, path: List<&2, Lint.Above>) -> List<&2, Bool>:
55	  match recursive:
56	    case True{}:
57	      [Bool.not(is_tail(path, True{}))]
58	    case False{}:
59	      []
60	
61	def deep.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Bool>:
62	  deep.of(Lint.is_recursive(path, node), path)
63	
64	# Whether a definition with the nodes `k` counts, if it calls itself outside a tail position (`found`): each does if
65	# `forking`, else one without a parallel let.
66	def deep.if(found: Bool, forking: Bool, k: List<&2, Lint.Node>) -> Bool:
67	  match found forking:
68	    case False{} _:
69	      False{}
70	    case True{} True{}:
71	      True{}
72	    case True{} False{}:
73	      Bool.not(Lint.forks(k, False{}))
74	
75	# The definitions among `nodes` that call themselves outside a tail position, as the check names them, onto `out`;
76	# with `forking` false, not those with a parallel let, whose such calls are the values of their forks.
77	def deep(nodes: List<&2, Lint.Node>, +forking: Bool, out: List<&2, String>) -> List<&2, String>:
78	  match nodes:
79	    case Nil{}:
80	      out
81	    case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +k, f}, rest}:
82	      deep(
83	        rest,
84	        forking,
85	        Lists.push(
86	          String,
87	          Lists.when(
88	            String,
89	            deep.if(
90	              List.contains(
91	                ~Bool,
92	                ~Bool.and,
93	                Lint.visit(
94	                  ~Unit,
95	                  ~Bool,
96	                  ~deep.visit,
97	                  Unit{},
98	                  [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
99	                ),
100	                True{}
101	              ),
102	              forking,
103	              k
104	            ),
105	            t
106	          ),
107	          out
108	        )
109	      )
110	    case Con{node, rest}:
111	      deep(rest, forking, out)
112	
113	def is_pattern(syntax: Lint.Syntax) -> Bool:
114	  match syntax:
115	    case Lint.PatternVariable{b, q}:
116	      True{}
117	    case Lint.PatternConstructor{t}:
118	      True{}
119	    case _:
120	      False{}
121	
122	def binders(nodes: List<&2, Lint.Node>, n: Nat) -> Nat:
123	  match nodes:
124	    case Nil{}:
125	      n
126	    case Con{Lint.Node{Lint.PatternVariable{b, q}, nm, s, k, f}, rest}:
127	      binders(rest, 1n+n)
128	    case Con{node, rest}:
129	      binders(rest, n)
130	
131	# Whether a let leads to a fork: it is one (it binds `many` names), or it binds one (`one`), and the last of `nodes`,
132	# the rest of its block, is a let that leads to one. The values of these lets are what a fork runs, or what runs just
133	# before it.
134	def leads(nodes: List<&2, Lint.Node>, many: Bool, one: Bool) -> Bool:
135	  match nodes many one:
136	    case _ True{} _:
137	      True{}
138	    case _ False{} False{}:
139	      False{}
140	    case Con{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, Nil{}} False{} True{}:
141	      +count = binders(kids, 0n)
142	      leads(kids, Nat.is_gt(count, 1n), Nat.is_eq(count, 1n))
143	    case Con{x, Nil{}} False{} True{}:
144	      False{}
145	    case Con{x, rest} False{} True{}:
146	      leads(rest, False{}, True{})
147	    case Nil{} False{} True{}:
148	      False{}
149	
150	# Whether `x`, the node at `at` under `parent`, is a value of a fork, or of a let just before one: not a binder, nor the
151	# rest of the block.
152	def is_value(x: Lint.Node, +parent: Lint.Node, at: U32) -> Bool:
153	  match x parent:
154	    case Lint.Node{s, n, sp, k, f} Lint.Node{ps, pn, psp, +kids, pf}:
155	      leads([parent], False{}, Bool.not(is_pattern(s)) && Bool.not(is_last(kids, at)))
156	
157	# Whether `x`, below `path`, or a node above it, is a value of a fork, or `found`.
158	def is_inside(path: List<&2, Lint.Above>, x: Lint.Node, found: Bool) -> Bool:
159	  match path found:
160	    case _ True{}:
161	      True{}
162	    case Nil{} False{}:
163	      False{}
164	    case Con{Lint.Above{+p, at}, rest} False{}:
165	      is_inside(rest, p, is_value(x, p, at))
166	
167	def message(+callee: String, loop: String) -> String:
168	  callee
169	    ++ " calls itself outside a tail position, so Bend gives each of its calls a frame, and "
170	    ++ loop
171	    ++ " calls it in a fork (a value of its parallel let, or of a let just before it). CPU: measured 4% to 8% faster for a raytracer after the fix; in a benchmark, such a call at each fork cut a 10x speedup to 1.9x. GPU: such a recursion in a `!` made a draw 2.3x slower (\"bend guide shaders\"). JS: not measured. Confidence: medium, as the cost grows with the depth of the recursion. Make "
172	    ++ callee
173	    ++ " tail-recursive with an accumulator, compute its value with native operations (such as U32.shln), or compute it once and pass it down as a parameter. If its input is short, expect this finding."
174	
175	# The finding about a call of a deep definition (if `deep`), when the call is in a fork.
176	def judge.deep(
177	  deep: Bool,
178	  path: List<&2, Lint.Above>,
179	  +node: Lint.Node,
180	  callee: String,
181	  name: String
182	) -> List<&2, Lint.Finding>:
183	  match deep:
184	    case True{}:
185	      Lint.finding(
186	        Lint.Information{},
187	        is_inside(path, node, False{}),
188	        Lint.Node.span(Some{node}),
189	        message(callee, name)
190	      )
191	    case False{}:
192	      []
193	
194	def judge.call(
195	  +owner: Owner,
196	  path: List<&2, Lint.Above>,
197	  node: Lint.Node,
198	  callee: String,
199	  +called: String
200	) -> List<&2, Lint.Finding>:
201	  match owner:
202	    case Owner{deeps, target, name}:
203	      judge.deep(
204	        List.contains(~String, ~String.eq, deeps, called) && Bool.not(String.eq(called, target)),
205	        path,
206	        node,
207	        callee,
208	        name
209	      )
210	
211	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
212	  match node:
213	    case Lint.Node{
214	      Lint.Application{},
215	      n,
216	      s,
217	      Con{Lint.Node{Lint.Reference{called}, callee, rs, rk, rf}, args},
218	      f
219	    }:
220	      judge.call(owner, path, node, callee, called)
221	    case _:
222	      []
223	
224	def defs(
225	  nodes: List<&2, Lint.Node>,
226	  +deeps: List<&2, String>,
227	  out: List<&2, Lint.Finding>
228	) -> List<&2, Lint.Finding>:
229	  match nodes:
230	    case Nil{}:
231	      List.reverse(&2, Lint.Finding, out)
232	    case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, k, f}, rest}:
233	      defs(
234	        rest,
235	        deeps,
236	        Lists.onto(
237	          &2,
238	          Lint.Finding,
239	          Lint.visit(
240	            ~Owner,
241	            ~Lint.Finding,
242	            ~visit,
243	            Owner{deeps, t, n},
244	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
245	          ),
246	          out
247	        )
248	      )
249	    case Con{node, rest}:
250	      defs(rest, deeps, out)
251	
252	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
253	  +nodes = Lint.Here.nodes(here)
254	  Lint.done(defs(nodes, deep(nodes, False{}, []), []))
255	
256	def rule() -> Lint.Rule:
257	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}