295
356
uncommitted changes in the other tree, they will be assigned to the
296
357
'other:' pseudo-revision.
298
from bzrlib import merge
299
annotated_a = list(self.annotate_iter(file_id,
300
_mod_revision.CURRENT_REVISION))
301
annotated_b = list(other.annotate_iter(file_id, 'other:'))
302
ancestors_a = self._get_ancestors(_mod_revision.CURRENT_REVISION)
303
ancestors_b = other._get_ancestors('other:')
304
return merge._plan_annotate_merge(annotated_a, annotated_b,
305
ancestors_a, ancestors_b)
359
data = self._get_plan_merge_data(file_id, other, base)
360
vf, last_revision_a, last_revision_b, last_revision_base = data
361
return vf.plan_merge(last_revision_a, last_revision_b,
364
def plan_file_lca_merge(self, file_id, other, base=None):
365
"""Generate a merge plan based lca-newness.
367
If the file contains uncommitted changes in this tree, they will be
368
attributed to the 'current:' pseudo-revision. If the file contains
369
uncommitted changes in the other tree, they will be assigned to the
370
'other:' pseudo-revision.
372
data = self._get_plan_merge_data(file_id, other, base)
373
vf, last_revision_a, last_revision_b, last_revision_base = data
374
return vf.plan_lca_merge(last_revision_a, last_revision_b,
377
def _iter_parent_trees(self):
378
"""Iterate through parent trees, defaulting to Tree.revision_tree."""
379
for revision_id in self.get_parent_ids():
381
yield self.revision_tree(revision_id)
382
except errors.NoSuchRevisionInTree:
383
yield self.repository.revision_tree(revision_id)
386
def _file_revision(revision_tree, file_id):
387
"""Determine the revision associated with a file in a given tree."""
388
revision_tree.lock_read()
390
return revision_tree.inventory[file_id].revision
392
revision_tree.unlock()
394
def _get_file_revision(self, file_id, vf, tree_revision):
395
"""Ensure that file_id, tree_revision is in vf to plan the merge."""
397
if getattr(self, '_repository', None) is None:
398
last_revision = tree_revision
399
parent_keys = [(file_id, self._file_revision(t, file_id)) for t in
400
self._iter_parent_trees()]
401
vf.add_lines((file_id, last_revision), parent_keys,
402
self.get_file(file_id).readlines())
403
repo = self.branch.repository
406
last_revision = self._file_revision(self, file_id)
407
base_vf = self._repository.texts
408
if base_vf not in vf.fallback_versionedfiles:
409
vf.fallback_versionedfiles.append(base_vf)
307
412
inventory = property(_get_inventory,
308
413
doc="Inventory of this Tree")
818
948
self.source._comparison_data(from_entry, path)
819
949
kind = (from_kind, None)
820
950
executable = (from_executable, None)
821
changed_content = True
951
changed_content = from_kind is not None
822
952
# the parent's path is necessarily known at this point.
823
953
yield(file_id, (path, to_path), changed_content, versioned, parent,
824
954
name, kind, executable)
827
# This was deprecated before 0.12, but did not have an official warning
828
@symbol_versioning.deprecated_function(symbol_versioning.zero_twelve)
829
def RevisionTree(*args, **kwargs):
830
"""RevisionTree has moved to bzrlib.revisiontree.RevisionTree()
832
Accessing it as bzrlib.tree.RevisionTree has been deprecated as of
835
from bzrlib.revisiontree import RevisionTree as _RevisionTree
836
return _RevisionTree(*args, **kwargs)
957
class MultiWalker(object):
958
"""Walk multiple trees simultaneously, getting combined results."""
960
# Note: This could be written to not assume you can do out-of-order
961
# lookups. Instead any nodes that don't match in all trees could be
962
# marked as 'deferred', and then returned in the final cleanup loop.
963
# For now, I think it is "nicer" to return things as close to the
964
# "master_tree" order as we can.
966
def __init__(self, master_tree, other_trees):
967
"""Create a new MultiWalker.
969
All trees being walked must implement "iter_entries_by_dir()", such
970
that they yield (path, object) tuples, where that object will have a
971
'.file_id' member, that can be used to check equality.
973
:param master_tree: All trees will be 'slaved' to the master_tree such
974
that nodes in master_tree will be used as 'first-pass' sync points.
975
Any nodes that aren't in master_tree will be merged in a second
977
:param other_trees: A list of other trees to walk simultaneously.
979
self._master_tree = master_tree
980
self._other_trees = other_trees
982
# Keep track of any nodes that were properly processed just out of
983
# order, that way we don't return them at the end, we don't have to
984
# track *all* processed file_ids, just the out-of-order ones
985
self._out_of_order_processed = set()
988
def _step_one(iterator):
989
"""Step an iter_entries_by_dir iterator.
991
:return: (has_more, path, ie)
992
If has_more is False, path and ie will be None.
995
path, ie = iterator.next()
996
except StopIteration:
997
return False, None, None
999
return True, path, ie
1002
def _cmp_path_by_dirblock(path1, path2):
1003
"""Compare two paths based on what directory they are in.
1005
This generates a sort order, such that all children of a directory are
1006
sorted together, and grandchildren are in the same order as the
1007
children appear. But all grandchildren come after all children.
1009
:param path1: first path
1010
:param path2: the second path
1011
:return: negative number if ``path1`` comes first,
1012
0 if paths are equal
1013
and a positive number if ``path2`` sorts first
1015
# Shortcut this special case
1018
# This is stolen from _dirstate_helpers_py.py, only switching it to
1019
# Unicode objects. Consider using encode_utf8() and then using the
1020
# optimized versions, or maybe writing optimized unicode versions.
1021
if not isinstance(path1, unicode):
1022
raise TypeError("'path1' must be a unicode string, not %s: %r"
1023
% (type(path1), path1))
1024
if not isinstance(path2, unicode):
1025
raise TypeError("'path2' must be a unicode string, not %s: %r"
1026
% (type(path2), path2))
1027
return cmp(MultiWalker._path_to_key(path1),
1028
MultiWalker._path_to_key(path2))
1031
def _path_to_key(path):
1032
dirname, basename = osutils.split(path)
1033
return (dirname.split(u'/'), basename)
1035
def _lookup_by_file_id(self, extra_entries, other_tree, file_id):
1036
"""Lookup an inventory entry by file_id.
1038
This is called when an entry is missing in the normal order.
1039
Generally this is because a file was either renamed, or it was
1040
deleted/added. If the entry was found in the inventory and not in
1041
extra_entries, it will be added to self._out_of_order_processed
1043
:param extra_entries: A dictionary of {file_id: (path, ie)}. This
1044
should be filled with entries that were found before they were
1045
used. If file_id is present, it will be removed from the
1047
:param other_tree: The Tree to search, in case we didn't find the entry
1049
:param file_id: The file_id to look for
1050
:return: (path, ie) if found or (None, None) if not present.
1052
if file_id in extra_entries:
1053
return extra_entries.pop(file_id)
1054
# TODO: Is id2path better as the first call, or is
1055
# inventory[file_id] better as a first check?
1057
cur_path = other_tree.id2path(file_id)
1058
except errors.NoSuchId:
1060
if cur_path is None:
1063
self._out_of_order_processed.add(file_id)
1064
cur_ie = other_tree.inventory[file_id]
1065
return (cur_path, cur_ie)
1068
"""Match up the values in the different trees."""
1069
for result in self._walk_master_tree():
1071
self._finish_others()
1072
for result in self._walk_others():
1075
def _walk_master_tree(self):
1076
"""First pass, walk all trees in lock-step.
1078
When we are done, all nodes in the master_tree will have been
1079
processed. _other_walkers, _other_entries, and _others_extra will be
1080
set on 'self' for future processing.
1082
# This iterator has the most "inlining" done, because it tends to touch
1083
# every file in the tree, while the others only hit nodes that don't
1085
master_iterator = self._master_tree.iter_entries_by_dir()
1087
other_walkers = [other.iter_entries_by_dir()
1088
for other in self._other_trees]
1089
other_entries = [self._step_one(walker) for walker in other_walkers]
1090
# Track extra nodes in the other trees
1091
others_extra = [{} for i in xrange(len(self._other_trees))]
1093
master_has_more = True
1094
step_one = self._step_one
1095
lookup_by_file_id = self._lookup_by_file_id
1096
out_of_order_processed = self._out_of_order_processed
1098
while master_has_more:
1099
(master_has_more, path, master_ie) = step_one(master_iterator)
1100
if not master_has_more:
1103
file_id = master_ie.file_id
1105
other_values_append = other_values.append
1106
next_other_entries = []
1107
next_other_entries_append = next_other_entries.append
1108
for idx, (other_has_more, other_path, other_ie) in enumerate(other_entries):
1109
if not other_has_more:
1110
other_values_append(lookup_by_file_id(
1111
others_extra[idx], self._other_trees[idx], file_id))
1112
next_other_entries_append((False, None, None))
1113
elif file_id == other_ie.file_id:
1114
# This is the critical code path, as most of the entries
1115
# should match between most trees.
1116
other_values_append((other_path, other_ie))
1117
next_other_entries_append(step_one(other_walkers[idx]))
1119
# This walker did not match, step it until it either
1120
# matches, or we know we are past the current walker.
1121
other_walker = other_walkers[idx]
1122
other_extra = others_extra[idx]
1123
while (other_has_more and
1124
self._cmp_path_by_dirblock(other_path, path) < 0):
1125
other_file_id = other_ie.file_id
1126
if other_file_id not in out_of_order_processed:
1127
other_extra[other_file_id] = (other_path, other_ie)
1128
other_has_more, other_path, other_ie = \
1129
step_one(other_walker)
1130
if other_has_more and other_ie.file_id == file_id:
1131
# We ended up walking to this point, match and step
1133
other_values_append((other_path, other_ie))
1134
other_has_more, other_path, other_ie = \
1135
step_one(other_walker)
1137
# This record isn't in the normal order, see if it
1139
other_values_append(lookup_by_file_id(
1140
other_extra, self._other_trees[idx], file_id))
1141
next_other_entries_append((other_has_more, other_path,
1143
other_entries = next_other_entries
1145
# We've matched all the walkers, yield this datapoint
1146
yield path, file_id, master_ie, other_values
1147
self._other_walkers = other_walkers
1148
self._other_entries = other_entries
1149
self._others_extra = others_extra
1151
def _finish_others(self):
1152
"""Finish walking the other iterators, so we get all entries."""
1153
for idx, info in enumerate(self._other_entries):
1154
other_extra = self._others_extra[idx]
1155
(other_has_more, other_path, other_ie) = info
1156
while other_has_more:
1157
other_file_id = other_ie.file_id
1158
if other_file_id not in self._out_of_order_processed:
1159
other_extra[other_file_id] = (other_path, other_ie)
1160
other_has_more, other_path, other_ie = \
1161
self._step_one(self._other_walkers[idx])
1162
del self._other_entries
1164
def _walk_others(self):
1165
"""Finish up by walking all the 'deferred' nodes."""
1166
# TODO: One alternative would be to grab all possible unprocessed
1167
# file_ids, and then sort by path, and then yield them. That
1168
# might ensure better ordering, in case a caller strictly
1169
# requires parents before children.
1170
for idx, other_extra in enumerate(self._others_extra):
1171
others = sorted(other_extra.itervalues(),
1172
key=lambda x: self._path_to_key(x[0]))
1173
for other_path, other_ie in others:
1174
file_id = other_ie.file_id
1175
# We don't need to check out_of_order_processed here, because
1176
# the lookup_by_file_id will be removing anything processed
1177
# from the extras cache
1178
other_extra.pop(file_id)
1179
other_values = [(None, None) for i in xrange(idx)]
1180
other_values.append((other_path, other_ie))
1181
for alt_idx, alt_extra in enumerate(self._others_extra[idx+1:]):
1182
alt_idx = alt_idx + idx + 1
1183
alt_extra = self._others_extra[alt_idx]
1184
alt_tree = self._other_trees[alt_idx]
1185
other_values.append(self._lookup_by_file_id(
1186
alt_extra, alt_tree, file_id))
1187
yield other_path, file_id, None, other_values
added
removed
bzrlib/tree.py
