DEV Community: Dima Novikov

Why datadiff matches arrays by key instead of computing tree edit distance

Dima Novikov — Sat, 19 Sep 2026 12:39:14 +0000

I wrote datadiff to compare structured data (JSON, YAML, CSV, TOML, XML) based on parsed values rather than line differences. Two files are parsed into a single internal tree representation, and the tool prints the differences as property paths—for example, spec.replicas: 3 → 5.

The main architectural decision was made upfront: I intentionally did not implement an optimal tree edit distance algorithm.

The idea came from a Hacker News discussion about Graphtage, Trail of Bits' semantic diff tool. Graphtage finds the minimal edit script between two trees, which is the mathematically correct way to describe what changed. However, most comments in that thread focused on execution time: diffing two Kubernetes pods took several minutes, and a 45 KB CSV was projected to take days. Computing tree edit distance is computationally heavy, and for configuration files, the precision rarely justifies the runtime.

The cost of tree edit distance

Handling objects in a structured diff is straightforward because keys provide identity. Arrays are different: elements have no inherent keys, so the algorithm has to determine which old element corresponds to which new one. An optimal diff evaluates potential pairings to find the sequence of edits with the lowest total cost. This allows it to detect when an element has simply moved rather than being deleted and recreated elsewhere, but it also causes runtime to scale poorly.

To see the practical impact, I ran a benchmark on an Apple M4 comparing Graphtage 0.5.0 with datadiff 0.4.1. The input files contained JSON arrays of objects with seven fields (including one nested object), where the updated file had its rows shuffled and 1% of the email fields modified:

objects	file size	datadiff `--key id`	Graphtage
100	14 KB	0.005 s	1.76 s
250	36 KB	0.005 s	9.38 s
500	73 KB	0.005 s	38.1 s
1,000	146 KB	0.010 s	timeout (>120 s)
10,000	1.5 MB	0.076 s	skipped
100,000	15 MB	0.46 s	skipped

Graphtage scales at roughly O(n²) or worse on this input. To be clear, the comparison is asymmetric: Graphtage solves the general problem without knowing how to identify items, whereas datadiff relies on being told that id is the primary key. In practice, however, config files almost always contain natural identifiers—such as container names, user IDs, or table primary keys.

How datadiff handles matching

The internal value representation is standard:

pub enum Value {
    Null,
    Bool(bool),
    Number(Number),
    String(String),
    Array(Vec<Value>),
    Object(BTreeMap<String, Value>),
}

Using BTreeMap for objects normalizes key ordering during parsing. Two objects with identical fields in different orders produce identical maps, so reformatting never triggers a diff. It also guarantees deterministic iteration order, which is convenient when using the tool as a git textconv driver.

Objects are compared by iterating over both maps. Arrays are compared positionally by default, unless the user provides a --key argument. When a key is specified, datadiff constructs an index map for each array:

fn key_map(arr: &[Value], key: &str) -> Option<BTreeMap<String, usize>> {
    let mut map = BTreeMap::new();
    for (i, item) in arr.iter().enumerate() {
        let Value::Object(obj) = item else {
            return None;
        };
        let kv = obj.get(key)?;
        let text = scalar_key_text(kv)?;
        if map.insert(text, i).is_some() {
            return None; // duplicate key value
        }
    }
    Some(map)
}

If any element is not an object, is missing the specified key, or has a non-scalar key value, or if two elements share a key value, the function returns None and the tool falls back to positional index matching. This fallback behavior is deliberate: --key name applies globally across the entire document, even though many nested arrays are simple string lists that lack a name field.

When both maps build successfully, matching elements is a direct lookup. Matching objects are diffed recursively, missing items are reported as insertions or deletions, and the key is incorporated into the output path: containers[name=api].image instead of containers[1].image. The total time complexity is O(n log n) due to map construction.

The limitation of this approach is obvious: without --key, reordered arrays produce positional diffs. datadiff will not detect moved items unless explicitly told how to identify them, and it never reports renames. For source code analysis, this would be insufficient; for configuration management, it avoids unbounded execution times.

Number equality and CSV edge cases

