pdf-odin-llm/encoding_test.odin

package pdf

import "core:fmt"
import "core:mem"
import "core:mem/virtual"
import "core:testing"
import "core:unicode/utf8"

// ---------------------------------------------------------------------------
// Helpers
//
// Test objects are built in a local arena so that a failing assertion cannot
// leak: the arena is destroyed on the way out whatever happened. Lookups are
// driven with a nil Document, which `dict_get` and friends degrade to direct
// access for -- the trees under test hold no indirect references.
// ---------------------------------------------------------------------------

@(private = "file")
Fixture :: struct {
    arena: virtual.Arena,
    alloc: mem.Allocator,
}

@(private = "file")
Pair :: struct {
    key:   string,
    value: Object,
}

@(private = "file")
fixture_init :: proc(f: ^Fixture) {
    _ = virtual.arena_init_growing(&f.arena)
    f.alloc = virtual.arena_allocator(&f.arena)
}

@(private = "file")
fixture_destroy :: proc(f: ^Fixture) {
    virtual.arena_destroy(&f.arena)
}

@(private = "file")
str :: proc(s: string) -> Object {
    return String(transmute([]byte)s)
}

@(private = "file")
arr :: proc(f: ^Fixture, items: ..Object) -> ^Array {
    a := new_array(f.alloc, max(len(items), 1))
    for it in items {
        array_push(a, it)
    }
    return a
}

@(private = "file")
dict :: proc(f: ^Fixture, pairs: ..Pair) -> ^Dict {
    d := new_dict(f.alloc, max(len(pairs), 1))
    for p in pairs {
        dict_set(d, p.key, p.value)
    }
    return d
}

@(private = "file")
kv :: proc(key: string, value: Object) -> Pair {
    return Pair{key, value}
}

// ---------------------------------------------------------------------------
// decode_text_string
// ---------------------------------------------------------------------------

@(test)
test_text_string_empty :: proc(t: ^testing.T) {
    got := decode_text_string({})
    defer delete(got)
    testing.expect_value(t, got, "")
}

@(test)
test_text_string_ascii :: proc(t: ^testing.T) {
    got := decode_text_string(transmute([]byte)string("Hello, PDF"))
    defer delete(got)
    testing.expect_value(t, got, "Hello, PDF")
}

// The whole of PDFDocEncoding that is not Latin-1: ISO 32000-2, Annex D.2.
@(test)
test_pdfdoc_encoding_specials :: proc(t: ^testing.T) {
    Case :: struct {
        code: byte,
        want: rune,
    }
    cases := []Case{
        // 0x18-0x1F: the accents Latin-1 leaves out.
        {0x18, '˘'}, {0x19, 'ˇ'}, {0x1A, 'ˆ'}, {0x1B, '˙'},
        {0x1C, '˝'}, {0x1D, '˛'}, {0x1E, '˚'}, {0x1F, '˜'},
        // 0x80-0x9E: the typography Latin-1 has no room for.
        {0x80, '•'}, {0x81, '†'}, {0x82, '‡'}, {0x83, '…'},
        {0x84, '—'}, {0x85, '–'}, {0x86, 'ƒ'}, {0x87, '⁄'},
        {0x88, '‹'}, {0x89, '›'}, {0x8A, '−'}, {0x8B, '‰'},
        {0x8C, '„'}, {0x8D, '“'}, {0x8E, '”'}, {0x8F, '‘'},
        {0x90, '’'}, {0x91, '‚'}, {0x92, '™'}, {0x93, 'fi'},
        {0x94, 'fl'}, {0x95, 'Ł'}, {0x96, 'Œ'}, {0x97, 'Š'},
        {0x98, 'Ÿ'}, {0x99, 'Ž'}, {0x9A, 'ı'}, {0x9B, 'ł'},
        {0x9C, 'œ'}, {0x9D, 'š'}, {0x9E, 'ž'},
        // 0xA0 is the euro sign, not a no-break space.
        {0xA0, '€'},
        // The four codes PDFDocEncoding leaves undefined fall back to their
        // own value, which keeps a Latin-1 round trip lossless.
        {0x00, '\x00'}, {0x7F, '\x7f'}, {0x9F, '\u009f'}, {0xAD, '\u00ad'},
        // Everything else is Latin-1.
        {0x01, '\x01'}, {0x41, 'A'}, {0x20, ' '}, {0xE9, 'é'}, {0xFF, 'ÿ'},
        {0xA9, '©'}, {0xB5, 'µ'},
    }
    for c in cases {
        raw := []byte{c.code}
        got := decode_text_string(raw)
        defer delete(got)
        want := utf8.runes_to_string({c.want})
        defer delete(want)
        if got != want {
            testing.expectf(t, false, "PDFDocEncoding 0x%02X: got %q, want %q", c.code, got, want)
        }
    }
}

