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)
created new head
--------------
test L:up a R:nc a b W: - 1 get local a to b
--------------
searching for copies back to rev 1
unmatched files in other:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local e300d1c794ec+ remote 4ce40f5aca24
rev: versions differ -> m
a: remote copied to b -> m
preserving a for resolve of b
preserving rev for resolve of rev
update: a 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging a and b to b
my b@e300d1c794ec+ other b@4ce40f5aca24 ancestor a@924404dff337
premerge successful
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@e300d1c794ec+ other rev@4ce40f5aca24 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
C a
--------------
created new head
--------------
test L:nc a b R:up a W: - 2 get rem change to a and b
--------------
searching for copies back to rev 1
unmatched files in local:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 86a2aa42fc76+ remote f4db7e329e71
a: remote is newer -> g
b: local copied/moved to a -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
getting a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b and a to b
my b@86a2aa42fc76+ other a@f4db7e329e71 ancestor a@924404dff337
premerge successful
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@86a2aa42fc76+ other rev@f4db7e329e71 ancestor rev@924404dff337
1 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M a
M b
a
--------------
created new head
--------------
test L:up a R:nm a b W: - 3 get local a change to b, remove a
--------------
searching for copies back to rev 1
unmatched files in other:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local e300d1c794ec+ remote bdb19105162a
rev: versions differ -> m
a: remote moved to b -> m
preserving a for resolve of b
preserving rev for resolve of rev
removing a
update: a 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging a and b to b
my b@e300d1c794ec+ other b@bdb19105162a ancestor a@924404dff337
premerge successful
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@e300d1c794ec+ other rev@bdb19105162a ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
--------------
created new head
--------------
test L:nm a b R:up a W: - 4 get remote change to b
--------------
searching for copies back to rev 1
unmatched files in local:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 02963e448370+ remote f4db7e329e71
b: local copied/moved to a -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b and a to b
my b@02963e448370+ other a@f4db7e329e71 ancestor a@924404dff337
premerge successful
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@02963e448370+ other rev@f4db7e329e71 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
--------------
created new head
--------------
test L: R:nc a b W: - 5 get b
--------------
searching for copies back to rev 1
unmatched files in other:
b
all copies found (* = to merge, ! = divergent):
b -> a
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 94b33a1b7f2d+ remote 4ce40f5aca24
rev: versions differ -> m
b: remote created -> g
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
getting b
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@94b33a1b7f2d+ other rev@4ce40f5aca24 ancestor rev@924404dff337
1 files updated, 1 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
C a
--------------
created new head
--------------
test L:nc a b R: W: - 6 nothing
--------------
searching for copies back to rev 1
unmatched files in local:
b
all copies found (* = to merge, ! = divergent):
b -> a
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 86a2aa42fc76+ remote 97c705ade336
rev: versions differ -> m
preserving rev for resolve of rev
update: rev 1/1 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@86a2aa42fc76+ other rev@97c705ade336 ancestor rev@924404dff337
0 files updated, 1 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
C a
C b
--------------
created new head
--------------
test L: R:nm a b W: - 7 get b
--------------
searching for copies back to rev 1
unmatched files in other:
b
all copies found (* = to merge, ! = divergent):
b -> a
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 94b33a1b7f2d+ remote bdb19105162a
a: other deleted -> r
rev: versions differ -> m
b: remote created -> g
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
removing a
update: b 2/3 files (66.67%)
getting b
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@94b33a1b7f2d+ other rev@bdb19105162a ancestor rev@924404dff337
1 files updated, 1 files merged, 1 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
--------------
created new head
--------------
test L:nm a b R: W: - 8 nothing
--------------
searching for copies back to rev 1
unmatched files in local:
b
all copies found (* = to merge, ! = divergent):
b -> a
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 02963e448370+ remote 97c705ade336
rev: versions differ -> m
preserving rev for resolve of rev
update: rev 1/1 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@02963e448370+ other rev@97c705ade336 ancestor rev@924404dff337
0 files updated, 1 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
C b
--------------
created new head
--------------
test L:um a b R:um a b W: - 9 do merge with ancestor in a
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 62e7bf090eba+ remote 49b6d8032493
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@62e7bf090eba+ other b@49b6d8032493 ancestor a@924404dff337
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@62e7bf090eba+ other rev@49b6d8032493 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
--------------
created new head
--------------
test L:nm a b R:nm a c W: - 11 get c, keep b
--------------
searching for copies back to rev 1
unmatched files in local:
b
unmatched files in other:
c
all copies found (* = to merge, ! = divergent):
c -> a !
b -> a !
checking for directory renames
a: divergent renames -> dr
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 02963e448370+ remote fe905ef2c33e
rev: versions differ -> m
c: remote created -> g
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
warning: detected divergent renames of a to:
b
c
update: c 2/3 files (66.67%)
getting c
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@02963e448370+ other rev@fe905ef2c33e ancestor rev@924404dff337
1 files updated, 1 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M c
C b
--------------
created new head
--------------
test L:nc a b R:up b W: - 12 merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 86a2aa42fc76+ remote af30c7647fc7
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@86a2aa42fc76+ other b@af30c7647fc7 ancestor b@000000000000
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@86a2aa42fc76+ other rev@af30c7647fc7 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
C a
--------------
created new head
--------------
test L:up b R:nm a b W: - 13 merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 59318016310c+ remote bdb19105162a
a: other deleted -> r
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
removing a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@59318016310c+ other b@bdb19105162a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@59318016310c+ other rev@bdb19105162a ancestor rev@924404dff337
0 files updated, 2 files merged, 1 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
--------------
created new head
--------------
test L:nc a b R:up a b W: - 14 merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 86a2aa42fc76+ remote 8dbce441892a
a: remote is newer -> g
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
getting a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@86a2aa42fc76+ other b@8dbce441892a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@86a2aa42fc76+ other rev@8dbce441892a ancestor rev@924404dff337
1 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M a
M b
--------------
created new head
--------------
test L:up b R:nm a b W: - 15 merge b no ancestor, remove a
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 59318016310c+ remote bdb19105162a
a: other deleted -> r
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
removing a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@59318016310c+ other b@bdb19105162a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@59318016310c+ other rev@bdb19105162a ancestor rev@924404dff337
0 files updated, 2 files merged, 1 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
--------------
created new head
--------------
test L:nc a b R:up a b W: - 16 get a, merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 86a2aa42fc76+ remote 8dbce441892a
a: remote is newer -> g
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
getting a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@86a2aa42fc76+ other b@8dbce441892a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@86a2aa42fc76+ other rev@8dbce441892a ancestor rev@924404dff337
1 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M a
M b
--------------
created new head
--------------
test L:up a b R:nc a b W: - 17 keep a, merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 0b76e65c8289+ remote 4ce40f5aca24
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@0b76e65c8289+ other b@4ce40f5aca24 ancestor b@000000000000
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@0b76e65c8289+ other rev@4ce40f5aca24 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
C a
--------------
created new head
--------------
test L:nm a b R:up a b W: - 18 merge b no ancestor
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 02963e448370+ remote 8dbce441892a
b: versions differ -> m
rev: versions differ -> m
remote changed a which local deleted
use (c)hanged version or leave (d)eleted? c
a: prompt recreating -> g
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
getting a
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@02963e448370+ other b@8dbce441892a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@02963e448370+ other rev@8dbce441892a ancestor rev@924404dff337
1 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M a
M b
--------------
created new head
--------------
test L:up a b R:nm a b W: - 19 merge b no ancestor, prompt remove a
--------------
searching for copies back to rev 1
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 0b76e65c8289+ remote bdb19105162a
local changed a which remote deleted
use (c)hanged version or (d)elete? c
a: prompt keep -> a
b: versions differ -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: a 1/3 files (33.33%)
update: b 2/3 files (66.67%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b
my b@0b76e65c8289+ other b@bdb19105162a ancestor b@000000000000
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@0b76e65c8289+ other rev@bdb19105162a ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
C a
--------------
created new head
--------------
test L:up a R:um a b W: - 20 merge a and b to b, remove a
--------------
searching for copies back to rev 1
unmatched files in other:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local e300d1c794ec+ remote 49b6d8032493
rev: versions differ -> m
a: remote moved to b -> m
preserving a for resolve of b
preserving rev for resolve of rev
removing a
update: a 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging a and b to b
my b@e300d1c794ec+ other b@49b6d8032493 ancestor a@924404dff337
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@e300d1c794ec+ other rev@49b6d8032493 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
--------------
created new head
--------------
test L:um a b R:up a W: - 21 merge a and b to b
--------------
searching for copies back to rev 1
unmatched files in local:
b
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 62e7bf090eba+ remote f4db7e329e71
b: local copied/moved to a -> m
rev: versions differ -> m
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/2 files (50.00%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b and a to b
my b@62e7bf090eba+ other a@f4db7e329e71 ancestor a@924404dff337
update: rev 2/2 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@62e7bf090eba+ other rev@f4db7e329e71 ancestor rev@924404dff337
0 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
--------------
created new head
--------------
test L:nm a b R:up a c W: - 23 get c, keep b
--------------
searching for copies back to rev 1
unmatched files in local:
b
unmatched files in other:
c
all copies found (* = to merge, ! = divergent):
b -> a *
checking for directory renames
resolving manifests
overwrite None partial False
ancestor 924404dff337 local 02963e448370+ remote 2b958612230f
b: local copied/moved to a -> m
rev: versions differ -> m
c: remote created -> g
preserving b for resolve of b
preserving rev for resolve of rev
update: b 1/3 files (33.33%)
picked tool 'python ../merge' for b (binary False symlink False)
merging b and a to b
my b@02963e448370+ other a@2b958612230f ancestor a@924404dff337
premerge successful
update: c 2/3 files (66.67%)
getting c
update: rev 3/3 files (100.00%)
picked tool 'python ../merge' for rev (binary False symlink False)
merging rev
my rev@02963e448370+ other rev@2b958612230f ancestor rev@924404dff337
1 files updated, 2 files merged, 0 files removed, 0 files unresolved
(branch merge, don't forget to commit)
--------------
M b
a
M c
--------------