##// END OF EJS Templates
similar: use common names for changectx variables...
Yuya Nishihara -
r31581:b1528d19 default
parent child Browse files
Show More
@@ -1,120 +1,120 b''
1 # similar.py - mechanisms for finding similar files
1 # similar.py - mechanisms for finding similar files
2 #
2 #
3 # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
3 # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
4 #
4 #
5 # This software may be used and distributed according to the terms of the
5 # This software may be used and distributed according to the terms of the
6 # GNU General Public License version 2 or any later version.
6 # GNU General Public License version 2 or any later version.
7
7
8 from __future__ import absolute_import
8 from __future__ import absolute_import
9
9
10 import hashlib
10 import hashlib
11
11
12 from .i18n import _
12 from .i18n import _
13 from . import (
13 from . import (
14 bdiff,
14 bdiff,
15 mdiff,
15 mdiff,
16 )
16 )
17
17
18 def _findexactmatches(repo, added, removed):
18 def _findexactmatches(repo, added, removed):
19 '''find renamed files that have no changes
19 '''find renamed files that have no changes
20
20
21 Takes a list of new filectxs and a list of removed filectxs, and yields
21 Takes a list of new filectxs and a list of removed filectxs, and yields
22 (before, after) tuples of exact matches.
22 (before, after) tuples of exact matches.
23 '''
23 '''
24 numfiles = len(added) + len(removed)
24 numfiles = len(added) + len(removed)
25
25
26 # Get hashes of removed files.
26 # Get hashes of removed files.
27 hashes = {}
27 hashes = {}
28 for i, fctx in enumerate(removed):
28 for i, fctx in enumerate(removed):
29 repo.ui.progress(_('searching for exact renames'), i, total=numfiles,
29 repo.ui.progress(_('searching for exact renames'), i, total=numfiles,
30 unit=_('files'))
30 unit=_('files'))
31 h = hashlib.sha1(fctx.data()).digest()
31 h = hashlib.sha1(fctx.data()).digest()
32 hashes[h] = fctx
32 hashes[h] = fctx
33
33
34 # For each added file, see if it corresponds to a removed file.
34 # For each added file, see if it corresponds to a removed file.
35 for i, fctx in enumerate(added):
35 for i, fctx in enumerate(added):
36 repo.ui.progress(_('searching for exact renames'), i + len(removed),
36 repo.ui.progress(_('searching for exact renames'), i + len(removed),
37 total=numfiles, unit=_('files'))
37 total=numfiles, unit=_('files'))
38 adata = fctx.data()
38 adata = fctx.data()
39 h = hashlib.sha1(adata).digest()
39 h = hashlib.sha1(adata).digest()
40 if h in hashes:
40 if h in hashes:
41 rfctx = hashes[h]
41 rfctx = hashes[h]
42 # compare between actual file contents for exact identity
42 # compare between actual file contents for exact identity
43 if adata == rfctx.data():
43 if adata == rfctx.data():
44 yield (rfctx, fctx)
44 yield (rfctx, fctx)
45
45
46 # Done
46 # Done
47 repo.ui.progress(_('searching for exact renames'), None)
47 repo.ui.progress(_('searching for exact renames'), None)
48
48
49 def _ctxdata(fctx):
49 def _ctxdata(fctx):
50 # lazily load text
50 # lazily load text
51 orig = fctx.data()
51 orig = fctx.data()
52 return orig, mdiff.splitnewlines(orig)
52 return orig, mdiff.splitnewlines(orig)
53
53
54 def _score(fctx, otherdata):
54 def _score(fctx, otherdata):
55 orig, lines = otherdata
55 orig, lines = otherdata
56 text = fctx.data()
56 text = fctx.data()
57 # bdiff.blocks() returns blocks of matching lines
57 # bdiff.blocks() returns blocks of matching lines
58 # count the number of bytes in each
58 # count the number of bytes in each
59 equal = 0
59 equal = 0
60 matches = bdiff.blocks(text, orig)
60 matches = bdiff.blocks(text, orig)
61 for x1, x2, y1, y2 in matches:
61 for x1, x2, y1, y2 in matches:
62 for line in lines[y1:y2]:
62 for line in lines[y1:y2]:
63 equal += len(line)
63 equal += len(line)
64
64
65 lengths = len(text) + len(orig)
65 lengths = len(text) + len(orig)
66 return equal * 2.0 / lengths
66 return equal * 2.0 / lengths
67
67
68 def score(fctx1, fctx2):
68 def score(fctx1, fctx2):
69 return _score(fctx1, _ctxdata(fctx2))
69 return _score(fctx1, _ctxdata(fctx2))
70
70
71 def _findsimilarmatches(repo, added, removed, threshold):
71 def _findsimilarmatches(repo, added, removed, threshold):
72 '''find potentially renamed files based on similar file content
72 '''find potentially renamed files based on similar file content
73
73
74 Takes a list of new filectxs and a list of removed filectxs, and yields
74 Takes a list of new filectxs and a list of removed filectxs, and yields
75 (before, after, score) tuples of partial matches.
75 (before, after, score) tuples of partial matches.
76 '''
76 '''
77 copies = {}
77 copies = {}
78 for i, r in enumerate(removed):
78 for i, r in enumerate(removed):
79 repo.ui.progress(_('searching for similar files'), i,
79 repo.ui.progress(_('searching for similar files'), i,
80 total=len(removed), unit=_('files'))
80 total=len(removed), unit=_('files'))
81
81
82 data = None
82 data = None
83 for a in added:
83 for a in added:
84 bestscore = copies.get(a, (None, threshold))[1]
84 bestscore = copies.get(a, (None, threshold))[1]
85 if data is None:
85 if data is None:
86 data = _ctxdata(r)
86 data = _ctxdata(r)
87 myscore = _score(a, data)
87 myscore = _score(a, data)
88 if myscore >= bestscore:
88 if myscore >= bestscore:
89 copies[a] = (r, myscore)
89 copies[a] = (r, myscore)
90 repo.ui.progress(_('searching'), None)
90 repo.ui.progress(_('searching'), None)
91
91
92 for dest, v in copies.iteritems():
92 for dest, v in copies.iteritems():
93 source, bscore = v
93 source, bscore = v
94 yield source, dest, bscore
94 yield source, dest, bscore
95
95
96 def findrenames(repo, added, removed, threshold):
96 def findrenames(repo, added, removed, threshold):
97 '''find renamed files -- yields (before, after, score) tuples'''
97 '''find renamed files -- yields (before, after, score) tuples'''
98 parentctx = repo['.']
98 wctx = repo[None]
99 workingctx = repo[None]
99 pctx = wctx.p1()
100
100
101 # Zero length files will be frequently unrelated to each other, and
101 # Zero length files will be frequently unrelated to each other, and
102 # tracking the deletion/addition of such a file will probably cause more
102 # tracking the deletion/addition of such a file will probably cause more
103 # harm than good. We strip them out here to avoid matching them later on.
103 # harm than good. We strip them out here to avoid matching them later on.
104 addedfiles = [workingctx[fp] for fp in sorted(added)
104 addedfiles = [wctx[fp] for fp in sorted(added)
105 if workingctx[fp].size() > 0]
105 if wctx[fp].size() > 0]
106 removedfiles = [parentctx[fp] for fp in sorted(removed)
106 removedfiles = [pctx[fp] for fp in sorted(removed)
107 if fp in parentctx and parentctx[fp].size() > 0]
107 if fp in pctx and pctx[fp].size() > 0]
108
108
109 # Find exact matches.
109 # Find exact matches.
110 matchedfiles = set()
110 matchedfiles = set()
111 for (a, b) in _findexactmatches(repo, addedfiles, removedfiles):
111 for (a, b) in _findexactmatches(repo, addedfiles, removedfiles):
112 matchedfiles.add(b)
112 matchedfiles.add(b)
113 yield (a.path(), b.path(), 1.0)
113 yield (a.path(), b.path(), 1.0)
114
114
115 # If the user requested similar files to be matched, search for them also.
115 # If the user requested similar files to be matched, search for them also.
116 if threshold < 1.0:
116 if threshold < 1.0:
117 addedfiles = [x for x in addedfiles if x not in matchedfiles]
117 addedfiles = [x for x in addedfiles if x not in matchedfiles]
118 for (a, b, score) in _findsimilarmatches(repo, addedfiles,
118 for (a, b, score) in _findsimilarmatches(repo, addedfiles,
119 removedfiles, threshold):
119 removedfiles, threshold):
120 yield (a.path(), b.path(), score)
120 yield (a.path(), b.path(), score)
General Comments 0
You need to be logged in to leave comments. Login now