a json library

part i taught the pieces. part ii spends them. the repository ships lib/json—a complete json decoder and encoder, escapes and \uXXXX and int-versus-float and failure positions included—written to prove the language can earn a living. it is six files and four hundred and change lines, and this chapter reads all of it, byte by byte. every panel below quotes the real files, and the executed samples either run the library itself or replay one of its moves small enough to fit on a page. first, what it feels like to use:

import "./using"
import "std/testing"

ok = decode "\{\"name\": \"kanso\", \"tags\": [\"fast\", \"simple\"]}"
bad = decode "\{\"name\": nope}"
print (describe ok)
  .> (_ -> print "recoded: {encode ok}")
  .> (_ -> print (testing/when_failed bad told))

decoded: { "name": "kanso" "tags": ["fast" "simple"] }
recoded: {"name":"kanso","tags":["fast","simple"]}
parse failed at byte 10: invalid literal

the module behind this panel is the library itself—the sample directory links the real lib/json files next to that main. three chapters shake hands in twelve lines: decode returns a value or an err, dispatch pulls the failure apart in describe, and the happy path never checks anything. note what the failure says: byte 10, invalid literal—the parser saw n, committed to null, and reported exactly where the input betrayed it.

six files, one namespace

the library is a directory, so chapter 07 already told you its shape: one namespace, files split by topic, alphabetical inside. the split reads like a table of contents:

• json.kso—the public api: decode, encode, the failure types
• value.kso—parsing values: objects, arrays, literals
• text.kso—strings, escapes, hex digits
• number.kso—ints, floats, and which bytes may start them
• scan.kso—whitespace and low-level cursor work
• json_test.kso—the suite

value.kso calls scan.kso's helpers without ceremony, and the test file reaches private helpers when it wants to. (the underscored names you'll see are house style from before pub arrived—the sweep that retires them rides with import enforcement.) the api file is where every read should start:

type _parsed
  pos:int
  value:json

type parse_failure
  position:int
  reason:string

fn _finish _ none
  err (parse_failure 0 "unexpected end of input")

fn _finish cs (_parsed p v)
  p2 = _skip_ws cs p
  if (p2 > (length cs)) v (_fail p2 "unexpected trailing characters")

fn decode s
  cs = bytes s
  _finish cs (_parse_value cs 1)

decode is three lines because the whole design lives in its two collaborators. every internal step returns a _parsed—a cursor position paired with the value parsed so far—because a parser's real product is not just a value but how far it got. and _finish is dispatch doing the last two checks: an absent result is the empty-input failure, and a present one is accepted only if nothing but whitespace remains. decode "1 x" fails at byte 3, and you will meet that exact assertion in the suite.

the next byte is the dispatch

most hand-written parsers begin with a lexer, a token enum, and a loop with a switch in it. kanso-json has none of those, because it doesn't need a value to branch on—it needs a value to dispatch on, and the next byte already is one. the heart of the parser is the chapter-03 move at industrial scale:

# value starts by byte: 34 quote, 91 bracket, 102 f, 110 n, 116 t, 123 brace
fn _value_for 34 cs p
  _parse_string cs (p + 1)

fn _value_for 91 cs p
  _parse_array cs (p + 1)

fn _value_for 102 cs p
  matched = _alse? cs p
  _word matched p 5 false

fn _value_for 110 cs p
  matched = _ull? cs p
  _word matched p 4 json_null

fn _value_for 116 cs p
  matched = _rue? cs p
  _word matched p 4 true

fn _value_for 123 cs p
  _parse_object cs (p + 1)

fn _value_for none _ p
  _fail p "unexpected end of input"

fn _value_for c cs p
  numeric = _number_start? c
  if numeric (_parse_number cs p) (_bad_value_char c p)

eight arms, one per way a json value can begin—including the none arm, because reading past the end of the byte array answers none, and running off the end of input is just an absent byte, dispatched like everything else. the three keyword literals each get a checker for their own tail: the first byte already chose the arm, so _rue? compares the three bytes after it where they sit, and _word turns that verdict into a result or a failure. reading past the end answers none, which equals no byte, so a truncated literal needs no length test of its own. here is that whole path, small enough to re-run on its own:

