← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Vincent Ladeuil
  • Date: 2011-02-10 12:37:27 UTC
  • mto: This revision was merged to the branch mainline in revision 5661.
  • Revision ID: v.ladeuil+lp@free.fr-20110210123727-8e0pu4wtlt6fj7nf
thread is already a python module, avoid confusion and use cethread instead.

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
258
258
        right = searchers[1].seen
259
259
        return (left.difference(right), right.difference(left))
260
260
 
 
261
    def find_descendants(self, old_key, new_key):
 
262
        """Find descendants of old_key that are ancestors of new_key."""
 
263
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
264
            old_key, new_key))
 
265
        graph = Graph(DictParentsProvider(child_map))
 
266
        searcher = graph._make_breadth_first_searcher([old_key])
 
267
        list(searcher)
 
268
        return searcher.seen
 
269
 
 
270
    def _find_descendant_ancestors(self, old_key, new_key):
 
271
        """Find ancestors of new_key that may be descendants of old_key."""
 
272
        stop = self._make_breadth_first_searcher([old_key])
 
273
        descendants = self._make_breadth_first_searcher([new_key])
 
274
        for revisions in descendants:
 
275
            old_stop = stop.seen.intersection(revisions)
 
276
            descendants.stop_searching_any(old_stop)
 
277
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
278
            descendants.stop_searching_any(seen_stop)
 
279
        return descendants.seen.difference(stop.seen)
 
280
 
 
281
    def get_child_map(self, keys):
 
282
        """Get a mapping from parents to children of the specified keys.
 
283
 
 
284
        This is simply the inversion of get_parent_map.  Only supplied keys
 
285
        will be discovered as children.
 
286
        :return: a dict of key:child_list for keys.
 
287
        """
 
288
        parent_map = self._parents_provider.get_parent_map(keys)
 
289
        parent_child = {}
 
290
        for child, parents in sorted(parent_map.items()):
 
291
            for parent in parents:
 
292
                parent_child.setdefault(parent, []).append(child)
 
293
        return parent_child
 
294
 
261
295
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
296
        """Find the left-hand distance to the NULL_REVISION.
263
297
 
862
896
                stop.add(parent_id)
863
897
        return found
864
898
 
 
899
    def find_lefthand_merger(self, merged_key, tip_key):
 
900
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
901
 
 
902
        We do this by first finding the descendants of merged_key, then
 
903
        walking through the lefthand ancestry of tip_key until we find a key
 
904
        that doesn't descend from merged_key.  Its child is the key that
 
905
        merged merged_key.
 
906
 
 
907
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
908
            merged_key if it is a lefthand ancestor of tip_key.
 
909
            None if no ancestor of tip_key merged merged_key.
 
910
        """
 
911
        descendants = self.find_descendants(merged_key, tip_key)
 
912
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
913
        last_candidate = None
 
914
        for candidate in candidate_iterator:
 
915
            if candidate not in descendants:
 
916
                return last_candidate
 
917
            last_candidate = candidate
 
918
 
865
919
    def find_unique_lca(self, left_revision, right_revision,
866
920
                        count_steps=False):
867
921
        """Find a unique LCA.
919
973
                yield (ghost, None)
920
974
            pending = next_pending
921
975
 
 
976
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
977
        if stop_keys is None:
 
978
            stop_keys = ()
 
979
        next_key = start_key
 
980
        def get_parents(key):
 
981
            try:
 
982
                return self._parents_provider.get_parent_map([key])[key]
 
983
            except KeyError:
 
984
                raise errors.RevisionNotPresent(next_key, self)
 
985
        while True:
 
986
            if next_key in stop_keys:
 
987
                return
 
988
            parents = get_parents(next_key)
 
989
            yield next_key
 
990
            if len(parents) == 0:
 
991
                return
 
992
            else:
 
993
                next_key = parents[0]
 
994
 
922
995
    def iter_topo_order(self, revisions):
923
996
        """Iterate through the input revisions in topological order.
924
997
 
1463
1536
            return revs, ghosts
1464
1537
 
1465
1538
 
1466
 
class SearchResult(object):
 
1539
class AbstractSearchResult(object):
 
1540
    """The result of a search, describing a set of keys.
 
1541
    
 
1542
    Search results are typically used as the 'fetch_spec' parameter when
 
1543
    fetching revisions.
 
1544
 
 
1545
    :seealso: AbstractSearch
 
1546
    """
 
1547
 
 
1548
    def get_recipe(self):
 
