Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

x2c The x2c Book

Architecture

x2c translates one .x file at a time into a matching .c and .h pair that a C compiler then builds. Everything the language adds on top of C is decided during that translation: Var values, immutable Lists and Strings, interpolation, pattern matching, defer, and lambdas. What comes out is plain C calling into the runtime archive. Each compiler phase transforms the previous phase’s output.

The compiler and the runtime are themselves x2c programs. A compiler written in the language it compiles cannot be built from source in one pass, so the repository carries pre-generated C to start from, then builds the compiler several times over and compares the results. That self-host build explains most of the repository layout.

For the modules that implement a particular language feature, see the implementation map. For the language being implemented, see the language reference. For the runtime these phases target, see the standard library overview. The compiler API reference lists the functions and types exposed by each compiler module.

Repository topology

bin/        the bootstrap compiler binary
bootstrap/  checked-in portable C for the compiler and the runtime
builds/     self-host stages 0 through 3
include/    links to runtime sources and stage-0 generated headers
lib/        x2c runtime sources
src/        x2c compiler sources
unittest/   runtime suites, compiler fixtures, probes, and benchmarks
examples/   curated executable and build-checked programs
docs/       this book: guide, reference, library, and internals
agents/     repository-facing documentation, contracts, and project skills
plans/      active plans-as-logs and archived execution records
etc/        shared Makefile rules, build configuration, symbol artifacts,
            and the Lisp bootstrap
tools/      documentation and stage-comparison checkers

Three of those directories hold generated files. builds/ holds whole staged builds and is not tracked. include/ holds only symlinks: the runtime .x sources from lib/, and the .h files stage 0 generated from them. That is where cc -iquote include finds runtime headers. The C under bootstrap/ is tracked, and it is re-emitted from a known-good stage 0 instead of edited by hand. The compiler under development is builds/0/x2c; see building the compiler for how it gets there.

The compiler pipeline

The compiler has 27 modules under src/. src/main.x dispatches commands and runs the translation loop; src/cli.x parses the command line. Nested interning pools keep batch translation close to single-file peak memory. For each input file the translator runs one pipeline:

source
  -> tokenizer
  -> shallow parse and global environment discovery
  -> full parse and type annotation
  -> fixed-point transforms
  -> generation and cache/initializer staging
  -> C token emission
  -> formatting and .c/.h output

Most phases have a flag that prints their output and stops, so you can watch the same file at successive stages; the full set is in compiler options. Here is one small file through all seven phases.

A worked example

String greet(String name) {
  return %"hello, $name";
}

One interpolated String is enough to illustrate every phase. Saved as greet.x in the repository root and translated into a scratch directory,

mkdir -p /tmp/x2c-arch
./builds/0/x2c translate --out-dir /tmp/x2c-arch greet.x

it produces greet.h:

/* auto-generated by x2c.  Do not edit! */

#pragma once

#ifndef __GUARD_0x10E936D3__
#define __GUARD_0x10E936D3__

#include "x2c.h"
String greet(String name);


#endif /* __GUARD_0x10E936D3__ */

and greet.c:

/* auto-generated by x2c.  Do not edit! */

#include "greet.h"

static String _0;

static int _init_guard_ = 0;





__attribute__((constructor)) static void _file_init_(void);

__attribute__((constructor)) static void _file_init_(void){
  x2c_initialize_protocols();
  if(_init_guard_) return;
  _init_guard_ = 1;
  _0 = String_new("hello, ");
}

String greet(String name){
  if(! _init_guard_) _file_init_();
  return String_join(NULL,  cons(String_var(_0),  cons(String_var(name),  NULL)));
}

The interpolation became a String_join over a cons list. The constant "hello, " became a file-static String built once by a generated initializer. The phases below make both of those decisions.

Tokenizing

Consumes source text, produces a positioned token array. Compiler.tokenize in src/compiler.x reads the file, hands the text to Tokenizer.new from lib/tokenizer.x, and scans it with the allocation-free character recognizers in lib/scan.x. Whitespace, comments, and preprocessor lines all become tokens. Later phases can therefore report positions in the original file, and directives can be re-emitted where they were written.

