Structural edit distance

English · 简体中文

Structure-aware matching of historical code edits with MCU and LCS.

This library compares two historical code edits by combining:

• LCS token alignment to establish a stable correspondence between code fragments;
• edit-center distance measured in the aligned token space;
• MCU distance measured by breadth-first expansion through syntax-tree parents;
• leaf overlap between compatible syntax nodes; and
• optional edit-content similarity checks.

The package also provides a compact local-Git API for commit hunk comparison. Compare normalized Edit objects directly, or select two commits and two hunks from the same repository to build Python AST/MCU features automatically.

Algorithm at a glance

Edit A + Edit B
      │
      ├── LCS token alignment ──▶ token/node correspondence
      │                              │
      ├── aligned edit centers ──────┴──▶ central distance filter
      │
      └── MCU nodes ── BFS over AST parents ──▶ structural distance
                                  │
                                  └── leaf overlap score
                                                   │
                                                   ▼
                                           MatchResult

The result is not a conventional character-level Levenshtein distance. A match requires sufficiently similar token sequences and compatible syntax-tree structure. The structural distance is returned as (distance_a, distance_b), where each component is the number of parent steps expanded from one edit's MCU.

Installation

git clone git@github.com:AWGiaGia/structural-edit-distance.git
cd structural-edit-distance
python -m pip install .

The library itself uses only the Python standard library. Install pytest to run the test suite:

python -m pip install pytest
pytest

Python API

from structural_edit_distance import Edit, TreeNode, compare_edits

function_a = TreeNode("function", [TreeNode("statement")])
function_b = TreeNode("function", [TreeNode("statement")])

edit_a = Edit(
    tokens=["return", "x"],
    token_nodes=[function_a.children[0], function_a.children[0]],
    edited_token_indices=[0],
    before_tokens=["return", "x"],
    after_tokens=["return", "y"],
    mcu_node=function_a,
)
edit_b = Edit(
    tokens=["return", "y"],
    token_nodes=[function_b.children[0], function_b.children[0]],
    edited_token_indices=[0],
    before_tokens=["return", "y"],
    after_tokens=["return", "z"],
    mcu_node=function_b,
)

result = compare_edits(edit_a, edit_b)
print(result.is_match)
print(result.as_dict())

Edit.tokens and Edit.token_nodes must have equal lengths. edited_token_indices identifies the changed region in the MCU token sequence. If mcu_node is omitted, it is inferred as the lowest common ancestor of the edited token nodes.

Historical edit relation classifier

classify_edit_relation explains how two edits are related after structural matching. The first argument is the target/later edit and the second is the reference/earlier edit. It aligns each edit's before_tokens and after_tokens with LCS, then checks directional evolution, reused additions, contained content, static context, and optional assignment-identifier metadata.

from structural_edit_distance import Edit, TreeNode, classify_edit_relation


def make_edit(before, after):
    statement = TreeNode("statement")
    function = TreeNode("function", [statement])
    return Edit(
        tokens=before,
        token_nodes=[statement for _ in before],
        edited_token_indices=[1],
        before_tokens=before,
        after_tokens=after,
        mcu_node=function,
    )


target = make_edit(
    ["call", "legacy_api", "value"],
    ["call", "new_api", "value"],
)
reference = make_edit(
    ["call", "old_api", "value"],
    ["call", "legacy_api", "value"],
)

relation = classify_edit_relation(target, reference)
print(relation.as_dict())

Output:

{
  "label": "subsequent_edit",
  "score": 1.0,
  "rule": "deleted_a_matches_added_b",
  "evidence": {
    "edit_a": {"deleted": ["legacy_api"], "added": ["new_api"], "static": ["call", "value"]},
    "edit_b": {"deleted": ["old_api"], "added": ["legacy_api"], "static": ["call", "value"]},
    "overlap": {"lcs_length": 1, "dice": 1.0, "left_coverage": 1.0, "right_coverage": 1.0, "left_length": 1, "right_length": 1}
  }
}

Available labels include subsequent_edit, similar_content_addition, added_content_subset, added_content_superset, similar_static_context, similar_added_identifiers, similar_deleted_identifiers, deleted_identifier_matches_static, and no_relation. The returned evidence makes each decision auditable. The standalone script is examples/classify_edit_relation.py.

Real repository example: compare two commit hunks

The following workflow compares hunk 0 from two historical commits in the same local repository. Each commit is diffed against its first parent.

First, inspect the available hunks and their indices:

sed-match list-hunks --repo /path/to/repository --commit <commit-a>
sed-match list-hunks --repo /path/to/repository --commit <commit-b>

Then compare the selected pair:

sed-match compare-hunks \
  --repo /path/to/repository \
  --commit-a <commit-a> --hunk-a 0 \
  --commit-b <commit-b> --hunk-b 0

Example output from a real three-commit Python repository:

$ sed-match list-hunks --repo ./demo-repo --commit 8f4bcf49e2790e750f92413d3ef8b4a755f84e6e
[
  {
    "index": 0,
    "path": "calculator.py",
    "old_start": 1,
    "old_count": 3,
    "new_start": 1,
    "new_count": 3,
    "header": "",
    "edit_type": "modify",
    "before_text": "    adjusted = value + 1\n",
    "after_text": "    adjusted = value + 2\n",
    "commit": "8f4bcf49e2790e750f92413d3ef8b4a755f84e6e"
  }
]

