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
258
306
right = searchers[1].seen
259
307
return (left.difference(right), right.difference(left))
309
def find_descendants(self, old_key, new_key):
310
"""Find descendants of old_key that are ancestors of new_key."""
311
child_map = self.get_child_map(self._find_descendant_ancestors(
313
graph = Graph(DictParentsProvider(child_map))
314
searcher = graph._make_breadth_first_searcher([old_key])
318
def _find_descendant_ancestors(self, old_key, new_key):
319
"""Find ancestors of new_key that may be descendants of old_key."""
320
stop = self._make_breadth_first_searcher([old_key])
321
descendants = self._make_breadth_first_searcher([new_key])
322
for revisions in descendants:
323
old_stop = stop.seen.intersection(revisions)
324
descendants.stop_searching_any(old_stop)
325
seen_stop = descendants.find_seen_ancestors(stop.step())
326
descendants.stop_searching_any(seen_stop)
327
return descendants.seen.difference(stop.seen)
329
def get_child_map(self, keys):
330
"""Get a mapping from parents to children of the specified keys.
332
This is simply the inversion of get_parent_map. Only supplied keys
333
will be discovered as children.
334
:return: a dict of key:child_list for keys.
336
parent_map = self._parents_provider.get_parent_map(keys)
338
for child, parents in sorted(parent_map.items()):
339
for parent in parents:
340
parent_child.setdefault(parent, []).append(child)
261
343
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
344
"""Find the left-hand distance to the NULL_REVISION.
1249
1368
next_query = self._next_query
1250
1369
excludes = self._stopped_keys.union(next_query)
1251
1370
included_keys = self.seen.difference(excludes)
1252
return SearchResult(self._started_keys, excludes, len(included_keys),
1371
return self._started_keys, excludes, included_keys
1373
def _get_result(self):
1374
"""Get a SearchResult for the current state of this searcher.
1376
:return: A SearchResult for this search so far. The SearchResult is
1377
static - the search can be advanced and the search result will not
1378
be invalidated or altered.
1380
from breezy.vf_search import SearchResult
1381
(started_keys, excludes, included_keys) = self.get_state()
1382
return SearchResult(started_keys, excludes, len(included_keys),
1255
1385
def step(self):
1258
1388
except StopIteration:
1262
1392
"""Return the next ancestors of this revision.
1264
1394
Ancestors are returned in the order they are seen in a breadth-first
1463
1596
return revs, ghosts
1466
class SearchResult(object):
1467
"""The result of a breadth first search.
1469
A SearchResult provides the ability to reconstruct the search or access a
1470
set of the keys the search found.
1473
def __init__(self, start_keys, exclude_keys, key_count, keys):
1474
"""Create a SearchResult.
1476
:param start_keys: The keys the search started at.
1477
:param exclude_keys: The keys the search excludes.
1478
:param key_count: The total number of keys (from start to but not
1480
:param keys: The keys the search found. Note that in future we may get
1481
a SearchResult from a smart server, in which case the keys list is
1482
not necessarily immediately available.
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
self._keys = frozenset(keys)
1487
def get_recipe(self):
1488
"""Return a recipe that can be used to replay this search.
1490
The recipe allows reconstruction of the same results at a later date
1491
without knowing all the found keys. The essential elements are a list
1492
of keys to start and to stop at. In order to give reproducible
1493
results when ghosts are encountered by a search they are automatically
1494
added to the exclude list (or else ghost filling may alter the
1497
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1498
revision_count). To recreate the results of this search, create a
1499
breadth first searcher on the same graph starting at start_keys.
1500
Then call next() (or next_with_ghosts()) repeatedly, and on every
1501
result, call stop_searching_any on any keys from the exclude_keys
1502
set. The revision_count value acts as a trivial cross-check - the
1503
found revisions of the new search should have as many elements as
1504
revision_count. If it does not, then additional revisions have been
1505
ghosted since the search was executed the first time and the second
1511
"""Return the keys found in this search.
1513
:return: A set of keys.
1518
"""Return false if the search lists 1 or more revisions."""
1519
return self._recipe[3] == 0
1521
def refine(self, seen, referenced):
1522
"""Create a new search by refining this search.
1524
:param seen: Revisions that have been satisfied.
1525
:param referenced: Revision references observed while satisfying some
1528
start = self._recipe[1]
1529
exclude = self._recipe[2]
1530
count = self._recipe[3]
1531
keys = self.get_keys()
1532
# New heads = referenced + old heads - seen things - exclude
1533
pending_refs = set(referenced)
1534
pending_refs.update(start)
1535
pending_refs.difference_update(seen)
1536
pending_refs.difference_update(exclude)
1537
# New exclude = old exclude + satisfied heads
1538
seen_heads = start.intersection(seen)
1539
exclude.update(seen_heads)
1540
# keys gets seen removed
1542
# length is reduced by len(seen)
1544
return SearchResult(pending_refs, exclude, count, keys)
1547
class PendingAncestryResult(object):
1548
"""A search result that will reconstruct the ancestry for some graph heads.
1550
Unlike SearchResult, this doesn't hold the complete search result in
1551
memory, it just holds a description of how to generate it.
1554
def __init__(self, heads, repo):
1557
:param heads: an iterable of graph heads.
1558
:param repo: a repository to use to generate the ancestry for the given
1561
self.heads = frozenset(heads)
1564
def get_recipe(self):
1565
"""Return a recipe that can be used to replay this search.
1567
The recipe allows reconstruction of the same results at a later date.
1569
:seealso SearchResult.get_recipe:
1571
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1572
To recreate this result, create a PendingAncestryResult with the
1575
return ('proxy-search', self.heads, set(), -1)
1578
"""See SearchResult.get_keys.
1580
Returns all the keys for the ancestry of the heads, excluding
1583
return self._get_keys(self.repo.get_graph())
1585
def _get_keys(self, graph):
1586
NULL_REVISION = revision.NULL_REVISION
1587
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1588
if key != NULL_REVISION and parents is not None]
1592
"""Return false if the search lists 1 or more revisions."""
1593
if revision.NULL_REVISION in self.heads:
1594
return len(self.heads) == 1
1596
return len(self.heads) == 0
1598
def refine(self, seen, referenced):
1599
"""Create a new search by refining this search.
1601
:param seen: Revisions that have been satisfied.
1602
:param referenced: Revision references observed while satisfying some
1605
referenced = self.heads.union(referenced)
1606
return PendingAncestryResult(referenced - seen, self.repo)
1599
def invert_parent_map(parent_map):
1600
"""Given a map from child => parents, create a map of parent=>children"""
1602
for child, parents in parent_map.iteritems():
1604
# Any given parent is likely to have only a small handful
1605
# of children, many will have only one. So we avoid mem overhead of
1606
# a list, in exchange for extra copying of tuples
1607
if p not in child_map:
1608
child_map[p] = (child,)
1610
child_map[p] = child_map[p] + (child,)
1609
1614
def collapse_linear_regions(parent_map):
1692
1697
"""See Graph.heads()"""
1693
1698
as_keys = [(i,) for i in ids]
1694
1699
head_keys = self._graph.heads(as_keys)
1695
return set([h[0] for h in head_keys])
1700
return {h[0] for h in head_keys}
1697
1702
def merge_sort(self, tip_revision):
1698
return self._graph.merge_sort((tip_revision,))
1703
nodes = self._graph.merge_sort((tip_revision,))
1705
node.key = node.key[0]
1708
def add_node(self, revision, parents):
1709
self._graph.add_node((revision,), [(p,) for p in parents])
1701
1712
_counters = [0,0,0,0,0,0,0]
1703
from bzrlib._known_graph_pyx import KnownGraph
1704
except ImportError, e:
1714
from ._known_graph_pyx import KnownGraph
1715
except ImportError as e:
1705
1716
osutils.failed_to_load_extension(e)
1706
from bzrlib._known_graph_py import KnownGraph
1717
from ._known_graph_py import KnownGraph
added
removed
breezy/graph.py
