state.go

Documentation: k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package json
     6  
     7  import (
     8  	"math"
     9  	"strconv"
    10  )
    11  
    12  var (
    13  	errMissingName   = &SyntacticError{str: "missing string for object name"}
    14  	errMissingColon  = &SyntacticError{str: "missing character ':' after object name"}
    15  	errMissingValue  = &SyntacticError{str: "missing value after object name"}
    16  	errMissingComma  = &SyntacticError{str: "missing character ',' after object or array value"}
    17  	errMismatchDelim = &SyntacticError{str: "mismatching structural token for object or array"}
    18  )
    19  
    20  const errInvalidNamespace = jsonError("object namespace is in an invalid state")
    21  
    22  type state struct {
    23  	// tokens validates whether the next token kind is valid.
    24  	tokens stateMachine
    25  
    26  	// names is a stack of object names.
    27  	// Not used if AllowDuplicateNames is true.
    28  	names objectNameStack
    29  
    30  	// namespaces is a stack of object namespaces.
    31  	// For performance reasons, Encoder or Decoder may not update this
    32  	// if Marshal or Unmarshal is able to track names in a more efficient way.
    33  	// See makeMapArshaler and makeStructArshaler.
    34  	// Not used if AllowDuplicateNames is true.
    35  	namespaces objectNamespaceStack
    36  }
    37  
    38  func (s *state) reset() {
    39  	s.tokens.reset()
    40  	s.names.reset()
    41  	s.namespaces.reset()
    42  }
    43  
    44  // appendStackPointer appends a JSON Pointer (RFC 6901) to the current value.
    45  // The returned pointer is only accurate if s.names is populated,
    46  // otherwise it uses the numeric index as the object member name.
    47  //
    48  // Invariant: Must call s.names.copyQuotedBuffer beforehand.
    49  func (s state) appendStackPointer(b []byte) []byte {
    50  	var objectDepth int
    51  	for i := 1; i < s.tokens.depth(); i++ {
    52  		e := s.tokens.index(i)
    53  		if e.length() == 0 {
    54  			break // empty object or array
    55  		}
    56  		b = append(b, '/')
    57  		switch {
    58  		case e.isObject():
    59  			if objectDepth < s.names.length() {
    60  				for _, c := range s.names.getUnquoted(objectDepth) {
    61  					// Per RFC 6901, section 3, escape '~' and '/' characters.
    62  					switch c {
    63  					case '~':
    64  						b = append(b, "~0"...)
    65  					case '/':
    66  						b = append(b, "~1"...)
    67  					default:
    68  						b = append(b, c)
    69  					}
    70  				}
    71  			} else {
    72  				// Since the names stack is unpopulated, the name is unknown.
    73  				// As a best-effort replacement, use the numeric member index.
    74  				// While inaccurate, it produces a syntactically valid pointer.
    75  				b = strconv.AppendUint(b, uint64((e.length()-1)/2), 10)
    76  			}
    77  			objectDepth++
    78  		case e.isArray():
    79  			b = strconv.AppendUint(b, uint64(e.length()-1), 10)
    80  		}
    81  	}
    82  	return b
    83  }
    84  
    85  // stateMachine is a push-down automaton that validates whether
    86  // a sequence of tokens is valid or not according to the JSON grammar.
    87  // It is useful for both encoding and decoding.
    88  //
    89  // It is a stack where each entry represents a nested JSON object or array.
    90  // The stack has a minimum depth of 1 where the first level is a
    91  // virtual JSON array to handle a stream of top-level JSON values.
    92  // The top-level virtual JSON array is special in that it doesn't require commas
    93  // between each JSON value.
    94  //
    95  // For performance, most methods are carefully written to be inlineable.
    96  // The zero value is a valid state machine ready for use.
    97  type stateMachine struct {
    98  	stack []stateEntry
    99  	last  stateEntry
   100  }
   101  
   102  // reset resets the state machine.
   103  // The machine always starts with a minimum depth of 1.
   104  func (m *stateMachine) reset() {
   105  	m.stack = m.stack[:0]
   106  	if cap(m.stack) > 1<<10 {
   107  		m.stack = nil
   108  	}
   109  	m.last = stateTypeArray
   110  }
   111  
   112  // depth is the current nested depth of JSON objects and arrays.
   113  // It is one-indexed (i.e., top-level values have a depth of 1).
   114  func (m stateMachine) depth() int {
   115  	return len(m.stack) + 1
   116  }
   117  
   118  // index returns a reference to the ith entry.
   119  // It is only valid until the next push method call.
   120  func (m *stateMachine) index(i int) *stateEntry {
   121  	if i == len(m.stack) {
   122  		return &m.last
   123  	}
   124  	return &m.stack[i]
   125  }
   126  
   127  // depthLength reports the current nested depth and
   128  // the length of the last JSON object or array.
   129  func (m stateMachine) depthLength() (int, int) {
   130  	return m.depth(), m.last.length()
   131  }
   132  
   133  // appendLiteral appends a JSON literal as the next token in the sequence.
   134  // If an error is returned, the state is not mutated.
   135  func (m *stateMachine) appendLiteral() error {
   136  	switch {
   137  	case m.last.needObjectName():
   138  		return errMissingName
   139  	case !m.last.isValidNamespace():
   140  		return errInvalidNamespace
   141  	default:
   142  		m.last.increment()
   143  		return nil
   144  	}
   145  }
   146  
   147  // appendString appends a JSON string as the next token in the sequence.
   148  // If an error is returned, the state is not mutated.
   149  func (m *stateMachine) appendString() error {
   150  	switch {
   151  	case !m.last.isValidNamespace():
   152  		return errInvalidNamespace
   153  	default:
   154  		m.last.increment()
   155  		return nil
   156  	}
   157  }
   158  
   159  // appendNumber appends a JSON number as the next token in the sequence.
   160  // If an error is returned, the state is not mutated.
   161  func (m *stateMachine) appendNumber() error {
   162  	return m.appendLiteral()
   163  }
   164  
   165  // pushObject appends a JSON start object token as next in the sequence.
   166  // If an error is returned, the state is not mutated.
   167  func (m *stateMachine) pushObject() error {
   168  	switch {
   169  	case m.last.needObjectName():
   170  		return errMissingName
   171  	case !m.last.isValidNamespace():
   172  		return errInvalidNamespace
   173  	default:
   174  		m.last.increment()
   175  		m.stack = append(m.stack, m.last)
   176  		m.last = stateTypeObject
   177  		return nil
   178  	}
   179  }
   180  
   181  // popObject appends a JSON end object token as next in the sequence.
   182  // If an error is returned, the state is not mutated.
   183  func (m *stateMachine) popObject() error {
   184  	switch {
   185  	case !m.last.isObject():
   186  		return errMismatchDelim
   187  	case m.last.needObjectValue():
   188  		return errMissingValue
   189  	case !m.last.isValidNamespace():
   190  		return errInvalidNamespace
   191  	default:
   192  		m.last = m.stack[len(m.stack)-1]
   193  		m.stack = m.stack[:len(m.stack)-1]
   194  		return nil
   195  	}
   196  }
   197  
   198  // pushArray appends a JSON start array token as next in the sequence.
   199  // If an error is returned, the state is not mutated.
   200  func (m *stateMachine) pushArray() error {
   201  	switch {
   202  	case m.last.needObjectName():
   203  		return errMissingName
   204  	case !m.last.isValidNamespace():
   205  		return errInvalidNamespace
   206  	default:
   207  		m.last.increment()
   208  		m.stack = append(m.stack, m.last)
   209  		m.last = stateTypeArray
   210  		return nil
   211  	}
   212  }
   213  
   214  // popArray appends a JSON end array token as next in the sequence.
   215  // If an error is returned, the state is not mutated.
   216  func (m *stateMachine) popArray() error {
   217  	switch {
   218  	case !m.last.isArray() || len(m.stack) == 0: // forbid popping top-level virtual JSON array
   219  		return errMismatchDelim
   220  	case !m.last.isValidNamespace():
   221  		return errInvalidNamespace
   222  	default:
   223  		m.last = m.stack[len(m.stack)-1]
   224  		m.stack = m.stack[:len(m.stack)-1]
   225  		return nil
   226  	}
   227  }
   228  
   229  // needIndent reports whether indent whitespace should be injected.
   230  // A zero value means that no whitespace should be injected.
   231  // A positive value means '\n', indentPrefix, and (n-1) copies of indentBody
   232  // should be appended to the output immediately before the next token.
   233  func (m stateMachine) needIndent(next Kind) (n int) {
   234  	willEnd := next == '}' || next == ']'
   235  	switch {
   236  	case m.depth() == 1:
   237  		return 0 // top-level values are never indented
   238  	case m.last.length() == 0 && willEnd:
   239  		return 0 // an empty object or array is never indented
   240  	case m.last.length() == 0 || m.last.needImplicitComma(next):
   241  		return m.depth()
   242  	case willEnd:
   243  		return m.depth() - 1
   244  	default:
   245  		return 0
   246  	}
   247  }
   248  
   249  // mayAppendDelim appends a colon or comma that may precede the next token.
   250  func (m stateMachine) mayAppendDelim(b []byte, next Kind) []byte {
   251  	switch {
   252  	case m.last.needImplicitColon():
   253  		return append(b, ':')
   254  	case m.last.needImplicitComma(next) && len(m.stack) != 0: // comma not needed for top-level values
   255  		return append(b, ',')
   256  	default:
   257  		return b
   258  	}
   259  }
   260  
   261  // needDelim reports whether a colon or comma token should be implicitly emitted
   262  // before the next token of the specified kind.
   263  // A zero value means no delimiter should be emitted.
   264  func (m stateMachine) needDelim(next Kind) (delim byte) {
   265  	switch {
   266  	case m.last.needImplicitColon():
   267  		return ':'
   268  	case m.last.needImplicitComma(next) && len(m.stack) != 0: // comma not needed for top-level values
   269  		return ','
   270  	default:
   271  		return 0
   272  	}
   273  }
   274  
   275  // checkDelim reports whether the specified delimiter should be there given
   276  // the kind of the next token that appears immediately afterwards.
   277  func (m stateMachine) checkDelim(delim byte, next Kind) error {
   278  	switch needDelim := m.needDelim(next); {
   279  	case needDelim == delim:
   280  		return nil
   281  	case needDelim == ':':
   282  		return errMissingColon
   283  	case needDelim == ',':
   284  		return errMissingComma
   285  	default:
   286  		return newInvalidCharacterError([]byte{delim}, "before next token")
   287  	}
   288  }
   289  
   290  // invalidateDisabledNamespaces marks all disabled namespaces as invalid.
   291  //
   292  // For efficiency, Marshal and Unmarshal may disable namespaces since there are
   293  // more efficient ways to track duplicate names. However, if an error occurs,
   294  // the namespaces in Encoder or Decoder will be left in an inconsistent state.
   295  // Mark the namespaces as invalid so that future method calls on
   296  // Encoder or Decoder will return an error.
   297  func (m *stateMachine) invalidateDisabledNamespaces() {
   298  	for i := 0; i < m.depth(); i++ {
   299  		e := m.index(i)
   300  		if !e.isActiveNamespace() {
   301  			e.invalidateNamespace()
   302  		}
   303  	}
   304  }
   305  
   306  // stateEntry encodes several artifacts within a single unsigned integer:
   307  //   - whether this represents a JSON object or array,
   308  //   - whether this object should check for duplicate names, and
   309  //   - how many elements are in this JSON object or array.
   310  type stateEntry uint64
   311  
   312  const (
   313  	// The type mask (1 bit) records whether this is a JSON object or array.
   314  	stateTypeMask   stateEntry = 0x8000_0000_0000_0000
   315  	stateTypeObject stateEntry = 0x8000_0000_0000_0000
   316  	stateTypeArray  stateEntry = 0x0000_0000_0000_0000
   317  
   318  	// The name check mask (2 bit) records whether to update
   319  	// the namespaces for the current JSON object and
   320  	// whether the namespace is valid.
   321  	stateNamespaceMask    stateEntry = 0x6000_0000_0000_0000
   322  	stateDisableNamespace stateEntry = 0x4000_0000_0000_0000
   323  	stateInvalidNamespace stateEntry = 0x2000_0000_0000_0000
   324  
   325  	// The count mask (61 bits) records the number of elements.
   326  	stateCountMask    stateEntry = 0x1fff_ffff_ffff_ffff
   327  	stateCountLSBMask stateEntry = 0x0000_0000_0000_0001
   328  	stateCountOdd     stateEntry = 0x0000_0000_0000_0001
   329  	stateCountEven    stateEntry = 0x0000_0000_0000_0000
   330  )
   331  
   332  // length reports the number of elements in the JSON object or array.
   333  // Each name and value in an object entry is treated as a separate element.
   334  func (e stateEntry) length() int {
   335  	return int(e & stateCountMask)
   336  }
   337  
   338  // isObject reports whether this is a JSON object.
   339  func (e stateEntry) isObject() bool {
   340  	return e&stateTypeMask == stateTypeObject
   341  }
   342  
   343  // isArray reports whether this is a JSON array.
   344  func (e stateEntry) isArray() bool {
   345  	return e&stateTypeMask == stateTypeArray
   346  }
   347  
   348  // needObjectName reports whether the next token must be a JSON string,
   349  // which is necessary for JSON object names.
   350  func (e stateEntry) needObjectName() bool {
   351  	return e&(stateTypeMask|stateCountLSBMask) == stateTypeObject|stateCountEven
   352  }
   353  
   354  // needImplicitColon reports whether an colon should occur next,
   355  // which always occurs after JSON object names.
   356  func (e stateEntry) needImplicitColon() bool {
   357  	return e.needObjectValue()
   358  }
   359  
   360  // needObjectValue reports whether the next token must be a JSON value,
   361  // which is necessary after every JSON object name.
   362  func (e stateEntry) needObjectValue() bool {
   363  	return e&(stateTypeMask|stateCountLSBMask) == stateTypeObject|stateCountOdd
   364  }
   365  
   366  // needImplicitComma reports whether an comma should occur next,
   367  // which always occurs after a value in a JSON object or array
   368  // before the next value (or name).
   369  func (e stateEntry) needImplicitComma(next Kind) bool {
   370  	return !e.needObjectValue() && e.length() > 0 && next != '}' && next != ']'
   371  }
   372  
   373  // increment increments the number of elements for the current object or array.
   374  // This assumes that overflow won't practically be an issue since
   375  // 1<<bits.OnesCount(stateCountMask) is sufficiently large.
   376  func (e *stateEntry) increment() {
   377  	(*e)++
   378  }
   379  
   380  // decrement decrements the number of elements for the current object or array.
   381  // It is the callers responsibility to ensure that e.length > 0.
   382  func (e *stateEntry) decrement() {
   383  	(*e)--
   384  }
   385  
   386  // disableNamespace disables the JSON object namespace such that the
   387  // Encoder or Decoder no longer updates the namespace.
   388  func (e *stateEntry) disableNamespace() {
   389  	*e |= stateDisableNamespace
   390  }
   391  
   392  // isActiveNamespace reports whether the JSON object namespace is actively
   393  // being updated and used for duplicate name checks.
   394  func (e stateEntry) isActiveNamespace() bool {
   395  	return e&(stateDisableNamespace) == 0
   396  }
   397  
   398  // invalidateNamespace marks the JSON object namespace as being invalid.
   399  func (e *stateEntry) invalidateNamespace() {
   400  	*e |= stateInvalidNamespace
   401  }
   402  
   403  // isValidNamespace reports whether the JSON object namespace is valid.
   404  func (e stateEntry) isValidNamespace() bool {
   405  	return e&(stateInvalidNamespace) == 0
   406  }
   407  
   408  // objectNameStack is a stack of names when descending into a JSON object.
   409  // In contrast to objectNamespaceStack, this only has to remember a single name
   410  // per JSON object.
   411  //
   412  // This data structure may contain offsets to encodeBuffer or decodeBuffer.
   413  // It violates clean abstraction of layers, but is significantly more efficient.
   414  // This ensures that popping and pushing in the common case is a trivial
   415  // push/pop of an offset integer.
   416  //
   417  // The zero value is an empty names stack ready for use.
   418  type objectNameStack struct {
   419  	// offsets is a stack of offsets for each name.
   420  	// A non-negative offset is the ending offset into the local names buffer.
   421  	// A negative offset is the bit-wise inverse of a starting offset into
   422  	// a remote buffer (e.g., encodeBuffer or decodeBuffer).
   423  	// A math.MinInt offset at the end implies that the last object is empty.
   424  	// Invariant: Positive offsets always occur before negative offsets.
   425  	offsets []int
   426  	// unquotedNames is a back-to-back concatenation of names.
   427  	unquotedNames []byte
   428  }
   429  
   430  func (ns *objectNameStack) reset() {
   431  	ns.offsets = ns.offsets[:0]
   432  	ns.unquotedNames = ns.unquotedNames[:0]
   433  	if cap(ns.offsets) > 1<<6 {
   434  		ns.offsets = nil // avoid pinning arbitrarily large amounts of memory
   435  	}
   436  	if cap(ns.unquotedNames) > 1<<10 {
   437  		ns.unquotedNames = nil // avoid pinning arbitrarily large amounts of memory
   438  	}
   439  }
   440  
   441  func (ns *objectNameStack) length() int {
   442  	return len(ns.offsets)
   443  }
   444  
   445  // getUnquoted retrieves the ith unquoted name in the namespace.
   446  // It returns an empty string if the last object is empty.
   447  //
   448  // Invariant: Must call copyQuotedBuffer beforehand.
   449  func (ns *objectNameStack) getUnquoted(i int) []byte {
   450  	ns.ensureCopiedBuffer()
   451  	if i == 0 {
   452  		return ns.unquotedNames[:ns.offsets[0]]
   453  	} else {
   454  		return ns.unquotedNames[ns.offsets[i-1]:ns.offsets[i-0]]
   455  	}
   456  }
   457  
   458  // invalidOffset indicates that the last JSON object currently has no name.
   459  const invalidOffset = math.MinInt
   460  
   461  // push descends into a nested JSON object.
   462  func (ns *objectNameStack) push() {
   463  	ns.offsets = append(ns.offsets, invalidOffset)
   464  }
   465  
   466  // replaceLastQuotedOffset replaces the last name with the starting offset
   467  // to the quoted name in some remote buffer. All offsets provided must be
   468  // relative to the same buffer until copyQuotedBuffer is called.
   469  func (ns *objectNameStack) replaceLastQuotedOffset(i int) {
   470  	// Use bit-wise inversion instead of naive multiplication by -1 to avoid
   471  	// ambiguity regarding zero (which is a valid offset into the names field).
   472  	// Bit-wise inversion is mathematically equivalent to -i-1,
   473  	// such that 0 becomes -1, 1 becomes -2, and so forth.
   474  	// This ensures that remote offsets are always negative.
   475  	ns.offsets[len(ns.offsets)-1] = ^i
   476  }
   477  
   478  // replaceLastUnquotedName replaces the last name with the provided name.
   479  //
   480  // Invariant: Must call copyQuotedBuffer beforehand.
   481  func (ns *objectNameStack) replaceLastUnquotedName(s string) {
   482  	ns.ensureCopiedBuffer()
   483  	var startOffset int
   484  	if len(ns.offsets) > 1 {
   485  		startOffset = ns.offsets[len(ns.offsets)-2]
   486  	}
   487  	ns.unquotedNames = append(ns.unquotedNames[:startOffset], s...)
   488  	ns.offsets[len(ns.offsets)-1] = len(ns.unquotedNames)
   489  }
   490  
   491  // clearLast removes any name in the last JSON object.
   492  // It is semantically equivalent to ns.push followed by ns.pop.
   493  func (ns *objectNameStack) clearLast() {
   494  	ns.offsets[len(ns.offsets)-1] = invalidOffset
   495  }
   496  
   497  // pop ascends out of a nested JSON object.
   498  func (ns *objectNameStack) pop() {
   499  	ns.offsets = ns.offsets[:len(ns.offsets)-1]
   500  }
   501  
   502  // copyQuotedBuffer copies names from the remote buffer into the local names
   503  // buffer so that there are no more offset references into the remote buffer.
   504  // This allows the remote buffer to change contents without affecting
   505  // the names that this data structure is trying to remember.
   506  func (ns *objectNameStack) copyQuotedBuffer(b []byte) {
   507  	// Find the first negative offset.
   508  	var i int
   509  	for i = len(ns.offsets) - 1; i >= 0 && ns.offsets[i] < 0; i-- {
   510  		continue
   511  	}
   512  
   513  	// Copy each name from the remote buffer into the local buffer.
   514  	for i = i + 1; i < len(ns.offsets); i++ {
   515  		if i == len(ns.offsets)-1 && ns.offsets[i] == invalidOffset {
   516  			if i == 0 {
   517  				ns.offsets[i] = 0
   518  			} else {
   519  				ns.offsets[i] = ns.offsets[i-1]
   520  			}
   521  			break // last JSON object had a push without any names
   522  		}
   523  
   524  		// As a form of Hyrum proofing, we write an invalid character into the
   525  		// buffer to make misuse of Decoder.ReadToken more obvious.
   526  		// We need to undo that mutation here.
   527  		quotedName := b[^ns.offsets[i]:]
   528  		if quotedName[0] == invalidateBufferByte {
   529  			quotedName[0] = '"'
   530  		}
   531  
   532  		// Append the unquoted name to the local buffer.
   533  		var startOffset int
   534  		if i > 0 {
   535  			startOffset = ns.offsets[i-1]
   536  		}
   537  		if n := consumeSimpleString(quotedName); n > 0 {
   538  			ns.unquotedNames = append(ns.unquotedNames[:startOffset], quotedName[len(`"`):n-len(`"`)]...)
   539  		} else {
   540  			ns.unquotedNames, _ = unescapeString(ns.unquotedNames[:startOffset], quotedName)
   541  		}
   542  		ns.offsets[i] = len(ns.unquotedNames)
   543  	}
   544  }
   545  
   546  func (ns *objectNameStack) ensureCopiedBuffer() {
   547  	if len(ns.offsets) > 0 && ns.offsets[len(ns.offsets)-1] < 0 {
   548  		panic("BUG: copyQuotedBuffer not called beforehand")
   549  	}
   550  }
   551  
   552  // objectNamespaceStack is a stack of object namespaces.
   553  // This data structure assists in detecting duplicate names.
   554  type objectNamespaceStack []objectNamespace
   555  
   556  // reset resets the object namespace stack.
   557  func (nss *objectNamespaceStack) reset() {
   558  	if cap(*nss) > 1<<10 {
   559  		*nss = nil
   560  	}
   561  	*nss = (*nss)[:0]
   562  }
   563  
   564  // push starts a new namespace for a nested JSON object.
   565  func (nss *objectNamespaceStack) push() {
   566  	if cap(*nss) > len(*nss) {
   567  		*nss = (*nss)[:len(*nss)+1]
   568  		nss.last().reset()
   569  	} else {
   570  		*nss = append(*nss, objectNamespace{})
   571  	}
   572  }
   573  
   574  // last returns a pointer to the last JSON object namespace.
   575  func (nss objectNamespaceStack) last() *objectNamespace {
   576  	return &nss[len(nss)-1]
   577  }
   578  
   579  // pop terminates the namespace for a nested JSON object.
   580  func (nss *objectNamespaceStack) pop() {
   581  	*nss = (*nss)[:len(*nss)-1]
   582  }
   583  
   584  // objectNamespace is the namespace for a JSON object.
   585  // In contrast to objectNameStack, this needs to remember a all names
   586  // per JSON object.
   587  //
   588  // The zero value is an empty namespace ready for use.
   589  type objectNamespace struct {
   590  	// It relies on a linear search over all the names before switching
   591  	// to use a Go map for direct lookup.
   592  
   593  	// endOffsets is a list of offsets to the end of each name in buffers.
   594  	// The length of offsets is the number of names in the namespace.
   595  	endOffsets []uint
   596  	// allUnquotedNames is a back-to-back concatenation of every name in the namespace.
   597  	allUnquotedNames []byte
   598  	// mapNames is a Go map containing every name in the namespace.
   599  	// Only valid if non-nil.
   600  	mapNames map[string]struct{}
   601  }
   602  
   603  // reset resets the namespace to be empty.
   604  func (ns *objectNamespace) reset() {
   605  	ns.endOffsets = ns.endOffsets[:0]
   606  	ns.allUnquotedNames = ns.allUnquotedNames[:0]
   607  	ns.mapNames = nil
   608  	if cap(ns.endOffsets) > 1<<6 {
   609  		ns.endOffsets = nil // avoid pinning arbitrarily large amounts of memory
   610  	}
   611  	if cap(ns.allUnquotedNames) > 1<<10 {
   612  		ns.allUnquotedNames = nil // avoid pinning arbitrarily large amounts of memory
   613  	}
   614  }
   615  
   616  // length reports the number of names in the namespace.
   617  func (ns *objectNamespace) length() int {
   618  	return len(ns.endOffsets)
   619  }
   620  
   621  // getUnquoted retrieves the ith unquoted name in the namespace.
   622  func (ns *objectNamespace) getUnquoted(i int) []byte {
   623  	if i == 0 {
   624  		return ns.allUnquotedNames[:ns.endOffsets[0]]
   625  	} else {
   626  		return ns.allUnquotedNames[ns.endOffsets[i-1]:ns.endOffsets[i-0]]
   627  	}
   628  }
   629  
   630  // lastUnquoted retrieves the last name in the namespace.
   631  func (ns *objectNamespace) lastUnquoted() []byte {
   632  	return ns.getUnquoted(ns.length() - 1)
   633  }
   634  
   635  // insertQuoted inserts a name and reports whether it was inserted,
   636  // which only occurs if name is not already in the namespace.
   637  // The provided name must be a valid JSON string.
   638  func (ns *objectNamespace) insertQuoted(name []byte, isVerbatim bool) bool {
   639  	if isVerbatim {
   640  		name = name[len(`"`) : len(name)-len(`"`)]
   641  	}
   642  	return ns.insert(name, !isVerbatim)
   643  }
   644  func (ns *objectNamespace) insertUnquoted(name []byte) bool {
   645  	return ns.insert(name, false)
   646  }
   647  func (ns *objectNamespace) insert(name []byte, quoted bool) bool {
   648  	var allNames []byte
   649  	if quoted {
   650  		allNames, _ = unescapeString(ns.allUnquotedNames, name)
   651  	} else {
   652  		allNames = append(ns.allUnquotedNames, name...)
   653  	}
   654  	name = allNames[len(ns.allUnquotedNames):]
   655  
   656  	// Switch to a map if the buffer is too large for linear search.
   657  	// This does not add the current name to the map.
   658  	if ns.mapNames == nil && (ns.length() > 64 || len(ns.allUnquotedNames) > 1024) {
   659  		ns.mapNames = make(map[string]struct{})
   660  		var startOffset uint
   661  		for _, endOffset := range ns.endOffsets {
   662  			name := ns.allUnquotedNames[startOffset:endOffset]
   663  			ns.mapNames[string(name)] = struct{}{} // allocates a new string
   664  			startOffset = endOffset
   665  		}
   666  	}
   667  
   668  	if ns.mapNames == nil {
   669  		// Perform linear search over the buffer to find matching names.
   670  		// It provides O(n) lookup, but does not require any allocations.
   671  		var startOffset uint
   672  		for _, endOffset := range ns.endOffsets {
   673  			if string(ns.allUnquotedNames[startOffset:endOffset]) == string(name) {
   674  				return false
   675  			}
   676  			startOffset = endOffset
   677  		}
   678  	} else {
   679  		// Use the map if it is populated.
   680  		// It provides O(1) lookup, but requires a string allocation per name.
   681  		if _, ok := ns.mapNames[string(name)]; ok {
   682  			return false
   683  		}
   684  		ns.mapNames[string(name)] = struct{}{} // allocates a new string
   685  	}
   686  
   687  	ns.allUnquotedNames = allNames
   688  	ns.endOffsets = append(ns.endOffsets, uint(len(ns.allUnquotedNames)))
   689  	return true
   690  }
   691  
   692  // removeLast removes the last name in the namespace.
   693  func (ns *objectNamespace) removeLast() {
   694  	if ns.mapNames != nil {
   695  		delete(ns.mapNames, string(ns.lastUnquoted()))
   696  	}
   697  	if ns.length()-1 == 0 {
   698  		ns.endOffsets = ns.endOffsets[:0]
   699  		ns.allUnquotedNames = ns.allUnquotedNames[:0]
   700  	} else {
   701  		ns.endOffsets = ns.endOffsets[:ns.length()-1]
   702  		ns.allUnquotedNames = ns.allUnquotedNames[:ns.endOffsets[ns.length()-1]]
   703  	}
   704  }
   705  
   706  type uintSet64 uint64
   707  
   708  func (s uintSet64) has(i uint) bool { return s&(1<<i) > 0 }
   709  func (s *uintSet64) set(i uint)     { *s |= 1 << i }
   710  
   711  // uintSet is a set of unsigned integers.
   712  // It is optimized for most integers being close to zero.
   713  type uintSet struct {
   714  	lo uintSet64
   715  	hi []uintSet64
   716  }
   717  
   718  // has reports whether i is in the set.
   719  func (s *uintSet) has(i uint) bool {
   720  	if i < 64 {
   721  		return s.lo.has(i)
   722  	} else {
   723  		i -= 64
   724  		iHi, iLo := int(i/64), i%64
   725  		return iHi < len(s.hi) && s.hi[iHi].has(iLo)
   726  	}
   727  }
   728  
   729  // insert inserts i into the set and reports whether it was the first insertion.
   730  func (s *uintSet) insert(i uint) bool {
   731  	// TODO: Make this inlineable at least for the lower 64-bit case.
   732  	if i < 64 {
   733  		has := s.lo.has(i)
   734  		s.lo.set(i)
   735  		return !has
   736  	} else {
   737  		i -= 64
   738  		iHi, iLo := int(i/64), i%64
   739  		if iHi >= len(s.hi) {
   740  			s.hi = append(s.hi, make([]uintSet64, iHi+1-len(s.hi))...)
   741  			s.hi = s.hi[:cap(s.hi)]
   742  		}
   743  		has := s.hi[iHi].has(iLo)
   744  		s.hi[iHi].set(iLo)
   745  		return !has
   746  	}
   747  }
   748
View as plain text