/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

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