# Graven: complete documentation

> Graven is an open specification for a zero-copy binary serialization format and its schema language (.graven), with a compiler (gravenc), lockfiles that refuse incompatible schema changes, frozen conformance vectors and a reference implementation in Rust.


---

<!-- source: docs/for-ai.md -->

# For AI assistants

This page is written for language models and the people who work with them. It is a
compact, self-contained guide to writing Graven schemas and using the tools correctly.
Linked pages have the details.

Two plain-text files are published with the site for tools that load documentation
directly:

- [`/llms.txt`](../llms.txt) is a short index in the [llms.txt](https://llmstxt.org)
  format: a summary of Graven, then links to every page as Markdown, starting with this guide.
- [`/llms-full.txt`](../llms-full.txt) has the whole documentation, specification included,
  in one file.

Every documentation page is also published as Markdown next to its HTML: replace `.html`
with `.md` in the address.

## What Graven is

Graven is a zero-copy binary serialization format with a schema language. A `.graven`
schema describes messages. The compiler `gravenc` checks it, records its layout in a
lockfile (`<schema>.graven.lock`) and generates code. Messages are read in place from the
buffer, with no parse step. The format (v1) is frozen and specified, with 42 conformance
vectors. The reference implementation is in Rust. Source: <https://github.com/lpj145/graven>.

Use it for data that is stored or exchanged for a long time and must stay readable as the
schema evolves: records, logs, messages between services. Prefer JSON for small,
human-edited configuration.

## Schema cheat sheet

```graven
namespace shop;                         // one per file; part of every schema id

import common;                          // another file's namespace; use as common.Money

/// Doc comments (///) go into the generated code.
enum Status : u8 { Draft = 0, Active = 1, Archived = 2 }   // base: u8, u16 or u32

struct Point { x: i32, y: i32 }         // inline and frozen: can never change

table Product {
  sku    @0: string;                    // required
  name   @1: string;
  price  @2: common.Money;              // imported struct
  status @3: Status = Active;           // default: absent reads Active
  tags   @4: [string]?;                 // optional list
  stock  @5: u32?;                      // optional scalar: absent ≠ 0
  @6: reserved u64;                     // a removed field: ID and slot kept forever
}

table Catalog {
  products @0: [Product];               // a list of tables
}

table Card { last4 @0: u16; }
table Pix  { key @0: string; }
union Method { Card @1: Card, Pix @2: Pix }   // variants are tables, tags > 0
```

Types: `u8`–`u128`, `i8`–`i128`, `f32`, `f64`, `bool`, `string` (UTF-8), `bytes`, `[T]`,
enums, structs, tables and unions. Field forms: `x @N: T;` (required), `x @N: T?;`
(optional), `x @N: T = literal;` (default, only for scalars, `bool` and enums),
`@N: reserved [T];`.

## Rules to follow

Write schemas that `gravenc` accepts the first time:

1. Field IDs in a table are contiguous from `@0`, with no gaps or repeats. Layout follows ID
   order, not text order.
2. Never renumber, reuse or delete an ID. A field that is no longer used becomes
   `@N: reserved;`.
3. Never change a field's type, an enum's base, a struct, or a default value. These
   are refused.
4. A new field in an existing table must be optional or have a default. A new required
   field is refused (`new-required`).
5. Making a required field optional or reserved breaks deployed readers. The compiler asks
   for `#[allow_breaking_readers]` on that field. Add the attribute only when the user
   explicitly accepts the break.
6. An incompatible change is a new type (`OrderV2`), not a new namespace or version
   suffix on the namespace.
7. `?` and `=` cannot be combined. Defaults are only for scalars, `bool` and enums
   (enums by variant name).
8. No lists of lists (`[[T]]`), no lists of unions, no struct that contains itself.
   Recursion is allowed only through tables.
9. Union variants are tables, with unique tags greater than 0. Tag 0 means "no value".
10. One namespace per file, and two files cannot share one. Imported types are always
    qualified by the last segment of their namespace (`common.Uuid`), or by an alias
    (`import acme.common as ac;`).
11. Validation rules (`range`, `len`, `finite`, `known`, `check(name)`) live on table fields
    (or `check(name)` on a `table`), never on structs. Reading (`from_bytes`) never runs
    them implicitly; call `view.validate(&checks)` or `XW::to_bytes_validated(&mut b, &checks, ...)`.
    Tightening or adding rules triggers `rule-tightened` / `check-added` warnings
    (confirmed with `#[allow_breaking_readers]`).

Renaming a field, adding an enum variant, adding a union variant and adding a table are
all allowed.

Full grammar and rules: [schema language](graven-language.md). Normative compatibility
rules: [specification §9](spec/graven-format-v1.md#9-schema-compatibility).

## Commands

```sh
gravenc update schema.graven --init        # first lockfile of a new schema
gravenc update schema.graven               # after a change: check compatibility, rewrite the lock
gravenc check --locked schemas/*.graven    # CI: fail if a lock is missing or out of date
gravenc from-json schema.graven --root Product in.json -o out.bin
gravenc to-json schema.graven out.bin      # one JSON document per message
gravenc inspect schema.graven out.bin      # decode and verify, with offsets
gravenc diff schema.graven                 # every change against the lock, with its verdict
gravenc scan log.bin --schema schema.graven   # find damaged or truncated records
```

Only `gravenc update` writes the lockfile. `build.rs` reads it and fails if it is missing
or out of date. Always commit the lockfile with the schema. Details: [tools](tools.md).

## Using it from Rust

Install the compiler with `cargo install graven-compiler`, and add to
`Cargo.toml`:

```toml
[dependencies]
graven = "0.2"

[build-dependencies]
graven-compiler = "0.2"
```

`build.rs`:

```rust
fn main() {
    graven_compiler::build::Build::new()
        .schema("schemas/common.graven")   // every file an import needs
        .schema("schemas/shop.graven")
        .compile()
        .unwrap_or_else(|e| panic!("{e}"));
}
```

Include each generated file alone in its own module:

```rust
pub mod common {
    include!(concat!(env!("OUT_DIR"), "/common.rs"));
}
pub mod shop {
    include!(concat!(env!("OUT_DIR"), "/shop.rs"));
}
```

Write and read an enveloped message:

```rust
use graven::{Builder, SimplePool};
use shop::{Catalog, CatalogW};

fn main() -> Result<(), graven::Error> {
    let pool = SimplePool::new(4096);
    let mut b = Builder::new_enveloped(&pool);
    let bytes = CatalogW::to_bytes(&mut b, |c| {
        let mut products = c.products(1);       // a list with a known length
        products
            .push()
            .sku("CF-01")
            .name("Coffee")
            .price(common::Money { cents: 8990, currency: 986 })
            .stock(120);
    })?;

    let catalog = Catalog::from_bytes(&bytes)?; // checks the envelope and verifies
    for p in catalog.products()?.iter() {
        let p = p?;
        println!("{} {:?}", p.sku()?, p.stock());
    }
    Ok(())
}
```

The generated API for a table `X`:
- `X::read(buf)` is a checked reader.
- `X::verified(buf)` verifies a bare message and returns a verified view.
- `X::from_bytes(buf)` does the same for an enveloped message, after checking its schema
  id and CRC.
- `XW` is the writer, with chainable setters, `XW::to_bytes` and `XW::seal`.
- Required scalars return the value, optional fields return an `Option`, and strings,
  lists and nested tables return a `Result`.

Details: [generated API](graven-language.md#11-generated-api-summary).

## JSON mapping

The tools and JSON conversion use this mapping:
- Integers are numbers. `u128`/`i128` values outside 64 bits are decimal strings.
- Floats are numbers, or `"NaN"`, `"inf"` and `"-inf"`.
- An enum is its variant name, or a number for an unknown value.
- `bytes` are a lowercase hex string.
- A union is `{"Variant": {…}}`.
- An absent optional field is left out. `null` on input means absent.

Translating JSON data into a schema: [coming from JSON](coming-from-json.md).

## Mistakes to avoid

- **Deleting a field or renumbering IDs to "clean up".** Reserve the field instead.
- **Treating `0` or `""` as absent.** Graven stores presence explicitly. Use `T?` when
  "not sent" is a distinct state.
- **Using `f64` for money.** Use an integer of minor units and a currency code.
- **Using a struct for something that may gain fields.** Structs are frozen; use a table.
- **Editing the lockfile by hand,** or regenerating it with `--init` to get past an error.
  That throws away the history that protects old data. Fix the schema instead.
- **Decoding untrusted bytes without verification.** Use `from_bytes` or `verified`.
- **Wrapping every record of a log in one big list.** Write one enveloped message per
  record. Wrap a list in a table only when it is read and written as a unit.

More: [good practice](good-practice.md).


---

<!-- source: docs/getting-started.md -->

# Getting started

Graven schemas (`.graven`) are language-neutral. The `gravenc` compiler validates schemas,
tracks compatibility in `<schema>.lock`, inspects binary files, and generates code.

## 1. Install `gravenc`

```sh
cargo install graven-compiler
```

*(Or from a source checkout: `cargo build --release -p graven-compiler --bin gravenc`.)*

## 2. Write a schema and create its lockfile

Create `schemas/bank.graven`:

```graven
namespace bank;

enum Currency : u16 { BRL = 0, USD = 1, EUR = 2 }

table Entry {
  account @0: u64;
  amount  @1: i64;
  memo    @2: string?;
}

table Transaction {
  id         @0: u64;
  ts         @1: u64;
  currency   @2: Currency;
  from_shard @3: u32;
  to_shard   @4: u32;
  entries    @5: [Entry];
  note       @6: string?;
}
```

Initialize its lockfile once:

```sh
gravenc update schemas/bank.graven --init
```

The lockfile (`schemas/bank.graven.lock`) records every table's `schema_id`, fixed-part
layout, defaults, and validation rules. Commit it alongside your `.graven` files.

## 3. Evolve, check, and generate

- **Check in CI:** `gravenc check --locked schemas/*.graven`
- **Update after changes:** `gravenc update schemas/bank.graven` (refuses breaking changes)
- **Generate code from the CLI:** `gravenc gen schemas/bank.graven -o generated/`
- **Inspect / convert binary data:** `gravenc inspect`, `gravenc to-json`, `gravenc from-json`

Because `<schema>.lock` records the resolved layout and `schema_id`s, generators for other
languages can target the lockfile directly without reimplementing the layout rules.

## Option: Rust project (`Cargo.toml` + `build.rs`)

If you are using Rust, you can run code generation automatically during `cargo build`
instead of invoking `gravenc gen` manually:

1. Install the compiler: `cargo install graven-compiler` (provides `gravenc`).
   Add the runtime and the code generator to your crate's `Cargo.toml`:

   ```toml
   [dependencies]
   graven = "0.2"

   [build-dependencies]
   graven-compiler = "0.2"
   ```

2. Write `schemas/bank.graven` and create its lockfile once: `gravenc update schemas/bank.graven --init`.
3. Generate code from `build.rs` (it reads the lock and never writes it):

   ```rust
   fn main() {
       graven_compiler::build::Build::new()
           .schema("schemas/bank.graven")
           .compile()
           .unwrap_or_else(|e| panic!("{e}"));
   }
   ```

4. Include the generated file **alone** in its own module:

   ```rust
   pub mod bank {
       include!(concat!(env!("OUT_DIR"), "/bank.rs"));
   }
   ```

5. When the schema changes, run `gravenc update schemas/bank.graven`: it checks compatibility
   against the lock before rewriting it. In CI, `gravenc check --locked schemas/*.graven`.

## Next steps

- [Coming from JSON](coming-from-json.md) — translate existing JSON data into a Graven schema.
- [Schema language](graven-language.md) — grammar, evolution rules, and the generated API.
- [Validation](validation.md) — built-in rules (`range`, `len`, `finite`, `known`) and custom `check(name)` hooks.
- [Tools](tools.md) — `diff`, `inspect`, `to-json`, `from-json`, `scan`, and editor support.


---

<!-- source: docs/coming-from-json.md -->

# Coming from JSON

If your data is JSON today, you already know its shape. This page translates that shape
into a Graven schema, piece by piece, using a small product catalog. Every command and
output below is real.

## The data

A catalog as most APIs would send it: an object with a list of products.

```json
{
  "products": [
    { "sku": "CF-01", "name": "Coffee beans 1kg", "price": { "cents": 8990, "currency": 986 },
      "tags": ["coffee", "beans"], "stock": 120 },
    { "sku": "MG-02", "name": "Ceramic mug", "price": { "cents": 3500, "currency": 986 },
      "status": "Draft" }
  ],
  "updated_at": 1700000000
}
```

## The schema

```graven
namespace shop;

enum Status : u8 { Draft = 0, Active = 1, Archived = 2 }

struct Money { cents: i64, currency: u16 }

table Product {
  sku    @0: string;
  name   @1: string;
  price  @2: Money;
  status @3: Status = Active;
  tags   @4: [string]?;
  stock  @5: u32?;
}

table Catalog {
  products   @0: [Product];
  updated_at @1: u64?;
}
```

Each decision, against the JSON it came from:

- **`Product` and `Catalog` are tables.** A JSON object whose keys you know becomes a
  table. Every field gets an ID (`@0`, `@1`, …); new fields are added later with new IDs at
  the end, and old readers keep working.
- **`price` is a struct.** `cents` and `currency` always travel together and will never
  change, so they are stored inline, side by side, with no per-field overhead. Use a
  struct only for groups like this; anything that may grow is a table.
- **`price.cents` is an integer.** JSON has one number type; here you choose. Money is an
  integer number of cents, never a float.
- **`status` is an enum with a default.** A fixed set of strings becomes an enum: one byte
  instead of a string. The first product has no `status` in the JSON, so it reads as the
  default, `Active`.
- **`tags` and `stock` are optional (`?`).** In JSON these keys are sometimes missing. In
  Graven, absent is recorded on the wire, so a stock of `0` is different from no stock.
- **`sku` and `name` are required.** A reader rejects a message without them.

## JSON concepts and their Graven counterparts

| In JSON | In Graven | Notes |
|---|---|---|
| object with known keys | `table` | fields have IDs; add new ones at the end |
| small group of values that never changes | `struct` | stored inline, frozen forever |
| array | `[T]` | lists of scalars, enums, structs, strings, bytes or tables |
| string | `string` | UTF-8, validated by `verify` |
| base64 or binary data | `bytes` | raw bytes, no encoding overhead |
| number | `u8` … `u128`, `i8` … `i128`, `f32`, `f64` | pick the range you need; money as integer cents |
| `true` / `false` | `bool` | |
| a fixed set of strings | `enum` | stored as an integer; unknown values survive |
| a key that may be missing, or `null` | optional field `T?` | absent is different from zero or empty |
| a missing key that means a known value | default `T = x` | the default is never written |
| `"type": "..."` choosing between shapes | `union` of tables | an unknown variant is reported, not an error |
| an object used as a map (`{"BRL": 5, "USD": 1}`) | a list of entry tables | `table Rate { code @0: string; value @1: i64; }` and `rates @0: [Rate]` |
| `null` inside an array | not available | lists have no absent elements; use a table with an optional field |

## Converting existing JSON

`gravenc` converts JSON into Graven messages and back, using the schema:

```sh
gravenc update catalog.graven --init        # create the lockfile once
gravenc from-json catalog.graven --root Catalog catalog.json -o catalog.bin
```

```text
catalog.bin: 1 message(s), 185 bytes
```

The minified JSON is 248 bytes; the Graven message is 185, including its 24-byte envelope
with schema id and checksum. To look inside:

```text
$ gravenc inspect catalog.graven catalog.bin
#0  offset 0  shop.Catalog  185 bytes
{
  "products": [
    {
      "sku": "CF-01",
      "name": "Coffee beans 1kg",
      "price": {
        "cents": 8990,
        "currency": 986
      },
      "status": "Active",
      "tags": [
        "coffee",
        "beans"
      ],
      "stock": 120
    },
    {
      "sku": "MG-02",
      "name": "Ceramic mug",
      "price": {
        "cents": 3500,
        "currency": 986
      },
      "status": "Draft"
    }
  ],
  "updated_at": 1700000000
}
```

The first product shows `"status": "Active"`: it was absent, so the reader applies the
default.

## A top-level array

Plenty of JSON is just an array: `[{"sku": "CF-01", …}, {"sku": "MG-02", …}]`. A Graven
message always starts at a table, so there are two ways to store it.

**Wrap it in a table**, as `Catalog` does above. The whole list is one message: choose this
when the list is read and written as a unit, like an API response or a configuration.
[Binary layout](binary-layout.md#lists-of-tables) shows such a list byte by byte.

**Store one message per element.** `from-json` reads a top-level array (or JSON Lines) as
one message per element and writes them one after another, each in its own envelope:

```sh
gravenc from-json catalog.graven --root Product products.json -o products.bin
```

```text
products.bin: 2 message(s), 192 bytes
```

Choose this for collections that grow: logs, events, exports. New records are appended
without rewriting the file, each record is checked on its own, and
[`gravenc scan`](tools.md#scan) tells a crash-truncated tail from real corruption.

```text
$ gravenc to-json catalog.graven products.bin
{"sku":"CF-01","name":"Coffee beans 1kg","price":{"cents":8990,"currency":986},"status":"Active","tags":["coffee","beans"],"stock":120}
{"sku":"MG-02","name":"Ceramic mug","price":{"cents":3500,"currency":986},"status":"Draft"}
```

## The same data from Rust

With the code `gravenc` generates for `catalog.graven` (see
[getting started](getting-started.md)):

```rust
use graven::{Builder, SimplePool};
use shop::{Catalog, CatalogW, Money, Status};

fn main() -> Result<(), graven::Error> {
    let pool = SimplePool::new(4096);
    let mut b = Builder::new_enveloped(&pool);
    let bytes = CatalogW::to_bytes(&mut b, |c| {
        c.updated_at(1_700_000_000);
        let mut products = c.products(2);
        products
            .push()
            .sku("CF-01")
            .name("Coffee beans 1kg")
            .price(Money { cents: 8990, currency: 986 })
            .tags(["coffee", "beans"])
            .stock(120);
        products
            .push()
            .sku("MG-02")
            .name("Ceramic mug")
            .price(Money { cents: 3500, currency: 986 })
            .status(Status::Draft);
    })?;

    let catalog = Catalog::from_bytes(&bytes)?;
    for p in catalog.products()?.iter() {
        let p = p?;
        println!("{} {} {:?} stock={:?}", p.sku()?, p.name()?, p.status(), p.stock());
    }
    Ok(())
}
```

```text
CF-01 Coffee beans 1kg Active stock=Some(120)
MG-02 Ceramic mug Draft stock=None
```

These bytes are identical to the `catalog.bin` that `gravenc from-json` produced from the
JSON: the tools and the generated code follow the same canonical layout.

## What works differently from JSON

- **Names are not in the bytes; IDs are.** Renaming a field is free. Reusing an ID, or
  changing a type, is refused by `gravenc update`.
- **Types are fixed by the schema.** A field cannot be a number in one message and a
  string in the next. Evolution follows the
  [compatibility rules](spec/graven-format-v1.md#9-schema-compatibility).
- **Absent is explicit.** Every field knows whether it was written, so `0`, `""` and
  "not sent" are three different things.
- **Reading is free until you touch a field.** There is no parse step: fields are read in
  place, and one `verify` makes untrusted input safe to read.


---

<!-- source: docs/good-practice.md -->

# Good practice

Advice for designing schemas and using them well. None of it is required by the format. Each
tip gives its reason, so you can tell when it does not apply.

## Designing schemas

### Make a field required only if it can never go away

A required field is a promise to every reader, including ones already deployed. Once it
exists, no writer can stop sending it without breaking those readers: the compiler stops
you with the `required-reserved` or `required-relaxed` warning until you confirm with
`#[allow_breaking_readers]`.

Use required for what defines the record: an id, a timestamp, an amount. Make everything
else optional (`?`) or give it a default.

```graven
table Order {
  id       @0: common.Uuid;     // the record is meaningless without it
  total    @1: common.Money;
  coupon   @2: string?;         // may be dropped some day
  priority @3: u8 = 1;          // absent reads as 1
}
```

### Pick a default only when you will never change it

Changing a default is refused (`default-changed`). Old messages that left the field out
would suddenly read a different value. If the "normal" value may change later, make the
field optional and apply the fallback in your code.

### Never delete a field: reserve it

When a field is no longer used, replace it with `@N: reserved;`. Its ID and its bytes in
the layout stay taken, so a future field can never be misread as the old one. Renaming a
field is free: the name is not on the wire.

### Make incompatible changes as a new type

If a change cannot be made compatibly, declare a new table (`OrderV2`) next to the old one.
It gets its own schema id, the two can coexist, and readers choose which one to accept. Do
not put versions in namespaces.

### Use enums for closed sets of values

A field like `"status": "Active"` stored as a string costs 4 bytes of pointer, 4 of length
and the text. As an enum it costs 1 byte and a presence bit, and a typo cannot get in.

```graven
enum Status : u8 { Draft = 0, Active = 1, Archived = 2 }
```

Readers must handle values they do not know: a newer writer may add a variant, and the
generated code reports it as `Unknown(n)` instead of failing.

### Use structs only for values that will never change

A struct is stored inline, with no pointer and no presence bits per member, which makes it
the most compact way to group fields. In exchange it is frozen: any change is refused
(`struct-changed`). Good structs: coordinates, a UUID, an amount with its currency. If you
can imagine adding a member, use a table.

### Choose integer sizes for the range, not for the typical value

Integers are stored at their full width, with no variable-length encoding, so a `u64`
always takes 8 bytes. Use `u8`/`u16` when the range is truly bounded (a percentage, a port).
Use `u64` for identifiers and counters that grow. Changing a type later is refused
(`type-changed`), so leave room.

### Store money as integers

Use an integer amount of minor units with a currency code, never `f32`/`f64`, which cannot
represent most decimal fractions exactly.

```graven
struct Money { cents: i64, currency: u16 }   // currency: ISO 4217 numeric code
```

### Share common types through imports

Put types used across schemas (`Uuid`, `Money`, `Address`) in one file and
[import](graven-language.md#7-imports) it. Copies in each file drift apart, and nothing
checks that they stay identical.

### Document fields with `///`

[Doc comments](graven-language.md#documentation-comments) are carried into the generated
code. Units, valid ranges and the meaning of an absent field are worth writing down: the
schema outlives the people who wrote it.

## Lists and collections

### Wrap a list that travels as a unit in a table

An API response, a configuration or a snapshot should be one message that holds a list.
The whole list then costs 12 bytes of structure plus about 8 bytes per string element,
with a single envelope if you use one. A top-level JSON array such as
`[{"name": "product_a"}, …]` with 100 elements takes 1712 bytes this way, against 2101 as
compact JSON.

### Store growing collections as one message per record

For logs, events and exports, write one enveloped message per record. Records are appended
without rewriting the file, each one is checked on its own, and
[`gravenc scan`](tools.md#scan) tells a crash-truncated tail from real corruption. The
price is 24 bytes of envelope per record: for 100 tiny records, 4300 bytes against 1712 for
one wrapped list. Do not use this layout for small lists that are always read whole.

### Prefer lists of structs for small fixed records

A `[Point]` stores its elements back to back with no pointers. A list of tables costs a
pointer per string or nested value inside each element, but its elements can evolve. Use
structs for numeric samples, coordinates and similar data that will never gain a field.

### Give the length when you know it

Writing a list whose length you pass up front is faster than writing it as a stream (about
1.4–1.7× in the [benchmarks](benchmarks.md)). Stream only when the length is truly unknown,
for example while reading from an iterator.

## Reading and writing

### Verify untrusted bytes once, then read freely

Bytes from the network, from disk or from another process are untrusted. Open them with
`from_bytes` (enveloped) or `verified` (bare). This walks the message once under fixed
depth and work limits, and gives you a verified view whose reads do not check again.
Plain `read` is also safe on any input, but it checks on every access, so prefer it only
when you read a field or two.

### Read lazily

A message is not decoded up front: reading one field costs about a nanosecond, whatever
the size of the message. Pass the view around and read fields where you need them instead
of copying everything into your own structs.

### Use the envelope at boundaries

Files, queues and network connections between services should carry enveloped messages:
the schema id stops a message being read as the wrong type, and the CRC32C separates a cut
write from corruption. Inside one process, or when a transport already frames and checks
messages and the type is known, a bare message saves 24 bytes and the CRC (about 10 ns on a
small message, about 1.6 µs on 64 KiB).

### Reuse the builder

Keep one `Builder` per thread and reuse it between messages. After warm-up, writing a
message then allocates nothing.

## Process

### Commit the lockfiles and check them in CI

The lockfile is the memory of every layout you have shipped. Commit it next to the
schema, review its diff like code, and run `gravenc check --locked` in CI so that no build
uses a schema the lock has not accepted.

### Change the lock deliberately

Only `gravenc update` writes the lock, and `build.rs` never does. When `update` refuses a
change, read the rule it names before reaching for `#[allow_breaking_readers]`. The
attribute exists for breaks you have planned, not to silence the compiler.


---

<!-- source: docs/spec/graven-format-v1.md -->

# Graven binary format v1 (normative specification)

Status: **frozen**. This document, together with the conformance vectors in
[`testvectors/v1/`](../conformance-vectors.md), defines format v1 for good. Any change
to what is written here is format v2 (a new `format_version` in the envelope).

The behavior described here is the behavior **implemented** by the reference runtime
(`crates/graven`, `crates/graven-layout`) and by the conformance interpreter
(`crates/graven-conformance`). The interpreter walks the schema independently (it decides,
from the schema as data, which fields to read and in which order), but reuses the
runtime primitives (`TableRef`, `VerifyCtx`, `compute_layout`). When this text and a
vector disagree, the vector wins (§10.1).

## 0. Terminology

The key words **MUST**, **MUST NOT**, **SHOULD**, **SHOULD NOT** and **MAY** are to be
interpreted as described in RFC 2119.

- **message**: a sequence of bytes that starts at the root table (no envelope). Also
  called a *buffer*; `len` is its length.
- **envelope**: an optional layer around a message (§8).
- **writer** / **reader**: whoever produces / consumes a message.
- **reader schema**: the schema the reader interprets the message with. It may be older
  or newer than the writer's (§9).
- **absolute position**: byte index from the start of the message (byte 0 = first byte
  of the root's `fixed_len`).
- **fixed-part offset**: byte index from the first byte of a table's fixed part (the
  byte right after `fixed_len`).
- Byte examples are hexadecimal; `[vector: name]` names the vector in `testvectors/v1/`
  that contains exactly those bytes.

The schema used in the examples is `conformance.v1`
(`crates/graven-conformance/schemas/conformance.graven`); its layout is in
[§3.4](#34-example-the-layout-of-conformancev1root).

---

## 1. Scope

This specification defines:

1. the format of a Graven message (tables, fields, variable-size data);
2. the read rules, including what a reader MUST reject and with which error;
3. full verification (`verify`) and its limits;
4. the optional envelope (magic, version, schema id, CRC32C);
5. the compatibility rules between versions of a schema;
6. the conformance criterion.

Out of scope: the full syntax of the `.graven` language (see the
[language guide](../graven-language.md)), the lockfile format, language APIs, on-disk
durability (`fsync`, atomic rename, truncation: those belong to the storage layer), RPC,
compression.

Not in format v1: lists of lists (`[[T]]`) and lists of unions (`[Union]`). A v1 schema
MUST NOT use them and a v1 compiler MUST reject them.

## 2. Conventions

### 2.1 Value encoding

- Every multi-byte quantity is **little-endian**.
- **There is no alignment and no padding.** Fields are packed; a reader MUST accept any
  value at any byte position.
- Integers: unsigned `u8 u16 u32 u64 u128`, two's-complement `i8 i16 i32 i64 i128`;
  1, 2, 4, 8, 16 bytes.
- Floats: `f32` / `f64` are IEEE-754 binary32 / binary64, 4 / 8 bytes. The bit pattern
  is preserved exactly (NaN payloads, `-0.0`); readers MUST NOT normalize.
  [vector: `all_fields` — `a_f32 = 0x3fc00000`, `a_f64 = 0xc0934a456d5cfaad`]
- `bool` has two encodings: 2 bits in a table's fixed part (§4.4), or 1 byte inside
  structs and list elements (§6.3, §5.3).
- Text (`string`) is UTF-8 with no terminator.

### 2.2 Pointers

A **pointer** is an `i32` stored in a 4-byte slot. Its value is relative to the absolute
position of the **first byte of the slot itself**:

```
target = absolute_position_of_slot + value
```

- `value = 0` means **absent** (a pointer never points at its own slot), except in
  `[string]`/`[bytes]` elements, where `0` means empty (§5.6).
- Negative values ("backward" pointers) are valid and MUST be accepted (§5.8).
- The reader MUST compute the target without overflow (for example, in 64 bits) and
  MUST reject a target `< 0` or `>= len` with `BadOffset`.
- A target inside the buffer whose content (length header, data) does not fit before
  `len` MUST be rejected with `OutOfBounds`.

[vector: `bad_offset` — the `name` pointer at position 72 is `2a 00 00 00` (42) and
points to 114, one byte past the end of a 114-byte message ⇒ `BadOffset`]

### 2.3 Maximum size

A message MUST NOT exceed `i32::MAX` (2 147 483 647) bytes; a writer MUST fail with
`TooLarge` instead of producing one. The reference runtime does not reject larger
buffers on read; readers are not required to reject them.

### 2.4 Root

A message starts directly with the root table: the root's `fixed_len` is in bytes
`0..2`. The raw message has no magic and no version (that is the envelope's job, §8). A
buffer shorter than 2 bytes, or whose root fixed part extends past `len`, MUST be
rejected with `OutOfBounds`.

---

## 3. Table

### 3.1 Wire shape

```
[u16 fixed_len][fixed part: fixed_len bytes]
```

- `fixed_len` is the size of the fixed part **according to the writer's schema**. The
  reference writer always writes the full `fixed_len` of its layout (§3.3), including
  reserved fields.
- The header and the whole fixed part MUST fit in the buffer; otherwise `OutOfBounds`.
- A reader whose layout is larger than `fixed_len` treats the fields outside it as
  absent (§4.2); a reader whose layout is smaller ignores the bytes it does not know.
- The fixed part holds **bit bytes** (presence bits) and **slots** (inline values,
  pointers, unions), in the order given by the layout algorithm.
- Tables that are elements of a `[Table]` list **do not** have their own `u16
  fixed_len`: they use the list's `elem_fixed_len` (§5.5).

### 3.2 Field kinds in the fixed part

| field type | kind (`FieldKind`) | slot | bits |
|---|---|---|---|
| `u8..u128`, `i8..i128`, `f32`, `f64` | `Scalar { size }` | `size` bytes | 1 (presence) |
| enum | `Scalar { size }`, `size` = size of the base type | 1, 2 or 4 bytes | 1 |
| struct (inline) | `Scalar { size }`, `size` = size of the struct | `size` bytes | 1 |
| `bool` | `Bool` | none | 2 (presence, value) |
| `string`, `bytes`, `[T]`, table | `Ptr` | 4 bytes (`i32` pointer) | 0 |
| union | `Union` | 6 bytes: `[u16 tag][i32 pointer]` | 0 |

A `reserved` field occupies in the layout exactly what it occupied with its original
type (slot and bits).

### 3.3 Layout algorithm

Fields are processed in **ID order** (`@0, @1, …`, with no gaps; reserved IDs are
included with their original type). The layout MUST be computed exactly by this
algorithm (a faithful copy of `graven_layout::compute_layout`):

```
bits(kind):  Scalar → 1;  Bool → 2;  Ptr, Union → 0
size(kind):  Scalar{size} → size;  Bool → 0;  Ptr → 4;  Union → 6

cursor ← 0                      # next free byte of the fixed part
open   ← none                   # open bit byte: (position, next free shift)
for each field f, in ID order:
    need ← bits(f.kind)
    if need > 0:
        if open = (p, s) and s + need ≤ 8:
            f.presence ← (p, s)
            open ← (p, s + need)
        else:
            p ← cursor;  cursor ← cursor + 1        # new bit byte, before the slot
            f.presence ← (p, 0)
            open ← (p, need)
    else:
        f.presence ← none
    if f.kind = Bool:
        f.slot ← none
    else:
        f.slot ← cursor;  cursor ← cursor + size(f.kind)
fixed_len ← cursor
```

Consequences (normative):

- A bit byte is opened **immediately before** the slot of the first field that did not
  fit in the previously open bit byte. A field's bit byte always precedes its slot.
- The 2 bits of a `bool` are never split across two bytes: if only 1 bit is left in the
  open byte, a new byte is opened (the leftover bit stays unused).
- Pointers and unions consume no bits and do not close the open bit byte.
- Appending fields at the end does not move the slot or bit of any earlier field;
  `fixed_len` only grows.
- Bit `(p, s)`: byte at fixed-part offset `p`, bit `s` counted from the least
  significant (`(byte >> s) & 1`). For `bool`, presence is at `s` and the value at
  `s + 1`.

### 3.4 Example: the layout of `conformance.v1.Root`

Fixed-part offsets (absolute position in the message = offset + 2, because the root
starts at 0). Bit `(p, s)`.

| ID | field | type | slot | bit |
|---|---|---|---|---|
| 0 | `a_u8` | `u8` | 1 | (0, 0) |
| 1 | `a_i16` | `i16?` | 2 | (0, 1) |
| 2 | `a_u32` | `u32 = 7` | 4 | (0, 2) |
| 3 | `a_i64` | `i64?` | 8 | (0, 3) |
| 4 | `a_u128` | `u128?` | 16 | (0, 4) |
| 5 | `a_i128` | `i128?` | 32 | (0, 5) |
| 6 | `a_f32` | `f32?` | 48 | (0, 6) |
| 7 | `a_f64` | `f64?` | 52 | (0, 7) |
| 8 | `flag` | `bool?` | — | (60, 0), value (60, 1) |
| 9 | `flag2` | `bool` | — | (60, 2), value (60, 3) |
| 10 | `color` | `Color?` (`u8`) | 61 | (60, 4) |
| 11 | `point` | `Point?` (8 bytes) | 62 | (60, 5) |
| 12 | `name` | `string?` | 70 | — |
| 13 | `blob` | `bytes?` | 74 | — |
| 14 | `nums` | `[u16]?` | 78 | — |
| 15 | `points` | `[Point]?` | 82 | — |
| 16 | `leaves` | `[Leaf]?` | 86 | — |
| 17 | `names` | `[string]?` | 90 | — |
| 18 | `blobs` | `[bytes]?` | 94 | — |
| 19 | `child` | `Leaf?` | 98 | — |
| 20 | `choice` | `Choice?` | 102 (tag 102..104, pointer 104..108) | — |
| 21 | *reserved* (was `old: u32?`) | — | 108 | (60, 6) |

`fixed_len = 112`. `RootV2` appends `extra @22: u64?` with slot 112 and bit (60, 7),
`fixed_len = 120`. `Leaf { n @0: u32; s @1: string?; next @2: Leaf? }`: `n` slot 1 bit
(0, 0), `s` slot 5, `next` slot 9, `fixed_len = 13`.

Complete message [vector: `minimal`] (114 bytes; only `a_u8 = 42` and `flag2 = true`):

```
pos 0..2    70 00          fixed_len = 112
pos 2       01             bit byte 0: a_u8 present (bit 0)
pos 3       2a             a_u8 = 42
pos 4..62   00 …           unwritten slots
pos 62      0c             bit byte 60: bits 2 and 3 = flag2 present, value true
pos 63..114 00 …
```

---

## 4. Presence

### 4.1 Principle

Absence is **on the wire**: a present `0` is different from absent.

- Every inline field (integer, float, enum, struct) has 1 presence bit; `1` = present.
  This holds for required and optional fields alike.
- `bool` has 2 bits: presence and value. When presence is `0`, the value bit MUST be
  ignored.
- Pointer: `0` = absent. Union: `tag = 0` = absent.
- An all-zero fixed part means "nothing present". The reference writer initializes the
  fixed part with zeros; defaults are applied by the reader and never written.

[vector: `zero_is_present` — byte 2 = `ff` (all 8 scalars present, all with value 0),
byte 62 = `35` = `0b0011_0101`: `flag` present with value false, `flag2` present with
value false, `color` and `point` present; `a_u32` reads as 0, not as the default 7]

### 4.2 Field read rule (3 steps)

To read field `f` of a table whose fixed part has size `fixed_len`, the reader MUST
apply, in this order:

1. **Classify the slot** `[o, o + size)` (fields with a slot: inline, `Ptr`, `Union`),
   testing in this order:
   - `o + size <= fixed_len` ⇒ slot **inside**: go to step 3;
   - otherwise, `o >= fixed_len` ⇒ slot **outside**: the field is absent;
   - otherwise (slot partially covered) ⇒ malformed table: `Truncated`.
2. **`bool`** (no slot): if the bit byte is outside (`p >= fixed_len`), the field is
   absent; otherwise go to step 3.
3. **The presence mark decides**: presence bit (inline and `bool`), pointer `≠ 0`
   (`Ptr`), `tag ≠ 0` (`Union`). A bit whose byte is outside `fixed_len` reads as 0.

The "inside" test comes first. Hence a zero-size slot (empty struct) with
`o == fixed_len` is **inside**, and the presence bit decides. Apart from that case, a
field's bit byte precedes its slot, so a slot inside `fixed_len` implies its bit byte is
inside too.

[vector: `truncated_slot` — the root's `fixed_len` = `42 00` (66): the slot of `point`
(offsets 62..70) is cut in half ⇒ `Truncated`]
[vector: `v1_read_by_v2` — message with `fixed_len = 112` read with `RootV2`: the slot
of `extra` (112..120) is entirely outside ⇒ absent]

### 4.3 Required, optional, default

The wire is identical for all three; the difference lives only in the reader schema.

- **Required** (`T`): if the field is absent by the rule in §4.2, the reader MUST fail
  with `Missing`. For a pointer, "present" means slot inside `fixed_len` and value
  `≠ 0` (the target is validated when the field is read). For a union, `tag ≠ 0`; if
  the tag is `≠ 0` but the pointer is `0`, the field is treated as absent, hence
  `Missing`.
- **Optional** (`T?`): absent is a valid result (`None`; in the vectors' value map, the
  key does not appear).
- **Default** (`T = x`): absent ⇒ the reader returns `x`. A default is never written by
  the writer.
- The required-field check of a table MUST also apply step 1 of §4.2 to **every**
  inline (`Scalar`) slot of the reader schema, required or not: an inline slot
  partially covered ⇒ `Truncated`, even if the field is never accessed. Reserved fields
  are exempt (§4.5).
- The writer does not enforce required fields; a message missing a required field is
  well-formed, and it is the reader that rejects it.

[vector: `minimal` — `a_u32` (`u32 = 7`) absent ⇒ reads as 7]
[vector: `missing_required` — byte 2 = `00`: the presence bit of `a_u8` is cleared
(the value 42 is still in the slot) ⇒ `Missing`]

### 4.4 `bool` in a table

The value of a `bool` with bit `(p, s)`: absent if `p >= fixed_len` or if bit `s` is
0; otherwise, bit `s + 1`.

[vector: `minimal` — byte 62 = `0c`: `flag` (bits 0,1) absent, `flag2` (bits 2,3)
present with value true]

### 4.5 Reserved fields

- A `reserved` field keeps the slot and bits of its original type in the layout.
- A writer MUST NOT write a reserved field (slot and bits stay zero).
- A reader MUST NOT read a reserved field: the content of its slot and bits is ignored
  without error (including a reserved slot partially covered by `fixed_len`), and the
  field never appears in the result.

[vector: `reserved_ignored` — written by an old writer that still had `old @21: u32?`:
byte 62 = `4c` (bit 6 = presence of `old`, plus `flag2`), positions 110..114 =
`ef be ad de`; read with `Root` without error and without the field]

---

## 5. Variable-size data

Variable-size data lives outside the fixed part, at any position in the buffer, reached
through a pointer (§2.2). Every length and count is a `u32`. The reader MUST check that
the header and the data fit in `len` (without arithmetic overflow) and reject with
`OutOfBounds` otherwise.

### 5.1 `string` and `bytes`

```
[u32 len][len bytes]
```

- `string`: the bytes MUST be valid UTF-8; otherwise `InvalidUtf8`.
- `bytes`: any content.
- A present `len = 0` is different from a `0` pointer (absent).

[vector: `v1_read_by_v2` — the `name` pointer at position 72 = `2a 00 00 00` ⇒ 114;
at 114: `02 00 00 00 76 31` = `"v1"`]
[vector: `all_fields` — the `blob` pointer at position 76 = `39 00 00 00` ⇒ 133; at
133: `04 00 00 00 00 01 fe ff`]
[vector: `empty_lists` — `name` ⇒ 114: `00 00 00 00` (empty string, present); `blob` ⇒
118: `00 00 00 00`]
[vector: `string_len_oob` — `len` = `05 00 00 00` with only 4 bytes left ⇒
`OutOfBounds`]
[vector: `bad_utf8` — first byte of the string (position 118) = `ff` ⇒ `InvalidUtf8`]

### 5.2 `[scalar]`, `[enum]`

```
[u32 count][count × size bytes]
```

Elements are packed; `size` is the size of the type (for an enum, its base type).
Unknown enum values in a list are accepted as raw values (§6.1).

[vector: `all_fields` — `nums: [u16]` at position 80 = `3d 00 00 00` ⇒ 141; at 141:
`03 00 00 00  00 00  01 00  ff ff` = `[0, 1, 65535]`]

### 5.3 `[bool]`

Same format as §5.2 with `size = 1`: each element is 1 byte. A writer MUST write `00`
(false) or `01` (true); a reader MUST read `00` as false and any other value as true.

[vector: `bool_struct_and_lists`]

### 5.4 `[struct]`

```
[u32 count][count × struct_size bytes]
```

Each element is the inline struct (§6.3), with no presence bits.

[vector: `all_fields` — `points: [Point]` at position 84 = `43 00 00 00` ⇒ 151; at 151:
`02 00 00 00  01 00 00 00 02 00 00 00  fd ff ff ff fc ff ff ff` =
`[(1, 2), (-3, -4)]`]

### 5.5 `[Table]`

```
[u32 count][u16 elem_fixed_len][count × fixed part of elem_fixed_len bytes]
```

- Elements are inline fixed parts, **without** their own `u16 fixed_len`; element `i`
  starts at `start + 6 + i × elem_fixed_len`.
- `elem_fixed_len` is the size of the fixed part according to the writer; each element
  is read with the rules of §4 using `elem_fixed_len` as `fixed_len`. This keeps the
  stride between elements correct across schema versions.
- `count × elem_fixed_len` (without overflow) MUST fit in `len` from `start + 6`;
  otherwise `OutOfBounds`.
- `elem_fixed_len = 0` is valid.
- Pointers inside an element are relative to their own slot inside the element.

[vector: `all_fields` — `leaves` at position 88 = `53 00 00 00` ⇒ 171; at 171:
`03 00 00 00  0d 00`, then 3 × 13 bytes. Element 0 at 177:
`01  01 00 00 00  22 00 00 00  00 00 00 00` (`n = 1`; the slot of `s` at 182 holds 34 ⇒
216, where `01 00 00 00 61` = `"a"` lives; `next` absent)]
[vectors: `table_list_elem_wider`, `table_list_elem_narrower`, `table_list_elem_zero`]

### 5.6 `[string]`, `[bytes]`

```
[u32 count][count × i32 pointer]
```

- Each pointer is relative to **its own slot** in the list and points to a
  `[u32 len][bytes]` (§5.1).
- An element pointer equal to `0` reads as an **empty** string / bytes (not as absent;
  lists have no absent elements). [vector: `strlist_null_elem`]

[vector: `all_fields` — `names` at position 92 = `9a 00 00 00` ⇒ 246; at 246:
`03 00 00 00  0c 00 00 00  0c 00 00 00  0d 00 00 00`; slot 0 (250) ⇒ 262:
`00 00 00 00` = `""`; slot 1 (254) ⇒ 266: `01 00 00 00 78` = `"x"`; slot 2 (258) ⇒
271: `04 00 00 00 6f 6c c3 a1` = `"olá"`]
[vector: `all_fields` — `blobs` at position 96 ⇒ 279, same format: `[ , ab, 010203]`]

### 5.7 Nested table

A table-typed field is a pointer to `[u16 fixed_len][fixed part]` (§3.1). Recursive
tables (a table that contains, directly or indirectly, a field of its own type) are
allowed.

[vector: `all_fields` — `child` at position 100 = `d3 00 00 00` ⇒ 311; at 311:
`0d 00  01  0a 00 00 00  08 00 00 00  0d 00 00 00` (`n = 10`, `s` ⇒ `"filho"`, `next`
⇒ another `Leaf`, recursively, 2 levels)]

### 5.8 Positions and sharing

- Variable-size data MAY come before or after whatever points to it (forward and
  backward pointers).
- Bytes not referenced by any pointer are allowed and ignored.
- More than one pointer MAY point to the same data. The cost of walking shared data is
  bounded by the `verify` budget (§7).
- Pointers MAY form a cycle; cycles are stopped by the `verify` depth limit (§7).

[vector: `streaming_leaves` — `leaves` written in streaming mode: the strings `"um"`
(114), `"dois"` (120) and a nested `Leaf` (128) come **before** the list header (153:
`03 00 00 00 0d 00`). Element 0 at 159; its `s` slot at 164 holds `ce ff ff ff` (−50)
⇒ 114. The `next` of element 2, slot at 194, holds `be ff ff ff` (−66) ⇒ 128]

---

## 6. Enums, unions and structs

### 6.1 Enum

- An enum has a base type `u8`, `u16` or `u32`, fixed forever; the value is stored as
  that integer.
- A value the reader schema does not know MUST NOT be an error: the reader MUST expose
  it as unknown, preserving the raw value (`Unknown(raw)` in the Rust runtime; a raw
  `UInt` in the vectors).

[vector: `unknown_enum` — byte 62 = `1c` (`flag2` + presence of `color`), byte 63 =
`09`: `color = 9`, outside `Color` ⇒ reads as 9]

### 6.2 Union

- 6-byte slot: `[u16 tag][i32 pointer]`. The pointer is relative to **its own first
  byte** (slot offset + 2), not to the start of the tag.
- Variants are tables only, with tags `≥ 1`, unique within the union. `tag = 0` =
  absent.
- `tag ≠ 0` with pointer `0` ⇒ the field is absent (§4.3).
  [vectors: `union_tag_null_ptr_optional`, `union_tag_null_ptr_required`]
- Known tag: the target is a table `[u16 fixed_len][fixed part]` of the variant's type.
- Tag unknown to the reader schema: MUST NOT be an error. The reader MUST expose the tag
  (`Unknown(tag)`; `{tag, value: {}}` in the vectors) and MUST NOT visit the payload's
  fields or charge it to the budget. The pointer, however, is resolved, and the
  target's header and fixed part are checked against `len` as in §3.1 (`BadOffset` /
  `OutOfBounds`). [vector: `union_unknown_tag_bad_ptr`]

[vector: `all_fields` — `choice` at position 104: `01 00` (tag 1), pointer at 106 =
`03 01 00 00` (259) ⇒ 365: `0d 00 01 14 00 00 00 08 00 00 00 00 00 00 00` (`Leaf`
with `n = 20`, `s = "escolha"`)]
[vector: `unknown_union_tag` — position 104: `05 00  08 00 00 00`: tag 5, pointer at
106 ⇒ 114, where a real `Leaf` lives; reads as `{tag: 5, value: {}}`]

### 6.3 Struct (frozen)

- Fields are packed in declaration order, with no padding and **no** presence bits;
  size = sum of the field sizes.
- Allowed types: integers, floats, `bool`, enums and other structs. A struct MUST NOT
  contain a pointer (string, bytes, list, table, union).
- A zero-size struct (no fields) is allowed in v1. As a table field, its empty slot
  follows §4.2: with `o == fixed_len` it is inside and the presence bit decides.
  [vector: `zero_size_slot_at_end`]
- A `bool` inside a struct takes **1 byte**: a writer MUST write `00` or `01`; a reader
  MUST read `00` as false and any other value as true. [vector: `bool_struct_and_lists`]
- A struct never changes after it is published (§9).
- As a table field, the whole struct is one inline slot with 1 presence bit.

[vector: `all_fields` — `point` at position 64: `ff ff ff ff ff ff ff 7f` =
`(x = -1, y = 2147483647)`]

---

## 7. Verification

### 7.1 Lazy reads and `verify`

The format supports lazy reading: a reader MAY validate only the root (header, fixed
part, required fields) and validate each field when it is accessed. In this mode, every
access MUST perform the checks of §2–§6 and return an error, never undefined behavior.

`verify` walks the **whole** message according to the reader schema. Data that comes
from outside (disk, network) SHOULD go through `verify` before it is trusted; reading
through the envelope (`from_bytes`) MUST perform a full `verify`. Conformance (§10) is
defined over a full read plus `verify`.

### 7.2 Walk

For each visited table (the root, nested tables, union variants with a known tag, and
each element of a `[Table]`):

1. required-field check (§4.3), including `Truncated` for inline slots;
2. enter: depth + 1; if the depth was already `max_depth` ⇒ `DepthExceeded`;
3. charge `2 + fixed_len` to the budget, **except** for `[Table]` elements (charged by
   the list);
4. read each **non-reserved** field of the reader schema (§4.2), validate its data
   (§5, §6) and charge the budget per §7.3; recurse into tables, known union variants
   and `[Table]` elements;
5. leave: depth − 1.

Fields the reader schema does not know (beyond its layout, or the payload of a union
with an unknown tag) MUST NOT be visited. The root has depth 1.

### 7.3 Budget

The budget is a number of "visited" bytes. Each piece of data is charged **every time
it is reached** (shared data is charged once per reference), after its bounds are
checked:

| data | charge |
|---|---|
| table (root, nested, union variant), not a list element | `2 + fixed_len` |
| `string` / `bytes` | `4 + len` (strings are UTF-8 validated first) |
| `[scalar]` / `[enum]` / `[bool]` / `[struct]` | `4 + count × max(size, 1)` |
| `[Table]` | `6 + count × max(elem_fixed_len, 1)` (covers the elements' fixed parts) |
| `[string]` / `[bytes]` | `4 + 4 × count`, plus `4 + len` per element |

A message MUST be rejected with `BudgetExceeded` when the **sum** of all charges of the
full walk exceeds the budget. (The sum does not depend on walk order.) The arithmetic
MUST saturate instead of overflowing.

The order between charging a table and entering it (counting depth) is not normative:
it only decides which of `BudgetExceeded` and `DepthExceeded` is reported when both
limits break in the same step, and error precedence is not normative (§7.5).

### 7.4 Default limits

- `max_depth = 64`;
- `budget = max(len × 8, 1 MiB)` (1 MiB = 1 048 576), where `len` is the size of the
  message (the payload, when there is an envelope).

`verify` and `from_bytes` MUST use these defaults. An API MAY offer explicit limits, but
the vectors assume the defaults.

[vector: `self_cycle` — the `next` of `child` (slot at 125) holds `f5 ff ff ff` (−11)
and points back to `child` itself (114): the walk descends until it passes 64 ⇒
`DepthExceeded`]
[vector: `budget_amplification` — 15 172 bytes, budget = 1 MiB (the floor); 1000
`leaves` elements whose `s` points to the same 2048-byte string: charges ≈
1000 × (4 + 2048) ≈ 2 MiB ⇒ `BudgetExceeded`]

### 7.5 What a reader MUST reject

| error | when |
|---|---|
| `OutOfBounds` | table header (`u16`) or fixed part past `len`; variable-size data header (`u32`, or `u32` + `u16` for `[Table]`) past `len`; `len × 1`, `count × size`, `count × elem_fixed_len` or `count × 4` past `len` (or overflow while computing it); empty buffer or buffer shorter than 2 bytes |
| `Truncated` | slot partially covered by `fixed_len` (§4.2) |
| `BadOffset` | pointer with target `< 0` or `>= len` (§2.2) |
| `InvalidUtf8` | `string` (field or `[string]` element) is not valid UTF-8 |
| `Missing` | required field of the reader schema is absent (§4.3) |
| `DepthExceeded` | table depth exceeds `max_depth` (§7.2) |
| `BudgetExceeded` | sum of charges exceeds the budget (§7.3) |

**Error precedence is not normative.** If a message has more than one defect, a reader
MAY return any of the applicable errors. (That is why each invalid vector has exactly
one defect.) The exception is the envelope check order (§8.4), which is normative.

A reader MUST NOT reject: unreferenced bytes; shared data (within the budget); backward
pointers; fields beyond the reader's layout; unknown enum values or union tags; the
content of reserved fields.

### 7.6 Error vocabulary

The vectors compare only the **name** of the `graven::Error` variant; the data some
variants carry (`field`, `needed`, `expected`/`found`, version) is not normative.

| variant | produced by | when |
|---|---|---|
| `OutOfBounds` | reader | §7.5 |
| `Truncated` | reader | §7.5 |
| `BadOffset` | reader | §7.5 |
| `InvalidUtf8` | reader | §7.5 |
| `Missing { field }` | reader | §7.5 |
| `DepthExceeded` | `verify` | §7.5 |
| `BudgetExceeded` | `verify` | §7.5 |
| `TooLarge` | **writer** | the message (or envelope payload) would exceed `i32::MAX` bytes; never produced by a reader |
| `BadMagic` | envelope | §8.4 step 2 |
| `UnsupportedVersion(v)` | envelope | §8.4 step 3 |
| `BadHeader` | envelope | §8.4 step 4 |
| `Incomplete { needed }` | envelope | §8.4 steps 1 and 5 |
| `ChecksumMismatch` | envelope | §8.4 step 6 |
| `SchemaMismatch { expected, found }` | read through envelope | §8.5 |

---

## 8. Envelope

### 8.1 Layout

An optional layer for disk and network. Messages without an envelope remain valid.

```
offset  size  field
0       4     magic = "GRVN" (47 52 56 4e)
4       1     format_version = 1
5       1     flags = 0
6       2     reserved = 0
8       8     schema_id (u64 LE)
16      4     payload_len (u32 LE)
20      N     payload: one graven message (§2.4), N = payload_len
20+N    4     crc32c (u32 LE) of bytes [0, 20+N)
```

Total size `24 + N`. A writer MUST NOT produce `payload_len > i32::MAX` (`TooLarge`).

[vector: `enveloped_all_fields` — 415 bytes; header
`47 52 56 4e  01  00  00 00  29 31 b4 27 2f ab 22 4c  87 01 00 00`
(`schema_id = 0x4c22ab2f27b43129`, `payload_len = 391`), payload = the bytes of
`all_fields`, trailer `76 50 c4 2a` (CRC `0x2ac45076`)]

### 8.2 `schema_id`

- Identifies the **root type** of the message.
- Value: 64-bit FNV-1a over the UTF-8 bytes of the fully qualified name of the root type
  (`namespace.Type`, e.g. `"conformance.v1.Root"`):

  ```
  h ← 0xcbf29ce484222325
  for each byte b:  h ← (h XOR b) × 0x100000001b3   (mod 2^64)
  ```

- The compiler MUST record the id in the lockfile on first compilation and read it from
  there afterwards, so the id never depends on the current text of the schema. Tables are
  matched by name, so a table cannot be renamed: the compatibility check reports
  `table-removed` (§9). An incompatible change is a new type, with a new name and so a new
  id (for example `OrderV2` next to `Order`); old and new messages never share an id.
- Among the schemas compiled together, each namespace is declared by exactly one file, and
  two tables MUST NOT share an id; the compiler MUST reject either situation.

[vector: `enveloped_all_fields` — `"conformance.v1.Root"` ⇒ `0x4c22ab2f27b43129`
(bytes `29 31 b4 27 2f ab 22 4c`)]
[vector: `env_wrong_schema` — `"conformance.v1.Leaf"` ⇒ `0x289ce2faa6b04709` (bytes
`09 47 b0 a6 fa e2 9c 28`)]

### 8.3 CRC32C

CRC-32C (Castagnoli): polynomial `0x1EDC6F41` (reflected form `0x82F63B78`), initial
value `0xFFFFFFFF`, reflected input and output, final XOR `0xFFFFFFFF`. Check values:
`crc32c("123456789") = 0xE3069283`; `crc32c("") = 0` (unit test in
`crates/graven/src/crc.rs`; not a vector). It covers the header **and** the payload.

[vector: `env_bitflip_payload` — trailer `aa aa 6e ad` = CRC `0xad6eaaaa` of the
original `minimal` envelope; the altered payload no longer matches]

### 8.4 Decoding and check order (normative)

A decoder MUST perform the checks **in this order** and stop at the first error:

1. `input_len < 20` ⇒ `Incomplete { needed: 20 }`;
2. bytes `0..4 ≠ "GRVN"` ⇒ `BadMagic`;
3. byte 4 `≠ 1` ⇒ `UnsupportedVersion(byte 4)`;
4. byte 5 `≠ 0`, or bytes 6..8 `≠ 0` ⇒ `BadHeader`;
5. `input_len < 24 + payload_len` (computed without overflow) ⇒
   `Incomplete { needed: 24 + payload_len }`;
6. CRC32C of `[0, 20 + payload_len)` `≠` the `u32` at
   `[20 + payload_len, 24 + payload_len)` ⇒ `ChecksumMismatch`.

Only then come the `schema_id` check (§8.5) and the payload read. A decoder MUST NOT
panic or read outside its input in any case.

**`Incomplete` ≠ `ChecksumMismatch`:**

- `Incomplete` means "bytes are missing": the input ends before the full header or
  before `24 + payload_len`. It is the normal result of an append-only file cut short
  by a crash; whoever reads the file MAY truncate it there.
- `ChecksumMismatch` means the envelope is complete and the CRC does not match: real
  corruption. It MUST NOT be treated as end of file.
- Because magic, version and flags are checked before the length, a header corrupted in
  those fields never turns into `Incomplete`. A corrupted `payload_len` results in
  `Incomplete` (if it grew past the input) or `ChecksumMismatch`, never in an accepted
  payload. [vectors: `env_payload_len_short_inplace`, `env_payload_len_long`]

| vector | input | error |
|---|---|---|
| `env_cut_header` | 10 bytes `47 52 56 4e 01 00 00 00 29 31` | `Incomplete` (20) |
| `env_bad_magic` | byte 0 `58` (`X`), CRC recomputed | `BadMagic` |
| `env_bad_version` | byte 4 `02`, CRC recomputed | `UnsupportedVersion` |
| `env_bad_header` | byte 5 `01`, CRC recomputed | `BadHeader` |
| `env_cut_payload` | 30 bytes (`payload_len = 114`) | `Incomplete` (138) |
| `env_cut_crc` | 136 bytes (half of the CRC) | `Incomplete` (138) |
| `env_bitflip_payload` | byte 23 (`a_u8`) `2a → 2b` | `ChecksumMismatch` |
| `env_bitflip_crc` | byte 137 `ad → 2d` | `ChecksumMismatch` |

### 8.5 Schema id and reading

After §8.4, a reader that expects root type `R` MUST compare `schema_id` with the id of
`R` and fail with `SchemaMismatch` if they differ; otherwise it MUST read the payload as
a message of `R` with full `verify` (§7), with `len` = `payload_len`. A well-formed
envelope whose payload is not a valid message fails with the message error.

[vector: `env_wrong_schema` — well-formed envelope, valid CRC, id of
`conformance.v1.Leaf`, read as `Root` ⇒ `SchemaMismatch`]
[vector: `env_payload_len_short` — valid CRC, payload shorter than the root's fixed
part ⇒ `OutOfBounds` (§2.4)]

### 8.6 Concatenation

- Bytes after the CRC are not an error: `decode` consumes `24 + payload_len` bytes and
  exposes that length so the next envelope can be read right after it.
- Envelopes MAY be concatenated (batches, append-only files). An iterator MUST stop at
  the first error; an `Incomplete` on the last envelope indicates a cut-off tail.
- Empty input = no envelopes.

[vector: `env_concat`]

---

## 9. Schema compatibility

These rules are normative for compilers. They guarantee that a writer and a reader
using different versions of the same schema understand each other (§4.2 provides the
mechanics: fields beyond `fixed_len` are absent; bytes beyond the reader's layout are
ignored).

The compiler MUST keep a lockfile with the computed layout (per table: IDs, type, size,
slot, bit, required/optional/default, reserved; per enum: base type and values; per
struct: fields and size; per root type: `schema_id`) and, on recompilation, compare the
new schema against the lockfile:

**Error** (the compiler MUST refuse):

- changing the type or size of a field; reusing an ID; reordering IDs; removing a field
  without marking it `reserved`;
- changing the base type of an enum, or changing a `struct`;
- adding a **required field without a default** after the first version (every new
  reader would fail on old messages): a new field is `T?` or has `= x`;
- making an optional field required (no default) (same reason);
- changing a field's default value, or giving a default to an optional field: old
  messages without the field would start reading a different value (silent wrong data);
- changing the value of an enum variant or removing it; removing a union variant or
  pointing its tag at another table (silent wrong data);
- changing the kind of a table, enum, struct or union (e.g. enum ↔ struct of the same
  size); removing a table;
- changing the namespace: it changes the schema id of every table (start a new lockfile on
  purpose if that is really intended).

**Warning** (breaks old readers with an explicit error, never with wrong data; the
compiler MUST require explicit confirmation in the schema, otherwise it is an error):

- marking a field that was required as `reserved`: old readers get `Missing`; readers
  that had it as optional get absent;
- making a required field optional or defaulted: new writers may omit it and old
  readers get `Missing`. Requiring confirmation here also stops required → optional →
  `reserved` from bypassing the previous warning.

A lockfile is only created without comparison for a new schema, on explicit request; a
missing lockfile MUST NOT be implicitly treated as "new schema".

**Allowed:**

- a new optional or defaulted ID at the end;
- `reserved` on an optional or defaulted field;
- default → optional (messages without the field start reading absent, never another
  value);
- renaming a field or an enum variant (names are not in the bytes);
- a new enum or union variant (old readers see an unknown value/tag, §6.1, §6.2).

[vector: `v2_read_by_v1` — written with `RootV2` (`fixed_len = 78 00` = 120; byte 62 =
`8c`, bit 7 = `extra`; `extra` at 114..122 = `88 77 66 55 44 33 22 11`) and read with
`Root`: `extra` ignored, `name` (⇒ 122, `"v1"`) read normally]
[vector: `v1_read_by_v2` — written with `Root`, read with `RootV2`: `extra` absent]
[vector: `reserved_ignored` — field removed and marked `reserved`]

---

## 10. Conformance

### 10.1 Reader

A reader implementation **conforms to format v1** if, for every vector
`testvectors/v1/<name>`, it produces exactly the result in the `.json`:

1. if `enveloped`: decode the envelope (§8.4) and check `schema_id` against the 64-bit
   FNV-1a of `schema` (§8.5); the payload is the message;
2. read the whole message with the reader schema `schema` and verify it (§7, default
   limits);
3. compare with `expect`: the value (encoding described in the
   [vectors README](../conformance-vectors.md); floats by bits) or the **name** of the
   error variant.

The vectors are frozen and normative: if this text and a vector conflict, the vector
wins; the error is in the text, which must be corrected.

### 10.2 Writer and canonical layout

A writer conforms if every message it produces is read by a conforming reader with the
values written. A writer does NOT need to reproduce specific bytes: readers MUST accept
any valid layout (data in any order, backward pointers, unreferenced bytes, shared
data).

The **canonical layout** is that of the reference writer, pinned byte for byte by the
valid vectors `minimal`, `all_fields`, `zero_is_present`, `empty_lists`,
`v2_read_by_v1`, `v1_read_by_v2` and `enveloped_all_fields`. A writer that wants output
identical to the reference (byte-for-byte tests, deduplication by hash) MUST follow:

- root at 0; each table's fixed part has the full `fixed_len` of the writer's layout,
  initialized with zeros; only written fields have non-zero bits/slots;
- variable-size data is appended at the end of the buffer, in the order it is written;
  fields are written in ID order; when writing a nested table, its header and fixed
  part are appended and its fields written (recursively) before the parent's next
  field;
- `[Table]` with a known count: header plus all fixed parts reserved at once, then each
  element's variable-size data, in element order;
- `[string]` / `[bytes]`: header and slots, then each element in order.

Streaming lists (`streaming_leaves`), filled reserved fields (`reserved_ignored`) and
unions with an unknown tag (`unknown_union_tag`) are **valid but non-canonical**
layouts: the vectors pin how to read them, not how to write them.

### 10.3 Vectors added after the first release

The following rules had no vector in the first version of `testvectors/v1/`. The vectors
below were added later (existing implementations already accepted them); no earlier
vector changed:

- `bool` inside a struct and `[bool]` elements (1 byte; non-zero = true) (§5.3, §6.3);
  `[enum]` with an unknown value [vector: `bool_struct_and_lists`];
- `[string]` / `[bytes]` element with pointer `0` ⇒ empty (§5.6)
  [vector: `strlist_null_elem`];
- union with `tag ≠ 0` and pointer `0` ⇒ absent / `Missing` (§4.3, §6.2)
  [vectors: `union_tag_null_ptr_optional`, `union_tag_null_ptr_required`];
- union with an unknown tag whose pointer is invalid ⇒ the pointer's error (§6.2): the
  vector pins `BadOffset` for a pointer one past the end
  [vector: `union_unknown_tag_bad_ptr`];
- reserved slot partially covered by `fixed_len` ⇒ no error (§4.5)
  [vector: `reserved_slot_partial`];
- pointer slot partially covered ⇒ `Truncated` [vector: `ptr_slot_partial`];
- `[Table]` with `elem_fixed_len` larger or smaller than the reader's layout;
  `elem_fixed_len = 0` [vectors: `table_list_elem_wider`, `table_list_elem_narrower`,
  `table_list_elem_zero`];
- zero-size slot (empty struct) with `o == fixed_len` ⇒ inside, the bit decides (§4.2)
  [vector: `zero_size_slot_at_end`];
- envelope concatenation (§8.6) [vector: `env_concat`];
- `payload_len` corrupted in place ⇒ `ChecksumMismatch` (smaller) or `Incomplete`
  (past the buffer) [vectors: `env_payload_len_short_inplace`, `env_payload_len_long`];
  a well-formed envelope (valid CRC) whose payload is shorter than the root's fixed
  part ⇒ the message's error (`OutOfBounds`, §8.5 → §2.4)
  [vector: `env_payload_len_short`].

`TooLarge` is a *writer* rule, not a reader rule: it does not fit in a read vector and
is covered by the runtime tests (`crates/graven/tests/writer_limits.rs`).

---

## Appendix A (informative): frame batches

The Rust runtime also offers batches of messages **without** an envelope
(`Builder::seal` / `take_frames`, read by `graven::frames`): each frame is
`[u32 len LE][message of len bytes]`, concatenated; a cut-off tail produces an
`OutOfBounds` and ends the iteration. This format has no magic, version, schema id or
CRC, has no vectors and is **not** part of the normative v1 format; for data that
leaves the process, use the envelope (§8).

## Appendix B (informative): design notes

Decisions that are easy to miss when reading the normative text:

1. **Envelope, not framing in the message.** The raw message has no magic, version or
   checksum; those live in the optional envelope (§8), so in-memory and in-process uses
   pay nothing for them.
2. **`verify` limits are fixed.** `max_depth = 64`, `budget = max(len × 8, 1 MiB)` and
   the charging rules of §7.3 (including `max(size, 1)` per element, so lists of
   zero-size elements also consume budget) are part of the format, so every conforming
   reader accepts and rejects the same inputs.
3. **No `[[T]]` and no `[Union]` in v1.** They can be added in a later version without
   changing any existing encoding.
4. **`bool` in structs and lists is one byte** (`00`/`01`; reading non-zero = true);
   the 2-bit encoding exists only in table fixed parts, where presence is needed.
5. **Unknown union tags are bounds-checked but not walked** (§6.2): the pointer is
   resolved and the target's header and fixed part are checked against `len`, without
   reading fields or charging the budget.
6. **Union with `tag ≠ 0` and pointer `0` is absent**, and a `0` pointer in a
   `[string]`/`[bytes]` element is empty: there are no "null" list elements.
7. **Truncated inline slots are caught at table level** (§4.3): the required-field check
   applies the slot rule to every inline slot of the reader schema, so a partially
   covered slot fails even if the field is never accessed. Reserved slots are exempt.
8. **Streaming lists** are a writer technique, not part of the format: on the wire they
   are ordinary relative (backward) pointers.
9. **Size limit.** A message is at most `i32::MAX` bytes, enforced by the writer
   (`TooLarge`), so every pointer fits in an `i32`.
10. **Writers do not enforce required fields.** A message missing a required field is
    well-formed; the reader rejects it with `Missing`.


---

<!-- source: docs/binary-layout.md -->

# Binary layout, by example

This page shows how each kind of value looks on the wire. Every example below was encoded by
the reference implementation (`gravenc from-json`) when this site was built, then annotated
from the layout in the lockfile. Point at a byte or a label to see what it encodes.

The examples are bare messages, without the [envelope](spec/graven-format-v1.md#8-envelope).
Byte offsets start at 0. Pointers are relative to the position of the pointer itself, so a
message can be copied or embedded anywhere without fixing them up.

Five colours are used throughout: structure (lengths, counts, presence bits, union tags),
inline values, pointers, variable-size data, and absent fields.

## Scalars, enums and presence

```graven
enum Unit : u8 { Celsius = 0, Fahrenheit = 1 }

table Reading {
  device  @0: u32;
  temp    @1: f32?;
  battery @2: u8?;
  unit    @3: Unit;
  online  @4: bool;
}
```

A table starts with a `u16` giving the length of its fixed part. Scalars live in the fixed
part, each in a slot at a position the compiler computes once and records in the lockfile.
One presence bit per scalar tells a present zero from an absent field: here `battery` is
absent, so its slot is ignored. A `bool` is two bits in the presence byte and has no slot.

<figure class="anatomy layout" data-example="scalars"><p class="explain">The example needs JavaScript.</p></figure>

## Strings and bytes

```graven
table Note {
  title @0: string;
  body  @1: string?;
  tag   @2: bytes?;
}
```

Variable-size data lives after the fixed part. The slot holds a 4-byte relative pointer; a
zero pointer means absent. The data is a `u32` length followed by the bytes, which a reader
borrows straight from the buffer.

<figure class="anatomy layout" data-example="strings"><p class="explain">The example needs JavaScript.</p></figure>

## Lists of scalars and structs

```graven
struct Point { x: i16, y: i16 }

table Path {
  ids    @0: [u16];
  points @1: [Point];
}
```

A list of fixed-size values is a `u32` count followed by the elements, packed with no
padding. Element `i` is at `4 + i × size`, so indexing is a multiplication, not a scan.

<figure class="anatomy layout" data-example="lists"><p class="explain">The example needs JavaScript.</p></figure>

## Lists of tables

```graven
table Product {
  name  @0: string;
  price @1: u32;
}

table Catalog {
  products @0: [Product];
}
```

This is the shape of a JSON array of objects, such as
`{"products": [{"name": "pen", "price": 150}, …]}` (see
[Coming from JSON](coming-from-json.md)). The list starts with a `u32` count and a `u16`
element length. The elements' fixed parts follow back to back, without a header each, so
element `i` is at `6 + i × length`. Each element can still have its own strings, lists and
nested tables: their pointers lead to data after the list.

Storing the element length in the list, rather than taking it from the schema, is what lets
a list written by a newer schema (with longer elements) be read by an older one, and the
other way round.

<figure class="anatomy layout" data-example="tables"><p class="explain">The example needs JavaScript.</p></figure>

## Lists of strings

```graven
table Tags {
  tags @0: [string];
}
```

A list of strings or byte arrays is a `u32` count followed by one pointer per element.

<figure class="anatomy layout" data-example="strlist"><p class="explain">The example needs JavaScript.</p></figure>

## Nested tables

```graven
table Customer {
  name @0: string;
  home @1: Address?;
}

table Address {
  city @0: string;
  zip  @1: u32;
}
```

A table field is a pointer to another table, with its own length header and presence bits.
Each table evolves on its own: adding a field to `Address` does not change `Customer`.

<figure class="anatomy layout" data-example="nested"><p class="explain">The example needs JavaScript.</p></figure>

## Unions

```graven
table Card { last4 @0: u16; }
table Pix  { key @0: string; }

union Method { Card @1: Card, Pix @2: Pix }

table Payment {
  amount @0: u32;
  method @1: Method;
}
```

A union slot is a `u16` tag followed by a pointer to the variant's table. Tag 0 means no
value. A reader that does not know a tag reports it as unknown instead of failing, so new
variants can be added.

<figure class="anatomy layout" data-example="union"><p class="explain">The example needs JavaScript.</p></figure>

The normative rules for all of the above are in the
[specification](spec/graven-format-v1.md).

<script src="../assets/layouts.js" defer></script>


---

<!-- source: docs/graven-language.md -->

# The schema language (`.graven`)

Reference for the language accepted by `gravenc` (crate `graven-compiler`) and for the Rust
code it generates. The binary format is specified normatively in the
[format specification](spec/graven-format-v1.md); this document explains how to write a
schema, how to evolve it, and what the generator produces.

```graven
namespace bank;

enum Currency : u16 { BRL = 0, USD = 1, EUR = 2 }

table Entry {
  account @0: u64;
  amount  @1: i64;
  memo    @2: string?;
}

table Transaction {
  id         @0: u64;
  ts         @1: u64;
  currency   @2: Currency;
  from_shard @3: u32;
  to_shard   @4: u32;
  entries    @5: [Entry];
  note       @6: string?;
}
```

## 1. Grammar

```text
schema    = "namespace" path ";" { import } { item } ;
import    = "import" path [ "as" ident ] ";" ;
path      = ident { "." ident } ;
item      = enum | struct | table | union ;
enum      = "enum" ident ":" type "{" [ evalue { "," evalue } [","] ] "}" ;
evalue    = ident "=" int ;                    (* decimal or 0x…, unsigned *)
struct    = "struct" ident "{" [ sfield { "," sfield } [","] ] "}" ;
sfield    = ident ":" type ;
table     = { attrs } "table" ident "{" { tfield } "}" ;
tfield    = { attrs } ( "@" int ":" "reserved" [ type ] ";"
                      | ident "@" int ":" type [ "?" ] [ "=" literal ] ";" ) ;
attrs     = "#" "[" attr { "," attr } [","] "]" ;
attr      = ident [ "(" [ arg { "," arg } [","] ] ")" ] ;
arg       = ident [ "=" literal ] ;
union     = "union" ident "{" uvar { "," uvar } [","] "}" ;   (* at least one variant *)
uvar      = ident "@" int ":" type ;
type      = ident [ "." ident ] | "[" type "]" ;   (* `name.Type`: an imported type *)
literal   = [ "-" ] int | [ "-" ] float | "true" | "false" | ident ;
ident     = ( letter | "_" ) { letter | digit | "_" } ;   (* ASCII *)
int       = decimal digits | "0x" hex digits ;           (* "_" separates digits *)
float     = digits ( "." digits [ exponent ] | exponent ) ;   (* 1.5, 2e10, 1.0e-3 *)
exponent  = ( "e" | "E" ) [ "+" | "-" ] digits ;
digits    = digit { digit | "_" } ;
```

Comments: `// …` to end of line and `/* … */`. Whitespace is free. Documentation
comments, `/// …`, document the declaration that follows them (see
[Documentation comments](#documentation-comments)). The `namespace` is
part of each table's `schema_id` (`"<namespace>.<Table>"`, spec §8.2).

### Documentation comments

A `///` comment documents the type, field, enum variant, union variant or struct field
right after it. The generated code carries it, so it shows up in the editor and in API
documentation next to the generated reader, verified view, writer, accessors and setters:

```graven
/// A double-entry transaction between two shards.
///
/// The entries of a transaction always sum to zero.
table Transaction {
  /// Unix time, in seconds.
  ts @1: u64;
}
```

- Consecutive `///` lines form one comment; blank `///` lines separate paragraphs, and
  Markdown is passed through.
- A `///` comment with no declaration after it is an error. `////` (four or more slashes)
  is an ordinary comment.
- Documentation is not part of the layout: it never appears in the lockfile, and adding,
  changing or removing it is always compatible. A reserved field generates no code, so its
  documentation is not kept.

## 2. Types

| Type | Where | Notes |
|---|---|---|
| `u8 u16 u32 u64 u128 i8 i16 i32 i64 i128` | field, struct, list | little-endian |
| `f32 f64` | field, struct, list | IEEE-754 |
| `bool` | field, struct, list | in a table it takes only bits (spec §4.4); in a struct or list, 1 byte |
| `string` | field, list | UTF-8, validated by `verify` |
| `bytes` | field, list | |
| `[T]` | field | `T` = scalar, `bool`, enum, struct, `string`, `bytes` or table; no `[[T]]` and no `[Union]` |
| `enum E : u8/u16/u32` | field, struct, list | an unknown value reads as `Unknown(raw)` |
| `struct S` | field, struct, list | **frozen**: packed fields, no padding, never evolves; only scalars, `bool`, enums and structs; no recursion |
| `table T` | field, list, union variant | evolves through IDs; recursion allowed |
| `union U` | field | variants are tables, unique tags `> 0`; an unknown tag reads as `Unknown(tag)` |

The built-in names (`u8`…`f64`, `bool`, `string`, `bytes`) cannot be redeclared.

## 3. Table fields: IDs, presence and defaults

Every field has an ID `@N`. IDs are **contiguous from `@0`**, with no repeats; ID order
defines the layout (spec §3.3), not the order in the text.

| Form | Presence | Reading a message without the field |
|---|---|---|
| `x @0: u32;` | required | `Missing` error (on `read` for scalars; on access/`verify` for pointers) |
| `x @0: u32?;` | optional | `None` |
| `x @0: u32 = 7;` | default | the default |

- Defaults are only allowed on scalars, `bool` or enums (by variant name:
  `color @3: Color = Red;`). `?` and `=` cannot be combined.
- An integer default may be any value of its type, from `i128::MIN` to `u128::MAX`, in
  decimal or `0x` hexadecimal, with `_` between digits.
- A float default is rounded to the nearest value of its type, as in any language
  (`f32 = 0.1` stores the `f32` closest to 0.1). A default that would become infinite, or
  a non-zero literal that would become 0 (`f32 = 1e-50`), is refused instead of being
  changed silently.
- An absent `bool` with a default reads the default; an absent required `bool` is
  `Missing`, like any other scalar.

## 4. Reserved fields

A field that leaves the schema **is not deleted**: it becomes reserved, keeping its ID
and slot.

```graven
table Root {
  a @0: u32;
  @1: reserved u32;   // was `old @1: u32?`
}
```

- The type may be omitted (`@1: reserved;`) when the lock already knows the field: the
  type comes from the lock. If both are present, they must match.
- A reserved field cannot be `?` or have a default; its ID is never reused
  (`id-reused`).
- Reserving a **required** field breaks old readers (they get `Missing`): that is the
  `required-reserved` warning, which requires confirmation with the attribute below.

## 5. Attributes and validation rules

### Evolution confirmation

`#[allow_breaking_readers]` confirms compatibility warnings:

- on a reserved, optional or defaulted field that used to be required (`required-reserved`, `required-relaxed`),
- on any field whose validation rules tightened or gained a check (`rule-tightened`, `check-added`),
- on a table that gained a table-level `check(name)` (`check-added`).

```graven
table T {
  a @0: u32;
  #[allow_breaking_readers] @1: reserved;   // `b` used to be required
  #[allow_breaking_readers] c @2: u32?;     // `c` used to be required
}
```

The attribute may stay in the schema after `update`; it only has an effect in the step
where the breaking change is introduced.

### Validation rules

Tables and table fields can declare value validation rules without changing the wire format
(see [proposal 0002](proposals/0002-validation.md)):

```graven
enum Status : u8 { Active = 0, Draft = 1 }

#[check(valid_period)]
table Promo {
  #[len(min = 1, max = 64), check(slug)]
  name @0: string;

  #[range(min = 1, max = 10_000_000)]
  price @1: u32;

  #[finite, range(min = 0.0, max = 100.0)]
  discount @2: f32?;

  #[known]
  status @3: Status;

  starts @4: u64;
  ends @5: u64;
}
```

| Rule | Applies to | Meaning |
|---|---|---|
| `range(min = a, max = b)` | integer and float fields | `a ≤ value ≤ b` (inclusive; NaN is outside); either bound may be omitted |
| `len(min = a, max = b)` | `string`, `bytes`, `[T]` | byte length (`string`/`bytes`) or element count (`[T]`); either bound may be omitted |
| `finite` | `f32`, `f64` | not NaN and not infinite |
| `known` | enum fields and `[Enum]` | value is a variant declared in the reader's schema |
| `check(name)` | any field or `table` | calls application-provided `Checks::name(&self, v) -> bool` |

Validation never runs implicitly on `from_bytes` or `to_bytes` (so old data stays readable).
When a schema declares rules, generated code provides `pub trait Checks`, `XVerified::validate(&checks)`
(stops at the first failure, no allocation), `XVerified::validate_all(&checks)` (collects `Vec<Invalid>`),
and `XW::to_bytes_validated(&mut b, &checks, |w| ...)`. Schemas without rules generate the exact same
code as before.

Any other attribute is an error.

## 6. Names

Besides being unique in their scope, names must produce valid, collision-free Rust.
`check` rejects (with `file:line:column`):

- a **type name** (enum, struct, table, union) that does not start with an uppercase
  letter `A–Z` — this rules out keywords, Rust primitives (`str`, `usize`) and
  collisions with the layout module and with variables of the generated code;
- a type whose (snake_case) layout module would be `self`, `super` or `crate` (`Crate`,
  `Super`, `SELF`); other modules that are keywords are emitted raw (`Type` ⇒
  `mod r#type`);
- `self`, `Self`, `super`, `crate` and `_` as any name. Other Rust keywords are accepted
  as fields and variants and are emitted as `r#name`;
- the enum variants `Unknown`, `from_raw` and `to_raw`; the union variant `Unknown`;
- any generated identifier repeated in the same scope:
  - **module** — for table `X`: `X`, `XVerified`, `XW`, `XE`, `XListW` (types and
    constructors), `mod x` (snake_case), `X_REQ`, `X_MASK`, `X_SCHEMA_ID` (UPPER_CASE of
    the snake form); for union `U`: `U`, `UVerified`; and the reserved name `SCHEMA_ID`.
    E.g. `HTTPServer` and `HttpServer` (both become `http_server`), `Foo` and `FooW`,
    `FOO` and `FOO_REQ`;
  - a table's **layout module** — `FIXED_LEN`, `PTR_SLOTS`, `FIELD` (offset of every
    non-`bool` field) and `FIELD_BIT` (scalars and `bool`). E.g. fields `fixed_len`,
    `ptr_slots`; `x` (scalar) with `x_bit`; `fooBar` with `foo_bar`;
  - **reader methods** — `read`, `verified`, `verified_with`, `from_bytes`, `verify`,
    `SCHEMA_ID` and one accessor per field;
  - **view methods** — `reader` and one accessor per field;
  - **writer methods** — `root`, `to_bytes`, `seal` and: one setter per field; for a list
    (except `[string]`/`[bytes]`) also `<field>_streaming`; for a union, one
    `<field>_<variant_snake>` per variant (and no `<field>`). E.g. `xs: [u32]` with
    `xs_streaming`; `u: U` (variant `Big`) with `u_big`.

`Option`, `String`, `Result`, `FnOnce` and the like are accepted: the generated code
only uses absolute paths (`::core::…`, `::graven::…`). So is a field named `schema_id`
(the method `schema_id()` does not collide with the const `SCHEMA_ID`). Style
recommendation: types and variants in `CamelCase`, fields in `snake_case` — the
generator does not rename, and other styles produce lint warnings in the crate that
includes the code.

## 7. Imports

A schema can use the types declared in other schemas by importing their namespace:

```graven
// common.graven
namespace common;

struct Money { cents: i64, currency: u16 }
table Address { street @0: string; city @1: string; }
```

```graven
// orders.graven
namespace orders;

import common;

table Order {
  total   @0: common.Money;
  ship_to @1: common.Address?;
}
```

- An import names a **namespace**, not a file. The compiler finds the file that declares it
  among the schemas compiled together: the ones passed to `build.rs` or `gravenc check`, and
  for single-schema commands, the `.graven` files under the schema's directory. Files can be
  moved or renamed freely.
- **One namespace, one file.** Two files declaring the same namespace in one compilation is
  an error.
- Imported types are always written qualified, by the last segment of their namespace:
  `import acme.common;` → `common.Money`. Unqualified names refer only to the file's own
  types, so adding a type to `common` never changes the meaning of a name elsewhere. When two
  imports would have the same name, give one an alias: `import acme.common as ac;`.
- Any type can be imported: structs, enums, tables and unions. Import cycles are errors.
- An imported table keeps the schema id of the namespace that declares it.
- The importing file's lockfile also records the layout of every imported type it uses, so a
  change to `common` that would break `orders` is refused by `gravenc update orders.graven`
  (rule `import-changed`), and a pull request that changes a shared type shows, in the lock
  diffs, every schema it affects. A compatible change to an imported type (a new optional
  field, a new enum variant) is accepted, and the importer's lock is refreshed with
  `gravenc update`.
- Namespaces carry no version: compatible changes evolve a type in place, and an
  incompatible change is a new type (`OrderV2` next to `Order`), with its own schema id.

## 8. Compatibility (lockfile)

The lock (`<schema>.lock`, deterministic TOML, committed next to the schema) stores the
state that must survive across versions: each table's `schema_id`, the layout (ID, type,
size, slot, bit, presence) and the types of reserved fields, enums, structs and unions.
`gravenc update` compares the new schema against the lock (normative rules in
[spec §9](spec/graven-format-v1.md#9-schema-compatibility)) before rewriting it.

**Errors** (refused):

| Rule | When |
|---|---|
| `type-changed` | a field's type or size changed (or a type changed kind: enum ↔ struct ↔ table ↔ union) |
| `id-reused` | a reserved ID became a field again |
| `ids-reordered` | fields swapped IDs |
| `field-removed` | a field disappeared without becoming `reserved` |
| `enum-base-changed` | an enum's base type changed |
| `struct-changed` | a struct's fields or size changed |
| `new-required` | a new required field without a default |
| `optional-to-required` | an optional/defaulted field became required |
| `table-removed` | a table in the lock disappeared |
| `default-changed` | a field's default value changed (old messages without the field would change meaning) |
| `default-added` | an optional field gained a default (old messages without the field would start reading the default; this also closes `= 5` → `?` → `= 6`) |
| `enum-variant-changed` | an enum variant changed value or was removed (renaming while keeping the value is allowed) |
| `union-variant-changed` | a union variant was removed, or its tag now points to another table |
| `namespace-changed` | the namespace changed, which changes every schema id; if that is intended, start a new lockfile (delete the lock and run `gravenc update --init`) |
| `layout-changed` | defensive: a different slot/bit with the same types (the sequential layout never produces this) |

**Warnings** (an error until confirmed with `#[allow_breaking_readers]` on the field or table):
`required-reserved` (required → reserved), `required-relaxed` (required →
optional/default), `rule-tightened` (a `range`/`len` bound tightened or a new built-in rule
added to an existing field), and `check-added` (a new `check(name)` added to an existing
field or table). Since `required-relaxed` also requires confirmation, reserving in two
steps (required → optional → reserved) does not escape the warning.

**Allowed**: a new optional or defaulted field (`new-optional`, `new-default`);
reserving an optional or defaulted field; default → optional; renaming a field; a new
enum or union variant; a new table.

## 9. Workflow: `gravenc update` vs `build.rs`

The lock only changes through an explicit action; the build never writes it.

```text
gravenc check  [--locked] <schema>...      validate schema(s) and compatibility with <schema>.lock
gravenc update <schema>... [--from <lock> | --init]
                                         apply the compatibility check and write <schema>.lock
gravenc gen    <schema> -o <dir>           generate <dir>/<file without .graven>.rs (creates <dir>)
```

- `check`: parse, check and (if there is a lock) compatibility; writes nothing. Warns
  (without failing) if the lock does not exist or would be updated. With `--locked`,
  both cases are errors (exit 1), as in `build.rs`: this is the CI command
  (`gravenc check --locked schemas/*.graven`), with no compilation.
- `update`: with a lock, only rewrites it if there is no error and no unconfirmed
  warning. Without a lock, it refuses unless given `--init` (a new schema: first lock,
  no history) or `--from` (a moved or renamed schema: compare against the old lock).
  This way a deleted lock or a renamed file does not reset the compatibility check.
  `--from <lock>` compares against another lock (e.g. `v2.graven` against
  `v1.graven.lock`), keeping its `schema_id`s; the lock written is always
  `<schema>.lock` (if the current `<schema>.lock` is unreadable, it is treated as
  missing and overwritten).
- `gen`: the same as `build.rs`, into a directory (created if missing).
- `diff`, `inspect`, `to-json`, `from-json` and `scan` work with schemas and data files; see
  [Tools](tools.md).
- Diagnostics go to stderr: `file:line:column: message` (compatibility messages name the
  rule); a confirmed warning is printed as `file:line:column: warning: message` and does
  not fail. Exit codes: 0 ok, 1 error, 2 usage error.

In the crate that uses the schema:

```rust
// build.rs
fn main() {
    graven_compiler::build::Build::new()
        .schema("schemas/bank.graven")     // reads schemas/bank.graven.lock
        .compile()                       // writes $OUT_DIR/bank.rs
        .unwrap_or_else(|e| panic!("{e}"));
}
```

`compile()` emits `cargo:rerun-if-changed` for the schema and the lock, and fails if:
the lock does not exist (the message points to `gravenc update --init` or `--from`);
regenerating the lock would change something (the schema was edited without
`gravenc update`); compatibility has an error or an unconfirmed warning; the schema does
not pass parse/check. Confirmed warnings become `cargo:warning`.

Typical cycle: create the `.graven` → `gravenc update --init` once; afterwards, edit the
`.graven` → `gravenc update` (review the findings) → commit schema and lock →
`cargo build`.

## 10. Safety: generated code lives alone in its module

**Include each generated file alone in its own module:**

```rust
#![deny(unsafe_code)]   // in the crate (generated code carries #[allow(unsafe_code)] where needed)

pub mod bank {
    include!(concat!(env!("OUT_DIR"), "/bank.rs"));
    // nothing else here
}
```

The view `XVerified<'a>` reads strings without revalidating UTF-8 (`str_unchecked`).
That is sound because it is only constructed after `verify()` has passed. Its tuple
field is private — but privacy in Rust is **per module**: *safe* code written in the
same module as the `include!` could write `XVerified(X::read(buf)?)` without verifying
and, given an invalid string, cause undefined behavior. Outside the module, that
construction does not compile. The header of every generated file repeats this warning.

When schemas import each other, include each generated file in a module named after the
last segment of its namespace, side by side: the generated `orders` code refers to
`super::common::Money`.

```rust
pub mod common { include!(concat!(env!("OUT_DIR"), "/common.rs")); }
pub mod orders { include!(concat!(env!("OUT_DIR"), "/orders.rs")); }
```

## 11. Generated API (summary)

For each **table** `X` (with a field `field`):

- `mod x { FIXED_LEN, FIELD, FIELD_BIT, PTR_SLOTS }` — the layout (spec §3.3);
- `X<'a>` — checked reader: `X::read(buf)`, accessors that validate on demand
  (required scalar ⇒ value; optional ⇒ `Option`; pointer ⇒ `Result<…>`),
  `verify(&mut VerifyCtx)`, `X::verified(buf)` / `X::verified_with(buf, ctx)` (read +
  verify ⇒ view), `X::from_bytes(envelope)` (checks the `schema_id` and verifies),
  `X::SCHEMA_ID`;
- `XVerified<'a>` — verified view: the same accessors, without revalidating UTF-8;
  `reader()` goes back to the reader;
- `XW<'b>` — writer: `XW::root(&mut builder)`, `XW::to_bytes(&mut builder, |w| …)`
  (an enveloped message), `XW::seal(…)` (envelope in a batch), chainable setters
  (`w.id(1).ts(2)`), a table list with a count (`w.entries(n)`) or streaming
  (`w.entries_streaming()`), a nested table (`w.child()`), a union by variant
  (`w.choice_leaf()`);
- `XE` (list element descriptor) and, for a table of scalars only, `XListW`;
- at module level: `X_REQ` and `X_SCHEMA_ID`. There is no module-level `SCHEMA_ID`: the
  "root" depends on who references whom and would silently change when a new table
  referenced the old one; use `X::SCHEMA_ID`.

**Enum** `E`: `enum E { …, Unknown(base) }` with `from_raw`/`to_raw`, `Default` (raw
value 0) and `graven::Le`. **Struct** `S`: `struct S { pub fields }` (`Copy`, `Default`,
`PartialEq`, and `Eq` when there are no floats) with `graven::Le`. **Union** `U`:
`enum U<'a> { Variant(T<'a>), …, Unknown(u16) }` for the reader and
`enum UVerified<'a>` for the view.


---

<!-- source: docs/validation.md -->

# Validation

Graven is a language-neutral binary format, and its validation model is designed so
every language agrees on the same rules without changing the wire format:

- **Structural (`verify` / `from_bytes`):** checks buffer bounds, UTF-8, required fields, depth
  and budget. Runs on read to guarantee memory safety.
- **Value rules (`validate` / `validate_all` / `to_bytes_validated`):** checks domain rules
  declared in the schema (`range`, `len`, `finite`, `known`, `check(name)`). **Never runs
  automatically on read**, so old data written under looser rules stays readable.

## 1. Built-in rules (portable across languages)

Declare built-in rules directly on table fields (structs are frozen and cannot carry rules):

```graven
namespace shop;

enum Status : u8 { Active = 0, Draft = 1 }

table Product {
  #[len(min = 1, max = 64)]
  name @0: string;

  #[range(min = 1, max = 10_000_000)]
  price @1: u32;

  #[finite, range(min = 0.0, max = 100.0)]
  discount @2: f32?;

  #[known]
  status @3: Status;
}
```

| Rule | Applies to | Meaning |
|---|---|---|
| `range(min = a, max = b)` | integers (`u8`..`u128`, `i8`..`i128`) and floats (`f32`, `f64`) | `a ≤ value ≤ b` (inclusive; `NaN` fails). Either bound may be omitted. |
| `len(min = a, max = b)` | `string`, `bytes`, `[T]` | **Byte** length (`string`/`bytes`) or element count (`[T]`). Either bound may be omitted. |
| `finite` | `f32`, `f64` | Rejects `NaN` and infinities. |
| `known` | `enum` and `[Enum]` | Rejects unknown enum variants (`Unknown(_)`). |

- `len` counts **UTF-8 bytes** rather than characters, because languages disagree on code
  points vs. grapheme clusters while byte counts are exact everywhere.
- Rules on an optional field (`?`) run **only when the field is present**.
- A field's default value must satisfy its own rules.
- If a schema uses **only** built-in rules (no `check(...)`), no application hooks are needed.

## 2. Custom checks (`check(name)`)

Graven intentionally has **no expression language** (like CEL) and **no regexes** in schemas:
regex dialects and evaluators differ across languages. Instead, `#[check(name)]` declares a
named hook in the schema, and each language implements it with its own standard libraries:

```graven
namespace shop;

#[check(valid_period)]
table Promo {
  #[len(min = 1, max = 64), check(slug)]
  name @0: string;

  #[check(email)]
  contact @1: string;

  starts @2: u64;
  ends   @3: u64;
}
```

- On a **field**, `check(name)` receives the field's value (e.g. string, integer, list).
- On a **table**, `check(name)` receives the verified table view.
- A check name must always have the same input type across the schema.

### In Rust (reference implementation)

From `Promo`, `gravenc` generates a `Checks` trait in `mod shop`:

```rust
// Generated in `mod shop` (do not write this yourself):
pub trait Checks {
    fn email(&self, v: &str) -> bool;
    fn slug(&self, v: &str) -> bool;
    fn valid_period(&self, v: &PromoVerified<'_>) -> bool;
}
```

Implement `Checks` in your application (delegating to crates like `regex` or `validator`):

```rust
use shop::{Checks, Promo, PromoVerified, PromoW};

struct AppChecks;

impl Checks for AppChecks {
    fn email(&self, v: &str) -> bool {
        v.contains('@') // or delegate to `validator::ValidateEmail`
    }

    fn slug(&self, v: &str) -> bool {
        !v.is_empty() && v.bytes().all(|b| b.is_ascii_alphanumeric() || b == b'-')
    }

    fn valid_period(&self, p: &PromoVerified<'_>) -> bool {
        p.starts() < p.ends()
    }
}
```

*(If a schema has only built-in rules, `Checks` is implemented for `()` so you can pass `&()`.)*

### In other languages

The schema stays identical. Any language generator maps `#[check(name)]` to its own
interface or callback object — for example, in TypeScript (once a TypeScript generator
exists), delegating to Zod:

```ts
const checks: shop.Checks = {
  email: (v) => z.string().email().safeParse(v).success,
  slug: (v) => /^[a-z0-9-]+$/.test(v),
  valid_period: (p) => p.starts() < p.ends(),
};
```

## 3. Running validation

Validation runs only when asked:

```rust
// On write: builds, verifies structure, and runs `AppChecks` + built-in rules.
let bytes = PromoW::to_bytes_validated(&mut builder, &AppChecks, |p| {
    p.name("summer-sale").contact("hi@example.com").starts(10).ends(20);
})?;

// On read: `from_bytes` checks structure only; call `validate` when needed.
let view = Promo::from_bytes(&bytes)?;
view.validate(&AppChecks)?;                  // stops at first failure (no allocation)
let all = view.validate_all(&AppChecks)?;    // collects every failure
```

Every failure reports the table, optional field, optional list index (for `[Enum]` or `[Table]`),
and the rule that failed (`Range`, `Len`, `Finite`, `Known`, or `Check("slug")`).

Schemas without any rules generate the exact same code as before.

## 4. Evolution (`graven.lock`)

`graven.lock` records every field's rules and each table's `check`s:

- **Allowed:** rules on a new field or table; loosening a `range`/`len` bound; removing a rule or `check(name)`.
- **Warning (`rule-tightened` / `check-added`):** tightening bounds, adding a rule to an
  existing field, or adding `check(name)` to an existing field or table. Confirm with
  `#[allow_breaking_readers]` on that field or table.

## 5. Dynamic validation & `gravenc inspect`

- **`graven-dynamic`:** `Validator::new(root, schema, registry)` checks at construction time
  that every reachable `check(name)` is registered in `CheckRegistry`.
- **`gravenc inspect`:** checks built-in rules (`range`, `len`, `finite`, `known`) and
  reports each `check(name)` as `not checked`.


---

<!-- source: docs/tools.md -->

# Tools

`gravenc` is the schema compiler and also the tool for working with Graven data by hand:
looking inside files, converting to and from JSON, checking logs after a crash and
reviewing schema changes. Every data tool reads the `.graven` schema and its lockfile, so
it decodes exactly what generated code would.

| Command | What it is for |
|---|---|
| [`gravenc check`](#check) | Validate schemas and their compatibility with the lockfile (CI). |
| [`gravenc update`](#update) | Apply the compatibility rules and write the lockfile. |
| [`gravenc gen`](#gen) | Generate Rust code. |
| [`gravenc diff`](#diff) | List what changed since the lockfile, with a verdict per change. |
| [`gravenc inspect`](#inspect) | Read the messages in a file. |
| [`gravenc to-json`](#to-json-and-from-json) | Decode messages as JSON. |
| [`gravenc from-json`](#to-json-and-from-json) | Encode JSON as messages. |
| [`gravenc scan`](#scan) | Check a file of envelopes: intact records, a cut-off tail, corruption. |

Install it with `cargo install graven-compiler`, or from a clone with
`cargo install --path crates/graven-compiler`.

Exit codes are the same for every command: `0` success, `1` an error or a problem found
in the data, `2` incorrect usage.

## check

```sh
gravenc check [--locked] <schema>...
```

Parses and checks each schema and, when a lockfile exists, the compatibility of the schema
with it. Schema ids are compared across all the schemas given: two differently named tables
with the same id would make their envelopes indistinguishable, so that is an error. Nothing
is written. Schemas that the given ones import are found under their directories and
checked with them. With `--locked`, a missing or out-of-date lockfile is an
error: this is the command for continuous integration.

```sh
gravenc check --locked schemas/*.graven
```

## update

```sh
gravenc update <schema>... [--init | --from <lock>]
```

The only way a lockfile changes. `update` compares the schema with the lockfile using the
[compatibility rules](spec/graven-format-v1.md#9-schema-compatibility) and rewrites the
lockfile only when there is no error and no unconfirmed warning.

- `--init` creates the first lockfile of a new schema.
- `--from <lock>` compares against another lockfile, for a schema that was moved or
  renamed. Without either flag, a schema with no lockfile is refused, so deleting a
  lockfile can never skip the compatibility check.

## gen

```sh
gravenc gen <schema> -o <dir>
```

Writes `<dir>/<schema name>.rs`, the same code the `build.rs` API produces, plus the code of
the schemas it imports. Most projects
use `build.rs` instead; see [getting started](getting-started.md).

## diff

```sh
gravenc diff <schema> [--against <lock>]
```

A readable report of every change between the lockfile (or another lockfile given with
`--against`) and the schema, each with the verdict `update` would give. Use it to review a
schema change in a pull request.

```text
$ gravenc diff bank.graven
bank.graven compared with bank.graven.lock

table Entry
  ~ amount @1: type i64 → i32      error: type-changed

table Transaction
  ~ note @6: optional → reserved   allowed: reserved-optional
  + fee @7: i64 = 0                allowed: new-default
  + channel @8: string?            allowed: new-optional

enum Currency
  + ARS = 3                        allowed: new-enum-variant

5 change(s): 4 allowed, 1 blocking
```

Fields that only moved because an earlier field changed size are not listed separately:
the change that caused it is.

## inspect

```sh
gravenc inspect <schema> <file> [--root <Table>] [--raw]
```

Decodes every message in a file and prints it as indented JSON, with the offset and the
table of each one. A file that starts with an envelope is read as a sequence of envelopes,
and each message's table is found from its schema id. A bare message has no schema id, so
it needs `--root`. If the schema declares validation rules, `inspect` checks the built-in
rules (`range`, `len`, `finite`, `known`) and reports each `check(name)` as `not checked`.

```text
$ gravenc inspect bank.graven log.bin
#0  offset 0  bank.Transaction  129 bytes
{
  "id": 42,
  "ts": 1700000000,
  "currency": "USD",
  "from_shard": 3,
  "to_shard": 7,
  "entries": [
    {
      "account": 1001,
      "amount": -2500,
      "memo": "transfer"
    },
    {
      "account": 2002,
      "amount": 2500
    }
  ],
  "note": "rent"
}
#1  offset 129  bank.Transaction  67 bytes
…
```

Every message is fully verified before it is shown: a damaged message is reported with
its error instead of being half-printed.

## to-json and from-json

```sh
gravenc to-json   <schema> <file> [--root <Table>] [--raw] [--pretty]
gravenc from-json <schema> --root <Table> <input.json | -> -o <output | -> [--raw]
```

`to-json` prints one JSON document per message (JSON Lines), ready for `jq`, scripts or
other systems. `from-json` reads one or more JSON documents and writes them as a file of
envelopes, or as a single bare message with `--raw`. Decoding the output of `from-json`
with `to-json` gives the same documents back.

```sh
gravenc to-json bank.graven log.bin | jq 'select(.currency == "USD") | .id'
gravenc from-json bank.graven --root Transaction fixtures.jsonl -o fixtures.bin
```

The JSON follows the schema:

| Schema type | JSON |
|---|---|
| integers | numbers; `u128`/`i128` values outside the 64-bit range are decimal strings |
| `f32`, `f64` | numbers; `"NaN"`, `"inf"` and `"-inf"` for non-finite values |
| `bool` | `true` / `false` |
| enum | the variant name; a number for a value the schema does not know |
| `string` | string |
| `bytes` | lowercase hex string |
| struct, table | object, fields in declaration order |
| list | array |
| union | `{"Variant": { … }}`; `{"$tag": 5}` for a tag the schema does not know |

Absent optional fields are left out and absent fields with a default show the default.
On input, `null` is the same as leaving a field out.
`from-json` rejects documents that do not match the schema and names the place:
`document 0: Order.total: struct Money needs every field; currency is missing`.

## scan

```sh
gravenc scan <file> [--schema <schema>] [--truncate]
```

Checks a file of envelopes, such as an append-only log, from start to end. It reports how
many records are intact and what stopped the scan, if anything. With `--schema`, every
payload is also fully verified and records are counted per table.

A crash during a write leaves an incomplete record at the end of the file:

```text
$ gravenc scan orders.bin --schema bank.graven
orders.bin: 1 record(s) intact, 129 bytes
  bank.Transaction                 1
incomplete tail at offset 129: 57 bytes of a record that was cut short, which is what a crash during a write leaves behind.
Every record before it is intact. Run with --truncate to cut the file at offset 129.
```

`--truncate` removes that tail, so the file ends after the last intact record and new
records can be appended again. It never removes anything else.

Damaged data inside the file is a different situation, and `scan` says so:

```text
$ gravenc scan damaged.bin
damaged.bin: 0 record(s) intact, 0 bytes
corrupt data at offset 0: ChecksumMismatch: the record is complete but its CRC does not match (corruption).
The 0 record(s) before it are intact.
The next intact record starts at offset 129; 1 intact record(s) follow from there (129 bytes in between cannot be read).
--truncate only removes an incomplete tail, never corrupt data.
```

The distinction comes from the envelope's normative check order
([spec §8.4](spec/graven-format-v1.md#84-decoding-and-check-order-normative)): an
incomplete record and a corrupt one can never be confused.

## Editor support

The repository includes a Visual Studio Code extension in `editors/vscode` with syntax
highlighting for `.graven` schemas and `.graven.lock` files, comment toggling and bracket
matching. To install it:

```sh
cd editors/vscode
npx @vscode/vsce package
code --install-extension graven-0.1.0.vsix
```


---

<!-- source: docs/conformance-vectors.md -->

# Conformance vectors

**Download:** [all v1 vectors (`.tar.gz`)](../graven-testvectors-v1.tar.gz). The files also live in
`testvectors/v1/` in the repository.

These files define conformance with format v1. Every implementation (the Rust runtime,
the code generated by the compiler, bindings for other languages) must read each `.bin`
and obtain exactly the result in the matching `.json`.

**A frozen vector never changes; a change means format v2.** The bytes and the
expectations are normative. If a writer starts producing different bytes, the bug is in
the writer, not in the vector. A new vector may only be *added*, and only if existing
implementations already accept it.

The schema is `crates/graven-conformance/schemas/conformance.graven` (namespace
`conformance.v1`; tables `Root`, `RootV2`, `Leaf`, `Extra`, `Holder`; union `Choice`;
enum `Color`; structs `Point`, `Flags`, `Empty`). `Extra` and `Holder` were added
together with the vectors for spec §10.3 (below); the original vectors did not change.

There are 42 vectors: 11 valid, 16 invalid, and 15 added later for spec §10.3.

## Files

Each vector is a pair `<name>.bin` (bytes) + `<name>.json` (expectation).

### Valid

| vector | content |
|---|---|
| `minimal` | Only the required fields (`a_u8 = 42`, `flag2 = true`); the absent `a_u32` reads as its default 7. |
| `all_fields` | Every field of `Root` present: integers at their extremes, floats, bool, enum, struct, multi-byte UTF-8 string, bytes, every list, `child` with `next` nested 2 levels deep, `choice` with tag 1. |
| `zero_is_present` | Every optional scalar present with value 0 (a present `a_u32 = 0` is 0, not the default 7); `false` bools present. |
| `empty_lists` | Every list present and empty, plus `name = ""` and an empty `blob` (present ≠ absent). |
| `streaming_leaves` | `leaves` written with `tables_streaming`: strings and nested tables come before the list header, so element pointers are negative (backward). |
| `unknown_enum` | `color = 9` (outside `Color`): reads as the raw value 9. |
| `unknown_union_tag` | `choice` with tag 5 (unknown) pointing to a real `Leaf`: reads as `{tag: 5, value: {}}`, payload not visited. |
| `v2_read_by_v1` | Written with `RootV2` (`extra` present), read with `Root`: `extra` ignored. |
| `v1_read_by_v2` | Written with `Root`, read with `RootV2`: `extra` absent. |
| `reserved_ignored` | Written by an old writer whose `Root` still had `old @21: u32?` (slot 21 filled, bit set); read with `Root` without error and without the field. |
| `enveloped_all_fields` | `all_fields` inside an envelope with the schema id of `conformance.v1.Root`. |

### Invalid

Each invalid vector has **exactly one** defect: it is a valid message (the "base") with
a single mutation. For mutations of the envelope header the CRC is recomputed, so the
only defect is the altered byte.

Error precedence:

- **message/payload**: precedence between errors when there are several defects is
  **not** normative (that is why each vector has a single defect);
- **envelope**: the check order **is** normative: header length (20) → magic → version
  → flags/reserved → `payload_len` (complete input) → CRC. Only after that come the
  schema id and the payload read.

Offsets below are byte offsets from 0.

| vector | base | mutation | error |
|---|---|---|---|
| `truncated_slot` | `minimal` | root `fixed_len` 112 → 66 (bytes 0..2), cutting the 8-byte `point` slot in half (fixed-part bytes 62..70) | `Truncated` |
| `bad_offset` | `minimal` | `name` pointer (byte 72) goes from 0 to 42: points to 114 = one past the end | `BadOffset` |
| `string_len_oob` | `minimal` + `name = "grvn"` | string length (byte 114) 4 → 5: one byte past the end | `OutOfBounds` |
| `bad_utf8` | `minimal` + `name = "grvn"` | first byte of the string (byte 118) `g` → `0xFF` | `InvalidUtf8` |
| `missing_required` | `minimal` | presence bit of `a_u8` (byte 2, bit 0) cleared | `Missing` |
| `self_cycle` | `minimal` + `child = {n: 5}` | `child.next` (bytes 125..129), previously null, points to `child` itself (−11) | `DepthExceeded` |
| `budget_amplification` | `minimal` + 1000 `leaves`, only `leaves[0].s` = a 2048-byte string | the `s` of the other 999 elements now points to the same string | `BudgetExceeded` |
| `env_bad_magic` | `minimal` in an envelope | byte 0 `G` → `X`, CRC recomputed (bytes 134..138) | `BadMagic` |
| `env_bad_version` | same | byte 4 (version) 1 → 2, CRC recomputed | `UnsupportedVersion` |
| `env_bad_header` | same | byte 5 (flags) 0 → 1, CRC recomputed | `BadHeader` |
| `env_cut_header` | same | cut at 10 bytes (the header has 20) | `Incomplete` |
| `env_cut_payload` | same | cut at 30 bytes (middle of the payload) | `Incomplete` |
| `env_cut_crc` | same | last 2 bytes (half of the CRC) removed | `Incomplete` |
| `env_bitflip_payload` | same | byte 23 (value of `a_u8` in the payload) 42 → 43 | `ChecksumMismatch` |
| `env_bitflip_crc` | same | byte 137 (last byte of the CRC) xor `0x80` | `ChecksumMismatch` |
| `env_wrong_schema` | same | well-formed envelope (valid CRC) with the schema id of `conformance.v1.Leaf` | `SchemaMismatch` |

### Added: spec §10.3 rules

Vectors for rules that had none. The `Extra` ones use `pick` = `Leaf {n: 1}` (a required
union). All are built byte by byte (`crates/graven-conformance/src/vectors.rs`,
`spec_10_3_cases`).

| vector | reader | message | result |
|---|---|---|---|
| `bool_struct_and_lists` | `Extra` | `flags = {on: 0x02, c: 1}`, `bools = [00, 01, 07]`, `colors = [0, 2, 9]` | value: `on = true`, `bools = [false, true, true]`, `colors = [0, 2, 9]` (9 unknown, raw value) |
| `strlist_null_elem` | `Extra` | `names = ["a", <pointer 0>, "c"]`, `blobs = [<pointer 0>]` | value: `["a", "", "c"]`, `[[]]` |
| `union_tag_null_ptr_optional` | `Root` | `minimal` + `choice` tag 1 with pointer 0 | value: `choice` absent |
| `union_tag_null_ptr_required` | `Extra` | `pick` tag 1 with pointer 0 | `Missing` |
| `union_unknown_tag_bad_ptr` | `Root` | `choice` tag 5 (unknown) with a pointer one past the end | `BadOffset`: the pointer is checked even though the payload is not visited |
| `reserved_slot_partial` | `Extra` | `fixed_len` cutting the reserved slot `@8` in half | value: no error; `tail` (after the cut) absent |
| `ptr_slot_partial` | `Extra` | `fixed_len` cutting the pointer slot of `tail` in half | `Truncated` |
| `zero_size_slot_at_end` | `Extra` | `e: Empty` present, `fixed_len` = offset of `e` (`o == fixed_len`) | value: `e` present (the bit decides, §4.2) |
| `table_list_elem_wider` | `Holder` | `[Leaf]` with `elem_fixed_len` = layout + 8 | value: the `Leaf`s, extra bytes ignored |
| `table_list_elem_narrower` | `Holder` | `[Leaf]` with an `elem_fixed_len` covering only `n` | value: `Leaf` without `s`/`next` |
| `table_list_elem_zero` | `Holder` | `table_list_elem_narrower` with `elem_fixed_len = 0` | `Missing` (`Leaf.n` is required and no element has room for it) |
| `env_concat` | `Root` | envelope of `minimal` followed by an envelope of `all_fields` | value: `minimal` (bytes after the CRC are not an error, §8.6) |
| `env_payload_len_short` | `Root` | `minimal` in an envelope with `payload_len` − 1 and a CRC valid for the smaller frame | `OutOfBounds` (well-formed envelope; the message lost its last byte) |
| `env_payload_len_short_inplace` | `Root` | `minimal` in an envelope with `payload_len` − 1 corrupted in place (CRC intact) | `ChecksumMismatch`: the CRC is read one byte early, over the wrong range; a shorter payload is never accepted |
| `env_payload_len_long` | `Root` | `payload_len` + 1, past the end of the buffer | `Incomplete` |

`budget_amplification` is ~15 KiB, so its verification budget is the 1 MiB floor
(`max(len × 8, 1 MiB)`); the charges add up to ~2 MiB (1000 × `4 + 2048`).

## How to read a vector

1. If `enveloped`: decode the envelope (envelope errors); if the envelope's schema id
   ≠ the 64-bit FNV-1a of `schema` ⇒ `SchemaMismatch`; the payload is the message.
2. Read the message with the reader schema `schema` and verify it entirely (equivalent
   to `Root::read(buf)` + `verify(&mut VerifyCtx::new(buf.len()))`: depth 64, budget
   `max(len × 8, 1 MiB)`).
3. Compare with `expect`.

## `.json` format

```json
{
  "schema": "conformance.v1.Root",
  "enveloped": false,
  "expect": { "value": <Value> }
}
```

or `"expect": { "error": "<Variant>" }`, where `<Variant>` is just the name of the
`graven::Error` variant: `OutOfBounds`, `Truncated`, `BadOffset`, `InvalidUtf8`,
`Missing`, `DepthExceeded`, `BudgetExceeded`, `BadMagic`, `UnsupportedVersion`,
`BadHeader`, `Incomplete`, `SchemaMismatch`, `ChecksumMismatch` (without the variant's
data).

- `schema`: the qualified name of the **reader** schema (for example
  `conformance.v1.Root` or `conformance.v1.RootV2`).
- `enveloped`: `true` if the `.bin` is an envelope.

### `<Value>` encoding

Externally tagged enum: every value is a single-key object named after the variant.
Numbers JSON cannot represent exactly are written as strings.

| value | JSON |
|---|---|
| bool | `{"Bool": true}` |
| unsigned integer, enum | `{"UInt": "7"}` (decimal, up to `u128`) |
| signed integer | `{"Int": "-7"}` (decimal, up to `i128`) |
| `f32` | `{"F32": "f32:0x3fc00000"}` (IEEE-754 bits, 8 lowercase hex digits) |
| `f64` | `{"F64": "f64:0x8000000000000000"}` (bits, 16 lowercase hex digits) |
| string | `{"Str": "hi"}` |
| bytes | `{"Bytes": "00ab"}` (lowercase hex, 2 digits per byte) |
| list | `{"List": [ … ]}` |
| table or struct | `{"Table": {"field": …}}` (sorted keys) |
| union | `{"Union": {"tag": 1, "value": {"Table": {…}}}}` |

Rules for a table's map:

- an absent optional field does **not** appear;
- an absent field with a default (`a_u32 = 7`) appears with the default;
- enums are `UInt` with the raw value (unknown ones included);
- reserved fields never appear;
- unknown union tag: `{"tag": N, "value": {"Table": {}}}`.

Equality is exact: floats compare by bits (`0.0 ≠ -0.0`). The reference is the
documentation of the `graven-conformance` crate (`crates/graven-conformance/src/lib.rs`).

## Regenerating / checking

The vectors are produced by `crates/graven-conformance/src/vectors.rs` (`cases()`).

```sh
cargo run -p graven-conformance --bin gen-vectors              # writes missing ones; refuses to change existing ones
cargo run -p graven-conformance --bin gen-vectors -- --check   # writes nothing; fails if anything is missing or differs
cargo test -p graven-conformance --test conformance            # bytes == cases(), read == .json, no orphans
```

`--force` overwrites differing files and prints a prominent warning. **Do not use it on
`v1`**: the v1 vectors are frozen, and changing them means format v2. A read error on an
existing file other than "not found" makes `gen-vectors` fail; it is never treated as a
missing file.


---

<!-- source: docs/benchmarks.md -->

# Benchmarks

The reference implementation compared with FlatBuffers and Cap'n Proto on the same data.
These numbers come from one machine and one run. Treat them as a measurement of this
implementation, not of the format in general, and run them on your own hardware before
relying on them. How we got to these numbers is in [History](history/index.md).

## Setup

| | |
|---|---|
| Machine | Intel Core i9-14900HX (32 threads), Linux 7.3 (CachyOS) |
| Compiler | rustc 1.94.0, `--release` |
| Libraries | flatbuffers 25.12.19 (flatc 25.12.19), capnp 0.27.3 (capnp 1.5.0), criterion 0.8.2 |
| Run | `--warm-up-time 1 --measurement-time 3`, median of the samples; run-to-run noise is about ±5% |
| Date | 2026-11-13 |

To reproduce:

```sh
cargo bench -p graven-bench --bench codec
cargo run --release -p graven-bench --bin sizes
cargo run --release -p graven-bench --bin allocs
```

### Scenarios

The same four messages are implemented in all three formats, and a test
(`crates/graven-bench/tests/equivalence.rs`) checks that every implementation reads the same
values for 20 random seeds per scenario.

| scenario | message |
|---|---|
| `bank/N` | a transaction with N entries, each with an optional memo string |
| `frame/N` | a game frame with N entities (position, velocity, health, flag) |
| `telemetry` | one IoT reading: five scalars, one optional |
| `chunk/N` | a stream chunk carrying N bytes of payload |

### Keeping the comparison fair

- **Reused contexts.** Graven reuses its `Builder`, FlatBuffers its `FlatBufferBuilder`
  (`reset()`), Cap'n Proto its scratch allocator.
- **Same output contract.** The `graven` write column hands out a borrowed slice, as
  FlatBuffers' `finished_data()` and Cap'n Proto's output `Vec` do. `graven_owned` returns an
  owned, reference-counted buffer per message; `graven_batched` packs messages into one
  buffer for sending.
- **Lists.** Cap'n Proto must know a list's length before writing it. `graven` in `bank`
  writes the list as a stream, without knowing its length; `graven_known` passes the
  length, as Cap'n Proto does.
- **Strings.** Graven validates UTF-8 on every read in its default mode. FlatBuffers'
  `root_unchecked` and Cap'n Proto do not. `graven_trusted` reads a message that was already
  verified, without validating again.
- **Verification.** FlatBuffers' verifier and Graven's `verify` walk the whole message
  before reading. Cap'n Proto checks lazily, while reading, and does not validate UTF-8, so
  its verified column is not the same amount of work.

## Size

Bytes per message. Smaller is better.

| scenario | Graven | FlatBuffers | Cap'n Proto | Cap'n Proto packed |
|---|---:|---:|---:|---:|
| bank/1 | 118 | 168 | 144 | **106** |
| bank/10 | 418 | 576 | 480 | **352** |
| bank/100 | 3607 | 4536 | 4080 | **2977** |
| frame/10 | 331 | 488 | 360 | **322** |
| frame/500 | **15521** | 20104 | 16040 | 15827 |
| telemetry, with humidity | **24** | 48 | 40 | 28 |
| telemetry, without humidity | 24 | 48 | 40 | **23** |
| chunk/64 | **87** | 112 | 104 | 90 |
| chunk/65536 | **65559** | 65584 | 65576 | 65626 |

Graven is smaller than FlatBuffers and unpacked Cap'n Proto everywhere. Packed Cap'n Proto
is smaller for messages with many small integers, and pays CPU time to pack and unpack.

## Allocations

Allocations per written message, after warm-up.

| scenario | Graven (stream) | Graven (known) | FlatBuffers | Cap'n Proto |
|---|---:|---:|---:|---:|
| bank/100 | 0 | 0 | 0 | 1 |
| frame/500 | 0 | 0 | 0 | 1 |
| telemetry | 0 | 0 | 0 | 1 |
| chunk/65536 | 0 | 0 | 0 | 1 |

## Time

Nanoseconds per message, median. Lower is better; bold is the fastest.

### Writing

| scenario | Graven (stream) | Graven (known) | FlatBuffers | Cap'n Proto |
|---|---:|---:|---:|---:|
| bank/1 | 31.4 | **22.9** | 56.3 | 57.0 |
| bank/10 | 85.6 | **56.6** | 343.1 | 82.1 |
| bank/100 | 632.4 | **378.2** | 3130.9 | 414.7 |
| frame/10 | **26.3** | | 333.8 | 61.9 |
| frame/500 | **777.4** | | 17751.0 | 876.4 |
| telemetry | **6.0** | | 21.5 | 33.8 |
| chunk/64 | **9.7** | | 20.0 | 44.0 |
| chunk/65536 | **966.4** | | 1731.6 | 2819.6 |

Only `bank` has a list whose length can be unknown; in the other rows the first column is
the only Graven measurement.

Owned and batched messages:

| scenario | borrowed | batched | owned |
|---|---:|---:|---:|
| telemetry | 6.0 | 7.1 | 22.6 |
| chunk/64 | 9.7 | 11.4 | 27.5 |
| frame/500 | 777.4 | 951.9 | 926.0 |

An owned message pays an atomic reference count; batching amortizes it over many messages.
A large owned message is also slower than a borrowed one because it needs fresh memory
instead of rewriting the same cache-hot buffer.

### Reading every field

| scenario | Graven | Graven (trusted) | FlatBuffers (unchecked) | Cap'n Proto |
|---|---:|---:|---:|---:|
| bank/1 | 18.8 | **7.5** | 22.6 | 67.7 |
| bank/10 | 57.9 | **23.6** | 79.3 | 111.9 |
| bank/100 | 476.0 | **194.6** | 685.4 | 633.4 |
| frame/10 | **58.9** | | 122.6 | 96.1 |
| frame/500 | 2414.5 | | 6433.0 | **2296.1** |
| telemetry | **1.4** | | 10.6 | 34.5 |
| chunk/64 | **2.4** | | 7.1 | 45.9 |
| chunk/65536 | **2.4** | | 7.0 | 45.9 |

### Reading one field

| scenario | Graven | FlatBuffers | Cap'n Proto |
|---|---:|---:|---:|
| bank/1, /10, /100 | **1.3–1.4** | 2.3 | 32.3 |
| frame/10, /500 | **2.5–2.6** | 4.1–4.2 | 41.7–42.4 |
| telemetry | **1.3** | 2.2 | 32.7 |
| chunk/64, /65536 | **1.2** | 2.3 | 32.6 |

### Verifying and reading every field

| scenario | Graven | FlatBuffers | Cap'n Proto (lazy) |
|---|---:|---:|---:|
| bank/1 | **28.7** | 114.6 | 66.5 |
| bank/10 | **86.5** | 466.4 | 111.8 |
| bank/100 | 712.4 | 4084.4 | **620.3** |
| frame/10 | **67.5** | 557.6 | 94.9 |
| frame/500 | 2705.1 | 27858.0 | **2250.2** |
| telemetry | **3.2** | 51.6 | 33.9 |
| chunk/64 | **4.7** | 39.0 | 45.4 |
| chunk/65536 | **4.6** | 38.7 | 45.3 |

## The envelope

The optional [envelope](spec/graven-format-v1.md#8-envelope) adds 24 bytes and a CRC32C over
the whole message.

| scenario | write, owned | write, enveloped | verify + read one field | `from_bytes` + read one field |
|---|---:|---:|---:|---:|
| telemetry | 21.8 | 32.0 | 2.4 | 12.0 |
| chunk/64 | 26.4 | 39.2 | 2.6 | 12.6 |
| bank/10 | 70.3 | 108.8 | 61.1 | 87.9 |
| chunk/65536 | 1567.2 | 2549.4 | 2.6 | 1622.1 |

Verification does not touch payload bytes, so a 64 KiB chunk verifies in under 3 ns; the
CRC reads all of them. For small messages the envelope costs about 10 ns on each side.

CRC32C throughput, hardware instruction against the portable software version (used
without `std`):

| size | hardware | software |
|---|---:|---:|
| 64 B | 6.0 ns | 11.7 ns |
| 1 KiB | 29.7 ns | 347.7 ns |
| 64 KiB | 1614.1 ns (≈ 40 GB/s) | 23463.0 ns (≈ 2.8 GB/s) |

## Where Graven loses

- **Size against packed Cap'n Proto** for messages made of many small integers.
- **Reading every field of `frame/500`** against Cap'n Proto: 2414 ns against 2296 ns, about 5%,
  within the noise of one run.
- **Verified reading of large messages** (`bank/100`, `frame/500`) against Cap'n Proto,
  whose check is lazy and skips UTF-8; against FlatBuffers' full verifier Graven is 6–10×
  faster.
- **Writing a list of unknown length** costs 1.4–1.7× a list whose length is known.


---

<!-- source: docs/testing.md -->

# Testing

## On every change

```sh
cargo test --workspace                       # ~1 min
cargo test -p graven --no-default-features   # no_std runtime
cargo clippy --workspace --all-targets
target/debug/gravenc check --locked $(find crates -name '*.graven' -not -path '*/tests/compat/*' -not -path '*/evo/*')
for f in crates/graven-schemas/schemas/evo/*.graven; do target/debug/gravenc check --locked "$f"; done
```

`cargo test` covers:
- the frozen vectors (`testvectors/v1/`, 42 vectors) against the conformance interpreter
  and against the generated code;
- the mutation gates (every single-byte mutation of every vector is read identically by
  the interpreter and the generated code);
- the `bank` v1/v2/v3 evolution matrix (`crates/graven-schemas/tests/evolution_matrix.rs`);
- the compiler's compatibility corpus, including version chains.

## Fuzzing (nightly + `cargo-fuzz`)

```sh
cargo install cargo-fuzz      # once
scripts/fuzz.sh               # 600 s per target, all 5 in parallel
scripts/fuzz.sh 60 read       # one target, 60 s
```

Targets run with `-O -a` (optimized, with debug assertions and overflow checks).

| target | what it guarantees |
|---|---|
| `read` | `read` of every root plus every accessor, over arbitrary bytes, never panics |
| `verify` | `verified` plus a walk of the verified view never panics |
| `envelope` | `decode`/`envelopes` never panic; the iterator stops at the first error; round trips are stable |
| `differential` | if `verified` accepts, the verified view reads exactly the same as the checked reader and as `reader()`, with no errors |
| `schema` | `parse` → `check` → `generate` never panic (arbitrary text and mutations of valid schemas) |

Roots covered:
- `conformance::{Root, Extra, Holder}`;
- `edge::Edge`;
- `bank::Transaction`, `game::Frame`, `iot::Telemetry`, `stream::Chunk`.

The seed corpus is the vectors and the repository's `.graven` files. A crash lands in
`fuzz/artifacts/<target>/`. For each finding:
1. minimize it with `cargo +nightly fuzz tmin <target> <file>`;
2. store the input in `fuzz/regressions/`;
3. write a regression test in `cargo test`;
4. fix the cause.

In the walkers (`fuzz/src/lib.rs`), each list is walked up to `MAX_ELEMS` elements.
Without `verify`, a `[Table]` with `elem_fixed_len = 0` can announce ~2³² elements in a
few bytes. That is legal for lazy reads (spec §7.1); `verify` stops it through the
budget.

Recommendation: before each release, run ≥ 1 h per target (`scripts/fuzz.sh 3600`).

## Miri (nightly)

```sh
scripts/miri.sh               # ~25 min on a desktop machine
```

Packages and configuration:
- Miri runs over `graven`, `graven-layout`, `graven-schemas`, `graven-codegen-tests` and
  `graven-conformance`.
- In `graven-compiler`, it runs over `--lib`, `parse`, `check`, `compat`, `lock` and
  `names`.
- Flags: `-Zmiri-strict-provenance -Zmiri-disable-isolation`. proptest writes
  regression files, so isolation is disabled.

Under `cfg(miri)` the mutation gates and proptest use smaller samples: the code exercised
is the same, with fewer cases. No test of `Verified`, `VListR`, `VStrList`,
`str_unchecked` or the envelope is skipped.

Two compiler test files stay out of Miri (the compiler has no `unsafe`):
- `cli.rs`, because it spawns processes;
- `codegen.rs`, because `prettyplease` over whole schemas takes hours under Miri.


---

<!-- source: docs/future.md -->

# The future

Graven is a small thing on purpose: a frozen wire format, a schema language with
enforced evolution, and a way to prove an implementation correct. Small foundations travel
far. This page describes where it can be applied, what already works for each area today,
and what would still need to be built. Nothing here is a promise or a schedule; it is a
map of where the format fits.

## Records that have to outlive their software

Accounting entries, invoices, fiscal documents, contracts, medical and audit records:
data that is written once, must never silently change meaning, and may have to be read
decades later, by software that does not exist yet.

**What already fits.** The format is frozen and specified down to the byte, with public
conformance vectors, so a record can be decoded without the program that wrote it. Each
envelope carries its schema id and a checksum, append-only files survive crashes, and
[`gravenc scan`](tools.md#scan) tells a cut-off write from real corruption.

**What would make it go further.** Archival conventions on top of the format: a manifest
that stores the schemas next to the data, periodic integrity reports, and signed
envelopes for records that must be tamper-evident.

## Libraries and SDKs shipped to other people

When code runs at a customer's site, you no longer choose when it upgrades. Ten versions
of a client may be talking to the same server at once.

**What already fits.** The lockfile and the compatibility rules guarantee that old and new
code read each other's messages without guessing; changes that would break that are
refused at build time, and [`gravenc diff`](tools.md#diff) shows the verdict of every
change before it ships.

**What would make it go further.** Implementations in the languages SDKs are written in,
such as TypeScript, Python, Go, Java, Kotlin, Swift and C#. Each one is measured against
the same 42 vectors, so "compatible" means the same thing everywhere.

## Event streams and messaging

Payloads for Kafka, NATS, queues and webhooks are produced by one team and consumed by
many, often long after they were written.

**What already fits.** The schema id in every envelope identifies the payload without a
side channel. A consumer verifies a message once and reads fields in place, so routing
or filtering by one field does not decode the rest.

**What would make it go further.** A schema registry that serves lockfiles by schema id,
and connectors for common brokers.

## Storage engines, caches and indexes

Values in key-value stores, rows in embedded databases, memory-mapped files.

**What already fits.** Reads are zero-copy: a value fetched from storage, or a page of a
memory-mapped file, can be read field by field without allocation. Reading one field of
a large record costs only that field.

**What would make it go further.** Export of envelope files to columnar formats such as
Apache Arrow and Parquet for analytics, and secondary-index helpers that extract fields
without full decoding.

## Devices at the edge

Point-of-sale terminals, scales, sensors and vehicles that collect data while offline and
send it in batches when they can.

**What already fits.** The format needs no allocator and no alignment, the Rust runtime is
`no_std` with two dependencies, and envelopes can be concatenated into a batch that the
receiving side checks record by record.

**What would make it go further.** A C implementation for microcontrollers, and a
store-and-forward library that persists a queue of envelopes on flash.

## Web applications

Browsers and web servers exchange JSON because it is everywhere, not because it fits:
every response is parsed in full, numbers lose precision past 2^53, and nothing stops a
newer server from sending a shape that an older tab, still open since yesterday, cannot
read.

**What already fits.** The browser already speaks binary: `fetch` returns an
`ArrayBuffer`, and WebSocket and WebTransport carry binary frames. Graven is little-endian
with no alignment, which is exactly what a `DataView` reads, so a client can read fields
in place from the response. Because the format is fully specified, nothing about it
depends on Rust. The compatibility rules cover the case JSON leaves to discipline: old
tabs keep working while the server moves ahead. `verify` protects the client from a
malformed response, and the schema id in the envelope says what arrived.

**What would make it go further.** A TypeScript implementation (runtime, `verify`,
envelope) with a code generator that reads the lockfile and emits typed readers and
writers, held to the same 42 vectors in the browser and in Node. A native implementation
suits the browser better than the Rust runtime compiled to WebAssembly, where every field
access would cross the JavaScript boundary and strings would be copied. A browser
DevTools panel would show binary responses as readable data.

**What to expect.** `JSON.parse` is highly optimized native code, so the gain is largest
for large messages, or when only a few fields of a response are read. With gzip or brotli
the size gap to JSON narrows. 64-bit integers become `BigInt` in JavaScript, which is
exact but less convenient than `number`.

## Plugins and sandboxes

Extensions written by third parties, often compiled to WebAssembly, that exchange data
with the host application.

**What already fits.** Buffers cross the boundary as bytes, with no shared object model,
and `verify` lets the host accept whatever a plugin returns without trusting it: depth
and total work are bounded, so a hostile buffer can only produce an error.

**What would make it go further.** A small guest-side library for WebAssembly modules and
a documented calling convention.

## Games and real-time state

Snapshots, replays, save files and network state, where reading must be fast and old
saves must still load after an update.

**What already fits.** Reading in place suits frame-by-frame state, and schema evolution
keeps old save files readable. The repository's `game` schema is used in the benchmarks.

**What would make it go further.** Delta encoding between snapshots, which would be a
library on top of the format rather than a change to it.

## Interchange between languages and teams

Data shared across services written in different languages, where JSON is used today
because it is everywhere.

**What already fits.** The schema language is language-neutral, the lockfile records every
layout a code generator needs, and [`gravenc to-json` and `from-json`](tools.md#to-json-and-from-json)
bridge to systems that only speak JSON. [Coming from JSON](coming-from-json.md) shows the
translation.

**What would make it go further.** Code generators for more languages, and importers from
JSON Schema, Protocol Buffers or OpenAPI definitions that produce a first `.graven` file.

## How the format itself can evolve

Format v1 is frozen and will stay readable for good. Ideas that do not fit in v1 are
candidates for a future version, announced by a new `format_version` in the envelope, and
v1 messages remain valid alongside it:

- lists of lists and lists of unions;
- a native map type;
- optional compression of the envelope payload.

Each would come with its own frozen vectors, under the same rules as v1.

## Taking part

The most valuable contribution is an implementation in another language. The
[specification](spec/graven-format-v1.md) is the reference, the
[conformance vectors](conformance-vectors.md) are the test, and an implementation that
reads all 42 vectors correctly is a conforming one.