← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Martin Pool
  • Date: 2010-01-29 14:09:05 UTC
  • mto: This revision was merged to the branch mainline in revision 4992.
  • Revision ID: mbp@sourcefrog.net-20100129140905-2uiarb6p8di1ywsr
Correction to url

from review: https://code.edge.launchpad.net/~mbp/bzr/doc/+merge/18250

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
18
 
import errno
19
 
from itertools import chain
20
 
import os
21
 
import warnings
22
 
 
23
18
from bzrlib import (
 
19
    branch as _mod_branch,
 
20
    conflicts as _mod_conflicts,
24
21
    debug,
 
22
    decorators,
25
23
    errors,
26
24
    graph as _mod_graph,
 
25
    hooks,
 
26
    merge3,
27
27
    osutils,
28
28
    patiencediff,
29
 
    registry,
 
29
    progress,
30
30
    revision as _mod_revision,
 
31
    textfile,
 
32
    trace,
 
33
    transform,
31
34
    tree as _mod_tree,
32
35
    tsort,
33
 
    )
34
 
from bzrlib.branch import Branch
35
 
from bzrlib.conflicts import ConflictList, Conflict
36
 
from bzrlib.errors import (BzrCommandError,
37
 
                           BzrError,
38
 
                           NoCommonAncestor,
39
 
                           NoCommits,
40
 
                           NoSuchRevision,
41
 
                           NoSuchFile,
42
 
                           NotBranchError,
43
 
                           NotVersionedError,
44
 
                           UnrelatedBranches,
45
 
                           UnsupportedOperation,
46
 
                           WorkingTreeNotRevision,
47
 
                           BinaryFile,
48
 
                           )
49
 
from bzrlib.graph import Graph
50
 
from bzrlib.merge3 import Merge3
51
 
from bzrlib.osutils import rename, pathjoin
52
 
from progress import DummyProgress, ProgressPhase
53
 
from bzrlib.revision import (NULL_REVISION, ensure_null)
54
 
from bzrlib.textfile import check_text_lines
55
 
from bzrlib.trace import mutter, warning, note, is_quiet
56
 
from bzrlib.transform import (TransformPreview, TreeTransform,
57
 
                              resolve_conflicts, cook_conflicts,
58
 
                              conflict_pass, FinalPaths, create_from_tree,
59
 
                              unique_add, ROOT_PARENT)
60
 
from bzrlib.versionedfile import PlanWeaveMerge
61
 
from bzrlib import ui
62
 
 
 
36
    ui,
 
37
    versionedfile
 
38
    )
 
39
from bzrlib.symbol_versioning import (
 
40
    deprecated_in,
 
41
    deprecated_method,
 
42
    )
63
43
# TODO: Report back as changes are merged in
64
44
 
65
45
 
66
46
def transform_tree(from_tree, to_tree, interesting_ids=None):
67
 
    merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
68
 
                interesting_ids=interesting_ids, this_tree=from_tree)
 
47
    from_tree.lock_tree_write()
 
48
    try:
 
49
        merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
 
50
                    interesting_ids=interesting_ids, this_tree=from_tree)
 
51
    finally:
 
52
        from_tree.unlock()
 
53
 
 
54
 
 
55
class MergeHooks(hooks.Hooks):
 
56
 
 
57
    def __init__(self):
 
58
        hooks.Hooks.__init__(self)
 
59
        self.create_hook(hooks.HookPoint('merge_file_content',
 
60
            "Called when file content needs to be merged (including when one "
 
61
            "side has deleted the file and the other has changed it)."
 
62
            "merge_file_content is called with a "
 
63
            "bzrlib.merge.MergeHookParams. The function should return a tuple "
 
64
            "of (status, lines), where status is one of 'not_applicable', "
 
65
            "'success', 'conflicted', or 'delete'.  If status is success or "
 
66
            "conflicted, then lines should be an iterable of strings of the "
 
67
            "new file contents.",
 
68
            (2, 1), None))
 
69
 
 
70
 
 
71
class MergeHookParams(object):
 
72
    """Object holding parameters passed to merge_file_content hooks.
 
73
 
 
74
    There are 3 fields hooks can access:
 
75
 
 
76
    :ivar merger: the Merger object
 
77
    :ivar file_id: the file ID of the file being merged
 
78
    :ivar trans_id: the transform ID for the merge of this file
 
79
    :ivar this_kind: kind of file_id in 'this' tree
 
80
    :ivar other_kind: kind of file_id in 'other' tree
 
81
    :ivar winner: one of 'this', 'other', 'conflict'
 
82
    """
 
83
 
 
84
    def __init__(self, merger, file_id, trans_id, this_kind, other_kind,
 
85
            winner):
 
86
        self.merger = merger
 
87
        self.file_id = file_id
 
88
        self.trans_id = trans_id
 
89
        self.this_kind = this_kind
 
90
        self.other_kind = other_kind
 
91
        self.winner = winner
 
92
 
 
93
    def is_file_merge(self):
 
94
        """True if this_kind and other_kind are both 'file'."""
 
95
        return self.this_kind == 'file' and self.other_kind == 'file'
 
96
 
 
97
    @decorators.cachedproperty
 
98
    def base_lines(self):
 
99
        """The lines of the 'base' version of the file."""
 
100
        return self.merger.get_lines(self.merger.base_tree, self.file_id)
 
101
 
 
102
    @decorators.cachedproperty
 
103
    def this_lines(self):
 
104
        """The lines of the 'this' version of the file."""
 
105
        return self.merger.get_lines(self.merger.this_tree, self.file_id)
 
106
 
 
107
    @decorators.cachedproperty
 
108
    def other_lines(self):
 
109
        """The lines of the 'other' version of the file."""
 
110
        return self.merger.get_lines(self.merger.other_tree, self.file_id)
69
111
 
70
112
 
71
113
class Merger(object):
 
114
 
 
115
    hooks = MergeHooks()
 
116
 
72
117
    def __init__(self, this_branch, other_tree=None, base_tree=None,
73
118
                 this_tree=None, pb=None, change_reporter=None,
74
119
                 recurse='down', revision_graph=None):
