68
53
def __repr__(self):
69
54
return "_StackedParentsProvider(%r)" % self._parent_providers
71
def get_parent_map(self, keys):
72
"""Get a mapping of keys => parents
56
def get_parents(self, revision_ids):
57
"""Find revision ids of the parents of a list of revisions
74
A dictionary is returned with an entry for each key present in this
75
source. If this source doesn't have information about a key, it should
59
A list is returned of the same length as the input. Each entry
60
is a list of parent ids for the corresponding input revision.
78
62
[NULL_REVISION] is used as the parent of the first user-committed
79
63
revision. Its parent list is empty.
81
:param keys: An iterable returning keys to check (eg revision_ids)
82
:return: A dictionary mapping each key to its parents
65
If the revision is not present (i.e. a ghost), None is used in place
66
of the list of parents.
86
69
for parents_provider in self._parent_providers:
87
new_found = parents_provider.get_parent_map(remaining)
70
pending_revisions = [r for r in revision_ids if r not in found]
71
parent_list = parents_provider.get_parents(pending_revisions)
72
new_found = dict((k, v) for k, v in zip(pending_revisions,
73
parent_list) if v is not None)
88
74
found.update(new_found)
89
remaining.difference_update(new_found)
75
if len(found) == len(revision_ids):
95
class CachingParentsProvider(object):
96
"""A parents provider which will cache the revision => parents in a dict.
98
This is useful for providers that have an expensive lookup.
101
def __init__(self, parent_provider):
102
self._real_provider = parent_provider
103
# Theoretically we could use an LRUCache here
107
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
109
def get_parent_map(self, keys):
110
"""See _StackedParentsProvider.get_parent_map"""
112
# If the _real_provider doesn't have a key, we cache a value of None,
113
# which we then later use to realize we cannot provide a value for that
120
if value is not None:
121
parent_map[key] = value
126
new_parents = self._real_provider.get_parent_map(needed)
127
cache.update(new_parents)
128
parent_map.update(new_parents)
129
needed.difference_update(new_parents)
130
cache.update(dict.fromkeys(needed, None))
77
return [found.get(r, None) for r in revision_ids]
134
80
class Graph(object):
204
143
return (left.difference(right).difference(common),
205
144
right.difference(left).difference(common))
207
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
def get_parents(self, revisions):
209
"""Find revision ids of the parents of a list of revisions
211
A list is returned of the same length as the input. Each entry
212
is a list of parent ids for the corresponding input revision.
214
[NULL_REVISION] is used as the parent of the first user-committed
215
revision. Its parent list is empty.
217
If the revision is not present (i.e. a ghost), None is used in place
218
of the list of parents.
220
Deprecated in bzr 1.2 - please see get_parent_map.
222
parents = self.get_parent_map(revisions)
223
return [parent.get(r, None) for r in revisions]
225
def get_parent_map(self, revisions):
226
"""Get a map of key:parent_list for revisions.
228
This implementation delegates to get_parents, for old parent_providers
229
that do not supply get_parent_map.
232
for rev, parents in self.get_parents(revisions):
233
if parents is not None:
234
result[rev] = parents
237
146
def _make_breadth_first_searcher(self, revisions):
238
147
return _BreadthFirstSearcher(revisions, self)
303
212
for searcher in searchers:
304
213
update_common(searcher, revision)
306
def heads(self, keys):
307
"""Return the heads from amongst keys.
309
This is done by searching the ancestries of each key. Any key that is
310
reachable from another key is not returned; all the others are.
312
This operation scales with the relative depth between any two keys. If
313
any two keys are completely disconnected all ancestry of both sides
316
:param keys: An iterable of keys.
317
:return: A set of the heads. Note that as a set there is no ordering
318
information. Callers will need to filter their input to create
319
order if they need it.
215
def _filter_candidate_lca(self, candidate_lca):
216
"""Remove candidates which are ancestors of other candidates.
218
This is done by searching the ancestries of each border ancestor. It
219
is perfomed on the principle that a border ancestor that is not an
220
ancestor of any other border ancestor is a lowest common ancestor.
222
Searches are stopped when they find a node that is determined to be a
223
common ancestor of all border ancestors, because this shows that it
224
cannot be a descendant of any border ancestor.
226
This will scale with the number of candidate ancestors and the length
227
of the shortest path from a candidate to an ancestor common to all
321
candidate_heads = set(keys)
322
if revision.NULL_REVISION in candidate_heads:
323
# NULL_REVISION is only a head if it is the only entry
324
candidate_heads.remove(revision.NULL_REVISION)
325
if not candidate_heads:
326
return set([revision.NULL_REVISION])
327
if len(candidate_heads) < 2:
328
return candidate_heads
329
230
searchers = dict((c, self._make_breadth_first_searcher([c]))
330
for c in candidate_heads)
231
for c in candidate_lca)
331
232
active_searchers = dict(searchers)
332
233
# skip over the actual candidate for each searcher
333
234
for searcher in active_searchers.itervalues():
335
# The common walker finds nodes that are common to two or more of the
336
# input keys, so that we don't access all history when a currently
337
# uncommon search point actually meets up with something behind a
338
# common search point. Common search points do not keep searches
339
# active; they just allow us to make searches inactive without
340
# accessing all history.
341
common_walker = self._make_breadth_first_searcher([])
342
236
while len(active_searchers) > 0:
347
except StopIteration:
348
# No common points being searched at this time.
350
237
for candidate in active_searchers.keys():
352
239
searcher = active_searchers[candidate]
356
243
# a descendant of another candidate.
359
ancestors.update(searcher.next())
246
ancestors = searcher.next()
360
247
except StopIteration:
361
248
del active_searchers[candidate]
363
# process found nodes
365
for ancestor in ancestors:
366
if ancestor in candidate_heads:
367
candidate_heads.remove(ancestor)
368
del searchers[ancestor]
369
if ancestor in active_searchers:
370
del active_searchers[ancestor]
371
# it may meet up with a known common node
372
if ancestor in common_walker.seen:
373
# some searcher has encountered our known common nodes:
375
ancestor_set = set([ancestor])
376
for searcher in searchers.itervalues():
377
searcher.stop_searching_any(ancestor_set)
379
# or it may have been just reached by all the searchers:
250
for ancestor in ancestors:
251
if ancestor in candidate_lca:
252
candidate_lca.remove(ancestor)
253
del searchers[ancestor]
254
if ancestor in active_searchers:
255
del active_searchers[ancestor]
380
256
for searcher in searchers.itervalues():
381
257
if ancestor not in searcher.seen:
384
# The final active searcher has just reached this node,
385
# making it be known as a descendant of all candidates,
386
# so we can stop searching it, and any seen ancestors
387
new_common.add(ancestor)
260
# if this revision was seen by all searchers, then it
261
# is a descendant of all candidates, so we can stop
262
# searching it, and any seen ancestors
388
263
for searcher in searchers.itervalues():
389
264
seen_ancestors =\
390
265
searcher.find_seen_ancestors(ancestor)
391
266
searcher.stop_searching_any(seen_ancestors)
392
common_walker.start_searching(new_common)
393
return candidate_heads
395
def find_unique_lca(self, left_revision, right_revision,
269
def find_unique_lca(self, left_revision, right_revision):
397
270
"""Find a unique LCA.
399
272
Find lowest common ancestors. If there is no unique common
405
278
Note that None is not an acceptable substitute for NULL_REVISION.
406
279
in the input for this method.
408
:param count_steps: If True, the return value will be a tuple of
409
(unique_lca, steps) where steps is the number of times that
410
find_lca was run. If False, only unique_lca is returned.
412
281
revisions = [left_revision, right_revision]
416
283
lca = self.find_lca(*revisions)
417
284
if len(lca) == 1:
423
286
if len(lca) == 0:
424
287
raise errors.NoCommonAncestor(left_revision, right_revision)
427
def iter_ancestry(self, revision_ids):
428
"""Iterate the ancestry of this revision.
430
:param revision_ids: Nodes to start the search
431
:return: Yield tuples mapping a revision_id to its parents for the
432
ancestry of revision_id.
433
Ghosts will be returned with None as their parents, and nodes
434
with no parents will have NULL_REVISION as their only parent. (As
435
defined by get_parent_map.)
436
There will also be a node for (NULL_REVISION, ())
438
pending = set(revision_ids)
441
processed.update(pending)
442
next_map = self.get_parent_map(pending)
444
for item in next_map.iteritems():
446
next_pending.update(p for p in item[1] if p not in processed)
447
ghosts = pending.difference(next_map)
450
pending = next_pending
452
290
def iter_topo_order(self, revisions):
453
291
"""Iterate through the input revisions in topological order.
456
294
An ancestor may sort after a descendant if the relationship is not
457
295
visible in the supplied list of revisions.
459
sorter = tsort.TopoSorter(self.get_parent_map(revisions))
297
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
460
298
return sorter.iter_topo_order()
462
300
def is_ancestor(self, candidate_ancestor, candidate_descendant):
463
301
"""Determine whether a revision is an ancestor of another.
465
We answer this using heads() as heads() has the logic to perform the
466
smallest number of parent lookups to determine the ancestral
467
relationship between N revisions.
469
return set([candidate_descendant]) == self.heads(
470
[candidate_ancestor, candidate_descendant])
473
class HeadsCache(object):
474
"""A cache of results for graph heads calls."""
476
def __init__(self, graph):
480
def heads(self, keys):
481
"""Return the heads of keys.
483
This matches the API of Graph.heads(), specifically the return value is
484
a set which can be mutated, and ordering of the input is not preserved
487
:see also: Graph.heads.
488
:param keys: The keys to calculate heads for.
489
:return: A set containing the heads, which may be mutated without
490
affecting future lookups.
492
keys = frozenset(keys)
494
return set(self._heads[keys])
496
heads = self.graph.heads(keys)
497
self._heads[keys] = heads
501
class FrozenHeadsCache(object):
502
"""Cache heads() calls, assuming the caller won't modify them."""
504
def __init__(self, graph):
508
def heads(self, keys):
509
"""Return the heads of keys.
511
Similar to Graph.heads(). The main difference is that the return value
512
is a frozen set which cannot be mutated.
514
:see also: Graph.heads.
515
:param keys: The keys to calculate heads for.
516
:return: A frozenset containing the heads.
518
keys = frozenset(keys)
520
return self._heads[keys]
522
heads = frozenset(self.graph.heads(keys))
523
self._heads[keys] = heads
526
def cache(self, keys, heads):
527
"""Store a known value."""
528
self._heads[frozenset(keys)] = frozenset(heads)
303
There are two possible outcomes: True and False, but there are three
304
possible relationships:
306
a) candidate_ancestor is an ancestor of candidate_descendant
307
b) candidate_ancestor is an descendant of candidate_descendant
308
c) candidate_ancestor is an sibling of candidate_descendant
310
To check for a, we walk from candidate_descendant, looking for
313
To check for b, we walk from candidate_ancestor, looking for
314
candidate_descendant.
316
To make a and b more efficient, we can stop any searches that hit
319
If we exhaust our searches, but neither a or b is true, then c is true.
321
In order to find c efficiently, we must avoid searching from
322
candidate_descendant or candidate_ancestor into common ancestors. But
323
if we don't search common ancestors at all, we won't know if we hit
324
common ancestors. So we have a walker for common ancestors. Note that
325
its searches are not required to terminate in order to determine c to
328
ancestor_walker = self._make_breadth_first_searcher(
329
[candidate_ancestor])
330
descendant_walker = self._make_breadth_first_searcher(
331
[candidate_descendant])
332
common_walker = self._make_breadth_first_searcher([])
333
active_ancestor = True
334
active_descendant = True
335
while (active_ancestor or active_descendant):
337
if active_descendant:
339
nodes = descendant_walker.next()
340
except StopIteration:
341
active_descendant = False
343
if candidate_ancestor in nodes:
345
new_common.update(nodes.intersection(ancestor_walker.seen))
348
nodes = ancestor_walker.next()
349
except StopIteration:
350
active_ancestor = False
352
if candidate_descendant in nodes:
354
new_common.update(nodes.intersection(
355
descendant_walker.seen))
357
new_common.update(common_walker.next())
358
except StopIteration:
360
for walker in (ancestor_walker, descendant_walker):
361
for node in new_common:
362
c_ancestors = walker.find_seen_ancestors(node)
363
walker.stop_searching_any(c_ancestors)
364
common_walker.start_searching(new_common)
531
368
class _BreadthFirstSearcher(object):
532
"""Parallel search breadth-first the ancestry of revisions.
369
"""Parallel search the breadth-first the ancestry of revisions.
534
371
This class implements the iterator protocol, but additionally
535
372
1. provides a set of seen ancestors, and
539
376
def __init__(self, revisions, parents_provider):
541
self._next_query = set(revisions)
543
self._started_keys = set(self._next_query)
544
self._stopped_keys = set()
545
self._parents_provider = parents_provider
546
self._returning = 'next_with_ghosts'
547
self._current_present = set()
548
self._current_ghosts = set()
549
self._current_parents = {}
377
self._start = set(revisions)
378
self._search_revisions = None
379
self.seen = set(revisions)
380
self._parents_provider = parents_provider
551
382
def __repr__(self):
556
search = '%s=%r' % (prefix, list(self._next_query))
557
return ('_BreadthFirstSearcher(iterations=%d, %s,'
558
' seen=%r)' % (self._iterations, search, list(self.seen)))
560
def get_result(self):
561
"""Get a SearchResult for the current state of this searcher.
563
:return: A SearchResult for this search so far. The SearchResult is
564
static - the search can be advanced and the search result will not
565
be invalidated or altered.
567
if self._returning == 'next':
568
# We have to know the current nodes children to be able to list the
569
# exclude keys for them. However, while we could have a second
570
# look-ahead result buffer and shuffle things around, this method
571
# is typically only called once per search - when memoising the
572
# results of the search.
573
found, ghosts, next, parents = self._do_query(self._next_query)
574
# pretend we didn't query: perhaps we should tweak _do_query to be
575
# entirely stateless?
576
self.seen.difference_update(next)
577
next_query = next.union(ghosts)
579
next_query = self._next_query
580
excludes = self._stopped_keys.union(next_query)
581
included_keys = self.seen.difference(excludes)
582
return SearchResult(self._started_keys, excludes, len(included_keys),
383
return ('_BreadthFirstSearcher(self._search_revisions=%r,'
384
' self.seen=%r)' % (self._search_revisions, self.seen))
586
387
"""Return the next ancestors of this revision.
588
389
Ancestors are returned in the order they are seen in a breadth-first
589
traversal. No ancestor will be returned more than once. Ancestors are
590
returned before their parentage is queried, so ghosts and missing
591
revisions (including the start revisions) are included in the result.
592
This can save a round trip in LCA style calculation by allowing
593
convergence to be detected without reading the data for the revision
594
the convergence occurs on.
596
:return: A set of revision_ids.
390
traversal. No ancestor will be returned more than once.
598
if self._returning != 'next':
599
# switch to returning the query, not the results.
600
self._returning = 'next'
601
self._iterations += 1
392
if self._search_revisions is None:
393
self._search_revisions = self._start
604
if len(self._next_query) == 0:
605
raise StopIteration()
606
# We have seen what we're querying at this point as we are returning
607
# the query, not the results.
608
self.seen.update(self._next_query)
609
return self._next_query
611
def next_with_ghosts(self):
612
"""Return the next found ancestors, with ghosts split out.
614
Ancestors are returned in the order they are seen in a breadth-first
615
traversal. No ancestor will be returned more than once. Ancestors are
616
returned only after asking for their parents, which allows us to detect
617
which revisions are ghosts and which are not.
619
:return: A tuple with (present ancestors, ghost ancestors) sets.
621
if self._returning != 'next_with_ghosts':
622
# switch to returning the results, not the current query.
623
self._returning = 'next_with_ghosts'
625
if len(self._next_query) == 0:
626
raise StopIteration()
628
return self._current_present, self._current_ghosts
631
"""Advance the search.
633
Updates self.seen, self._next_query, self._current_present,
634
self._current_ghosts, self._current_parents and self._iterations.
636
self._iterations += 1
637
found, ghosts, next, parents = self._do_query(self._next_query)
638
self._current_present = found
639
self._current_ghosts = ghosts
640
self._next_query = next
641
self._current_parents = parents
642
# ghosts are implicit stop points, otherwise the search cannot be
643
# repeated when ghosts are filled.
644
self._stopped_keys.update(ghosts)
646
def _do_query(self, revisions):
647
"""Query for revisions.
649
Adds revisions to the seen set.
651
:param revisions: Revisions to query.
652
:return: A tuple: (set(found_revisions), set(ghost_revisions),
653
set(parents_of_found_revisions), dict(found_revisions:parents)).
655
found_parents = set()
656
parents_of_found = set()
657
# revisions may contain nodes that point to other nodes in revisions:
658
# we want to filter them out.
659
self.seen.update(revisions)
660
parent_map = self._parents_provider.get_parent_map(revisions)
661
for rev_id, parents in parent_map.iteritems():
662
found_parents.add(rev_id)
663
parents_of_found.update(p for p in parents if p not in self.seen)
664
ghost_parents = revisions - found_parents
665
return found_parents, ghost_parents, parents_of_found, parent_map
395
new_search_revisions = set()
396
for parents in self._parents_provider.get_parents(
397
self._search_revisions):
400
new_search_revisions.update(p for p in parents if
402
self._search_revisions = new_search_revisions
403
if len(self._search_revisions) == 0:
404
raise StopIteration()
405
self.seen.update(self._search_revisions)
406
return self._search_revisions
667
408
def __iter__(self):
686
427
None of the specified revisions are required to be present in the
687
428
search list. In this case, the call is a no-op.
689
revisions = frozenset(revisions)
690
if self._returning == 'next':
691
stopped = self._next_query.intersection(revisions)
692
self._next_query = self._next_query.difference(revisions)
694
stopped_present = self._current_present.intersection(revisions)
695
stopped = stopped_present.union(
696
self._current_ghosts.intersection(revisions))
697
self._current_present.difference_update(stopped)
698
self._current_ghosts.difference_update(stopped)
699
# stopping 'x' should stop returning parents of 'x', but
700
# not if 'y' always references those same parents
701
stop_rev_references = {}
702
for rev in stopped_present:
703
for parent_id in self._current_parents[rev]:
704
if parent_id not in stop_rev_references:
705
stop_rev_references[parent_id] = 0
706
stop_rev_references[parent_id] += 1
707
# if only the stopped revisions reference it, the ref count will be
709
for parents in self._current_parents.itervalues():
710
for parent_id in parents:
712
stop_rev_references[parent_id] -= 1
716
for rev_id, refs in stop_rev_references.iteritems():
718
stop_parents.add(rev_id)
719
self._next_query.difference_update(stop_parents)
720
self._stopped_keys.update(stopped)
430
stopped = self._search_revisions.intersection(revisions)
431
self._search_revisions = self._search_revisions.difference(revisions)
723
434
def start_searching(self, revisions):
724
"""Add revisions to the search.
726
The parents of revisions will be returned from the next call to next()
727
or next_with_ghosts(). If next_with_ghosts was the most recently used
728
next* call then the return value is the result of looking up the
729
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
731
revisions = frozenset(revisions)
732
self._started_keys.update(revisions)
733
new_revisions = revisions.difference(self.seen)
734
revs, ghosts, query, parents = self._do_query(revisions)
735
self._stopped_keys.update(ghosts)
736
if self._returning == 'next':
737
self._next_query.update(new_revisions)
435
if self._search_revisions is None:
436
self._start = set(revisions)
739
# perform a query on revisions
740
self._current_present.update(revs)
741
self._current_ghosts.update(ghosts)
742
self._next_query.update(query)
743
self._current_parents.update(parents)
747
class SearchResult(object):
748
"""The result of a breadth first search.
750
A SearchResult provides the ability to reconstruct the search or access a
751
set of the keys the search found.
754
def __init__(self, start_keys, exclude_keys, key_count, keys):
755
"""Create a SearchResult.
757
:param start_keys: The keys the search started at.
758
:param exclude_keys: The keys the search excludes.
759
:param key_count: The total number of keys (from start to but not
761
:param keys: The keys the search found. Note that in future we may get
762
a SearchResult from a smart server, in which case the keys list is
763
not necessarily immediately available.
765
self._recipe = (start_keys, exclude_keys, key_count)
766
self._keys = frozenset(keys)
768
def get_recipe(self):
769
"""Return a recipe that can be used to replay this search.
771
The recipe allows reconstruction of the same results at a later date
772
without knowing all the found keys. The essential elements are a list
773
of keys to start and and to stop at. In order to give reproducible
774
results when ghosts are encountered by a search they are automatically
775
added to the exclude list (or else ghost filling may alter the
778
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
779
recreate the results of this search, create a breadth first
780
searcher on the same graph starting at start_keys. Then call next()
781
(or next_with_ghosts()) repeatedly, and on every result, call
782
stop_searching_any on any keys from the exclude_keys set. The
783
revision_count value acts as a trivial cross-check - the found
784
revisions of the new search should have as many elements as
785
revision_count. If it does not, then additional revisions have been
786
ghosted since the search was executed the first time and the second
792
"""Return the keys found in this search.
794
:return: A set of keys.
438
self._search_revisions.update(revisions.difference(self.seen))
439
self.seen.update(revisions)
added
removed
bzrlib/graph.py
