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
# common patterns in test at can safely be replaced
import os
substitutions = [
# list of possible compressions
(br'(zstd,)?zlib,none,bzip2', br'$USUAL_COMPRESSIONS$'),
(br'=(zstd,)?zlib', br'=$BUNDLE2_COMPRESSIONS$'),
# capabilities sent through http
(
br'bundlecaps=HG20%2Cbundle2%3DHG20%250A'
br'bookmarks%250A'
br'changegroup%253D01%252C02%250A'
br'checkheads%253Drelated%250A'
br'digests%253Dmd5%252Csha1%252Csha512%250A'
br'error%253Dabort%252Cunsupportedcontent%252Cpushraced%252Cpushkey%250A'
br'hgtagsfnodes%250A'
br'listkeys%250A'
br'phases%253Dheads%250A'
br'pushkey%250A'
br'remote-changegroup%253Dhttp%252Chttps%250A'
br'stream%253Dv2',
# (the replacement patterns)
br'$USUAL_BUNDLE_CAPS$',
),
(
br'bundlecaps=HG20%2Cbundle2%3DHG20%250A'
br'bookmarks%250A'
br'changegroup%253D01%252C02%250A'
br'checkheads%3Drelated%0A'
br'digests%253Dmd5%252Csha1%252Csha512%250A'
br'error%253Dabort%252Cunsupportedcontent%252Cpushraced%252Cpushkey%250A'
br'hgtagsfnodes%250A'
br'listkeys%250A'
br'phases%253Dheads%250A'
br'pushkey%250A'
br'remote-changegroup%253Dhttp%252Chttps',
# (the replacement patterns)
br'$USUAL_BUNDLE_CAPS_SERVER$',
),
# bundle2 capabilities sent through ssh
(
br'bundle2=HG20%0A'
br'bookmarks%0A'
br'changegroup%3D01%2C02%0A'
br'checkheads%3Drelated%0A'
br'digests%3Dmd5%2Csha1%2Csha512%0A'
br'error%3Dabort%2Cunsupportedcontent%2Cpushraced%2Cpushkey%0A'
br'hgtagsfnodes%0A'
br'listkeys%0A'
br'phases%3Dheads%0A'
br'pushkey%0A'
br'remote-changegroup%3Dhttp%2Chttps%0A'
br'stream%3Dv2',
# (replacement patterns)
br'$USUAL_BUNDLE2_CAPS$',
),
# bundle2 capabilities advertised by the server
(
br'bundle2=HG20%0A'
br'bookmarks%0A'
br'changegroup%3D01%2C02%0A'
br'checkheads%3Drelated%0A'
br'digests%3Dmd5%2Csha1%2Csha512%0A'
br'error%3Dabort%2Cunsupportedcontent%2Cpushraced%2Cpushkey%0A'
br'hgtagsfnodes%0A'
br'listkeys%0A'
br'phases%3Dheads%0A'
br'pushkey%0A'
br'remote-changegroup%3Dhttp%2Chttps',
# (replacement patterns)
br'$USUAL_BUNDLE2_CAPS_SERVER$',
),
(
br'bundle2=HG20%0A'
br'bookmarks%0A'
br'changegroup%3D01%2C02%0A'
br'digests%3Dmd5%2Csha1%2Csha512%0A'
br'error%3Dabort%2Cunsupportedcontent%2Cpushraced%2Cpushkey%0A'
br'hgtagsfnodes%0A'
br'listkeys%0A'
br'pushkey%0A'
br'remote-changegroup%3Dhttp%2Chttps%0A'
br'stream%3Dv2',
# (replacement patterns)
br'$USUAL_BUNDLE2_CAPS_NO_PHASES$',
),
# HTTP access log dates
(
br' - - \[\d\d/.../2\d\d\d \d\d:\d\d:\d\d] "(GET|PUT|POST)',
lambda m: br' - - [$LOGDATE$] "' + m.group(1),
),
# HTTP error log dates
(
br' - - \[\d\d/.../2\d\d\d \d\d:\d\d:\d\d] (HG error:|Exception)',
lambda m: br' - - [$ERRDATE$] ' + m.group(1),
),
# HTTP header dates- RFC 1123
(
br'([Dd]ate): [A-Za-z]{3}, \d\d [A-Za-z]{3} \d{4} \d\d:\d\d:\d\d GMT',
lambda m: br'%s: $HTTP_DATE$' % m.group(1),
),
# LFS expiration value
(
br'"expires_at": "\d{4}-\d\d-\d\dT\d\d:\d\d:\d\dZ"',
br'"expires_at": "$ISO_8601_DATE_TIME$"',
),
# Windows has an extra '/' in the following lines that get globbed away:
# pushing to file:/*/$TESTTMP/r2 (glob)
# comparing with file:/*/$TESTTMP/r2 (glob)
# sub/maybelarge.dat: largefile 34..9c not available from
# file:/*/$TESTTMP/largefiles-repo (glob)
(
br'(.*file:/)/?(/\$TESTTMP.*)',
lambda m: m.group(1) + b'*' + m.group(2) + b' (glob)',
),
# `hg clone --stream` output
(
br'transferred (\S+?) KB in \S+? seconds \(.+?/sec\)(?: \(glob\))?(.*)',
lambda m: (
br'transferred %s KB in * seconds (* */sec) (glob)%s'
% (m.group(1), m.group(2))
),
),
]
# Various platform error strings, keyed on a common replacement string
_errors = {
br'$ENOENT$': (
# IOError in Python does not have the same error message
# than in Rust, and automatic conversion is not possible
# because of module member privacy.
br'No such file or directory \(os error 2\)',
# strerror()
br'No such file or directory',
# FormatMessage(ERROR_FILE_NOT_FOUND)
br'The system cannot find the file specified',
),
br'$ENOTDIR$': (
# strerror()
br'Not a directory',
# FormatMessage(ERROR_PATH_NOT_FOUND)
br'The system cannot find the path specified',
),
br'$ECONNRESET$': (
# strerror()
br'Connection reset by peer',
# FormatMessage(WSAECONNRESET)
br'An existing connection was forcibly closed by the remote host',
),
br'$EADDRINUSE$': (
# strerror()
br'Address already in use',
# FormatMessage(WSAEADDRINUSE)
br'Only one usage of each socket address'
br' \(protocol/network address/port\) is normally permitted',
),
br'$EADDRNOTAVAIL$': (
# strerror()
br'Cannot assign requested address',
# FormatMessage(WSAEADDRNOTAVAIL)
),
}
for replace, msgs in _errors.items():
substitutions.extend((m, replace) for m in msgs)
# Output lines on Windows that can be autocorrected for '\' vs '/' path
# differences.
_winpathfixes = [
# cloning subrepo s\ss from $TESTTMP/t/s/ss
# cloning subrepo foo\bar from http://localhost:$HGPORT/foo/bar
br'(?m)^cloning subrepo \S+\\.*',
# pulling from $TESTTMP\issue1852a
br'(?m)^pulling from \$TESTTMP\\.*',
# pushing to $TESTTMP\a
br'(?m)^pushing to \$TESTTMP\\.*',
# pushing subrepo s\ss to $TESTTMP/t/s/ss
br'(?m)^pushing subrepo \S+\\\S+ to.*',
# moving d1\d11\a1 to d3/d11/a1
br'(?m)^moving \S+\\.*',
# d1\a: not recording move - dummy does not exist
br'\S+\\\S+: not recording move .+',
# reverting s\a
br'(?m)^reverting (?!subrepo ).*\\.*',
# saved backup bundle to
# $TESTTMP\test\.hg\strip-backup/443431ffac4f-2fc5398a-backup.hg
br'(?m)^saved backup bundle to \$TESTTMP.*\.hg',
# no changes made to subrepo s\ss since last push to ../tcc/s/ss
br'(?m)^no changes made to subrepo \S+\\\S+ since.*',
# changeset 5:9cc5aa7204f0: stuff/maybelarge.dat references missing
# $TESTTMP\largefiles-repo-hg\.hg\largefiles\76..38
br'(?m)^changeset .* references (corrupted|missing) \$TESTTMP\\.*',
# stuff/maybelarge.dat: largefile 76..38 not available from
# file:/*/$TESTTMP\largefiles-repo (glob)
br'.*: largefile \S+ not available from file:/\*/.+',
]
if os.name == 'nt':
substitutions.extend(
[
(s, lambda match: match.group().replace(b'\\', b'/'))
for s in _winpathfixes
]
)