258
258
right = searchers[1].seen
259
259
return (left.difference(right), right.difference(left))
261
def find_descendants(self, old_key, new_key):
262
"""Find descendants of old_key that are ancestors of new_key."""
263
child_map = self.get_child_map(self._find_descendant_ancestors(
265
graph = Graph(DictParentsProvider(child_map))
266
searcher = graph._make_breadth_first_searcher([old_key])
270
def _find_descendant_ancestors(self, old_key, new_key):
271
"""Find ancestors of new_key that may be descendants of old_key."""
272
stop = self._make_breadth_first_searcher([old_key])
273
descendants = self._make_breadth_first_searcher([new_key])
274
for revisions in descendants:
275
old_stop = stop.seen.intersection(revisions)
276
descendants.stop_searching_any(old_stop)
277
seen_stop = descendants.find_seen_ancestors(stop.step())
278
descendants.stop_searching_any(seen_stop)
279
return descendants.seen.difference(stop.seen)
281
def get_child_map(self, keys):
282
"""Get a mapping from parents to children of the specified keys.
284
This is simply the inversion of get_parent_map. Only supplied keys
285
will be discovered as children.
286
:return: a dict of key:child_list for keys.
288
parent_map = self._parents_provider.get_parent_map(keys)
290
for child, parents in sorted(parent_map.items()):
291
for parent in parents:
292
parent_child.setdefault(parent, []).append(child)
261
295
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
296
"""Find the left-hand distance to the NULL_REVISION.
862
896
stop.add(parent_id)
899
def find_lefthand_merger(self, merged_key, tip_key):
900
"""Find the first lefthand ancestor of tip_key that merged merged_key.
902
We do this by first finding the descendants of merged_key, then
903
walking through the lefthand ancestry of tip_key until we find a key
904
that doesn't descend from merged_key. Its child is the key that
907
:return: The first lefthand ancestor of tip_key to merge merged_key.
908
merged_key if it is a lefthand ancestor of tip_key.
909
None if no ancestor of tip_key merged merged_key.
911
descendants = self.find_descendants(merged_key, tip_key)
912
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
913
last_candidate = None
914
for candidate in candidate_iterator:
915
if candidate not in descendants:
916
return last_candidate
917
last_candidate = candidate
865
919
def find_unique_lca(self, left_revision, right_revision,
866
920
count_steps=False):
867
921
"""Find a unique LCA.
919
973
yield (ghost, None)
920
974
pending = next_pending
976
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
977
if stop_keys is None:
980
def get_parents(key):
982
return self._parents_provider.get_parent_map([key])[key]
984
raise errors.RevisionNotPresent(next_key, self)
986
if next_key in stop_keys:
988
parents = get_parents(next_key)
990
if len(parents) == 0:
993
next_key = parents[0]
922
995
def iter_topo_order(self, revisions):
923
996
"""Iterate through the input revisions in topological order.
1685
1758
def __init__(self, graph):
1686
1759
self._graph = graph
1761
def topo_sort(self):
1762
return [r for (r,) in self._graph.topo_sort()]
1688
1764
def heads(self, ids):
1689
1765
"""See Graph.heads()"""
1690
1766
as_keys = [(i,) for i in ids]
1691
1767
head_keys = self._graph.heads(as_keys)
1692
1768
return set([h[0] for h in head_keys])
1770
def merge_sort(self, tip_revision):
1771
return self._graph.merge_sort((tip_revision,))
1695
1774
_counters = [0,0,0,0,0,0,0]
added
removed
bzrlib/graph.py
