/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2011-01-19 18:40:15 UTC
  • mfrom: (5622 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5624.
  • Revision ID: jelmer@samba.org-20110119184015-ahycpz0yduideif0
merge bzr.dev.

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
1536
1536
            return revs, ghosts
1537
1537
 
1538
1538
 
1539
 
class SearchResult(object):
 
1539
class AbstractSearchResult(object):
 
1540
 
 
1541
    def get_recipe(self):
 
1542
        """Return a recipe that can be used to replay this search.
 
1543
 
 
1544
        The recipe allows reconstruction of the same results at a later date.
 
1545
 
 
1546
        :return: A tuple of (search_kind_str, *details).  The details vary by
 
1547
            kind of search result.
 
1548
        """
 
1549
        raise NotImplementedError(self.get_recipe)
 
1550
 
 
1551
    def get_network_struct(self):
 
1552
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1553
        raise NotImplementedError(self.get_network_struct)
 
1554
 
 
1555
    def get_keys(self):
 
1556
        """Return the keys found in this search.
 
1557
 
 
1558
        :return: A set of keys.
 
1559
        """
 
1560
        raise NotImplementedError(self.get_keys)
 
1561
 
 
1562
    def is_empty(self):
 
1563
        """Return false if the search lists 1 or more revisions."""
 
1564
        raise NotImplementedError(self.is_empty)
 
1565
 
 
1566
    def refine(self, seen, referenced):
 
1567
        """Create a new search by refining this search.
 
1568
 
 
1569
        :param seen: Revisions that have been satisfied.
 
1570
        :param referenced: Revision references observed while satisfying some
 
1571
            of this search.
 
1572
        :return: A search result.
 
1573
        """
 
1574
        raise NotImplementedError(self.refine)
 
1575
 
 
1576
 
 
1577
class AbstractSearch(object):
 
1578
 
 
1579
    def get_search_result(self):
 
1580
        """Construct a network-ready search result from this search description.
 
1581
 
 
1582
        This may take some time to search repositories, etc.
 
1583
 
 
1584
        :return: A search result.
 
1585
        """
 
1586
        raise NotImplementedError(self.get_search_result)
 
1587
 
 
1588
 
 
1589
class SearchResult(AbstractSearchResult):
1540
1590
    """The result of a breadth first search.
1541
1591
 
1542
1592
    A SearchResult provides the ability to reconstruct the search or access a
1557
1607
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1558
1608
        self._keys = frozenset(keys)
1559
1609
 
 
1610
    def __repr__(self):
 
1611
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1612
        if len(start_keys) > 5:
 
1613
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1614
        else:
 
1615
            start_keys_repr = repr(start_keys)
 
1616
        if len(exclude_keys) > 5:
 
1617
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1618
        else:
 
1619
            exclude_keys_repr = repr(exclude_keys)
 
1620
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1621
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1622
 
1560
1623
    def get_recipe(self):
1561
1624
        """Return a recipe that can be used to replay this search.
1562
1625
 
1580
1643
        """
1581
1644
        return self._recipe
1582
1645
 
 
1646
    def get_network_struct(self):
 
1647
        start_keys = ' '.join(self._recipe[1])
 
1648
        stop_keys = ' '.join(self._recipe[2])
 
1649
        count = str(self._recipe[3])
 
1650
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1651
 
1583
1652
    def get_keys(self):
1584
1653
        """Return the keys found in this search.
1585
1654
 
1617
1686
        return SearchResult(pending_refs, exclude, count, keys)
1618
1687
 
1619
1688
 
1620
 
class PendingAncestryResult(object):
 
1689
class PendingAncestryResult(AbstractSearchResult):
1621
1690
    """A search result that will reconstruct the ancestry for some graph heads.
1622
1691
 
1623
1692
    Unlike SearchResult, this doesn't hold the complete search result in
1634
1703
        self.heads = frozenset(heads)
1635
1704
        self.repo = repo
1636
1705
 
 
1706
    def __repr__(self):
 
1707
        if len(self.heads) > 5:
 
1708
            heads_repr = repr(list(self.heads)[:5] + ', ...]')
 
1709
        else:
 
1710
            heads_repr = repr(self.heads)
 
1711
        return '<%s heads:%s repo:%r>' % (
 
1712
            self.__class__.__name__, heads_repr, self.repo)
 
1713
 
1637
1714
    def get_recipe(self):
1638
1715
        """Return a recipe that can be used to replay this search.
1639
1716
 
1647
1724
        """
1648
1725
        return ('proxy-search', self.heads, set(), -1)
1649
1726
 
 
1727
    def get_network_struct(self):
 
1728
        parts = ['ancestry-of']
 
1729
        parts.extend(self.heads)
 
1730
        return parts
 
1731
 
1650
1732
    def get_keys(self):
1651
1733
        """See SearchResult.get_keys.
1652
1734
 
1679
1761
        return PendingAncestryResult(referenced - seen, self.repo)
1680
1762
 
1681
1763
 
 
1764
class EmptySearchResult(AbstractSearchResult):
 
1765
    """An empty search result."""
 
1766
 
 
1767
    def is_empty(self):
 
1768
        return True
 
1769
    
 
1770
 
 
1771
class EverythingResult(AbstractSearchResult):
 
1772
    """A search result that simply requests everything in the repository."""
 
1773
 
 
1774
    def __init__(self, repo):
 
1775
        self._repo = repo
 
1776
 
 
1777
    def __repr__(self):
 
1778
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1779
 
 
1780
    def get_recipe(self):
 
1781
        raise NotImplementedError(self.get_recipe)
 
1782
 
 
1783
    def get_network_struct(self):
 
1784
        return ('everything',)
 
1785
 
 
1786
    def get_keys(self):
 
1787
        if 'evil' in debug.debug_flags:
 
1788
            from bzrlib import remote
 
1789
            if isinstance(self._repo, remote.RemoteRepository):
 
1790
                # warn developers (not users) not to do this
 
1791
                trace.mutter_callsite(
 
1792
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1793
        return self._repo.all_revision_ids()
 
1794
 
 
1795
    def is_empty(self):
 
1796
        # It's ok for this to wrongly return False: the worst that can happen
 
1797
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1798
        # repository.  And almost all repositories are non-empty.
 
1799
        return False
 
1800
 
 
1801
    def refine(self, seen, referenced):
 
1802
        heads = set(self._repo.all_revision_ids())
 
1803
        heads.difference_update(seen)
 
1804
        heads.update(referenced)
 
1805
        return PendingAncestryResult(heads, self._repo)
 
1806
 
 
1807
 
 
1808
class EverythingNotInOther(AbstractSearch):
 
1809
    """Find all revisions in that are in one repo but not the other."""
 
1810
 
 
1811
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1812
        self.to_repo = to_repo
 
1813
        self.from_repo = from_repo
 
1814
        self.find_ghosts = find_ghosts
 
1815
 
 
1816
    def get_search_result(self):
 
1817
        return self.to_repo.search_missing_revision_ids(
 
1818
            self.from_repo, find_ghosts=self.find_ghosts)
 
1819
 
 
1820
 
 
1821
class NotInOtherForRevs(AbstractSearch):
 
1822
    """Find all revisions missing in one repo for a some specific heads."""
 
1823
 
 
1824
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1825
            find_ghosts=False):
 
1826
        """Constructor.
 
1827
 
 
1828
        :param required_ids: revision IDs of heads that must be found, or else
 
1829
            the search will fail with NoSuchRevision.  All revisions in their
 
1830
            ancestry not already in the other repository will be included in
 
1831
            the search result.
 
1832
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1833
            source repository.  If present, then their ancestry not already
 
1834
            found in other will be included in the search result.
 
1835
        """
 
1836
        self.to_repo = to_repo
 
1837
        self.from_repo = from_repo
 
1838
        self.find_ghosts = find_ghosts
 
1839
        self.required_ids = required_ids
 
1840
        self.if_present_ids = if_present_ids
 
1841
 
 
1842
    def __repr__(self):
 
1843
        if len(self.required_ids) > 5:
 
1844
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1845
        else:
 
1846
            reqd_revs_repr = repr(self.required_ids)
 
1847
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1848
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1849
        else:
 
1850
            ifp_revs_repr = repr(self.if_present_ids)
 
1851
 
 
1852
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1853
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1854
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
 
1855
 
 
1856
    def get_search_result(self):
 
1857
        return self.to_repo.search_missing_revision_ids(
 
1858
            self.from_repo, revision_ids=self.required_ids,
 
1859
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
 
1860
 
 
1861
 
1682
1862
def collapse_linear_regions(parent_map):
1683
1863
    """Collapse regions of the graph that are 'linear'.
1684
1864