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
Set up repo
$ cat << EOF >> $HGRCPATH
> [ui]
> origbackuppath=.hg/origbackups
> [merge]
> checkunknown=warn
> EOF
$ hg init repo
$ cd repo
$ echo base > base
$ hg add base
$ hg commit -m "base"
Make a dir named b that contains a file, and a file named d
$ mkdir -p b
$ echo c1 > b/c
$ echo d1 > d
$ hg add b/c d
$ hg commit -m "c1"
$ hg bookmark c1
Peform an update that causes b/c to be backed up
$ hg up -q 0
$ mkdir -p b
$ echo c2 > b/c
$ hg up --verbose c1
resolving manifests
b/c: replacing untracked file
getting b/c
creating directory: $TESTTMP/repo/.hg/origbackups/b
getting d
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark c1)
$ test -f .hg/origbackups/b/c
Make files named b and d
$ hg up -q 0
$ echo b1 > b
$ echo d2 > d
$ hg add b d
$ hg commit -m b1
created new head
$ hg bookmark b1
Perform an update that causes b to be backed up - it should replace the backup b dir
$ hg up -q 0
$ echo b2 > b
$ hg up --verbose b1
resolving manifests
b: replacing untracked file
getting b
removing conflicting directory: $TESTTMP/repo/.hg/origbackups/b
getting d
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark b1)
$ test -f .hg/origbackups/b
Perform an update the causes b/c to be backed up again - it should replace the backup b file
$ hg up -q 0
$ mkdir b
$ echo c3 > b/c
$ hg up --verbose c1
resolving manifests
b/c: replacing untracked file
getting b/c
creating directory: $TESTTMP/repo/.hg/origbackups/b
removing conflicting file: $TESTTMP/repo/.hg/origbackups/b
getting d
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark c1)
$ test -d .hg/origbackups/b
Cause two symlinks to be backed up that points to a valid location from the backup dir
$ hg up -q 0
$ mkdir ../sym-link-target
#if symlink
$ ln -s ../../../sym-link-target b
$ ln -s ../../../sym-link-target d
#else
$ touch b d
#endif
$ hg up b1
b: replacing untracked file
d: replacing untracked file
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark b1)
#if symlink
$ readlink.py .hg/origbackups/b
.hg/origbackups/b -> ../../../sym-link-target
#endif
Perform an update that causes b/c and d to be backed up again - b/c should not go into the target dir
$ hg up -q 0
$ mkdir b
$ echo c4 > b/c
$ echo d3 > d
$ hg up --verbose c1
resolving manifests
b/c: replacing untracked file
d: replacing untracked file
getting b/c
creating directory: $TESTTMP/repo/.hg/origbackups/b
removing conflicting file: $TESTTMP/repo/.hg/origbackups/b
getting d
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark c1)
$ cat .hg/origbackups/b/c
c4
$ cat .hg/origbackups/d
d3
$ ls ../sym-link-target
Incorrectly configure origbackuppath to be under a file
$ echo data > .hg/badorigbackups
$ hg up -q 0
$ mkdir b
$ echo c5 > b/c
$ hg up --verbose c1 --config ui.origbackuppath=.hg/badorigbackups
resolving manifests
b/c: replacing untracked file
getting b/c
creating directory: $TESTTMP/repo/.hg/badorigbackups/b
removing conflicting file: $TESTTMP/repo/.hg/badorigbackups
getting d
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
(activating bookmark c1)
$ ls .hg/badorigbackups/b
c