Introduction

m2-syn is a parser-independent typed syntax graph for Macaulay2. One syntax! declaration describes the algebraic shape of the graph; generated implementations provide construction, traversal, source provenance, and conversion from a concrete syntax tree.

The API is experimental and may change while the typed grammar and parser adapter interfaces are being established.

Project direction

This crate began as the syntax and analysis layer for the Macaulay2 language server. It grew into a standalone, syn-like foundation for M2: an owned, typed representation that can be constructed from source, traversed and rewritten, and emitted as code.

The current priority is the basic source pipeline:

1. read M2 source and parse it with Tree-sitter;
2. reconstruct the complete typed AST;
3. emit normalized M2 that parses back to the same structure.

The syntax model follows the grammar published as tree-sitter-macaulay2 6.0.0, resolved from the registry like any other dependency. Local builds and tests therefore exercise the same grammar downstream users get, rather than whatever happens to be checked out beside the repository.

Round-tripping through both the Tree-sitter and native parser backends works end to end, and quote_m2!/parse_quote_m2! are stable enough for everyday use (see Quoting). The next steps are a converter from M2’s own Core parser output and a macro-expansion engine built on the typed graph; Core’s own concrete tree is considerably less structured than either parser backend here (no named fields, several statement forms share one flat node shape distinguished only by which positional slots are populated), so the typed graph and its generated APIs must stay parser-independent rather than special-cased around it.

Longer term, m2-syn should support semantic and typechecking walks, incremental analysis after referenced code changes, selected node metadata, and procedural macros for M2. Visit, VisitMut, and Fold are intended as the basic traversal and transformation vocabulary for that work. The guiding design rule is to describe as little grammar as possible in syntax! and generate the repetitive construction, traversal, reconstruction, and printing machinery.

Representation pipeline

The frontend has a lexical representation, a framed cell representation, and one generated typed graph:

source --Lex--> TokenStream --Tokenize--> CellStream<CellTokenStream> --Parser--> typed CST
   |                                                                            |
   +------------------> Tree-sitter CST --------------------Migrate--------------+
                                                                                |
source <-----------------------Display/Lex---------------------------------------+

TokenStream contains only lexical token trees. Tokenize performs the first grammar-aware step: it confirms top-level cell boundaries and recursively adds CellTokenTree::Adj markers. Each resulting CellTokenStream is therefore a partially parsed cell, and CellStream records EOC and EOF structurally through the sequence rather than virtual tokens. Layout is the source gap between two neighbouring spans, so a file’s two edges need owners: the BOF marker spans the layout before the first significant byte and the EOF marker the layout after the last one. Each is emitted only while it still physically borders the first or last cell, so joined or edited streams never reinstate stale text. Converting a cell back into a raw TokenStream removes adjacency recursively.

Parse and Lex are the two directions at the typed boundary. For a typed value c, parsing its emission should recover c. Emitting a parsed raw stream may normalize insignificant layout:

Parse(Lex(c)) = c
Lex(Parse(tokens)) = normalize(tokens)

The two parser backends differ only in how they reach the generated graph. NativeParser consumes framed cells and constructs it directly from the shared token cursor. TreeSitterParser lowers Tree-sitter’s concrete grammar layout directly and uses ExternalCstNode plus generated Migrate for compatible leaves, operators, and tokens. It never routes the source through NativeParser. Those adapter traits are not an alternative graph or a traversal API; typed traversal is generated as Visit, VisitMut, and Fold.

The ownership boundaries are intentionally narrow:

syntax! {
    // Structural precedences with no single owning token; every operator
    // below carries its own precedence inline instead.
    precedence: {
        PREC_CONTROL = 12,
    }

    tokens {
        // L/R is the binary associativity. A third slot overrides the
        // prefix strength when it differs from the precedence.
        [+] { bin, pref, aug } (50, L)
        [=] { infix }          (14, R)
        [if] [then] [else]     (PREC_CONTROL)
        [,]
    }

    #[operator(prefix)]
    enum PrefixOperator {}
    #[operator(binary)]
    enum BinaryOperator {}
    #[operator(postfix)]
    enum PostfixOperator {}

    struct Symbol;

    struct BinaryExpression {
        left: Expr,
        operator: BinaryOperator,
        right: Expr,
    }

    enum Expr {
        BinaryExpression,
        Symbol,
    }
}

