Make a deep object delta diff in TypeScript

2019-09-25 (Wednesday) | 400 words (~2 minutes reading)

Notes to myself.

Building on the object path enumeration, we can also make a deep object diff or delta.

E.g. given these two objects:

{ "a": { "b": { "c": "123" } }, "foo": "hello" }

{ "a": { "b": { "c": "123", "d": "456" } }, "foo": "hello" }

We would make this delta diff:

{ "a": { "b": { "d": "456" } } }

This uses a few utility functions aside from enumeratePaths, but it should be relatively clear what they do here:

import _ from "lodash"

import { enumeratePaths } from "./enumeratePaths"
import { objGet, objSet } from "./objPath"

export function makeDelta(
    oldObject: IStringToUnknown,
    newObject: IStringToUnknown,
): IStringToUnknown {
    if (typeof newObject !== typeof oldObject) {
        return newObject
    }
    if (!_.isObject(newObject)) {
        return newObject
    }

    const paths: string[] = _.uniq(
        enumeratePaths(oldObject).concat(enumeratePaths(newObject)),
    )
    let pathSplits: string[][] = paths.map((path: string): string[] =>
        path.split("/"),
    )
    pathSplits = pathSplits.filter((thisPath: string[]): boolean => {
        return !pathSplits.find((otherPath: string[]): boolean => {
            return (
                otherPath[0] === thisPath[0] &&
                otherPath.length > thisPath.length
            )
        })
    })

    const delta: IStringToUnknown = {}

    pathSplits.forEach((pathSplit: string[]): void => {
        const oldValue = objGet(oldObject, pathSplit)
        const newValue = objGet(newObject, pathSplit)
        if (newValue !== oldValue) {
            objSet(delta, pathSplit, newValue)
        }
    })

    return delta
}

We get the unique set of all possible paths in both objects (O(n) for each leaf key), and then compare each of those paths between the two objects so overall this should be O(2n) for each unique leaf key between the two objects.

There’s an import step in the middle, which is to ignore the shorter of two paths with the same prefix, so overall we get O(3n), which boils down to O(n).

There may be a faster way to do this (probably by doing it in 2 passes instead of 3), but it seems clear and sufficiently fast for small objects.


Tech mentioned