bisect: avoid copying ancestor list for non-merge commits
During a bisection, hg needs to compute a list of all ancestors for every
candidate commit. This is accomplished via a bottom-up traversal of the set of
candidates, during which each revision's ancestor list is populated using the
ancestor list of its parent(s). Previously, this involved copying the entire
list, which could be very long in if the bisection range was large.
To help improve this, we can observe that each candidate commit is visited
exactly once, at which point its ancestor list is copied into its children's
lists and then dropped. In the case of non-merge commits, a commit's ancestor
list consists exactly of its parent's list plus itself. This means that we can
trivially reuse the parent's existing list for one of its non-merge children,
which avoids copying entirely if that commit is the parent's only child. This
makes bisections over linear ranges of commits much faster.
During some informal testing in the large publicly-available `mozilla-central`
repository, this noticeably sped up bisections over large ranges of history:
Setup:
$ cd mozilla-central
$ hg bisect --reset
$ hg bisect --good 0
$ hg log -r tip -T '{rev}\n'
628417
Test:
$ time hg bisect --bad tip --noupdate
Before:
real 3m35.927s
user 3m35.553s
sys 0m0.319s
After:
real 1m41.142s
user 1m40.810s
sys 0m0.285s
$ cat >> $HGRCPATH <<EOF
> [extensions]
> rebase=
> drawdag=$TESTDIR/drawdag.py
>
> [phases]
> publish=False
>
> [alias]
> tglog = log -G --template "{rev}: {node|short} '{desc}' bookmarks: {bookmarks}\n"
> EOF
Create a repo with several bookmarks
$ hg init a
$ cd a
$ echo a > a
$ hg ci -Am A
adding a
$ echo b > b
$ hg ci -Am B
adding b
$ hg book 'X'
$ hg book 'Y'
$ echo c > c
$ hg ci -Am C
adding c
$ hg book 'Z'
$ hg up -q 0
$ echo d > d
$ hg ci -Am D
adding d
created new head
$ hg book W
$ hg tglog
@ 3: 41acb9dca9eb 'D' bookmarks: W
|
| o 2: 49cb3485fa0c 'C' bookmarks: Y Z
| |
| o 1: 6c81ed0049f8 'B' bookmarks: X
|/
o 0: 1994f17a630e 'A' bookmarks:
Move only rebased bookmarks
$ cd ..
$ hg clone -q a a1
$ cd a1
$ hg up -q Z
Test deleting divergent bookmarks from dest (issue3685)
$ hg book -r 3 Z@diverge
... and also test that bookmarks not on dest or not being moved aren't deleted
$ hg book -r 3 X@diverge
$ hg book -r 0 Y@diverge
$ hg tglog
o 3: 41acb9dca9eb 'D' bookmarks: W X@diverge Z@diverge
|
| @ 2: 49cb3485fa0c 'C' bookmarks: Y Z
| |
| o 1: 6c81ed0049f8 'B' bookmarks: X
|/
o 0: 1994f17a630e 'A' bookmarks: Y@diverge
$ hg rebase -s Y -d 3
rebasing 2:49cb3485fa0c Y Z "C"
saved backup bundle to $TESTTMP/a1/.hg/strip-backup/49cb3485fa0c-126f3e97-rebase.hg
$ hg tglog
@ 3: 17fb3faba63c 'C' bookmarks: Y Z
|
o 2: 41acb9dca9eb 'D' bookmarks: W X@diverge
|
| o 1: 6c81ed0049f8 'B' bookmarks: X
|/
o 0: 1994f17a630e 'A' bookmarks: Y@diverge
Do not try to keep active but deleted divergent bookmark
$ cd ..
$ hg clone -q a a4
$ cd a4
$ hg up -q 2
$ hg book W@diverge
$ hg rebase -s W -d .
rebasing 3:41acb9dca9eb W tip "D"
saved backup bundle to $TESTTMP/a4/.hg/strip-backup/41acb9dca9eb-b35a6a63-rebase.hg
$ hg bookmarks
W 3:0d3554f74897
X 1:6c81ed0049f8
Y 2:49cb3485fa0c
Z 2:49cb3485fa0c
Keep bookmarks to the correct rebased changeset
$ cd ..
$ hg clone -q a a2
$ cd a2
$ hg up -q Z
$ hg rebase -s 1 -d 3
rebasing 1:6c81ed0049f8 X "B"
rebasing 2:49cb3485fa0c Y Z "C"
saved backup bundle to $TESTTMP/a2/.hg/strip-backup/6c81ed0049f8-a687065f-rebase.hg
$ hg tglog
@ 3: 3d5fa227f4b5 'C' bookmarks: Y Z
|
o 2: e926fccfa8ec 'B' bookmarks: X
|
o 1: 41acb9dca9eb 'D' bookmarks: W
|
o 0: 1994f17a630e 'A' bookmarks:
Keep active bookmark on the correct changeset
$ cd ..
$ hg clone -q a a3
$ cd a3
$ hg up -q X
$ hg rebase -d W
rebasing 1:6c81ed0049f8 X "B"
rebasing 2:49cb3485fa0c Y Z "C"
saved backup bundle to $TESTTMP/a3/.hg/strip-backup/6c81ed0049f8-a687065f-rebase.hg
$ hg tglog
o 3: 3d5fa227f4b5 'C' bookmarks: Y Z
|
@ 2: e926fccfa8ec 'B' bookmarks: X
|
o 1: 41acb9dca9eb 'D' bookmarks: W
|
o 0: 1994f17a630e 'A' bookmarks:
$ hg bookmarks
W 1:41acb9dca9eb
* X 2:e926fccfa8ec
Y 3:3d5fa227f4b5
Z 3:3d5fa227f4b5
rebase --continue with bookmarks present (issue3802)
$ hg up 2
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
(leaving bookmark X)
$ echo 'C' > c
$ hg add c
$ hg ci -m 'other C'
created new head
$ hg up 3
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg rebase --dest 4
rebasing 3:3d5fa227f4b5 Y Z "C"
merging c
warning: conflicts while merging c! (edit, then use 'hg resolve --mark')
unresolved conflicts (see 'hg resolve', then 'hg rebase --continue')
[240]
$ echo 'c' > c
$ hg resolve --mark c
(no more unresolved files)
continue: hg rebase --continue
$ hg rebase --continue
rebasing 3:3d5fa227f4b5 Y Z "C"
saved backup bundle to $TESTTMP/a3/.hg/strip-backup/3d5fa227f4b5-c6ea2371-rebase.hg
$ hg tglog
@ 4: 45c0f0ec1203 'C' bookmarks: Y Z
|
o 3: b0e10b7175fd 'other C' bookmarks:
|
o 2: e926fccfa8ec 'B' bookmarks: X
|
o 1: 41acb9dca9eb 'D' bookmarks: W
|
o 0: 1994f17a630e 'A' bookmarks:
ensure that bookmarks given the names of revset functions can be used
as --rev arguments (issue3950)
$ hg update -q 3
$ echo bimble > bimble
$ hg add bimble
$ hg commit -q -m 'bisect'
$ echo e >> bimble
$ hg ci -m bisect2
$ echo e >> bimble
$ hg ci -m bisect3
$ hg book bisect
$ hg update -q Y
$ hg rebase -r '"bisect"^^::"bisect"^' -r bisect -d Z
rebasing 5:345c90f326a4 "bisect"
rebasing 6:f677a2907404 "bisect2"
rebasing 7:325c16001345 bisect tip "bisect3"
saved backup bundle to $TESTTMP/a3/.hg/strip-backup/345c90f326a4-b4840586-rebase.hg
Bookmark and working parent get moved even if --keep is set (issue5682)
$ hg init $TESTTMP/book-keep
$ cd $TESTTMP/book-keep
$ hg debugdrawdag <<'EOS'
> B C
> |/
> A
> EOS
$ eval `hg tags -T 'hg bookmark -ir {node} {tag};\n' | grep -v tip`
$ rm .hg/localtags
$ hg up -q B
$ hg tglog
o 2: dc0947a82db8 'C' bookmarks: C
|
| @ 1: 112478962961 'B' bookmarks: B
|/
o 0: 426bada5c675 'A' bookmarks: A
$ hg rebase -r B -d C --keep
rebasing 1:112478962961 B "B"
$ hg tglog
@ 3: 9769fc65c4c5 'B' bookmarks: B
|
o 2: dc0947a82db8 'C' bookmarks: C
|
| o 1: 112478962961 'B' bookmarks:
|/
o 0: 426bada5c675 'A' bookmarks: A