← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/rename_map.py

  • Committer: Vincent Ladeuil
  • Date: 2011-12-21 14:25:26 UTC
  • mto: This revision was merged to the branch mainline in revision 6397.
  • Revision ID: v.ladeuil+lp@free.fr-20111221142526-pnwau0xnalimujts
Provides MemoryStack to simplify configuration setup in tests

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/rename_map.py
 
1
# Copyright (C) 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
from __future__ import absolute_import
 
18
 
 
19
from cStringIO import StringIO
 
20
 
 
21
from bzrlib import (
 
22
    osutils,
 
23
    progress,
 
24
    trace,
 
25
)
 
26
from bzrlib.ui import ui_factory
 
27
from bzrlib.i18n import gettext
 
28
 
 
29
class RenameMap(object):
 
30
    """Determine a mapping of renames."""
 
31
 
 
32
    def __init__(self, tree):
 
33
        self.tree = tree
 
34
        self.edge_hashes = {}
 
35
 
 
36
    @staticmethod
 
37
    def iter_edge_hashes(lines):
 
38
        """Iterate through the hashes of line pairs (which make up an edge).
 
39
 
 
40
        The hash is truncated using a modulus to avoid excessive memory
 
41
        consumption by the hitscount dict.  A modulus of 10Mi means that the
 
42
        maximum number of keys is 10Mi.  (Keys are normally 32 bits, e.g.
 
43
        4 Gi)
 
44
        """
 
45
        modulus = 1024 * 1024 * 10
 
46
        for n in range(len(lines)):
 
47
            yield hash(tuple(lines[n:n+2])) % modulus
 
48
 
 
49
    def add_edge_hashes(self, lines, tag):
 
50
        """Update edge_hashes to include the given lines.
 
51
 
 
52
        :param lines: The lines to update the hashes for.
 
53
        :param tag: A tag uniquely associated with these lines (i.e. file-id)
 
54
        """
 
55
        for my_hash in self.iter_edge_hashes(lines):
 
56
            self.edge_hashes.setdefault(my_hash, set()).add(tag)
 
57
 
 
58
    def add_file_edge_hashes(self, tree, file_ids):
 
59
        """Update to reflect the hashes for files in the tree.
 
60
 
 
61
        :param tree: The tree containing the files.
 
62
        :param file_ids: A list of file_ids to perform the updates for.
 
63
        """
 
64
        desired_files = [(f, f) for f in file_ids]
 
65
        task = ui_factory.nested_progress_bar()
 
66
        try:
 
67
            for num, (file_id, contents) in enumerate(
 
68
                tree.iter_files_bytes(desired_files)):
 
69
                task.update(gettext('Calculating hashes'), num, len(file_ids))
 
70
                s = StringIO()
 
71
                s.writelines(contents)
 
72
                s.seek(0)
 
73
                self.add_edge_hashes(s.readlines(), file_id)
 
74
        finally:
 
75
            task.finished()
 
76
 
 
77
    def hitcounts(self, lines):
 
78
        """Count the number of hash hits for each tag, for the given lines.
 
79
 
 
80
        Hits are weighted according to the number of tags the hash is
 
81
        associated with; more tags means that the hash is less rare and should
 
82
        tend to be ignored.
 
83
        :param lines: The lines to calculate hashes of.
 
84
        :return: a dict of {tag: hitcount}
 
85
        """
 
86
        hits = {}
 
87
        for my_hash in self.iter_edge_hashes(lines):
 
88
            tags = self.edge_hashes.get(my_hash)
 
89
            if tags is None:
 
90
                continue
 
91
            taglen = len(tags)
 
92
            for tag in tags:
 
93
                if tag not in hits:
 
94
                    hits[tag] = 0
 
95
                hits[tag] += 1.0 / taglen
 
96
        return hits
 
97
 
 
98
    def get_all_hits(self, paths):
 
99
        """Find all the hit counts for the listed paths in the tree.
 
100
 
 
101
        :return: A list of tuples of count, path, file_id.
 
102
        """
 
103
        all_hits = []
 
104
        task = ui_factory.nested_progress_bar()
 
105
        try:
 
106
            for num, path in enumerate(paths):
 
107
                task.update(gettext('Determining hash hits'), num, len(paths))
 
108
                hits = self.hitcounts(self.tree.get_file_lines(None,
 
109
                                                               path=path))
 
110
                all_hits.extend((v, path, k) for k, v in hits.items())
 
111
        finally:
 
112
            task.finished()
 
113
        return all_hits
 
114
 
 
115
    def file_match(self, paths):
 
116
        """Return a mapping from file_ids to the supplied paths."""
 
117
        return self._match_hits(self.get_all_hits(paths))
 
118
 
 
119
    @staticmethod
 
120
    def _match_hits(hit_list):
 
121
        """Using a hit list, determine a path-to-fileid map.
 
122
 
 
123
        The hit list is a list of (count, path, file_id), where count is a
 
124
        (possibly float) number, with higher numbers indicating stronger
 
125
        matches.
 
126
        """
 
127
        seen_file_ids = set()
 
128
        path_map = {}
 
129
        for count, path, file_id in sorted(hit_list, reverse=True):
 
130
            if path in path_map or file_id in seen_file_ids:
 
131
                continue
 
132
            path_map[path] = file_id
 
133
            seen_file_ids.add(file_id)
 
134
        return path_map
 
135
 
 
136
    def get_required_parents(self, matches):
 