@(test)
test_pdfdoc_encoding_round_trip :: proc(t: ^testing.T) {
    // Every byte decodes to exactly one rune, and no byte is dropped.
    raw := make([]byte, 256)
    defer delete(raw)
    for i in 0 ..< 256 {
        raw[i] = byte(i)
    }
    got := decode_text_string(raw)
    defer delete(got)
    testing.expect_value(t, utf8.rune_count_in_string(got), 256)
}

@(test)
test_text_string_utf16be :: proc(t: ^testing.T) {
    Case :: struct {
        name: string,
        raw:  []byte,
        want: string,
    }
    cases := []Case{
        {"bom only", {0xFE, 0xFF}, ""},
        {"ascii", {0xFE, 0xFF, 0x00, 'H', 0x00, 'i'}, "Hi"},
        {"bmp", {0xFE, 0xFF, 0x00, 0xE9}, "é"},
        // U+1F600 GRINNING FACE, the canonical surrogate pair.
        {"surrogate pair", {0xFE, 0xFF, 0xD8, 0x3D, 0xDE, 0x00}, "\U0001F600"},
        {"pair then text", {0xFE, 0xFF, 0xD8, 0x3D, 0xDE, 0x00, 0x00, '!'}, "\U0001F600!"},
        // A high surrogate followed by an ordinary character: the character
        // survives and the surrogate becomes U+FFFD, never invalid UTF-8.
        {"unpaired high", {0xFE, 0xFF, 0xD8, 0x3D, 0x00, 'A'}, "�A"},
        {"unpaired high at end", {0xFE, 0xFF, 0xD8, 0x3D}, "�"},
        {"unpaired low", {0xFE, 0xFF, 0xDE, 0x00}, "�"},
        {"two highs", {0xFE, 0xFF, 0xD8, 0x3D, 0xD8, 0x3D, 0xDE, 0x00}, "�\U0001F600"},
        // Truncated in the middle of a code unit.
        {"odd length", {0xFE, 0xFF, 0x00, 'A', 0x00}, "A�"},
        {"odd length only", {0xFE, 0xFF, 0x41}, "�"},
    }
    for c in cases {
        got := decode_text_string(c.raw)
        defer delete(got)
        if got != c.want {
            testing.expectf(t, false, "utf16be %s: got %q, want %q", c.name, got, c.want)
        }
    }
}

@(test)
test_text_string_utf16le :: proc(t: ^testing.T) {
    // Not in the format, but produced in the wild often enough to decode.
    got := decode_text_string({0xFF, 0xFE, 'H', 0x00, 'i', 0x00})
    defer delete(got)
    testing.expect_value(t, got, "Hi")

    pair := decode_text_string({0xFF, 0xFE, 0x3D, 0xD8, 0x00, 0xDE})
    defer delete(pair)
    testing.expect_value(t, pair, "\U0001F600")
}

@(test)
test_text_string_utf8_bom :: proc(t: ^testing.T) {
    got := decode_text_string({0xEF, 0xBB, 0xBF, 0xC3, 0xA9, 'x'})
    defer delete(got)
    testing.expect_value(t, got, "éx")

    // A truncated sequence after a mark that promised UTF-8.
    bad := decode_text_string({0xEF, 0xBB, 0xBF, 'a', 0xC3})
    defer delete(bad)
    testing.expect_value(t, bad, "a�")

    // A byte that can never start a UTF-8 sequence.
    lone := decode_text_string({0xEF, 0xBB, 0xBF, 0xFF, 'z'})
    defer delete(lone)
    testing.expect_value(t, lone, "�z")

    empty := decode_text_string({0xEF, 0xBB, 0xBF})
    defer delete(empty)
    testing.expect_value(t, empty, "")
}

@(test)
test_text_string_short_marks :: proc(t: ^testing.T) {
    // One byte of what would have been a mark is PDFDocEncoding, not a
    // truncated UTF-16 string.
    one := decode_text_string({0xFE})
    defer delete(one)
    testing.expect_value(t, one, "þ")

    two := decode_text_string({0xEF, 0xBB})
    defer delete(two)
    testing.expect_value(t, two, "ï»")
}

