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 from node import * |
8 from node import * |
|
9 from demandload import demandload |
|
10 demandload(globals(), "heapq") |
9 |
11 |
10 class changectx(object): |
12 class changectx(object): |
11 """A changecontext object makes access to data related to a particular |
13 """A changecontext object makes access to data related to a particular |
12 changeset convenient.""" |
14 changeset convenient.""" |
13 def __init__(self, repo, changeid): |
15 def __init__(self, repo, changeid): |
143 filelog=self._filelog) for x in c ] |
145 filelog=self._filelog) for x in c ] |
144 |
146 |
145 def annotate(self): |
147 def annotate(self): |
146 return self._filelog.annotate(self._filenode) |
148 return self._filelog.annotate(self._filenode) |
147 |
149 |
|
150 def ancestor(self, fc2): |
|
151 """ |
|
152 find the common ancestor file context, if any, of self, and fc2 |
|
153 """ |
|
154 |
|
155 a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) |
|
156 |
|
157 if a == b: |
|
158 return self |
|
159 |
|
160 if a[0] == b[0]: |
|
161 n = self._filelog.ancestor(a[1], b[1]) |
|
162 if n != nullid: |
|
163 return filectx(self._repo, self._path, |
|
164 fileid=n, filelog=self._filelog) |
|
165 |
|
166 # build a graph of all ancestors, crossing renames |
|
167 ag = {} |
|
168 fv = [a, b] |
|
169 flcache = {self._path:self._filelog, fc2._path:fc2._filelog} |
|
170 |
|
171 while fv: |
|
172 f,n = fv.pop() |
|
173 try: |
|
174 fl = flcache[f] |
|
175 except KeyError: |
|
176 flcache[f] = self._repo.file(f) |
|
177 fl = flcache[f] |
|
178 v = [n] |
|
179 while v: |
|
180 n = v.pop() |
|
181 c = (f, n) |
|
182 if c in ag: |
|
183 continue |
|
184 |
|
185 pl = [ n for n in fl.parents(n) if n != nullid ] |
|
186 v += pl |
|
187 pl = [ (f, n) for n in pl ] |
|
188 re = fl.renamed(n) |
|
189 if re: |
|
190 pl.append(re) |
|
191 if re not in ag: |
|
192 fv.append(re) |
|
193 ag[c] = pl |
|
194 |
|
195 dist = {} |
|
196 def depth(node): |
|
197 try: |
|
198 return dist[node] |
|
199 except KeyError: |
|
200 pl = ag[node] |
|
201 if not pl: |
|
202 dist[node] = 0 |
|
203 else: |
|
204 dist[node] = max([depth(p) for p in pl]) + 1 |
|
205 return dist[node] |
|
206 |
|
207 # traverse ancestors in order of decreasing distance from root |
|
208 def ancestors(vertex): |
|
209 h = [(-depth(vertex), vertex)] |
|
210 seen = {} |
|
211 while h: |
|
212 d, v = heapq.heappop(h) |
|
213 if v not in seen: |
|
214 seen[v] = 1 |
|
215 yield (-d, v) |
|
216 for p in ag[v]: |
|
217 heapq.heappush(h, (-depth(p), p)) |
|
218 |
|
219 def generations(vertex): |
|
220 sg, s = None, {} |
|
221 for g,v in ancestors(vertex): |
|
222 if g != sg: |
|
223 if sg: |
|
224 yield sg, s |
|
225 sg, s = g, {v:1} |
|
226 else: |
|
227 s[v] = 1 |
|
228 yield sg, s |
|
229 |
|
230 x = generations(a) |
|
231 y = generations(b) |
|
232 gx = x.next() |
|
233 gy = y.next() |
|
234 |
|
235 # increment each ancestor list until it is closer to root than |
|
236 # the other, or they match |
|
237 try: |
|
238 while 1: |
|
239 if gx[0] == gy[0]: |
|
240 # find the intersection |
|
241 i = [ n for n in gx[1] if n in gy[1] ] |
|
242 if i: |
|
243 fp,fn = i[0] |
|
244 fl = flcache[fp] |
|
245 return filectx(self._repo, fp, fileid=fn, filelog=fl) |
|
246 else: |
|
247 gy = y.next() |
|
248 gx = x.next() |
|
249 elif gx[0] < gy[0]: |
|
250 gy = y.next() |
|
251 else: |
|
252 gx = x.next() |
|
253 except StopIteration: |
|
254 return None |