summaryrefslogtreecommitdiffstats
path: root/vendor/github.com/pelletier/go-toml/v2/internal/tracker/seen.go
blob: 40e23f8304a7f98799776e3073bdfe19beb511f5 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
package tracker

import (
	"bytes"
	"fmt"
	"sync"

	"github.com/pelletier/go-toml/v2/unstable"
)

type keyKind uint8

const (
	invalidKind keyKind = iota
	valueKind
	tableKind
	arrayTableKind
)

func (k keyKind) String() string {
	switch k {
	case invalidKind:
		return "invalid"
	case valueKind:
		return "value"
	case tableKind:
		return "table"
	case arrayTableKind:
		return "array table"
	}
	panic("missing keyKind string mapping")
}

// SeenTracker tracks which keys have been seen with which TOML type to flag
// duplicates and mismatches according to the spec.
//
// Each node in the visited tree is represented by an entry. Each entry has an
// identifier, which is provided by a counter. Entries are stored in the array
// entries. As new nodes are discovered (referenced for the first time in the
// TOML document), entries are created and appended to the array. An entry
// points to its parent using its id.
//
// To find whether a given key (sequence of []byte) has already been visited,
// the entries are linearly searched, looking for one with the right name and
// parent id.
//
// Given that all keys appear in the document after their parent, it is
// guaranteed that all descendants of a node are stored after the node, this
// speeds up the search process.
//
// When encountering [[array tables]], the descendants of that node are removed
// to allow that branch of the tree to be "rediscovered". To maintain the
// invariant above, the deletion process needs to keep the order of entries.
// This results in more copies in that case.
type SeenTracker struct {
	entries    []entry
	currentIdx int
}

var pool sync.Pool

func (s *SeenTracker) reset() {
	// Always contains a root element at index 0.
	s.currentIdx = 0
	if len(s.entries) == 0 {
		s.entries = make([]entry, 1, 2)
	} else {
		s.entries = s.entries[:1]
	}
	s.entries[0].child = -1
	s.entries[0].next = -1
}

type entry struct {
	// Use -1 to indicate no child or no sibling.
	child int
	next  int

	name     []byte
	kind     keyKind
	explicit bool
	kv       bool
}

// Find the index of the child of parentIdx with key k. Returns -1 if
// it does not exist.
func (s *SeenTracker) find(parentIdx int, k []byte) int {
	for i := s.entries[parentIdx].child; i >= 0; i = s.entries[i].next {
		if bytes.Equal(s.entries[i].name, k) {
			return i
		}
	}
	return -1
}

// Remove all descendants of node at position idx.
func (s *SeenTracker) clear(idx int) {
	if idx >= len(s.entries) {
		return
	}

	for i := s.entries[idx].child; i >= 0; {
		next := s.entries[i].next
		n := s.entries[0].next
		s.entries[0].next = i
		s.entries[i].next = n
		s.entries[i].name = nil
		s.clear(i)
		i = next
	}

	s.entries[idx].child = -1
}

func (s *SeenTracker) create(parentIdx int, name []byte, kind keyKind, explicit bool, kv bool) int {
	e := entry{
		child: -1,
		next:  s.entries[parentIdx].child,

		name:     name,
		kind:     kind,
		explicit: explicit,
		kv:       kv,
	}
	var idx int
	if s.entries[0].next >= 0 {
		idx = s.entries[0].next
		s.entries[0].next = s.entries[idx].next
		s.entries[idx] = e
	} else {
		idx = len(s.entries)
		s.entries = append(s.entries, e)
	}

	s.entries[parentIdx].child = idx

	return idx
}

func (s *SeenTracker) setExplicitFlag(parentIdx int) {
	for i := s.entries[parentIdx].child; i >= 0; i = s.entries[i].next {
		if s.entries[i].kv {
			s.entries[i].explicit = true
			s.entries[i].kv = false
		}
		s.setExplicitFlag(i)
	}
}

// CheckExpression takes a top-level node and checks that it does not contain
// keys that have been seen in previous calls, and validates that types are
// consistent.
func (s *SeenTracker) CheckExpression(node *unstable.Node) error {
	if s.entries == nil {
		s.reset()
	}
	switch node.Kind {
	case unstable.KeyValue:
		return s.checkKeyValue(node)
	case unstable.Table:
		return s.checkTable(node)
	case unstable.ArrayTable:
		return s.checkArrayTable(node)
	default:
		panic(fmt.Errorf("this should not be a top level node type: %s", node.Kind))
	}
}

