encoding: fix trim() to be O(n) instead of O(n^2)
`encoding.trim()` iterated over the possible lengths smaller than the
input and created a slice for each. It then calculated the column
width of the result, which is of course O(n), so the overall algorithm
was O(n). This patch rewrites it to iterate over the unicode
characters, keeping track of the length so far. Also, the old
algorithm started from the end of the string, which made it much worse
when the input is large and the limit is small (such as the typical 72
we pass to it).
You can time it by running something like this:
```
time python3 -c 'from mercurial.utils import stringutil; print(stringutil.ellipsis(b"0123456789" * 1000, 5))'
```
That drops from 4.05 s to 83 ms with this patch (and most of that is
of course startup time).
Differential Revision: https://phab.mercurial-scm.org/D12089
# In most cases, the mercurial repository can be read by the bundled hg, but
# that isn't always true because third-party extensions may change the store
# format, for example. In which case, the system hg installation is used.
#
# We want to use the hg version being tested when interacting with the test
# repository, and the system hg when interacting with the mercurial source code
# repository.
#
# The mercurial source repository was typically orignally cloned with the
# system mercurial installation, and may require extensions or settings from
# the system installation.
if [ -n "$HGTESTEXTRAEXTENSIONS" ]; then
for extension in $HGTESTEXTRAEXTENSIONS; do
extraoptions="$extraoptions --config extensions.$extension=!"
done
fi
syshg () {
(
syshgenv
exec hg "$@"
)
}
# Revert the environment so that running "hg" runs the system hg
# rather than the test hg installation.
syshgenv () {
. "$HGTEST_RESTOREENV"
HGPLAIN=1
export HGPLAIN
}
# The test-repo is a live hg repository which may have evolution markers
# created, e.g. when a ~/.hgrc enabled evolution.
#
# Tests may be run using a custom HGRCPATH, which do not enable evolution
# markers by default.
#
# If test-repo includes evolution markers, and we do not enable evolution
# markers, hg will occasionally complain when it notices them, which disrupts
# tests resulting in sporadic failures.
#
# Since we aren't performing any write operations on the test-repo, there's
# no harm in telling hg that we support evolution markers, which is what the
# following lines for the hgrc file do:
cat >> "$HGRCPATH" << EOF
[experimental]
evolution = createmarkers
EOF
# Use the system hg command if the bundled hg can't read the repository with
# no warning nor error.
if [ -n "`hg id -R "$TESTDIR/.." 2>&1 >/dev/null`" ]; then
alias testrepohg=syshg
alias testrepohgenv=syshgenv
else
alias testrepohg="hg $extraoptions"
alias testrepohgenv=:
fi