Repository: mduggan/cdifflib (language: python)

Issue:
difflib and cdifflib matched blocks differs
Hello!

The matching blocks found with `difflib` and `cdifflib` differs for input data `a` and `b` as found in the script below. Most of the blocks are the same, but a few small blocks differs. It would be nice if the two implementations gives identical output for compatibility.

I'm using Python 3.6.3 and cdifflib 1.2.0.

Example execution:

```
$ python3 test.py
[Match(a=0, b=21, size=27),
 Match(a=28, b=49, size=12),
 Match(a=45, b=66, size=2),
 Match(a=60, b=81, size=2),
 Match(a=66, b=87, size=5),
 Match(a=83, b=104, size=96),
 Match(a=190, b=200, size=0)]
[Match(a=0, b=21, size=27),
 Match(a=28, b=49, size=12),
 Match(a=45, b=66, size=2),
 Match(a=48, b=69, size=1),
 Match(a=50, b=71, size=2),
 Match(a=53, b=74, size=4),
 Match(a=58, b=79, size=1),
 Match(a=60, b=81, size=2),
 Match(a=63, b=84, size=2),
 Match(a=66, b=87, size=5),
 Match(a=72, b=93, size=5),
 Match(a=78, b=99, size=4),
 Match(a=83, b=104, size=96),
 Match(a=190, b=200, size=0)]
Traceback (most recent call last):
  File "test.py", line 58, in <module>
    assert difflib_matches == cdifflib_matches
AssertionError
```

Script to reproduce the issue:

``` python3
from pprint import pprint
import difflib
import cdifflib

a = [
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    124, 16, 12, 12, 12, 108, 588, 1316, 12, 8,
    42, 6, 168, 36, 12, 10, 10, 158, 36, 10,
    24, 152, 914, 84, 216, 4, 10, 254, 8, 40,
    54, 20, 12, 54, 38, 10, 8, 310, 6, 580,
    28, 20, 44, 12, 24, 34, 44, 4, 20, 8,
    16, 14, 12, 8, 12, 20, 14, 28, 12, 24,
    6, 12, 372, 544, 1212, 28, 64, 12, 16, 16,
    34, 146, 70, 284, 110, 206, 354, 612, 16, 12,
    18, 6, 18, 6, 6, 20, 6, 12, 12, 12,
    20, 12, 12, 12, 20, 12, 12, 358, 258, 12,
    54, 20, 8, 8, 6, 16, 12, 6, 112, 130,
    16, 8, 26, 8, 8, 44, 44, 22, 88, 314,
    394, 588, 122, 6, 644, 6, 32, 24, 924, 10,
    66, 22, 270, 16, 1340, 2408, 54, 452, 158, 1950,
    382, 594, 38, 110, 106, 40, 56, 5302, 1398, 6,
    1016, 814, 46, 112, 14, 6, 14, 12, 6, 6,
    46, 16, 80, 80, 68, 84, 82, 6, 1224, 518
]

b = [
    284, 6, 528, 64, 16, 230, 254, 6, 162, 350,
    28, 22, 88, 18, 136, 64, 36, 32, 102, 14,
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    12, 124, 16, 12, 12, 12, 108, 588, 1312, 12,
    8, 42, 6, 168, 36, 12, 10, 10, 158, 36,
    10, 26, 154, 906, 82, 214, 4, 10, 242, 8,
    38, 54, 20, 14, 54, 38, 10, 8, 314, 6,
    574, 28, 20, 38, 12, 24, 22, 44, 4, 20,
    8, 16, 12, 12, 8, 12, 20, 14, 24, 12,
    24, 6, 12, 382, 544, 1212, 28, 64, 12, 16,
    16, 34, 146, 70, 284, 110, 206, 354, 612, 16,
    12, 18, 6, 18, 6, 6, 20, 6, 12, 12,
    12, 20, 12, 12, 12, 20, 12, 12, 358, 258,
    12, 54, 20, 8, 8, 6, 16, 12, 6, 112,
    130, 16, 8, 26, 8, 8, 44, 44, 22, 88,
    314, 394, 588, 122, 6, 644, 6, 32, 24, 924,
    10, 66, 22, 270, 16, 1340, 2408, 54, 452, 158,
    1950, 382, 594, 38, 110, 106, 40, 56, 5302, 1398,
    6, 1016, 814, 46, 112, 14, 6, 14, 12, 6
]

sm = difflib.SequenceMatcher(None, a, b)
difflib_matches = sm.get_matching_blocks()
pprint(difflib_matches)

sm = cdifflib.CSequenceMatcher(None, a, b)
cdifflib_matches = list(sm.get_matching_blocks())
pprint(cdifflib_matches)

assert difflib_matches == cdifflib_matches
```


Discussion / hints:
Thanks for the report! Yes they're supposed to be producing the same results, so I consider it a bug if they're not.  I'll try to take a look at this in the next few days

Fix patch:
diff --git a/_cdifflib.c b/_cdifflib.c
index d71c25a..e5fef2f 100644
--- a/_cdifflib.c
+++ b/_cdifflib.c
@@ -129,9 +129,12 @@ _find_longest_match_worker(
             PyDict_Clear(newj2len);
         }
 
-        /* besti and bestj are offset by 1 */
-        besti++;
-        bestj++;
+        /* besti and bestj are offset by 1 if set in the loop above */
+        if (bestsize)
+        {
+            besti++;
+            bestj++;
+        }
 
         /* Done with these now. */
         Py_DECREF(j2len);
@@ -424,7 +427,7 @@ chain_b(PyObject *module, PyObject *args)
     popular = PySet_New(NULL);
     autojunk = PyObject_GetAttrString(self, "autojunk");
     assert(autojunk != NULL);
