Saving and Loading Bytes

A structure built from self-relative links means the same thing wherever its bytes are. Chapter 13 pointed that out in passing. This chapter cashes it in: saving such a structure is writing its bytes, and loading it is reading them back, with no serializer, no schema and no fixing up of pointers. The interesting part is the loading, because bytes from outside the program are the one place where the compiler cannot vouch for the references inside them.

#Three built-ins21.1

Here is the binary tree of geese from Chapter 13 saved to a file and loaded back:

import os;

struct Node { name: u8[..8], weight: i32, left: Node&<u32>?, right: Node&<u32>? }

fn insert(tree: Node[>..]&, name: u8[:], weight: i32) {
    if tree.len == 0 { tree.push(Node { name: name, weight: weight }); return; }
    var cur .= tree[0];
    loop {
        if weight < cur.weight {
            let l = cur.left;
            if l { cur .= l; continue; }
            cur.left .= tree.push(Node { name: name, weight: weight });
            return;
        }
        let r = cur.right;
        if r { cur .= r; continue; }
        cur.right .= tree.push(Node { name: name, weight: weight });
        return;
    }
}

fn lightest(tree: Node[>..]&) -> u8[:] {
    var cur .= tree[0];
    loop {
        let l = cur.left;
        guard l else { break; }
        cur .= l;
    }
    return cur.name[..];
}

fn main() {
    var tree: Node[>..] = [];
    insert(tree, "Ada", 45);
    insert(tree, "Bea", 52);
    insert(tree, "Cleo", 38);
    insert(tree, "Dot", 41);
    let image = tree.to_bytes();
    print(image.len, " bytes, ", bytes_of(tree).len, " of them nodes");
    write_file("flock.bin", image);

    var disk: u8[>..] = [];
    read_file("flock.bin", disk);
    var loaded, ok = from_bytes<Node[>..]>(disk);
    print(ok, ", ", loaded.len, " nodes, the lightest is ", lightest(loaded));
    insert(loaded, "Eve", 30);
    print("after one more insert: ", lightest(loaded));
    delete_file("flock.bin");
}

85 bytes, 84 of them nodes
true, 4 nodes, the lightest is Cleo
after one more insert: Eve

The image is the 84 bytes of the four nodes exactly as they sit in memory, preceded by a one-byte length. Loading copied the bytes into a new grow-only array, and that array is an ordinary one. You can walk it, index it, and keep inserting into it, as the last line does.

#Verification21.2

from_bytes is where safety could break down. Everywhere else, the compiler has proved every reference valid before the program ran. But a file can contain anything: random bytes, a file from an older version, or bytes deliberately crafted to point somewhere they should not.

So from_bytes checks the image before it becomes a value. It checks the framing, every enum tag, every length, that every varint is in its canonical form, and that every link lands exactly on the start of an element in the same image. If anything is wrong, you get false and an empty array, never a wild reference:

struct Node { name: u8[..8], weight: i32, left: Node&<u32>?, right: Node&<u32>? }

fn main() {
    var tree: Node[>..] = [Node { name: "Ada", weight: 45 }];
    let b .= tree.push(Node { name: "Bea", weight: 52 });
    tree[0].right .= b;
    var image = tree.to_bytes();
    var good, ok = from_bytes<Node[>..]>(image);
    image[image.len - 4] = 99;                 // corrupt a link
    var bad, bad_ok = from_bytes<Node[>..]>(image);
    print(ok, " ", good.len, ", then ", bad_ok, " ", bad.len);
}

true 2, then false 0

What the check guarantees is safety, not integrity. A file whose name bytes were edited still describes a perfectly well-formed tree, and loads fine. If you need to know that a file is the one you wrote, add a checksum.

#Variable-size records21.3

Images work for any array, including the variable-size records from Chapter 10. The image of a diary of entries with inline notes is just the diary's bytes:

struct Entry { day: varint, note: u8[varint] }

fn main() {
    var diary: Entry[>..] = [];
    diary.push(Entry { day: 1, note: "first egg" });
    diary.push(Entry { day: 3, note: "two eggs" });
    let image = diary.to_bytes();
    var back, ok = from_bytes<Entry[>..]>(image);
    print(ok, ", ", image.len, " bytes: ", back);
}

true, 22 bytes: [Entry { 1, "first egg" }, Entry { 3, "two eggs" }]

#What cannot be saved21.4

A link measured from a named global pool, T&<u32 in pool>, depends on the pool, which is not part of the image, so an array holding such links cannot be written out:

struct Goose { name: u8[..8], mate: Goose&<u16 in flock>? }

var flock: Goose[>..] = [];

fn main() {
    flock.push(Goose { name: "Ada", .. });
    print(bytes_of(flock).len);
}

error: bytes_of cannot write Goose[>..] out: Goose&<u16 in flock>? is measured from flock, not from the image

Plain references and slices cannot be saved either, for the same reason. Use self-relative links for data that will be saved.

#Writing without copying21.5

to_bytes builds a new array holding the image. When the data is large, you can avoid that copy: write a length prefix with format_uleb from std, then append the bytes_of view straight to the file:

import std;
import os;

fn main() {
    var weights: i32[>..] = [];
    for i in 1000 { weights.push(i as i32); }
    var head: u8[>..] = [];
    format_uleb(head, bytes_of(weights).len);
    write_file("weights.bin", head);
    append_file("weights.bin", bytes_of(weights));
    var disk: u8[>..] = [];
    read_file("weights.bin", disk);
    var back, ok = from_bytes<i32[>..]>(disk);
    print(ok, " ", back.len, " ", back[999], " ", disk.len, " bytes on disk");
    delete_file("weights.bin");
}

true 1000 999 4002 bytes on disk

#Exercises21.6

1. Save the diary above to a file with write_file_atomic, load it back, and add a third entry to the loaded copy.

2. Take the image of a u8[][>..] holding three words and print every byte of it. Can you see where each word's length is stored?

3. Write a function that loads an image of geese and returns either the array or an error message, using a trailing bool. What should it return for an empty file?