Myers Diff

Computes the differences between two sequences efficiently, commonly used in version control systems to show changes between file revisions.

/**
 * @file Myers Diff
 * @author Dustin Boston
 * @see E. Myers, "An O(ND) difference algorithm and its variations,"
 *   _Algorithmica_, vol. 1, no. 1–4, pp. 251–266, 1986.
 * @see J. Coglan, "The Myers diff algorithm: part 1," The if works,
 *   https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
 * @see R. Elder, "Myers Diff Algorithm - Code & Interactive Visualization,"
 *   Robert Elder Software Inc, https://blog.robertelder.org/diff-algorithm/
 */

/**
 * Creates an array that can have negative indexes using a JavaScript Proxy.
 *
 * @example
 *   ```ts
 *   const array = new NegativeArray(1, 2, 3, 4, 5);
 *   console.log(array[-1]); // Output: 5
 *   array[-2] = 42;
 *   console.log(array[3]); // Output: 42
 *   console.log(array[10]); // Output: undefined
 *   ```;
 *
 * @param arrayToProxy - The array to be proxied.
 * @returns A proxied array allowing negative indexing.
 * @see A. Balane, "JavaScript array negative index using proxies," Medium,
 *   https://medium.com/uncaught-exception/javascript-array-negative-index-using-proxies-ed096dc84416
 */
class NegativeArray<T> extends Array<T> {
  constructor(...items: T[]) {
    super(...items);

// eslint-disable-next-line no-constructor-return
    return new Proxy(this, {
      get(
        target: T[],
        property: string | symbol,
        receiver: any,
      ): T | undefined {
        if (typeof property === 'string' && !Number.isNaN(Number(property))) {
          let propertyValue = Number.parseInt(property, 10);
          if (propertyValue < 0) propertyValue += target.length;
          return target[propertyValue];
        }

// Safe casting of the Reflect.get return value to expected type
        return Reflect.get(target, property, receiver) as T | undefined;
      },
      set(
        target: T[],
        property: string | symbol,
        value: T,
        receiver: any,
      ): boolean {
        if (typeof property === 'string' && !Number.isNaN(Number(property))) {
          let propertyValue = Number.parseInt(property, 10);
          if (propertyValue < 0) propertyValue += target.length;
          target[propertyValue] = value; // Safe assignment of typed value
          return true;
        }

return Reflect.set(target, property, value, receiver);
      },
    });
  }
}

/**
 * Computes the diff between two strings using the Myers algorithm and returns
 * an edit script in the form `xD` or `xIb` where `x` is the `x` coordinate, `D`
 * is delete, `I` is insert, and `b` is the char inserted at`x`, for example
 * `1D,2D,3IB,6D,7IC`.
 *
 * @param original - The original string.
 * @param target - The target string to compare.
 * @returns An edit script.
 */
function diff(original: string, target: string): string[] {
  const operations: string[] = [];
  const editTrace = shortestEdit(original, target);
  if (!editTrace) throw new Error('Invalid return.');

// Backtrack yields from the end to the start.
  for (const [previousX, previousY, currentX, currentY] of backtrack(
    original.length,
    target.length,
    editTrace,
  )) {
    const targetChar = target[previousY];
    if (currentX === previousX) operations.unshift(`${currentX}I${targetChar}`);
    else if (currentY === previousY) operations.unshift(`${currentX}D`);
  }

return operations;
}

/**
 * The Greedy LCS/SES Algorithm (figure 2 in the paper) Finds the shortest edit
 * path for two strings using the Myers diff algorithm.
 *
 * @param original - The original string.
 * @param target - The target string.
 * @returns The trace of V operations with each step taken.
 */
function shortestEdit(
  original: string,
  target: string,
): number[][] | undefined {
  const originalLength = original.length;
  const targetLength = target.length;
  const maxLength = originalLength + targetLength;

/** An array of the furthest reaching edit distances across the edit graph */
  const furthestReachingPoints: number[] = new NegativeArray<number>(
    2 * maxLength + 2,
  );
  furthestReachingPoints[1] = 0;

/** Record of each operation */
  const trace: number[][] = new NegativeArray<number[]>();

// Calculate distances (d)
  for (let distance = 0; distance <= maxLength + 1; distance++) {
    trace.push(new NegativeArray<number>(...furthestReachingPoints));

// Calculate the operations (k)
    for (let diagonal = -distance; diagonal <= distance + 1; diagonal += 2) {
      let currentX =
        diagonal === -distance ||
        (diagonal !== distance &&
          furthestReachingPoints[diagonal - 1] <
            furthestReachingPoints[diagonal + 1])
          ? furthestReachingPoints[diagonal + 1] // Move down (deletion)
          : furthestReachingPoints[diagonal - 1] + 1; // Move right (insertion)

let currentY = currentX - diagonal;
      while (
        currentX < originalLength &&
        currentY < targetLength &&
        original[currentX] === target[currentY]
      ) {
        currentX++;
        currentY++;
      }

furthestReachingPoints[diagonal] = currentX;
      if (currentX >= originalLength && currentY >= targetLength) {
        return trace;
      }
    }
  }
}

/** Records a movement from the previous position to the current position. */
type Move = [
  previousX: number,
  previousY: number,
  currentX: number,
  currentY: number,
];

/**
 * A generator function that backtracks from the computed trace to find the
 * actual diff path.
 *
 * @param originalLength - Length of the original string.
 * @param targetLength - Length of the target string.
 * @param trace - The edit trace
 * @yields Individual moves to transform the original string into the target
 *   string.
 */
function* backtrack(
  originalLength: number,
  targetLength: number,
  trace: number[][],
): Generator<Move, void> {
  let currentX = originalLength;
  let currentY = targetLength;

for (let distance = trace.length - 1; distance > -1; distance--) {
    /** Array of furthest reaching x distances across the edit graph */
    const furthestReachingPoints = trace[distance];
    /** The operation */
    const diagonal = currentX - currentY;

/** Previous edit operation */
    const previousDiagonal =
      diagonal === -distance ||
      (diagonal !== distance &&
        furthestReachingPoints[diagonal - 1] <
          furthestReachingPoints[diagonal + 1])
        ? diagonal + 1
        : diagonal - 1;

const previousX = furthestReachingPoints[previousDiagonal];
    const previousY = previousX - previousDiagonal;

while (currentX > previousX && currentY > previousY) {
      yield [currentX - 1, currentY - 1, currentX, currentY];
      currentX -= 1;
      currentY -= 1;
    }

if (distance > 0) yield [previousX, previousY, currentX, currentY];
    currentX = previousX;
    currentY = previousY;
  }
}

// Usage
(() => {
  const array = new NegativeArray(1, 2, 3, 4, 5);
  if (array[-1] !== 5) {
    throw new Error(`Expected 5 but got ${array[-1]}`);
  }

// Diff between 'ABCABBA' and 'CBABAC'
  const abcActual = diff('ABCABBA', 'CBABAC');
  const abcExpected = '1D,2D,3IB,6D,7IC';

if (abcActual.toString() !== abcExpected) {
    throw new Error(`Expected ${abcExpected} but got ${abcActual.join(',')}`);
  }

// Diff between 'CARE' and 'BEAR'
  const careActual = diff('CARE', 'BEAR');
  const careExpected = '1D,1IB,1IE,4D';

if (careActual.toString() !== careExpected) {
    throw new Error(`Expected ${careExpected} but got ${careActual.join(',')}`);
  }

console.log('Diff passed');
})();