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. It returns true if it is the first time this node's key is seen.
   153  // Useful to clear array tables on first use.
   154  func (s *SeenTracker) CheckExpression(node *unstable.Node) (bool, error) {
   155  	if s.entries == nil {
   156  		s.reset()
   157  	}
   158  	switch node.Kind {
   159  	case unstable.KeyValue:
   160  		return s.checkKeyValue(node)
   161  	case unstable.Table:
   162  		return s.checkTable(node)
   163  	case unstable.ArrayTable:
   164  		return s.checkArrayTable(node)
   165  	default:
   166  		panic(fmt.Errorf("this should not be a top level node type: %s", node.Kind))
   167  	}
   168  }
   169  
   170  func (s *SeenTracker) checkTable(node *unstable.Node) (bool, error) {
   171  	if s.currentIdx >= 0 {
   172  		s.setExplicitFlag(s.currentIdx)
   173  	}
   174  
   175  	it := node.Key()
   176  
   177  	parentIdx := 0
   178  
   179  	// This code is duplicated in checkArrayTable. This is because factoring
   180  	// it in a function requires to copy the iterator, or allocate it to the
   181  	// heap, which is not cheap.
   182  	for it.Next() {
   183  		if it.IsLast() {
   184  			break
   185  		}
   186  
   187  		k := it.Node().Data
   188  
   189  		idx := s.find(parentIdx, k)
   190  
   191  		if idx < 0 {
   192  			idx = s.create(parentIdx, k, tableKind, false, false)
   193  		} else {
   194  			entry := s.entries[idx]
   195  			if entry.kind == valueKind {
   196  				return false, fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
   197  			}
   198  		}
   199  		parentIdx = idx
   200  	}
   201  
   202  	k := it.Node().Data
   203  	idx := s.find(parentIdx, k)
   204  
   205  	first := false
   206  	if idx >= 0 {
   207  		kind := s.entries[idx].kind
   208  		if kind != tableKind {
   209  			return false, fmt.Errorf("toml: key %s should be a table, not a %s", string(k), kind)
   210  		}
   211  		if s.entries[idx].explicit {
   212  			return false, fmt.Errorf("toml: table %s already exists", string(k))
   213  		}
   214  		s.entries[idx].explicit = true
   215  	} else {
   216  		idx = s.create(parentIdx, k, tableKind, true, false)
   217  		first = true
   218  	}
   219  
   220  	s.currentIdx = idx
   221  
   222  	return first, nil
   223  }
   224  
   225  func (s *SeenTracker) checkArrayTable(node *unstable.Node) (bool, error) {
   226  	if s.currentIdx >= 0 {
   227  		s.setExplicitFlag(s.currentIdx)
   228  	}
   229  
   230  	it := node.Key()
   231  
   232  	parentIdx := 0
   233  
   234  	for it.Next() {
   235  		if it.IsLast() {
   236  			break
   237  		}
   238  
   239  		k := it.Node().Data
   240  
   241  		idx := s.find(parentIdx, k)
   242  
   243  		if idx < 0 {
   244  			idx = s.create(parentIdx, k, tableKind, false, false)
   245  		} else {
   246  			entry := s.entries[idx]
   247  			if entry.kind == valueKind {
   248  				return false, fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
   249  			}
   250  		}
   251  
   252  		parentIdx = idx
   253  	}
   254  
   255  	k := it.Node().Data
   256  	idx := s.find(parentIdx, k)
   257  
   258  	firstTime := idx < 0
   259  	if firstTime {
   260  		idx = s.create(parentIdx, k, arrayTableKind, true, false)
   261  	} else {
   262  		kind := s.entries[idx].kind
   263  		if kind != arrayTableKind {
   264  			return false, fmt.Errorf("toml: key %s already exists as a %s,  but should be an array table", kind, string(k))
   265  		}
   266  		s.clear(idx)
   267  	}
   268  
   269  	s.currentIdx = idx
   270  
   271  	return firstTime, nil
   272  }
   273  
   274  func (s *SeenTracker) checkKeyValue(node *unstable.Node) (bool, error) {
   275  	parentIdx := s.currentIdx
   276  	it := node.Key()
   277  
   278  	for it.Next() {
   279  		k := it.Node().Data
   280  
   281  		idx := s.find(parentIdx, k)
   282  
   283  		if idx < 0 {
   284  			idx = s.create(parentIdx, k, tableKind, false, true)
   285  		} else {
   286  			entry := s.entries[idx]
   287  			if it.IsLast() {
   288  				return false, fmt.Errorf("toml: key %s is already defined", string(k))
   289  			} else if entry.kind != tableKind {
   290  				return false, fmt.Errorf("toml: expected %s to be a table, not a %s", string(k), entry.kind)
   291  			} else if entry.explicit {
   292  				return false, fmt.Errorf("toml: cannot redefine table %s that has already been explicitly defined", string(k))
   293  			}
   294  		}
   295  
   296  		parentIdx = idx
   297  	}
   298  
   299  	s.entries[parentIdx].kind = valueKind
   300  
   301  	value := node.Value()
   302  
   303  	switch value.Kind {
   304  	case unstable.InlineTable:
   305  		return s.checkInlineTable(value)
   306  	case unstable.Array:
   307  		return s.checkArray(value)
   308  	}
   309  
   310  	return false, nil
   311  }
   312  
   313  func (s *SeenTracker) checkArray(node *unstable.Node) (first bool, err error) {
   314  	it := node.Children()
   315  	for it.Next() {
   316  		n := it.Node()
   317  		switch n.Kind {
   318  		case unstable.InlineTable:
   319  			first, err = s.checkInlineTable(n)
   320  			if err != nil {
   321  				return false, err
   322  			}
   323  		case unstable.Array:
   324  			first, err = s.checkArray(n)
   325  			if err != nil {
   326  				return false, err
   327  			}
   328  		}
   329  	}
   330  	return first, nil
   331  }
   332  
   333  func (s *SeenTracker) checkInlineTable(node *unstable.Node) (first bool, err error) {
   334  	if pool.New == nil {
   335  		pool.New = func() interface{} {
   336  			return &SeenTracker{}
   337  		}
   338  	}
   339  
   340  	s = pool.Get().(*SeenTracker)
   341  	s.reset()
   342  
   343  	it := node.Children()
   344  	for it.Next() {
   345  		n := it.Node()
   346  		first, err = s.checkKeyValue(n)
   347  		if err != nil {
   348  			return false, err
   349  		}
   350  	}
   351  
   352  	// As inline tables are self-contained, the tracker does not
   353  	// need to retain the details of what they contain. The
   354  	// keyValue element that creates the inline table is kept to
   355  	// mark the presence of the inline table and prevent
   356  	// redefinition of its keys: check* functions cannot walk into
   357  	// a value.
   358  	pool.Put(s)
   359  	return first, nil
   360  }
   361
View as plain text