value.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393
  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. "bytes"
  7. "errors"
  8. "io"
  9. "slices"
  10. "sync"
  11. "github.com/go-json-experiment/json/internal/jsonflags"
  12. "github.com/go-json-experiment/json/internal/jsonwire"
  13. )
  14. // NOTE: Value is analogous to v1 json.RawMessage.
  15. // AppendFormat formats the JSON value in src and appends it to dst
  16. // according to the specified options.
  17. // See [Value.Format] for more details about the formatting behavior.
  18. //
  19. // The dst and src may overlap.
  20. // If an error is reported, then the entirety of src is appended to dst.
  21. func AppendFormat(dst, src []byte, opts ...Options) ([]byte, error) {
  22. e := getBufferedEncoder(opts...)
  23. defer putBufferedEncoder(e)
  24. e.s.Flags.Set(jsonflags.OmitTopLevelNewline | 1)
  25. if err := e.s.WriteValue(src); err != nil {
  26. return append(dst, src...), err
  27. }
  28. return append(dst, e.s.Buf...), nil
  29. }
  30. // Value represents a single raw JSON value, which may be one of the following:
  31. // - a JSON literal (i.e., null, true, or false)
  32. // - a JSON string (e.g., "hello, world!")
  33. // - a JSON number (e.g., 123.456)
  34. // - an entire JSON object (e.g., {"fizz":"buzz"} )
  35. // - an entire JSON array (e.g., [1,2,3] )
  36. //
  37. // Value can represent entire array or object values, while [Token] cannot.
  38. // Value may contain leading and/or trailing whitespace.
  39. type Value []byte
  40. // Clone returns a copy of v.
  41. func (v Value) Clone() Value {
  42. return bytes.Clone(v)
  43. }
  44. // String returns the string formatting of v.
  45. func (v Value) String() string {
  46. if v == nil {
  47. return "null"
  48. }
  49. return string(v)
  50. }
  51. // IsValid reports whether the raw JSON value is syntactically valid
  52. // according to the specified options.
  53. //
  54. // By default (if no options are specified), it validates according to RFC 7493.
  55. // It verifies whether the input is properly encoded as UTF-8,
  56. // that escape sequences within strings decode to valid Unicode codepoints, and
  57. // that all names in each object are unique.
  58. // It does not verify whether numbers are representable within the limits
  59. // of any common numeric type (e.g., float64, int64, or uint64).
  60. //
  61. // Relevant options include:
  62. // - [AllowDuplicateNames]
  63. // - [AllowInvalidUTF8]
  64. //
  65. // All other options are ignored.
  66. func (v Value) IsValid(opts ...Options) bool {
  67. // TODO: Document support for [WithByteLimit] and [WithDepthLimit].
  68. d := getBufferedDecoder(v, opts...)
  69. defer putBufferedDecoder(d)
  70. _, errVal := d.ReadValue()
  71. _, errEOF := d.ReadToken()
  72. return errVal == nil && errEOF == io.EOF
  73. }
  74. // Format formats the raw JSON value in place.
  75. //
  76. // By default (if no options are specified), it validates according to RFC 7493
  77. // and produces the minimal JSON representation, where
  78. // all whitespace is elided and JSON strings use the shortest encoding.
  79. //
  80. // Relevant options include:
  81. // - [AllowDuplicateNames]
  82. // - [AllowInvalidUTF8]
  83. // - [EscapeForHTML]
  84. // - [EscapeForJS]
  85. // - [PreserveRawStrings]
  86. // - [CanonicalizeRawInts]
  87. // - [CanonicalizeRawFloats]
  88. // - [ReorderRawObjects]
  89. // - [SpaceAfterColon]
  90. // - [SpaceAfterComma]
  91. // - [Multiline]
  92. // - [WithIndent]
  93. // - [WithIndentPrefix]
  94. //
  95. // All other options are ignored.
  96. //
  97. // It is guaranteed to succeed if the value is valid according to the same options.
  98. // If the value is already formatted, then the buffer is not mutated.
  99. func (v *Value) Format(opts ...Options) error {
  100. // TODO: Document support for [WithByteLimit] and [WithDepthLimit].
  101. return v.format(opts, nil)
  102. }
  103. // format accepts two []Options to avoid the allocation appending them together.
  104. // It is equivalent to v.Format(append(opts1, opts2...)...).
  105. func (v *Value) format(opts1, opts2 []Options) error {
  106. e := getBufferedEncoder(opts1...)
  107. defer putBufferedEncoder(e)
  108. e.s.Join(opts2...)
  109. e.s.Flags.Set(jsonflags.OmitTopLevelNewline | 1)
  110. if err := e.s.WriteValue(*v); err != nil {
  111. return err
  112. }
  113. if !bytes.Equal(*v, e.s.Buf) {
  114. *v = append((*v)[:0], e.s.Buf...)
  115. }
  116. return nil
  117. }
  118. // Compact removes all whitespace from the raw JSON value.
  119. //
  120. // It does not reformat JSON strings or numbers to use any other representation.
  121. // To maximize the set of JSON values that can be formatted,
  122. // this permits values with duplicate names and invalid UTF-8.
  123. //
  124. // Compact is equivalent to calling [Value.Format] with the following options:
  125. // - [AllowDuplicateNames](true)
  126. // - [AllowInvalidUTF8](true)
  127. // - [PreserveRawStrings](true)
  128. //
  129. // Any options specified by the caller are applied after the initial set
  130. // and may deliberately override prior options.
  131. func (v *Value) Compact(opts ...Options) error {
  132. return v.format([]Options{
  133. AllowDuplicateNames(true),
  134. AllowInvalidUTF8(true),
  135. PreserveRawStrings(true),
  136. }, opts)
  137. }
  138. // Indent reformats the whitespace in the raw JSON value so that each element
  139. // in a JSON object or array begins on a indented line according to the nesting.
  140. //
  141. // It does not reformat JSON strings or numbers to use any other representation.
  142. // To maximize the set of JSON values that can be formatted,
  143. // this permits values with duplicate names and invalid UTF-8.
  144. //
  145. // Indent is equivalent to calling [Value.Format] with the following options:
  146. // - [AllowDuplicateNames](true)
  147. // - [AllowInvalidUTF8](true)
  148. // - [PreserveRawStrings](true)
  149. // - [Multiline](true)
  150. //
  151. // Any options specified by the caller are applied after the initial set
  152. // and may deliberately override prior options.
  153. func (v *Value) Indent(opts ...Options) error {
  154. return v.format([]Options{
  155. AllowDuplicateNames(true),
  156. AllowInvalidUTF8(true),
  157. PreserveRawStrings(true),
  158. Multiline(true),
  159. }, opts)
  160. }
  161. // Canonicalize canonicalizes the raw JSON value according to the
  162. // JSON Canonicalization Scheme (JCS) as defined by RFC 8785
  163. // where it produces a stable representation of a JSON value.
  164. //
  165. // JSON strings are formatted to use their minimal representation,
  166. // JSON numbers are formatted as double precision numbers according
  167. // to some stable serialization algorithm.
  168. // JSON object members are sorted in ascending order by name.
  169. // All whitespace is removed.
  170. //
  171. // The output stability is dependent on the stability of the application data
  172. // (see RFC 8785, Appendix E). It cannot produce stable output from
  173. // fundamentally unstable input. For example, if the JSON value
  174. // contains ephemeral data (e.g., a frequently changing timestamp),
  175. // then the value is still unstable regardless of whether this is called.
  176. //
  177. // Canonicalize is equivalent to calling [Value.Format] with the following options:
  178. // - [CanonicalizeRawInts](true)
  179. // - [CanonicalizeRawFloats](true)
  180. // - [ReorderRawObjects](true)
  181. //
  182. // Any options specified by the caller are applied after the initial set
  183. // and may deliberately override prior options.
  184. //
  185. // Note that JCS treats all JSON numbers as IEEE 754 double precision numbers.
  186. // Any numbers with precision beyond what is representable by that form
  187. // will lose their precision when canonicalized. For example, integer values
  188. // beyond ±2⁵³ will lose their precision. To preserve the original representation
  189. // of JSON integers, additionally set [CanonicalizeRawInts] to false:
  190. //
  191. // v.Canonicalize(jsontext.CanonicalizeRawInts(false))
  192. func (v *Value) Canonicalize(opts ...Options) error {
  193. return v.format([]Options{
  194. CanonicalizeRawInts(true),
  195. CanonicalizeRawFloats(true),
  196. ReorderRawObjects(true),
  197. }, opts)
  198. }
  199. // MarshalJSON returns v as the JSON encoding of v.
  200. // It returns the stored value as the raw JSON output without any validation.
  201. // If v is nil, then this returns a JSON null.
  202. func (v Value) MarshalJSON() ([]byte, error) {
  203. // NOTE: This matches the behavior of v1 json.RawMessage.MarshalJSON.
  204. if v == nil {
  205. return []byte("null"), nil
  206. }
  207. return v, nil
  208. }
  209. // UnmarshalJSON sets v as the JSON encoding of b.
  210. // It stores a copy of the provided raw JSON input without any validation.
  211. func (v *Value) UnmarshalJSON(b []byte) error {
  212. // NOTE: This matches the behavior of v1 json.RawMessage.UnmarshalJSON.
  213. if v == nil {
  214. return errors.New("jsontext.Value: UnmarshalJSON on nil pointer")
  215. }
  216. *v = append((*v)[:0], b...)
  217. return nil
  218. }
  219. // Kind returns the starting token kind.
  220. // For a valid value, this will never include '}' or ']'.
  221. func (v Value) Kind() Kind {
  222. if v := v[jsonwire.ConsumeWhitespace(v):]; len(v) > 0 {
  223. return Kind(v[0]).normalize()
  224. }
  225. return invalidKind
  226. }
  227. const commaAndWhitespace = ", \n\r\t"
  228. type objectMember struct {
  229. // name is the unquoted name.
  230. name []byte // e.g., "name"
  231. // buffer is the entirety of the raw JSON object member
  232. // starting from right after the previous member (or opening '{')
  233. // until right after the member value.
  234. buffer []byte // e.g., `, \n\r\t"name": "value"`
  235. }
  236. func (x objectMember) Compare(y objectMember) int {
  237. if c := jsonwire.CompareUTF16(x.name, y.name); c != 0 {
  238. return c
  239. }
  240. // With [AllowDuplicateNames] or [AllowInvalidUTF8],
  241. // names could be identical, so also sort using the member value.
  242. return jsonwire.CompareUTF16(
  243. bytes.TrimLeft(x.buffer, commaAndWhitespace),
  244. bytes.TrimLeft(y.buffer, commaAndWhitespace))
  245. }
  246. var objectMemberPool = sync.Pool{New: func() any { return new([]objectMember) }}
  247. func getObjectMembers() *[]objectMember {
  248. ns := objectMemberPool.Get().(*[]objectMember)
  249. *ns = (*ns)[:0]
  250. return ns
  251. }
  252. func putObjectMembers(ns *[]objectMember) {
  253. if cap(*ns) < 1<<10 {
  254. clear(*ns) // avoid pinning name and buffer
  255. objectMemberPool.Put(ns)
  256. }
  257. }
  258. // mustReorderObjects reorders in-place all object members in a JSON value,
  259. // which must be valid otherwise it panics.
  260. func mustReorderObjects(b []byte) {
  261. // Obtain a buffered encoder just to use its internal buffer as
  262. // a scratch buffer for reordering object members.
  263. e2 := getBufferedEncoder()
  264. defer putBufferedEncoder(e2)
  265. // Disable unnecessary checks to syntactically parse the JSON value.
  266. d := getBufferedDecoder(b)
  267. defer putBufferedDecoder(d)
  268. d.s.Flags.Set(jsonflags.AllowDuplicateNames | jsonflags.AllowInvalidUTF8 | 1)
  269. mustReorderObjectsFromDecoder(d, &e2.s.Buf) // per RFC 8785, section 3.2.3
  270. }
  271. // mustReorderObjectsFromDecoder recursively reorders all object members in place
  272. // according to the ordering specified in RFC 8785, section 3.2.3.
  273. //
  274. // Pre-conditions:
  275. // - The value is valid (i.e., no decoder errors should ever occur).
  276. // - Initial call is provided a Decoder reading from the start of v.
  277. //
  278. // Post-conditions:
  279. // - Exactly one JSON value is read from the Decoder.
  280. // - All fully-parsed JSON objects are reordered by directly moving
  281. // the members in the value buffer.
  282. //
  283. // The runtime is approximately O(n·log(n)) + O(m·log(m)),
  284. // where n is len(v) and m is the total number of object members.
  285. func mustReorderObjectsFromDecoder(d *Decoder, scratch *[]byte) {
  286. switch tok, err := d.ReadToken(); tok.Kind() {
  287. case '{':
  288. // Iterate and collect the name and offsets for every object member.
  289. members := getObjectMembers()
  290. defer putObjectMembers(members)
  291. var prevMember objectMember
  292. isSorted := true
  293. beforeBody := d.InputOffset() // offset after '{'
  294. for d.PeekKind() != '}' {
  295. beforeName := d.InputOffset()
  296. var flags jsonwire.ValueFlags
  297. name, _ := d.s.ReadValue(&flags)
  298. name = jsonwire.UnquoteMayCopy(name, flags.IsVerbatim())
  299. mustReorderObjectsFromDecoder(d, scratch)
  300. afterValue := d.InputOffset()
  301. currMember := objectMember{name, d.s.buf[beforeName:afterValue]}
  302. if isSorted && len(*members) > 0 {
  303. isSorted = objectMember.Compare(prevMember, currMember) < 0
  304. }
  305. *members = append(*members, currMember)
  306. prevMember = currMember
  307. }
  308. afterBody := d.InputOffset() // offset before '}'
  309. d.ReadToken()
  310. // Sort the members; return early if it's already sorted.
  311. if isSorted {
  312. return
  313. }
  314. firstBufferBeforeSorting := (*members)[0].buffer
  315. slices.SortFunc(*members, objectMember.Compare)
  316. firstBufferAfterSorting := (*members)[0].buffer
  317. // Append the reordered members to a new buffer,
  318. // then copy the reordered members back over the original members.
  319. // Avoid swapping in place since each member may be a different size
  320. // where moving a member over a smaller member may corrupt the data
  321. // for subsequent members before they have been moved.
  322. //
  323. // The following invariant must hold:
  324. // sum([m.after-m.before for m in members]) == afterBody-beforeBody
  325. commaAndWhitespacePrefix := func(b []byte) []byte {
  326. return b[:len(b)-len(bytes.TrimLeft(b, commaAndWhitespace))]
  327. }
  328. sorted := (*scratch)[:0]
  329. for i, member := range *members {
  330. switch {
  331. case i == 0 && &member.buffer[0] != &firstBufferBeforeSorting[0]:
  332. // First member after sorting is not the first member before sorting,
  333. // so use the prefix of the first member before sorting.
  334. sorted = append(sorted, commaAndWhitespacePrefix(firstBufferBeforeSorting)...)
  335. sorted = append(sorted, bytes.TrimLeft(member.buffer, commaAndWhitespace)...)
  336. case i != 0 && &member.buffer[0] == &firstBufferBeforeSorting[0]:
  337. // Later member after sorting is the first member before sorting,
  338. // so use the prefix of the first member after sorting.
  339. sorted = append(sorted, commaAndWhitespacePrefix(firstBufferAfterSorting)...)
  340. sorted = append(sorted, bytes.TrimLeft(member.buffer, commaAndWhitespace)...)
  341. default:
  342. sorted = append(sorted, member.buffer...)
  343. }
  344. }
  345. if int(afterBody-beforeBody) != len(sorted) {
  346. panic("BUG: length invariant violated")
  347. }
  348. copy(d.s.buf[beforeBody:afterBody], sorted)
  349. // Update scratch buffer to the largest amount ever used.
  350. if len(sorted) > len(*scratch) {
  351. *scratch = sorted
  352. }
  353. case '[':
  354. for d.PeekKind() != ']' {
  355. mustReorderObjectsFromDecoder(d, scratch)
  356. }
  357. d.ReadToken()
  358. default:
  359. if err != nil {
  360. panic("BUG: " + err.Error())
  361. }
  362. }
  363. }