Mercurial > hg > mercurial-crew-with-dirclash
annotate mercurial/revlog.py @ 73:ee1cbe841e01
Change revlog to use new patch code
author | mpm@selenic.com |
---|---|
date | Mon, 16 May 2005 22:10:02 -0800 |
parents | 47c9a869adee |
children | d993ebd69d28 |
rev | line source |
---|---|
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
1 # revlog.py - storage back-end for mercurial |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
2 # |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
3 # This provides efficient delta storage with O(1) retrieve and append |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
4 # and O(changes) merge between branches |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
5 # |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
6 # Copyright 2005 Matt Mackall <mpm@selenic.com> |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
7 # |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
8 # This software may be used and distributed according to the terms |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
9 # of the GNU General Public License, incorporated herein by reference. |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
10 |
36
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
11 import zlib, struct, sha, os, tempfile, binascii |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
12 from mercurial import mdiff |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
13 |
36
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
14 def hex(node): return binascii.hexlify(node) |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
15 def bin(node): return binascii.unhexlify(node) |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
16 |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
17 def compress(text): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
18 return zlib.compress(text) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
19 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
20 def decompress(bin): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
21 return zlib.decompress(bin) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
22 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
23 def hash(text, p1, p2): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
24 l = [p1, p2] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
25 l.sort() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
26 return sha.sha(l[0] + l[1] + text).digest() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
27 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
28 nullid = "\0" * 20 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
29 indexformat = ">4l20s20s20s" |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
30 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
31 class revlog: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
32 def __init__(self, opener, indexfile, datafile): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
33 self.indexfile = indexfile |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
34 self.datafile = datafile |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
35 self.index = [] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
36 self.opener = opener |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
37 self.cache = None |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
38 # read the whole index for now, handle on-demand later |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
39 try: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
40 n = 0 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
41 i = self.opener(self.indexfile).read() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
42 s = struct.calcsize(indexformat) |
73 | 43 |
44 # preallocate arrays | |
45 l = len(i)/s | |
46 self.index = [None] * l | |
47 m = [None] * l | |
48 | |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
49 for f in xrange(0, len(i), s): |
26 | 50 # offset, size, base, linkrev, p1, p2, nodeid |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
51 e = struct.unpack(indexformat, i[f:f + s]) |
73 | 52 self.index[n] = e |
53 m[n] = (e[6], n) | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
54 n += 1 |
73 | 55 |
56 self.nodemap = dict(m) | |
57 except IOError: | |
58 self.nodemap = {} | |
59 self.nodemap[nullid] = -1 | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
60 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
61 def tip(self): return self.node(len(self.index) - 1) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
62 def count(self): return len(self.index) |
26 | 63 def node(self, rev): return (rev < 0) and nullid or self.index[rev][6] |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
64 def rev(self, node): return self.nodemap[node] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
65 def linkrev(self, node): return self.index[self.nodemap[node]][3] |
2 | 66 def parents(self, node): |
67 if node == nullid: return (nullid, nullid) | |
68 return self.index[self.nodemap[node]][4:6] | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
69 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
70 def start(self, rev): return self.index[rev][0] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
71 def length(self, rev): return self.index[rev][1] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
72 def end(self, rev): return self.start(rev) + self.length(rev) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
73 def base(self, rev): return self.index[rev][2] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
74 |
36
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
75 def lookup(self, id): |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
76 try: |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
77 rev = int(id) |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
78 return self.node(rev) |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
79 except ValueError: |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
80 c = [] |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
81 for n in self.nodemap: |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
82 if id in hex(n): |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
83 c.append(n) |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
84 if len(c) > 1: raise KeyError("Ambiguous identifier") |
67 | 85 if len(c) < 1: raise KeyError("No match found") |
36
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
86 return c[0] |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
87 |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
88 return None |
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
89 |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
90 def revisions(self, list): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
91 # this can be optimized to do spans, etc |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
92 # be stupid for now |
14
e0e5c1b9febd
Fix off-by-one truncation in transaction rollback.
mpm@selenic.com
parents:
2
diff
changeset
|
93 for node in list: |
e0e5c1b9febd
Fix off-by-one truncation in transaction rollback.
mpm@selenic.com
parents:
2
diff
changeset
|
94 yield self.revision(node) |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
95 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
96 def diff(self, a, b): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
97 return mdiff.textdiff(a, b) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
98 |
73 | 99 def patches(self, t, pl): |
100 return mdiff.patches(t, pl) | |
101 | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
102 def revision(self, node): |
36
da28286bf6b7
Add smart node lookup by substring or by rev number
mpm@selenic.com
parents:
26
diff
changeset
|
103 if node == nullid: return "" |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
104 if self.cache and self.cache[0] == node: return self.cache[2] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
105 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
106 text = None |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
107 rev = self.rev(node) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
108 base = self.base(rev) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
109 start = self.start(base) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
110 end = self.end(rev) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
111 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
112 if self.cache and self.cache[1] >= base and self.cache[1] < rev: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
113 base = self.cache[1] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
114 start = self.start(base + 1) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
115 text = self.cache[2] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
116 last = 0 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
117 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
118 f = self.opener(self.datafile) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
119 f.seek(start) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
120 data = f.read(end - start) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
121 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
122 if not text: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
123 last = self.length(base) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
124 text = decompress(data[:last]) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
125 |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
126 bins = [] |
64 | 127 for r in xrange(base + 1, rev + 1): |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
128 s = self.length(r) |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
129 bins.append(decompress(data[last:last + s])) |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
130 last = last + s |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
131 |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
132 text = mdiff.patches(text, bins) |
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
133 |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
134 (p1, p2) = self.parents(node) |
26 | 135 if node != hash(text, p1, p2): |
136 raise "integrity check failed on %s:%d" % (self.datafile, rev) | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
137 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
138 self.cache = (node, rev, text) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
139 return text |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
140 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
141 def addrevision(self, text, transaction, link, p1=None, p2=None): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
142 if text is None: text = "" |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
143 if p1 is None: p1 = self.tip() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
144 if p2 is None: p2 = nullid |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
145 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
146 node = hash(text, p1, p2) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
147 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
148 n = self.count() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
149 t = n - 1 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
150 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
151 if n: |
64 | 152 base = self.base(t) |
153 start = self.start(base) | |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
154 end = self.end(t) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
155 prev = self.revision(self.tip()) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
156 data = compress(self.diff(prev, text)) |
64 | 157 dist = end - start + len(data) |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
158 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
159 # full versions are inserted when the needed deltas |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
160 # become comparable to the uncompressed text |
64 | 161 if not n or dist > len(text) * 2: |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
162 data = compress(text) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
163 base = n |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
164 else: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
165 base = self.base(t) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
166 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
167 offset = 0 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
168 if t >= 0: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
169 offset = self.end(t) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
170 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
171 e = (offset, len(data), base, link, p1, p2, node) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
172 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
173 self.index.append(e) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
174 self.nodemap[node] = n |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
175 entry = struct.pack(indexformat, *e) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
176 |
26 | 177 transaction.add(self.datafile, e[0]) |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
178 self.opener(self.datafile, "a").write(data) |
41 | 179 transaction.add(self.indexfile, n * len(entry)) |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
180 self.opener(self.indexfile, "a").write(entry) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
181 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
182 self.cache = (node, n, text) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
183 return node |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
184 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
185 def ancestor(self, a, b): |
45
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
186 def expand(list, map): |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
187 a = [] |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
188 while list: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
189 n = list.pop(0) |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
190 map[n] = 1 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
191 yield n |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
192 for p in self.parents(n): |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
193 if p != nullid and p not in map: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
194 list.append(p) |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
195 yield nullid |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
196 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
197 amap = {} |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
198 bmap = {} |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
199 ag = expand([a], amap) |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
200 bg = expand([b], bmap) |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
201 adone = bdone = 0 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
202 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
203 while not adone or not bdone: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
204 if not adone: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
205 an = ag.next() |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
206 if an == nullid: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
207 adone = 1 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
208 elif an in bmap: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
209 return an |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
210 if not bdone: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
211 bn = bg.next() |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
212 if bn == nullid: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
213 bdone = 1 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
214 elif bn in amap: |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
215 return bn |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
216 |
f2b2d5daec30
Fix recursion depth trouble with ancestor algorithm
mpm@selenic.com
parents:
41
diff
changeset
|
217 return nullid |
0
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
218 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
219 def mergedag(self, other, transaction, linkseq, accumulate = None): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
220 """combine the nodes from other's DAG into ours""" |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
221 old = self.tip() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
222 i = self.count() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
223 l = [] |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
224 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
225 # merge the other revision log into our DAG |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
226 for r in range(other.count()): |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
227 id = other.node(r) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
228 if id not in self.nodemap: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
229 (xn, yn) = other.parents(id) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
230 l.append((id, xn, yn)) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
231 self.nodemap[id] = i |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
232 i += 1 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
233 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
234 # merge node date for new nodes |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
235 r = other.revisions([e[0] for e in l]) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
236 for e in l: |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
237 t = r.next() |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
238 if accumulate: accumulate(t) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
239 self.addrevision(t, transaction, linkseq.next(), e[1], e[2]) |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
240 |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
241 # return the unmerged heads for later resolving |
9117c6561b0b
Add back links from file revisions to changeset revisions
mpm@selenic.com
parents:
diff
changeset
|
242 return (old, self.tip()) |
46 | 243 |
244 def group(self, linkmap): | |
245 # given a list of changeset revs, return a set of deltas and | |
246 # metadata corresponding to nodes the first delta is | |
247 # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to | |
248 # have this parent as it has all history before these | |
249 # changesets. parent is parent[0] | |
250 | |
251 revs = [] | |
252 needed = {} | |
253 | |
254 # find file nodes/revs that match changeset revs | |
255 for i in xrange(0, self.count()): | |
256 if self.index[i][3] in linkmap: | |
257 revs.append(i) | |
258 needed[i] = 1 | |
259 | |
260 # if we don't have any revisions touched by these changesets, bail | |
261 if not revs: return struct.pack(">l", 0) | |
262 | |
263 # add the parent of the first rev | |
264 p = self.parents(self.node(revs[0]))[0] | |
265 revs.insert(0, self.rev(p)) | |
266 | |
267 # for each delta that isn't contiguous in the log, we need to | |
268 # reconstruct the base, reconstruct the result, and then | |
269 # calculate the delta. We also need to do this where we've | |
270 # stored a full version and not a delta | |
271 for i in xrange(0, len(revs) - 1): | |
272 a, b = revs[i], revs[i + 1] | |
273 if a + 1 != b or self.base(b) == b: | |
274 for j in xrange(self.base(a), a + 1): | |
275 needed[j] = 1 | |
276 for j in xrange(self.base(b), b + 1): | |
277 needed[j] = 1 | |
278 | |
279 # calculate spans to retrieve from datafile | |
280 needed = needed.keys() | |
281 needed.sort() | |
282 spans = [] | |
283 for n in needed: | |
284 if n < 0: continue | |
285 o = self.start(n) | |
286 l = self.length(n) | |
287 spans.append((o, l, [(n, l)])) | |
288 | |
289 # merge spans | |
290 merge = [spans.pop(0)] | |
291 while spans: | |
292 e = spans.pop(0) | |
293 f = merge[-1] | |
294 if e[0] == f[0] + f[1]: | |
295 merge[-1] = (f[0], f[1] + e[1], f[2] + e[2]) | |
296 else: | |
297 merge.append(e) | |
298 | |
299 # read spans in, divide up chunks | |
300 chunks = {} | |
301 for span in merge: | |
302 # we reopen the file for each span to make http happy for now | |
303 f = self.opener(self.datafile) | |
304 f.seek(span[0]) | |
305 data = f.read(span[1]) | |
306 | |
307 # divide up the span | |
308 pos = 0 | |
309 for r, l in span[2]: | |
310 chunks[r] = data[pos: pos + l] | |
311 pos += l | |
312 | |
313 # helper to reconstruct intermediate versions | |
314 def construct(text, base, rev): | |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
315 bins = [decompress(chunks[r]) for r in xrange(base + 1, rev + 1)] |
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
316 return mdiff.patches(text, bins) |
46 | 317 |
318 # build deltas | |
319 deltas = [] | |
71
47c9a869adee
Add mdiff.patches to speed up applying thousands of patches to the manifest
mpm@selenic.com
parents:
67
diff
changeset
|
320 for d in xrange(0, len(revs) - 1): |
46 | 321 a, b = revs[d], revs[d + 1] |
322 n = self.node(b) | |
323 | |
324 if a + 1 != b or self.base(b) == b: | |
325 if a >= 0: | |
326 base = self.base(a) | |
327 ta = decompress(chunks[self.base(a)]) | |
328 ta = construct(ta, base, a) | |
329 else: | |
330 ta = "" | |
331 | |
332 base = self.base(b) | |
333 if a > base: | |
334 base = a | |
335 tb = ta | |
336 else: | |
337 tb = decompress(chunks[self.base(b)]) | |
338 tb = construct(tb, base, b) | |
339 d = self.diff(ta, tb) | |
340 else: | |
341 d = decompress(chunks[b]) | |
342 | |
343 p = self.parents(n) | |
344 meta = n + p[0] + p[1] + linkmap[self.linkrev(n)] | |
345 l = struct.pack(">l", len(meta) + len(d) + 4) | |
346 deltas.append(l + meta + d) | |
347 | |
348 l = struct.pack(">l", sum(map(len, deltas)) + 4) | |
349 deltas.insert(0, l) | |
350 return "".join(deltas) | |
351 | |
352 def addgroup(self, data, linkmapper, transaction): | |
353 # given a set of deltas, add them to the revision log. the | |
354 # first delta is against its parent, which should be in our | |
355 # log, the rest are against the previous delta. | |
356 | |
65
d40cc5aacc31
Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents:
64
diff
changeset
|
357 if not data: return self.tip() |
46 | 358 |
359 # retrieve the parent revision of the delta chain | |
65
d40cc5aacc31
Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents:
64
diff
changeset
|
360 chain = data[24:44] |
46 | 361 |
362 # track the base of the current delta log | |
363 r = self.count() | |
364 t = r - 1 | |
365 | |
366 base = prev = -1 | |
367 start = end = 0 | |
368 if r: | |
369 start = self.start(self.base(t)) | |
370 end = self.end(t) | |
371 measure = self.length(self.base(t)) | |
372 base = self.base(t) | |
373 prev = self.tip() | |
374 | |
375 transaction.add(self.datafile, end) | |
376 transaction.add(self.indexfile, r * struct.calcsize(indexformat)) | |
377 dfh = self.opener(self.datafile, "a") | |
378 ifh = self.opener(self.indexfile, "a") | |
379 | |
380 # loop through our set of deltas | |
65
d40cc5aacc31
Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents:
64
diff
changeset
|
381 pos = 0 |
46 | 382 while pos < len(data): |
383 l, node, p1, p2, cs = struct.unpack(">l20s20s20s20s", | |
384 data[pos:pos+84]) | |
385 link = linkmapper(cs) | |
386 delta = data[pos + 84:pos + l] | |
387 pos += l | |
388 | |
389 # full versions are inserted when the needed deltas become | |
390 # comparable to the uncompressed text or when the previous | |
391 # version is not the one we have a delta against. We use | |
392 # the size of the previous full rev as a proxy for the | |
393 # current size. | |
394 | |
395 if chain == prev: | |
396 cdelta = compress(delta) | |
397 | |
398 if chain != prev or (end - start + len(cdelta)) > measure * 2: | |
399 # flush our writes here so we can read it in revision | |
400 dfh.flush() | |
401 ifh.flush() | |
65
d40cc5aacc31
Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents:
64
diff
changeset
|
402 text = self.revision(chain) |
73 | 403 text = self.patches(text, [delta]) |
46 | 404 chk = self.addrevision(text, transaction, link, p1, p2) |
405 if chk != node: | |
406 raise "consistency error adding group" | |
407 measure = len(text) | |
408 else: | |
409 e = (end, len(cdelta), self.base(t), link, p1, p2, node) | |
410 self.index.append(e) | |
411 self.nodemap[node] = r | |
412 dfh.write(cdelta) | |
413 ifh.write(struct.pack(indexformat, *e)) | |
414 | |
65
d40cc5aacc31
Fix up a bunch of bugs in the new merge code
mpm@selenic.com
parents:
64
diff
changeset
|
415 t, r, chain, prev = r, r + 1, node, node |
46 | 416 start = self.start(self.base(t)) |
417 end = self.end(t) | |
418 | |
419 dfh.close() | |
420 ifh.close() | |
421 return node |