import "std/text"

type parse_failure
  position
  reason

# The first byte chose the arm, so what is left to check is the tail of one
# known keyword, compared where it sits. Reading past the end answers `none`,
# which equals no byte, so a truncated literal needs no length test.
fn alse? cs p
  cs[p + 1] == 97 and cs[p + 2] == 108 and cs[p + 3] == 115 and cs[p + 4] == 101

fn decode_literal s
  cs = text/bytes s
  value_for cs[1] cs 1

fn fail p reason
  err (parse_failure p reason)

fn rue? cs p
  cs[p + 1] == 114 and cs[p + 2] == 117 and cs[p + 3] == 101

fn ull? cs p
  cs[p + 1] == 117 and cs[p + 2] == 108 and cs[p + 3] == 108

fn value_for 102 cs p
  matched = alse? cs p
  word matched p false

fn value_for 110 cs p
  matched = ull? cs p
  word matched p "null"

fn value_for 116 cs p
  matched = rue? cs p
  word matched p true

fn value_for none _ p
  fail p "unexpected end of input"

fn value_for c _ p
  fail p "unexpected character `{text/utf8 [c]}`"

fn word true _ v
  v

fn word false p _
  fail p "invalid literal"

# `show` sits one package over from the raising: the decoder refuses a
# document and says nothing about what a caller does with that. A foreign
# reason is named, never destructured.
fn show (err r:parse_failure)
  "err at {r.position}: {r.reason}"

fn show v
  "ok: {v}"

print (show (decode_literal "true"))
  .> (_ -> print (show (decode_literal "null")))
  .> (_ -> print (show (decode_literal "nope")))
  .> (_ -> print (show (decode_literal "?")))

ok: true
ok: null
err at 1: invalid literal
err at 1: unexpected character `?`

the tail predicates read the spellings a byte at a time—114, 117, 101 is rue in utf-8—and each comparison is an == against a byte the input already holds. nope starts with n, so the parser commits to null and _word reports the mismatch; ? starts nothing, so the catch-all arm names the offending byte. and notice what the parser never writes: not one line of "check if the last step failed." a bad literal becomes an err deep inside, and it comes back out with its position intact. chapter 04's rule decides which callers pay for that: the ones the checker can see have to name the err, which is where finish, array_step, obj_key, obj_value and str_low get their e@(err _) arms. through the rest it still costs nothing to write.

arrays and objects follow the same discipline one level up. _array_delim dispatches on the byte after an element—comma means more items, 93 (a closing bracket) means done, none means the input ended mid-array—and the object path adds only a key: _obj_key_start insists on a quote, _expect_char demands the colon, and _obj_value folds each pair into a map with put. there is no recursion limit to manage and no parser state to restore, because every step passes its whole world—the bytes and a position—forward as arguments.

strings and the escape path

strings are where json parsers earn or lose their keep, and text.kso is the library's biggest file. the design is a two-speed scanner. the fast path bets that most strings contain no escapes: find2 hunts for the next quote or backslash byte, and dispatch on what it found decides which world you're in:

fn _string_at cs 34 start p
  _parsed (p + 1) (_string_ok p (utf8 (slice cs start (p - 1))))

fn _string_at cs 92 start p
  _str_chars cs p (append (bytes "") (slice cs start (p - 1)))

fn _string_at _ none _ p
  _fail p "unterminated string"

fn _string_at cs _ start p
  _string_scan cs start (p + 1)

fn _string_scan cs start p
  n = find2 cs p 34 92
  _string_at cs cs[n] start n

read from the bottom. a quote (34) ends the string, and the value is one slice of the original input—no copying, no character loop. a backslash (92) abandons the bet: the bytes so far are moved into an accumulator and the slow path takes over, appending decoded bytes one escape at a time. none means the input ended inside the string. the slow path is another dispatch table—one arm per legal escape character, each pushing the byte it names:

fn _str_escape cs 110 p acc
  _str_chars cs (p + 2) (append acc 10)

fn _str_escape cs 117 p acc
  _str_unicode cs p acc

fn _str_escape _ c p _
  _fail p "invalid escape `\\{utf8 [c]}`"

