1533
1594
return revs, ghosts
1536
class AbstractSearchResult(object):
1537
"""The result of a search, describing a set of keys.
1539
Search results are typically used as the 'fetch_spec' parameter when
1542
:seealso: AbstractSearch
1545
def get_recipe(self):
1546
"""Return a recipe that can be used to replay this search.
1548
The recipe allows reconstruction of the same results at a later date.
1550
:return: A tuple of (search_kind_str, *details). The details vary by
1551
kind of search result.
1553
raise NotImplementedError(self.get_recipe)
1555
def get_network_struct(self):
1556
"""Return a tuple that can be transmitted via the HPSS protocol."""
1557
raise NotImplementedError(self.get_network_struct)
1560
"""Return the keys found in this search.
1562
:return: A set of keys.
1564
raise NotImplementedError(self.get_keys)
1567
"""Return false if the search lists 1 or more revisions."""
1568
raise NotImplementedError(self.is_empty)
1570
def refine(self, seen, referenced):
1571
"""Create a new search by refining this search.
1573
:param seen: Revisions that have been satisfied.
1574
:param referenced: Revision references observed while satisfying some
1576
:return: A search result.
1578
raise NotImplementedError(self.refine)
1581
class AbstractSearch(object):
1582
"""A search that can be executed, producing a search result.
1584
:seealso: AbstractSearchResult
1588
"""Construct a network-ready search result from this search description.
1590
This may take some time to search repositories, etc.
1592
:return: A search result (an object that implements
1593
AbstractSearchResult's API).
1595
raise NotImplementedError(self.execute)
1598
class SearchResult(AbstractSearchResult):
1599
"""The result of a breadth first search.
1601
A SearchResult provides the ability to reconstruct the search or access a
1602
set of the keys the search found.
1605
def __init__(self, start_keys, exclude_keys, key_count, keys):
1606
"""Create a SearchResult.
1608
:param start_keys: The keys the search started at.
1609
:param exclude_keys: The keys the search excludes.
1610
:param key_count: The total number of keys (from start to but not
1612
:param keys: The keys the search found. Note that in future we may get
1613
a SearchResult from a smart server, in which case the keys list is
1614
not necessarily immediately available.
1616
self._recipe = ('search', start_keys, exclude_keys, key_count)
1617
self._keys = frozenset(keys)
1620
kind, start_keys, exclude_keys, key_count = self._recipe
1621
if len(start_keys) > 5:
1622
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1624
start_keys_repr = repr(start_keys)
1625
if len(exclude_keys) > 5:
1626
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1628
exclude_keys_repr = repr(exclude_keys)
1629
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1630
kind, start_keys_repr, exclude_keys_repr, key_count)
1632
def get_recipe(self):
1633
"""Return a recipe that can be used to replay this search.
1635
The recipe allows reconstruction of the same results at a later date
1636
without knowing all the found keys. The essential elements are a list
1637
of keys to start and to stop at. In order to give reproducible
1638
results when ghosts are encountered by a search they are automatically
1639
added to the exclude list (or else ghost filling may alter the
1642
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1643
revision_count). To recreate the results of this search, create a
1644
breadth first searcher on the same graph starting at start_keys.
1645
Then call next() (or next_with_ghosts()) repeatedly, and on every
1646
result, call stop_searching_any on any keys from the exclude_keys
1647
set. The revision_count value acts as a trivial cross-check - the
1648
found revisions of the new search should have as many elements as
1649
revision_count. If it does not, then additional revisions have been
1650
ghosted since the search was executed the first time and the second
1655
def get_network_struct(self):
1656
start_keys = ' '.join(self._recipe[1])
1657
stop_keys = ' '.join(self._recipe[2])
1658
count = str(self._recipe[3])
1659
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1662
"""Return the keys found in this search.
1664
:return: A set of keys.
1669
"""Return false if the search lists 1 or more revisions."""
1670
return self._recipe[3] == 0
1672
def refine(self, seen, referenced):
1673
"""Create a new search by refining this search.
1675
:param seen: Revisions that have been satisfied.
1676
:param referenced: Revision references observed while satisfying some
1679
start = self._recipe[1]
1680
exclude = self._recipe[2]
1681
count = self._recipe[3]
1682
keys = self.get_keys()
1683
# New heads = referenced + old heads - seen things - exclude
1684
pending_refs = set(referenced)
1685
pending_refs.update(start)
1686
pending_refs.difference_update(seen)
1687
pending_refs.difference_update(exclude)
1688
# New exclude = old exclude + satisfied heads
1689
seen_heads = start.intersection(seen)
1690
exclude.update(seen_heads)
1691
# keys gets seen removed
1693
# length is reduced by len(seen)
1695
return SearchResult(pending_refs, exclude, count, keys)
1698
class PendingAncestryResult(AbstractSearchResult):
1699
"""A search result that will reconstruct the ancestry for some graph heads.
1701
Unlike SearchResult, this doesn't hold the complete search result in
1702
memory, it just holds a description of how to generate it.
1705
def __init__(self, heads, repo):
1708
:param heads: an iterable of graph heads.
1709
:param repo: a repository to use to generate the ancestry for the given
1712
self.heads = frozenset(heads)
1716
if len(self.heads) > 5:
1717
heads_repr = repr(list(self.heads)[:5])[:-1]
1718
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1720
heads_repr = repr(self.heads)
1721
return '<%s heads:%s repo:%r>' % (
1722
self.__class__.__name__, heads_repr, self.repo)
1724
def get_recipe(self):
1725
"""Return a recipe that can be used to replay this search.
1727
The recipe allows reconstruction of the same results at a later date.
1729
:seealso SearchResult.get_recipe:
1731
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1732
To recreate this result, create a PendingAncestryResult with the
1735
return ('proxy-search', self.heads, set(), -1)
1737
def get_network_struct(self):
1738
parts = ['ancestry-of']
1739
parts.extend(self.heads)
1743
"""See SearchResult.get_keys.
1745
Returns all the keys for the ancestry of the heads, excluding
1748
return self._get_keys(self.repo.get_graph())
1750
def _get_keys(self, graph):
1751
NULL_REVISION = revision.NULL_REVISION
1752
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1753
if key != NULL_REVISION and parents is not None]
1757
"""Return false if the search lists 1 or more revisions."""
1758
if revision.NULL_REVISION in self.heads:
1759
return len(self.heads) == 1
1761
return len(self.heads) == 0
1763
def refine(self, seen, referenced):
1764
"""Create a new search by refining this search.
1766
:param seen: Revisions that have been satisfied.
1767
:param referenced: Revision references observed while satisfying some
1770
referenced = self.heads.union(referenced)
1771
return PendingAncestryResult(referenced - seen, self.repo)
1774
class EmptySearchResult(AbstractSearchResult):
1775
"""An empty search result."""
1781
class EverythingResult(AbstractSearchResult):
1782
"""A search result that simply requests everything in the repository."""
1784
def __init__(self, repo):
1788
return '%s(%r)' % (self.__class__.__name__, self._repo)
1790
def get_recipe(self):
1791
raise NotImplementedError(self.get_recipe)
1793
def get_network_struct(self):
1794
return ('everything',)
1797
if 'evil' in debug.debug_flags:
1798
from bzrlib import remote
1799
if isinstance(self._repo, remote.RemoteRepository):
1800
# warn developers (not users) not to do this
1801
trace.mutter_callsite(
1802
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1803
return self._repo.all_revision_ids()
1806
# It's ok for this to wrongly return False: the worst that can happen
1807
# is that RemoteStreamSource will initiate a get_stream on an empty
1808
# repository. And almost all repositories are non-empty.
1811
def refine(self, seen, referenced):
1812
heads = set(self._repo.all_revision_ids())
1813
heads.difference_update(seen)
1814
heads.update(referenced)
1815
return PendingAncestryResult(heads, self._repo)
1818
class EverythingNotInOther(AbstractSearch):
1819
"""Find all revisions in that are in one repo but not the other."""
1821
def __init__(self, to_repo, from_repo, find_ghosts=False):
1822
self.to_repo = to_repo
1823
self.from_repo = from_repo
1824
self.find_ghosts = find_ghosts
1827
return self.to_repo.search_missing_revision_ids(
1828
self.from_repo, find_ghosts=self.find_ghosts)
1831
class NotInOtherForRevs(AbstractSearch):
1832
"""Find all revisions missing in one repo for a some specific heads."""
1834
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1838
:param required_ids: revision IDs of heads that must be found, or else
1839
the search will fail with NoSuchRevision. All revisions in their
1840
ancestry not already in the other repository will be included in
1842
:param if_present_ids: revision IDs of heads that may be absent in the
1843
source repository. If present, then their ancestry not already
1844
found in other will be included in the search result.
1846
self.to_repo = to_repo
1847
self.from_repo = from_repo
1848
self.find_ghosts = find_ghosts
1849
self.required_ids = required_ids
1850
self.if_present_ids = if_present_ids
1853
if len(self.required_ids) > 5:
1854
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1856
reqd_revs_repr = repr(self.required_ids)
1857
if self.if_present_ids and len(self.if_present_ids) > 5:
1858
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1860
ifp_revs_repr = repr(self.if_present_ids)
1862
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1863
self.__class__.__name__, self.from_repo, self.to_repo,
1864
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1867
return self.to_repo.search_missing_revision_ids(
1868
self.from_repo, revision_ids=self.required_ids,
1869
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1597
def invert_parent_map(parent_map):
1598
"""Given a map from child => parents, create a map of parent=>children"""
1600
for child, parents in parent_map.iteritems():
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,)
1608
child_map[p] = child_map[p] + (child,)
1872
1612
def collapse_linear_regions(parent_map):
added
removed
bzrlib/graph.py
