59
58
def __repr__(self):
60
59
return 'DictParentsProvider(%r)' % self.ancestry
61
# Note: DictParentsProvider does not implement get_cached_parent_map
62
# Arguably, the data is clearly cached in memory. However, this class
63
# is mostly used for testing, and it keeps the tests clean to not
62
66
def get_parent_map(self, keys):
63
67
"""See StackedParentsProvider.get_parent_map"""
64
68
ancestry = self.ancestry
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
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
72
class StackedParentsProvider(object):
72
73
"""A parents provider which stacks (or unions) multiple providers.
74
75
The providers are queries in the order of the provided parent_providers.
77
78
def __init__(self, parent_providers):
78
79
self._parent_providers = parent_providers
258
304
right = searchers[1].seen
259
305
return (left.difference(right), right.difference(left))
307
def find_descendants(self, old_key, new_key):
308
"""Find descendants of old_key that are ancestors of new_key."""
309
child_map = self.get_child_map(self._find_descendant_ancestors(
311
graph = Graph(DictParentsProvider(child_map))
312
searcher = graph._make_breadth_first_searcher([old_key])
316
def _find_descendant_ancestors(self, old_key, new_key):
317
"""Find ancestors of new_key that may be descendants of old_key."""
318
stop = self._make_breadth_first_searcher([old_key])
319
descendants = self._make_breadth_first_searcher([new_key])
320
for revisions in descendants:
321
old_stop = stop.seen.intersection(revisions)
322
descendants.stop_searching_any(old_stop)
323
seen_stop = descendants.find_seen_ancestors(stop.step())
324
descendants.stop_searching_any(seen_stop)
325
return descendants.seen.difference(stop.seen)
327
def get_child_map(self, keys):
328
"""Get a mapping from parents to children of the specified keys.
330
This is simply the inversion of get_parent_map. Only supplied keys
331
will be discovered as children.
332
:return: a dict of key:child_list for keys.
334
parent_map = self._parents_provider.get_parent_map(keys)
336
for child, parents in sorted(parent_map.items()):
337
for parent in parents:
338
parent_child.setdefault(parent, []).append(child)
261
341
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
342
"""Find the left-hand distance to the NULL_REVISION.
1463
1584
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)
1587
def invert_parent_map(parent_map):
1588
"""Given a map from child => parents, create a map of parent=>children"""
1590
for child, parents in parent_map.iteritems():
1592
# Any given parent is likely to have only a small handful
1593
# of children, many will have only one. So we avoid mem overhead of
1594
# a list, in exchange for extra copying of tuples
1595
if p not in child_map:
1596
child_map[p] = (child,)
1598
child_map[p] = child_map[p] + (child,)
1609
1602
def collapse_linear_regions(parent_map):
added
removed
bzrlib/graph.py