In a configuration diff, 1 and 1.0 should compare equal, but serde parses them into distinct internal types. datadiff handles equality across representations explicitly:

pub fn numbers_eq(a: &Number, b: &Number) -> bool {
    match (a, b) {
        (Number::Int(x), Number::Int(y)) => x == y,
        (Number::UInt(x), Number::UInt(y)) => x == y,
        (Number::Int(x), Number::UInt(y)) => *x >= 0 && *x as u64 == *y,
        (Number::UInt(x), Number::Int(y)) => *y >= 0 && *x == *y as u64,
        _ => a.as_f64() == b.as_f64(),
    }
}

CSV files introduced additional edge cases because they have no schema or types. My initial implementation attempted to parse fields as i64, then f64, and fell back to raw strings. This failed in three distinct ways:

"00544".parse::<i64>() parses to 544, masking changes where leading zeros were stripped (such as postal codes).
f64::from_str accepts "nan", "inf", and "infinity" case-insensitively. A string value "Nan" parsed as NaN, and since NaN != NaN, an unchanged row produced a false diff.
20-digit identifiers overflow i64, parse as f64, lose lower-order bits, and compare equal to different numeric values.

To resolve this, strings are only converted to numbers if the conversion does not alter the underlying text:

fn is_plain_number(s: &str) -> bool {
    let numeric_chars = s
        .bytes()
        .all(|b| b.is_ascii_digit() || matches!(b, b'+' | b'-' | b'.' | b'e' | b'E'));
    let unsigned = s.trim_start_matches(['+', '-']).as_bytes();
    let leading_zero = unsigned.len() > 1 && unsigned[0] == b'0' && unsigned[1].is_ascii_digit();
    numeric_chars && !leading_zero
}

Values with leading zeros, words such as nan or inf, and integers too long for i64 now remain strings, while 100 and 100.0 still compare equal.

A macOS test race condition

During integration testing, test cases generated temporary directories named using std::process::id() and SystemTime::now() nanoseconds. After I added a test that calls this helper in a loop, tests occasionally failed because one test read fixture files written by another test running in parallel in the same process.

On macOS, SystemTime updates at microsecond resolution rather than nanoseconds. Concurrent tests started at roughly the same time were generating identical paths and overwriting each other's test fixtures. Appending an AtomicUsize counter to the directory names resolved the collision.

What the tradeoff bought

Matching arrays by key is a weaker guarantee than an optimal edit script.
datadiff cannot tell you that an element moved unless the key says so, and it
has to be told which field the key is. What it gets back is the case
configuration files actually hit: a 15 MB file diffed in half a second instead
of not finishing at all.

The code is at github.com/dimanovikov/datadiff
under MIT / Apache-2.0, and the benchmark above is
bench/compare_graphtage.py
in the same repository.

Teaching git diff to read JSON and YAML

Dima Novikov — Fri, 11 Sep 2026 13:25:01 +0000

A formatter reordered the keys in a Kubernetes manifest and git diff lit up
six lines. One of them changed the replica count. I only noticed after the
deploy.

That is not a git bug. A line diff compares lines, and in structured data the
line is the wrong unit: move a key two lines up and nothing changed, but every
line did. So you learn to read config diffs slowly, which means sometimes you
read them fast.

I wrote a tool for this, and the part worth writing about is not the diffing.
It is getting it inside git diff, because git has two extension points for
this and they behave differently in ways the docs do not spell out.

The two hooks

Git lets you replace a diff in two places.

An external diff driver takes over entirely. Git hands your program both
versions and prints nothing of its own. You own the output.

git config diff.datadiff.command "datadiff git-diff"

A textconv filter is narrower. Your program converts each version to text,
and git line-diffs the two outputs as usual.

git config diff.datadiff.textconv "datadiff normalize"

Then point file types at the driver:

echo '*.yaml diff=datadiff' >> .gitattributes

The surprise is that these cover different commands. I expected the external
driver to apply everywhere. It does not.

Command	What runs
`git diff`	external driver
`git log -p`	textconv
`git show`	textconv
`git blame`	textconv

