Typescript Diff

diff.example.ts

import {byField, differ} from './diff';

export type Address = {
    id: number | null;
    street: string;
    city: string;
    state: string;
    zip: string;
};

export type President = {
    firstNames: Array<string>;
    lastName: string;
    birthYear: number;
    party?: string;
    electedYears: Array<number>;
    addresses: Array<Address>;
};

export const president: President = {
    lastName: 'Bush',
    birthYear: 1946,
    firstNames: ['George', 'Walker'],
    electedYears: [2001, 2005],
    addresses: [
        {
            id: 1,
            street: '742 Evergreen Terrace',
            city: 'Springfield',
            state: 'U.S.',
            zip: '99999'
        },
        {
            id: 2,
            street: '11228 W Sunset Blvd',
            city: 'Los Angeles',
            state: 'U.S.',
            zip: '90049'
        }
    ]
};

export const addressDiffer = differ<Address>().object({
    id: differ(),
    street: differ(),
    city: differ(),
    zip: differ(),
    state: differ()
});

export const presidentDiffer = differ<President>().object({
    birthYear: differ(),
    party: differ(),
    firstNames: differ().array(),
    lastName: differ(),
    electedYears: differ().array(),
    addresses: addressDiffer.array(byField('id'))
});

const diff = presidentDiffer.diff(president, president);

diff.pipes.ts

import {Pipe, PipeTransform} from '@angular/core';
import {ArrayDiffItem, Diff, left, leftIndex, modified, right, rightIndex} from './diff';

@Pipe({name: 'left'})
export class LeftPipe implements PipeTransform {

  transform<T>(diff: Diff<T>) {
    return left(diff);
  }
}

@Pipe({name: 'right'})
export class RightPipe implements PipeTransform {

  transform<T>(diff: Diff<T>) {
    return right(diff);
  }
}

@Pipe({name: 'modified'})
export class Modified implements PipeTransform {

  transform(diff: Diff<any>) {
    return modified(diff);
  }
}

@Pipe({name: 'leftIndex'})
export class LeftIndexPipe implements PipeTransform {

  transform(diff: ArrayDiffItem) {
    return leftIndex(diff);
  }
}

@Pipe({name: 'rightIndex'})
export class RightIndexPipe implements PipeTransform {

  transform(diff: ArrayDiffItem) {
    return rightIndex(diff);
  }
}

@Pipe({
  name: 'diffClass'
})
export class DiffClassPipe implements PipeTransform {

  transform(diff: Diff<any>) {
    if (!modified(diff)) {
      return 'unchanged';
    } else if (left(diff) === null && right(diff) !== null) {
      return 'added';
    } else if (left(diff) !== null && right(diff) === null) {
      return 'deleted';
    } else {
      return 'changed';
    }
  }
}

diff.ts

export type Equivalence<T> = (left: T | null, right: T | null, leftIndex: number, rightIndex: number) => boolean;

export function byValue<T>(): Equivalence<T> {
  return (left, right) => left === right;
}

export function byFunction<T, V>(extractor: (target: T | null) => V, equivalence: Equivalence<V> = byValue()): Equivalence<T> {
  return (left, right, leftIndex, rightIndex) => equivalence(extractor(left), extractor(right), leftIndex, rightIndex);
}

export function byField<T, K extends keyof T>(key: K, equivalence: Equivalence<T[K] | null> = byValue()): Equivalence<T> {
  return byFunction(target => target?.[key] ?? null, equivalence);
}

export function byIndex<T>(): Equivalence<T> {
  return (_left, _right, leftIndex, rightIndex) => leftIndex === rightIndex;
}

const LEFT: unique symbol = Symbol('left');
const RIGHT: unique symbol = Symbol('right');
const MODIFIED: unique symbol = Symbol('modified');
const LEFT_INDEX: unique symbol = Symbol('leftIndex');
const RIGHT_INDEX: unique symbol = Symbol('rightIndex');

export type Diff<T> = {
  readonly [LEFT]: T | null;
  readonly [RIGHT]: T | null;
  readonly [MODIFIED]: boolean;
};

export type ArrayDiffItem = {
  [LEFT_INDEX]: number | null;
  [RIGHT_INDEX]: number | null;
};