@(test)
test_decode_text_object :: proc(t: ^testing.T) {
    got := decode_text_object(nil, str("Title"))
    defer delete(got)
    testing.expect_value(t, got, "Title")

    // A missing or wrongly typed entry is the empty string, not a crash.
    none := decode_text_object(nil, nil)
    defer delete(none)
    testing.expect_value(t, none, "")

    num := decode_text_object(nil, i64(7))
    defer delete(num)
    testing.expect_value(t, num, "")
}

// ---------------------------------------------------------------------------
// parse_date
// ---------------------------------------------------------------------------

@(test)
test_parse_date_shapes :: proc(t: ^testing.T) {
    Case :: struct {
        raw:  string,
        want: Date,
    }
    cases := []Case{
        // The form the spec gives (ISO 32000-2, 7.9.4).
        {"D:199812231952-08'00'", {1998, 12, 23, 19, 52, 0, -8, 0, true}},
        {"D:20050320174900+01'00'", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // An offset whose minutes are not zero: the sign is on both fields.
        {"D:20050320174900-05'30'", {2005, 3, 20, 17, 49, 0, -5, -30, true}},
        // Apostrophes missing entirely -- several writers do this.
        {"D:200503201749+0100", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // A doubled trailing apostrophe, which the 1.7 spec's own example had.
        {"D:20050320174900+01'00''", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // A colon where the apostrophe belongs (XMP habits leaking in).
        {"D:20050320174900+01:00", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // Only the hours of the offset.
        {"D:20050320174900+01", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // Z, with and without the redundant zero offset after it.
        {"D:20050320174900Z", {2005, 3, 20, 17, 49, 0, 0, 0, true}},
        {"D:20050320174900Z00'00'", {2005, 3, 20, 17, 49, 0, 0, 0, true}},
        // No "D:" prefix, and a lower-case one.
        {"20050320174900", {2005, 3, 20, 17, 49, 0, 0, 0, false}},
        {"d:20050320", {2005, 3, 20, 0, 0, 0, 0, 0, false}},
        // Truncated at every field boundary.
        {"D:2005", {2005, 1, 1, 0, 0, 0, 0, 0, false}},
        {"D:200503", {2005, 3, 1, 0, 0, 0, 0, 0, false}},
        {"D:20050320", {2005, 3, 20, 0, 0, 0, 0, 0, false}},
        {"D:2005032017", {2005, 3, 20, 17, 0, 0, 0, 0, false}},
        {"D:200503201749", {2005, 3, 20, 17, 49, 0, 0, 0, false}},
        // An odd digit where a two-digit field belongs is dropped, not guessed.
        {"D:2005032", {2005, 3, 1, 0, 0, 0, 0, 0, false}},
        // Leading whitespace, and a space before the offset.
        {"  D:20050320174900 -03'00'", {2005, 3, 20, 17, 49, 0, -3, 0, true}},
        // Every field out of range: clamped, not rejected.
        {"D:20051345996199+99'99'", {2005, 12, 31, 23, 59, 59, 23, 59, true}},
        // Month 0 and day 0 are what "unset" looks like in some writers.
        {"D:20050000000000", {2005, 1, 1, 0, 0, 0, 0, 0, false}},
        // 29 February against the Gregorian leap rule, century years included.
        {"D:20210229", {2021, 2, 28, 0, 0, 0, 0, 0, false}},
        {"D:20200229", {2020, 2, 29, 0, 0, 0, 0, 0, false}},
        {"D:19000229", {1900, 2, 28, 0, 0, 0, 0, 0, false}},
        {"D:20000229", {2000, 2, 29, 0, 0, 0, 0, 0, false}},
        // 31 April clamps to the 30th.
        {"D:20050431", {2005, 4, 30, 0, 0, 0, 0, 0, false}},
        // A sign with no digits after it is not an offset.
        {"D:20050320174900+", {2005, 3, 20, 17, 49, 0, 0, 0, false}},
        // Trailing junk after a complete date is ignored.
        {"D:20050320174900+01'00'garbage", {2005, 3, 20, 17, 49, 0, 1, 0, true}},
        // A 24th hour (midnight ending the day) clamps back rather than
        // rolling the date over.
        {"D:20050320240000", {2005, 3, 20, 23, 0, 0, 0, 0, false}},
        // A leap second clamps.
        {"D:20051231235960Z", {2005, 12, 31, 23, 59, 59, 0, 0, true}},
        // A lower-case z is accepted the way a lower-case d: is.
        {"D:20051231235900z", {2005, 12, 31, 23, 59, 0, 0, 0, true}},
    }
    for c in cases {
        got, ok := parse_date(transmute([]byte)c.raw)
        if !ok {
            testing.expectf(t, false, "parse_date(%q): not ok", c.raw)
            continue
        }
        if got != c.want {
            testing.expectf(t, false, "parse_date(%q):\n got %v\nwant %v", c.raw, got, c.want)
        }
    }
}

@(test)
test_parse_date_rejects :: proc(t: ^testing.T) {
    bad := []string{
        "",
        "D:",
        "D",
        "not a date",
        "D:203",             // three digits is not a year
        "\x00\x00\x00",
        "D:  ",
        "199",
        // Junk long enough that a year-shaped run late in it is out of the
        // window: a date is a few dozen bytes, not a haystack.
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1999",
    }
    for s in bad {
        if _, ok := parse_date(transmute([]byte)s); ok {
            testing.expectf(t, false, "parse_date(%q): expected failure", s)
        }
    }
}

@(test)
test_date_offset_minutes :: proc(t: ^testing.T) {
    d, ok := parse_date(transmute([]byte)string("D:20050320174900-05'30'"))
    testing.expect(t, ok)
    testing.expect_value(t, date_offset_minutes(d), -330)

    d2, ok2 := parse_date(transmute([]byte)string("D:20050320174900+05'45'"))
    testing.expect(t, ok2)
    testing.expect_value(t, date_offset_minutes(d2), 345)

    d3, ok3 := parse_date(transmute([]byte)string("D:20050320"))
    testing.expect(t, ok3)
    testing.expect_value(t, date_offset_minutes(d3), 0)
}

// ---------------------------------------------------------------------------
// Name and number trees
// ---------------------------------------------------------------------------

// name_leaf builds a leaf holding the given keys, each mapped to the name
// "v<key>", with the /Limits the format requires of a non-root node.
@(private = "file")
name_leaf :: proc(f: ^Fixture, keys: ..string) -> ^Dict {
    names := new_array(f.alloc, 2 * len(keys))
    for k in keys {
        array_push(names, str(k))
        array_push(names, Name(fmt.aprintf("v%s", k, allocator = f.alloc)))
    }
    return dict(f,
        kv("Names", names),
        kv("Limits", arr(f, str(keys[0]), str(keys[len(keys) - 1]))),
    )
}

@(private = "file")
inner :: proc(f: ^Fixture, lo, hi: string, kids: ..^Dict) -> ^Dict {
    ka := new_array(f.alloc, len(kids))
    for k in kids {
        array_push(ka, k)
    }
    return dict(f, kv("Kids", ka), kv("Limits", arr(f, str(lo), str(hi))))
}

// A three-level tree: root -> 2 branches -> 2 leaves each, 12 keys in all.
@(private = "file")
build_name_tree :: proc(f: ^Fixture) -> ^Dict {
    l1 := name_leaf(f, "alpha", "bravo", "charlie")
    l2 := name_leaf(f, "delta", "echo", "foxtrot")
    l3 := name_leaf(f, "golf", "hotel", "india")
    l4 := name_leaf(f, "juliet", "kilo", "lima")
    b1 := inner(f, "alpha", "foxtrot", l1, l2)
    b2 := inner(f, "golf", "lima", l3, l4)
    return dict(f, kv("Kids", arr(f, b1, b2)))
}

@(private = "file")
TREE_KEYS := []string{
    "alpha", "bravo", "charlie", "delta", "echo", "foxtrot",
    "golf", "hotel", "india", "juliet", "kilo", "lima",
}

@(test)
test_name_tree_lookup :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    root := build_name_tree(&f)
    for k in TREE_KEYS {
        got := name_tree_lookup(nil, root, transmute([]byte)k)
        want := fmt.aprintf("v%s", k, allocator = f.alloc)
        if !name_is(got, want) {
            testing.expectf(t, false, "name_tree_lookup(%q): got %v, want /%s", k, got, want)
        }
    }
}

@(test)
test_name_tree_misses :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    root := build_name_tree(&f)
    misses := []string{
        "",             // before everything
        "aardvark",     // below the first limit
        "bravado",      // inside a leaf's range, not present
        "foxtrot2",     // between two branches
        "zulu",         // above the last limit
        "ALPHA",        // byte order is case sensitive
        "alph",         // a prefix of a key is not the key
        "alphabet",     // a key with more after it is not the key
    }
    for k in misses {
        got := name_tree_lookup(nil, root, transmute([]byte)k)
        if got != nil {
            testing.expectf(t, false, "name_tree_lookup(%q): got %v, want null", k, got)
        }
    }
}

@(test)
test_name_tree_edge_nodes :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    // A nil root, an empty dictionary, and a root that is itself a leaf.
    testing.expect(t, name_tree_lookup(nil, nil, transmute([]byte)string("x")) == nil)

    empty := dict(&f)
    testing.expect(t, name_tree_lookup(nil, empty, transmute([]byte)string("x")) == nil)

    flat := dict(&f, kv("Names", arr(&f, str("only"), i64(42))))
    n, ok := to_int(name_tree_lookup(nil, flat, transmute([]byte)string("only")))
    testing.expect(t, ok)
    testing.expect_value(t, n, 42)

    // An odd-length /Names array: the dangling key has no value, and reading
    // one must not run off the end of the array.
    ragged := dict(&f, kv("Names", arr(&f, str("a"), i64(1), str("b"))))
    testing.expect(t, name_tree_lookup(nil, ragged, transmute([]byte)string("b")) == nil)
    got, _ := to_int(name_tree_lookup(nil, ragged, transmute([]byte)string("a")))
    testing.expect_value(t, got, 1)

    // /Names of the wrong type altogether.
    wrong := dict(&f, kv("Names", i64(3)), kv("Kids", str("nope")))
    testing.expect(t, name_tree_lookup(nil, wrong, transmute([]byte)string("a")) == nil)
}

@(test)
test_name_tree_unsorted_leaf :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    // A /Names array in the wrong order, and one whose keys are not all
    // strings. A binary search misses both; the linear fallback finds them.
    unsorted := dict(&f, kv("Names", arr(&f,
        str("zulu"), i64(1), str("alpha"), i64(2), str("mike"), i64(3))))
    Want :: struct {
        key:   string,
        value: i64,
    }
    wants := []Want{{"zulu", 1}, {"alpha", 2}, {"mike", 3}}
    for w in wants {
        v, ok := to_int(name_tree_lookup(nil, unsorted, transmute([]byte)w.key))
        testing.expect(t, ok)
        testing.expect_value(t, v, w.value)
    }

    typed := dict(&f, kv("Names", arr(&f,
        Name("notastring"), i64(1), str("real"), i64(2))))
    v, ok := to_int(name_tree_lookup(nil, typed, transmute([]byte)string("real")))
    testing.expect(t, ok)
    testing.expect_value(t, v, 2)
}

@(test)
test_name_tree_cycle_terminates :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    // A node whose only kid is itself.
    self := dict(&f)
    dict_set(self, "Kids", arr(&f, self))
    testing.expect(t, name_tree_lookup(nil, self, transmute([]byte)string("x")) == nil)

    // A two-node cycle with a real leaf hanging off it: the lookup must still
    // find the key, still answer a miss, and still terminate.
    a := dict(&f)
    b := dict(&f)
    leaf := dict(&f, kv("Names", arr(&f, str("found"), i64(9))))
    dict_set(a, "Kids", arr(&f, b, leaf))
    dict_set(b, "Kids", arr(&f, a))
    v, ok := to_int(name_tree_lookup(nil, a, transmute([]byte)string("found")))
    testing.expect(t, ok)
    testing.expect_value(t, v, 9)
    testing.expect(t, name_tree_lookup(nil, a, transmute([]byte)string("missing")) == nil)

    keys, values := name_tree_collect(nil, a)
    defer delete(keys)
    defer delete(values)
    testing.expect_value(t, len(keys), 1)
    testing.expect_value(t, len(values), 1)
}