90
135
        self.show_base = False
91
136
        self.reprocess = False
92
137
        if pb is None:
93
 
            pb = DummyProgress()
 
138
            pb = progress.DummyProgress()
94
139
        self._pb = pb
95
140
        self.pp = None
96
141
        self.recurse = recurse
102
147
        self._is_criss_cross = None
103
148
        self._lca_trees = None
104
149
 
 
150
    def cache_trees_with_revision_ids(self, trees):
 
151
        """Cache any tree in trees if it has a revision_id."""
 
152
        for maybe_tree in trees:
 
153
            if maybe_tree is None:
 
154
                continue
 
155
            try:
 
156
                rev_id = maybe_tree.get_revision_id()
 
157
            except AttributeError:
 
158
                continue
 
159
            self._cached_trees[rev_id] = maybe_tree
 
160
 
105
161
    @property
106
162
    def revision_graph(self):
107
163
        if self._revision_graph is None:
169
225
                base_revision_id, tree.branch.last_revision())):
170
226
                base_revision_id = None
171
227
            else:
172
 
                warning('Performing cherrypick')
 
228
                trace.warning('Performing cherrypick')
173
229
        merger = klass.from_revision_ids(pb, tree, other_revision_id,
174
230
                                         base_revision_id, revision_graph=
175
231
                                         revision_graph)
227
283
        if revno is None:
228
284
            tree = workingtree.WorkingTree.open_containing(location)[0]
229
285
            return tree.branch, tree
230
 
        branch = Branch.open_containing(location, possible_transports)[0]
 
286
        branch = _mod_branch.Branch.open_containing(
 
287
            location, possible_transports)[0]
231
288
        if revno == -1:
232
289
            revision_id = branch.last_revision()
233
290
        else:
234
291
            revision_id = branch.get_rev_id(revno)
235
 
        revision_id = ensure_null(revision_id)
 
292
        revision_id = _mod_revision.ensure_null(revision_id)
236
293
        return branch, self.revision_tree(revision_id, branch)
237
294
 
 
295
    @deprecated_method(deprecated_in((2, 1, 0)))
238
296
    def ensure_revision_trees(self):
239
297
        if self.this_revision_tree is None:
240
298
            self.this_basis_tree = self.revision_tree(self.this_basis)
244
302
        if self.other_rev_id is None:
245
303
            other_basis_tree = self.revision_tree(self.other_basis)
246
304
            if other_basis_tree.has_changes(self.other_tree):
247
 
                raise WorkingTreeNotRevision(self.this_tree)
 
305
                raise errors.WorkingTreeNotRevision(self.this_tree)
248
306
            other_rev_id = self.other_basis
249
307
            self.other_tree = other_basis_tree
250
308
 
 
309
    @deprecated_method(deprecated_in((2, 1, 0)))
251
310
    def file_revisions(self, file_id):
252
311
        self.ensure_revision_trees()
253
312
        def get_id(tree, file_id):
256
315
        if self.this_rev_id is None:
257
316
            if self.this_basis_tree.get_file_sha1(file_id) != \
258
317
                self.this_tree.get_file_sha1(file_id):
259
 
                raise WorkingTreeNotRevision(self.this_tree)
 
318
                raise errors.WorkingTreeNotRevision(self.this_tree)
260
319
 
261
320
        trees = (self.this_basis_tree, self.other_tree)
262
321
        return [get_id(tree, file_id) for tree in trees]
263
322
 
 
323
    @deprecated_method(deprecated_in((2, 1, 0)))
264
324
    def check_basis(self, check_clean, require_commits=True):
265
325
        if self.this_basis is None and require_commits is True:
266
 
            raise BzrCommandError("This branch has no commits."
267
 
                                  " (perhaps you would prefer 'bzr pull')")
 
326
            raise errors.BzrCommandError(
 
327
                "This branch has no commits."
 
328
                " (perhaps you would prefer 'bzr pull')")
268
329
        if check_clean:
269
330
            self.compare_basis()
270
331
            if self.this_basis != self.this_rev_id:
271
332
                raise errors.UncommittedChanges(self.this_tree)
272
333
 
 
334
    @deprecated_method(deprecated_in((2, 1, 0)))
273
335
    def compare_basis(self):
274
336
        try:
275
337
            basis_tree = self.revision_tree(self.this_tree.last_revision())
282
344
        self.interesting_files = file_list
283
345
 
284
346
    def set_pending(self):
285
 
        if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
 
347
        if (not self.base_is_ancestor or not self.base_is_other_ancestor
 
348
            or self.other_rev_id is None):
286
349
            return
287
350
        self._add_parent()
288
351
 
318
381
            self.other_rev_id = _mod_revision.ensure_null(
319
382
                self.other_branch.last_revision())
320
383
            if _mod_revision.is_null(self.other_rev_id):
321
 
                raise NoCommits(self.other_branch)
 
384
                raise errors.NoCommits(self.other_branch)
322
385
            self.other_basis = self.other_rev_id
323
386
        elif other_revision[1] is not None:
324
387
            self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
327
390
            self.other_rev_id = None
328
391
            self.other_basis = self.other_branch.last_revision()
329
392
            if self.other_basis is None:
330
 
                raise NoCommits(self.other_branch)
 
393
                raise errors.NoCommits(self.other_branch)
331
394
        if self.other_rev_id is not None:
332
395
            self._cached_trees[self.other_rev_id] = self.other_tree
333
396
        self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
360
423
            target.fetch(source, revision_id)
361
424
 
362
425
    def find_base(self):
363
 
        revisions = [ensure_null(self.this_basis),
364
 
                     ensure_null(self.other_basis)]
365
 
        if NULL_REVISION in revisions:
366
 
            self.base_rev_id = NULL_REVISION
 
426
        revisions = [_mod_revision.ensure_null(self.this_basis),
 
427
                     _mod_revision.ensure_null(self.other_basis)]
 
428
        if _mod_revision.NULL_REVISION in revisions:
 
429
            self.base_rev_id = _mod_revision.NULL_REVISION
