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 a
adding b
adding d
adding c
% should give a 404 - file does not exist
404 Not Found
error: bork@8580ff50825a: not found in manifest
% should succeed
200 Script output follows
/a/
/b/
200 Script output follows
a
200 Script output follows
b
% should give a 404 - repo is not published
404 Not Found
error: repository c not found
% atom-log without basedir
<link rel="self" href="http://example.com:8080/a/atom-log"/>
<link rel="alternate" href="http://example.com:8080/a/"/>
<link href="http://example.com:8080/a/rev/8580ff50825a"/>
% rss-log without basedir
<guid isPermaLink="true">http://example.com:8080/a/rev/8580ff50825a</guid>
% should succeed, slashy names
200 Script output follows
/t/a/
/b/
/coll/a/
/coll/a/.hg/patches/
/coll/b/
/coll/c/
/rcoll/a/
/rcoll/a/.hg/patches/
/rcoll/b/
/rcoll/b/d/
/rcoll/c/
200 Script output follows
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-US">
<head>
<link rel="icon" href="/static/hgicon.png" type="image/png" />
<meta name="robots" content="index, nofollow" />
<link rel="stylesheet" href="/static/style-paper.css" type="text/css" />
<title>Mercurial repositories index</title>
</head>
<body>
<div class="container">
<div class="menu">
<a href="http://mercurial.selenic.com/">
<img src="/static/hglogo.png" width=75 height=90 border=0 alt="mercurial" /></a>
</div>
<div class="main">
<h2>Mercurial Repositories</h2>
<table class="bigtable">
<tr>
<th><a href="?sort=name">Name</a></th>
<th><a href="?sort=description">Description</a></th>
<th><a href="?sort=contact">Contact</a></th>
<th><a href="?sort=lastchange">Last modified</a></th>
<th> </th>
</tr>
<tr class="parity0">
<td><a href="/t/a/?style=paper">t/a</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity1">
<td><a href="/b/?style=paper">b</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity0">
<td><a href="/coll/a/?style=paper">coll/a</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity1">
<td><a href="/coll/a/.hg/patches/?style=paper">coll/a/.hg/patches</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity0">
<td><a href="/coll/b/?style=paper">coll/b</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity1">
<td><a href="/coll/c/?style=paper">coll/c</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity0">
<td><a href="/rcoll/a/?style=paper">rcoll/a</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity1">
<td><a href="/rcoll/a/.hg/patches/?style=paper">rcoll/a/.hg/patches</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity0">
<td><a href="/rcoll/b/?style=paper">rcoll/b</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity1">
<td><a href="/rcoll/b/d/?style=paper">rcoll/b/d</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
<tr class="parity0">
<td><a href="/rcoll/c/?style=paper">rcoll/c</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
</table>
</div>
</div>
</body>
</html>
200 Script output follows
/t/a/
200 Script output follows
/t/a/
200 Script output follows
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-US">
<head>
<link rel="icon" href="/static/hgicon.png" type="image/png" />
<meta name="robots" content="index, nofollow" />
<link rel="stylesheet" href="/static/style-paper.css" type="text/css" />
<title>Mercurial repositories index</title>
</head>
<body>
<div class="container">
<div class="menu">
<a href="http://mercurial.selenic.com/">
<img src="/static/hglogo.png" width=75 height=90 border=0 alt="mercurial" /></a>
</div>
<div class="main">
<h2>Mercurial Repositories</h2>
<table class="bigtable">
<tr>
<th><a href="?sort=name">Name</a></th>
<th><a href="?sort=description">Description</a></th>
<th><a href="?sort=contact">Contact</a></th>
<th><a href="?sort=lastchange">Last modified</a></th>
<th> </th>
</tr>
<tr class="parity0">
<td><a href="/t/a/?style=paper">a</a></td>
<td>unknown</td>
<td>Foo Bar <foo.bar@example.com></td>
<td class="age">seconds ago</td>
<td class="indexlinks"></td>
</tr>
</table>
</div>
</div>
</body>
</html>
200 Script output follows
<?xml version="1.0" encoding="ascii"?>
<feed xmlns="http://127.0.0.1/2005/Atom">
<!-- Changelog -->
<id>http://127.0.0.1/t/a/</id>
<link rel="self" href="http://127.0.0.1/t/a/atom-log"/>
<link rel="alternate" href="http://127.0.0.1/t/a/"/>
<title>t/a Changelog</title>
<updated>1970-01-01T00:00:01+00:00</updated>
<entry>
<title>a</title>
<id>http://127.0.0.1/t/a/#changeset-8580ff50825a50c8f716709acdf8de0deddcd6ab</id>
<link href="http://127.0.0.1/t/a/rev/8580ff50825a"/>
<author>
<name>test</name>
<email>test</email>
</author>
<updated>1970-01-01T00:00:01+00:00</updated>
<published>1970-01-01T00:00:01+00:00</published>
<content type="xhtml">
<div xmlns="http://127.0.0.1/1999/xhtml">
<pre xml:space="preserve">a</pre>
</div>
</content>
</entry>
</feed>
200 Script output follows
<?xml version="1.0" encoding="ascii"?>
<feed xmlns="http://127.0.0.1/2005/Atom">
<!-- Changelog -->
<id>http://127.0.0.1/t/a/</id>
<link rel="self" href="http://127.0.0.1/t/a/atom-log"/>
<link rel="alternate" href="http://127.0.0.1/t/a/"/>
<title>t/a Changelog</title>
<updated>1970-01-01T00:00:01+00:00</updated>
<entry>
<title>a</title>
<id>http://127.0.0.1/t/a/#changeset-8580ff50825a50c8f716709acdf8de0deddcd6ab</id>
<link href="http://127.0.0.1/t/a/rev/8580ff50825a"/>
<author>
<name>test</name>
<email>test</email>
</author>
<updated>1970-01-01T00:00:01+00:00</updated>
<published>1970-01-01T00:00:01+00:00</published>
<content type="xhtml">
<div xmlns="http://127.0.0.1/1999/xhtml">
<pre xml:space="preserve">a</pre>
</div>
</content>
</entry>
</feed>
200 Script output follows
a
200 Script output follows
/coll/a/
/coll/a/.hg/patches/
/coll/b/
/coll/c/
200 Script output follows
a
200 Script output follows
/rcoll/a/
/rcoll/a/.hg/patches/
/rcoll/b/
/rcoll/b/d/
/rcoll/c/
200 Script output follows
d
% test descend = False
200 Script output follows
/c/
200 Script output follows
/t/a/
/t/b/
% collections: should succeed
200 Script output follows
/a/
/a/.hg/patches/
/b/
/c/
200 Script output follows
a
200 Script output follows
b
200 Script output follows
c
% atom-log with basedir /
<link rel="self" href="http://example.com:8080/a/atom-log"/>
<link rel="alternate" href="http://example.com:8080/a/"/>
<link href="http://example.com:8080/a/rev/8580ff50825a"/>
% rss-log with basedir /
<guid isPermaLink="true">http://example.com:8080/a/rev/8580ff50825a</guid>
% atom-log with basedir /foo/
<link rel="self" href="http://example.com:8080/foo/a/atom-log"/>
<link rel="alternate" href="http://example.com:8080/foo/a/"/>
<link href="http://example.com:8080/foo/a/rev/8580ff50825a"/>
% rss-log with basedir /foo/
<guid isPermaLink="true">http://example.com:8080/foo/a/rev/8580ff50825a</guid>
% paths errors 1
% paths errors 2
% paths errors 3
% collections errors
% collections errors 2