Module

differ

AST differ — structural diff on Patitas frozen ASTs.

Compares two Patitas Document trees and produces a changeset describing which nodes were added, removed, or modified. Leverages the fact that all Patitas AST nodes are frozen dataclasses (hashable, comparable via ==).

The differ uses a known-schema structural diff (not generic tree edit distance) with fast-path skipping of unchanged subtrees.

Example:

from patitas import parse
from patitas.differ import diff_documents

old_doc = parse("# Hello\nWorld")
new_doc = parse("# Hello\nUpdated world")

changes = diff_documents(old_doc, new_doc)
for change in changes:
    print(f"{change.kind} at {change.path}")

Thread Safety:

diff_documents is a pure function — safe to call from any thread.
1Class4Functions

Classes

ASTChange 5 ▼
A single change between two AST trees.

A single change between two AST trees.

Attributes

Name Type Description
kind Literal['added', 'removed', 'modified']

Type of change — added, removed, or modified.
path tuple[int, ...]

Position in the tree as a tuple of child indices.
old_node object | None

The node before the change (None for additions).
new_node object | None

The node after the change (None for removals).
Example —

(2, 0) means "third child of root, first child of that".

Functions

diff_documents 3 tuple[ASTChange, ...] ▼
Structural diff on two Patitas Document trees. Returns a tuple of ASTChange ob…
def diff_documents(old: Document, new: Document, *, recursive: bool = False) -> tuple[ASTChange, ...]

Structural diff on two Patitas Document trees.

Returns a tuple of ASTChange objects describing the differences. Unchanged subtrees are skipped in O(1) via==on frozen nodes.

Algorithm:

1. Walk both trees in parallel by child index (positional comparison).
2. For each position, compare nodes via ``==``.
3. If equal, skip the subtree (fast path — frozen nodes).
4. If different types, emit removed + added.
5. If same type but different content, emit modified.
6. Handle length mismatches (trailing adds/removes).

This is NOT a generic tree edit distance (which is NP-hard). It's a positional diff on a known schema where children are ordered tuples, not arbitrary sets.

Parameters
Name Type Description
old Document
new Document
recursive bool Default:False
Returns
tuple[ASTChange, ...]
_diff_children 5 None ▼
Recursively diff ordered child tuples. Walks both tuples by index. For positio…
def _diff_children(old_children: tuple[Block, ...], new_children: tuple[Block, ...], parent_path: tuple[int, ...], changes: list[ASTChange], *, recursive: bool) -> None

Recursively diff ordered child tuples.

Walks both tuples by index. For positions beyond one tuple's length, emits additions or removals as appropriate.

Parameters
Name Type Description
old_children tuple[Block, ...]
new_children tuple[Block, ...]
parent_path tuple[int, ...]
changes list[ASTChange]
recursive bool
_child_blocks 1 tuple[Block, ...] ▼
Extract direct child blocks for supported container nodes.
def _child_blocks(node: Block) -> tuple[Block, ...]
Parameters
Name Type Description
node Block
Returns
tuple[Block, ...]
_diff_nested 4 None ▼
Recursively diff nested block children for finer-grained invalidation.
def _diff_nested(old_node: Block, new_node: Block, parent_path: tuple[int, ...], changes: list[ASTChange]) -> None
Parameters
Name Type Description
old_node Block
new_node Block
parent_path tuple[int, ...]
changes list[ASTChange]