367
430
            self.base_tree = self.revision_tree(self.base_rev_id)
368
431
            self._is_criss_cross = False
369
432
        else:
370
433
            lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
371
434
            self._is_criss_cross = False
372
435
            if len(lcas) == 0:
373
 
                self.base_rev_id = NULL_REVISION
 
436
                self.base_rev_id = _mod_revision.NULL_REVISION
374
437
            elif len(lcas) == 1:
375
438
                self.base_rev_id = list(lcas)[0]
376
439
            else: # len(lcas) > 1
385
448
                    self.base_rev_id = self.revision_graph.find_unique_lca(
386
449
                                            *lcas)
387
450
                self._is_criss_cross = True
388
 
            if self.base_rev_id == NULL_REVISION:
389
 
                raise UnrelatedBranches()
 
451
            if self.base_rev_id == _mod_revision.NULL_REVISION:
 
452
                raise errors.UnrelatedBranches()
390
453
            if self._is_criss_cross:
391
 
                warning('Warning: criss-cross merge encountered.  See bzr'
392
 
                        ' help criss-cross.')
393
 
                mutter('Criss-cross lcas: %r' % lcas)
 
454
                trace.warning('Warning: criss-cross merge encountered.  See bzr'
 
455
                              ' help criss-cross.')
 
456
                trace.mutter('Criss-cross lcas: %r' % lcas)
394
457
                interesting_revision_ids = [self.base_rev_id]
395
458
                interesting_revision_ids.extend(lcas)
396
459
                interesting_trees = dict((t.get_revision_id(), t)
406
469
                self.base_tree = self.revision_tree(self.base_rev_id)
407
470
        self.base_is_ancestor = True
408
471
        self.base_is_other_ancestor = True
409
 
        mutter('Base revid: %r' % self.base_rev_id)
 
472
        trace.mutter('Base revid: %r' % self.base_rev_id)
410
473
 
411
474
    def set_base(self, base_revision):
412
475
        """Set the base revision to use for the merge.
413
476
 
414
477
        :param base_revision: A 2-list containing a path and revision number.
415
478
        """
416
 
        mutter("doing merge() with no base_revision specified")
 
479
        trace.mutter("doing merge() with no base_revision specified")
417
480
        if base_revision == [None, None]:
418
481
            self.find_base()
419
482
        else:
432
495
                  'other_tree': self.other_tree,
433
496
                  'interesting_ids': self.interesting_ids,
434
497
                  'interesting_files': self.interesting_files,
435
 
                  'pp': self.pp,
 
498
                  'pp': self.pp, 'this_branch': self.this_branch,
436
499
                  'do_merge': False}
437
500
        if self.merge_type.requires_base:
438
501
            kwargs['base_tree'] = self.base_tree
439
502
        if self.merge_type.supports_reprocess:
440
503
            kwargs['reprocess'] = self.reprocess
441
504
        elif self.reprocess:
442
 
            raise BzrError("Conflict reduction is not supported for merge"
443
 
                                  " type %s." % self.merge_type)
 
505
            raise errors.BzrError(
 
506
                "Conflict reduction is not supported for merge"
 
507
                " type %s." % self.merge_type)
444
508
        if self.merge_type.supports_show_base:
445
509
            kwargs['show_base'] = self.show_base
446
510
        elif self.show_base:
447
 
            raise BzrError("Showing base is not supported for this"
448
 
                           " merge type. %s" % self.merge_type)
 
511
            raise errors.BzrError("Showing base is not supported for this"
 
512
                                  " merge type. %s" % self.merge_type)
449
513
        if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
450
514
            and not self.base_is_other_ancestor):
451
515
            raise errors.CannotReverseCherrypick()
500
564
        finally:
501
565
            self.this_tree.unlock()
502
566
        if len(merge.cooked_conflicts) == 0:
503
 
            if not self.ignore_zero and not is_quiet():
504
 
                note("All changes applied successfully.")
 
567
            if not self.ignore_zero and not trace.is_quiet():
 
568
                trace.note("All changes applied successfully.")
505
569
        else:
506
 
            note("%d conflicts encountered." % len(merge.cooked_conflicts))
 
570
            trace.note("%d conflicts encountered."
 
571
                       % len(merge.cooked_conflicts))
507
572
 
508
573
        return len(merge.cooked_conflicts)
509
574
 
538
603
 
539
604
    def __init__(self, working_tree, this_tree, base_tree, other_tree,
540
605
                 interesting_ids=None, reprocess=False, show_base=False,
541
 
                 pb=DummyProgress(), pp=None, change_reporter=None,
 
606
                 pb=progress.DummyProgress(), pp=None, change_reporter=None,
542
607
                 interesting_files=None, do_merge=True,
543
 
                 cherrypick=False, lca_trees=None):
 
608
                 cherrypick=False, lca_trees=None, this_branch=None):
