trailofbits / trailofbits/graphtage
Detect moved, split, and merged nodes when diffing
Nobody has claimed this yet.
- 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:
- A move operation for whole nodes, so that relocating a subtree costs less than removing and reinserting it.
--ignore-list-orderalready treats a reordered list as unchanged, but only for whole lists, and it does not report the move. - Split and merge operations for sequence nodes, so that one string becoming several adjacent strings, or the reverse, is a single edit.
- Rendering these in the formatters, and deciding whether they belong in
--only-editsand--edit-digestoutput.
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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