# differ

URL: /patitas/api/differ/
Section: api
Description: 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.

---

> For a complete page index, fetch /patitas/llms.txt.

Open LLM text
(/patitas/api/differ/index.txt)

Share with AI

Ask Claude
(https://claude.ai/new?q=Please%20help%20me%20understand%20this%20documentation%3A%20%2Fpatitas%2Fapi%2Fdiffer%2Findex.txt)

Ask ChatGPT
(https://chatgpt.com/?q=Please%20help%20me%20understand%20this%20documentation%3A%20%2Fpatitas%2Fapi%2Fdiffer%2Findex.txt)

Ask Gemini
(https://gemini.google.com/app?q=Please%20help%20me%20understand%20this%20documentation%3A%20%2Fpatitas%2Fapi%2Fdiffer%2Findex.txt)

Ask Copilot
(https://copilot.microsoft.com/?q=Please%20help%20me%20understand%20this%20documentation%3A%20%2Fpatitas%2Fapi%2Fdiffer%2Findex.txt)

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 (/patitas/api/differ/#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 (/patitas/api/nodes/#Document)`

`new`
`Document (/patitas/api/nodes/#Document)`

`recursive`
`bool`

Default:`False`

##### Returns

`tuple[ASTChange (/patitas/api/differ/#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 (/patitas/api/differ/#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 (/patitas/api/differ/#ASTChange)]`