fn _str_hex4 cs p
  h1 = _hex_digit cs[p]
  h2 = _hex_digit (cs[p + 1])
  h3 = _hex_digit (cs[p + 2])
  h4 = _hex_digit (cs[p + 3])
  h1 * 4096 + h2 * 256 + h3 * 16 + h4

fn _str_unicode cs p acc
  code = _str_hex4 cs (p + 2)
  if (code < 55296 or 57343 < code)
    _str_chars cs (p + 6) (append acc (from_code code))
    _str_surrogate cs p acc code

the file has eight arms for the named escapes—110 is \n, and its siblings for \", \\, \/, \b, \f, \r, \t read identically—plus an end-of-input arm and the two shown here. \uXXXX is the interesting one: _str_hex4 reads four hex digits into a code point, from_code turns the code point into a character, and its utf-8 bytes join the accumulator. a code point in the surrogate range is half a character, and _str_surrogate goes looking for the other half. the digit math is worth running with your own eyes:

import "std/text"

fn decode_u s
  cs = text/bytes s
  h1 = hex_digit cs[1]
  h2 = hex_digit cs[2]
  h3 = hex_digit cs[3]
  h4 = hex_digit cs[4]
  text/from_code (h1 * 4096 + h2 * 256 + h3 * 16 + h4)

fn hex_alpha c
  if (96 < c and c < 103) (c - 87) (hex_upper c)

fn hex_digit none
  err "unexpected end of input"

fn hex_digit c
  if (47 < c and c < 58) (c - 48) (hex_alpha c)

fn hex_upper c
  if (64 < c and c < 71) (c - 55) (err "invalid hex digit")

pub play = print (decode_u "00e9")
  .> (_ -> print (decode_u "305f"))
  .> (_ -> print (decode_u "7b80"))

é
た
简

those are the library's own hex functions, verbatim—the three-way relay _hex_digit → _hex_alpha → _hex_upper tries digits, then lowercase, then uppercase, and a byte that is none of them raises the one genuinely unhandleable failure in the file. that last character is 7b80—简, the first half of 簡素. the library can spell its own name.

numbers without a lexer

numbers get the same treatment, and one call answers both questions. text/number_span starts at the number's first byte and returns the position of the first byte that cannot belong to it, negated when a ., an e or an E went past. the runtime classifies sixteen bytes at a time, where a walk written in kanso dispatched on every byte. by the time the answer comes back, the library knows where the number ends and which converter to call:

fn scan cs start p
  spanned cs start (text/number_span cs p)

fn spanned cs start e
  if (e < 0) (number_done cs start (0 - e) true) (number_done cs start e false)

fn number_done cs start p true
  parsed p (number_ok start (text/to_float (text/slice cs start (p - 1))))

fn number_done cs start p false
  parsed p (number_ok start (text/to_int (text/slice cs start (p - 1))))

replay the decision on its own inputs. the sample below asks the two questions apart, one walk each, in kanso rather than in the runtime; it prints which converter would fire:

import "std/text"

fn classify s
  cs = text/bytes s
  q = number_end cs 1
  digits = text/slice cs 1 (q - 1)
  floaty = mark_from cs 1 (q - 1)
  if floaty "float64 {text/to_float digits}" "int {text/to_int digits}"

fn is_number_char 43
  true

fn is_number_char 45
  true

fn is_number_char 46
  true

fn is_number_char 69
  true

fn is_number_char 101
  true

fn is_number_char none
  false

fn is_number_char c
  47 < c and c < 58

fn mark_from cs p q
  if (p > q) false (mark_step cs cs[p] p q)

fn mark_step _ 46 _ _
  true

fn mark_step _ 69 _ _
  true

fn mark_step _ 101 _ _
  true

fn mark_step _ none _ _
  false

fn mark_step cs _ p q
  mark_from cs (p + 1) q

fn number_end cs p
  if (is_number_char cs[p]) (number_end cs (p + 1)) p

print (classify "42")
  .> (_ -> print (classify "-17"))
  .> (_ -> print (classify "3.25"))
  .> (_ -> print (classify "6e3"))

