70
82
class Merger(object):
71
def __init__(self, this_branch, other_tree=None, base_tree=None,
72
this_tree=None, pb=DummyProgress(), change_reporter=None,
73
recurse='down', revision_graph=None):
83
def __init__(self, this_branch, other_tree=None, base_tree=None,
84
this_tree=None, pb=DummyProgress()):
74
85
object.__init__(self)
86
assert this_tree is not None, "this_tree is required"
75
87
self.this_branch = this_branch
76
self.this_basis = _mod_revision.ensure_null(
77
this_branch.last_revision())
88
self.this_basis = this_branch.last_revision()
78
89
self.this_rev_id = None
79
90
self.this_tree = this_tree
80
91
self.this_revision_tree = None
81
92
self.this_basis_tree = None
82
93
self.other_tree = other_tree
83
self.other_branch = None
84
94
self.base_tree = base_tree
85
95
self.ignore_zero = False
86
96
self.backup_files = False
87
97
self.interesting_ids = None
88
self.interesting_files = None
89
98
self.show_base = False
90
99
self.reprocess = False
93
self.recurse = recurse
94
self.change_reporter = change_reporter
95
self._cached_trees = {}
96
self._revision_graph = revision_graph
97
self._base_is_ancestor = None
98
self._base_is_other_ancestor = None
101
def revision_graph(self):
102
if self._revision_graph is None:
103
self._revision_graph = self.this_branch.repository.get_graph()
104
return self._revision_graph
106
def _set_base_is_ancestor(self, value):
107
self._base_is_ancestor = value
109
def _get_base_is_ancestor(self):
110
if self._base_is_ancestor is None:
111
self._base_is_ancestor = self.revision_graph.is_ancestor(
112
self.base_rev_id, self.this_basis)
113
return self._base_is_ancestor
115
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
117
def _set_base_is_other_ancestor(self, value):
118
self._base_is_other_ancestor = value
120
def _get_base_is_other_ancestor(self):
121
if self._base_is_other_ancestor is None:
122
if self.other_basis is None:
124
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
125
self.base_rev_id, self.other_basis)
126
return self._base_is_other_ancestor
128
base_is_other_ancestor = property(_get_base_is_other_ancestor,
129
_set_base_is_other_ancestor)
132
def from_uncommitted(tree, other_tree, pb):
133
"""Return a Merger for uncommitted changes in other_tree.
135
:param tree: The tree to merge into
136
:param other_tree: The tree to get uncommitted changes from
137
:param pb: A progress indicator
139
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
141
merger.base_rev_id = merger.base_tree.get_revision_id()
142
merger.other_rev_id = None
143
merger.other_basis = merger.base_rev_id
147
def from_mergeable(klass, tree, mergeable, pb):
148
"""Return a Merger for a bundle or merge directive.
150
:param tree: The tree to merge changes into
151
:param mergeable: A merge directive or bundle
152
:param pb: A progress indicator
154
mergeable.install_revisions(tree.branch.repository)
155
base_revision_id, other_revision_id, verified =\
156
mergeable.get_merge_request(tree.branch.repository)
157
revision_graph = tree.branch.repository.get_graph()
158
if base_revision_id is not None:
159
if (base_revision_id != _mod_revision.NULL_REVISION and
160
revision_graph.is_ancestor(
161
base_revision_id, tree.branch.last_revision())):
162
base_revision_id = None
164
warning('Performing cherrypick')
165
merger = klass.from_revision_ids(pb, tree, other_revision_id,
166
base_revision_id, revision_graph=
168
return merger, verified
171
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
172
base_branch=None, revision_graph=None):
173
"""Return a Merger for revision-ids.
175
:param tree: The tree to merge changes into
176
:param other: The revision-id to use as OTHER
177
:param base: The revision-id to use as BASE. If not specified, will
179
:param other_branch: A branch containing the other revision-id. If
180
not supplied, tree.branch is used.
181
:param base_branch: A branch containing the base revision-id. If
182
not supplied, other_branch or tree.branch will be used.
183
:param revision_graph: If you have a revision_graph precomputed, pass
184
it in, otherwise it will be created for you.
185
:param pb: A progress indicator
187
merger = Merger(tree.branch, this_tree=tree, pb=pb,
188
revision_graph=revision_graph)
189
if other_branch is None:
190
other_branch = tree.branch
191
merger.set_other_revision(other, other_branch)
195
if base_branch is None:
196
base_branch = other_branch
197
merger.set_base_revision(base, base_branch)
200
def revision_tree(self, revision_id, branch=None):
201
if revision_id not in self._cached_trees:
203
branch = self.this_branch
205
tree = self.this_tree.revision_tree(revision_id)
206
except errors.NoSuchRevisionInTree:
207
tree = branch.repository.revision_tree(revision_id)
208
self._cached_trees[revision_id] = tree
209
return self._cached_trees[revision_id]
211
def _get_tree(self, treespec, possible_transports=None):
212
from bzrlib import workingtree
213
location, revno = treespec
215
tree = workingtree.WorkingTree.open_containing(location)[0]
216
return tree.branch, tree
217
branch = Branch.open_containing(location, possible_transports)[0]
219
revision_id = branch.last_revision()
221
revision_id = branch.get_rev_id(revno)
222
revision_id = ensure_null(revision_id)
223
return branch, self.revision_tree(revision_id, branch)
102
def revision_tree(self, revision_id):
103
return self.this_branch.repository.revision_tree(revision_id)
225
105
def ensure_revision_trees(self):
226
106
if self.this_revision_tree is None:
227
self.this_basis_tree = self.revision_tree(self.this_basis)
107
self.this_basis_tree = self.this_branch.repository.revision_tree(
228
109
if self.this_basis == self.this_rev_id:
229
110
self.this_revision_tree = self.this_basis_tree
231
112
if self.other_rev_id is None:
232
113
other_basis_tree = self.revision_tree(self.other_basis)
233
changes = other_basis_tree.changes_from(self.other_tree)
114
changes = compare_trees(self.other_tree, other_basis_tree)
234
115
if changes.has_changed():
235
116
raise WorkingTreeNotRevision(self.this_tree)
236
other_rev_id = self.other_basis
117
other_rev_id = other_basis
237
118
self.other_tree = other_basis_tree
239
120
def file_revisions(self, file_id):
240
121
self.ensure_revision_trees()
241
122
def get_id(tree, file_id):
242
123
revision_id = tree.inventory[file_id].revision
124
assert revision_id is not None
243
125
return revision_id
244
126
if self.this_rev_id is None:
245
127
if self.this_basis_tree.get_file_sha1(file_id) != \
249
131
trees = (self.this_basis_tree, self.other_tree)
250
132
return [get_id(tree, file_id) for tree in trees]
252
def check_basis(self, check_clean, require_commits=True):
253
if self.this_basis is None and require_commits is True:
254
raise BzrCommandError("This branch has no commits."
255
" (perhaps you would prefer 'bzr pull')")
134
def check_basis(self, check_clean):
135
if self.this_basis is None:
136
raise BzrCommandError("This branch has no commits")
257
138
self.compare_basis()
258
139
if self.this_basis != self.this_rev_id:
259
raise errors.UncommittedChanges(self.this_tree)
140
raise BzrCommandError("Working tree has uncommitted changes.")
261
142
def compare_basis(self):
263
basis_tree = self.revision_tree(self.this_tree.last_revision())
264
except errors.NoSuchRevision:
265
basis_tree = self.this_tree.basis_tree()
266
changes = self.this_tree.changes_from(basis_tree)
143
changes = compare_trees(self.this_tree,
144
self.this_tree.basis_tree(), False)
267
145
if not changes.has_changed():
268
146
self.this_rev_id = self.this_basis
270
148
def set_interesting_files(self, file_list):
271
self.interesting_files = file_list
150
self._set_interesting_files(file_list)
151
except NotVersionedError, e:
152
raise BzrCommandError("%s is not a source file in any"
155
def _set_interesting_files(self, file_list):
156
"""Set the list of interesting ids from a list of files."""
157
if file_list is None:
158
self.interesting_ids = None
161
interesting_ids = set()
162
for path in file_list:
164
for tree in (self.this_tree, self.base_tree, self.other_tree):
165
file_id = tree.inventory.path2id(path)
166
if file_id is not None:
167
interesting_ids.add(file_id)
170
raise NotVersionedError(path=path)
171
self.interesting_ids = interesting_ids
273
173
def set_pending(self):
274
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
278
def _add_parent(self):
279
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
280
new_parent_trees = []
281
for revision_id in new_parents:
283
tree = self.revision_tree(revision_id)
284
except errors.NoSuchRevision:
288
new_parent_trees.append((revision_id, tree))
290
self.this_tree.set_parent_trees(new_parent_trees,
291
allow_leftmost_as_ghost=True)
293
for _revision_id, tree in new_parent_trees:
297
def set_other(self, other_revision, possible_transports=None):
298
"""Set the revision and tree to merge from.
300
This sets the other_tree, other_rev_id, other_basis attributes.
302
:param other_revision: The [path, revision] list to merge from.
304
self.other_branch, self.other_tree = self._get_tree(other_revision,
174
if not self.base_is_ancestor:
176
if self.other_rev_id is None:
178
ancestry = self.this_branch.repository.get_ancestry(self.this_basis)
179
if self.other_rev_id in ancestry:
181
self.this_tree.add_pending_merge(self.other_rev_id)
183
def set_other(self, other_revision):
184
other_branch, self.other_tree = _get_tree(other_revision,
306
186
if other_revision[1] == -1:
307
self.other_rev_id = _mod_revision.ensure_null(
308
self.other_branch.last_revision())
309
if _mod_revision.is_null(self.other_rev_id):
310
raise NoCommits(self.other_branch)
187
self.other_rev_id = other_branch.last_revision()
188
if self.other_rev_id is None:
189
raise NoCommits(other_branch)
311
190
self.other_basis = self.other_rev_id
312
191
elif other_revision[1] is not None:
313
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
192
self.other_rev_id = other_branch.get_rev_id(other_revision[1])
314
193
self.other_basis = self.other_rev_id
316
195
self.other_rev_id = None
317
self.other_basis = self.other_branch.last_revision()
196
self.other_basis = other_branch.last_revision()
318
197
if self.other_basis is None:
319
raise NoCommits(self.other_branch)
320
if self.other_rev_id is not None:
321
self._cached_trees[self.other_rev_id] = self.other_tree
322
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
324
def set_other_revision(self, revision_id, other_branch):
325
"""Set 'other' based on a branch and revision id
327
:param revision_id: The revision to use for a tree
328
:param other_branch: The branch containing this tree
330
self.other_rev_id = revision_id
331
self.other_branch = other_branch
332
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
333
self.other_tree = self.revision_tree(revision_id)
334
self.other_basis = revision_id
336
def set_base_revision(self, revision_id, branch):
337
"""Set 'base' based on a branch and revision id
339
:param revision_id: The revision to use for a tree
340
:param branch: The branch containing this tree
342
self.base_rev_id = revision_id
343
self.base_branch = branch
344
self._maybe_fetch(branch, self.this_branch, revision_id)
345
self.base_tree = self.revision_tree(revision_id)
347
def _maybe_fetch(self, source, target, revision_id):
348
if not source.repository.has_same_location(target.repository):
349
target.fetch(source, revision_id)
352
revisions = [ensure_null(self.this_basis),
353
ensure_null(self.other_basis)]
354
if NULL_REVISION in revisions:
355
self.base_rev_id = NULL_REVISION
357
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
358
revisions[0], revisions[1], count_steps=True)
359
if self.base_rev_id == NULL_REVISION:
360
raise UnrelatedBranches()
362
warning('Warning: criss-cross merge encountered. See bzr'
363
' help criss-cross.')
364
self.base_tree = self.revision_tree(self.base_rev_id)
365
self.base_is_ancestor = True
366
self.base_is_other_ancestor = True
198
raise NoCommits(other_branch)
199
if other_branch.base != self.this_branch.base:
200
self.this_branch.fetch(other_branch, last_revision=self.other_basis)
368
202
def set_base(self, base_revision):
369
"""Set the base revision to use for the merge.
371
:param base_revision: A 2-list containing a path and revision number.
373
203
mutter("doing merge() with no base_revision specified")
374
204
if base_revision == [None, None]:
206
self.base_rev_id = common_ancestor(self.this_basis,
208
self.this_branch.repository,
210
except NoCommonAncestor:
211
raise UnrelatedBranches()
212
self.base_tree = _get_revid_tree(self.this_branch, self.base_rev_id,
214
self.base_is_ancestor = True
377
base_branch, self.base_tree = self._get_tree(base_revision)
216
base_branch, self.base_tree = _get_tree(base_revision)
378
217
if base_revision[1] == -1:
379
218
self.base_rev_id = base_branch.last_revision()
380
219
elif base_revision[1] is None:
381
self.base_rev_id = _mod_revision.NULL_REVISION
220
self.base_rev_id = None
383
self.base_rev_id = _mod_revision.ensure_null(
384
base_branch.get_rev_id(base_revision[1]))
385
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
222
self.base_rev_id = base_branch.get_rev_id(base_revision[1])
223
self.this_branch.fetch(base_branch)
224
self.base_is_ancestor = is_ancestor(self.this_basis,
387
def make_merger(self):
388
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
389
'other_tree': self.other_tree,
390
'interesting_ids': self.interesting_ids,
391
'interesting_files': self.interesting_files,
229
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
230
'other_tree': self.other_tree,
231
'interesting_ids': self.interesting_ids}
394
232
if self.merge_type.requires_base:
395
233
kwargs['base_tree'] = self.base_tree
396
234
if self.merge_type.supports_reprocess:
397
235
kwargs['reprocess'] = self.reprocess
398
236
elif self.reprocess:
399
raise BzrError("Conflict reduction is not supported for merge"
400
" type %s." % self.merge_type)
237
raise BzrError("Reprocess is not supported for this merge"
238
" type. %s" % merge_type)
401
239
if self.merge_type.supports_show_base:
402
240
kwargs['show_base'] = self.show_base
403
241
elif self.show_base:
404
242
raise BzrError("Showing base is not supported for this"
405
" merge type. %s" % self.merge_type)
406
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
407
and not self.base_is_other_ancestor):
408
raise errors.CannotReverseCherrypick()
409
if self.merge_type.supports_cherrypick:
410
kwargs['cherrypick'] = (not self.base_is_ancestor or
411
not self.base_is_other_ancestor)
412
return self.merge_type(pb=self._pb,
413
change_reporter=self.change_reporter,
416
def _do_merge_to(self, merge):
418
if self.recurse == 'down':
419
for relpath, file_id in self.this_tree.iter_references():
420
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
421
other_revision = self.other_tree.get_reference_revision(
423
if other_revision == sub_tree.last_revision():
425
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
426
sub_merge.merge_type = self.merge_type
427
other_branch = self.other_branch.reference_parent(file_id, relpath)
428
sub_merge.set_other_revision(other_revision, other_branch)
429
base_revision = self.base_tree.get_reference_revision(file_id)
430
sub_merge.base_tree = \
431
sub_tree.branch.repository.revision_tree(base_revision)
432
sub_merge.base_rev_id = base_revision
436
self.this_tree.lock_tree_write()
438
if self.base_tree is not None:
439
self.base_tree.lock_read()
441
if self.other_tree is not None:
442
self.other_tree.lock_read()
444
merge = self.make_merger()
445
self._do_merge_to(merge)
447
if self.other_tree is not None:
448
self.other_tree.unlock()
450
if self.base_tree is not None:
451
self.base_tree.unlock()
453
self.this_tree.unlock()
243
" merge type. %s" % self.merge_type)
244
merge = self.merge_type(pb=self._pb, **kwargs)
454
245
if len(merge.cooked_conflicts) == 0:
455
if not self.ignore_zero and not is_quiet():
246
if not self.ignore_zero:
456
247
note("All changes applied successfully.")
458
249
note("%d conflicts encountered." % len(merge.cooked_conflicts))
460
251
return len(merge.cooked_conflicts)
253
def regen_inventory(self, new_entries):
254
old_entries = self.this_tree.read_working_inventory()
258
for path, file_id in new_entries:
261
new_entries_map[file_id] = path
263
def id2path(file_id):
264
path = new_entries_map.get(file_id)
267
entry = old_entries[file_id]
268
if entry.parent_id is None:
270
return pathjoin(id2path(entry.parent_id), entry.name)
272
for file_id in old_entries:
273
entry = old_entries[file_id]
274
path = id2path(file_id)
275
new_inventory[file_id] = (path, file_id, entry.parent_id,
277
by_path[path] = file_id
282
for path, file_id in new_entries:
284
del new_inventory[file_id]
287
new_path_list.append((path, file_id))
288
if file_id not in old_entries:
290
# Ensure no file is added before its parent
292
for path, file_id in new_path_list:
296
parent = by_path[os.path.dirname(path)]
297
abspath = pathjoin(self.this_tree.basedir, path)
298
kind = bzrlib.osutils.file_kind(abspath)
299
new_inventory[file_id] = (path, file_id, parent, kind)
300
by_path[path] = file_id
302
# Get a list in insertion order
303
new_inventory_list = new_inventory.values()
304
mutter ("""Inventory regeneration:
305
old length: %i insertions: %i deletions: %i new_length: %i"""\
306
% (len(old_entries), insertions, deletions,
307
len(new_inventory_list)))
308
assert len(new_inventory_list) == len(old_entries) + insertions\
310
new_inventory_list.sort()
311
return new_inventory_list
463
314
class Merge3Merger(object):
464
315
"""Three-way merger that uses the merge3 text merger"""
511
331
self.reprocess = reprocess
512
332
self.show_base = show_base
515
self.change_reporter = change_reporter
516
self.cherrypick = cherrypick
518
self.pp = ProgressPhase("Merge phase", 3, self.pb)
523
self.this_tree.lock_tree_write()
524
self.base_tree.lock_read()
525
self.other_tree.lock_read()
526
self.tt = TreeTransform(self.this_tree, self.pb)
335
if interesting_ids is not None:
336
all_ids = interesting_ids
338
all_ids = set(base_tree)
339
all_ids.update(other_tree)
340
self.tt = TreeTransform(working_tree, self.pb)
529
self._compute_transform()
531
results = self.tt.apply(no_conflicts=True)
532
self.write_modified(results)
342
for num, file_id in enumerate(all_ids):
343
self.pb.update('Preparing file merge', num+1, len(all_ids))
344
self.merge_names(file_id)
345
file_status = self.merge_contents(file_id)
346
self.merge_executable(file_id, file_status)
349
fs_conflicts = resolve_conflicts(self.tt, self.pb)
350
self.cook_conflicts(fs_conflicts)
351
for line in conflicts_strings(self.cooked_conflicts):
534
self.this_tree.add_conflicts(self.cooked_conflicts)
535
except UnsupportedOperation:
539
self.other_tree.unlock()
540
self.base_tree.unlock()
541
self.this_tree.unlock()
544
def make_preview_transform(self):
545
self.base_tree.lock_read()
546
self.other_tree.lock_read()
547
self.tt = TransformPreview(self.this_tree)
550
self._compute_transform()
553
self.other_tree.unlock()
554
self.base_tree.unlock()
558
def _compute_transform(self):
559
entries = self._entries3()
560
child_pb = ui.ui_factory.nested_progress_bar()
562
for num, (file_id, changed, parents3, names3,
563
executable3) in enumerate(entries):
564
child_pb.update('Preparing file merge', num, len(entries))
565
self._merge_names(file_id, parents3, names3)
567
file_status = self.merge_contents(file_id)
569
file_status = 'unmodified'
570
self._merge_executable(file_id,
571
executable3, file_status)
576
child_pb = ui.ui_factory.nested_progress_bar()
578
fs_conflicts = resolve_conflicts(self.tt, child_pb,
579
lambda t, c: conflict_pass(t, c, self.other_tree))
582
if self.change_reporter is not None:
583
from bzrlib import delta
584
delta.report_changes(
585
self.tt.iter_changes(), self.change_reporter)
586
self.cook_conflicts(fs_conflicts)
587
for conflict in self.cooked_conflicts:
591
"""Gather data about files modified between three trees.
593
Return a list of tuples of file_id, changed, parents3, names3,
594
executable3. changed is a boolean indicating whether the file contents
595
or kind were changed. parents3 is a tuple of parent ids for base,
596
other and this. names3 is a tuple of names for base, other and this.
597
executable3 is a tuple of execute-bit values for base, other and this.
600
iterator = self.other_tree.iter_changes(self.base_tree,
601
include_unchanged=True, specific_files=self.interesting_files,
602
extra_trees=[self.this_tree])
603
for (file_id, paths, changed, versioned, parents, names, kind,
604
executable) in iterator:
605
if (self.interesting_ids is not None and
606
file_id not in self.interesting_ids):
608
if file_id in self.this_tree.inventory:
609
entry = self.this_tree.inventory[file_id]
610
this_name = entry.name
611
this_parent = entry.parent_id
612
this_executable = entry.executable
616
this_executable = None
617
parents3 = parents + (this_parent,)
618
names3 = names + (this_name,)
619
executable3 = executable + (this_executable,)
620
result.append((file_id, changed, parents3, names3, executable3))
625
self.tt.final_kind(self.tt.root)
627
self.tt.cancel_deletion(self.tt.root)
628
if self.tt.final_file_id(self.tt.root) is None:
629
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
631
if self.other_tree.inventory.root is None:
633
other_root_file_id = self.other_tree.get_root_id()
634
other_root = self.tt.trans_id_file_id(other_root_file_id)
635
if other_root == self.tt.root:
638
self.tt.final_kind(other_root)
641
if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
642
# the other tree's root is a non-root in the current tree
644
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
645
self.tt.cancel_creation(other_root)
646
self.tt.cancel_versioning(other_root)
648
def reparent_children(self, ie, target):
649
for thing, child in ie.children.iteritems():
650
trans_id = self.tt.trans_id_file_id(child.file_id)
651
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
653
def write_modified(self, results):
655
for path in results.modified_paths:
656
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
659
hash = self.this_tree.get_file_sha1(file_id)
662
modified_hashes[file_id] = hash
663
self.this_tree.set_merge_modified(modified_hashes)
666
361
def parent(entry, file_id):
667
362
"""Determine the parent for a file_id (used as a key method)"""
1015
676
if path.endswith(suffix):
1016
677
path = path[:-len(suffix)]
1018
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1019
self.cooked_conflicts.append(c)
679
self.cooked_conflicts.append((conflict_type, file_id, path))
1020
680
if conflict_type == 'text conflict':
1021
681
trans_id = conflict[1]
1022
682
path = fp.get_path(trans_id)
1023
683
file_id = self.tt.final_file_id(trans_id)
1024
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1025
self.cooked_conflicts.append(c)
684
self.cooked_conflicts.append((conflict_type, file_id, path))
1027
686
for trans_id, conflicts in name_conflicts.iteritems():
1029
688
this_parent, other_parent = conflicts['parent conflict']
1030
if this_parent == other_parent:
1031
raise AssertionError()
689
assert this_parent != other_parent
1032
690
except KeyError:
1033
691
this_parent = other_parent = \
1034
692
self.tt.final_file_id(self.tt.final_parent(trans_id))
1036
694
this_name, other_name = conflicts['name conflict']
1037
if this_name == other_name:
1038
raise AssertionError()
695
assert this_name != other_name
1039
696
except KeyError:
1040
697
this_name = other_name = self.tt.final_name(trans_id)
1041
698
other_path = fp.get_path(trans_id)
1042
if this_parent is not None and this_name is not None:
699
if this_parent is not None:
1043
700
this_parent_path = \
1044
701
fp.get_path(self.tt.trans_id_file_id(this_parent))
1045
702
this_path = pathjoin(this_parent_path, this_name)
1047
704
this_path = "<deleted>"
1048
705
file_id = self.tt.final_file_id(trans_id)
1049
c = Conflict.factory('path conflict', path=this_path,
1050
conflict_path=other_path, file_id=file_id)
1051
self.cooked_conflicts.append(c)
1052
self.cooked_conflicts.sort(key=Conflict.sort_key)
706
self.cooked_conflicts.append(('path conflict', file_id, this_path,
1055
710
class WeaveMerger(Merge3Merger):
1056
711
"""Three-way tree merger, text weave merger."""
1057
supports_reprocess = True
712
supports_reprocess = False
1058
713
supports_show_base = False
1059
supports_reverse_cherrypick = False
1060
history_based = True
715
def __init__(self, working_tree, this_tree, base_tree, other_tree,
716
interesting_ids=None, pb=DummyProgress()):
717
self.this_revision_tree = self._get_revision_tree(this_tree)
718
self.other_revision_tree = self._get_revision_tree(other_tree)
719
super(WeaveMerger, self).__init__(working_tree, this_tree,
720
base_tree, other_tree,
721
interesting_ids=interesting_ids,
724
def _get_revision_tree(self, tree):
725
"""Return a revision tree releated to this tree.
726
If the tree is a WorkingTree, the basis will be returned.
728
if getattr(tree, 'get_weave', False) is False:
729
# If we have a WorkingTree, try using the basis
730
return tree.branch.basis_tree()
734
def _check_file(self, file_id):
735
"""Check that the revision tree's version of the file matches."""
736
for tree, rt in ((self.this_tree, self.this_revision_tree),
737
(self.other_tree, self.other_revision_tree)):
740
if tree.get_file_sha1(file_id) != rt.get_file_sha1(file_id):
741
raise WorkingTreeNotRevision(self.this_tree)
1062
743
def _merged_lines(self, file_id):
1063
744
"""Generate the merged lines.
1064
745
There is no distinction between lines that are meant to contain <<<<<<<
1068
base = self.base_tree
1071
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1073
if 'merge' in debug.debug_flags:
1075
trans_id = self.tt.trans_id_file_id(file_id)
1076
name = self.tt.final_name(trans_id) + '.plan'
1077
contents = ('%10s|%s' % l for l in plan)
1078
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1079
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1080
'>>>>>>> MERGE-SOURCE\n')
1081
return textmerge.merge_lines(self.reprocess)
748
weave = self.this_revision_tree.get_weave(file_id)
749
this_revision_id = self.this_revision_tree.inventory[file_id].revision
750
other_revision_id = \
751
self.other_revision_tree.inventory[file_id].revision
752
this_i = weave.lookup(this_revision_id)
753
other_i = weave.lookup(other_revision_id)
754
plan = weave.plan_merge(this_i, other_i)
755
return weave.weave_merge(plan, '<<<<<<< TREE\n',
756
'>>>>>>> MERGE-SOURCE\n')
1083
758
def text_merge(self, file_id, trans_id):
1084
759
"""Perform a (weave) text merge for a given file and file-id.
1085
760
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1086
761
and a conflict will be noted.
1088
lines, conflicts = self._merged_lines(file_id)
1090
# Note we're checking whether the OUTPUT is binary in this case,
1091
# because we don't want to get into weave merge guts.
1092
check_text_lines(lines)
763
self._check_file(file_id)
764
lines = self._merged_lines(file_id)
765
conflicts = '<<<<<<< TREE\n' in lines
1093
766
self.tt.create_file(lines, trans_id)
1095
768
self._raw_conflicts.append(('text conflict', trans_id))
1185
825
branch.get_revision_tree(base_revision))'
1187
827
if this_tree is None:
1188
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1189
"parameter as of bzrlib version 0.8.")
1190
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1191
pb=pb, change_reporter=change_reporter)
828
warn("bzrlib.merge.merge_inner requires a this_tree parameter as of "
829
"bzrlib version 0.8.",
832
this_tree = this_branch.bzrdir.open_workingtree()
833
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1192
835
merger.backup_files = backup_files
1193
836
merger.merge_type = merge_type
1194
837
merger.interesting_ids = interesting_ids
1195
merger.ignore_zero = ignore_zero
1196
838
if interesting_files:
1198
raise ValueError('Only supply interesting_ids'
1199
' or interesting_files')
1200
merger.interesting_files = interesting_files
1201
merger.show_base = show_base
839
assert not interesting_ids, ('Only supply interesting_ids'
840
' or interesting_files')
841
merger._set_interesting_files(interesting_files)
842
merger.show_base = show_base
1202
843
merger.reprocess = reprocess
1203
844
merger.other_rev_id = other_rev_id
1204
845
merger.other_basis = other_rev_id
1205
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1206
if get_revision_id is None:
1207
get_revision_id = base_tree.last_revision
1208
merger.set_base_revision(get_revision_id(), this_branch)
1209
846
return merger.do_merge()
1211
def get_merge_type_registry():
1212
"""Merge type registry is in bzrlib.option to avoid circular imports.
1214
This method provides a sanctioned way to retrieve it.
1216
from bzrlib import option
1217
return option._merge_type_registry
1220
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1221
def status_a(revision, text):
1222
if revision in ancestors_b:
1223
return 'killed-b', text
1225
return 'new-a', text
1227
def status_b(revision, text):
1228
if revision in ancestors_a:
1229
return 'killed-a', text
1231
return 'new-b', text
1233
plain_a = [t for (a, t) in annotated_a]
1234
plain_b = [t for (a, t) in annotated_b]
1235
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1236
blocks = matcher.get_matching_blocks()
1239
for ai, bi, l in blocks:
1240
# process all mismatched sections
1241
# (last mismatched section is handled because blocks always
1242
# includes a 0-length last block)
1243
for revision, text in annotated_a[a_cur:ai]:
1244
yield status_a(revision, text)
1245
for revision, text in annotated_b[b_cur:bi]:
1246
yield status_b(revision, text)
1247
# and now the matched section
1250
for text_a in plain_a[ai:a_cur]:
1251
yield "unchanged", text_a
1254
class _PlanMergeBase(object):
1256
def __init__(self, a_rev, b_rev, vf, key_prefix):
1259
:param a_rev: Revision-id of one revision to merge
1260
:param b_rev: Revision-id of the other revision to merge
1261
:param vf: A VersionedFiles containing both revisions
1262
:param key_prefix: A prefix for accessing keys in vf, typically
1268
self._last_lines = None
1269
self._last_lines_revision_id = None
1270
self._cached_matching_blocks = {}
1271
self._key_prefix = key_prefix
1272
self._precache_tip_lines()
1274
def _precache_tip_lines(self):
1275
lines = self.get_lines([self.a_rev, self.b_rev])
1276
self.lines_a = lines[self.a_rev]
1277
self.lines_b = lines[self.b_rev]
1279
def get_lines(self, revisions):
1280
"""Get lines for revisions from the backing VersionedFiles.
1282
:raises RevisionNotPresent: on absent texts.
1284
keys = [(self._key_prefix + (rev,)) for rev in revisions]
1286
for record in self.vf.get_record_stream(keys, 'unordered', True):
1287
if record.storage_kind == 'absent':
1288
raise errors.RevisionNotPresent(record.key, self.vf)
1289
result[record.key[-1]] = osutils.split_lines(
1290
record.get_bytes_as('fulltext'))
1293
def plan_merge(self):
1294
"""Generate a 'plan' for merging the two revisions.
1296
This involves comparing their texts and determining the cause of
1297
differences. If text A has a line and text B does not, then either the
1298
line was added to text A, or it was deleted from B. Once the causes
1299
are combined, they are written out in the format described in
1300
VersionedFile.plan_merge
1302
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1303
unique_a, unique_b = self._unique_lines(blocks)
1304
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1305
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1306
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1308
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1311
for i, j, n in blocks:
1312
for a_index in range(last_i, i):
1313
if a_index in new_a:
1314
if a_index in killed_b:
1315
yield 'conflicted-a', self.lines_a[a_index]
1317
yield 'new-a', self.lines_a[a_index]
1319
yield 'killed-b', self.lines_a[a_index]
1320
for b_index in range(last_j, j):
1321
if b_index in new_b:
1322
if b_index in killed_a:
1323
yield 'conflicted-b', self.lines_b[b_index]
1325
yield 'new-b', self.lines_b[b_index]
1327
yield 'killed-a', self.lines_b[b_index]
1328
# handle common lines
1329
for a_index in range(i, i+n):
1330
yield 'unchanged', self.lines_a[a_index]
1334
def _get_matching_blocks(self, left_revision, right_revision):
1335
"""Return a description of which sections of two revisions match.
1337
See SequenceMatcher.get_matching_blocks
1339
cached = self._cached_matching_blocks.get((left_revision,
1341
if cached is not None:
1343
if self._last_lines_revision_id == left_revision:
1344
left_lines = self._last_lines
1345
right_lines = self.get_lines([right_revision])[right_revision]
1347
lines = self.get_lines([left_revision, right_revision])
1348
left_lines = lines[left_revision]
1349
right_lines = lines[right_revision]
1350
self._last_lines = right_lines
1351
self._last_lines_revision_id = right_revision
1352
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1354
return matcher.get_matching_blocks()
1356
def _unique_lines(self, matching_blocks):
1357
"""Analyse matching_blocks to determine which lines are unique
1359
:return: a tuple of (unique_left, unique_right), where the values are
1360
sets of line numbers of unique lines.
1366
for i, j, n in matching_blocks:
1367
unique_left.extend(range(last_i, i))
1368
unique_right.extend(range(last_j, j))
1371
return unique_left, unique_right
1374
def _subtract_plans(old_plan, new_plan):
1375
"""Remove changes from new_plan that came from old_plan.
1377
It is assumed that the difference between the old_plan and new_plan
1378
is their choice of 'b' text.
1380
All lines from new_plan that differ from old_plan are emitted
1381
verbatim. All lines from new_plan that match old_plan but are
1382
not about the 'b' revision are emitted verbatim.
1384
Lines that match and are about the 'b' revision are the lines we
1385
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1386
is skipped entirely.
1388
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1391
for i, j, n in matcher.get_matching_blocks():
1392
for jj in range(last_j, j):
1394
for jj in range(j, j+n):
1395
plan_line = new_plan[jj]
1396
if plan_line[0] == 'new-b':
1398
elif plan_line[0] == 'killed-b':
1399
yield 'unchanged', plan_line[1]
1405
class _PlanMerge(_PlanMergeBase):
1406
"""Plan an annotate merge using on-the-fly annotation"""
1408
def __init__(self, a_rev, b_rev, vf, key_prefix):
1409
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1410
self.a_key = self._key_prefix + (self.a_rev,)
1411
self.b_key = self._key_prefix + (self.b_rev,)
1412
self.graph = Graph(self.vf)
1413
heads = self.graph.heads((self.a_key, self.b_key))
1415
# one side dominates, so we can just return its values, yay for
1417
# Ideally we would know that before we get this far
1418
self._head_key = heads.pop()
1419
if self._head_key == self.a_key:
1423
mutter('found dominating revision for %s\n%s > %s', self.vf,
1424
self._head_key[-1], other)
1427
self._head_key = None
1430
def _precache_tip_lines(self):
1431
# Turn this into a no-op, because we will do this later
1434
def _find_recursive_lcas(self):
1435
"""Find all the ancestors back to a unique lca"""
1436
cur_ancestors = (self.a_key, self.b_key)
1437
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1438
# rather than a key tuple. We will just map that directly to no common
1442
next_lcas = self.graph.find_lca(*cur_ancestors)
1443
# Map a plain NULL_REVISION to a simple no-ancestors
1444
if next_lcas == set([NULL_REVISION]):
1446
# Order the lca's based on when they were merged into the tip
1447
# While the actual merge portion of weave merge uses a set() of
1448
# active revisions, the order of insertion *does* effect the
1449
# implicit ordering of the texts.
1450
for rev_key in cur_ancestors:
1451
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1453
parent_map[rev_key] = ordered_parents
1454
if len(next_lcas) == 0:
1456
elif len(next_lcas) == 1:
1457
parent_map[list(next_lcas)[0]] = ()
1459
elif len(next_lcas) > 2:
1460
# More than 2 lca's, fall back to grabbing all nodes between
1461
# this and the unique lca.
1462
mutter('More than 2 LCAs, falling back to all nodes for:'
1463
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1464
cur_lcas = next_lcas
1465
while len(cur_lcas) > 1:
1466
cur_lcas = self.graph.find_lca(*cur_lcas)
1467
if len(cur_lcas) == 0:
1468
# No common base to find, use the full ancestry
1471
unique_lca = list(cur_lcas)[0]
1472
if unique_lca == NULL_REVISION:
1473
# find_lca will return a plain 'NULL_REVISION' rather
1474
# than a key tuple when there is no common ancestor, we
1475
# prefer to just use None, because it doesn't confuse
1476
# _get_interesting_texts()
1478
parent_map.update(self._find_unique_parents(next_lcas,
1481
cur_ancestors = next_lcas
1484
def _find_unique_parents(self, tip_keys, base_key):
1485
"""Find ancestors of tip that aren't ancestors of base.
1487
:param tip_keys: Nodes that are interesting
1488
:param base_key: Cull all ancestors of this node
1489
:return: The parent map for all revisions between tip_keys and
1490
base_key. base_key will be included. References to nodes outside of
1491
the ancestor set will also be removed.
1493
# TODO: this would be simpler if find_unique_ancestors took a list
1494
# instead of a single tip, internally it supports it, but it
1495
# isn't a "backwards compatible" api change.
1496
if base_key is None:
1497
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1498
# We remove NULL_REVISION because it isn't a proper tuple key, and
1499
# thus confuses things like _get_interesting_texts, and our logic
1500
# to add the texts into the memory weave.
1501
if NULL_REVISION in parent_map:
1502
parent_map.pop(NULL_REVISION)
1505
for tip in tip_keys:
1507
self.graph.find_unique_ancestors(tip, [base_key]))
1508
parent_map = self.graph.get_parent_map(interesting)
1509
parent_map[base_key] = ()
1510
culled_parent_map, child_map, tails = self._remove_external_references(
1512
# Remove all the tails but base_key
1513
if base_key is not None:
1514
tails.remove(base_key)
1515
self._prune_tails(culled_parent_map, child_map, tails)
1516
# Now remove all the uninteresting 'linear' regions
1517
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1521
def _remove_external_references(parent_map):
1522
"""Remove references that go outside of the parent map.
1524
:param parent_map: Something returned from Graph.get_parent_map(keys)
1525
:return: (filtered_parent_map, child_map, tails)
1526
filtered_parent_map is parent_map without external references
1527
child_map is the {parent_key: [child_keys]} mapping
1528
tails is a list of nodes that do not have any parents in the map
1530
# TODO: The basic effect of this function seems more generic than
1531
# _PlanMerge. But the specific details of building a child_map,
1532
# and computing tails seems very specific to _PlanMerge.
1533
# Still, should this be in Graph land?
1534
filtered_parent_map = {}
1537
for key, parent_keys in parent_map.iteritems():
1538
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1539
if not culled_parent_keys:
1541
for parent_key in culled_parent_keys:
1542
child_map.setdefault(parent_key, []).append(key)
1543
# TODO: Do we want to do this, it adds overhead for every node,
1544
# just to say that the node has no children
1545
child_map.setdefault(key, [])
1546
filtered_parent_map[key] = culled_parent_keys
1547
return filtered_parent_map, child_map, tails
1550
def _prune_tails(parent_map, child_map, tails_to_remove):
1551
"""Remove tails from the parent map.
1553
This will remove the supplied revisions until no more children have 0
1556
:param parent_map: A dict of {child: [parents]}, this dictionary will
1557
be modified in place.
1558
:param tails_to_remove: A list of tips that should be removed,
1559
this list will be consumed
1560
:param child_map: The reverse dict of parent_map ({parent: [children]})
1561
this dict will be modified
1562
:return: None, parent_map will be modified in place.
1564
while tails_to_remove:
1565
next = tails_to_remove.pop()
1566
parent_map.pop(next)
1567
children = child_map.pop(next)
1568
for child in children:
1569
child_parents = parent_map[child]
1570
child_parents.remove(next)
1571
if len(child_parents) == 0:
1572
tails_to_remove.append(child)
1574
def _get_interesting_texts(self, parent_map):
1575
"""Return a dict of texts we are interested in.
1577
Note that the input is in key tuples, but the output is in plain
1580
:param parent_map: The output from _find_recursive_lcas
1581
:return: A dict of {'revision_id':lines} as returned by
1582
_PlanMergeBase.get_lines()
1584
all_revision_keys = set(parent_map)
1585
all_revision_keys.add(self.a_key)
1586
all_revision_keys.add(self.b_key)
1588
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1589
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1592
def _build_weave(self):
1593
from bzrlib import weave
1594
self._weave = weave.Weave(weave_name='in_memory_weave',
1595
allow_reserved=True)
1596
parent_map = self._find_recursive_lcas()
1598
all_texts = self._get_interesting_texts(parent_map)
1600
# Note: Unfortunately, the order given by topo_sort will effect the
1601
# ordering resolution in the output. Specifically, if you add A then B,
1602
# then in the output text A lines will show up before B lines. And, of
1603
# course, topo_sort doesn't guarantee any real ordering.
1604
# So we use merge_sort, and add a fake node on the tip.
1605
# This ensures that left-hand parents will always be inserted into the
1606
# weave before right-hand parents.
1607
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1608
parent_map[tip_key] = (self.a_key, self.b_key)
1610
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1614
# for key in tsort.topo_sort(parent_map):
1615
parent_keys = parent_map[key]
1616
revision_id = key[-1]
1617
parent_ids = [k[-1] for k in parent_keys]
1618
self._weave.add_lines(revision_id, parent_ids,
1619
all_texts[revision_id])
1621
def plan_merge(self):
1622
"""Generate a 'plan' for merging the two revisions.
1624
This involves comparing their texts and determining the cause of
1625
differences. If text A has a line and text B does not, then either the
1626
line was added to text A, or it was deleted from B. Once the causes
1627
are combined, they are written out in the format described in
1628
VersionedFile.plan_merge
1630
if self._head_key is not None: # There was a single head
1631
if self._head_key == self.a_key:
1634
if self._head_key != self.b_key:
1635
raise AssertionError('There was an invalid head: %s != %s'
1636
% (self.b_key, self._head_key))
1638
head_rev = self._head_key[-1]
1639
lines = self.get_lines([head_rev])[head_rev]
1640
return ((plan, line) for line in lines)
1641
return self._weave.plan_merge(self.a_rev, self.b_rev)
1644
class _PlanLCAMerge(_PlanMergeBase):
1646
This merge algorithm differs from _PlanMerge in that:
1647
1. comparisons are done against LCAs only
1648
2. cases where a contested line is new versus one LCA but old versus
1649
another are marked as conflicts, by emitting the line as conflicted-a
1652
This is faster, and hopefully produces more useful output.
1655
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
1656
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1657
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1660
if lca == NULL_REVISION:
1663
self.lcas.add(lca[-1])
1664
for lca in self.lcas:
1665
if _mod_revision.is_null(lca):
1668
lca_lines = self.get_lines([lca])[lca]
1669
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1671
blocks = list(matcher.get_matching_blocks())
1672
self._cached_matching_blocks[(a_rev, lca)] = blocks
1673
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1675
blocks = list(matcher.get_matching_blocks())
1676
self._cached_matching_blocks[(b_rev, lca)] = blocks
1678
def _determine_status(self, revision_id, unique_line_numbers):
1679
"""Determines the status unique lines versus all lcas.
1681
Basically, determines why the line is unique to this revision.
1683
A line may be determined new, killed, or both.
1685
If a line is determined new, that means it was not present in at least
1686
one LCA, and is not present in the other merge revision.
1688
If a line is determined killed, that means the line was present in
1691
If a line is killed and new, this indicates that the two merge
1692
revisions contain differing conflict resolutions.
1693
:param revision_id: The id of the revision in which the lines are
1695
:param unique_line_numbers: The line numbers of unique lines.
1696
:return a tuple of (new_this, killed_other):
1700
unique_line_numbers = set(unique_line_numbers)
1701
for lca in self.lcas:
1702
blocks = self._get_matching_blocks(revision_id, lca)
1703
unique_vs_lca, _ignored = self._unique_lines(blocks)
1704
new.update(unique_line_numbers.intersection(unique_vs_lca))
1705
killed.update(unique_line_numbers.difference(unique_vs_lca))
849
merge_types = { "merge3": (Merge3Merger, "Native diff3-style merge"),
850
"diff3": (Diff3Merger, "Merge using external diff3"),
851
'weave': (WeaveMerger, "Weave-based merge")
added
removed
bzrlib/merge.py
