← 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-04-20 15:06:17 UTC
  • mto: This revision was merged to the branch mainline in revision 5836.
  • Revision ID: john@arbash-meinel.com-20110420150617-i41caxgemg32tq1r
Start adding tests that _worth_saving_limit works as expected.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
from __future__ import absolute_import
18
 
 
19
17
import time
20
18
 
21
19
from bzrlib import (
60
58
    def __repr__(self):
61
59
        return 'DictParentsProvider(%r)' % self.ancestry
62
60
 
63
 
    # Note: DictParentsProvider does not implement get_cached_parent_map
64
 
    #       Arguably, the data is clearly cached in memory. However, this class
65
 
    #       is mostly used for testing, and it keeps the tests clean to not
66
 
    #       change it.
67
 
 
68
61
    def get_parent_map(self, keys):
69
62
        """See StackedParentsProvider.get_parent_map"""
70
63
        ancestry = self.ancestry
71
 
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
64
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
72
65
 
73
66
 
74
67
class StackedParentsProvider(object):
75
68
    """A parents provider which stacks (or unions) multiple providers.
76
 
 
 
69
    
77
70
    The providers are queries in the order of the provided parent_providers.
78
71
    """
79
 
 
 
72
    
80
73
    def __init__(self, parent_providers):
81
74
        self._parent_providers = parent_providers
82
75
 
98
91
        """
99
92
        found = {}
100
93
        remaining = set(keys)
101
 
        # This adds getattr() overhead to each get_parent_map call. However,
102
 
        # this is StackedParentsProvider, which means we're dealing with I/O
103
 
        # (either local indexes, or remote RPCs), so CPU overhead should be
104
 
        # minimal.
105
 
        for parents_provider in self._parent_providers:
106
 
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
107
 
                                 None)
108
 
            if get_cached is None:
109
 
                continue
110
 
            new_found = get_cached(remaining)
111
 
            found.update(new_found)
112
 
            remaining.difference_update(new_found)
113
 
            if not remaining:
114
 
                break
115
 
        if not remaining:
116
 
            return found
117
94
        for parents_provider in self._parent_providers:
118
95
            new_found = parents_provider.get_parent_map(remaining)
119
96
            found.update(new_found)
173
150
            return None
174
151
        return dict(self._cache)
175
152
 
176
 
    def get_cached_parent_map(self, keys):
177
 
        """Return items from the cache.
178
 
 
179
 
        This returns the same info as get_parent_map, but explicitly does not
180
 
        invoke the supplied ParentsProvider to search for uncached values.
181
 
        """
182
 
        cache = self._cache
183
 
        if cache is None:
184
 
            return {}
185
 
        return dict([(key, cache[key]) for key in keys if key in cache])
186
 
 
187
153
    def get_parent_map(self, keys):
188
154
        """See StackedParentsProvider.get_parent_map."""
189
155
        cache = self._cache
213
179
            self.missing_keys.add(key)
214
180
 
215
181
 
216
 
class CallableToParentsProviderAdapter(object):
217
 
    """A parents provider that adapts any callable to the parents provider API.
218
 
 
219
 
    i.e. it accepts calls to self.get_parent_map and relays them to the
220
 
    callable it was constructed with.
221
 
    """
222
 
 
223
 
    def __init__(self, a_callable):
224
 
        self.callable = a_callable
225
 
 
226
 
    def __repr__(self):
227
 
        return "%s(%r)" % (self.__class__.__name__, self.callable)
228
 
 
229
 
    def get_parent_map(self, keys):
230
 
        return self.callable(keys)
231
 
 
232
 
 
233
182
class Graph(object):
234
183
    """Provide incremental access to revision graphs.
235
184
 
284
233
        common ancestor of all border ancestors, because this shows that it
285
234
        cannot be a descendant of any border ancestor.
286
235
 
287
 
        The scaling of this operation should be proportional to:
288
 
 
 
236
        The scaling of this operation should be proportional to
289
237
        1. The number of uncommon ancestors
290
238
        2. The number of border ancestors
291
239
        3. The length of the shortest path between a border ancestor and an
423
371
 
424
372
        :param unique_revision: The revision_id whose ancestry we are
425
373
            interested in.
426
 
            (XXX: Would this API be better if we allowed multiple revisions on
427
 
            to be searched here?)
 
374
            XXX: Would this API be better if we allowed multiple revisions on
 
375
                 to be searched here?
428
376
        :param common_revisions: Revision_ids of ancestries to exclude.
429
377
        :return: A set of revisions in the ancestry of unique_revision
430
378
        """
1348
1296
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1349
1297
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1350
1298
 
1351
 
    def get_state(self):
1352
 
        """Get the current state of this searcher.
 
1299
    def get_result(self):
 
1300
        """Get a SearchResult for the current state of this searcher.
1353
1301
 
1354
 
        :return: Tuple with started keys, excludes and included keys
 
1302
        :return: A SearchResult for this search so far. The SearchResult is
 
1303
            static - the search can be advanced and the search result will not
 
1304
            be invalidated or altered.
1355
1305
        """
1356
1306
        if self._returning == 'next':
1357
1307
            # We have to know the current nodes children to be able to list the
1368
1318
            next_query = self._next_query
1369
1319
        excludes = self._stopped_keys.union(next_query)
1370
1320
        included_keys = self.seen.difference(excludes)
1371
 
        return self._started_keys, excludes, included_keys
1372
 
 
1373
 
    def _get_result(self):
1374
 
        """Get a SearchResult for the current state of this searcher.
1375
 
 
1376
 
        :return: A SearchResult for this search so far. The SearchResult is
1377
 
            static - the search can be advanced and the search result will not
1378
 
            be invalidated or altered.
1379
 
        """
1380
 
        from bzrlib.vf_search import SearchResult
1381
 
        (started_keys, excludes, included_keys) = self.get_state()
1382
 
        return SearchResult(started_keys, excludes, len(included_keys),
 
1321
        return SearchResult(self._started_keys, excludes, len(included_keys),
1383
1322
            included_keys)
1384
1323
 
1385
1324
    def step(self):
1462
1401
        parents_of_found = set()
1463
1402
        # revisions may contain nodes that point to other nodes in revisions:
1464
1403
        # we want to filter them out.
1465
 
        seen = self.seen
1466
 
        seen.update(revisions)
 
1404
        self.seen.update(revisions)
1467
1405
        parent_map = self._parents_provider.get_parent_map(revisions)
1468
1406
        found_revisions.update(parent_map)
1469
1407
        for rev_id, parents in parent_map.iteritems():
1470
1408
            if parents is None:
1471
1409
                continue
1472
 
            new_found_parents = [p for p in parents if p not in seen]
 
1410
            new_found_parents = [p for p in parents if p not in self.seen]
1473
1411
            if new_found_parents:
1474
1412
                # Calling set.update() with an empty generator is actually
1475
1413
                # rather expensive.
1594
1532
            return revs, ghosts
1595
1533
 
1596
1534
 
1597
 
def invert_parent_map(parent_map):
1598
 
    """Given a map from child => parents, create a map of parent=>children"""
1599
 
    child_map = {}
1600
 
    for child, parents in parent_map.iteritems():
1601
 
        for p in parents:
1602
 
            # Any given parent is likely to have only a small handful
1603
 
            # of children, many will have only one. So we avoid mem overhead of
1604
 
            # a list, in exchange for extra copying of tuples
1605
 
            if p not in child_map:
1606
 
                child_map[p] = (child,)
1607
 
            else:
1608
 
                child_map[p] = child_map[p] + (child,)
1609
 
    return child_map
 
1535
class AbstractSearchResult(object):
 
1536
    """The result of a search, describing a set of keys.
 
1537
    
 
1538
    Search results are typically used as the 'fetch_spec' parameter when
 
1539
    fetching revisions.
 
1540
 
 
1541
    :seealso: AbstractSearch
 
1542
    """
 
1543
 
 
1544
    def get_recipe(self):
 
1545
        """Return a recipe that can be used to replay this search.
 
1546
 
 
1547
        The recipe allows reconstruction of the same results at a later date.
 
1548
 
 
1549
        :return: A tuple of (search_kind_str, *details).  The details vary by
 
1550
            kind of search result.
 
1551
        """
 
1552
        raise NotImplementedError(self.get_recipe)
 
1553
 
 
1554
    def get_network_struct(self):
 
1555
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1556
        raise NotImplementedError(self.get_network_struct)
 
1557
 
 
1558
    def get_keys(self):
 
1559
        """Return the keys found in this search.
 
1560
 
 
1561
        :return: A set of keys.
 
1562
        """
 
1563
        raise NotImplementedError(self.get_keys)
 
1564
 
 
1565
    def is_empty(self):
 
1566
        """Return false if the search lists 1 or more revisions."""
 
1567
        raise NotImplementedError(self.is_empty)
 
1568
 
 
1569
    def refine(self, seen, referenced):
 
1570
        """Create a new search by refining this search.
 
1571
 
 
1572
        :param seen: Revisions that have been satisfied.
 
1573
        :param referenced: Revision references observed while satisfying some
 
1574
            of this search.
 
1575
        :return: A search result.
 
1576
        """
 
1577
        raise NotImplementedError(self.refine)
 
1578
 
 
1579
 
 
1580
class AbstractSearch(object):
 
1581
    """A search that can be executed, producing a search result.
 
1582
 
 
1583
    :seealso: AbstractSearchResult
 
1584
    """
 
1585
 
 
1586
    def execute(self):
 
1587
        """Construct a network-ready search result from this search description.
 
1588
 
 
1589
        This may take some time to search repositories, etc.
 
1590
 
 
1591
        :return: A search result (an object that implements
 
1592
            AbstractSearchResult's API).
 
1593
        """
 
1594
        raise NotImplementedError(self.execute)
 
1595
 
 
1596
 
 
1597
class SearchResult(AbstractSearchResult):
 
1598
    """The result of a breadth first search.
 
1599
 
 
1600
    A SearchResult provides the ability to reconstruct the search or access a
 
1601
    set of the keys the search found.
 
1602
    """
 
1603
 
 
1604
    def __init__(self, start_keys, exclude_keys, key_count, keys):
 
1605
        """Create a SearchResult.
 
1606
 
 
1607
        :param start_keys: The keys the search started at.
 
1608
        :param exclude_keys: The keys the search excludes.
 
1609
        :param key_count: The total number of keys (from start to but not
 
1610
            including exclude).
 
1611
        :param keys: The keys the search found. Note that in future we may get
 
1612
            a SearchResult from a smart server, in which case the keys list is
 
1613
            not necessarily immediately available.
 
1614
        """
 
1615
        self._recipe = ('search', start_keys, exclude_keys, key_count)
 
1616
        self._keys = frozenset(keys)
 
1617
 
 
1618
    def __repr__(self):
 
1619
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1620
        if len(start_keys) > 5:
 
1621
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1622
        else:
 
1623
            start_keys_repr = repr(start_keys)
 
1624
        if len(exclude_keys) > 5:
 
1625
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1626
        else:
 
1627
            exclude_keys_repr = repr(exclude_keys)
 
1628
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1629
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1630
 
 
1631
    def get_recipe(self):
 
1632
        """Return a recipe that can be used to replay this search.
 
1633
 
 
1634
        The recipe allows reconstruction of the same results at a later date
 
1635
        without knowing all the found keys. The essential elements are a list
 
1636
        of keys to start and to stop at. In order to give reproducible
 
1637
        results when ghosts are encountered by a search they are automatically
 
1638
        added to the exclude list (or else ghost filling may alter the
 
1639
        results).
 
1640
 
 
1641
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1642
            revision_count). To recreate the results of this search, create a
 
1643
            breadth first searcher on the same graph starting at start_keys.
 
1644
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1645
            result, call stop_searching_any on any keys from the exclude_keys
 
1646
            set. The revision_count value acts as a trivial cross-check - the
 
1647
            found revisions of the new search should have as many elements as
 
1648
            revision_count. If it does not, then additional revisions have been
 
1649
            ghosted since the search was executed the first time and the second
 
1650
            time.
 
1651
        """
 
1652
        return self._recipe
 
1653
 
 
1654
    def get_network_struct(self):
 
1655
        start_keys = ' '.join(self._recipe[1])
 
1656
        stop_keys = ' '.join(self._recipe[2])
 
1657
        count = str(self._recipe[3])
 
1658
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1659
 
 
1660
    def get_keys(self):
 
1661
        """Return the keys found in this search.
 
1662
 
 
1663
        :return: A set of keys.
 
1664
        """
 
1665
        return self._keys
 
1666
 
 
1667
    def is_empty(self):
 
1668
        """Return false if the search lists 1 or more revisions."""
 
1669
        return self._recipe[3] == 0
 
1670
 
 
1671
    def refine(self, seen, referenced):
 
1672
        """Create a new search by refining this search.
 
1673
 
 
1674
        :param seen: Revisions that have been satisfied.
 
1675
        :param referenced: Revision references observed while satisfying some
 
1676
            of this search.
 
1677
        """
 
1678
        start = self._recipe[1]
 
1679
        exclude = self._recipe[2]
 
1680
        count = self._recipe[3]
 
1681
        keys = self.get_keys()
 
1682
        # New heads = referenced + old heads - seen things - exclude
 
1683
        pending_refs = set(referenced)
 
1684
        pending_refs.update(start)
 
1685
        pending_refs.difference_update(seen)
 
1686
        pending_refs.difference_update(exclude)
 
1687
        # New exclude = old exclude + satisfied heads
 
1688
        seen_heads = start.intersection(seen)
 
1689
        exclude.update(seen_heads)
 
1690
        # keys gets seen removed
 
1691
        keys = keys - seen
 
1692
        # length is reduced by len(seen)
 
1693
        count -= len(seen)
 
1694
        return SearchResult(pending_refs, exclude, count, keys)
 
1695
 
 
1696
 
 
1697
class PendingAncestryResult(AbstractSearchResult):
 
1698
    """A search result that will reconstruct the ancestry for some graph heads.
 
1699
 
 
1700
    Unlike SearchResult, this doesn't hold the complete search result in
 
1701
    memory, it just holds a description of how to generate it.
 
1702
    """
 
1703
 
 
1704
    def __init__(self, heads, repo):
 
1705
        """Constructor.
 
1706
 
 
1707
        :param heads: an iterable of graph heads.
 
1708
        :param repo: a repository to use to generate the ancestry for the given
 
1709
            heads.
 
1710
        """
 
1711
        self.heads = frozenset(heads)
 
1712
        self.repo = repo
 
1713
 
 
1714
    def __repr__(self):
 
1715
        if len(self.heads) > 5:
 
1716
            heads_repr = repr(list(self.heads)[:5])[:-1]
 
1717
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
 
1718
        else:
 
1719
            heads_repr = repr(self.heads)
 
1720
        return '<%s heads:%s repo:%r>' % (
 
1721
            self.__class__.__name__, heads_repr, self.repo)
 
1722
 
 
1723
    def get_recipe(self):
 
1724
        """Return a recipe that can be used to replay this search.
 
1725
 
 
1726
        The recipe allows reconstruction of the same results at a later date.
 
1727
 
 
1728
        :seealso SearchResult.get_recipe:
 
1729
 
 
1730
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1731
            To recreate this result, create a PendingAncestryResult with the
 
1732
            start_keys_set.
 
1733
        """
 
1734
        return ('proxy-search', self.heads, set(), -1)
 
1735
 
 
1736
    def get_network_struct(self):
 
1737
        parts = ['ancestry-of']
 
1738
        parts.extend(self.heads)
 
1739
        return parts
 
1740
 
 
1741
    def get_keys(self):
 
1742
        """See SearchResult.get_keys.
 
1743
 
 
1744
        Returns all the keys for the ancestry of the heads, excluding
 
1745
        NULL_REVISION.
 
1746
        """
 
1747
        return self._get_keys(self.repo.get_graph())
 
1748
 
 
1749
    def _get_keys(self, graph):
 
1750
        NULL_REVISION = revision.NULL_REVISION
 
1751
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1752
                if key != NULL_REVISION and parents is not None]
 
1753
        return keys
 
1754
 
 
1755
    def is_empty(self):
 
1756
        """Return false if the search lists 1 or more revisions."""
 
1757
        if revision.NULL_REVISION in self.heads:
 
1758
            return len(self.heads) == 1
 
1759
        else:
 
1760
            return len(self.heads) == 0
 
1761
 
 
1762
    def refine(self, seen, referenced):
 
1763
        """Create a new search by refining this search.
 
1764
 
 
1765
        :param seen: Revisions that have been satisfied.
 
1766
        :param referenced: Revision references observed while satisfying some
 
1767
            of this search.
 
1768
        """
 
1769
        referenced = self.heads.union(referenced)
 
1770
        return PendingAncestryResult(referenced - seen, self.repo)
 
1771
 
 
1772
 
 
1773
class EmptySearchResult(AbstractSearchResult):
 
1774
    """An empty search result."""
 
1775
 
 
1776
    def is_empty(self):
 
1777
        return True
 
1778
    
 
1779
 
 
1780
class EverythingResult(AbstractSearchResult):
 
1781
    """A search result that simply requests everything in the repository."""
 
1782
 
 
1783
    def __init__(self, repo):
 
1784
        self._repo = repo
 
1785
 
 
1786
    def __repr__(self):
 
1787
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1788
 
 
1789
    def get_recipe(self):
 
1790
        raise NotImplementedError(self.get_recipe)
 
1791
 
 
1792
    def get_network_struct(self):
 
1793
        return ('everything',)
 
1794
 
 
1795
    def get_keys(self):
 
1796
        if 'evil' in debug.debug_flags:
 
1797
            from bzrlib import remote
 
1798
            if isinstance(self._repo, remote.RemoteRepository):
 
1799
                # warn developers (not users) not to do this
 
1800
                trace.mutter_callsite(
 
1801
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1802
        return self._repo.all_revision_ids()
 
1803
 
 
1804
    def is_empty(self):
 
1805
        # It's ok for this to wrongly return False: the worst that can happen
 
1806
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1807
        # repository.  And almost all repositories are non-empty.
 
1808
        return False
 
1809
 
 
1810
    def refine(self, seen, referenced):
 
1811
        heads = set(self._repo.all_revision_ids())
 
1812
        heads.difference_update(seen)
 
1813
        heads.update(referenced)
 
1814
        return PendingAncestryResult(heads, self._repo)
 
1815
 
 
1816
 
 
1817
class EverythingNotInOther(AbstractSearch):
 
1818
    """Find all revisions in that are in one repo but not the other."""
 
1819
 
 
1820
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1821
        self.to_repo = to_repo
 
1822
        self.from_repo = from_repo
 
1823
        self.find_ghosts = find_ghosts
 
1824
 
 
1825
    def execute(self):
 
1826
        return self.to_repo.search_missing_revision_ids(
 
1827
            self.from_repo, find_ghosts=self.find_ghosts)
 
1828
 
 
1829
 
 
1830
class NotInOtherForRevs(AbstractSearch):
 
1831
    """Find all revisions missing in one repo for a some specific heads."""
 
1832
 
 
1833
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1834
            find_ghosts=False):
 
1835
        """Constructor.
 
1836
 
 
1837
        :param required_ids: revision IDs of heads that must be found, or else
 
1838
            the search will fail with NoSuchRevision.  All revisions in their
 
1839
            ancestry not already in the other repository will be included in
 
1840
            the search result.
 
1841
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1842
            source repository.  If present, then their ancestry not already
 
1843
            found in other will be included in the search result.
 
1844
        """
 
1845
        self.to_repo = to_repo
 
1846
        self.from_repo = from_repo
 
1847
        self.find_ghosts = find_ghosts
 
1848
        self.required_ids = required_ids
 
1849
        self.if_present_ids = if_present_ids
 
1850
 
 
1851
    def __repr__(self):
 
1852
        if len(self.required_ids) > 5:
 
1853
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1854
        else:
 
1855
            reqd_revs_repr = repr(self.required_ids)
 
1856
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1857
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1858
        else:
 
1859
            ifp_revs_repr = repr(self.if_present_ids)
 
1860
 
 
1861
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1862
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1863
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
 
1864
 
 
1865
    def execute(self):
 
1866
        return self.to_repo.search_missing_revision_ids(
 
1867
            self.from_repo, revision_ids=self.required_ids,
 
1868
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1610
1869
 
1611
1870
 
1612
1871
def collapse_linear_regions(parent_map):
1698
1957
        return set([h[0] for h in head_keys])
1699
1958
 
1700
1959
    def merge_sort(self, tip_revision):
1701
 
        nodes = self._graph.merge_sort((tip_revision,))
1702
 
        for node in nodes:
1703
 
            node.key = node.key[0]
1704
 
        return nodes
 
1960
        return self._graph.merge_sort((tip_revision,))
1705
1961
 
1706
1962
    def add_node(self, revision, parents):
1707
1963
        self._graph.add_node((revision,), [(p,) for p in parents])