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, built-in macros,
            and the compile-time Lisp environment and SDK
tools/      documentation and stage-comparison checkers

Three of those directories hold generated files. builds/ holds whole staged builds and is not tracked. include/x2c/ holds only symlinks: the runtime .x sources from lib/, and the .h files stage 0 generated from them. That is where cc -iquote include/x2c 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 lives under src/. src/main.x dispatches commands and runs the translation loop; src/cli.x parses the command line. src/frontend.x owns configured source stages and isolated unit lifetimes shared with internal tools. 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, the declarations of lib/x2c.x and everything it includes. src/collect.x shallow-parses 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 prelude. Includes that land under lib/ or include/ are already covered by the prelude 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.

A file’s contribution is collected once per process. Translating a unit also writes it beside the generated C as a unit interface, <stem>.xi: the ordered declaration maps, include placeholders, and private and public markers for the visibility pragmas, the source content hash, function definitions, and the macro, Lisp, and embedded-text files the walk read with their hashes. A declaration map below a private marker holds only what that region publishes, so an including unit never sees a private type or static helper, and a package’s surface stops at that marker. The file holds one (interface 2 "path" "hash" (PARTS...) (DEFINITIONS...) (DEPENDENCIES...)) form in %() List syntax, with bare Atoms for its structural words and Strings for identifiers; the reader reads that one form without evaluating it. Before walking a file’s source, collection looks for its interface in the output directory, then in the directory that mirrors the file’s home-relative path under the compiler’s stage directory (or under an installed home), then in a package’s builds/. An interface is used only when its recorded path and every hash still match; otherwise collection walks the source. The prelude is the runtime x2c.xi interface from the library batch, so a stage build produces the prelude the next batch and the next stage replay, and no tracked file is both an input and an output of a build. x2c env prelude prints the interface a compiler would replay; an empty value means the compiler walks the source of lib/x2c.x, which costs about a quarter of a second per process.

--cpp-symbols and --live-symbols discover symbols through the host C preprocessor: 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. src/comptime.x translates a function marked for compile-time use into the Lisp the macro session evaluates, with etc/comptime.xlisp as its runtime. 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.

src/cleanup.x runs once after that fixed point, over each function on its own. It assigns a name to the runtime record of every defer and try region, builds the statements that leave the region, and runs them wherever control leaves it: the region’s own end, a return – after saving the value, since cleanup may change what the expression read – a break or continue that leaves the construct that bounds it, and an outward goto. The pass rejects a jump into a region, including the region a static local’s runtime initializer opens over the rest of its block. The pass also marks the locals and parameters a try writes as volatile, which C requires of automatic state changed across sigsetjmp. Because it rewrites transfers, it runs after the driver reaches its fixed point.

./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, and patch main when the unit has one. Generation synthesizes already-lowered nodes, so it runs no further transform pass.

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 the current function’s name and static objects. Emission is therefore reentrant, and a unit that fails cannot contaminate the next one. src/cleanup.x has already placed each region’s cleanup statements on every exit that leaves the region, so emission prints frames, records, and statements where the AST puts them. 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 occupy their own lines, 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

The modules under src/ divide ownership as follows:

  • src/cli.x, src/main.x – option metadata and parsing, dispatch, logging, the per-file translation loop, and output/exit policy;
  • src/frontend.x – configured source stages, process translation support, and sequential unit Context/Type lifetimes;
  • src/repl.x, src/repl-session.x – terminal interaction, persistent submissions, and named inspection over the frontend and evaluator;
  • 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/install.x – package installation, removal, and listing under the x2c home, with fetch, digest, and extraction as host child processes;
  • src/script.x – x2c script: the per-user executable cache, its lock, and executing a current or freshly built script;
  • 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/comptime.x – translating a function marked for compile-time use into the Lisp the macro session evaluates; etc/comptime.xlisp is its runtime;
  • 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 – global environment discovery and unit interfaces;
  • src/utils.x – repository discovery, the driver’s fatal error line, and forked translation workers;
  • src/transform.x, src/lambda.x, src/cleanup.x – lowering to emitter-ready AST, including which exits leave a cleanup region and which locals an error transfer preserves;
  • src/regions.x – per-function region summaries and the warnings for a value that can outlive the region that allocated it;
  • 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;
  • src/format.x – C tokens to text;
  • src/diagnostics.x – recorded diagnostics;
  • src/sourceview.x – request-owned source overlays and logical file paths;
  • src/editor.x – one-request diagnostics, definition, and hover transport over the configured frontend and source overlays.

The internal frontend is shared by the CLI, editor, and source graph tool. A Frontend borrows a configured CliRequest; its ParsedUnit retains the compiler, AST, diagnostics, and preprocessor output until explicit close. The stages are start/tokenize, collect, and parse. Failed stages return to the caller with readable diagnostics. Adapters choose printing and process exit; the default frontend collects without printing. Closing a unit releases its owned Lisp session, Type unit, and isolated Context before the next unit opens.

Process type/header caches and generated-name state still require sequential units. This extraction does not establish a concurrent or stable public compiler-library API, nor does it contain a user macro that explicitly aborts or exits the process.

The optional editor worker in tools/x2c-editor/ uses the same frontend and project configuration. SourceView supplies immutable unsaved text under each file’s canonical path; an empty overlay remains a present file. The request owns overlays, while a parsed unit owns disk text and semantic results.

Declaration metadata follows the actual symbol-map contribution and key through collection and imports. The primary parser associates resolved bindings with physical token spans for definition and hover queries. It does not infer a source location for constructed syntax that has no physical token. Each editor request runs in a fresh process and collects source declarations without reading .xi interfaces, which do not carry their physical spans. This isolates process caches and macro failures from the editor service.

The VS Code adapter under etc/vsc-extension/ converts compiler UTF-8 byte offsets to editor positions and discards responses after document changes or cancellation. It executes semantic requests only in trusted local workspaces. Syntax highlighting remains available independently of the native worker.

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 compiler uses it to read .xi interfaces and to run compile-time macros;
  • 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.

Prepared Lisp programs include eligible immediate lambda applications, such as the local bindings produced by let and match-case. Their bodies borrow the live caller environment. Macro preparation permits only bounded, effect-free evaluation; dependency guards at each expansion site check the bindings after preceding calls have run. Unsupported preparation or a changed binding uses the ordinary evaluator, preserving macro effects and rebinding. Pattern matching still executes compiled Match plans on MatchMachine.

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.