59
60
def __repr__(self):
60
61
return 'DictParentsProvider(%r)' % self.ancestry
63
# Note: DictParentsProvider does not implement get_cached_parent_map
64
# Arguably, the data is clearly cached in memory. However, this class
65
# is mostly used for testing, and it keeps the tests clean to not
62
68
def get_parent_map(self, keys):
63
69
"""See StackedParentsProvider.get_parent_map"""
64
70
ancestry = self.ancestry
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
71
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
67
@deprecated_function(deprecated_in((1, 16, 0)))
68
def _StackedParentsProvider(*args, **kwargs):
69
return StackedParentsProvider(*args, **kwargs)
71
74
class StackedParentsProvider(object):
72
75
"""A parents provider which stacks (or unions) multiple providers.
74
77
The providers are queries in the order of the provided parent_providers.
77
80
def __init__(self, parent_providers):
78
81
self._parent_providers = parent_providers
1536
1594
return revs, ghosts
1539
class SearchResult(object):
1540
"""The result of a breadth first search.
1542
A SearchResult provides the ability to reconstruct the search or access a
1543
set of the keys the search found.
1546
def __init__(self, start_keys, exclude_keys, key_count, keys):
1547
"""Create a SearchResult.
1549
:param start_keys: The keys the search started at.
1550
:param exclude_keys: The keys the search excludes.
1551
:param key_count: The total number of keys (from start to but not
1553
:param keys: The keys the search found. Note that in future we may get
1554
a SearchResult from a smart server, in which case the keys list is
1555
not necessarily immediately available.
1557
self._recipe = ('search', start_keys, exclude_keys, key_count)
1558
self._keys = frozenset(keys)
1560
def get_recipe(self):
1561
"""Return a recipe that can be used to replay this search.
1563
The recipe allows reconstruction of the same results at a later date
1564
without knowing all the found keys. The essential elements are a list
1565
of keys to start and to stop at. In order to give reproducible
1566
results when ghosts are encountered by a search they are automatically
1567
added to the exclude list (or else ghost filling may alter the
1570
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1571
revision_count). To recreate the results of this search, create a
1572
breadth first searcher on the same graph starting at start_keys.
1573
Then call next() (or next_with_ghosts()) repeatedly, and on every
1574
result, call stop_searching_any on any keys from the exclude_keys
1575
set. The revision_count value acts as a trivial cross-check - the
1576
found revisions of the new search should have as many elements as
1577
revision_count. If it does not, then additional revisions have been
1578
ghosted since the search was executed the first time and the second
1584
"""Return the keys found in this search.
1586
:return: A set of keys.
1591
"""Return false if the search lists 1 or more revisions."""
1592
return self._recipe[3] == 0
1594
def refine(self, seen, referenced):
1595
"""Create a new search by refining this search.
1597
:param seen: Revisions that have been satisfied.
1598
:param referenced: Revision references observed while satisfying some
1601
start = self._recipe[1]
1602
exclude = self._recipe[2]
1603
count = self._recipe[3]
1604
keys = self.get_keys()
1605
# New heads = referenced + old heads - seen things - exclude
1606
pending_refs = set(referenced)
1607
pending_refs.update(start)
1608
pending_refs.difference_update(seen)
1609
pending_refs.difference_update(exclude)
1610
# New exclude = old exclude + satisfied heads
1611
seen_heads = start.intersection(seen)
1612
exclude.update(seen_heads)
1613
# keys gets seen removed
1615
# length is reduced by len(seen)
1617
return SearchResult(pending_refs, exclude, count, keys)
1620
class PendingAncestryResult(object):
1621
"""A search result that will reconstruct the ancestry for some graph heads.
1623
Unlike SearchResult, this doesn't hold the complete search result in
1624
memory, it just holds a description of how to generate it.
1627
def __init__(self, heads, repo):
1630
:param heads: an iterable of graph heads.
1631
:param repo: a repository to use to generate the ancestry for the given
1634
self.heads = frozenset(heads)
1637
def get_recipe(self):
1638
"""Return a recipe that can be used to replay this search.
1640
The recipe allows reconstruction of the same results at a later date.
1642
:seealso SearchResult.get_recipe:
1644
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1645
To recreate this result, create a PendingAncestryResult with the
1648
return ('proxy-search', self.heads, set(), -1)
1651
"""See SearchResult.get_keys.
1653
Returns all the keys for the ancestry of the heads, excluding
1656
return self._get_keys(self.repo.get_graph())
1658
def _get_keys(self, graph):
1659
NULL_REVISION = revision.NULL_REVISION
1660
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1661
if key != NULL_REVISION and parents is not None]
1665
"""Return false if the search lists 1 or more revisions."""
1666
if revision.NULL_REVISION in self.heads:
1667
return len(self.heads) == 1
1669
return len(self.heads) == 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
referenced = self.heads.union(referenced)
1679
return PendingAncestryResult(referenced - seen, self.repo)
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,)
1682
1612
def collapse_linear_regions(parent_map):
added
removed
bzrlib/graph.py
