[LyX/master] Compare: collapse scattered within-word change runs (#6889)
Pavel Sanda
sanda at lyx.org
Fri Sep 4 19:49:11 UTC 2026
commit ca56e5a0676ad7df5f74fe79ddf3e677b4e727ba
Author: Pavel Sanda <sanda at lyx.org>
Date: Wed Aug 26 23:53:04 2026 +0200
Compare: collapse scattered within-word change runs (#6889)
Fixup compare scattered output (bug #6889).
Myers postprocessing to refine diff from mathematically minimal into human
readable. This adds first pass (IVa) over fragmented words and rewrites them
as a continuous text while leaving single-char typos in place.
The next planned pass (IVb) will be over words.
Assisted-by: Claude Fable 5
---
src/Compare.cpp | 317 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 316 insertions(+), 1 deletion(-)
diff --git a/src/Compare.cpp b/src/Compare.cpp
index 01c5c87469..8e84478073 100644
--- a/src/Compare.cpp
+++ b/src/Compare.cpp
@@ -51,7 +51,99 @@
* diffInset case ("very rare case" mentioned in diff_i), tracked as #9395.
* This is now fixed by processSnake recursion on L_ses == 0 and closes both
* problems above. I. should be now redundant and ripe for the waste bin.
- */
+ *
+ * IV. Myers postprocessing refining the diff on non-CJK languages
+ * Problem:
+ * The previous steps create mathematically minimal but frequently unreadable diff -
+ * it scatters tiny CT fragments across words and sentences. Example from bug #6889:
+ * instead of {unique}[single] the results looks like {u}[si]n{iqu}[gl]e.
+ * Approach:
+ * First refine for single chars and later we switch to words (for performance reasons)
+ * while leaving the char-level diffs functional so small char-level typos are easily seen.
+ *
+ * Prior art:
+ * - LibreOffice takes the opposite route - by default diffs whole words (so no word-level
+ * scatter), but has a ByChar mode as well.
+ * - MS Word gives choice between char vs word level.
+ * - Google diff-match-patch keeps a char diff and post-processes it, like us.
+ *
+ * IVa. Detector for "this word's character diff is the scattered-noise"
+ *
+ * * First some terminology:
+ * "Single continuous run" - at most one deleted block, then at most one inserted block, in that order
+ * - {...} - pure deletion
+ * - [...] - pure insertion
+ * - {...}[...] - deletion immediately followed by insertion (a substitution)
+ *
+ * - []{} does not occur (compare always emits delete first)
+ * - mixtures {}[]{}[] do not occur (compare always builds whole subrange as deleted/inserted -
+ * mixture always occurs with snake inside (>=1 unchanged character) eg {}[]s{}[], but
+ * then it's no more continuous run.
+ *
+ * "Unchanged interior" - a run of unchanged characters (="survivor") that touches neither end
+ * of the word - i.e. it has changed text on both sides.
+ *
+ * Note: our matcher is font- and language-aware so every survivor is, by
+ * construction, font- and language-identical between old and new.
+ * We deliberately do not use case of differently formatted survivor
+ * as a signal for "keep"; it's rare and complicates code.
+ *
+ * "Crumb" - an interior unchanged piece of 1-2 characters (this 3 chars threshold is the only knob
+ * in our collapse detector).
+ *
+ * * Now the heuristics:
+ * Keep char-diff for: edits are single continuous run (one consecutive {del}[ins] run) OR
+ * "real shared text, not coincidence" - edits are separated by substantial
+ * (>= 3 char) unchanged stretches.
+ * Otherwise reject diff, collapse as whole word diff {old}[new].
+ *
+ * * Consequences (Lx stands for x-row of the examples table)
+ * 1. A single contiguous edit has only boundary (prefix/suffix) survivors, so it is always kept ->
+ * typo fixes stay character-precise: (L1) correct[i]on.
+ * 2. A substantial unchanged interior is kept: (L2) {d}[m]isprove{n}[d] keeps the real shared stem
+ * isprove even though both ends changed.
+ * 3. A crumb triggers a whole-word collapse: (L3) {beating}[boaring].
+ * 4. The decision is per-word all-or-nothing: one interior crumb collapses the entire word,
+ * because a half-cleaned word still reads as fragments.
+ * 5. The trigger is the size of the interior unchanged survivor, not the amount of change - so a
+ * small change with a solid survivor is kept (L2), while a small change straddling a crumb is collapsed (L3).
+ *
+ * * Examples:
+ * ------------------------------------------------------------------------------------------------------
+ * | old -> new | raw character diff | unchanged interior | verdict | result |
+ * ------------------------------------------------------------------------------------------------------
+ * | correcton -> correction | correct[i]on | none (all boundary) | keep | correct[i]on |
+ * ------------------------------------------------------------------------------------------------------
+ * | disproven -> misproved | {d}[m]isprove{n}[d] | isprove (7) | keep | {d}[m]isprove{n}[d] |
+ * ------------------------------------------------------------------------------------------------------
+ * | 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.
+ *
+ * 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.
+ * ATM we try to win the case with easy case with strong signal (crumb inside/collapsing typo)
+ * and leave the hard/more ambigous case left because the win is small ("still reads fine").
+ *
+ * Libreoffice situation: collapse to a whole-word replacement when the two words are
+ * too dissimilar - "< X% similar -> replace the word"). Make sense, but single typos
+ * in words are missed and replaced by whole word CT in default case, BUT:
+ * 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.
+ *
+ **/
#include <config.h>
@@ -63,6 +155,7 @@
#include "Changes.h"
#include "CutAndPaste.h"
#include "Font.h"
+#include "Language.h"
#include "insets/InsetText.h"
@@ -345,6 +438,10 @@ private:
/// recursively be applied to any InsetTexts that are within the snake.
void processSnake(DocRangePair const & rp);
+ /// Fix scattering of Myers' output (bug #6889). Called when the
+ /// paragraph list of a text level is complete (the end of diff/Inset).
+ void cleanupChangeRuns(ParagraphList & pars);
+
/// Writes the range to the destination buffer
void writeToDestBuffer(DocRange const & range,
Change::Type type = Change::UNCHANGED);
@@ -582,6 +679,204 @@ static bool traverseSnake(DocPair & p, DocRangePair const & range,
}
+/////////////////////////////////////////////////////////////////////
+//
+// Cleanup of the scattered comparison output (bug #6889)
+//
+// Structure of the cleanup:
+//
+// diff() -------+
+// diffInset() --+--> cleanupChangeRuns(*dest_pars_)
+//
+// cleanupChangeRuns(pars)
+// |
+// +-- for each paragraph par:
+// |
+// +-- collapseClusters(par, ...) [IVa: within a word]
+// |
+// +-- for each cluster:
+// hasInteriorCrumb(cluster)? --yes--> rewriteAsRun(par, cluster)
+// --no---> keep as is
+//
+//
+// 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
+// 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.
+//
+// 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.
+//
+// The whole pass is skipped for CJK-type languages without whitespace word
+// boundaries (Language::wordWrap() == false), where a single character
+// already is a word and the character diff needs no fixing.
+//
+/////////////////////////////////////////////////////////////////////
+
+/// A position range within a paragraph.
+struct PosRange {
+ pos_type begin;
+ pos_type end;
+};
+
+
+/// We need to preserve each character's font across the
+/// erase-and-reinsert that rewriteAsRun performs.
+struct CharWithFont {
+ char_type c;
+ Font font;
+};
+
+
+/// 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.
+static void rewriteAsRun(Paragraph & par, pos_type begin, pos_type end,
+ BufferParams const & bparams, int author)
+{
+ // The callers guarantee an inset-free range.
+ LASSERT(!par.hasInsets(begin, end), return);
+
+ // what you get if you reject every change, "unique"
+ vector<CharWithFont> oldtext;
+ // what you get if you accept every change, "single"
+ vector<CharWithFont> newtext;
+
+ // 1. prepare clean range
+ for (pos_type pos = begin; pos < end; ++pos) {
+ CharWithFont const cf{par.getChar(pos),
+ par.getFontSettings(bparams, pos)};
+ Change::Type const type = par.lookupChange(pos).type;
+ if (type != Change::INSERTED) //unchanged + deleted
+ oldtext.push_back(cf);
+ if (type != Change::DELETED) //unchanged + inserted
+ newtext.push_back(cf);
+ }
+
+ // 2. delete scattered range
+ par.eraseChars(begin, end, false);
+
+ // 3. insert clean range
+ 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);
+}
+
+
+/// 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
+/// touching a cluster edge is a boundary survivor (the cluster's shared
+/// prefix/suffix) and does not count.
+///
+/// Clear ones:
+/// Input: b{e}[o]a{t}[r]ing -> true (interior survivor "a", 1 char, is a crumb)
+/// Input: {d}[m]isprove{n}[d] -> false (interior survivor "isprove", 7 chars, kept)
+/// Input: pre{heat}[boil] -> false (boundary prefix survivor "pre", exempt)
+/// Input: {jump}[walk]ing -> false (boundary suffix survivor "ing", exempt)
+///
+/// Less clear ones (see the "further work" in architecture description):
+/// Input: a{lpha}[ztec] -> false (boundary prefix survivor "a", exempt)
+/// Input: {c}[b]at -> false (boundary suffix survivor "at", exempt)
+static bool hasInteriorCrumb(Paragraph const & par,
+ pos_type cbegin, pos_type cend)
+{
+ pos_type pos = cbegin;
+ while (pos < cend) {
+ if (par.isChanged(pos)) {
+ ++pos;
+ continue;
+ }
+ pos_type const sbegin = pos; // survivor: [sbegin, pos)
+ while (pos < cend && !par.isChanged(pos))
+ ++pos;
+
+ // 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;
+ if (interior_only && too_short)
+ return true;
+ }
+ return false;
+}
+
+
+/// Collapse unreadable character changes at word boundaries.
+///
+/// A "cluster" here means the text span we decide in this pass (and may collapse):
+/// one word, or several words when the separators between them were
+/// themselves changed. The cluster boundaries define interior for hasInteriorCrumb
+/// (i.e. the specification's survivor with "changed text on both sides").
+///
+/// the {cat}[dog] sat -> one cluster = one word: the unchanged spaces around
+/// {cat}[dog] delimit it, so "the" and "sat" stay out
+/// and are not clusters themselves either.
+/// {Some new f}[F]ootnote -> the whole string is ONE cluster across three words:
+/// the deleted run swallows the spaces between them,
+/// so nothing delimits - which is why a cluster is not
+/// just "a word".
+/// in -> out:
+/// "the {u}[si]n{iqu}[gl]e correct[i]on" -> "the {unique}[single] correct[i]on"
+/// "{S}[F]o{me new fo}otnote" -> "{Some new footnote}[Footnote]"
+static void collapseClusters(Paragraph & par, BufferParams const & bparams,
+ int author)
+{
+ // A position takes part in a cluster if it is changed or if it is a
+ // word character; unchanged word separators (spaces, punctuation,
+ // ...) delimit the clusters. Insets always do, whatever their change
+ // status, because a rewrite cannot move them.
+ pos_type psize = par.size();
+ vector<PosRange> clusters;
+ pos_type pos = 0;
+ while (pos < psize) {
+ if (par.isInset(pos) //insets are hard anchors
+ || (!par.isChanged(pos) && par.isWordSeparator(pos))) { //*unedited* space/punctuation
+ ++pos;
+ // this position is gap between clusters, candidate for cluster opens on next non-separator
+ continue;
+ }
+ pos_type cbegin = pos;
+ // for candidate to become real cluster it needs to contain CT
+ bool has_change = false;
+ while (pos < psize && !par.isInset(pos)
+ && (par.isChanged(pos) || !par.isWordSeparator(pos))) {
+ has_change |= par.isChanged(pos);
+ ++pos;
+ }
+ if (has_change)
+ clusters.push_back(PosRange{cbegin, pos});
+ }
+
+ // Go through the collected clusters and collapse the scattered ones.
+ // Rewrite changes par length, thus go from back to front so the positions remain valid.
+ vector<PosRange>::const_reverse_iterator it = clusters.rbegin();
+ for (; it != clusters.rend(); ++it) {
+ if (hasInteriorCrumb(par, it->begin, it->end))
+ rewriteAsRun(par, it->begin, it->end, bparams, author);
+ }
+}
+
+
/////////////////////////////////////////////////////////////////////
//
// Compare::Impl
@@ -589,6 +884,22 @@ static bool traverseSnake(DocPair & p, DocRangePair const & range,
/////////////////////////////////////////////////////////////////////
+void Compare::Impl::cleanupChangeRuns(ParagraphList & pars)
+{
+ BufferParams const & bparams = dest_buf_->params();
+
+ // CJK-type languages have no whitespace word boundaries
+ if (!bparams.language->wordWrap())
+ return;
+
+ int const author = compare_.options_.author;
+
+ ParagraphList::iterator it = pars.begin();
+ for (; it != pars.end(); ++it)
+ collapseClusters(*it, bparams, author);
+}
+
+
void Compare::Impl::furthestDpathKdiagonal(int D, int k,
DocRangePair const & rp, Direction direction)
{
@@ -777,6 +1088,8 @@ bool Compare::Impl::diff(Buffer const * new_buf, Buffer const * old_buf,
if (!rp_new.o.empty() || !rp_new.n.empty())
diff_i(rp_new);
+ cleanupChangeRuns(*dest_pars_);
+
for (pit_type p = 0; p < (pit_type)dest_pars_->size(); ++p) {
(*dest_pars_)[p].setInsetBuffers(const_cast<Buffer &>(*dest_buf));
(*dest_pars_)[p].setInsetOwner(&dest_buf_->inset());
@@ -871,6 +1184,8 @@ void Compare::Impl::diffInset(Inset * inset, DocPair const & p)
diff_i(rp);
--nested_inset_level_;
+ cleanupChangeRuns(*dest_pars_);
+
dest_pars_ = backup_dest_pars;
}
More information about the lyx-cvs
mailing list