lower-lang 0.4.1

Lowers lossless syntax trees into HIR through declarative semantic archetypes and hygienic templates.
Documentation

The model

  • A Mapping is a language's semantics as data, built with a MappingBuilder. 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 Arch says what a node means and where its parts are: each field is a Pick — a child by host field label, or by position or kind for trees without labels.
  • A Template is a small HIR-shaped AST with ${field} holes, written as text in HIR's template syntax (Template::parse("bool_and", "if ${lhs} { not(not(${rhs})) } else { false }"), MappingBuilder::parse_template) or built with a TemplateBuilder. Every instantiation records its own HIR expansion; the binders it introduces carry that expansion's hygiene mark. templates has the common ones: while, do-while, C for, for-each, &&, ||, ??, ?, x++.
  • Places are evaluated once. let_place p = ${place} in p = add(p, 1) names a place ($a[f()]) once for reads and writes (HIR LetPlace); compound assignment with a host function, an intrinsic, or a template (OpSpec::CompoundExtern / CompoundIntrinsic / CompoundTemplate: PHP .=, **=, ??=) lowers that way, and so does the built-in x++.
  • PHP semantics are policy and archetypes, not special cases: LangPolicy::php() turns on function-scoped foreach/catch variables, implicit locals, promote-to-float integers, and PHP number spelling; Arch::Interp joins string segments, Arch::UseTree flattens group imports, Arch::MixinRule lowers trait insteadof/as, and Arch::Attr attaches attributes.
  • PHP classes and loops (0.4.1) are policy and mapping entries too: LangPolicy::implicit_receiver gives methods $this, BreakLevels::Numeric makes break 2 a labelled jump, MappingBuilder::modifier_in gives ... one meaning in parameters and another in arguments, and template_node_when picks a template by a child.
  • lower is the one-call entry point; Lowerer adds a Budget, a compilation unit, and field labels. The result is a Lowered: a valid hir_lang::Hir and every Problem in 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, four language policies, one with every 0.4.1 feature on) 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 resolve every random result through the real resolver, resolve-lang 0.4 (lexical policy or PHP's, matching the lowering policy), and check that every resolved reference names a binder with its own hygiene mark and that resolution is deterministic; integration tests put user variables named like the templates' temporaries (it, t, old) next to for-each, ??, and x++, and the Mox tests resolve under Policy::php().
A template text means exactly what the builder would build. A differential property test generates 512 random templates per run (every expression, statement, pattern, and type form, holes of every kind, binders, labels, closures, let_place, keyed yield), renders each as text and builds it with TemplateBuilder side by side, and checks that parsing the text gives the same template (compared in a canonical form). Every template text of the Mox sketch parses, and the ones that matter for the demo (&&, ||, ++, --, echo, print, yield from) lower into HIR that validates and resolves with no diagnostics.
Hostile template text never panics, overflows the stack, or runs long. Property tests feed 512 arbitrary strings and 512 token soups of the template vocabulary per run; parsing is recursive descent with a nesting cap (MAX_TEMPLATE_DEPTH = 32), checked for 16 nesting forms past the cap on a 512 KiB thread, and a length cap (MAX_TEMPLATE_TEXT = 1 MiB); every lookup is a sorted-map lookup, so parsing is never quadratic. Every refusal is a TemplateError::Syntax with the byte range; tests cover every error kind and pin the range for most.
Places are evaluated once. Tests count the index expressions and calls in lowered Mox code: $a[$k] .= …, ??=, **=, ++$i, $i++, --$i, $i-- each evaluate their place once, and ++$a[f()] calls f once with the let_place template where the sketch's current text calls it three times.
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.
Methods see $this; closures capture it as PHP does. A property generates random classes (static and instance methods) holding random nests of closures (static or not, explicit or implicit captures, use ($this) or not) and named functions that read $this, and checks against a reference model: one receiver per instance method, which closures capture $this, and which reads are NoReceiver problems; every resolved $this names a receiver or a capture, and lowering is deterministic. Mox classes (constructors setting $this->x, methods reading it, parent::__construct, new C(...) and new $name(...), static methods through self:: and K::, mixin methods, closures and arrow functions over $this, classes with no visibility keyword under default_member_visibility = Public) run end to end through resolve-lang 0.4.1, bcgen-lang 0.4, and bvm-lang 2.0.0-alpha.4. A template that binds its own this around user code resolves each this to its own binder.
break N / continue N reach the right loop. A property generates random nests of loops, closures, and jumps with levels 0 to 5 and checks every jump against a reference that counts loops per function: the labelled target, a plain jump, or the exact BreakLevel problem; only targeted loops get labels. Nested loops with continue, continue 2, break 2, and break 1 run end to end on bvm-lang; 5,000 nested loops lower on a 256 KiB stack.
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

[dependencies]
lower-lang = "0.4"
hir-lang = "0.4"      # the output
intern-lang = "1"     # names
syntax-lang = "1"     # the input

Without the standard library:

[dependencies]
lower-lang = { version = "0.4", default-features = false }

Quick start

A mapping for 1 + 2, a tree built with syntax-lang's builder, and one call:

use hir_lang::OpKind;
use intern_lang::Interner;
use lower_lang::{lower, Arch, MappingBuilder, OpSpec, Pick, TokenRole};
use syntax_lang::{Builder, Span, Token, TokenKind};

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum K { File, Add, Num, Plus, Space }
impl TokenKind for K {
    fn is_trivia(&self) -> bool { matches!(self, K::Space) }
}

// The semantics, as data.
let mut b = MappingBuilder::new();
b.node(K::File, Arch::Module { name: Pick::Absent, items: Pick::Nodes });
b.node(K::Add, Arch::binary()); // lhs = 1st child, op = 2nd, rhs = 3rd
b.token(K::Num, TokenRole::Int);
b.binary_op(K::Plus, OpSpec::Op(OpKind::Add));
let mapping = b.build()?;

// `1 + 2`
let mut t = Builder::new();
t.start_node(K::File);
t.start_node(K::Add);
t.token(Token::new(K::Num, Span::new(0, 1)));
t.token(Token::new(K::Space, Span::new(1, 2)));
t.token(Token::new(K::Plus, Span::new(2, 3)));
t.token(Token::new(K::Space, Span::new(3, 4)));
t.token(Token::new(K::Num, Span::new(4, 5)));
t.finish_node();
t.finish_node();
let tree = t.finish().expect("balanced");

let mut names = Interner::new();
let out = lower(&tree, "1 + 2", &mapping, &mut names).expect("within budget");
assert!(out.problems.is_empty());
assert_eq!(
    hir_lang::print(&out.hir, &names),
    "(module\n  (block\n    (do\n      (op add overflow=error\n        (lit 1)\n        (lit 2)))))"
);
# Ok::<(), lower_lang::MappingError>(())

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 hir_lang::{ExpnKind, OpKind};
use intern_lang::Interner;
use lower_lang::{lower, templates, Arch, MappingBuilder, OpSpec, Pick, TokenRole};
use syntax_lang::{Builder, Span, Token, TokenKind};

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum K { File, While, Block, Name, WhileKw }
impl TokenKind for K {}

let mut b = MappingBuilder::new();
let while_loop = b.template(templates::while_loop())?;
b.node(K::File, Arch::Module { name: Pick::Absent, items: Pick::Nodes });
// holes: cond, body, label
b.template_node(K::While, while_loop, &[Pick::Kind(K::Name), Pick::Kind(K::Block), Pick::Absent]);
b.node(K::Block, Arch::Block { stmts: Pick::Nodes, tail: Pick::Absent, label: Pick::Absent, tail_from_last: false });
b.token(K::Name, TokenRole::Name);
let mapping = b.build()?;

// `while go {}` — with the half-typed `while {}` next to it.
let mut t = Builder::new();
t.start_node(K::File);
t.start_node(K::While);
t.token(Token::new(K::WhileKw, Span::new(0, 5)));
t.token(Token::new(K::Name, Span::new(6, 8)));
t.start_node(K::Block);
t.finish_node();
t.finish_node();
t.start_node(K::While);
t.token(Token::new(K::WhileKw, Span::new(9, 14)));
t.start_node(K::Block);
t.finish_node();
t.finish_node();
t.finish_node();
let tree = t.finish().expect("balanced");

let mut names = Interner::new();
let out = lower(&tree, "while go while", &mapping, &mut names).expect("within budget");
// The second `while` has no condition: one problem, and the HIR is still valid.
assert_eq!(out.problems.len(), 1);
assert_eq!(out.hir.validate(), Ok(()));
let first = out.hir.expansion(hir_lang::ExpnId::from_u32(1)).expect("recorded");
assert_eq!(first.kind, ExpnKind::Desugar);
assert_eq!(names.resolve(first.name), Some("while"));
# Ok::<(), lower_lang::MappingError>(())

Templates as text

LexerSketch sketches write their sugar as template text (LSF2 [semantics.templates]). The text is parsed once into a template, never substituted; holes take their kind from where they are written:

use lower_lang::{HoleKind, MappingBuilder, OpSpec, Template};

// PHP's `&&` returns a bool.
let and = Template::parse("bool_and", "if ${lhs} { not(not(${rhs})) } else { false }")?;
assert_eq!(and.hole(0), Some(("lhs", HoleKind::Expr, false)));

// Registered in sketch order; `++$x` evaluates its place once.
let mut b = MappingBuilder::<u8>::new();
let pre_inc = b.parse_template("pre_increment", "let_place p = ${place} in p = add(p, 1)")?;
let echo = b.parse_template("echo", "extern:mox.echo(${...values})")?;
b.prefix_op(1, OpSpec::Template(pre_inc));
let concat = b.name("mox.concat");
b.binary_op(2, OpSpec::CompoundIntrinsic(concat)); // `.=`, place evaluated once
let _ = echo;
assert!(b.build().is_ok());

// Errors carry the byte range.
let err = Template::parse("t", "add(${x})").unwrap_err();
assert_eq!(err.to_string(), "template text, bytes 0..3: the operation takes 2 operands, 1 given");
# Ok::<(), Box<dyn std::error::Error>>(())

examples/textual.rs lowers a small Mox program through such templates and prints the HIR.

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.
textual Mox's sugar as template text: &&, ++/-- with let_place (the place evaluated once), echo, and .= through OpSpec::CompoundIntrinsic; prints the HIR.
classes Mox classes under the 0.4.1 policies: a constructor setting $this->x, parent::__construct, a closure over $this, and continue 2 / break 2; prints the HIR, then resolves, compiles with bcgen-lang 0.4, and runs it on bvm-lang.

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) ~9.3 ms ~19 M elements/s
calc/1m 1,771,001 elements (1.9 MB) → 748,002 HIR nodes ~122 ms ~14.5 M elements/s
templates/100k 93,001 elements, mostly while + &&/|| templates ~5.5 ms ~17 M elements/s
templates/1m 930,001 elements ~78 ms ~11.9 M elements/s
deep/100k_prefix_chain one 100,000-deep chain (200,005 elements) ~28 ms ~7.2 M elements/s
php/100k 169,050 elements (245 KB of Mox): group use, foreach with function-scoped variables, interpolated strings, heredocs, try/catch ~15 ms ~11 M elements/s
php/1m 1,690,500 elements (2.5 MB) ~194 ms ~8.7 M elements/s
oop/100k 114,400 elements of Mox classes under the 0.4.1 policies: receivers, closures over $this, continue 2 / break 2, rest and spread, include_once ~7.8 ms ~14.6 M elements/s
oop/1m 1,144,000 elements ~97 ms ~11.8 M elements/s
template_text/mox the 19 template texts of the Mox sketch (783 bytes), parsed and registered ~20 µs ~37 MiB/s
template_text/large one 1 MiB template text (12,878 statements, about 155,000 template nodes) ~23 ms ~43 MiB/s

