Diffing and merging notebooks — Jupyter Enhancement Proposals (2024)

Basic use cases of notebook diff#

• View difference between two versions of a file:nbdiff base.ipynb remote.ipynb

• Store difference between two versions of a file to a patch filenbdiff base.ipynb remote.ipynb patch.json

• Compute diff of notebooks for use in a regression test framework:

 import nbdime di = nbdime.diff_notebooks(a, b) assert not di

• View difference of output cells after re-executing notebook

Variations will be added on demand with arguments to the nbdiff command, e.g.:

• View diff of sources only

• View diff of output cells (basic text diff of output cells, image diff with external tool)

Basic use cases of notebook merge#

The main use case for the merge tool will be a git-compatible commandline merge tool:

 nbmerge base.ipynb local.ipynb remote.ipynb merged.ipynb

which can be called from git and launch a console tool or web gui for conflict resolution if needed.Ideally the web gui can reuse as much as possible from Jupyter Notebook.

Goals:

• Trouble free automatic merge when no merge conflicts occur

• Optional behaviour to drop conflicting output, execution counts, and eventual other secondary data

• Easy to use interactive conflict resolution

Notes on initial implementation#

• An initial version of diff gui can simply show e.g. two differingimages side by side, but later versions should do something moreclever.

• An initial version of merge can simply join or optionally deleteconflicting output.

• An initial version of conflict resolution can be to output anotebook with conflicts marked within cells, to be manually editedas a regular jupyter notebook.

Diff format for mappings#

For mappings, the key is always a string. Valid ops are:

• { "op": "remove", "key": <string> }: delete existing value at key

• { "op": "add", "key": <string>, "value": <value> }: insert new value at key not previously existing

• { "op": "replace", "key": <string>, "value": <value> }: replace existing value at key with new value

• { "op": "patch", "key": <string>, "diff": <diffobject> }: patch existing value at key with another diffobject

Diff format for sequences (list and string)#

For sequences the key is always an integer index. This index isrelative to object A of length N. Valid ops are:

• { "op": "removerange", "key": <string>, "length": <n>}: delete the values A[key:key+length]

• { "op": "addrange", "key": <string>, "valuelist": <values> }: insert new items from valuelist before A[key], at end if key=len(A)

• { "op": "patch", "key": <string>, "diff": <diffobject> }: patch existing value at key with another diffobject

Relation to JSONPatch#

The above described diff representation has similarities with theJSONPatch standard but is different in some significant ways:

• JSONPatch contains operations “move”, “copy”, “test” not used bynbdime, and nbdime contains operations “addrange”, “removerange”, and“patch” not in JSONPatch.

• Instead of providing a recursive “patch” op, JSONPatch uses a deepJSON pointer based “path” item in each operation instead of the “key”item nbdime uses. This way JSONPatch can represent the diff object asa single list instead of the ‘tree’ of lists that nbdime uses. Theadvantage of the recursive approach is that e.g. all changes to a cellare grouped and do not need to be collected.

• JSONPatch uses indices that relate to the intermediate (partiallypatched) object, meaning transformation number n cannot be interpretedwithout going through the transformations up to n-1. In nbdime theindices relate to the base object, which means ‘delete cell 7’ meansdeleting cell 7 of the base notebook independently of the previoustransformations in the diff.

A conversion function can fairly easily be implemented.

Handling nested structures by alignment and recursion#

The diff of objects A and B is computed recursively, handling dictsand lists with different algorithms.

Diff approach for dicts#

When computing the diff of two dicts, items are always aligned by keyvalue, i.e. under no circ*mstances are values under different keyscompared or diffed. This makes both diff and merge quitestraightforward. Modified leaf values that are both a list or both adict will be diffed recursively, with the diff object recording a“patch” operation. Any other modified leaf values are consideredreplaced.

Diff approach for lists#

We wish to diff sequences and also recurse and diff aligned elementswithin the sequences. The core approach is to first align elements,requiring some heuristic for comparing elements, and then recursivelydiff the elements that are determined equal. These heuristics willcontain the bulk of the notebook-specific diff algorithmcustomizations.

The most used approach for computing linebased diffs of source code isto solve the longest common subsequence (lcs) problem or somevariation of it. We extend the vanilla LCS problem by allowingcustomizable predicates for approximate equality of two items,allowing e.g. a source cell predicate to determine that two pieces ofsource code are approximately equal and should be considered the samecell, or an output cell predicate to determine that two bitmap imagesare almost equal.

In addition we have an experimental multilevel algorithm that employsa basic LCS algorithm with a sequence of increasingly relaxed equalitypredicates, allowing e.g. prioritizing equality of source+output overjust equality of source. Note that determining good heuristics andrefining the above mentioned algorithms will be a significant part ofthe work and some experimentation must be allowed. In particular thebehaviour of the multilevel approach must be investigated further andother approaches could be considered..

Displaying metadata diffs#

The notebook format has metadata in various locations,including on each cell, output, and top-level on the notebook.These are dictionaries with potentially arbitrary JSON content.Computing metadata diffs is not different from any other dictionary diff.However, metadata generally does not have a visual representation in the live notebook,but it must be indicated in the diff view if there are changes.We will explore various represenentations of metadata changes in the notebook view.The most primitive would be to display the raw dictionary diff as a JSON field in the notebook view,near the displayable item the metadata is associated with.

Note about the potential addition of a “move” transformation#

In the current implementation there is no “move” operation.Furthermore we make some assumptions on the structure of the jsonobjects and what kind of transformations are meaningful in a diff.

Items swapping position in a list will be considered added and removedinstead of moved, but in a future iteration adding a “move” operationis an option to be considered. The main use case for this would be toresolve merges without conflicts when cells in a notebook arereordered on one side and modified on the other side.

Even if we add the move operation, values will never be moved betweenkeys in a dict, e.g.:

diff({"a":"x", "b":"y"}, {"a":"y", "b":"x"})

will be:

[{"op": "replace", "key": "a", "value": "y"}, {"op": "replace", "key": "b", "value": "x"}]

In a notebook context this means for example that data will never beconsidered to move across input cells and output cells.