The canonical declaration lives in src/schema/nodes.rs, where the syntax! procedural macro expands it into the token, node, traversal, and fold items, and into the visit, visit_mut, and fold modules re-exported at the crate root. The expansion is items only — no macro_rules! — so rust-analyzer resolves every generated name.

Token! and Delimiter! are ordinary source in src/schema/macros.rs instead of part of that expansion. Neither depends on the schema: Token! forwards the spelling to the token! procedural macro, and the delimiter families are a fixed set.

The schema

Every token is declared in tokens { ... }; adjacent spellings share the metadata written on their right. A binary role writes L or R, while a literal strength remains available for a non-associative rule. A prefix role binds at the token’s precedence unless a third slot overrides it, and post writes no strength at all. The separate precedence stage only holds names for structural precedences with no single owning operator token (delimiter/control-clause stoppers the native parser references directly); it is not a shared table operators look their numbers up in, so a level used by exactly one token is just written as a literal there and nowhere else. The aug tag generates the corresponding assignment token, which binds exactly like the = it abbreviates and so takes its rule from that declaration.

Boxing is explicit: put * after a declaration name when recursive references to that type need Box. Ordinary fields, token types, and nonrecursive categories remain inline. Constructors accept the declared types and hide that storage conversion. Generated signatures consistently refer to literal token types through Token![...]; their concrete Rust names are an implementation detail of the expansion.

Delimited<T> retains any of the four paired delimiter families, while a second type parameter such as Delimiter![()] refines the family statically. Both spelled boundary spans are stored. The convenient type macros construct the refined forms:

#![allow(unused)]
fn main() {
use m2_syn::{Lex, Span};

type Parenthesized = m2_syn::paren!(m2_syn::Token![+]);
let value: Parenthesized = m2_syn::paren!(
    m2_syn::Token![+](Span::detached()),
    Span::detached(),
);
assert_eq!(value.to_m2(), "(+)");
}

paren!, brackets!, braces!, and angle_bars! cover the four families. punct!(T) names a nonempty comma-punctuated sequence; punct!(value first) and punct!(pairs first; comma => next) construct one while retaining every typed comma and its span. Use Option<Punctuated<T>> when the whole sequence may be absent, or put an empty alternative in T when components may be empty. Every delimiter atom and wrapper implements both Parse and Lex, so they can be direct parse_quote_m2! targets.

A field normally uses its Rust name as its CST field name. Mark it (_) when it should consume the next matching unlabelled child instead. The schema deliberately permits only named struct fields and bare-type enum variants — a variant never spells out a separate name, since it’s always either the wrapped type’s own name or, for a variant wrapping a token, that token’s capitalized name — keeping both the declaration and generated API shaped like ordinary Rust rather than requiring the same fact to be written twice.

Generated implementations

The declaration generates the following API without requiring per-node handwritten boilerplate. Runtime alternatives are represented only by the grammar-backed enums themselves; there is no parallel global node-kind enum.

The traversal traits have ordinary, independently addressable modules: visit::Visit, visit_mut::VisitMut, and fold::Fold. Their node-specific method inventories and free default walkers are generated from the syntax declaration, so adding a node cannot leave one traversal API incomplete. An override can inspect a node and call its module’s free walker to continue into its children. VisitMut edits the owned typed graph in place. Fold consumes nodes and returns the reconstructed graph.

cargo run --example type_inference demonstrates the intended analysis path: generated Visit dispatch selects node-specific rules, and the binary rule consumes the neighbouring operand facts to compute an upward-closed result range. Each rule overrides exactly one node, calls that node’s free walker when it needs its operands, and records the most specific Macaulay2 class it can prove; conditionals join their branches through the class hierarchy and unmodelled expressions keep the Thing bound. Symbol resolution, graph storage and fixed-point solving belong in the analysis/LSP layer; this example only verifies the syntax traversal boundary, so its span-keyed fact table is the smallest storage that lets a parent rule read what its children proved.

