← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: John Arbash Meinel
  • Date: 2008-07-31 19:12:59 UTC
  • mto: (3697.7.4 1.7)
  • mto: This revision was merged to the branch mainline in revision 3748.
  • Revision ID: john@arbash-meinel.com-20080731191259-81qy04c3h4bxir0s
Several updates.

Add a document describing the merge algorithm, and the rationale
for the different steps.
Change the sha1 algorithm to use get_file_sha1() rather than assuming the
inventory entries text_sha1 value is correct. (It is always None for working trees.)
For sha1-values specifically, don't allow overruling an LCA value when one tip
seems to supersede the other's value. We will still do this for names and parent_ids.
Add tests that we conflict if lcas disagree and tips do not have the same content,
even if one of them is an lca value, and one is newer.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
711
711
            if interesting_ids is not None and file_id not in interesting_ids:
712
712
                continue
713
713
 
714
 
            # I believe we can actually change this to see if last_rev is
715
 
            # identical to *any* of the lca values. Though we should actually
716
 
            # use the _lca_multi_way logic. However, it may be worthwhile to
717
 
            # shortcut entries that are identical in all of LCA + OTHER, just
718
 
            # to avoid the overhead of looking up information in BASE and THIS.
 
714
            # If other_revision is found in any of the lcas, that means this
 
715
            # node is uninteresting. This is because when merging, if there are
 
716
            # multiple heads(), we have to create a new node. So if we didn't,
 
717
            # we know that the ancestry is linear, and that OTHER did not
 
718
            # modify anything
 
719
            # See doc/developers/lca_merge_resolution.txt for details
719
720
            other_revision = other_ie.revision
 
721
            is_unmodified = False
720
722
            for lca_path, ie in lca_values:
721
 
                if ie is None or ie.revision != other_revision:
 
723
                if ie is not None and ie.revision == other_revision:
 
724
                    is_unmodified = True
722
725
                    break
723
 
            else: # Identical in all trees
 
726
            if is_unmodified:
724
727
                continue
725
728
 
726
729
            lca_entries = []
744
747
            lca_parent_ids = []
745
748
            lca_names = []
746
749
            lca_executable = []
747
 
            lca_sha1s = []
748
750
            for lca_ie in lca_entries:
749
751
                lca_kinds.append(lca_ie.kind)
750
752
                lca_parent_ids.append(lca_ie.parent_id)
751
753
                lca_names.append(lca_ie.name)
752
754
                lca_executable.append(lca_ie.executable)
753
 
                lca_sha1s.append(lca_ie.text_sha1)
754
755
 
755
756
            kind_winner = Merge3Merger._lca_multi_way(
756
757
                (base_ie.kind, lca_kinds),
775
776
                        continue
776
777
                    content_changed = False
777
778
                elif other_ie.kind == 'file':
 
779
                    def get_sha1(ie, tree):
 
780
                        if ie.kind is None:
 
781
                            return None
 
782
                        return tree.get_file_sha1(file_id)
 
783
                    base_sha1 = get_sha1(base_ie, self.base_tree)
 
784
                    lca_sha1s = [get_sha1(ie, tree) for ie, tree
 
785
                                 in zip(lca_entries, self._lca_trees)]
 
786
                    this_sha1 = get_sha1(this_ie, self.this_tree)
 
787
                    other_sha1 = get_sha1(other_ie, self.other_tree)
778
788
                    sha1_winner = Merge3Merger._lca_multi_way(
779
 
                        (base_ie.text_sha1, lca_sha1s),
780
 
                        other_ie.text_sha1, this_ie.text_sha1)
 
789
                        (base_sha1, lca_sha1s), other_sha1, this_sha1,
 
790
                        allow_overriding_lca=False)
781
791
                    exec_winner = Merge3Merger._lca_multi_way(
782
792
                        (base_ie.executable, lca_executable),
783
793
                        other_ie.executable, this_ie.executable)
907
917
            return "other"
908
918
 
909
919
    @staticmethod
910
 
    def _lca_multi_way(bases, other, this):
 
920
    def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
911
921
        """Consider LCAs when determining whether a change has occurred.
912
922
 
913
923
        If LCAS are all identical, this is the same as a _three_way comparison.
915
925
        :param bases: value in (BASE, [LCAS])
916
926
        :param other: value in OTHER
917
927
        :param this: value in THIS
 
928
        :param allow_overriding_lca: If there is more than one unique lca
 
929
            value, allow OTHER to override THIS if it has a new value, and
 
930
            THIS only has an lca value, or vice versa. This is appropriate for
 
931
            truly scalar values, not as much for non-scalars.
918
932
        :return: 'this', 'other', or 'conflict' depending on whether an entry
919
933
            changed or not.
920
934
        """
 
935
        # See doc/developers/lca_merge_resolution.txt for details about this
 
936
        # algorithm.
921
937
        if other == this:
922
938
            # Either Ambiguously clean, or nothing was actually changed. We
923
939
            # don't really care
928
944
                                      if lca_val != base_val]
929
945
        if len(filtered_lca_vals) == 0:
930
946
            return Merge3Merger._three_way(base_val, other, this)
931
 
        else:
932
 
            first_lca_val = filtered_lca_vals[0]
933
 
            for lca_val in filtered_lca_vals[1:]:
934
 
                if lca_val != first_lca_val:
935
 
                    break
936
 
            else: # all lcas are equal, use 3-way logic
937
 
                return Merge3Merger._three_way(first_lca_val, other, this)
938
 
        if other in filtered_lca_vals:
939
 
            if this in filtered_lca_vals:
940
 
                # Each side picked a different lca, conflict
941
 
                return 'conflict'
942
 
            else:
943
 
                # This has a value which supersedes both lca values, and other
 
947
 
 
948
        unique_lca_vals = set(filtered_lca_vals)
 
949
        if len(unique_lca_vals) == 1:
 
950
            return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
 
951
 
 
952
        if allow_overriding_lca:
 
953
            if other in unique_lca_vals:
 
954
                if this in unique_lca_vals:
 
955
                    # Each side picked a different lca, conflict
 
956
                    return 'conflict'
 
957
                else:
 
958
                    # This has a value which supersedes both lca values, and
 
959
                    # other only has an lca value
 
960
                    return 'this'
 
961
            elif this in unique_lca_vals:
 
962
                # OTHER has a value which supersedes both lca values, and this
944
963
                # only has an lca value
945
 
                return 'this'
946
 
        elif this in filtered_lca_vals:
947
 
            # OTHER has a value which supersedes both lca values, and this only
948
 
            # has an lca value
949
 
            return 'other'
 
964
                return 'other'
950
965
 
951
966
        # At this point, the lcas disagree, and the tips disagree
952
967
        return 'conflict'