syntax-lang 1.0.0

Lossless concrete syntax tree (CST) with trivia.
Documentation

Performance First

Latest local Criterion means (cargo bench, Windows x86_64, Rust stable). A tree of n one-byte tokens grouped in runs of eight:

  • Build (parser drive → finished tree): ~14.6 ns per token (build/4096 ≈ 59.7 µs).
  • Token walk (tokens() over every leaf): a single allocation-free pass, linear in leaf count.
  • Node walk (descendants() over every node): a single allocation-free pass, linear in node count.

Both traversals keep their work stack on the heap and borrow the tree, so neither allocates per element and neither recurses. Reconstructing a node's text (node.text(source)) is a single sub-slice of the source string — no allocation, no copy.

Features

  • Lossless. Trivia (whitespace, comments) is preserved as leaf tokens in source order; the tree reproduces the source exactly.
  • Grammar-agnostic. One kind type K covers both node and token kinds (the rowan model); the tree is generic over any K and needs no trait bound.
  • Zero-copy text. Tokens carry spans, not owned strings. node.text(source) borrows a sub-slice of the source.
  • Stack-safe at any depth. Builder, tokens(), descendants(), and Drop are all iterative — a 200,000-level tree is built, walked, and freed without a stack overflow.
  • Non-panicking builder. Structural misuse (unbalanced close, token at the root, a second root) is reported as a BuildError from finish(), never a panic.
  • no_std. Needs only alloc. The default std feature forwards to the token and span crates.

Installation

[dependencies]
syntax-lang = "1"

Or from the terminal:

cargo add syntax-lang

Example

A language defines one kind type for both nodes and tokens, then a parser drives the Builder to produce the tree.

use syntax_lang::{Builder, Span, Token, TokenKind};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Kind {
    // node kinds
    Root,
    Sum,
    // token kinds
    Num,
    Plus,
    Space,
}

impl TokenKind for Kind {
    fn is_trivia(&self) -> bool {
        matches!(self, Kind::Space)
    }
}

// Build the CST for `1 + 2`, keeping the spaces as trivia.
let mut b = Builder::new();
b.start_node(Kind::Root);
b.start_node(Kind::Sum);
b.token(Token::new(Kind::Num, Span::new(0, 1)));
b.token(Token::new(Kind::Space, Span::new(1, 2)));
b.token(Token::new(Kind::Plus, Span::new(2, 3)));
b.token(Token::new(Kind::Space, Span::new(3, 4)));
b.token(Token::new(Kind::Num, Span::new(4, 5)));
b.finish_node(); // close Sum
b.finish_node(); // close Root

let root = b.finish().expect("balanced");

// Lossless: the tree reproduces the source, trivia and all.
assert_eq!(root.text("1 + 2"), Some("1 + 2"));
assert_eq!(root.tokens().count(), 5);

// A formatter walks the significant tokens and skips the trivia.
let significant = root.tokens().filter(|t| !t.is_trivia()).count();
assert_eq!(significant, 3);

Walking a tree

  • node.tokens() — every leaf token in source order (the lossless stream, trivia included).
  • node.descendants() — every node in pre-order (a parent before its descendants).
  • node.children() / child_nodes() / child_tokens() — the direct level.
  • node.text(source) — the exact source slice this node covers, or None if the span lies outside source.

All of these are iterative and allocation-free.

API Overview

For the complete reference with parameter notes and multiple examples per item, see docs/API.md.

  • Node — an interior node: kind, covering span, ordered children, and the traversals.
  • Element — one child: a nested Node or a leaf Token.
  • Builder — assembles a tree from start_node / token / finish_node calls.
  • BuildError — why a builder could not produce a tree.
  • Re-exports: Token, TokenKind, Symbol (token-lang) and Span, Spanned (span-lang).

Design notes

  • Why spans, not text. A CST that owns copies of every lexeme duplicates the whole source. syntax-lang stores each token's byte range instead; the source string is the single source of truth, so the tree is compact and node.text(source) is a borrow. This is the highest-performance option and matches what token-lang already carries on a token.
  • Why one kind type. Nodes and tokens share K so generic tooling can ask a child's kind without first branching on node-vs-token, and a language declares its whole vocabulary in one enum.
  • Why iterative everything. A parser can emit an arbitrarily deep tree from adversarial input (a long run of open delimiters). Recursive drop glue would overflow the stack on such a tree, turning untrusted input into a crash. Traversal and teardown keep their stack on the heap so depth is bounded by memory, not the call stack.

Contributing

See dev/DIRECTIVES.md for engineering standards and the definition of done. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.