./builds/0/x2c translate --dump-tokens greet.x

(   1, 1  )	ident               String
(   1, 7  )	space               ␠
(   1, 8  )	ident               greet
(   1, 13 )	(                   (
(   1, 14 )	ident               String
(   1, 20 )	space               ␠
(   1, 21 )	ident               name
(   1, 25 )	)                   )
(   1, 26 )	space               ␠
(   1, 27 )	{                   {
(   1, 28 )	space               ␤␠␠
(   2, 3  )	return              return
(   2, 9  )	space               ␠
(   2, 10 )	%"                  %"
(   2, 12 )	segment             hello,␠
(   2, 19 )	$                   $
(   2, 20 )	ident               name
(   2, 24 )	"                   "
(   2, 25 )	;                   ;
(   2, 26 )	space               ␤
(   3, 1  )	}                   }
(   3, 2  )	space               ␤

␠ and ␤ stand for space and newline. %" and segment are already token classes. The scanner recognizes interpolation; no later pass rescans string contents.

Shallow parse and global environment discovery

Consumes the token stream and whatever declarations the file can see, produces a Map from global name to type. This phase exists because x2c’s typed lowering has to know the type of every name in scope, including names that come from C headers the compiler never parses in full.

The default path does not run the C preprocessor. Every unit starts from the implicit runtime prelude: src/snapshot.x loads etc/symbols.xlisp – a deterministic, versioned serialization of the runtime’s own global symbol Map – once per process, through the shared Lisp reader. src/collect.x then shallow-parses the source text directly, splicing quote-includes inline at their include points in the same order the preprocessor would have produced them, resolving each through the same search order (the including file’s directory, ., src/, lib/, then the -I chain), and overlays what it finds on the snapshot. Includes that land under lib/ or include/ are already covered by the snapshot and are skipped; unresolved angle includes are system headers the generated C re-includes anyway; unresolved quote includes are driver errors. Each file is spliced once by real path, so include cycles terminate. Across a batch, src/main.x keeps per-header contributions in etc/header-symbols.xlisp, a cache validated against the snapshot’s content hash, so repeated headers are not re-collected.

--cpp-symbols and --live-symbols switch to the original path, where the toolchain force-loads lib/x2c.x and runs cc -E -P as a child process. Paths stay separate argv elements, and stdout, stderr, and the real child status come back independently. A second Compiler shallow-parses that output instead.

Either way this is a discovery pass. Shallow parsing (Compiler.shallow_parse) skips function bodies, and full parsing, source diagnostics, and emitted C all come from the original positioned token stream. --no-cpp skips symbol discovery and is a diagnostic aid for C-only source. --dump-symbols prints the symbol table the compiler ends up with; the implicit runtime contributes a few thousand rows, so grep the output.

Full parse and type annotation

Consumes tokens plus the global environment, produces the parsed AST: immutable Lists, tagged by node kind, annotated with resolved types. Compiler.full_parse in src/compiler.x drives a recursive-descent grammar split across four modules – src/parse.x for declarations and top-level forms, including initializer recognition and the function-body boundary, src/expressions.x for the C precedence ladder plus dotted method sugar, src/statements.x for control flow, match, try/catch, and defer, and src/literals.x for collection, interpolated String, and lambda literals. The built-in source macro in src/macros.x, etc/builtin-macros.xmacro, and etc/builtin-macros.xlisp expands foreach during this pass. src/type.x owns the List-backed Type representation those modules consult; src/ast.x owns sequence placement and binding helpers; src/compiler.x itself owns lexical scopes, symbol lookup from inner to outer, generated names, and the filtered <malformed> recovery boundary used to synchronize after a parse diagnostic; src/diagnostics.x collects positioned diagnostics in order.

Macro definitions use that same recursive-descent parser in macro mode. Each semantic entry point accepts a typed parameter or compile-time Lisp slot and otherwise follows the ordinary grammar, so the stored template is an ordinary AST List. An invocation parses its arguments through those entry points, matches their canonical capture rows once, replaces the template once, and hands the result to the ordinary recursive syntax binder. Nested invocations and Lisp slots are expanded when that binder reaches them; there is no second macro grammar or post-expansion validation pass.

