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.
--- 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 ###
#############################
--- /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 ..