استوديو مقارنة النصوص والأكواد (Diff)

// Complete Myers O(ND) Line Diffing Engine in TypeScript
export interface DiffChunk {
  type: 'equal' | 'insert' | 'delete';
  value: string;
}

export function computeMyersDiff(originalText: string, modifiedText: string): DiffChunk[] {
  const a = originalText.split('\n');
  const b = modifiedText.split('\n');
  const N = a.length;
  const M = b.length;
  const max = N + M;
  
  if (N === 0 && M === 0) return [];
  
  // Array tracking furthest reaching x coordinate on diagonal k
  const offset = max;
  const v = new Int32Array(2 * max + 1);
  const trace: Int32Array[] = [];

  for (let d = 0; d <= max; d++) {
    trace.push(new Int32Array(v));
    for (let k = -d; k <= d; k += 2) {
      let x: number;
      // Decide whether to move down (from k+1) or right (from k-1)
      if (k === -d || (k !== d && v[k - 1 + offset] < v[k + 1 + offset])) {
        x = v[k + 1 + offset]; // Down (insertion)
      } else {
        x = v[k - 1 + offset] + 1; // Right (deletion)
      }

      let y = x - k;
      // Greedily slide down diagonal while lines match
      while (x < N && y < M && a[x] === b[y]) {
        x++;
        y++;
      }

      v[k + offset] = x;

      if (x >= N && y >= M) {
        // Target reached! Backtrack through trace to build edit script
        return backtrackDiff(trace, a, b, d);
      }
    }
  }

  return [];
}

function backtrackDiff(trace: Int32Array[], a: string[], b: string[], d: number): DiffChunk[] {
  const result: DiffChunk[] = [];
  let x = a.length;
  let y = b.length;
  const max = a.length + b.length;
  const offset = max;

  for (let step = d; step > 0; step--) {
    const v = trace[step];
    const k = x - y;
    let prevK: number;

    if (k === -step || (k !== step && v[k - 1 + offset] < v[k + 1 + offset])) {
      prevK = k + 1;
    } else {
      prevK = k - 1;
    }

    const prevX = v[prevK + offset];
    const prevY = prevX - prevK;

    // Record diagonal moves (equal lines)
    while (x > prevX && y > prevY && a[x - 1] === b[y - 1]) {
      result.unshift({ type: 'equal', value: a[x - 1] });
      x--;
      y--;
    }

    // Record edit move
    if (x === prevX) {
      result.unshift({ type: 'insert', value: b[y - 1] });
      y--;
    } else {
      result.unshift({ type: 'delete', value: a[x - 1] });
      x--;
    }
  }

  // Record initial equal lines at start
  while (x > 0 && y > 0) {
    result.unshift({ type: 'equal', value: a[x - 1] });
    x--;
    y--;
  }

  return result;
}