/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/multiwalker.py

  • Committer: Jelmer Vernooij
  • Date: 2019-05-12 09:30:18 UTC
  • mto: This revision was merged to the branch mainline in revision 7314.
  • Revision ID: jelmer@jelmer.uk-20190512093018-5qoe0ynr5mfzt7o7
Split out MultiWalker.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/multiwalker.py
 
1
# Copyright (C) 2005-2011 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
"""Walk multiple trees simultaneously.
 
18
"""
 
19
 
 
20
from __future__ import absolute_import
 
21
 
 
22
from . import (
 
23
    errors,
 
24
    osutils,
 
25
    )
 
26
 
 
27
from .sixish import (
 
28
    text_type,
 
29
    viewvalues,
 
30
    )
 
31
 
 
32
 
 
33
class MultiWalker(object):
 
34
    """Walk multiple trees simultaneously, getting combined results."""
 
35
 
 
36
    # Note: This could be written to not assume you can do out-of-order
 
37
    #       lookups. Instead any nodes that don't match in all trees could be
 
38
    #       marked as 'deferred', and then returned in the final cleanup loop.
 
39
    #       For now, I think it is "nicer" to return things as close to the
 
40
    #       "master_tree" order as we can.
 
41
 
 
42
    def __init__(self, master_tree, other_trees):
 
43
        """Create a new MultiWalker.
 
44
 
 
45
        All trees being walked must implement "iter_entries_by_dir()", such
 
46
        that they yield (path, object) tuples, where that object will have a
 
47
        '.file_id' member, that can be used to check equality.
 
48
 
 
49
        :param master_tree: All trees will be 'slaved' to the master_tree such
 
50
            that nodes in master_tree will be used as 'first-pass' sync points.
 
51
            Any nodes that aren't in master_tree will be merged in a second
 
52
            pass.
 
53
        :param other_trees: A list of other trees to walk simultaneously.
 
54
        """
 
55
        self._master_tree = master_tree
 
56
        self._other_trees = other_trees
 
57
 
 
58
        # Keep track of any nodes that were properly processed just out of
 
59
        # order, that way we don't return them at the end, we don't have to
 
60
        # track *all* processed file_ids, just the out-of-order ones
 
61
        self._out_of_order_processed = set()
 
62
 
 
63
    @staticmethod
 
64
    def _step_one(iterator):
 
65
        """Step an iter_entries_by_dir iterator.
 
66
 
 
67
        :return: (has_more, path, ie)
 
68
            If has_more is False, path and ie will be None.
 
69
        """
 
70
        try:
 
71
            path, ie = next(iterator)
 
72
        except StopIteration:
 
73
            return False, None, None
 
74
        else:
 
75
            return True, path, ie
 
76
 
 
77
    @staticmethod
 
78
    def _lt_path_by_dirblock(path1, path2):
 
79
        """Compare two paths based on what directory they are in.
 
80
 
 
81
        This generates a sort order, such that all children of a directory are
 
82
        sorted together, and grandchildren are in the same order as the
 
83
        children appear. But all grandchildren come after all children.
 
84
 
 
85
        :param path1: first path
 
86
        :param path2: the second path
 
87
        :return: negative number if ``path1`` comes first,
 
88
            0 if paths are equal
 
89
            and a positive number if ``path2`` sorts first
 
90
        """
 
91
        # Shortcut this special case
 
92
        if path1 == path2:
 
93
            return False
 
94
        # This is stolen from _dirstate_helpers_py.py, only switching it to
 
95
        # Unicode objects. Consider using encode_utf8() and then using the
 
96
        # optimized versions, or maybe writing optimized unicode versions.
 
97
        if not isinstance(path1, text_type):
 
98
            raise TypeError("'path1' must be a unicode string, not %s: %r"
 
99
                            % (type(path1), path1))
 
100
        if not isinstance(path2, text_type):
 
101
            raise TypeError("'path2' must be a unicode string, not %s: %r"
 
102
                            % (type(path2), path2))
 
103
        return (MultiWalker._path_to_key(path1) <
 
104
                MultiWalker._path_to_key(path2))
 
105
 
 
106
    @staticmethod
 
107
    def _path_to_key(path):
 
108
        dirname, basename = osutils.split(path)
 
109
        return (dirname.split(u'/'), basename)
 
110
 
 
111
    def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
 
112
        """Lookup an inventory entry by file_id.
 
113
 
 
114
        This is called when an entry is missing in the normal order.
 
115
        Generally this is because a file was either renamed, or it was
 
116
        deleted/added. If the entry was found in the inventory and not in
 
117
        extra_entries, it will be added to self._out_of_order_processed
 
118
 
 
119
        :param extra_entries: A dictionary of {file_id: (path, ie)}.  This
 
120
            should be filled with entries that were found before they were
 
121
            used. If file_id is present, it will be removed from the
 
122
            dictionary.
 
123
        :param other_tree: The Tree to search, in case we didn't find the entry
 
124
            yet.
 
125
        :param file_id: The file_id to look for
 
126
        :return: (path, ie) if found or (None, None) if not present.
 
127
        """
 
128
        if file_id in extra_entries:
 
129
            return extra_entries.pop(file_id)
 
130
        # TODO: Is id2path better as the first call, or is
 
131
        #       inventory[file_id] better as a first check?
 
132
        try:
 
133
            cur_path = other_tree.id2path(file_id)
 
134
        except errors.NoSuchId:
 
135
            cur_path = None
 
136
        if cur_path is None:
 
137
            return (None, None)
 
138
        else:
 
139
            self._out_of_order_processed.add(file_id)
 
140
            cur_ie = other_tree.root_inventory.get_entry(file_id)
 
141
            return (cur_path, cur_ie)
 
142
 
 
143
    def iter_all(self):
 
144
        """Match up the values in the different trees."""
 
145
        for result in self._walk_master_tree():
 
146
            yield result
 
147
        self._finish_others()
 
148
        for result in self._walk_others():
 
149
            yield result
 
150
 
 
151
    def _walk_master_tree(self):
 
152
        """First pass, walk all trees in lock-step.
 
153
 
 
154
        When we are done, all nodes in the master_tree will have been
 
155
        processed. _other_walkers, _other_entries, and _others_extra will be
 
156
        set on 'self' for future processing.
 
157
        """
 
158
        # This iterator has the most "inlining" done, because it tends to touch
 
159
        # every file in the tree, while the others only hit nodes that don't
 
160
        # match.
 
161
        master_iterator = self._master_tree.iter_entries_by_dir()
 
162
 
 
163
        other_walkers = [other.iter_entries_by_dir()
 
164
                         for other in self._other_trees]
 
165
        other_entries = [self._step_one(walker) for walker in other_walkers]
 
166
        # Track extra nodes in the other trees
 
167
        others_extra = [{} for _ in range(len(self._other_trees))]
 
168
 
 
169
        master_has_more = True
 
170
        step_one = self._step_one
 
171
        lookup_by_file_id = self._lookup_by_file_id
 
172
        out_of_order_processed = self._out_of_order_processed
 
173
 
 
174
        while master_has_more:
 
175
            (master_has_more, path, master_ie) = step_one(master_iterator)
 
176
            if not master_has_more:
 
177
                break
 
178
 
 
179
            file_id = master_ie.file_id
 
180
            other_values = []
 
181
            other_values_append = other_values.append
 
182
            next_other_entries = []
 
183
            next_other_entries_append = next_other_entries.append
 
184
            for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
 
185
                if not other_has_more:
 
186
                    other_values_append(lookup_by_file_id(
 
187
                        others_extra[idx], self._other_trees[idx], file_id))
 
188
                    next_other_entries_append((False, None, None))
 
189
                elif file_id == other_ie.file_id:
 
