# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@ens-lyon.org>
# Date 1489129061 28800
# Node ID 3f787182509f7abd9a095e156150d27b7e8c29c5
# Parent  010a8af416a068782f12f61932ee3d6b4bb7117c
discovery: introduce "stable slicing" methods

We introduce new code that leverage the stable sorting to slices a graph in a
way "stable" accross repository. This should allow us to use theses slices for
obsolescence markers discovery.

diff -r 010a8af416a0 -r 3f787182509f hgext3rd/evolve/obsdiscovery.py
--- a/hgext3rd/evolve/obsdiscovery.py	Thu Mar 09 19:18:11 2017 -0800
+++ b/hgext3rd/evolve/obsdiscovery.py	Thu Mar 09 22:57:41 2017 -0800
@@ -16,6 +16,7 @@
 
 import collections
 import hashlib
+import math
 
 from mercurial import (
     cmdutil,
@@ -29,6 +30,7 @@
     obsolete,
     scmutil,
     setdiscovery,
+    util,
     wireproto,
 )
 from mercurial.hgweb import hgweb_mod
@@ -268,6 +270,131 @@
             stack.extend(cs)   # stack the rest for later
     return result
 
+##############################
+### Range Hash computation ###
+##############################
+@eh.command(
+    'debugstablerange',
+    [
+        ('', 'rev', [], 'heads to start from'),
+    ],
+    _(''))
+def debugstablerange(ui, repo, **opts):
+    """display the ::REVS set topologically sorted in a stable way
+    """
+    n = repo.changelog.node
+    s = node.short
+    revs = scmutil.revrange(repo, opts['rev'])
+    toproceed = [_range(repo, r, 0, ) for r in revs]
+    ranges = set(toproceed)
+    while toproceed:
+        entry = toproceed.pop()
+        for r in entry.subranges():
+            if r not in ranges:
+                ranges.add(r)
+                toproceed.append(r)
+    ranges = list(ranges)
+    ranges.sort(key=lambda r: (-len(r), n(r.head)))
+    ui.status('rev         node index size depth\n')
+    for r in ranges:
+        ui.status('%3d %s %5d %4d %5d\n'
+                  % (r.head, s(n(r.head)), r.index, len(r), r.depth))
+
+_depthcache = {}
+def _depth(repo, rev):
+    cl = repo.changelog
+    n = cl.node(rev)
+    depth = _depthcache.get(n, None)
+    if depth is None:
+        depth = _depthcache[n] = len(list(cl.ancestors([rev], inclusive=True)))
+    return depth
+
+def _hlp2(i):
+    """return highest power of two lower than 'i'"""
+    return 2 ** int(math.log(i - 1, 2))
+
+
+class _range(object):
+
+    def __init__(self, repo, head, index, revs=None):
+        self._repo = repo
+        self.head = head
+        self.index = index
+        if revs is not None:
+            self._revs = revs
+        assert index < self.depth, (head, index, self.depth, revs)
+
+    def __hash__(self):
+        return self._id
+
+    def __eq__(self, other):
+        if type(self) != type(other):
+            raise NotImplementedError()
+        return self.stablekey == other.stablekey
+
+    @util.propertycache
+    def _id(self):
+        return hash(self.stablekey)
+
+    @util.propertycache
+    def stablekey(self):
+        return (self.node, self.index)
+
+    @util.propertycache
+    def node(self):
+        return self._repo.changelog.node(self.head)
+
+    def __len__(self):
+        return len(self._revs)
+
+    @util.propertycache
+    def depth(self):
+        return _depth(self._repo, self.head)
+
+    @util.propertycache
+    def _revs(self):
+        return _stablesort(self._repo, [self.head])[self.index:]
+
+    def _slicesat(self, globalindex):
+        localindex = globalindex - self.index
+
+        cl = self._repo.changelog
+
+        bottom = self._revs[:localindex]
+        top = self._revs[localindex:]
+        bheads = self._repo.revs('heads(%ld)', bottom)
+        result = []
+        if len(bheads) == 1:
+            newhead = bottom[-1]
+            newstart = _depth(self._repo, newhead) - len(bottom)
+            result.append(_range(self._repo, newhead, newstart, bottom))
+        else:
+            cl = self._repo.changelog
+            for h in bheads:
+                subset = cl.ancestors([h], inclusive=True)
+                hrevs = [r for r in bottom if r in subset]
+                start = _depth(self._repo, h) - len(hrevs)
+                entry = _range(self._repo, h, start, [r for r in bottom if r in subset])
+                result.append(entry)
+        result.append(_range(self._repo, self.head, globalindex, top))
+        return result
+
+    def subranges(self):
+        if len(self) == 1:
+            return []
+        step = _hlp2(self.depth)
+        standard_start = 0
+        while standard_start < self.index and 0 < step:
+            if standard_start + step < self.depth:
+                standard_start += step
+            step //= 2
+        if self.index == standard_start:
+            slicesize = _hlp2(len(self))
+            return self._slicesat(self.index + slicesize)
+        else:
+            assert standard_start < self.depth
+            return self._slicesat(standard_start)
+
 #############################
 ### Tree Hash computation ###
 #############################
