Patitas — A Markdown Parser Built for Parallel Parsing

How Patitas achieves lock-free parallel Markdown parsing with immutable AST, ContextVar config, and an O(n) ReDoS-proof lexer — 6.6x speedup on 8 cores.

4 min read
patitas

Patitas is built around two claims: Markdown parsing should be safe on untrusted input, and it should scale across cores on free-threaded Python.

Most Markdown parsers quietly compromise one of those. They either lean on regex-heavy parsing that can backtrack badly, or they make concurrency an afterthought.

The regex problem is not theoretical. Submit a carefully crafted string that causes the engine to backtrack exponentially, and a parser can stall long enough to become a denial-of-service vector.

Patitas doesn't use regex in the hot path. It uses a hand-written finite state machine. Single-character lookahead. No backtracking. Processing time is linear in input length, guaranteed. Malicious Markdown is just slow Markdown — not a vulnerability.

That's one problem. The other is concurrency.

Series context

Part 3 of 6 — Free-Threading in the Bengal Ecosystem. Patitas is the Markdown layer — used by Bengal for content parsing.

Run it

uv python install 3.14t
uv run --python=3.14t python -c "
from concurrent.futures import ThreadPoolExecutor
from patitas import parse

docs = ['# Doc ' + str(i) for i in range(1000)]
with ThreadPoolExecutor(max_workers=8) as ex:
    results = list(ex.map(parse, docs))
print(f'Parsed {len(results)} documents in parallel')
"

No special API. No "parallel parser" mode. Just executor.map(parse, docs).

Performance

List table has no rows

The scaling is the headline. The reason it happens is the architecture underneath it: immutable AST, ContextVar for config, and single-use lexer and parser instances. No shared mutable state between parses.

The O(n) lexer

The first piece is the lexer. Its goal is simple: always move forward.

"""State-machine lexer with O(n) guaranteed performance.

Uses a window-based approach:
1. Scan to end of line (find window)
2. Classify the line (pure logic, no position changes)
3. Commit position (always advances)

No regex in the hot path. Zero ReDoS vulnerability by construction.
"""

Single-character lookahead. No backtracking. That makes it safe for untrusted input in web apps, APIs, and CI pipelines that process user-submitted docs.

Immutable AST

All AST nodes are frozen dataclasses with tuple children:

@dataclass(frozen=True, slots=True)
class Heading(Node):
    level: int
    children: tuple[Inline, ...]

@dataclass(frozen=True, slots=True)
class Strong(Node):
    children: tuple[Inline, ...]

tuple over list means no appending and no reordering after construction. Combined with frozen=True, AST nodes are hashable, comparable via ==, and safe to pass between threads without copying.

That is the concurrency story in one sentence: each parse produces a finished value, not a mutable tree that other code has to tiptoe around.

ContextVar for parse configuration

Parse config such as tables, footnotes, math, and directive registry needs to be available deep in the parser. Storing it on a shared Markdown instance would require locks when multiple threads parse with different configs.

_parse_config: ContextVar[ParseConfig] = ContextVar(
    "parse_config", default=_DEFAULT_CONFIG
)

Thread A can parse with tables enabled while thread B parses with math enabled. They do not interfere, and the caller does not need to think about locking.

Single-use lexer and parser

The lexer and parser still hold mutable state during a parse: position, line number, block stack. Instead of making those objects shareable, Patitas makes them single-use:

# Each parse() call creates fresh instances
parser = Parser(source, source_file=source_file)
blocks = parser.parse()

Create, use, discard. The cost of creating a parser is small compared to the parse itself, and the benefit is zero contention between parses.

Incremental parsing

When a user edits one paragraph in a 100KB document, re-parsing everything is wasteful. parse_incremental() re-parses only the affected region and splices the result back together:

def parse_incremental(
    new_source, previous, edit_start, edit_end, new_length, *,
    source_file=None,
) -> Document:
    first_affected, last_affected = _find_affected_range(
        old_blocks, edit_start, edit_end
    )
    new_blocks = _parse_region(region_source, reparse_start, source_file)
    result_children = (*before, *new_blocks, *adjusted_after)
    return Document(location=loc, children=result_children)

Because the existing AST is immutable, you can slice it, pass parts to other threads, and build a new Document from pieces. That is why small edits can be roughly 200x faster than a full re-parse.

What this means in practice

On free-threaded Python 3.14t, executor.map(parse, docs) scales to ~6.6x on 8 cores. 1,000 documents parsed in parallel with no locks and no special API. The O(n) lexer means you can safely parse untrusted Markdown in web applications without ReDoS risk.

Patitas feeds Bengal for static site rendering. Every code block in every docs site goes through Patitas — and from there, to Rosettes for highlighting.

Further reading