1	# performance/eager_branch: a value that Bend computes even when it is not needed, and that runs a loop
2	# of the program to its end: a value of `Bool.pick`, or the right side of `&&` or `||`. These are
3	# functions, so their arguments are computed before they choose; a `match` runs only its chosen case.
4	# Heuristics: measured on the CPU, a Bool.pick whose unused value called a doubly recursive fib took 0.28
5	# s, against 0.055 s for a match. clang drops an unused loop that compiles to one native loop: under
6	# Bool.pick, a 2G-step tail loop cost nothing measurable, and under `&&`, a 400M-step one; the JS lane
7	# still runs it. A tail loop that called Base's List.contains, which applies a closure, at each step did
8	# not drop: 0.86 s for 40M steps, against 0.09 s for a match. So a call is reported when it is of a loop
9	# that calls itself outside a tail position, or of one under which a parallel let, a closure's
10	# application (not a `~` parameter's) or such a loop runs, or of a definition that calls such a loop,
11	# through the program's files. A loop's own call in `&&` or `||` is never a tail call. Base's
12	# definitions are not seen: a call of one counts as one native loop, so a loop slow only through Base is
13	# not reported. A call under a lambda counts, though it runs only when the lambda does. A value in a
14	# lambda, a type or an equation does not run, and is skipped; an erased argument (a proof's) is not told
15	# from a live one. A loop that is short in practice makes a finding that costs little to ignore.
16	import Base
17	import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
18	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
19	import bend-lint-api@0.2.2.0/shared/names.bend as Names
20	import bend-lint-api@0.2.2.0/shared/sets.bend as Sets
21	import ./deep_call_in_fork.bend as Deep
22	
23	# Types
24	# =====
25	
26	# A value Bend computes whether needed or not: what computes it ("pick", "&&" or "||"), and the value.
27	type Eager is Data:
28	  Eager{kind: String, value: Maybe<&2, Lint.Node>}
29	
30	# What judging the calls in one definition reads: the definitions of the program a call of which runs a loop to its end
31	# (see costly), and the definition, as the check names them.
32	type Owner is Data:
33	  Owner{costly: Set(), target: String}
34	
35	# Functions
36	# =========
37	# What an application with the nodes `kids` computes whether needed or not, as its node at `at` is one of its
38	# arguments: "pick" for a value of Bool.pick, "&&" or "||" for their right side, "" for none.
39	def eager(kids: List<&2, Lint.Node>, +at: U32) -> String:
40	  match kids:
41	    case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, Con{ty, Con{c, Con{x, Con{y, rest}}}}}:
42	      Bool.pick(
43	        String,
44	        String.eq(t, "Bool.pick") && (U32.is_eq(at, 3) || U32.is_eq(at, 4)),
45	        "pick",
46	        ""
47	      )
48	    case Con{Lint.Node{Lint.Reference{+t}, n, s, k, f}, Con{left, Con{right, Nil{}}}}:
49	      Bool.pick(
50	        String,
51	        U32.is_eq(at, 2),
52	        Bool.pick(
53	          String,
54	          String.eq(t, "Bool.and"),
55	          "&&",
56	          Bool.pick(String, String.eq(t, "Bool.or"), "||", "")
57	        ),
58	        ""
59	      )
60	    case _:
61	      ""
62	
63	def Eager.of(+kind: String, value: Maybe<&2, Lint.Node>) -> Maybe<&2, Eager>:
64	  Lists.when(Eager, Bool.not(String.eq(kind, "")), Eager{kind, value})
65	
66	# The eager value a call below `path` is in, if one is above it and no lambda comes between. `found` stops the walk
67	# once one is found.
68	def eagerly(path: List<&2, Lint.Above>, found: Maybe<&2, Eager>) -> Maybe<&2, Eager>:
69	  match path found:
70	    case _ Some{e}:
71	      Some{e}
72	    case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, +kids, f}, +at}, rest} None{}:
73	      eagerly(rest, Eager.of(eager(kids, at), List.get(&2, Lint.Node, kids, U32.to_nat(at))))
74	    case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} None{}:
75	      None{}
76	    case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} None{}:
77	      None{}
78	    case Con{a, rest} None{}:
79	      eagerly(rest, None{})
80	    case Nil{} None{}:
81	      None{}
82	
83	def why(+kind: String, +callee: String) -> String:
84	  Bool.pick(
85	    String,
86	    String.eq(kind, "pick"),
87	    "Bool.pick computes both of its values before it picks one, so this call of "
88	      ++ callee
89	      ++ " runs even when the condition picks the other value",
90	    kind
91	      ++ " computes its right side even when its left side decides the result ("
92	      ++ Bool.pick(String, String.eq(kind, "&&"), "False", "True")
93	      ++ "), so this call of "
94	      ++ callee
95	      ++ " runs even then"
96	  )
97	
98	def message(kind: String, +callee: String, own: Bool) -> String:
99	  why(
100	    kind,
101	    callee
102	  )
103	    ++ Bool.pick(
104	      String,
105	      own,
106	      ": it is the loop's own call, so the loop walks to its end instead of stopping where the condition decides",
107	      ""
108	    )
109	    ++ ". CPU and GPU: measured 5x slower than a match, for an unused call that calls itself outside a tail position. JS: computes both values too. Confidence: medium, as the cost is what the unneeded call computes. Choose with a match: pass the condition to a helper whose match runs only the needed value; inside a loop, where that helper would call the loop back (Bend refuses mutual recursion), pass the condition to the next call, and match on it there. If "
110	    ++ callee
111	    ++ " runs only a few steps here, expect this finding."
112	
113	def judged(eager: Maybe<&2, Eager>, callee: String, own: Bool) -> List<&2, Lint.Finding>:
114	  match eager:
115	    case Some{Eager{kind, value}}:
116	      Lint.finding(Lint.Information{}, True{}, Lint.Node.span(value), message(kind, callee, own))
117	    case None{}:
118	      []
119	
120	def looping(
121	  hit: Bool,
122	  path: List<&2, Lint.Above>,
123	  callee: String,
124	  own: Bool
125	) -> List<&2, Lint.Finding>:
126	  match hit:
127	    case True{}:
128	      judged(eagerly(path, None{}), callee, own)
129	    case False{}:
130	      []
131	
132	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
133	  match owner node:
134	    case Owner{
135	      costly,
136	      target
137	    } Lint.Node{
138	      Lint.Application{},
139	      n,
140	      s,
141	      Con{Lint.Node{Lint.Reference{+called}, callee, rs, rk, rf}, args},
142	      f
143	    }:
144	      looping(
145	        Sets.has(costly, called) && Lint.is_live(path),
146	        path,
147	        callee,
148	        String.eq(called, target)
149	      )
150	    case _ _:
151	      []
152	
153	def defs(
154	  nodes: List<&2, Lint.Node>,
155	  +costly: Set(),
156	  out: List<&2, Lint.Finding>
157	) -> List<&2, Lint.Finding>:
158	  match nodes:
159	    case Nil{}:
160	      List.reverse(&2, Lint.Finding, out)
161	    case Con{Lint.Node{Lint.Definition{+t, u}, n, s, k, f}, rest}:
162	      defs(
163	        rest,
164	        costly,
165	        Lists.onto(
166	          &2,
167	          Lint.Finding,
168	          Lint.visit(
169	            ~Owner,
170	            ~Lint.Finding,
171	            ~visit,
172	            Owner{costly, t},
173	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
174	          ),
175	          out
176	        )
177	      )
178	    case Con{node, rest}:
179	      defs(rest, costly, out)
180	
181	# The binders of the `~` parameters among a definition's nodes, onto `out`: a call of one is inlined, not a closure's.
182	def templates(nodes: List<&2, Lint.Node>, out: List<&2, U32>) -> List<&2, U32>:
183	  match nodes:
184	    case Nil{}:
185	      out
186	    case Con{Lint.Node{Lint.Parameter{b, Lint.Template{}}, n, s, k, f}, rest}:
187	      templates(rest, b <> out)
188	    case Con{node, rest}:
189	      templates(rest, out)
190	
191	# A closure's application: of a variable that no `~` parameter (`templates`) binds.
192	def applies.visit(
193	  +templates: List<&2, U32>,
194	  +path: List<&2, Lint.Above>,
195	  +node: Lint.Node
196	) -> List<&2, Unit>:
197	  match node:
198	    case Lint.Node{
199	      Lint.Application{},
200	      n,
201	      s,
202	      Con{Lint.Node{Lint.Variable{b}, vn, vs, vk, vf}, args},
203	      f
204	    }:
205	      Lists.push(
206	        Unit,
207	        Lists.when(Unit, Bool.not(List.contains(~U32, ~U32.is_eq, templates, b)), Unit{}),
208	        []
209	      )
210	    case _:
211	      []
212	
213	# Whether a definition's nodes apply a closure, or `found`.
214	def applies(+kids: List<&2, Lint.Node>, found: Bool) -> Bool:
215	  match found:
216	    case True{}:
217	      True{}
218	    case False{}:
219	      Bool.not(
220	        List.is_empty(
221	          &2,
222	          Unit,
223	          Lint.visit(~List<&2, U32>, ~Unit, ~applies.visit, templates(kids, []), kids)
224	        )
225	      )
226	
227	# The definitions among a file's `nodes` whose own body keeps them from compiling to a native loop, onto `out`: a
228	# parallel let is in them, or a closure's application.
229	def unflat(nodes: List<&2, Lint.Node>, out: List<&2, String>) -> List<&2, String>:
230	  match nodes:
231	    case Nil{}:
232	      out
233	    case Con{Lint.Node{Lint.Definition{t, u}, n, s, +kids, f}, rest}:
234	      unflat(
235	        rest,
236	        Lists.push(String, Lists.when(String, applies(kids, Lint.forks(kids, False{})), t), out)
237	      )
238	    case Con{node, rest}:
239	      unflat(rest, out)
240	
241	# The definitions of the program whose own body keeps them from compiling to a native loop, onto `out`: those of
242	# `unflat`, and those that call themselves outside a tail position.
243	def program.unflat(sources: List<&2, Lint.Source>, out: List<&2, String>) -> List<&2, String>:
244	  match sources:
245	    case Nil{}:
246	      out
247	    case Con{Lint.Source{path, ns, text, +nodes}, rest}:
248	      program.unflat(rest, unflat(nodes, Deep.deep(nodes, True{}, out)))
249	
250	def calls_itself(info: Maybe<&2, Lint.Def>) -> Bool:
251	  match info:
252	    case Some{Lint.Def{t, ps, forks, calls, r}}:
253	      List.contains(~String, ~String.eq, calls, t)
254	    case None{}:
255	      False{}
256	
257	# The definitions among `names` that call themselves and are in `unflat`, onto `out`.
258	def loops(
259	  names: List<&2, String>,
260	  +defs: Map<&2, Maybe<&2, Lint.Def>>,
261	  +unflat: Set(),
262	  out: List<&2, String>
263	) -> List<&2, String>:
264	  match names:
265	    case Nil{}:
266	      out
267	    case Con{+t, rest}:
268	      loops(
269	        rest,
270	        defs,
271	        unflat,
272	        Lists.push(
273	          String,
274	          Lists.when(String, Sets.has(unflat, t) && calls_itself(Names.find(Lint.Def, defs, t)), t),
275	          out
276	        )
277	      )
278	
279	# The definitions of the program a call of which runs a loop to its end, even when its value is unused: a loop that does
280	# not compile to a native loop, as its body, or one it calls, keeps it from that (see program.unflat); or a definition
281	# that calls such a loop.
282	def costly(+sources: List<&2, Lint.Source>, +defs: Map<&2, Maybe<&2, Lint.Def>>) -> Set():
283	  Lint.Program.callers(
284	    sources,
285	    defs,
286	    Set.from_list(
287	      loops(
288	        Map.keys(&2, Maybe<&2, Lint.Def>, defs),
289	        defs,
290	        Lint.Program.callers(sources, defs, Set.from_list(program.unflat(sources, []))),
291	        []
292	      )
293	    )
294	  )
295	
296	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
297	  +sources = Lint.Here.sources(here)
298	  Lint.done(
299	    defs(
300	      Lint.Here.nodes(here),
301	      costly(sources, Lint.Program.defs(sources, Map.new(&2, Maybe<&2, Lint.Def>))),
302	      []
303	    )
304	  )
305	
306	def rule() -> Lint.Rule:
307	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}