myersDiff function

List<DiffSegment> myersDiff(String oldText, String newText)

Compute Myers diff between two strings and return coalesced segments of Equal, Insert, and Remove operations.

print(myersDiff('Hello', 'Hello')); // Prints 1 diff segment with op equal
print(myersDiff('Hello', 'Hello World')); // Prints 2 diff segments with op equal and insert

Implementation

List<DiffSegment> myersDiff(String oldText, String newText) {
  if (oldText == newText) {
    if (oldText.isEmpty) {
      return <DiffSegment>[];
    } else {
      return <DiffSegment>[
        DiffSegment(
          op: DiffOp.equal,
          text: oldText,
          oldStart: 0,
          oldEnd: oldText.length,
          newStart: 0,
          newEnd: newText.length,
        ),
      ];
    }
  }
  if (oldText.isEmpty) {
    return <DiffSegment>[
      DiffSegment(
        op: DiffOp.insert,
        text: newText,
        oldStart: 0,
        oldEnd: 0,
        newStart: 0,
        newEnd: newText.length,
      ),
    ];
  }
  if (newText.isEmpty) {
    return <DiffSegment>[
      DiffSegment(
        op: DiffOp.remove,
        text: oldText,
        oldStart: 0,
        oldEnd: oldText.length,
        newStart: 0,
        newEnd: 0,
      ),
    ];
  }

  // Trim common prefix and suffix to reduce the problem size.
  final prefixLen = _commonPrefix(oldText, newText);
  final suffixLen = _commonSuffix(
    oldText,
    newText,
    prefixLen,
  );

  final segments = <DiffSegment>[];
  if (prefixLen > 0) {
    segments.add(
      DiffSegment(
        op: DiffOp.equal,
        text: oldText.substring(0, prefixLen),
        oldStart: 0,
        oldEnd: prefixLen,
        newStart: 0,
        newEnd: prefixLen,
      ),
    );
  }

  final aMid = oldText.substring(prefixLen, oldText.length - suffixLen);
  final bMid = newText.substring(prefixLen, newText.length - suffixLen);

  if (aMid.isEmpty && bMid.isNotEmpty) {
    segments.add(
      DiffSegment(
        op: DiffOp.insert,
        text: bMid,
        oldStart: prefixLen,
        oldEnd: prefixLen,
        newStart: prefixLen,
        newEnd: newText.length - suffixLen,
      ),
    );
  } else if (bMid.isEmpty && aMid.isNotEmpty) {
    segments.add(
      DiffSegment(
        op: DiffOp.remove,
        text: aMid,
        oldStart: prefixLen,
        oldEnd: oldText.length - suffixLen,
        newStart: prefixLen,
        newEnd: prefixLen,
      ),
    );
  } else if (aMid.isNotEmpty || bMid.isNotEmpty) {
    final a = aMid.codeUnits;
    final b = bMid.codeUnits;
    final edits = _shortestEditScript(a, b);
    segments.addAll(_coalesce(a, b, edits, prefixLen, prefixLen));
  }

  if (suffixLen > 0) {
    final oldSuffixStart = oldText.length - suffixLen;
    final newSuffixStart = newText.length - suffixLen;
    segments.add(
      DiffSegment(
        op: DiffOp.equal,
        text: oldText.substring(oldSuffixStart),
        oldStart: oldSuffixStart,
        oldEnd: oldText.length,
        newStart: newSuffixStart,
        newEnd: newText.length,
      ),
    );
  }

  return segments;
}