in src/Editor/Text/Impl/TextModel/NormalizedTextChangeCollection.cs [112:291]
private static IReadOnlyList<TextChange> Normalize(IReadOnlyList<TextChange> changes, StringDifferenceOptions? differenceOptions, ITextDifferencingService textDifferencingService,
ITextSnapshot before, ITextSnapshot after)
{
if (changes.Count == 1 && differenceOptions == null)
{
// By far the most common path
// If we are computing minimal changes, we need to go through the
// algorithm anyway, since this change may be split up into many
// smaller changes
return new TextChange[] { changes[0] };
}
else if (changes.Count == 0)
{
return Array.Empty<TextChange>();
}
TextChange[] work = TextUtilities.StableSort(changes, TextChange.Compare);
// work is now sorted by increasing Position
int accumulatedDelta = 0;
int a = 0;
int b = 1;
while (b < work.Length)
{
// examine a pair of changes and attempt to combine them
TextChange aChange = work[a];
TextChange bChange = work[b];
int gap = bChange.OldPosition - aChange.OldEnd;
if (gap > 0)
{
// independent changes
aChange.NewPosition = aChange.OldPosition + accumulatedDelta;
accumulatedDelta += aChange.Delta;
a = b;
b = a + 1;
}
else
{
// dependent changes. merge all adjacent dependent changes into a single change in one pass,
// to avoid expensive pairwise concatenations.
//
// Use StringRebuilders (which allow strings to be concatenated without creating copies of the strings) to assemble the
// pieces.
StringRebuilder newRebuilder = aChange._newText;
StringRebuilder oldRebuilder = aChange._oldText;
int aChangeIncrementalDeletions = 0;
do
{
newRebuilder = newRebuilder.Append(bChange._newText);
if (gap == 0)
{
// abutting deletions
oldRebuilder = oldRebuilder.Append(bChange._oldText);
aChangeIncrementalDeletions += bChange.OldLength;
aChange.LineBreakBoundaryConditions =
(aChange.LineBreakBoundaryConditions & LineBreakBoundaryConditions.PrecedingReturn) |
(bChange.LineBreakBoundaryConditions & LineBreakBoundaryConditions.SucceedingNewline);
}
else
{
// overlapping deletions
if (aChange.OldEnd + aChangeIncrementalDeletions < bChange.OldEnd)
{
int overlap = aChange.OldEnd + aChangeIncrementalDeletions - bChange.OldPosition;
oldRebuilder = oldRebuilder.Append(bChange._oldText.GetSubText(Span.FromBounds(overlap, bChange._oldText.Length)));
aChangeIncrementalDeletions += (bChange.OldLength - overlap);
aChange.LineBreakBoundaryConditions =
(aChange.LineBreakBoundaryConditions & LineBreakBoundaryConditions.PrecedingReturn) |
(bChange.LineBreakBoundaryConditions & LineBreakBoundaryConditions.SucceedingNewline);
}
// else bChange deletion subsumed by aChange deletion
}
work[b] = null;
b++;
if (b == work.Length)
{
break;
}
bChange = work[b];
gap = bChange.OldPosition - aChange.OldEnd - aChangeIncrementalDeletions;
} while (gap <= 0);
work[a]._oldText = oldRebuilder;
work[a]._newText = newRebuilder;
if (b < work.Length)
{
aChange.NewPosition = aChange.OldPosition + accumulatedDelta;
accumulatedDelta += aChange.Delta;
a = b;
b = a + 1;
}
}
}
// a points to the last surviving change
work[a].NewPosition = work[a].OldPosition + accumulatedDelta;
List<TextChange> result = new List<TextChange>();
if (differenceOptions.HasValue)
{
Requires.NotNull(textDifferencingService, nameof(textDifferencingService));
foreach (TextChange change in work)
{
if (change == null) continue;
// Make sure this is a replacement
if (change.OldLength == 0 || change.NewLength == 0)
{
result.Add(change);
continue;
}
if (change.OldLength >= TextModelOptions.DiffSizeThreshold ||
change.NewLength >= TextModelOptions.DiffSizeThreshold)
{
change.IsOpaque = true;
result.Add(change);
continue;
// too big to even attempt a diff. This is aimed at the reload-a-giant-file scenario
// where OOM during diff is a distinct possibility.
}
// Make sure to turn off IgnoreTrimWhiteSpace, since that doesn't make sense in
// the context of a minimal edit
StringDifferenceOptions options = new StringDifferenceOptions(differenceOptions.Value);
options.IgnoreTrimWhiteSpace = false;
IHierarchicalDifferenceCollection diffs;
if (before != null && after != null)
{
// Don't materialize the strings when we know the before and after snapshots. They might be really huge and cause OOM.
// We will take this path in the file reload case.
diffs = textDifferencingService.DiffSnapshotSpans(new SnapshotSpan(before, change.OldSpan),
new SnapshotSpan(after, change.NewSpan), options);
}
else
{
// We need to evaluate the old and new text for the differencing service
string oldText = change.OldText;
string newText = change.NewText;
if (string.Equals(oldText, newText, StringComparison.Ordinal))
{
// This change simply evaporates. This case occurs frequently in Venus and it is much
// better to short circuit it here than to fire up the differencing engine.
continue;
}
diffs = textDifferencingService.DiffStrings(oldText, newText, options);
}
// Keep track of deltas for the "new" position, for sanity check
int delta = 0;
// Add all the changes from the difference collection
result.AddRange(GetChangesFromDifferenceCollection(ref delta, change, change._oldText, change._newText, diffs));
// Sanity check
// If delta != 0, then we've constructed asymmetrical insertions and
// deletions, which should be impossible
Debug.Assert(delta == change.Delta, "Minimal edit delta should be equal to replaced text change's delta.");
}
}
// If we aren't computing minimal changes, then copy over the non-null changes
else
{
foreach (TextChange change in work)
{
if (change != null)
result.Add(change);
}
}
return result;
}