1 package tracker
2 3 import (
4 "bytes"
5 "fmt"
6 "sync"
7 8 "github.com/pelletier/go-toml/v2/unstable"
9 )
10 11 type keyKind uint8
12 13 const (
14 invalidKind keyKind = iota
15 valueKind
16 tableKind
17 arrayTableKind
18 )
19 20 func (k keyKind) String() string {
21 switch k {
22 case invalidKind:
23 return "invalid"
24 case valueKind:
25 return "value"
26 case tableKind:
27 return "table"
28 case arrayTableKind:
29 return "array table"
30 }
31 panic("missing keyKind string mapping")
32 }
33 34 // SeenTracker tracks which keys have been seen with which TOML type to flag
35 // duplicates and mismatches according to the spec.
36 //
37 // Each node in the visited tree is represented by an entry. Each entry has an
38 // identifier, which is provided by a counter. Entries are stored in the array
39 // entries. As new nodes are discovered (referenced for the first time in the
40 // TOML document), entries are created and appended to the array. An entry
41 // points to its parent using its id.
42 //
43 // To find whether a given key (sequence of []byte) has already been visited,
44 // the entries are linearly searched, looking for one with the right name and
45 // parent id.
46 //
47 // Given that all keys appear in the document after their parent, it is
48 // guaranteed that all descendants of a node are stored after the node, this
49 // speeds up the search process.
50 //
51 // When encountering [[array tables]], the descendants of that node are removed
52 // to allow that branch of the tree to be "rediscovered". To maintain the
53 // invariant above, the deletion process needs to keep the order of entries.
54 // This results in more copies in that case.
55 type SeenTracker struct {
56 entries []entry
57 currentIdx int
58 }
59 60 var pool sync.Pool
61 62 func (s *SeenTracker) reset() {
63 // Always contains a root element at index 0.
64 s.currentIdx = 0
65 if len(s.entries) == 0 {
66 s.entries = make([]entry, 1, 2)
67 } else {
68 s.entries = s.entries[:1]
69 }
70 s.entries[0].child = -1
71 s.entries[0].next = -1
72 }
73 74 type entry struct {
75 // Use -1 to indicate no child or no sibling.
76 child int
77 next int
78 79 name []byte
80 kind keyKind
81 explicit bool
82 kv bool
83 }
84 85 // Find the index of the child of parentIdx with key k. Returns -1 if
86 // it does not exist.
87 func (s *SeenTracker) find(parentIdx int, k []byte) int {
88 for i := s.entries[parentIdx].child; i >= 0; i = s.entries[i].next {
89 if bytes.Equal(s.entries[i].name, k) {
90 return i
91 }
92 }
93 return -1
94 }
95 96 // Remove all descendants of node at position idx.
97 func (s *SeenTracker) clear(idx int) {
98 if idx >= len(s.entries) {
99 return
100 }
101 102 for i := s.entries[idx].child; i >= 0; {
103 next := s.entries[i].next
104 n := s.entries[0].next
105 s.entries[0].next = i
106 s.entries[i].next = n
107 s.entries[i].name = nil
108 s.clear(i)
109 i = next
110 }
111 112 s.entries[idx].child = -1
113 }
114 115 func (s *SeenTracker) create(parentIdx int, name []byte, kind keyKind, explicit bool, kv bool) int {
116 e := entry{
117 child: -1,
118 next: s.entries[parentIdx].child,
119 120 name: name,
121 kind: kind,
122 explicit: explicit,
123 kv: kv,
124 }
125 var idx int
126 if s.entries[0].next >= 0 {
127 idx = s.entries[0].next
128 s.entries[0].next = s.entries[idx].next
129 s.entries[idx] = e
130 } else {
131 idx = len(s.entries)
132 s.entries = append(s.entries, e)
133 }
134 135 s.entries[parentIdx].child = idx
136 137 return idx
138 }
139 140 func (s *SeenTracker) setExplicitFlag(parentIdx int) {
141 for i := s.entries[parentIdx].child; i >= 0; i = s.entries[i].next {
142 if s.entries[i].kv {
143 s.entries[i].explicit = true
144 s.entries[i].kv = false
145 }
146 s.setExplicitFlag(i)
147 }
148 }
149 150 // CheckExpression takes a top-level node and checks that it does not contain
151 // keys that have been seen in previous calls, and validates that types are
152 // consistent.
153 func (s *SeenTracker) CheckExpression(node *unstable.Node) error {
154 if s.entries == nil {
155 s.reset()
156 }
157 switch node.Kind {
158 case unstable.KeyValue:
159 return s.checkKeyValue(node)
160 case unstable.Table:
161 return s.checkTable(node)
162 case unstable.ArrayTable:
163 return s.checkArrayTable(node)
164 default:
165 panic(fmt.Errorf("this should not be a top level node type: %s", node.Kind))
166 }
167 }
168 169 func (s *SeenTracker) checkTable(node *unstable.Node) error {
170 if s.currentIdx >= 0 {
171 s.setExplicitFlag(s.currentIdx)
172 }
173 174 it := node.Key()
175 176 parentIdx := 0
177 178 // This code is duplicated in checkArrayTable. This is because factoring
179 // it in a function requires to copy the iterator, or allocate it to the
180 // heap, which is not cheap.
181 for it.Next() {
182 if it.IsLast() {
183 break
184 }
185 186 k := it.Node().Data
187 188 idx := s.find(parentIdx, k)
189 190 if idx < 0 {
191 idx = s.create(parentIdx, k, tableKind, false, false)
192 } else {
193 entry := s.entries[idx]
194 if entry.kind == valueKind {
195 return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
196 }
197 }
198 parentIdx = idx
199 }
200 201 k := it.Node().Data
202 idx := s.find(parentIdx, k)
203 204 if idx >= 0 {
205 kind := s.entries[idx].kind
206 if kind != tableKind {
207 return fmt.Errorf("toml: key %s should be a table, not a %s", string(k), kind)
208 }
209 if s.entries[idx].explicit {
210 return fmt.Errorf("toml: table %s already exists", string(k))
211 }
212 s.entries[idx].explicit = true
213 } else {
214 idx = s.create(parentIdx, k, tableKind, true, false)
215 }
216 217 s.currentIdx = idx
218 219 return nil
220 }
221 222 func (s *SeenTracker) checkArrayTable(node *unstable.Node) error {
223 if s.currentIdx >= 0 {
224 s.setExplicitFlag(s.currentIdx)
225 }
226 227 it := node.Key()
228 229 parentIdx := 0
230 231 for it.Next() {
232 if it.IsLast() {
233 break
234 }
235 236 k := it.Node().Data
237 238 idx := s.find(parentIdx, k)
239 240 if idx < 0 {
241 idx = s.create(parentIdx, k, tableKind, false, false)
242 } else {
243 entry := s.entries[idx]
244 if entry.kind == valueKind {
245 return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
246 }
247 }
248 249 parentIdx = idx
250 }
251 252 k := it.Node().Data
253 idx := s.find(parentIdx, k)
254 255 if idx >= 0 {
256 kind := s.entries[idx].kind
257 if kind != arrayTableKind {
258 return fmt.Errorf("toml: key %s already exists as a %s, but should be an array table", kind, string(k))
259 }
260 s.clear(idx)
261 } else {
262 idx = s.create(parentIdx, k, arrayTableKind, true, false)
263 }
264 265 s.currentIdx = idx
266 267 return nil
268 }
269 270 func (s *SeenTracker) checkKeyValue(node *unstable.Node) error {
271 parentIdx := s.currentIdx
272 it := node.Key()
273 274 for it.Next() {
275 k := it.Node().Data
276 277 idx := s.find(parentIdx, k)
278 279 if idx < 0 {
280 idx = s.create(parentIdx, k, tableKind, false, true)
281 } else {
282 entry := s.entries[idx]
283 if it.IsLast() {
284 return fmt.Errorf("toml: key %s is already defined", string(k))
285 } else if entry.kind != tableKind {
286 return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
287 } else if entry.explicit {
288 return fmt.Errorf("toml: cannot redefine table %s that has already been explicitly defined", string(k))
289 }
290 }
291 292 parentIdx = idx
293 }
294 295 s.entries[parentIdx].kind = valueKind
296 297 value := node.Value()
298 299 switch value.Kind {
300 case unstable.InlineTable:
301 return s.checkInlineTable(value)
302 case unstable.Array:
303 return s.checkArray(value)
304 }
305 306 return nil
307 }
308 309 func (s *SeenTracker) checkArray(node *unstable.Node) error {
310 it := node.Children()
311 for it.Next() {
312 n := it.Node()
313 switch n.Kind {
314 case unstable.InlineTable:
315 err := s.checkInlineTable(n)
316 if err != nil {
317 return err
318 }
319 case unstable.Array:
320 err := s.checkArray(n)
321 if err != nil {
322 return err
323 }
324 }
325 }
326 return nil
327 }
328 329 func (s *SeenTracker) checkInlineTable(node *unstable.Node) error {
330 if pool.New == nil {
331 pool.New = func() interface{} {
332 return &SeenTracker{}
333 }
334 }
335 336 s = pool.Get().(*SeenTracker)
337 s.reset()
338 339 it := node.Children()
340 for it.Next() {
341 n := it.Node()
342 err := s.checkKeyValue(n)
343 if err != nil {
344 return err
345 }
346 }
347 348 // As inline tables are self-contained, the tracker does not
349 // need to retain the details of what they contain. The
350 // keyValue element that creates the inline table is kept to
351 // mark the presence of the inline table and prevent
352 // redefinition of its keys: check* functions cannot walk into
353 // a value.
354 pool.Put(s)
355 return nil
356 }
357