1	# performance/missed_fork: calls of a definition to itself that could run in parallel, but run one after
2	# the other: two or more in one expression (`f(x) + f(y)`, `Node{f(x), f(y)}`), or in lets that follow
3	# each other (`l = f(x)`, then `r = f(y)`), where no call uses the result of another.
4	# Heuristics: Bend forks only the values of a parallel let (`a b = f(x) f(y)`), and its calls are
5	# independent, as Bend is pure. Whether a fork pays depends on how much work each call does, which the
6	# rule cannot see: measured on the CPU, forking a walk of a 1M-leaf tree, called 10 times, made it 2.5x
7	# faster; forking the same walk of 1k-leaf trees, called 100,000 times in a loop, made it 3.9x slower;
8	# forking a small expression tree that BendSR evaluates once per data point made it 230x slower. The JS
9	# lane runs on one thread, so it does not gain. Calls in different values of Bool.pick, or on the two
10	# sides of `&&` or `||`, are alternatives, not both needed (see performance/eager_branch): they do not
11	# count together. Calls written the same way compute the same value, so they are left to
12	# performance/repeated_call, which asks to compute it once (pow2(30): 0.1 s, against 0.6 s forked). It
13	# skips a definition that returns IO: its calls build effects, they do not run them. A call inside
14	# another call of itself, inside a lambda, or in a type, does not count.
15	import Base
16	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
17	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
18	import bend-lint-api@0.2.2.0/shared/strings.bend as Strings
19	
20	# Types
21	# =====
22	
23	# What judging one definition reads: its name as the check names it and as written, whether it returns IO (its calls
24	# build effects, they do not run them), and the file's text.
25	type Owner is Data:
26	  Owner{target: String, name: String, io: Bool, text: String}
27	
28	# A let that binds one name to a call of its definition to itself: where its binder starts, the binder as written, the
29	# binder, and the call.
30	type Bound is Data:
31	  Bound{from: U32, written: String, binder: U32, call: Lint.Node}
32	
33	# The lets of a run so far (last first), their binders, and the findings so far (last first).
34	type Run is Data:
35	  Run{bounds: List<&2, Bound>, binders: List<&2, U32>, out: List<&2, Lint.Finding>}
36	
37	# Functions
38	# =========
39	def trim.go(cs: List<&2, Char>) -> List<&2, Char>:
40	  match cs:
41	    case Con{' ', rest}:
42	      trim.go(rest)
43	    case _:
44	      cs
45	
46	def trimmed(s: String) -> String:
47	  String.from_list(List.reverse(&2, Char, trim.go(List.reverse(&2, Char, String.to_list(s)))))
48	
49	# Whether an application's nodes call Bool.pick, Bool.and or Bool.or: its arguments are alternatives, each an
50	# expression of its own.
51	def is_choice(kids: List<&2, Lint.Node>) -> Bool:
52	  match kids:
53	    case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
54	      List.contains(~String, ~String.eq, ["Bool.pick", "Bool.and", "Bool.or"], t)
55	    case _:
56	      False{}
57	
58	# Whether a node of this syntax ends the expression a call is in.
59	def is_boundary(syntax: Lint.Syntax) -> Bool:
60	  match syntax:
61	    case Lint.Application{}:
62	      False{}
63	    case Lint.Construction{t}:
64	      False{}
65	    case Lint.Annotation{}:
66	      False{}
67	    case _:
68	      True{}
69	
70	# Whether a definition's nodes say it returns IO, as written.
71	def returns_io(nodes: List<&2, Lint.Node>) -> Bool:
72	  match nodes:
73	    case Nil{}:
74	      False{}
75	    case Con{
76	      Lint.Node{Lint.Returns{}, n, s, Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, k}, f},
77	      rest
78	    }:
79	      String.eq(t, "IO")
80	    case Con{
81	      Lint.Node{
82	        Lint.Returns{},
83	        n,
84	        s,
85	        Con{
86	          Lint.Node{
87	            Lint.Application{},
88	            an,
89	            as,
90	            Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, ak},
91	            af
92	          },
93	          k
94	        },
95	        f
96	      },
97	      rest
98	    }:
99	      String.eq(t, "IO")
100	    case Con{node, rest}:
101	      returns_io(rest)
102	
103	# Whether an application's nodes call `target`: its function is a reference to it.
104	def calls.to(kids: List<&2, Lint.Node>, target: String) -> Bool:
105	  match kids:
106	    case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
107	      String.eq(t, target)
108	    case _:
109	      False{}
110	
111	# `out` with the span of a call of `target` (if `call`), where the call is.
112	def called.at(
113	  call: Bool,
114	  span: Maybe<&2, Lint.Span>,
115	  out: List<&2, Lint.Span>
116	) -> List<&2, Lint.Span>:
117	  match call:
118	    case True{}:
119	      Lists.push(Lint.Span, span, out)
120	    case False{}:
121	      out
122	
123	# Where the calls of `target` among `nodes` and under them are (onto `out`, last first), in the expression they start:
124	# a node that ends it starts another, and so does each argument of a choice (Bool.pick, Bool.and, Bool.or); a call
125	# inside another call of `target` does not count: none does if `nodes` are the parts of one, or of a choice (`inside`).
126	def calls(
127	  nodes: List<&2, Lint.Node>,
128	  +target: String,
129	  out: List<&2, Lint.Span>,
130	  inside: Bool
131	) -> List<&2, Lint.Span>:
132	  match nodes inside:
133	    case _ True{}:
134	      out
135	    case Nil{} False{}:
136	      out
137	    case Con{Lint.Node{Lint.Application{}, n, span, +kids, f}, rest} False{}:
138	      +call = calls.to(kids, target)
139	      calls(
140	        rest,
141	        target,
142	        calls(kids, target, called.at(call, span, out), call || is_choice(kids)),
143	        False{}
144	      )
145	    case Con{Lint.Node{Lint.Construction{t}, n, s, kids, f}, rest} False{}:
146	      calls(rest, target, calls(kids, target, out, False{}), False{})
147	    case Con{Lint.Node{Lint.Annotation{}, n, s, kids, f}, rest} False{}:
148	      calls(rest, target, calls(kids, target, out, False{}), False{})
149	    case Con{node, rest} False{}:
150	      calls(rest, target, out, False{})
151	
152	def texts(spans: List<&2, Lint.Span>, +text: String, out: List<&2, String>) -> List<&2, String>:
153	  match spans:
154	    case Nil{}:
155	      out
156	    case Con{s, rest}:
157	      texts(rest, text, Lint.Span.text(text, Some{s}) <> out)
158	
159	def names() -> List<&2, String>:
160	  ["a", "b", "c", "d", "e", "g", "h", "k"]
161	
162	# Fresh names for `n` values, as a parallel let binds them.
163	def binders(
164	  texts: List<&2, String>,
165	  ns: List<&2, String>,
166	  out: List<&2, String>
167	) -> List<&2, String>:
168	  match texts ns:
169	    case Con{t, rest} Con{n, more}:
170	      binders(rest, more, n <> out)
171	    case Con{t, rest} Nil{}:
172	      binders(rest, [], "x" <> out)
173	    case Nil{} _:
174	      List.reverse(&2, String, out)
175	
176	def quoted(texts: List<&2, String>, out: List<&2, String>) -> List<&2, String>:
177	  match texts:
178	    case Nil{}:
179	      List.reverse(&2, String, out)
180	    case Con{t, rest}:
181	      quoted(rest, ("`" ++ t ++ "`") <> out)
182	
183	def costs() -> String:
184	  "Bend runs calls in parallel only as the values of a parallel let. CPU, and GPU under a `!`: measured 2.5x faster for a few calls over a 1M-leaf tree, but 3.9x slower for 100,000 calls over 1k-leaf trees, and 230x slower for a small tree walked once per data point. JS: one thread, so no gain. Confidence: low, as it depends on how much work each call does."
185	
186	def expected() -> String:
187	  " If this definition runs once per item of a loop, or below a fork that already fills the cores, expect this finding."
188	
189	def count(texts: List<&2, String>) -> String:
190	  U32.show(U32.from_nat(Lists.length(&2, String, texts)))
191	
192	def Call.message(loop: String, +texts: List<&2, String>) -> String:
193	  loop
194	    ++ " calls itself "
195	    ++ count(texts)
196	    ++ " times in this expression ("
197	    ++ String.join(quoted(texts, []), ", ")
198	    ++ "), and these calls run one after the other. "
199	    ++ costs()
200	    ++ " To run them in parallel, bind them first with one parallel let of fresh names, such as `"
201	    ++ String.join(binders(texts, names(), []), " ")
202	    ++ " = "
203	    ++ String.join(texts, " ")
204	    ++ "`, and use those names here."
205	    ++ expected()
206	
207	# The finding about an expression at `span` that holds the calls at `spans` (last first), if they are two or more.
208	def alike.go(texts: List<&2, String>, +first: String, ok: Bool) -> Bool:
209	  match texts ok:
210	    case _ False{}:
211	      False{}
212	    case Nil{} True{}:
213	      True{}
214	    case Con{t, rest} True{}:
215	      alike.go(rest, first, String.eq(t, first))
216	
217	# Whether `texts`, the calls of one finding, are all written the same way.
218	def is_alike(texts: List<&2, String>) -> Bool:
219	  match texts:
220	    case Con{t, rest}:
221	      alike.go(rest, t, True{})
222	    case Nil{}:
223	      True{}
224	
225	def Call.finding.of(
226	  many: Bool,
227	  +spans: List<&2, Lint.Span>,
228	  span: Maybe<&2, Lint.Span>,
229	  +owner: Owner
230	) -> List<&2, Lint.Finding>:
231	  match many owner:
232	    case True{} Owner{target, name, io, +text}:
233	      Lint.finding(
234	        Lint.Hint{},
235	        Bool.not(is_alike(texts(spans, text, []))),
236	        span,
237	        Call.message(name, texts(spans, text, []))
238	      )
239	    case _ _:
240	      []
241	
242	def Call.finding(
243	  +spans: List<&2, Lint.Span>,
244	  span: Maybe<&2, Lint.Span>,
245	  owner: Owner
246	) -> List<&2, Lint.Finding>:
247	  Call.finding.of(Nat.is_gt(Lists.length(&2, Lint.Span, spans), 1n), spans, span, owner)
248	
249	# Whether the node below `path` starts an expression: the node above it ends one, or is a choice.
250	def starts(path: List<&2, Lint.Above>) -> Bool:
251	  match path:
252	    case Nil{}:
253	      True{}
254	    case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, kids, f}, at}, rest}:
255	      is_choice(kids)
256	    case Con{Lint.Above{Lint.Node{syntax, n, s, k, f}, at}, rest}:
257	      is_boundary(syntax)
258	
259	# The call of a let's value, if the value is a call of `target`, typed or not.
260	def called(value: Lint.Node, target: String) -> Maybe<&2, Lint.Node>:
261	  match value:
262	    case Lint.Node{Lint.Application{}, n, s, +kids, f}:
263	      Lists.when(Lint.Node, calls.to(kids, target), Lint.Node{Lint.Application{}, n, s, kids, f})
264	    case Lint.Node{
265	      Lint.Annotation{},
266	      n,
267	      s,
268	      Con{Lint.Node{Lint.Application{}, cn, cs, +kids, cf}, k},
269	      f
270	    }:
271	      Lists.when(Lint.Node, calls.to(kids, target), Lint.Node{Lint.Application{}, cn, cs, kids, cf})
272	    case _:
273	      None{}
274	
275	# A let that binds one name to a call of `target`, if `node` is one.
276	def bound(+node: Lint.Node, +owner: Owner) -> Maybe<&2, Bound>:
277	  match node owner:
278	    case Lint.Node{
279	      Lint.Destructure{q},
280	      n,
281	      s,
282	      Con{
283	        Lint.Node{Lint.PatternVariable{b, pq}, pn, Some{Lint.Span{p, +from, end}}, pk, pf},
284	        Con{value, Con{rest, Nil{}}}
285	      },
286	      f
287	    } Owner{target, name, io, text}:
288	      Maybe.map(
289	        &2,
290	        Lint.Node,
291	        Bound,
292	        call => Bound{from, trimmed(Strings.slice(text, from, end)), b, call},
293	        called(value, target)
294	      )
295	    case _ _:
296	      None{}
297	
298	# Whether a variable the file writes, of one of `binders`, is among `nodes` or under them, or `found`.
299	def uses(nodes: List<&2, Lint.Node>, +binders: List<&2, U32>, found: Bool) -> Bool:
300	  match nodes found:
301	    case _ True{}:
302	      True{}
303	    case Nil{} False{}:
304	      False{}
305	    case Con{Lint.Node{Lint.Variable{v}, n, Some{s}, k, f}, rest} False{}:
306	      uses(rest, binders, List.contains(~U32, ~U32.is_eq, binders, v))
307	    case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
308	      uses(rest, binders, uses(kids, binders, False{}))
309	
310	def Bound.texts(
311	  bounds: List<&2, Bound>,
312	  +text: String,
313	  written: List<&2, String>,
314	  called: List<&2, String>
315	) -> List<&2, String>
316	  & List<&2, String>:
317	  match bounds:
318	    case Nil{}:
319	      (written, called)
320	    case Con{Bound{f, w, b, Lint.Node{s, n, span, k, fs}}, rest}:
321	      Bound.texts(rest, text, w <> written, Lint.Span.text(text, span) <> called)
322	
323	def Run.lets(
324	  written: List<&2, String>,
325	  called: List<&2, String>,
326	  out: List<&2, String>
327	) -> List<&2, String>:
328	  match written called:
329	    case Con{w, rest} Con{c, more}:
330	      Run.lets(rest, more, ("`" ++ w ++ " = " ++ c ++ "`") <> out)
331	    case _ _:
332	      List.reverse(&2, String, out)
333	
334	def Run.message(loop: String, texts: List<&2, String> & List<&2, String>) -> String:
335	  match texts:
336	    case Tuple{+written, +called}:
337	      loop
338	        ++ " calls itself in "
339	        ++ count(called)
340	        ++ " lets that follow each other ("
341	        ++ String.join(Run.lets(written, called, []), ", ")
342	        ++ "), and these calls run one after the other. "
343	        ++ costs()
344	        ++ " To run them in parallel, merge the lets into one: `"
345	        ++ String.join(written, " ")
346	        ++ " = "
347	        ++ String.join(called, " ")
348	        ++ "`."
349	        ++ expected()
350	
351	# Whether the calls of a run of lets are all written the same way.
352	def Run.alike(texts: List<&2, String> & List<&2, String>) -> Bool:
353	  match texts:
354	    case Tuple{written, called}:
355	      is_alike(called)
356	
357	def Bound.from(bound: Maybe<&2, Bound>) -> U32:
358	  match bound:
359	    case Some{Bound{from, w, b, c}}:
360	      from
361	    case None{}:
362	      0
363	
364	# The finding about a run of lets (last first), if it has two lets or more: from the first's binder to the last's call.
365	def Run.finding(+bounds: List<&2, Bound>, +owner: Owner) -> List<&2, Lint.Finding>:
366	  match bounds owner:
367	    case Con{
368	      Bound{f, w, b, Lint.Node{s, n, Some{Lint.Span{path, beg, end}}, k, fs}},
369	      Con{second, more}
370	    } Owner{target, name, io, +text}:
371	      Lint.finding(
372	        Lint.Hint{},
373	        Bool.not(Run.alike(Bound.texts(bounds, text, [], []))),
374	        Some{Lint.Span{path, Bound.from(List.last(&2, Bound, bounds)), end}},
375	        Run.message(name, Bound.texts(bounds, text, [], []))
376	      )
377	    case _ _:
378	      []
379	
380	# The run after a let (`bound`, if it is one): the let joins it if its call uses no binder of the run; else the run
381	# ends, and the let starts the next.
382	def Run.add(bound: Maybe<&2, Bound>, owner: Owner, run: Run) -> Run:
383	  match bound run:
384	    case Some{Bound{+f, +w, +b, +c}} Run{+bounds, +binders, +out}:
385	      Bool.pick(
386	        Run,
387	        uses([c], binders, False{}),
388	        Run{
389	          [Bound{f, w, b, c}],
390	          [b],
391	          Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out)
392	        },
393	        Run{Bound{f, w, b, c} <> bounds, b <> binders, out}
394	      )
395	    case None{} Run{bounds, binders, out}:
396	      Run{[], [], Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out)}
397	
398	def Run.finding.end(run: Run, owner: Owner) -> List<&2, Lint.Finding>:
399	  match run:
400	    case Run{bounds, binders, out}:
401	      List.reverse(&2, Lint.Finding, Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out))
402	
403	# The findings about the runs of lets that follow each other from `node`, a let, after `run`: each next let is the rest
404	# of block of the one before, while its call uses no binder of the run.
405	def chain(node: Lint.Node, +owner: Owner, run: Run) -> List<&2, Lint.Finding>:
406	  match node:
407	    case Lint.Node{Lint.Destructure{q}, n, s, Con{binder, Con{value, Con{+rest, Nil{}}}}, f}:
408	      chain(
409	        rest,
410	        owner,
411	        Run.add(
412	          bound(Lint.Node{Lint.Destructure{q}, n, s, [binder, value, rest], f}, owner),
413	          owner,
414	          run
415	        )
416	      )
417	    case _:
418	      Run.finding.end(run, owner)
419	
420	# Whether a let below `path` goes on a run from the let above it: it is that let's rest of block, and that let binds
421	# one name to a call.
422	def follows(path: List<&2, Lint.Above>, owner: Owner) -> Bool:
423	  match path:
424	    case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, at}, rest}:
425	      U32.is_eq(
426	        (at + 1: U32),
427	        U32.from_nat(Lists.length(&2, Lint.Node, kids))
428	      )
429	        && Maybe.is_some(&2, Bound, bound(Lint.Node{Lint.Destructure{q}, n, s, kids, f}, owner))
430	    case _:
431	      False{}
432	
433	# The finding about the calls of the expression a node starts, if it starts one (`root`).
434	def roots(
435	  root: Bool,
436	  node: Lint.Node,
437	  span: Maybe<&2, Lint.Span>,
438	  +owner: Owner
439	) -> List<&2, Lint.Finding>:
440	  match root owner:
441	    case True{} Owner{target, name, io, text}:
442	      Call.finding(calls([node], target, [], False{}), span, owner)
443	    case _ _:
444	      []
445	
446	# The findings about the runs of lets from a node, if it starts one (`head`).
447	def lets(head: Bool, node: Lint.Node, owner: Owner) -> List<&2, Lint.Finding>:
448	  match head:
449	    case True{}:
450	      chain(node, owner, Run{[], [], []})
451	    case False{}:
452	      []
453	
454	# The findings at a node of a definition below `path`: about the calls of the expression it starts, and about the runs
455	# of lets from it, if it starts one.
456	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
457	  match owner node:
458	    case Owner{target, name, io, text} Lint.Node{syntax, n, span, k, f}:
459	      Lists.append(
460	        &2,
461	        Lint.Finding,
462	        roots(
463	          Bool.not(io) && Bool.not(is_boundary(syntax)) && starts(path) && Lint.is_live(path),
464	          node,
465	          span,
466	          owner
467	        ),
468	        lets(
469	          Maybe.is_some(
470	            &2,
471	            Bound,
472	            bound(node, owner)
473	          )
474	            && Bool.not(follows(path, owner))
475	            && Lint.is_live(path),
476	          node,
477	          owner
478	        )
479	      )
480	
481	def defs(
482	  nodes: List<&2, Lint.Node>,
483	  +text: String,
484	  out: List<&2, Lint.Finding>
485	) -> List<&2, Lint.Finding>:
486	  match nodes:
487	    case Nil{}:
488	      List.reverse(&2, Lint.Finding, out)
489	    case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, +k, f}, rest}:
490	      defs(
491	        rest,
492	        text,
493	        Lists.onto(
494	          &2,
495	          Lint.Finding,
496	          Lint.visit(
497	            ~Owner,
498	            ~Lint.Finding,
499	            ~visit,
500	            Owner{t, n, returns_io(k), text},
501	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
502	          ),
503	          out
504	        )
505	      )
506	    case Con{node, rest}:
507	      defs(rest, text, out)
508	
509	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
510	  Lint.done(defs(Lint.Here.nodes(here), Lint.Here.text(here), []))
511	
512	def rule() -> Lint.Rule:
513	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}