Show More
@@ -1,112 +1,115 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 | util, |
|
|||
17 | ) |
|
16 | ) | |
18 |
|
17 | |||
19 | def _findexactmatches(repo, added, removed): |
|
18 | def _findexactmatches(repo, added, removed): | |
20 | '''find renamed files that have no changes |
|
19 | '''find renamed files that have no changes | |
21 |
|
20 | |||
22 | 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 | |
23 | (before, after) tuples of exact matches. |
|
22 | (before, after) tuples of exact matches. | |
24 | ''' |
|
23 | ''' | |
25 | numfiles = len(added) + len(removed) |
|
24 | numfiles = len(added) + len(removed) | |
26 |
|
25 | |||
27 | # Get hashes of removed files. |
|
26 | # Get hashes of removed files. | |
28 | hashes = {} |
|
27 | hashes = {} | |
29 | for i, fctx in enumerate(removed): |
|
28 | for i, fctx in enumerate(removed): | |
30 | repo.ui.progress(_('searching for exact renames'), i, total=numfiles, |
|
29 | repo.ui.progress(_('searching for exact renames'), i, total=numfiles, | |
31 | unit=_('files')) |
|
30 | unit=_('files')) | |
32 | h = hashlib.sha1(fctx.data()).digest() |
|
31 | h = hashlib.sha1(fctx.data()).digest() | |
33 | hashes[h] = fctx |
|
32 | hashes[h] = fctx | |
34 |
|
33 | |||
35 | # 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. | |
36 | for i, fctx in enumerate(added): |
|
35 | for i, fctx in enumerate(added): | |
37 | repo.ui.progress(_('searching for exact renames'), i + len(removed), |
|
36 | repo.ui.progress(_('searching for exact renames'), i + len(removed), | |
38 | total=numfiles, unit=_('files')) |
|
37 | total=numfiles, unit=_('files')) | |
39 | h = hashlib.sha1(fctx.data()).digest() |
|
38 | h = hashlib.sha1(fctx.data()).digest() | |
40 | if h in hashes: |
|
39 | if h in hashes: | |
41 | yield (hashes[h], fctx) |
|
40 | yield (hashes[h], fctx) | |
42 |
|
41 | |||
43 | # Done |
|
42 | # Done | |
44 | repo.ui.progress(_('searching for exact renames'), None) |
|
43 | repo.ui.progress(_('searching for exact renames'), None) | |
45 |
|
44 | |||
46 | @util.cachefunc |
|
|||
47 | def _ctxdata(fctx): |
|
45 | def _ctxdata(fctx): | |
48 | # lazily load text |
|
46 | # lazily load text | |
49 | orig = fctx.data() |
|
47 | orig = fctx.data() | |
50 | return orig, mdiff.splitnewlines(orig) |
|
48 | return orig, mdiff.splitnewlines(orig) | |
51 |
|
49 | |||
52 | @util.cachefunc |
|
50 | def _score(fctx, otherdata): | |
53 | def score(fctx1, fctx2): |
|
51 | orig, lines = otherdata | |
54 |
text = fctx |
|
52 | text = fctx.data() | |
55 | orig, lines = _ctxdata(fctx2) |
|
|||
56 | # bdiff.blocks() returns blocks of matching lines |
|
53 | # bdiff.blocks() returns blocks of matching lines | |
57 | # count the number of bytes in each |
|
54 | # count the number of bytes in each | |
58 | equal = 0 |
|
55 | equal = 0 | |
59 | matches = bdiff.blocks(text, orig) |
|
56 | matches = bdiff.blocks(text, orig) | |
60 | for x1, x2, y1, y2 in matches: |
|
57 | for x1, x2, y1, y2 in matches: | |
61 | for line in lines[y1:y2]: |
|
58 | for line in lines[y1:y2]: | |
62 | equal += len(line) |
|
59 | equal += len(line) | |
63 |
|
60 | |||
64 | lengths = len(text) + len(orig) |
|
61 | lengths = len(text) + len(orig) | |
65 | return equal * 2.0 / lengths |
|
62 | return equal * 2.0 / lengths | |
66 |
|
63 | |||
|
64 | def score(fctx1, fctx2): | |||
|
65 | return _score(fctx1, _ctxdata(fctx2)) | |||
|
66 | ||||
67 | def _findsimilarmatches(repo, added, removed, threshold): |
|
67 | def _findsimilarmatches(repo, added, removed, threshold): | |
68 | '''find potentially renamed files based on similar file content |
|
68 | '''find potentially renamed files based on similar file content | |
69 |
|
69 | |||
70 | Takes a list of new filectxs and a list of removed filectxs, and yields |
|
70 | Takes a list of new filectxs and a list of removed filectxs, and yields | |
71 | (before, after, score) tuples of partial matches. |
|
71 | (before, after, score) tuples of partial matches. | |
72 | ''' |
|
72 | ''' | |
73 | copies = {} |
|
73 | copies = {} | |
74 | for i, r in enumerate(removed): |
|
74 | for i, r in enumerate(removed): | |
75 | repo.ui.progress(_('searching for similar files'), i, |
|
75 | repo.ui.progress(_('searching for similar files'), i, | |
76 | total=len(removed), unit=_('files')) |
|
76 | total=len(removed), unit=_('files')) | |
77 |
|
77 | |||
|
78 | data = None | |||
78 | for a in added: |
|
79 | for a in added: | |
79 | bestscore = copies.get(a, (None, threshold))[1] |
|
80 | bestscore = copies.get(a, (None, threshold))[1] | |
80 | myscore = score(a, r) |
|
81 | if data is None: | |
|
82 | data = _ctxdata(r) | |||
|
83 | myscore = _score(a, data) | |||
81 | if myscore >= bestscore: |
|
84 | if myscore >= bestscore: | |
82 | copies[a] = (r, myscore) |
|
85 | copies[a] = (r, myscore) | |
83 | repo.ui.progress(_('searching'), None) |
|
86 | repo.ui.progress(_('searching'), None) | |
84 |
|
87 | |||
85 | for dest, v in copies.iteritems(): |
|
88 | for dest, v in copies.iteritems(): | |
86 | source, bscore = v |
|
89 | source, bscore = v | |
87 | yield source, dest, bscore |
|
90 | yield source, dest, bscore | |
88 |
|
91 | |||
89 | def findrenames(repo, added, removed, threshold): |
|
92 | def findrenames(repo, added, removed, threshold): | |
90 | '''find renamed files -- yields (before, after, score) tuples''' |
|
93 | '''find renamed files -- yields (before, after, score) tuples''' | |
91 | parentctx = repo['.'] |
|
94 | parentctx = repo['.'] | |
92 | workingctx = repo[None] |
|
95 | workingctx = repo[None] | |
93 |
|
96 | |||
94 | # Zero length files will be frequently unrelated to each other, and |
|
97 | # Zero length files will be frequently unrelated to each other, and | |
95 | # tracking the deletion/addition of such a file will probably cause more |
|
98 | # tracking the deletion/addition of such a file will probably cause more | |
96 | # harm than good. We strip them out here to avoid matching them later on. |
|
99 | # harm than good. We strip them out here to avoid matching them later on. | |
97 | addedfiles = set([workingctx[fp] for fp in added |
|
100 | addedfiles = set([workingctx[fp] for fp in added | |
98 | if workingctx[fp].size() > 0]) |
|
101 | if workingctx[fp].size() > 0]) | |
99 | removedfiles = set([parentctx[fp] for fp in removed |
|
102 | removedfiles = set([parentctx[fp] for fp in removed | |
100 | if fp in parentctx and parentctx[fp].size() > 0]) |
|
103 | if fp in parentctx and parentctx[fp].size() > 0]) | |
101 |
|
104 | |||
102 | # Find exact matches. |
|
105 | # Find exact matches. | |
103 | for (a, b) in _findexactmatches(repo, |
|
106 | for (a, b) in _findexactmatches(repo, | |
104 | sorted(addedfiles), sorted(removedfiles)): |
|
107 | sorted(addedfiles), sorted(removedfiles)): | |
105 | addedfiles.remove(b) |
|
108 | addedfiles.remove(b) | |
106 | yield (a.path(), b.path(), 1.0) |
|
109 | yield (a.path(), b.path(), 1.0) | |
107 |
|
110 | |||
108 | # If the user requested similar files to be matched, search for them also. |
|
111 | # If the user requested similar files to be matched, search for them also. | |
109 | if threshold < 1.0: |
|
112 | if threshold < 1.0: | |
110 | for (a, b, score) in _findsimilarmatches(repo, |
|
113 | for (a, b, score) in _findsimilarmatches(repo, | |
111 | sorted(addedfiles), sorted(removedfiles), threshold): |
|
114 | sorted(addedfiles), sorted(removedfiles), threshold): | |
112 | yield (a.path(), b.path(), score) |
|
115 | yield (a.path(), b.path(), score) |
General Comments 0
You need to be logged in to leave comments.
Login now