328 

   329     def _stableparent(self, repo, headrev):

   330         """The parent of the changeset with reusable subrange

   331 

   332         For non-merge it is simple, there is a single parent. For Mercurial we

   333         have to find the right one. Since the stable sort use merge-point, we

   334         know that one of REV parents stable sort is a subset of REV stable

   335         sort. In other word:

   336 

   337             sort(::REV) = sort(::min(parents(REV))

   338                           + sort(only(max(parents(REV)), min(parents(REV)))

   339                           + [REV]

   340 

   341         We are looking for that `min(parents(REV))`. Since the subrange are

   342         based on the sort, we can reuse its subrange as well.

   343         """

   344         p1, p2 = repo.changelog.parentrevs(headrev)

   345         relevant_parent = None

   346         if p2 == nodemod.nullrev:

   347             relevant_parent = p1

   348         else:

   349             tiebreaker = stablesort._mergepoint_tie_breaker(repo)

   350             relevant_parent = min(p1, p2, key=tiebreaker)

   351         return relevant_parent

   352 

   353     def subranges(self, repo, rangeid):

   354         headrev, initial_index = rangeid

   355         # size 1 range can't be sliced

   356         if self.rangelength(repo, rangeid) == 1:

   357             return []

   358         # find were we need to slice

   359         slicepoint = self._slicepoint(repo, rangeid)

   360 

   361         stable_parent = self._stableparent(repo, headrev)

   362         stable_parent_depth = self.depthrev(repo, stable_parent)

   363         stable_parent_range = (stable_parent, initial_index)

   364 

   365         # top range is always the same, so we can build it early for all

   366         top_range = (headrev, slicepoint)

   367 

   368         # now find out about the lower range, if we are lucky there is only

   369         # one, otherwise we need to issue multiple one to cover every revision

   370         # on the lower set. (and cover them only once).

   371         if slicepoint == stable_parent_depth:

   372             # luckly shot, the parent is actually the head of the lower range

   373             subranges = [

   374                 stable_parent_range,

   375                 top_range,

   376             ]

   377         elif slicepoint < stable_parent_depth:

   378             # The parent is above the slice point,

   379             # it's lower subrange will be the same so we just get them,

   380             # (and the top range is always the same)

   381             subranges = self.subranges(repo, stable_parent_range)[:-1]

   382             subranges.append(top_range)

   383         elif initial_index < stable_parent_depth < slicepoint:

   384             # the parent is below the range we are considering, we need to

   385             # compute these uniques subranges

   386             subranges = [stable_parent_range]

   387             subranges.extend(self._unique_subranges(repo, headrev,

   388                                                     stable_parent_depth,

   389                                                     slicepoint))

   390             subranges.append(top_range)

   391         else:

   392             # we cannot reuse the parent range at all

   393             subranges = list(self._unique_subranges(repo, headrev,

   394                                                     initial_index,

   395                                                     slicepoint))

   396             subranges.append(top_range)

   397 

   398         return subranges

   399 

   400     def _unique_subranges(self, repo, headrev, initial_index, slicepoint):

   401         """Compute subrange unique to the exclusive part of merge"""

   402         result = []

   403         depth = repo.depthcache.get

   404         skips = depth(headrev) - slicepoint

   405 

   406         def nextrevs():

   407             revs = self._sortcache.walkfrom(repo, headrev)

   408             towalk = depth(headrev) - initial_index

   409             while 0 < towalk:

   410                 yield next(revs)

   411                 towalk -= 1

   412             yield None

   413         revs = nextrevs()

   414         for i in xrange(skips):

   415             next(revs)

   416         rangehead = current = next(revs)

   417         rangepath = self._sortcache.walkfrom(repo, current)

   418         nextonpath = next(rangepath, None)

   419         steps = 0

   420         while current is not None:

   421             while current == nextonpath and current is not None:

   422                 steps += 1

   423                 current = next(revs)

   424                 nextonpath = next(rangepath, None)

   425             result.append((rangehead, depth(rangehead) - steps))

   426             if current is not None:

   427                 rangehead = current

   428                 rangepath = self._sortcache.walkfrom(repo, current)

   429                 nextonpath = next(rangepath, None)

   430                 steps = 0

   431         result.reverse()

   432         return result