func (s *SeenTracker) checkTable(node *unstable.Node) error {
	if s.currentIdx >= 0 {
		s.setExplicitFlag(s.currentIdx)
	}

	it := node.Key()

	parentIdx := 0

	// This code is duplicated in checkArrayTable. This is because factoring
	// it in a function requires to copy the iterator, or allocate it to the
	// heap, which is not cheap.
	for it.Next() {
		if it.IsLast() {
			break
		}

		k := it.Node().Data

		idx := s.find(parentIdx, k)

		if idx < 0 {
			idx = s.create(parentIdx, k, tableKind, false, false)
		} else {
			entry := s.entries[idx]
			if entry.kind == valueKind {
				return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
			}
		}
		parentIdx = idx
	}

	k := it.Node().Data
	idx := s.find(parentIdx, k)

	if idx >= 0 {
		kind := s.entries[idx].kind
		if kind != tableKind {
			return fmt.Errorf("toml: key %s should be a table, not a %s", string(k), kind)
		}
		if s.entries[idx].explicit {
			return fmt.Errorf("toml: table %s already exists", string(k))
		}
		s.entries[idx].explicit = true
	} else {
		idx = s.create(parentIdx, k, tableKind, true, false)
	}

	s.currentIdx = idx

	return nil
}

func (s *SeenTracker) checkArrayTable(node *unstable.Node) error {
	if s.currentIdx >= 0 {
		s.setExplicitFlag(s.currentIdx)
	}

	it := node.Key()

	parentIdx := 0

	for it.Next() {
		if it.IsLast() {
			break
		}

		k := it.Node().Data

		idx := s.find(parentIdx, k)

		if idx < 0 {
			idx = s.create(parentIdx, k, tableKind, false, false)
		} else {
			entry := s.entries[idx]
			if entry.kind == valueKind {
				return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
			}
		}

		parentIdx = idx
	}

	k := it.Node().Data
	idx := s.find(parentIdx, k)

	if idx >= 0 {
		kind := s.entries[idx].kind
		if kind != arrayTableKind {
			return fmt.Errorf("toml: key %s already exists as a %s,  but should be an array table", kind, string(k))
		}
		s.clear(idx)
	} else {
		idx = s.create(parentIdx, k, arrayTableKind, true, false)
	}

	s.currentIdx = idx

	return nil
}

func (s *SeenTracker) checkKeyValue(node *unstable.Node) error {
	parentIdx := s.currentIdx
	it := node.Key()

	for it.Next() {
		k := it.Node().Data

		idx := s.find(parentIdx, k)

		if idx < 0 {
			idx = s.create(parentIdx, k, tableKind, false, true)
		} else {
			entry := s.entries[idx]
			if it.IsLast() {
				return fmt.Errorf("toml: key %s is already defined", string(k))
			} else if entry.kind != tableKind {
				return fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
			} else if entry.explicit {
				return fmt.Errorf("toml: cannot redefine table %s that has already been explicitly defined", string(k))
			}
		}

		parentIdx = idx
	}

	s.entries[parentIdx].kind = valueKind

	value := node.Value()

	switch value.Kind {
	case unstable.InlineTable:
		return s.checkInlineTable(value)
	case unstable.Array:
		return s.checkArray(value)
	}

	return nil
}

func (s *SeenTracker) checkArray(node *unstable.Node) error {
	it := node.Children()
	for it.Next() {
		n := it.Node()
		switch n.Kind {
		case unstable.InlineTable:
			err := s.checkInlineTable(n)
			if err != nil {
				return err
			}
		case unstable.Array:
			err := s.checkArray(n)
			if err != nil {
				return err
			}
		}
	}
	return nil
}

func (s *SeenTracker) checkInlineTable(node *unstable.Node) error {
	if pool.New == nil {
		pool.New = func() interface{} {
			return &SeenTracker{}
		}
	}

	s = pool.Get().(*SeenTracker)
	s.reset()

	it := node.Children()
	for it.Next() {
		n := it.Node()
		err := s.checkKeyValue(n)
		if err != nil {
			return err
		}
	}

	// As inline tables are self-contained, the tracker does not
	// need to retain the details of what they contain. The
	// keyValue element that creates the inline table is kept to
	// mark the presence of the inline table and prevent
	// redefinition of its keys: check* functions cannot walk into
	// a value.
	pool.Put(s)
	return nil
}