/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: Canonical.com Patch Queue Manager
  • Date: 2007-12-04 00:42:43 UTC
  • mfrom: (3062.1.14 fast-plan-merge)
  • Revision ID: pqm@pqm.ubuntu.com-20071204004243-cgss0sl9yf0ayepc
Speed up annotate on packs

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, topo_sorted=False))
 
1156
        b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
 
1157
        self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
 
1158
        self._last_lines = None
 
1159
        self._last_lines_revision_id = None
 
1160
 
 
1161
    def plan_merge(self):
 
1162
        """Generate a 'plan' for merging the two revisions.
 
1163
 
 
1164
        This involves comparing their texts and determining the cause of
 
1165
        differences.  If text A has a line and text B does not, then either the
 
1166
        line was added to text A, or it was deleted from B.  Once the causes
 
1167
        are combined, they are written out in the format described in
 
1168
        VersionedFile.plan_merge
 
1169
        """
 
1170
        blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
 
1171
        new_a = self._find_new(self.a_rev)
 
1172
        new_b = self._find_new(self.b_rev)
 
1173
        last_i = 0
 
1174
        last_j = 0
 
1175
        a_lines = self.vf.get_lines(self.a_rev)
 
1176
        b_lines = self.vf.get_lines(self.b_rev)
 
1177
        for i, j, n in blocks:
 
1178
            # determine why lines aren't common
 
1179
            for a_index in range(last_i, i):
 
1180
                if a_index in new_a:
 
1181
                    cause = 'new-a'
 
1182
                else:
 
1183
                    cause = 'killed-b'
 
1184
                yield cause, a_lines[a_index]
 
1185
            for b_index in range(last_j, j):
 
1186
                if b_index in new_b:
 
1187
                    cause = 'new-b'
 
1188
                else:
 
1189
                    cause = 'killed-a'
 
1190
                yield cause, b_lines[b_index]
 
1191
            # handle common lines
 
1192
            for a_index in range(i, i+n):
 
1193
                yield 'unchanged', a_lines[a_index]
 
1194
            last_i = i+n
 
1195
            last_j = j+n
 
1196
 
 
1197
    def _get_matching_blocks(self, left_revision, right_revision):
 
1198
        """Return a description of which sections of two revisions match.
 
1199
 
 
1200
        See SequenceMatcher.get_matching_blocks
 
1201
        """
 
1202
        if self._last_lines_revision_id == left_revision:
 
1203
            left_lines = self._last_lines
 
1204
        else:
 
1205
            left_lines = self.vf.get_lines(left_revision)
 
1206
        right_lines = self.vf.get_lines(right_revision)
 
1207
        self._last_lines = right_lines
 
1208
        self._last_lines_revision_id = right_revision
 
1209
        matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
 
1210
                                                       right_lines)
 
1211
        return matcher.get_matching_blocks()
 
1212
 
 
1213
    def _unique_lines(self, matching_blocks):
 
1214
        """Analyse matching_blocks to determine which lines are unique
 
1215
 
 
1216
        :return: a tuple of (unique_left, unique_right), where the values are
 
1217
            sets of line numbers of unique lines.
 
1218
        """
 
1219
        last_i = 0
 
1220
        last_j = 0
 
1221
        unique_left = []
 
1222
        unique_right = []
 
1223
        for i, j, n in matching_blocks:
 
1224
            unique_left.extend(range(last_i, i))
 
1225
            unique_right.extend(range(last_j, j))
 
1226
            last_i = i + n
 
1227
            last_j = j + n
 
1228
        return unique_left, unique_right
 
1229
 
 
1230
    def _find_new(self, version_id):
 
1231
        """Determine which lines are new in the ancestry of this version.
 
1232
 
 
1233
        If a lines is present in this version, and not present in any
 
1234
        common ancestor, it is considered new.
 
1235
        """
 
1236
        if version_id not in self.uncommon:
 
1237
            return set()
 
1238
        parents = self.vf.get_parents(version_id)
 
1239
        if len(parents) == 0:
 
1240
            return set(range(len(self.vf.get_lines(version_id))))
 
1241
        new = None
 
1242
        for parent in parents:
 
1243
            blocks = self._get_matching_blocks(version_id, parent)
 
1244
            result, unused = self._unique_lines(blocks)
 
1245
            parent_new = self._find_new(parent)
 
1246
            for i, j, n in blocks:
 
1247
                for ii, jj in [(i+r, j+r) for r in range(n)]:
 
1248
                    if jj in parent_new:
 
1249
                        result.append(ii)
 
1250
            if new is None:
 
1251
                new = set(result)
 
1252
            else:
 
1253
                new.intersection_update(result)
 
1254
        return new