Show More
@@ -6,6 +6,8 b'' | |||
|
6 | 6 | # of the GNU General Public License, incorporated herein by reference. |
|
7 | 7 | |
|
8 | 8 | from node import * |
|
9 | from demandload import demandload | |
|
10 | demandload(globals(), "heapq") | |
|
9 | 11 | |
|
10 | 12 | class changectx(object): |
|
11 | 13 | """A changecontext object makes access to data related to a particular |
@@ -145,3 +147,108 b' class filectx(object):' | |||
|
145 | 147 | def annotate(self): |
|
146 | 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 |
General Comments 0
You need to be logged in to leave comments.
Login now