← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
64
64
        ancestry = self.ancestry
65
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
66
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
67
 
71
68
class StackedParentsProvider(object):
72
69
    """A parents provider which stacks (or unions) multiple providers.
258
255
        right = searchers[1].seen
259
256
        return (left.difference(right), right.difference(left))
260
257
 
 
258
    def find_descendants(self, old_key, new_key):
 
259
        """Find descendants of old_key that are ancestors of new_key."""
 
260
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
261
            old_key, new_key))
 
262
        graph = Graph(DictParentsProvider(child_map))
 
263
        searcher = graph._make_breadth_first_searcher([old_key])
 
264
        list(searcher)
 
265
        return searcher.seen
 
266
 
 
267
    def _find_descendant_ancestors(self, old_key, new_key):
 
268
        """Find ancestors of new_key that may be descendants of old_key."""
 
269
        stop = self._make_breadth_first_searcher([old_key])
 
270
        descendants = self._make_breadth_first_searcher([new_key])
 
271
        for revisions in descendants:
 
272
            old_stop = stop.seen.intersection(revisions)
 
273
            descendants.stop_searching_any(old_stop)
 
274
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
275
            descendants.stop_searching_any(seen_stop)
 
276
        return descendants.seen.difference(stop.seen)
 
277
 
 
278
    def get_child_map(self, keys):
 
279
        """Get a mapping from parents to children of the specified keys.
 
280
 
 
281
        This is simply the inversion of get_parent_map.  Only supplied keys
 
282
        will be discovered as children.
 
283
        :return: a dict of key:child_list for keys.
 
284
        """
 
285
        parent_map = self._parents_provider.get_parent_map(keys)
 
286
        parent_child = {}
 
287
        for child, parents in sorted(parent_map.items()):
 
288
            for parent in parents:
 
289
                parent_child.setdefault(parent, []).append(child)
 
290
        return parent_child
 
291
 
261
292
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
293
        """Find the left-hand distance to the NULL_REVISION.
263
294
 
862
893
                stop.add(parent_id)
863
894
        return found
864
895
 
 
896
    def find_lefthand_merger(self, merged_key, tip_key):
 
897
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
898
 
 
899
        We do this by first finding the descendants of merged_key, then
 
900
        walking through the lefthand ancestry of tip_key until we find a key
 
901
        that doesn't descend from merged_key.  Its child is the key that
 
902
        merged merged_key.
 
903
 
 
904
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
905
            merged_key if it is a lefthand ancestor of tip_key.
 
906
            None if no ancestor of tip_key merged merged_key.
 
907
        """
 
908
        descendants = self.find_descendants(merged_key, tip_key)
 
909
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
910
        last_candidate = None
 
911
        for candidate in candidate_iterator:
 
912
            if candidate not in descendants:
 
913
                return last_candidate
 
914
            last_candidate = candidate
 
915
 
865
916
    def find_unique_lca(self, left_revision, right_revision,
866
917
                        count_steps=False):
867
918
        """Find a unique LCA.
919
970
                yield (ghost, None)
920
971
            pending = next_pending
921
972
 
 
973
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
974
        if stop_keys is None:
 
975
            stop_keys = ()
 
976
        next_key = start_key
 
977
        def get_parents(key):
 
978
            try:
 
979
                return self._parents_provider.get_parent_map([key])[key]
 
980
            except KeyError:
 
981
                raise errors.RevisionNotPresent(next_key, self)
 
982
        while True:
 
983
            if next_key in stop_keys:
 
984
                return
 
985
            parents = get_parents(next_key)
 
986
            yield next_key
 
987
            if len(parents) == 0:
 
988
                return
 
989
            else:
 
990
                next_key = parents[0]
 
991
 
922
992
    def iter_topo_order(self, revisions):
923
993
        """Iterate through the input revisions in topological order.
924
994
 
1463
1533
            return revs, ghosts
1464
1534
 
1465
1535
 
1466
 
class SearchResult(object):
 
1536
class AbstractSearchResult(object):
 
1537
    """The result of a search, describing a set of keys.
 
1538
    
 
1539
    Search results are typically used as the 'fetch_spec' parameter when
 
1540
    fetching revisions.
 
1541
 
 
1542
    :seealso: AbstractSearch
 
1543
    """
 
1544
 
 
1545
    def get_recipe(self):
 
1546
        """Return a recipe that can be used to replay this search.
 
