seen.go

Documentation: github.com/pelletier/go-toml/v2/internal/tracker

     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
View as plain text