error[naming]: `is_number_char` answers only true or false: name it `is_number_char?`
  --> numbers.kso:10:4
  10 | fn is_number_char 43
          ^
error[naming]: `mark_from` answers only true or false: name it `mark_from?`
  --> numbers.kso:31:4
  31 | fn mark_from cs p q
          ^
error[naming]: `mark_step` answers only true or false: name it `mark_step?`
  --> numbers.kso:34:4
  34 | fn mark_step _ 46 _ _
          ^

the sample's helpers are the library's older shape, kept on purpose: is_number_char and number_end find where the number stops, and mark_from walks the same bytes again asking whether a float mark went past. the library carries the mark along with the scan now and reads each number's bytes once. an integer stays an integer—42 decodes to int 42, not 42.0—and anything marked with a dot or an exponent becomes a float64, so 6e3 is 6000.0. the greedy scan is deliberately looser than the json grammar in either shape: any plausible number byte is accepted, and to_int or to_float is the real judge. if the conversion fails, _number_ok converts that refusal into a parse_failure pinned to where the number began. let the builtin own the hard part; the parser only needs to know where the number stops and whether a float mark appeared.

failure carries its position

every failure in the library flows through one two-line function:

fn _fail p reason
  err (parse_failure p reason)

# json whitespace bytes: tab, newline, carriage return, space
fn _ws? 9
  true

fn _ws? 10
  true

fn _ws? 13
  true

fn _ws? 32
  true

fn _ws? none
  false

fn _ws? _
  false

fn _skip_ws cs p
  if (_ws? cs[p]) (_skip_ws cs (p + 1)) p

a parse_failure is an err wrapping a record: the byte position and a human reason. because the cursor is always an argument, the position is always at hand when something goes wrong—there is no "current location" to reconstruct from a lexer's state. the mini-decoder below is _finish's trailing-characters check in miniature: skip whitespace, read a value, skip whitespace again, and demand the input be over. the sample keeps the library's _ws? and _skip_ws byte for byte:

import "std/text"

type parse_failure
  position
  reason

fn decode_int s
  cs = text/bytes s
  p = skip_ws cs 1
  q = digits_end cs p
  v = text/to_int (text/slice cs p (q - 1))
  trailing cs (skip_ws cs q) v

fn digits_end cs p
  if (digit? cs[p]) (digits_end cs (p + 1)) p

fn fail p reason
  err (parse_failure p reason)

fn digit? none
  false

fn digit? c
  47 < c and c < 58

fn ws? 9
  true

fn ws? 10
  true

fn ws? 13
  true

fn ws? 32
  true

fn ws? none
  false

fn ws? _
  false

# `show` sits one package over from the raising: the decoder refuses a
# document and says nothing about what a caller does with that. A foreign
# reason is named, never destructured.
fn show (err r:parse_failure)
  "err at {r.position}: {r.reason}"

fn show v
  "ok: {v}"

fn skip_ws cs p
  if (ws? cs[p]) (skip_ws cs (p + 1)) p

fn trailing cs p v
  if (p > length cs) v (fail p "unexpected trailing characters")

print (show (decode_int "  42  "))
  .> (_ -> print (show (decode_int "1 x")))
  .> (_ -> print (show (decode_int "  7 ;")))

ok: 42
err at 3: unexpected trailing characters
err at 5: unexpected trailing characters

positions point at the first byte the parser could not accept: the x in 1 x sits at byte 3, the ; at byte 5. the policy choice that rounds the failure story out is not json's to make, and the panel below is a caller's file rather than the library's:

type defect
  reason:string

fn must (err reason)
  err (defect "{reason}")

fn must v
  v

chapter 04 drew the line: an err a caller might reasonably handle is a value to dispatch on; an err nobody should handle rises to the endpoint. decode hands back the first kind, because malformed input is the caller's business—maybe it retries, maybe it reports byte 10 to a user. converting to the second kind—a failure on input you control, a config file baked into the program, a fixture, where a parse failure is a bug with your name on it—is the caller's move to make, and it has to be, because json cannot make it. json could write an arm for its own err, since an arm names a failure wherever it is written, and it does not: the library has nothing to say about a document it has already refused, and an arm inside it would decide for every caller at once. the suite reads the position from outside, through std/testing, and a caller who wants the defect conversion writes it in their own package.

