← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2011-05-11 11:35:28 UTC
  • mto: This revision was merged to the branch mainline in revision 5851.
  • Revision ID: john@arbash-meinel.com-20110511113528-qepibuwxicjrbb2h
Break compatibility with python <2.6.

This includes auditing the code for places where we were doing
explicit 'sys.version' checks and removing them as appropriate.

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
 
258
271
        right = searchers[1].seen
259
272
        return (left.difference(right), right.difference(left))
260
273
 
 
274
    def find_descendants(self, old_key, new_key):
 
275
        """Find descendants of old_key that are ancestors of new_key."""
 
276
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
277
            old_key, new_key))
 
278
        graph = Graph(DictParentsProvider(child_map))
 
279
        searcher = graph._make_breadth_first_searcher([old_key])
 
280
        list(searcher)
 
281
        return searcher.seen
 
282
 
 
283
    def _find_descendant_ancestors(self, old_key, new_key):
 
284
        """Find ancestors of new_key that may be descendants of old_key."""
 
285
        stop = self._make_breadth_first_searcher([old_key])
 
286
        descendants = self._make_breadth_first_searcher([new_key])
 
287
        for revisions in descendants:
 
288
            old_stop = stop.seen.intersection(revisions)
 
289
            descendants.stop_searching_any(old_stop)
 
290
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
291
            descendants.stop_searching_any(seen_stop)
 
292
        return descendants.seen.difference(stop.seen)
 
293
 
 
294
    def get_child_map(self, keys):
 
295
        """Get a mapping from parents to children of the specified keys.
 
296
 
 
297
        This is simply the inversion of get_parent_map.  Only supplied keys
 
298
        will be discovered as children.
 
299
        :return: a dict of key:child_list for keys.
 
300
        """
 
301
        parent_map = self._parents_provider.get_parent_map(keys)
 
302
        parent_child = {}
 
303
        for child, parents in sorted(parent_map.items()):
 
304
            for parent in parents:
 
305
                parent_child.setdefault(parent, []).append(child)
 
306
        return parent_child
 
307
 
261
308
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
309
        """Find the left-hand distance to the NULL_REVISION.
263
310
 
862
909
                stop.add(parent_id)
863
910
        return found
864
911
 
 
912
    def find_lefthand_merger(self, merged_key, tip_key):
 
913
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
914
 
 
915
        We do this by first finding the descendants of merged_key, then
 
916
        walking through the lefthand ancestry of tip_key until we find a key
 
917
        that doesn't descend from merged_key.  Its child is the key that
 
918
        merged merged_key.
 
919
 
 
920
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
921
            merged_key if it is a lefthand ancestor of tip_key.
 
922
            None if no ancestor of tip_key merged merged_key.
 
923
        """
 
924
        descendants = self.find_descendants(merged_key, tip_key)
 
925
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
926
        last_candidate = None
 
927
        for candidate in candidate_iterator:
 
928
            if candidate not in descendants:
 
929
                return last_candidate
 
930
            last_candidate = candidate
 
931
 
865
932
    def find_unique_lca(self, left_revision, right_revision,
866
933
                        count_steps=False):
867
934
        """Find a unique LCA.
919
986
                yield (ghost, None)
920
987
            pending = next_pending
921
988
 
 
989
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
990
        if stop_keys is None:
 
991
            stop_keys = ()
 
992
        next_key = start_key
 
993
        def get_parents(key):
 
994
            try:
 
995
                return self._parents_provider.get_parent_map([key])[key]
 
996
            except KeyError:
 
997
                raise errors.RevisionNotPresent(next_key, self)
 
998
        while True:
 
999
            if next_key in stop_keys:
 
1000
                return
 
1001
            parents = get_parents(next_key)
 
1002
            yield next_key
 
1003
            if len(parents) == 0:
 
1004
                return
 
1005
            else:
 
1006
                next_key = parents[0]
 
1007
 
922
1008
    def iter_topo_order(self, revisions):
923
1009
        """Iterate through the input revisions in topological order.
924
1010
 
1463
1549
            return revs, ghosts
1464
1550
 
1465
1551
 
1466
 
class SearchResult(object):
 
1552
class AbstractSearchResult(object):
 
1553
    """The result of a search, describing a set of keys.
 
1554
    
 
1555
    Search results are typically used as the 'fetch_spec' parameter when
 
1556
    fetching revisions.
 
1557
 
 
1558
    :seealso: AbstractSearch
 
1559
    """
 
