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
$ hg init repo
$ cd repo
$ hg init subrepo
$ echo a > subrepo/a
$ hg -R subrepo ci -Am adda
adding a
$ echo 'subrepo = subrepo' > .hgsub
$ hg ci -Am addsubrepo
adding .hgsub
$ echo b > subrepo/b
$ hg -R subrepo ci -Am addb
adding b
$ hg ci -m updatedsub
ignore blanklines in .hgsubstate
>>> open('.hgsubstate', 'wb').write(b'\n\n \t \n \n') and None
$ hg st --subrepos
M .hgsubstate
$ hg revert -qC .hgsubstate
abort more gracefully on .hgsubstate parsing error
$ cp .hgsubstate .hgsubstate.old
>>> open('.hgsubstate', 'wb').write(b'\ninvalid') and None
$ hg st --subrepos --cwd $TESTTMP -R $TESTTMP/repo
abort: invalid subrepository revision specifier in 'repo/.hgsubstate' line 2
[255]
$ mv .hgsubstate.old .hgsubstate
delete .hgsub and revert it
$ rm .hgsub
$ hg revert .hgsub
warning: subrepo spec file '.hgsub' not found
warning: subrepo spec file '.hgsub' not found
delete .hgsubstate and revert it
$ rm .hgsubstate
$ hg revert .hgsubstate
delete .hgsub and update
$ rm .hgsub
$ hg up 0 --cwd $TESTTMP -R $TESTTMP/repo
warning: subrepo spec file 'repo/.hgsub' not found
warning: subrepo spec file 'repo/.hgsub' not found
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg st
warning: subrepo spec file '.hgsub' not found
! .hgsub
$ ls -A subrepo
.hg
a
delete .hgsubstate and update
$ hg up -C
warning: subrepo spec file '.hgsub' not found
warning: subrepo spec file '.hgsub' not found
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ rm .hgsubstate
$ hg up 0
other [destination] changed .hgsubstate which local [working copy] deleted
use (c)hanged version or leave (d)eleted? c
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg st
$ ls -A subrepo
.hg
a
Enable obsolete
$ cat >> $HGRCPATH << EOF
> [ui]
> logtemplate= {rev}:{node|short} {desc|firstline}
> [phases]
> publish=False
> [experimental]
> evolution.createmarkers=True
> EOF
check that we can update parent repo with missing (amended) subrepo revision
$ hg up --repository subrepo -r tip
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg ci -m "updated subrepo to tip"
created new head
$ cd subrepo
$ hg update -r tip
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ echo foo > a
$ hg commit --amend -m "addb (amended)"
$ cd ..
$ hg update --clean .
revision 102a90ea7b4a in subrepository "subrepo" is hidden
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
check that --hidden is propagated to the subrepo
$ hg -R subrepo up tip
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg ci -m 'commit with amended subrepo'
$ echo bar > subrepo/a
$ hg -R subrepo ci --amend -m "amend a (again)"
$ hg --hidden cat subrepo/a
foo
verify will warn if locked-in subrepo revisions are hidden or missing
$ hg ci -m "amended subrepo (again)"
$ hg --config extensions.strip= --hidden strip -R subrepo -qr 'tip' --config devel.strip-obsmarkers=no
$ hg verify
checking changesets
checking manifests
crosschecking files in changesets and manifests
checking files
checked 5 changesets with 5 changes to 2 files
checking subrepo links
subrepo 'subrepo' is hidden in revision a66de08943b6
subrepo 'subrepo' is hidden in revision 674d05939c1e
subrepo 'subrepo' not found in revision a7d05d9055a4
verifying shouldn't init a new subrepo if the reference doesn't exist
$ mv subrepo b
$ hg verify
checking changesets
checking manifests
crosschecking files in changesets and manifests
checking files
checked 5 changesets with 5 changes to 2 files
checking subrepo links
0: repository $TESTTMP/repo/subrepo not found
1: repository $TESTTMP/repo/subrepo not found
3: repository $TESTTMP/repo/subrepo not found
4: repository $TESTTMP/repo/subrepo not found
$ ls -A
.hg
.hgsub
.hgsubstate
b
$ mv b subrepo
$ cd ..