1	# rule index: a def that calls itself also calls `List.get(..)` or
2	# `String.get(..)`. Both walk the cons list from the head to the index, so a
3	# per-index loop is quadratic (AppSprout's sort went from 39 s to 0.9 s
4	# walking the list itself). Walk the list in the recursion, or materialize
5	# what the loop needs in one pass. A get anywhere in the def is reported,
6	# one in a base arm that runs once included. A literal index of any size
7	# (`List.get(.., xs, 0n)`, `5000n`) is exempt, as are laws and proofs (a def
8	# with no type at all fills a law: it is a proof). A
9	# `List.get` on a fixed table (a literal, a sized array, a constant
10	# `List.replicate`) is `table`'s finding instead, so the two rules do not
11	# both report that call. `String.get` is never `table`'s: it stays here. A
12	# get that is the def's own self-call is exempt: the step of a def named
13	# `List.get` or `String.get` itself (Base's), which walks one cell per call.
14	import Base
15	import ../../src.bend as Src
16	import ../../finding.bend as F
17	import ../../syntax/lex.bend as Lex
18	import ../../syntax/tree.bend as Tree
19	import ../calls.bend as Calls
20	import ../../lazy/lazy.bend as Lazy
21	import ./table.bend as Table
22	
23	# is the chain exactly one number?
24	def literal(nn: Tree.Node) -> Bool:
25	  match nn:
26	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
27	      True{}
28	    case other:
29	      False{}
30	
31	# a fixed table is reported by `table`, not here
32	def held(+list: Bool, coll: Tree.Node, +fixed: List<&2, String>) -> Bool:
33	  match list:
34	    case False{}:
35	      False{}
36	    case True{}:
37	      Table.owns(coll, fixed)
38	
39	# is the call named get, and not the def's own (self)?
40	def named(+tt: String, +self: String, +get: String) -> Bool:
41	  Bool.and(String.eq(tt, get), Bool.not(String.eq(tt, self)))
42	
43	# every List.get / String.get call at a computed index, but self's own
44	def walk(nn: Tree.Node, +path: String, +fixed: List<&2, String>, +self: String) -> List<&2, F.Finding>:
45	  match nn:
46	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
47	      +list = named(t, self, "List.get")
48	      +as = Calls.args(kids)
49	      +get = Bool.and(String.eq(o, "("), Bool.or(list, named(t, self, "String.get")))
50	      +fire = Bool.and(get, Bool.and(Bool.not(literal(Calls.arg(as, Bool.pick(Nat, list, 3n, 1n)))),
51	        Bool.not(held(list, Calls.arg(as, 2n), fixed))))
52	      +more = List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(rest, path, fixed, self)])
53	      Bool.pick(List<&2, F.Finding>, fire,
54	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "index",
55	          t ++ " in a recursive def walks the list from its head on every step, which is quadratic; recurse over the list itself."} <> more,
56	        more)
57	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
58	      List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(rest, path, fixed, self)])
59	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
60	      List.concat(&2, F.Finding, [walk(kids, path, fixed, self), walk(body, path, fixed, self),
61	        walk(rest, path, fixed, self)])
62	    case Tree.NCons{h, rest}:
63	      walk(rest, path, fixed, self)
64	    case other:
65	      Nil{}
66	
67	def check.go(
68	  ds: List<&2, Calls.Def>,
69	  +mods: List<&2, String>,
70	  +path: String,
71	  acc: List<&2, List<&2, F.Finding>>
72	) -> List<&2, F.Finding>:
73	  match ds:
74	    case Nil{}:
75	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
76	    case Con{Calls.Def{+name, +sig, +body}, rest}:
77	      check.go(rest, mods, path,
78	        Lazy.stop(List<&2, F.Finding>,
79	          Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
80	          _u => walk(body, path, Table.scope(body, mods), name)) <> acc)
81	
82	# the rule
83	def check(ss: Src.Src) -> List<&2, F.Finding>:
84	  Src.Src{path, text, toks, tree, bound, items} = ss
85	  +ds = Calls.defs(tree)
86	  check.go(ds, Table.modules(ds, []), path, [])