[Python-checkins] r46905 - python/trunk/Lib/difflib.py

Tue Jun 13 05:30:08 CEST 2006

Author: tim.peters
Date: Tue Jun 13 05:30:07 2006
New Revision: 46905
Modified:
 python/trunk/Lib/difflib.py
Log:
get_matching_blocks(): rewrote code & comments so they match; added
more comments about why it's this way at all; and removed what looked
like needless expense (sorting (i, j, k) triples directly should give
exactly the same order as sorting (i, (i, j, k)) pairs).
Modified: python/trunk/Lib/difflib.py
==============================================================================

--- python/trunk/Lib/difflib.py	(original)
+++ python/trunk/Lib/difflib.py	Tue Jun 13 05:30:07 2006
@@ -474,30 +474,30 @@
 if self.matching_blocks is not None:
 return self.matching_blocks
 la, lb = len(self.a), len(self.b)
+ self.matching_blocks = matching_blocks = []
 
- indexed_blocks = []
+ # This is most naturally expressed as a recursive algorithm, but
+ # at least one user bumped into extreme use cases that exceeded
+ # the recursion limit on their box. So, now we maintain a list
+ # ('queue`) of blocks we still need to look at, and append partial
+ # results to `matching_blocks` in a loop; the matches are sorted
+ # at the end.
 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()
-
+ 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
- i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
-
- if k:
+ if k: # if k is 0, there was no matching block
+ matching_blocks.append(x)
 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
+ matching_blocks.sort()
+ matching_blocks.append( (la, lb, 0) )
+ return matching_blocks
 
 def get_opcodes(self):
 """Return list of 5-tuples describing how to turn a into b.
