Editscript diffs and patches Clojure data with minimal edits

An edit script, not a diff for humans

Editscript is a library designed to extract the differences between two Clojure or ClojureScript data structures as an editscript, which represents the minimal modification necessary to transform one into the other. The word minimal is doing the work, and the README says so directly when it compares itself to alternatives: Editscript is designed for data diffing, such as data preservation and recovery, not for being looked at by humans. That framing is the most useful thing in the documentation, because it tells you the shape of the output is not the point. The output is a compact, machine-applicable description of a change, and the intended consumer is code that applies it, not code that renders it. The library can diff and patch any nested Clojure or ClojureScript data structures consisting of regular maps, vectors, lists, sets and values, and custom data can also be handled if you implement the library's protocols.

Paths, operations and a patch that inverts the diff

An editscript is a vector of edits, where each edit is a vector of two or three elements. The first element is the path, similar to the path vector used by update-in, but with one important difference: update-in only works for associative data structures, map and vector, whereas the editscript works for map, vector, list and set alike. The second element is a keyword naming the operation, one of :- for deletion, :+ for addition, :r for data replacement or :s for string edit, and for addition and replacement the third element is the new value. The round trip is the property to check, and the library's usage example closes the loop: computing a diff, patching with it, and asserting that the result equals the second value. The path model being update-in-like means the mental model transfers directly to anyone who has used Clojure's core library.

The usage example, end to end

The example in the documentation is compact enough to reproduce. Two nested structures are defined, differing in a string, a number, a vector inside a map and a set:

(require '[editscript.core :as e])

;; Here are two pieces of data, a and b
(def a ["Hello word" 24 22 {:a [1 2 3]} 1 3 #{1 2}])
(def b ["Hello world" 24 23 {:a [2 3]} 1 3 #{1 2 3}])

;; compute the editscript between a and b using the default options
(def d (e/diff a b))

;; look at the editscript
(e/get-edits d)
;;==>
;; [[[0] :r "Hello world"] [[2] :r 23] [[3 :a 0] :-] [[6 3] :+ 3]]

;; diff using the quick algorithm and diff the strings by character
;; there are other string diff levels: :word, :line, or :none (default)
(def d-q (e/diff a b {:algo :quick :str-diff :character}))

(e/get-edits d-q)
;;==>
;; [[[0] :s [9 [:+ "l"] 1]] [[2] :r 23] [[3 :a 0] :-] [[6 3] :+ 3]]

;; get the edit distance, i.e. number of edits
(e/edit-distance d)
;;==> 4

;; get the size of the editscript, i.e. number of nodes
(e/get-size d)
;;==> 23

;; patch a with the editscript to get back b, so that
(= b (e/patch a d))
;;==> true
(= b (e/patch a d-q))
;;==> true

Two details are worth pulling out. The default algorithm replaces the whole string, producing a single :r edit, while the quick algorithm with character-level string diffing produces an :s edit carrying a character-level patch instead. And the library reports two different measures, the edit distance, which is the number of edits, and the size, which is the number of nodes in the script, and the two are not the same thing.

Two algorithms and the trade between size and speed

The library implements two diffing algorithms and the choice is explicit in the options map, with the default producing diffs that are optimal in the number of editing operations and the resulting script size, and a quick algorithm offered as the alternative. The README states the trade plainly: if speed is your primary concern, the quick algorithm of Editscript is the fastest among all the alternatives, and its diff size is reasonably small for the benchmarked data sets. If the diff size is your primary concern, the A* algorithm is the only available option that guarantees optimal data size, but it is also the slowest. There is also a string diff level to choose, with :word, :line and :none as the default. So a caller has three decisions rather than one: which algorithm, which string granularity, and whether the size or the latency matters more for the pipeline the diff is feeding.

Scripts can be stored, sent and reloaded

A useful property of the design is that the editscript has a plain Clojure representation. get-edits returns a plain vector, and that vector can be passed around, stored or modified as usual, and then loaded back as a new editscript with edits->script, and the reloaded script works the same as the original:

;; get the edits as a plain Clojure vector
(def v (e/get-edits d))

v
;;==>
;;[[[0] :r "Hello world"] [[2] :r 23] [[3 :a 0] :-] [[6 3] :+ 3]]

;; the plain Clojure vector can be passed around, stored, or modified as usual,
;; then be loaded back as a new EditScript
(def d' (e/edits->script v))

;; the new EditScript works the same as the old one
(= b (e/patch a d'))
;;==> true

That round trip is what makes the library usable for a synchronisation protocol, because the thing on the wire is ordinary data that any Clojure runtime on the other end can read and turn back into a script. The README points at a Clojure/north 2020 talk on data diffing based software architecture patterns for the wider idea, and the API documentation lives on cljdoc.

Who is using it and how they use it

The library is described as stable and as having been in production use to power the core product of Juji for several years, and the README keeps a list of users, with an invitation to add a line on an issue. Clerk uses it to improve the usability of a synchronised atom by sending a minimal diff from the JVM to the browser, which the README credits with achieving 60fps sync for updates in both directions. Evident Systems uses it as the main way of evaluating changes within the convergent reference type in its CRDT library, Converge. microdata.no uses it to sync client state to the server so users can pick up their work where they left it. Oche uses it to sync game state between client and server, and Streetlinx uses it to capture deltas to drive a newsfeed and generate alerts. The spread is informative: these are all cases where the diff is a transport format rather than a report.

The alternatives, honestly assessed

The README compares four libraries, which is more useful than most projects' competitive sections. deep-diff2 applies the Wu et al. 1990 algorithm by first converting trees into linear structures; it is only faster than the A* algorithm of Editscript, its results are the largest in size, and although it cannot achieve optimal tree diffing it has an interesting use for visualisation, so the recommendation is to use deep-diff2 if you want to visualise the differences. It does not patch. clojure.data/diff and differ are similar to the quick algorithm in that they do a naive walk-through, so their diffs are not optimal. clojure.data/diff is good for detecting what changed and how, but is slow, its results are large, and it does not patch either. differ looks best in the numbers, does patch, and is fast with the smallest results, but it cuts corners and fails all the property based tests, so the advice is to use it only if you understand its failing patterns. The repository contains a /bench folder with a benchmark comparing the alternatives.

Editorial conclusion

Editscript is a good fit for a Clojure team that needs to move state between a JVM and a browser, or to store and recover a data structure, and that cares about the size of the diff on the wire rather than only its speed, because the A* algorithm guarantees an optimal script. It is a poor fit if the diff is going to be read by a human, since the library says plainly that it is designed for data diffing and data preservation rather than for being looked at, and it is a poor fit for a project that has to diff data outside Clojure. Check three things before you adopt it: that your data is built from maps, vectors, lists, sets and ordinary values, or that you are prepared to implement the library's protocols for your own types, since custom data is only handled that way; that patch is the operation you actually need, because the competing libraries the README names mostly do not offer it; and that you pick the algorithm deliberately, since the default gives optimal size and the quick algorithm is the fastest of the alternatives but is not optimal.

Frequently asked questions

Official sources

1. Issues
2. juji-io/editscript on GitHub
3. License: EPL-1.0
4. README