diff_cleanupSemantic method

void diff_cleanupSemantic(List<Diff> diffs)

Reduce the number of edits by eliminating semantically trivial equalities. diffs is a List of Diff objects.

Implementation

void diff_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;
  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 == Operation.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 == Operation.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, Diff(Operation.delete, lastEquality));
        // Change second copy to insert.
        diffs[equalities.last + 1].operation = Operation.insert;
        // Throw away the equality we just deleted.
        equalities.removeLast();
        // Throw away the previous equality (it needs to be reevaluated).
        if (equalities.isNotEmpty) {
          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) {
    diff_cleanupMerge(diffs);
  }
  _diff_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 == Operation.delete &&
        diffs[pointer].operation == Operation.insert) {
      String deletion = diffs[pointer - 1].text;
      String insertion = diffs[pointer].text;
      int overlap_length1 = _diff_commonOverlap(deletion, insertion);
      int overlap_length2 = _diff_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,
              Diff(Operation.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,
              Diff(Operation.equal, deletion.substring(0, overlap_length2)));
          diffs[pointer - 1] = Diff(Operation.insert,
              insertion.substring(0, insertion.length - overlap_length2));
          diffs[pointer + 1] =
              Diff(Operation.delete, deletion.substring(overlap_length2));
          pointer++;
        }
      }
      pointer++;
    }
    pointer++;
  }
}