544
609
        """Initialize the merger object and perform the merge.
545
610
 
546
611
        :param working_tree: The working tree to apply the merge to
547
612
        :param this_tree: The local tree in the merge operation
548
613
        :param base_tree: The common tree in the merge operation
549
614
        :param other_tree: The other tree to merge changes from
 
615
        :param this_branch: The branch associated with this_tree
550
616
        :param interesting_ids: The file_ids of files that should be
551
617
            participate in the merge.  May not be combined with
552
618
            interesting_files.
575
641
        self.this_tree = working_tree
576
642
        self.base_tree = base_tree
577
643
        self.other_tree = other_tree
 
644
        self.this_branch = this_branch
578
645
        self._raw_conflicts = []
579
646
        self.cooked_conflicts = []
580
647
        self.reprocess = reprocess
590
657
        self.change_reporter = change_reporter
591
658
        self.cherrypick = cherrypick
592
659
        if self.pp is None:
593
 
            self.pp = ProgressPhase("Merge phase", 3, self.pb)
 
660
            self.pp = progress.ProgressPhase("Merge phase", 3, self.pb)
594
661
        if do_merge:
595
662
            self.do_merge()
596
663
 
598
665
        self.this_tree.lock_tree_write()
599
666
        self.base_tree.lock_read()
600
667
        self.other_tree.lock_read()
601
 
        self.tt = TreeTransform(self.this_tree, self.pb)
602
668
        try:
603
 
            self.pp.next_phase()
604
 
            self._compute_transform()
605
 
            self.pp.next_phase()
606
 
            results = self.tt.apply(no_conflicts=True)
607
 
            self.write_modified(results)
 
669
            self.tt = transform.TreeTransform(self.this_tree, self.pb)
608
670
            try:
609
 
                self.this_tree.add_conflicts(self.cooked_conflicts)
610
 
            except UnsupportedOperation:
611
 
                pass
 
671
                self.pp.next_phase()
 
672
                self._compute_transform()
 
673
                self.pp.next_phase()
 
674
                results = self.tt.apply(no_conflicts=True)
 
675
                self.write_modified(results)
 
676
                try:
 
677
                    self.this_tree.add_conflicts(self.cooked_conflicts)
 
678
                except errors.UnsupportedOperation:
 
679
                    pass
 
680
            finally:
 
681
                self.tt.finalize()
612
682
        finally:
613
 
            self.tt.finalize()
614
683
            self.other_tree.unlock()
615
684
            self.base_tree.unlock()
616
685
            self.this_tree.unlock()
619
688
    def make_preview_transform(self):
620
689
        self.base_tree.lock_read()
621
690
        self.other_tree.lock_read()
622
 
        self.tt = TransformPreview(self.this_tree)
 
691
        self.tt = transform.TransformPreview(self.this_tree)
623
692
        try:
624
693
            self.pp.next_phase()
625
694
            self._compute_transform()
655
724
        self.pp.next_phase()
656
725
        child_pb = ui.ui_factory.nested_progress_bar()
657
726
        try:
658
 
            fs_conflicts = resolve_conflicts(self.tt, child_pb,
659
 
                lambda t, c: conflict_pass(t, c, self.other_tree))
 
727
            fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,
 
728
                lambda t, c: transform.conflict_pass(t, c, self.other_tree))
660
729
        finally:
661
730
            child_pb.finished()
662
731
        if self.change_reporter is not None:
665
734
                self.tt.iter_changes(), self.change_reporter)
666
735
        self.cook_conflicts(fs_conflicts)
667
736
        for conflict in self.cooked_conflicts:
668
 
            warning(conflict)
 
737
            trace.warning(conflict)
669
738
 
670
739
    def _entries3(self):
671
740
        """Gather data about files modified between three trees.
873
942
    def fix_root(self):
874
943
        try:
875
944
            self.tt.final_kind(self.tt.root)
876
 
        except NoSuchFile:
 
945
        except errors.NoSuchFile:
877
946
            self.tt.cancel_deletion(self.tt.root)
878
947
        if self.tt.final_file_id(self.tt.root) is None:
