123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356 |
- package tracker
- import (
- "bytes"
- "fmt"
- "sync"
- "github.com/pelletier/go-toml/v2/internal/ast"
- )
- 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 *ast.Node) error {
- if s.entries == nil {
- s.reset()
- }
- switch node.Kind {
- case ast.KeyValue:
- return s.checkKeyValue(node)
- case ast.Table:
- return s.checkTable(node)
- case ast.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 *ast.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 *ast.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 *ast.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 ast.InlineTable:
- return s.checkInlineTable(value)
- case ast.Array:
- return s.checkArray(value)
- }
- return nil
- }
- func (s *SeenTracker) checkArray(node *ast.Node) error {
- it := node.Children()
- for it.Next() {
- n := it.Node()
- switch n.Kind {
- case ast.InlineTable:
- err := s.checkInlineTable(n)
- if err != nil {
- return err
- }
- case ast.Array:
- err := s.checkArray(n)
- if err != nil {
- return err
- }
- }
- }
- return nil
- }
- func (s *SeenTracker) checkInlineTable(node *ast.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
- }
|