src/rules/table.bend
bolt@1.26.0.0 · 252 lines · 0 definitions
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.
9import Base
10import bolt@1.26.0.0/src/finding.bend as F
11import bolt@1.26.0.0/src/syntax/lex.bend as Lex
12import bolt@1.26.0.0/src/syntax/tree.bend as Tree
13import bolt@1.26.0.0/src/rules/calls.bend as Calls
14import bolt@1.26.0.0/src/lazy/lazy.bend as Lazy
15
16# is the chain exactly one number?
17def 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
25def 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
38def 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
53def 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
61def 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
71def 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
77def 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()`
88def 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
97def 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
105def 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
109def 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
118def 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
128def 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
136def 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
144def 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 `=`
160def 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
170def 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
179def 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
185def 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
191def 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
206def 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
214def 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
223def 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
227def 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
237def 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)))], [])