Git only calls an external driver for git diff. History commands fall back to
a line diff, and textconv is your only way in there. Which turns out to be the
right split anyway: when I ask "what did I just change" I want data paths, and
when I read history I want a normal diff, just without the noise.

So git diff now says:

~ spec.replicas: 3 → 5

and git log -p says:

 apiVersion: apps/v1
 spec:
-  replicas: 3
+  replicas: 5
   template:
     image: app:1.0

The reordering is gone from the second one because both sides get canonicalised
before git compares them. Same file, same commit, two different questions.

Four things that bit me

Git passes seven arguments, not two

An external driver is called as:

path old-file old-hex old-mode new-file new-hex new-mode

The two versions are arguments two and five. Argument one is the path. A tool
that takes old new cannot be plugged in directly, it will compare the
filename against the old version. You either wrap it in a shell function that
picks out $2 and $5, or you teach the tool git's convention. I did the
second, the shim has problems I will get to.

A non-zero exit kills the whole diff

This one cost me the most. My tool exits 1 when it finds differences, which is
correct for a CLI and fatal for a diff driver. Git reads any non-zero status as
the driver having failed:

fatal: external diff died, stopping at deploy.yaml

Not "this file failed". The entire diff stops, and every file after that one is
never shown.

It gets worse. The obvious case is a file that is not structured data at all,
which you can avoid with a careful .gitattributes. The case you cannot avoid
is a file that is invalid right now because you are in the middle of editing
it. You type half a JSON object, run git diff to see what you have done, and
git blows up. A driver that does that gets uninstalled the same day.

So the driver has to swallow its own errors:

deploy.json
  no semantic diff: invalid JSON: EOF while parsing a value at line 2
  run `git diff --no-ext-diff` to see this file as plain text
cfg.toml
~ x.n: 1 → 2

Prints a note, keeps walking, exits zero.

The format has to come from argument one

Git stages the two versions in temporary files. In my testing the basename
survived (/tmp/git-blob-CVrzDV/conf.json), so sniffing the extension off the
temp file happens to work. I would not rely on it. Argument one is the real
path and it is always there, so detect the format from that and fall back to
the temp files, not the other way around.

This is the first reason to prefer a subcommand over a shell shim: $2 and
$5 are all the shim has, so it is guessing.

Read bytes, not text, in the fallback

My textconv mode passes a file through unchanged when it cannot parse it. The
first version did this:

std::fs::read_to_string(file).unwrap_or_default()

Which is fine until someone has a config in CP1251. read_to_string fails on
invalid UTF-8, unwrap_or_default hands back an empty string, both sides
normalize to nothing, and git reports the file as unchanged. The file vanished
from git log -p entirely. That is worse than no integration: a plain diff at
least tells you the versions differ.

let raw = std::fs::read(file).unwrap_or_default();
std::io::stdout().write_all(&raw).ok();

Copy bytes. A fallback that loses data is not a fallback.

The shim, and why I stopped using it

You can get most of this with one line and no new code:

git config diff.datadiff.command 'f() { datadiff --exit-zero "$2" "$5"; }; f'

It works. I shipped that first and documented it. Four things pushed me to a
real subcommand:

it cannot name the file it is diffing, and git prints nothing around driver output, so a diff across five files is unreadable
the format is guessed from temp files
a file that is invalid mid-edit aborts everything
the function syntax needs a POSIX shell, so Windows users are out

If you are wiring up an existing tool, start with the shim. If you own the
tool, spend the afternoon.

What this does not fix

Submodules and symlinks reach the driver if your .gitattributes pattern is
broad enough, and there is nothing useful to say about either, so they land in
the same note-and-continue path. With the narrow patterns you actually want
(*.json, *.yaml) they never get there.

Colour is handled for you, incidentally. Git pipes driver output to a pager, so
a library that checks for a tty turns colour off on its own.

The tool is datadiff, Rust,
MIT/Apache-2.0, and it also does CSV, TOML and XML plus a --fail-on mode for
CI. But the git mechanics above are not specific to it. If you maintain
anything that understands a file format better than diff does, these are the
two hooks and those are the four traps.