./builds/0/x2c translate --dump-ast greet.x

(function ("String")
 (bind (binding 2 "greet")
  ((fnmod (params (param ("String") (bind (binding 1 "name") ()))))))
 (block
  (at 1 (return ("String")
         (expr ("String")
          (segments (cache 0)
           (segvar (expr ("String") (ident (binding 1 "name"))))))))))

Types are attached as the tree is built. The function, its parameter, the return, and the interpolated expression all carry ("String") already. Identifiers have become numbered bindings, and each statement is wrapped in an (at N ...) node. That number indexes the compiler’s table of recorded source positions, so a later phase can still report the line the statement came from. Source preprocessor lines survive as preproc nodes, kept in source order at the top level and inside compound statements. The implicit runtime prelude is not a source token or AST node.

One decision has already been made here. The literal segment "hello, " holds no dynamic references, so src/literals.x recorded it as a cacheable constant and the AST refers to it by slot:

./builds/0/x2c translate --dump-cache greet.x

0	==>	(string (expr ("String") (literal ("String") "hello, ")))

Fixed-point transforms

Consumes the parsed AST, produces a lowered AST that the emitter can walk without knowing about x2c. src/transform.x drives it, one pass over the whole translation unit at a time, repeated until the tree stops changing – literally until the new tree is the same object as the old one, because lowering one construct routinely exposes another. src/lambda.x handles lambdas, which need additional declarations. A noncapturing lambda becomes a static helper function, plus an adapter when the receiving callback type differs from the helper’s signature. When a Func is expected, a direct function or noncapturing lambda also gets one reusable file-static handle. A function-pointer value uses an adapter shared by its canonical pointer type and a new Func whose copied context snapshots that pointer. A capturing lambda becomes a FuncAdapter helper and a Func whose copied typed context supplies its value snapshots and explicitly captured reference addresses. Capture bindings have separate identities from their source bindings, so moving a source into a shared cell cannot retarget a sibling snapshot. Parsed lambdas and constructed capture rows resolve in the same lexical environment. A public inline function reaches these source-owned helpers through a generated bridge that also runs the owning unit’s initializer. Those synthesized declarations go onto a compiler-owned early-declaration queue, are driven to a fixed point themselves, and are appended to the unit.

./builds/0/x2c translate --dump-transforms greet.x

(function ("String")
 (bind (binding 2 "greet")
  ((fnmod (params (param ("String") (bind (binding 1 "name") ()))))))
 (block
  (at 2 (return
         (expr ("String")
          ("String_join(NULL, "
           (expr ("List")
            (cons (expr ("Var")
                   (call (expr ((func (("String"))) "Var")
                          (ident (binding 15 "String_var")))
                    (args (expr ("String") (cache 0)))))
             (cons (expr ("Var")
                    (call (expr ((func (("String"))) "Var")
                           (ident (binding 15 "String_var")))
                     (args (expr ("String") (ident (binding 1 "name"))))))
              (nil)))) ")"))))))

The interpolation is gone, replaced by a String_join call over a cons list of boxed Var values, each String_var call naming its callee as a resolved binding carrying that function’s type. The return no longer carries a type annotation; nothing downstream needs it. Some children are now raw C text. Transforms may produce emitter-ready fragments, so "String_join(NULL, " sits in the tree as a String instead of a call node.

Generation and cache staging

Consumes the lowered AST for one unit, produces two ASTs – one per output file – plus the generated initialization that makes cached constants work. src/generate.x owns the sequence: drop whitespace and comment nodes, partition declarations and functions into header and source halves, ask src/cache.x to materialize the cache slots as file statics with an initializer, fold every file-level initialization block into one guarded _file_init_ function, synthesize static prototypes, restore vertical spacing, add the unit’s own header as its primary include, patch main when the unit has one, and run one more transform pass under the generation-phase contract.

