annotate mercurial/similar.py @ 50501:4242acf5c399

store: use the new boolean property in `remotefilelogserver`
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Mon, 15 May 2023 22:11:02 +0200
parents f254fc73d956
children 493034cc3265
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
1 # similar.py - mechanisms for finding similar files
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
2 #
46819
d4ba4d51f85f contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents: 45942
diff changeset
3 # Copyright 2005-2007 Olivia Mackall <olivia@selenic.com>
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
4 #
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
5 # This software may be used and distributed according to the terms of the
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
6 # GNU General Public License version 2 or any later version.
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
7
27359
a56c47ed3885 similar: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 16683
diff changeset
8
a56c47ed3885 similar: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 16683
diff changeset
9 from .i18n import _
43106
d783f945a701 py3: finish porting iteritems() to pycompat and remove source transformer
Gregory Szorc <gregory.szorc@gmail.com>
parents: 43077
diff changeset
10 from . import (
d783f945a701 py3: finish porting iteritems() to pycompat and remove source transformer
Gregory Szorc <gregory.szorc@gmail.com>
parents: 43077
diff changeset
11 mdiff,
d783f945a701 py3: finish porting iteritems() to pycompat and remove source transformer
Gregory Szorc <gregory.szorc@gmail.com>
parents: 43077
diff changeset
12 )
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
13
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
14
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
15 def _findexactmatches(repo, added, removed):
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 43106
diff changeset
16 """find renamed files that have no changes
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
17
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
18 Takes a list of new filectxs and a list of removed filectxs, and yields
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
19 (before, after) tuples of exact matches.
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 43106
diff changeset
20 """
31584
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
21 # Build table of removed files: {hash(fctx.data()): [fctx, ...]}.
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
22 # We use hash() to discard fctx.data() from memory.
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
23 hashes = {}
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
24 progress = repo.ui.makeprogress(
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
25 _(b'searching for exact renames'),
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
26 total=(len(added) + len(removed)),
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
27 unit=_(b'files'),
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
28 )
38348
cd196be26cb7 similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 32202
diff changeset
29 for fctx in removed:
cd196be26cb7 similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 32202
diff changeset
30 progress.increment()
31584
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
31 h = hash(fctx.data())
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
32 if h not in hashes:
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
33 hashes[h] = [fctx]
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
34 else:
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
35 hashes[h].append(fctx)
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
36
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
37 # For each added file, see if it corresponds to a removed file.
38348
cd196be26cb7 similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 32202
diff changeset
38 for fctx in added:
cd196be26cb7 similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 32202
diff changeset
39 progress.increment()
31210
e1d035905b2e similar: compare between actual file contents for exact identity
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 30809
diff changeset
40 adata = fctx.data()
31584
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
41 h = hash(adata)
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
42 for rfctx in hashes.get(h, []):
31210
e1d035905b2e similar: compare between actual file contents for exact identity
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 30809
diff changeset
43 # compare between actual file contents for exact identity
e1d035905b2e similar: compare between actual file contents for exact identity
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 30809
diff changeset
44 if adata == rfctx.data():
e1d035905b2e similar: compare between actual file contents for exact identity
FUJIWARA Katsunori <foozy@lares.dti.ne.jp>
parents: 30809
diff changeset
45 yield (rfctx, fctx)
31584
985a98c6bad0 similar: use cheaper hash() function to test exact matches
Yuya Nishihara <yuya@tcha.org>
parents: 31583
diff changeset
46 break
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
47
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
48 # Done
38373
ef692614e601 progress: hide update(None) in a new complete() method
Martin von Zweigbergk <martinvonz@google.com>
parents: 38348
diff changeset
49 progress.complete()
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
50
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
51
30805
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
52 def _ctxdata(fctx):
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
53 # lazily load text
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
54 orig = fctx.data()
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
55 return orig, mdiff.splitnewlines(orig)
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
56
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
57
30809
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
58 def _score(fctx, otherdata):
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
59 orig, lines = otherdata
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
60 text = fctx.data()
32202
ded48ad55146 bdiff: proxy through mdiff module
Yuya Nishihara <yuya@tcha.org>
parents: 31584
diff changeset
61 # mdiff.blocks() returns blocks of matching lines
30805
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
62 # count the number of bytes in each
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
63 equal = 0
32202
ded48ad55146 bdiff: proxy through mdiff module
Yuya Nishihara <yuya@tcha.org>
parents: 31584
diff changeset
64 matches = mdiff.blocks(text, orig)
30805
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
65 for x1, x2, y1, y2 in matches:
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
66 for line in lines[y1:y2]:
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
67 equal += len(line)
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
68
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
69 lengths = len(text) + len(orig)
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
70 return equal * 2.0 / lengths
0ae287eb6a4f similar: move score function to module level
Sean Farley <sean@farley.io>
parents: 30791
diff changeset
71
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
72
30809
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
73 def score(fctx1, fctx2):
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
74 return _score(fctx1, _ctxdata(fctx2))
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
75
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
76
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
77 def _findsimilarmatches(repo, added, removed, threshold):
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 43106
diff changeset
78 """find potentially renamed files based on similar file content
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
79
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
80 Takes a list of new filectxs and a list of removed filectxs, and yields
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
81 (before, after, score) tuples of partial matches.
45942
89a2afe31e82 formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents: 43106
diff changeset
82 """
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
83 copies = {}
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
84 progress = repo.ui.makeprogress(
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
85 _(b'searching for similar files'), unit=_(b'files'), total=len(removed)
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
86 )
38395
59c9d3cc810f similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 38373
diff changeset
87 for r in removed:
59c9d3cc810f similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 38373
diff changeset
88 progress.increment()
30809
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
89 data = None
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
90 for a in added:
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
91 bestscore = copies.get(a, (None, threshold))[1]
30809
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
92 if data is None:
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
93 data = _ctxdata(r)
8614546154cb similar: remove caching from the module level
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 30805
diff changeset
94 myscore = _score(a, data)
31583
2efd9771323e similar: take the first match instead of the last
Yuya Nishihara <yuya@tcha.org>
parents: 31582
diff changeset
95 if myscore > bestscore:
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
96 copies[a] = (r, myscore)
38395
59c9d3cc810f similar: use progress helper
Martin von Zweigbergk <martinvonz@google.com>
parents: 38373
diff changeset
97 progress.complete()
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
98
48913
f254fc73d956 global: bulk replace simple pycompat.iteritems(x) with x.items()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 48875
diff changeset
99 for dest, v in copies.items():
30791
ada160a8cfd8 similar: rename local variable to not collide with previous
Sean Farley <sean@farley.io>
parents: 29341
diff changeset
100 source, bscore = v
ada160a8cfd8 similar: rename local variable to not collide with previous
Sean Farley <sean@farley.io>
parents: 29341
diff changeset
101 yield source, dest, bscore
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
102
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
103
31582
2e254165a37c similar: do not look up and create filectx more than once
Yuya Nishihara <yuya@tcha.org>
parents: 31581
diff changeset
104 def _dropempty(fctxs):
2e254165a37c similar: do not look up and create filectx more than once
Yuya Nishihara <yuya@tcha.org>
parents: 31581
diff changeset
105 return [x for x in fctxs if x.size() > 0]
2e254165a37c similar: do not look up and create filectx more than once
Yuya Nishihara <yuya@tcha.org>
parents: 31581
diff changeset
106
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
107
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
108 def findrenames(repo, added, removed, threshold):
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
109 '''find renamed files -- yields (before, after, score) tuples'''
31581
b1528d195a13 similar: use common names for changectx variables
Yuya Nishihara <yuya@tcha.org>
parents: 31580
diff changeset
110 wctx = repo[None]
b1528d195a13 similar: use common names for changectx variables
Yuya Nishihara <yuya@tcha.org>
parents: 31580
diff changeset
111 pctx = wctx.p1()
11059
ef4aa90b1e58 Move 'findrenames' code into its own file.
David Greenaway <hg-dev@davidgreenaway.com>
parents:
diff changeset
112
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
113 # Zero length files will be frequently unrelated to each other, and
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
114 # tracking the deletion/addition of such a file will probably cause more
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
115 # harm than good. We strip them out here to avoid matching them later on.
31582
2e254165a37c similar: do not look up and create filectx more than once
Yuya Nishihara <yuya@tcha.org>
parents: 31581
diff changeset
116 addedfiles = _dropempty(wctx[fp] for fp in sorted(added))
2e254165a37c similar: do not look up and create filectx more than once
Yuya Nishihara <yuya@tcha.org>
parents: 31581
diff changeset
117 removedfiles = _dropempty(pctx[fp] for fp in sorted(removed) if fp in pctx)
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
118
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
119 # Find exact matches.
31580
d3e2af4e0128 similar: get rid of quadratic addedfiles.remove()
Yuya Nishihara <yuya@tcha.org>
parents: 31579
diff changeset
120 matchedfiles = set()
d3e2af4e0128 similar: get rid of quadratic addedfiles.remove()
Yuya Nishihara <yuya@tcha.org>
parents: 31579
diff changeset
121 for (a, b) in _findexactmatches(repo, addedfiles, removedfiles):
d3e2af4e0128 similar: get rid of quadratic addedfiles.remove()
Yuya Nishihara <yuya@tcha.org>
parents: 31579
diff changeset
122 matchedfiles.add(b)
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
123 yield (a.path(), b.path(), 1.0)
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
124
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
125 # If the user requested similar files to be matched, search for them also.
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
126 if threshold < 1.0:
31580
d3e2af4e0128 similar: get rid of quadratic addedfiles.remove()
Yuya Nishihara <yuya@tcha.org>
parents: 31579
diff changeset
127 addedfiles = [x for x in addedfiles if x not in matchedfiles]
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
128 for (a, b, score) in _findsimilarmatches(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
129 repo, addedfiles, removedfiles, threshold
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38395
diff changeset
130 ):
11060
e6df01776e08 findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
David Greenaway <hg-dev@davidgreenaway.com>
parents: 11059
diff changeset
131 yield (a.path(), b.path(), score)