lower-lang 0.3.0

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, 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++.
  • 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.
  • 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, 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

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

Without the standard library:

[dependencies]
lower-lang = { version = "0.3", 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>(())

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.

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. HIR is a tree, so the second use of a hole (x++ reads and writes x) is a copy_subtree copy, 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_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/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.