1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#! /bin/sh -e
# DP: Fix difflib where certain patterns of differences were making difflib
# DP: touch the recursion limit.
dir=
if [ $# -eq 3 -a "$2" = '-d' ]; then
pdir="-d $3"
dir="$3/"
elif [ $# -ne 1 ]; then
echo >&2 "usage: `basename $0`: -patch|-unpatch [-d <srcdir>]"
exit 1
fi
case "$1" in
-patch)
patch $pdir -f --no-backup-if-mismatch -p0 < $0
;;
-unpatch)
patch $pdir -f --no-backup-if-mismatch -R -p0 < $0
;;
*)
echo >&2 "usage: `basename $0`: -patch|-unpatch [-d <srcdir>]"
exit 1
esac
exit 0
Index: Lib/difflib.py
===================================================================
--- Lib/difflib.py (revision 42211)
+++ Lib/difflib.py (revision 42212)
@@ -473,27 +473,32 @@
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.
|