export const left = <T>(diff: Diff<T>) => diff[LEFT];
export const right = <T>(diff: Diff<T>) => diff[RIGHT];
export const modified = (diff: Diff<any>) => diff[MODIFIED];
export const leftIndex = (diff: ArrayDiffItem) => diff[LEFT_INDEX];
export const rightIndex = (diff: ArrayDiffItem) => diff[RIGHT_INDEX];

type Properties<T> = {
  readonly [K in keyof T]?: Differ<T[K], any>;
};

type PropertiesDiff<P> = {
  readonly [K in keyof P]: P[K] extends Differ<any, infer D> ? D : never;
};

export type Differ<T, D extends Diff<T>> = {
  diff(left: T | null, right: T | null): D;
};

const array = <T, D extends Diff<T>>(differ: Differ<T, D>, equivalence: Equivalence<T>) => ({
  diff: (left: Array<T> | null, right: Array<T> | null) => {
    const array = arrayDiff(left ?? [], right ?? [], differ, equivalence);
    const modified = array.some(({[MODIFIED]: modified}) => modified);
    return Object.assign(array, {[LEFT]: left, [RIGHT]: right, [MODIFIED]: modified});
  }
});

const object = <T, P extends Properties<T>>(props: P) => ({
  diff(left: T | null, right: T | null) {
    // TODO check if we can make all `any` go away
    const properties = Object.entries(props).reduce((result, [property, differ]) => ({
      ...result,
      [property]: (differ as Differ<any, any>).diff((left as any)?.[property], (right as any)?.[property])
    }), {}) as PropertiesDiff<P>;
    const modified = Object.entries<Diff<any>>(properties).some(([_property, {[MODIFIED]: modified}]) => modified);
    return {[LEFT]: left, [RIGHT]: right, [MODIFIED]: modified, ...properties};
  },
  array(equivalence: Equivalence<T> = byValue()) {
    return array(this, equivalence);
  }
});

export const differ = <T>() => ({
  diff(left: T | null, right: T | null) {
    return {[LEFT]: left, [RIGHT]: right, [MODIFIED]: left !== right};
  },
  array(equivalence: Equivalence<T> = byValue()) {
    return array(this, equivalence);
  },
  object<P extends Properties<T>>(props: keyof P extends keyof T ? P : never) {
    return object<T, P>(props);
  }
});

function arrayDiff<T, D extends Diff<T>>(left: Array<T>, right: Array<T>, differ: Differ<T, D>, equivalence: Equivalence<T>) {
  const f = (leftIndex: number | null, rightIndex: number | null) => ({
    ...differ.diff(leftIndex === null ? null : left[leftIndex], rightIndex === null ? null : right[rightIndex]),
    [LEFT_INDEX]: leftIndex,
    [RIGHT_INDEX]: rightIndex
  });
  const e = (leftIndex: number, rightIndex: number) => equivalence(left[leftIndex], right[rightIndex], leftIndex, rightIndex);
  const n = left?.length ?? 0;
  const m = right?.length ?? 0;
  const z = n + m;
  const v = Array<number>(z + 1 + z).fill(0);
  const trace: Array<typeof v> = [];
  const result: Array<D & ArrayDiffItem> = [];
  for (let d = 0; d <= z; d++) {
    trace.push([...v]);
    for (let k = -d; k <= d; k += 2) {
      let x = k === -d || k !== d && v[z + k - 1] < v[z + k + 1] ? v[z + k + 1] : v[z + k - 1] + 1;
      let y = x - k;
      while (x < n && y < m && e(x, y)) {
        x++;
        y++;
      }
      v[z + k] = x;
      if (x === n && y === m) {
        do {
          const v = trace[d];
          const k = x - y;
          const pk = k === -d || k !== d && v[z + k - 1] < v[z + k + 1] ? k + 1 : k - 1;
          const px = v[z + pk];
          const py = px - pk;
          while (x > px && y > py) {
            result.unshift(f(--x, --y))
          }
          if (d > 0) {
            result.unshift(f(x === px ? null : x = px, y === py ? null : y = py));
          }
        } while (--d >= 0);
        return result;
      }
    }
  }
  return result;
}