BSN-1001 - Incremental Parsing with Tree-sitter

Living Document Notice
Published 2026-09-10. The evolving architecture, revisions, and connected notes for this dispatch live in the Stax Digital Garden.

Incremental Parsing with Tree-sitter

Summary

Full re-parsing of Markdown ASTs on individual keystrokes degrades interactive editor frame rates when documents exceed 10,000 lines. When evaluating large Markdown files, standard batch parsers discard the complete syntax tree on every byte insertion, re-allocating memory and traversing the entire document linearly.

Tree-sitter resolves this latency penalty by retaining the prior concrete syntax tree (CST) and re-evaluating only the subtrees intersected by the edited byte range. Integrating Tree-sitter into the Bosun local-first core engine allows keystroke-level syntax updates to execute under 150 microseconds across 50,000-line documents.

Byte Edit Records and Tree Mutation

To mutate an existing syntax tree without triggering a full re-parse, the editor frontend records text changes as discrete byte-offset deltas. These deltas are encapsulated in a TSInputEdit struct passed directly into the parser core before invoking the parsing step.

#[repr(C)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TSInputEdit {
    pub start_byte: u32,
    pub old_end_byte: u32,
    pub new_end_byte: u32,
    pub start_point: TSPoint,
    pub old_end_point: TSPoint,
    pub new_end_point: TSPoint,
}
 
#[repr(C)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TSPoint {
    pub row: u32,
    pub column: u32,
}

When an edit occurs at byte offset 4,120, Tree-sitter searches the existing CST to identify the smallest node enclosing the modification. It adjusts the byte spans of all subsequent nodes in the tree by adding (new_end_byte - old_end_byte). During the subsequent call to ts_parser_parse(), the parser reuses unchanged syntax nodes directly from the old tree, allocating new nodes only for modified grammar rules.

This incremental step avoids scanning unaffected paragraphs or headers located earlier or later in the document buffer. The parser reconstructs the ancestor path from the edit site up to the root node, re-validating grammar states in logarithmic time relative to document length.

Scanner Architecture for CommonMark and Frontmatter

Markdown syntax presents structural parsing challenges due to ambiguous indentation rules, nested block quotes, and YAML frontmatter delimiters. Tree-sitter handles context-free constructs through a generated LR(1) state machine, while context-dependent constructs rely on an external C scanner.

bool tree_sitter_markdown_external_scanner_scan(
    void *payload,
    TSLexer *lexer,
    const bool *valid_symbols
) {
    ScannerState *state = (ScannerState *)payload;
    if (valid_symbols[YAML_DELIMITER] && lexer->get_column(lexer) == 0) {
        if (scan_yaml_delimiter(lexer, state)) {
            lexer->result_symbol = YAML_DELIMITER;
            return true;
        }
    }
    return false;
}

The external scanner maintains an internal stack tracking block quote nesting depth and list item indentation levels. By serializing and deserializing this scanner state into fixed-size byte buffers, Tree-sitter preserves scanner consistency across incremental edits without re-scanning preceding blocks.

When a user inserts a character inside an existing list item, the scanner deserializes the active indent level, validates the delimiter character, and returns control to the parser without allocating auxiliary stack memory on the heap.

Memory Arena Allocation for CST Nodes

Tracking fine-grained CST nodes introduces heap allocation pressure. In naive implementations, allocating distinct heap nodes for every token causes memory fragmentation and CPU cache thrashing. Bosun addresses this overhead by maintaining syntax nodes within contiguous memory arenas.

Each node holds an explicit 32-bit symbol identifier, parent/child indices, and byte offsets rather than direct 64-bit pointers. This compact layout limits node size to 24 bytes, allowing cache lines to hold multiple adjacent syntax nodes during depth-first tree traversals.

Recycling memory arenas across edits keeps overall resident memory stable even after hundreds of consecutive typing operations. The arena allocator reuses freed node slots without returning virtual pages to the host operating system.

Parsing Performance Across Document Scales

The table below details benchmark results comparing full re-parsing against Tree-sitter incremental parsing across varying document sizes on an AMD Ryzen 9 7950X machine.

Document Scale (Lines)	Source Byte Size	Full Parse Latency (ms)	Incremental Edit Latency (μs)	Node Heap Allocations
500 lines	24.2 KB	0.82 ms	12.4 μs	0 bytes (reused)
2,500 lines	128.6 KB	4.15 ms	28.1 μs	144 bytes
10,000 lines	512.4 KB	16.80 ms	64.2 μs	288 bytes
25,000 lines	1.28 MB	42.10 ms	98.7 μs	432 bytes
50,000 lines	2.56 MB	87.40 ms	142.6 μs	576 bytes

---

• Directus Target: bosunpkm-blog
• Garden Source Reference: MOC - Bosun PKM Engine, MOC - Bosun PKM Tools, MOC - The Plain-Text Longevity Standard