diff options
| -rw-r--r-- | Lib/difflib.py | 39 | ||||
| -rw-r--r-- | Lib/test/test_difflib.py | 9 | ||||
| -rw-r--r-- | Misc/NEWS | 3 |
3 files changed, 34 insertions, 17 deletions
diff --git a/Lib/difflib.py b/Lib/difflib.py index 3558f53..55f69ba 100644 --- a/Lib/difflib.py +++ b/Lib/difflib.py @@ -473,27 +473,32 @@ class SequenceMatcher: if self.matching_blocks is not None: return self.matching_blocks - self.matching_blocks = [] la, lb = len(self.a), len(self.b) - self.__helper(0, la, 0, lb, self.matching_blocks) + + indexed_blocks = [] + queue = [(0, la, 0, lb)] + while queue: + # builds list of matching blocks covering a[alo:ahi] and + # b[blo:bhi], appending them in increasing order to answer + alo, ahi, blo, bhi = queue.pop() + + # a[alo:i] vs b[blo:j] unknown + # a[i:i+k] same as b[j:j+k] + # a[i+k:ahi] vs b[j+k:bhi] unknown + i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi) + + if k: + if alo < i and blo < j: + queue.append((alo, i, blo, j)) + indexed_blocks.append((i, x)) + if i+k < ahi and j+k < bhi: + queue.append((i+k, ahi, j+k, bhi)) + indexed_blocks.sort() + + self.matching_blocks = [elem[1] for elem in indexed_blocks] self.matching_blocks.append( (la, lb, 0) ) return self.matching_blocks - # builds list of matching blocks covering a[alo:ahi] and - # b[blo:bhi], appending them in increasing order to answer - - def __helper(self, alo, ahi, blo, bhi, answer): - i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi) - # a[alo:i] vs b[blo:j] unknown - # a[i:i+k] same as b[j:j+k] - # a[i+k:ahi] vs b[j+k:bhi] unknown - if k: - if alo < i and blo < j: - self.__helper(alo, i, blo, j, answer) - answer.append(x) - if i+k < ahi and j+k < bhi: - self.__helper(i+k, ahi, j+k, bhi, answer) - def get_opcodes(self): """Return list of 5-tuples describing how to turn a into b. diff --git a/Lib/test/test_difflib.py b/Lib/test/test_difflib.py index c0bf66e..52feef0 100644 --- a/Lib/test/test_difflib.py +++ b/Lib/test/test_difflib.py @@ -2,6 +2,7 @@ import difflib from test.test_support import run_unittest, findfile import unittest import doctest +import sys class TestSFbugs(unittest.TestCase): @@ -143,6 +144,14 @@ class TestSFpatches(unittest.TestCase): self.assertEqual(actual,expect) + def test_recursion_limit(self): + # Check if the problem described in patch #1413711 exists. + limit = sys.getrecursionlimit() + old = [(i%2 and "K:%d" or "V:A:%d") % i for i in range(limit*2)] + new = [(i%2 and "K:%d" or "V:B:%d") % i for i in range(limit*2)] + difflib.SequenceMatcher(None, old, new).get_opcodes() + + Doctests = doctest.DocTestSuite(difflib) run_unittest(TestSFpatches, TestSFbugs, Doctests) @@ -676,6 +676,9 @@ Library - ` uu.encode()`` and ``uu.decode()`` now support unicode filenames. +- Patch #1413711: Certain patterns of differences were making difflib + touch the recursion limit. + Build ----- |