[sdk/kommit] /: Fix LCS alghorithm

Git commit 1d8c7bfec16167cba4a8ec53cca90c1638366b8f by Hamed Masafi.
Committed on 18/08/2026 at 15:27.
Pushed by hamedmasafi into branch 'master'.

Fix LCS alghorithm

M  +1    -0    .gitignore
M  +15   -20   src/libkommitdiff/lcs.cpp
M  +31   -37   src/libkommitdiff/lcs.h

https://invent.kde.org/sdk/kommit/-/commit/1d8c7bfec16167cba4a8ec53cca90c1638366b8f

diff --git a/.gitignore b/.gitignore
index 69495346..f77ebdbf 100644
--- a/.gitignore
+++ b/.gitignore
@@ -105,3 +105,4 @@ _packages/
 /.clang-format
 /compile_commands.json
 .cache
+.qtcreator/
diff --git a/src/libkommitdiff/lcs.cpp b/src/libkommitdiff/lcs.cpp
index 439a2b94..d4dde8cc 100644
--- a/src/libkommitdiff/lcs.cpp
+++ b/src/libkommitdiff/lcs.cpp
@@ -74,6 +74,7 @@ Solution longestCommonSubsequence(const QStringList &source, const QStringList &
 {
     Array2<int> l(source.size() + 1, target.size() + 1);
 
+    // 1. ساخت ماتریس LCS
     for (int i = 0; i <= source.count(); i++) {
         for (int j = 0; j <= target.count(); j++) {
             if (i == 0 || j == 0) {
@@ -86,36 +87,30 @@ Solution longestCommonSubsequence(const QStringList &source, const QStringList &
         }
     }
 
+    // 2. بازگشت به عقب (Backtracking) برای یافتن مسیر تطابق
     int i = source.count();
     int j = target.count();
     Solution r;
 
-    int si{-1};
-    int sj{-1};
-
     while (i > 0 && j > 0) {
         if (isEqual(source.at(i - 1), target.at(j - 1))) {
-            r.prepend(qMakePair(i - 1, j - 1));
-            i--;
-            j--;
-            si = i;
-            sj = j;
-        } else {
-            if (si != -1 && sj != -1) { }
-
-            int n = maxIn(l(i - 1, j), l(i, j - 1), l(i - 1, j - 1));
-            switch (n) {
-            case 1:
-                i--;
-                break;
-            case 2:
+            // نکته کلیدی اینجاست:
+            // اگر طول LCS با نادیده گرفتن عنصر فعلی target یکسان باشد، یعنی این عنصر
+            // جزو بهترین تطابق نیست. با انجام j--، الگوریتم مجبور می‌شود به عقب برگردد
+            // و اولین وقوع این خط را پیدا کند. این کار باعث گروه‌بندی صحیح خطوط اضافه
+            // شده در انتها می‌شود و از پراکندگی آن‌ها جلوگیری می‌کند.
+            if (l(i, j) == l(i, j - 1)) {
                 j--;
-                break;
-            default:
+            } else {
+                r.prepend(qMakePair(i - 1, j - 1));
                 i--;
                 j--;
-                break;
             }
+        } else if (l(i - 1, j) >= l(i, j - 1)) {
+            // ترجیح دادن i-- در حالت تساوی، یک استاندارد رایج برای تولید Diff پایدار است
+            i--;
+        } else {
+            j--;
         }
     }
 
diff --git a/src/libkommitdiff/lcs.h b/src/libkommitdiff/lcs.h
index 2e606eb4..7be8e998 100644
--- a/src/libkommitdiff/lcs.h
+++ b/src/libkommitdiff/lcs.h
@@ -53,6 +53,7 @@ template<typename T>
 {
     Array2<int> l(left.size() + 1, right.size() + 1);
 
+    // 1. ساخت ماتریس LCS
     for (int i = 0; i <= left.count(); i++) {
         for (int j = 0; j <= right.count(); j++) {
             if (i == 0 || j == 0) {
@@ -65,53 +66,46 @@ template<typename T>
         }
     }
 
+    // 2. بازگشت به عقب (Backtracking) برای یافتن Chunkهای تطابق
     int i = left.count();
     int j = right.count();
     QList<LcsResult> result;
 
     while (i > 0 && j > 0) {
         if (equals(left.at(i - 1), right.at(j - 1))) {
-            int leftEnd = i - 1;
-            int rightEnd = j - 1;
-            int leftStart = leftEnd;
-            int rightStart = rightEnd;
-
-            // Move diagonally while elements match
-            while (i > 0 && j > 0 && equals(left.at(i - 1), right.at(j - 1))) {
-                --i;
-                --j;
-                leftStart = i;
-                rightStart = j;
+            // نکته کلیدی اصلاح:
+            // اگر طول LCS با نادیده گرفتن عنصر فعلی از right (یا left) یکسان باشد،
+            // یعنی این عنصر جزو "ضروری‌ترین" تطابق‌ها نیست. با عقب گرد (j-- یا i--)،
+            // الگوریتم مجبور می‌شود به عقب برگردد و اولین وقوع ممکن را پیدا کند.
+            // این کار باعث می‌شود آکولادهای پایانی به درستی به بلوک اصلی خود گره بخورند
+            // و بلوک‌های جدید به صورت یکپارچه در انتها به عنوان Insert شناسایی شوند.
+            if (l(i, j) == l(i, j - 1)) {
+                j--;
+            } else if (l(i, j) == l(i - 1, j)) {
+                i--;
+            } else {
+                // این یک تطابق ضروری است. حالا تمام خطوط متوالی یکسان را پیدا کن (Chunk)
+                int leftEnd = i - 1;
+                int rightEnd = j - 1;
+                int leftStart = leftEnd;
+                int rightStart = rightEnd;
+
+                while (i > 0 && j > 0 && equals(left.at(i - 1), right.at(j - 1))) {
+                    --i;
+                    --j;
+                    leftStart = i;
+                    rightStart = j;
+                }
+
+                result.prepend({leftStart, leftEnd, rightStart, rightEnd});
             }
-
-            // Add the matched subsequence to result
-            result.prepend({leftStart, leftEnd, rightStart, rightEnd});
-
-            // i--;
-            // j--;
-            // if (!started) {
-            //     si = i;
-            //     sj = j;
-            //     started = true;
-            // }
         } else {
-            // if (started) {
-            //     r << LcsResult{si, i, sj, j};
-            //     started = false;
-            // }
-
-            int n = maxIn(l(i - 1, j), l(i, j - 1), l(i - 1, j - 1));
-            switch (n) {
-            case 1:
-                i--;
-                break;
-            case 2:
-                j--;
-                break;
-            default:
+            // منطق استاندارد و صحیح بازگشت به عقب در LCS
+            // در حالت تساوی، ترجیح با i-- است که منجر به Diff پایدارتر (Stable) می‌شود
+            if (l(i - 1, j) >= l(i, j - 1)) {
                 i--;
+            } else {
                 j--;
-                break;
             }
         }
     }