src/cache.x is why _0 exists in the worked example. It owns discovery and materialization of cached constants between lowering and emission: immutable String, boxed Var, and canonical List/cons graphs share generated storage, while mutable collections are copied at their use sites, so caching never changes identity semantics. An ordinary C literal promoted to String enters this same cache without changing its C escape spelling. Parenthesized and conditional raw-string expressions distribute promotion to their literal leaves; dynamic leaves retain their per-evaluation conversion and conditional evaluation still selects only one arm.

Generation computes the transitive cache graph used by each output region. Source-resident values keep the compact _N statics in the .c file. A public inline body instead gets deterministic, filename-hashed static slots in the generated header, so each consuming C translation unit remains self-contained. If the same key occurs in both regions, each region has a slot, but String and List canonicalization makes the resulting value identity the same.

The generated C provides two ways to run the guarded initializer. __attribute__((constructor)) runs the source or TU-local header initializer at load time where the host supports it. A source entry that needs file initialization, or an inline entry that references a header cache, also checks its corresponding guard, so initialization also runs on hosts without constructor support. These immutable values are allocated eagerly and retained for the process lifetime, so an allocation failure happens during load-time initialization instead of at the literal’s source expression.

C token emission

Consumes the lowered AST, produces a flat List of C tokens. src/emit.x does this with one stack-local Emitter per translation unit, which holds cleanup guards and preserved automatic names. Emission is therefore reentrant, and a unit that fails cannot contaminate the next one. Cleanup lowering happens here instead of in the transform phase, because it depends on emission order. defer blocks, catch handlers, and scope exits must run in the right sequence and must preserve the active exit kind across returns, loop exits, and Error transfer. Preprocessor nodes are re-emitted here too, with .x include targets rewritten to the generated .h they correspond to.

./builds/0/x2c translate --dump-code greet.x

String greet(String name){
  return String_join(NULL,  cons(String_var(_0),  cons(String_var(name),  NULL)));
}

That is the emitted unit on its own. The include line, the _0 static, and _file_init_ are all added afterwards by generation. That is why the final greet.c opens with #include "greet.h" while the declaration and the implicit runtime include are in greet.h.

Formatting and output

Consumes the C token List, produces text. src/format.x walks the tokens without reordering them: parenthesis depth suppresses statement breaks inside expressions, preprocessor tokens get their escaped quotes normalized, and a Buffer materializes the final String. The result is valid, readable C, with spacing determined by the emitter. src/generate.x then writes the two files, named from the input basename inside the --out-dir directory; a write failure becomes a diagnostic carrying the target path and the host error.

unittest/compiler-fixtures/ pins the output of each phase. It stores expected tokens, AST, transformed AST, symbol tables, generated C, and exit status per fixture, so a change in any phase shows up as a diff.

Module ownership

Gathered in one place, for the 27 modules under src/:

  • src/cli.x, src/main.x – option metadata and parsing, dispatch, logging, the per-file translation loop, and interning brackets;
  • src/project.x, src/build.x, src/toolchain.x – manifest membership and target relationships, typed native build requests and incremental state, and host compile/archive/link actions;
  • src/report.x – dependency-free terminal progress and stable completion receipts on standard error;
  • src/bootstrap.x – source-bearing APE extraction and the one-time transition to a matched host-native compiler and runtime;
  • src/deps.x – x2c dependency parsing and atomic depfile publication;
  • src/compiler.x – shared compiler state, token navigation, scopes, symbol lookup, generated names, phase entry points, and phase recovery;
  • src/parse.x, src/expressions.x, src/statements.x, src/literals.x – grammar and AST construction;
  • src/macros.x – compile-time macro definitions, imports, Lisp lifting, hygiene, and expansion;
  • src/ast.x – AST sequence placement and binding helpers;
  • src/type.x, src/protocol.x – type representation, conversions, protocol declarations, conformance, and generated adapters;
  • src/collect.x, src/snapshot.x – global environment discovery and the serialized symbol snapshot;
  • src/utils.x – repository discovery, child-process execution, output capture, and exit status;
  • src/transform.x, src/lambda.x – lowering to emitter-ready AST;
  • src/cache.x – cached constants and their generated initialization;
  • src/generate.x – header/source partitioning, unit initialization, include guards, and output writes;
  • src/emit.x – AST to C tokens, including cleanup lowering;
  • src/format.x – C tokens to text;
  • src/diagnostics.x – recorded diagnostics.

