← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2011-04-19 10:42:59 UTC
  • mto: This revision was merged to the branch mainline in revision 5806.
  • Revision ID: jelmer@samba.org-20110419104259-g9exlcp1f5jdu3ci
Move Inventory._get_mutable_inventory -> mutable_inventory_from_tree.

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.
258
254
        right = searchers[1].seen
259
255
        return (left.difference(right), right.difference(left))
260
256
 
 
257
    def find_descendants(self, old_key, new_key):
 
258
        """Find descendants of old_key that are ancestors of new_key."""
 
259
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
260
            old_key, new_key))
 
261
        graph = Graph(DictParentsProvider(child_map))
 
262
        searcher = graph._make_breadth_first_searcher([old_key])
 
263
        list(searcher)
 
264
        return searcher.seen
 
265
 
 
266
    def _find_descendant_ancestors(self, old_key, new_key):
 
267
        """Find ancestors of new_key that may be descendants of old_key."""
 
268
        stop = self._make_breadth_first_searcher([old_key])
 
269
        descendants = self._make_breadth_first_searcher([new_key])
 
270
        for revisions in descendants:
 
271
            old_stop = stop.seen.intersection(revisions)
 
272
            descendants.stop_searching_any(old_stop)
 
273
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
274
            descendants.stop_searching_any(seen_stop)
 
275
        return descendants.seen.difference(stop.seen)
 
276
 
 
277
    def get_child_map(self, keys):
 
278
        """Get a mapping from parents to children of the specified keys.
 
279
 
 
280
        This is simply the inversion of get_parent_map.  Only supplied keys
 
281
        will be discovered as children.
 
282
        :return: a dict of key:child_list for keys.
 
283
        """
 
284
        parent_map = self._parents_provider.get_parent_map(keys)
 
285
        parent_child = {}
 
286
        for child, parents in sorted(parent_map.items()):
 
287
            for parent in parents:
 
288
                parent_child.setdefault(parent, []).append(child)
 
289
        return parent_child
 
290
 
261
291
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
292
        """Find the left-hand distance to the NULL_REVISION.
263
293
 
862
892
                stop.add(parent_id)
863
893
        return found
864
894
 
 
895
    def find_lefthand_merger(self, merged_key, tip_key):
 
896
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
897
 
 
898
        We do this by first finding the descendants of merged_key, then
 
899
        walking through the lefthand ancestry of tip_key until we find a key
 
900
        that doesn't descend from merged_key.  Its child is the key that
 
901
        merged merged_key.
 
902
 
 
903
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
904
            merged_key if it is a lefthand ancestor of tip_key.
 
905
            None if no ancestor of tip_key merged merged_key.
 
906
        """
 
907
        descendants = self.find_descendants(merged_key, tip_key)
 
908
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
909
        last_candidate = None
 
910
        for candidate in candidate_iterator:
 
911
            if candidate not in descendants:
 
912
                return last_candidate
 
913
            last_candidate = candidate
 
914
 
865
915
    def find_unique_lca(self, left_revision, right_revision,
866
916
                        count_steps=False):
867
917
        """Find a unique LCA.
919
969
                yield (ghost, None)
920
970
            pending = next_pending
921
971
 
 
972
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
973
        if stop_keys is None:
 
974
            stop_keys = ()
 
975
        next_key = start_key
 
976
        def get_parents(key):
 
977
            try:
 
978
                return self._parents_provider.get_parent_map([key])[key]
 
979
            except KeyError:
 
980
                raise errors.RevisionNotPresent(next_key, self)
 
981
        while True:
 
982
            if next_key in stop_keys:
 
983
                return
 
984
            parents = get_parents(next_key)
 
985
            yield next_key
 
986
            if len(parents) == 0:
 
987
                return
 
988
            else:
 
989
                next_key = parents[0]
 
990
 
922
991
    def iter_topo_order(self, revisions):
923
992
        """Iterate through the input revisions in topological order.
924
993
 
1463
1532
            return revs, ghosts
1464
1533
 
1465
1534
 
1466
 
class SearchResult(object):
 
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):
1467
1598
    """The result of a breadth first search.
1468
1599
 
1469
1600
    A SearchResult provides the ability to reconstruct the search or access a
1484
1615
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1616
        self._keys = frozenset(keys)
1486
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
 
1487
1631
    def get_recipe(self):
1488
1632
        """Return a recipe that can be used to replay this search.
1489
1633
 
1507
1651
        """
1508
1652
        return self._recipe
1509
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
 
1510
1660
    def get_keys(self):
1511
1661
        """Return the keys found in this search.
1512
1662
 
1544
1694
        return SearchResult(pending_refs, exclude, count, keys)
1545
1695
 
1546
1696
 
1547
 
class PendingAncestryResult(object):
 
1697
class PendingAncestryResult(AbstractSearchResult):
1548
1698
    """A search result that will reconstruct the ancestry for some graph heads.
1549
1699
 
1550
1700
    Unlike SearchResult, this doesn't hold the complete search result in
1561
1711
        self.heads = frozenset(heads)
1562
1712
        self.repo = repo
1563
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
 
1564
1723
    def get_recipe(self):
1565
1724
        """Return a recipe that can be used to replay this search.
1566
1725
 
1574
1733
        """
1575
1734
        return ('proxy-search', self.heads, set(), -1)
1576
1735
 
 
1736
    def get_network_struct(self):
 
1737
        parts = ['ancestry-of']
 
1738
        parts.extend(self.heads)
 
1739
        return parts
 
1740
 
1577
1741
    def get_keys(self):
1578
1742
        """See SearchResult.get_keys.
1579
1743
 
1606
1770
        return PendingAncestryResult(referenced - seen, self.repo)
1607
1771
 
1608
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)
 
1869
 
 
1870
 
1609
1871
def collapse_linear_regions(parent_map):
1610
1872
    """Collapse regions of the graph that are 'linear'.
1611
1873
 
1697
1959
    def merge_sort(self, tip_revision):
1698
1960
        return self._graph.merge_sort((tip_revision,))
1699
1961
 
 
1962
    def add_node(self, revision, parents):
 
1963
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1964
 
1700
1965
 
1701
1966
_counters = [0,0,0,0,0,0,0]
1702
1967
try: