lower-lang 0.2.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++.
  • 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, &&/`
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.2"
hir-lang = "0.3"      # the output
intern-lang = "1"     # names
syntax-lang = "1"     # the input

Without the standard library:

[dependencies]
lower-lang = { version = "0.2", 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.
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.

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