/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: John Arbash Meinel
  • Date: 2008-07-09 23:21:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080709232113-qvkxigm18om27i39
Switch to the get_parent_map design I had settled on.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
27
27
    patiencediff,
28
28
    registry,
29
29
    revision as _mod_revision,
 
30
    tsort,
30
31
    )
31
32
from bzrlib.branch import Branch
32
33
from bzrlib.conflicts import ConflictList, Conflict
1423
1424
    def _find_recursive_lcas(self):
1424
1425
        """Find all the ancestors back to a unique lca"""
1425
1426
        cur_ancestors = (self.a_key, self.b_key)
1426
 
        ancestor_keys = [cur_ancestors]
1427
1427
        # graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1428
 
        # rather than a key tuple, but everything else expects tuples, so we
1429
 
        # adapt the result to be normalized, this way we don't have to special
1430
 
        # case _get_interesting_texts, etc.
1431
 
        null_key = self._key_prefix + (NULL_REVISION,)
 
1428
        # rather than a key tuple. We will just map that directly to no common
 
1429
        # ancestors.
 
1430
        parent_map = {}
1432
1431
        while True:
1433
1432
            next_lcas = self.graph.find_lca(*cur_ancestors)
1434
 
            ancestor_keys.append(next_lcas)
 
1433
            # Map a plain NULL_REVISION to a simple no-ancestors
 
1434
            if next_lcas == set([NULL_REVISION]):
 
1435
                next_lcas = ()
 
1436
            for rev_key in cur_ancestors:
 
1437
                # These don't need to be properly sorted, because
 
1438
                # weave.add_lines() just treats them as a set.
 
1439
                parent_map[rev_key] = tuple(next_lcas)
1435
1440
            if len(next_lcas) == 0:
1436
 
                ancestor_keys[-1] = [null_key]
1437
 
                self.vf.add_lines(null_key, [], [])
1438
1441
                break
1439
1442
            elif len(next_lcas) == 1:
1440
 
                if next_lcas == set([NULL_REVISION]):
1441
 
                    ancestor_keys[-1] = [null_key]
1442
 
                    self.vf.add_lines(null_key, [], [])
 
1443
                parent_map[next_lcas.pop()] = ()
1443
1444
                break
1444
1445
            cur_ancestors = next_lcas
1445
 
        ancestor_keys.reverse()
1446
 
        return ancestor_keys
 
1446
        return parent_map
1447
1447
 
1448
 
    def _get_interesting_texts(self, lca_keys):
 
1448
    def _get_interesting_texts(self, parent_map):
1449
1449
        """Return a dict of texts we are interested in.
1450
1450
 
1451
1451
        Note that the input is in key tuples, but the output is in plain
1452
1452
        revision ids.
1453
1453
 
1454
 
        :param lca_keys: The output from _find_recursive_lcas
 
1454
        :param parent_map: The output from _find_recursive_lcas
1455
1455
        :return: A dict of {'revision_id':lines} as returned by
1456
1456
            _PlanMergeBase.get_lines()
1457
1457
        """
1458
 
        all_revision_ids = set()
1459
 
        # lcas are in keys, but get_lines works in revision_ids
1460
 
        for ancestor_keys in lca_keys:
1461
 
            all_revision_ids.update([key[-1] for key in ancestor_keys])
1462
 
        all_revision_ids.add(self.a_rev)
1463
 
        all_revision_ids.add(self.b_rev)
 
1458
        all_revision_keys = set(parent_map)
 
1459
        all_revision_keys.add(self.a_key)
 
1460
        all_revision_keys.add(self.b_key)
1464
1461
 
1465
 
        all_texts = self.get_lines(all_revision_ids)
 
1462
        # Everything else is in 'keys' but get_lines is in 'revision_ids'
 
1463
        all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1466
1464
        return all_texts
1467
1465
 
1468
1466
    def _build_weave(self):
1469
1467
        from bzrlib import weave
1470
1468
        self._weave = weave.Weave(weave_name='in_memory_weave',
1471
1469
                                  allow_reserved=True)
1472
 
        lca_keys = self._find_recursive_lcas()
1473
 
 
1474
 
        all_texts = self._get_interesting_texts(lca_keys)
1475
 
 
1476
 
        last_parents = ()
1477
 
        for ancestor_keys in lca_keys:
1478
 
            for ancestor_key in ancestor_keys:
1479
 
                ancestor = ancestor_key[-1]
1480
 
                if self._weave.has_version(ancestor):
1481
 
                    # Most likely this happened because one node purely
1482
 
                    # dominated another in the per-file graph. That is okay, we
1483
 
                    # already have it in the weave, and the plan should be very
1484
 
                    # straightforward.
1485
 
                    continue
1486
 
                self._weave.add_lines(ancestor, last_parents,
1487
 
                                      all_texts[ancestor])
1488
 
            last_parents = [a[-1] for a in ancestor_keys]
 
1470
        parent_map = self._find_recursive_lcas()
 
1471
 
 
1472
        all_texts = self._get_interesting_texts(parent_map)
 
1473
 
 
1474
        # Note: Unfortunately, the order given by topo_sort will effect the
 
1475
        # ordering resolution in the output. Specifically, if you add A then B,
 
1476
        # then in the output text A lines will show up before B lines. And, of
 
1477
        # course, topo_sort doesn't guarantee any real ordering.
 
1478
        # Maybe we want to use merge_sorted? Though we would need to add a
 
1479
        # 'pseudo' node for the tip.
 
1480
        for key in tsort.topo_sort(parent_map):
 
1481
            parent_keys = parent_map[key]
 
1482
            revision_id = key[-1]
 
1483
            parent_ids = [k[-1] for k in parent_keys]
 
1484
            self._weave.add_lines(revision_id, parent_ids,
 
1485
                                  all_texts[revision_id])
1489
1486
 
1490
1487
    def plan_merge(self):
1491
1488
        """Generate a 'plan' for merging the two revisions.