The oop/* rows are 0.4.1 (oop_off/* lowers the same trees with the receiver and numeric levels off, about 7 to 13% faster because it builds fewer HIR nodes); interleaved A/B runs put 0.4.1 within noise of 0.4.0 on calc/100k and templates/100k. The other rows are one run of the 0.4.0 benchmarks while other builds shared the machine; run-to-run noise was up to about 20%, so treat them as rough. In A/B runs in one session, lowering with the 0.4 code and with the 0.3 code (both on hir-lang 0.4) was within that noise; moving the 0.3 code from hir-lang 0.3 to 0.4 measured about 5% slower on calc/100k (hir-lang's validation) and unchanged on templates/100k and deep. Of the calc/1m time, hir-lang's validation and node building are roughly 50 ms (measured for 0.3.0); the rest is lowering's traversal, interning, and dispatch. The PHP policy's per-binding hoisting is the main reason php/* is slower per element than calc/*. Template text parsing is linear: the 1 MiB text parses at about the rate of the small ones. The release gate re-measures on Windows and Linux.

cargo bench --bench bench

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 a Labeler and the mapping uses Pick::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, C for, for-each, &&, ||, ??, ?, and x++ are templates. Each instantiation is an HIR expansion (Desugar for 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; places are named once. HIR is a tree, so the second use of a hole is a copy_subtree copy, charged against the node budget, and its code runs twice. Where that is wrong (++, --, compound assignment), the template names the place with let_place, so its operands are evaluated once.
  • Template text is parsed, never substituted (decision D26). The parser builds the same template AST the builder does; holes are filled with already-lowered HIR, so a template cannot produce text that re-lexes differently. It parses the template subset of HIR spec §20 ahead of hir-lang 0.5, which ships the full textual parser; this front end will be checked against it then.
  • 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_lenient repairs and reports the rest.

Testing

cargo test                       # unit + integration + property + doctests
cargo test --no-default-features # no_std + alloc
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

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/hir_0_4.rs covers the hir-lang 0.4 forms (unions and intersections, keyed yield and yield from, place-once compounds, lenient repair); tests/textual.rs parses every template text of the Mox sketch and lowers Mox code through them into HIR that validates and resolves through resolve-lang; the template text parser's own tests and its differential property are in src/text/tests.rs; tests/receivers.rs, tests/break_levels.rs, and tests/modifiers_and_conditions.rs cover 0.4.1 (implicit receivers, numeric break levels, per-archetype modifiers, conditional templates, keyword type names), each with programs run end to end through resolve-lang 0.4, bcgen-lang 0.4, and bvm-lang 2.0.0-alpha.4 (dev-dependencies) and, for receivers and levels, a property against a reference model; 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.