1549
        """Return a recipe that can be used to replay this search.
 
1550
 
 
1551
        The recipe allows reconstruction of the same results at a later date.
 
1552
 
 
1553
        :return: A tuple of (search_kind_str, *details).  The details vary by
 
1554
            kind of search result.
 
1555
        """
 
1556
        raise NotImplementedError(self.get_recipe)
 
1557
 
 
1558
    def get_network_struct(self):
 
1559
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1560
        raise NotImplementedError(self.get_network_struct)
 
1561
 
 
1562
    def get_keys(self):
 
1563
        """Return the keys found in this search.
 
1564
 
 
1565
        :return: A set of keys.
 
1566
        """
 
1567
        raise NotImplementedError(self.get_keys)
 
1568
 
 
1569
    def is_empty(self):
 
1570
        """Return false if the search lists 1 or more revisions."""
 
1571
        raise NotImplementedError(self.is_empty)
 
1572
 
 
1573
    def refine(self, seen, referenced):
 
1574
        """Create a new search by refining this search.
 
1575
 
 
1576
        :param seen: Revisions that have been satisfied.
 
1577
        :param referenced: Revision references observed while satisfying some
 
1578
            of this search.
 
1579
        :return: A search result.
 
1580
        """
 
1581
        raise NotImplementedError(self.refine)
 
1582
 
 
1583
 
 
1584
class AbstractSearch(object):
 
1585
    """A search that can be executed, producing a search result.
 
1586
 
 
1587
    :seealso: AbstractSearchResult
 
1588
    """
 
1589
 
 
1590
    def execute(self):
 
1591
        """Construct a network-ready search result from this search description.
 
1592
 
 
1593
        This may take some time to search repositories, etc.
 
1594
 
 
1595
        :return: A search result (an object that implements
 
1596
            AbstractSearchResult's API).
 
1597
        """
 
1598
        raise NotImplementedError(self.execute)
 
1599
 
 
1600
 
 
1601
class SearchResult(AbstractSearchResult):
1467
1602
    """The result of a breadth first search.
1468
1603
 
1469
1604
    A SearchResult provides the ability to reconstruct the search or access a
1484
1619
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1620
        self._keys = frozenset(keys)
1486
1621
 
 
1622
    def __repr__(self):
 
1623
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1624
        if len(start_keys) > 5:
 
1625
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1626
        else:
 
1627
            start_keys_repr = repr(start_keys)
 
1628
        if len(exclude_keys) > 5:
 
1629
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1630
        else:
 
1631
            exclude_keys_repr = repr(exclude_keys)
 
1632
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1633
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1634
 
1487
1635
    def get_recipe(self):
1488
1636
        """Return a recipe that can be used to replay this search.
1489
1637
 
1507
1655
        """
1508
1656
        return self._recipe
1509
1657
 
 
1658
    def get_network_struct(self):
 
1659
        start_keys = ' '.join(self._recipe[1])
 
1660
        stop_keys = ' '.join(self._recipe[2])
 
1661
        count = str(self._recipe[3])
 
1662
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1663
 
1510
1664
    def get_keys(self):
1511
1665
        """Return the keys found in this search.
1512
1666
 
1544
1698
        return SearchResult(pending_refs, exclude, count, keys)
1545
1699
 
1546
1700
 
1547
 
class PendingAncestryResult(object):
 
1701
class PendingAncestryResult(AbstractSearchResult):
1548
1702
    """A search result that will reconstruct the ancestry for some graph heads.
1549
1703
 
1550
1704
    Unlike SearchResult, this doesn't hold the complete search result in
1561
1715
        self.heads = frozenset(heads)
1562
1716
        self.repo = repo
1563
1717
 
 
1718
    def __repr__(self):
 
1719
        if len(self.heads) > 5:
 
1720
            heads_repr = repr(list(self.heads)[:5])[:-1]
 
1721
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
 
1722
        else:
 
1723
            heads_repr = repr(self.heads)
 
1724
        return '<%s heads:%s repo:%r>' % (
 
1725
            self.__class__.__name__, heads_repr, self.repo)
 
1726
 
1564
1727
    def get_recipe(self):
1565
1728
        """Return a recipe that can be used to replay this search.
1566
1729
 
1574
1737
        """
1575
1738
        return ('proxy-search', self.heads, set(), -1)
1576
1739
 
 
1740
    def get_network_struct(self):
 
1741
        parts = ['ancestry-of']
 
1742
        parts.extend(self.heads)
 
1743
        return parts
 
1744
 
1577
1745
    def get_keys(self):
1578
1746
        """See SearchResult.get_keys.