@(test)
test_name_tree_deep_chain :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    // A chain far deeper than MAX_DEPTH with the payload at the bottom. The
    // walk must stop rather than recurse, and must not crash.
    deep := dict(&f, kv("Names", arr(&f, str("bottom"), i64(1))))
    for _ in 0 ..< 200 {
        deep = dict(&f, kv("Kids", arr(&f, deep)))
    }
    testing.expect(t, name_tree_lookup(nil, deep, transmute([]byte)string("bottom")) == nil)

    keys, values := name_tree_collect(nil, deep)
    defer delete(keys)
    defer delete(values)
    testing.expect_value(t, len(keys), 0)
    testing.expect_value(t, len(values), 0)
}

@(test)
test_name_tree_collect :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    root := build_name_tree(&f)
    keys, values := name_tree_collect(nil, root)
    defer delete(keys)
    defer delete(values)

    testing.expect_value(t, len(keys), len(TREE_KEYS))
    testing.expect_value(t, len(values), len(TREE_KEYS))
    for w, i in TREE_KEYS {
        if i >= len(keys) {
            break
        }
        if string(keys[i]) != w {
            testing.expectf(t, false, "collect[%d]: got %q, want %q", i, string(keys[i]), w)
        }
        if !name_is(values[i], fmt.aprintf("v%s", w, allocator = f.alloc)) {
            testing.expectf(t, false, "collect[%d]: value %v", i, values[i])
        }
    }
}

