trailofbits / trailofbits/graphtage

Detect moved, split, and merged nodes when diffing

Open
#184 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
Python
Stars
2.5k
Forks
61
Avg merge
6h 45m
Merged PRs (30d)
45

Description

Graphtage's edit model has four operations: match, insert, remove, and replace (graphtage/edits.py). None of them relocates a node. Moving a value from one part of a tree to another therefore costs a remove plus an insert, and splitting one string across several nodes costs a remove of the original plus an insert of every fragment. The resulting edit script is correct, but it is larger than the change it describes, and it does not read the way a person would describe what happened.

Splitting this out of #46, which asked for it while diffing rich-text documents from a Slate editor. In that model a paragraph is a list of {"text": ...} nodes, so applying bold to a word in the middle of a run splits one text node into three:

// before
{"type": "p", "children": [
  {"text": "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin "},
  {"text": "efficitur", "bold": true},
  {"text": " sit amet sem a feugiat. Sed finibus eleifend elit a ultrices. Curabitur ac massa at mauris mollis varius."}
]}

// after
{"type": "p", "children": [
  {"text": "Lorem ipsum dolor sit "},
  {"text": "amet", "bold": true},
  {"text": ", consectetur Hello World adipiscing elit. Proin "},
  {"text": "efficitur", "bold": true},
  {"text": " sit amet sem. Sed finibus "},
  {"text": "eleifend", "underline": true},
  {"text": " elit a ultrices. Curabitur ac massa at mauris mollis varius."}
]}

The change is one split, one added bold, one inserted phrase, one more split, and one added underline. Here is what Graphtage 0.4.0 reports:

$ graphtage --no-status before.json after.json
[
    {
        "children": [
            ++{
                "text": "Lorem ipsum dolor sit "
            }++,
            ++{
                "bold": true,
                "text": "amet"
            }++,
            {
                "text": "~~Lorem~~++,++ ~~ipsum dolo~~++consectetu++r~~ sit~~ ~~am~~++H++e~~t, c~~++ll++o~~nsectetur~~++ World++ adipiscing elit. Proin "
            },
            ...

Because no edit expresses "this node was split," the matcher pairs the original first text node against the third node of the new document and falls back to a character-level Levenshtein diff between two strings that share almost nothing. The output is accurate about the bytes and useless as a description of the change.

Scope, roughly in order of cost:

  1. A move operation for whole nodes, so that relocating a subtree costs less than removing and reinserting it. --ignore-list-order already treats a reordered list as unchanged, but only for whole lists, and it does not report the move.
  2. Split and merge operations for sequence nodes, so that one string becoming several adjacent strings, or the reverse, is a single edit.
  3. Rendering these in the formatters, and deciding whether they belong in --only-edits and --edit-digest output.

This is not a small change. Optimal tree edit distance with moves is NP-hard, so any implementation is a heuristic, and the cost model in graphtage/bounds.py and graphtage/search.py assumes edits are independent, which moves and splits are not. Treat this as a research item rather than a scheduled feature.

Filed to track the part of #46 that remains after the non-terminating diff reported there was fixed. cc @Hideman85

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the edit operations in graphtage/edits.py, then inspect the cost and search assumptions in graphtage/bounds.py and graphtage/search.py. Review --ignore-list-order and the formatters to define how move, split, and merge edits should be represented, rendered, and handled by --only-edits and --edit-digest; done requires a documented heuristic and consistent output.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
tooling
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.