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