@(test)
test_name_tree_collect_empty :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    keys, values := name_tree_collect(nil, nil)
    testing.expect_value(t, len(keys), 0)
    testing.expect_value(t, len(values), 0)

    keys2, values2 := name_tree_collect(nil, dict(&f))
    testing.expect_value(t, len(keys2), 0)
    testing.expect_value(t, len(values2), 0)
}

// The keys collect returns point into the objects, not at copies.
@(test)
test_name_tree_collect_borrows_keys :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    src := "borrowed"
    root := dict(&f, kv("Names", arr(&f, String(transmute([]byte)src), i64(1))))
    keys, values := name_tree_collect(nil, root)
    defer delete(keys)
    defer delete(values)

    testing.expect_value(t, len(keys), 1)
    testing.expect_value(t, len(values), 1)
    testing.expect(t, raw_data(keys[0]) == raw_data(transmute([]byte)src))
}

@(test)
test_number_tree_lookup :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    // /PageLabels-shaped: three leaves, two of them under a branch.
    l1 := dict(&f,
        kv("Nums", arr(&f, i64(0), Name("a"), i64(4), Name("b"))),
        kv("Limits", arr(&f, i64(0), i64(4))))
    l2 := dict(&f,
        kv("Nums", arr(&f, i64(9), Name("c"), i64(16), Name("d"))),
        kv("Limits", arr(&f, i64(9), i64(16))))
    l3 := dict(&f,
        kv("Nums", arr(&f, i64(100), Name("e"))),
        kv("Limits", arr(&f, i64(100), i64(100))))
    b1 := dict(&f, kv("Kids", arr(&f, l1, l2)), kv("Limits", arr(&f, i64(0), i64(16))))
    root := dict(&f, kv("Kids", arr(&f, b1, l3)))

    Case :: struct {
        key:  i64,
        want: string,   // "" for a miss
    }
    cases := []Case{
        {0, "a"}, {4, "b"}, {9, "c"}, {16, "d"}, {100, "e"},
        {-1, ""}, {1, ""}, {5, ""}, {17, ""}, {99, ""}, {101, ""},
        {max(i64), ""}, {min(i64), ""},
    }
    for c in cases {
        got := number_tree_lookup(nil, root, c.key)
        if c.want == "" {
            if got != nil {
                testing.expectf(t, false, "number_tree_lookup(%d): got %v, want null", c.key, got)
            }
        } else if !name_is(got, c.want) {
            testing.expectf(t, false, "number_tree_lookup(%d): got %v, want /%s", c.key, got, c.want)
        }
    }
}