The runtime boundary

The compiler is an x2c program and uses the same runtime that generated programs use. There is no compiler-private collection library, so every runtime weakness the compiler hits is one a user program can hit. The main divisions:

  • lib/scope.x owns allocation lifetime, and lib/pool.x the nested interning pools layered over it;
  • lib/var.x, lib/varconvert.x, lib/varops.x, and lib/dispatch.x own tagged values, cause-raising conversion, operators, and dynamic dispatch;
  • lib/string.x, lib/symbol.x, lib/atom.x, and lib/list.x own canonical immutable values;
  • lib/block.x, lib/buffer.x, lib/array.x, and lib/map.x own mutable storage;
  • lib/iter.x owns status-bearing traversal;
  • lib/match.x owns list-pattern matching and plan compilation; lib/match-machine.x executes those plans over the shared wordcode and state definitions in lib/machine.x;
  • lib/lisp.x owns the embedded Lisp reader, session, and evaluator, while lib/lisp-machine.x executes eligible prepared Lisp programs; the build itself uses Lisp for the symbol artifacts in etc/;
  • lib/func.x owns generic native calls through generated adapters;
  • lib/tokenizer.x and lib/scan.x own tokenization, so the compiler’s first phase is library code;
  • lib/error.x owns failure records, handlers, and policy;
  • lib/exception.x owns Error transfer and cleanup frames, while lib/file.x and lib/logger.x provide file I/O and logging;
  • lib/common.x supplies shared representation and initialization support;
  • lib/lib.x contains the standalone DisjointSet utility.

lib/x2c.x is the generated source definition of the implicit runtime prelude. The generator leaves out the optional x2c system modules; they are built with the runtime and need an explicit source include. Runtime component headers keep selective includes while they build the aggregate. Every other generated header includes x2c.h.

The self-host build

Because src/*.x and lib/*.x are x2c, building them requires an x2c compiler, and the only way to get the first one is to start from C that an earlier x2c compiler emitted. That C is tracked under bootstrap/. It has to stay portable, since a C toolchain is all you have at that point.

bootstrap/  -- cc -->  bootstrap compiler
                              |  translates lib/ and src/
                              v
                          builds/0  ->  builds/1  ->  builds/2  ->  builds/3

generated C compared byte for byte:
  stage-diff-0   bootstrap/  against  builds/0
  stage-diff-1   builds/0    against  builds/1
  stage-diff-2   builds/1    against  builds/2
  stage-diff-3   builds/2    against  builds/3

Each arrow is one full translation of lib/ and src/ followed by a C build, and each stage directory holds both halves: the C that the previous compiler in the chain emitted, and the binary built from it. So builds/0 is the bootstrap compiler’s output, builds/1 is stage 0’s output, and so on. Stage 0 is the compiler everything else uses. Stages 1 through 3 show that it reproduces itself, and make stage-3 builds them.

Staging matters because a change to src/ changes two things at once: the compiler’s behavior, and the program that compiler is asked to compile. Stage 0 shows only that the old compiler could translate the new source. Stage 1 is the first build where the new compiler compiles the new source, and stage 2 is the first build where a compiler produced by the new compiler does. Some bugs need both halves of the change to appear, such as a lowering that emits code its own new parser mishandles. Those surface at stage 1 or 2 and nowhere earlier.

The comparison is byte-exact. tools/check-generated-stages.sh, behind the make stage-diff-0 through make stage-diff-3 targets, compares the generated .c/.h file sets of two neighbouring stages and then compares every file byte for byte. stage-diff-0 asks whether the bootstrap compiler re-emits the C it was built from; the rest ask whether each stage emits what the stage before it emitted. Once two adjacent stages agree, the chain has reached a fixed point.

A byte comparison can catch problems that behavioral tests miss. An iteration order that depends on addresses, or a generated-name counter that carries across translation units, shows up here while every suite still passes. The same phase run twice has to produce the same bytes.