879
948
            self.tt.version_file(self.tt.tree_file_id(self.tt.root),
886
955
            return
887
956
        try:
888
957
            self.tt.final_kind(other_root)
889
 
        except NoSuchFile:
 
958
        except errors.NoSuchFile:
890
959
            return
891
 
        if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
 
960
        if self.this_tree.has_id(self.other_tree.inventory.root.file_id):
892
961
            # the other tree's root is a non-root in the current tree
893
962
            return
894
963
        self.reparent_children(self.other_tree.inventory.root, self.tt.root)
936
1005
    @staticmethod
937
1006
    def executable(tree, file_id):
938
1007
        """Determine the executability of a file-id (used as a key method)."""
939
 
        if file_id not in tree:
 
1008
        if not tree.has_id(file_id):
940
1009
            return None
941
1010
        if tree.kind(file_id) != "file":
942
1011
            return False
945
1014
    @staticmethod
946
1015
    def kind(tree, file_id):
947
1016
        """Determine the kind of a file-id (used as a key method)."""
948
 
        if file_id not in tree:
 
1017
        if not tree.has_id(file_id):
949
1018
            return None
950
1019
        return tree.kind(file_id)
951
1020
 
1034
1103
 
1035
1104
    def merge_names(self, file_id):
1036
1105
        def get_entry(tree):
1037
 
            if file_id in tree.inventory:
 
1106
            if tree.has_id(file_id):
1038
1107
                return tree.inventory[file_id]
1039
1108
            else:
1040
1109
                return None
1103
1172
                contents = None
1104
1173
            return kind, contents
1105
1174
 
1106
 
        def contents_conflict():
1107
 
            trans_id = self.tt.trans_id_file_id(file_id)
1108
 
            name = self.tt.final_name(trans_id)
1109
 
            parent_id = self.tt.final_parent(trans_id)
1110
 
            if file_id in self.this_tree.inventory:
1111
 
                self.tt.unversion_file(trans_id)
1112
 
                if file_id in self.this_tree:
1113
 
                    self.tt.delete_contents(trans_id)
1114
 
            file_group = self._dump_conflicts(name, parent_id, file_id,
1115
 
                                              set_version=True)
1116
 
            self._raw_conflicts.append(('contents conflict', file_group))
1117
 
 
1118
1175
        # See SPOT run.  run, SPOT, run.
1119
1176
        # So we're not QUITE repeating ourselves; we do tricky things with
1120
1177
        # file kind...
1136
1193
        if winner == 'this':
1137
1194
            # No interesting changes introduced by OTHER
1138
1195
            return "unmodified"
 
1196
        # We have a hypothetical conflict, but if we have files, then we
 
1197
        # can try to merge the content
1139
1198
        trans_id = self.tt.trans_id_file_id(file_id)
1140
 
        if winner == 'other':
 
1199
        params = MergeHookParams(self, file_id, trans_id, this_pair[0],
 
1200
            other_pair[0], winner)
 
1201
        hooks = Merger.hooks['merge_file_content']
 
1202
        hooks = list(hooks) + [self.default_text_merge]
 
1203
        hook_status = 'not_applicable'
 
1204
        for hook in hooks:
 
1205
            hook_status, lines = hook(params)
 
1206
            if hook_status != 'not_applicable':
 
1207
                # Don't try any more hooks, this one applies.
 
1208
                break
 
1209
        result = "modified"
 
1210
        if hook_status == 'not_applicable':
 
1211
            # This is a contents conflict, because none of the available
 
1212
            # functions could merge it.
 
1213
            result = None
 
1214
            name = self.tt.final_name(trans_id)
 
1215
            parent_id = self.tt.final_parent(trans_id)
 
1216
            if self.this_tree.has_id(file_id):
 
1217
                self.tt.unversion_file(trans_id)
 
1218
            file_group = self._dump_conflicts(name, parent_id, file_id,
 
1219
                                              set_version=True)
 
1220
            self._raw_conflicts.append(('contents conflict', file_group))
 
1221
        elif hook_status == 'success':
 
1222
            self.tt.create_file(lines, trans_id)
 
1223
        elif hook_status == 'conflicted':
 
1224
            # XXX: perhaps the hook should be able to provide
 
1225
            # the BASE/THIS/OTHER files?
 
1226
            self.tt.create_file(lines, trans_id)
 
1227
            self._raw_conflicts.append(('text conflict', trans_id))
 
1228
            name = self.tt.final_name(trans_id)
 
1229
            parent_id = self.tt.final_parent(trans_id)
 
1230
            self._dump_conflicts(name, parent_id, file_id)
 
1231
        elif hook_status == 'delete':
 
1232
            self.tt.unversion_file(trans_id)
 
1233
            result = "deleted"
 
1234
        elif hook_status == 'done':
 
1235
            # The hook function did whatever it needs to do directly, no
 
1236
            # further action needed here.
 
1237
            pass
 
1238
        else:
 
1239
            raise AssertionError('unknown hook_status: %r' % (hook_status,))
 
1240
        if not self.this_tree.has_id(file_id) and result == "modified":
 
1241
            self.tt.version_file(file_id, trans_id)
 
1242
        # The merge has been performed, so the old contents should not be
 
1243
        # retained.
 
1244
        try:
 
1245
            self.tt.delete_contents(trans_id)
 
1246
        except errors.NoSuchFile:
 
1247
            pass
 
1248
        return result
 
1249
 
 
1250
    def _default_other_winner_merge(self, merge_hook_params):
 
1251
        """Replace this contents with other."""
 
1252
        file_id = merge_hook_params.file_id
 
1253
        trans_id = merge_hook_params.trans_id
 
1254
        file_in_this = self.this_tree.has_id(file_id)
 
1255
        if self.other_tree.has_id(file_id):
 
1256
            # OTHER changed the file
 
1257
            wt = self.this_tree
 
1258
            if wt.supports_content_filtering():
 
1259
                # We get the path from the working tree if it exists.
 
1260
                # That fails though when OTHER is adding a file, so
 
1261
                # we fall back to the other tree to find the path if
 
1262
                # it doesn't exist locally.
 
1263
                try:
 
1264
                    filter_tree_path = wt.id2path(file_id)
 
1265
                except errors.NoSuchId:
 
1266
                    filter_tree_path = self.other_tree.id2path(file_id)
 
1267
            else:
 
1268
                # Skip the id2path lookup for older formats
 
1269
                filter_tree_path = None
 
1270
            transform.create_from_tree(self.tt, trans_id,
 
1271
                             self.other_tree, file_id,
 
1272
                             filter_tree_path=filter_tree_path)
 
1273
            return 'done', None
 
1274
        elif file_in_this:
 
1275
            # OTHER deleted the file
 
1276
            return 'delete', None
 
1277
        else:
 
1278
            raise AssertionError(
 
1279
                'winner is OTHER, but file_id %r not in THIS or OTHER tree'
 
1280
                % (file_id,))
 
1281
 
 
1282
    def default_text_merge(self, merge_hook_params):
 
1283
        if merge_hook_params.winner == 'other':
1141
1284
            # OTHER is a straight winner, so replace this contents with other
1142
 
            file_in_this = file_id in self.this_tree
1143
 
            if file_in_this:
1144
 
                # Remove any existing contents
1145
 
                self.tt.delete_contents(trans_id)
1146
 
            if file_id in self.other_tree:
1147
 
                # OTHER changed the file
1148
 
                create_from_tree(self.tt, trans_id,
1149
 
                                 self.other_tree, file_id)
1150
 
                if not file_in_this:
1151
 
                    self.tt.version_file(file_id, trans_id)
1152
 
                return "modified"
1153
 
            elif file_in_this:
1154
 
                # OTHER deleted the file
1155
 
                self.tt.unversion_file(trans_id)
1156
 
                return "deleted"
 
1285
            return self._default_other_winner_merge(merge_hook_params)
 
1286
        elif merge_hook_params.is_file_merge():
 
1287
            # THIS and OTHER are both files, so text merge.  Either
 
1288
            # BASE is a file, or both converted to files, so at least we
 
1289
            # have agreement that output should be a file.
 
1290
            try:
 
1291
                self.text_merge(merge_hook_params.file_id,
 
1292
                    merge_hook_params.trans_id)
 
1293
            except errors.BinaryFile:
 
1294
                return 'not_applicable', None
 
1295
            return 'done', None
1157
1296
        else:
1158
 
            # We have a hypothetical conflict, but if we have files, then we
1159
 
            # can try to merge the content
1160
 
            if this_pair[0] == 'file' and other_pair[0] == 'file':
1161
 
                # THIS and OTHER are both files, so text merge.  Either
1162
 
                # BASE is a file, or both converted to files, so at least we
1163
 
                # have agreement that output should be a file.
1164
 
                try:
1165
 
                    self.text_merge(file_id, trans_id)
1166
 
                except BinaryFile:
1167
 
                    return contents_conflict()
1168
 
                if file_id not in self.this_tree:
1169
 
                    self.tt.version_file(file_id, trans_id)
1170
 
                try:
1171
 
                    self.tt.tree_kind(trans_id)
1172
 
                    self.tt.delete_contents(trans_id)
1173
 
                except NoSuchFile:
1174
 
                    pass
1175
 
                return "modified"
1176
 
            else:
1177
 
                return contents_conflict()
 
1297
            return 'not_applicable', None
1178
1298
 
1179
1299
    def get_lines(self, tree, file_id):
1180
1300
        """Return the lines in a file, or an empty list."""
1181
 
        if file_id in tree:
 
1301
        if tree.has_id(file_id):
1182
1302
            return tree.get_file(file_id).readlines()
1183
1303
        else:
1184
1304
            return []
1187
1307
        """Perform a three-way text merge on a file_id"""
1188
1308
        # it's possible that we got here with base as a different type.
1189
1309
        # if so, we just want two-way text conflicts.
1190
 
        if file_id in self.base_tree and \
 
1310
        if self.base_tree.has_id(file_id) and \
1191
1311
            self.base_tree.kind(file_id) == "file":
1192
1312
            base_lines = self.get_lines(self.base_tree, file_id)
1193
1313
        else:
1194
1314
            base_lines = []
1195
1315
        other_lines = self.get_lines(self.other_tree, file_id)
1196
1316
        this_lines = self.get_lines(self.this_tree, file_id)
1197
 
        m3 = Merge3(base_lines, this_lines, other_lines,
1198
 
                    is_cherrypick=self.cherrypick)
 
1317
        m3 = merge3.Merge3(base_lines, this_lines, other_lines,
 
1318
                           is_cherrypick=self.cherrypick)
1199
1319
        start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1200
1320
        if self.show_base is True:
1201
1321
            base_marker = '|' * 7
1239
1359
                ('THIS', self.this_tree, this_lines)]
