Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Diffing and merging notebooks

Problem

Diffing and merging notebooks is not properly handled by standard linebased diff and merge tools.

Proposed Enhancement

Detailed Explanation

Preliminary work resides in nbdime.

Fundamentally, we envision use cases mainly in the categories of a merge command for version control integration, and diff command for inspecting changes and automated regression testing. At the core of it all is the diff algorithms, which must handle not only text in source cells but also a number of data formats based on mime types in output cells.

Cell source is usually the primary content, and output can presumably be regenerated. In general it is not possible to guarantee that merged sources and merged output is consistent or makes any kind of sense. For many use cases options to silently drop output instead of requiring conflict resolution will produce a smoother workflow. However such data loss should only happen when explicitly requested.

Basic use cases of notebook diff

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

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

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:

Notes on initial implementation

Diff format

The diff object represents the difference between two objects A and B as a list of operations (ops) to apply to A to obtain B. Each operation is represented as a dict with at least two items:

{ "op": <opname>, "key": <key> }

The objects A and B are either mappings (dicts) or sequences (lists), and a different set of ops are legal for mappings and sequences. Depending on the op, the operation dict usually contains an additional argument, documented below.

Diff format for mappings

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

Diff format for sequences (list and string)

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

Relation to JSONPatch

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

A conversion function can fairly easily be implemented.

High level diff algorithm approach

The package will contain both generic and notebook-specific variants of diff algorithms.

The generic diff algorithms will handle most json-compatible objects:

The generic variants will by extension produce correct diffs for notebooks, but the notebook-specific variants aim to produce more meaningful diffs. “Meaningful” is a subjective concept and the algorithm descriptions below are therefore fairly high-level with many details left up to the implementation.

Handling nested structures by alignment and recursion

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

Diff approach for dicts

When computing the diff of two dicts, items are always aligned by key value, i.e. under no circumstances are values under different keys compared or diffed. This makes both diff and merge quite straightforward. Modified leaf values that are both a list or both a dict will be diffed recursively, with the diff object recording a “patch” operation. Any other modified leaf values are considered replaced.

Diff approach for lists

We wish to diff sequences and also recurse and diff aligned elements within the sequences. The core approach is to first align elements, requiring some heuristic for comparing elements, and then recursively diff the elements that are determined equal. These heuristics will contain the bulk of the notebook-specific diff algorithm customizations.

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

In addition we have an experimental multilevel algorithm that employs a basic LCS algorithm with a sequence of increasingly relaxed equality predicates, allowing e.g. prioritizing equality of source+output over just equality of source. Note that determining good heuristics and refining the above mentioned algorithms will be a significant part of the work and some experimentation must be allowed. In particular the behaviour of the multilevel approach must be investigated further and other 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 json objects and what kind of transformations are meaningful in a diff.

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

Even if we add the move operation, values will never be moved between keys 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 be considered to move across input cells and output cells.

Merge format

A merge takes as input a base object (notebook) and local and remote objects (notebooks) that are modified versions of base. The merge computes the diffs base->local and base->remote and tries to apply all changes from each diff to base. The merge returns a merged object (notebook) contains all successfully applied changes from both sides, and two diff objects merged->local and merged->remote which contain the remaining conflicting changes that need manual resolution.

Pros and Cons

Pros associated with this implementation include:

Cons associated with this implementation include:

Interested Contributors

@martinal @minrk

Information
Jupyter Enhancement Proposals (JEP) Guidelines
JEPs
Jupyter Kernel Gateway Incorporation