tobogganSe connecter

packages

The Louise packages, each released on its own

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

823 lignes · 19738 octetsBrut · Historique
1/// JSON (RFC 8259): a value, a parser of untrusted text, a writer, and
2/// `@derive(ToJson)`. Decoding into your own types is `json/decode`.
3///
4/// json.parse "[1, \"two\", null]" // Ok(Array([Int(1), String("two"), Null]))
5/// json.write (Object([("a", Int(1))])) // "\{\"a\":1}"
6/// json.encode [1, 2, 3] // "[1,2,3]", through ToJson
7///
8/// `parse` reads untrusted input (request bodies): nesting is bounded
9/// (see [`max_depth`]), a key appears at most once in an object, every
10/// escape is checked (a lone surrogate is an error), and a number too
11/// large for a `Float` is an error rather than an infinity. A number
12/// with no fraction and no exponent is an `Int`, of any size; any other
13/// is a `Float`.
14///
15/// An object keeps its keys in the order they were read or built, so
16/// `write` is deterministic: `parse (write v) == Ok(v)`.
17
18import std/bytes
19import std/dict
20import std/float
21import std/int
22import std/list
23import std/result
24import std/string
25
26/// A JSON value. `Object` keeps its entries in order.
27@derive Eq Debug
28pub type Value
29{ Null
30, Bool(Bool)
31, Int(Int)
32, Float(Float)
33, String(String)
34, Array(List<Value>)
35, Object(List<(String, Value)>)
36}
37
38/// Why [`parse`] or a decoder (`json/decode`) failed.
39@derive Eq Debug
40pub type DecodeError
41{ /// The text is not JSON; `at` is the byte offset.
42 Malformed(at: Int, message: String)
43 /// The JSON parsed, but the value at `path` is not the one expected.
44 /// A path is object keys and array indexes, outermost first.
45, Mismatch(path: List<String>, expected: String, found: String)
46 /// The object at `path` has no field `name`.
47, Missing(path: List<String>, name: String)
48}
49
50impl Show<DecodeError>
51{
52 fn show :: e
53 {
54 match e
55 { Malformed(at, message) -> "invalid JSON at byte {at}: {message}"
56 , Mismatch
57 ( path
58 , expected
59 , found
60 ) -> "{located path}: expected {expected}, found {found}"
61 , Missing(path, name) -> "{located path}: missing field \"{name}\""
62 }
63 }
64}
65
66impl Show<Value>
67{
68 fn show :: v
69 {
70 write v
71 }
72}
73
74/// `path` as `$.ships.0.symbol`, the root as `$`.
75pub fn located :: path: List<String> -> String
76{
77 string.concat ["$", ..list.map path fn p { ".{p}" }]
78}
79
80/// The most nesting [`parse`] accepts (arrays and objects; 512). Deeper
81/// input is an error, so a hostile body cannot overflow the stack.
82pub fn max_depth :: -> Int
83{
84 512
85}
86
87/// What a `Value` is, for error messages ("a string", "an object").
88pub fn kind :: v: Value -> String
89{
90 match v
91 { Null -> "null"
92 , Bool(_) -> "a bool"
93 , Int(_) -> "an integer"
94 , Float(_) -> "a number"
95 , String(_) -> "a string"
96 , Array(_) -> "an array"
97 , Object(_) -> "an object"
98 }
99}
100
101/// The value of `name` in an object; `None` for a missing key or a value
102/// that is not an object.
103pub fn get :: v: Value name: String -> Option<Value>
104{
105 match v
106 { Object(entries) ->
107 list.find entries fn entry { entry.0 == name }
108 |> option_map fn entry { entry.1 }
109 , _ -> None
110 }
111}
112
113fn option_map :: o: Option<a> f: fn(a) -> b -> Option<b>
114{
115 match o { Some(x) -> Some(f x), None -> None }
116}
117
118// ---- writing -------------------------------------------------------------------
119
120/// `value` as compact JSON text. Panics on a `Float` that is infinite or
121/// NaN: JSON has no such number.
122pub fn write :: value: Value -> String
123{
124 bytes.build_string (write_value (bytes.builder ()) value)
125}
126
127/// `value` as JSON text indented by two spaces per level, for people to
128/// read (docs, examples, logs). Same panics as [`write`].
129pub fn pretty :: value: Value -> String
130{
131 bytes.build_string (pretty_value (bytes.builder ()) value 0)
132}
133
134fn write_value :: b: bytes.Builder value: Value -> bytes.Builder
135{
136 match value
137 { Null -> bytes.append_string b "null"
138 , Bool(True) -> bytes.append_string b "true"
139 , Bool(False) -> bytes.append_string b "false"
140 , Int(n) -> bytes.append_string b "{n}"
141 , Float(x) -> bytes.append_string b (number x)
142 , String(s) -> write_string b s
143 , Array(items) ->
144 {
145 let b = bytes.append_byte b 91
146 let b = separated b items write_value
147 bytes.append_byte b 93
148 }
149 , Object(entries) ->
150 {
151 let b = bytes.append_byte b 123
152 let b = separated b entries write_entry
153 bytes.append_byte b 125
154 }
155 }
156}
157
158fn write_entry :: b: bytes.Builder entry: (String, Value) -> bytes.Builder
159{
160 let b = write_string b entry.0
161 write_value (bytes.append_byte b 58) entry.1
162}
163
164/// Each item written by `each`, with a comma between two.
165fn separated ::
166 b: bytes.Builder
167 items: List<a>
168 each: fn(bytes.Builder, a) -> bytes.Builder
169 -> bytes.Builder
170{
171 match items
172 { [] -> b
173 , [first, ..rest] ->
174 list.fold
175 rest
176 (each b first)
177 fn b item { each (bytes.append_byte b 44) item }
178 }
179}
180
181fn pretty_value :: b: bytes.Builder value: Value depth: Int -> bytes.Builder
182{
183 match value
184 { Array([]) -> bytes.append_string b "[]"
185 , Object([]) -> bytes.append_string b "\{\}"
186 , Array(items) ->
187 {
188 let b = bytes.append_byte b 91
189 let b =
190 indented b items depth fn b item { pretty_value b item (depth + 1) }
191 bytes.append_byte b 93
192 }
193 , Object(entries) ->
194 {
195 let b = bytes.append_byte b 123
196 let b =
197 indented
198 b
199 entries
200 depth
201 fn b entry
202 {
203 let b = bytes.append_string (write_string b entry.0) ": "
204 pretty_value b entry.1 (depth + 1)
205 }
206 bytes.append_byte b 125
207 }
208 , _ -> write_value b value
209 }
210}
211
212/// Each item on a line of its own, one level deeper than `depth`, and
213/// the closing bracket's line back at `depth`.
214fn indented ::
215 b: bytes.Builder
216 items: List<a>
217 depth: Int
218 each: fn(bytes.Builder, a) -> bytes.Builder
219 -> bytes.Builder
220{
221 let inner = "\n" <> string.repeat " " (depth + 1)
222 let b =
223 separated b items fn b item { each (bytes.append_string b inner) item }
224 bytes.append_string b ("\n" <> string.repeat " " depth)
225}
226
227/// A finite `Float` as a JSON number: `show` already writes `1.0`,
228/// `1e300` and `1.5e-7`, which are all JSON.
229fn number :: x: Float -> String
230{
231 if x != x || x - x != 0.0
232 {
233 panic "json.write: {x} is not a JSON number"
234 }
235 else
236 {
237 "{x}"
238 }
239}
240
241/// `s` quoted, with `"`, `\` and the control characters escaped. Runs of
242/// bytes that need no escape are copied whole.
243fn write_string :: b: bytes.Builder s: String -> bytes.Builder
244{
245 let data = bytes.from_string s
246 let b = escape_from (bytes.append_byte b 34) data 0 0
247 bytes.append_byte b 34
248}
249
250fn escape_from ::
251 b: bytes.Builder
252 data: Bytes
253 start: Int
254 at: Int
255 -> bytes.Builder
256{
257 if at == bytes.length data
258 {
259 bytes.append b (bytes.slice data start at)
260 }
261 else
262 {
263 let byte = bytes.read_u8 data at
264 match escape_of byte
265 { "" -> escape_from b data start (at + 1)
266 , escape ->
267 {
268 let b = bytes.append b (bytes.slice data start at)
269 escape_from (bytes.append_string b escape) data (at + 1) (at + 1)
270 }
271 }
272 }
273}
274
275/// The escape `byte` is written as, or `""` when it is written as is.
276fn escape_of :: byte: Int -> String
277{
278 match byte
279 { 34 -> "\\\""
280 , 92 -> "\\\\"
281 , 8 -> "\\b"
282 , 12 -> "\\f"
283 , 10 -> "\\n"
284 , 13 -> "\\r"
285 , 9 -> "\\t"
286 , _ -> if byte < 32 { "\\u00" <> hex_byte byte } else { "" }
287 }
288}
289
290fn hex_byte :: byte: Int -> String
291{
292 let digits = "0123456789abcdef"
293 let high = int.shift_right byte 4
294 let low = int.and byte 15
295 string.slice digits high (high + 1) <> string.slice digits low (low + 1)
296}
297
298// ---- parsing -------------------------------------------------------------------
299
300/// The JSON value `text` holds. Whitespace may surround it; anything
301/// else after it is an error.
302pub fn parse :: text: String -> Result<Value, DecodeError>
303{
304 let data = bytes.from_string text
305 use (value, at) <- result.try (value_at data (spaced data 0) 0)
306 let end = spaced data at
307 if end == bytes.length data
308 {
309 Ok(value)
310 }
311 else
312 {
313 Error(Malformed(end, "text after the value"))
314 }
315}
316
317/// [`parse`] of a request body: `data` must be UTF-8.
318pub fn parse_bytes :: data: Bytes -> Result<Value, DecodeError>
319{
320 match bytes.to_string data
321 { Ok(text) -> parse text
322 , Error(e) -> Error(Malformed(0, "the text is not UTF-8: {e}"))
323 }
324}
325
326type Parsed<a> = Result<(a, Int), DecodeError>
327
328fn value_at :: data: Bytes at: Int depth: Int -> Parsed<Value>
329{
330 match bytes.get data at
331 { None -> Error(Malformed(at, "expected a value, found the end"))
332 , Some(byte) -> match byte
333 { 123 -> nested data at depth object_at
334 , 91 -> nested data at depth array_at
335 , 34 ->
336 string_at data at |> result.map fn found { (String(found.0), found.1) }
337 , 116 -> literal data at "true" Bool(True)
338 , 102 -> literal data at "false" Bool(False)
339 , 110 -> literal data at "null" Null
340 , _ -> if byte == 45 || (byte >= 48 && byte <= 57)
341 {
342 number_at data at
343 }
344 else
345 {
346 Error(Malformed(at, "expected a value"))
347 }
348 }
349 }
350}
351
352fn nested ::
353 data: Bytes
354 at: Int
355 depth: Int
356 inside: fn(Bytes, Int, Int) -> Parsed<Value>
357 -> Parsed<Value>
358{
359 if depth >= max_depth ()
360 {
361 Error(Malformed(at, "nesting deeper than {max_depth ()} levels"))
362 }
363 else
364 {
365 inside data (spaced data (at + 1)) (depth + 1)
366 }
367}
368
369fn literal :: data: Bytes at: Int word: String value: Value -> Parsed<Value>
370{
371 let end = at + string.byte_length word
372 if end <= bytes.length data
373 && bytes.slice data at end == bytes.from_string word
374 {
375 Ok((value, end))
376 }
377 else
378 {
379 Error(Malformed(at, "expected a value"))
380 }
381}
382
383/// The index of the first byte at or after `at` that is not JSON
384/// whitespace (space, tab, line feed, carriage return).
385fn spaced :: data: Bytes at: Int -> Int
386{
387 match bytes.get data at
388 { Some(32) | Some(9) | Some(10) | Some(13) -> spaced data (at + 1), _ -> at }
389}
390
391// -- arrays and objects
392
393fn array_at :: data: Bytes at: Int depth: Int -> Parsed<Value>
394{
395 match bytes.get data at
396 { Some(93) -> Ok((Array([]), at + 1)), _ -> items_at data at depth [] }
397}
398
399fn items_at :: data: Bytes at: Int depth: Int kept: List<Value> -> Parsed<Value>
400{
401 use (item, after) <- result.try (value_at data at depth)
402 let next = spaced data after
403 match bytes.get data next
404 { Some(44) -> items_at data (spaced data (next + 1)) depth [item, ..kept]
405 , Some(93) -> Ok((Array(list.reverse [item, ..kept]), next + 1))
406 , _ -> Error(Malformed(next, "expected , or ] in an array"))
407 }
408}
409
410fn object_at :: data: Bytes at: Int depth: Int -> Parsed<Value>
411{
412 match bytes.get data at
413 { Some(125) -> Ok((Object([]), at + 1))
414 , _ -> entries_at data at depth [] (dict.empty ())
415 }
416}
417
418fn entries_at ::
419 data: Bytes
420 at: Int
421 depth: Int
422 kept: List<(String, Value)>
423 seen: dict.Dict<String, ()>
424 -> Parsed<Value>
425{
426 use (name, after_name) <- result.try (key_at data at)
427 if dict.has seen name
428 {
429 Error(Malformed(at, "the key \"{name}\" appears twice"))
430 }
431 else
432 {
433 let colon = spaced data after_name
434 match bytes.get data colon
435 { Some(58) ->
436 {
437 use (value, after) <-
438 result.try (value_at data (spaced data (colon + 1)) depth)
439 let kept = [(name, value), ..kept]
440 let next = spaced data after
441 match bytes.get data next
442 { Some(44) ->
443 entries_at
444 data
445 (spaced data (next + 1))
446 depth
447 kept
448 (dict.insert seen name ())
449 , Some(125) -> Ok((Object(list.reverse kept), next + 1))
450 , _ -> Error(Malformed(next, "expected , or \} in an object"))
451 }
452 }
453 , _ -> Error(Malformed(colon, "expected : after a key"))
454 }
455 }
456}
457
458fn key_at :: data: Bytes at: Int -> Parsed<String>
459{
460 match bytes.get data at
461 { Some(34) -> string_at data at
462 , _ -> Error(Malformed(at, "expected a key (a string)"))
463 }
464}
465
466// -- strings
467
468/// The string whose opening quote is at `at`, and the index after its
469/// closing quote. Runs of plain bytes are copied whole; the input is
470/// UTF-8 already, so only escapes need building.
471fn string_at :: data: Bytes at: Int -> Parsed<String>
472{
473 chars_at data (at + 1) (at + 1) (bytes.builder ())
474}
475
476fn chars_at ::
477 data: Bytes
478 start: Int
479 at: Int
480 kept: bytes.Builder
481 -> Parsed<String>
482{
483 match bytes.get data at
484 { None -> Error(Malformed(at, "an unterminated string"))
485 , Some(34) ->
486 Ok( ( bytes.build_string (bytes.append kept (bytes.slice data start at))
487 , at + 1
488 )
489 )
490 , Some(92) -> match escape_at data at
491 { Ok((point, after)) ->
492 chars_at
493 data
494 after
495 after
496 (utf8 (bytes.append kept (bytes.slice data start at)) point)
497 , Error(e) -> Error(e)
498 }
499 , Some(byte) -> if byte < 32
500 {
501 Error(Malformed(at, "a control character in a string"))
502 }
503 else
504 {
505 chars_at data start (at + 1) kept
506 }
507 }
508}
509
510/// The code point the escape whose backslash is at `at` stands for,
511/// and the index after the escape.
512fn escape_at :: data: Bytes at: Int -> Result<(Int, Int), DecodeError>
513{
514 match bytes.get data (at + 1)
515 { Some(117) -> unicode_at data at
516 , Some(byte) -> match unescaped byte
517 { Some(plain) -> Ok((plain, at + 2))
518 , None -> Error(Malformed(at, "an unknown escape"))
519 }
520 , None -> Error(Malformed(at, "an unknown escape"))
521 }
522}
523
524/// The byte a one-letter escape `\x` stands for, where `x` is `byte`.
525fn unescaped :: byte: Int -> Option<Int>
526{
527 match byte
528 { 34 -> Some(34)
529 , 92 -> Some(92)
530 , 47 -> Some(47)
531 , 98 -> Some(8)
532 , 102 -> Some(12)
533 , 110 -> Some(10)
534 , 114 -> Some(13)
535 , 116 -> Some(9)
536 , _ -> None
537 }
538}
539
540/// A `\uXXXX` escape at `at`, or a surrogate pair of two of them.
541fn unicode_at :: data: Bytes at: Int -> Result<(Int, Int), DecodeError>
542{
543 use unit <- result.try (hex4 data (at + 2))
544 if unit >= 0xD800 && unit <= 0xDBFF
545 {
546 let low_at = at + 6
547 let second = if bytes.get data low_at == Some(92)
548 && bytes.get data (low_at + 1) == Some(117)
549 {
550 hex4 data (low_at + 2)
551 }
552 else
553 {
554 Error(Malformed(at, "a high surrogate with no low surrogate after it"))
555 }
556 use low <- result.try second
557 if low >= 0xDC00 && low <= 0xDFFF
558 {
559 let point = 0x10000 + int.shift_left (unit - 0xD800) 10 + (low - 0xDC00)
560 Ok((point, low_at + 6))
561 }
562 else
563 {
564 Error( Malformed( low_at
565 , "a high surrogate with no low surrogate after it"
566 )
567 )
568 }
569 }
570 else if unit >= 0xDC00 && unit <= 0xDFFF
571 {
572 Error(Malformed(at, "a low surrogate with no high surrogate before it"))
573 }
574 else
575 {
576 Ok((unit, at + 6))
577 }
578}
579
580/// The four hex digits at `at`, as a number.
581fn hex4 :: data: Bytes at: Int -> Result<Int, DecodeError>
582{
583 hex_from data at 0 0
584}
585
586fn hex_from :: data: Bytes at: Int seen: Int n: Int -> Result<Int, DecodeError>
587{
588 if seen == 4
589 {
590 Ok(n)
591 }
592 else
593 {
594 match bytes.get data (at + seen) |> option_map hex_digit
595 { Some(Some(d)) -> hex_from data at (seen + 1) (n * 16 + d)
596 , _ -> Error(Malformed(at - 2, "\\u needs four hex digits"))
597 }
598 }
599}
600
601fn hex_digit :: byte: Int -> Option<Int>
602{
603 if byte >= 48 && byte <= 57
604 {
605 Some(byte - 48)
606 }
607 else if byte >= 97 && byte <= 102
608 {
609 Some(byte - 87)
610 }
611 else if byte >= 65 && byte <= 70
612 {
613 Some(byte - 55)
614 }
615 else
616 {
617 None
618 }
619}
620
621/// `point` (a Unicode scalar value) appended as UTF-8.
622fn utf8 :: b: bytes.Builder point: Int -> bytes.Builder
623{
624 let tail = fn b shift
625 {
626 bytes.append_byte b (128 + int.and (int.shift_right point shift) 63)
627 }
628 if point < 0x80
629 {
630 bytes.append_byte b point
631 }
632 else if point < 0x800
633 {
634 tail (bytes.append_byte b (192 + int.shift_right point 6)) 0
635 }
636 else if point < 0x10000
637 {
638 tail (tail (bytes.append_byte b (224 + int.shift_right point 12)) 6) 0
639 }
640 else
641 {
642 tail
643 (tail (tail (bytes.append_byte b (240 + int.shift_right point 18)) 12) 6)
644 0
645 }
646}
647
648// -- numbers
649
650/// The number at `at`: `-? (0 | [1-9][0-9]*) (. [0-9]+)? ([eE] [+-]? [0-9]+)?`.
651fn number_at :: data: Bytes at: Int -> Parsed<Value>
652{
653 let signed = if bytes.get data at == Some(45) { at + 1 } else { at }
654 let whole = digits data signed
655 if whole == signed
656 {
657 Error(Malformed(at, "expected a digit"))
658 }
659 else if bytes.get data signed == Some(48) && whole > signed + 1
660 {
661 Error(Malformed(at, "a number with a leading zero"))
662 }
663 else
664 {
665 use fraction <- result.try (part data whole 46 False)
666 use exponent <- result.try (part data fraction 101 True)
667 let text = bytes.to_string_lossy (bytes.slice data at exponent)
668 if exponent == whole
669 {
670 match string.to_int text
671 { Ok(n) -> Ok((Int(n), exponent)), Error(e) -> Error(Malformed(at, e)) }
672 }
673 else
674 {
675 match float.parse text
676 { Ok(x) -> if x - x == 0.0
677 {
678 Ok((Float(x), exponent))
679 }
680 else
681 {
682 Error(Malformed(at, "a number too large for a Float"))
683 }
684 , Error(e) -> Error(Malformed(at, e))
685 }
686 }
687 }
688}
689
690/// After a number's digits at `at`: a part that starts with `mark` (`.`,
691/// or `e`/`E` when `exponent`) and needs at least one digit, or nothing.
692fn part ::
693 data: Bytes
694 at: Int
695 mark: Int
696 exponent: Bool
697 -> Result<Int, DecodeError>
698{
699 let marked = match bytes.get data at
700 { Some(byte) -> byte == mark || (exponent && byte == 69), None -> False }
701 if marked
702 {
703 let first = at + 1
704 let first = if exponent
705 && (bytes.get data first == Some(43) || bytes.get data first == Some(45))
706 {
707 first + 1
708 }
709 else
710 {
711 first
712 }
713 let end = digits data first
714 if end == first
715 {
716 Error(Malformed(at, "expected a digit"))
717 }
718 else
719 {
720 Ok(end)
721 }
722 }
723 else
724 {
725 Ok(at)
726 }
727}
728
729/// The index after the run of ASCII digits starting at `at`.
730fn digits :: data: Bytes at: Int -> Int
731{
732 match bytes.get data at
733 { Some(byte) if byte >= 48 && byte <= 57 -> digits data (at + 1), _ -> at }
734}
735
736// ---- the trait -----------------------------------------------------------------
737
738/// Encoding to JSON. `@derive(ToJson)` writes a record as an object keyed
739/// by field label, a positional constructor as an object from its name
740/// to its fields' array, and a constructor without fields as its name:
741/// the convention of `std/msgpack`'s `ToMsgPack`. Decoding is
742/// `json/decode`: ADR 0019's derives consume a value, they do not
743/// produce one.
744@derivable to_json_of_constructor
745pub trait ToJson<a>
746{
747 fn to_json :: x: a -> Value
748}
749
750/// The derive function of [`ToJson`] (ADR 0019).
751fn to_json_of_constructor :: c: Constructor<Value> -> Value
752{
753 match c.fields
754 { [] -> String(c.name)
755 , [f, ..] if f.label != "" ->
756 Object(list.map c.fields fn f { (f.label, f.value) })
757 , fields -> Object([(c.name, Array(list.map fields fn f { f.value }))])
758 }
759}
760
761/// `x` as compact JSON text: [`write`] of [`to_json`](ToJson).
762pub fn encode :: x: a -> String where ToJson<a>
763{
764 write (to_json x)
765}
766
767impl ToJson<Value>
768{
769 fn to_json :: v
770 {
771 v
772 }
773}
774
775impl ToJson<Int>
776{
777 fn to_json :: n
778 {
779 Int(n)
780 }
781}
782
783impl ToJson<Float>
784{
785 fn to_json :: x
786 {
787 Float(x)
788 }
789}
790
791impl ToJson<String>
792{
793 fn to_json :: s
794 {
795 String(s)
796 }
797}
798
799impl ToJson<Bool>
800{
801 fn to_json :: b
802 {
803 Bool(b)
804 }
805}
806
807impl ToJson<List<a>> where ToJson<a>
808{
809 fn to_json :: xs
810 {
811 Array(list.map xs to_json)
812 }
813}
814
815/// `None` is `null` and `Some(x)` is `x`, as JSON APIs expect (so an
816/// `Option<Option<a>>` cannot tell `Some(None)` from `None`).
817impl ToJson<Option<a>> where ToJson<a>
818{
819 fn to_json :: o
820 {
821 match o { Some(x) -> to_json x, None -> Null }
822 }
823}