1240
1360
        if not no_base:
1241
1361
            data.append(('BASE', self.base_tree, base_lines))
 
1362
 
 
1363
        # We need to use the actual path in the working tree of the file here,
 
1364
        # ignoring the conflict suffixes
 
1365
        wt = self.this_tree
 
1366
        if wt.supports_content_filtering():
 
1367
            try:
 
1368
                filter_tree_path = wt.id2path(file_id)
 
1369
            except errors.NoSuchId:
 
1370
                # file has been deleted
 
1371
                filter_tree_path = None
 
1372
        else:
 
1373
            # Skip the id2path lookup for older formats
 
1374
            filter_tree_path = None
 
1375
 
1242
1376
        versioned = False
1243
1377
        file_group = []
1244
1378
        for suffix, tree, lines in data:
1245
 
            if file_id in tree:
 
1379
            if tree.has_id(file_id):
1246
1380
                trans_id = self._conflict_file(name, parent_id, tree, file_id,
1247
 
                                               suffix, lines)
 
1381
                                               suffix, lines, filter_tree_path)
1248
1382
                file_group.append(trans_id)
1249
1383
                if set_version and not versioned:
1250
1384
                    self.tt.version_file(file_id, trans_id)
1252
1386
        return file_group
1253
1387
 
1254
1388
    def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1255
 
                       lines=None):
 
1389
                       lines=None, filter_tree_path=None):
1256
1390
        """Emit a single conflict file."""
1257
1391
        name = name + '.' + suffix
1258
1392
        trans_id = self.tt.create_path(name, parent_id)
1259
 
        create_from_tree(self.tt, trans_id, tree, file_id, lines)
 
1393
        transform.create_from_tree(self.tt, trans_id, tree, file_id, lines,
 
1394
            filter_tree_path)
1260
1395
        return trans_id
1261
1396
 
1262
1397
    def merge_executable(self, file_id, file_status):
1286
1421
        try:
1287
1422
            if self.tt.final_kind(trans_id) != "file":
1288
1423
                return
1289
 
        except NoSuchFile:
 
1424
        except errors.NoSuchFile:
1290
1425
            return
1291
1426
        if winner == "this":
1292
1427
            executability = this_executable
1293
1428
        else:
1294
 
            if file_id in self.other_tree:
 
1429
            if self.other_tree.has_id(file_id):
1295
1430
                executability = other_executable
1296
 
            elif file_id in self.this_tree:
 
1431
            elif self.this_tree.has_id(file_id):
1297
1432
                executability = this_executable
1298
 
            elif file_id in self.base_tree:
 
1433
            elif self.base_tree_has_id(file_id):
1299
1434
                executability = base_executable
1300
1435
        if executability is not None:
1301
1436
            trans_id = self.tt.trans_id_file_id(file_id)
1303
1438
 
1304
1439
    def cook_conflicts(self, fs_conflicts):
1305
1440
        """Convert all conflicts into a form that doesn't depend on trans_id"""
1306
 
        from conflicts import Conflict
1307
1441
        name_conflicts = {}
1308
 
        self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
1309
 
        fp = FinalPaths(self.tt)
 
1442
        self.cooked_conflicts.extend(transform.cook_conflicts(
 
1443
                fs_conflicts, self.tt))
 
1444
        fp = transform.FinalPaths(self.tt)
1310
1445
        for conflict in self._raw_conflicts:
1311
1446
            conflict_type = conflict[0]
1312
1447
            if conflict_type in ('name conflict', 'parent conflict'):
1314
1449
                conflict_args = conflict[2:]
1315
1450
                if trans_id not in name_conflicts:
1316
1451
                    name_conflicts[trans_id] = {}
1317
 
                unique_add(name_conflicts[trans_id], conflict_type,
1318
 
                           conflict_args)
 
1452
                transform.unique_add(name_conflicts[trans_id], conflict_type,
 
1453
                                     conflict_args)
1319
1454
            if conflict_type == 'contents conflict':
1320
1455
                for trans_id in conflict[1]:
1321
1456
                    file_id = self.tt.final_file_id(trans_id)
1326
1461
                    if path.endswith(suffix):
1327
1462
                        path = path[:-len(suffix)]
1328
1463
                        break
1329
 
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
1464
                c = _mod_conflicts.Conflict.factory(conflict_type,
 
1465
                                                    path=path, file_id=file_id)
1330
1466
                self.cooked_conflicts.append(c)
1331
1467
            if conflict_type == 'text conflict':