1579
1747
 
1606
1774
        return PendingAncestryResult(referenced - seen, self.repo)
1607
1775
 
1608
1776
 
 
1777
class EmptySearchResult(AbstractSearchResult):
 
1778
    """An empty search result."""
 
1779
 
 
1780
    def is_empty(self):
 
1781
        return True
 
1782
    
 
1783
 
 
1784
class EverythingResult(AbstractSearchResult):
 
1785
    """A search result that simply requests everything in the repository."""
 
1786
 
 
1787
    def __init__(self, repo):
 
1788
        self._repo = repo
 
1789
 
 
1790
    def __repr__(self):
 
1791
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1792
 
 
1793
    def get_recipe(self):
 
1794
        raise NotImplementedError(self.get_recipe)
 
1795
 
 
1796
    def get_network_struct(self):
 
1797
        return ('everything',)
 
1798
 
 
1799
    def get_keys(self):
 
1800
        if 'evil' in debug.debug_flags:
 
1801
            from bzrlib import remote
 
1802
            if isinstance(self._repo, remote.RemoteRepository):
 
1803
                # warn developers (not users) not to do this
 
1804
                trace.mutter_callsite(
 
1805
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1806
        return self._repo.all_revision_ids()
 
1807
 
 
1808
    def is_empty(self):
 
1809
        # It's ok for this to wrongly return False: the worst that can happen
 
1810
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1811
        # repository.  And almost all repositories are non-empty.
 
1812
        return False
 
1813
 
 
1814
    def refine(self, seen, referenced):
 
1815
        heads = set(self._repo.all_revision_ids())
 
1816
        heads.difference_update(seen)
 
1817
        heads.update(referenced)
 
1818
        return PendingAncestryResult(heads, self._repo)
 
1819
 
 
1820
 
 
1821
class EverythingNotInOther(AbstractSearch):
 
1822
    """Find all revisions in that are in one repo but not the other."""
 
1823
 
 
1824
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1825
        self.to_repo = to_repo
 
1826
        self.from_repo = from_repo
 
1827
        self.find_ghosts = find_ghosts
 
1828
 
 
1829
    def execute(self):
 
1830
        return self.to_repo.search_missing_revision_ids(
 
1831
            self.from_repo, find_ghosts=self.find_ghosts)
 
1832
 
 
1833
 
 
1834
class NotInOtherForRevs(AbstractSearch):
 
1835
    """Find all revisions missing in one repo for a some specific heads."""
 
1836
 
 
1837
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1838
            find_ghosts=False):
 
1839
        """Constructor.
 
1840
 
 
1841
        :param required_ids: revision IDs of heads that must be found, or else
 
1842
            the search will fail with NoSuchRevision.  All revisions in their
 
1843
            ancestry not already in the other repository will be included in
 
1844
            the search result.
 
1845
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1846
            source repository.  If present, then their ancestry not already
 
1847
            found in other will be included in the search result.
 
1848
        """
 
1849
        self.to_repo = to_repo
 
1850
        self.from_repo = from_repo
 
1851
        self.find_ghosts = find_ghosts
 
1852
        self.required_ids = required_ids
 
1853
        self.if_present_ids = if_present_ids
 
1854
 
 
1855
    def __repr__(self):
 
1856
        if len(self.required_ids) > 5:
 
1857
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1858
        else:
 
1859
            reqd_revs_repr = repr(self.required_ids)
 
1860
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1861
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1862
        else:
 
1863
            ifp_revs_repr = repr(self.if_present_ids)
 
1864
 
 
1865
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1866
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1867
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
 
1868
 
 
1869
    def execute(self):
 
1870
        return self.to_repo.search_missing_revision_ids(
 
1871
            self.from_repo, revision_ids=self.required_ids,
 
1872
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
 
1873
 
 
1874
 
1609
1875
def collapse_linear_regions(parent_map):
1610
1876
    """Collapse regions of the graph that are 'linear'.
1611
1877
 
1697
1963
    def merge_sort(self, tip_revision):
1698
1964
        return self._graph.merge_sort((tip_revision,))
1699
1965
 
 
1966
    def add_node(self, revision, parents):
 
1967
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1968
 
1700
1969
 
1701
1970
_counters = [0,0,0,0,0,0,0]
1702
1971
try: