← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

Merge down-thread (including bzr.dev)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
28
28
    patiencediff,
29
29
    registry,
30
30
    revision as _mod_revision,
 
31
    tree as _mod_tree,
31
32
    tsort,
32
33
    )
33
34
from bzrlib.branch import Branch
96
97
        self._revision_graph = revision_graph
97
98
        self._base_is_ancestor = None
98
99
        self._base_is_other_ancestor = None
 
100
        self._is_criss_cross = None
 
101
        self._lca_trees = None
99
102
 
100
103
    @property
101
104
    def revision_graph(self):
353
356
                     ensure_null(self.other_basis)]
354
357
        if NULL_REVISION in revisions:
355
358
            self.base_rev_id = NULL_REVISION
 
359
            self.base_tree = self.revision_tree(self.base_rev_id)
 
360
            self._is_criss_cross = False
356
361
        else:
357
 
            self.base_rev_id, steps = self.revision_graph.find_unique_lca(
358
 
                revisions[0], revisions[1], count_steps=True)
 
362
            lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
 
363
            self._is_criss_cross = False
 
364
            if len(lcas) == 0:
 
365
                self.base_rev_id = NULL_REVISION
 
366
            elif len(lcas) == 1:
 
367
                self.base_rev_id = list(lcas)[0]
 
368
            else: # len(lcas) > 1
 
369
                if len(lcas) > 2:
 
370
                    # find_unique_lca can only handle 2 nodes, so we have to
 
371
                    # start back at the beginning. It is a shame to traverse
 
372
                    # the graph again, but better than re-implementing
 
373
                    # find_unique_lca.
 
374
                    self.base_rev_id = self.revision_graph.find_unique_lca(
 
375
                                            revisions[0], revisions[1])
 
376
                else:
 
377
                    self.base_rev_id = self.revision_graph.find_unique_lca(
 
378
                                            *lcas)
 
379
                self._is_criss_cross = True
359
380
            if self.base_rev_id == NULL_REVISION:
360
381
                raise UnrelatedBranches()
361
 
            if steps > 1:
 
382
            if self._is_criss_cross:
362
383
                warning('Warning: criss-cross merge encountered.  See bzr'
363
384
                        ' help criss-cross.')
364
 
        self.base_tree = self.revision_tree(self.base_rev_id)
 
385
                interesting_revision_ids = [self.base_rev_id]
 
386
                interesting_revision_ids.extend(lcas)
 
387
                interesting_trees = dict((t.get_revision_id(), t)
 
388
                    for t in self.this_branch.repository.revision_trees(
 
389
                        interesting_revision_ids))
 
390
                self._cached_trees.update(interesting_trees)
 
391
                self.base_tree = interesting_trees.pop(self.base_rev_id)
 
392
                sorted_lca_keys = self.revision_graph.find_merge_order(
 
393
                    revisions[0], lcas)
 
394
                self._lca_trees = [interesting_trees[key]
 
395
                                   for key in sorted_lca_keys]
 
396
            else:
 
397
                self.base_tree = self.revision_tree(self.base_rev_id)
365
398
        self.base_is_ancestor = True
366
399
        self.base_is_other_ancestor = True
367
400
 
409
442
        if self.merge_type.supports_cherrypick:
410
443
            kwargs['cherrypick'] = (not self.base_is_ancestor or
411
444
                                    not self.base_is_other_ancestor)
 
445
        if self._is_criss_cross and getattr(self.merge_type,
 
446
                                            'supports_lca_trees', False):
 
447
            kwargs['lca_trees'] = self._lca_trees
412
448
        return self.merge_type(pb=self._pb,
413
449
                               change_reporter=self.change_reporter,
414
450
                               **kwargs)
460
496
        return len(merge.cooked_conflicts)
461
497
 
462
498
 
 
499
class _InventoryNoneEntry(object):
 
500
    """This represents an inventory entry which *isn't there*.
 
501
 
 
502
    It simplifies the merging logic if we always have an InventoryEntry, even
 
503
    if it isn't actually present
 
504
    """
 
