/// JSON (RFC 8259): a value, a parser of untrusted text, a writer, and /// `@derive(ToJson)`. Decoding into your own types is `json/decode`. /// /// json.parse "[1, \"two\", null]" // Ok(Array([Int(1), String("two"), Null])) /// json.write (Object([("a", Int(1))])) // "\{\"a\":1}" /// json.encode [1, 2, 3] // "[1,2,3]", through ToJson /// /// `parse` reads untrusted input (request bodies): nesting is bounded /// (see [`max_depth`]), a key appears at most once in an object, every /// escape is checked (a lone surrogate is an error), and a number too /// large for a `Float` is an error rather than an infinity. A number /// with no fraction and no exponent is an `Int`, of any size; any other /// is a `Float`. /// /// An object keeps its keys in the order they were read or built, so /// `write` is deterministic: `parse (write v) == Ok(v)`. import std/bytes import std/dict import std/float import std/int import std/list import std/result import std/string /// A JSON value. `Object` keeps its entries in order. @derive Eq Debug pub type Value { Null , Bool(Bool) , Int(Int) , Float(Float) , String(String) , Array(List) , Object(List<(String, Value)>) } /// Why [`parse`] or a decoder (`json/decode`) failed. @derive Eq Debug pub type DecodeError { /// The text is not JSON; `at` is the byte offset. Malformed(at: Int, message: String) /// The JSON parsed, but the value at `path` is not the one expected. /// A path is object keys and array indexes, outermost first. , Mismatch(path: List, expected: String, found: String) /// The object at `path` has no field `name`. , Missing(path: List, name: String) } impl Show { fn show :: e { match e { Malformed(at, message) -> "invalid JSON at byte {at}: {message}" , Mismatch ( path , expected , found ) -> "{located path}: expected {expected}, found {found}" , Missing(path, name) -> "{located path}: missing field \"{name}\"" } } } impl Show { fn show :: v { write v } } /// `path` as `$.ships.0.symbol`, the root as `$`. pub fn located :: path: List -> String { string.concat ["$", ..list.map path fn p { ".{p}" }] } /// The most nesting [`parse`] accepts (arrays and objects; 512). Deeper /// input is an error, so a hostile body cannot overflow the stack. pub fn max_depth :: -> Int { 512 } /// What a `Value` is, for error messages ("a string", "an object"). pub fn kind :: v: Value -> String { match v { Null -> "null" , Bool(_) -> "a bool" , Int(_) -> "an integer" , Float(_) -> "a number" , String(_) -> "a string" , Array(_) -> "an array" , Object(_) -> "an object" } } /// The value of `name` in an object; `None` for a missing key or a value /// that is not an object. pub fn get :: v: Value name: String -> Option { match v { Object(entries) -> list.find entries fn entry { entry.0 == name } |> option_map fn entry { entry.1 } , _ -> None } } fn option_map :: o: Option f: fn(a) -> b -> Option { match o { Some(x) -> Some(f x), None -> None } } // ---- writing ------------------------------------------------------------------- /// `value` as compact JSON text. Panics on a `Float` that is infinite or /// NaN: JSON has no such number. pub fn write :: value: Value -> String { bytes.build_string (write_value (bytes.builder ()) value) } /// `value` as JSON text indented by two spaces per level, for people to /// read (docs, examples, logs). Same panics as [`write`]. pub fn pretty :: value: Value -> String { bytes.build_string (pretty_value (bytes.builder ()) value 0) } fn write_value :: b: bytes.Builder value: Value -> bytes.Builder { match value { Null -> bytes.append_string b "null" , Bool(True) -> bytes.append_string b "true" , Bool(False) -> bytes.append_string b "false" , Int(n) -> bytes.append_string b "{n}" , Float(x) -> bytes.append_string b (number x) , String(s) -> write_string b s , Array(items) -> { let b = bytes.append_byte b 91 let b = separated b items write_value bytes.append_byte b 93 } , Object(entries) -> { let b = bytes.append_byte b 123 let b = separated b entries write_entry bytes.append_byte b 125 } } } fn write_entry :: b: bytes.Builder entry: (String, Value) -> bytes.Builder { let b = write_string b entry.0 write_value (bytes.append_byte b 58) entry.1 } /// Each item written by `each`, with a comma between two. fn separated :: b: bytes.Builder items: List each: fn(bytes.Builder, a) -> bytes.Builder -> bytes.Builder { match items { [] -> b , [first, ..rest] -> list.fold rest (each b first) fn b item { each (bytes.append_byte b 44) item } } } fn pretty_value :: b: bytes.Builder value: Value depth: Int -> bytes.Builder { match value { Array([]) -> bytes.append_string b "[]" , Object([]) -> bytes.append_string b "\{\}" , Array(items) -> { let b = bytes.append_byte b 91 let b = indented b items depth fn b item { pretty_value b item (depth + 1) } bytes.append_byte b 93 } , Object(entries) -> { let b = bytes.append_byte b 123 let b = indented b entries depth fn b entry { let b = bytes.append_string (write_string b entry.0) ": " pretty_value b entry.1 (depth + 1) } bytes.append_byte b 125 } , _ -> write_value b value } } /// Each item on a line of its own, one level deeper than `depth`, and /// the closing bracket's line back at `depth`. fn indented :: b: bytes.Builder items: List depth: Int each: fn(bytes.Builder, a) -> bytes.Builder -> bytes.Builder { let inner = "\n" <> string.repeat " " (depth + 1) let b = separated b items fn b item { each (bytes.append_string b inner) item } bytes.append_string b ("\n" <> string.repeat " " depth) } /// A finite `Float` as a JSON number: `show` already writes `1.0`, /// `1e300` and `1.5e-7`, which are all JSON. fn number :: x: Float -> String { if x != x || x - x != 0.0 { panic "json.write: {x} is not a JSON number" } else { "{x}" } } /// `s` quoted, with `"`, `\` and the control characters escaped. Runs of /// bytes that need no escape are copied whole. fn write_string :: b: bytes.Builder s: String -> bytes.Builder { let data = bytes.from_string s let b = escape_from (bytes.append_byte b 34) data 0 0 bytes.append_byte b 34 } fn escape_from :: b: bytes.Builder data: Bytes start: Int at: Int -> bytes.Builder { if at == bytes.length data { bytes.append b (bytes.slice data start at) } else { let byte = bytes.read_u8 data at match escape_of byte { "" -> escape_from b data start (at + 1) , escape -> { let b = bytes.append b (bytes.slice data start at) escape_from (bytes.append_string b escape) data (at + 1) (at + 1) } } } } /// The escape `byte` is written as, or `""` when it is written as is. fn escape_of :: byte: Int -> String { match byte { 34 -> "\\\"" , 92 -> "\\\\" , 8 -> "\\b" , 12 -> "\\f" , 10 -> "\\n" , 13 -> "\\r" , 9 -> "\\t" , _ -> if byte < 32 { "\\u00" <> hex_byte byte } else { "" } } } fn hex_byte :: byte: Int -> String { let digits = "0123456789abcdef" let high = int.shift_right byte 4 let low = int.and byte 15 string.slice digits high (high + 1) <> string.slice digits low (low + 1) } // ---- parsing ------------------------------------------------------------------- /// The JSON value `text` holds. Whitespace may surround it; anything /// else after it is an error. pub fn parse :: text: String -> Result { let data = bytes.from_string text use (value, at) <- result.try (value_at data (spaced data 0) 0) let end = spaced data at if end == bytes.length data { Ok(value) } else { Error(Malformed(end, "text after the value")) } } /// [`parse`] of a request body: `data` must be UTF-8. pub fn parse_bytes :: data: Bytes -> Result { match bytes.to_string data { Ok(text) -> parse text , Error(e) -> Error(Malformed(0, "the text is not UTF-8: {e}")) } } type Parsed = Result<(a, Int), DecodeError> fn value_at :: data: Bytes at: Int depth: Int -> Parsed { match bytes.get data at { None -> Error(Malformed(at, "expected a value, found the end")) , Some(byte) -> match byte { 123 -> nested data at depth object_at , 91 -> nested data at depth array_at , 34 -> string_at data at |> result.map fn found { (String(found.0), found.1) } , 116 -> literal data at "true" Bool(True) , 102 -> literal data at "false" Bool(False) , 110 -> literal data at "null" Null , _ -> if byte == 45 || (byte >= 48 && byte <= 57) { number_at data at } else { Error(Malformed(at, "expected a value")) } } } } fn nested :: data: Bytes at: Int depth: Int inside: fn(Bytes, Int, Int) -> Parsed -> Parsed { if depth >= max_depth () { Error(Malformed(at, "nesting deeper than {max_depth ()} levels")) } else { inside data (spaced data (at + 1)) (depth + 1) } } fn literal :: data: Bytes at: Int word: String value: Value -> Parsed { let end = at + string.byte_length word if end <= bytes.length data && bytes.slice data at end == bytes.from_string word { Ok((value, end)) } else { Error(Malformed(at, "expected a value")) } } /// The index of the first byte at or after `at` that is not JSON /// whitespace (space, tab, line feed, carriage return). fn spaced :: data: Bytes at: Int -> Int { match bytes.get data at { Some(32) | Some(9) | Some(10) | Some(13) -> spaced data (at + 1), _ -> at } } // -- arrays and objects fn array_at :: data: Bytes at: Int depth: Int -> Parsed { match bytes.get data at { Some(93) -> Ok((Array([]), at + 1)), _ -> items_at data at depth [] } } fn items_at :: data: Bytes at: Int depth: Int kept: List -> Parsed { use (item, after) <- result.try (value_at data at depth) let next = spaced data after match bytes.get data next { Some(44) -> items_at data (spaced data (next + 1)) depth [item, ..kept] , Some(93) -> Ok((Array(list.reverse [item, ..kept]), next + 1)) , _ -> Error(Malformed(next, "expected , or ] in an array")) } } fn object_at :: data: Bytes at: Int depth: Int -> Parsed { match bytes.get data at { Some(125) -> Ok((Object([]), at + 1)) , _ -> entries_at data at depth [] (dict.empty ()) } } fn entries_at :: data: Bytes at: Int depth: Int kept: List<(String, Value)> seen: dict.Dict -> Parsed { use (name, after_name) <- result.try (key_at data at) if dict.has seen name { Error(Malformed(at, "the key \"{name}\" appears twice")) } else { let colon = spaced data after_name match bytes.get data colon { Some(58) -> { use (value, after) <- result.try (value_at data (spaced data (colon + 1)) depth) let kept = [(name, value), ..kept] let next = spaced data after match bytes.get data next { Some(44) -> entries_at data (spaced data (next + 1)) depth kept (dict.insert seen name ()) , Some(125) -> Ok((Object(list.reverse kept), next + 1)) , _ -> Error(Malformed(next, "expected , or \} in an object")) } } , _ -> Error(Malformed(colon, "expected : after a key")) } } } fn key_at :: data: Bytes at: Int -> Parsed { match bytes.get data at { Some(34) -> string_at data at , _ -> Error(Malformed(at, "expected a key (a string)")) } } // -- strings /// The string whose opening quote is at `at`, and the index after its /// closing quote. Runs of plain bytes are copied whole; the input is /// UTF-8 already, so only escapes need building. fn string_at :: data: Bytes at: Int -> Parsed { chars_at data (at + 1) (at + 1) (bytes.builder ()) } fn chars_at :: data: Bytes start: Int at: Int kept: bytes.Builder -> Parsed { match bytes.get data at { None -> Error(Malformed(at, "an unterminated string")) , Some(34) -> Ok( ( bytes.build_string (bytes.append kept (bytes.slice data start at)) , at + 1 ) ) , Some(92) -> match escape_at data at { Ok((point, after)) -> chars_at data after after (utf8 (bytes.append kept (bytes.slice data start at)) point) , Error(e) -> Error(e) } , Some(byte) -> if byte < 32 { Error(Malformed(at, "a control character in a string")) } else { chars_at data start (at + 1) kept } } } /// The code point the escape whose backslash is at `at` stands for, /// and the index after the escape. fn escape_at :: data: Bytes at: Int -> Result<(Int, Int), DecodeError> { match bytes.get data (at + 1) { Some(117) -> unicode_at data at , Some(byte) -> match unescaped byte { Some(plain) -> Ok((plain, at + 2)) , None -> Error(Malformed(at, "an unknown escape")) } , None -> Error(Malformed(at, "an unknown escape")) } } /// The byte a one-letter escape `\x` stands for, where `x` is `byte`. fn unescaped :: byte: Int -> Option { match byte { 34 -> Some(34) , 92 -> Some(92) , 47 -> Some(47) , 98 -> Some(8) , 102 -> Some(12) , 110 -> Some(10) , 114 -> Some(13) , 116 -> Some(9) , _ -> None } } /// A `\uXXXX` escape at `at`, or a surrogate pair of two of them. fn unicode_at :: data: Bytes at: Int -> Result<(Int, Int), DecodeError> { use unit <- result.try (hex4 data (at + 2)) if unit >= 0xD800 && unit <= 0xDBFF { let low_at = at + 6 let second = if bytes.get data low_at == Some(92) && bytes.get data (low_at + 1) == Some(117) { hex4 data (low_at + 2) } else { Error(Malformed(at, "a high surrogate with no low surrogate after it")) } use low <- result.try second if low >= 0xDC00 && low <= 0xDFFF { let point = 0x10000 + int.shift_left (unit - 0xD800) 10 + (low - 0xDC00) Ok((point, low_at + 6)) } else { Error( Malformed( low_at , "a high surrogate with no low surrogate after it" ) ) } } else if unit >= 0xDC00 && unit <= 0xDFFF { Error(Malformed(at, "a low surrogate with no high surrogate before it")) } else { Ok((unit, at + 6)) } } /// The four hex digits at `at`, as a number. fn hex4 :: data: Bytes at: Int -> Result { hex_from data at 0 0 } fn hex_from :: data: Bytes at: Int seen: Int n: Int -> Result { if seen == 4 { Ok(n) } else { match bytes.get data (at + seen) |> option_map hex_digit { Some(Some(d)) -> hex_from data at (seen + 1) (n * 16 + d) , _ -> Error(Malformed(at - 2, "\\u needs four hex digits")) } } } fn hex_digit :: byte: Int -> Option { if byte >= 48 && byte <= 57 { Some(byte - 48) } else if byte >= 97 && byte <= 102 { Some(byte - 87) } else if byte >= 65 && byte <= 70 { Some(byte - 55) } else { None } } /// `point` (a Unicode scalar value) appended as UTF-8. fn utf8 :: b: bytes.Builder point: Int -> bytes.Builder { let tail = fn b shift { bytes.append_byte b (128 + int.and (int.shift_right point shift) 63) } if point < 0x80 { bytes.append_byte b point } else if point < 0x800 { tail (bytes.append_byte b (192 + int.shift_right point 6)) 0 } else if point < 0x10000 { tail (tail (bytes.append_byte b (224 + int.shift_right point 12)) 6) 0 } else { tail (tail (tail (bytes.append_byte b (240 + int.shift_right point 18)) 12) 6) 0 } } // -- numbers /// The number at `at`: `-? (0 | [1-9][0-9]*) (. [0-9]+)? ([eE] [+-]? [0-9]+)?`. fn number_at :: data: Bytes at: Int -> Parsed { let signed = if bytes.get data at == Some(45) { at + 1 } else { at } let whole = digits data signed if whole == signed { Error(Malformed(at, "expected a digit")) } else if bytes.get data signed == Some(48) && whole > signed + 1 { Error(Malformed(at, "a number with a leading zero")) } else { use fraction <- result.try (part data whole 46 False) use exponent <- result.try (part data fraction 101 True) let text = bytes.to_string_lossy (bytes.slice data at exponent) if exponent == whole { match string.to_int text { Ok(n) -> Ok((Int(n), exponent)), Error(e) -> Error(Malformed(at, e)) } } else { match float.parse text { Ok(x) -> if x - x == 0.0 { Ok((Float(x), exponent)) } else { Error(Malformed(at, "a number too large for a Float")) } , Error(e) -> Error(Malformed(at, e)) } } } } /// After a number's digits at `at`: a part that starts with `mark` (`.`, /// or `e`/`E` when `exponent`) and needs at least one digit, or nothing. fn part :: data: Bytes at: Int mark: Int exponent: Bool -> Result { let marked = match bytes.get data at { Some(byte) -> byte == mark || (exponent && byte == 69), None -> False } if marked { let first = at + 1 let first = if exponent && (bytes.get data first == Some(43) || bytes.get data first == Some(45)) { first + 1 } else { first } let end = digits data first if end == first { Error(Malformed(at, "expected a digit")) } else { Ok(end) } } else { Ok(at) } } /// The index after the run of ASCII digits starting at `at`. fn digits :: data: Bytes at: Int -> Int { match bytes.get data at { Some(byte) if byte >= 48 && byte <= 57 -> digits data (at + 1), _ -> at } } // ---- the trait ----------------------------------------------------------------- /// Encoding to JSON. `@derive(ToJson)` writes a record as an object keyed /// by field label, a positional constructor as an object from its name /// to its fields' array, and a constructor without fields as its name: /// the convention of `std/msgpack`'s `ToMsgPack`. Decoding is /// `json/decode`: ADR 0019's derives consume a value, they do not /// produce one. @derivable to_json_of_constructor pub trait ToJson { fn to_json :: x: a -> Value } /// The derive function of [`ToJson`] (ADR 0019). fn to_json_of_constructor :: c: Constructor -> Value { match c.fields { [] -> String(c.name) , [f, ..] if f.label != "" -> Object(list.map c.fields fn f { (f.label, f.value) }) , fields -> Object([(c.name, Array(list.map fields fn f { f.value }))]) } } /// `x` as compact JSON text: [`write`] of [`to_json`](ToJson). pub fn encode :: x: a -> String where ToJson { write (to_json x) } impl ToJson { fn to_json :: v { v } } impl ToJson { fn to_json :: n { Int(n) } } impl ToJson { fn to_json :: x { Float(x) } } impl ToJson { fn to_json :: s { String(s) } } impl ToJson { fn to_json :: b { Bool(b) } } impl ToJson> where ToJson { fn to_json :: xs { Array(list.map xs to_json) } } /// `None` is `null` and `Some(x)` is `x`, as JSON APIs expect (so an /// `Option>` cannot tell `Some(None)` from `None`). impl ToJson> where ToJson { fn to_json :: o { match o { Some(x) -> to_json x, None -> Null } } }