1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "errors"
7 "fmt"
8 "math"
9 "math/big"
10 "strconv"
11 "strings"
12 "unicode"
13 "unicode/utf8"
14)
15
16// MaxJSONDepth bounds the nesting that FromJSON accepts and that ToJSON and
17// EncodeJSON write. JavaScript engines fail with a stack overflow somewhere
18// in that region; fromJSON reports it like any other parse error. The bound
19// also stops the encoder on cyclic values, which can be built through
20// [Array.Append].
21const MaxJSONDepth = 1000
22
23// FromJSON parses JSON text into a [Value], like the fromJSON function.
24//
25// The reader is Json.NET's, as in the runner (Sdk/Functions/FromJson.cs:
26// JToken.ReadFrom on a JsonTextReader, then ToPipelineContextData), so it
27// accepts more than RFC 8259:
28//
29// - only the first value is read, anything after it is ignored;
30// - strings may use single quotes and may contain raw control characters,
31// object names may be unquoted (letters, digits, _ and $);
32// - a trailing comma is accepted, an empty array element is an empty string;
33// - NaN, Infinity and -Infinity are numbers, numbers may be written .5, 5.,
34// 1.e2, 01 or 0x1F (hexadecimal, no sign), and undefined is an empty
35// string;
36// - nesting is limited to 64 levels (JsonReader.MaxDepth).
37//
38// Not ported (they fail here): comments and constructors (new Date(1)).
39// Numbers are float64 (1e999 is +Inf). Objects become [*Dictionary] values in
40// document order; a repeated key, compared case-insensitively, keeps the
41// spelling and position of its first occurrence and the value of its last.
42// An unpaired surrogate escape reads as U+FFFD.
43func FromJSON(data []byte) (Value, error) {
44 s := string(data)
45 if !utf8.ValidString(s) {
46 s = string([]rune(s)) // invalid bytes become U+FFFD
47 }
48 p := &jsonParser{s: s}
49 p.skipSpace()
50 if p.i >= len(p.s) {
51 return nil, p.fail("Error reading JToken from JsonReader.")
52 }
53 return p.value(0)
54}
55
56// jsonReaderMaxDepth is Json.NET's JsonReader.MaxDepth default.
57const jsonReaderMaxDepth = 64
58
59type jsonParser struct {
60 s string
61 i int
62 // started is false until the first token is read (Json.NET's Start state):
63 // an error at the first column of the text then reports line 0.
64 started bool
65 // stack is the open containers, for the path of an error.
66 stack []jsonFrame
67}
68
69// jsonFrame is an open array or object, as far as the path of an error needs.
70type jsonFrame struct {
71 obj bool
72 n int // array: values read so far
73 name string // object: the current property name
74 has bool
75}
76
77// JSONError is a failure of FromJSON. Its text is the message of the
78// Newtonsoft.Json.JsonReaderException the runner raises for the same input,
79// "<reason> Path '<path>', line <n>, position <n>.", which GitHub prints. The
80// reasons, paths and positions are reproduced for the failures seen in
81// practice (an unexpected character, a truncated text, a bad literal or number,
82// an unterminated string...); for the rarer ones the reason or the position may
83// differ from Json.NET's, but the text keeps the same form. See PORTING.md.
84type JSONError struct {
85 // Reason is the message without the position, e.g. "Unexpected character
86 // encountered while parsing value: n."
87 Reason string
88 // Path is the JSON path of the last token read ("a.b[0]"), "" at the root.
89 Path string
90 // Line and Position are Json.NET's JsonTextReader.LineNumber and
91 // LinePosition: 1-based lines (0 before the first token), 0-based
92 // positions, counted in UTF-16 units.
93 Line, Position int
94}
95
96func (e *JSONError) Error() string {
97 return fmt.Sprintf("%s Path '%s', line %d, position %d.", e.Reason, e.Path, e.Line, e.Position)
98}
99
100// ExceptionClass is the .NET class of the exception, which GitHub prints in
101// front of the message when it does not know where the expression is.
102func (e *JSONError) ExceptionClass() string { return "Newtonsoft.Json.JsonReaderException" }
103
104// fail builds the error for the current position.
105func (p *jsonParser) fail(reason string) error {
106 line, pos := 1, 0
107 units := 0
108 for i := 0; i < p.i && i < len(p.s); {
109 r, w := utf8.DecodeRuneInString(p.s[i:])
110 i += w
111 switch {
112 case r == '\n', r == '\r' && (i >= len(p.s) || p.s[i] != '\n'):
113 line++
114 units = 0
115 case r == '\r':
116 // the line break is counted with the following \n
117 units++
118 default:
119 units++
120 if r >= 0x10000 {
121 units++
122 }
123 }
124 }
125 pos = units
126 if !p.started && pos == 0 {
127 line = 0
128 }
129 return &JSONError{Reason: reason, Path: p.path(), Line: line, Position: pos}
130}
131
132// path is JsonReader.Path: the property names and indexes of the open
133// containers, the container being read only once it has a current element.
134func (p *jsonParser) path() string {
135 var sb strings.Builder
136 for _, f := range p.stack {
137 switch {
138 case f.obj && f.has:
139 if strings.ContainsAny(f.name, ". '/\"[]()\t\n\r\f\b\\\u0085\u2028\u2029") {
140 sb.WriteString("['" + strings.NewReplacer("\\", "\\\\", "'", "\\'").Replace(f.name) + "']")
141 } else {
142 if sb.Len() > 0 {
143 sb.WriteByte('.')
144 }
145 sb.WriteString(f.name)
146 }
147 case !f.obj && f.n > 0:
148 fmt.Fprintf(&sb, "[%d]", f.n-1)
149 }
150 }
151 return sb.String()
152}
153
154func (p *jsonParser) top() *jsonFrame {
155 if len(p.stack) == 0 {
156 return nil
157 }
158 return &p.stack[len(p.stack)-1]
159}
160
161// valueRead counts a finished scalar in the open array.
162func (p *jsonParser) valueRead() {
163 p.started = true
164 if f := p.top(); f != nil && !f.obj {
165 f.n++
166 }
167}
168
169// unexpected is the error for a character that cannot start a value (or, at
170// the end of the text, for a text that stops too early).
171func (p *jsonParser) unexpected() error {
172 if p.i >= len(p.s) {
173 return p.fail("Unexpected end when reading JSON.")
174 }
175 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
176 return p.fail("Unexpected character encountered while parsing value: " + string(r) + ".")
177}
178
179// unexpectedAfter is the error for a character where a separator or the end of
180// the container should be.
181func (p *jsonParser) unexpectedAfter() error {
182 if p.i >= len(p.s) {
183 return p.unterminated()
184 }
185 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
186 return p.fail("After parsing a value an unexpected character was encountered: " + string(r) + ".")
187}
188
189// unterminated is the error for a text that ends inside an array or object.
190func (p *jsonParser) unterminated() error {
191 f := p.top()
192 if f == nil {
193 return p.fail("Unexpected end when reading JSON.")
194 }
195 kind := "JArray"
196 if f.obj {
197 kind = "JObject"
198 }
199 if (f.obj && !f.has) || (!f.obj && f.n == 0) {
200 return p.fail("Error reading " + kind + " from JsonReader.")
201 }
202 return p.fail("Unexpected end of content while loading " + kind + ".")
203}
204
205// badLiteral is the error for a word that starts like true, false, null, NaN,
206// Infinity or undefined but is not one: Json.NET compares the characters one
207// by one and fails at the first that differs.
208func (p *jsonParser) badLiteral(word, kind string) error {
209 if len(p.s)-p.i < len(word) {
210 p.i = len(p.s)
211 return p.fail("Unexpected end when reading JSON.")
212 }
213 k := 0
214 for k < len(word) && p.s[p.i+k] == word[k] {
215 k++
216 }
217 p.i += k
218 return p.fail("Error parsing " + kind + " value.")
219}
220
221func (p *jsonParser) skipSpace() {
222 for p.i < len(p.s) {
223 r, w := utf8.DecodeRuneInString(p.s[p.i:])
224 if !isNetSpace(r) {
225 return
226 }
227 p.i += w
228 }
229}
230
231// isJSONSeparator reports whether c ends a literal or a number.
232func isJSONSeparator(r rune) bool {
233 switch r {
234 case ',', '}', ']', ')', '/':
235 return true
236 }
237 return isNetSpace(r)
238}
239
240// token returns the run of characters up to the next separator.
241func (p *jsonParser) token() string {
242 start := p.i
243 for p.i < len(p.s) {
244 r, w := utf8.DecodeRuneInString(p.s[p.i:])
245 if isJSONSeparator(r) {
246 break
247 }
248 p.i += w
249 }
250 return p.s[start:p.i]
251}
252
253func (p *jsonParser) value(depth int) (Value, error) {
254 if p.i >= len(p.s) {
255 return nil, p.unexpected()
256 }
257 switch c := p.s[p.i]; {
258 case c == '{':
259 return p.object(depth + 1)
260 case c == '[':
261 return p.array(depth + 1)
262 case c == '"' || c == '\'':
263 s, err := p.str()
264 if err != nil {
265 return nil, err
266 }
267 p.valueRead()
268 return String(s), nil
269 case c == '-' || c == '.' || c >= '0' && c <= '9':
270 v, err := p.number()
271 if err == nil {
272 p.valueRead()
273 }
274 return v, err
275 case c == '/':
276 p.i++
277 if p.i >= len(p.s) {
278 return nil, p.fail("Unexpected end while parsing comment.")
279 }
280 if p.s[p.i] != '*' {
281 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
282 return nil, p.fail("Error parsing comment. Expected: *, got " + string(r) + ".")
283 }
284 p.i--
285 return nil, p.fail("Comments are not supported by this port.")
286 case c == ']' && len(p.stack) == 0:
287 p.i++
288 return nil, p.fail("JsonToken EndArray is not valid for closing JsonType None.")
289 }
290 if c := p.s[p.i]; c == ',' && depth == 0 {
291 // A comma where the document should start is an undefined value,
292 // which Json.NET reads as an empty string; whatever follows is ignored
293 // like any text after the first value.
294 return String(""), nil
295 }
296 start := p.i
297 var v Value
298 kind := ""
299 switch word := p.token(); word {
300 case "true":
301 v, kind = Boolean(true), "boolean"
302 case "false":
303 v, kind = Boolean(false), "boolean"
304 case "null":
305 v, kind = Null{}, "null"
306 case "undefined":
307 v, kind = String(""), "undefined"
308 case "NaN":
309 v, kind = Number(nan), "NaN"
310 case "Infinity":
311 v, kind = Number(posInf), "Infinity"
312 default:
313 p.i = start
314 return nil, p.literalError()
315 }
316 if err := p.afterLiteral(kind); err != nil {
317 return nil, err
318 }
319 p.valueRead()
320 return v, nil
321}
322
323// literalError explains a word that is not a literal, by its first letter.
324func (p *jsonParser) literalError() error {
325 next := byte(0)
326 if p.i+1 < len(p.s) {
327 next = p.s[p.i+1]
328 }
329 switch p.s[p.i] {
330 case 't':
331 return p.badLiteral("true", "boolean")
332 case 'f':
333 return p.badLiteral("false", "boolean")
334 case 'n':
335 if next == 'u' {
336 return p.badLiteral("null", "null")
337 }
338 case 'N':
339 return p.badLiteral("NaN", "NaN")
340 case 'I':
341 return p.badLiteral("Infinity", "Infinity")
342 case 'u':
343 return p.badLiteral("undefined", "undefined")
344 }
345 return p.unexpected()
346}
347
348// afterLiteral checks the character that follows a word literal (true, null,
349// NaN...): Json.NET only accepts a "/" there when it starts a comment, and
350// comments are not ported, so any "/" is an error here. Anything else is left
351// for the caller (white space, a comma, a closing bracket, or trailing text).
352func (p *jsonParser) afterLiteral(kind string) error {
353 if p.i >= len(p.s) || p.s[p.i] != '/' {
354 return nil
355 }
356 if p.i+1 < len(p.s) && (p.s[p.i+1] == '/' || p.s[p.i+1] == '*') {
357 return p.fail("Comments are not supported by this port.")
358 }
359 return p.fail("Error parsing " + kind + " value.")
360}
361
362// number reads a number token: decimal with optional sign, fraction and
363// exponent (a digit is required in the mantissa), -Infinity, or an unsigned
364// 0x hexadecimal integer.
365func (p *jsonParser) number() (Value, error) {
366 start := p.i
367 if strings.HasPrefix(p.s[p.i:], "-I") {
368 if !strings.HasPrefix(p.s[p.i:], "-Infinity") {
369 return nil, p.badLiteral("-Infinity", "-Infinity")
370 }
371 }
372 tok, err := p.numberToken()
373 if err != nil {
374 return nil, err
375 }
376 if tok == "-Infinity" {
377 if err := p.afterLiteral("-Infinity"); err != nil {
378 return nil, err
379 }
380 return Number(math.Inf(-1)), nil
381 }
382 if len(tok) > 2 && tok[0] == '0' && (tok[1] == 'x' || tok[1] == 'X') {
383 if len(tok) <= 18 {
384 if n, err := strconv.ParseUint(tok[2:], 16, 64); err == nil && !strings.ContainsAny(tok[2:], "+-_") {
385 return Number(float64(int64(n))), nil
386 }
387 }
388 return nil, p.badNumber(start, tok)
389 }
390 // A non-negative number with a leading zero is octal when it has only
391 // digits (010 is 8, 08 is an error) and an error unless the zero is
392 // followed by ".", "e" or "E" (01.5, 012e1 and 00.5 fail). A negative
393 // number is read as decimal whatever its zeros (-010 is -10).
394 if len(tok) > 1 && tok[0] == '0' && tok[1] != '.' && tok[1] != 'e' && tok[1] != 'E' {
395 v, ok := parseOctal64(tok[1:])
396 if !ok {
397 return nil, p.badNumber(start, tok)
398 }
399 return Number(v), nil
400 }
401 body := strings.TrimPrefix(tok, "-")
402 if !isDecimalLiteral(body) {
403 return nil, p.badNumber(start, tok)
404 }
405 if isBigInteger(body) {
406 // Json.NET reads an integer that does not fit in 64 bits as a
407 // BigInteger, and (Double)BigInteger truncates toward zero to 53 bits
408 // instead of rounding to nearest.
409 if _, err := strconv.ParseInt(tok, 10, 64); err != nil {
410 n, _ := new(big.Int).SetString(tok, 10)
411 f, _ := new(big.Float).SetPrec(53).SetMode(big.ToZero).SetInt(n).Float64()
412 return Number(f), nil
413 }
414 }
415 f, _ := strconv.ParseFloat(tok, 64) // range errors give ±Inf
416 if f == 0 && isBigInteger(body) {
417 f = 0 // an integer token is read as a long: "-0" and "-00" are plain 0
418 }
419 return Number(f), nil
420}
421
422// numberToken reads the characters of a number as JsonTextReader does: those
423// of a fixed set (digits, signs, ".", a-f, A-F, x, X) up to a separator; any
424// other character is an error at its own position.
425func (p *jsonParser) numberToken() (string, error) {
426 start := p.i
427 for p.i < len(p.s) {
428 c := p.s[p.i]
429 switch {
430 case c >= '0' && c <= '9', c >= 'a' && c <= 'f', c >= 'A' && c <= 'F',
431 c == '+', c == '-', c == '.', c == 'x', c == 'X', c == 'I', c == 'n', c == 'i', c == 't', c == 'y':
432 if c == 'I' || c == 'n' || c == 'i' || c == 't' || c == 'y' {
433 // only the letters of -Infinity are read on; anything else
434 // is not in the set
435 if !strings.HasPrefix(p.s[start:], "-Infinity") {
436 return "", p.numberChar()
437 }
438 }
439 p.i++
440 default:
441 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
442 if isJSONSeparator(r) {
443 return p.s[start:p.i], nil
444 }
445 return "", p.numberChar()
446 }
447 }
448 return p.s[start:p.i], nil
449}
450
451func (p *jsonParser) numberChar() error {
452 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
453 return p.fail("Unexpected character encountered while parsing number: " + string(r) + ".")
454}
455
456// badNumber is the error for a malformed number token; Json.NET reports it at
457// the end of the token, with the element already counted in the path.
458func (p *jsonParser) badNumber(start int, tok string) error {
459 p.i = start + len(tok)
460 p.valueRead()
461 return p.fail("Input string '" + tok + "' is not a valid number.")
462}
463
464// parseOctal64 reads octal digits as Convert.ToInt64(s, 8) does: leading
465// zeros are free, at most 64 significant bits, and a value of 2^63 or more
466// wraps to a negative number (1777777777777777777777 is -1).
467func parseOctal64(digits string) (float64, bool) {
468 if digits == "" {
469 return 0, false
470 }
471 var v uint64
472 for i := 0; i < len(digits); i++ {
473 c := digits[i]
474 if c < '0' || c > '7' {
475 return 0, false
476 }
477 if v>>61 != 0 {
478 return 0, false // the next shift would leave 64 bits
479 }
480 v = v<<3 | uint64(c-'0')
481 }
482 return float64(int64(v)), true
483}
484
485// isBigInteger reports whether s is only digits.
486func isBigInteger(s string) bool {
487 for i := 0; i < len(s); i++ {
488 if s[i] < '0' || s[i] > '9' {
489 return false
490 }
491 }
492 return s != ""
493}
494
495// str reads a string literal; p.i is on the opening quote.
496func (p *jsonParser) str() (string, error) {
497 quote := p.s[p.i]
498 p.i++
499 var b strings.Builder
500 for {
501 if p.i >= len(p.s) {
502 return "", p.fail("Unterminated string. Expected delimiter: " + string(quote) + ".")
503 }
504 c := p.s[p.i]
505 if c == quote {
506 p.i++
507 return b.String(), nil
508 }
509 if c != '\\' {
510 b.WriteByte(c)
511 p.i++
512 continue
513 }
514 p.i++
515 if p.i >= len(p.s) {
516 return "", p.fail("Unterminated string. Expected delimiter: " + string(quote) + ".")
517 }
518 e := p.s[p.i]
519 p.i++
520 switch e {
521 case '"', '\'', '\\', '/':
522 b.WriteByte(e)
523 case 'b':
524 b.WriteByte('\b')
525 case 'f':
526 b.WriteByte('\f')
527 case 'n':
528 b.WriteByte('\n')
529 case 'r':
530 b.WriteByte('\r')
531 case 't':
532 b.WriteByte('\t')
533 case 'u':
534 r, err := p.hex4()
535 if err != nil {
536 return "", err
537 }
538 if r >= 0xD800 && r < 0xDC00 && strings.HasPrefix(p.s[p.i:], `\u`) {
539 save := p.i
540 p.i += 2
541 lo, err := p.hex4()
542 if err != nil {
543 return "", err
544 }
545 if lo >= 0xDC00 && lo < 0xE000 {
546 r = 0x10000 + (r-0xD800)<<10 + (lo - 0xDC00)
547 } else {
548 p.i = save // not a pair; the second escape is read on its own
549 }
550 }
551 if r >= 0xD800 && r < 0xE000 {
552 r = utf8.RuneError // an unpaired surrogate
553 }
554 b.WriteRune(r)
555 default:
556 return "", p.fail("Bad JSON escape sequence: \\" + string(e) + ".")
557 }
558 }
559}
560
561func (p *jsonParser) hex4() (rune, error) {
562 // JsonTextReader needs a character after the four digits (EnsureChars).
563 if p.i+4 >= len(p.s) {
564 return 0, p.fail("Unexpected end while parsing Unicode escape sequence.")
565 }
566 first := p.i
567 var r rune
568 for k := 0; k < 4; k++ {
569 c := p.s[p.i]
570 var d byte
571 switch {
572 case c >= '0' && c <= '9':
573 d = c - '0'
574 case c >= 'a' && c <= 'f':
575 d = c - 'a' + 10
576 case c >= 'A' && c <= 'F':
577 d = c - 'A' + 10
578 default:
579 p.i = first
580 return 0, p.fail("Invalid Unicode escape sequence: \\u" + p.s[first:first+4] + ".")
581 }
582 r = r<<4 | rune(d)
583 p.i++
584 }
585 return r, nil
586}
587
588func (p *jsonParser) array(depth int) (Value, error) {
589 if depth > jsonReaderMaxDepth {
590 return nil, p.fail(fmt.Sprintf("The reader's MaxDepth of %d has been exceeded.", jsonReaderMaxDepth))
591 }
592 p.i++
593 p.valueRead()
594 p.stack = append(p.stack, jsonFrame{})
595 arr := &Array{}
596 for {
597 p.skipSpace()
598 if p.i >= len(p.s) {
599 return nil, p.unterminated()
600 }
601 switch p.s[p.i] {
602 case ']':
603 p.i++
604 p.pop()
605 return arr, nil
606 case ',':
607 // An empty element is "undefined", which reads as an empty string.
608 p.i++
609 p.valueRead()
610 arr.items = append(arr.items, String(""))
611 continue
612 }
613 v, err := p.value(depth)
614 if err != nil {
615 return nil, err
616 }
617 arr.items = append(arr.items, v)
618 p.skipSpace()
619 if p.i >= len(p.s) {
620 return nil, p.unterminated()
621 }
622 switch p.s[p.i] {
623 case ',':
624 p.i++
625 case ']':
626 default:
627 return nil, p.unexpectedAfter()
628 }
629 }
630}
631
632// pop closes the innermost container; it counts as a value of its parent.
633func (p *jsonParser) pop() {
634 p.stack = p.stack[:len(p.stack)-1]
635}
636
637// propertyName reads a quoted or unquoted object name.
638func (p *jsonParser) propertyName() (string, error) {
639 if p.s[p.i] == '"' || p.s[p.i] == '\'' {
640 return p.str()
641 }
642 start := p.i
643 if r, _ := utf8.DecodeRuneInString(p.s[p.i:]); !unicode.IsLetter(r) && !unicode.IsDigit(r) && r != '_' && r != '$' {
644 return "", p.fail("Invalid property identifier character: " + string(r) + ".")
645 }
646 for p.i < len(p.s) {
647 r, w := utf8.DecodeRuneInString(p.s[p.i:])
648 if r == ':' || isNetSpace(r) {
649 break
650 }
651 if !unicode.IsLetter(r) && !unicode.IsDigit(r) && r != '_' && r != '$' {
652 return "", p.fail("Invalid JavaScript property identifier character: " + string(r) + ".")
653 }
654 p.i += w
655 }
656 if p.i >= len(p.s) {
657 return "", p.fail("Unexpected end while parsing unquoted property name.")
658 }
659 if p.i == start {
660 return "", p.unexpected()
661 }
662 return p.s[start:p.i], nil
663}
664
665func (p *jsonParser) object(depth int) (Value, error) {
666 if depth > jsonReaderMaxDepth {
667 return nil, p.fail(fmt.Sprintf("The reader's MaxDepth of %d has been exceeded.", jsonReaderMaxDepth))
668 }
669 p.i++
670 p.valueRead()
671 p.stack = append(p.stack, jsonFrame{obj: true})
672 d := NewDictionary()
673 for {
674 p.skipSpace()
675 if p.i >= len(p.s) {
676 return nil, p.unterminated()
677 }
678 if p.s[p.i] == '}' {
679 p.i++
680 p.pop()
681 return d, nil
682 }
683 k, err := p.propertyName()
684 if err != nil {
685 return nil, err
686 }
687 p.skipSpace()
688 if p.i >= len(p.s) {
689 return nil, p.unterminated()
690 }
691 if p.s[p.i] != ':' {
692 r, _ := utf8.DecodeRuneInString(p.s[p.i:])
693 return nil, p.fail("Invalid character after parsing property name. Expected ':' but got: " + string(r) + ".")
694 }
695 p.i++
696 f := p.top()
697 f.name, f.has = k, true
698 p.skipSpace()
699 if p.i >= len(p.s) {
700 return nil, p.unterminated()
701 }
702 v, err := p.value(depth)
703 if err != nil {
704 return nil, err
705 }
706 d.set(k, v)
707 p.skipSpace()
708 if p.i >= len(p.s) {
709 return nil, p.unterminated()
710 }
711 switch p.s[p.i] {
712 case ',':
713 p.i++
714 case '}':
715 default:
716 return nil, p.unexpectedAfter()
717 }
718 }
719}
720
721// ToJSON renders v as the toJSON function does (Sdk/Functions/ToJson.cs): two
722// space indentation, "key": value pairs in the dictionary's order, "[]" and
723// "{}" for empty containers. A number is written as its string form
724// (numberToCoercedString: at most 15 significant digits, so NaN and the
725// infinities are written as such). Strings are escaped as Json.NET does by
726// default: quotes, backslashes, \b \f \n \r \t, the other control characters
727// as \u00xx, and U+0085, U+2028 and U+2029 as \uxxxx; everything else,
728// including non-ASCII text, is written as is.
729//
730// ToJSON suits the finite values that FromJSON and Evaluate produce. A value
731// nested deeper than [MaxJSONDepth], which only a cyclic value built by hand
732// can be, makes it return "null"; use [EncodeJSON] to get an error instead
733// and to bound the output.
734func ToJSON(v Value) string {
735 s, err := EncodeJSON(v, -1)
736 if err != nil {
737 return "null"
738 }
739 return s
740}
741
742// EncodeJSON is [ToJSON] with limits: it fails when v is nested deeper than
743// [MaxJSONDepth] and, when maxBytes is not negative, as soon as the output
744// would exceed maxBytes bytes, without building the rest.
745func EncodeJSON(v Value, maxBytes int) (string, error) {
746 w := &jsonWriter{limit: maxBytes}
747 w.value(v, 0)
748 if w.err != nil {
749 return "", w.err
750 }
751 return w.b.String(), nil
752}
753
754var (
755 errJSONTooDeep = errors.New("value nested too deeply to encode as JSON (a cycle?)")
756 errJSONTooBig = errors.New("JSON output exceeds the size limit")
757)
758
759type jsonWriter struct {
760 b strings.Builder
761 limit int // negative: unlimited
762 err error
763}
764
765// grow reports whether n more bytes may be written, recording the error
766// otherwise.
767func (w *jsonWriter) grow(n int) bool {
768 if w.err != nil {
769 return false
770 }
771 if w.limit >= 0 && n > w.limit-w.b.Len() {
772 w.err = errJSONTooBig
773 return false
774 }
775 return true
776}
777
778func (w *jsonWriter) str(s string) {
779 if w.grow(len(s)) {
780 w.b.WriteString(s)
781 }
782}
783
784func (w *jsonWriter) indent(depth int) {
785 if w.grow(2 * depth) {
786 for i := 0; i < depth; i++ {
787 w.b.WriteString(" ")
788 }
789 }
790}
791
792func (w *jsonWriter) value(v Value, depth int) {
793 if w.err != nil {
794 return
795 }
796 if depth > MaxJSONDepth {
797 w.err = errJSONTooDeep
798 return
799 }
800 switch x := normalize(v).(type) {
801 case Null:
802 w.str("null")
803 case Boolean:
804 if x {
805 w.str("true")
806 } else {
807 w.str("false")
808 }
809 case Number:
810 // The runner writes the number as it converts it to a string
811 // (ToJson.WriteValue: value.ConvertToString()), so NaN and the
812 // infinities are written as such, and a number has at most 15
813 // significant digits. JSON.stringify gives null and the shortest
814 // round-trip form.
815 w.str(numberToCoercedString(float64(x)))
816 case String:
817 w.jsonString(string(x))
818 case *Array:
819 if len(x.items) == 0 {
820 w.str("[]")
821 return
822 }
823 w.str("[\n")
824 for i, it := range x.items {
825 w.indent(depth + 1)
826 w.value(it, depth+1)
827 if i < len(x.items)-1 {
828 w.str(",")
829 }
830 w.str("\n")
831 if w.err != nil {
832 return
833 }
834 }
835 w.indent(depth)
836 w.str("]")
837 case *Dictionary:
838 if len(x.keys) == 0 {
839 w.str("{}")
840 return
841 }
842 keys := x.keys
843 w.str("{\n")
844 for i, k := range keys {
845 val, _ := x.Get(k)
846 w.indent(depth + 1)
847 w.jsonString(k)
848 w.str(": ")
849 w.value(val, depth+1)
850 if i < len(keys)-1 {
851 w.str(",")
852 }
853 w.str("\n")
854 if w.err != nil {
855 return
856 }
857 }
858 w.indent(depth)
859 w.str("}")
860 }
861}
862
863const hexDigits = "0123456789abcdef"
864
865func (w *jsonWriter) jsonString(s string) {
866 if !w.grow(len(s) + 2) {
867 return
868 }
869 w.b.WriteByte('"')
870 for i := 0; i < len(s); {
871 r, n := decodeRune(s[i:])
872 i += n
873 var esc string
874 switch {
875 case r == '"':
876 esc = `\"`
877 case r == '\\':
878 esc = `\\`
879 case r == '\b':
880 esc = `\b`
881 case r == '\f':
882 esc = `\f`
883 case r == '\n':
884 esc = `\n`
885 case r == '\r':
886 esc = `\r`
887 case r == '\t':
888 esc = `\t`
889 case r < 0x20:
890 esc = `\u00` + string([]byte{hexDigits[r>>4], hexDigits[r&0xF]})
891 case r == 0x85 || r == 0x2028 || r == 0x2029 || r >= 0xD800 && r < 0xE000:
892 esc = `\u` + string([]byte{hexDigits[r>>12], hexDigits[r>>8&0xF], hexDigits[r>>4&0xF], hexDigits[r&0xF]})
893 }
894 if esc != "" {
895 if !w.grow(len(esc)) {
896 return
897 }
898 w.b.WriteString(esc)
899 continue
900 }
901 if !w.grow(utf8.RuneLen(r)) {
902 return
903 }
904 w.b.WriteRune(r) // other invalid UTF-8 comes out as U+FFFD
905 }
906 if w.grow(1) {
907 w.b.WriteByte('"')
908 }
909}