190
                    # This is the critical code path, as most of the entries
 
191
                    # should match between most trees.
 
192
                    other_values_append((other_path, other_ie))
 
193
                    next_other_entries_append(step_one(other_walkers[idx]))
 
194
                else:
 
195
                    # This walker did not match, step it until it either
 
196
                    # matches, or we know we are past the current walker.
 
197
                    other_walker = other_walkers[idx]
 
198
                    other_extra = others_extra[idx]
 
199
                    while (other_has_more and
 
200
                           self._lt_path_by_dirblock(other_path, path)):
 
201
                        other_file_id = other_ie.file_id
 
202
                        if other_file_id not in out_of_order_processed:
 
203
                            other_extra[other_file_id] = (other_path, other_ie)
 
204
                        other_has_more, other_path, other_ie = \
 
205
                            step_one(other_walker)
 
206
                    if other_has_more and other_ie.file_id == file_id:
 
207
                        # We ended up walking to this point, match and step
 
208
                        # again
 
209
                        other_values_append((other_path, other_ie))
 
210
                        other_has_more, other_path, other_ie = \
 
211
                            step_one(other_walker)
 
212
                    else:
 
213
                        # This record isn't in the normal order, see if it
 
214
                        # exists at all.
 
215
                        other_values_append(lookup_by_file_id(
 
216
                            other_extra, self._other_trees[idx], file_id))
 
217
                    next_other_entries_append((other_has_more, other_path,
 
218
                                               other_ie))
 
219
            other_entries = next_other_entries
 
220
 
 
221
            # We've matched all the walkers, yield this datapoint
 
222
            yield path, file_id, master_ie, other_values
 
223
        self._other_walkers = other_walkers
 
224
        self._other_entries = other_entries
 
225
        self._others_extra = others_extra
 
226
 
 
227
    def _finish_others(self):
 
228
        """Finish walking the other iterators, so we get all entries."""
 
229
        for idx, info in enumerate(self._other_entries):
 
230
            other_extra = self._others_extra[idx]
 
231
            (other_has_more, other_path, other_ie) = info
 
232
            while other_has_more:
 
233
                other_file_id = other_ie.file_id
 
234
                if other_file_id not in self._out_of_order_processed:
 
235
                    other_extra[other_file_id] = (other_path, other_ie)
 
236
                other_has_more, other_path, other_ie = \
 
237
                    self._step_one(self._other_walkers[idx])
 
238
        del self._other_entries
 
239
 
 
240
    def _walk_others(self):
 
241
        """Finish up by walking all the 'deferred' nodes."""
 
242
        # TODO: One alternative would be to grab all possible unprocessed
 
243
        #       file_ids, and then sort by path, and then yield them. That
 
244
        #       might ensure better ordering, in case a caller strictly
 
245
        #       requires parents before children.
 
246
        for idx, other_extra in enumerate(self._others_extra):
 
247
            others = sorted(viewvalues(other_extra),
 
248
                            key=lambda x: self._path_to_key(x[0]))
 
249
            for other_path, other_ie in others:
 
250
                file_id = other_ie.file_id
 
251
                # We don't need to check out_of_order_processed here, because
 
252
                # the lookup_by_file_id will be removing anything processed
 
253
                # from the extras cache
 
254
                other_extra.pop(file_id)
 
255
                other_values = [(None, None)] * idx
 
256
                other_values.append((other_path, other_ie))
 
257
                for alt_idx, alt_extra in enumerate(self._others_extra[idx + 1:]):
 
258
                    alt_idx = alt_idx + idx + 1
 
259
                    alt_extra = self._others_extra[alt_idx]
 
260
                    alt_tree = self._other_trees[alt_idx]
 
261
                    other_values.append(self._lookup_by_file_id(
 
262
                        alt_extra, alt_tree, file_id))
 
263
                yield other_path, file_id, None, other_values
 
264
 
 
265
 
 
266