1560
 
 
1561
    def get_recipe(self):
 
1562
        """Return a recipe that can be used to replay this search.
 
1563
 
 
1564
        The recipe allows reconstruction of the same results at a later date.
 
1565
 
 
1566
        :return: A tuple of (search_kind_str, *details).  The details vary by
 
1567
            kind of search result.
 
1568
        """
 
1569
        raise NotImplementedError(self.get_recipe)
 
1570
 
 
1571
    def get_network_struct(self):
 
1572
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1573
        raise NotImplementedError(self.get_network_struct)
 
1574
 
 
1575
    def get_keys(self):
 
1576
        """Return the keys found in this search.
 
1577
 
 
1578
        :return: A set of keys.
 
1579
        """
 
1580
        raise NotImplementedError(self.get_keys)
 
1581
 
 
1582
    def is_empty(self):
 
1583
        """Return false if the search lists 1 or more revisions."""
 
1584
        raise NotImplementedError(self.is_empty)
 
1585
 
 
1586
    def refine(self, seen, referenced):
 
1587
        """Create a new search by refining this search.
 
1588
 
 
1589
        :param seen: Revisions that have been satisfied.
 
1590
        :param referenced: Revision references observed while satisfying some
 
1591
            of this search.
 
1592
        :return: A search result.
 
1593
        """
 
1594
        raise NotImplementedError(self.refine)
 
1595
 
 
1596
 
 
1597
class AbstractSearch(object):
 
1598
    """A search that can be executed, producing a search result.
 
1599
 
 
1600
    :seealso: AbstractSearchResult
 
1601
    """
 
1602
 
 
1603
    def execute(self):
 
1604
        """Construct a network-ready search result from this search description.
 
1605
 
 
1606
        This may take some time to search repositories, etc.
 
1607
 
 
1608
        :return: A search result (an object that implements
 
1609
            AbstractSearchResult's API).
 
1610
        """
 
1611
        raise NotImplementedError(self.execute)
 
1612
 
 
1613
 
 
1614
class SearchResult(AbstractSearchResult):
1467
1615
    """The result of a breadth first search.
1468
1616
 
1469
1617
    A SearchResult provides the ability to reconstruct the search or access a
1484
1632
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1633
        self._keys = frozenset(keys)
1486
1634
 
 
1635
    def __repr__(self):
 
1636
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1637
        if len(start_keys) > 5:
 
1638
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1639
        else:
 
1640
            start_keys_repr = repr(start_keys)
 
1641
        if len(exclude_keys) > 5:
 
1642
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1643
        else:
 
1644
            exclude_keys_repr = repr(exclude_keys)
 
1645
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1646
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1647
 
1487
1648
    def get_recipe(self):
1488
1649
        """Return a recipe that can be used to replay this search.
1489
1650
 
1507
1668
        """
1508
1669
        return self._recipe
1509
1670
 
 
1671
    def get_network_struct(self):
 
1672
        start_keys = ' '.join(self._recipe[1])
 
1673
        stop_keys = ' '.join(self._recipe[2])
 
1674
        count = str(self._recipe[3])
 
1675
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1676
 
1510
1677
    def get_keys(self):
1511
1678
        """Return the keys found in this search.
1512
1679
 
1544
1711
        return SearchResult(pending_refs, exclude, count, keys)
1545
1712
 
1546
1713
 
1547
 
class PendingAncestryResult(object):
 
1714
class PendingAncestryResult(AbstractSearchResult):
1548
1715
    """A search result that will reconstruct the ancestry for some graph heads.
1549
1716
 
1550
1717
    Unlike SearchResult, this doesn't hold the complete search result in
1561
1728
        self.heads = frozenset(heads)
1562
1729
        self.repo = repo
1563
1730
 
 
1731
    def __repr__(self):
 
1732
        if len(self.heads) > 5:
 
1733
            heads_repr = repr(list(self.heads)[:5])[:-1]
 
1734
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
 
1735
        else:
 
1736
            heads_repr = repr(self.heads)
 
1737
        return '<%s heads:%s repo:%r>' % (
 
1738
            self.__class__.__name__, heads_repr, self.repo)
 
1739
 
1564
1740
    def get_recipe(self):
1565
1741
        """Return a recipe that can be used to replay this search.
1566
1742
 
