findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
We speed up 'findrenames' for the usecase when a user specifies they
want a similarity of 100% by matching files by their exact SHA1 hash
value. This reduces the number of comparisons required to find exact
matches from O(n^2) to O(n).
While it would be nice if we could just use mercurial's pre-calculated
SHA1 hash for existing files, this hash includes the file's ancestor
information making it unsuitable for our purposes. Instead, we calculate
the hash of old content from scratch.
The following benchmarks were taken on the current head of crew:
addremove 100% similarity:
rm -rf *; hg up -C; mv tests tests.new
hg --time addremove -s100 --dry-run
before: real 176.350 secs (user 128.890+0.000 sys 47.430+0.000)
after: real 2.130 secs (user 1.890+0.000 sys 0.240+0.000)
addremove 75% similarity:
rm -rf *; hg up -C; mv tests tests.new; \
for i in tests.new/*; do echo x >> $i; done
hg --time addremove -s75 --dry-run
before: real 264.560 secs (user 215.130+0.000 sys 49.410+0.000)
after: real 218.710 secs (user 172.790+0.000 sys 45.870+0.000)
adding r1
adding r2
0 files updated, 0 files merged, 1 files removed, 0 files unresolved
adding b1
created new head
adding b2
adding b3
4 b3
3 b2
2 0:17ab29e464c6 b1
1 r2
0 r1
updating to branch default
4 files updated, 0 files merged, 0 files removed, 0 files unresolved
1 files updated, 0 files merged, 3 files removed, 0 files unresolved
% rebase b onto r1
applying 37a1297eb21b
37a1297eb21b transplanted to e234d668f844
applying 722f4667af76
722f4667af76 transplanted to 539f377d78df
applying a53251cdf717
a53251cdf717 transplanted to ffd6818a3975
7 b3
6 b2
5 1:d11e3596cc1a b1
4 b3
3 b2
2 0:17ab29e464c6 b1
1 r2
0 r1
updating to branch default
4 files updated, 0 files merged, 0 files removed, 0 files unresolved
1 files updated, 0 files merged, 3 files removed, 0 files unresolved
% rebase b onto r1, skipping b2
applying 37a1297eb21b
37a1297eb21b transplanted to e234d668f844
applying a53251cdf717
a53251cdf717 transplanted to 7275fda4d04f
6 b3
5 1:d11e3596cc1a b1
4 b3
3 b2
2 0:17ab29e464c6 b1
1 r2
0 r1
% remote transplant
requesting all changes
adding changesets
adding manifests
adding file changes
added 2 changesets with 2 changes to 2 files
updating to branch default
2 files updated, 0 files merged, 0 files removed, 0 files unresolved
searching for changes
applying 37a1297eb21b
37a1297eb21b transplanted to c19cf0ccb069
applying a53251cdf717
a53251cdf717 transplanted to f7fe5bf98525
3 b3
(transplanted from a53251cdf717679d1907b289f991534be05c997a)
2 b1
(transplanted from 37a1297eb21b3ef5c5d2ffac22121a0988ed9f21)
1 r2
0 r1
% skip previous transplants
searching for changes
applying 722f4667af76
722f4667af76 transplanted to 47156cd86c0b
4 b2
3 b3
(transplanted from a53251cdf717679d1907b289f991534be05c997a)
2 b1
(transplanted from 37a1297eb21b3ef5c5d2ffac22121a0988ed9f21)
1 r2
0 r1
% skip local changes transplanted to the source
adding b4
updating to branch default
4 files updated, 0 files merged, 0 files removed, 0 files unresolved
searching for changes
applying 4333daefcb15
4333daefcb15 transplanted to 5f42c04e07cc
% remote transplant with pull
requesting all changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 1 changes to 1 files
updating to branch default
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
searching for changes
searching for changes
adding changesets
adding manifests
adding file changes
added 1 changesets with 1 changes to 1 files
applying a53251cdf717
a53251cdf717 transplanted to 8d9279348abb
2 b3
1 b1
0 r1
% transplant --continue
adding foo
adding toremove
adding added
removing toremove
adding bar
2 files updated, 0 files merged, 2 files removed, 0 files unresolved
created new head
applying a1e30dd1b8e7
patching file foo
Hunk #1 FAILED at 0
1 out of 1 hunks FAILED -- saving rejects to file foo.rej
patch failed to apply
abort: Fix up the merge and run hg transplant --continue
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
applying a1e30dd1b8e7
patching file foo
Hunk #1 FAILED at 0
1 out of 1 hunks FAILED -- saving rejects to file foo.rej
patch failed to apply
abort: Fix up the merge and run hg transplant --continue
a1e30dd1b8e7 transplanted as f1563cf27039
skipping already applied revision 1:a1e30dd1b8e7
applying 1739ac5f6139
1739ac5f6139 transplanted to d649c221319f
applying 0282d5fbbe02
0282d5fbbe02 transplanted to 77418277ccb3
added
bar
foo
% test transplant merge
adding a
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
created new head
% tranplant
applying 42dc4432fd35
1:42dc4432fd35 merged at a9f4acbac129
% test transplant into empty repository
requesting all changes
adding changesets
adding manifests
adding file changes
added 4 changesets with 4 changes to 4 files
% test filter
filtering
applying 17ab29e464c6
17ab29e464c6 transplanted to e9ffc54ea104
filtering
applying 37a1297eb21b
37a1297eb21b transplanted to 348b36d0b6a5
filtering
applying 722f4667af76
722f4667af76 transplanted to 0aa6979afb95
filtering
applying a53251cdf717
a53251cdf717 transplanted to 14f8512272b5
3 b3
2 b2
1 b1
0 r2
% test filter with failed patch
0 files updated, 0 files merged, 3 files removed, 0 files unresolved
adding b1
adding test-filter
created new head
file b1 already exists
1 out of 1 hunks FAILED -- saving rejects to file b1.rej
abort: Fix up the merge and run hg transplant --continue
filtering
applying 348b36d0b6a5
patch failed to apply
% test with a win32ext like setup (differing EOLs)
adding a
adding b
nothing changed
applying 2e849d776c17
2e849d776c17 transplanted to 589cea8ba85b
'a\r\nb\r\n'