commit 281c6ffee5a84bd90d348a8e23f1b379ca9ccb2b
Author: Pavel Sanda <[email protected]>
Date: Mon Jul 20 01:59:28 2026 +0200
Slow start on refactor of the Comparison feature.
Write-up is mine but it was really Claude who helped to march
through the code and map it onto classical Myers primitives.
---
src/Compare.cpp | 43 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 43 insertions(+)
diff --git a/src/Compare.cpp b/src/Compare.cpp
index 09ae6b5ef4..fe2d851349 100644
--- a/src/Compare.cpp
+++ b/src/Compare.cpp
@@ -8,6 +8,49 @@
* Full author contact details are available in file CREDITS.
*/
+/**
+ * The current architecture of Comparison algorithm:
+ *
+ * We use variant of Myers algorithm. It gets more complicated because insets
can
+ * be recursive - each level of recursion needs to be flattened and run as
single
+ * instance of Myers.
+ *
+ * To keep running on single level we must introduce shallow match - the
algorithm
+ * is happy to match overall structure of text and insets but does not look
inside
+ * the insets - that's left for separate recursive run.
+ *
+ *
+ * Currently three levels of processing:
+ *
+ * I. Initial diff() kick-off
+ * - finds initial forward snake and processSnake (III)
+ * - diff_i of the remaining
+ *
+ * II. Myers recursive core diff_i()
+ * 1. Finds bidirectionally middle snake from ends to the middle of the
given range
+ * -> L_ses - length of the shortest edit script
+ * 2.
+ * a) all equal (shallow match, L_ses == 0, default for empty snake) ->
copy back
+ * b) all different (middle_snake.o.empty) -> give back old as deleted,
new as inserted
+ * c) proper snake -> Divide and conquer:
+ * diff_i(before snake)
+ * processSnake(snake)
+ * diff_i(after snake)
+ *
+ * III. Process shallow-matched content (processSnake)
+ * - copy all paragraphs
+ * - for each editable inset in the copy -> diff_i (via diffInset + some
iterators magic)
+ * - copy -> destination buffer
+ *
+ *
+ * Notes: AFAICS from Myers point of view II. & III. should be enough and it's
not clear
+ * from comments or commits why bother with I.
+ * Attempt to mind-read Vincent: If there is shallow-match right on the
top level
+ * diff_i does *not* recurse into insets and would miss changes. This
is fixed by
+ * processSnake in I. -- which is just band-aid and explodes in more
nested diffInset
+ * case ("very rare case" mentioned in diff_i), now tracked as #9395.
+ */
+
#include <config.h>
#include "Compare.h"
--
lyx-cvs mailing list
[email protected]
https://lists.lyx.org/mailman/listinfo/lyx-cvs