1332
1468
                trans_id = conflict[1]
1333
1469
                path = fp.get_path(trans_id)
1334
1470
                file_id = self.tt.final_file_id(trans_id)
1335
 
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
1471
                c = _mod_conflicts.Conflict.factory(conflict_type,
 
1472
                                                    path=path, file_id=file_id)
1336
1473
                self.cooked_conflicts.append(c)
1337
1474
 
1338
1475
        for trans_id, conflicts in name_conflicts.iteritems():
1353
1490
            if this_parent is not None and this_name is not None:
1354
1491
                this_parent_path = \
1355
1492
                    fp.get_path(self.tt.trans_id_file_id(this_parent))
1356
 
                this_path = pathjoin(this_parent_path, this_name)
 
1493
                this_path = osutils.pathjoin(this_parent_path, this_name)
1357
1494
            else:
1358
1495
                this_path = "<deleted>"
1359
1496
            file_id = self.tt.final_file_id(trans_id)
1360
 
            c = Conflict.factory('path conflict', path=this_path,
1361
 
                                 conflict_path=other_path, file_id=file_id)
 
1497
            c = _mod_conflicts.Conflict.factory('path conflict', path=this_path,
 
1498
                                                conflict_path=other_path,
 
1499
                                                file_id=file_id)
1362
1500
            self.cooked_conflicts.append(c)
1363
 
        self.cooked_conflicts.sort(key=Conflict.sort_key)
 
1501
        self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)
1364
1502
 
1365
1503
 
1366
1504
class WeaveMerger(Merge3Merger):
1370
1508
    supports_reverse_cherrypick = False
1371
1509
    history_based = True
1372
1510
 
1373
 
    def _merged_lines(self, file_id):
1374
 
        """Generate the merged lines.
1375
 
        There is no distinction between lines that are meant to contain <<<<<<<
1376
 
        and conflicts.
1377
 
        """
1378
 
        if self.cherrypick:
1379
 
            base = self.base_tree
1380
 
        else:
1381
 
            base = None
1382
 
        plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
 
1511
    def _generate_merge_plan(self, file_id, base):
 
1512
        return self.this_tree.plan_file_merge(file_id, self.other_tree,
1383
1513
                                              base=base)
 
1514
 
 
1515
    def _merged_lines(self, file_id):
 
1516
        """Generate the merged lines.
 
1517
        There is no distinction between lines that are meant to contain <<<<<<<
 
1518
        and conflicts.
 
1519
        """
 
1520
        if self.cherrypick:
 
1521
            base = self.base_tree
 
1522
        else:
 
1523
            base = None
 
1524
        plan = self._generate_merge_plan(file_id, base)
1384
1525
        if 'merge' in debug.debug_flags:
1385
1526
            plan = list(plan)
1386
1527
            trans_id = self.tt.trans_id_file_id(file_id)
1387
1528
            name = self.tt.final_name(trans_id) + '.plan'
1388
 
            contents = ('%10s|%s' % l for l in plan)
 
1529
            contents = ('%11s|%s' % l for l in plan)
1389
1530
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1390
 
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1391
 
            '>>>>>>> MERGE-SOURCE\n')
1392
 
        return textmerge.merge_lines(self.reprocess)
 
1531
        textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',
 
1532
                                                 '>>>>>>> MERGE-SOURCE\n')
 
1533
        lines, conflicts = textmerge.merge_lines(self.reprocess)
 
1534
        if conflicts:
 
1535
            base_lines = textmerge.base_from_plan()
 
1536
        else:
 
1537
            base_lines = None
 
1538
        return lines, base_lines
1393
1539
 
1394
1540
    def text_merge(self, file_id, trans_id):
1395
1541
        """Perform a (weave) text merge for a given file and file-id.
1396
1542
        If conflicts are encountered, .THIS and .OTHER files will be emitted,
1397
1543
        and a conflict will be noted.
1398
1544
        """
1399
 
        lines, conflicts = self._merged_lines(file_id)
 
1545
        lines, base_lines = self._merged_lines(file_id)
1400
1546
        lines = list(lines)
1401
1547
        # Note we're checking whether the OUTPUT is binary in this case,
1402
1548
        # because we don't want to get into weave merge guts.
1403
 
        check_text_lines(lines)
 
1549
        textfile.check_text_lines(lines)
1404
1550
        self.tt.create_file(lines, trans_id)
1405
 
        if conflicts:
 
1551
        if base_lines is not None:
 
1552
            # Conflict
1406
1553
            self._raw_conflicts.append(('text conflict', trans_id))
1407
1554
            name = self.tt.final_name(trans_id)
1408
1555
            parent_id = self.tt.final_parent(trans_id)
1409
1556
            file_group = self._dump_conflicts(name, parent_id, file_id,
1410
 
                                              no_base=True)
 
1557
                                              no_base=False,
 
1558
                                              base_lines=base_lines)
1411
1559
            file_group.append(trans_id)
1412
1560
 
1413
1561
 
1414
1562
class LCAMerger(WeaveMerger):
1415
1563
 
1416
 
    def _merged_lines(self, file_id):
1417
 
        """Generate the merged lines.
1418
 
        There is no distinction between lines that are meant to contain <<<<<<<
1419
 
        and conflicts.
1420
 
        """
1421
 
        if self.cherrypick:
1422
 
            base = self.base_tree
1423
 
        else:
1424
 
            base = None
1425
 
        plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
 
1564
    def _generate_merge_plan(self, file_id, base):
 
1565
        return self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1426
1566
                                                  base=base)
1427
 
        if 'merge' in debug.debug_flags:
1428
 
            plan = list(plan)
1429
 
            trans_id = self.tt.trans_id_file_id(file_id)
1430
 
            name = self.tt.final_name(trans_id) + '.plan'
1431
 
            contents = ('%10s|%s' % l for l in plan)
1432
 
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1433
 
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1434
 
            '>>>>>>> MERGE-SOURCE\n')
1435
 
        return textmerge.merge_lines(self.reprocess)
1436
 
 
1437
1567
 
