/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

  • Committer: Aaron Bentley
  • Date: 2007-12-02 23:52:03 UTC
  • mto: This revision was merged to the branch mainline in revision 3073.
  • Revision ID: aaron.bentley@utoronto.ca-20071202235203-e1c69qbqegre7nfj
Move PlanMerge into merge and _PlanMergeVersionedFile into versionedfile

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
1135
1135
        for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1136
1136
            assert text_a == text_b
1137
1137
            yield "unchanged", text_a
 
1138
 
 
1139
 
 
1140
class PlanMerge(object):
 
1141
    """Plan an annotate merge using on-the-fly annotation"""
 
1142
 
 
1143
    def __init__(self, a_rev, b_rev, vf):
 
1144
        """Contructor.
 
1145
 
 
1146
        :param a_rev: Revision-id of one revision to merge
 
1147
        :param b_rev: Revision-id of the other revision to merge
 
1148
        :param vf: A versionedfile containing both revisions
 
1149
        """
 
1150
        self.a_rev = a_rev
 
1151
        self.b_rev = b_rev
 
1152
        self.lines_a = vf.get_lines(a_rev)
 
1153
        self.lines_b = vf.get_lines(b_rev)
 
1154
        self.vf = vf
 
1155
        a_ancestry = set(vf.get_ancestry(a_rev))
 
1156
        b_ancestry = set(vf.get_ancestry(b_rev))
 
1157
        self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
 
1158
 
 
1159
    def plan_merge(self):
 
1160
        """Generate a 'plan' for merging the two revisions.
 
1161
 
 
1162
        This involves comparing their texts and determining the cause of
 
1163
        differences.  If text A has a line and text B does not, then either the
 
1164
        line was added to text A, or it was deleted from B.  Once the causes
 
1165
        are combined, they are written out in the format described in
 
1166
        VersionedFile.plan_merge
 
1167
        """
 
1168
        blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
 
1169
        new_a = self._find_new(self.a_rev)
 
1170
        new_b = self._find_new(self.b_rev)
 
1171
        last_i = 0
 
1172
        last_j = 0
 
1173
        a_lines = self.vf.get_lines(self.a_rev)
 
1174
        b_lines = self.vf.get_lines(self.b_rev)
 
1175
        for i, j, n in blocks:
 
1176
            # determine why lines aren't common
 
1177
            for a_index in range(last_i, i):
 
1178
                if a_index in new_a:
 
1179
                    cause = 'new-a'
 
1180
                else:
 
1181
                    cause = 'killed-b'
 
1182
                yield cause, a_lines[a_index]
 
1183
            for b_index in range(last_j, j):
 
1184
                if b_index in new_b:
 
1185
                    cause = 'new-b'
 
1186
                else:
 
1187
                    cause = 'killed-a'
 
1188
                yield cause, b_lines[b_index]
 
1189
            # handle common lines
 
1190
            for a_index in range(i, i+n):
 
1191
                yield 'unchanged', a_lines[a_index]
 
1192
            last_i = i+n
 
1193
            last_j = j+n
 
1194
 
 
1195
    def _get_matching_blocks(self, left_revision, right_revision):
 
1196
        """Return a description of which sections of two revisions match.
 
1197
 
 
1198
        See SequenceMatcher.get_matching_blocks
 
1199
        """
 
1200
        left_lines = self.vf.get_lines(left_revision)
 
1201
        right_lines = self.vf.get_lines(right_revision)
 
1202
        matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
 
1203
                                                       right_lines)
 
1204
        return matcher.get_matching_blocks()
 
1205
 
 
1206
    def _unique_lines(self, matching_blocks):
 
1207
        """Analyse matching_blocks to determine which lines are unique
 
1208
 
 
1209
        :return: a tuple of (unique_left, unique_right), where the values are
 
1210
            sets of line numbers of unique lines.
 
1211
        """
 
1212
        last_i = 0
 
1213
        last_j = 0
 
1214
        unique_left = []
 
1215
        unique_right = []
 
1216
        for i, j, n in matching_blocks:
 
1217
            unique_left.extend(range(last_i, i))
 
1218
            unique_right.extend(range(last_j, j))
 
1219
            last_i = i + n
 
1220
            last_j = j + n
 
1221
        return unique_left, unique_right
 
1222
 
 
1223
    def _find_new(self, version_id):
 
1224
        """Determine which lines are new in the ancestry of this version.
 
1225
 
 
1226
        If a lines is present in this version, and not present in any
 
1227
        common ancestor, it is considered new.
 
1228
        """
 
1229
        if version_id not in self.uncommon:
 
1230
            return set()
 
1231
        parents = self.vf.get_parents(version_id)
 
1232
        if len(parents) == 0:
 
1233
            return set(range(len(self.vf.get_lines(version_id))))
 
1234
        new = None
 
1235
        for parent in parents:
 
1236
            blocks = self._get_matching_blocks(version_id, parent)
 
1237
            result, unused = self._unique_lines(blocks)
 
1238
            parent_new = self._find_new(parent)
 
1239
            for i, j, n in blocks:
 
1240
                for ii, jj in [(i+r, j+r) for r in range(n)]:
 
1241
                    if jj in parent_new:
 
1242
                        result.append(ii)
 
1243
            if new is None:
 
1244
                new = set(result)
 
1245
            else:
 
1246
                new.intersection_update(result)
 
1247
        return new