-    if (PyObject_IsTrue(autojunk) && n > 200) {
+    if (PyObject_IsTrue(autojunk) && n >= 200) {
         long ntest = n/100 + 1;
         PyObject *items = PyDict_Items(b2j);
         long b2jlen = PyList_GET_SIZE(items);
diff --git a/_cdifflib3.c b/_cdifflib3.c
index a35a2c9..4ea1ba0 100644
--- a/_cdifflib3.c
+++ b/_cdifflib3.c
@@ -129,9 +129,12 @@ _find_longest_match_worker(
             PyDict_Clear(newj2len);
         }
 
-        /* besti and bestj are offset by 1 */
-        besti++;
-        bestj++;
+        /* besti and bestj are offset by 1 if set in the loop above */
+        if (bestsize)
+        {
+            besti++;
+            bestj++;
+        }
 
         /* Done with these now. */
         Py_DECREF(j2len);
@@ -424,7 +427,7 @@ chain_b(PyObject *module, PyObject *args)
     popular = PySet_New(NULL);
     autojunk = PyObject_GetAttrString(self, "autojunk");
     assert(autojunk != NULL);
-    if (PyObject_IsTrue(autojunk) && n > 200) {
+    if (PyObject_IsTrue(autojunk) && n >= 200) {
         long ntest = n/100 + 1;
         PyObject *items = PyDict_Items(b2j);
         long b2jlen = PyList_GET_SIZE(items);


Test patch:
diff --git a/tests/cdifflib_tests.py b/tests/cdifflib_tests.py
index aa03d6f..2d6d814 100755
--- a/tests/cdifflib_tests.py
+++ b/tests/cdifflib_tests.py
@@ -116,6 +116,20 @@ def genb():
         # actually difflib doesn't handle generators, just check cdiff result.
         self.assertGreater(cdiff, 0)
 
+    def testCDifflibWithBug5Data(self):
+        """Check cdifflib returns the same result for bug #5
+           (autojunk handling issues)"""
+        from . import testdata
+
+        # note: convert both to lists for Python 3.3
+        sm = SequenceMatcher(None, testdata.a5, testdata.b5)
+        difflib_matches = list(sm.get_matching_blocks())
+
+        sm = CSequenceMatcher(None, testdata.a5, testdata.b5)
+        cdifflib_matches = list(sm.get_matching_blocks())
+
+        self.assertEqual(difflib_matches, cdifflib_matches)
+
 
 def main():
     from optparse import OptionParser
diff --git a/tests/testdata.py b/tests/testdata.py
new file mode 100644
index 0000000..c377044
--- /dev/null
+++ b/tests/testdata.py
@@ -0,0 +1,33 @@
+"""
+Test data from bug https://github.com/mduggan/cdifflib/issues/5
+
+Revealed some bugs with autojunk handling
+"""
+a5 = [
+    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+    12, 124, 16, 12, 12, 12, 108, 588, 1316, 12, 8, 42, 6, 168, 36, 12, 10, 10,
+    158, 36, 10, 24, 152, 914, 84, 216, 4, 10, 254, 8, 40, 54, 20, 12, 54, 38,
+    10, 8, 310, 6, 580, 28, 20, 44, 12, 24, 34, 44, 4, 20, 8, 16, 14, 12, 8,
+    12, 20, 14, 28, 12, 24, 6, 12, 372, 544, 1212, 28, 64, 12, 16, 16, 34, 146,
+    70, 284, 110, 206, 354, 612, 16, 12, 18, 6, 18, 6, 6, 20, 6, 12, 12, 12,
+    20, 12, 12, 12, 20, 12, 12, 358, 258, 12, 54, 20, 8, 8, 6, 16, 12, 6, 112,
+    130, 16, 8, 26, 8, 8, 44, 44, 22, 88, 314, 394, 588, 122, 6, 644, 6, 32,
+    24, 924, 10, 66, 22, 270, 16, 1340, 2408, 54, 452, 158, 1950, 382, 594, 38,
+    110, 106, 40, 56, 5302, 1398, 6, 1016, 814, 46, 112, 14, 6, 14, 12, 6, 6,
+    46, 16, 80, 80, 68, 84, 82, 6, 1224, 518
+]
+
+b5 = [
+    284, 6, 528, 64, 16, 230, 254, 6, 162, 350, 28, 22, 88, 18, 136, 64, 36,
+    32, 102, 14, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+    12, 12, 12, 12, 12, 12, 124, 16, 12, 12, 12, 108, 588, 1312, 12, 8, 42, 6,
+    168, 36, 12, 10, 10, 158, 36, 10, 26, 154, 906, 82, 214, 4, 10, 242, 8, 38,
+    54, 20, 14, 54, 38, 10, 8, 314, 6, 574, 28, 20, 38, 12, 24, 22, 44, 4, 20,
+    8, 16, 12, 12, 8, 12, 20, 14, 24, 12, 24, 6, 12, 382, 544, 1212, 28, 64,
+    12, 16, 16, 34, 146, 70, 284, 110, 206, 354, 612, 16, 12, 18, 6, 18, 6, 6,
+    20, 6, 12, 12, 12, 20, 12, 12, 12, 20, 12, 12, 358, 258, 12, 54, 20, 8, 8,
+    6, 16, 12, 6, 112, 130, 16, 8, 26, 8, 8, 44, 44, 22, 88, 314, 394, 588,
+    122, 6, 644, 6, 32, 24, 924, 10, 66, 22, 270, 16, 1340, 2408, 54, 452, 158,
+    1950, 382, 594, 38, 110, 106, 40, 56, 5302, 1398, 6, 1016, 814, 46, 112,
+    14, 6, 14, 12, 6
+]