Status: Accepted
Date: October 3, 2026
History: the records this one replaces are archived in docs/history/adr; read them only for how the decision was reached
Answers: ADR-001 D4’s Stage 1 - self-hosting: Nikaia
compiling Nikaia, which said where the road ends and not how it is walked;
the three questions the syntax tree raised (what a Span is, whether
Spanned[T] is a Nikaia generic, how the remaining Rust reads a tree Nikaia
declares) - the owner chose the tree moves whole and a Span is two
u32; the former open-decisions.md, How the ring after
the tree reads the checker’s types - the owner chose moving them whole,
measured first; and the owner’s question whether the move would be cheaper in
bigger pieces, with the cost the move of describe made visible
(#124)
Related: ADR-001 D4 (the staged build: Stage 0 a
transpiler, Stage 1 self-hosting, Stage 2 verification),
ADR-290 (a Nikaia piece joins a Rust program as an ordinary
Cargo module - the route every move takes),
ADR-002 D4 (the committed pre-lowering),
ADR-290 D11 (this language has to be written in),
ADR-286 D1 and Part I 9.1 (a package is a directory, its files
one namespace),
ADR-204 D1 (what a declared type derives),
ADR-246 (the compiler puts the box in),
ADR-285 (u32, u64, a literal as large as a u64),
ADR-290 (a Rust crate’s surface, described),
ADR-100 (a ledger is a file, believed only against its sources),
ADR-286 (? and $V), ADR-285 (a literal pins
nothing)
How is Stage 1 - the compiler’s pipeline in Nikaia - reached from a 44,000-line compiler in Rust, and what does each step decide on the way?
Four questions came up in order, each blocking the next ring of modules:
match a tree Rust declares. Moving it decides what a Span is
(a Range<usize>, where Nikaia has no usize), whether Spanned[T] is a
generic Nikaia writes, and how the Rust that remains reads a tree declared
in the other language. The tree also needed four things the language could
not say: Copy, an i128 literal, a described Rust type (Symbol) that
copies and compares, and Default.sync, throws, keeps, the
checker’s 633 lines over Ty) reads Ty and the ledger’s records. Move
them as they are, or redesign them (interning, as Zig and rustc do) on
the way?slice four times), a table (BESIDE) listed which tool saw
which, and names collided when two were read together.| Compiler | Its answer | Source |
|---|---|---|
| Many languages | bootstrap with a second compiler written from scratch in the new language | §3 |
| Go 1.5 | moved the compiler from C to Go by mechanical translation; the shape of the types did not change during the move - the move and the redesign were kept apart | D13 |
| TypeScript | one Type object per type, created through caches; a text boundary (.d.ts) re-read by the same parser; moving its compiler to another language |
D14 |
rustc |
ty::Ty<'tcx> interned in an arena, compared by pointer; .rmeta binary across units |
D14 |
| Swift | canonical types interned in the ASTContext; .swiftinterface, text |
D14 |
| Zig | InternPool: every type and comptime value a u32 index |
D14 |
rustc (constant arithmetic) |
a declared operand holds every step to its type | D11 |
| Go, Zig, Swift (constants) | an exact number of any size | D11 |
Zig interns for four reasons: its front end is
the build (it has its own back ends), a type is a comptime value, incremental
compilation patches a binary in place, and the workload is several hundred
thousand lines. None holds here today - rustc follows the front end, a type
is not a value (ADR-304 D2), a unit’s boundary is a re-read text ledger, and
the largest unit was 1,197 lines - and each could change, which is why D14’s
answer carries the conditions that reopen it.
| Question | Option | Why it lost / won |
|---|---|---|
| the road | a second compiler from scratch | tested by nothing until it is finished, and finished is 44,000 lines |
| a module at a time, leaves first | chosen: the existing suite tests every step (D1, D2) | |
the largest module first (check) |
it reads everything, so it cannot move until everything it reads has; starting there is starting at the end | |
| the tree | the tree stays Rust, Nikaia reads it as a described crate | needs match over a foreign enum, which describe does not record; the tree would stay Rust for good, and Stage 1 is unreachable by construction |
| a copy of the tree in Nikaia, converted at the boundary | two declarations of one tree, and a conversion on every module call forever | |
| the tree moves whole, the Rust re-exports it | chosen (D6) | |
a Span |
i64 |
a sign nothing uses at twice the width, on every node |
two u32 |
chosen (D7); a source over 4 GiB is refused | |
| a literal | i128 in the language |
one field of the compiler’s tree is not a reason for a number type Part I does not offer |
| a magnitude and a sign | chosen (D9.2) - it is how a literal is written | |
| a fold | in i64, claiming nothing past it |
a sum past i64 would reach rustc unrefused |
| an exact number of any size (Go, Zig, Swift) | buys nothing: every number past 65 bits is refused anyway | |
| a magnitude and a sign, each step held to a pinned type | chosen (D11) | |
| the checker’s types | flatten them into plain data in each module’s adapter (open decision’s option 2) | an adapter per module, deleted again once the types move; the owner declined it |
intern (u32 handles into a pool) |
only if a measurement says so (D14); it did not | |
| move them whole, as values, measured first | chosen (D12-D14) | |
| the files | each tool a one-file program, a table of who sees whom | the cost counted at describe’s move: four copies of one helper, a table, colliding names |
| one package | chosen (D17-D20) |
The .nika is written under crates/nikaia-std/src/tools/, lowered by
nikaia lower-std and committed (ADR-290, ADR-002 D4; how it is lowered is
D18). The compiler’s module keeps its name and its callers and shrinks to the
conversions a Nikaia module cannot write for this crate - an error into
anyhow, an i64 into a usize. The whole test suite is the proof: the
tests that held the Rust module hold the Nikaia one, unchanged or changed only
where a type’s spelling moved.
A module moves once everything it reads is Nikaia or crosses the boundary as
plain data (text, numbers, lists). The leaves - fixed, emit::template,
manifest - go first; then the ring that reads only the syntax tree, which
moves by its own decision (D6-D11); then the ring that reads the checker’s
types (D12-D16). A leaf that pulls in a crate (toml) moves without it: the
crate stays behind the adapter, as D5 lets winnow and clap stay, and what
moves is the module’s own logic.
Never worked around in the .nika - the move exists to find it. A line that
is the language’s own answer (.clone() where ADR-282 D3 says a view stays a
view) is not a workaround; a line bent to avoid a lowering the emitter gets
wrong is, and is not written.
scripts/self_hosting.py counts the lines that say something in each language
scripts/badges.py draws it into the README as the
self-hosted badge. A package that moves a module says the new share in its
changelog entry.Stage 1 is reached when main’s pipeline - read, check, lower - runs
Nikaia from end to end, with Rust left only as adapters to crates (winnow,
clap, the file system). Stage 2 is reached when the lowered compiler
lowers its own sources to byte-identical Rust, and a test compares the two.
crate::ast re-exports it.tools/ast.nika declares all of the tree’s types; crate::ast in the
compiler is pub use nikaia_std::tools::ast::* plus the few lines of Rust
Nikaia cannot say (int_value, int_literal, which need an i128). Nothing
is duplicated and nothing converts: the lowered types are the compiler’s
types. What a Rust caller needs that Nikaia cannot write - a Span’s
usize doors, WithSpan - stands in nikaia-std, because an impl of a
type stands only in the crate that declares it (D19).
Span is a struct of two u32, a copy, and a source is at most 4 GiB.Span { start: u32, end: u32 }. A byte offset is never negative, and every
node carries one, so i64 would be a sign nothing uses at twice the width.
A source longer than u32::MAX bytes is refused where it is read, with a
message, rather than wrapped. The at offsets (ListLit, LitStr, With,
SelectArm) are u32 too. The Range<usize> the Rust needs to slice the
source is a method of the adapter, not a field.
Spanned[T] is a generic struct Nikaia writes, and the boxes are where the compiler puts them.Spanned[T] with node, span and doc: ?String. A field that closes a
ring of types is boxed by ADR-246 D1’s rule, not by the hand that wrote the
Rust; where the rule boxes a different field, the Rust readers follow the
declaration.
copies() says so and the emitter derives Copy beside Clone (ADR-204
D1, extended). Nothing a program writes changes meaning.LitInt { value: u64,
negative: bool }, exactly ADR-285 D19’s range. Readers ask for the value
they need rather than doing i128 arithmetic.describe
reads #[derive(…)] and drafts copies and compares (ADR-290), and the
checker reads them for a foreign type as for a declared one.
winnow_grammar::Symbol is described with both.Default: a type that derived one is built by a named constructor
(FnParams::none(), FrameAttr::bare(), Span::nowhere()).Span becomes D7’s struct, still in Rust; the 4 GiB refusal.LitInt becomes D9.2’s shape and Default goes, still in Rust.ast.nika replaces ast/mod.rs; what changes in the Rust readers is
only what the declaration decided differently (the boxes).A u64 and a bool, 65 bits, which hold every literal ADR-285 D19 allows.
The arithmetic is checked on the magnitudes, and a step that leaves the 65
bits is too large, which NK1116 says as more than the widest - no number
past it is named. A declared operand holds every step to its type, as
rustc does: let a: i32 = 2000000000 then a + a - a is refused at
a + a. A literal still pins nothing (ADR-285). No i128 joins Part I 2.2.
Ty, Shape, the ledger’s records (FnContract, TypeContract,
Signature, the field, variant and config entries, Ledger) and their small
enums are declared in Nikaia beside ast.nika and re-exported from
contracts, so every reader keeps its path. This is D6’s route a second time.
(a) a measurement that decides the shape (D14); (b) the declarations move in
that shape, the algorithms staying Rust; (c) the text form - parse and print
of a signature, and reading a ledger back - moves beside ledger.nika;
(d) the algorithms (fits, bind, substitute, qualify, …) move.
Deciding the shape first keeps the move and the redesign apart, which is
Go 1.5’s lesson.
Ty moves as values.Interning is chosen only if both hold on the corpus’s largest programs:
cloning, dropping and comparing Ty is at least 15 % of the front end’s
instructions, net of what interning adds; and the front end is at least
10 % of an end-to-end debug build - or if measured growth carries the
first past 15 % at 75,000 lines. Otherwise Ty stays a plain tree with a
text form.
The answer is: move as values. Ty measured 3.4-6.6 % of the front end,
flat with program size, so the first condition fails.
It is reopened when any of these is seen: Ty broad at or above 15 % in a
report.py row, or rising more than a point per doubling (after checking for
a walk); last-level misses under Ty at or above 5 %; a back end of Nikaia’s
own; build-time evaluation that computes types; a unit past 4,000 lines - then
the measurement is run again by D15-D16.
The prediction is written and committed before the first run, so the result cannot be shaped to fit it, and it is left as written beside the result.
Costs from callgrind on the unmodified release compiler (instructions,
inclusive, the same on every run); counts from a separate census build whose
timings are never quoted. Every known source of error is listed with its
direction and correction before the result is read; benches/ty-census/
runs D14’s measurement again.
src/tools is a package.Its files share one namespace (Part I 9.1, ADR-286 D1): a name declared in any of them is written as it is in any other, a private helper is the package’s, and two files may not declare the same name.
nikaia lower-std checks every file with the others beside it, against
std’s ledger and the tools’ described one (tools/described.contracts,
D9.3), and lowers them into one generated module per tools file,
crates/nikaia-std/src/tools/lowered/<stem>.rs, with the index lowered.rs.
There is no table of which tool reads which.
The index lowered.rs declares one module per file - tools::ty,
tools::ledger, tools::rust - re-exporting what that file declares pub,
so nikaia_std::tools::ty::Ty stays the path it was. The Rust that
nikaia-std writes beside the package because Nikaia cannot say it is listed
by the file it serves (sysroot::HAND_WRITTEN) and joins that file’s module.
An error type declared in another file of the package is recognised as the package’s own error when a function throws it, in a program’s package as in this one.
nikaia-std holds the compiler’s tree and types; the crate every generated
program links compiles them too, and the linker drops what a program never
reads - the trade tools::rust already made (ADR-290 D16).Span is Copy, and a source file
over 4 GiB is refused.null in a field D8 boxes costs an allocation where the hand had
Option<Box<T>> - ADR-246 D5.3’s trade..nika changes one generated file, lowered/<stem>.rs.Ord) stays where ADR-204 §4 left
it; the three places that needed one write it.Ty - the name interner’s
lookup cost, and an empty program copying the ledger’s records - stays in
#122.