@(test)
test_number_tree_cycle_and_collect :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    a := dict(&f)
    leaf := dict(&f, kv("Nums", arr(&f, i64(3), Name("x"), i64(7), Name("y"))))
    dict_set(a, "Kids", arr(&f, a, leaf))
    testing.expect(t, name_is(number_tree_lookup(nil, a, 7), "y"))
    testing.expect(t, number_tree_lookup(nil, a, 8) == nil)

    keys, values := number_tree_collect(nil, a)
    defer delete(keys)
    defer delete(values)
    testing.expect_value(t, len(keys), 2)
    testing.expect_value(t, keys[0], i64(3))
    testing.expect_value(t, keys[1], i64(7))
    testing.expect(t, name_is(values[1], "y"))
}

// A /Limits entry of the wrong type, or with too few elements, is unusable;
// the node below it is searched anyway rather than silently losing its keys.
@(test)
test_tree_bad_limits :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    l1 := dict(&f,
        kv("Names", arr(&f, str("key"), i64(1))),
        kv("Limits", arr(&f, i64(0), i64(9))))
    l2 := dict(&f,
        kv("Names", arr(&f, str("other"), i64(2))),
        kv("Limits", arr(&f, str("other"))))
    root := dict(&f, kv("Kids", arr(&f, l1, l2)))

    v1, ok1 := to_int(name_tree_lookup(nil, root, transmute([]byte)string("key")))
    testing.expect(t, ok1)
    testing.expect_value(t, v1, 1)
    v2, ok2 := to_int(name_tree_lookup(nil, root, transmute([]byte)string("other")))
    testing.expect(t, ok2)
    testing.expect_value(t, v2, 2)
}

