[LyX/master] Slow start on refactor of the Comparison feature.

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