1547
 
 
1548
        The recipe allows reconstruction of the same results at a later date.
 
1549
 
 
1550
        :return: A tuple of (search_kind_str, *details).  The details vary by
 
1551
            kind of search result.
 
1552
        """
 
1553
        raise NotImplementedError(self.get_recipe)
 
1554
 
 
1555
    def get_network_struct(self):
 
1556
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1557
        raise NotImplementedError(self.get_network_struct)
 
1558
 
 
1559
    def get_keys(self):
 
1560
        """Return the keys found in this search.
 
1561
 
 
1562
        :return: A set of keys.
 
1563
        """
 
1564
        raise NotImplementedError(self.get_keys)
 
1565
 
 
1566
    def is_empty(self):
 
1567
        """Return false if the search lists 1 or more revisions."""
 
1568
        raise NotImplementedError(self.is_empty)
 
1569
 
 
1570
    def refine(self, seen, referenced):
 
1571
        """Create a new search by refining this search.
 
1572
 
 
1573
        :param seen: Revisions that have been satisfied.
 
1574
        :param referenced: Revision references observed while satisfying some
 
1575
            of this search.
 
1576
        :return: A search result.
 
1577
        """
 
1578
        raise NotImplementedError(self.refine)
 
1579
 
 
1580
 
 
1581
class AbstractSearch(object):
 
1582
    """A search that can be executed, producing a search result.
 
1583
 
 
1584
    :seealso: AbstractSearchResult
 
1585
    """
 
1586
 
 
1587
    def execute(self):
 
1588
        """Construct a network-ready search result from this search description.
 
1589
 
 
1590
        This may take some time to search repositories, etc.
 
