41 def textdiff(a, b): |
41 def textdiff(a, b): |
42 return diff(a.splitlines(1), b.splitlines(1)) |
42 return diff(a.splitlines(1), b.splitlines(1)) |
43 |
43 |
44 def sortdiff(a, b): |
44 def sortdiff(a, b): |
45 la = lb = 0 |
45 la = lb = 0 |
|
46 lena = len(a) |
|
47 lenb = len(b) |
|
48 |
|
49 while 1: |
|
50 am, bm, = la, lb |
46 |
51 |
47 while 1: |
52 # walk over matching lines |
48 if la >= len(a) or lb >= len(b): break |
53 while lb < lenb and la < lenb and a[la] == b[lb] : |
49 if b[lb] < a[la]: |
|
50 si = lb |
|
51 while lb < len(b) and b[lb] < a[la] : lb += 1 |
|
52 yield "insert", la, la, si, lb |
|
53 elif a[la] < b[lb]: |
|
54 si = la |
|
55 while la < len(a) and a[la] < b[lb]: la += 1 |
|
56 yield "delete", si, la, lb, lb |
|
57 else: |
|
58 la += 1 |
54 la += 1 |
59 lb += 1 |
55 lb += 1 |
60 |
56 |
61 if lb < len(b): |
57 if la > am: |
62 yield "insert", la, la, lb, len(b) |
58 yield (am, bm, la - am) # return a match |
63 |
59 |
64 if la < len(a): |
60 # skip mismatched lines from b |
65 yield "delete", la, len(a), lb, lb |
61 while lb < lenb and b[lb] < a[la]: |
|
62 lb += 1 |
|
63 |
|
64 if lb >= lenb: |
|
65 break |
|
66 |
|
67 # skip mismatched lines from a |
|
68 while la < lena and b[lb] > a[la]: |
|
69 la += 1 |
|
70 |
|
71 if la >= lena: |
|
72 break |
|
73 |
|
74 yield (lena, lenb, 0) |
66 |
75 |
67 def diff(a, b, sorted=0): |
76 def diff(a, b, sorted=0): |
|
77 if not a: |
|
78 s = "".join(b) |
|
79 return s and (struct.pack(">lll", 0, 0, len(s)) + s) |
|
80 |
68 bin = [] |
81 bin = [] |
69 p = [0] |
82 p = [0] |
70 for i in a: p.append(p[-1] + len(i)) |
83 for i in a: p.append(p[-1] + len(i)) |
71 |
84 |
72 if sorted: |
85 if sorted: |
74 d = sortdiff(a, b) |
87 d = sortdiff(a, b) |
75 except: |
88 except: |
76 print a, b |
89 print a, b |
77 raise |
90 raise |
78 else: |
91 else: |
79 d = difflib.SequenceMatcher(None, a, b).get_opcodes() |
92 d = difflib.SequenceMatcher(None, a, b).get_matching_blocks() |
80 |
93 la = 0 |
81 for o, m, n, s, t in d: |
94 lb = 0 |
82 if o == 'equal': continue |
95 for am, bm, size in d: |
83 s = "".join(b[s:t]) |
96 s = "".join(b[lb:bm]) |
84 bin.append(struct.pack(">lll", p[m], p[n], len(s)) + s) |
97 if am > la or s: |
85 |
98 bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s) |
|
99 la = am + size |
|
100 lb = bm + size |
|
101 |
86 return "".join(bin) |
102 return "".join(bin) |
87 |
103 |
88 def patchtext(bin): |
104 def patchtext(bin): |
89 pos = 0 |
105 pos = 0 |
90 t = [] |
106 t = [] |