/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/rename_map.py

  • Committer: Jelmer Vernooij
  • Date: 2018-05-19 13:16:11 UTC
  • mto: (6968.4.3 git-archive)
  • mto: This revision was merged to the branch mainline in revision 6972.
  • Revision ID: jelmer@jelmer.uk-20180519131611-l9h9ud41j7qg1m03
Move tar/zip to breezy.archive.

Show diffs side-by-side

added added

removed removed

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