87
90
self.recurse = recurse
88
91
self.change_reporter = change_reporter
89
92
self._cached_trees = {}
93
self._revision_graph = revision_graph
94
self._base_is_ancestor = None
95
self._base_is_other_ancestor = None
98
def revision_graph(self):
99
if self._revision_graph is None:
100
self._revision_graph = self.this_branch.repository.get_graph()
101
return self._revision_graph
103
def _set_base_is_ancestor(self, value):
104
self._base_is_ancestor = value
106
def _get_base_is_ancestor(self):
107
if self._base_is_ancestor is None:
108
self._base_is_ancestor = self.revision_graph.is_ancestor(
109
self.base_rev_id, self.this_basis)
110
return self._base_is_ancestor
112
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
114
def _set_base_is_other_ancestor(self, value):
115
self._base_is_other_ancestor = value
117
def _get_base_is_other_ancestor(self):
118
if self._base_is_other_ancestor is None:
119
self.base_is_other_ancestor = self.revision_graph.is_ancestor(
120
self.base_rev_id, self.other_basis)
121
return self._base_is_other_ancestor
123
base_is_other_ancestor = property(_get_base_is_other_ancestor,
124
_set_base_is_other_ancestor)
127
def from_uncommitted(tree, other_tree, pb):
128
"""Return a Merger for uncommitted changes in other_tree.
130
:param tree: The tree to merge into
131
:param other_tree: The tree to get uncommitted changes from
132
:param pb: A progress indicator
134
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
136
merger.base_rev_id = merger.base_tree.get_revision_id()
137
merger.other_rev_id = None
138
merger.other_basis = merger.base_rev_id
142
def from_mergeable(klass, tree, mergeable, pb):
143
"""Return a Merger for a bundle or merge directive.
145
:param tree: The tree to merge changes into
146
:param mergeable: A merge directive or bundle
147
:param pb: A progress indicator
149
mergeable.install_revisions(tree.branch.repository)
150
base_revision_id, other_revision_id, verified =\
151
mergeable.get_merge_request(tree.branch.repository)
152
revision_graph = tree.branch.repository.get_graph()
153
if (base_revision_id != _mod_revision.NULL_REVISION and
154
revision_graph.is_ancestor(
155
base_revision_id, tree.branch.last_revision())):
156
base_revision_id = None
158
warning('Performing cherrypick')
159
merger = klass.from_revision_ids(pb, tree, other_revision_id,
160
base_revision_id, revision_graph=
162
return merger, verified
165
def from_revision_ids(pb, this, other, base=None, other_branch=None,
166
base_branch=None, revision_graph=None):
167
"""Return a Merger for revision-ids.
169
:param tree: The tree to merge changes into
170
:param other: The revision-id to use as OTHER
171
:param base: The revision-id to use as BASE. If not specified, will
173
:param other_branch: A branch containing the other revision-id. If
174
not supplied, this.branch is used.
175
:param base_branch: A branch containing the base revision-id. If
176
not supplied, other_branch or this.branch will be used.
177
:param pb: A progress indicator
179
merger = Merger(this.branch, this_tree=this, pb=pb,
180
revision_graph=revision_graph)
181
if other_branch is None:
182
other_branch = this.branch
183
merger.set_other_revision(other, other_branch)
187
if base_branch is None:
188
base_branch = other_branch
189
merger.set_base_revision(base, base_branch)
91
192
def revision_tree(self, revision_id, branch=None):
92
193
if revision_id not in self._cached_trees:
382
499
self.change_reporter = change_reporter
383
500
if self.pp is None:
384
501
self.pp = ProgressPhase("Merge phase", 3, self.pb)
386
self.tt = TreeTransform(working_tree, self.pb)
506
self.this_tree.lock_tree_write()
507
self.base_tree.lock_read()
508
self.other_tree.lock_read()
509
self.tt = TreeTransform(self.this_tree, self.pb)
388
511
self.pp.next_phase()
389
entries = self._entries3()
390
child_pb = ui.ui_factory.nested_progress_bar()
392
for num, (file_id, changed, parents3, names3,
393
executable3) in enumerate(entries):
394
child_pb.update('Preparing file merge', num, len(entries))
395
self._merge_names(file_id, parents3, names3)
397
file_status = self.merge_contents(file_id)
399
file_status = 'unmodified'
400
self._merge_executable(file_id,
401
executable3, file_status)
406
child_pb = ui.ui_factory.nested_progress_bar()
408
fs_conflicts = resolve_conflicts(self.tt, child_pb,
409
lambda t, c: conflict_pass(t, c, self.other_tree))
412
if change_reporter is not None:
413
from bzrlib import delta
414
delta.report_changes(self.tt._iter_changes(), change_reporter)
415
self.cook_conflicts(fs_conflicts)
416
for conflict in self.cooked_conflicts:
512
self._compute_transform()
418
513
self.pp.next_phase()
419
514
results = self.tt.apply(no_conflicts=True)
420
515
self.write_modified(results)
422
working_tree.add_conflicts(self.cooked_conflicts)
517
self.this_tree.add_conflicts(self.cooked_conflicts)
423
518
except UnsupportedOperation:
896
1037
"""Three-way tree merger, text weave merger."""
897
1038
supports_reprocess = True
898
1039
supports_show_base = False
1040
supports_reverse_cherrypick = False
1041
history_based = True
900
1043
def __init__(self, working_tree, this_tree, base_tree, other_tree,
901
1044
interesting_ids=None, pb=DummyProgress(), pp=None,
902
1045
reprocess=False, change_reporter=None,
903
interesting_files=None):
904
self.this_revision_tree = self._get_revision_tree(this_tree)
905
self.other_revision_tree = self._get_revision_tree(other_tree)
1046
interesting_files=None, cherrypick=False, do_merge=True):
1047
self.cherrypick = cherrypick
906
1048
super(WeaveMerger, self).__init__(working_tree, this_tree,
907
1049
base_tree, other_tree,
908
1050
interesting_ids=interesting_ids,
909
1051
pb=pb, pp=pp, reprocess=reprocess,
910
change_reporter=change_reporter)
912
def _get_revision_tree(self, tree):
913
"""Return a revision tree related to this tree.
914
If the tree is a WorkingTree, the basis will be returned.
916
if getattr(tree, 'get_weave', False) is False:
917
# If we have a WorkingTree, try using the basis
918
return tree.branch.basis_tree()
922
def _check_file(self, file_id):
923
"""Check that the revision tree's version of the file matches."""
924
for tree, rt in ((self.this_tree, self.this_revision_tree),
925
(self.other_tree, self.other_revision_tree)):
928
if tree.get_file_sha1(file_id) != rt.get_file_sha1(file_id):
929
raise WorkingTreeNotRevision(self.this_tree)
1052
change_reporter=change_reporter,
931
1055
def _merged_lines(self, file_id):
932
1056
"""Generate the merged lines.
933
1057
There is no distinction between lines that are meant to contain <<<<<<<
936
weave = self.this_revision_tree.get_weave(file_id)
937
this_revision_id = self.this_revision_tree.inventory[file_id].revision
938
other_revision_id = \
939
self.other_revision_tree.inventory[file_id].revision
940
wm = WeaveMerge(weave, this_revision_id, other_revision_id,
941
'<<<<<<< TREE\n', '>>>>>>> MERGE-SOURCE\n')
942
return wm.merge_lines(self.reprocess)
1061
base = self.base_tree
1064
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1066
if 'merge' in debug.debug_flags:
1068
trans_id = self.tt.trans_id_file_id(file_id)
1069
name = self.tt.final_name(trans_id) + '.plan'
1070
contents = ('%10s|%s' % l for l in plan)
1071
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1072
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1073
'>>>>>>> MERGE-SOURCE\n')
1074
return textmerge.merge_lines(self.reprocess)
944
1076
def text_merge(self, file_id, trans_id):
945
1077
"""Perform a (weave) text merge for a given file and file-id.
946
1078
If conflicts are encountered, .THIS and .OTHER files will be emitted,
947
1079
and a conflict will be noted.
949
self._check_file(file_id)
950
1081
lines, conflicts = self._merged_lines(file_id)
951
1082
lines = list(lines)
952
1083
# Note we're checking whether the OUTPUT is binary in this case,
1049
1204
from bzrlib import option
1050
1205
return option._merge_type_registry
1208
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1209
def status_a(revision, text):
1210
if revision in ancestors_b:
1211
return 'killed-b', text
1213
return 'new-a', text
1215
def status_b(revision, text):
1216
if revision in ancestors_a:
1217
return 'killed-a', text
1219
return 'new-b', text
1221
plain_a = [t for (a, t) in annotated_a]
1222
plain_b = [t for (a, t) in annotated_b]
1223
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1224
blocks = matcher.get_matching_blocks()
1227
for ai, bi, l in blocks:
1228
# process all mismatched sections
1229
# (last mismatched section is handled because blocks always
1230
# includes a 0-length last block)
1231
for revision, text in annotated_a[a_cur:ai]:
1232
yield status_a(revision, text)
1233
for revision, text in annotated_b[b_cur:bi]:
1234
yield status_b(revision, text)
1236
# and now the matched section
1239
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1240
assert text_a == text_b
1241
yield "unchanged", text_a
1244
class _PlanMergeBase(object):
1246
def __init__(self, a_rev, b_rev, vf):
1249
:param a_rev: Revision-id of one revision to merge
1250
:param b_rev: Revision-id of the other revision to merge
1251
:param vf: A versionedfile containing both revisions
1255
self.lines_a = vf.get_lines(a_rev)
1256
self.lines_b = vf.get_lines(b_rev)
1258
self._last_lines = None
1259
self._last_lines_revision_id = None
1260
self._cached_matching_blocks = {}
1262
def plan_merge(self):
1263
"""Generate a 'plan' for merging the two revisions.
1265
This involves comparing their texts and determining the cause of
1266
differences. If text A has a line and text B does not, then either the
1267
line was added to text A, or it was deleted from B. Once the causes
1268
are combined, they are written out in the format described in
1269
VersionedFile.plan_merge
1271
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1272
unique_a, unique_b = self._unique_lines(blocks)
1273
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1274
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1275
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1277
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1280
for i, j, n in blocks:
1281
for a_index in range(last_i, i):
1282
if a_index in new_a:
1283
if a_index in killed_b:
1284
yield 'conflicted-a', self.lines_a[a_index]
1286
yield 'new-a', self.lines_a[a_index]
1288
yield 'killed-b', self.lines_a[a_index]
1289
for b_index in range(last_j, j):
1290
if b_index in new_b:
1291
if b_index in killed_a:
1292
yield 'conflicted-b', self.lines_b[a_index]
1294
yield 'new-b', self.lines_b[b_index]
1296
yield 'killed-a', self.lines_b[b_index]
1297
# handle common lines
1298
for a_index in range(i, i+n):
1299
yield 'unchanged', self.lines_a[a_index]
1303
def _get_matching_blocks(self, left_revision, right_revision):
1304
"""Return a description of which sections of two revisions match.
1306
See SequenceMatcher.get_matching_blocks
1308
cached = self._cached_matching_blocks.get((left_revision,
1310
if cached is not None:
1312
if self._last_lines_revision_id == left_revision:
1313
left_lines = self._last_lines
1315
left_lines = self.vf.get_lines(left_revision)
1316
right_lines = self.vf.get_lines(right_revision)
1317
self._last_lines = right_lines
1318
self._last_lines_revision_id = right_revision
1319
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1321
return matcher.get_matching_blocks()
1323
def _unique_lines(self, matching_blocks):
1324
"""Analyse matching_blocks to determine which lines are unique
1326
:return: a tuple of (unique_left, unique_right), where the values are
1327
sets of line numbers of unique lines.
1333
for i, j, n in matching_blocks:
1334
unique_left.extend(range(last_i, i))
1335
unique_right.extend(range(last_j, j))
1338
return unique_left, unique_right
1341
def _subtract_plans(old_plan, new_plan):
1342
"""Remove changes from new_plan that came from old_plan.
1344
It is assumed that the difference between the old_plan and new_plan
1345
is their choice of 'b' text.
1347
All lines from new_plan that differ from old_plan are emitted
1348
verbatim. All lines from new_plan that match old_plan but are
1349
not about the 'b' revision are emitted verbatim.
1351
Lines that match and are about the 'b' revision are the lines we
1352
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1353
is skipped entirely.
1355
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1358
for i, j, n in matcher.get_matching_blocks():
1359
for jj in range(last_j, j):
1361
for jj in range(j, j+n):
1362
plan_line = new_plan[jj]
1363
if plan_line[0] == 'new-b':
1365
elif plan_line[0] == 'killed-b':
1366
yield 'unchanged', plan_line[1]
1372
class _PlanMerge(_PlanMergeBase):
1373
"""Plan an annotate merge using on-the-fly annotation"""
1375
def __init__(self, a_rev, b_rev, vf):
1376
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1377
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1378
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1379
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1381
def _determine_status(self, revision_id, unique_line_numbers):
1382
"""Determines the status unique lines versus all lcas.
1384
Basically, determines why the line is unique to this revision.
1386
A line may be determined new or killed, but not both.
1388
:param revision_id: The id of the revision in which the lines are
1390
:param unique_line_numbers: The line numbers of unique lines.
1391
:return a tuple of (new_this, killed_other):
1393
new = self._find_new(revision_id)
1394
killed = set(unique_line_numbers).difference(new)
1397
def _find_new(self, version_id):
1398
"""Determine which lines are new in the ancestry of this version.
1400
If a lines is present in this version, and not present in any
1401
common ancestor, it is considered new.
1403
if version_id not in self.uncommon:
1405
parents = self.vf.get_parents(version_id)
1406
if len(parents) == 0:
1407
return set(range(len(self.vf.get_lines(version_id))))
1409
for parent in parents:
1410
blocks = self._get_matching_blocks(version_id, parent)
1411
result, unused = self._unique_lines(blocks)
1412
parent_new = self._find_new(parent)
1413
for i, j, n in blocks:
1414
for ii, jj in [(i+r, j+r) for r in range(n)]:
1415
if jj in parent_new:
1420
new.intersection_update(result)
1424
class _PlanLCAMerge(_PlanMergeBase):
1426
This merge algorithm differs from _PlanMerge in that:
1427
1. comparisons are done against LCAs only
1428
2. cases where a contested line is new versus one LCA but old versus
1429
another are marked as conflicts, by emitting the line as conflicted-a
1432
This is faster, and hopefully produces more useful output.
1435
def __init__(self, a_rev, b_rev, vf, graph):
1436
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1437
self.lcas = graph.find_lca(a_rev, b_rev)
1438
for lca in self.lcas:
1439
lca_lines = self.vf.get_lines(lca)
1440
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1442
blocks = list(matcher.get_matching_blocks())
1443
self._cached_matching_blocks[(a_rev, lca)] = blocks
1444
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1446
blocks = list(matcher.get_matching_blocks())
1447
self._cached_matching_blocks[(b_rev, lca)] = blocks
1449
def _determine_status(self, revision_id, unique_line_numbers):
1450
"""Determines the status unique lines versus all lcas.
1452
Basically, determines why the line is unique to this revision.
1454
A line may be determined new, killed, or both.
1456
If a line is determined new, that means it was not present in at least
1457
one LCA, and is not present in the other merge revision.
1459
If a line is determined killed, that means the line was present in
1462
If a line is killed and new, this indicates that the two merge
1463
revisions contain differing conflict resolutions.
1464
:param revision_id: The id of the revision in which the lines are
1466
:param unique_line_numbers: The line numbers of unique lines.
1467
:return a tuple of (new_this, killed_other):
1471
unique_line_numbers = set(unique_line_numbers)
1472
for lca in self.lcas:
1473
blocks = self._get_matching_blocks(revision_id, lca)
1474
unique_vs_lca, _ignored = self._unique_lines(blocks)
1475
new.update(unique_line_numbers.intersection(unique_vs_lca))
1476
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