the suite

nineteen booleans pin the whole library—decoding every value kind, both escape directions, unicode, whitespace, error positions, and a round trip:

test_decode_unicode = decode "\"\\u00e9\"" == "é"

test_error_position =
  decoded = decode "[1, nope]"
  testing/when_failed decoded (r -> r.position == 5)

test_error_trailing =
  decoded = decode "1 x"
  testing/when_failed decoded (r -> r.position == 3)


test_roundtrip =
  text = "\{\"a\":[1,2.5,\"x\"],\"b\":null}"
  encode (decode text) == text

test_decode_array ... ok
test_decode_bool ... ok
test_decode_escapes ... ok
test_decode_float ... ok
test_decode_int ... ok
test_decode_nested ... ok
test_decode_object ... ok
test_decode_string ... ok
test_decode_surrogate_pair ... ok
test_decode_unicode ... ok
test_decode_whitespace ... ok
test_encode_empty_list ... ok
test_encode_empty_map ... ok
test_encode_escapes ... ok
test_encode_shorthands ... ok
test_encode_nested ... ok
test_error_position ... ok
test_error_trailing ... ok
test_roundtrip ... ok
19 passed, 0 failed

look at what each test costs. test_error_position asserts that decoding [1, nope] fails at byte 5—the whole failure model in one comparison. it goes through std/testing, which hands the reason record to a continuation, because json may not reach into an err json raised. test_roundtrip is the deepest assertion in the file: decode a document, encode the result, and demand the original text back. it holds because encode is canonical—no spaces, keys in map order—so a canonically-written input survives the loop byte for byte. and every one of them is a plain equality between values, which chapter 07 promised would be enough.

encode and pretty-printing

the decoder is a search; the encoder is a fold. one arm per value kind, and every arm appends onto the same byte accumulator, so a byte is written once no matter how deep in the tree it was born. encode itself is two calls: seed the builder, decode the finished bytes back into a string.

fn encode v
  text/utf8 (_encode_onto (text/bytes "") v)

fn _encode_onto acc true
  text/append acc "true"

fn _encode_onto acc json_null
  text/append acc "null"

fn _encode_onto acc n:int
  text/append acc "{n}"

fn _encode_onto acc s:string
  opened = _escape_onto (text/append acc 34) s
  text/append opened 34

fn _encode_onto acc xs:[]json
  if (length xs == 0) (text/append acc "[]") (_encode_list acc xs)

fn _encode_onto acc m:map[string json]
  _encode_map acc (keys m) (values m)

(the false and float64 arms read exactly like their neighbors, and _encode_list and _encode_map walk their elements with a comma between each pair. a map goes in as two lists, its keys and its values, which line up position by position, so the walk reads the ith of each.) where the literal arms dispatch on a value, the last four dispatch on a type—n:int, xs:[]json—which is the other half of chapter 03. text/append is the builder from chapter 06: the accumulator owns its buffer and extends it in place when it can, so the fold of appends costs what one pass over the output costs, while every intermediate stays an ordinary value.

the one arm with real work is strings, and the work is _escape_onto: decode's escape path run in reverse. it dispatches on bytes, the way decode's scanner does, and it borrows decode's other habit too—one scan (find2_below: the first quote, backslash, or control byte) proves most strings need no escaping at all, and a proven-clean string is appended whole, in one copy. the sample carries the library's escape functions verbatim and quotes two awkward strings—one with a quote and a newline, one with a bell character (byte 7) in the middle:

import "std/list"
import "std/text"

fn esc_byte acc 9
  text/append (text/append acc 92) 116

fn esc_byte acc 10
  text/append (text/append acc 92) 110

fn esc_byte acc 13
  text/append (text/append acc 92) 114

fn esc_byte acc 34
  text/append (text/append acc 92) 34

fn esc_byte acc 92
  text/append (text/append acc 92) 92

fn esc_byte acc b
  if (b < 32) (u_bytes acc b) (text/append acc b)