1574
1750
        """
1575
1751
        return ('proxy-search', self.heads, set(), -1)
1576
1752
 
 
1753
    def get_network_struct(self):
 
1754
        parts = ['ancestry-of']
 
1755
        parts.extend(self.heads)
 
1756
        return parts
 
1757
 
1577
1758
    def get_keys(self):
1578
1759
        """See SearchResult.get_keys.
1579
1760
 
1606
1787
        return PendingAncestryResult(referenced - seen, self.repo)
1607
1788
 
1608
1789
 
 
1790
class EmptySearchResult(AbstractSearchResult):
 
1791
    """An empty search result."""
 
1792
 
 
1793
    def is_empty(self):
 
1794
        return True
 
1795
    
 
1796
 
 
1797
class EverythingResult(AbstractSearchResult):
 
1798
    """A search result that simply requests everything in the repository."""
 
1799
 
 
1800
    def __init__(self, repo):
 
1801
        self._repo = repo
 
1802
 
 
1803
    def __repr__(self):
 
1804
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1805
 
 
1806
    def get_recipe(self):
 
1807
        raise NotImplementedError(self.get_recipe)
 
1808
 
 
1809
    def get_network_struct(self):
 
1810
        return ('everything',)
 
1811
 
 
1812
    def get_keys(self):
 
1813
        if 'evil' in debug.debug_flags:
 
1814
            from bzrlib import remote
 
1815
            if isinstance(self._repo, remote.RemoteRepository):
 
1816
                # warn developers (not users) not to do this
 
1817
                trace.mutter_callsite(
 
1818
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1819
        return self._repo.all_revision_ids()
 
1820
 
 
1821
    def is_empty(self):
 
1822
        # It's ok for this to wrongly return False: the worst that can happen
 
1823
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1824
        # repository.  And almost all repositories are non-empty.
 
1825
        return False
 
1826
 
 
1827
    def refine(self, seen, referenced):
 
1828
        heads = set(self._repo.all_revision_ids())
 
1829
        heads.difference_update(seen)
 
1830
        heads.update(referenced)
 
1831
        return PendingAncestryResult(heads, self._repo)
 
1832
 
 
1833
 
 
1834
class EverythingNotInOther(AbstractSearch):
 
1835
    """Find all revisions in that are in one repo but not the other."""
 
1836
 
 
1837
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1838
        self.to_repo = to_repo
 
1839
        self.from_repo = from_repo
 
1840
        self.find_ghosts = find_ghosts
 
1841
 
 
1842
    def execute(self):
 
1843
        return self.to_repo.search_missing_revision_ids(
 
1844
            self.from_repo, find_ghosts=self.find_ghosts)
 
1845
 
 
1846
 
 
1847
class NotInOtherForRevs(AbstractSearch):
 
1848
    """Find all revisions missing in one repo for a some specific heads."""
 
1849
 
 
1850
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1851
            find_ghosts=False):
 
1852
        """Constructor.
 
1853
 
 
1854
        :param required_ids: revision IDs of heads that must be found, or else
 
1855
            the search will fail with NoSuchRevision.  All revisions in their
 
1856
            ancestry not already in the other repository will be included in
 
1857
            the search result.
 
1858
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1859
            source repository.  If present, then their ancestry not already
 
1860
            found in other will be included in the search result.
 
1861
        """
 
1862
        self.to_repo = to_repo
 
1863
        self.from_repo = from_repo
 
1864
        self.find_ghosts = find_ghosts
 
1865
        self.required_ids = required_ids
 
1866
        self.if_present_ids = if_present_ids
 
1867
 
 
1868
    def __repr__(self):
 
1869
        if len(self.required_ids) > 5:
 
1870
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1871
        else:
 
1872
            reqd_revs_repr = repr(self.required_ids)
 
1873
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1874
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1875
        else:
 
1876
            ifp_revs_repr = repr(self.if_present_ids)
 
1877
 
 
1878
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1879
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1880
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
 
1881
 
 
1882
    def execute(self):
 
1883
        return self.to_repo.search_missing_revision_ids(
 
1884
            self.from_repo, revision_ids=self.required_ids,
 
1885
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
 
1886
 
 
1887
 
1609
1888
def collapse_linear_regions(parent_map):
1610
1889
    """Collapse regions of the graph that are 'linear'.
1611
1890
 
1697
1976
    def merge_sort(self, tip_revision):
1698
1977
        return self._graph.merge_sort((tip_revision,))
1699
1978
 
 
1979
    def add_node(self, revision, parents):
 
1980
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1981
 
1700
1982
 
1701
1983
_counters = [0,0,0,0,0,0,0]
1702
1984
try: