← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Andrew Bennetts
  • Date: 2010-10-13 00:26:41 UTC
  • mto: This revision was merged to the branch mainline in revision 5498.
  • Revision ID: andrew.bennetts@canonical.com-20101013002641-9tlh9k89mlj1666m
Keep docs-plain working.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007-2010 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
23
23
    revision,
24
24
    trace,
25
25
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
26
27
 
27
28
STEP_UNIQUE_SEARCHER_EVERY = 5
28
29
 
63
64
        ancestry = self.ancestry
64
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
65
66
 
 
67
@deprecated_function(deprecated_in((1, 16, 0)))
 
68
def _StackedParentsProvider(*args, **kwargs):
 
69
    return StackedParentsProvider(*args, **kwargs)
66
70
 
67
71
class StackedParentsProvider(object):
68
72
    """A parents provider which stacks (or unions) multiple providers.
179
183
            self.missing_keys.add(key)
180
184
 
181
185
 
182
 
class CallableToParentsProviderAdapter(object):
183
 
    """A parents provider that adapts any callable to the parents provider API.
184
 
 
185
 
    i.e. it accepts calls to self.get_parent_map and relays them to the
186
 
    callable it was constructed with.
187
 
    """
188
 
 
189
 
    def __init__(self, a_callable):
190
 
        self.callable = a_callable
191
 
 
192
 
    def __repr__(self):
193
 
        return "%s(%r)" % (self.__class__.__name__, self.callable)
194
 
 
195
 
    def get_parent_map(self, keys):
196
 
        return self.callable(keys)
197
 
 
198
 
 
199
186
class Graph(object):
200
187
    """Provide incremental access to revision graphs.
201
188
 
250
237
        common ancestor of all border ancestors, because this shows that it
251
238
        cannot be a descendant of any border ancestor.
252
239
 
253
 
        The scaling of this operation should be proportional to:
254
 
 
 
240
        The scaling of this operation should be proportional to
255
241
        1. The number of uncommon ancestors
256
242
        2. The number of border ancestors
257
243
        3. The length of the shortest path between a border ancestor and an
389
375
 
390
376
        :param unique_revision: The revision_id whose ancestry we are
391
377
            interested in.
392
 
            (XXX: Would this API be better if we allowed multiple revisions on
393
 
            to be searched here?)
 
378
            XXX: Would this API be better if we allowed multiple revisions on
 
379
                 to be searched here?
394
380
        :param common_revisions: Revision_ids of ancestries to exclude.
395
381
        :return: A set of revisions in the ancestry of unique_revision
396
382
        """
1550
1536
            return revs, ghosts
1551
1537
 
1552
1538
 
1553
 
class AbstractSearchResult(object):
1554
 
    """The result of a search, describing a set of keys.
1555
 
    
1556
 
    Search results are typically used as the 'fetch_spec' parameter when
1557
 
    fetching revisions.
1558
 
 
1559
 
    :seealso: AbstractSearch
1560
 
    """
1561
 
 
1562
 
    def get_recipe(self):
1563
 
        """Return a recipe that can be used to replay this search.
1564
 
 
1565
 
        The recipe allows reconstruction of the same results at a later date.
1566
 
 
1567
 
        :return: A tuple of `(search_kind_str, *details)`.  The details vary by
1568
 
            kind of search result.
1569
 
        """
1570
 
        raise NotImplementedError(self.get_recipe)
1571
 
 
1572
 
    def get_network_struct(self):
1573
 
        """Return a tuple that can be transmitted via the HPSS protocol."""
1574
 
        raise NotImplementedError(self.get_network_struct)
1575
 
 
1576
 
    def get_keys(self):
1577
 
        """Return the keys found in this search.
1578
 
 
1579
 
        :return: A set of keys.
1580
 
        """
1581
 
        raise NotImplementedError(self.get_keys)
1582
 
 
1583
 
    def is_empty(self):
1584
 
        """Return false if the search lists 1 or more revisions."""
1585
 
        raise NotImplementedError(self.is_empty)
1586
 
 
1587
 
    def refine(self, seen, referenced):
1588
 
        """Create a new search by refining this search.
1589
 
 
1590
 
        :param seen: Revisions that have been satisfied.
1591
 
        :param referenced: Revision references observed while satisfying some
1592
 
            of this search.
1593
 
        :return: A search result.
