239
239
# skip over the actual candidate for each searcher
240
240
for searcher in active_searchers.itervalues():
242
# The common walker finds nodes that are common to two or more of the
243
# input keys, so that we don't access all history when a currently
244
# uncommon search point actually meets up with something behind a
245
# common search point. Common search points do not keep searches
246
# active; they just allow us to make searches inactive without
247
# accessing all history.
248
common_walker = self._make_breadth_first_searcher([])
242
249
while len(active_searchers) > 0:
254
except StopIteration:
243
256
for candidate in active_searchers.keys():
245
258
searcher = active_searchers[candidate]
249
262
# a descendant of another candidate.
252
ancestors = searcher.next()
265
ancestors.update(searcher.next())
253
266
except StopIteration:
254
267
del active_searchers[candidate]
256
for ancestor in ancestors:
257
if ancestor in candidate_heads:
258
candidate_heads.remove(ancestor)
259
del searchers[ancestor]
260
if ancestor in active_searchers:
261
del active_searchers[ancestor]
269
# process found nodes
271
for ancestor in ancestors:
272
if ancestor in candidate_heads:
273
candidate_heads.remove(ancestor)
274
del searchers[ancestor]
275
if ancestor in active_searchers:
276
del active_searchers[ancestor]
277
# it may meet up with a known common node
278
already_common = ancestor in common_walker.seen
279
if not already_common:
280
# or it may have been just reached by all the searchers:
262
281
for searcher in searchers.itervalues():
263
282
if ancestor not in searcher.seen:
266
# if this revision was seen by all searchers, then it
267
# is a descendant of all candidates, so we can stop
268
# searching it, and any seen ancestors
269
for searcher in searchers.itervalues():
271
searcher.find_seen_ancestors(ancestor)
272
searcher.stop_searching_any(seen_ancestors)
288
# some searcher has encountered our known common nodes:
290
ancestor_set = set([ancestor])
291
for searcher in searchers.itervalues():
292
searcher.stop_searching_any(ancestor_set)
294
# The final active searcher has just reached this node,
295
# making it be known as a descendant of all candidates, so
296
# we can stop searching it, and any seen ancestors
297
new_common.add(ancestor)
298
for searcher in searchers.itervalues():
300
searcher.find_seen_ancestors(ancestor)
301
searcher.stop_searching_any(seen_ancestors)
302
common_walker.start_searching(new_common)
273
303
return candidate_heads
275
305
def find_unique_lca(self, left_revision, right_revision):
306
336
def is_ancestor(self, candidate_ancestor, candidate_descendant):
307
337
"""Determine whether a revision is an ancestor of another.
309
There are two possible outcomes: True and False, but there are three
310
possible relationships:
312
a) candidate_ancestor is an ancestor of candidate_descendant
313
b) candidate_ancestor is an descendant of candidate_descendant
314
c) candidate_ancestor is an sibling of candidate_descendant
316
To check for a, we walk from candidate_descendant, looking for
319
To check for b, we walk from candidate_ancestor, looking for
320
candidate_descendant.
322
To make a and b more efficient, we can stop any searches that hit
325
If we exhaust our searches, but neither a or b is true, then c is true.
327
In order to find c efficiently, we must avoid searching from
328
candidate_descendant or candidate_ancestor into common ancestors. But
329
if we don't search common ancestors at all, we won't know if we hit
330
common ancestors. So we have a walker for common ancestors. Note that
331
its searches are not required to terminate in order to determine c to
334
ancestor_walker = self._make_breadth_first_searcher(
335
[candidate_ancestor])
336
descendant_walker = self._make_breadth_first_searcher(
337
[candidate_descendant])
338
common_walker = self._make_breadth_first_searcher([])
339
active_ancestor = True
340
active_descendant = True
341
while (active_ancestor or active_descendant):
343
if active_descendant:
345
nodes = descendant_walker.next()
346
except StopIteration:
347
active_descendant = False
349
if candidate_ancestor in nodes:
351
new_common.update(nodes.intersection(ancestor_walker.seen))
354
nodes = ancestor_walker.next()
355
except StopIteration:
356
active_ancestor = False
358
if candidate_descendant in nodes:
360
new_common.update(nodes.intersection(
361
descendant_walker.seen))
363
new_common.update(common_walker.next())
364
except StopIteration:
366
for walker in (ancestor_walker, descendant_walker):
367
for node in new_common:
368
c_ancestors = walker.find_seen_ancestors(node)
369
walker.stop_searching_any(c_ancestors)
370
common_walker.start_searching(new_common)
339
We answer this using heads() as heads() has the logic to perform the
340
smallest number of parent looksup to determine the ancestral
341
relationship between N revisions.
343
return set([candidate_descendant]) == self.heads(
344
[candidate_ancestor, candidate_descendant])
347
class HeadsCache(object):
348
"""A cache of results for graph heads calls."""
350
def __init__(self, graph):
354
def heads(self, keys):
355
"""Return the heads of keys.
357
This matches the API of Graph.heads(), specifically the return value is
358
a set which can be mutated, and ordering of the input is not preserved
361
:see also: Graph.heads.
362
:param keys: The keys to calculate heads for.
363
:return: A set containing the heads, which may be mutated without
364
affecting future lookups.
366
keys = frozenset(keys)
368
return set(self._heads[keys])
370
heads = self.graph.heads(keys)
371
self._heads[keys] = heads
374
375
class HeadsCache(object):
added
removed
bzrlib/graph.py
