Mercurial > hg > mercurial-crew-with-dirclash

comparison mercurial/mdiff.py @ 325:ad87e19854a6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
mdiff: reinstate new algorithm -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 mdiff: reinstate new algorithm This unreverts the new algorithm with a fix from Chris (s/len/lena) and adds some comments on what it's doing. manifest hash: 75fc1acee1926e57d495f67a44cd88d9555f2356 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.0 (GNU/Linux) iD8DBQFCrf4UywK+sNU5EO8RAoRzAKCA2vpUAGNqTkDeba3YHo6XXht7VgCfXQK0 /j5yv5cucnsYezCdclpftOA= =FNMD -----END PGP SIGNATURE-----
author mpm@selenic.com
date Mon, 13 Jun 2005 13:43:48 -0800
parents 2819f63b16bf
children 235443668bea
comparison
equal deleted inserted replaced
324:ce81bdd91d06 325:ad87e19854a6
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 = []