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 start
adding new
% new file
diff --git a/new b/new
new file mode 100644
--- /dev/null
+++ b/new
@@ -0,0 +1,1 @@
+new
% copy
diff --git a/new b/copy
copy from new
copy to copy
% rename
diff --git a/copy b/rename
rename from copy
rename to rename
% delete
diff --git a/rename b/rename
deleted file mode 100644
--- a/rename
+++ /dev/null
@@ -1,1 +0,0 @@
-new
adding src
% chmod 644
diff --git a/src b/src
old mode 100644
new mode 100755
% rename+mod+chmod
diff --git a/src b/dst
old mode 100755
new mode 100644
rename from src
rename to dst
--- a/src
+++ b/dst
@@ -3,3 +3,4 @@
3
4
5
+a
% nonexistent in tip+chmod
diff --git a/src b/src
old mode 100644
new mode 100755
% binary diff
diff --git a/binfile.bin b/binfile.bin
new file mode 100644
index 0000000000000000000000000000000000000000..37ba3d1c6f17137d9c5f5776fa040caf5fe73ff9
GIT binary patch
literal 593
zc$@)I0<QguP)<h;3K|Lk000e1NJLTq000mG000mO0ssI2kdbIM00009a7bBm000XU
z000XU0RWnu7ytkO2XskIMF-Uh9TW;VpMjwv0005-Nkl<ZD9@FWPs=e;7{<>W$NUkd
zX$nnYLt$-$V!?uy+1V%`z&Eh=ah|duER<4|QWhju3gb^nF*8iYobxWG-qqXl=2~5M
z*IoDB)sG^CfNuoBmqLTVU^<;@nwHP!1wrWd`{(mHo6VNXWtyh{alzqmsH*yYzpvLT
zLdY<T=ks|woh-`&01!ej#(xbV1f|pI*=%;d-%F*E*X#ZH`4I%6SS+$EJDE&ct=8po
ziN#{?_j|kD%Cd|oiqds`xm@;oJ-^?NG3Gdqrs?5u*zI;{nogxsx~^|Fn^Y?Gdc6<;
zfMJ+iF1J`LMx&A2?dEwNW8ClebzPTbIh{@$hS6*`kH@1d%Lo7fA#}N1)oN7`gm$~V
z+wDx#)OFqMcE{s!JN0-xhG8ItAjVkJwEcb`3WWlJfU2r?;Pd%dmR+q@mSri5q9_W-
zaR2~ECX?B2w+zELozC0s*6Z~|QG^f{3I#<`?)Q7U-JZ|q5W;9Q8i_=pBuSzunx=U;
z9C)5jBoYw9^?EHyQl(M}1OlQcCX>lXB*ODN003Z&P17_@)3Pi=i0wb04<W?v-u}7K
zXmmQA+wDgE!qR9o8jr`%=ab_&uh(l?R=r;Tjiqon91I2-hIu?57~@*4h7h9uORK#=
fQItJW-{SoTm)8|5##k|m00000NkvXXu0mjf{mKw4
% import binary diff
applying b.diff
% rename binary file
diff --git a/binfile.bin b/renamed.bin
rename from binfile.bin
rename to renamed.bin
% diff across many revisions
diff --git a/dst2 b/dst3
rename from dst2
rename to dst3
% reversed
diff --git a/dst3 b/dst2
rename from dst3
rename to dst2
% file created before r1 and renamed before r2
diff --git a/foo b/bar
rename from foo
rename to bar
--- a/foo
+++ b/bar
@@ -1,2 +1,3 @@
a
b
+c
% reversed
diff --git a/bar b/foo
rename from bar
rename to foo
--- a/bar
+++ b/foo
@@ -1,3 +1,2 @@
a
b
-c
% file created in r1 and renamed before r2
diff --git a/foo b/bar
rename from foo
rename to bar
--- a/foo
+++ b/bar
@@ -1,1 +1,3 @@
a
+b
+c
% reversed
diff --git a/bar b/foo
rename from bar
rename to foo
--- a/bar
+++ b/foo
@@ -1,3 +1,1 @@
a
-b
-c
% file created after r1 and renamed before r2
diff --git a/bar b/bar
new file mode 100644
--- /dev/null
+++ b/bar
@@ -0,0 +1,3 @@
+a
+b
+c
% reversed
diff --git a/bar b/bar
deleted file mode 100644
--- a/bar
+++ /dev/null
@@ -1,3 +0,0 @@
-a
-b
-c
% comparing with the working dir
% there's a copy in the working dir...
diff --git a/created2 b/created3
rename from created2
rename to created3
% ...but there's another copy between the original rev and the wd
diff --git a/created b/created3
rename from created
rename to created3
% ...but the source of the copy was created after the original rev
diff --git a/created3 b/created3
new file mode 100644
--- /dev/null
+++ b/created3
@@ -0,0 +1,1 @@
+
% created in parent of wd; renamed in the wd
diff --git a/brand-new b/brand-new2
rename from brand-new
rename to brand-new2
% created between r1 and parent of wd; renamed in the wd
diff --git a/brand-new2 b/brand-new2
new file mode 100644
--- /dev/null
+++ b/brand-new2
@@ -0,0 +1,1 @@
+
% one file is copied to many destinations and removed
diff --git a/brand-new2 b/brand-new3
rename from brand-new2
rename to brand-new3
diff --git a/brand-new2 b/brand-new3-2
copy from brand-new2
copy to brand-new3-2
% reversed
diff --git a/brand-new3 b/brand-new2
rename from brand-new3
rename to brand-new2
diff --git a/brand-new3-2 b/brand-new3-2
deleted file mode 100644
--- a/brand-new3-2
+++ /dev/null
@@ -1,1 +0,0 @@
-
% there should be a trailing TAB if there are spaces in the file name
diff --git a/with spaces b/with spaces
new file mode 100644
--- /dev/null
+++ b/with spaces
@@ -0,0 +1,1 @@
+foo