// A /Kids array holding things that are not dictionaries.
@(test)
test_tree_junk_kids :: proc(t: ^testing.T) {
    f: Fixture
    fixture_init(&f)
    defer fixture_destroy(&f)

    leaf := dict(&f, kv("Names", arr(&f, str("k"), i64(5))))
    root := dict(&f, kv("Kids", arr(&f, i64(1), Name("no"), nil, str("no"), leaf)))
    v, ok := to_int(name_tree_lookup(nil, root, transmute([]byte)string("k")))
    testing.expect(t, ok)
    testing.expect_value(t, v, 5)

    keys, values := name_tree_collect(nil, root)
    defer delete(keys)
    defer delete(values)
    testing.expect_value(t, len(keys), 1)
    testing.expect_value(t, len(values), 1)
}

// ---------------------------------------------------------------------------
// Fuzz-shaped
//
// The bytes reaching these two procedures came out of a file, so the property
// that matters is not "correct" but "never wrong in a way that hurts": the
// text always UTF-8, the date always in range, neither ever hanging.
// ---------------------------------------------------------------------------

@(private = "file")
fuzz_next :: proc(state: ^u64) -> u64 {
    x := state^
    x ~= x << 13
    x ~= x >> 7
    x ~= x << 17
    state^ = x
    return x
}

@(test)
test_text_string_output_is_always_utf8 :: proc(t: ^testing.T) {
    state: u64 = 0x2545F4914F6CDD1D
    buf: [40]byte
    marks := [][]byte{{}, {0xFE, 0xFF}, {0xFF, 0xFE}, {0xEF, 0xBB, 0xBF}}
    for _ in 0 ..< 6000 {
        n := int(fuzz_next(&state) % u64(len(buf) + 1))
        for i in 0 ..< n {
            buf[i] = byte(fuzz_next(&state))
        }
        // Steer a quarter of the cases onto each decoder rather than leaving
        // it to chance, which would almost always pick PDFDocEncoding.
        mark := marks[fuzz_next(&state) % u64(len(marks))]
        if n >= len(mark) {
            copy(buf[:], mark)
        }
        got := decode_text_string(buf[:n])
        defer delete(got)
        if !utf8.valid_string(got) {
            testing.expectf(t, false, "invalid UTF-8 out of %x: %x", buf[:n], transmute([]byte)got)
            return
        }
    }
}

@(test)
test_parse_date_output_is_always_in_range :: proc(t: ^testing.T) {
    state: u64 = 0x9E3779B97F4A7C15
    buf: [24]byte
    alphabet := "0123456789D:+-Z' \x00zx"
    for _ in 0 ..< 6000 {
        n := int(fuzz_next(&state) % u64(len(buf) + 1))
        for i in 0 ..< n {
            buf[i] = alphabet[fuzz_next(&state) % u64(len(alphabet))]
        }
        d, ok := parse_date(buf[:n])
        if !ok {
            continue
        }
        in_range :=
            d.year >= 0 && d.year <= 9999 &&
            d.month >= 1 && d.month <= 12 &&
            d.day >= 1 && d.day <= date_days_in_month(d.year, d.month) &&
            d.hour >= 0 && d.hour <= 23 &&
            d.minute >= 0 && d.minute <= 59 &&
            d.second >= 0 && d.second <= 59 &&
            d.tz_hour >= -23 && d.tz_hour <= 23 &&
            d.tz_minute >= -59 && d.tz_minute <= 59
        if !in_range {
            testing.expectf(t, false, "out of range date %v from %q", d, string(buf[:n]))
            return
        }
    }
}