1594
 
        """
1595
 
        raise NotImplementedError(self.refine)
1596
 
 
1597
 
 
1598
 
class AbstractSearch(object):
1599
 
    """A search that can be executed, producing a search result.
1600
 
 
1601
 
    :seealso: AbstractSearchResult
1602
 
    """
1603
 
 
1604
 
    def execute(self):
1605
 
        """Construct a network-ready search result from this search description.
1606
 
 
1607
 
        This may take some time to search repositories, etc.
1608
 
 
1609
 
        :return: A search result (an object that implements
1610
 
            AbstractSearchResult's API).
1611
 
        """
1612
 
        raise NotImplementedError(self.execute)
1613
 
 
1614
 
 
1615
 
class SearchResult(AbstractSearchResult):
 
1539
class SearchResult(object):
1616
1540
    """The result of a breadth first search.
1617
1541
 
1618
1542
    A SearchResult provides the ability to reconstruct the search or access a
1633
1557
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1634
1558
        self._keys = frozenset(keys)
1635
1559
 
1636
 
    def __repr__(self):
1637
 
        kind, start_keys, exclude_keys, key_count = self._recipe
1638
 
        if len(start_keys) > 5:
1639
 
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1640
 
        else:
1641
 
            start_keys_repr = repr(start_keys)
1642
 
        if len(exclude_keys) > 5:
1643
 
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1644
 
        else:
1645
 
            exclude_keys_repr = repr(exclude_keys)
1646
 
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1647
 
            kind, start_keys_repr, exclude_keys_repr, key_count)
1648
 
 
1649
1560
    def get_recipe(self):
1650
1561
        """Return a recipe that can be used to replay this search.
1651
1562
 
1669
1580
        """
1670
1581
        return self._recipe
1671
1582
 
1672
 
    def get_network_struct(self):
1673
 
        start_keys = ' '.join(self._recipe[1])
1674
 
        stop_keys = ' '.join(self._recipe[2])
1675
 
        count = str(self._recipe[3])
1676
 
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1677
 
 
1678
1583
    def get_keys(self):
1679
1584
        """Return the keys found in this search.
1680
1585
 
1712
1617
        return SearchResult(pending_refs, exclude, count, keys)
1713
1618
 
1714
1619
 
1715
 
class PendingAncestryResult(AbstractSearchResult):
 
1620
class PendingAncestryResult(object):
1716
1621
    """A search result that will reconstruct the ancestry for some graph heads.
1717
1622
 
1718
1623
    Unlike SearchResult, this doesn't hold the complete search result in
1729
1634
        self.heads = frozenset(heads)
1730
1635
        self.repo = repo
1731
1636
 
1732
 
    def __repr__(self):
1733
 
        if len(self.heads) > 5:
1734
 
            heads_repr = repr(list(self.heads)[:5])[:-1]
1735
 
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1736
 
        else:
1737
 
            heads_repr = repr(self.heads)
1738
 
        return '<%s heads:%s repo:%r>' % (
1739
 
            self.__class__.__name__, heads_repr, self.repo)
1740
 
 
1741
1637
    def get_recipe(self):
1742
1638
        """Return a recipe that can be used to replay this search.
1743
1639
 
1751
1647
        """
1752
1648
        return ('proxy-search', self.heads, set(), -1)
1753
1649
 
1754
 
    def get_network_struct(self):
1755
 
        parts = ['ancestry-of']
1756
 
        parts.extend(self.heads)
1757
 
        return parts
1758
 
 
1759
1650
    def get_keys(self):
