Architecture

Architecture

TinyTokenizer uses a two-level tokenization architecture designed for high performance and flexibility.

Two-Level Design

Source Text
    │
    ▼
┌─────────────────────────────────────────────┐
│  Level 1: Lexer                             │
│  - Stateless character classifier           │
│  - Produces SimpleToken structs             │
│  - SIMD-optimized with SearchValues<char>   │
│  - Never backtracks, never fails            │
└─────────────────────────────────────────────┘
    │
    ▼
┌─────────────────────────────────────────────┐
│  Level 2: TokenParser                       │
│  - Combines simple tokens into semantic     │
│    Token records                            │
│  - Handles blocks, strings, comments        │
│  - Recursive block parsing                  │
│  - Error recovery with ErrorToken           │
└─────────────────────────────────────────────┘
    │
    ▼
Semantic Tokens (Token records)

Level 1 — Lexer

The Lexer class performs pure character classification:

• Stateless — No context between characters
• Never fails — Every character produces a token
• SIMD-optimized — Uses SearchValues<char> for vectorized matching
• Outputs SimpleToken — Lightweight struct with position tracking

var lexer = new Lexer();
IEnumerable<SimpleToken> simpleTokens = lexer.Lex("foo(x)");

// Produces: Ident, OpenParen, Ident, CloseParen

Level 2 — TokenParser

The TokenParser class combines simple tokens into semantic tokens:

• Combines tokens — Merges OpenParen + content + CloseParen into BlockToken
• Handles strings — Recognizes escape sequences
• Parses comments — Single-line and multi-line
• Matches operators — Greedy multi-character operator matching
• Error recovery — Produces ErrorToken for malformed input

var parser = new TokenParser(options);
IEnumerable<Token> tokens = parser.Parse(simpleTokens);

// Produces: IdentToken, BlockToken (with children)

Zero-Allocation Design

TinyTokenizer minimizes heap allocations through several techniques:

ReadOnlyMemory<char> Content

Token content references the original source string without copying:

public abstract record Token(ReadOnlyMemory<char> Content, TokenType Type, long Position);

// Access spans for processing without allocation
ReadOnlySpan<char> span = token.ContentSpan;

SimpleToken as Struct

Level 1 tokens are value types to avoid heap allocations during lexing:

public readonly record struct SimpleToken(
    SimpleTokenType Type,
    ReadOnlyMemory<char> Content,
    int Position);

ArrayPoolBufferWriter

The parser uses pooled buffers from CommunityToolkit.HighPerformance:

using var contentBuilder = new ArrayPoolBufferWriter<char>();
// Build token content without allocating new arrays

Operator Matching with OperatorTrie

Multi-character operators are matched using a trie data structure for O(k) lookup where k is operator length:

// Configured operators: ==, ===, =>, =
// Input: "==="

// Trie performs greedy matching:
// 1. Match '=' → found "="
// 2. Match '=' → found "=="
// 3. Match '=' → found "===" ← longest match wins

This ensures operators like === are matched before == without backtracking.

Red-Green Syntax Trees

TinyAst uses the red-green tree pattern (similar to Roslyn):

Green Nodes (Internal)

• Immutable — Never modified after creation
• Shared — Identical subtrees share the same green node instance
• Position-agnostic — Don't store absolute positions
• Cached — GreenNodeCache interns common patterns

Red Nodes (Public API)

• Navigable — Have parent references
• Position-aware — Know their absolute position in source
• Lazy — Created on-demand as you traverse
• Cheap to create — Thin wrappers around green nodes

// Red nodes are what you work with
SyntaxNode root = tree.Root;
SyntaxNode parent = node.Parent;
int position = node.Position;

// Green nodes are implementation details
// (not directly exposed in public API)

Benefits

1. Memory efficient — Shared green nodes for repeated patterns
2. Fast edits — Only rebuild affected subtree paths
3. Undo/redo — Simply swap the root green node
4. Thread-safe — Immutable green layer is safe to share

SIMD Optimization

The lexer uses SearchValues<char> for vectorized character classification:

// Pre-built character sets
private static readonly SearchValues<char> SingleCharTokens =
    SearchValues.Create("{}[]()'\"\\/.*#@=+-<>|&%^~?!:,;");

// Vectorized contains check (uses SIMD when available)
if (SingleCharTokens.Contains(c))
{
    // Fast path for known token characters
}

This provides significant speedup when processing large files on modern CPUs with SIMD support.

See Also

• Token Types — SimpleToken vs Token types
• Configuration — TokenizerOptions and operator configuration
• TinyAst Guide — Working with syntax trees