TypeScript implementation of computing difference of given two JavaScript value

diff.ts

type Addition = {
  type: 'addition'
  next: any
}

type Change = {
  type: 'change'
  prev: any
  next: any
}

type Deletion = {
  type: 'deletion'
  prev: any
}

type Diff = Addition | Change | Deletion | undefined | Diff[] | { [key: string]: Diff }

function diff(oPrev: any, oNext: any): Diff {
  // primitive
  if (typeof oPrev !== typeof oNext || typeof oPrev !== 'object') {
    if (oPrev === oNext) return undefined
    if (oPrev === undefined) {
      return {
        type: 'addition',
        next: oNext,
      }
    }
    if (oNext === undefined) {
      return {
        type: 'deletion',
        prev: oPrev,
      }
    }
    return {
      type: 'change',
      prev: oPrev,
      next: oNext,
    }
  }

  // both null
  if (!oPrev && !oNext) return undefined

  // only one is null
  if (!oPrev || !oNext) {
    return {
      type: 'change',
      prev: oPrev,
      next: oNext,
    }
  }

  const isPrevArray = oPrev instanceof Array
  const isNextArray = oNext instanceof Array

  if (isPrevArray && isNextArray) {
    // early termination
    if (oPrev === oNext) return undefined

    const maxLength = oPrev.length > oNext.length ? oPrev.length : oNext.length
    const minLength = oPrev.length > oNext.length ? oNext.length : oPrev.length
    const result = [] as any[]

    for (let i = 0; i < maxLength; ++i) {
      if (i < minLength) {
        result[i] = diff(oPrev[i], oNext[i])
      } else if (oPrev.length === maxLength) {
        result[i] = {
          type: 'deletion',
          prev: oPrev[i],
        }
      } else {
        result[i] = {
          type: 'addition',
          next: oNext[i],
        }
      }
    }

    if (result.some(Boolean)) {
      return result
    }
    return undefined
  }

  if (!isPrevArray && !isNextArray) {
    // early termination
    if (oPrev === oNext) return undefined

    const prevKeys = Object.fromEntries(Object.keys(oPrev).map(key => [key, true]))
    const nextKeys = Object.fromEntries(Object.keys(oNext).map(key => [key, true]))
    const commKeys = { ...prevKeys, ...nextKeys }
    const result = {} as Record<string, any>
    
    for (const key of Object.keys(commKeys)) {
      if (prevKeys[key] && nextKeys[key]) {
        const difference = diff(oPrev[key], oNext[key])

        if (difference) {
          result[key] = difference
        }
      } else if (prevKeys[key]) {
        result[key] = {
          type: 'deletion',
          prev: oPrev[key],
        }
      } else {
        result[key] = {
          type: 'addition',
          next: oNext[key]
        }
      }
    }

    if (Object.keys(result).length === 0) return undefined
    return result
  }

  return {
    type: 'change',
    prev: oPrev,
    next: oNext,
  }
}

This function computes the difference between two given object. The exact rules are pretty complicated, though it's intuitive.

Example

This function is inspired by git diff. You can think this function as git diff of JavaScript object. Any result for unchanged value is undefined.

const result = diff({
  a: 'A',
  b: 'B',
},
{
  a: 'AA',
  c: 'C',
})

const equivalentTo = {
  a: { type: 'change', prev: 'A', next: 'AA' },
  b: { type: 'deletion', prev: 'B' },
  c: { type: 'addition', next: 'C' },
}

This function also supports array recursion like following:

const result = diff([1, 2, [3, 4]], [0, 2, [3], 'x'])
const equivalentTo = [
  { type: 'change', prev: 1, next: 0 },
  undefined,
  [
    undefined,
    { type: 'deletion', prev: 4 },
  ],
  { type: 'addition', next: 'x' },
}

This function also supports object recursion like following:

const result = diff({ x: { y: 'z' }}, { x: { y: 'zz' }})
const equivalentTo = {
  x: {
    y: {
      type: 'changes',
      prev: 'z',
      next: 'zz',
    }
  }
}

Rule

• undefined and null are different
• null is considered as primitive value
• value of function type is only considred with its reference
• undefined → non undefined is considered as addition
• non undefined → undefined is considered as deletion
• non undefined → non undefined is either change or same
  • if both values are in same primitive or reference relation, it's same
  • otherwise, it's change
• if both values are compound type like Array or object (but not null) will be compared recursively
  • if they are both Array
    • if oPrev is longer than oNext, unmatched elements of oPrev in [oNext.length, oPrev.length) will be considered as deletion
    • if oPrev is shorter than oNext, unmatched elements of oNext in [oPrev.length, oNext.length) will be considered as addition
    • otherwise it's either change or same
    • if every elements are same, two arrays are same
  • if they are both object
    • the values for keys of oPrev which doesn't exist in oNext will be considered as deletion
    • the values for keys of oNext which doesn't exist in oPrev will be considered as addition
    • otherwise it's either change or same
    • if every values are same, two objects are same
• result of recursively same, it returns undefined
• otherwise it returns the composition of deeper results

The return type of given function is not possible to represented perfectly using typescript, since it's an inifnite set. TypeScript type infer system has limitation. It can be described by following context free-like grammar: (actually I don't have idean what is this structures is called)

T := L | T[] | Record<string, T>
L := "addition" | "deletion" | "change" | "undefined"

// example
"addition"
{ "foo": "deletion" }
["undefined", "addition", { "bar": ["baz"] }]

Caveats

Note that this code doesn't protect infinite recursion caused by mutual dependency between two compound types. In general sense it's very useless. To protect this, very high cost operation is required.

const x = {} as any
const y = {} as any
x.y = y
y.x = x
diff(x, y) // boom

Note that this function doesn't find maximum match for array. For example, following two arrays has 3 changes and one deletion. Finding maximum match is very high cost (See React's reconcillation docs)

[0, 1, 2, 3]
[1, 2, 3]