[LyX/master] Compare: do not duplicate shared affixes when collapsing a run (part of #6889)
Pavel Sanda
sanda at lyx.org
Tue Sep 8 18:10:42 UTC 2026
commit 7580192c0f1f699febd33b9aaa2800333a67f350
Author: Pavel Sanda <sanda at lyx.org>
Date: Mon Sep 7 11:46:17 2026 +0200
Compare: do not duplicate shared affixes when collapsing a run (part of #6889)
Extend character IVa phase - add postprocessing which keeps long shared
affix untouched.
Assisted-by: Claude Opus 4.8
---
src/Compare.cpp | 195 ++++++++++++++++++++++++++++++++++++++++++++++----------
1 file changed, 162 insertions(+), 33 deletions(-)
diff --git a/src/Compare.cpp b/src/Compare.cpp
index 8e84478073..79b6f3dbdf 100644
--- a/src/Compare.cpp
+++ b/src/Compare.cpp
@@ -64,6 +64,11 @@
* Prior art:
* - LibreOffice takes the opposite route - by default diffs whole words (so no word-level
* scatter), but has a ByChar mode as well.
+ * cf. its CommonSubseq::IgnoreIsolatedPieces, which drops isolated common runs
+ * <= nIgnoreLen (2 in char mode, 3 in word mode) and exempts the common prefix/suffix -
+ * the same small 2-3 char line and boundary exemption as our crumb in IVa. Unlike us it
+ * does no intra-word refinement, so a one-letter typo marks the whole word; lyx keeps
+ * it precise.
* - MS Word gives choice between char vs word level.
* - Google diff-match-patch keeps a char diff and post-processes it, like us.
*
@@ -118,18 +123,12 @@
* ------------------------------------------------------------------------------------------------------
* | beating -> boaring | b{e}[o]a{t}[r]ing | a (1) | collapse | {beating}[boaring] |
* ------------------------------------------------------------------------------------------------------
- *
- * * Prior art: cf. LibreOffice's CommonSubseq::IgnoreIsolatedPieces, which drops isolated common runs
- * <= nIgnoreLen (2 in char mode, 3 in word mode) and exempts the common prefix/suffix -
- * the same small 2-3 char line and boundary exemption as our crumb. Unlike us it does no
- * intra-word refinement, so a one-letter typo marks the whole word; lyx keeps it precise.
*
* * Possible further work:
- * We decide only on the interior crumb and do not consider the size of boundary survivors.
- * So clear case pre{heat}[boil] stays, but also less clear case a{lpha}[ztec] stays, when
- * "a" is likely just chance. We keep it now, as our main problem really isn't detection of
- * real edits, but rather fragmentation -- and unreadability, which follows. a{lpha}[ztec]
- * reads fine.
+ * The collapse decision looks only at the interior crumb, never at how long the boundary survivors
+ * are. So clear case pre{heat}[boil] stays, but also less clear case a{lpha}[ztec] stays, when "a"
+ * is likely just chance. We keep it now, as our main problem really isn't detection of real edits,
+ * but rather fragmentation -- and unreadability, which follows. a{lpha}[ztec] reads fine.
*
* If we implement check for this, we a) need new threshold to tune b) valuable typo edits
* can be lost when mistuned. At the end we really need more experience with this.
@@ -142,6 +141,59 @@
* Food for thought: when LO docs share the ancestry, their "Revision Save ID" tags which
* are recorded per edit session can actually track "real" edits and this whole game is suddenly
* solvable without guessing.
+ *
+ *
+ * * IVa postprocessing: Trimming the collapsed run
+ *
+ * Example of previous stage: trans{p}[f]or{t}[m] -> {transport}[transform].
+ * The detector above does not use boundary survivors - the evidence of scatter is
+ * survivor inside. Once collapse happens those shared boundary survivors ("trans")
+ * multiply, which is desired for short ones ("e" in {unique}[single]), but not nice
+ * for long ones (say >= 3 chars). So in this step we peel off the long common pre/suffix:
+ * {transport}[transform] -> trans{port}[form].
+ *
+ * So we will use one threshold, for both operations:
+ * interior survivor < 3 -> noise -> collapse through it
+ * boundary survivor >= 3 -> signal -> keep it, never duplicate it
+ *
+ * (The affixes must match in font as well, so a re-formatted stretch is never silently
+ * shown as unchanged.)
+ *
+ * Examples after trimming:
+ * --------------------------------------------------------------------------------------------------------------
+ * | old -> new | collapsed run | shared affix | after trimming |
+ * --------------------------------------------------------------------------------------------------------------
+ * | Some new footnote -> Footnote | {Some new footnote}[Footnote] | ootnote (7) | {Some new f}[F]ootnote |
+ * --------------------------------------------------------------------------------------------------------------
+ * | transport -> transform | {transport}[transform] | trans (5) | trans{port}[form] |
+ * --------------------------------------------------------------------------------------------------------------
+ * | transporting -> transforming | {transporting}[transforming] | trans (5), ing (3) | trans{port}[form]ing |
+ * --------------------------------------------------------------------------------------------------------------
+ * | beating -> boaring | {beating}[boaring] | b (1), ing (3) | {beat}[boar]ing |
+ * --------------------------------------------------------------------------------------------------------------
+ * | unique -> single | {unique}[single] | e (1) | {unique}[single] |
+ * --------------------------------------------------------------------------------------------------------------
+ * Affixes shorter than 3 are left alone - hence "b" and "e" above survive.
+ *
+ *
+ * * All IVa stages illustrated (transport -> transform):
+ *
+ * 1) Raw Myers: trans{p}[f]or{t}[m]
+ * Minimal, correct & unreadable.
+ *
+ * 2) The cluster = trans{p}[f]or{t}[m]
+ * Survivors: "trans" (5) touches the cluster start -> boundary survivor -> ignore
+ * "or" (2) has change on both sides -> interior survivor
+ *
+ * 3) Has interior crumb: "or" is interior and length 2 < 3 -> crumb -> collapse.
+ * The verdict is per cluster, all or nothing: {transport}[transform]
+ *
+ * 4) Trimming common affixes:
+ * common prefix "trans" (5 >= 3) -> kept unchanged
+ * rest "port" vs "form" -> no common suffix ("t" vs "m")
+ * giving trans{port}[form]
+ * The crumb "or" stays inside {port}[form]: trimming does not undo the collapse,
+ * it just doesn't duplicate what decision 2 already ignored.
*
**/
@@ -695,25 +747,31 @@ static bool traverseSnake(DocPair & p, DocRangePair const & range,
// +-- collapseClusters(par, ...) [IVa: within a word]
// |
// +-- for each cluster:
-// hasInteriorCrumb(cluster)? --yes--> rewriteAsRun(par, cluster)
-// --no---> keep as is
+// hasInteriorCrumb(cluster)?
+// -- no ---> keep as is
+// -- yes --> rewriteAsRun(par, cluster)
+// |
+// +-- affixesToKeep(old, new)
+// -- <3 --> duplicate into both parts
+// -- 3+ --> keep affix unchanged
//
//
// collapseClusters (within a word): a changed region together with the
// words it touches forms a cluster. If the characterwise diff inside a
// cluster is unreadable (it contains an unchanged piece in the cluster
-// interior shorter than min_interior_survivor), the cluster is collapsed
+// interior shorter than min_real_survivor), the cluster is collapsed
// into one continuous run: deleted old words followed by inserted new
-// words. A single contiguous edit within a word (e.g. a typo fix) only
-// has unchanged pieces touching the cluster boundary, so it is kept as
-// is.
+// words, except for long shared affixes, which are left unchanged.
+// A single contiguous edit within a word (e.g. a typo fix) only has
+// unchanged pieces touching the cluster boundary, so it is kept as is.
//
// The collapse duplicates the affected unchanged characters (they appear
// once in the deleted and once in the inserted part of the run), trading
-// mark precision for readability. Insets are never duplicated or moved:
-// clusters are split at inset positions, so a rewritten range never
-// contains an inset. Paragraph breaks are not crossed either, so all
-// rewrites are local to one paragraph.
+// mark precision for readability - except a long prefix/suffix shared by the two
+// versions, which is kept as unchanged text instead (see affixesToKeep).
+// Insets are never duplicated or moved: clusters are split at inset positions,
+// so a rewritten range never contains an inset. Paragraph breaks are not
+// crossed either, so all rewrites are local to one paragraph.
//
// The whole pass is skipped for CJK-type languages without whitespace word
// boundaries (Language::wordWrap() == false), where a single character
@@ -736,12 +794,76 @@ struct CharWithFont {
};
-/// Called when detector for scattered noise triggers.
+/// Threshold for "real shared text, not coincidence" inside word.
+/// The only knob of IVa, used at two separate stages:
+/// - interior survivor shorter than this -> a crumb, i.e. noise: collapse
+/// - boundary survivor at least this long -> signal: keep it, do not duplicate
+static pos_type const min_real_survivor = 3;
+
+
+/// How much of a collapsed run's shared affix should be kept as unchanged text.
+///
+/// oldtext / newtext are the same paragraph range in its two versions:
+/// the range holds trans{p}[f]or{t}[m]
+/// oldtext "transport" (every change rejected)
+/// newtext "transform" (every change accepted)
+///
+/// Identical start(/end) makes the continuous run print that text twice, once
+/// struck out and once inserted. affixesToKeep returns how much of it to keep
+/// unchanged instead:
+/// collapsed run after trimming returns shared affix
+/// {transport}[transform] trans{port}[form] {5, 0} "trans"
+/// {transporting}[transforming] trans{port}[form]ing {5, 3} "trans" + "ing"
+/// {Some new footnote}[Footnote] {Some new f}[F]ootnote {0, 7} "ootnote"
+///
+/// An affix shorter than min_real_survivor stays inside the collapsed run:
+/// {unique}[single] {unique}[single] {0, 0} "e"
+/// {beating}[boaring] {beat}[boar]ing {0, 3} "b" + "ing"
+///
+/// Fonts have to match as well, so a re-formatted stretch is never shown unchanged:
+/// "trans" upright vs "trans" italic {0, 0}
+///
+/// Returns the {prefix, suffix} character counts, 0 where nothing is kept.
+static pair<pos_type, pos_type> affixesToKeep(vector<CharWithFont> const & oldtext,
+ vector<CharWithFont> const & newtext)
+{
+ pos_type const osize = static_cast<pos_type>(oldtext.size());
+ pos_type const nsize = static_cast<pos_type>(newtext.size());
+ pos_type const max_affix = min(osize, nsize);
+ auto const same = [](CharWithFont const & a, CharWithFont const & b) {
+ return a.c == b.c && a.font == b.font;
+ };
+
+ pos_type prefix = 0;
+ while (prefix < max_affix && same(oldtext[prefix], newtext[prefix]))
+ ++prefix;
+ if (prefix < min_real_survivor)
+ prefix = 0;
+
+ // stop at the prefix, so that prefix and suffix cannot overlap
+ pos_type suffix = 0;
+ while (suffix < max_affix - prefix
+ && same(oldtext[osize - 1 - suffix], newtext[nsize - 1 - suffix]))
+ ++suffix;
+ if (suffix < min_real_survivor)
+ suffix = 0;
+
+ return {prefix, suffix};
+}
+
+
+/// Rewrite called when detector for scattered noise triggers.
/// scattered input: par[begin:end] = "{u}[si]n{iqu}[gl]e"
/// clean output: par[begin:end2] = "{unique}[single]"
/// Rewrites the range [begin, end) of par, which may hold any mixture of unchanged,
/// deleted and inserted positions, as one continuous run {old}[new], unchanged
/// chars duplicated into both parts. The range must not contain insets.
+///
+/// An affix common to the old and the new text is not duplicated but kept as unchanged
+/// text, provided it is long enough. The previous detector triggers only on *interior*, not
+/// boundary survivors, and to be in sync this rewrite does not touch (long enough) affix:
+/// scattered input: par[begin:end] = "trans{p}[f]or{t}[m]" (affix="trans")
+/// clean output: par[begin:end2] = "trans{port}[form]"
static void rewriteAsRun(Paragraph & par, pos_type begin, pos_type end,
BufferParams const & bparams, int author)
{
@@ -764,27 +886,34 @@ static void rewriteAsRun(Paragraph & par, pos_type begin, pos_type end,
newtext.push_back(cf);
}
- // 2. delete scattered range
+ // 2. keep a long enough shared affix instead of duplicating it.
+ // Trimming a shorter one would re-create the very scatter we remove here.
+ pos_type const osize = static_cast<pos_type>(oldtext.size());
+ pos_type const nsize = static_cast<pos_type>(newtext.size());
+ auto const [prefix, suffix] = affixesToKeep(oldtext, newtext);
+
+ // 3. delete scattered range
par.eraseChars(begin, end, false);
- // 3. insert clean range
+ // 4. insert clean range
+ Change const unchanged(Change::UNCHANGED);
Change const deleted(Change::DELETED, author);
Change const inserted(Change::INSERTED, author);
pos_type pos = begin;
- for (CharWithFont const & cf : oldtext)
- par.insertChar(pos++, cf.c, cf.font, deleted);
- for (CharWithFont const & cf : newtext)
- par.insertChar(pos++, cf.c, cf.font, inserted);
+ for (pos_type i = 0; i < prefix; ++i)
+ par.insertChar(pos++, oldtext[i].c, oldtext[i].font, unchanged);
+ for (pos_type i = prefix; i < osize - suffix; ++i)
+ par.insertChar(pos++, oldtext[i].c, oldtext[i].font, deleted);
+ for (pos_type i = prefix; i < nsize - suffix; ++i)
+ par.insertChar(pos++, newtext[i].c, newtext[i].font, inserted);
+ for (pos_type i = osize - suffix; i < osize; ++i)
+ par.insertChar(pos++, oldtext[i].c, oldtext[i].font, unchanged);
}
-/// In-word "real shared text, not coincidence" threshold.
-/// We need to collapse diff for crumb < threshold.
-static pos_type const min_interior_survivor = 3;
-
/// Does the cluster [cbegin, cend) contain a crumb - an interior survivor
-/// (changed text on both sides) shorter than min_interior_survivor? A survivor
+/// (changed text on both sides) shorter than min_real_survivor? A survivor
/// touching a cluster edge is a boundary survivor (the cluster's shared
/// prefix/suffix) and does not count.
///
@@ -813,7 +942,7 @@ static bool hasInteriorCrumb(Paragraph const & par,
// a boundary survivor is the real shared prefix/suffix, not a crumb
bool interior_only = sbegin > cbegin && pos < cend;
// a short unchanged run is coincidental overlap, not meaningful shared text
- bool too_short = pos - sbegin < min_interior_survivor;
+ bool too_short = pos - sbegin < min_real_survivor;
if (interior_only && too_short)
return true;
}
More information about the lyx-cvs
mailing list