Parsing

Status: Current Last updated: 2026-09-09 07:46 EDT

The parsing pipeline converts CHAT text into a typed ChatFile AST. The default and canonical parser is the tree-sitter parser (talkbank-parser). A second implementation, talkbank-parser-re2c, exists alongside it as a specification oracle and high-throughput batch parser; it produces the same ChatFile model and is opt-in via chatter validate --parser re2c. The LSP and all production paths default to the tree-sitter parser.

Tree-Sitter Parser

The talkbank-parser crate wraps the tree-sitter C parser and converts its concrete syntax tree (CST) into the ChatFile model.

Full-file parsing is the canonical entry point. TreeSitterParser also provides fragment methods (parse_word_fragment(), parse_main_tier_fragment(), parse_chat_file_fragment(), etc.) for parsing isolated CHAT fragments directly.

CST → AST Pipeline

flowchart LR
    chat["CHAT text\n(.cha file)"]
    grammar["tree-sitter grammar\n(grammar.js → parser.c)"]
    cst["Concrete Syntax Tree\n(all whitespace preserved)"]
    walker["TreeSitterParser\n(CST traversal)"]
    ast["ChatFile AST\n(semantic model)"]

    chat --> grammar --> cst --> walker --> ast

Source text
    ↓ tree-sitter parse
Concrete Syntax Tree (CST), green tree with all tokens
    ↓ tree_parsing (Rust)
ChatFile AST, typed model with validation-ready data

The CST preserves every character of the source (whitespace, punctuation, comments). The Rust tree-parsing modules extract semantic information from the CST into the typed model through a generated typed traversal layer, described next.

The generated typed traversal (generated_traversal)

The bridge between the tree-sitter CST and the typed model is a single generated module, crates/talkbank-parser/src/generated_traversal.rs, produced by the tree-sitter-grammar-utils generator from the grammar’s own machine-readable description (grammar/src/grammar.json plus node-types.json). It contains one extract_* function per grammar rule, each returning a typed view of that rule’s children, so consumer code dispatches on generated types rather than on node.kind() strings.

Every child position a grammar rule models is exposed as a NodeSlot with five states, of which each position’s type admits only the ones that position can produce:

The generator names the position’s kind in the slot’s type. A ChildSlot (a child taken by kind) is never Unexpected; a SeqSlot (an inline sequence) is never Missing or Unexpected; a ChoiceSlot can be any of the five; a ClassifiedSlot (a supertype rule’s own node) is never Absent. The impossible states have the uninhabited Never as their payload, so an arm that reads a node out of one does not compile, and a match by value may omit it. Every generated accessor hands out a reference, and a match through a reference must still name every variant, so a consumer matches slot.view(), which copies the recovery states out by value and borrows only the present payload. The parser’s shared verbs (expect_present, expect_structure, expect_delimiter, present) are generic over all four kinds.

This design makes silent recovery-node loss structurally impossible at modeled positions: Missing and Error are explicit variants every call site must handle, not conditions a hand-written walk can forget to check, and a diagnostic for a state the position cannot reach cannot be written either. Missing maps to E342 (a MISSING placeholder for a required element); Error reaches E316, which is the generic “content could not be parsed” catch-all.

That asymmetry matters when reading a diagnostic. E342 names a specific fact the parser knows. E316 names the absence of one, so an E316 on input a human can read is a standing invitation to ask whether the parser, rather than the file, is at fault: a generic code standing in for a specific rule is one of the documented tells of a chatter defect. Hand-walking the CST with node.kind() comparisons, and classifying the text of ERROR nodes to guess what was malformed, are both banned in production parser code for exactly this reason.

What to write instead, when the question really is “which alternative is this node?” A grammar rule whose alternatives are each a single named kind lowers to a <Rule>Choice enum, and the generator emits that enum’s own classifier, <Rule>Choice::from_node. It returns Option<Self>: None says the node is not one of the alternatives, which is a fact about the input, not a default to paper over. Matching the result is exhaustive, so adding an alternative to the grammar breaks compilation at every site that decides on it, which a chain of kind() string comparisons never does.