1438
1568
class Diff3Merger(Merge3Merger):
1439
1569
    """Three-way merger using external diff3 for text merging"""
1440
1570
 
1441
1571
    def dump_file(self, temp_dir, name, tree, file_id):
1442
 
        out_path = pathjoin(temp_dir, name)
 
1572
        out_path = osutils.pathjoin(temp_dir, name)
1443
1573
        out_file = open(out_path, "wb")
1444
1574
        try:
1445
1575
            in_file = tree.get_file(file_id)
1457
1587
        import bzrlib.patch
1458
1588
        temp_dir = osutils.mkdtemp(prefix="bzr-")
1459
1589
        try:
1460
 
            new_file = pathjoin(temp_dir, "new")
 
1590
            new_file = osutils.pathjoin(temp_dir, "new")
1461
1591
            this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1462
1592
            base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1463
1593
            other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1464
1594
            status = bzrlib.patch.diff3(new_file, this, base, other)
1465
1595
            if status not in (0, 1):
1466
 
                raise BzrError("Unhandled diff3 exit code")
 
1596
                raise errors.BzrError("Unhandled diff3 exit code")
1467
1597
            f = open(new_file, 'rb')
1468
1598
            try:
1469
1599
                self.tt.create_file(f, trans_id)
1487
1617
                other_rev_id=None,
1488
1618
                interesting_files=None,
1489
1619
                this_tree=None,
1490
 
                pb=DummyProgress(),
 
1620
                pb=progress.DummyProgress(),
1491
1621
                change_reporter=None):
1492
1622
    """Primary interface for merging.
1493
1623
 
1496
1626
                     branch.get_revision_tree(base_revision))'
1497
1627
        """
1498
1628
    if this_tree is None:
1499
 
        raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1500
 
            "parameter as of bzrlib version 0.8.")
 
1629
        raise errors.BzrError("bzrlib.merge.merge_inner requires a this_tree "
 
1630
                              "parameter as of bzrlib version 0.8.")
1501
1631
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1502
1632
                    pb=pb, change_reporter=change_reporter)
1503
1633
    merger.backup_files = backup_files
1516
1646
    get_revision_id = getattr(base_tree, 'get_revision_id', None)
1517
1647
    if get_revision_id is None:
1518
1648
        get_revision_id = base_tree.last_revision
 
1649
    merger.cache_trees_with_revision_ids([other_tree, base_tree, this_tree])
1519
1650
    merger.set_base_revision(get_revision_id(), this_branch)
1520
1651
    return merger.do_merge()
1521
1652
 
1720
1851
        super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1721
1852
        self.a_key = self._key_prefix + (self.a_rev,)
1722
1853
        self.b_key = self._key_prefix + (self.b_rev,)
1723
 
        self.graph = Graph(self.vf)
 
1854
        self.graph = _mod_graph.Graph(self.vf)
1724
1855
        heads = self.graph.heads((self.a_key, self.b_key))
1725
1856
        if len(heads) == 1:
1726
1857
            # one side dominates, so we can just return its values, yay for
1731
1862
                other = b_rev
1732
1863
            else:
1733
1864
                other = a_rev
1734
 
            mutter('found dominating revision for %s\n%s > %s', self.vf,
1735
 
                   self._head_key[-1], other)
 
1865
            trace.mutter('found dominating revision for %s\n%s > %s', self.vf,
 
1866
                         self._head_key[-1], other)
1736
1867
            self._weave = None
1737
1868
        else:
1738
1869
            self._head_key = None
1752
1883
        while True:
1753
1884
            next_lcas = self.graph.find_lca(*cur_ancestors)
1754
1885
            # Map a plain NULL_REVISION to a simple no-ancestors
1755
 
            if next_lcas == set([NULL_REVISION]):
 
1886
            if next_lcas == set([_mod_revision.NULL_REVISION]):
1756
1887
                next_lcas = ()
1757
1888
            # Order the lca's based on when they were merged into the tip
1758
1889
            # While the actual merge portion of weave merge uses a set() of
1770
1901
            elif len(next_lcas) > 2:
1771
1902
                # More than 2 lca's, fall back to grabbing all nodes between
1772
1903
                # this and the unique lca.
1773
 
                mutter('More than 2 LCAs, falling back to all nodes for:'
1774
 
                       ' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
 
1904
                trace.mutter('More than 2 LCAs, falling back to all nodes for:'
 
1905
                             ' %s, %s\n=> %s',
 
1906
                             self.a_key, self.b_key, cur_ancestors)
1775
1907
                cur_lcas = next_lcas
1776
1908
                while len(cur_lcas) > 1:
1777
1909
                    cur_lcas = self.graph.find_lca(*cur_lcas)
1780
1912
                    unique_lca = None
1781
1913
                else:
1782
1914
                    unique_lca = list(cur_lcas)[0]
1783
 
                    if unique_lca == NULL_REVISION:
 
1915
                    if unique_lca == _mod_revision.NULL_REVISION:
1784
1916
                        # find_lca will return a plain 'NULL_REVISION' rather
1785
1917
                        # than a key tuple when there is no common ancestor, we
1786
1918
                        # prefer to just use None, because it doesn't confuse
1809
1941
            # We remove NULL_REVISION because it isn't a proper tuple key, and
1810
1942
            # thus confuses things like _get_interesting_texts, and our logic
1811
1943
            # to add the texts into the memory weave.
1812
 
            if NULL_REVISION in parent_map:
1813
 
                parent_map.pop(NULL_REVISION)
 
1944
            if _mod_revision.NULL_REVISION in parent_map:
 
1945
                parent_map.pop(_mod_revision.NULL_REVISION)
1814
1946
        else:
1815
1947
            interesting = set()
1816
1948
            for tip in tip_keys:
1968
2100
        lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1969
2101
        self.lcas = set()
1970
2102
        for lca in lcas:
1971
 
            if lca == NULL_REVISION:
 
2103
            if lca == _mod_revision.NULL_REVISION:
1972
2104
                self.lcas.add(lca)
1973
2105
            else:
1974
2106
                self.lcas.add(lca[-1])