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