The guide

README.md is a thin pointer. This is where the depth lives: what the language is, why it’s built this way, what exists, and an index of every design document. History — what shipped when, and what each slice found, including corrections — is ROADMAP.md. Neither belongs in the index below, which says what each document settles, not how it got there.

Design lands here before the code that implements it, which is the cheap place for it to be wrong. When it turns out wrong anyway, the document that made the claim is corrected in place rather than quietly edited — ROADMAP.md says which.

Where this came from

cancho began as the lower-level sibling of Lex, a high-level, interpreted language, and took its worldview from it: ownership and authority as one system, defined behaviour, a canonical content-addressable syntax tree. That is history. cancho stands on its own now: it has its own compiler, its own standard library, its own packages and its own tools (cancho authority, cancho-vcs, the products listed in the repositories of this organisation), and it depends on nothing from Lex or from lex-os, the agent runtime Lex had. If a runtime that confines a program to what its authority report says is needed, it is built in cancho, from the report the compiler already writes.

The documents that compared the two (vcs.md, under-a-grant.md, related-work.md) are kept as the record of what was measured and decided; they are not a plan to integrate with Lex.

Why

Three things this philosophy buys that no systems language currently combines:

1. Capabilities all the way down. Ownership and effects are the same idea — both are resource tracking. Allocation is an effect, a heap value is a linear resource, FFI is a capability you must be granted. Owning a capability discharges its effects and borrowing declares them, so main’s row is [] however much it does.
2. Determinism as a language property. No UB, defined evaluation order, deterministic layout — which is what makes replay, attestation and content-addressing mean anything, and exactly what C throws away. Written out operation by operation in defined-behaviour.md.
3. A checker that is fast and total, because the guarantee is only worth what it costs to verify.

What exists

What is not there yet, and why, is ROADMAP.md.

The language in one page

A value is res or val. A res value is consumed exactly once on every path. Mode is structural — a res member makes the whole aggregate res — so Held[File] is res where Held[int] is val.

res struct Ticket { serial: int }

fn redeem(t: Ticket) -> [] int {
    let Ticket { serial } = t;      // the whole is spent, the parts produced
    return serial;                  // `int` is `val`, so nothing is owed now
}

There is no drop and no destructor: a resource is destroyed by naming the function that knows how, which is what keeps an effect row honest once there are effect rows.

Looking without spending is a borrow. borrow freezes for a read, borrow mut locks for a write — nothing else may touch the value at all, not even a read.

fn serial_of[&r](t: &r Ticket) -> [] int { return t.serial; }

borrow held as &r in {
    putchar(i, 48 + serial_of(r));    // `held` is frozen; `r` reads it
}                                     // owned again here

There is no borrow checker. A region is a block, so a reference’s validity is lexical rather than inferred: no non-lexical lifetimes, no variance, no dataflow. A binding is Owned, Frozen or Locked, set at block entry and restored at block exit; r_inner <= r_outer holds exactly when the outer block encloses the inner one, which is a walk up a stack; and escape is an occurs-check over one type.

An effect is a borrowed capability.

fn triple(n: int) -> [] int { return n * 3; }                // pure, and says so
fn show[&i](io: &!i Io, n: int) -> [io_write] int { ... }    // borrows the console

fn main(world: World) -> [] int {
    let Split { io, ffi, fs, heap, args } = split(world);    // the one source of authority
    release(args); release(heap); release(fs); release(ffi); // unused authority is still a resource
    borrow mut io as &!i in { show(i, 7); }
    release(io);                                             // destroyed exactly once
    return 0;
}

[io_write] on a signature means the function was handed an &!i Io it did not create — so reading the row and reading the parameter list are the same act, and a function that was given nothing cannot print however much it wants to. There is no ambient constructor: Io { } is refused, main’s World is the only authority in the program, and it is linear, so forgetting to release it does not compile.

main’s own row is [] even though it prints, because it owns the capability rather than borrowing one — and ownership is already visible in the parameter list.

A row is a canonically ordered set, so it hashes, which is what per-unit identity is made of. It is exact in both directions: performing an effect you did not declare and declaring one you never perform are both errors, because an inexact row means [] stops meaning pure. And there is no list of legal labels — every label traces back to a builtin that performs one, so a label with nothing underneath it is refused the moment it is written.

A foreign call is the same idea pointed at C.

extern fn labs[&f](ffi: &f Ffi("libc"), n: int) -> [ffi("libc")] int;

let libc = narrow(ffi, "libc");        // `Ffi("")` -> `Ffi("libc")`, one way only
borrow libc as &f in { n = labs(f, 0 - 7); }

Narrowing is prefix extension and goes one way. Ffi("") names no library, so it authorises nothing until narrowed; an Ffi("libcrypto") can never become an Ffi("libc"). It also consumes what it attenuates, so there is no way back to the wider capability. The capability is checked and then erased: what libc receives is the integer and nothing else.

Memory has three shapes, and the same region machinery checks all of them.

region a {                                   // an arena: released in one call
    let xs = alloc_slice[a](5, 0);           // xs : &!a [int]
    xs[0] = 3;                               // bounds-checked; out of range traps
}

let node = box(h, Node { value: 1 });        // the heap: `Box[T]` is `res`
let tail = unbox(h, node);                   // the only thing that ends one

An arena is a region — same block, same parent chain, same occurs-check. Nothing whose type mentions a leaves the block, and release is one free whatever was allocated. Box[T] is res, so the exactly-once rule written for capabilities and file handles turns out to be a memory safety rule for free: no leaks, no double frees, no use-after-free, none of them checked by anything new.

A string is a run of bytes and claims no encoding. str is not a type; a string is &r [byte], an ordinary slice and therefore an ordinary reference, so regions, the escape check and the unique-to-shared coercion all came for free.

Arithmetic is checked. +, -, * and unary - produce the right answer or trap — they never wrap. Wrapping is expressible but has to be asked for by name. Division traps on a zero divisor and on int::MIN / -1 rather than being undefined. Evaluation order is left to right everywhere, including a struct literal’s fields, and that is enforced rather than merely intended.

Real programs run on this, byte-for-byte checked against the originals: GNU coreutils base64 and sort (porting.md), a REST endpoint answered over a real socket (net.md), and examples/seek/, not a port — a search tool shaped for an agent calling it rather than a person typing at a shell (agent-tools.md).

Related work

cancho builds on other people’s ideas, and the closest of them got there first.

• Austral — the nearest relative: linear types, capabilities as linear values with a root capability handed to the entry point, lexical borrowing, no borrow checker. Most of this core is Austral’s first. cancho adds the same authority stated as an exact effect row, which is what cancho authority reads.
• Koka — effects as a row of labels. Kept the row; no handlers, no row polymorphism.
• Effekt — effects as capabilities, from the effect-handler side: the closest statement of “an effect is a borrowed capability”.
• Cyclone — lexical regions; here without Rust’s inference.
• Rust — ownership as move; the borrow checker declined.
• Vale — generational references, which Gen is.
• Zig — defer.
• Pony, Hylo — other answers to aliasing and ownership. Pony’s val means something different from this one.
• The object-capability model (E, Robust Composition) and Capsicum — no ambient authority.
• Lex — where the worldview came from (history; cancho no longer depends on it).

The competitor is WASI, not Rust. For running code you did not write, WebAssembly with WASI enforces authority at run time, by trying. cancho knows it before execution, from the program’s text, with no runtime cost. What each project contributed, traced to the document that used it: related-work.md.

Design commitments

Taken from Lex’s design, long ago: examples-as-tests, [budget], effect declarations as the function’s contract.

Explicit non-goals

• Not a Rust clone. No trait-system maximalism, no GATs, no specialisation, no borrow checker. Chasing Rust’s power means inheriting Rust’s implementation cost and abandoning totality — the failure mode this design exists to avoid.
• Not self-hosting-first. The compiler started in Rust, as a starting point, not an end-state; it is now being written in cancho itself, stage by stage, with the Rust compiler as the check at each one (self-hosting.md).

Performance

Linearity and effects are erased at compile time; generics monomorphise. The gap to C is a backend question, not a price of ownership: Rust sits within 4% of C on the same kernels (against-c-and-rust.md), and once the overflow trap and a vectorising backend (--backend llvm, now the default) are both in place, this language measures statistically indistinguishable from C on the one kernel checked directly against it.

The derivation — what the trap costs, what each backend can and cannot express, and every kernel measured — lives where it was measured rather than restated here: overflow-cost.md, check-cost.md, backend-limits.md, llvm-backend.md, benchmarks-game.md.

Layout

crates/cancho-syntax    lexer, canonical-shaped AST, parser
crates/cancho-types     the type vocabulary: representation and unification
crates/cancho-ir        resolution, type checking, monomorphisation; the IR
crates/cancho-codegen   Cranelift lowering, native object emission
crates/cancho-codegen-llvm  the LLVM backend, --backend llvm (default)
crates/cancho-id        canonical encoding and content hashes
crates/cancho-vcs       content-addressed operation log (vcs.md)
crates/cancho           the CLI
std/                     the standard library, as Lex source
examples/                programs meant to be read
packages/                published cancho-vcs packages (package-system.md)
tests/accept             fixtures that must compile and run
tests/reject             fixtures that must be refused, each stating why
benches/                 checked/wrapping pairs; what the overflow trap costs
scripts/bench.py         runs them and prints the table
docs/                    this directory

