in Python/Product/PythonTools/PythonTools/Editor/Formatting/DiffMatchPatch.cs [1169:1291]
public void diff_cleanupMerge(List<Diff> diffs) {
// Add a dummy entry at the end.
diffs.Add(new Diff(Operation.EQUAL, string.Empty));
int pointer = 0;
int count_delete = 0;
int count_insert = 0;
string text_delete = string.Empty;
string text_insert = string.Empty;
int commonlength;
while (pointer < diffs.Count) {
switch (diffs[pointer].operation) {
case Operation.INSERT:
count_insert++;
text_insert += diffs[pointer].text;
pointer++;
break;
case Operation.DELETE:
count_delete++;
text_delete += diffs[pointer].text;
pointer++;
break;
case Operation.EQUAL:
// Upon reaching an equality, check for prior redundancies.
if (count_delete + count_insert > 1) {
if (count_delete != 0 && count_insert != 0) {
// Factor out any common prefixies.
commonlength = this.diff_commonPrefix(text_insert, text_delete);
if (commonlength != 0) {
if ((pointer - count_delete - count_insert) > 0 &&
diffs[pointer - count_delete - count_insert - 1].operation
== Operation.EQUAL) {
diffs[pointer - count_delete - count_insert - 1].text
+= text_insert.Substring(0, commonlength);
} else {
diffs.Insert(0, new Diff(Operation.EQUAL,
text_insert.Substring(0, commonlength)));
pointer++;
}
text_insert = text_insert.Substring(commonlength);
text_delete = text_delete.Substring(commonlength);
}
// Factor out any common suffixies.
commonlength = this.diff_commonSuffix(text_insert, text_delete);
if (commonlength != 0) {
diffs[pointer].text = text_insert.Substring(text_insert.Length
- commonlength) + diffs[pointer].text;
text_insert = text_insert.Substring(0, text_insert.Length
- commonlength);
text_delete = text_delete.Substring(0, text_delete.Length
- commonlength);
}
}
// Delete the offending records and add the merged ones.
pointer -= count_delete + count_insert;
diffs.Splice(pointer, count_delete + count_insert);
if (text_delete.Length != 0) {
diffs.Splice(pointer, 0,
new Diff(Operation.DELETE, text_delete));
pointer++;
}
if (text_insert.Length != 0) {
diffs.Splice(pointer, 0,
new Diff(Operation.INSERT, text_insert));
pointer++;
}
pointer++;
} else if (pointer != 0
&& diffs[pointer - 1].operation == Operation.EQUAL) {
// Merge this equality with the previous one.
diffs[pointer - 1].text += diffs[pointer].text;
diffs.RemoveAt(pointer);
} else {
pointer++;
}
count_insert = 0;
count_delete = 0;
text_delete = string.Empty;
text_insert = string.Empty;
break;
}
}
if (diffs[diffs.Count - 1].text.Length == 0) {
diffs.RemoveAt(diffs.Count - 1); // Remove the dummy entry at the end.
}
// Second pass: look for single edits surrounded on both sides by
// equalities which can be shifted sideways to eliminate an equality.
// e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
bool changes = false;
pointer = 1;
// Intentionally ignore the first and last element (don't need checking).
while (pointer < (diffs.Count - 1)) {
if (diffs[pointer - 1].operation == Operation.EQUAL &&
diffs[pointer + 1].operation == Operation.EQUAL) {
// This is a single edit surrounded by equalities.
if (diffs[pointer].text.EndsWith(diffs[pointer - 1].text,
StringComparison.Ordinal)) {
// Shift the edit over the previous equality.
diffs[pointer].text = diffs[pointer - 1].text +
diffs[pointer].text.Substring(0, diffs[pointer].text.Length -
diffs[pointer - 1].text.Length);
diffs[pointer + 1].text = diffs[pointer - 1].text
+ diffs[pointer + 1].text;
diffs.Splice(pointer - 1, 1);
changes = true;
} else if (diffs[pointer].text.StartsWith(diffs[pointer + 1].text,
StringComparison.Ordinal)) {
// Shift the edit over the next equality.
diffs[pointer - 1].text += diffs[pointer + 1].text;
diffs[pointer].text =
diffs[pointer].text.Substring(diffs[pointer + 1].text.Length)
+ diffs[pointer + 1].text;
diffs.Splice(pointer + 1, 1);
changes = true;
}
}
pointer++;
}
// If shifts were made, the diff needs reordering and another shift sweep.
if (changes) {
this.diff_cleanupMerge(diffs);
}
}