Mercurial > public > mercurial-scm > hg

comparison mercurial/revlog.py @ 147:b6d8ed7aeba0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A new ancestor algorithm The old ancestor algorithm could get fooled into returning ancestors closer to root than it ought to. Hopefully this one, which strictly orders its search by distance from room, will be foolproof.
author mpm@selenic.com
date Tue, 24 May 2005 23:11:44 -0800
parents f6d1f8a84372
children 083c38bdfa64 083c38bdfa64
comparison
equal deleted inserted replaced
146:4a828422247d 147:b6d8ed7aeba0
6 # Copyright 2005 Matt Mackall <mpm@selenic.com> 6 # Copyright 2005 Matt Mackall <mpm@selenic.com>
7 # 7 #
8 # This software may be used and distributed according to the terms 8 # This software may be used and distributed according to the terms
9 # of the GNU General Public License, incorporated herein by reference. 9 # of the GNU General Public License, incorporated herein by reference.
10 10
11 import zlib, struct, sha, os, tempfile, binascii 11 import zlib, struct, sha, os, tempfile, binascii, heapq
12 from mercurial import mdiff 12 from mercurial import mdiff
13 13
14 def hex(node): return binascii.hexlify(node) 14 def hex(node): return binascii.hexlify(node)
15 def bin(node): return binascii.unhexlify(node) 15 def bin(node): return binascii.unhexlify(node)
16 def short(node): return hex(node[:4]) 16 def short(node): return hex(node[:4])
274 274
275 self.cache = (node, n, text) 275 self.cache = (node, n, text)
276 return node 276 return node
277 277
278 def ancestor(self, a, b): 278 def ancestor(self, a, b):
279 def expand(list, map): 279 # calculate the distance of every node from root
280 a = [] 280 dist = {nullid: 0}
281 while list: 281 for i in xrange(self.count()):
282 n = list.pop(0) 282 n = self.node(i)
283 map[n] = 1 283 p1, p2 = self.parents(n)
284 yield n 284 dist[n] = max(dist[p1], dist[p2]) + 1
285 for p in self.parents(n): 285
286 if p != nullid and p not in map: 286 # traverse ancestors in order of decreasing distance from root
287 list.append(p) 287 def ancestors(node):
288 yield nullid 288 # we store negative distances because heap returns smallest member
289 289 h = [(-dist[node], node)]
290 amap = {} 290 seen = {}
291 bmap = {} 291 earliest = self.count()
292 ag = expand([a], amap) 292 while h:
293 bg = expand([b], bmap) 293 d, n = heapq.heappop(h)
294 adone = bdone = 0 294 r = self.rev(n)
295 295 if n not in seen:
296 while not adone or not bdone: 296 seen[n] = 1
297 if not adone: 297 yield (-d, n)
298 an = ag.next() 298 for p in self.parents(n):
299 if an == nullid: 299 heapq.heappush(h, (-dist[p], p))
300 adone = 1 300
301 elif an in bmap: 301 x = ancestors(a)
302 return an 302 y = ancestors(b)
303 if not bdone: 303 lx = x.next()
304 bn = bg.next() 304 ly = y.next()
305 if bn == nullid: 305
306 bdone = 1 306 # increment each ancestor list until it is closer to root than
307 elif bn in amap: 307 # the other, or they match
308 return bn 308 while 1:
309 309 if lx == ly:
310 return nullid 310 return lx[1]
311 elif lx < ly:
312 ly = y.next()
313 elif lx > ly:
314 lx = x.next()
311 315
312 def group(self, linkmap): 316 def group(self, linkmap):
313 # given a list of changeset revs, return a set of deltas and 317 # given a list of changeset revs, return a set of deltas and
314 # metadata corresponding to nodes. the first delta is 318 # metadata corresponding to nodes. the first delta is
315 # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to 319 # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to