137
        """Return a dict of all file parents that must be versioned.
 
138
 
 
139
        The keys are the required parents and the values are sets of their
 
140
        children.
 
141
        """
 
142
        required_parents = {}
 
143
        for path in matches:
 
144
            while True:
 
145
                child = path
 
146
                path = osutils.dirname(path)
 
147
                if self.tree.path2id(path) is not None:
 
148
                    break
 
149
                required_parents.setdefault(path, []).append(child)
 
150
        require_ids = {}
 
151
        for parent, children in required_parents.iteritems():
 
152
            child_file_ids = set()
 
153
            for child in children:
 
154
                file_id = matches.get(child)
 
155
                if file_id is not None:
 
156
                    child_file_ids.add(file_id)
 
157
            require_ids[parent] = child_file_ids
 
158
        return require_ids
 
159
 
 
160
    def match_parents(self, required_parents, missing_parents):
 
161
        """Map parent directories to file-ids.
 
162
 
 
163
        This is done by finding similarity between the file-ids of children of
 
164
        required parent directories and the file-ids of children of missing
 
165
        parent directories.
 
166
        """
 
167
        all_hits = []
 
168
        for file_id, file_id_children in missing_parents.iteritems():
 
169
            for path, path_children in required_parents.iteritems():
 
170
                hits = len(path_children.intersection(file_id_children))
 
171
                if hits > 0:
 
172
                    all_hits.append((hits, path, file_id))
 
173
        return self._match_hits(all_hits)
 
174
 
 
175
    def _find_missing_files(self, basis):
 
176
        missing_files = set()
 
177
        missing_parents = {}
 
178
        candidate_files = set()
 
179
        task = ui_factory.nested_progress_bar()
 
180
        iterator = self.tree.iter_changes(basis, want_unversioned=True,
 
181
                                          pb=task)
 
182
        try:
 
183
            for (file_id, paths, changed_content, versioned, parent, name,
 
184
                 kind, executable) in iterator:
 
185
                if kind[1] is None and versioned[1]:
 
186
                    missing_parents.setdefault(parent[0], set()).add(file_id)
 
187
                    if kind[0] == 'file':
 
188
                        missing_files.add(file_id)
 
189
                    else:
 
190
                        #other kinds are not handled
 
191
                        pass
 
192
                if versioned == (False, False):
 
193
                    if self.tree.is_ignored(paths[1]):
 
194
                        continue
 
195
                    if kind[1] == 'file':
 
196
                        candidate_files.add(paths[1])
 
197
                    if kind[1] == 'directory':
 
198
                        for _dir, children in self.tree.walkdirs(paths[1]):
 
199
                            for child in children:
 
200
                                if child[2] == 'file':
 
201
                                    candidate_files.add(child[0])
 
202
        finally:
 
203
            task.finished()
 
204
        return missing_files, missing_parents, candidate_files
 
205
 
 
206
    @classmethod
 
207
    def guess_renames(klass, tree, dry_run=False):
 
208
        """Guess which files to rename, and perform the rename.
 
209
 
 
210
        We assume that unversioned files and missing files indicate that
 
211
        versioned files have been renamed outside of Bazaar.
 
212
 
 
213
        :param tree: A write-locked working tree.
 
214
        """
 
215
        required_parents = {}
 
216
        task = ui_factory.nested_progress_bar()
 
217
        try:
 
218
            pp = progress.ProgressPhase('Guessing renames', 4, task)
 
219
            basis = tree.basis_tree()
 
220
            basis.lock_read()
 
221
            try:
 
222
                rn = klass(tree)
 
223
                pp.next_phase()
 
224
                missing_files, missing_parents, candidate_files = (
 
225
                    rn._find_missing_files(basis))
 
226
                pp.next_phase()
 
227
                rn.add_file_edge_hashes(basis, missing_files)
 
228
            finally:
 
229
                basis.unlock()
 
230
            pp.next_phase()
 
231
            matches = rn.file_match(candidate_files)
 
232
            parents_matches = matches
 
233
            while len(parents_matches) > 0:
 
234
                required_parents = rn.get_required_parents(
 
235
                    parents_matches)
 
236
                parents_matches = rn.match_parents(required_parents,
 
237
                                                   missing_parents)
 
238
                matches.update(parents_matches)
 
239
            pp.next_phase()
 
240
            delta = rn._make_inventory_delta(matches)
 
241
            for old, new, file_id, entry in delta:
 
242
                trace.note( gettext("{0} => {1}").format(old, new) )
 
243
            if not dry_run:
 
244
                tree.add(required_parents)
 
245
                tree.apply_inventory_delta(delta)
 
246
        finally:
 
247
            task.finished()
 
248
 
 
249
    def _make_inventory_delta(self, matches):
 
250
        delta = []
 
251
        file_id_matches = dict((f, p) for p, f in matches.items())
 
252
        for old_path, entry in self.tree.iter_entries_by_dir(matches.values()):
 
253
            new_path = file_id_matches[entry.file_id]
 
254
            parent_path, new_name = osutils.split(new_path)
 
255
            parent_id = matches.get(parent_path)
 
256
            if parent_id is None:
 
257
                parent_id = self.tree.path2id(parent_path)
 
258
            if entry.name == new_name and entry.parent_id == parent_id:
 
259
                continue
 
260
            new_entry = entry.copy()
 
261
            new_entry.parent_id = parent_id
 
262
            new_entry.name = new_name
 
263
            delta.append((old_path, new_path, new_entry.file_id, new_entry))
 
264
        return delta