505
    executable = None
 
506
    kind = None
 
507
    name = None
 
508
    parent_id = None
 
509
    revision = None
 
510
    symlink_target = None
 
511
    text_sha1 = None
 
512
 
 
513
_none_entry = _InventoryNoneEntry()
 
514
 
 
515
 
463
516
class Merge3Merger(object):
464
517
    """Three-way merger that uses the merge3 text merger"""
465
518
    requires_base = True
469
522
    supports_cherrypick = True
470
523
    supports_reverse_cherrypick = True
471
524
    winner_idx = {"this": 2, "other": 1, "conflict": 1}
 
525
    supports_lca_trees = True
472
526
 
473
527
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
474
528
                 interesting_ids=None, reprocess=False, show_base=False,
475
529
                 pb=DummyProgress(), pp=None, change_reporter=None,
476
530
                 interesting_files=None, do_merge=True,
477
 
                 cherrypick=False):
 
531
                 cherrypick=False, lca_trees=None):
478
532
        """Initialize the merger object and perform the merge.
479
533
 
480
534
        :param working_tree: The working tree to apply the merge to
496
550
            be combined with interesting_ids.  If neither interesting_files nor
497
551
            interesting_ids is specified, all files may participate in the
498
552
            merge.
 
553
        :param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
 
554
            if the ancestry was found to include a criss-cross merge.
 
555
            Otherwise should be None.
499
556
        """
500
557
        object.__init__(self)
501
558
        if interesting_files is not None and interesting_ids is not None:
510
567
        self.cooked_conflicts = []
511
568
        self.reprocess = reprocess
512
569
        self.show_base = show_base
 
570
        self._lca_trees = lca_trees
 
571
        # Uncommenting this will change the default algorithm to always use
 
572
        # _entries_lca. This can be useful for running the test suite and
 
573
        # making sure we haven't missed any corner cases.
 
574
        # if lca_trees is None:
 
575
        #     self._lca_trees = [self.base_tree]
513
576
        self.pb = pb
514
577
        self.pp = pp
515
578
        self.change_reporter = change_reporter
556
619
        return self.tt
557
620
 
558
621
    def _compute_transform(self):
559
 
        entries = self._entries3()
 
622
        if self._lca_trees is None:
 
623
            entries = self._entries3()
 
624
            resolver = self._three_way
 
625
        else:
 
626
            entries = self._entries_lca()
 
627
            resolver = self._lca_multi_way
560
628
        child_pb = ui.ui_factory.nested_progress_bar()
561
629
        try:
562
630
            for num, (file_id, changed, parents3, names3,
563
631
                      executable3) in enumerate(entries):
564
632
                child_pb.update('Preparing file merge', num, len(entries))
565
 
                self._merge_names(file_id, parents3, names3)
 
633
                self._merge_names(file_id, parents3, names3, resolver=resolver)
566
634
                if changed:
567
635
                    file_status = self.merge_contents(file_id)
568
636
                else:
569
637
                    file_status = 'unmodified'
570
638
                self._merge_executable(file_id,
571
 
                    executable3, file_status)
 
639
                    executable3, file_status, resolver=resolver)
572
640
        finally:
573
641
            child_pb.finished()
574
642
        self.fix_root()
620
688
            result.append((file_id, changed, parents3, names3, executable3))
621
689
        return result
622
690
 
 
691
    def _entries_lca(self):
 
692
        """Gather data about files modified between multiple trees.
 
693
 
 
694
        This compares OTHER versus all LCA trees, and for interesting entries,
 
695
        it then compares with THIS and BASE.
 
696
 
 
697
        For the multi-valued entries, the format will be (BASE, [lca1, lca2])
 
698
        :return: [(file_id, changed, parents, names, executable)]
 
699
            file_id     Simple file_id of the entry
 
700
            changed     Boolean, True if the kind or contents changed
 
701
                        else False
 
702
            parents     ((base, [parent_id, in, lcas]), parent_id_other,
 
703
                         parent_id_this)
 
704
            names       ((base, [name, in, lcas]), name_in_other, name_in_this)
 
705
            executable  ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
 
706
        """
 
707
        if self.interesting_files is not None:
 
708
            lookup_trees = [self.this_tree, self.base_tree]
 
709
            lookup_trees.extend(self._lca_trees)
 
710
            # I think we should include the lca trees as well
 
711
            interesting_ids = self.other_tree.paths2ids(self.interesting_files,
 
712
                                                        lookup_trees)
 
713
        else:
 
714
            interesting_ids = self.interesting_ids
 
715
        result = []
 
716
        walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
 
717
 
 
718
        base_inventory = self.base_tree.inventory
 
719
        this_inventory = self.this_tree.inventory
 
720
        for path, file_id, other_ie, lca_values in walker.iter_all():
 
721
            # Is this modified at all from any of the other trees?
 
722
            if other_ie is None:
 
723
                other_ie = _none_entry
 
724
            if interesting_ids is not None and file_id not in interesting_ids:
 
725
                continue
 
726
 
 
727
            # If other_revision is found in any of the lcas, that means this
 
728
            # node is uninteresting. This is because when merging, if there are
 
729
            # multiple heads(), we have to create a new node. So if we didn't,
 
730
            # we know that the ancestry is linear, and that OTHER did not
 
731
            # modify anything
 
732
            # See doc/developers/lca_merge_resolution.txt for details
 
733
            other_revision = other_ie.revision
 
734
            if other_revision is not None:
 
735
                # We can't use this shortcut when other_revision is None,
 
736
                # because it may be None because things are WorkingTrees, and
 
737
                # not because it is *actually* None.
 
738
                is_unmodified = False
 
739
                for lca_path, ie in lca_values:
 
740
                    if ie is not None and ie.revision == other_revision:
 
741
                        is_unmodified = True
 
742
                        break
 
743
                if is_unmodified:
 
744
                    continue
 
745
 
 
746
            lca_entries = []
 
747
            for lca_path, lca_ie in lca_values:
 
748
                if lca_ie is None:
 
749
                    lca_entries.append(_none_entry)
 
750
                else:
 
751
                    lca_entries.append(lca_ie)
 
752
 
 
753
            if file_id in base_inventory:
 
754
                base_ie = base_inventory[file_id]
 
755
            else:
 
756
                base_ie = _none_entry
 
757
 
 
758
            if file_id in this_inventory:
 
759
                this_ie = this_inventory[file_id]
 
760
            else:
 
761
                this_ie = _none_entry
 
762
 
 
763
            lca_kinds = []
 
764
            lca_parent_ids = []
 
765
            lca_names = []
 
766
            lca_executable = []
 
767
            for lca_ie in lca_entries:
 
768
                lca_kinds.append(lca_ie.kind)
 
769
                lca_parent_ids.append(lca_ie.parent_id)
 
770
                lca_names.append(lca_ie.name)
 
771
                lca_executable.append(lca_ie.executable)
 
772
 
 
773
            kind_winner = self._lca_multi_way(
 
774
                (base_ie.kind, lca_kinds),
 
775
                other_ie.kind, this_ie.kind)
 
776
            parent_id_winner = self._lca_multi_way(
 
777
                (base_ie.parent_id, lca_parent_ids),
 
778
                other_ie.parent_id, this_ie.parent_id)
 
779
            name_winner = self._lca_multi_way(
 
780
                (base_ie.name, lca_names),
 
781
                other_ie.name, this_ie.name)
 
782
 
 
783
            content_changed = True
 
784
            if kind_winner == 'this':
 
785
                # No kind change in OTHER, see if there are *any* changes
 
786
                if other_ie.kind == None:
 
787
                    # No content and 'this' wins the kind, so skip this?
 
788
                    # continue
 
789
                    pass
 
790
                elif other_ie.kind == 'directory':
 
791
                    if parent_id_winner == 'this' and name_winner == 'this':
 
792
                        # No change for this directory in OTHER, skip
 
793
                        continue
 
794
                    content_changed = False
 
795
                elif other_ie.kind == 'file':
 
796
                    def get_sha1(ie, tree):
 
797
                        if ie.kind != 'file':
 
798
                            return None
 
799
                        return tree.get_file_sha1(file_id)
 
800
                    base_sha1 = get_sha1(base_ie, self.base_tree)
 
801
                    lca_sha1s = [get_sha1(ie, tree) for ie, tree
 
802
                                 in zip(lca_entries, self._lca_trees)]
 
803
                    this_sha1 = get_sha1(this_ie, self.this_tree)
 
804
                    other_sha1 = get_sha1(other_ie, self.other_tree)
 
805
                    sha1_winner = self._lca_multi_way(
 
806
                        (base_sha1, lca_sha1s), other_sha1, this_sha1,
 
807
                        allow_overriding_lca=False)
 
808
                    exec_winner = self._lca_multi_way(
 
809
                        (base_ie.executable, lca_executable),
 
810
                        other_ie.executable, this_ie.executable)
 
811
                    if (parent_id_winner == 'this' and name_winner == 'this'
 
812
                        and sha1_winner == 'this' and exec_winner == 'this'):
 
813
                        # No kind, parent, name, exec, or content change for
 
814
                        # OTHER, so this node is not considered interesting
 
815
                        continue
 
816
                    if sha1_winner == 'this':
 
817
                        content_changed = False
 
818
                elif other_ie.kind == 'symlink':
 
819
                    def get_target(ie, tree):
 
820
                        if ie.kind != 'symlink':
 
821
                            return None
 
822
                        return tree.get_symlink_target(file_id)
 
823
                    base_target = get_target(base_ie, self.base_tree)
 
824
                    lca_targets = [get_target(ie, tree) for ie, tree
 
825
                                   in zip(lca_entries, self._lca_trees)]
 
826
                    this_target = get_target(this_ie, self.this_tree)
 
827
                    other_target = get_target(other_ie, self.other_tree)
 
828
                    target_winner = self._lca_multi_way(
 
829
                        (base_target, lca_targets),
 
830
                        other_target, this_target)
 
831
                    if (parent_id_winner == 'this' and name_winner == 'this'
 
832
                        and target_winner == 'this'):
 
833
                        # No kind, parent, name, or symlink target change
 
834
                        # not interesting
 
835
                        continue
 
836
                    if target_winner == 'this':
 
837
                        content_changed = False
 
838
                elif other_ie.kind == 'tree-reference':
 
839
                    # The 'changed' information seems to be handled at a higher
 
840
                    # level. At least, _entries3 returns False for content
 
841
                    # changed, even when at a new revision_id.
 
842
                    content_changed = False
 
843
                    if (parent_id_winner == 'this' and name_winner == 'this'):
 
844
                        # Nothing interesting
 
845
                        continue
 
846
                else:
 
847
                    raise AssertionError('unhandled kind: %s' % other_ie.kind)
 
848
                # XXX: We need to handle kind == 'symlink'
 
849
 
 
850
            # If we have gotten this far, that means something has changed
 
851
            result.append((file_id, content_changed,
 
852
                           ((base_ie.parent_id, lca_parent_ids),
 
853
                            other_ie.parent_id, this_ie.parent_id),
 
854
                           ((base_ie.name, lca_names),
 
855
                            other_ie.name, this_ie.name),
 
856
                           ((base_ie.executable, lca_executable),
 
857
                            other_ie.executable, this_ie.executable)
 
858
                          ))
 
859
        return result
 
860
 
 
861
 
623
862
    def fix_root(self):
624
863
        try:
625
864
            self.tt.final_kind(self.tt.root)
714
953
            return "other"
715
954
 
716
955
    @staticmethod
 
956
    def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
 
