##// END OF EJS Templates
pure/bdiff: fix circular import
Matt Mackall -
r7944:e9b48afd default
parent child Browse files
Show More
@@ -1,69 +1,76 b''
1 # bdiff.py - Python implementation of bdiff.c
1 # bdiff.py - Python implementation of bdiff.c
2 #
2 #
3 # Copyright 2009 Matt Mackall <mpm@selenic.com> and others
3 # Copyright 2009 Matt Mackall <mpm@selenic.com> and others
4 #
4 #
5 # This software may be used and distributed according to the terms
5 # This software may be used and distributed according to the terms
6 # of the GNU General Public License, incorporated herein by reference.
6 # of the GNU General Public License, incorporated herein by reference.
7
7
8 import struct, difflib
8 import struct, difflib
9 # mdiff import moved to bottom due to import cycle
9
10 def splitnewlines(text):
11 '''like str.splitlines, but only split on newlines.'''
12 lines = [l + '\n' for l in text.split('\n')]
13 if lines:
14 if lines[-1] == '\n':
15 lines.pop()
16 else:
17 lines[-1] = lines[-1][:-1]
18 return lines
10
19
11 def _normalizeblocks(a, b, blocks):
20 def _normalizeblocks(a, b, blocks):
12 prev = None
21 prev = None
13 for curr in blocks:
22 for curr in blocks:
14 if prev is None:
23 if prev is None:
15 prev = curr
24 prev = curr
16 continue
25 continue
17 shift = 0
26 shift = 0
18
27
19 a1, b1, l1 = prev
28 a1, b1, l1 = prev
20 a1end = a1 + l1
29 a1end = a1 + l1
21 b1end = b1 + l1
30 b1end = b1 + l1
22
31
23 a2, b2, l2 = curr
32 a2, b2, l2 = curr
24 a2end = a2 + l2
33 a2end = a2 + l2
25 b2end = b2 + l2
34 b2end = b2 + l2
26 if a1end == a2:
35 if a1end == a2:
27 while a1end+shift < a2end and a[a1end+shift] == b[b1end+shift]:
36 while a1end+shift < a2end and a[a1end+shift] == b[b1end+shift]:
28 shift += 1
37 shift += 1
29 elif b1end == b2:
38 elif b1end == b2:
30 while b1end+shift < b2end and a[a1end+shift] == b[b1end+shift]:
39 while b1end+shift < b2end and a[a1end+shift] == b[b1end+shift]:
31 shift += 1
40 shift += 1
32 yield a1, b1, l1+shift
41 yield a1, b1, l1+shift
33 prev = a2+shift, b2+shift, l2-shift
42 prev = a2+shift, b2+shift, l2-shift
34 yield prev
43 yield prev
35
44
36 def bdiff(a, b):
45 def bdiff(a, b):
37 a = str(a).splitlines(True)
46 a = str(a).splitlines(True)
38 b = str(b).splitlines(True)
47 b = str(b).splitlines(True)
39
48
40 if not a:
49 if not a:
41 s = "".join(b)
50 s = "".join(b)
42 return s and (struct.pack(">lll", 0, 0, len(s)) + s)
51 return s and (struct.pack(">lll", 0, 0, len(s)) + s)
43
52
44 bin = []
53 bin = []
45 p = [0]
54 p = [0]
46 for i in a: p.append(p[-1] + len(i))
55 for i in a: p.append(p[-1] + len(i))
47
56
48 d = difflib.SequenceMatcher(None, a, b).get_matching_blocks()
57 d = difflib.SequenceMatcher(None, a, b).get_matching_blocks()
49 d = _normalizeblocks(a, b, d)
58 d = _normalizeblocks(a, b, d)
50 la = 0
59 la = 0
51 lb = 0
60 lb = 0
52 for am, bm, size in d:
61 for am, bm, size in d:
53 s = "".join(b[lb:bm])
62 s = "".join(b[lb:bm])
54 if am > la or s:
63 if am > la or s:
55 bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s)
64 bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s)
56 la = am + size
65 la = am + size
57 lb = bm + size
66 lb = bm + size
58
67
59 return "".join(bin)
68 return "".join(bin)
60
69
61 def blocks(a, b):
70 def blocks(a, b):
62 an = mdiff.splitnewlines(a)
71 an = splitnewlines(a)
63 bn = mdiff.splitnewlines(b)
72 bn = splitnewlines(b)
64 d = difflib.SequenceMatcher(None, an, bn).get_matching_blocks()
73 d = difflib.SequenceMatcher(None, an, bn).get_matching_blocks()
65 d = _normalizeblocks(an, bn, d)
74 d = _normalizeblocks(an, bn, d)
66 return [(i, i + n, j, j + n) for (i, j, n) in d]
75 return [(i, i + n, j, j + n) for (i, j, n) in d]
67
76
68 # this breaks an import cycle
69 import mdiff
General Comments 0
You need to be logged in to leave comments. Login now