computeTextDelta function
Computes the single contiguous TextDelta that turns oldText into
newText, or null when they are equal.
Uses common prefix/suffix trimming — O(n) worst case and O(edit size) for the typical edit-at-caret — instead of a full diff. Offsets are in UTF-16 code units, and both boundaries are snapped to a code-point boundary, so a surrogate pair is never split between the kept and the replaced region.
When the resulting collapsed caret (the selection offset after the
edit) is known, it disambiguates edits that touch a run of identical
characters: inserting a \n right before an existing \n, typing a space
before a space, etc. Prefix/suffix trimming alone is ambiguous there — the
two candidate positions produce the same string but a different edit — and
plain greedy trimming slides the edit past the caret, attaching the new
characters to the wrong side. Anchoring the edit so it ends at caret
keeps it where the user actually typed. Pass null (the default) to skip
this, e.g. when mapping a remote change rather than a local gesture.
Non-contiguous edits (which no single editing gesture produces) collapse into one delta spanning both, which is still correct — just coarser.
Implementation
TextDelta? computeTextDelta(String oldText, String newText, {int? caret}) {
if (oldText == newText) {
return null;
}
final oldLength = oldText.length;
final newLength = newText.length;
final maxPrefix = oldLength < newLength ? oldLength : newLength;
var start = 0;
while (start < maxPrefix &&
oldText.codeUnitAt(start) == newText.codeUnitAt(start)) {
start++;
}
final prefix = start;
// Break the identical-run ambiguity toward the caret: the inserted run must
// end at [caret], so the kept prefix cannot reach past it. A net insertion
// of `k` characters starts `k` before the caret; a deletion/replacement
// starts at the caret. We only ever *shorten* the prefix here — the freed
// characters fold into the changed region, so the delta stays string-exact
// — and then re-derive the suffix below against the corrected boundary.
if (caret != null && caret >= 0 && caret <= newLength) {
final netInsert = newLength > oldLength ? newLength - oldLength : 0;
final cap = caret - netInsert;
if (cap < start) {
start = cap < 0 ? 0 : cap;
}
}
var endOld = oldLength;
var endNew = newLength;
while (true) {
while (endOld > start &&
endNew > start &&
oldText.codeUnitAt(endOld - 1) == newText.codeUnitAt(endNew - 1)) {
endOld--;
endNew--;
}
// An embed the fold would carry into the inserted text is kept, not
// deleted and typed again.
final foldEnd = prefix < endNew ? prefix : endNew;
var embed = foldEnd - 1;
while (embed >= start && newText.codeUnitAt(embed) != _objectReplacement) {
embed--;
}
if (embed < start) {
break;
}
start = embed + 1;
endOld = oldLength;
endNew = newLength;
}
// Never split a surrogate pair: widen the replaced region instead.
if (start > 0 && RuneOffsets.isHighSurrogate(oldText.codeUnitAt(start - 1))) {
start--;
}
if (endOld < oldLength &&
RuneOffsets.isLowSurrogate(oldText.codeUnitAt(endOld))) {
endOld++;
endNew++;
}
return TextDelta(
index: start,
deleted: endOld - start,
inserted: newText.substring(start, endNew),
);
}