/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: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2019-02-14 03:30:18 UTC
  • mfrom: (6745.1.3 test-file-ids)
  • Revision ID: breezy.the.bot@gmail.com-20190214033018-4mhv416kiuozgned
Fix a commonly typoed word: compatibility.

Merged from https://code.launchpad.net/~jelmer/brz/compatibility-typos/+merge/363008

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