The model
- A
Mappingis a language's semantics as data, built with aMappingBuilder. It mirrors LexerSketch's LSF2[semantics]sections: node kinds to archetypes ([semantics.bind]), templates ([semantics.lower]), and operators with their policies ([semantics.ops]), plus the token roles, modifiers (mut,async,&,...), and path roots the archetypes read. - An
Archsays what a node means and where its parts are: each field is aPick— a child by host field label, or by position or kind for trees without labels. - A
Templateis a small HIR-shaped AST with${field}holes, built with aTemplateBuilder. Every instantiation records its own HIR expansion; the binders it introduces carry that expansion's hygiene mark.templateshas the common ones:while,do-while, Cfor,for-each,&&,||,??,?,x++. loweris the one-call entry point;Lowereradds aBudget, a compilation unit, and field labels. The result is aLowered: a validhir_lang::Hirand everyProblemin source order.
What it guarantees, and how each guarantee is checked:
| Guarantee | How it is held |
|---|---|
| Lowering never panics and always yields valid HIR, on any tree. | Property tests lower 512 random trees per run (random kinds and shapes over a mapping with most archetypes, error nodes, unmapped kinds, every template, two language policies) and 512 trees with spans outside the source or off character boundaries; every result re-validates. 256 random token soups per run, parsed by lang-forge into deep half-typed trees, lower the same way. Every prefix of a program (typing it one character at a time) lowers. |
| Every node and binder has an origin inside the source, through template expansions. | Checked on every result of every property test and integration test: each node's span lies in the source and each expansion it names exists. |
| Templates are hygienic: their names never capture or are captured by user names. | Property tests run a resolver (lookup_local + resolve) over every random result and check that every resolved reference names a binder with its own hygiene mark; integration tests put user variables named like the templates' temporaries (it, t, old) next to for-each, ??, and x++. |
| Lowering preserves meaning. | A property test generates random calc programs (assignments, arithmetic, comparisons, &&/` |
| Lowering is deterministic. | Every random tree is lowered twice with fresh interners; the printed HIR with origins, the binders, and the problems are identical. |
| Budgets stop runaway work. | A node budget and a template-application depth budget; property tests check that a too-small node budget is an error, never a panic or a hang, and integration tests cut a template chain at the depth budget without losing the user's code. |
| Any tree depth is safe. | Lowering is an explicit-stack machine; a test lowers a 100,000-deep operator chain on the default test stack. |
Installation
[]
= "0.2"
= "0.3" # the output
= "1" # names
= "1" # the input
Without the standard library:
[]
= { = "0.2", = false }
Quick start
A mapping for 1 + 2, a tree built with syntax-lang's builder, and one call:
use OpKind;
use Interner;
use ;
use ;
// The semantics, as data.
let mut b = new;
b.node;
b.node; // lhs = 1st child, op = 2nd, rhs = 3rd
b.token;
b.binary_op;
let mapping = b.build?;
// `1 + 2`
let mut t = new;
t.start_node;
t.start_node;
t.token;
t.token;
t.token;
t.token;
t.token;
t.finish_node;
t.finish_node;
let tree = t.finish.expect;
let mut names = new;
let out = lower.expect;
assert!;
assert_eq!;
# Ok::
Sugar through hygienic templates
while c { b } is a template over HIR's one loop. The template's own names
are marked with its expansion, so they can never meet the user's:
use ;
use Interner;
use ;
use ;
let mut b = new;
let while_loop = b.template?;
b.node;
// holes: cond, body, label
b.template_node;
b.node;
b.token;
let mapping = b.build?;
// `while go {}` — with the half-typed `while {}` next to it.
let mut t = new;
t.start_node;
t.start_node;
t.token;
t.token;
t.start_node;
t.finish_node;
t.finish_node;
t.start_node;
t.token;
t.start_node;
t.finish_node;
t.finish_node;
t.finish_node;
let tree = t.finish.expect;
let mut names = new;
let out = lower.expect;
// The second `while` has no condition: one problem, and the HIR is still valid.
assert_eq!;
assert_eq!;
let first = out.hir.expansion.expect;
assert_eq!;
assert_eq!;
# Ok::
Trees from lang-forge
lang-forge 1.x trees have no field labels yet, so a mapping addresses a
node's children by kind (Pick::Kind), position (Pick::Nth), or neighbour
(Pick::After, Pick::Before). examples/calc.rs forges
a small language from an .lsf schematic and lowers a program and a half-typed
one; tests/calc.rs checks the result end to end, and a
resolver resolves every local reference by HIR's scope rules.
Examples
Runnable programs in examples/:
| Example | What it shows |
|---|---|
calc |
The Tier-1 path end to end: an .lsf schematic forged by lang-forge, a mapping, a program and a half-typed one lowered, printed with origins and problems. |
hygiene |
A Mox-style foreach through the built-in for_each template next to a user variable $it; a toy resolver shows the user's $it and the template's it never meet. The tree is built with syntax-lang's Builder. |
Performance
Lowering is one explicit-stack pass over the tree that builds HIR bottom-up with hir-lang's builder, then hir-lang's lenient validation. Picks are resolved against a node's significant children with linear scans; kind tables are sorted vectors (binary search); scratch buffers (children, values, lists, template-instantiation state) are pooled and reused, so steady-state lowering allocates only what the HIR itself stores.
Measured with benches/bench.rs (library only: the
trees are parsed once, outside the measurement; the measurement includes
finish_lenient validation), Windows 11, x86_64, Rust stable, release
profile. Elements are syntax-tree nodes plus tokens (trivia included).
| Benchmark | Input | Time | Throughput |
|---|---|---|---|
calc/100k |
177,101 elements (189 KB of calc) | ~12.6 ms | ~14 M elements/s |
calc/1m |
1,771,001 elements (1.9 MB) → 748,002 HIR nodes | ~157 ms | ~11 M elements/s |
templates/100k |
93,001 elements, mostly while + &&/|| templates |
~12 ms | ~7.8 M elements/s |
templates/1m |
930,001 elements | ~129 ms | ~7.2 M elements/s |
deep/100k_prefix_chain |
one 100,000-deep chain (200,004 elements) | ~37 ms | ~5.4 M elements/s |
Of the calc/1m time, measured separately: hir-lang's validation is about
20 ms and hir-lang's node building about 30 ms (its own published figure for a
similar size); the rest is lowering's traversal, interning, and dispatch.
These figures were taken on an otherwise idle machine just before the final
change of this release (the check that a child is not picked by two fields);
an interleaved A/B of that check on a heavily loaded machine was dominated by
noise and puts its cost at no more than about 10%. The release gate re-measures
on Windows and Linux.
Design notes
- Archetypes, not code. Most constructs of real languages are instances of a small set of forms (LexerSketch ARCHITECTURE §5). A mapping says which node kind is which form and where its parts are; nothing about a language is hard-coded, and nothing requires a closure.
- Fields by label or by position. LSF2 grammars name their fields
(
name:expr); a host that has labels supplies aLabelerand the mapping usesPick::Label. Trees without labels use kind and position picks. A child picked by two fields (positional picks alias in half-typed code) is lowered once and reported. - One loop, templates for the rest. HIR has one loop and no short-circuit
operators;
while,do-while, Cfor,for-each,&&,||,??,?, andx++are templates. Each instantiation is an HIR expansion (Desugarfor the built-ins), so diagnostics and tools can see the surface form. - Hygiene by construction. A template's binders are created fresh per
instantiation with the expansion's mark and referenced by binder id; its free
names carry the mark too and resolve at the definition site; host symbols
(
extern_) are pre-resolved. User code in holes keeps its own (root) marks. - Holes used twice are copied. HIR is a tree, so the second use of a hole
(
x++reads and writesx) is acopy_subtreecopy, charged against the node budget. - Templates are acyclic by construction. A template may apply only templates registered before it, so expansion terminates; a depth budget bounds long chains anyway, and a cut chain keeps the user's code attached.
- Half-typed code is normal input. Error nodes, unmapped kinds, missing
parts, wrong contexts, unknown operators and labels, bad literals and escapes
each become an HIR error form plus a
Problem;finish_lenientrepairs and reports the rest.
Testing
tests/calc.rs is the worked example end to end (lang-forge
→ CST → lower-lang → hir-lang → resolve), including every prefix of a program;
tests/mox.rs covers Mox-flavoured constructs built with
syntax-lang's Builder ($vars, foreach, by-reference parameters and place
arguments, implicit locals, global/static, use captures, -> members,
$$var, $a[], classes with mixins, try/catch/finally, generators, map
literals); tests/archetypes.rs covers the rest of the
catalogue and every problem kind; tests/properties.rs
holds the property tests and the reference evaluator. Every rust example in
this README and in docs/API.md is compiled and run as a
doctest.
Cross-platform support
- Linux (x86_64, aarch64)
- macOS (x86_64, Apple Silicon)
- Windows (x86_64)
The crate uses no operating-system facilities and no platform-specific code; the same tree lowers to the same HIR everywhere.
Contributing
See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the invariants and the definition of done, and dev/ROADMAP.md for what comes next. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.