BSN-1002 - Deterministic Round-Trip Serialization

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

Deterministic Round-Trip Serialization

Summary

Standard Markdown abstract syntax trees discard whitespace, comments, and formatting trivia during compilation. When programmatic transformations modify a document, such as updating frontmatter tags or renaming wikilinks, re-serializing a lossy AST reformats the entire file, producing noisy Git diffs and corrupting custom markdown idioms.

Bosun adopts a lossless green-red tree architecture inspired by Rowan. By recording exact byte spans, newline variations, and indentation tokens directly in immutable green nodes, the serialization engine guarantees zero byte mutation outside modified syntax branches.

Green-Red Tree Representation

A green-red tree separates syntax topology from semantic context. A GreenNode contains only child count, length in bytes, and a syntax kind tag. Green nodes contain no pointers to parent elements and know nothing about their absolute file offset.

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct GreenNode {
    kind: SyntaxKind,
    text_len: TextSize,
    children: Arc<[GreenElement]>,
}
 
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum GreenElement {
    Node(GreenNode),
    Token(GreenToken),
}
 
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct GreenToken {
    kind: SyntaxKind,
    text: Arc<str>,
}

Because green nodes are immutable and position-independent, identical subtrees share memory through structural sharing. Red nodes wrap green nodes lazily, calculating absolute text ranges and parent pointers on demand as code navigates the tree.

When a document modification occurs, the engine constructs new green nodes only for the mutated leaf and its direct ancestors up to the root. All sibling nodes remain untouched in memory, preserving their exact pointers and byte boundaries.

Preserving Trivia and Non-Semantic Tokens

In traditional parsers, spaces between list markers and item text or blank lines between paragraphs are discarded. In Bosun, these tokens are retained as trivia variants within the SyntaxKind enumeration.

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
#[repr(u16)]
pub enum SyntaxKind {
    Whitespace = 0,
    Newline,
    ListMarkerDash,
    ListMarkerAsterisk,
    WikilinkOpen,
    WikilinkTarget,
    WikilinkClose,
    Paragraph,
    Document,
}

When a link target is renamed from old-target to new-target, only the WikilinkTarget token green node is replaced. The surrounding brackets, preceding text, following punctuation, and file newlines remain unchanged at the byte level.

This design preserves Windows CRLF line endings, trailing tab characters, and indentation variations without introducing unintended formatting normalization.

Round-Trip Invariant Verification

To guarantee serialization safety, the Bosun test suite runs continuous round-trip validation over a corpus of 120,000 Markdown files. The verification pipeline parses a source file into a green-red tree and immediately emits text back to a memory buffer without mutation.

The emitted bytes must match the source file byte-for-byte under cryptographic hash comparison. Any divergence in carriage return handling or tab preservation fails the build gate.

Automated fuzz testing generates millions of randomized edits across edge cases, including unclosed code fences, malformed tables, and deeply nested blockquotes. In every scenario, re-serializing unchanged document sections produces an empty byte diff against original source files.

Serialization Throughput and Token Footprints

The table below presents throughput benchmarks for CST generation and serialization back to plain text on an Apple M2 Max processor.

Corpus Size (Files)	Total File Size	Parse to CST Latency	Serialization Throughput	Round-Trip Byte Divergence
1,000 files	8.4 MB	18.2 ms	485 MB/s	0 bytes
5,000 files	42.1 MB	91.4 ms	478 MB/s	0 bytes
20,000 files	168.5 MB	362.8 ms	482 MB/s	0 bytes
50,000 files	421.2 MB	912.0 ms	475 MB/s	0 bytes
100,000 files	842.5 MB	1,840.5 ms	471 MB/s	0 bytes

---

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