1	# performance/eager_branch: a value that Bend computes even when it is not needed, and that calls a
2	# definition of the file that calls itself outside a tail position: a value of `Bool.pick`, or the right
3	# side of `&&` or `||`. These are functions, so their arguments are computed before they choose; a
4	# `match` runs only its chosen case.
5	# Heuristics: measured on the CPU, a Bool.pick whose unused value called a doubly recursive fib took 0.28
6	# s, against 0.055 s for a match. A loop whose calls of itself are all tail calls is not reported: clang
7	# drops it when its value is unused (under Bool.pick, a 2G-step loop cost nothing measurable), though the
8	# JS lane still runs it. A loop's own call in `&&` or `||` is never a tail call. A call of a definition
9	# that does not call itself, or of Base, is cheap and not reported. A value in a lambda, a type or an
10	# equation does not run, and is skipped; an erased argument (a proof's) is not told from a live one. A
11	# loop that is short in practice makes a finding that costs little to ignore.
12	import Base
13	import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
14	import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
15	import ./deep_call_in_fork.bend as Deep
16	
17	# Types
18	# =====
19	
20	# A value Bend computes whether needed or not: what computes it ("pick", "&&" or "||"), and the value.
21	type Eager is Data:
22	  Eager{kind: String, value: Maybe<&2, Lint.Node>}
23	
24	# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
25	# position (as the check names them), and the definition, as the check names it.
26	type Owner is Data:
27	  Owner{deeps: List<&2, String>, target: String}
28	
29	# Functions
30	# =========
31	# What an application with the nodes `kids` computes whether needed or not, as its node at `at` is one of its
32	# arguments: "pick" for a value of Bool.pick, "&&" or "||" for their right side, "" for none.
33	def eager(kids: List<&2, Lint.Node>, +at: U32) -> String:
34	  match kids:
35	    case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, Con{ty, Con{c, Con{x, Con{y, rest}}}}}:
36	      Bool.pick(
37	        String,
38	        String.eq(t, "Bool.pick") && (U32.is_eq(at, 3) || U32.is_eq(at, 4)),
39	        "pick",
40	        ""
41	      )
42	    case Con{Lint.Node{Lint.Reference{+t}, n, s, k, f}, Con{left, Con{right, Nil{}}}}:
43	      Bool.pick(
44	        String,
45	        U32.is_eq(at, 2),
46	        Bool.pick(
47	          String,
48	          String.eq(t, "Bool.and"),
49	          "&&",
50	          Bool.pick(String, String.eq(t, "Bool.or"), "||", "")
51	        ),
52	        ""
53	      )
54	    case _:
55	      ""
56	
57	def Eager.of(+kind: String, value: Maybe<&2, Lint.Node>) -> Maybe<&2, Eager>:
58	  Lists.when(Eager, Bool.not(String.eq(kind, "")), Eager{kind, value})
59	
60	# The eager value a call below `path` is in, if one is above it and no lambda comes between. `found` stops the walk
61	# once one is found.
62	def eagerly(path: List<&2, Lint.Above>, found: Maybe<&2, Eager>) -> Maybe<&2, Eager>:
63	  match path found:
64	    case _ Some{e}:
65	      Some{e}
66	    case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, +kids, f}, +at}, rest} None{}:
67	      eagerly(rest, Eager.of(eager(kids, at), List.get(&2, Lint.Node, kids, U32.to_nat(at))))
68	    case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} None{}:
69	      None{}
70	    case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} None{}:
71	      None{}
72	    case Con{a, rest} None{}:
73	      eagerly(rest, None{})
74	    case Nil{} None{}:
75	      None{}
76	
77	def why(+kind: String, +callee: String) -> String:
78	  Bool.pick(
79	    String,
80	    String.eq(kind, "pick"),
81	    "Bool.pick computes both of its values before it picks one, so this call of "
82	      ++ callee
83	      ++ " runs even when the condition picks the other value",
84	    kind
85	      ++ " computes its right side even when its left side decides the result ("
86	      ++ Bool.pick(String, String.eq(kind, "&&"), "False", "True")
87	      ++ "), so this call of "
88	      ++ callee
89	      ++ " runs even then"
90	  )
91	
92	def message(kind: String, +callee: String, own: Bool) -> String:
93	  why(
94	    kind,
95	    callee
96	  )
97	    ++ Bool.pick(
98	      String,
99	      own,
100	      ": it is the loop's own call, so the loop walks to its end instead of stopping where the condition decides",
101	      ""
102	    )
103	    ++ ". 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 "
104	    ++ callee
105	    ++ " runs only a few steps here, expect this finding."
106	
107	def judged(eager: Maybe<&2, Eager>, callee: String, own: Bool) -> List<&2, Lint.Finding>:
108	  match eager:
109	    case Some{Eager{kind, value}}:
110	      Lint.finding(Lint.Information{}, True{}, Lint.Node.span(value), message(kind, callee, own))
111	    case None{}:
112	      []
113	
114	def looping(
115	  hit: Bool,
116	  path: List<&2, Lint.Above>,
117	  callee: String,
118	  own: Bool
119	) -> List<&2, Lint.Finding>:
120	  match hit:
121	    case True{}:
122	      judged(eagerly(path, None{}), callee, own)
123	    case False{}:
124	      []
125	
126	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
127	  match owner node:
128	    case Owner{
129	      deeps,
130	      target
131	    } Lint.Node{
132	      Lint.Application{},
133	      n,
134	      s,
135	      Con{Lint.Node{Lint.Reference{+called}, callee, rs, rk, rf}, args},
136	      f
137	    }:
138	      looping(
139	        List.contains(~String, ~String.eq, deeps, called) && Lint.is_live(path),
140	        path,
141	        callee,
142	        String.eq(called, target)
143	      )
144	    case _ _:
145	      []
146	
147	def defs(
148	  nodes: List<&2, Lint.Node>,
149	  +deeps: List<&2, String>,
150	  out: List<&2, Lint.Finding>
151	) -> List<&2, Lint.Finding>:
152	  match nodes:
153	    case Nil{}:
154	      List.reverse(&2, Lint.Finding, out)
155	    case Con{Lint.Node{Lint.Definition{+t, u}, n, s, k, f}, rest}:
156	      defs(
157	        rest,
158	        deeps,
159	        Lists.onto(
160	          &2,
161	          Lint.Finding,
162	          Lint.visit(
163	            ~Owner,
164	            ~Lint.Finding,
165	            ~visit,
166	            Owner{deeps, t},
167	            [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
168	          ),
169	          out
170	        )
171	      )
172	    case Con{node, rest}:
173	      defs(rest, deeps, out)
174	
175	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
176	  +nodes = Lint.Here.nodes(here)
177	  Lint.done(defs(nodes, Deep.deep(nodes, True{}, []), []))
178	
179	def rule() -> Lint.Rule:
180	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}