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

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.

The repository is available at github.com/dimanovikov/datadiff under the MIT / Apache-2.0 licenses. The benchmark script is in the repository as bench/compare_graphtage.py.