Goose

Serialization of relative-reference structures: a verified loader

Implemented. This document describes the serialization guarantees, the loader's validation rules, and how the implementation preserves §9's safety guarantees.

1. Serialization guarantees

A structure whose links are all self-relative references (§3.9) is position-independent: a tree of Node { v: i32, l: Node&<u32>?, r: Node&<u32>? } in a Node[>..], or a Sexp..[>..] pool, is a contiguous sequence of bytes whose links remain valid when the sequence is relocated. bench/design.md counts "Goose data is already its own serialized form" among the design's advantages: saving is a write of the element region, loading is a read of it, and there is no pointer fixup pass because there are no pointers.

Three builtins (§12) express that. samples/25_serialize.goose is the worked example; test/storage/serialize.goose is the coverage.

2. Why loading requires validation

from_bytes<T[>..]>(bytes) that reinterpreted the bytes would be the first operation in the language that can produce a reference the checker did not prove valid: a corrupted or malicious offset is an address anywhere in memory, which breaks the first priority of §9.1 outright. Every other unsafety Goose admits is type-safe reuse (§9.4); this one is not. The loader must therefore validate the bytes before accepting them as a value, as a FlatBuffers verifier does.

What is verified is safety, not integrity. An image whose data bytes were edited still describes a well-formed structure and is accepted with the wrong numbers in it; a checksum, not the verifier, is what says the file is the one that was written. Nor does anything say the file came from this program: the type is not in the image, which is a container format's job and not the language's.

3. The image

uleb128(payload byte count)  payload = the array's element region

The prefix is what lets a reader of a stream or a long file size its read before it has the whole image; it is the ULEB128 of §3.6, and format_uleb / parse_uleb in stdlib/std.goose are the same encoding for a program that wants to write or read it itself. from_bytes requires the prefix to account for exactly the rest of the slice, so truncation and extension are both caught before the walk starts.

The payload is little-endian by construction: the layouts of C.2 are, and every target this compiles for is. That is now a stated requirement rather than an accident — to_bytes, bytes_of and from_bytes each test the host and abort (GS_E_ENDIAN) on a big-endian one, which is a folded constant on every real target. A big-endian port would have to either prove an image never leaves the program or emit byte-swapping variants.

4. What must be verified

For a candidate payload of T[...]:

  1. Framing. The payload parses as a sequence of T values: for fixed T the byte length is a multiple of sizeof(T); for variable T a sequential walk of the elements (the same walk print and == use) ends exactly at the payload's end, every varint terminates, every tag is in range, every nested length fits what is left.
  2. Element starts. The walk yields the set of element start offsets, and for variable-mode ADTs the tag at each start.
  3. Links. For every self-relative reference field at absolute offset f with stored offset o: o == 0 is null and legal only where the field is optional; otherwise f + o is an element start. A reference typed at a variant addresses that variant's payload, so what must be an element start is f + o − sizeof(tag), and the tag there must be that variant's. A reference whose pointee type is neither the element type nor a variant of it — an i64&<u16> into a field of an element — would need every valid address of that type enumerated; v1 rejects such element types for from_bytes, at the call, by name (see §7).
  4. Excluded types. Plain references and slices (they are addresses) and in pool references (they mean an offset into a named global pool, not into the image) are rejected for all three builtins. Resizable fields cannot be array elements in the first place.

Everything §3.9 already guarantees about a self-relative structure built by the program — both ends in one root array — is exactly what step 3 checks for one arriving from outside. A verified image is then indistinguishable from a constructed one, and the ordinary rules apply to it from then on: the result is rooted at its own variable, it grows, and relative stores into it are checked like any other.

A reusable pool (§5.4) writes and loads like any other array. Its freelist is separate state that no image carries, so a loaded pool starts with an empty freelist and all slots live, consistent with §5.4.

5. The builtins

fn to_bytes(a) -> u8[>..]                            // the image, as a fresh value
fn to_bytes(a, out: u8[>..]&)                        // the image, appended to a builder
fn bytes_of(a) -> u8[:]                              // the payload alone, as a view
fn from_bytes<T[>..]>(bytes: u8[:]) -> T[>..], bool  // a verified copy, or [] and false

All three are safe for any array or slice whose element type contains no plain references, slices or in pool references (a static check), and are spelled either way per UFCS: a.to_bytes() or to_bytes(a[1..]).

to_bytes copies. The two-argument form appends to a growable u8 array the caller owns — resizable or limited — so a message or file header can go in front of the image without a second copy, and the one-argument form builds a fresh u8[>..] at its destination like any other result (§7.3).

bytes_of copies nothing: it is a u8[:] over the element region, rooted at the array exactly as a slice of it would be, so §5.1 and §5.2 keep the array from shrinking under it and §9 keeps it from outliving it. It is never writable, whatever the array's own provenance: writing through it could create relative references that the checker had not validated. Its length is what the framing prefix would have said, so a save that writes its own header (format_uleb) and then the payload produces a file from_bytes reads back, with no image ever built in memory.

from_bytes checks the prefix, runs the verifier over the payload, then copies it into the result's element region; the count the verifier returns becomes the result's length. Its result is a fresh array rooted at its own variable, exactly as if the program had pushed the elements itself, so it needs no new rule in §9. It builds any array kind whose contents are an element run plus a count — T[>..], T[>..<], and the T[] family, whose count goes into the destination's own length prefix. A fixed or limited array would additionally need the count to match a capacity the image does not carry, so those are rejected.

The bool is the verifier's verdict; on failure the array is empty. It may be dropped (var a = from_bytes<T>(b);), when the caller accepts an empty array as the result of invalid input.

Both are ordinary builtins with custom typechecking (like default<T>()); from_bytes needs its explicit type argument (§7.7).

The pair round-trips: from_bytes<T[>..]>(a.to_bytes()) is a, for every element type from_bytes accepts.

6. Generating the verifier per type

The verifier is generated per element type, like the equality and size functions codegen already emits (gs_size_T, EmitEqWalk): gs_verify_T(const uint8_t *p, int64_t n, uint8_t *bm) -> int64_t returns the element count, or −1. It is EmitVerifyWalk in codegen_types.h, a case per type kind driven by the layout (Layout, C.2), recursing into struct fields and variant payloads, with a check per relative-reference field — about 250 lines of codegen rather than a new subsystem.

The limited-array case is the one worth calling out: slots past the stored length were never written (§5.3), so the walk checks the links in the live slots only, and then skips the cursor over the whole capacity.

The bitmap ceiling. One bit per payload byte, on one data stack, so the largest verifiable image of variable elements is eight times a stack's reservation — 16 GB at the default GS_STACK_RESERVE of 2 GB, and it moves with that constant. A payload past it is rejected (false) rather than growing into the guard region, which would be an abort. Fixed-element images have no such limit, since they need no scratch. The alternative — an array of element offsets and a binary search per link — has no ceiling but costs 8 bytes per element instead of one bit per byte, which is worse for every element under 64 bytes and turns an O(1) test into an O(log n) one.

7. Open points