← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Move all features to bzrlib.tests.features in 2.5

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
23
23
    revision,
24
24
    trace,
25
25
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
26
 
28
27
STEP_UNIQUE_SEARCHER_EVERY = 5
29
28
 
64
63
        ancestry = self.ancestry
65
64
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
65
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
66
 
71
67
class StackedParentsProvider(object):
72
68
    """A parents provider which stacks (or unions) multiple providers.
183
179
            self.missing_keys.add(key)
184
180
 
185
181
 
 
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
 
186
199
class Graph(object):
187
200
    """Provide incremental access to revision graphs.
188
201
 
237
250
        common ancestor of all border ancestors, because this shows that it
238
251
        cannot be a descendant of any border ancestor.
239
252
 
240
 
        The scaling of this operation should be proportional to
 
253
        The scaling of this operation should be proportional to:
 
254
 
241
255
        1. The number of uncommon ancestors
242
256
        2. The number of border ancestors
243
257
        3. The length of the shortest path between a border ancestor and an
258
272
        right = searchers[1].seen
259
273
        return (left.difference(right), right.difference(left))
260
274
 
 
275
    def find_descendants(self, old_key, new_key):
 
276
        """Find descendants of old_key that are ancestors of new_key."""
 
277
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
278
            old_key, new_key))
 
279
        graph = Graph(DictParentsProvider(child_map))
 
280
        searcher = graph._make_breadth_first_searcher([old_key])
 
281
        list(searcher)
 
282
        return searcher.seen
 
283
 
 
284
    def _find_descendant_ancestors(self, old_key, new_key):
 
285
        """Find ancestors of new_key that may be descendants of old_key."""
 
286
        stop = self._make_breadth_first_searcher([old_key])
 
287
        descendants = self._make_breadth_first_searcher([new_key])
 
288
        for revisions in descendants:
 
289
            old_stop = stop.seen.intersection(revisions)
 
290
            descendants.stop_searching_any(old_stop)
 
291
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
292
            descendants.stop_searching_any(seen_stop)
 
293
        return descendants.seen.difference(stop.seen)
 
294
 
 
295
    def get_child_map(self, keys):
 
296
        """Get a mapping from parents to children of the specified keys.
 
297
 
 
298
        This is simply the inversion of get_parent_map.  Only supplied keys
 
299
        will be discovered as children.
 
300
        :return: a dict of key:child_list for keys.
 
301
        """
 
302
        parent_map = self._parents_provider.get_parent_map(keys)
 
303
        parent_child = {}
 
304
        for child, parents in sorted(parent_map.items()):
 
305
            for parent in parents:
 
306
                parent_child.setdefault(parent, []).append(child)
 
307
        return parent_child
 
308
 
261
309
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
310
        """Find the left-hand distance to the NULL_REVISION.
263
311
 
341
389
 
342
390
        :param unique_revision: The revision_id whose ancestry we are
343
391
            interested in.
344
 
            XXX: Would this API be better if we allowed multiple revisions on
345
 
                 to be searched here?
 
392
            (XXX: Would this API be better if we allowed multiple revisions on
 
393
            to be searched here?)
346
394
        :param common_revisions: Revision_ids of ancestries to exclude.
347
395
        :return: A set of revisions in the ancestry of unique_revision
348
396
        """
862
910
                stop.add(parent_id)
863
911
        return found
864
912
 
 
913
    def find_lefthand_merger(self, merged_key, tip_key):
 
914
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
915
 
 
916
        We do this by first finding the descendants of merged_key, then
 
917
        walking through the lefthand ancestry of tip_key until we find a key
 
918
        that doesn't descend from merged_key.  Its child is the key that
 
919
        merged merged_key.
 
920
 
 
921
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
922
            merged_key if it is a lefthand ancestor of tip_key.
 
923
            None if no ancestor of tip_key merged merged_key.
 
924
        """
 
925
        descendants = self.find_descendants(merged_key, tip_key)
 
926
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
927
        last_candidate = None
 
928
        for candidate in candidate_iterator:
 
929
            if candidate not in descendants:
 
930
                return last_candidate
 
931
            last_candidate = candidate
 
932
 
865
933
    def find_unique_lca(self, left_revision, right_revision,
866
934
                        count_steps=False):
867
935
        """Find a unique LCA.
919
987
                yield (ghost, None)
920
988
            pending = next_pending
921
989
 
 
990
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
991
        if stop_keys is None:
 
992
            stop_keys = ()
 
993
        next_key = start_key
 
994
        def get_parents(key):
 
995
            try:
 
996
                return self._parents_provider.get_parent_map([key])[key]
 
997
            except KeyError:
 
998
                raise errors.RevisionNotPresent(next_key, self)
 
999
        while True:
 
1000
            if next_key in stop_keys:
 
1001
                return
 
1002
            parents = get_parents(next_key)
 
1003
            yield next_key
 
1004
            if len(parents) == 0:
 
1005
                return
 
1006
            else:
 
1007
                next_key = parents[0]
 
1008
 
922
1009
    def iter_topo_order(self, revisions):
923
1010
        """Iterate through the input revisions in topological order.
924
1011
 
1463
1550
            return revs, ghosts
1464
1551
 
1465
1552
 
1466
 
class SearchResult(object):
 
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):
1467
1616
    """The result of a breadth first search.
1468
1617
 
1469
1618
    A SearchResult provides the ability to reconstruct the search or access a
1484
1633
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1634
        self._keys = frozenset(keys)
1486
1635
 
 
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
 
1487
1649
    def get_recipe(self):
1488
1650
        """Return a recipe that can be used to replay this search.
1489
1651
 
1507
1669
        """
1508
1670
        return self._recipe
1509
1671
 
 
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
 
1510
1678
    def get_keys(self):
1511
1679
        """Return the keys found in this search.
1512
1680
 
1544
1712
        return SearchResult(pending_refs, exclude, count, keys)
1545
1713
 
1546
1714
 
1547
 
class PendingAncestryResult(object):
 
1715
class PendingAncestryResult(AbstractSearchResult):
1548
1716
    """A search result that will reconstruct the ancestry for some graph heads.
1549
1717
 
1550
1718
    Unlike SearchResult, this doesn't hold the complete search result in
1561
1729
        self.heads = frozenset(heads)
1562
1730
        self.repo = repo
1563
1731
 
 
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
 
1564
1741
    def get_recipe(self):
1565
1742
        """Return a recipe that can be used to replay this search.
1566
1743
 
1574
1751
        """
1575
1752
        return ('proxy-search', self.heads, set(), -1)
1576
1753
 
 
1754
    def get_network_struct(self):
 
1755
        parts = ['ancestry-of']
 
1756
        parts.extend(self.heads)
 
1757
        return parts
 
1758
 
1577
1759
    def get_keys(self):
1578
1760
        """See SearchResult.get_keys.
1579
1761
 
1606
1788
        return PendingAncestryResult(referenced - seen, self.repo)
1607
1789
 
1608
1790
 
 
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
 
1609
1894
def collapse_linear_regions(parent_map):
1610
1895
    """Collapse regions of the graph that are 'linear'.
1611
1896
 
1695
1980
        return set([h[0] for h in head_keys])
1696
1981
 
1697
1982
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((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])
1699
1990
 
1700
1991
 
1701
1992
_counters = [0,0,0,0,0,0,0]