957
        """Consider LCAs when determining whether a change has occurred.
 
958
 
 
959
        If LCAS are all identical, this is the same as a _three_way comparison.
 
960
 
 
961
        :param bases: value in (BASE, [LCAS])
 
962
        :param other: value in OTHER
 
963
        :param this: value in THIS
 
964
        :param allow_overriding_lca: If there is more than one unique lca
 
965
            value, allow OTHER to override THIS if it has a new value, and
 
966
            THIS only has an lca value, or vice versa. This is appropriate for
 
967
            truly scalar values, not as much for non-scalars.
 
968
        :return: 'this', 'other', or 'conflict' depending on whether an entry
 
969
            changed or not.
 
970
        """
 
971
        # See doc/developers/lca_merge_resolution.txt for details about this
 
972
        # algorithm.
 
973
        if other == this:
 
974
            # Either Ambiguously clean, or nothing was actually changed. We
 
975
            # don't really care
 
976
            return 'this'
 
977
        base_val, lca_vals = bases
 
978
        # Remove 'base_val' from the lca_vals, because it is not interesting
 
979
        filtered_lca_vals = [lca_val for lca_val in lca_vals
 
980
                                      if lca_val != base_val]
 
981
        if len(filtered_lca_vals) == 0:
 
982
            return Merge3Merger._three_way(base_val, other, this)
 
983
 
 
984
        unique_lca_vals = set(filtered_lca_vals)
 
985
        if len(unique_lca_vals) == 1:
 
986
            return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
 
987
 
 
988
        if allow_overriding_lca:
 
989
            if other in unique_lca_vals:
 
990
                if this in unique_lca_vals:
 
991
                    # Each side picked a different lca, conflict
 
992
                    return 'conflict'
 
993
                else:
 
994
                    # This has a value which supersedes both lca values, and
 
995
                    # other only has an lca value
 
996
                    return 'this'
 
997
            elif this in unique_lca_vals:
 
998
                # OTHER has a value which supersedes both lca values, and this
 
999
                # only has an lca value
 
1000
                return 'other'
 
1001
 
 
1002
        # At this point, the lcas disagree, and the tips disagree
 
1003
        return 'conflict'
 
1004
 
 
1005
    @staticmethod
717
1006
    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
718
1007
        """Do a three-way test on a scalar.
719
1008
        Return "this", "other" or "conflict", depending whether a value wins.
751
1040
            else:
752
1041
                names.append(entry.name)
753
1042
                parents.append(entry.parent_id)
754
 
        return self._merge_names(file_id, parents, names)
 
1043
        return self._merge_names(file_id, parents, names,
 
1044
                                 resolver=self._three_way)
755
1045
 
756
 
    def _merge_names(self, file_id, parents, names):
 
1046
    def _merge_names(self, file_id, parents, names, resolver):
757
1047
        """Perform a merge on file_id names and parents"""
758
1048
        base_name, other_name, this_name = names
759
1049
        base_parent, other_parent, this_parent = parents
760
1050
 
761
 
        name_winner = self._three_way(*names)
 
1051
        name_winner = resolver(*names)
762
1052
 
763
 
        parent_id_winner = self._three_way(*parents)
 
1053
        parent_id_winner = resolver(*parents)
764
1054
        if this_name is None:
765
1055
            if name_winner == "this":
766
1056
                name_winner = "other"
954
1244
        """Perform a merge on the execute bit."""
955
1245
        executable = [self.executable(t, file_id) for t in (self.base_tree,
956
1246
                      self.other_tree, self.this_tree)]
957
 
        self._merge_executable(file_id, executable, file_status)
 
1247
        self._merge_executable(file_id, executable, file_status,
 
1248
                               resolver=self._three_way)
958
1249
 
959
 
    def _merge_executable(self, file_id, executable, file_status):
 
1250
    def _merge_executable(self, file_id, executable, file_status,
 
1251
                          resolver):
960
1252
        """Perform a merge on the execute bit."""
961
1253
        base_executable, other_executable, this_executable = executable
962
1254
        if file_status == "deleted":
963
1255
            return
964
 
        winner = self._three_way(*executable)
 
1256
        winner = resolver(*executable)
965
1257
        if winner == "conflict":
966
1258
        # There must be a None in here, if we have a conflict, but we
967
1259
        # need executability since file status was not deleted.