1591
 
 
1592
        :return: A search result (an object that implements
 
1593
            AbstractSearchResult's API).
 
1594
        """
 
1595
        raise NotImplementedError(self.execute)
 
1596
 
 
1597
 
 
1598
class SearchResult(AbstractSearchResult):
1467
1599
    """The result of a breadth first search.
1468
1600
 
1469
1601
    A SearchResult provides the ability to reconstruct the search or access a
1484
1616
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1617
        self._keys = frozenset(keys)
1486
1618
 
 
1619
    def __repr__(self):
 
1620
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1621
        if len(start_keys) > 5:
 
1622
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1623
        else:
 
1624
            start_keys_repr = repr(start_keys)
 
1625
        if len(exclude_keys) > 5:
 
1626
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1627
        else:
 
1628
            exclude_keys_repr = repr(exclude_keys)
 
1629
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1630
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1631
 
1487
1632
    def get_recipe(self):
1488
1633
        """Return a recipe that can be used to replay this search.
1489
1634
 
1507
1652
        """
1508
1653
        return self._recipe
1509
1654
 
 
1655
    def get_network_struct(self):
 
1656
        start_keys = ' '.join(self._recipe[1])
 
1657
        stop_keys = ' '.join(self._recipe[2])
 
1658
        count = str(self._recipe[3])
 
1659
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1660
 
1510
1661
    def get_keys(self):
1511
1662
        """Return the keys found in this search.
1512
1663
 
1544
1695
        return SearchResult(pending_refs, exclude, count, keys)
1545
1696
 
1546
1697
 
1547
 
class PendingAncestryResult(object):
 
1698
class PendingAncestryResult(AbstractSearchResult):
1548
1699
    """A search result that will reconstruct the ancestry for some graph heads.
1549
1700
 
1550
1701
    Unlike SearchResult, this doesn't hold the complete search result in
1561
1712
        self.heads = frozenset(heads)
1562
1713
        self.repo = repo
1563
1714
 
 
1715
    def __repr__(self):
 
1716
        if len(self.heads) > 5:
 
1717
            heads_repr = repr(list(self.heads)[:5])[:-1]
 
1718
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
 
1719
        else:
 
1720
            heads_repr = repr(self.heads)
 
1721
        return '<%s heads:%s repo:%r>' % (
 
1722
            self.__class__.__name__, heads_repr, self.repo)
 
1723
 
1564
1724
    def get_recipe(self):
1565
1725
        """Return a recipe that can be used to replay this search.
1566
1726
 
1574
1734
        """
1575
1735
        return ('proxy-search', self.heads, set(), -1)
1576
1736
 
 
1737
    def get_network_struct(self):
 
1738
        parts = ['ancestry-of']
 
1739
        parts.extend(self.heads)
 
1740
        return parts
 
1741
 
1577
1742
    def get_keys(self):
1578
1743
        """See SearchResult.get_keys.
1579
1744
 
1606
1771
        return PendingAncestryResult(referenced - seen, self.repo)
1607
1772
 
1608
1773
 
 
1774
class EmptySearchResult(AbstractSearchResult):
 
1775
    """An empty search result."""
 
1776
 
 
1777
    def is_empty(self):
 
1778
        return True
 
1779
    
 
1780
 
 
1781
class EverythingResult(AbstractSearchResult):
 
1782
    """A search result that simply requests everything in the repository."""
 
1783
 
 
1784
    def __init__(self, repo):
 
1785
        self._repo = repo
 
1786
 
 
1787
    def __repr__(self):
 
1788
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1789
 
 
1790
    def get_recipe(self):
 
1791
        raise NotImplementedError(self.get_recipe)
 
1792
 
 
1793
    def get_network_struct(self):
 
1794
        return ('everything',)
 
1795
 
 
1796
    def get_keys(self):
 
1797
        if 'evil' in debug.debug_flags:
 
1798
            from bzrlib import remote
 
1799
            if isinstance(self._repo, remote.RemoteRepository):
 
1800
                # warn developers (not users) not to do this
 
1801
                trace.mutter_callsite(
 
1802
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1803
        return self._repo.all_revision_ids()
 
1804
 
 
1805
    def is_empty(self):
 
1806
        # It's ok for this to wrongly return False: the worst that can happen
 
1807
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1808
        # repository.  And almost all repositories are non-empty.
 
1809
        return False
 
1810
 
 
1811
    def refine(self, seen, referenced):
 
1812
        heads = set(self._repo.all_revision_ids())
 
1813
        heads.difference_update(seen)
 
1814
        heads.update(referenced)
 
1815
        return PendingAncestryResult(heads, self._repo)
 
1816
 
 
1817
 
 
1818
class EverythingNotInOther(AbstractSearch):
 
1819
    """Find all revisions in that are in one repo but not the other."""
 
1820
 
 
1821
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1822
        self.to_repo = to_repo
 
1823
        self.from_repo = from_repo
 
1824
        self.find_ghosts = find_ghosts
 
1825
 
 
1826
    def execute(self):
 
1827
        return self.to_repo.search_missing_revision_ids(
 
1828
            self.from_repo, find_ghosts=self.find_ghosts)
 
1829
 
 
1830
 
 
1831
class NotInOtherForRevs(AbstractSearch):
 
1832
    """Find all revisions missing in one repo for a some specific heads."""
 
1833
 
 
1834
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1835
            find_ghosts=False):
 
1836
        """Constructor.
 
1837
 
 
1838
        :param required_ids: revision IDs of heads that must be found, or else
 
1839
            the search will fail with NoSuchRevision.  All revisions in their
 
1840
            ancestry not already in the other repository will be included in
 
1841
            the search result.
 
1842
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1843
            source repository.  If present, then their ancestry not already
 
1844
            found in other will be included in the search result.
 
1845
        """
 
1846
        self.to_repo = to_repo
 
1847
        self.from_repo = from_repo
 
1848
        self.find_ghosts = find_ghosts
 
1849
        self.required_ids = required_ids
 
1850
        self.if_present_ids = if_present_ids
 
1851
 
 
1852
    def __repr__(self):
 
1853
        if len(self.required_ids) > 5:
 
1854
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1855
        else:
 
1856
            reqd_revs_repr = repr(self.required_ids)
 
1857
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1858
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1859
        else:
 
1860
            ifp_revs_repr = repr(self.if_present_ids)
 
1861
 
 
1862
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1863
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1864
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
 
1865
 
 
1866
    def execute(self):
 
1867
        return self.to_repo.search_missing_revision_ids(
 
1868
            self.from_repo, revision_ids=self.required_ids,
 
1869
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
 
1870
 
 
1871
 
1609
1872
def collapse_linear_regions(parent_map):
1610
1873
    """Collapse regions of the graph that are 'linear'.
1611
1874
 
1697
1960
    def merge_sort(self, tip_revision):
1698
1961
        return self._graph.merge_sort((tip_revision,))
1699
1962
 
 
1963
    def add_node(self, revision, parents):
 
1964
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1965
 
1700
1966
 
1701
1967
_counters = [0,0,0,0,0,0,0]
1702
1968
try: