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++. - PHP semantics are policy and archetypes, not special cases:
LangPolicy::php()turns on function-scopedforeach/catchvariables, implicit locals, promote-to-float integers, and PHP number spelling;Arch::Interpjoins string segments,Arch::UseTreeflattens group imports,Arch::MixinRulelowers traitinsteadof/as, andArch::Attrattaches attributes. 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, &&/` |
| PHP and Python semantics match independent references. | Property tests check function-scoped foreach/catch bindings (random destructuring var, foreach, and catch, nested, with by-reference bindings) against a reference scope model, interpolated strings against a reference concatenation, heredoc indentation against PHP 7.3's rule, integer literals of every radix and separator policy against a u128 reference, and nested use trees against a recursive flattener. Random trees reach the 0.3 paths (attributes attached and misplaced, use trees, interpolation joins, decoded texts) on every run, under the PHP policy as well. |
| 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.3"
= "0.3" # the output
= "1" # names
= "1" # the input
Without the standard library:
[]
= { = "0.3", = 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. |
php |
LangPolicy::php() on a Mox function: a group use, an attribute, foreach variables still visible after the loop, an interpolated string and an indented heredoc, PHP octal and separators. |
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) | ~11.3 ms | ~15.7 M elements/s |
calc/1m |
1,771,001 elements (1.9 MB) → 748,002 HIR nodes | ~139 ms | ~12.8 M elements/s |
templates/100k |
93,001 elements, mostly while + &&/|| templates |
~7.7 ms | ~12 M elements/s |
templates/1m |
930,001 elements | ~96 ms | ~9.7 M elements/s |
deep/100k_prefix_chain |
one 100,000-deep chain (200,004 elements) | ~30 ms | ~6.7 M elements/s |
php/100k |
169,050 elements (245 KB of Mox): group use, foreach with function-scoped variables, interpolated strings, heredocs, try/catch |
~18.8 ms | ~9.0 M elements/s |
php/1m |
1,690,500 elements (2.5 MB) | ~233 ms | ~7.3 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.
The 0.3.0 figures were taken while other builds ran on the same machine, so
they are noisy (criterion's comparison against the 0.2.0 run, itself taken
under load, reports the 0.2 benchmarks 50–60% faster, which is mostly load,
not code). The PHP policy's per-binding hoisting (a temporary, a Desugar
expansion, and an assignment for every foreach/catch variable) is the
main reason php/* is slower per element than calc/*. 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 and trait rules, try/catch/finally,
generators, map literals, interpolated strings, heredocs, function-scoped
foreach/catch variables, group use, attributes, PHP number literals);
tests/semantics.rs holds the 0.3 semantics tests and
their property tests against references (function-scoped bindings,
interpolation, heredocs, integer literals, use trees);
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.