From 548148810bfb4f44450a93f98912a5eee07d4303 Mon Sep 17 00:00:00 2001
From: Gustavo Niemeyer <gustavo@niemeyer.net>
Date: Tue, 31 Jan 2006 18:34:13 +0000
Subject: Patch #1413711: Certain patterns of differences were making difflib
touch the recursion limit. The applied patch inlines the recursive __helper
method in a non-recursive way.
---
Lib/difflib.py | 39 ++++++++++++++++++++++-----------------
Lib/test/test_difflib.py | 9 +++++++++
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)
diff --git a/Misc/NEWS b/Misc/NEWS
index 830583c..484b50a 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -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
-----
--
cgit v0.12