Spans

A Span is a byte range and may retain a shared handle to the source buffer it indexes. Source-backed spans return their text directly; offset-only spans can still index an explicitly supplied str or String.

#![allow(unused)]
fn main() {
use m2_syn::Span;

let source = "quotient ring";
let ring = Span::source(source).subspan(9, 13);
assert_eq!(ring.text(), Some("ring"));
assert_eq!(&source[&ring], "ring");
}

Tokens and textual leaves store only spans, never copied spellings. Composite nodes derive theirs by joining their components, so a node’s span is exactly the extent of the syntax beneath it. Hand-built syntax may use Span::detached(), which names no location; constructors attach a source-backed fragment when variable text is supplied.

No line or column

A span stores one offset per boundary. Line and column are deliberately absent: they are facts about a particular buffer’s contents, not about the position, so they belong to whoever holds the buffer and can be recovered from it on demand. rustc makes the same choice — its Span holds lo and hi byte positions, and SourceMap binary-searches a line table when a diagnostic needs to print file:line:col.

This also removes the need for sentinel endpoints. (line, column) has no greatest element, so “end of file” would have to be invented; a byte offset does not, and an unclosed group simply ends at source.len(), which the lexer has in hand the moment it reaches end of input.

Edits

A TextEdit acts on both halves of the indexing relation — on the buffer, and on the spans that index it — and the two actions agree:

#![allow(unused)]
fn main() {
use m2_syn::{Span, TextEdit};

let source = "quotient ring";
let ring = Span::source(source).subspan(9, 13);
let edit = TextEdit::insertion(0, "the ");

let edited = edit.apply(source).unwrap();
assert_eq!(&edited[ring.shifted(&edit)], &source[&ring]);
}

A span shifted past an edit keeps naming the syntax it named before. Text landing inside a span is carried into it, and a span the edit deletes outright collapses to a zero-width span where it used to be rather than detaching, because it still records where the syntax was.

What spans are not

A span is not the identity of a semantic object, and it is not a stable handle across edits. Incremental dependency identity belongs in the semantic layer. Macro hygiene likewise is a separate axis — rustc keeps it in a SyntaxContext alongside the byte positions rather than inside them — and is not yet modelled here.

Native lexer

lex is the first native-parser layer. It accepts any byte iterator and returns the same source-spanned TokenStream used by quoting and emission. The raw token categories are Group, Ident, Literal, and Punct; comments are retained as trivia attached to those atoms or to the surrounding stream. The lexer does not synthesize typed nodes, adjacency, EOC, or EOF. Physical layout remains recoverable from source gaps. After greedy token recognition, structural delimiter pairs become recursive Group trees that retain exact opening and closing spans.

Generated Token![..] values are checked typed refinements of these raw atoms, not another TokenTree variant. Tokenize performs the later framing step and represents adjacency explicitly as CellTokenTree::Adj; converting the cell back to lexical tokens removes it. Thus f(x) and f (x) have the same framed operator, while return 1 has none. The lexer applies context-free maximal munch across generated operators, delimiters, and comment openers. Consequently |--1 begins with the |- operator rather than a comment, while a token beginning with -- is a line comment. Likewise, (*) remains the single greedy operator rather than a parenthesized group. Quotation marks are part of a single literal token, not delimiter groups.

$ remains part of an identifier. Package$name$12 is one IdentToken; its typed Symbol merely adds optional subspans for Package and 12. Only one package qualifier and one decimal index can be marked. Exact Core$word spellings use a separate hardcoded renaming hook, so Core$not behaves as not, but Core$Core$not is an ordinary symbol.

Precision precedes exponent in a decimal real literal. 1p53, .5p20, and 1.25p53e3 are single FloatLiteral nodes. In 1e3p20, the completed exponent ends the literal and p20 is the adjacent symbol.

