← 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-07-06 09:22:00 UTC
  • mfrom: (6008 +trunk)
  • mto: (6012.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 6013.
  • Revision ID: v.ladeuil+lp@free.fr-20110706092200-7iai2mwzc0sqdsvf
Merging in trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
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
 
237
250
        common ancestor of all border ancestors, because this shows that it
238
251
        cannot be a descendant of any border ancestor.
239
252
 
240
 
        The scaling of this operation should be proportional to
 
253
        The scaling of this operation should be proportional to:
 
254
 
241
255
        1. The number of uncommon ancestors
242
256
        2. The number of border ancestors
243
257
        3. The length of the shortest path between a border ancestor and an
375
389
 
376
390
        :param unique_revision: The revision_id whose ancestry we are
377
391
            interested in.
378
 
            XXX: Would this API be better if we allowed multiple revisions on
379
 
                 to be searched here?
 
392
            (XXX: Would this API be better if we allowed multiple revisions on
 
393
            to be searched here?)
380
394
        :param common_revisions: Revision_ids of ancestries to exclude.
381
395
        :return: A set of revisions in the ancestry of unique_revision
382
396
        """
1536
1550
            return revs, ghosts
1537
1551
 
1538
1552
 
1539
 
class SearchResult(object):
 
1553
class AbstractSearchResult(object):
 
1554
    """The result of a search, describing a set of keys.
 
1555
    
 
1556
    Search results are typically used as the 'fetch_spec' parameter when
 
1557
    fetching revisions.
 
1558
 
 
1559
    :seealso: AbstractSearch
 
1560
    """
 
1561
 
 
1562
    def get_recipe(self):
 
1563
        """Return a recipe that can be used to replay this search.
 
1564
 
 
1565
        The recipe allows reconstruction of the same results at a later date.
 
1566
 
 
1567
        :return: A tuple of `(search_kind_str, *details)`.  The details vary by
 
1568
            kind of search result.
 
1569
        """
 
1570
        raise NotImplementedError(self.get_recipe)
 
1571
 
 
1572
    def get_network_struct(self):
 
1573
        """Return a tuple that can be transmitted via the HPSS protocol."""
 
1574
        raise NotImplementedError(self.get_network_struct)
 
1575
 
 
1576
    def get_keys(self):
 
1577
        """Return the keys found in this search.
 
1578
 
 
1579
        :return: A set of keys.
 
1580
        """
 
1581
        raise NotImplementedError(self.get_keys)
 
1582
 
 
1583
    def is_empty(self):
 
1584
        """Return false if the search lists 1 or more revisions."""
 
1585
        raise NotImplementedError(self.is_empty)
 
1586
 
 
1587
    def refine(self, seen, referenced):
 
1588
        """Create a new search by refining this search.
 
1589
 
 
1590
        :param seen: Revisions that have been satisfied.
 
1591
        :param referenced: Revision references observed while satisfying some
 
1592
            of this search.
 
1593
        :return: A search result.
 
1594
        """
 
1595
        raise NotImplementedError(self.refine)
 
1596
 
 
1597
 
 
1598
class AbstractSearch(object):
 
1599
    """A search that can be executed, producing a search result.
 
1600
 
 
1601
    :seealso: AbstractSearchResult
 
1602
    """
 
1603
 
 
1604
    def execute(self):
 
1605
        """Construct a network-ready search result from this search description.
 
1606
 
 
1607
        This may take some time to search repositories, etc.
 
1608
 
 
1609
        :return: A search result (an object that implements
 
1610
            AbstractSearchResult's API).
 
1611
        """
 
1612
        raise NotImplementedError(self.execute)
 
1613
 
 
1614
 
 
1615
class SearchResult(AbstractSearchResult):
1540
1616
    """The result of a breadth first search.
1541
1617
 
1542
1618
    A SearchResult provides the ability to reconstruct the search or access a
1557
1633
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1558
1634
        self._keys = frozenset(keys)
1559
1635
 
 
1636
    def __repr__(self):
 
1637
        kind, start_keys, exclude_keys, key_count = self._recipe
 
1638
        if len(start_keys) > 5:
 
1639
            start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
 
1640
        else:
 
1641
            start_keys_repr = repr(start_keys)
 
1642
        if len(exclude_keys) > 5:
 
1643
            exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
 
1644
        else:
 
1645
            exclude_keys_repr = repr(exclude_keys)
 
1646
        return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
 
1647
            kind, start_keys_repr, exclude_keys_repr, key_count)
 
1648
 
1560
1649
    def get_recipe(self):
1561
1650
        """Return a recipe that can be used to replay this search.
1562
1651
 
1580
1669
        """
1581
1670
        return self._recipe
1582
1671
 
 
1672
    def get_network_struct(self):
 
1673
        start_keys = ' '.join(self._recipe[1])
 
1674
        stop_keys = ' '.join(self._recipe[2])
 
1675
        count = str(self._recipe[3])
 
1676
        return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
 
1677
 
1583
1678
    def get_keys(self):
1584
1679
        """Return the keys found in this search.
1585
1680
 
1617
1712
        return SearchResult(pending_refs, exclude, count, keys)
1618
1713
 
1619
1714
 
1620
 
class PendingAncestryResult(object):
 
1715
class PendingAncestryResult(AbstractSearchResult):
1621
1716
    """A search result that will reconstruct the ancestry for some graph heads.
1622
1717
 
1623
1718
    Unlike SearchResult, this doesn't hold the complete search result in
1634
1729
        self.heads = frozenset(heads)
1635
1730
        self.repo = repo
1636
1731
 
 
1732
    def __repr__(self):
 
1733
        if len(self.heads) > 5:
 
1734
            heads_repr = repr(list(self.heads)[:5])[:-1]
 
1735
            heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
 
1736
        else:
 
1737
            heads_repr = repr(self.heads)
 
1738
        return '<%s heads:%s repo:%r>' % (
 
1739
            self.__class__.__name__, heads_repr, self.repo)
 
1740
 
1637
1741
    def get_recipe(self):
1638
1742
        """Return a recipe that can be used to replay this search.
1639
1743
 
1647
1751
        """
1648
1752
        return ('proxy-search', self.heads, set(), -1)
1649
1753
 
 
1754
    def get_network_struct(self):
 
1755
        parts = ['ancestry-of']
 
1756
        parts.extend(self.heads)
 
1757
        return parts
 
1758
 
1650
1759
    def get_keys(self):
1651
1760
        """See SearchResult.get_keys.
1652
1761
 
1679
1788
        return PendingAncestryResult(referenced - seen, self.repo)
1680
1789
 
1681
1790
 
 
1791
class EmptySearchResult(AbstractSearchResult):
 
1792
    """An empty search result."""
 
1793
 
 
1794
    def is_empty(self):
 
1795
        return True
 
1796
    
 
1797
 
 
1798
class EverythingResult(AbstractSearchResult):
 
1799
    """A search result that simply requests everything in the repository."""
 
1800
 
 
1801
    def __init__(self, repo):
 
1802
        self._repo = repo
 
1803
 
 
1804
    def __repr__(self):
 
1805
        return '%s(%r)' % (self.__class__.__name__, self._repo)
 
1806
 
 
1807
    def get_recipe(self):
 
1808
        raise NotImplementedError(self.get_recipe)
 
1809
 
 
1810
    def get_network_struct(self):
 
1811
        return ('everything',)
 
1812
 
 
1813
    def get_keys(self):
 
1814
        if 'evil' in debug.debug_flags:
 
1815
            from bzrlib import remote
 
1816
            if isinstance(self._repo, remote.RemoteRepository):
 
1817
                # warn developers (not users) not to do this
 
1818
                trace.mutter_callsite(
 
1819
                    2, "EverythingResult(RemoteRepository).get_keys() is slow.")
 
1820
        return self._repo.all_revision_ids()
 
1821
 
 
1822
    def is_empty(self):
 
1823
        # It's ok for this to wrongly return False: the worst that can happen
 
1824
        # is that RemoteStreamSource will initiate a get_stream on an empty
 
1825
        # repository.  And almost all repositories are non-empty.
 
1826
        return False
 
1827
 
 
1828
    def refine(self, seen, referenced):
 
1829
        heads = set(self._repo.all_revision_ids())
 
1830
        heads.difference_update(seen)
 
1831
        heads.update(referenced)
 
1832
        return PendingAncestryResult(heads, self._repo)
 
1833
 
 
1834
 
 
1835
class EverythingNotInOther(AbstractSearch):
 
1836
    """Find all revisions in that are in one repo but not the other."""
 
1837
 
 
1838
    def __init__(self, to_repo, from_repo, find_ghosts=False):
 
1839
        self.to_repo = to_repo
 
1840
        self.from_repo = from_repo
 
1841
        self.find_ghosts = find_ghosts
 
1842
 
 
1843
    def execute(self):
 
1844
        return self.to_repo.search_missing_revision_ids(
 
1845
            self.from_repo, find_ghosts=self.find_ghosts)
 
1846
 
 
1847
 
 
1848
class NotInOtherForRevs(AbstractSearch):
 
1849
    """Find all revisions missing in one repo for a some specific heads."""
 
1850
 
 
1851
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
 
1852
            find_ghosts=False, limit=None):
 
1853
        """Constructor.
 
1854
 
 
1855
        :param required_ids: revision IDs of heads that must be found, or else
 
1856
            the search will fail with NoSuchRevision.  All revisions in their
 
1857
            ancestry not already in the other repository will be included in
 
1858
            the search result.
 
1859
        :param if_present_ids: revision IDs of heads that may be absent in the
 
1860
            source repository.  If present, then their ancestry not already
 
1861
            found in other will be included in the search result.
 
1862
        :param limit: maximum number of revisions to fetch
 
1863
        """
 
1864
        self.to_repo = to_repo
 
1865
        self.from_repo = from_repo
 
1866
        self.find_ghosts = find_ghosts
 
1867
        self.required_ids = required_ids
 
1868
        self.if_present_ids = if_present_ids
 
1869
        self.limit = limit
 
1870
 
 
1871
    def __repr__(self):
 
1872
        if len(self.required_ids) > 5:
 
1873
            reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
 
1874
        else:
 
1875
            reqd_revs_repr = repr(self.required_ids)
 
1876
        if self.if_present_ids and len(self.if_present_ids) > 5:
 
1877
            ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
 
1878
        else:
 
1879
            ifp_revs_repr = repr(self.if_present_ids)
 
1880
 
 
1881
        return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
 
1882
                "limit:%r>") % (
 
1883
                self.__class__.__name__, self.from_repo, self.to_repo,
 
1884
                self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
 
1885
                self.limit)
 
1886
 
 
1887
    def execute(self):
 
1888
        return self.to_repo.search_missing_revision_ids(
 
1889
            self.from_repo, revision_ids=self.required_ids,
 
1890
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
 
1891
            limit=self.limit)
 
1892
 
 
1893
 
1682
1894
def collapse_linear_regions(parent_map):
1683
1895
    """Collapse regions of the graph that are 'linear'.
1684
1896
 
1768
1980
        return set([h[0] for h in head_keys])
1769
1981
 
1770
1982
    def merge_sort(self, tip_revision):
1771
 
        return self._graph.merge_sort((tip_revision,))
 
1983
        nodes = self._graph.merge_sort((tip_revision,))
 
1984
        for node in nodes:
 
1985
            node.key = node.key[0]
 
1986
        return nodes
1772
1987
 
1773
1988
    def add_node(self, revision, parents):
1774
1989
        self._graph.add_node((revision,), [(p,) for p in parents])