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