fn escape_able acc bs
  list/fold bs acc (a b -> esc_byte a b)

fn escape_clean acc s bs n
  if (length bs < n) (text/append acc s) (escape_able acc bs)

fn escape_onto acc s
  bs = text/bytes s
  escape_clean acc s bs (text/find2_below bs 1 34 92 32)

fn escape_str s
  text/utf8 (escape_onto (text/bytes "") s)

hex_byte_table = text/bytes "0123456789abcdef"

fn hex_code n
  hex_byte_table[n + 1]

pub play =
  bell = text/from_code 7
  print (quote_str "a\"b\nc") .> (_ -> print (quote_str "ring{bell}ring"))

fn quote_str s
  "\"{escape_str s}\""

fn u_bytes acc b
  lo = hex_code (b % 16)
  hi = hex_code (b / 16)
  text/append (text/append (text/append acc "\\u00") hi) lo

"a\"b\nc"
"ring\u0007ring"

encode is deliberately compact—machine-to-machine json wants no whitespace. a pretty-printer is the same fold with an indent depth threaded through, and it is small enough to write here in full. this is the chapter's one extension beyond the library, written string-per-node because that style reads best on a page; threading the byte builder through it instead is a good exercise, and the library's own encode above is the worked answer:

import "std/list"
import "std/text"

type json_null

fn entry_block (entry k v) d
  "{pad d}\"{k}\": {pretty v d}"

fn pad 0
  ""

fn pad n
  "  {pad (n - 1)}"

pub play =
  doc = { "name":"kanso" "port":8080 "tags":["fast" "simple"] }
  print (pretty doc 0)

fn pretty true _
  "true"

fn pretty false _
  "false"

fn pretty json_null _
  "null"

fn pretty n:int _
  "{n}"

fn pretty x:float64 _
  "{x}"

fn pretty s:string _
  "\"{s}\""

fn pretty xs:[]some d
  d2 = d + 1
  lines = list/to_list (list/map xs (v -> "{pad d2}{pretty v d2}"))
  inner = text/join lines ",\n"
  "[\n{inner}\n{pad d}]"

fn pretty m:map[string some] d
  d2 = d + 1
  lines = list/to_list (list/map (entries m) (e -> entry_block e d2))
  inner = text/join lines ",\n"
  "\{\n{inner}\n{pad d}}"

{
  "name": "kanso",
  "port": 8080,
  "tags": [
    "fast",
    "simple"
  ]
}

same eight-arm shape as encode, one extra argument. the scalar arms ignore the depth with _; the compound arms deepen it and lay each element on its own indented line. _pad is recursion instead of a loop—dispatch on 0 is the base case—and the whole printer is under forty lines. drop it into lib/json as pretty.kso (with _escape_str in place of the naive string arm) and it would be the module's seventh file, sharing the namespace like everything else.

what you can do now

you have now read a real library end to end, and nothing in it was new: byte dispatch is chapter 03, the err railway is chapter 04, the module layout is chapter 07, and the rest is arithmetic. that is the point of part ii—the language does not grow a special mode for serious programs. you can navigate kanso-json by name, extend it in its own style, and—the sharper skill—recognize its shapes elsewhere: a two-speed scanner betting on the common case, a cursor threaded as an argument so failures always know where they are, a caller choosing between handleable failure and defect in one word. next chapter, the same language simulates elections.

exercises

1. make pretty the module's seventh file. add pretty.kso to a copy of lib/json, swap its naive string arm for one that uses _escape_str, and add test_pretty_roundtrip: decoding a pretty-printed document must equal decoding the compact original.
2. json forbids leading zeros—007 is not a number—but to_int happily accepts it. add the rejection to _parse_number with a positioned failure, and a test pinning where decode "[1, 007]" fails.
3. _str_unicode reads exactly one \uXXXX. characters outside the basic plane arrive as surrogate pairs—"😀" is one emoji, not two characters. extend the escape path to spot a high surrogate, demand its partner, and combine them; pin it with a test.
4. the suite pins positions for a bad literal and trailing characters, but not for an unterminated string. write test_error_unterminated asserting the position decode "\"abc" fails at, predicting the number before you run it.