1	# rule eager: a branch of a `Bool.pick` calls a recursive def of the same
2	# file. Bool.pick is an ordinary def, so both branch arguments are evaluated
3	# before the call: the work in a branch runs whatever the condition says, and
4	# the condition never saves it. `pick` catches the self-call and `strict` the
5	# one under Bool.and/or; a call to a neighbour is the same bug and neither
6	# sees it (a game's overlap test moved out of a pick branch took a scene from
7	# 31 to 55 fps; one `gaps(..)` in a branch here ran on every file the linter
8	# read, 88 s of a 100 s run). Bind the call above the pick (`+x = gaps(..)`),
9	# or take the branch lazily (`Lazy.stop`, `Lazy.or_else` from src/lazy/lazy.bend:
10	# the last argument is a `Unit -> T` thunk, applied only on the branch that
11	# needs it). Two things keep it off idiomatic code: only a call to a def of
12	# this file counts, and only to one that loops (it calls itself, or reaches
13	# something that does), since a Base call and a one-line accessor are
14	# everywhere and cost nothing; only the branch arguments count, not the type
15	# and the condition, which run whatever is written; and what sits after a
16	# `=>` is a lambda's body, which the call does not run. The body ends at the
17	# next comma of its group, so an argument after it counts again.
18	import Base
19	import ../../src.bend as Src
20	import ../../finding.bend as F
21	import ../../syntax/lex.bend as Lex
22	import ../../syntax/tree.bend as Tree
23	import ../../lazy/lazy.bend as Lazy
24	import ../calls.bend as Calls
25	
26	# every name a node calls, `f(..)`, at any depth
27	def called(nn: Tree.Node) -> List<&2, String>:
28	  match nn:
29	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
30	      +more = List.concat(&2, String, [called(kids), called(rest)])
31	      Bool.pick(List<&2, String>, String.eq(o, "("), t <> more, more)
32	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
33	      List.concat(&2, String, [called(kids), called(rest)])
34	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
35	      List.concat(&2, String, [called(kids), called(body), called(rest)])
36	    case Tree.NCons{h, rest}:
37	      called(rest)
38	    case other:
39	      Nil{}
40	
41	# does the list hold a name the set has?
42	def any_of(cs: List<&2, String>, +set: List<&2, String>) -> Bool:
43	  match cs:
44	    case Nil{}:
45	      False{}
46	    case Con{c, t}:
47	      Lazy.or_else(List.contains(~String, ~String.eq, set, c), _u => any_of(t, set))
48	
49	def loops.go(ds: List<&2, Calls.Def>, +acc: List<&2, String>) -> List<&2, String>:
50	  match ds:
51	    case Nil{}:
52	      acc
53	    case Con{Calls.Def{+name, sig, body}, rest}:
54	      +cs = called(body)
55	      +deep = Bool.or(List.contains(~String, ~String.eq, cs, name), any_of(cs, acc))
56	      loops.go(rest, Bool.pick(List<&2, String>, deep, name <> acc, acc))
57	
58	# the defs of the file that loop: one that calls itself, or that reaches one
59	# that does (a def is defined above its use and there is no mutual recursion,
60	# so one pass down the file settles it)
61	def loops(ds: List<&2, Calls.Def>) -> List<&2, String>:
62	  loops.go(ds, [])
63	
64	# the hot a leaf leaves behind: a `=>` clears it for the lambda's body; a
65	# comma of a pick's own group moves to its next argument, hot from the third
66	# on (0 the type, 1 the condition, 2 and 3 the branches), and a comma of any
67	# other group returns it to keep; any other leaf leaves it as it was
68	def work.hot(kk: Lex.TokKind, +hot: Bool, +seg: U32, +keep: Bool) -> Bool:
69	  match kk:
70	    case Lex.TLam{}:
71	      False{}
72	    case Lex.TComma{}:
73	      +in_pick = U32.is_lt(seg, 9)
74	      +next = Bool.pick(U32, in_pick, (seg + 1 : U32), seg)
75	      Bool.pick(Bool, in_pick, Bool.not(U32.is_lt(next, 2)), keep)
76	    case other:
77	      hot
78	
79	# the argument a leaf leaves behind: a comma of a pick's own group moves on
80	def work.seg(kk: Lex.TokKind, +seg: U32) -> U32:
81	  match kk:
82	    case Lex.TComma{}:
83	      Bool.pick(U32, U32.is_lt(seg, 9), (seg + 1 : U32), seg)
84	    case other:
85	      seg
86	
87	# can the leaf name a call (it is neither a `=>` nor a comma)?
88	def work.name(kk: Lex.TokKind) -> Bool:
89	  match kk:
90	    case Lex.TLam{}:
91	      False{}
92	    case Lex.TComma{}:
93	      False{}
94	    case other:
95	      True{}
96	
97	# the work under a def's body: hot says the node sits in a branch argument of
98	# a `Bool.pick` (so it runs whatever the condition), seg counts the arguments
99	# of the pick whose group this chain is (0 the type, 1 the condition, 2 and 3
100	# the branches; 9 for a chain that is not a pick's), and keep is what hot
101	# returns to at the next comma of a chain that is not a pick's, so a `=>`
102	# clears hot for the lambda's own body and not for the arguments after it. A
103	# leaf moves the state by its kind (work.hot, work.seg); a `=>` or a comma
104	# before a group names no call, so that group is walked as any other
105	def work(
106	  nn: Tree.Node,
107	  +ns: List<&2, String>,
108	  +self: String,
109	  +path: String,
110	  +hot: Bool,
111	  +seg: U32,
112	  +keep: Bool
113	) -> List<&2, F.Finding>:
114	  match nn:
115	    case Tree.NCons{Tree.Leaf{Lex.Tok{+k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
116	      +now = work.hot(k, hot, seg, keep)
117	      +call = Bool.and(work.name(k), String.eq(o, "("))
118	      +is_pick = Bool.and(call, String.eq(t, "Bool.pick"))
119	      +mine = Bool.and(Bool.not(String.eq(t, self)), List.contains(~String, ~String.eq, ns, t))
120	      +report = Bool.and(now, Bool.and(call, mine))
121	      +inner = Bool.and(now, Bool.not(is_pick))
122	      +more = List.concat(&2, F.Finding,
123	        [work(kids, ns, self, path, inner, Bool.pick(U32, is_pick, 0, 9), inner),
124	          work(rest, ns, self, path, now, work.seg(k, seg), keep)])
125	      Bool.pick(List<&2, F.Finding>, report,
126	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "eager",
127	          t ++ " is called in a branch of Bool.pick, which evaluates both branches, so it runs whatever the condition; bind it above the pick, or branch with `match` on the condition."}
128	          <> more,
129	        more)
130	    case Tree.NCons{Tree.Leaf{Lex.Tok{+k, t, l, c}}, rest}:
131	      work(rest, ns, self, path, work.hot(k, hot, seg, keep), work.seg(k, seg), keep)
132	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
133	      List.concat(&2, F.Finding, [work(kids, ns, self, path, hot, 9, hot), work(rest, ns, self, path, hot, seg, keep)])
134	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
135	      List.concat(&2, F.Finding, [work(kids, ns, self, path, False{}, 9, False{}),
136	        work(body, ns, self, path, False{}, 9, False{}),
137	        work(rest, ns, self, path, hot, seg, keep)])
138	    case Tree.NCons{h, rest}:
139	      work(rest, ns, self, path, hot, seg, keep)
140	    case other:
141	      Nil{}
142	
143	def check.go(
144	  ds: List<&2, Calls.Def>,
145	  +ns: List<&2, String>,
146	  +path: String,
147	  acc: List<&2, List<&2, F.Finding>>
148	) -> List<&2, F.Finding>:
149	  match ds:
150	    case Nil{}:
151	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
152	    case Con{Calls.Def{+name, +sig, body}, rest}:
153	      check.go(rest, ns, path,
154	        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
155	          _u => work(body, ns, name, path, False{}, 9, False{})) <> acc)
156	
157	# the rule
158	def check(ss: Src.Src) -> List<&2, F.Finding>:
159	  Src.Src{path, text, toks, tree, bound, items} = ss
160	  +ds = Calls.defs(tree)
161	  check.go(ds, loops(ds), path, [])