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.
12	import Base
13	import ../../src.bend as Src
14	import ../../finding.bend as F
15	import ../../syntax/lex.bend as Lex
16	import ../../syntax/tree.bend as Tree
17	import ../calls.bend as Calls
18	import ../../lazy/lazy.bend as Lazy
19	import ./table.bend as Table
20	
21	# is the chain exactly one number?
22	def literal(nn: Tree.Node) -> Bool:
23	  match nn:
24	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
25	      True{}
26	    case other:
27	      False{}
28	
29	# a fixed table is reported by `table`, not here
30	def held(+list: Bool, coll: Tree.Node, +fixed: List<&2, String>) -> Bool:
31	  match list:
32	    case False{}:
33	      False{}
34	    case True{}:
35	      Table.owns(coll, fixed)
36	
37	# every List.get / String.get call at a computed index
38	def walk(nn: Tree.Node, +path: String, +fixed: List<&2, String>) -> List<&2, F.Finding>:
39	  match nn:
40	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
41	      +list = String.eq(t, "List.get")
42	      +as = Calls.args(kids)
43	      +get = Bool.and(String.eq(o, "("), Bool.or(list, String.eq(t, "String.get")))
44	      +fire = Bool.and(get, Bool.and(Bool.not(literal(Calls.arg(as, Bool.pick(Nat, list, 3n, 1n)))),
45	        Bool.not(held(list, Calls.arg(as, 2n), fixed))))
46	      +more = List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(rest, path, fixed)])
47	      Bool.pick(List<&2, F.Finding>, fire,
48	        F.Finding{path, l, c, U32.from_nat(String.length(t)), "index",
49	          t ++ " in a recursive def walks the list from its head on every step, which is quadratic; recurse over the list itself."} <> more,
50	        more)
51	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
52	      List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(rest, path, fixed)])
53	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
54	      List.concat(&2, F.Finding, [walk(kids, path, fixed), walk(body, path, fixed), walk(rest, path, fixed)])
55	    case Tree.NCons{h, rest}:
56	      walk(rest, path, fixed)
57	    case other:
58	      Nil{}
59	
60	def check.go(
61	  ds: List<&2, Calls.Def>,
62	  +mods: List<&2, String>,
63	  +path: String,
64	  acc: List<&2, List<&2, F.Finding>>
65	) -> List<&2, F.Finding>:
66	  match ds:
67	    case Nil{}:
68	      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
69	    case Con{Calls.Def{+name, +sig, +body}, rest}:
70	      check.go(rest, mods, path,
71	        Lazy.stop(List<&2, F.Finding>,
72	          Bool.not(Bool.and(Calls.calls(body, name), Bool.not(Calls.exempt(path, sig)))), [],
73	          _u => walk(body, path, Table.scope(body, mods))) <> acc)
74	
75	# the rule
76	def check(ss: Src.Src) -> List<&2, F.Finding>:
77	  Src.Src{path, text, toks, tree, bound, items} = ss
78	  +ds = Calls.defs(tree)
79	  check.go(ds, Table.modules(ds, []), path, [])