1532
1594
return revs, ghosts
1535
class AbstractSearchResult(object):
1536
"""The result of a search, describing a set of keys.
1538
Search results are typically used as the 'fetch_spec' parameter when
1541
:seealso: AbstractSearch
1544
def get_recipe(self):
1545
"""Return a recipe that can be used to replay this search.
1547
The recipe allows reconstruction of the same results at a later date.
1549
:return: A tuple of (search_kind_str, *details). The details vary by
1550
kind of search result.
1552
raise NotImplementedError(self.get_recipe)
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)
1559
"""Return the keys found in this search.
1561
:return: A set of keys.
1563
raise NotImplementedError(self.get_keys)
1566
"""Return false if the search lists 1 or more revisions."""
1567
raise NotImplementedError(self.is_empty)
1569
def refine(self, seen, referenced):
1570
"""Create a new search by refining this search.
1572
:param seen: Revisions that have been satisfied.
1573
:param referenced: Revision references observed while satisfying some
1575
:return: A search result.
1577
raise NotImplementedError(self.refine)
1580
class AbstractSearch(object):
1581
"""A search that can be executed, producing a search result.
1583
:seealso: AbstractSearchResult
1587
"""Construct a network-ready search result from this search description.
1589
This may take some time to search repositories, etc.
1591
:return: A search result (an object that implements
1592
AbstractSearchResult's API).
1594
raise NotImplementedError(self.execute)
1597
class SearchResult(AbstractSearchResult):
1598
"""The result of a breadth first search.
1600
A SearchResult provides the ability to reconstruct the search or access a
1601
set of the keys the search found.
1604
def __init__(self, start_keys, exclude_keys, key_count, keys):
1605
"""Create a SearchResult.
1607
:param start_keys: The keys the search started at.
1608
:param exclude_keys: The keys the search excludes.
1609
:param key_count: The total number of keys (from start to but not
1611
:param keys: The keys the search found. Note that in future we may get
1612
a SearchResult from a smart server, in which case the keys list is
1613
not necessarily immediately available.
1615
self._recipe = ('search', start_keys, exclude_keys, key_count)
1616
self._keys = frozenset(keys)
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] + ', ...]'
1623
start_keys_repr = repr(start_keys)
1624
if len(exclude_keys) > 5:
1625
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
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)
1631
def get_recipe(self):
1632
"""Return a recipe that can be used to replay this search.
1634
The recipe allows reconstruction of the same results at a later date
1635
without knowing all the found keys. The essential elements are a list
1636
of keys to start and to stop at. In order to give reproducible
1637
results when ghosts are encountered by a search they are automatically
1638
added to the exclude list (or else ghost filling may alter the
1641
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1642
revision_count). To recreate the results of this search, create a
1643
breadth first searcher on the same graph starting at start_keys.
1644
Then call next() (or next_with_ghosts()) repeatedly, and on every
1645
result, call stop_searching_any on any keys from the exclude_keys
1646
set. The revision_count value acts as a trivial cross-check - the
1647
found revisions of the new search should have as many elements as
1648
revision_count. If it does not, then additional revisions have been
1649
ghosted since the search was executed the first time and the second
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)))
1661
"""Return the keys found in this search.
1663
:return: A set of keys.
1668
"""Return false if the search lists 1 or more revisions."""
1669
return self._recipe[3] == 0
1671
def refine(self, seen, referenced):
1672
"""Create a new search by refining this search.
1674
:param seen: Revisions that have been satisfied.
1675
:param referenced: Revision references observed while satisfying some
1678
start = self._recipe[1]
1679
exclude = self._recipe[2]
1680
count = self._recipe[3]
1681
keys = self.get_keys()
1682
# New heads = referenced + old heads - seen things - exclude
1683
pending_refs = set(referenced)
1684
pending_refs.update(start)
1685
pending_refs.difference_update(seen)
1686
pending_refs.difference_update(exclude)
1687
# New exclude = old exclude + satisfied heads
1688
seen_heads = start.intersection(seen)
1689
exclude.update(seen_heads)
1690
# keys gets seen removed
1692
# length is reduced by len(seen)
1694
return SearchResult(pending_refs, exclude, count, keys)
1697
class PendingAncestryResult(AbstractSearchResult):
1698
"""A search result that will reconstruct the ancestry for some graph heads.
1700
Unlike SearchResult, this doesn't hold the complete search result in
1701
memory, it just holds a description of how to generate it.
1704
def __init__(self, heads, repo):
1707
:param heads: an iterable of graph heads.
1708
:param repo: a repository to use to generate the ancestry for the given
1711
self.heads = frozenset(heads)
1715
if len(self.heads) > 5:
1716
heads_repr = repr(list(self.heads)[:5])[:-1]
1717
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1719
heads_repr = repr(self.heads)
1720
return '<%s heads:%s repo:%r>' % (
1721
self.__class__.__name__, heads_repr, self.repo)
1723
def get_recipe(self):
1724
"""Return a recipe that can be used to replay this search.
1726
The recipe allows reconstruction of the same results at a later date.
1728
:seealso SearchResult.get_recipe:
1730
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1731
To recreate this result, create a PendingAncestryResult with the
1734
return ('proxy-search', self.heads, set(), -1)
1736
def get_network_struct(self):
1737
parts = ['ancestry-of']
1738
parts.extend(self.heads)
1742
"""See SearchResult.get_keys.
1744
Returns all the keys for the ancestry of the heads, excluding
1747
return self._get_keys(self.repo.get_graph())
1749
def _get_keys(self, graph):
1750
NULL_REVISION = revision.NULL_REVISION
1751
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1752
if key != NULL_REVISION and parents is not None]
1756
"""Return false if the search lists 1 or more revisions."""
1757
if revision.NULL_REVISION in self.heads:
1758
return len(self.heads) == 1
1760
return len(self.heads) == 0
1762
def refine(self, seen, referenced):
1763
"""Create a new search by refining this search.
1765
:param seen: Revisions that have been satisfied.
1766
:param referenced: Revision references observed while satisfying some
1769
referenced = self.heads.union(referenced)
1770
return PendingAncestryResult(referenced - seen, self.repo)
1773
class EmptySearchResult(AbstractSearchResult):
1774
"""An empty search result."""
1780
class EverythingResult(AbstractSearchResult):
1781
"""A search result that simply requests everything in the repository."""
1783
def __init__(self, repo):
1787
return '%s(%r)' % (self.__class__.__name__, self._repo)
1789
def get_recipe(self):
1790
raise NotImplementedError(self.get_recipe)
1792
def get_network_struct(self):
1793
return ('everything',)
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()
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.
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)
1817
class EverythingNotInOther(AbstractSearch):
1818
"""Find all revisions in that are in one repo but not the other."""
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
1826
return self.to_repo.search_missing_revision_ids(
1827
self.from_repo, find_ghosts=self.find_ghosts)
1830
class NotInOtherForRevs(AbstractSearch):
1831
"""Find all revisions missing in one repo for a some specific heads."""
1833
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
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
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.
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
1852
if len(self.required_ids) > 5:
1853
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
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] + ', ...]'
1859
ifp_revs_repr = repr(self.if_present_ids)
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)
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)
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,)
1871
1612
def collapse_linear_regions(parent_map):
added
removed
bzrlib/graph.py
