1	# src/rules/table: what a fixed table is, for `index`. A fixed table is a
2	# literal list, an array, or `List.replicate` / `Array.new` / `List.range`
3	# with a constant count, written inline, defined beside the loop, or held by
4	# the let of that name in scope; a let reaches the statements after it and
5	# the blocks under them, not a sibling case arm, and a later let of the name
6	# to anything else ends it. `index` leaves a get of one alone. This was the
7	# `table` rule (U008), retired: it had no public hits; `hit` still builds the
8	# finding that rule gave, which `index` reads only as "a fixed table". Pure.
9	import Base
10	import ../finding.bend as F
11	import ../syntax/lex.bend as Lex
12	import ../syntax/tree.bend as Tree
13	import ./calls.bend as Calls
14	import ../lazy/lazy.bend as Lazy
15	
16	# is the chain exactly one number?
17	def literal(nn: Tree.Node) -> Bool:
18	  match nn:
19	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
20	      True{}
21	    case other:
22	      False{}
23	
24	# a top-level token of this text, not one nested in a group
25	def top_has(nn: Tree.Node, +want: String) -> Bool:
26	  match nn:
27	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
28	      top_has(rest, want)
29	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, rest}:
30	      +more = top_has(rest, want)
31	      Bool.or(String.eq(t, want), more)
32	    case Tree.NCons{h, rest}:
33	      top_has(rest, want)
34	    case other:
35	      False{}
36	
37	# `[v : T*n]` or `[v : T^d]`, and the size is a number
38	def array_sized(nn: Tree.Node) -> Bool:
39	  match nn:
40	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TOp{}, +op, l, c}},
41	        Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l2, c2}}, rest}}:
42	      +here = Bool.or(String.eq(op, "*"), String.eq(op, "^"))
43	      +more = array_sized(rest)
44	      Bool.or(here, more)
45	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
46	      array_sized(rest)
47	    case Tree.NCons{h, rest}:
48	      array_sized(rest)
49	    case other:
50	      False{}
51	
52	# the chain is exactly one number
53	def lone_num(nn: Tree.Node) -> Bool:
54	  match nn:
55	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TNum{}, t, l, c}}, Tree.NNil{}}:
56	      True{}
57	    case other:
58	      False{}
59	
60	# `List.replicate` / `Array.new` count at argument 2; `List.range` at the end
61	def range_count(as: List<&2, Tree.Node>) -> Bool:
62	  match as:
63	    case Nil{}:
64	      False{}
65	    case Con{h, Nil{}}:
66	      lone_num(h)
67	    case Con{h, rest}:
68	      range_count(rest)
69	
70	# a constant-size constructor, not a length taken from the data
71	def built_call(+tt: String, kids: Tree.Node) -> Bool:
72	  +as = Calls.args(kids)
73	  +rep = Bool.or(String.eq(tt, "List.replicate"), String.eq(tt, "Array.new"))
74	  Bool.or(Bool.and(rep, lone_num(Calls.arg(as, 2n))), Bool.and(String.eq(tt, "List.range"), range_count(as)))
75	
76	# a list literal, a sized array, or a constant-size constructor
77	def built(nn: Tree.Node) -> Bool:
78	  match nn:
79	    case Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, +kids, close}, Tree.NNil{}}:
80	      Bool.and(String.eq(o, "["), Bool.or(top_has(kids, ","), Bool.and(top_has(kids, ":"), array_sized(kids))))
81	    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}},
82	        Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, Tree.NNil{}}}:
83	      Bool.and(String.eq(o, "("), built_call(t, kids))
84	    case other:
85	      False{}
86	
87	# the chain is exactly this call's name, with no arguments that matter: `name()`
88	def call_name(nn: Tree.Node) -> String:
89	  match nn:
90	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}},
91	        Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, kids, _}, Tree.NNil{}}}:
92	      Bool.pick(String, String.eq(o, "("), t, "")
93	    case other:
94	      ""
95	
96	# the chain is exactly one lowercase name
97	def lone_name(nn: Tree.Node) -> String:
98	  match nn:
99	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, Tree.NNil{}}:
100	      t
101	    case other:
102	      ""
103	
104	# one use of a name, told apart from its other uses by where it stands
105	def key(+tt: String, +line: U32, +col: U32) -> String:
106	  tt ++ "@" ++ U32.show(line) ++ ":" ++ U32.show(col)
107	
108	# the chain is exactly one lowercase name: that use's key
109	def lone_key(nn: Tree.Node) -> String:
110	  match nn:
111	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, +l, +c}}, Tree.NNil{}}:
112	      key(t, l, c)
113	    case other:
114	      ""
115	
116	# the list argument is a fixed table: inline, a use of a let that holds one,
117	# or `name()` / `name` for a table def of the file
118	def owns(+nn: Tree.Node, +fixed: List<&2, String>) -> Bool:
119	  +called = call_name(nn)
120	  +named = lone_name(nn)
121	  +used = lone_key(nn)
122	  Bool.or(built(nn), Bool.or(
123	    Bool.and(Bool.not(String.is_empty(named)),
124	      Bool.or(List.contains(~String, ~String.eq, fixed, named), List.contains(~String, ~String.eq, fixed, used))),
125	    Bool.and(Bool.not(String.is_empty(called)), List.contains(~String, ~String.eq, fixed, called))))
126	
127	# one plain name before `=`, when the pattern is not a destructure
128	def bind_bad(+bad: Bool, +nm: String) -> String:
129	  match bad:
130	    case True{}:
131	      ""
132	    case False{}:
133	      nm
134	
135	# one plain name before `=`, when there is one
136	def bind_at(+seen: Bool, +bad: Bool, +nm: String) -> String:
137	  match seen:
138	    case False{}:
139	      ""
140	    case True{}:
141	      bind_bad(bad, nm)
142	
143	# the one plain name a statement binds, or empty
144	def bind_name(nn: Tree.Node, +seen: Bool, +bad: Bool, +nm: String) -> String:
145	  match nn:
146	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
147	      bind_at(seen, bad, nm)
148	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
149	      bind_name(rest, True{}, Bool.or(bad, seen), t)
150	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TUpper{}, t, l, c}}, rest}:
151	      bind_name(rest, seen, True{}, nm)
152	    case Tree.NCons{Tree.Group{open, kids, close}, rest}:
153	      bind_name(rest, seen, bad, nm)
154	    case Tree.NCons{h, rest}:
155	      bind_name(rest, seen, bad, nm)
156	    case other:
157	      ""
158	
159	# the right-hand side: the chain after a statement's top-level `=`
160	def bind_rhs(nn: Tree.Node) -> Tree.Node:
161	  match nn:
162	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
163	      rest
164	    case Tree.NCons{h, rest}:
165	      bind_rhs(rest)
166	    case other:
167	      Tree.NNil{}
168	
169	# the names in scope without this one
170	def drop(live: List<&2, String>, +nm: String) -> List<&2, String>:
171	  match live:
172	    case Nil{}:
173	      []
174	    case Con{+h, rest}:
175	      +more = drop(rest, nm)
176	      Bool.pick(List<&2, String>, String.eq(h, nm), more, h <> more)
177	
178	# after a let of `nm`: it holds a table only when this binding is one
179	def rebind(+nm: String, +tab: Bool, +live: List<&2, String>) -> List<&2, String>:
180	  +out = drop(live, nm)
181	  Bool.pick(List<&2, String>, String.is_empty(nm), live,
182	    Bool.pick(List<&2, String>, tab, nm <> out, out))
183	
184	# a name use joins the keys when the let in scope for it holds a table
185	def use_at(+tt: String, +line: U32, +col: U32, +live: List<&2, String>, +acc: List<&2, String>) -> List<&2, String>:
186	  Bool.pick(List<&2, String>, List.contains(~String, ~String.eq, live, tt), key(tt, line, col) <> acc, acc)
187	
188	# the keys of every name use under the node whose binding in scope is a
189	# table: a let reaches the statements after it and their bodies, not an
190	# enclosing block or a sibling arm, and a later let of the name replaces it
191	def lets(nn: Tree.Node, +live: List<&2, String>, acc: List<&2, String>) -> List<&2, String>:
192	  match nn:
193	    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
194	      +next = rebind(bind_name(kids, False{}, False{}, ""), built(bind_rhs(kids)), live)
195	      lets(rest, next, lets(body, live, lets(kids, live, acc)))
196	    case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
197	      lets(rest, live, lets(kids, live, acc))
198	    case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, +l, +c}}, rest}:
199	      lets(rest, live, use_at(t, l, c, live, acc))
200	    case Tree.NCons{h, rest}:
201	      lets(rest, live, acc)
202	    case other:
203	      acc
204	
205	# a def whose body is one fixed table
206	def mod_one(body: Tree.Node, +name: String, +acc: List<&2, String>) -> List<&2, String>:
207	  match body:
208	    case Tree.NCons{Tree.Stmt{kind, +kids, inn}, Tree.NNil{}}:
209	      Bool.pick(List<&2, String>, built(kids), name <> acc, acc)
210	    case other:
211	      acc
212	
213	# defs of this file whose body is one fixed table
214	def modules(ds: List<&2, Calls.Def>, acc: List<&2, String>) -> List<&2, String>:
215	  match ds:
216	    case Nil{}:
217	      acc
218	    case Con{Calls.Def{+name, sig, +body}, rest}:
219	      modules(rest, mod_one(body, name, acc))
220	
221	# fixed tables visible in this def: the file's table defs by name, and each
222	# use of a let whose binding in scope is a table, by its key
223	def scope(body: Tree.Node, +mods: List<&2, String>) -> List<&2, String>:
224	  lets(body, [], mods)
225	
226	# the finding for a get or a set
227	def cite(+get: Bool, +path: String, +line: U32, +col: U32, +len: U32) -> F.Finding:
228	  match get:
229	    case True{}:
230	      F.Finding{path, line, col, len, "table",
231	        "List.get in a recursive def walks the table from its head on every step; keep the table in an Array and use Array.get."}
232	    case False{}:
233	      F.Finding{path, line, col, len, "table",
234	        "List.set in a recursive def copies the list to change one element; keep the table in an Array and use Array.set."}
235	
236	# a get or a set of a fixed table at a computed index
237	def hit(
238	  +open: Bool,
239	  +tt: String,
240	  kids: Tree.Node,
241	  +fixed: List<&2, String>,
242	  +path: String,
243	  +line: U32,
244	  +col: U32
245	) -> List<&2, F.Finding>:
246	  +get = String.eq(tt, "List.get")
247	  +set = String.eq(tt, "List.set")
248	  +op = Bool.and(open, Bool.or(get, set))
249	  +as = Calls.args(kids)
250	  +fire = Bool.and(op, Bool.and(Bool.not(literal(Calls.arg(as, 3n))), owns(Calls.arg(as, 2n), fixed)))
251	  Bool.pick(List<&2, F.Finding>, fire,
252	    [cite(get, path, line, col, U32.from_nat(String.length(tt)))], [])