1594
1549
return revs, 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,)
1552
class AbstractSearchResult(object):
1553
"""The result of a search, describing a set of keys.
1555
Search results are typically used as the 'fetch_spec' parameter when
1558
:seealso: AbstractSearch
1561
def get_recipe(self):
1562
"""Return a recipe that can be used to replay this search.
1564
The recipe allows reconstruction of the same results at a later date.
1566
:return: A tuple of (search_kind_str, *details). The details vary by
1567
kind of search result.
1569
raise NotImplementedError(self.get_recipe)
1571
def get_network_struct(self):
1572
"""Return a tuple that can be transmitted via the HPSS protocol."""
1573
raise NotImplementedError(self.get_network_struct)
1576
"""Return the keys found in this search.
1578
:return: A set of keys.
1580
raise NotImplementedError(self.get_keys)
1583
"""Return false if the search lists 1 or more revisions."""
1584
raise NotImplementedError(self.is_empty)
1586
def refine(self, seen, referenced):
1587
"""Create a new search by refining this search.
1589
:param seen: Revisions that have been satisfied.
1590
:param referenced: Revision references observed while satisfying some
1592
:return: A search result.
1594
raise NotImplementedError(self.refine)
1597
class AbstractSearch(object):
1598
"""A search that can be executed, producing a search result.
1600
:seealso: AbstractSearchResult
1604
"""Construct a network-ready search result from this search description.
1606
This may take some time to search repositories, etc.
1608
:return: A search result (an object that implements
1609
AbstractSearchResult's API).
1611
raise NotImplementedError(self.execute)
1614
class SearchResult(AbstractSearchResult):
1615
"""The result of a breadth first search.
1617
A SearchResult provides the ability to reconstruct the search or access a
1618
set of the keys the search found.
1621
def __init__(self, start_keys, exclude_keys, key_count, keys):
1622
"""Create a SearchResult.
1624
:param start_keys: The keys the search started at.
1625
:param exclude_keys: The keys the search excludes.
1626
:param key_count: The total number of keys (from start to but not
1628
:param keys: The keys the search found. Note that in future we may get
1629
a SearchResult from a smart server, in which case the keys list is
1630
not necessarily immediately available.
1632
self._recipe = ('search', start_keys, exclude_keys, key_count)
1633
self._keys = frozenset(keys)
1636
kind, start_keys, exclude_keys, key_count = self._recipe
1637
if len(start_keys) > 5:
1638
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1640
start_keys_repr = repr(start_keys)
1641
if len(exclude_keys) > 5:
1642
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1644
exclude_keys_repr = repr(exclude_keys)
1645
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1646
kind, start_keys_repr, exclude_keys_repr, key_count)
1648
def get_recipe(self):
1649
"""Return a recipe that can be used to replay this search.
1651
The recipe allows reconstruction of the same results at a later date
1652
without knowing all the found keys. The essential elements are a list
1653
of keys to start and to stop at. In order to give reproducible
1654
results when ghosts are encountered by a search they are automatically
1655
added to the exclude list (or else ghost filling may alter the
1658
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1659
revision_count). To recreate the results of this search, create a
1660
breadth first searcher on the same graph starting at start_keys.
1661
Then call next() (or next_with_ghosts()) repeatedly, and on every
1662
result, call stop_searching_any on any keys from the exclude_keys
1663
set. The revision_count value acts as a trivial cross-check - the
1664
found revisions of the new search should have as many elements as
1665
revision_count. If it does not, then additional revisions have been
1666
ghosted since the search was executed the first time and the second
1671
def get_network_struct(self):
1672
start_keys = ' '.join(self._recipe[1])
1673
stop_keys = ' '.join(self._recipe[2])
1674
count = str(self._recipe[3])
1675
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1678
"""Return the keys found in this search.
1680
:return: A set of keys.
1685
"""Return false if the search lists 1 or more revisions."""
1686
return self._recipe[3] == 0
1688
def refine(self, seen, referenced):
1689
"""Create a new search by refining this search.
1691
:param seen: Revisions that have been satisfied.
1692
:param referenced: Revision references observed while satisfying some
1695
start = self._recipe[1]
1696
exclude = self._recipe[2]
1697
count = self._recipe[3]
1698
keys = self.get_keys()
1699
# New heads = referenced + old heads - seen things - exclude
1700
pending_refs = set(referenced)
1701
pending_refs.update(start)
1702
pending_refs.difference_update(seen)
1703
pending_refs.difference_update(exclude)
1704
# New exclude = old exclude + satisfied heads
1705
seen_heads = start.intersection(seen)
1706
exclude.update(seen_heads)
1707
# keys gets seen removed
1709
# length is reduced by len(seen)
1711
return SearchResult(pending_refs, exclude, count, keys)
1714
class PendingAncestryResult(AbstractSearchResult):
1715
"""A search result that will reconstruct the ancestry for some graph heads.
1717
Unlike SearchResult, this doesn't hold the complete search result in
1718
memory, it just holds a description of how to generate it.
1721
def __init__(self, heads, repo):
1724
:param heads: an iterable of graph heads.
1725
:param repo: a repository to use to generate the ancestry for the given
1728
self.heads = frozenset(heads)
1732
if len(self.heads) > 5:
1733
heads_repr = repr(list(self.heads)[:5])[:-1]
1734
heads_repr += ', <%d more>...]' % (len(self.heads) - 5,)
1736
heads_repr = repr(self.heads)
1737
return '<%s heads:%s repo:%r>' % (
1738
self.__class__.__name__, heads_repr, self.repo)
1740
def get_recipe(self):
1741
"""Return a recipe that can be used to replay this search.
1743
The recipe allows reconstruction of the same results at a later date.
1745
:seealso SearchResult.get_recipe:
1747
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1748
To recreate this result, create a PendingAncestryResult with the
1751
return ('proxy-search', self.heads, set(), -1)
1753
def get_network_struct(self):
1754
parts = ['ancestry-of']
1755
parts.extend(self.heads)
1759
"""See SearchResult.get_keys.
1761
Returns all the keys for the ancestry of the heads, excluding
1764
return self._get_keys(self.repo.get_graph())
1766
def _get_keys(self, graph):
1767
NULL_REVISION = revision.NULL_REVISION
1768
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1769
if key != NULL_REVISION and parents is not None]
1773
"""Return false if the search lists 1 or more revisions."""
1774
if revision.NULL_REVISION in self.heads:
1775
return len(self.heads) == 1
1777
return len(self.heads) == 0
1779
def refine(self, seen, referenced):
1780
"""Create a new search by refining this search.
1782
:param seen: Revisions that have been satisfied.
1783
:param referenced: Revision references observed while satisfying some
1786
referenced = self.heads.union(referenced)
1787
return PendingAncestryResult(referenced - seen, self.repo)
1790
class EmptySearchResult(AbstractSearchResult):
1791
"""An empty search result."""
1797
class EverythingResult(AbstractSearchResult):
1798
"""A search result that simply requests everything in the repository."""
1800
def __init__(self, repo):
1804
return '%s(%r)' % (self.__class__.__name__, self._repo)
1806
def get_recipe(self):
1807
raise NotImplementedError(self.get_recipe)
1809
def get_network_struct(self):
1810
return ('everything',)
1813
if 'evil' in debug.debug_flags:
1814
from bzrlib import remote
1815
if isinstance(self._repo, remote.RemoteRepository):
1816
# warn developers (not users) not to do this
1817
trace.mutter_callsite(
1818
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1819
return self._repo.all_revision_ids()
1822
# It's ok for this to wrongly return False: the worst that can happen
1823
# is that RemoteStreamSource will initiate a get_stream on an empty
1824
# repository. And almost all repositories are non-empty.
1827
def refine(self, seen, referenced):
1828
heads = set(self._repo.all_revision_ids())
1829
heads.difference_update(seen)
1830
heads.update(referenced)
1831
return PendingAncestryResult(heads, self._repo)
1834
class EverythingNotInOther(AbstractSearch):
1835
"""Find all revisions in that are in one repo but not the other."""
1837
def __init__(self, to_repo, from_repo, find_ghosts=False):
1838
self.to_repo = to_repo
1839
self.from_repo = from_repo
1840
self.find_ghosts = find_ghosts
1843
return self.to_repo.search_missing_revision_ids(
1844
self.from_repo, find_ghosts=self.find_ghosts)
1847
class NotInOtherForRevs(AbstractSearch):
1848
"""Find all revisions missing in one repo for a some specific heads."""
1850
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1854
:param required_ids: revision IDs of heads that must be found, or else
1855
the search will fail with NoSuchRevision. All revisions in their
1856
ancestry not already in the other repository will be included in
1858
:param if_present_ids: revision IDs of heads that may be absent in the
1859
source repository. If present, then their ancestry not already
1860
found in other will be included in the search result.
1862
self.to_repo = to_repo
1863
self.from_repo = from_repo
1864
self.find_ghosts = find_ghosts
1865
self.required_ids = required_ids
1866
self.if_present_ids = if_present_ids
1869
if len(self.required_ids) > 5:
1870
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1872
reqd_revs_repr = repr(self.required_ids)
1873
if self.if_present_ids and len(self.if_present_ids) > 5:
1874
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1876
ifp_revs_repr = repr(self.if_present_ids)
1878
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1879
self.__class__.__name__, self.from_repo, self.to_repo,
1880
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1883
return self.to_repo.search_missing_revision_ids(
1884
self.from_repo, revision_ids=self.required_ids,
1885
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1612
1888
def collapse_linear_regions(parent_map):
added
removed
bzrlib/graph.py