diff -r 010a8af416a0 -r 3f787182509f tests/test-stablerange.t
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-stablerange.t	Thu Mar 09 22:57:41 2017 -0800
@@ -0,0 +1,672 @@
+Test for stable ordering capabilities
+=====================================
+
+  $ . $TESTDIR/testlib/pythonpath.sh
+
+  $ cat << EOF >> $HGRCPATH
+  > [extensions]
+  > hgext3rd.evolve =
+  > [ui]
+  > logtemplate = "{rev} {node|short} {desc} {tags}\n"
+  > EOF
+
+Simple linear test
+==================
+
+  $ hg init repo_linear
+  $ cd repo_linear
+  $ hg debugbuilddag '.+6'
+  $ hg debugstablerange --rev 1
+  rev         node index size depth
+    1 66f7d451a68b     0    2     2
+    0 1ea73414a91b     0    1     1
+    1 66f7d451a68b     1    1     2
+  $ hg debugstablerange --rev 1 > 1.range
+
+bigger subset reuse most of the previous one
+
+  $ hg debugstablerange --rev 4
+  rev         node index size depth
+    4 bebd167eb94d     0    5     5
+    3 2dc09a01254d     0    4     4
+    3 2dc09a01254d     2    2     4
+    1 66f7d451a68b     0    2     2
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    1 66f7d451a68b     1    1     2
+    4 bebd167eb94d     4    1     5
+  $ hg debugstablerange --rev 4 > 4.range
+  $ diff -u 1.range 4.range
+  --- 1.range	* (glob)
+  +++ 4.range	* (glob)
+  @@ -1,4 +1,10 @@
+   rev         node index size depth
+  +  4 bebd167eb94d     0    5     5
+  +  3 2dc09a01254d     0    4     4
+  +  3 2dc09a01254d     2    2     4
+     1 66f7d451a68b     0    2     2
+  +  2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+  +  3 2dc09a01254d     3    1     4
+     1 66f7d451a68b     1    1     2
+  +  4 bebd167eb94d     4    1     5
+  [1]
+
+Using a range not ending on 2**N boundary
+we fall back on 2**N as much as possible
+
+  $ hg debugstablerange --rev 5
+  rev         node index size depth
+    5 c8d03c1b5e94     0    6     6
+    3 2dc09a01254d     0    4     4
+    3 2dc09a01254d     2    2     4
+    1 66f7d451a68b     0    2     2
+    5 c8d03c1b5e94     4    2     6
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    1 66f7d451a68b     1    1     2
+    4 bebd167eb94d     4    1     5
+    5 c8d03c1b5e94     5    1     6
+  $ hg debugstablerange --rev 5 > 5.range
+  $ diff -u 4.range 5.range
+  --- 4.range	* (glob)
+  +++ 5.range	* (glob)
+  @@ -1,10 +1,12 @@
+   rev         node index size depth
+  -  4 bebd167eb94d     0    5     5
+  +  5 c8d03c1b5e94     0    6     6
+     3 2dc09a01254d     0    4     4
+     3 2dc09a01254d     2    2     4
+     1 66f7d451a68b     0    2     2
+  +  5 c8d03c1b5e94     4    2     6
+     2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+     3 2dc09a01254d     3    1     4
+     1 66f7d451a68b     1    1     2
+     4 bebd167eb94d     4    1     5
+  +  5 c8d03c1b5e94     5    1     6
+  [1]
+
+Even two unperfect range overlap a lot
+
+  $ hg debugstablerange --rev tip
+  rev         node index size depth
+    6 f69452c5b1af     0    7     7
+    3 2dc09a01254d     0    4     4
+    6 f69452c5b1af     4    3     7
+    3 2dc09a01254d     2    2     4
+    1 66f7d451a68b     0    2     2
+    5 c8d03c1b5e94     4    2     6
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    1 66f7d451a68b     1    1     2
+    4 bebd167eb94d     4    1     5
+    5 c8d03c1b5e94     5    1     6
+    6 f69452c5b1af     6    1     7
+  $ hg debugstablerange --rev tip > tip.range
+  $ diff -u 5.range tip.range
+  --- 5.range	* (glob)
+  +++ tip.range	* (glob)
+  @@ -1,6 +1,7 @@
+   rev         node index size depth
+  -  5 c8d03c1b5e94     0    6     6
+  +  6 f69452c5b1af     0    7     7
+     3 2dc09a01254d     0    4     4
+  +  6 f69452c5b1af     4    3     7
+     3 2dc09a01254d     2    2     4
+     1 66f7d451a68b     0    2     2
+     5 c8d03c1b5e94     4    2     6
+  @@ -10,3 +11,4 @@
+     1 66f7d451a68b     1    1     2
+     4 bebd167eb94d     4    1     5
+     5 c8d03c1b5e94     5    1     6
+  +  6 f69452c5b1af     6    1     7
+  [1]
+
+  $ cd ..
+
+Case with merge
+===============
+
+Simple case: branching is on a boundary
+--------------------------------------------
+
+  $ hg init repo_merge_split_on_boundary
+  $ cd repo_merge_split_on_boundary
+  $ hg debugbuilddag '.:base
+  > +3:left
+  > <base+3:right
+  > <left/right:merge
+  > +2:head
+  > '
+  $ hg log -G
+  o  9 0338daf18215 r9 head tip
+  |
+  o  8 71b32fcf3f71 r8
+  |
+  o    7 5f18015f9110 r7 merge
+  |\
+  | o  6 a2f58e9c1e56 r6 right
+  | |
+  | o  5 3a367db1fabc r5
+  | |
+  | o  4 e7bd5218ca15 r4
+  | |
+  o |  3 2dc09a01254d r3 left
+  | |
+  o |  2 01241442b3c2 r2
+  | |
+  o |  1 66f7d451a68b r1
+  |/
+  o  0 1ea73414a91b r0 base
+  
+
+Each of the linear branch reuse range internally
+
+(left branch)
+
+  $ hg debugstablerange --rev 'left~2'
+  rev         node index size depth
+    1 66f7d451a68b     0    2     2
+    0 1ea73414a91b     0    1     1
+    1 66f7d451a68b     1    1     2
+  $ hg debugstablerange --rev 'left~2' > left-2.range
+  $ hg debugstablerange --rev left
+  rev         node index size depth
+    3 2dc09a01254d     0    4     4
+    3 2dc09a01254d     2    2     4
+    1 66f7d451a68b     0    2     2
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    1 66f7d451a68b     1    1     2
+  $ hg debugstablerange --rev 'left' > left.range
+  $ diff -u left-2.range left.range
+  --- left-2.range	* (glob)
+  +++ left.range	* (glob)
+  @@ -1,4 +1,8 @@
+   rev         node index size depth
+  +  3 2dc09a01254d     0    4     4
+  +  3 2dc09a01254d     2    2     4
+     1 66f7d451a68b     0    2     2
+  +  2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+  +  3 2dc09a01254d     3    1     4
+     1 66f7d451a68b     1    1     2
+  [1]
+
+(right branch)
+
+  $ hg debugstablerange --rev right~2
+  rev         node index size depth
+    4 e7bd5218ca15     0    2     2
+    0 1ea73414a91b     0    1     1
+    4 e7bd5218ca15     1    1     2
+  $ hg debugstablerange --rev 'right~2' > right-2.range
+  $ hg debugstablerange --rev right
+  rev         node index size depth
+    6 a2f58e9c1e56     0    4     4
+    6 a2f58e9c1e56     2    2     4
+    4 e7bd5218ca15     0    2     2
+    0 1ea73414a91b     0    1     1
+    5 3a367db1fabc     2    1     3
+    6 a2f58e9c1e56     3    1     4
+    4 e7bd5218ca15     1    1     2
+  $ hg debugstablerange --rev 'right' > right.range
+  $ diff -u right-2.range right.range
+  --- right-2.range	* (glob)
+  +++ right.range	* (glob)
+  @@ -1,4 +1,8 @@
+   rev         node index size depth
+  +  6 a2f58e9c1e56     0    4     4
+  +  6 a2f58e9c1e56     2    2     4
+     4 e7bd5218ca15     0    2     2
+     0 1ea73414a91b     0    1     1
+  +  5 3a367db1fabc     2    1     3
+  +  6 a2f58e9c1e56     3    1     4
+     4 e7bd5218ca15     1    1     2
+  [1]
+
+The merge reuse as much of the slicing created for one of the branch
+
+  $ hg debugstablerange --rev merge
+  rev         node index size depth
+    7 5f18015f9110     0    8     8
+    3 2dc09a01254d     0    4     4
+    7 5f18015f9110     4    4     8
+    3 2dc09a01254d     2    2     4
+    5 3a367db1fabc     1    2     3
+    7 5f18015f9110     6    2     8
+    1 66f7d451a68b     0    2     2
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    5 3a367db1fabc     2    1     3
+    7 5f18015f9110     7    1     8
+    1 66f7d451a68b     1    1     2
+    6 a2f58e9c1e56     3    1     4
+    4 e7bd5218ca15     1    1     2
+  $ hg debugstablerange --rev 'merge' > merge.range
+  $ diff -u left.range merge.range
+  --- left.range	* (glob)
+  +++ merge.range	* (glob)
+  @@ -1,8 +1,16 @@
+   rev         node index size depth
+  +  7 5f18015f9110     0    8     8
+     3 2dc09a01254d     0    4     4
+  +  7 5f18015f9110     4    4     8
+     3 2dc09a01254d     2    2     4
+  +  5 3a367db1fabc     1    2     3
+  +  7 5f18015f9110     6    2     8
+     1 66f7d451a68b     0    2     2
+     2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+     3 2dc09a01254d     3    1     4
+  +  5 3a367db1fabc     2    1     3
+  +  7 5f18015f9110     7    1     8
+     1 66f7d451a68b     1    1     2
+  +  6 a2f58e9c1e56     3    1     4
+  +  4 e7bd5218ca15     1    1     2
+  [1]
+  $ diff -u right.range merge.range
+  --- right.range	* (glob)
+  +++ merge.range	* (glob)
+  @@ -1,8 +1,16 @@
+   rev         node index size depth
+  -  6 a2f58e9c1e56     0    4     4
+  -  6 a2f58e9c1e56     2    2     4
+  -  4 e7bd5218ca15     0    2     2
+  +  7 5f18015f9110     0    8     8
+  +  3 2dc09a01254d     0    4     4
+  +  7 5f18015f9110     4    4     8
+  +  3 2dc09a01254d     2    2     4
+  +  5 3a367db1fabc     1    2     3
+  +  7 5f18015f9110     6    2     8
+  +  1 66f7d451a68b     0    2     2
+  +  2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+  +  3 2dc09a01254d     3    1     4
+     5 3a367db1fabc     2    1     3
+  +  7 5f18015f9110     7    1     8
+  +  1 66f7d451a68b     1    1     2
+     6 a2f58e9c1e56     3    1     4
+     4 e7bd5218ca15     1    1     2
+  [1]
+  $ cd ..
+
+slice create multiple heads
+---------------------------
+
+  $ hg init repo_merge_split_heads
+  $ cd repo_merge_split_heads
+  $ hg debugbuilddag '.:base
+  > +4:left
+  > <base+5:right
+  > <left/right:merge
+  > +2:head
+  > '
+  $ hg debugbuilddag '.:base
+  > +3:left
+  > <base+3:right
+  > <left/right:merge
+  > +2:head
+  > '
+  abort: repository is not empty
+  [255]
+  $ hg log -G
+  o  12 e6b8d5b46647 r12 head tip
+  |
+  o  11 485383494a89 r11
+  |
+  o    10 8aca7f8c9bd2 r10 merge
+  |\
+  | o  9 f4b7da68b467 r9 right
+  | |
+  | o  8 857477a9aebb r8
+  | |
+  | o  7 42b07e8da27d r7
+  | |
+  | o  6 b9bc20507e0b r6
+  | |
+  | o  5 de561312eff4 r5
+  | |
+  o |  4 bebd167eb94d r4 left
+  | |
+  o |  3 2dc09a01254d r3
+  | |
+  o |  2 01241442b3c2 r2
+  | |
+  o |  1 66f7d451a68b r1
+  |/
+  o  0 1ea73414a91b r0 base
+  
+
+Each of the linear branch reuse range internally
+
+(left branch)
+
+  $ hg debugstablerange --rev 'left~2'
+  rev         node index size depth
+    2 01241442b3c2     0    3     3
+    1 66f7d451a68b     0    2     2
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    1 66f7d451a68b     1    1     2
+  $ hg debugstablerange --rev 'left~2' > left-2.range
+  $ hg debugstablerange --rev left
+  rev         node index size depth
+    4 bebd167eb94d     0    5     5
+    3 2dc09a01254d     0    4     4
+    3 2dc09a01254d     2    2     4
+    1 66f7d451a68b     0    2     2
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    1 66f7d451a68b     1    1     2
+    4 bebd167eb94d     4    1     5
+  $ hg debugstablerange --rev 'left' > left.range
+  $ diff -u left-2.range left.range
+  --- left-2.range	* (glob)
+  +++ left.range	* (glob)
+  @@ -1,6 +1,10 @@
+   rev         node index size depth
+  -  2 01241442b3c2     0    3     3
+  +  4 bebd167eb94d     0    5     5
+  +  3 2dc09a01254d     0    4     4
+  +  3 2dc09a01254d     2    2     4
+     1 66f7d451a68b     0    2     2
+     2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+  +  3 2dc09a01254d     3    1     4
+     1 66f7d451a68b     1    1     2
+  +  4 bebd167eb94d     4    1     5
+  [1]
+
+(right branch)
+
+  $ hg debugstablerange --rev right~2
+  rev         node index size depth
+    7 42b07e8da27d     0    4     4
+    7 42b07e8da27d     2    2     4
+    5 de561312eff4     0    2     2
+    0 1ea73414a91b     0    1     1
+    7 42b07e8da27d     3    1     4
+    6 b9bc20507e0b     2    1     3
+    5 de561312eff4     1    1     2
+  $ hg debugstablerange --rev 'right~2' > right-2.range
+  $ hg debugstablerange --rev right
+  rev         node index size depth
+    9 f4b7da68b467     0    6     6
+    7 42b07e8da27d     0    4     4
+    7 42b07e8da27d     2    2     4
+    5 de561312eff4     0    2     2
+    9 f4b7da68b467     4    2     6
+    0 1ea73414a91b     0    1     1
+    7 42b07e8da27d     3    1     4
+    8 857477a9aebb     4    1     5
+    6 b9bc20507e0b     2    1     3
+    5 de561312eff4     1    1     2
+    9 f4b7da68b467     5    1     6
+  $ hg debugstablerange --rev 'right' > right.range
+  $ diff -u right-2.range right.range
+  --- right-2.range	* (glob)
+  +++ right.range	* (glob)
+  @@ -1,8 +1,12 @@
+   rev         node index size depth
+  +  9 f4b7da68b467     0    6     6
+     7 42b07e8da27d     0    4     4
+     7 42b07e8da27d     2    2     4
+     5 de561312eff4     0    2     2
+  +  9 f4b7da68b467     4    2     6
+     0 1ea73414a91b     0    1     1
+     7 42b07e8da27d     3    1     4
+  +  8 857477a9aebb     4    1     5
+     6 b9bc20507e0b     2    1     3
+     5 de561312eff4     1    1     2
+  +  9 f4b7da68b467     5    1     6
+  [1]
+
+In this case, the bottom of the split will have multiple heads,
+
+So we'll create more than 1 subrange out of it.
+
+We are still able to reuse one of the branch however
+
+  $ hg debugstablerange --rev merge
+  rev         node index size depth
+   10 8aca7f8c9bd2     0   11    11
+    4 bebd167eb94d     0    5     5
+    3 2dc09a01254d     0    4     4
+    7 42b07e8da27d     0    4     4
+   10 8aca7f8c9bd2     8    3    11
+    3 2dc09a01254d     2    2     4
+    7 42b07e8da27d     2    2     4
+    1 66f7d451a68b     0    2     2
+    5 de561312eff4     0    2     2
+    9 f4b7da68b467     4    2     6
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    7 42b07e8da27d     3    1     4
+    1 66f7d451a68b     1    1     2
+    8 857477a9aebb     4    1     5
+   10 8aca7f8c9bd2    10    1    11
+    6 b9bc20507e0b     2    1     3
+    4 bebd167eb94d     4    1     5
+    5 de561312eff4     1    1     2
+    9 f4b7da68b467     5    1     6
+  $ hg debugstablerange --rev 'merge' > merge.range
+  $ diff -u left.range merge.range
+  --- left.range	* (glob)
+  +++ merge.range	* (glob)
+  @@ -1,10 +1,22 @@
+   rev         node index size depth
+  + 10 8aca7f8c9bd2     0   11    11
+     4 bebd167eb94d     0    5     5
+     3 2dc09a01254d     0    4     4
+  +  7 42b07e8da27d     0    4     4
+  + 10 8aca7f8c9bd2     8    3    11
+     3 2dc09a01254d     2    2     4
+  +  7 42b07e8da27d     2    2     4
+     1 66f7d451a68b     0    2     2
+  +  5 de561312eff4     0    2     2
+  +  9 f4b7da68b467     4    2     6
+     2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+     3 2dc09a01254d     3    1     4
+  +  7 42b07e8da27d     3    1     4
+     1 66f7d451a68b     1    1     2
+  +  8 857477a9aebb     4    1     5
+  + 10 8aca7f8c9bd2    10    1    11
+  +  6 b9bc20507e0b     2    1     3
+     4 bebd167eb94d     4    1     5
+  +  5 de561312eff4     1    1     2
+  +  9 f4b7da68b467     5    1     6
+  [1]
+  $ diff -u right.range merge.range
+  --- right.range	* (glob)
+  +++ merge.range	* (glob)
+  @@ -1,12 +1,22 @@
+   rev         node index size depth
+  -  9 f4b7da68b467     0    6     6
+  + 10 8aca7f8c9bd2     0   11    11
+  +  4 bebd167eb94d     0    5     5
+  +  3 2dc09a01254d     0    4     4
+     7 42b07e8da27d     0    4     4
+  + 10 8aca7f8c9bd2     8    3    11
+  +  3 2dc09a01254d     2    2     4
+     7 42b07e8da27d     2    2     4
+  +  1 66f7d451a68b     0    2     2
+     5 de561312eff4     0    2     2
+     9 f4b7da68b467     4    2     6
+  +  2 01241442b3c2     2    1     3
+     0 1ea73414a91b     0    1     1
+  +  3 2dc09a01254d     3    1     4
+     7 42b07e8da27d     3    1     4
+  +  1 66f7d451a68b     1    1     2
+     8 857477a9aebb     4    1     5
+  + 10 8aca7f8c9bd2    10    1    11
+     6 b9bc20507e0b     2    1     3
+  +  4 bebd167eb94d     4    1     5
+     5 de561312eff4     1    1     2
+     9 f4b7da68b467     5    1     6
+  [1]
+
+Range above the merge, reuse subrange from the merge
+
+  $ hg debugstablerange --rev tip
+  rev         node index size depth
+   12 e6b8d5b46647     0   13    13
+    4 bebd167eb94d     0    5     5
+   12 e6b8d5b46647     8    5    13
+    3 2dc09a01254d     0    4     4
+    7 42b07e8da27d     0    4     4
+   11 485383494a89     8    4    12
+    3 2dc09a01254d     2    2     4
+    7 42b07e8da27d     2    2     4
+   11 485383494a89    10    2    12
+    1 66f7d451a68b     0    2     2
+    5 de561312eff4     0    2     2
+    9 f4b7da68b467     4    2     6
+    2 01241442b3c2     2    1     3
+    0 1ea73414a91b     0    1     1
+    3 2dc09a01254d     3    1     4
+    7 42b07e8da27d     3    1     4
+   11 485383494a89    11    1    12
+    1 66f7d451a68b     1    1     2
+    8 857477a9aebb     4    1     5
+   10 8aca7f8c9bd2    10    1    11
+    6 b9bc20507e0b     2    1     3
+    4 bebd167eb94d     4    1     5
+    5 de561312eff4     1    1     2
+   12 e6b8d5b46647    12    1    13
+    9 f4b7da68b467     5    1     6
+  $ hg debugstablerange --rev 'tip' > tip.range
+  $ diff -u merge.range tip.range
+  --- merge.range	* (glob)
+  +++ tip.range	* (glob)
+  @@ -1,11 +1,13 @@
+   rev         node index size depth
+  - 10 8aca7f8c9bd2     0   11    11
+  + 12 e6b8d5b46647     0   13    13
+     4 bebd167eb94d     0    5     5
+  + 12 e6b8d5b46647     8    5    13
+     3 2dc09a01254d     0    4     4
+     7 42b07e8da27d     0    4     4
+  - 10 8aca7f8c9bd2     8    3    11
+  + 11 485383494a89     8    4    12
+     3 2dc09a01254d     2    2     4
+     7 42b07e8da27d     2    2     4
+  + 11 485383494a89    10    2    12
+     1 66f7d451a68b     0    2     2
+     5 de561312eff4     0    2     2
+     9 f4b7da68b467     4    2     6
+  @@ -13,10 +15,12 @@
+     0 1ea73414a91b     0    1     1
+     3 2dc09a01254d     3    1     4
+     7 42b07e8da27d     3    1     4
+  + 11 485383494a89    11    1    12
+     1 66f7d451a68b     1    1     2
+     8 857477a9aebb     4    1     5
+    10 8aca7f8c9bd2    10    1    11
+     6 b9bc20507e0b     2    1     3
+     4 bebd167eb94d     4    1     5
+     5 de561312eff4     1    1     2
+  + 12 e6b8d5b46647    12    1    13
+     9 f4b7da68b467     5    1     6
+  [1]
+
+  $ cd ..
+
+Tests range with criss cross merge in the graph
+===============================================
+
+  $ hg init repo_criss_cross
+  $ cd repo_criss_cross
+  $ hg debugbuilddag '
+  > ..:g   # 2 nodes, tagged "g"
+  > <2.:h   # another node base one -2 -> 0, tagged "h"
+  > *1/2:m # merge -1 and -2 (1, 2), tagged "m"
+  > <2+2:i # 2 nodes based on -2, tag head as "i"
+  > .:c    # 1 node tagged "c"
+  > <m+3:a # 3 nodes base on the "m" tag
+  > <2.:b  # 1 node based on -2; tagged "b"
+  > <m+2:d # 2 nodes from "m" tagged "d"
+  > <2.:e  # 1 node based on -2, tagged "e"
+  > <m+1:f # 1 node based on "m" tagged "f"
+  > <i/f   # merge "i" and "f"
+  > '
+  $ hg log -G
+  o    15 1d8d22637c2d r15 tip
+  |\
+  | o  14 43227190fef8 r14 f
+  | |
+  | | o  13 b4594d867745 r13 e
+  | | |
+  | | | o  12 e46a4836065c r12 d
+  | | |/
+  | | o  11 bab5d5bf48bd r11
+  | |/
+  | | o  10 ff43616e5d0f r10 b
+  | | |
+  | | | o  9 dcbb326fdec2 r9 a
+  | | |/
+  | | o  8 d62d843c9a01 r8
+  | | |
+  | | o  7 e7d9710d9fc6 r7
+  | |/
+  +---o  6 2702dd0c91e7 r6 c
+  | |
+  o |  5 f0f3ef9a6cd5 r5 i
+  | |
+  o |  4 4c748ffd1a46 r4
+  | |
+  | o  3 2b6d669947cd r3 m
+  |/|
+  o |  2 fa942426a6fd r2 h
+  | |
+  | o  1 66f7d451a68b r1 g
+  |/
+  o  0 1ea73414a91b r0
+  
+  $ hg debugstablerange --rev 'head()'
+  rev         node index size depth
+   15 1d8d22637c2d     0    8     8
+    9 dcbb326fdec2     0    7     7
+   10 ff43616e5d0f     0    7     7
+   13 b4594d867745     0    6     6
+   12 e46a4836065c     0    6     6
+    6 2702dd0c91e7     0    5     5
+   15 1d8d22637c2d     4    4     8
+    3 2b6d669947cd     0    4     4
+    5 f0f3ef9a6cd5     0    4     4
+    9 dcbb326fdec2     4    3     7
+   10 ff43616e5d0f     4    3     7
+   15 1d8d22637c2d     6    2     8
+    3 2b6d669947cd     2    2     4
+    1 66f7d451a68b     0    2     2
+   13 b4594d867745     4    2     6
+    8 d62d843c9a01     4    2     6
+   12 e46a4836065c     4    2     6
+    5 f0f3ef9a6cd5     2    2     4
+    2 fa942426a6fd     0    2     2
+   15 1d8d22637c2d     7    1     8
+    0 1ea73414a91b     0    1     1
+    6 2702dd0c91e7     4    1     5
+    3 2b6d669947cd     3    1     4
+   14 43227190fef8     4    1     5
+    4 4c748ffd1a46     2    1     3
+    1 66f7d451a68b     1    1     2
+   13 b4594d867745     5    1     6
+   11 bab5d5bf48bd     4    1     5
+    8 d62d843c9a01     5    1     6
+    9 dcbb326fdec2     6    1     7
+   12 e46a4836065c     5    1     6
+    7 e7d9710d9fc6     4    1     5
+    5 f0f3ef9a6cd5     3    1     4
+    2 fa942426a6fd     1    1     2
+   10 ff43616e5d0f     6    1     7
+  $ cd ..