The classifier is emitted exactly when a kind can identify an alternative. A choice with a sequence, repeat or optional alternative is told apart by STRUCTURE, so it deliberately gets none: there, the shape is the question, and a kind-keyed answer would be a guess. When no classifier exists, extract the rule and match on the carrier rather than reaching for kind().

The ban above stood for a year with nothing to point at, which is why the node_types kind-constant catalogue kept being reached for: a prohibition loses to whatever the API actually makes easy. This is that missing affordance, and it lives in the generator so every consuming grammar gets it.

Recovery handling is two-layered by design: the per-position NodeSlot states cover every position the grammar models, and a whole-tree recovery backstop (see the recovery discussion below) surfaces recovery nodes that land where no grammar rule models a slot, such as top-level junk. The layers are complementary, and both are load-bearing: removing the backstop demonstrably regresses the CHECK-parity and recovery-is-not-validity test suites.

The module is regenerated whenever the grammar changes; the command and its preconditions are in Grammar Workflow. It is never edited by hand: generator defects are fixed in tree-sitter-grammar-utils and regenerated.

The staleness guard proves less than its name suggests. generated_traversal_is_current recomputes the digests of grammar.json and node-types.json, so it catches a forgotten regeneration after a grammar change and nothing else. It cannot see which generator produced the file, so a module emitted by an older backend passes indefinitely. The generator’s name and version are stamped in the file’s own header comment; read that when the question is which backend built it.

Error Recovery

Tree-sitter’s GLR algorithm provides automatic error recovery. When the parser encounters unexpected input, it:

1. Inserts ERROR nodes in the CST
2. Continues parsing the rest of the file
3. Reports parse errors via the ErrorSink trait

This means the parser always produces a result, even for malformed files, it extracts as much structure as possible.

ParseOutcome

Individual parse functions return ParseOutcome<T>:

• ParseOutcome::parsed(value): successfully parsed
• ParseOutcome::rejected(): could not parse this node (error already reported)

This allows the parser to skip individual malformed elements while continuing to parse the rest of the file.

Parser Equivalence

The reference corpus is the primary correctness signal:

cargo test -p talkbank-parser-tests --tests reference_corpus_parses

Each .cha file is its own test, so failures are reported per file. The file count is deliberately not stated here: this page claimed 78 for months while the corpus grew past a hundred. Ask the tree (rg --files -g '*.cha' corpus/reference | wc -l).

TreeSitterParser API

TreeSitterParser is the concrete canonical parser handle. Reuse an instance across calls. The shared talkbank_model::ChatParser trait also supports generic callers and backend parity tests; both tree-sitter and re2c implement it. Its sink methods are generic, so the trait is not a dyn trait object.

use talkbank_parser::TreeSitterParser;

let parser = TreeSitterParser::new()?;

// Full-file parsing (methods on TreeSitterParser).
// ParseProduct::Built retains the file and diagnostics together, even when
// recovery was necessary. Unbuildable has diagnostics without a model.
let product = parser.parse_chat_file(&source);
// parse_chat_file_streaming pushes diagnostics into an ErrorSink as it
// goes, useful for very large files or LSP-style incremental flows.
let chat_file = parser.parse_chat_file_streaming(&source, &errors);

// Fragment parsing (methods on TreeSitterParser), used when synthesizing
// CHAT from non-CHAT sources (ASR output, UD annotations).
let word = parser.parse_word_fragment(word_text, document_offset, &errors);
let main_tier = parser.parse_main_tier_fragment(tier_text, document_offset, &errors);

Diagnostic coordinates

Fragment parsing adds the caller’s offset to model spans and diagnostic document locations. FragmentSource admits the complete input range before parsing and owns this translation for both backends. Admission checks origin + input.len() without overflowing; ranges beyond u32::MAX are rejected with E310 and an unknown location, since no representable location exists. Origins above i32::MAX remain supported: the existing signed edit-shift interface receives bounded positive steps, never a wrapped negative origin. A diagnostic’s ErrorContext owns its own source text, so its highlight remains relative to that text. Wrapper removal is a separate operation owned by WrappedFragment; it projects the synthetic source before applying any document origin.

