cleanupSemantic function

void cleanupSemantic(List<Diff> diffs)

Reduce the number of edits by eliminating semantically trivial equalities.

diffs is a List of Diff objects.

Implementation

void cleanupSemantic(List<Diff> diffs) {
  bool changes = false;
  // Stack of indices where equalities are found.
  final equalities = <int>[];
  // Always equal to diffs[equalities.last()].text
  String? lastequality = null;
  int pointer = 0;  // Index of current position.
  // Number of characters that changed prior to the equality.
  int length_insertions1 = 0;
  int length_deletions1 = 0;
  // Number of characters that changed after the equality.
  int length_insertions2 = 0;
  int length_deletions2 = 0;
  while (pointer < diffs.length) {
    if (diffs[pointer].operation == DIFF_EQUAL) {  // Equality found.
      equalities.add(pointer);
      length_insertions1 = length_insertions2;
      length_deletions1 = length_deletions2;
      length_insertions2 = 0;
      length_deletions2 = 0;
      lastequality = diffs[pointer].text;
    } else {  // An insertion or deletion.
      if (diffs[pointer].operation == DIFF_INSERT) {
        length_insertions2 += diffs[pointer].text.length;
      } else {
        length_deletions2 += diffs[pointer].text.length;
      }
      // Eliminate an equality that is smaller or equal to the edits on both
      // sides of it.
      if (lastequality != null
          && (lastequality.length
              <= max(length_insertions1, length_deletions1))
          && (lastequality.length
              <= max(length_insertions2, length_deletions2))) {
        // Duplicate record.
        diffs.insert(equalities.last, new Diff(DIFF_DELETE, lastequality));
        // Change second copy to insert.
        diffs[equalities.last + 1].operation = DIFF_INSERT;
        // Throw away the equality we just deleted.
        equalities.removeLast();
        // Throw away the previous equality (it needs to be reevaluated).
        if (!equalities.isEmpty) {
          equalities.removeLast();
        }
        pointer = equalities.isEmpty ? -1 : equalities.last;
        length_insertions1 = 0;  // Reset the counters.
        length_deletions1 = 0;
        length_insertions2 = 0;
        length_deletions2 = 0;
        lastequality = null;
        changes = true;
      }
    }
    pointer++;
  }

  // Normalize the diff.
  if (changes) {
    cleanupMerge(diffs);
  }
  cleanupSemanticLossless(diffs);

  // Find any overlaps between deletions and insertions.
  // e.g: <del>abcxxx</del><ins>xxxdef</ins>
  //   -> <del>abc</del>xxx<ins>def</ins>
  // e.g: <del>xxxabc</del><ins>defxxx</ins>
  //   -> <ins>def</ins>xxx<del>abc</del>
  // Only extract an overlap if it is as big as the edit ahead or behind it.
  pointer = 1;
  while (pointer < diffs.length) {
    if (diffs[pointer - 1].operation == DIFF_DELETE
        && diffs[pointer].operation == DIFF_INSERT) {
      String deletion = diffs[pointer - 1].text;
      String insertion = diffs[pointer].text;
      int overlap_length1 = commonOverlap(deletion, insertion);
      int overlap_length2 = commonOverlap(insertion, deletion);
      if (overlap_length1 >= overlap_length2) {
        if (overlap_length1 >= deletion.length / 2 ||
            overlap_length1 >= insertion.length / 2) {
          // Overlap found.
          // Insert an equality and trim the surrounding edits.
          diffs.insert(pointer,
              new Diff(DIFF_EQUAL, insertion.substring(0, overlap_length1)));
          diffs[pointer - 1].text =
              deletion.substring(0, deletion.length - overlap_length1);
          diffs[pointer + 1].text = insertion.substring(overlap_length1);
          pointer++;
        }
      } else {
        if (overlap_length2 >= deletion.length / 2 ||
            overlap_length2 >= insertion.length / 2) {
          // Reverse overlap found.
          // Insert an equality and swap and trim the surrounding edits.
          diffs.insert(pointer,
              new Diff(DIFF_EQUAL, deletion.substring(0, overlap_length2)));
          diffs[pointer - 1] = new Diff(DIFF_INSERT,
              insertion.substring(0, insertion.length - overlap_length2));
          diffs[pointer + 1] = new Diff(DIFF_DELETE,
              deletion.substring(overlap_length2));
          pointer++;
        }
      }
      pointer++;
    }
    pointer++;
  }
}