The lexer owns one validated source buffer and gives every atom a span into the same allocation. Variable spellings are therefore sliced from source instead of copied into token nodes. The byte-iterator entry point first materializes its finite input; lex_str starts directly from source text.

#![allow(unused)]
fn main() {
use m2_syn::{TokenTree, lex_str};

let tokens = lex_str("***1")?;
let spellings = tokens
    .into_iter()
    .filter_map(|token| match token {
        TokenTree::Literal(token) => Some(token.text().to_owned()),
        token => token.spelling().map(str::to_owned),
    })
    .collect::<Vec<_>>();

assert_eq!(spellings, ["**", "*", "1"]);
Ok::<(), m2_syn::LexError>(())
}

Parser adapters

Generated migration depends only on ExternalCstNode. TreeSitterNode adapts Tree-sitter identity, field names, source text, extras, and ranges to that interface for schema-compatible leaves, operators, and tokens. Complete-file TreeSitterParser lowers Tree-sitter’s muted, pack, delimiter, operator, assignment, and control nodes directly into the cleaned typed graph; it does not re-lex the source or call the native parser. The external node view ends at the adapter and is never stored in a typed node.

Parser<T> is the parser-backend boundary. It receives a CellStream and returns a generated syntax target. T defaults to SourceFile, while parsers may implement the trait again for more specific targets such as Expr. Both built-in backends implement this same cell-stream API. A parser with its own CST can implement ExternalCstNode and call migrate; a parser whose native model already matches the generated graph can construct the target directly.

The target-owned Parse trait is the dual of Lex: parse2::<T> consumes one complete TokenStream as T. Generated Token![..] atoms, raw token categories, token streams, boxes, delimiters, comma-punctuated collections, and terminated bodies implement it. ParseStream shares immutable token storage through the persistent TokenStream handle; end-of-input is cursor state rather than a synthetic token. A fork has an independent index and advance_to explicitly commits successful speculation. parse_quote_m2! composes quoting with type-inferred parsing.

Lex::to_token_stream is the lexical projection, while Tokenize produces framed cells. The native parser supports the normalized round trip CellStream -> SourceFile -> CellStream -> SourceFile. Generated concrete token structs are deliberately underscore-prefixed; use Token![..] to name their types and inspect the underlying TokenTree after Lex when working with a heterogeneous stream. Delimiter structs follow the same rule through Delimiter![..].

Cell framing is shared infrastructure rather than a parser side effect. Semicolons and complete physical lines confirm top-level boundaries; delimiter groups are framed recursively but their separators never become top-level boundaries. The result uses CellTokenTree::Adj instead of manufacturing empty punctuation inside the lexical stream.

#![allow(unused)]
fn main() {
use std::convert::Infallible;
use m2_syn::nodes::{BOF, EOF, SourceFile};
use m2_syn::{CellStream, Parser, Span, Tokenize, lex_str, parse_with};

struct EmptyParser;

impl Parser for EmptyParser {
    type Error = Infallible;

    fn parse_cells(&mut self, _cells: CellStream) -> Result<SourceFile, Self::Error> {
        Ok(SourceFile::new(
            BOF::new("", Span::for_text("")),
            Vec::new(),
            EOF::new("", Span::for_text("")),
        ))
    }
}

let tokens = lex_str("").unwrap();
let cells = tokens.to_cell_stream().unwrap();
let file = parse_with(&mut EmptyParser, cells).unwrap();
assert!(file.cells.is_empty());
}

TreeSitterParser is the built-in implementation and can be retained across calls. parse_file remains the convenience function that creates one for a single parse.

parse_file is the concrete Macaulay2 parser entry point:

fn main() -> Result<(), m2_syn::ParseError> {
use m2_syn::{Lex, parse_file};

let file = parse_file("x + 1\ny + x * 2")?;
let normalized = file.to_m2();
assert_eq!(parse_file(&normalized)?.to_m2(), normalized);
Ok(())
}

parse_tokens connects generated or quoted M2 back to typed syntax:

