state.go 27 KB

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