Everything a program can be refused for is refused in cancho-ir, so the backend has no error path for a program — only for the environment. Each fixture declares its own expectation in its header (//~ STDOUT, //~ EXIT, //~ ERROR), so adding a rule to the language means adding a fixture.

Every design document

One line of purpose, one short phrase of status. What each slice found — the measurements, the bugs, the corrections — is ROADMAP.md, not repeated here; a doc’s own header carries its own detail.

linearity-and-effects.md was the gating artifact: the decision set that determined whether this is a three-month prototype or a three-year project. It was settled before M2 started, its must-reject list was read as what it is — the M2 conformance suite, stated in advance — and M2 was then built against it slice by slice.

Linearity and effects

Status: settled, implementation in progress. This is the gating artifact for M2 (#2), and it was reviewed and accepted before any M2 code was written. The rules below are now the specification the implementation is measured against; §12 lists what is still open, and nothing there blocks the rest.

Implemented: §3 through §8 — modes, linearity, both borrow modes, arenas, exact effect rows, narrowing, capabilities and FFI. §2’s claim now holds in code: an effect is a borrowed capability, [io] on a signature means the function was handed an &!i Io it did not create, and the only checker that runs over any of it is the linearity and borrow checker §3–§5 already needed.

§7.4 and §8.4 arrived together, because Ffi(library) is the first capability that carries data and so the first thing there is to narrow. A foreign call is now a real call into libc, gated by a capability that names the library it reaches.

§6 was the last of them, and it is where §5’s bet is paid for: lexical regions are cheap to check precisely because a reference cannot outlive its block, and an arena is what data that outlives its creator lives in instead. Both open a region, both are checked by the same occurs-check.

Not implemented: §9 — the escape hatches.

Where the concrete syntax below differs from what was implemented, §5.3 says so and why. The syntax here was always illustrative (§1); the rules are what this document is for.

This document is the spec the M2 conformance suite encodes. Section 11 is that suite, written out as a fixture list, and it is the part to argue with hardest: design churn on this page is cheap, and churn after the checker exists ripples through the checker and every fixture.

1. How to read this

The syntax below extends M0’s. It is illustrative — a concrete syntax is not settled and the formatter’s rules are still open (#1) — but it is used consistently, so the examples can be read as programs rather than sketches.

Every rule in this document comes with at least one accept example and at least one must-reject example. A rule with no must-reject example is not a rule; it is a hope.

Three words are used precisely throughout:

• consume — to use a resource in the one way that ends its life.
• borrow — to obtain a non-owning reference, valid for a lexically delimited region and no longer.
• capability — a value that is the authority to do something. Not a ticket that is checked, not a permission that is looked up: the authority itself, which you either hold or do not.

2. The one rule

The thesis of cancho is that ownership and effects are the same idea, and that a language designed from scratch can have one system where Rust and Koka have two. Here is that claim made precise:

Prior art, credited late (#75). Austral had already shown the first half: capabilities as linear values, with a root capability handed to the entry point, checked by the same machinery as every other linear value. What this document adds is the second half — that same authority stated as an exact effect row — and related-work.md §2 says what that buys and what Austral got to first.

The resource rule. Every resource is created once, used exactly as its mode permits, and destroyed once. A function’s signature names every resource that crosses its boundary: moved (by value), borrowed (by reference, for a named region), or performed (as an effect). There is one judgment, and the checker makes it once.

The unification is not a slogan about two checkers agreeing. It is an elaboration:

An effect is a borrowed capability, and an effect row is surface syntax for the capability parameters a function requires. [io] on a signature means the function takes an &!io Io it did not create. Elaboration inserts the parameter; after elaboration the only checker that runs is the linearity and borrow checker. There is no second pass that reasons about effects.

Everything else in this document follows from that sentence. In particular:

The last row is what buys examples-as-tests, carried over from Lex: a function whose row is [] can be run by the checker, because a pure function has nothing to run against. That is not a bonus feature bolted on later; it is the reason the row must be exact.

3. Modes: val and res

Every type has a mode, fixed at its declaration.

• val — unrestricted. Copyable, discardable, no obligations. int, bool, &r T, and any struct or ADT built only from val fields.
• res — linear. Exactly one use, no implicit copy, no implicit discard. Declared with res, or inferred for any aggregate containing a res field.

struct Point { x: int, y: int }          // val: all fields are val
res struct File { fd: int }              // res: declared
struct Pair { a: int, f: File }          // res: inferred, because File is res

Mode is structural and computed in one pass over a type’s fields. It is never inferred from use, and there is no mode polymorphism in M2 (see §10).

Reject — a res value copied:

fn twice(f: File) -> [] (File, File) {
    return (f, f);          // ✗ `f` is used twice
}

Reject — a val type declared to contain a res one:

val struct Wrapper { f: File }   // ✗ a val type may not contain a res field

An explicit val on a type whose members are all val asserts exactly what absence already checks, so the two are the same declaration and hash the same (docs/canonical-ast.md §3). res is different: it is a fact about the type that every caller can observe, so it changes the hash.

3.1 Generics carry mode; type parameters do not

Mode is computed after substitution, so a generic type takes its mode from its arguments: Held[File] is res and Held[int] is val, and neither needed a word written on it. Nothing new is required for that — it falls out of mode being structural.

A type parameter, though, is val, because mode is never inferred from use (§3) and a rigid T has no members to read. That has a consequence worth stating plainly, because §12 lists mode polymorphism as open and monomorphisation has quietly answered half of it:

A generic function body is checked once with its parameters rigid, where T is val, and then again for each copy, where T is whatever that copy instantiated it at. So fn id[T](x: T) -> T does work for both modes — and fn sink[T](x: T) -> int { return 0; } is accepted where it is written and refused at the instantiation that leaks.

That is the price, and it is the price §12 predicted: the error lands on the definition’s line, from a call site elsewhere. The message names the instantiation so it can be found, and tests/reject/res_leaked_from_generic.cho pins the behaviour. What is not available is a signature that says “this works for every mode” and is checked once — that remains open, and is the part that interacts with every other rule here.

4. Linearity: linear, not affine

Decision: linear. A res value must be consumed exactly once on every path. A value that reaches the end of its scope unconsumed is a compile error.

Two rejected alternatives, and why:

• Affine (use at most once, silent drop allowed) permits exactly the failure the system exists to prevent: a file that is never closed, a capability that is never returned, an arena handle that is silently abandoned. Affine is linear with the interesting case removed.
• Linear with implicit destructors, Rust’s answer, reintroduces invisible effects. A destructor is code — it can write, it can close, it can fail — and running it at a scope exit nobody wrote means the effect row on the enclosing function is a lie. “C’s effects must not be invisible” (#1) applies to our own drop glue first.

So: no implicit drop, ever. The obligation is discharged by naming the consumer.

4.1 What consumes a value

Exactly four things, and nothing else:

1. Passing it by value to a parameter that takes ownership.
2. Returning it.
3. Destructuring it in a let or a match arm. The whole is consumed and the parts are produced, each subject to the rule in turn.
4. Storing it into a res aggregate, which is case 1 by another name — the constructor is a function that takes ownership.

There is no drop(x) built into the language. A resource is destroyed by the function that knows how: close(f) for a File, free(b) for a Box, release(c) for a capability. Each such function is either a primitive or ends in destructuring to val parts.

Four places would otherwise be a fifth consumer by accident, and each is refused instead. They are consequences of the list above rather than new rules, but each has a fixture, because a rule with no must-reject fixture is a hope:

Assignment is the fifth: f = open(2) overwrites whatever f held, so a live res binding must be spent before it can be reassigned (assign_over_live_res.cho). A spent one may be, and is live again after.

Destructuring takes the whole value apart — every field named, exactly once. A pattern that names some of the fields would be a partial move, which is not on the list (destructure_partial.cho).

Accept:

fn read_and_close(f: File) -> [fs] Bytes {
    let (bytes, f) = read_all(f);   // read_all gives the File back
    close(f);                        // consumed exactly once
    return bytes;
}

Reject — unconsumed at scope end:

fn leak(f: File) -> [] int {
    return 0;                        // ✗ `f` is still live
}

Reject — unconsumed on one path only:

fn sometimes(f: File, flag: bool) -> [fs] int {
    if flag {
        close(f);
        return 0;
    } else {
        return 1;                    // ✗ `f` is live on this path
    }
}

Reject — use after move:

fn after_move(f: File) -> [fs] int {
    close(f);
    return size(f);                  // ✗ `f` was consumed by `close`
}

4.2 Conditional consumption

Every path must agree about what is live. The checker joins branch states at a merge point and rejects any disagreement, rather than inserting the fix-up Rust calls drop flags — a dynamic drop flag is a runtime cost hidden behind a static guarantee, and hidden costs are what a systems language is judged on.

Reject — branches disagree:

fn disagree(f: File, flag: bool) -> [fs] int {
    if flag { close(f); }            // ✗ `f` is dead here, live in the else
    return 0;
}

Accept — both paths agree:

fn agree(f: File, flag: bool) -> [fs] int {
    if flag { close(f); } else { close(f); }
    return 0;
}

Yes, that is verbose. defer close(f); is the obvious sugar and it is deliberately not in M2: sugar that expands to a consumption on every exit path can be added later without changing one rule in this document, and adding it now would mean debugging the expansion and the checker at the same time.

Built — docs/defer.md. And the prediction held: not one rule in this document changed. defer is expanded during lowering into the statement it stands for, once per exit path, so the checker replays exactly the events it would have replayed for the version above.

4.3 Loops

A loop body must leave the live set exactly as it found it. A body that consumes a variable declared outside it is rejected, because the second iteration would use it again.

Reject:

fn loop_consume(f: File, n: int) -> [fs] int {
    var i = 0;
    while i < n {
        close(f);                    // ✗ consumed inside a loop body
        i = i + 1;
    }
    return 0;
}

The check is a comparison of two live sets at the back edge. It is not a fixpoint: the body is walked once, and the sets must match.

5. Borrowing: non-owning reads exist, and they are lexical

Decision: yes, M2 has non-owning references — and no, there is no borrow checker. The difference is that a reference’s validity is a lexical fact here, not an inferred one.

The mechanism is a region variable introduced by a block:

borrow f as &r in {
    let n = size(r);                 // r : &r File
    print_int(io, n)
}
// f is owned again here; r does not exist

Four rules, all local (the spelling differs a little from what was built — see §5.3):

1. borrow x as &r in { .. } freezes x for the block and binds a reference of type &r T. Frozen means: not movable, not consumable, not uniquely borrowable.
2. borrow mut x as &!r in { .. } locks x for the block and binds &!r T, a unique reference. Locked means: nothing else may touch x at all — no read, no second borrow, no move.
3. &r T and &!r T have mode val. They are copyable and discardable, which is sound precisely because the referent is frozen or locked for the whole region and the region is a block.
4. Escape is an occurs-check. The type of a borrow block’s result may not mention r. That is the entire escape rule, it is one traversal of one type, and it cannot diverge.

This is Cyclone’s idea with Rust’s inference deleted. What is gone:

• no non-lexical lifetimes — a region is a block, full stop;
• no lifetime inference — regions are written, or they are function parameters;
• no variance, no subtyping of general types;
• no borrow-checker dataflow — a variable’s state is Owned | Frozen | Locked, a three-valued flag set at block entry and restored at block exit.

Accept — a reference used and discarded inside its region:

fn describe(f: File, io: &!i Io) -> [io] int {
    borrow f as &r in {
        print_int(io, size(r))
    };
    close(f);
    return 0;
}

Reject — a reference escaping its region:

fn escape(f: File) -> [] &r File {   // ✗ `r` is not a region in scope here
    return borrow f as &r in { r };  // ✗ the block's result type mentions `r`
}

Reject — moving a frozen value:

fn move_frozen(f: File) -> [fs] int {
    borrow f as &r in {
        close(f);                    // ✗ `f` is frozen by the enclosing borrow
        0
    };
    return 0;
}

Reject — two unique borrows at once:

fn double_unique(buf: Bytes) -> [] int {
    borrow mut buf as &!a in {
        borrow mut buf as &!b in {   // ✗ `buf` is locked
            0
        }
    }
}

Accept — two shared borrows at once:

fn double_shared(buf: Bytes) -> [] int {
    borrow buf as &a in {
        borrow buf as &b in {
            return len(a) + len(b);
        }
    }
}

5.1 Region parameters on functions

A function that takes a reference is region-polymorphic, with the region written. The binder wears an &, so which parameters are regions is a fact about the declaration rather than something read off the parameter list:

fn len[&r](s: &r Bytes) -> [] int

At a call site the region parameter is instantiated with the caller’s region. That instantiation is first-order unification of a single name — not constraint solving, and not something that can fail to terminate.

5.2 The outlives relation, and why it is a stack

Two references obtained from different borrow blocks have different regions and cannot be used where one region is expected. Rust solves this with subtyping and variance. M2 solves it by noticing that regions are introduced by nested blocks, and nesting is a stack:

r_inner <= r_outer holds exactly when r_outer’s block lexically encloses r_inner’s. A value of type &r_outer T may be used where &r_inner T is expected. Nothing else coerces, and T never changes.

A function may declare the same relation between its region parameters, and the call site discharges it with the same lexical lookup:

fn copy_into[&dst, &src where src <= dst](d: &!dst Bytes, s: &src Bytes) -> [] int

Checking src <= dst is a walk up a stack whose depth is the block nesting of the function being checked. It is O(depth), it has no fixpoint, and the relation is total because a stack is a total order.

Reject — unrelated regions:

fn unrelated(a: Bytes, b: Bytes) -> [] int {
    borrow a as &x in { borrow b as &y in { same_region(x, y) } }
    // ✗ `x` and `y` are siblings; neither outlives the other
}

Instantiation is one assignment, which has a consequence worth stating: a function with one region parameter requires all its reference arguments to be at one region, and whichever argument is checked first decides which. Two references from different blocks cannot both fit, even when one outlives the other — the coercion runs from the argument to the parameter, not between two arguments. Declaring two parameters and the where clause that relates them is how a function says it accepts both, and that is exactly what copy_into above is for. Widening this is constraint solving, which §10 spends its whole argument refusing.

5.3 What was built, where it differs

§1 says the syntax here is illustrative. Three places where the implementation chose differently, and why:

• borrow is a statement, not an expression. cancho blocks are statement lists with no tail expression, so borrow f as &r in { r } has nowhere to put a result. It is shaped like if and while instead, and a value leaves a block the way it always has — by return, which is the case rule 4 is about.
• A region binder wears its &: fn len[&r], not fn len[r]. Reading which bracket entries are regions off the parameter list leaves a region nobody used ambiguous, and makes every diagnostic about the declaration a riddle.
• Escape is checked in two places, not one. Rule 4 says the block’s result may not mention r. With no block result, the two ways out are a return and a binding declared outside the block whose type inference fills in from inside it. Both are the same occurs-check over one type; tests/reject/reference_escapes_via_inference.cho is the second one, and it is not hypothetical.

A place is narrower than it looks. Writing through a &!r needs somewhere to write to, and the left side of an assignment is a whole binding or a field reached through a unique reference — not a field of an owned local. c.n = 2 on a local is refused: that is a partial write, and what a partial write means for a binding holding a res field is a question §4 does not answer. Assigning the whole value says the same thing and asks nothing new. The restriction is not load-bearing and can be lifted once §4 has an answer.

There is no *r yet: a reference to a struct is read with .field, which covers what §5’s own examples do. A reference to a scalar can be made and passed and not otherwise read, which is a wart rather than a rule.

A unique reference may be used where a shared one is expected, and never the reverse. &!r T is &r T plus permission to write, so passing one read-only hands the callee strictly less than it already held. This arrived with §6 rather than here: arenas hand back &!a and nothing else, so without the coercion no function written against &r could touch allocated data at all. The referent stays invariant either way — “T never changes”.

Locking is what makes the implementation cheap. A reference is a pointer at a buffer the referent is spilled into for the block. A shared borrow needs no write-back, because the referent is frozen and the two cannot drift. A unique borrow reads the buffer back when the block closes — sound precisely because nothing else may touch the value while it is locked, so the buffer is the only version that moved. Two copies of one &!r are two copies of one pointer, so writes through them alias correctly rather than racing to be last writer.

6. Arenas are regions

A region variable is introduced by borrow, and by one other thing:

region a {
    let node = alloc[a](Node { value: 1 });   // node : &!a Node
    walk(node)
}   // the whole arena is released here, in O(1)

region a { .. } opens an arena. alloc[a] allocates in it and hands back a unique reference carrying the region. At block exit the arena is released wholesale — one pointer reset, no traversal, no per-object bookkeeping.

What escapes: nothing whose type mentions a. This is the same occurs-check as §5, which is the point — an arena’s lifetime and a borrow’s lifetime are one mechanism, not two that happen to look alike.

Nesting is the same stack: an inner region may hold references into an outer one (r_outer <= r_inner by §5.2), and never the reverse.

Reject — a reference escaping an arena:

fn escape_arena() -> [] &a Node {    // ✗ `a` is not a region in scope here
    return region a { alloc[a](Node { value: 1 }) };   // ✗ result mentions `a`
}

Reject — an inner region’s reference stored into an outer one:

fn outlive(outer: &!o Slot) -> [] int {
    region i {
        let n = alloc[i](Node { value: 1 });
        store(outer, n);         // ✗ `&!i Node` does not outlive `o`
    }
    return 0;
}

6.1 Arenas hold val data only

An arena releases memory. It does not close files, release capabilities or run anything. So:

alloc[a] requires its argument’s type to have mode val. A res value placed in an arena would have its memory reclaimed at block exit with its linear obligation undischarged — a leak with a static blessing.

Reject:

fn arena_res(f: File) -> [] int {
    region a {
        let p = alloc[a](f);     // ✗ File is res; arenas hold val data only
        0
    }
}

This is restrictive and knowingly so. The alternative — arena teardown as a consumption event, with per-object finalisers — reintroduces implicit destructors and turns an O(1) release into a traversal. If it turns out to bite in practice, the fix is a separate scope construct with explicit registration, not a weakening of this rule.

What was built. region a { .. } and alloc[a](v), spelled as above. The region name is written bare in both, because & is the reference constructor and there is nothing in either position for it to construct.

An arena is a borrow block with the referent taken out. Opening one pushes a block onto the same table §5 uses, with the same parent link — so §5.2’s outlives relation, §5’s occurs-check and the scope rules apply to it without a line of new reasoning. reference_escapes_arena.cho is refused by the code that refuses reference_escapes_borrow.cho, and inner_region_stored_in_outer.cho by the code behind unrelated_regions.cho. That is §6’s claim — “an arena’s lifetime and a borrow’s lifetime are one mechanism, not two that happen to look alike” — and it is structural rather than asserted.

alloc[a] hands back &!a T, an ordinary unique reference. There is no second notion of a pointer-into-an-arena, so reading, writing through it and passing it to a region-polymorphic function all work unchanged. a must be an arena open right now: a borrow block’s region is a region but has no chunk behind it, and a region parameter is a caller’s, not this function’s to allocate in.

One new coercion, which §6 forces. A unique reference is accepted where a shared one is expected, never the reverse — &!r T is &r T plus permission to write, so handing one over read-only gives the callee strictly less than it already had. Without it nothing written against &r could touch arena data at all, since alloc hands back &!a and nothing else. The referent stays invariant.

At runtime an arena is one malloc when the block opens and one free when it closes (as built since region-chunk-cache.md: one chunk taken from the thread’s stack of freed ones, or malloced, and given back, cleared, when it closes), with a bump pointer in between; a return out of a region releases every arena it leaves, innermost first. Release is one call whatever was allocated, which is the O(1) the section is trading expressiveness for — and it is only a free, because §6.1 kept everything with an obligation out of the chunk.

Exhausting the chunk traps. A single chunk is what makes release one call; growing it would make release a walk. The alternative to trapping is writing past the end of an allocation, which is undefined behaviour, which this language does not have. So the arena is 64 KiB and asking for more kills the process, deterministically, the same way division by zero does. Growth that keeps both properties is an M3 question and the trap is what keeps the answer honest until it is answered.

7. Effects

7.1 Sets, not rows

Decision: an effect row is a canonically ordered set of labels. No duplicate labels, no row variables in M2.

“Rows or sets” (#2) is a question about what duplicate labels buy. They buy effect handlers and masking — a Koka catch that handles the innermost exn and leaves an outer one alone. M2 has no handlers, so duplicates would be a cost with no purchase. Sets also have the property the rest of this project needs: a canonical order makes an effect row hashable, and a signature that hashes deterministically is what per-unit identity is made of (#1).

Two operations are needed, and only two:

• union, to compute a body’s effects;
• subset, to check a call against a declaration.

Both are linear in the number of labels, which is small and statically bounded.

7.2 Declared at boundaries, inferred inside

Decision: every function signature declares its row. Inference happens only within a body.

Whole-program effect inference is exactly the non-local, potentially-diverging analysis the totality commitment forbids, and an inferred row is a contract nobody wrote and everybody depends on. Inside a body there is nothing to infer but a union over the calls, which is a fold.

The check at a call site is: the callee’s row is a subset of the enclosing function’s declared row.

Reject — an undeclared effect:

fn quiet(io: &!i Io) -> [] int {
    print_int(io, 1);                // ✗ `print_int` performs `io`; row is []
    return 0;
}

Every signature writes its row, including []. An absent row would be an inferred one, and “inferred at the boundary” is the thing this section refuses — so purity is written down and visible rather than worked out.

The grounding runs the other way from what a reader might expect: a label is not declared anywhere, it is performed by a primitive, and a label nothing performs can never appear in an exact row. So [telepathy] is refused by §7.3 without anyone maintaining a list of legal effect names, and adding a new effect means adding something that performs it.

7.3 A declared effect that is not performed is an error

Not a warning. The row is exact or it is decoration, and an inexact row means [] no longer means pure — which costs examples-as-tests, and costs a signature hash that means something.

Reject — an over-wide row:

fn pure_after_all(io: &!i Io) -> [io] int {
    return 1;                        // ✗ declared `io`, performs nothing
}

This is the same rule as lex agent-guidelines §1.2 (“narrow effects, always; if the checker rejects, narrow the body, not the signature”) turned from a guideline into a type error. The cost is that a signature cannot reserve room for a future implementation; that tension is recorded in §12.

7.4 Narrowing

An effect label may carry a value, which is what makes [fs_write("/tmp/x")] different from [fs_write]. The value comes from the capability:

fn write_log(fs: &!f Fs) -> [fs_write(f)] int

and f’s own type records what it was narrowed to. Narrowing is a function on capabilities:

let logs = narrow_path(fs, "/var/log/app");   // Fs("/var") -> Fs("/var/log/app")

Narrowing only, in both directions. A capability can be attenuated and never widened — the same commitment lex-os makes for manifests, for the same reason: a program must not be able to grant itself what it was not given.

In M2 the argument to a narrowing function must be a literal, so the refinement is checkable structurally. General compile-time refinement waits for comptime, which is deliberately excluded from “minimal” (#1).

Reject — widening:

fn widen(fs: &!f Fs) -> [fs_write("/")] int {
    return write(fs, "/etc/passwd");  // ✗ `f` is narrowed to "/var/log"
}

What was built. narrow(cap, "libc"), on the one capability that carries a value: Ffi. What a capability was narrowed to travels in its type — Ffi("libc") and Ffi("libm") are different types — and the label carries the same text, so ffi and ffi("libc") are different labels and a row containing one is a different SigId from a row containing the other.

Refinement is prefix extension, which is what makes it checkable by reading rather than by solving: narrow(c, t) is accepted exactly when t extends what c already names, and refused otherwise.

(M3 added Fs(prefix) as the second capability carrying a value, over the same narrow. One rule had to be made sharper for it: a path prefix extends at a / or not at all, because /tmp is a byte prefix of /tmpevil and does not contain it — fs_sibling_prefix.cho. A library name has no such structure, so Ffi keeps the plain textual rule. See docs/filesystem.md §1.1.) The unnarrowed root is the empty string, a prefix of everything, so the Ffi that split hands out can still become any library while an Ffi("libcrypto") can never become Ffi("libc") — effect_widened.cho. Narrowing to what a capability already names is refused too: it grants nothing and would read as though it had.

Narrowing consumes. The wider capability is spent, which is the whole point — after narrowing there is no way back to it, because linearity says there is no second use. For the same reason a borrowed capability cannot be narrowed: a borrow is the promise to give it back.

Narrowing into several. For the two path capabilities, Fs and Exec, narrow(cap, "a", "b", ...) spends cap once and answers a tuple of cap’s type narrowed to each literal, in the order written. The lattice still has one chain per capability, but a program may now hold several capabilities that are not on one chain, each strictly inside the one consumed, so the children together reach nothing the parent did not and main’s narrowing line still names everything the program will ever touch. The literals are checked as the single form checks them, and must be pairwise unrelated. docs/narrowing-into-several.md.

Covering, not equality. §8.2’s discharge rule reads the same prefix order: owning Ffi("") discharges every ffi(...) label, because its holder can narrow to any of them, and owning a World discharges both io and the Ffi root. That is why main still declares [] while the program calls into libc. For a path label (fs_read, fs_write, exec) the order is the path prefix, extends_path, not the byte prefix: owning Fs("/tmp") does not discharge fs_read("/tmpevil") (docs/filesystem.md §1.1).

8. Capabilities

8.1 What one looks like

What was built. World, Io, Ffi(library) and — from M3 — Fs(prefix), plus the Split that split hands back: let Split { io, ffi, fs } = split(world);. Heap still waits for general allocation: a capability for an effect nothing can perform is decoration, which is what §7.3 refuses for rows and what this refuses for the same reason.

A capability the program does not need is still a resource, so a program that calls into no library releases its Ffi rather than ignoring it. Adding a capability to Split is therefore a breaking change every program has to acknowledge — which happened twice, for Ffi and again for Fs, each time touching every program in the tree. That is the honest cost of there being no ambient authority, and it is the cost being paid rather than avoided.

The prelude’s types are predeclared rather than written in a program, and a program may not declare its own — capability_redeclared.cho. Nor write one as a literal: Io { } would be an ambient constructor spelled differently, so it is refused (no_ambient_capability.cho). Since World and Io carry no fields, taking one apart would end authority without naming a consumer, so that is refused too and release is the only way (capability_destructured.cho). Split is destructured on purpose.

Owning discharges; borrowing declares. §8.2’s remark that main’s row is [] is implemented as a rule: an effect whose capability a function owns by value does not appear in its row, because ownership is already visible in the parameter list and is strictly stronger than borrowing. A borrowed &!i Io discharges nothing — it is exactly what [io] names.

A capability is an ordinary res value. It has no special kind, no special syntax, and no runtime representation beyond what its type says — most are zero-sized, and the ones that are not (a file descriptor, an arena pointer) are the size of the thing they authorise. Capabilities erase at compile time except where they carry data. Threading one costs nothing.

res World                     // the root of all authority
res Heap                      // allocation
res Io                        // console
res Fs(prefix: Path)          // filesystem below a prefix
res Ffi(library: Name)        // foreign calls into one library

8.2 Where one comes from

One place:

fn main(world: World) -> [] int {
    let Split { heap, io, fs, ffi } = split(world);   // consumes `world`
    ...
}

World is linear and the runtime hands over exactly one. split consumes it. There is no ambient constructor, no Io::global(), no unsafe { } that conjures one. A function that is not given a capability cannot perform its effect, which is the whole safety story, stated as a type.

That main’s own row is [] is not a quirk: a row lists the capabilities a function borrows, and ownership is already visible in the parameter list. Owning authority is strictly stronger than borrowing it, and strictly more visible.

8.3 How one is threaded

By borrow, not by move — a callee should not consume its caller’s authority:

fn greet(io: &!i Io) -> [io] int {
    return write_str(io, "hello\n");
}

fn main(world: World) -> [] int {
    let Split { heap, io, fs, ffi } = split(world);
    borrow mut io as &!i in { greet(i) };
    release(heap); release(io); release(fs); release(ffi);
    return 0;
}

The four release calls are the linearity rule doing its job: authority is a resource, and a resource is destroyed exactly once. A program that forgets one does not compile.

Reject — an effect performed without the capability:

fn sneaky() -> [io] int {
    return write_str(global_io(), "hello\n");   // ✗ no such thing as global_io
}

Reject — a capability used after release:

fn after_release(io: Io) -> [io] int {
    release(io);
    borrow mut io as &!i in { greet(i) }        // ✗ `io` was consumed
}

8.4 FFI

A foreign call is an effect like any other, and its capability names the library:

extern fn strlen(f: &!ffi Ffi, s: &r Bytes) -> [ffi("libc")] int

The declaration is the only place a foreign signature is written, the capability is the only way to reach it, and the row makes the call visible in every caller’s signature all the way up. C’s effects stop being invisible at the exact point they enter the program.

What was built. extern fn declarations, lowered to real imports and called through the platform’s own convention:

extern fn labs[&f](ffi: &f Ffi("libc"), n: int) -> [ffi("libc")] int;

A foreign declaration is a signature with no body, so its SigId and BodyId are the same hash — there is nothing else it could be a hash of. It is region-polymorphic like any other function, because the capability it takes is borrowed, but it takes no type parameters: C has none to instantiate.

The declaration is where the rules are enforced, because it is the only place the signature is written. Three of them:

• the row and the capability parameters must agree exactly, in both directions — a declaration naming an effect it holds no capability for is ffi_without_capability.cho, and one holding a capability it does not declare is foreign_effect_undeclared.cho;
• the borrowed capability must name a library. The unnarrowed root names none, so Ffi("") is refused here — narrow first;
• only what C can name crosses: int, bool, (), and borrowed capabilities, which do not cross at all. An aggregate has no layout agreement between the two sides yet, and a reference to anything but a capability would be a pointer this compiler has not promised to lay out.

int at the boundary is the platform’s 64-bit integer, not C’s int — which is why the fixtures call labs rather than abs. A narrower C integer type needs a type to name it, and M2 does not have one.

The capability does not travel. It is checked, then erased: what libc receives is the integer and nothing else. narrowed_capability.cho calls labs(-7) and prints 7, which it could not do if a zero-sized capability were pushed in front of the argument.

A foreign name is not also a written function’s name: two answers to one call is one answer too many.

9. Escape hatches

Built, and this section was half wrong. See docs/sharing.md.

Both hatches below were written. Gen is a library exactly as described and now lives in examples/slab/. Rc is not expressible at all: it needs a copyable pointer, and this language has none — Box[T] is res, a reference is bounded by its region, and there is no third thing. Three ways of trying are three fixtures in tests/reject/, each refused by a different rule that was not written with Rc in mind.

So “neither touches the checker” is the claim that did not survive being built: a real Rc is a language feature, not a library. sharing.md §2.3 has what you can have instead — shared ownership is reachable, the ambient handle is not.

The rest of this section stands, and sharing.md supersedes the Rc row of the table.

Linearity cannot express shared mutable graphs, observers, or any structure where “who owns this” has no answer. Two hatches, both libraries, not language features — neither touches the checker, and that is the point:

Both are res. Rc is consumed by release_rc, a Slab by free_slab. Neither is reached for by default, and neither hides its cost: the runtime cost table above is part of the contract, in the same spirit as [budget].

Gen is the one to prefer. A stale generational handle is a value — None — and the program decides what to do about it. A dangling pointer is undefined behaviour and the program does not get a say. That asymmetry is most of why this language exists.

That last paragraph turned out to be stronger than it knew: Gen is not merely the one to prefer, it is the only one of the two there is. See docs/sharing.md.

10. Why the checker stays fast and total

The commitment is “fast and total” (#1), which means: every check terminates, and the cost is bounded by the size of the function being checked. What earns that here:

1. No global inference. Every signature is complete — types, regions, effects. A function is checked against its callees’ signatures, never against their bodies.
2. No fixpoints. The loop rule compares two live sets at a back edge rather than iterating to convergence. Branch joins compare and refuse rather than patching up.
3. Regions are a stack. <= is a lexical lookup, not a constraint graph.
4. Effects are sets. Union and subset over a small, statically bounded label set.
5. No subtyping except the one region coercion, which never changes the type it decorates. No variance. No trait resolution — there are no traits (#1, non-goals).
6. No higher-order functions in M2, so no effect row variables and no mode polymorphism. This is the single largest simplification in this document, and it is why the row-versus-set question in §7.1 could be answered so cheaply. When closures arrive they bring row variables with them, and this section is where the argument has to be re-made. (function-values.md §4.3 re-made it for captureless function values, which bring no row variables: a call through one is checked against the row in its type. Row variables arrive only with abstracting over rows.)

Each function’s check is one walk of its body carrying a three-valued state per local and a set per call. That is linear in body size with an O(nesting-depth) lookup, and nothing in it can diverge.

11. The must-reject suite

This is the deliverable the gate actually cares about: the rules above, restated as fixtures. M0 already has the harness — tests/reject/*.cho, each fixture declaring its own expected message in a //~ ERROR header, run by crates/cancho/tests/conformance.rs. M2 adds to it; it does not invent anything.

A ✓ in the last column means the fixture exists and the rule is enforced. Every row carries one.

§7 adds three more: effect_not_propagated.cho (a row is transitive), ungrounded_effect_label.cho (a label nothing performs) and effect_row_required.cho (the syntax).

§8.4 adds one beyond the table — foreign_effect_undeclared.cho, a foreign declaration holding a capability its row does not name.

§8 adds three: world_leaked.cho (the root is a resource too), capability_destructured.cho (taking one apart is not releasing it) and capability_redeclared.cho (a program may not declare its own Io). main_takes_the_world.cho replaces M0’s main_takes_arguments.cho, since main now takes exactly one thing.

§5 adds eight must-reject fixtures beyond the table, for the rules §5.3 describes and for the syntax: region_not_in_scope.cho, reference_escapes_via_inference.cho, assign_while_frozen.cho, borrow_after_move.cho, borrow_mode_mismatch.cho, unique_borrow_of_frozen.cho, write_through_shared.cho and assign_field_of_local.cho. Its accepting counterparts are borrow_and_return.cho, two_shared_borrows.cho, nested_regions.cho and unique_borrow.cho.

§4.1’s four accidental consumers and §3.1’s instantiation rule add six more must-reject fixtures beyond the table — res_discarded.cho, res_field_read.cho, res_matched_by_wildcard.cho, res_payload_ignored.cho, assign_over_live_res.cho, destructure_partial.cho and res_leaked_from_generic.cho — plus var_destructure.cho for the syntax. Their accepting counterpart is destructuring.cho.

Each fixture is the smallest program that triggers its rule and nothing else. An accepting counterpart goes in tests/accept/ for every one of them — a rule that rejects everything is not a rule either:

12. Open questions

These are genuinely open. They are not blocking — each can be settled after M2 code exists without invalidating a rule above — but they are the places to push if something here feels wrong.

• Reserving room in a row. §7.3 makes an unperformed declared effect an error, which forbids a signature that anticipates its implementation. Is that right for a published library, where widening a row later is a breaking change? An explicit opt-out is easy to add and hard to take back.

• defer. Answered — see docs/defer.md. Yes, still visible, and the question turned on what the word means here: not “written on the line where it runs” but the type says what happened. The effect is still in the row, the exactly-once rule is still enforced on every path, and the line is still written — one below the acquisition, which is where a reader looks for the pairing. A destructor would have failed that test; defer names the function.

• Capability release at main. Answered no — see docs/authority.md. The affine-hole argument holds, and it is not the interesting one: even if reclaiming were safe it would be wrong, because those four lines are the only place a program’s authority surface is written down. main owns rather than borrows, so its row is [] and every entry point in this repository has the same signature — the releases are the declaration, not ceremony around it. What the tooling owed was to read them, which cancho authority now does.

• Mode polymorphism. Answered — see docs/mode-polymorphism.md. The half-answer below was right: monomorphisation does make fn id[T](x: T) -> T work at both modes. The signature that says so is [T: val], checked once and enforced at the call site, and an unbounded parameter is checked as res. Checking the claim also found a leak and a double free: a val on a generic declaration was trusted rather than checked, so Wrap[Box[int]] was val by assertion. The original text follows.

  Half-answered by §3.1: monomorphisation does make fn id[T](x: T) -> T work at both modes, because each copy is checked at the type it was instantiated at. What is still open is a signature that says so and is checked once — the part that interacts with every rule here at once, and the part that would keep the error off the definition’s line.

• Rc cycles. Documented as a leak. A systems language may be entitled to say exactly that, or a Weak may be table stakes.

• Budget. Answered no — see docs/budget.md. It does not belong here. lex-os already separates the three questions a capability language faces — may this reach X at all (the type check, which is this document), which host or path (the perimeter), and how much (the supervisor, charged per mediated command) — and a budget’s units settle it: wall-clock seconds, commands, money in cents. None of those is a property of a program’s text. What was wanted is legibility rather than enforcement, and that is cancho authority --output json.

13. What this forces on M1

M2 cannot be bolted onto an M1 that made these impossible. Three things the type checker must get right the first time, before any of the above is written:

1. Signatures are complete and are the unit of checking. A body is checked against signatures only. If M1 lets any part of a signature be inferred from a body, §10.1 is already lost.
2. Types are values the compiler can compare cheaply and hash canonically — including, eventually, regions and effect rows. An effect set’s canonical order is not an afterthought; it is what makes a signature hash.
3. The branch join is a real operation. M1’s checker should join branch states even when the only state is types, because §4.2 is that same join with a live set added.

Nothing in M1 needs to know what a capability is. It does need to be built so that adding one is adding a rule, not rewriting a pass.

Bootstrap and self-hosting

cancho’s compiler started in Rust, because Cranelift is a Rust library and the first milestone had to prove a code generator. It is now being written in cancho, stage by stage, with the Rust compiler as the check each stage is held to. This page says where that stands (2026-10-15) and how to use it; self-hosting.md has the stage-by-stage record and the measurements, and the plan to finish is epic #491.

Where it stands

• The compiler in cancho is examples/selfhost/: about 22,000 lines of cancho. It reads a program and writes LLVM IR; clang finishes the build.
• It is the default. cancho build, run and test write the code with it on macOS and Linux (x86-64 and aarch64), after the Rust front end has checked the program (see below). It is built once, from sources compiled into the cancho binary, and cached; nothing has to be next to the binary. A build it cannot do (it has no code for a construct, or it fails) is done by the Rust compiler, and the Cranelift backend and WebAssembly stay the Rust compiler’s. CANCHO_COMPILER=rust asks for the Rust compiler alone.
• It compiles itself to a fixed point, on three systems: built on macOS, on Linux x86-64 and on Linux aarch64 (a Raspberry Pi 5), it writes byte-identical IR for its own source.
• It builds real programs. The whole conformance suite passes with every build going through the default (710 tests on macOS aarch64), and CI runs the suite through the compiler in cancho alone, with no Rust check and no fallback (CANCHO_COMPILER=auto), on macOS, Linux x86-64 and Linux aarch64, minus the few differences listed in .github/selfhost-known-differences.txt. The projects cancho-cache, cancho-oci, cancho-robot, cancho-gpu and cancho-hooks build with it.
• It nearly refuses what the language refuses. Of the 337 programs in tests/reject/ that are not a property of a target (marked //~ TARGET), it refuses 333 with the rule the Rust compiler gives; the 4 left are listed in reject_gaps.txt: a row in the type of a function value, what an owned capability discharges by path, and a region settled by inference (#512). That is why the default still lets the Rust front end check first, and it stops when the list is empty (a test says so).
• A refusal says why without the Rust front end when the compiler in cancho is named alone: where (file:line:column), the sentence of the rule (Rule::explanation, generated into the compiler’s tables), the rule, the line and what of it. The sentence is the rule’s, the same for every program it refuses; the names and types in the Rust compiler’s messages are a later stage.
• Only code generation goes through it. check, authority, ids, fmt, vcs and the Cranelift and WebAssembly backends are still the Rust compiler’s. Windows is not a target of either compiler.

Using it

cancho build program.cho --std -o program               # the default
CANCHO_COMPILER=rust cancho build program.cho -o program  # the Rust compiler alone
CANCHO_COMPILER=auto cancho build program.cho -o program  # the one in cancho alone: what it refuses, no fallback
cancho build --compiler ./some-compiler program.cho       # a compiler you built yourself

The first build takes a few seconds more: it builds the compiler in cancho (with the Rust one) into the cache, keyed by a hash of its sources ($CANCHO_CACHE, or ~/.cache/cancho). CANCHO_SELFHOST_SOURCES=<dir> builds it from a directory instead, for working on it. Named alone, a construct it has no code for yet is a refusal that says so, at that construct.

What is left

Tracked in #491: the last four refusals; the other commands (check, fmt, …); the Cranelift and WebAssembly backends; the runtime text that is still generated from the Rust crates; keeping golden outputs for when the Rust compiler is gone, and a seed that needs no Rust; compile time and whether Windows is a target.

Code quality, measured once (Linux x86-64, tests/programs/tls_prims_bench.cho built with --std, instructions a call under valgrind as scripts/tls_perf.py check counts them, against the baseline recorded for the Rust compiler): the Rust compiler is within 1.06 of the baseline on all 36 rows; the compiler in cancho is 1.26 to 1.32 times it on the P-256 rows (p256_shared 1.32, p256_public 1.30, ECDSA 1.26 to 1.28), about the same on the AES-GCM, ChaCha20-Poly1305, HKDF, HMAC, SHA-2 and X25519 rows (0.97 to 1.13) and 4.97 on calibrate (a loop of a single instruction a step for the Rust compiler, 5,007 instructions a call against 1,008). The binary is 360,208 bytes against 318,656. So the tls-perf job builds with CANCHO_COMPILER=rust: its baseline is the Rust compiler’s code, and it guards that. Closing this gap, or recording a baseline of the compiler in cancho, is code quality’s share of #491.

History: the v0 compiler

Decisions M0 had to settle to exist, recorded here so they are not re-litigated by accident. Each was an open question in #1.

Bootstrap host language: Rust

The v0 compiler is written in Rust. The alternative was hosting it in current Lex.

Rust wins for one reason that outweighs the rest: Cranelift is a Rust library. Hosting in Lex means reaching a code generator through FFI on day one, which is the part of the pipeline M0 exists to prove.

This was a bootstrap decision, not a permanent one: the compiler is now being written in cancho itself (above), and the Rust one is the check it is held to.

File extension: .cho

.cho over .lxs. Shorter, and the collision risk (LiveScript) is not one this ecosystem will meet in practice. cancho build hello.cho.

Layout of the Rust compiler

crates/cancho-syntax    lexer, canonical-shaped AST, parser
crates/cancho-ir        resolution and well-formedness checks; the M0 IR
crates/cancho-codegen   Cranelift lowering, native object emission
crates/cancho           the CLI
examples/                programs that are meant to be read
tests/accept             fixtures that must compile and run
tests/reject             fixtures that must be refused, each stating why

Everything the compiler can refuse, it refuses in cancho-ir. The backend takes IR that has already been proven well-formed, so Cranelift lowering has no error path for a program — only for the environment.

The M0 surface

Historical: this is what M0 shipped. M1 adds bool, &&, || and !, and the rules below are unchanged by it.

One type (int, 64-bit signed), functions and calls, arithmetic, comparison, if/else, while, and let/var bindings. That is the whole language.

Rules M0 already enforces, because they were cheaper to write than to retrofit:

• Every path through a function must return. The check is structural and conservative: a while never counts as a terminator, even while 1 { }.
• Code after a return is refused rather than silently dropped.
• let is immutable and so are parameters; var is the mutable binding.
• A binding may shadow one from an enclosing block, but not one in its own.
• An initialiser cannot see the binding it initialises: let x = x; reads an outer x or is refused.
• Functions are not values. M0 has no closures and no function pointers, so a bare function name is an error rather than a mystery.

Things that are scaffolding, and what replaces them

Two entries have already left this table. M0 had comparisons yield int (0 or 1) and had if/while test any integer for non-zero, both because it had no bool. M1 introduced one, so a comparison has the type it always meant and a condition is required to be that type. The convention became a rule, which is the shape every scaffold above is meant to end in.

Division is not on that list. a / b and a % b trap on a zero divisor and on int::MIN / -1. A trap is defined behaviour; C’s answer here is not, and that difference is the whole point (#1). tests/ has a fixture that runs the trap and asserts the process dies rather than continuing with nonsense.

What the AST already does for canonicalisation

Nothing hashes the AST yet — per-unit identity is M3 work and docs/canonical-ast.md is unwritten. But an AST retrofitted for hashing is an AST whose hashes are already wrong, so the shape is settled now:

• Nodes live in arenas; spans live in parallel side tables. A hash walks the arenas and never sees a byte offset.
• Whitespace, comments and redundant parentheses die in the lexer and parser. Two files differing only in layout produce identical arenas — there is a test that asserts exactly this.
• Integer literals are stored as values, not spellings: 007 and 7 are one node.
• Names intern to dense indices, assigned in order of first appearance.
• Every list is a Vec in source order. No set, no map, no iteration order that depends on an address or a hash seed reaches any output.

Exit codes

cancho run is the exception: it exits with the compiled program’s status, so cancho run p.cho and cancho build p.cho && ./p agree.

The canonical AST and per-unit identity

Status: proposed. Written alongside the first implementation of hashing (M3, #1). The rules below are what cancho-id implements; the parts that are not yet contracts are called out in §8, and nothing here is frozen until that section is empty.

cancho claims a “canonical, content-addressable AST, designed in from day one” (#1). M0 shaped the AST for it and M1 left that shape intact. This document is the other half: what exactly gets hashed, what two programs must agree on for their hashes to agree, and — the part that matters most — what a hash is allowed to change with.

1. What a unit is

A unit is one top-level declaration: a function, a struct, or an enum. Each has an identity of its own, independent of the file it sits in and of what sits beside it.

That is the whole point of per-unit identity. Moving a function between files, or reordering declarations, changes nothing about it. A unit is not a line range.

2. Two identities, not one

Every function has two hashes, and the split is load-bearing:

A caller depends on a callee’s SigId and on nothing else about it. So rewriting a function’s body — a faster algorithm, a clearer loop — leaves every caller’s identity untouched. Only a change a caller could observe propagates.

This is also what makes the graph acyclic. A body refers to its callees by their SigId, and a SigId never depends on a body, so mutual recursion cannot produce a cycle:

fn even(n: int) -> bool { if n == 0 { return true; } return odd(n - 1); }
fn odd(n: int) -> bool  { if n == 0 { return false; } return even(n - 1); }

BodyId(even) contains SigId(odd), BodyId(odd) contains SigId(even), and neither SigId contains either body. A Merkle graph over cyclic source.

Struct and enum declarations have a single TypeId, since they have no body to separate. A foreign declaration (extern fn) is a signature with no body, so its SigId and BodyId are the same hash — there is nothing else a body hash could be a hash of.

2a. The printer is the other direction

cancho print <file> renders a parsed unit back to text. It is the AST→text half of the same pipeline: a store that addresses code by hash needs a way to show a declaration it fetched, and that rendering has to be canonical or the display would depend on who stored it.

Two contracts, both enforced by a test that walks every .cho file in the repository:

• Identity-preserving. Parsing the output gives back the same SigId, BodyId and TypeId for every declaration.
• Idempotent. Printing the output again changes nothing.

The printer is deliberately not a formatter. §3 below says comments never reach the AST, precisely so that formatting cannot change a hash — which means anything built on the AST cannot put them back, and a fmt that silently deleted every comment in a file would be a bad trade. Rendering a stored declaration, where there were no comments to lose, is the job this does.

Writing it found two places where the canonical form is decided by the grammar rather than by the tree, both of which the round-trip test caught rather than review:

• a struct literal in an if, while or match head has to keep its parentheses, because its braces would otherwise be taken for the block — and parentheses leave no node behind to remember that;
• - immediately before an integer token is one literal rather than a negation of one (which is how -9223372036854775808 is writable at all), so a negation of a literal has to stay visibly apart from one.

3. What must not change a hash

These are the properties the AST shape was built for, and each has a test:

• Formatting. Whitespace, line breaks and indentation never reach the AST.
• Comments. Discarded in the lexer.
• Redundant parentheses. (a + b) * c and (((a + b)) * c) are one tree; grouping leaves no node behind.
• Literal spelling. 007, 7 and 1_000 are values, not text. 0x7 will be too, when it exists.
• Position in the file. Spans live in side tables, never inside a node.
• Neighbours. A unit hashes alone. Adding, removing or reordering other declarations changes nothing.
• Local names. See §5 — this one is a decision rather than a consequence.
• A redundant val. A declaration’s mode is val unless it says otherwise, so writing the word on a type whose members are all val asserts exactly what absence already checks — and a val that was not true is refused before anything hashes it. The two declarations are one type.

3.1 What must change a hash

• Any operator, literal value, or control-flow structure.
• Any type in a signature, and the order of parameters.
• A callee’s signature, transitively.
• Field and variant order in a declaration, because they are positional to the backend and observable through construction.
• A declaration’s res (docs/linearity-and-effects.md §3). A linear type is not the same type as a copyable one, and every caller can tell.

4. The encoding

A hash is taken over a byte string, and the byte string is what has to be canonical. The rules:

1. Every node starts with a one-byte tag. Tags are assigned explicitly and never reused; §8 explains why they are not yet frozen.
2. Integers are fixed-width little-endian. i64 as eight bytes, counts as four. No variable-length encoding, because two encoders must not be able to disagree about the short form.
3. Strings are length-prefixed UTF-8 — four bytes of length, then the bytes. Never null-terminated, so a name cannot smuggle a delimiter.
4. Sequences are length-prefixed, then their elements in order.
5. Nested hashes go in as their 32 raw bytes.

4.1 Names are text, never interner indices

The AST interns names to dense indices, and those indices are assigned in order of first appearance across the whole file. They are deterministic for one file and meaningless between two. Encoding an index would make a unit’s hash depend on what else the file happened to mention first — exactly the neighbour dependence §1 exists to remove.

So the encoding carries the name’s bytes. This is the one place where the convenient in-memory representation is the wrong thing to hash, and writing this document is how it was noticed.

5. Local names do not matter; the decision and the cost

Decision: bodies are hashed up to alpha-equivalence. Renaming a local binding does not change BodyId.

fn f(n: int) -> int { let doubled = n * 2; return doubled; }
fn f(n: int) -> int { let d = n * 2; return d; }

Both have the same BodyId. A reference to a bound name encodes the binder’s position — how many binders back it was introduced — rather than its text. A reference to something not bound locally, such as a function, encodes its identity instead.

The case for: a rename is a refactor that cannot change what a function computes, and an attestation that says “this function does X” should survive one. The case against: it costs a scope walk during hashing, and it means two textually different files can produce byte-identical hashes, which surprises anyone expecting a hash of the source.

The second is a real cost and is accepted deliberately: this is a hash of a program, not of a file. Anyone wanting the latter should hash the file.

Parameter names are excluded from SigId for the same reason — cancho has no named arguments, so a caller cannot observe them. Generic parameter names are excluded and their count included, since fn f[T](x: T) and fn f[U](x: U) differ in no way a caller can see.

6. Domain separation

Every hash begins with a domain tag, so a signature’s bytes can never be mistaken for a body’s even if they coincide:

cancho.sig.v1      a function signature
cancho.body.v1     a function body
cancho.type.v1     a struct or enum declaration

The v1 is not decoration. When a rule in this document changes, the version changes with it, and old hashes stay readable as what they were rather than becoming silently wrong.

The hash is BLAKE3, 32 bytes, rendered as lowercase hex and abbreviated to 16 characters for display only. Never for comparison.

7. What this buys

Nothing in M3 consumes these hashes yet, which is worth saying plainly. They are built now because:

• The AST shape can be checked. M0 claimed the AST was built for canonicalisation. Until something hashed it, that was an assertion. It is now a test suite.
• Attestation needs them (#1), and so does any incremental build, cache or registry. Each of those is easier to add to a compiler that already has stable identities than to retrofit.
• The self-hosting spike depends on exactly this. #1 proposes porting lex-ast/lex-vcs canonical forms and checking byte-identical OpId/SigId/StageId against a 136k-op corpus. A cancho that cannot hash its own AST cannot run that experiment.

8. Not yet contracts

Per docs/INVARIANTS.md’s convention in lex-lang: these are implemented but not promised, and may change without a version bump until this section is empty.

• Tag values. The byte assigned to each node kind is stable within a build and not yet frozen across releases. Freezing them means writing them down here as a table, which is worth doing once the AST stops growing — every milestone from M2 on adds nodes.

  Until then the moves are at least visible: crates/cancho-id/tests/golden.rs pins 35 fixtures, one per node family, to the hashes they emit today. It is not a freeze and a failure is not a bug report — it asks which of two things happened, an intended encoding change or something reaching the hash that should not have, and says to record the answer in the commit message. The point is the rate: the question of whether this section can ever be emptied is a question about how often these actually move, and nothing was measuring that. The 61 tests beside the encoder are all relational — they compare two hashes to each other and none of them says what a hash is.

  Measured (#69): hash-stability.md, and the instrument has never been exercised. Twenty commits have touched the encoder and none of them since the fixtures landed, so fourteen green commits are worth less than they look — the measurement was installed after the movement stopped. What has moved is the vocabulary a body is written in: across 67 commits, 71% of this repository’s own .cho revisions no longer type-check under today’s build, and one label rename (io into io_read and io_write) accounts for 42% of that. The rate a hash-keyed tool would experience is the second one.

• BodyId across a type-checker change. Bodies hash from the AST, not the typed IR, so inference changes do not move them today. Whether that survives M2 — where a body’s meaning depends on effects and linearity that are not syntactically present — is open.

• Cross-version stability. No claim is made that a hash from this build matches one from any other build. The domain tags exist so that claim can be made later.

Struct literal and pattern field order was the fourth entry here and is closed, but not the way it was written. Both halves of the claim were wrong, so the correction is recorded rather than the text quietly replaced.

It said a struct literal “lists its fields in whatever order it likes and the checker reorders them”, making P { x: 1, y: 2 } and P { y: 2, x: 1 } the same value hashing differently. The checker does not reorder them — it refuses the second spelling:

field `x` is written after `y`, but `P` declares it before; a struct literal's fields run in declaration order, so writing them in another order would hide what runs first

That is defined-behaviour.md §3 doing its job — the order you read is the order it runs — and it means there was never a gap here. There is only one spelling of a given literal, so the hash could not disagree with the value.

It also said the destructuring pattern had “the same gap for the same reason — the declaration’s order is not known where the encoder runs”. That gap was real: let P { y, x } = p compiles and used to hash differently from let P { x, y } = p, though a pattern binds by name and runs nothing. But the stated reason was wrong twice over. The encoder holds the whole Ast and could look a declaration up; and it does not need to, because sorting by name settles it without a lookup and is the better rule anyway — it also survives a struct reordering its own fields, which binds nothing different and should move no body’s hash.

So the pattern’s field names are now sorted where they are encoded. The binders are sorted with them, because they are positional from the destructure onwards: encoding [x, y] while pushing [y, x] would give two programs that bind differently the same bytes, and a collision is worse than the spurious difference being removed. There is a test for that, and one for shadowing.

A tuple destructuring and an enum pattern’s bindings are positional and stay that way: let (a, b) = t and let (b, a) = t are different programs.

Defined behaviour

Status: settled for what exists; the open list at the end is what does not exist yet. Written for M3 (#1), and implemented in the same slice rather than after it — every rule below has a fixture, and the ones that end a process have a conformance test that runs the binary and checks it died.

C and Rust both leave behaviour open in places, and C leaves it open in the places that matter most. This document is the list of those places and what cancho defines them to instead.

This is not pedantry, and it is not a safety feature bolted on the side. It is what makes the rest of the project mean anything: content-addressing, replay and attestation are claims about a program’s behaviour, and a program with undefined behaviour has no behaviour to make claims about. A hash over source that can compile to two different answers is a hash over nothing.

1. The rule

Every operation either produces a defined result or ends the process. Nothing is left to the implementation, the optimiser, or the target.

There is no third outcome. In particular there is no “this is undefined, so the compiler may assume it never happens” — the assumption C makes, which is where its worst miscompilations come from.

Ending the process is a trap: the instruction stream contains an instruction that faults, the operating system kills the process, and the exit status says so. On both supported targets that is SIGILL. A trap is not a panic: there is no unwinding, no handler, no destructor, nothing to catch. The program stops.

Trapping is not a cop-out. A trap is deterministic — the same input traps on every target, every run, every build — which is exactly what undefined behaviour is not.

2. Integers

int is 64-bit, two’s complement, signed. There is one integer type; unsigned types and other widths are not in the language yet (§8).

2.1 Overflow traps

+, -, * and unary - produce the mathematically correct result, or they trap. They never wrap.

let n = 9223372036854775807;
n + 1                      // traps
0 - (0 - 9223372036854775807 - 1)   // traps: -int::MIN has no counterpart

Wrapping silently is defined behaviour — C has it for unsigned types, Rust has it in release builds — so it would satisfy §1. It is refused anyway, on the same grounds division by zero is: a silently wrong answer is worse than a stopped process, because the wrong answer propagates and the stop does not. A checksum that wraps is doing arithmetic; a balance that wraps is a bug that will be found somewhere else, later, by someone else.

The cost is real and is paid on purpose: every addition is a checked addition.

This paragraph used to say “a branch that is never taken is close to free on both targets, and ‘close to free’ is the right price for an answer that is always right.” The first half is true and the second half was a guess. Measured (docs/overflow-cost.md): the branch costs 2.8% where calls dominate and 3.6% where memory does — close to free, as claimed. But an arithmetic-bound reduction pays 40%, and not because of the branch: a trap is observable, so the additions cannot be reassociated, so the loop cannot vectorise. The same guarantee costs clang 46% and gcc 74% on the same loop, which is how we know it is the semantics rather than the backend.

None of that changes the argument above — a silently wrong answer still propagates where a stopped process does not — but the price is a range with a rule attached, not a number: it is whether arithmetic is on the critical path. §2.2 exists for the loops where it is.

2.2 Wrapping is spelled out

Wraparound is the intent in a hash, a checksum, a PRNG or a cycle counter, and a language that cannot express it forces a workaround worse than the thing it forbids. So the three wrapping operations exist as builtins:

wrapping_add(a, b)
wrapping_sub(a, b)
wrapping_mul(a, b)

Each is two’s-complement wraparound, defined for every input, and never traps. The asymmetry is the point: + is what you write when you mean arithmetic, wrapping_add is what you write when you mean the bits. You cannot get the second by accident.

There is deliberately no wrapping division: / has no overflow case that wrapping would help with (see below).

2.3 Division and remainder

/ and % trap on two inputs:

• a zero divisor — there is no answer, and C’s answer is undefined;
• int::MIN / -1 — the quotient has no representation, which is the same overflow as §2.1 and traps for the same reason.

int::MIN % -1 was in that second row until emitted-checks.md §4.1 read the binary, and it does not trap: a % -1 is 0, for every dividend including int::MIN, and 0 is representable where the quotient is not. The reason this document gave was the quotient’s, borrowed by an operator that produces no quotient. The compiler was right and the rule was wrong, and §4.2 there records that the constant folder had copied the rule rather than the compiler — so the same expression was a compile error written down and a 0 computed.

Otherwise division truncates toward zero and the remainder takes the sign of the dividend, which is C99’s rule and Rust’s:

 7 /  3 ==  2       7 %  3 ==  1
-7 /  3 == -2      -7 %  3 == -1
 7 / -3 == -2       7 % -3 ==  1

2.4 Literals

An integer literal that does not fit in int is refused by the parser, not truncated. 007, 7 and 0_0_7 are the same value and the same hash: the AST stores the value, never the spelling.

3. Evaluation order

Left to right, everywhere, always. Every rule below is a consequence of that one, and each is enforced rather than merely intended.

• Binary operators evaluate the left operand, then the right. f() + g() runs f first.

• && and || short-circuit. The right operand is not evaluated when the left already decides the answer. These are the only operators that skip an operand, and they are control flow rather than instructions.

• Call arguments evaluate left to right, all of them, before the call. This includes arguments a builtin discards: a capability argument is checked and erased, but an expression that computes one still runs.

• Enum payloads evaluate left to right, in the order written, which is also the order declared — a variant’s payload is positional.

• Struct literal fields run in declaration order, and writing them in any other order is refused rather than silently reordered:

  struct P { x: int, y: int }
  P { y: f(), x: g() }     // ✗ refused: `x` is declared before `y`
  

  A struct’s fields are laid out and evaluated in declaration order, so a literal written the other way round would run g() before f() while reading as though it did the opposite. In a language whose whole argument is that effects are visible in the text, having side effects reorder underneath the text is the wrong trade. The order you read is the order it runs, and the compiler keeps it that way.

• Assignment evaluates the right-hand side first, then the place. For r.f = g() that means g() runs before r is evaluated. Nothing in the language can currently observe the difference — a place is a binding or a field through a reference, neither of which can have a side effect — and it is written down here so that it stays true when places grow.

4. Memory

• There is no uninitialised memory. let and var both require an initialiser; the grammar has no form that declares a binding without a value. So there is nothing to read before it is written.
• There are no null references. A reference comes from borrow or from alloc, and both produce one that points at something.
• There are no dangling references. A reference’s region is a block, and nothing whose type mentions that region leaves it (linearity-and-effects.md §5, §6). The check is an occurs-check over one type, not an analysis.
• Every index is bounds-checked, and an out-of-range one traps. s[i] compares i against the length the slice carries, and the comparison is unsigned — so a negative index, read as an enormous unsigned one, is caught by the same instruction as an index past the end. There is no unchecked form and no release mode that removes the check: reading past the end of an allocation is the undefined behaviour §1 says this language does not have.
• byte_of traps outside 0..255 rather than truncating (strings.md §2), and one unsigned comparison covers both ends, so byte_of(-1) dies with byte_of(256). int_of is always defined and always lands in 0..255, which is why it widens unsigned.
• A slice’s length is checked where it is made. alloc_slice[a](n, v) traps on a negative n, and the byte count n * stride is a checked multiplication like any other (§2.1) — an overflowing length would otherwise ask the arena for less memory than it is about to write.
• Arena exhaustion traps. An arena is one 64 KiB chunk; asking for more than it holds kills the process rather than writing past the end of the allocation (§6 of linearity-and-effects.md). Growing the chunk would make release a walk instead of one free, and that trade has not been made.
• Allocation failure traps. If malloc returns null when a region opens, the process dies there rather than storing through it.
• No aliasing rules to violate. There is no restrict, no noalias and no pointer provenance to lose, because the language has no raw pointers. Two copies of one &!r alias, and that is defined: they are two copies of one address, and writes through them land in the order they run.

5. Layout

Struct fields are laid out in declaration order. A value is scalarised into leaves — an int or a bool is one leaf, a struct is its fields’ leaves in order, an enum is a tag leaf followed by the widest variant’s — and where a value has to live in memory, each leaf takes 8 bytes. A reference is one leaf, a pointer; a slice is two, a pointer and a length, because [T] is the one referent whose size is not in its type. A slice’s elements are contiguous, each one stride apart — the leaf count times 8, except for byte, which is packed one per byte (strings.md §3). That is the only size in the language that is not a multiple of 8, and it is confined to byte so that a string is something C could read.

This is deterministic, and the same compiler on the same source produces the same layout every time. It is not yet a stability contract. Nothing depends on it across processes: no aggregate crosses the FFI boundary (§8.4 refuses one), nothing is serialised, and layout does not reach any hash. When something does depend on it, the rule and its guarantees go in canonical-ast.md beside the other invariants, and this paragraph gets shorter.

6. The foreign boundary

C’s behaviour is C’s. What this language defines is what reaches it:

• only int, bool and () cross, plus borrowed capabilities, which do not cross at all (linearity-and-effects.md §8.4);
• int at the boundary is the platform’s 64-bit integer, not C’s int;
• a value narrowed on the way out — putchar’s character reaches libc as a 32-bit int — is truncated by two’s-complement truncation, which is defined, and what libc does with it afterwards is C’s rule, not ours.

Past that point the guarantee stops, and it stops visibly: reaching C at all requires an Ffi capability, and the effect row of every caller above says so. That is the trade §8.4 makes — C’s effects are not eliminated, they are made impossible to reach silently.

7. What is not defined, and never will be

Nothing. There is no list of “implementation-defined” behaviour and no “unspecified” category. If an operation exists, this document says what it does or says that it traps.

8. What does not exist yet

These are not undefined — they are absent. Each gets a rule here in the slice that adds it, before the code that needs one:

9. How this is enforced

Not by assertion. Every rule above is a fixture:

A rule with no fixture is a rule this project does not have.

And a rule with no price is a rule nobody has finished arguing for. overflow-cost.md prices the overflow trap and check-cost.md prices the rest: of the eight checks above that can appear in a loop body, six make their operation non-reassociable, the worst being truncate(f) at 3.35×, and the three that are free are free for three unrelated reasons. None of that is an argument against the rules — a silently wrong answer is what §2.1 exists to refuse — but the cost of a guarantee belongs next to the guarantee.

poison.md prices the one alternative anybody has proposed, a flag reduced at a boundary instead of a stop, and finds it a good trade for per-element checks and no help at all for the overflow check carried by a reduction. It would be a change to §2.1 rather than an optimisation underneath it, because what it gives up is where — and a defined-but-wrong fallback used until the boundary is the silently wrong answer §2.1 is about.

Reading through a reference

Status: settled, and built in the same change. The gate for the two limits heap.md §3.0 and §4.1 found and did not fix. They looked like two problems and are one, which is why they get one document.

1. One gap, two symptoms

This language can make references — borrow, &!a T from an arena, contents on a box — and it can follow them in exactly two ways: field access (h.fd) and indexing (s[n]). That is all.

Two things fall out of the hole that leaves.

A scalar behind a reference cannot be read. &r int has existed since M2 and there has never been a way to get the int out of one. heap.md §3.0 records it: contents on a Box[int] hands back a reference with nothing you can do to it.

A recursive structure cannot be read without destroying it. match requires ownership, so taking a list apart to look at it is taking it apart. heap.md §4.1 records it, and examples/tree.cho is built around it: the walk that prints the tree is the walk that frees it, because no other walk is expressible.

The second is the one that matters. A structure you can only read by consuming is a structure you can read once, and “traverse this twice” is not an exotic requirement — it is len then sum.

2. The rule

A reference gives references.

Matching &r E binds every payload as a reference into the enum, carrying the scrutinee’s mode and its region:

match list {                       // list: &l List
    List::Empty => { .. }
    List::Cons(value, rest) => { .. }   // value: &l int, rest: &l Box[List]
}

Nothing moves out of a reference, ever. That single sentence is the whole type rule, and it is what keeps linearity intact: a payload that is res binds as a borrow of that res, so no obligation is created, nothing is consumed, and the scrutinee is exactly as owned after the match as before it.

2.0 The same rule, for field access

Stated here for match, and it holds for the other way to reach into a value. Field access is not an exception, and for two separate stretches it was one.

The rule decides what comes back, not whether anything does:

A val field is copied out, which costs the referent nothing and is what a reference is for. A res field cannot be copied — that is what res means — so what comes back is a reference to it, exactly as match on a reference binds a res payload. h.held on a &r Holder is a &r Box[int], carrying the base’s mode and its region: a field of a &!r is reachable uniquely, a field of a &r is not, and either way the field’s reference lives exactly as long as the one it was reached through.

The remaining difference in that table — a val field copies where a val payload borrows — is the ergonomic one, and it is the reason b.used is not *b.used.

The hole this closed, twice

Reading a res field through a reference was first allowed and unsound. It produced a second owner of a value the referent still owned, and under valgrind that was an Invalid free() from ordinary code with no unsafe anywhere — which this language does not have. It contradicted heap.md §3.1’s “a double free is unexpressible”.

It was then refused outright, which fixed the unsoundness and overshot: a struct with a res field could not be read through a reference at all, while the equivalent enum could. Two standard-library modules paid for that with an accessor that takes the whole value and hands it back — std.buffer’s write and std.vec’s get — and collections.md §5.1 recorded it as the next thing to settle.

A borrow is the answer to both, and the reason is worth stating plainly: the double free was never about reading, it was about owning. So the refusal belongs at the use rather than at the read, and it is already there. Every route to a second owner is refused by the ordinary type rule, because &r Box[int] is not Box[int]:

unbox(heap, holder.held)          // expected `Box[?0]`, found `&r Box[int]`
Holder { held: holder.held }      // expected `Box[int]`, found `&r Box[int]`
return holder.held;               // expected `Box[int]`, found `&r Box[int]`

That is one rule doing the work two were doing, and the surviving one is the rule the language already had.

Reaching a res field on an owner is still refused

Unchanged, and for a different reason: there is no reference involved, so reading the field would move it out of a value that is still whole, leaving a half-consumed aggregate the checker cannot describe. Take it apart with a destructuring let, which names every part at once.

2.1 Why not Rust’s binding modes

Rust infers whether a pattern binding is a move, a copy, a & or a &mut, from the scrutinee and the pattern together. It is genuinely convenient and it is genuinely subtle — the rules have been revised more than once, and “what mode is this binding in” is a question a reader has to reconstruct.

This language does not do implicit. The rule above has no modes to infer and no defaults to remember: match an owned enum and you get owned payloads, match a reference and you get references of the same mode. Which one you are in is visible in the scrutinee, one line up.

2.2 Two unique bindings from one match

match on &!r E binds each payload as &!r T — several unique references at once, into one referent.

That is sound for the same reason two fields of a struct can both be written: the payload positions of a single variant are disjoint. They are different offsets in the same value, no two patterns name the same one, and a variant’s payload cannot overlap itself. Nothing here needs an aliasing analysis; it needs the layout, which the backend already has.

3. *r — the dereference

*r          // r: &q T  ->  T,  when T is `val`
*r = v      // r: &!q T,  when T is `val`

Reading copies the value out. Writing replaces it. Both require T to be val:

• copying a res out of a reference would duplicate an obligation — two values, one of which nobody is required to consume. §4 exists to make that impossible and this does not get an exception;
• writing over a res would drop whatever was there without naming a consumer, which is the same silent drop assign_over_live_res.cho already refuses.

A res behind a reference is read the way it always was — by borrowing it further, or by field access — and ended by whatever function ends it, on the owner.

* is prefix, so it never collides with multiplication: a * *b is a product of a and what b points at, and the parser knows which position it is in. It binds tighter than any binary operator and looser than postfix, so *p.x is *(p.x) and (*p).x is written with the parentheses — which p.x already does for you, since field access reaches through a reference on its own.

4. What this unlocks

A read-only traversal of a recursive structure, which is the thing that was impossible:

fn total[&l](list: &l List) -> [] int {
    match list {
        List::Empty => { return 0; }
        List::Cons(value, rest) => { return *value + total(contents(rest)); }
    }
}

value is &l int and *value reads it. rest is &l Box[List], contents follows the box to &l List, and the recursion borrows for exactly as long as this frame does. The list is not touched: it is still owned by the caller, still owes exactly one traversal that ends it, and can be read as many times as anyone likes first.

examples/tree.cho stops having to compute everything in the pass that frees: contains, deepest and tally take &t Tree, hold no capability at all, and leave the tree as owned as they found it. The consuming walk is still there and still the only thing that ends the tree — it simply is no longer the only thing that can look at one.

tests/accept/match_a_reference.cho is the minimal version: a list read three times, then freed once.

5. What this does not add

• No ref patterns and no & patterns. There is one rule and the scrutinee decides it. A pattern that could override the mode would be the inference §2.1 is refusing.
• No moving out of a reference, with or without a marker. res ownership lives with the owner; a reference is a promise to give it back.
• No nested patterns. A pattern is still one variant and a name per payload position, matching M1. Nesting is orthogonal to this and can come later without changing anything here.
• No match on a reference to a struct. A struct is destructured with let, and reaching its fields through a reference already works.

6. Open

7. The must-reject suite

And the accepting counterparts:

The heap

Status: settled, and built in the same change. The gate for the last unchecked box on M2’s list (#1): “escape hatches with documented runtime cost”. §9 of linearity-and-effects.md named two — Rc and Gen — and both are libraries over an allocator that did not exist. This document is that allocator.

It is also the answer to the one thing the README has said was missing since M2: a general heap.

1. What is actually missing

Everything in this language so far lives in a frame or an arena. Both are lexical: a value’s lifetime is a block, and §5’s escape check exists to make sure nothing outlives the block it was written in.

That is a real memory discipline and it covers most programs. What it cannot express is a value whose lifetime is decided by the program rather than by the source text — a node added to a structure that outlives the function that made it, a result handed back up, anything recursive.

The concrete symptom, today:

struct Node { value: int, next: Node }
// error: type `Node` contains itself, so it has no finite size
//        (M1 has no references)

Every linked structure in computing is that declaration plus one indirection. This document adds the indirection.

2. Heap is the fifth capability

linearity-and-effects.md §8.1 listed it first and built it last, for the reason §7.3 gives: a capability for an effect nothing can perform is decoration.

res Heap                      // allocation

It carries no value, like Io and unlike Ffi(library) and Fs(prefix) — there is nothing to narrow, because a heap has no parts to name. It discharges one plain label, heap, and a function that allocates says so:

fn make[&x](h: &!x Heap, n: int) -> [heap] Box[int]

It is borrowed uniquely, like Io and unlike Ffi and Fs. Those two are keys: holding one changes nothing, and two holders at once is the same as one. An allocator has state, and the honest type for shared mutable state is the one that says only one reference reaches it.

split therefore hands back four capabilities:

let Split { io, ffi, fs, heap } = split(world);

which breaks every program in the tree for the third time. §8.1 already calls that the honest cost of there being no ambient authority, and it is still the right trade: a program that does not allocate releases its Heap and says so in one line.

3. Box[T] — one value, one allocation

res Box[T]

Three operations, and they are the whole surface:

box(h: &!x Heap, value: T) -> [heap] Box[T]
unbox(h: &!x Heap, b: Box[T]) -> [heap] T
contents(b: &r Box[T]) -> [] &r T        // and &!r Box[T] -> &!r T

box allocates size_of(T) bytes and moves the value in. unbox consumes the box, frees the allocation, and yields the value back. contents is the dereference: it borrows what the box owns, for exactly as long as the box itself is borrowed, and preserves the borrow’s mode.

borrow b as &r in { total = contents(r).x + contents(r).y; }   // read
borrow mut b as &!w in { contents(w).x = 10; }                 // write

3.0 What contents cannot do, and why that is not the heap’s fault

This language has no dereference operator. A reference is read through field access (h.fd) or indexing (s[n]), and there is no syntax for reading a whole scalar through one — &r int has been unreadable since M2, and nothing in this document changes that.

So contents is what you want for a box of a struct, an enum or a slice, and for a box of an int it hands back a reference with nothing to do. Read a boxed scalar with unbox, which is the operation that was going to end the box anyway.

That is a real sharp edge and it is stated rather than papered over. It is also not a heap problem: the missing thing is a general dereference, it was missing before this document, and giving Box a private one would hide a gap the language should close in the open. §7 lists it.

Box[T] is res whatever T is, including Box[int]. T’s mode says whether the contents must be consumed; the box is res because it owns an allocation, and that is true of a box of anything.

3.1 The heap cannot leak

This is the property worth the whole section.

A Box[T] is a linear resource. §4’s rule is that a res value is consumed exactly once on every path — so a box that is never unboxed is a compile error, at the point the program forgot it, with the same message an unreleased capability gets.

(That this holds at all depends on reading-references.md §2.0, which was added later. Until it was, a res field could be read out of a shared reference — including a Box — which produced a second owner and a real double free. The claim in this section was false for as long as that hole was open, and is true with it closed.)

So in this language, the general heap does not leak. Not “should not”: cannot, checked, before the program runs. Nor can it double-free or use-after-free, for the same reason from the other direction — unbox consumes, and using a consumed value is refused.

That is a stronger claim than either escape hatch in §9 will be able to make. Rc leaks cycles by construction, and says so. A Box does not, because there is nothing for a cycle to be made of: a box is owned by exactly one place, always, and the compiler knows which.

The checker guaranteeing unbox runs is a claim about the program, so the claim about the emitted code is checked separately, two ways:

• under valgrind on linux-x86_64 — one million allocs, one million frees, “in use at exit: 0 bytes in 0 blocks”, no errors;
• in CI on both targets, by the_heap_actually_frees: eight million 2 KiB boxes one at a time, which is one box’s footprint if freeing works and 16 GB if it does not. A regression that dropped the free does not produce a worse number there, it fails outright.

3.2 What it costs

In the spirit of [budget] and §9’s cost table, stated rather than hidden:

No header, no refcount, no tag: Box[T] at run time is a pointer and nothing else, which is why contents is a load and why a box costs the same as the malloc it is. malloc returning NULL traps, the way an exhausted arena does (§6) — this language does not have undefined behaviour to continue into.

4. Recursive types, through a box and only through a box

The size check stays exactly as it was, with one hole in it:

A type may contain itself if every path back to itself passes through a Box.

Because Box[T] is a pointer, it is one leaf however large T is, so the size computation terminates. The refusal in §1 is unchanged for a type that contains itself directly — that still has no finite size, and the error still says so.

enum Tree {
    Leaf,
    Node(Box[Tree], int, Box[Tree]),
}

This is the payoff. It is also, in a linear language, more interesting than it looks:

fn drop_tree[&x](h: &!x Heap, t: Tree) -> [heap] int {
    match t {
        Tree::Leaf => { return 0; }
        Tree::Node(left, value, right) => {
            let l = unbox(h, left);
            let r = unbox(h, right);
            return drop_tree(h, l) + drop_tree(h, r) + 1;
        }
    }
}

Every node is freed exactly once, and a version of this function that forgot a subtree would not compile — left and right are res values produced by the match, and §4 requires both. The traversal that frees a tree and the proof that it freed all of it are the same code.

4.1 Reading a recursive structure means consuming it

The second sharp edge, found the same way as §3.0’s — by writing the fixture.

match requires ownership. A borrowed enum cannot be matched (&l List is refused with “cannot be matched”), and that has been true since M1; nothing about the heap changes it. So there is no way to walk a linked list without taking it apart, and a read-only traversal of a recursive structure is not expressible today.

For a box of a struct this does not bite, because field access already reaches through a reference: contents(r).x reads without consuming, and tests/accept/box_roundtrip.cho does exactly that. It bites for enums, which is what every recursive type needs a variant of.

The consequence is worth stating plainly rather than hiding: in this language today, walking a list frees it. That is a real restriction and also a strangely honest one — the traversal and the proof it released everything are one piece of code, which is the property §3.1 is about. What is missing is matching through a reference, which needs binding modes and is a type-system feature of its own. §7 lists it.

5. Heap or arena?

Both exist on purpose and neither replaces the other. The choice is not about performance first; it is about whether a lifetime is lexical.

The arena is still the right default: bulk lifetime, bulk cost, nothing to track. Reach for a box when a value has to outlive the block that made it, or when a type has to contain itself.

6. What this does not add

• No Box[[T]]. Boxing an unsized referent means a box carrying a length, which is a second shape with its own rules. Slices come from arenas (docs/strings.md §5) and that stays true.
• No Rc, no Gen. §9’s two hatches are libraries, and this language has no module system to put a library in. They also need the thing this document deliberately does not have: a way to share. Both wait, and §9’s cost table already says what they will cost when they arrive.
• No realloc, no growable buffer. Vec is a library over a heap and a copy, and it waits for the same reason.
• No custom allocators. Heap is one capability naming one allocator. An allocator parameter is Rc[h] T’s h, which is §9’s problem.

7. Open

8. The must-reject suite

Stated in advance, as every section of linearity-and-effects.md §11 was.

And the accepting counterparts:

Plus the_heap_actually_frees (§3.1), because whether the emitted code frees is not a property any single program’s types can state.

An allocation that fails traps rather than returning a null nobody checked, the way an exhausted arena does (§6). That one has no conformance test of its own and this document will not claim otherwise: a test would have to exhaust the machine’s memory, where the arena’s chunk is a fixed 64 KiB and can be exhausted in a loop. It is the same trapz on the same malloc result, and exhausting_an_arena_traps_rather_than_running_past_the_chunk covers that shape.

Boxed slices

Status: settled, and built in the same change. heap.md §5 deferred this with one sentence — “Boxing an unsized referent means a box carrying a length, which is a second shape with its own rules” — and §7 listed it as open. This is those rules.

It is the foundation every collection needs. A growable buffer is a boxed slice plus a copy, and Vec, a hash map, a slab and a string builder are all a growable buffer plus a policy.

1. What is missing

A run of values can live in two places today and neither is enough.

An arena slice (alloc_slice[a]) is bounded by its block. That is the whole design of §6 and it is right for what it is for, but a collection that outlives the function that built it cannot be one.

A box (Box[T]) escapes its block, which is the point of heap.md, but it holds exactly one value of a sized type. [T] is unsized — its length is a runtime value — so Box[[T]] was refused.

Between them there is no run of values whose lifetime the program decides. So there is no Vec, no buffer that grows, and no collection at all.

2. The second shape

Box[T] at run time is a pointer and nothing else (heap.md §3.2). Box[[T]] cannot be, because nothing else knows how many elements there are:

A boxed slice is a pointer and a length — two leaves, where an ordinary box is one. The box owns the length, because the length is what was allocated.

That is the same pair &r [T] already is, which is what makes §3’s dereference work without a new rule.

2.1 Elements are val, as everywhere else

Same rule as an arena (§6.1) and for the same reason: ending a boxed slice frees memory and runs nothing, so a linear obligation put inside one would be dropped rather than discharged. The error is the one arenas already give, because it is the same rule rather than a new one.

3. Three operations

box_slice(h: &!x Heap, count: int, fill: T) -> [heap] Box[[T]]
unbox_slice(h: &!x Heap, b: Box[[T]])       -> [heap] int
contents(b: &r Box[[T]])                    -> [] &r [T]

box_slice allocates count elements and writes fill into each, the way alloc_slice does — a loop, because the length is a runtime value, which is what makes it a slice. A negative count traps, and so does a count * stride that overflows: asking for less memory than you are about to write is not a small allocation, it is a mistake.

unbox_slice is a different operation from unbox, and has to be. unbox hands back what the box held; [T] is unsized, so there is nothing to hand back. This frees the allocation and answers how many elements it freed. It is the only consumer a boxed slice has, so §3.1 of heap.md holds here unchanged: a boxed slice that is never unboxed is a compile error, and the heap still cannot leak.

contents is the same contents, mode- and region-preserving, and needed no new rule in the checker at all — a boxed slice’s two leaves are a &r [T], so the dereference that reads a box reads this one too. Only the backend had to learn that it is loading two leaves rather than one.

3.1 What it costs

4. Growing is not an operation

There is no grow, push or realloc, and that is deliberate.

Growing a buffer is: allocate a bigger one, copy, end the old one. Every part of that is already expressible, and writing it as a library rather than a builtin means the policy — double each time? add a fixed amount? — belongs to the program that chose it rather than to the language.

examples/buffer/ is that library: buffer.cho holds a growable byte buffer built on these three operations, and main.cho uses it to build a string whose length nothing knew in advance. It is about sixty lines, and it needed nothing this document did not add.

5. What this does not add

• No realloc. §4. It would also be a lie about cost: realloc can move or extend, and a language whose whole claim is that costs are visible should not hide which one happened.
• No res elements. §2.1.
• No slicing a slice. s[a..b] is a second referent into one allocation, which needs a decision about who owns what and is a different feature.
• No Vec in a standard library. There is no standard library. §4’s example is a library, and it lives with its program.

6. Open

7. The must-reject suite

And the accepting counterparts:

Plus a conformance test: a negative count traps, and so does a count whose byte size overflows.

Sharing

Status: settled and built, and it corrects the document it implements.

§9 of linearity-and-effects.md is the last unbuilt item on M2’s list. It names two escape hatches, Rc and Gen, and says of both:

“both libraries, not language features — neither touches the checker, and that is the point.”

That is true of Gen and false of Rc. This document is what building them found, and §9 now points here.

1. What §9 was for

Linearity says a value has exactly one owner. That is most of why this language can promise no leaks, no double frees and no use-after-free without a garbage collector or a borrow checker.

It also cannot express a graph, an observer, or anything where “who owns this” has no answer. §9 is the admission that such structures exist and the plan for reaching them: two libraries, paying a documented runtime cost, neither of which the checker has to know about.

The plan was right about the cost and about Gen. It was wrong about whether Rc can be written at all.

2. Rc is not expressible, and that is not a small thing

Rc needs N owners of one allocation. An owner has to be a value, so the question is what value could refer to that allocation. This language has three, and none of them works:

• Box[T] is res — used exactly once. Two of them referring to one allocation is precisely what linearity forbids.
• &r T is bounded by its region. An Rc outlives any block, and a reference cannot.
• &static [byte] outlives everything, and there is no way to make one except a literal.

So there is no copyable pointer, and Rc is a copyable pointer with a count attached.

2.1 Three ways to try, three different refusals

This was not reasoned out in the abstract. Each shape was written and compiled, and the compiler refused each for its own reason:

Three rules, none of which was written with Rc in mind, and each of which is individually right. Together they say the same thing: nothing here copies a pointer.

The first refusal has since got plainer, which is worth recording because it makes the argument stronger rather than weaker. reading-references.md §2.0 used to refuse reading a res field through a reference outright; now it hands back a borrow of that field, and rc.held is a &r Box[Cell]. The Rc still does not compile, because the struct literal wants a Box[Cell] it owns and a borrow is not an owner. So what refuses clone is no longer a rule about reading at all — it is the type — and the three refusals are still three, still unrelated, and one of them is now something no design decision had to choose.

2.2 What it would take, and why not yet

A val type that holds a heap address. That is a raw pointer, and adding one would put back exactly the hole this language spent M2 closing: a copyable address is a use-after-free waiting for the allocation to end.

It could be done safely — a pointer whose only consumer is a checked operation, with the count in the allocation — but that is a language feature with its own document, not a library. §9’s “neither touches the checker” is the part that does not survive contact.

2.3 What you can have instead

Shared ownership is not impossible here; the ambient handle is. An Rc whose operations thread a slab — clone(slab, handle), release(slab, handle) — is expressible today, because then the handle is an index rather than a pointer and the slab is the one owner.

That is Gen with a reference count where its generation goes, which is why §9’s own advice — “Gen is the one to prefer” — turns out to be stronger than it knew.

3. Gen is a library, exactly as promised

Credit, added late (#75). A handle that is a plain index plus a generation, checked against the arena that issued it on every use, is Vale’s generational reference. This section was written without saying so; related-work.md §1 now does.

val struct Gen { index: int, generation: int }

Two plain ints. val, so it copies freely; and it points at nothing, which is why copying it is safe. The Slab owns every value, is res, and is ended exactly once like any other resource.

A handle is checked on every use, against the slab it was made for:

1. is the index in range?
2. is that slot live?
3. does its generation match the handle’s?

Any of those failing gives Missing — a value the program decides what to do about. A dangling pointer is undefined behaviour and the program gets no say. §9 says that asymmetry “is most of why this language exists”, and it is the whole reason Gen is worth its cost.

3.1 What it costs

The slab is one boxed slice (boxed-slices.md), so the values are contiguous and the whole thing is one allocation and one free.

Generations are not recycled and int is 64-bit, so a slot would have to be reused more times than a program can count before a stale handle could collide with a live one. This document will not pretend that is a proof; it is a bound, and it is the same one every generational-index library relies on.

4. What building it found about the language

A library is a better test of a language than a test suite is, and this one surfaced three things that made it more verbose than it should be. None is a soundness problem and all three are ergonomics:

• No tuples. (Closed — docs/tuples.md.) insert must answer with both a slab and a handle, so it returns a res struct Inserted { slab, handle } declared for the purpose. Every operation that threads the slab needs one.
• No renaming in a destructuring pattern. (Closed for tuples, by the same change.) let Slab { entries, live } binds those names and no others, so two slabs cannot be taken apart in one scope.
• No shadowing within a block. (Closed — docs/shadowing.md.) Threading a value through several steps means fresh, live, emptied, stale — four names for one slab — because let slab = ... twice in a block is refused.

Together they make value-threading APIs wordy, which is the exact style a linear language pushes you toward. They were listed in §6 rather than fixed here, because each is a language change and this document is a library.

All three were fixed in the two slices after this one, and that is the useful thing about having written them down: docs/tuples.md and docs/shadowing.md are the first features here whose case was made entirely by a library rather than by a design. examples/slab/ has since lost Inserted, Looked, one whole function and seven of the eight names it had for one slab — without weakening a rule, and without its object file changing.

5. What this does not add

• No Rc. §2.
• No raw pointers. §2.2 — and that is the point, not an omission.
• No generic Slab[T]. The library is a slab of int, because monomorphised generics over a boxed slice work but the example is clearer without the extra parameter. Nothing stops a Slab[T].
• No free list. §3.1: insert scans. Making it O(1) is a policy the library would choose, the way buffer.cho chose doubling.

6. Open

7. The suite

Three fixtures for one conclusion, which is unusual and deliberate: the claim in §2 is that Rc fails whichever way it is attempted, and one fixture would only show that it fails one way.

Does &! mean unique? Measured, and the answer is no — twice over

Status: a documented no, and the README asked a question its own table had already answered.

ROADMAP.md’s first what is next row, README.md’s performance section and gpu.md §4 all carry the same open question: &! does not mean what Rust’s &mut means, both(s, s) compiles, and whether to change that is “a real question with a real cost”. The stated cost was “it refuses programs that compile today”.

That is not the cost. Across 82 programs, the rule refuses one fixture, and that fixture exists to document the behaviour being changed. The real cost is in two places neither row named:

1. Provenance across a call is a borrow checker. Two of the three ways to alias a &! today close syntactically. The third does not, and closing it means tracking where a returned reference came from — the machinery README.md’s design commitments rule out by name, two sections above the question.
2. The backend cannot hold the answer. Cranelift 0.121.2 has no noalias. Its whole aliasing vocabulary is three fixed WebAssembly regions, and AbiParam carries no attribute for it. A proved fact would have nowhere to go.

So the performance half of the question is unreachable at both ends, independently, and the correctness half is a research budget rather than a pass. §6 is what would change that.

1. What &! means today

slicing.md §4 already said it, in the opposite direction from the README:

Two copies of one &!r are two copies of one pointer, so writes through them alias correctly rather than racing to be last writer.

&! is a lock on the binding for a block. borrow mut x as &!r in { … } freezes x — nothing may read it, move it, assign to it or borrow it again while the block runs, and linear.rs enforces all four (tests/reject/two_unique_borrows.cho and four siblings). That is a real guarantee and it is the one the language delivers.

What it is not is a promise about references. A &!r T value is val: copyable, storable, returnable. Once one exists, the lock on the binding says nothing about how many copies of the pointer are in flight.

2. The corpus, counted

A temporary probe in crates/cancho-ir/src/lib.rs — at the call-argument loop, and at the lowering of a name to Expr::Load — reported every reference-typed argument’s root place and every read of a &! binding, under an environment variable. The corpus is every program the repository builds: 11 single-file examples, 8 example directories, 53 tests/accept/ fixtures and 10 benchmark programs, 82 programs, each compiled with --std. Counts below are distinct source positions, with the standard library’s own sites counted once rather than once per program.

The counts are from before §3’s four fixtures were added. Those fixtures alias on purpose, so they would each add a row to the table; leaving them out is what makes it a measurement of the corpus rather than of this document.

The single aliasing call site is before in examples/sort/sort.cho (named by function, not line: this sentence said :148 when the call was already on line 177, and a formatter moves lines):

bytes.compare(text[a_at..a_at + a_len], text[b_at..b_at + b_len])

Two overlapping-by-construction views of one buffer, both shared. Rust accepts it, C accepts it, and no uniqueness rule would refuse it. So: in every line of cancho this repository has, nothing aliases a unique reference except the fixtures written to prove it can.

That is the number the ROADMAP row wanted, and it says the rule is cheap. §3 is why cheap is not the same as available.

3. Three routes, and they are not the same difficulty

Each is a tests/accept/ fixture, accepted today, printing 2 — the second write, read back through the first reference.

Route 1 — the same place twice

both(s, s)      // tests/accept/aliasing_same_place_twice.cho

Closed by a syntactic rule: no two reference arguments of one call may share a root place, where the root is found by walking through field projections, indexes and subslices to the binding underneath. Cost, by §2: zero call sites in the corpus. It is the version everyone reaches for first, and it is worth exactly as much as §3.2 leaves it.

Route 2 — a copy into another binding

let t = s;      // tests/accept/aliasing_through_a_copy.cho
both(s, t)

Two roots, one object. Route 1’s rule does not see it, and neither does any rule that reads one expression at a time.

Closing it means a &! reference stops being val: copying one becomes a move, and every ordinary use becomes an implicit reborrow — the reference handed to a call is a fresh borrow that ends when the call does, which is what Rust does silently at every &mut argument.

The reborrow is not optional. Without it the corpus loses 1,943 reads, 154 of them inside the standard library; examples/tour.cho alone reads a &! binding in 372 distinct places. With it, the cost of the move rule is the 2 places that copy a &! into a new binding, both of them in tests/accept/unique_borrow.cho, whose comment says what it is doing:

&!r is val, so it copies — and the copies are copies of one pointer, so writes through them alias rather than racing to be the last writer.

A slice makes the same copy without a binding: alloc_slice[r](4, s) is four aliases of one object (tests/accept/aliasing_in_a_slice_of_references.cho). A struct cannot: a type declaration takes no region parameters, so a field can only name a region that needs none — &static, read-only data that aliases no arena. That asymmetry is the reason route 2 is bounded at all.

Route 3 — laundered through a return

fn head[&a](s: &!a [int]) -> [] &!a [int] { return s[0..1]; }
both(head(s), s)          // tests/accept/aliasing_through_a_return.cho

This one has no syntactic fix. The caller sees two expressions of the same type and no reason to think they touch the same bytes, because nothing in head’s signature says the result borrows the argument.

Regions do not say it. -> [] &!a [int] says the result lives in the same arena as the parameter — and so does every other reference into that arena, including ones with nothing to do with s. A rule that treated same-region as same-object would refuse two unrelated slices of one arena, which is most of what arenas are for. Region identity is not provenance.

Knowing that head’s result borrows head’s argument, and carrying that through the call, is the fact Rust’s lifetimes encode and its borrow checker propagates.

4. What each closure would cost

4.1 Route 1 alone: free, and worth nothing

Zero programs refused, and &! still does not mean unique, because routes 2 and 3 each reach the same aliasing in one extra line. A rule that refuses the obvious spelling of a thing it permits is worse than no rule: it tells a reader — and AGENTS.md tells an agent — that aliasing unique references is refused, which would then be false.

4.2 Routes 1 and 2: cheap, and still not unique

Two fixture sites, plus implicit reborrow, which is real compiler work: 1,943 read sites have to become reborrows that end at the right point, and “the right point” is a scope question the checker currently never asks about references. Route 3 survives, so &! still does not mean unique and no noalias follows.

4.3 Route 3: the non-goal

Two ways to close it:

• Ban the shape. Refuse any function returning a &! in a parameter’s region. The corpus has exactly one such function — std.buffer.room, added because fs_read writes into a buffer the caller must hand it as room before it knows the length (porting.md §9) — and exactly one call site, examples/sort. So the ban costs the standard library a function that a port needed and nothing replaces, in order to rule out a pattern that the same port proved is the honest way to write it.
• Track provenance. The signature says which argument the result borrows from, and the checker propagates it. That is lifetimes, and propagating them is a borrow checker.

README.md’s own design commitments, two sections above the open question:

and its non-goals: “No trait-system maximalism, no GATs, no specialisation, no borrow checker.”

The question was answered before it was asked. What the measurement adds is which fact is the expensive one, so that the answer is a reason rather than a preference.

5. The other end: the backend cannot take the answer

Suppose the checker proved it anyway. The fact has one consumer — the code generator — and cancho generates through Cranelift 0.121.2, which does not have the concept.

• ir::AbiParam is { value_type, purpose, extension }. purpose is Normal | StructArgument | StructReturn | VMContext. There is no aliasing attribute on a parameter.
• The only aliasing vocabulary in the IR is MemFlags’ AliasRegion::{Heap, Table, Vmctx} — three fixed disjoint regions for WebAssembly’s memory model, not a per-pointer restrict.
• noalias does not appear anywhere in cranelift-codegen’s ir.

So the performance claim the README retracted cannot be recovered by fixing the checker alone. It needs the checker and a backend that has the attribute — LLVM, which the same table already names for release builds and gpu.md §1 places outside the next slices.

Two independent blockers is the finding. Either one alone would make this a “not yet”; both make it a different project.

6. What would change the answer

In the order that would make it worth reopening:

Update: threads exist, and the second condition is met. spawn (#128) lets two threads hold copies of one &!; the checker accepted it and the writes raced. Measured in atomics.md §2 (benches/atomics/race.cho: two threads, one counter, updates lost on every run on both backends). The correctness argument is no longer nil. §6.1 closes it for spawn, and only for spawn: routes 2 and 3 are still open everywhere else.

6.1 What spawn does about it

Making &! linear everywhere (route 2’s move rule plus implicit reborrow) is the general fix, and §4.2 says what it costs: 1,943 read sites become reborrows that end at a scope the checker never asks about. A thread needs much less. It needs the one fact route 2 lacked at one call: this reference has been given away and is not back yet.

spawn with a &! payload now lends the reference to the thread, and join ends the loan (linear.rs: Lease, Alias, Bind, Join; lower/conc.rs). Concretely:

• every &! binding has a root – itself, or, when it was initialised or assigned from names that are &! references (let a = r, let h = head(r)), the roots of those. That is the provenance route 2 and the one-call form of route 3 need, kept as a set of slots rather than as a borrow checker;
• spawn(p, f) records a lease on p’s roots. Spawning a second payload with a root already leased, or reading any &! with a leased root (a copy, a field write through it, a call passing it) is borrow-conflict until the handle’s join. The spawning thread is a second writer too;
• the lease ends at join(h) where h is the binding that took the handle, or at join(spawn(..)). A branch must agree on whether it is held, and a loop must leave it as it found it;
• a handle passed on any other way (to a function that joins it, into a tuple) keeps its lease for the rest of the borrow. That refuses a program that would have been fine rather than admitting one that races. (tests/reject/spawn_unique_loop_lease_survives.cho, spawn_unique_branches_disagree.cho.)

What it does not close, stated so it is not read as more:

• a &! parameter handed in twice (f(s, s), route 1) – two parameters are two roots here. f can spawn both;
• a &! fetched out of a slice of references – alloc_slice[r](4, s)’s four aliases of one object (§3, route 2’s slice case), spawn(many[0], f) and spawn(many[1], f). The payload reads many, a slice, not a &!, so no root is found and no lease is taken. A call that is passed the reference (head(r)) is followed, because the &! is read as a name;
• disjoint writes through two &! slices of one buffer (thread-payloads.md T-P3). Not refused or admitted by this; a slice payload is still one leaf too wide;
• the object under borrow shared is &, which nothing writes through, and is unaffected.

Cost, measured: across the repository cargo test --workspace and the 82-program corpus of §2, the only programs this refused were benches/atomics/race.cho and benches/atomics/sb.cho, the two that exist to demonstrate the hole. They no longer compile and are kept, with their measurements, as the record. No tests/accept/ fixture, example or package spawned a &! twice.

Edition and hash. It is a soundness tightening, which editions.md’s opening says should stay a refusal and not become an edition: a program it refuses was already racing, so there is no old edition worth preserving. The refusal is raised by the linearity replay from events lowering already walks; the IR it emits is the same, so no content hash changes (identity.rs is unaffected, and the reject fixtures are the only new files).

The first two are conditions, not work items. If both arrive, the third is a milestone with a design document of its own, and this one is its §1.

Until then &! means what slicing.md §4 said it means — a lock on a binding — and the four fixtures in §3 keep that honest: each is accepted today, so the day one of them is refused, it is a red build and a deliberate decision rather than a drift.

7. What this does not say

• Not that aliasing is safe. It is defined — two writes through one pointer, in program order, last one wins — which is what defined-behaviour.md promises and all it promises. A program that aliases by accident is still wrong; nothing here catches it.
• Not that the rule is hard. Routes 1 and 2 are a few hundred lines. The measurement says they are cheap and insufficient, which is a worse combination than expensive, because it is the one that invites shipping half.
• Not that Rust is ahead on the axis the README claimed. It is, and README.md says so. This document is about what it would take to catch up, not about whether the gap is real.

Collections

Status: settled and built, and the answer is about shape rather than about generics.

The README’s “still missing” line read: a writer abstraction, and Option/Result over resources — neither blocked by the language any more, both wanting a library design. Half of that was right. Writing the library found that the linked collection holds resources and the array one cannot, for a reason no API design gets around, and that saying so out loud needed a bound the language did not have.

1. What was already true

mode-polymorphism.md §1 established that a generic container works at a resource type and a copyable one in the same program, and has since M2. That holds for every collection here:

enum Option[T]     { None, Some(T) }
enum Result[T, E]  { Ok(T), Err(E) }
enum List[T]       { Empty, Cons(T, Box[List[T]]) }

Option[Ticket] is a resource the checker will not let a program forget. Option[int] is copyable. Neither declaration writes a mode keyword, because the mode is computed from the argument — and computing it is what makes one declaration serve both.

Result[Ticket, int] is the case worth naming: two parameters at two different modes in one type. The type is a resource either way, because the mode is a fact about the type and not about which variant a particular value happens to be in. A program holding a Result[Ticket, int] that turned out to be Err still has to consume it — and consuming it is a match, which costs nothing.

So three of the four modules here needed no language change at all. They needed someone to write them and check the claim.

2. The array cannot hold a resource

Vec[T] is the one that does not work, and the reason is not the generics. It is that a Vec keeps its elements in a boxed slice, and a boxed slice holds val data only. Two independent reasons, either of which alone would be enough:

The fill is copied into every element. box_slice(h, n, fill) is one allocation holding n copies of fill, and a linear value cannot be copied at all. There is no uninitialised alternative to reach for: defined-behaviour.md has no uninitialised memory in it.

Freeing the run runs nothing. unbox_slice is one free. It does not walk the elements, because there is nothing to walk them with — this language has no destructors, and heap.md says so as a design decision rather than an omission. An obligation sitting in element 3 would be dropped rather than discharged, which is precisely the affine hole §4 of linearity-and-effects.md refuses everywhere else.

The second reason is the one that closes the question. The first looks like an API problem — hand empty a list of elements instead of a fill, and it goes away. The second does not: however a Vec[Ticket] were built, ending it would have to end every ticket, and nothing in the language can be asked to do that.

2.1 And the list can

A list is a chain of boxes, and unbox hands back what the box held. So taking a list apart produces its elements, one at a time, and a program that wants to end them has each one in its hand as it goes. The walk that reads the list is the walk that frees it, which tests/accept/linked_list.cho has said since M2 — what is new is only that the list is now generic, so it says it for List[Ticket] too.

One allocation per element is the price, and it is a real one. What it buys is the only container a program can put a resource in.

3. So the bound goes on the declaration

std.vec has to say this, and saying it was the one thing the language could not do:

res struct Vec[T: val] { held: Box[[T]], used: int, fill: T }

The vector owns an allocation, so it is res. Its elements are copyable, so T is val. Two modes in one declaration, about two different things — and a val/res keyword cannot express it, because the keyword speaks about the aggregate while this is about a parameter.

Before this, a bound on a type declaration was refused outright, on the grounds that val struct Wrap[T] already means T: val. That reasoning is correct and it is not general:

• A val aggregate is val at every instantiation, which can only hold if every argument is. So saying val is the bound, and writing it again is a second way to say one thing. Still refused.
• A res aggregate promises nothing whatever about its parameters.
• An undeclared one has its mode computed from them, so a bound is a restriction on what may instantiate it rather than a restatement.

In the last two the bound says something new, so it is written. This is mode-polymorphism.md §6’s second open row, answered — and answered the other way from how that row guessed, which had only the val case in view.

There is no [T: res], on a type any more than on a function: an unbounded parameter is already checked as res, so a res bound would change nothing (mode-polymorphism.md §3.2).

3.1 It reaches the hash

A bound narrows what may instantiate the declaration, exactly as narrowing a field’s type would, so two declarations differing only in a bound accept different programs and must be two types. Not through mode_tag, which reads an absent mode as val: that is right for a declaration and wrong here, since unbounded is the stronger check.

3.2 And it is kept at the use site

Vec[Ticket] is refused where the caller wrote Vec[Ticket], naming the bound. That placement is the whole argument for having the bound at all. Without it the program would still be refused — a boxed slice holds val data only — but the refusal would land inside std/vec.cho, pointing at a box_slice call the caller neither wrote nor can change. An error inside a library is the worst possible place for one.

4. A generic function can move a resource, and can never end one

This is the rule the whole library is shaped by, and it falls out of having no way to speak about a T except by moving it.

list.push moves a T into a node. list.pop consumes the list, frees exactly the one node it took apart, and hands the element back:

pub fn pop[T, &h](heap: &!h Heap, list: List[T]) -> [heap] Option[(T, List[T])]

It discharges nothing. After it returns, the caller owes the T. A pop that dropped the element instead would have to be [T: val], and then there would be no way to get a resource out of a list at all.

So list.drop — which ends every element — is [T: val], and over a resource the caller writes the drain itself. That is not a gap in the library so much as the language observing that only the owner of a Ticket knows what ending one means. examples/queue.cho is that loop, eight lines long, and the job it forgets to finish is a compile error rather than a leak.

4.1 The drain is recursive, and that is forced

A while loop that pops until empty leaves a List[T] behind, and the checker cannot see that it is empty — emptiness is a fact about the value, not about the type. So the residual still carries the obligation, and consuming it needs the same drain, which is where it came in.

Recursion has no residual: the base case is Empty, and a match consumes that outright. Every drain in this repository is written that way, and it is worth knowing it is a requirement rather than a taste.

4.2 The bug this turned up

Keeping a declaration’s bound means reading an argument’s mode, and it read it against nothing — so a rigid T came out res however the enclosing function had bounded it:

val struct Wrap[T] { held: T }

fn rewrap[T: val](w: Wrap[T]) -> [] T { ... }
    error: `Wrap` is declared `val`, so its type arguments are `val`
           too, and `T` is `res`

T is bounded val on the line above. A [T: val] function could not name a val aggregate at T at all, which made the bound unusable in exactly the position it exists for. The mode of an argument is now read against the bounds of the declaration the type is written inside.

5. What the module system still owed

Pattern::Variant carried no qualifier. An enum could be named through an import, held, and passed around — and never taken apart, because a match could only name an enum its own module declared.

That is fatal for a library of enums. std.option would have been a type a program could hold and never open. So a pattern takes the same qualifier every other reference does:

match list.pop(heap, queue) {
    option.Option::None => { ... }
    option.Option::Some(pair) => { ... }
}

A module still reaches no hash: what gets encoded is the referenced declaration’s hash, which the qualifier is only used to look up (modules.md §2). The same match written flat and written through an import is one body, and there is a test.

5.1 The asymmetry that was still open — now closed

match on a reference borrows: a reference gives references (reading-references.md §2). Field access on one used to copy, which is why it was refused for a res field — so a struct with a res field could not be read through a reference at all, while the equivalent enum could.

Two library modules paid for that, and both are fixed:

pub fn get[T: val](v: Vec[T], i: int) -> [] (T, Vec[T])    // before
pub fn get[T: val, &v](v: &v Vec[T], i: int) -> [] T       // after

reading-references.md §2.0 now hands back a borrow of a res field, so v.held is a &v Box[[T]] and a getter is a getter. std.buffer’s write lost the same workaround — it takes a &b Buffer and the buffer is not spent by being printed.

The fill this module keeps is not one of those workarounds and stayed: reserve needs a value to fill a bigger run with, and keeping a spare T is free precisely because T is val.

6. The modules

is_some, is_ok and length take a reference, which is what lets them work over a resource: reading an Option[Ticket] that way costs the caller nothing, where taking it by value would hand over a ticket the caller still owes.

7. Open

8. The suite

Testing a program written here, not the compiler that builds it

Status: built. §2’s primitive (trap(), and std.test’s assert/assert_eq/assert_ne on it) is on both backends, and §3’s runner is cancho test. A program — an agent’s or a person’s — had no way to state “this must be true” at all before this, not even that. What is not built is listed in §5: no per-test timeout, no message on a failed assertion, nothing generic over T.

1. What was missing, and how it was found

An agent-usability survey this session — not a hunt for a specific bug, a direct question about what the toolchain still lacked for real use — found that cargo test (crates/cancho/tests/conformance/) is purely internal to developing the compiler itself, and that nothing comparable exists for a program written in cancho. The real path to testing one’s own function, before this document, was: write another .cho file, compare values with if/==, and return a distinct int as the process exit status. No assertion, no failure message, no way to tell “this test failed” from “this program computed 1” apart from reading the number back and remembering what it meant.

That gap outranked several stdlib holes found the same session (std.vec missing pop/remove/insert, no regex, no readdir) because it is not a missing convenience — it is the thing that would let an agent (or anyone) trust code it just wrote, here, rather than eyeballing it.

2. trap(), and assert built on it

This repository’s own answer to “an assumption failed” has been a trap since M0: no message, no exception, SIGILL on both targets, exactly like an overflowing + or an out-of-range index (docs/defined-behaviour.md §1). Every existing trap is the compiler’s own arithmetic or bounds check firing on its own. Nothing let a program reach that outcome deliberately — there was no primitive to build assert out of.

trap() is that primitive: no arguments, [] int like byte_of’s own fixed signature (the int is never actually produced, since the call never returns, but the type checker needs a result type to check the call site the ordinary way), no capability, because deciding to trap is not an effect on the world. Both backends already carried the one instruction this needs — Cranelift’s trapnz/trap, the LLVM backend’s own trap_if (ud2 on x86-64, udf #0xc11f on aarch64, the same instruction docs/llvm-backend.md §3.2/§3.3 already measured for every checked operation) — so this is the first builtin that reaches it unconditionally rather than behind a check the compiler emits on its own, and adding it was mechanical on both: one trap(TrapCode::unwrap_user(1)) plus a fresh dead block in cancho-codegen, one trap_if("true") in cancho-codegen-llvm.

std.test.assert(condition: bool) -> [] int is a library function built on it, not a second builtin:

pub fn assert(condition: bool) -> [] int {
    if condition {
        return 0;
    }
    return trap();
}

A library function rather than a builtin for the same reason std.buffer’s doubling policy is a library and not a builtin (docs/boxed-slices.md §4): deciding when to trap is the caller’s policy — trap() is the primitive, assert is one way to use it, and nothing stops a program from writing its own. assert_eq/assert_ne are assert(a == b)/assert(a != b) spelled out, over int, the same way docs/collections.md’s own unwrap_or spells out a two-line match: not a new primitive, a name for the line every caller would otherwise write for itself.

tests/accept/assert.cho is the pass side, checked against its own //~ STDOUT///~ EXIT the ordinary way. The fail side cannot be: a trap is not a value a program’s return can produce, so traps.rs::assert_fails_the_same_way_every_other_trap_does checks it the way every other trap fixture here is checked — built, run, and confirmed killed by a signal (run.status.code() == None), not exited.

3. The runner: cancho test

This language has no macros and no reflection (README.md’s own “what’s deliberately not here”), so nothing can enumerate a program’s own declarations from inside it. cancho test some_file.cho does it from outside: it parses each named file, takes every fn test_*, writes a main that runs whichever one argv[1] names, builds once, and runs the executable once per test, because a trap kills the process it happens in and a runner has to survive one test’s failure to report the next (crates/cancho/src/test_cli.rs).

$ cancho test --std ok.cho
running 4 tests
test test_add ... ok
test test_returns_nonzero ... FAILED
test test_traps ... FAILED
test test_with_caps ... ok

failures:

---- test_returns_nonzero ----
returned 7, and a test answers 0 to pass

---- test_traps ----
trapped: killed by signal 4 (SIGILL, the trap every checked operation ends with)

test result: FAILED. 2 passed; 2 failed

The shape of a test. fn test_x[regions](caps) -> [row] int: no type parameters, returns int, and every parameter is a unique reference to Heap or to Io, at most one of each. It answers 0 to pass; anything else, or a signal, is a failure. A fn test_* of any other shape is refused with exit 2 rather than skipped, because a test that silently did not run reads as a pass. A test in a module other than the root must be pub, since the runner reaches it from outside.

Capabilities (the row this closes in §5). A test that needs a heap or the console declares it, exactly as main would: the synthesized main splits World, releases ffi/fs/args, borrows heap and io uniquely, passes each test the ones it names, and releases them after. The row is exact, as everywhere here ([heap] on a test that never touches the heap is a refusal), so a test that asks for Io has to use it.

No main in a test file. The runner supplies its own, so a file that declares a root-module main is refused with exit 2.

Exit codes. 0 every test passed; 4 the program built and at least one test failed (a new code, test only, so a caller can tell a red test from 1, “the program was refused”, a broken build); 2 no test_* functions were found — a run that found none is not a pass — or one has the wrong shape; 3 the environment failed. A status that is a multiple of 256 would read back as 0 as a process exit, so the synthesized main answers 1 for it instead.

4. What this does not propose

Not a message on a failed assertion. Every trap in this language is message-less by design (§2’s whole argument), and assert inherits that rather than becoming the one trap that carries text — a caller that wants to know which assertion failed reaches for check --output json’s located diagnostics at compile time, or reads the source at the line a debugger stops on at run time, the same way any other trap here is diagnosed.

Not assert_eq/assert_ne over anything but int. A generic version wants == over an arbitrary T, which this language does not have for every type (docs/collections.md never built one either) — open, not answered here, the same way docs/collections.md §7 leaves map/and_then open for want of closures.

5. Open

satisfy: a contract a candidate must meet

Status: designed, then the smallest slice built (#406). What exists and is composed, unchanged: the checker (cancho check, every refusal as data), the test runner (cancho test, docs/testing.md §3), and cancho-id’s per-declaration identity. What is new here is the composition being a command with a verdict, and one addition to it: the contract pins the SigId the caller depends on, so satisfaction is against a specific identity, not a name.

1. What a contract is

A contract is a .cho file — the only language the checker already reads, so a contract is checkable the day it is written and needs no new format, parser or schema:

// contract: max
// sig: 8f13...   (optional: the pinned SigId, `cancho ids` of the declaration)

fn test_max_picks_the_larger() -> [] int {
    if max(3, 7) != 7 { return 1; }
    ...
}

Three parts, two of them free:

1. The signature — implied by the contract’s own tests: they call the candidate by name, so a candidate with the wrong arity or parameter types is refused by the ordinary checker, with the rule tag and position check --output json already answers (unknown-name, arity mismatches, type mismatches). A candidate that does not check against the contract’s calls does not get as far as running.
2. The examples — test_* functions with concrete inputs, the shape cancho test already runs. Satisfaction includes them passing.
3. The properties — the same test_* functions, written as witnesses over ranges rather than points (max(i, 100-i) against max(100-i, i) for a hundred values). A property that is not decidable at compile time is witnessed, which is what a test can honestly say; a property that is decidable (min(a,a) == a) is witnessed too, and the difference is the writer’s to state, not the tool’s to guess.

2. What satisfy does

cancho satisfy <contract.cho> <candidate.cho> [--std]:

1. Checks the two files as one program — the contract’s tests against the candidate’s declarations. A refusal here is the ordinary refusal vocabulary, located, as data with --output json.
2. Runs the contract’s tests against the candidate, exactly as cancho test does, one process per test.
3. Answers the verdict as data: satisfied (with the recomputed SigId of each contract-named declaration, so the caller can see what it now depends on), or the refusals / failures that stand between the candidate and the contract.

Exit codes: 0 satisfied, 1 refused (checker), 4 failed (tests) — the same codes check and test already answer, because satisfy is those two commands composed, with the verdict named.

3. What the slice deliberately does not do

• No generation. The candidate is written by an agent or a person; the compiler is the gate, never the author. agent-errors.md §2’s finding holds here too: suggested_transform needs op ids, and this slice does not add them.
• No new trust machinery. The verdict is check plus test, composed. An attestation of satisfaction is the vcs gate’s job (docs/vcs.md), reached through vcs publish of the candidate once it satisfies — nothing here duplicates it.
• No property language. A property is a test function. When the language can express a decidable property as data (a term, not a program), that is a new slice with its own design; today’s honest answer is the witness.

A contract that never calls the candidate is refused (exit 2, like an empty one): the check is syntactic, a call name( to something the candidate declares in the contract’s own source, comments and strings set aside. It is a floor, not a proof of strength: a contract that calls the candidate once and asserts nothing about the result is still satisfied, and so is one that calls it only on a branch no test takes. Strength is the contract author’s, which is the same limit a test suite has.

4. The committed artifact

tests/satisfy/ holds the first real contract and its candidate — std.math’s max, contract with point examples and a commutativity witness, candidate the ordinary if — and CI runs cancho satisfy tests/satisfy/max.contract.cho tests/satisfy/max.candidate.cho --std so the loop’s first end-to-end run is a checked property of the repository, per the issue’s own verification ask.

cancho fmt: one layout, with the comments put back

Status: built. cancho fmt <file|dir>... [--check] (crates/cancho-syntax/src/format.rs, crates/cancho/src/fmt_cli.rs). Applied to every tracked program, and held there by a test (§5).

1. What was missing

cancho print renders one parsed file in canonical form, and says in its own header that it is not a formatter, because it cannot be: comments are discarded by the lexer, so that formatting can never change a content hash (docs/canonical-ast.md §3), and a printer built on the AST can only delete them. So an agent writing cancho had a canonical layout it could not use on a real file, and nothing to hold a codebase to one layout either — cargo fmt --check exists for the compiler’s own Rust, and there was no counterpart for the programs written in this language.

2. How it works

The AST has no comments, no blank lines and no literal spellings, so a formatter cannot work from the AST alone. This one does not try to extend it (that would let layout reach a hash); it uses the text as well:

1. print the parsed file. That is the layout.

2. Tokenise the source and the printed text and align the two token streams. They differ in a short, known list of ways, and the aligner knows each one and nothing else:

   • the printer drops redundant parentheses ((a) + 1 → a + 1);
   • it may add or drop a trailing comma;
   • it spells a literal one way. 'a', 0x10, 1_000 and 1.50 print as 97, 16, 1000 and 1.5, so the source’s spelling is put back — a formatter that rewrote 'a' to 97 would be deleting the one readable thing in the line;
   • else { if .. } prints as else if .. (§3);
   • pub before extern is read and discarded by the parser (ExternDecl has no visibility to keep), so it does not print;
   • every import is written before the first declaration.

   Any other mismatch is not a layout difference, and the formatter stops: the file is reported and left alone.

3. Put each comment where it was, by the token next to it: at the end of the output line that token ended up on, if it was written at the end of a line there; otherwise on its own line above the line of the next token. A comment in the middle of an expression has no stand-alone place, and moves above its statement. Keep one blank line where the source had one or more — never right after a { or right before a }.

4. Check the result (§4), and return it only if every check passes.

3. What it decides

• else if. print used to write an else block holding one if as else { if .. }, one level deeper per link: the parser reads else if as exactly that block, so the two are one AST and one hash, and the ladder was the shape nobody writes. print now writes the chain, so fmt and print agree. This changes print’s output for any program with an else if; no identity moves.
• One statement per line. if c { x = 1; } on one line becomes three. The printer has one layout and this is it.
• Blank lines. One is kept where the source had one or more; one separates items regardless, which print already did.
• Trailing whitespace and CRLF go; \n endings are written.
• A comment’s text is never edited, apart from trailing whitespace.

4. Why it can be trusted

A formatter that is sometimes wrong is worse than none, so format returns text only if the text passes three checks, run on every call:

1. It parses, and print of it equals print of the original: no token changed meaning.
2. It holds the same comments, in the same order.
3. It is a fixed point: formatting it again changes nothing.

A file that fails one is not half-formatted; fmt reports it (path: not formatted: <why>, exit 1) and leaves it as it was. What each check is for was found, not assumed: building the aligner against the repository’s own sources turned up four things the first version could not reproduce — else if (§3, which was a printer problem, not an aligner one), pub extern fn, a dropped } that looked exactly like a printed one (the drops are decided before the matches), and std/ed25519.cho’s import in the middle of the file, which is now at the top.

Measured on the repository: of the 138 programs under std/, examples/, packages/ and tests/accept/, all 138 format, 74 would change, and formatting all 74 leaves cancho ids unchanged for every one of the 80 tests/accept fixtures (a SigId and a BodyId per function — cancho ids before and after, byte for byte), and a second fmt --check over the result finds nothing to do. formatting::every_tracked_program_formats is that sweep as a test, and formatting_never_panics_on_a_damaged_program deletes each line of three real files in turn and formats what is left.

5. What this does not do

• Applied, and kept applied. 93 files under std/, examples/, packages/, tests/accept/ and benches/ changed (1,281 lines added, 817 removed, nearly all of it one-line if c { x; } made three), and formatting::the_repository_is_formatted fails on any of them that stops being canonical. tests/reject/ is left alone: most of it does not parse, on purpose, and its line numbers are what the fixtures assert. The full suite passes unchanged, which is also the check that no identity moved: the conformance tests hash these files.
• No line wrapping. The printer writes one statement per line however long. Wrapping a long call is a layout decision with its own documentation to write, not a side effect of this.
• A comment inside an expression moves (§2.3). It is kept and ordered, not left where it was.
• Imports are not sorted, as print does not (print.rs’s module_header: nothing hashes an import).
• --check and a refusal share exit 1. The first means “would change”, the second “cannot be formatted”; the message says which. A caller that needs them apart reads the prose.

6. Open

std.json: parsing and writing JSON with nothing the caller did not hand it

Status: built. std/json.cho; tests tests/lex/json_*_test.cho (29, run by cancho test), conformance/json.rs; drivers under tests/programs/. Strict RFC 8259; no tree, no allocation of its own. §5 has the numbers, and §6 has the two compiler bugs it found.

1. Why

The question that started this was whether a FastAPI-shaped package is buildable here, and the first thing it needs is the thing every request carries. There was no JSON in the language at all: the VCS op log is JSON on the Rust side, --output json is JSON out of the CLI, and examples/serve writes {"ok":true} as a string literal.

2. The design: a tape, not a tree

A value tree is a heap, a free list and a drop order for every document, and a request handler wants none of them. std.json parses into a tape the caller provides: one flat [int], three ints a node, that points back into the source bytes instead of copying them.

let tape = alloc_slice[a](json.tape_len(body), 0);     // or a heap slice
let nodes = json.parse(body, tape);
let age = json.to_int(body, tape, json.get(body, tape, 0, "age"));

• A node is named by its index; -1 is “no node”, and every accessor answers its zero value for it, so get(get(get(..))) needs no check between steps.
• A string is not decoded until asked for: the node holds the byte range inside the quotes and a flag saying whether it has an escape. A string with none (string_plain) is its bytes in the source, borrowed with no copy (string_view). A number is not converted until asked for: an object is walked for the key and the one value, and the other forty are never turned into anything.
• An object’s children are its pairs in order; a key at node k has its value at k + 1 and the next key at skip(k + 1). at and get are linear in the position, which is what a flat list costs and what a request body of a few dozen fields makes irrelevant.

This is simdjson’s shape, and it is the shape here for a different reason: it is the one that needs no ownership. Everything lives in a slice the caller already knows how to size (tape_len is always enough: a node is at least a byte) and free.

Writing goes the other way, through a Writer that owns a std.buffer, puts the commas, colons and quotes in itself, and is moved through every call like a Buffer is, because growing it replaces the allocation under it.

3. What it decides

3.1 parse_with: no region per call

parse begins region a { let st = alloc_slice[a](2, 0); ... }: two ints of state in an arena made and freed on every call. A caller that parses one large document never notices. A caller that parses a million small ones (JSON lines, one request body after another) pays for the arena a million times, and on macOS that is nearly all of what a call costs. cancho-table’s reader design (docs/readers.md §6) measured it and asked for this.

let st = alloc_slice[a](2, 0);                 // or a heap slice; once
let tape = alloc_slice[a](12288, 0);           // once
let nodes = json.parse_with(line, tape, st);   // per document, no region

st is at least two ints. Their contents on entry do not matter (parse_with sets them), so one st serves any number of documents and nothing of one document is visible to the next. A shorter st is the caller’s bug and traps at the first store, as any index out of range does. parse is unchanged, byte for byte, so no identity that mentions it moved (§3.3). The name is parse_with (open to a better one; readers.md §6 used it for its spike, and it sorts beside parse).

Measured (benches/json_lines.py: 1,000,000 JSON lines of 72 bytes, {"id":..,"status":.., "bytes":..,"path":..,"note":..}, the task per line parse, get of status and bytes, two to_int, a count and a sum; cost per line = (best of 5 runs of 11 rounds − best of 5 runs of 1 round) / 10 rounds / lines, so reading the file drops out; every mode’s answer is compared with the rows’ before it is timed). parse is one tape reused for every line; region is a tape allocated in a region per line, which is what a first version writes.

Per line is wall time over all lines, so a perfectly parallel mode divides by the thread count. parse on the Mac does the opposite: 1.6 µs per line at 16 threads against 0.57 µs at 1, 2.6x slower with 16 threads than with one (2.9x in the re-measured run): a region is a malloc and a free, and this allocator does not scale with threads here (not diagnosed further); parse_with goes from 94 to 9.7 ns, 9.6x. On Linux the arena is cheap (about 30 ns), so the gain at one thread is small (1.02x in the re-measured run, 1.18x in the earlier one), which is what readers.md predicted (283 against 255). The number worth having is the Mac’s: it is where a user’s laptop is, and where “a library function that gets slower when you add threads” costs a day to find.

3.2 The differential

parse_with is the same grammar as parse and a second copy of its body (a call from parse would have been shorter and would have moved parse’s identity, §3.3), so the claim that they agree is tested rather than argued. tests/programs/json_with_diff.cho runs both on every document, into a tape of the right size and into one too short (where the full code and the partial tape come from), with the state slice still holding the previous document’s garbage, and compares the answers and every int of both tapes. conformance/json.rs feeds it 58,733 documents (11,444 accepted, 47,289 refused): the seeds, every prefix of every seed, every short seed with each of 39 pool bytes in each position, 40,000 randomly damaged seeds and the edge documents of the JSON test suites written out (depth 127, 128, 129, 1000 and 100,000, lone surrogates, overlong and truncated UTF-8, a BOM, 01, 1., NaN, comments, trailing bytes). Zero differences. A second test classifies the edge documents with serde_json so that “they agree” cannot mean “both wrong the same way”. scripts/json_with_suite.py runs nst/JSONTestSuite (318 files; not vendored): 95 y_ all accepted, 188 n_ all refused, 10 i_ accepted and 25 refused, parse and parse_with agreeing on all 318, answers and tapes. Breaking parse_with three ways (not resetting the node count, not checking trailing bytes, an off-by-one error position) fails the differential each time (differ 3, differ 37, differ 0 is the document index that caught it).

3.3 Identity

Adding parse_with adds a body and a sig to std.json and changes none: cancho ids --std over a program that imports every std module lists 1,805 identities on origin/main (6a8bc1ed; 1,677 when this was first measured, before more std modules arrived) and the same 1,805 plus those two on this branch (comm finds nothing only on origin/main). Over the programs in tests/ and examples/ that cancho ids can read, 95 list identical identities with and without this change; with --std all 211 differ by exactly those two lines and nothing else. (The earlier run reported 165.)

4. Why it can be trusted

• Numbers: 13,000 of them, bit for bit. conformance/json.rs reads a corpus with Rust’s str::parse::<f64> (correctly rounded) as the reference: random doubles over every exponent in their shortest form, 17-digit decimals, the exact decimal midpoint between two adjacent floats and one digit either side of it (the case a floating-point shortcut gets wrong, built from m * 5^s / 10^s in 128-bit integers), integers on both sides of 2^53 and of int’s ends, subnormals, the overflow edge, and exponents of a million digits. Zero mismatches.

  Corrected: that corpus built its halfway cells only among the normal floats (m of 54 bits, shifts under 26), so “and subnormals” meant random subnormals in their shortest form – which no tie can be – and the claim above said more than it tested. A downstream table reader found that to_float read the exact halfway point between two of the larger subnormals (between about 1e-308 and 2^-1022: the 768 significant digits of (2k+1) * 2^-1075) to the wrong neighbour about half the time: the digit cap was 767, so the final 5 was dropped as a “sticky” digit, the tie became a value above the middle, and it went up whatever the parity. Measured: 33,541 of the 1,000,000 cells of float_text.rs (3.4%; 440 of 1,700 in the first reproduction, and 113 of 400 exact midpoints of 52-bit subnormals) read wrong, none in any other shape. The cap is 768 now. conformance/float_text.rs reads 1,000,000 cells against Rust’s parse – the halfway point, a hair above and a hair below it for every subnormal below 64 units, for the largest subnormals and smallest normals, for 30,000 anywhere, and up to DBL_MAX plus half an ulp (a tie that rounds to infinity) – and scripts/float_differential.py runs the same driver against Python’s float() and against exact rational arithmetic (fractions), 1,000,000 cells, 0 differences. The same run checks to_int against an i128 parse clamped to i64.

• Accept and refuse what serde_json does, over damaged input. Ten valid documents and 1,500 mutations of them (one to two bytes replaced, deleted, inserted, swapped or truncated from a pool of structural and non-ASCII bytes): 291 accepted by both, 1,218 refused by both, no disagreement. Every accepted one is written back out by std.json’s own writer and read by serde_json to the same value. One policy difference, found by it and declared in §3: 1.5e22100 is a number serde_json refuses as out of range and this accepts as an infinity.

• 29 library tests, in the language, on both backends (tests/lex/): every error code with its position, UTF-8 corner cases built byte by byte in a buffer, escape decoding including a surrogate pair, saturation at both ends of int, writer output exact to the byte, and 1,500 floats written and read back to the same bits.

• Misuse traps are checked by building eight misusing programs and confirming each dies by signal.

4.1 The part that was hard: reading a float

A decimal with 15 or fewer digits and a power of ten within 10^±22 is two exact floats and one correctly rounded operation (Clinger’s fast path). Everything else – and a random double printed in 17 digits is the common case – needs exact arithmetic, because m * 10^e in floating point is off by an ulp often enough to break a round trip. slow_decimal does it with std.bignum: the digits (up to 768, the most a halfway point can have, plus a sticky digit for the rest) and the power of ten become bignums, scaled so the quotient has 56–57 bits, divided bit by bit, and rounded on those bits with the remainder as the sticky bit. Limbs are sized to the number (a 17-digit one needs a dozen where a worst-case one needs hundreds), which is what took it from 18 µs to under 1 µs.

5. Measured

tests/programs/json_bench.cho and json_write_bench.cho; timing from outside as the difference between one round and twenty-one, so the byte-at-a-time stdin read is left out. A 4-core sandbox; Python 3.11’s C json, which builds every Python object where the tape builds none – the comparison is real for a handler that touches a few fields and unfair to the tape for one that needs every value, so both columns are given.

Reading

Writing 200,000 small objects (id, name, a score of the form n/8, a bool, a two-element array), 15.7 MB, byte-for-byte the same bytes as json.dumps(separators=(",", ":")):

The honest reading. Scanning is fast and conversion is not uniformly: 17-digit floats are the weak case (about 0.9 µs each, 3.3× slower than Python’s float()), and writing a 17-digit float is slower still (§7). A handler reading a few fields and writing a short reply is at the top of both tables; one that converts 300,000 random doubles is not.

6. Found along the way

Writing a module that is the third to declare a pub fn drop found two compiler bugs, both with their own regression test (conformance/modules.rs, both backends), and modules.md §3.1.1 records them:

• Functions: every function was emitted as lexs_<name>. The type checker accepted two modules each declaring drop; the assembler refused with invalid redefinition of function 'lexs_drop'. Symbols are module.name now.
• Statics (silent, and worse): a static was looked up among every module’s and the first taken, so two modules each with static table read one table. a.first() * 10 + b.first() answered 55 where the tables held 5 and 7. Looked up in its own module now.

And one change outside this module’s files that it needed: std.fmt’s float_into prints a number with a short decimal form (3.5, 19.99, 0.000125) without the exact algorithm (a candidate m / 10^k is checked by one exact division; 10^-k wider than a float’s spacing makes the candidate unique, so it is the shortest and the nearest). That took float writing from 6 µs to under 0.5 µs where it applies, and the existing oracle test (against Rust’s {:e}) now includes 2,000 short decimals and their one-ulp neighbours, which must fall back correctly.

6.1 Splicing a document in: put_fragment

The writer had no way to take an already-written value – a schema another library generated, a stored row, a cached answer – so a service assembling an OpenAPI document or a list response from stored JSON built it by hand with a Buffer and commas, correct only by construction. put_fragment(heap, w, fragment) writes the fragment as the next value, with the writer’s own commas and colons. The fragment is checked: parsed with this module’s strict parser, it must be exactly one value (whitespace around it is fine); a second value, a trailing comma, or nothing traps, for the reason finish traps on an open container – splicing a non-value makes the whole document invalid from a distance. The cost is one pass over the fragment and a tape freed before it returns. (put_raw is the writer’s private helper for null, true and the rest, and is not that: it trusts its text.)

7. What it does not do

8. Open

std.map: a hash map from byte strings to copyable values

Status: built. std/map.cho; tests tests/lex/map_test.cho (5, run by cancho test on both backends); drivers tests/programs/map_bench.cho and map_lookup_bench.cho. Insert, overwrite, lookup, remove, and iteration in insertion order. §5 has the numbers, §7 the compiler bug a benchmark found.

1. Why

json.md §8 listed it: an object with forty members is walked linearly by json.get, which is what a flat tape costs and is fine until it is not. The same shape comes up everywhere a program keys on text it was handed – an HTTP route table, a header set, a symbol table, a cache – and until now a program wrote a Vec of pairs and scanned it.

2. The decision: a key is bytes

A map generic over its key needs a hash and an equality for that key. This language has no traits, so the choice was between passing both as function values on every call (function-values.md), and fixing the key type. Everything keyed on today is bytes: member names, headers, routes, file names, identifiers. So the key is &[byte], and the value is any val type, the same bound std.vec has and for the same two reasons (collections.md §2).

The map copies the key into storage of its own on put, so the slice a caller passes need not outlive the call. key_at hands back a view into that storage, valid until the map is next written to.

A map keyed on integers is not this module. It would be a different hash (an integer needs no byte loop) and no copy; nothing has asked for it, and map.put(h, m, key_bytes_of(n), v) works in the meantime.

3. The structure

slots   [0 | -1 | entry+1 ...]   power-of-two length, at most half full
meta    [start, length, hash, live] per entry
vals    [V] per entry
keys    one Buffer, every key's bytes back to back

Open addressing, linear probing, and the entries themselves in the order they were first put. Three consequences are the interface:

• Iteration is deterministic. 0..entries(m) skipping !is_live is the insertion order, whatever the hash did, so a program that prints a map prints the same bytes on every run and every machine. A key that is overwritten keeps its place; a key removed and put again goes to the end.
• Removal marks, it does not move. remove makes the entry dead and its slot a tombstone (-1). Entry numbers held by a caller stay valid until the next put that finds the entry arrays full, which compacts: live entries are copied in order into arrays sized for twice their number and the dead ones’ key bytes are dropped.
• The table is never more than half full, tombstones included. It is sized from the entry capacity and every tombstone is an entry not yet compacted away, so a probe always reaches an empty slot and the lookup loop needs no bound.

put and remove have the shapes std.vec gave push and pop: put takes the map by value and returns it because growth replaces the storage; remove takes it by unique reference because nothing is replaced.

4. The hash

FNV-1a over the bytes, seeded, then murmur3’s fmix64 finalizer. FNV-1a is one xor and one multiply a byte and is not strong; the finalizer is what makes the low bits – the ones that pick a slot – depend on every byte, so sequential keys (key-0, key-1, …) do not cluster. The 64-bit offset basis has its top bit set and does not parse as a literal (sha512.md), so it is built from halves; wrapping_mul is the multiply and shr33 masks the arithmetic shift into a logical one.

It is not a defence against a hostile key set. An attacker who knows the seed – or the hash, with a seed of zero – can choose keys that all land in one probe chain and make a lookup linear. If keys arrive from outside, pass a per-process seed from a source of randomness. That raises the cost of the attack from “send keys” to “learn the seed”, which is what a seeded non-cryptographic hash can do and what Python and Rust’s defaults also stop at (theirs are stronger hashes; the shape of the defence is the same). A keyed hash such as SipHash is the upgrade if a caller needs more, and it is a change to hash alone.

5. Evidence

Correctness

The last row is how the random test was checked to be able to fail at all. The starting capacity is 4, so the run grows the table many times and compacts it with tombstones in the probe chains.

Speed. One shared, noisy machine; each figure is the spread of three runs, taken as a difference between a short and a long run so the build of the table cancels.

The honest reading is the same ballpark as Rust’s standard map, not faster. Rust’s default hasher is SipHash, built for the hostile-key case §4 declines, so a Rust map with a cheap hasher would be quicker; and its keys are separate allocations where these are one contiguous buffer, which is a layout difference as much as a table one. The Python column is one run.

Put 1M keys, get 1M, remove 500k, get 1M (map_bench.cho), building every key as a string as it goes: cancho 1.2-1.4 s, Rust 1.6-2.2 s, Python 2.4 s. That figure is mostly key construction and allocation, which all three do.

6. What it does not do

7. Found along the way: the LLVM backend grew the stack inside loops

The first benchmark died with SIGSEGV at 30,000 keys. Cranelift ran it correctly; so did the LLVM backend at 20,000.

gdb showed lexs_run’s frame pointer near the top of the stack and its stack pointer exactly 8 MiB lower. The disassembly had lea -0x70(%rax),%rdi; mov %rdi,%rsp inside the loop: a dynamic alloca. The backend emitted an alloca where it was used for the buffer every borrow writes its referent into (a Map is nine words, so 0x70 bytes) and for the one-byte temporary every && and || merges through. An alloca outside the entry block takes stack each time it runs and returns it only when the function does, and mem2reg promotes only entry-block ones. About 30,000 iterations was the 8 MiB.

Every alloca outside the slot prologue is now collected and spliced into the entry block (FuncEmitter::hoist); the cell is the same one each time the code runs, which is all any of these uses wanted. A region inside a loop is covered too: its base and bump cells were the same pattern.

Why nothing caught it. The conformance suite’s loops are short, and where they were long the reference never reached a function the optimiser could not see through, so the alloca was deleted as dead. The regression test (a_loop_body_does_not_grow_the_stack_on_either_backend) took three attempts for exactly that reason: the first two passed on the broken compiler. The version that fails there passes the borrowed value to a non-tail recursive function with a depth known only at run time, so the reference escapes, and runs 20 million iterations of a borrow and a && / ||. It was run against the unfixed backend and fails with SIGSEGV there.

That is the second bug in a row that a library found and a compiler test did not (json.md §6), and the pattern is the same: the compiler was tested on programs written to test the compiler.

8. Open

std.http and std.route: reading a request and choosing a handler

Status: built. std/http.cho (request parser, percent-decoding, query lookup, response head) and std/route.cho (method + path to a route id); tests tests/lex/http_test.cho (8) and route_test.cho (2), run by cancho test; conformance/http.rs; drivers under tests/programs/. No sockets, no allocation of their own beyond the router’s tables. §6 is the evidence, §7 the numbers.

1. Why

json.md was the first piece of a FastAPI-shaped package; this is the second and third. A request arrives as bytes and has to become a method, a path, some headers and a length (std.http), and then a decision about which code runs (std.route). packages/http-request could read a request and stream its body to standard output, which is what the two programs that needed it did, and was no help to a program that wants to look at one.

It is a parser and a router, not a server: nothing here touches a socket, so it works the same on bytes from net.sockets, from a file, or from a test. The server loop, body reading and an end-to-end benchmark against a real framework are the next piece (§8).

2. std.http: the table

parse(src, table) fills a table of integers the caller provides – offsets into src, nothing copied, the shape std.json’s tape has – and answers the offset where the body starts, or a negative error. slots(n) is how big the table must be for n headers; more headers than that is a refusal, not a truncation.

let table = box_slice(heap, http.slots(32), 0);
let n = http.parse(request, contents(w));
if n >= 0 { let id = route.find(router, http.method(request, t), http.path(request, t), p); }

src may hold more than the head (the start of a body, or the next request of a pipelined connection): parse stops at the blank line and never looks past it, and its answer is where to resume.

An error is a value, and says where: 0 - (position * 16 + code), decoded by error_code, error_position and error_message, the encoding std.json uses. One code is not a refusal: 1 means the head has not all arrived, is_incomplete says so, and a server reads more and calls parse again. A head longer than max_head() (64 KiB) with no blank line is code 10, not 1, so a peer cannot make a server buffer without bound.

3. What is refused, and why

The posture is std.json’s: strict, and a refusal says where. Most of what HTTP/1.1 parsers disagree about is how a message ends, and disagreement there is request smuggling: a proxy and a server that read the same bytes as two different requests. So the ambiguous ones are refused.

Line endings are CRLF only; a bare line feed is refused (code 6). A request with a repeated Content-Length that agrees is accepted, because RFC 9112 §6.3 allows collapsing it.

One thing this does not do: a malformed head is refused only once the blank line has arrived, so garbage with no terminator gets code 1 until the limit or the connection’s own timeout, not an immediate 400. A server needs a read timeout regardless, and parsing line by line as bytes arrive would refuse sooner; nothing needs it yet.

After the table, the accessors: method, target, path (before any ?, still percent-encoded), query, version, header_count, header_name/header_value, find_header/header (case-insensitive; write the name lowercase), content_length (-1 for none or chunked), is_chunked, body_start, and keeps_alive (HTTP/1.1 unless it said close, HTTP/1.0 only if it said keep-alive; tokens in a comma-separated Connection value are found).

percent_decode(text, out, plus_is_space) decodes into a buffer you provide and answers the length, or -1 for a malformed or truncated escape or no room – never “pass it through”. query_value(query, key) answers the raw (start, end) of the first key=value, or (-1, -1); a key with no = has an empty value.

respond_head(heap, out, status, content_type, length, keep_alive) appends the status line, Content-Type, Content-Length, Connection and the blank line. It traps on a content_type containing a carriage return, line feed or NUL, and on a status outside 100-999 or a negative length: header injection is a program bug, and the place to find it is the first response, not a client’s cookie jar.

respond_no_content(heap, out, status, keep_alive, extra) is the head of a response with no body at all – 204 No Content and 304 Not Modified – which may not carry a Content-Length (RFC 9110 §8.6, §15.3.5) and have no use for the Content-Type that respond_head always writes. It writes the status line, Connection, the extra lines and the blank line. It traps on any other status (a 200 with no length on a keep-alive connection has no end a client can find) and on a bad extra, like respond_head_with (the final CRLF of extra is optional: http-server.md §13). Found by building a service whose DELETE wanted a 204: respond_head could only say Content-Length: 0 with a type, and the example answered 200 with the deleted record instead.

4. Decisions

5. std.route

A router answers one question: given GET and /users/42/posts, which of the routes a program registered is it, and which parts of the path were parameters? It answers with a route id the program chose, and the program matches on it. There is no registry of function values, so dispatch is a jump the compiler can see, and a handler no route reaches is one reachability can drop.

r = route.add(heap, r, "GET", "/health", 1);
r = route.add(heap, r, "GET", "/users/:id/posts/:post", 2);
r = route.add(heap, r, "GET", "/files/*path", 3);

:name is one non-empty segment; *name, last only, is the rest of the path, even empty. Parameters come back as (start, end) ranges of the path in pattern order, in a table of 2 * most_params(router) ints.

All the rules, because a router with a hidden rule is a router with a security bug:

1. Static first. A pattern with no parameter is found by hash. Only if no static route has the path are the others tried.
2. Of the parameterised, the one added first that fits wins. Not the most specific; the first. Order is the one thing a reader can see.
3. The path is matched as sent. %-escapes are not decoded first: /%75sers does not match /users. The parameters are raw ranges; decode them with http.percent_decode. Exactly one spelling of a path reaches a route, which is what keeps a proxy’s access rule and this router from disagreeing about which route it was.
4. No normalisation. /a/ is not /a; /a//b is not /a/b; an empty segment matches no :param; no redirect is issued.
5. Methods are exact and case-sensitive (RFC 9110 §9.1). get is not GET.
6. 405 is not 404. find answers -2 for a path some route has under another method, -1 for a path no route has. (It does not say which methods, so no Allow header; §8.)

A malformed pattern, an id below zero, an empty method, or a second static route for the same method and path traps at registration – the program is wrong, and a table is written once, at start.

How lookup scales. Parameterised routes are indexed by their first literal segment, so a table of a thousand /svc17/items/:id routes costs a lookup like a table of ten; only routes sharing a first segment, and routes that begin with a parameter, are compared one by one. The first version scanned every parameterised route in order, and §7 has what that cost.

5.1 http.dechunk: a chunked request body

dechunk(src, out) -> (consumed, decoded) reads the chunked body at src[0] (where parse said the body starts) into out. consumed is the bytes of src the whole body took – terminating chunk and blank line included, so a pipelined request is found right after – and decoded the bytes written; consumed is negative when there is no body to return: -1 not all here yet, -2 a size that is not 1-8 hex digits, -3 framing that is not exactly CRLF, -4 too large for out, -5 a chunk extension or trailer. dechunk_incomplete and dechunk_message read the code.

Strict on purpose: extensions and trailers are where smuggling lives, nothing here needs them, and refusing is one line where interpreting them is a page. When more bytes arrive the decode starts again from the first chunk (cost proportional to the body, bounded by out). Tested three ways: unit tests for a good body, every prefix of one (never wrongly refused – that is what lets a server call it again after each read), and each refusal; a differential test against a second decoder written independently in Rust over 600 generated bodies, each mutated four ways and cut once, plus overflow sizes – every one of the six outcomes reached; and two mutations of the decoder (nine digits allowed; a trailer treated as “wait”) each failing it.

6. Evidence

Two things worth saying about how the first of those went. The parser differential passed the first time it ran, which is a reason to read the counts rather than the green: the statistics line is printed by the test and shows 1,089 accepted, not a handful. And the router corpus first produced no “no route” answers at all – a random one-segment route came out as /*rest, which matches everything – so its first version agreed with the reference on a table that could not fail on that axis. Fixed by never generating a root rest route, and the test now asserts every answer occurs more than a hundred times.

7. Measurements

One shared, noisy machine; each figure a spread over three runs, as a difference between a short and a long run. The request is a browser-sized head: 427 bytes, a path with two parameters and a query, 9 headers.

So about four times slower than httparse and about thirty times faster than Python’s parser. Parse and route together are one to two microseconds, which is a million requests a second a core before a socket is involved; the socket is where the time goes.

Before the router was indexed by first segment, parse and route together cost 4.0 µs a request with 100 routes and 17.5 µs with 1,000, linear in the table. After it, the cost is flat from none to 5,000. (The benchmark’s routes have distinct first segments, which is the case the index serves; a thousand routes under one prefix would still be a thousand comparisons, and §8 says so.)

Two optimisations that were tried and measured: the blank-line search went from a general substring scan to one that looks hard only at line feeds (1.35 to 1.0 µs, the whole gain); a compile-time table of character classes instead of comparison chains made no difference, and was kept only because it reads more clearly.

What is not measured here, and not claimed: a request through a real socket, a keep-alive connection, or anything against FastAPI. The first measurement of that, an accept loop, was in the conversation that proposed this work; a router-backed server is the next thing to build.

8. Not done

examples/api: a JSON API server, and what it costs

Status: built, migrated (§8), and the loop extracted into a package (http-server.md). examples/api/api.cho over std.http, std.route, std.json, std.conns and the native socket builtins of native-sockets.md – no Ffi, no extern fn; conformance/api.rs (21 tests over real sockets); the load generator and the references behind §5’s figures are in benches/server/. One thread, keep-alive, pipelining, a JSON API with four routes. §§1-7 describe the first version, a poll(2) loop over Ffi("libc"); §8 says what replaced it and what that cost. Where §§1-7 name poll, send, MSG_DONTWAIT or the net.sockets package they are history, not description.

1. Why

json.md, map.md and http.md built the pieces of a FastAPI-shaped stack and each said the same thing in its last section: no socket loop, so no requests-per-second, so no honest answer to how fast would this be? This is the loop, and §5 is the answer.

It is an example program, not a std module. A server needs Ffi("libc") for read, write, poll and the rest, and std does not hold foreign declarations; the net.sockets package does, and the repository’s own test (the_network_programs_are_counted) insists that package stay the only file that declares bind, listen and accept. So the program imports it, as serve/ and collect/ do, and adds the three declarations nothing else wants: poll, signal, time.

2. The shape

poll(listener + every connection)
  listener readable      -> accept, put the connection in the next slot
  connection readable    -> read what has arrived into its buffer
                            -> answer every complete request at the front of it
                            -> move what is left (the start of the next) to the front
  connection silent too long -> close it

Connections live in a dense array: the poll records, the buffers (16 KiB each, one slab), the fill counts and the last-activity times are indexed together, and closing connection k moves the last one into slot k, bytes and all. The loop visits connections last first so that move only ever touches one already looked at.

What that buys, and conformance/api.rs checks each of them:

Two of those tests were written because a mutation survived. Deleting the move-to-the-front passed every test I had first, because none of them put the start of a request behind a whole one in the same read; deleting the byte copy in the close path passed too, because none closed a connection while the last one held a half-sent head. Each now has a test that fails with the mutation and passes without it.

The write path went through the same exercise, and it was harder, for reasons worth keeping. Making send blocking again failed the stall tests at once (the other clients starve). But deleting the shift of unsent bytes after a partial send survived three versions of the test:

1. The first never made a send partial at all. On Linux loopback a send is whole or refused, never partial – the kernel accepts a whole skb once any room is free – so the resume code ran only for the last hundred bytes of an answer and its shift loop ran zero times. A small receive buffer on the client made the test crawl (a window under one segment and delayed ACKs: about 100 KB/s), and a small SO_SNDBUF still gave whole sends.
2. So the program gained a fourth argument, a send quantum: no send is handed more than that many bytes. It is a plausible fairness knob, and the only deterministic way to make partial sends certain on both operating systems.
3. Even then the mutation survived, because the /blob body was one repeated byte and a chunk sent twice is indistinguishable from the right one. The body is now abcdefghij... repeating, and the test checks every byte’s position.

The last case, a connection that is to close after a large answer, was caught by neither the stall tests nor the refusal tests; its first test could not tell “closed promptly” from “closed by the idle timeout nine seconds later” and passed on the mutation anyway. It now runs with a thirty-second timeout, so only a prompt close passes.

And then macOS failed, which none of the above could have found. The first push went green on Linux and red on macOS, on the two tests about a client that stops reading. The reasoning that followed went wrong twice before the data settled it, and the order is worth keeping:

1. Wrong flag? 0x40 is MSG_WAITALL on macOS. A test of the flag the server chose passed: it picked 0x80, correctly.
2. Bigger kernel buffers, so 32 MB never stalled anything? A Rust probe of how much a loopback connection queues for a non-reading peer: 540 KB on the macOS runner. No.
3. So the only way a client that never reads could be delivered all 32 MB was for the server to have been blocked in send and let go when the client finally read, which also explains the other client’s read timing out. A probe with nothing of ours in the path – a blocking socket, a peer that does not read, send(MSG_DONTWAIT) – blocked on macOS. The flag is not honoured there for a send.

The fix is the timeout, and it was checked the way the rest were: with the flag removed and the timeout kept, the stall tests pass on Linux (Linux behaving as macOS does); with both removed they fail with the same EAGAIN the macOS job reported. That reproduces the failure on the machine I could run on and shows the fix is what cures it.

a_send_to_a_peer_that_is_not_reading_returns_instead_of_waiting is that probe, kept: it sets the timeout and flag as the server does and fails, naming the flags, on a system where a send still waits.

3. Decisions

4. What it answers

GET  /health        {"ok":true}
GET  /users/:id     {"id":42,"name":"user-42"}      400 if :id is not a number
POST /add           {"a":1,"b":2}  ->  {"sum":3}     422 if not two integers; a body that is
                                                     not JSON says what is wrong with it
GET  /search?q=...  {"q":"a b","length":3}           q percent-decoded, `+` a space; length in bytes

and {"error":...} for a path no route has (404), a path with another method (405), a request the parser refuses (400, and the connection closes), a chunked body (501), a request that cannot fit (413) and a head that cannot (431).

5. Measurements

The machine is a shared four-core container, so every figure is the spread of three five-second runs and the ratios are the claim, not the absolute numbers. The load generator is a C program written for this (benches/server/kload.c; closed loop: 2 threads, 16 connections each, every connection sends one request and waits for the whole response, GET /users/42, keep-alive), pinned to two cores; each server to one.

So about ninety percent of what a C loop of the same design does without parsing anything, and roughly forty times FastAPI (the extremes of the two ranges are 33 and 50) on the same core and the same request. Two copies sharing a port with reuseport reached 149,000 - 161,000 (the C one 167,000 - 187,000); with two of the four cores spent on the load generator that is a measure of the generator and the kernel as much as of the server, and is reported as that and not as scaling.

After non-blocking writes (send with MSG_DONTWAIT and a send timeout, per-connection state, POLLOUT bookkeeping), measured in the same session against the blocking version it replaced, three runs each, twice: the blocking version 128,000 - 151,000, the new one 119,000 - 141,000, with the C ceiling itself spread over 123,000 - 150,000 in that session. No measurable regression within the machine’s noise; the point estimates are about four percent apart, which three five-second runs cannot resolve. The figures in the table above are from an earlier, quieter session and are kept as measured.

Memory: 1.5 MB resident idle, 1.6 MB after three seconds under load with 32 connections – the 16 MiB of connection buffers are calloced and touched only as a connection uses them.

What this does not show. It is one request shape, a small answer, on loopback: no TLS, no body larger than a few bytes, no 10,000 connections, no tail latencies (the generator reported throughput, not percentiles; §10 has them now). The Python figures are for this container’s Python 3.11 and this machine; a faster interpreter would shrink the ratio, not close it. FastAPI with two workers measured lower than with one in this setup (1,200); that is the way uvicorn spreads a handful of long-lived connections across workers, not a property of FastAPI, and no multi-worker FastAPI figure is claimed. And the earlier figure in the conversation that proposed this – 27,000 requests a second for cancho against 980 for FastAPI – was a connection per request; this one is keep-alive, which is why both numbers are so much higher and the gap is wider.

6. What it does not do

7. Found along the way

Nothing in the compiler this time, which is worth stating given the last two pieces each found a bug: after two signature slips the compiler caught (a json.is_int call with one argument too many, a local named like a function), the server answered every route correctly on its first run. What the tests found was two places the tests were thin (§2), and one wrong expectation of mine ("a b cé" is seven bytes, not six).

8. Over native sockets: what changed, and the number that fell

native-sockets.md is the account of the builtins; this is what they did to this program.

What went. Four extern fns of its own and eight imported from packages/net-sockets – twelve libc symbols behind Ffi("libc"), which made the authority report say ffi("libc") and nothing else. signal(SIGPIPE) (conn_write cannot raise it), the SO_SNDTIMEO workaround and the per-OS MSG_DONTWAIT flag with the is_linux probe (conn_write does not wait on a non-blocking connection, on either kernel), the SO_REUSE* guesses (a flag on tcp_listen), the hand-built sockaddr_in, and the poll-record byte array and its set_record/move_record (a Poller and tokens). net.lock and the package fetch are gone from the build. cancho authority now reports net_in – naming no port, because the port is an argument – conn_accept, conn_read, conn_write, poll, clock, heap, args and the console, and the_server_holds_no_foreign_authority pins it.

What changed in the loop. Connections are a std.conns.Table, found by slot, and the Poller’s token is the slot plus one. Closing one frees its slot instead of moving the last connection into its place (so the swap-remove, and the test named for it, now check only that closing one never disturbs another). The idle timeout is a once-a-second sweep over the slots with a monotonic clock, not a check made as each connection is visited.

The number. Same machine, same load (2 threads x 16 connections, closed loop, GET /users/42), server on one core, three five-second runs:

A 47% fall, and it is the kernel, not the program. The C reference with the same loop and no parsing falls the same way when its poll is replaced by epoll – about 150,000 to about 80,000 – so the cancho server holds about nine tenths of the C ceiling for either, as it did before. What was ruled out, in order: the extra builtin calls and the ticket round trip (conns.read and conns.write are about one percent of the instructions each, under callgrind); extra syscalls (strace -c: one receive and one send per request and a wait every 20-odd, for both); the clock (19 ns a call, no syscall); O_NONBLOCK (the same with blocking connections); and server CPU (identical – about 390 ticks in the window for both, so each request costs the kernel twice as much). What is left is epoll against poll in this environment: a Firecracker VM, four cores, kernel 6.18, where a persistent wait-queue registration costs every arriving packet a callback that poll – registering only while it waits – never pays. That last step is an inference from the C comparison, not something observed inside the kernel.

What this corrects. native-sockets.md §4 said epoll was “also the scalable answer … a performance change as well as a safety one”. Measured here it is the reverse: poll is faster by about 1.8x at 32 connections and by about 1.8x at 300 (C: 186,000 and 165,000 against 96,000 and 105,000; cancho before and after: 173,000 and 159,000 against 86,000 and 88,000). The crossover where epoll’s O(ready) beats poll’s O(registered) was not found at or below 300 connections; 800 could not be measured (the load generator reported short reads against every server, C included). So the claim is withdrawn until it is measured on hardware that is not a VM. The Poller is the same abstraction either way: a poll(2)-backed one would need a registration table in memory the runtime owns, a larger change than this was, and it is recorded in native-sockets.md §10.4 as the open question it now is.

Still true. Against FastAPI (2,560 - 3,550 in §5) the migrated server is still about twenty-five times faster on the same core and request, down from forty, and at 73,000 it holds about nine tenths of what a C epoll loop does without parsing anything.

9. Gaps closed since

Allow on a 405 (route.allowed, http.respond_head_with) and typed route parameters (route.param_nat, param, param_decoded) – both in http.md §8 – and examples/api uses them: GET /add answers 405 with Allow: POST, and /users/:id and /blob/:n read their number with param_nat instead of a private parser.

10. Tail latency

§5 said “no tail latencies (the generator reports throughput, not percentiles)”. benches/server/kload.c now takes a sixth argument, lat, and prints percentiles in microseconds: from just before a request is written to the whole response having been read, one sample per request, every sample kept and sorted (no sketch). It is a closed loop with K requests in flight a thread, so a sample is a request’s service time plus its wait behind the others in its round – what a client of a busy server sees, not what an idle one does, and the reason these numbers grow with the connection count below. Same machine and placement as §5 (server on one core, load on two others), 32 connections, four seconds, one run each:

What it says. cancho tracks the C loop of the same kind at every percentile – its p99 is within 10% of C’s epoll and its p99.9 is below it – so the loop has no pathological tail of its own; the shape is the kernel’s, which §8 found. The one thing worth noticing is the max of 33 ms in the poll version: one sample in 555,000, a single stall (a scheduler hiccup in a shared VM is the likeliest cause; it did not recur in the later runs and is reported rather than explained away). Against FastAPI the gap is about 45 times at the median and about 80 times at p99, wider than the throughput gap because Python’s tail is long – garbage collection and the event loop’s own scheduling – where this program allocates from a heap it controls.

With 400 connections (the generator could not open more than 256 a thread until this change; it now allocates its connection table) the same server does 84,000 a second at p50 2.9 ms, p99 7.5 ms, p99.9 9.9 ms, max 10.9 ms. That is queueing, not slowness: 400 requests in flight at 84,000 a second is 4.8 ms each by Little’s law, and the p50 is 2.9.

Caveats, and they are the §5 ones plus this: one run each, so a ratio is the claim and a digit is not; a shared VM with a noisy tail of its own; loopback, so no network; FastAPI measured here with the versions this container installs (0.142, uvicorn 0.54) at 2,100 requests a second, a little under §5’s 2,560 – which is the point of keeping the ratio and not the figure.

Chunked request bodies and larger bodies. std.http.dechunk decodes a chunked body into a buffer – strictly: it refuses chunk extensions and trailers (where request smuggling lives, and nothing here needs either), a bare line feed, a size that is not 1-8 hex digits, and a body that would not fit – and the server hands the handler the decoded bytes, so /add cannot tell a chunked POST from one with a length (http.md §5.1). A body that arrives in pieces is decoded again from its first chunk each time more of it does, which costs in proportion to the body and is bounded by the buffer. api’s fifth argument sets the per-connection input buffer from 4 KiB to 1 MiB: a 40 KB JSON body is refused with 413 by default and answered with api 8080 no 9 0 65536. Measured: the decoder agrees with a second, independently written decoder on 3,604 generated and mutated bodies (every outcome reached; two mutations of the decoder each fail the test), and the server’s throughput and tail are unchanged (69,000-72,000 a second, p99 about 0.65 ms).

What is still not done in this server: streaming a body to a handler as it arrives (so a 100 MB upload does not need a 100 MB buffer), Expect: 100-continue, and trailers. (packages/http-server has all three since http-server.md §12: a server that calls limits streams, answers 100 Continue when its application asks, and accepts and discards trailers and chunk extensions. examples/api does not call it.)

http.server: the server loop as a package

Status: built (§7). examples/api/api.cho carried the whole loop – accept, read, parse, frame, pipeline, back-pressure, idle sweep – with the application’s routes inside it. A second server would copy 600 lines. This extracts the loop; docs/server.md stays the account of what the loop does and costs, this says where it lives and why it has this shape. §11 (byte-fed mode, so the loop can sit behind TLS) is built too, and examples/https_hello is the HTTPS server made of it and packages/tls. So is §12 (streaming request bodies and Expect: 100-continue): a body larger than the buffer, in pieces, with the same back-pressure and two timers of its own.

1. What was asked

Take the loop out of the example so a server is its routes and a main. It is the piece cancho-web would build on, and the first package that imports std (package-system.md §4.8).

2. The obvious shape does not type-check

The first design is serve(heap, router, handler, ...): the loop calls a handler it was given. Lex has function values (function-values.md), so this looks free. It is not, and the reason is measured rather than assumed:

fn drive[&k](heap: &!k Heap, h: fn(&k [byte]) -> [] int) -> [heap] int {
    let b = box_slice(heap, 8, byte_of(0));
    borrow mut b as &!bw in { let c = contents(bw); n = h(c[0..4]); }

is refused – bw does not outlive k, so a reference valid for the first cannot be used where the second is expected. A function value’s type may mention only regions already in scope where it is written (function-values.md §4.2, “a type quantified over its own regions (rank 2) is refused”), and the request the loop would hand a handler lives in a buffer the loop borrowed itself. The handler’s parameters would need a region the caller cannot name. So a callback cannot receive a view of the loop’s own buffers, and copying every request into an owned value to get round that costs an allocation per request on the path the benchmark measures.

3. The shape that does: the loop is the application’s

The package owns the state and the work that has no business being rewritten – sockets, framing, pipelining, back-pressure, timeouts – and returns control at the one place the application has something to say:

let srv = server.open(heap, poller, listener, size, chunk, idle);
while true {
    srv = server.wait(heap, srv, clock, listener, 1000);     // I/O, once
    while (k = server.next(heap, srv)) >= 0 {                // a request is in hand
        // server.head / parsed / body: views of the loop's buffers
        // ... the application builds its answer ...
        server.respond(srv, answer);                          // send, or queue
    }
}

The views are ordinary borrows of the Server (&s), valid inside the borrow that reads them – which is what a rank-1 region system is good at, and what a callback is not. The application’s own state is its own variables, which a callback with no closures could not reach at all (function-values.md §4.1).

What stays in the package: everything drain, emit and serve_on did. What moves out: the route table and the handler, which were never the loop’s.

4. The contract

• open takes the Poller and the listener and registers the listener; the server owns the Poller from then on and close ends it.
• wait is the one place that blocks (at most timeout_ms). It accepts, reads, writes what was queued, sweeps idle connections, and leaves a list of connections that hold input. It takes and returns the Server by value because accepting replaces the connection table (std.conns.put grows it).
• next answers the slot of a connection holding one complete request, parsed and (if chunked) decoded, or -1 when none is left. Refusals the loop owns – 400 for a request the parser rejects, 413/431 for one that cannot fit – are answered inside next and never reach the application.
• respond appends the answer to the current connection: straight to the kernel if nothing is queued ahead of it, otherwise to the connection’s output buffer, in order. Once a connection has output waiting next takes no more requests from it: back-pressure is the loop’s, not the application’s.
• The application must call next until -1 before the next wait. A request skipped would sit unanswered; wait therefore finishes any connection next left half-visited and re-queues unvisited ones rather than losing them.