On Fri, Sep 04, 2026 at 09:52:28PM +0200, Pavel Sanda wrote:
> > You might want to look at tests/*expected files if you want to check how
> > "correct"
> > versions look now. I am currently aware of one more possible addition,
> > which is visible
> > in basic_inset test case:
> > raw Myers: {S}[F]o{me new fo}otnote text <- the scatter (lone "o"
> > crumb)
> > IVa now: {Some new footnote}[Footnote] text <- collapses the whole
> > cluster
> > further work: {Some new f}[F]ootnote text <- keep "ootnote text",
> > mark only the real edits
> >
> > but I keep trimming the common prefix/suffix for some later work.
Now the further work, see the attached.
Pavel
>From 6e03346bc5f2d89b77190361107de3e0b986ceb1 Mon Sep 17 00:00:00 2001
From: Pavel Sanda <[email protected]>
Date: Mon, 7 Sep 2026 00:29:21 +0200
Subject: [PATCH 1/2] 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 | 170 +++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 146 insertions(+), 24 deletions(-)
diff --git a/src/Compare.cpp b/src/Compare.cpp
index 8e84478073..9e6e4dc4d0 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.
*
**/
@@ -702,7 +754,7 @@ static bool traverseSnake(DocPair & p, DocRangePair const & range,
// 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
@@ -736,12 +788,75 @@ 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. keptAffixes 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> keptAffixes(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 +879,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] = keptAffixes(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 +935,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;
}
--
2.39.5
>From d6bb5e84abef98131c8519ee95df3d146f95602f Mon Sep 17 00:00:00 2001
From: Pavel Sanda <[email protected]>
Date: Mon, 7 Sep 2026 00:29:21 +0200
Subject: [PATCH 2/2] Compare tests: add cases for IVa add postprocessing
Assisted-by: Claude Opus 4.8
---
.../affix_trim/diffs.expected.lyx | 132 ++++++++++++++++++
.../compare_tests/affix_trim/new.lyx | 104 ++++++++++++++
.../compare_tests/affix_trim/old.lyx | 104 ++++++++++++++
.../basic_insets/diffs.expected.lyx | 6 +-
4 files changed, 343 insertions(+), 3 deletions(-)
create mode 100644 development/batchtests/compare_tests/affix_trim/diffs.expected.lyx
create mode 100644 development/batchtests/compare_tests/affix_trim/new.lyx
create mode 100644 development/batchtests/compare_tests/affix_trim/old.lyx
diff --git a/development/batchtests/compare_tests/affix_trim/diffs.expected.lyx b/development/batchtests/compare_tests/affix_trim/diffs.expected.lyx
new file mode 100644
index 0000000000..b45cb2e807
--- /dev/null
+++ b/development/batchtests/compare_tests/affix_trim/diffs.expected.lyx
@@ -0,0 +1,132 @@
+#LyX 2.6 created this file. For more info see https://www.lyx.org/
+\lyxformat 660
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass article
+\use_default_options true
+\maintain_unincluded_children no
+\language newzealand
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package aligned-overset 0
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification default
+\crossref_package refstyle
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\backgroundcolor none
+\fontcolor none
+\notefontcolor lightgray
+\boxbgcolor red
+\table_border_color default
+\table_odd_row_color default
+\table_even_row_color default
+\table_alt_row_colors_start 1
+\index Index
+\shortcut idx
+\color #ff008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\parfillskip "default" ""
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes true
+\output_changes true
+\change_bars false
+\postpone_fragile_content true
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\docbook_mathml_version 0
+\author 1660427103 "Document Comparison"
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+The trans
+\change_deleted 1660427103 1788732869
+port
+\change_inserted 1660427103 1788732869
+form
+\change_unchanged
+ layer is fast.
+\end_layout
+
+\begin_layout Standard
+We are trans
+\change_deleted 1660427103 1788732869
+port
+\change_inserted 1660427103 1788732869
+form
+\change_unchanged
+ing data now.
+\end_layout
+
+\begin_layout Standard
+This result is
+\change_deleted 1660427103 1788732869
+unique
+\change_inserted 1660427103 1788732869
+single
+\change_unchanged
+.
+\end_layout
+
+\end_body
+\end_document
diff --git a/development/batchtests/compare_tests/affix_trim/new.lyx b/development/batchtests/compare_tests/affix_trim/new.lyx
new file mode 100644
index 0000000000..c7d7594024
--- /dev/null
+++ b/development/batchtests/compare_tests/affix_trim/new.lyx
@@ -0,0 +1,104 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 599
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass article
+\use_default_options true
+\maintain_unincluded_children no
+\language newzealand
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content true
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+
+The transform layer is fast.
+\end_layout
+
+\begin_layout Standard
+
+We are transforming data now.
+\end_layout
+
+\begin_layout Standard
+
+This result is single.
+\end_layout
+
+
+\end_body
+\end_document
diff --git a/development/batchtests/compare_tests/affix_trim/old.lyx b/development/batchtests/compare_tests/affix_trim/old.lyx
new file mode 100644
index 0000000000..8a2e27b9ae
--- /dev/null
+++ b/development/batchtests/compare_tests/affix_trim/old.lyx
@@ -0,0 +1,104 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 599
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass article
+\use_default_options true
+\maintain_unincluded_children no
+\language newzealand
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content true
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+
+The transport layer is fast.
+\end_layout
+
+\begin_layout Standard
+
+We are transporting data now.
+\end_layout
+
+\begin_layout Standard
+
+This result is unique.
+\end_layout
+
+
+\end_body
+\end_document
diff --git a/development/batchtests/compare_tests/basic_insets/diffs.expected.lyx b/development/batchtests/compare_tests/basic_insets/diffs.expected.lyx
index 0759c62b36..4d056d0b66 100644
--- a/development/batchtests/compare_tests/basic_insets/diffs.expected.lyx
+++ b/development/batchtests/compare_tests/basic_insets/diffs.expected.lyx
@@ -105,11 +105,11 @@ status open
\begin_layout Plain Layout
\change_deleted 1660427103 1786609652
-Some new footnote
+Some new f
\change_inserted 1660427103 1786609652
-Footnote
+F
\change_unchanged
- text
+ootnote text
\end_layout
\end_inset
--
2.39.5
--
lyx-devel mailing list
[email protected]
https://lists.lyx.org/mailman/listinfo/lyx-devel
