16 demandload(globals(), "binascii changegroup errno heapq mdiff os")

    16 demandload(globals(), "binascii changegroup errno ancestor mdiff os")

  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()