/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: Vincent Ladeuil
  • Date: 2008-01-03 15:12:58 UTC
  • mfrom: (3158 +trunk)
  • mto: (3159.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 3161.
  • Revision ID: v.ladeuil+lp@free.fr-20080103151258-idpzfox078f80vhe
merge bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
1041
1041
            file_group.append(trans_id)
1042
1042
 
1043
1043
 
 
1044
class LCAMerger(WeaveMerger):
 
1045
 
 
1046
    def _merged_lines(self, file_id):
 
1047
        """Generate the merged lines.
 
1048
        There is no distinction between lines that are meant to contain <<<<<<<
 
1049
        and conflicts.
 
1050
        """
 
1051
        if self.cherrypick:
 
1052
            base = self.base_tree
 
1053
        else:
 
1054
            base = None
 
1055
        plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
 
1056
                                                  base=base)
 
1057
        if 'merge' in debug.debug_flags:
 
1058
            plan = list(plan)
 
1059
            trans_id = self.tt.trans_id_file_id(file_id)
 
1060
            name = self.tt.final_name(trans_id) + '.plan'
 
1061
            contents = ('%10s|%s' % l for l in plan)
 
1062
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
 
1063
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
 
1064
            '>>>>>>> MERGE-SOURCE\n')
 
1065
        return textmerge.merge_lines(self.reprocess)
 
1066
 
 
1067
 
1044
1068
class Diff3Merger(Merge3Merger):
1045
1069
    """Three-way merger using external diff3 for text merging"""
1046
1070
 
1165
1189
            yield "unchanged", text_a
1166
1190
 
1167
1191
 
1168
 
class _PlanMerge(object):
1169
 
    """Plan an annotate merge using on-the-fly annotation"""
 
1192
class _PlanMergeBase(object):
1170
1193
 
1171
1194
    def __init__(self, a_rev, b_rev, vf):
1172
1195
        """Contructor.
1180
1203
        self.lines_a = vf.get_lines(a_rev)
1181
1204
        self.lines_b = vf.get_lines(b_rev)
1182
1205
        self.vf = vf
1183
 
        a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1184
 
        b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1185
 
        self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1186
1206
        self._last_lines = None
1187
1207
        self._last_lines_revision_id = None
 
1208
        self._cached_matching_blocks = {}
1188
1209
 
1189
1210
    def plan_merge(self):
1190
1211
        """Generate a 'plan' for merging the two revisions.
1196
1217
        VersionedFile.plan_merge
1197
1218
        """
1198
1219
        blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1199
 
        new_a = self._find_new(self.a_rev)
1200
 
        new_b = self._find_new(self.b_rev)
 
1220
        unique_a, unique_b = self._unique_lines(blocks)
 
1221
        new_a, killed_b = self._determine_status(self.a_rev, unique_a)
 
1222
        new_b, killed_a = self._determine_status(self.b_rev, unique_b)
 
1223
        return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
 
1224
 
 
1225
    def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1201
1226
        last_i = 0
1202
1227
        last_j = 0
1203
 
        a_lines = self.vf.get_lines(self.a_rev)
1204
 
        b_lines = self.vf.get_lines(self.b_rev)
1205
1228
        for i, j, n in blocks:
1206
 
            # determine why lines aren't common
1207
1229
            for a_index in range(last_i, i):
1208
1230
                if a_index in new_a:
1209
 
                    cause = 'new-a'
 
1231
                    if a_index in killed_b:
 
1232
                        yield 'conflicted-a', self.lines_a[a_index]
 
1233
                    else:
 
1234
                        yield 'new-a', self.lines_a[a_index]
1210
1235
                else:
1211
 
                    cause = 'killed-b'
1212
 
                yield cause, a_lines[a_index]
 
1236
                    yield 'killed-b', self.lines_a[a_index]
1213
1237
            for b_index in range(last_j, j):
1214
1238
                if b_index in new_b:
1215
 
                    cause = 'new-b'
 
1239
                    if b_index in killed_a:
 
1240
                        yield 'conflicted-b', self.lines_b[a_index]
 
1241
                    else:
 
1242
                        yield 'new-b', self.lines_b[b_index]
1216
1243
                else:
1217
 
                    cause = 'killed-a'
1218
 
                yield cause, b_lines[b_index]
 
1244
                    yield 'killed-a', self.lines_b[b_index]
1219
1245
            # handle common lines
1220
1246
            for a_index in range(i, i+n):
1221
 
                yield 'unchanged', a_lines[a_index]
 
1247
                yield 'unchanged', self.lines_a[a_index]
1222
1248
            last_i = i+n
1223
1249
            last_j = j+n
1224
1250
 
1227
1253
 
1228
1254
        See SequenceMatcher.get_matching_blocks
1229
1255
        """
 
1256
        cached = self._cached_matching_blocks.get((left_revision,
 
1257
                                                   right_revision))
 
1258
        if cached is not None:
 
1259
            return cached
1230
1260
        if self._last_lines_revision_id == left_revision:
1231
1261
            left_lines = self._last_lines
1232
1262
        else:
1255
1285
            last_j = j + n
1256
1286
        return unique_left, unique_right
1257
1287
 
 
1288
    @staticmethod
 
1289
    def _subtract_plans(old_plan, new_plan):
 
1290
        """Remove changes from new_plan that came from old_plan.
 
1291
 
 
1292
        It is assumed that the difference between the old_plan and new_plan
 
1293
        is their choice of 'b' text.
 
1294
 
 
1295
        All lines from new_plan that differ from old_plan are emitted
 
1296
        verbatim.  All lines from new_plan that match old_plan but are
 
1297
        not about the 'b' revision are emitted verbatim.
 
1298
 
 
1299
        Lines that match and are about the 'b' revision are the lines we
 
1300
        don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
 
1301
        is skipped entirely.
 
1302
        """
 
1303
        matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
 
1304
                                                       new_plan)
 
1305
        last_j = 0
 
1306
        for i, j, n in matcher.get_matching_blocks():
 
1307
            for jj in range(last_j, j):
 
1308
                yield new_plan[jj]
 
1309
            for jj in range(j, j+n):
 
1310
                plan_line = new_plan[jj]
 
1311
                if plan_line[0] == 'new-b':
 
1312
                    pass
 
1313
                elif plan_line[0] == 'killed-b':
 
1314
                    yield 'unchanged', plan_line[1]
 
1315
                else:
 
1316
                    yield plan_line
 
1317
            last_j = j + n
 
1318
 
 
1319
 
 
1320
class _PlanMerge(_PlanMergeBase):
 
1321
    """Plan an annotate merge using on-the-fly annotation"""
 
1322
 
 
1323
    def __init__(self, a_rev, b_rev, vf):
 
1324
       _PlanMergeBase.__init__(self, a_rev, b_rev, vf)
 
1325
       a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
 
1326
       b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
 
1327
       self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
 
1328
 
 
1329
    def _determine_status(self, revision_id, unique_line_numbers):
 
1330
        """Determines the status unique lines versus all lcas.
 
1331
 
 
1332
        Basically, determines why the line is unique to this revision.
 
1333
 
 
1334
        A line may be determined new or killed, but not both.
 
1335
 
 
1336
        :param revision_id: The id of the revision in which the lines are
 
1337
            unique
 
1338
        :param unique_line_numbers: The line numbers of unique lines.
 
1339
        :return a tuple of (new_this, killed_other):
 
1340
        """
 
1341
        new = self._find_new(revision_id)
 
1342
        killed = set(unique_line_numbers).difference(new)
 
1343
        return new, killed
 
1344
 
1258
1345
    def _find_new(self, version_id):
1259
1346
        """Determine which lines are new in the ancestry of this version.
1260
1347
 
1281
1368
                new.intersection_update(result)
1282
1369
        return new
1283
1370
 
1284
 
    @staticmethod
1285
 
    def _subtract_plans(old_plan, new_plan):
1286
 
        matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1287
 
                                                       new_plan)
1288
 
        last_j = 0
1289
 
        for i, j, n in matcher.get_matching_blocks():
1290
 
            for jj in range(last_j, j):
1291
 
                yield new_plan[jj]
1292
 
            for jj in range(j, j+n):
1293
 
                plan_line = new_plan[jj]
1294
 
                if plan_line[0] == 'new-b':
1295
 
                    pass
1296
 
                elif plan_line[0] == 'killed-b':
1297
 
                    yield 'unchanged', plan_line[1]
1298
 
                else:
1299
 
                    yield plan_line
1300
 
            last_j = j + n
 
1371
 
 
1372
class _PlanLCAMerge(_PlanMergeBase):
 
1373
    """
 
1374
    This merge algorithm differs from _PlanMerge in that:
 
1375
    1. comparisons are done against LCAs only
 
1376
    2. cases where a contested line is new versus one LCA but old versus
 
1377
       another are marked as conflicts, by emitting the line as conflicted-a
 
1378
       or conflicted-b.
 
1379
 
 
1380
    This is faster, and hopefully produces more useful output.
 
1381
    """
 
1382
 
 
1383
    def __init__(self, a_rev, b_rev, vf, graph):
 
1384
        _PlanMergeBase.__init__(self, a_rev, b_rev, vf)
 
1385
        self.lcas = graph.find_lca(a_rev, b_rev)
 
1386
        for lca in self.lcas:
 
1387
            lca_lines = self.vf.get_lines(lca)
 
1388
            matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
 
1389
                                                           lca_lines)
 
1390
            blocks = list(matcher.get_matching_blocks())
 
1391
            self._cached_matching_blocks[(a_rev, lca)] = blocks
 
1392
            matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
 
1393
                                                           lca_lines)
 
1394
            blocks = list(matcher.get_matching_blocks())
 
1395
            self._cached_matching_blocks[(b_rev, lca)] = blocks
 
1396
 
 
1397
    def _determine_status(self, revision_id, unique_line_numbers):
 
1398
        """Determines the status unique lines versus all lcas.
 
1399
 
 
1400
        Basically, determines why the line is unique to this revision.
 
1401
 
 
1402
        A line may be determined new, killed, or both.
 
1403
 
 
1404
        If a line is determined new, that means it was not present in at least
 
1405
        one LCA, and is not present in the other merge revision.
 
1406
 
 
1407
        If a line is determined killed, that means the line was present in
 
1408
        at least one LCA.
 
1409
 
 
1410
        If a line is killed and new, this indicates that the two merge
 
1411
        revisions contain differing conflict resolutions.
 
1412
        :param revision_id: The id of the revision in which the lines are
 
1413
            unique
 
1414
        :param unique_line_numbers: The line numbers of unique lines.
 
1415
        :return a tuple of (new_this, killed_other):
 
1416
        """
 
1417
        new = set()
 
1418
        killed = set()
 
1419
        unique_line_numbers = set(unique_line_numbers)
 
1420
        for lca in self.lcas:
 
1421
            blocks = self._get_matching_blocks(revision_id, lca)
 
1422
            unique_vs_lca, _ignored = self._unique_lines(blocks)
 
1423
            new.update(unique_line_numbers.intersection(unique_vs_lca))
 
1424
            killed.update(unique_line_numbers.difference(unique_vs_lca))
 
1425
        return new, killed