fn main() -> Result<(), m2_syn::ParseError> {
use m2_syn::{Lex, parse_tokens, quote_m2};

let quoted = quote_m2! { left + (right) };
let file = parse_tokens(&quoted)?;
assert_eq!(file.to_m2(), "left + (right)");
Ok(())
}

ParsedFile provides the convenient source-to-source interface over these lower-level pieces. It owns one mutable typed CST and computes every current output from that tree, so a token projection cannot silently become stale after an edit. The original source remains available separately as an immutable snapshot. from_source uses Tree-sitter; from_source_native selects the direct precedence parser.

fn main() -> Result<(), Box<dyn std::error::Error>> {
use m2_syn::{ParsedFile, Symbol, visit_mut::VisitMut};

struct Rename;

impl VisitMut for Rename {
    fn visit_symbol_mut(&mut self, symbol: &mut Symbol) {
        if symbol.text() == "left" {
            symbol.set_text("renamed");
        }
    }
}

let file = ParsedFile::from_source("left + right")?.edit(|cst| {
    Rename.visit_source_file_mut(cst);
});

assert_eq!(file.original_source(), "left + right");
assert_eq!(file.to_source(), "renamed + right");

// Stable, uncolored projections are useful in tests and diagnostics.
println!("{}", file.pretty_tokens());
println!("{}", file.pretty_cst());

// One terminal-aware report includes the retained input, recursively flattened
// tokens, and the generated typed CST.
file.print_pretty()?;
Ok(())
}

The CST view is generated from the same schema as node construction and traversal. Struct fields become labelled edges, category enums remain invisible implementation details, punctuated sequences expose both values and comma tokens, leaf source spellings precede their node types, and delimiters show separate opening and closing boundaries. The token view rotates primitive sequences into compact horizontal bands: centered token text occupies the first row and token type the second, with recursive group openings and closings represented as ordinary columns. End-of-cell markers are explicit, always end a band, and group delimiters provide the only soft wrapping boundaries. Trivia is hidden by default and coalesced when enabled. Source ranges can be disabled and ANSI styling can be selected explicitly through PrettyReport.

Run the inspector with its built-in example or give it an M2 source file:

cargo run --example inspect
cargo run --example inspect -- path/to/file.m2

ChildCursor removes Tree-sitter extras, so comments do not come from the Tree-sitter CST. After lowering, the adapter lexes the same source, settles every comment onto the raw token it follows, and transfers that trivia to the typed terminal or delimiter spanning exactly the same bytes, which places comments as the native parser does.

Quoting

quote_m2! constructs an M2 TokenStream from Rust tokens. $(...) interpolates any Rust expression implementing Lex. Each interpolation is first emitted as a real fragment, so punctuation, identifiers, literals, and groups compose according to their actual token boundaries rather than the Rust expression’s type. Parentheses, brackets, braces, and M2 angle bars are emitted as recursive raw groups.

$[pattern in iterator] { ... } repeats a recursively quoted template using an ordinary Rust for loop. The iterator and pattern are explicit; interpolations that do not depend on the pattern are reused normally on each iteration.

#![allow(unused)]
fn main() {
use m2_syn::{Span, Symbol, quote_m2};

let value = Symbol::new("value", Span::detached());
let tokens = quote_m2! {
    result = $(value) + 1;
    return result
};

assert_eq!(tokens.to_string(), "result=value+1;return result");

let values = [
    Symbol::new("left", Span::detached()),
    Symbol::new("right", Span::detached()),
];
let comma = m2_syn::Token![,](Span::detached());
let repeated = quote_m2! {
    $[value in &values] { $(value) $(comma) }
};
assert_eq!(repeated.to_string(), "left,right,");
}

The rendered text is normalized M2 source, not a lossless reproduction of whitespace or comments discarded by the typed graph.

Development

Run the complete workspace checks from the repository root:

cargo fmt --all --check
cargo check --workspace
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace

The schema is expanded by the syntax! procedural macro, so changes to src/schema/nodes.rs are picked up by the next compile; there is no generated source to refresh or commit.

m2-syn is licensed under the GNU General Public License v3.0.