$ sed-match compare-hunks --repo ./demo-repo \
    --commit-a 8f4bcf49e2790e750f92413d3ef8b4a755f84e6e --hunk-a 0 \
    --commit-b 3e6635c01f05150a6ad563cfe38ef722815bfd29 --hunk-b 0
{
  "is_match": true,
  "structural_distance": [
    0,
    0
  ],
  "leaf_score": 0.8,
  "central_distance": 0,
  "lcs_match": [
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12],
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12]
  ],
  "reason": "matched",
  "semantic_relation": "similar_static_context",
  "semantic_evidence": {
    "label": "similar_static_context",
    "score": 1.0,
    "rule": "static_token_overlap",
    "evidence": {
      "edit_a": {"deleted": ["1"], "added": ["2"], "static": ["adjusted", "=", "value", "+"]},
      "edit_b": {"deleted": ["2"], "added": ["3"], "static": ["adjusted", "=", "value", "+"]}
    }
  }
}

The two commits change the same expression inside normalize; the matcher therefore finds the same structural unit, zero center distance, and a successful match.

The same operation is available through Python:

from structural_edit_distance import compare_commit_hunks, extract_commit_hunks

repo = "/path/to/repository"
commit_a = "<commit-a>"
commit_b = "<commit-b>"

# A commit can contain multiple file hunks. Inspect these lists before choosing
# the two indices you want to compare.
hunks_a = extract_commit_hunks(repo, commit_a)
hunks_b = extract_commit_hunks(repo, commit_b)

for index, hunk in enumerate(hunks_a):
    print("A", index, hunk.path, hunk.header, hunk.before_text, hunk.after_text)
for index, hunk in enumerate(hunks_b):
    print("B", index, hunk.path, hunk.header, hunk.before_text, hunk.after_text)

result = compare_commit_hunks(
    repo,
    commit_a,
    0,  # hunk index in commit A
    commit_b,
    0,  # hunk index in commit B
)
print(result.is_match)
print(result.as_dict())

An executable version is provided in examples/compare_commit_hunks.py:

python examples/compare_commit_hunks.py \
  /path/to/repository <commit-a> <commit-b> \
  --hunk-a 0 --hunk-b 0

What the repository pipeline extracts

For each selected commit, the package:

1. resolves the commit and its first parent;
2. runs a local unified Git diff and parses file paths, hunk headers, old/new line ranges, context, deleted lines, and added lines;
3. reads the corresponding pre-commit file (or the post-commit file for a pure addition);
4. parses Python source with the standard-library ast and tokenize modules;
5. selects the smallest enclosing function, async function, or class as the code unit;
6. marks tokens on the changed lines and computes their lowest common ancestor as the MCU; and
7. sends both Edit objects to compare_edits.

The local repository must already contain both commits. Python hunk extraction uses the standard-library AST and tokenizer. Integrate another parser by constructing normalized Edit and TreeNode objects. Merge commits are compared with their first parent, and root commits are compared with Git's empty tree.

Result schema

compare_edits returns a MatchResult with:

Field	Meaning
is_match	Whether all enabled structural checks pass
structural_distance	(distance_a, distance_b) parent-expansion steps, or null
leaf_score	Dice-style overlap of mapped MCU leaves
central_distance	Distance between edit centers in LCS space
lcs_match	Two lists of aligned token indices
reason	Human-readable acceptance/rejection reason
semantic_relation	Optional content relation, such as subsequent editing
semantic_evidence	Relation label, score, rule, and token-level evidence

Parameters

compare_edits(
    edit_a,
    edit_b,
    threshold=0.7,
    max_central_distance=100,
    max_path_distance=40,
    min_lcs_ratio=0.4,
    semantic_check=False,
    relation_threshold=0.9,
)

• threshold: minimum MCU leaf-overlap score;
• max_central_distance: maximum edit-center separation after LCS alignment;
• max_path_distance: maximum sum of parent expansions explored by BFS;
• min_lcs_ratio: minimum normalized LCS ratio, 2 * LCS / (len(A) + len(B));
• semantic_check: additionally require a recognized edit-content relation.
• relation_threshold: minimum LCS/coverage score used by the historical relation classifier.

Adapting Tree-sitter nodes

Python hunk extraction uses the standard-library AST. To integrate another language with Tree-sitter, construct a TreeNode for each syntax node, set its type, recursively attach children, and use the corresponding leaf TreeNode for each token in Edit.token_nodes.

CLI

sed-match provides three subcommands:

sed-match json <input.json>
sed-match list-hunks --repo <repo> --commit <commit>
sed-match compare-hunks --repo <repo> --commit-a <sha> --hunk-a <n> --commit-b <sha> --hunk-b <n>

json accepts normalized edit_a and edit_b token arrays. The two repository commands extract real commit hunks and Python syntax trees.

License

This project is licensed under the MIT License.