Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/revlog.py @ 3135:b1db258e875c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Abstract ancestor algorithm into generic function Make depth calculation non-recursive Add simple shortcut for linear ancestry Convert context to use ancestor function make memoized parents function Convert revlog to use ancestor function
author Matt Mackall <mpm@selenic.com>
date Wed, 20 Sep 2006 16:50:50 -0500
parents cff3c58a5766
children 1fd1cdcc4200
comparison
equal deleted inserted replaced
3134:abd9a05fca0b 3135:b1db258e875c
11 """ 11 """
12 12
13 from node import * 13 from node import *
14 from i18n import gettext as _ 14 from i18n import gettext as _
15 from demandload import demandload 15 from demandload import demandload
16 demandload(globals(), "binascii changegroup errno heapq mdiff os") 16 demandload(globals(), "binascii changegroup errno ancestor mdiff os")
17 demandload(globals(), "sha struct util zlib") 17 demandload(globals(), "sha struct util zlib")
18 18
19 # revlog version strings 19 # revlog version strings
20 REVLOGV0 = 0 20 REVLOGV0 = 0
21 REVLOGNG = 1 21 REVLOGNG = 1
1014 return node 1014 return node
1015 1015
1016 def ancestor(self, a, b): 1016 def ancestor(self, a, b):
1017 """calculate the least common ancestor of nodes a and b""" 1017 """calculate the least common ancestor of nodes a and b"""
1018 1018
1019 # start with some short cuts for the linear cases 1019 def parents(node):
1020 if a == b: 1020 return [p for p in self.parents(node) if p != nullid]
1021 return a 1021
1022 ra = self.rev(a) 1022 return ancestor.ancestor(a, b, parents) or nullid
1023 rb = self.rev(b)
1024 if ra < rb:
1025 last = b
1026 first = a
1027 else:
1028 last = a
1029 first = b
1030
1031 # reachable won't include stop in the list, so we have to use a parent
1032 reachable = self.reachable(last, stop=self.parents(first)[0])
1033 if first in reachable:
1034 return first
1035
1036 # calculate the distance of every node from root
1037 dist = {nullid: 0}
1038 for i in xrange(self.count()):
1039 n = self.node(i)
1040 p1, p2 = self.parents(n)
1041 dist[n] = max(dist[p1], dist[p2]) + 1
1042
1043 # traverse ancestors in order of decreasing distance from root
1044 def ancestors(node):
1045 # we store negative distances because heap returns smallest member
1046 h = [(-dist[node], node)]
1047 seen = {}
1048 while h:
1049 d, n = heapq.heappop(h)
1050 if n not in seen:
1051 seen[n] = 1
1052 yield (-d, n)
1053 for p in self.parents(n):
1054 heapq.heappush(h, (-dist[p], p))
1055
1056 def generations(node):
1057 sg, s = None, {}
1058 for g,n in ancestors(node):
1059 if g != sg:
1060 if sg:
1061 yield sg, s
1062 sg, s = g, {n:1}
1063 else:
1064 s[n] = 1
1065 yield sg, s
1066
1067 x = generations(a)
1068 y = generations(b)
1069 gx = x.next()
1070 gy = y.next()
1071
1072 # increment each ancestor list until it is closer to root than
1073 # the other, or they match
1074 while 1:
1075 #print "ancestor gen %s %s" % (gx[0], gy[0])
1076 if gx[0] == gy[0]:
1077 # find the intersection
1078 i = [ n for n in gx[1] if n in gy[1] ]
1079 if i:
1080 return i[0]
1081 else:
1082 #print "next"
1083 gy = y.next()
1084 gx = x.next()
1085 elif gx[0] < gy[0]:
1086 #print "next y"
1087 gy = y.next()
1088 else:
1089 #print "next x"
1090 gx = x.next()
1091 1023
1092 def group(self, nodelist, lookup, infocollect=None): 1024 def group(self, nodelist, lookup, infocollect=None):
1093 """calculate a delta group 1025 """calculate a delta group
1094 1026
1095 Given a list of changeset revs, return a set of deltas and 1027 Given a list of changeset revs, return a set of deltas and