1760
1651
        """See SearchResult.get_keys.
1761
1652
 
1788
1679
        return PendingAncestryResult(referenced - seen, self.repo)
1789
1680
 
1790
1681
 
1791
 
class EmptySearchResult(AbstractSearchResult):
1792
 
    """An empty search result."""
1793
 
 
1794
 
    def is_empty(self):
1795
 
        return True
1796
 
    
1797
 
 
1798
 
class EverythingResult(AbstractSearchResult):
1799
 
    """A search result that simply requests everything in the repository."""
1800
 
 
1801
 
    def __init__(self, repo):
1802
 
        self._repo = repo
1803
 
 
1804
 
    def __repr__(self):
1805
 
        return '%s(%r)' % (self.__class__.__name__, self._repo)
1806
 
 
1807
 
    def get_recipe(self):
1808
 
        raise NotImplementedError(self.get_recipe)
1809
 
 
1810
 
    def get_network_struct(self):
1811
 
        return ('everything',)
1812
 
 
1813
 
    def get_keys(self):
1814
 
        if 'evil' in debug.debug_flags:
1815
 
            from bzrlib import remote
1816
 
            if isinstance(self._repo, remote.RemoteRepository):
1817
 
                # warn developers (not users) not to do this
1818
 
                trace.mutter_callsite(
1819
 
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1820
 
        return self._repo.all_revision_ids()
1821
 
 
1822
 
    def is_empty(self):
1823
 
        # It's ok for this to wrongly return False: the worst that can happen
1824
 
        # is that RemoteStreamSource will initiate a get_stream on an empty
1825
 
        # repository.  And almost all repositories are non-empty.
1826
 
        return False
1827
 
 
1828
 
    def refine(self, seen, referenced):
1829
 
        heads = set(self._repo.all_revision_ids())
1830
 
        heads.difference_update(seen)
1831
 
        heads.update(referenced)
1832
 
        return PendingAncestryResult(heads, self._repo)
1833
 
 
1834
 
 
1835
 
class EverythingNotInOther(AbstractSearch):
1836
 
    """Find all revisions in that are in one repo but not the other."""
1837
 
 
1838
 
    def __init__(self, to_repo, from_repo, find_ghosts=False):
1839
 
        self.to_repo = to_repo
1840
 
        self.from_repo = from_repo
1841
 
        self.find_ghosts = find_ghosts
1842
 
 
1843
 
    def execute(self):
1844
 
        return self.to_repo.search_missing_revision_ids(
1845
 
            self.from_repo, find_ghosts=self.find_ghosts)
1846
 
 
1847
 
 
1848
 
class NotInOtherForRevs(AbstractSearch):
1849
 
    """Find all revisions missing in one repo for a some specific heads."""
1850
 
 
1851
 
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1852
 
            find_ghosts=False, limit=None):
1853
 
        """Constructor.
1854
 
 
1855
 
        :param required_ids: revision IDs of heads that must be found, or else
1856
 
            the search will fail with NoSuchRevision.  All revisions in their
1857
 
            ancestry not already in the other repository will be included in
1858
 
            the search result.
1859
 
        :param if_present_ids: revision IDs of heads that may be absent in the
1860
 
            source repository.  If present, then their ancestry not already
1861
 
            found in other will be included in the search result.
1862
 
        :param limit: maximum number of revisions to fetch
1863
 
        """
1864
 
        self.to_repo = to_repo
1865
 
        self.from_repo = from_repo
1866
 
        self.find_ghosts = find_ghosts
1867
 
        self.required_ids = required_ids
1868
 
        self.if_present_ids = if_present_ids
1869
 
        self.limit = limit
1870
 
 
1871
 
    def __repr__(self):
1872
 
        if len(self.required_ids) > 5:
1873
 
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1874
 
        else:
1875
 
            reqd_revs_repr = repr(self.required_ids)
1876
 
        if self.if_present_ids and len(self.if_present_ids) > 5:
1877
 
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1878
 
        else:
1879
 
            ifp_revs_repr = repr(self.if_present_ids)
1880
 
 
1881
 
        return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
1882
 
                "limit:%r>") % (
1883
 
                self.__class__.__name__, self.from_repo, self.to_repo,
1884
 
                self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
1885
 
                self.limit)
1886
 
 
1887
 
    def execute(self):
1888
 
        return self.to_repo.search_missing_revision_ids(
1889
 
            self.from_repo, revision_ids=self.required_ids,
1890
 
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
1891
 
            limit=self.limit)
1892
 
 
1893
 
 
1894
1682
def collapse_linear_regions(parent_map):
1895
1683
    """Collapse regions of the graph that are 'linear'.
1896
1684
 
1980
1768
        return set([h[0] for h in head_keys])
1981
1769
 
1982
1770
    def merge_sort(self, tip_revision):
1983
 
        nodes = self._graph.merge_sort((tip_revision,))
1984
 
        for node in nodes:
1985
 
            node.key = node.key[0]
1986
 
        return nodes
1987
 
 
1988
 
    def add_node(self, revision, parents):
1989
 
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1771
        return self._graph.merge_sort((tip_revision,))
1990
1772
 
1991
1773
 
1992
1774
_counters = [0,0,0,0,0,0,0]