Word and main-tier fragments use the multi-root grammar directly, so there is no synthetic prefix to subtract. MainTierFragment admits a typed main-tier node only when it covers the complete parse source and the root has no extra or unexpected content. Lowering consumes that proof together with the original input, clipping the aggregate tier/content spans to exclude an appended line terminator. LF and CRLF supplied by the caller remain part of those spans. Trailing garbage or another tier cannot be silently ignored. Header, utterance, participant-entry and dependent-tier adapters, including the standalone parse_header and parse_tiers entry points, use an owned WrappedFragment: its constructor records the actual input boundary as it assembles the source, and both the model projection and diagnostic sink use that boundary. Its diagnostic sink removes that prefix from both primary and secondary spans. Context is projected only when its text exactly matches the owned synthetic source; an independent context retains its own coordinates regardless of length. cargo test -p talkbank-parser --lib api::fragment::tests checks long inputs, related labels and independent context text. These adapters no longer use the legacy sink’s length heuristic. Header lowering consumes a HeaderFragment that owns the located node together with its wrapped source. Admission requires the node to account for all caller text: only surrounding whitespace may lie outside it or extend into the synthetic line terminator. The former start-only check accepted the first of two headers and discarded the second. The public regression reproduces that refusal boundary, while controls retain folded header content and caller-supplied LF/CRLF. Raw ordinal lookup and document-root navigation remain separate traversal improvements. Header lookup failures carry tree facts in HeaderNotFound, rather than constructing a parse error with invented empty context. The fragment caller attaches the real input and its full span; public fragment rebasing then adds the document origin to the location while leaving that context local. The context_public_api::unlocated_header_reports_the_callers_source_and_origin regression exercises this failure through the public API at origins zero and 200. Complete documents passed to the utterance adapter are recognized through generated typed CST traversal and receive no extra document wrapper.

cargo test -p talkbank-parser --test integration context_public_api reproduces the fragment regression checks: UTF-8 word spans, caller offsets, rejected fragments, and utterances with or without a trailing newline or document headers. These caught obsolete prefix subtraction that collapsed valid word spans to zero, subtraction of caller origins from errors, and unremoved synthetic prefixes on rejected utterances and participant entries.

The E326 boundary test exercises both parsers with LF and CRLF, UTF-8 content, and offsets zero and 200. Unsupported-line recovery must identify each skipped line, retain following utterances, and preserve the diagnostic’s local source highlight. The fragment_range_tests public-API controls exercise both backends above 2 GiB, at the final representable byte, and with overflowing ranges. They also verify that diagnostic context stays snippet-relative. Synthetic terminators for morphology, phonology and grammatical-relation fragments are parsed at local origin zero; only the extracted caller result is moved into document coordinates. Wrapper allocation separately admits its complete synthetic source size, and trimming a caller newline cannot bypass admission of the original input range. This does not change the legacy SpanShift edit API or Span::from_usize truncation for unrelated callers; the admitted parser paths replace their raw origin casts. The legacy OffsetAdjustingErrorSink remains exported by the model crate for compatibility, but the tree-sitter parser has no remaining callers. Its eventual removal is separate from migrating these owned parser paths.

Missing encoding declaration

The document grammar admits an absent @UTF8 anchor as an explicit optional slot. Lowering consumes that generated slot and retains the present headers and utterances without inventing an encoding declaration. Shared validation still rejects the file with E503. Previously the canonical parser discarded the entire document and reported several required headers as missing even though they were present. The authored E503 example and its declaration-present control exercise this recovery; CLAN CHECK reports the corresponding CHECK (69).

The re2c file parser carries each header’s lexer extent and separator together in HeaderProvenance. Lowering uses that extent instead of an unknown span, so shared missing-header diagnostics derive a real EOF from the final header. The cross-backend missing_encoding_keeps_the_document_and_locates_the_single_refusal test checks retained utterances, exact diagnostics, and EOF locations at zero, nonzero and maximum representable document origins.

Recovery-wrapper suppression requires a private DocumentRecoveryWrapper proof at the document position: every direct child must be a generated document construct or separately reported recovery. A recognizable header beside malformed raw tokens, or a stray header beside a complete document, cannot suppress E316.

DocumentRoot owns both the original syntax root and the selected document. Lowering finds a complete document even after a recovery sibling, while the diagnostic backstop covers the entire source. This prevents trailing text after @End from validating clean and avoids missing-header cascades when a leading error precedes an otherwise complete document. Private fields prevent callers from combining a document with an unrelated diagnostic scope.

Syntax completeness does not establish semantic validity; shared validation still owns required headers and other CHAT rules. The LSP owns source-bound analysis snapshots rather than a second parser-level cache-admission API.

At EOF, lowering retains a generated MainTierNode stranded outside its line wrapper by reusing the normal utterance builder and parse-health transition. For the flattened simple terminal sequence without a final newline, TerminalMainTier pairs the generated grammar tokens with the original source range. Lowering reuses the normal main-tier fragment parser, which clips its synthetic newline and rebases into caller coordinates. The diagnostic backstop uses the same structural admission. The E502 example checks retained speech and diagnostics in both newline forms, including maximum representable source origins; leading and trailing recovery-region regressions remain separate.

AST Structure

The resulting ChatFile AST has a recursive content structure:

flowchart TD
    cf["ChatFile"]
    hdr["Headers\n@Languages, @Participants,\n@ID, @Options"]
    utts["Utterances[]"]
    mt["MainTier\nspeaker + content"]
    dt["DependentTiers[]\n%mor, %gra, %pho, %sin, %wor"]
    uc["UtteranceContent\n24 variants"]
    leaf["Leaves\nWord | ReplacedWord | Separator"]
    group["Groups\nGroup | AnnotatedGroup |\nRetrace | PhoGroup | SinGroup | Quotation"]

    cf --> hdr & utts
    utts --> mt & dt
    mt --> uc
    uc --> leaf & group
    group -->|recurse| uc

Parser String Handling

The tree-sitter parser constructs owned model types (e.g., MorWord, GrammaticalRelation) directly from CST text. String-heavy types like PosCategory and MorStem use Arc<str> interning to avoid redundant allocations for repeated values. Short strings in model newtypes use SmolStr for inline storage up to 23 bytes.

Editor source revisions

The LSP stores one DocumentAnalysis owning exact source bytes, a tree-sitter CST, the lowered model, and diagnostics. Its constructor is the only route to those artifacts. Reusing the CST first applies an InputEdit computed from its own prior source, so debounced intermediate edits cannot substitute the wrong baseline. Both the edit boundaries and tree-sitter columns use UTF-8 bytes; LSP wire positions remain UTF-16.

Each changed analysis lowers the model and calls ChatFile::validate_with_alignment in full. Previous header errors or absolute AST spans are not copied into a new revision. This removes the independent cache maps and custom validation sequence that missed deleted headers and file-level checks. Tree-sitter incrementality and whole-analysis reuse for identical source remain. More selective semantic reuse needs an explicit dependency and span-identity design plus measurements.

Feature requests during debounce admit cached models/trees only for identical source, otherwise parsing the requested text transiently. Pull diagnostics use the same analysis constructor as pushed diagnostics. A replaced or closed revision cannot commit its analysis, and push results carry the editor version. No cache guard crosses asynchronous publication.

The existing stdio integration binary checks fresh-open/edit parity, skipped revisions and requests during debounce. Its process owner handles shutdown and cleanup; the message inbox preserves interleaved notifications while awaiting responses. This catches production orchestration errors that isolated tree splicing helpers could not.

For a local computation measurement, run the ignored measure_analysis_latency library test with --ignored --nocapture. Optionally set TALKBANK_LSP_BENCH_SOURCE to an existing transcript; it is read without changes. Record build profile and distinguish computation from the 250 ms debounce. The benchmark is intentionally excluded from CI and sets no timing threshold.

This page last changed: 2026-09-09 (commit b6bfc5d2). The whole book last changed: 2026-09-15 (commit bb4bef82).