231
231
order if they need it.
233
233
candidate_heads = set(keys)
234
if len(candidate_heads) < 2:
235
return candidate_heads
234
236
searchers = dict((c, self._make_breadth_first_searcher([c]))
235
237
for c in candidate_heads)
236
238
active_searchers = dict(searchers)
237
239
# skip over the actual candidate for each searcher
238
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([])
240
249
while len(active_searchers) > 0:
254
except StopIteration:
255
# No common points being searched at this time.
241
257
for candidate in active_searchers.keys():
243
259
searcher = active_searchers[candidate]
247
263
# a descendant of another candidate.
250
ancestors = searcher.next()
266
ancestors.update(searcher.next())
251
267
except StopIteration:
252
268
del active_searchers[candidate]
254
for ancestor in ancestors:
255
if ancestor in candidate_heads:
256
candidate_heads.remove(ancestor)
257
del searchers[ancestor]
258
if ancestor in active_searchers:
259
del active_searchers[ancestor]
270
# process found nodes
272
for ancestor in ancestors:
273
if ancestor in candidate_heads:
274
candidate_heads.remove(ancestor)
275
del searchers[ancestor]
276
if ancestor in active_searchers:
277
del active_searchers[ancestor]
278
# it may meet up with a known common node
279
if ancestor in common_walker.seen:
280
# some searcher has encountered our known common nodes:
282
ancestor_set = set([ancestor])
283
for searcher in searchers.itervalues():
284
searcher.stop_searching_any(ancestor_set)
286
# or it may have been just reached by all the searchers:
260
287
for searcher in searchers.itervalues():
261
288
if ancestor not in searcher.seen:
264
# if this revision was seen by all searchers, then it
265
# is a descendant of all candidates, so we can stop
266
# searching it, and any seen ancestors
291
# The final active searcher has just reached this node,
292
# making it be known as a descendant of all candidates,
293
# so we can stop searching it, and any seen ancestors
294
new_common.add(ancestor)
267
295
for searcher in searchers.itervalues():
268
296
seen_ancestors =\
269
297
searcher.find_seen_ancestors(ancestor)
270
298
searcher.stop_searching_any(seen_ancestors)
299
common_walker.start_searching(new_common)
271
300
return candidate_heads
273
302
def find_unique_lca(self, left_revision, right_revision):
304
333
def is_ancestor(self, candidate_ancestor, candidate_descendant):
305
334
"""Determine whether a revision is an ancestor of another.
307
There are two possible outcomes: True and False, but there are three
308
possible relationships:
310
a) candidate_ancestor is an ancestor of candidate_descendant
311
b) candidate_ancestor is an descendant of candidate_descendant
312
c) candidate_ancestor is an sibling of candidate_descendant
314
To check for a, we walk from candidate_descendant, looking for
317
To check for b, we walk from candidate_ancestor, looking for
318
candidate_descendant.
320
To make a and b more efficient, we can stop any searches that hit
323
If we exhaust our searches, but neither a or b is true, then c is true.
325
In order to find c efficiently, we must avoid searching from
326
candidate_descendant or candidate_ancestor into common ancestors. But
327
if we don't search common ancestors at all, we won't know if we hit
328
common ancestors. So we have a walker for common ancestors. Note that
329
its searches are not required to terminate in order to determine c to
332
ancestor_walker = self._make_breadth_first_searcher(
333
[candidate_ancestor])
334
descendant_walker = self._make_breadth_first_searcher(
335
[candidate_descendant])
336
common_walker = self._make_breadth_first_searcher([])
337
active_ancestor = True
338
active_descendant = True
339
while (active_ancestor or active_descendant):
341
if active_descendant:
343
nodes = descendant_walker.next()
344
except StopIteration:
345
active_descendant = False
347
if candidate_ancestor in nodes:
349
new_common.update(nodes.intersection(ancestor_walker.seen))
352
nodes = ancestor_walker.next()
353
except StopIteration:
354
active_ancestor = False
356
if candidate_descendant in nodes:
358
new_common.update(nodes.intersection(
359
descendant_walker.seen))
361
new_common.update(common_walker.next())
362
except StopIteration:
364
for walker in (ancestor_walker, descendant_walker):
365
for node in new_common:
366
c_ancestors = walker.find_seen_ancestors(node)
367
walker.stop_searching_any(c_ancestors)
368
common_walker.start_searching(new_common)
336
We answer this using heads() as heads() has the logic to perform the
337
smallest number of parent looksup to determine the ancestral
338
relationship between N revisions.
340
return set([candidate_descendant]) == self.heads(
341
[candidate_ancestor, candidate_descendant])
344
class HeadsCache(object):
345
"""A cache of results for graph heads calls."""
347
def __init__(self, graph):
351
def heads(self, keys):
352
"""Return the heads of keys.
354
This matches the API of Graph.heads(), specifically the return value is
355
a set which can be mutated, and ordering of the input is not preserved
358
:see also: Graph.heads.
359
:param keys: The keys to calculate heads for.
360
:return: A set containing the heads, which may be mutated without
361
affecting future lookups.
363
keys = frozenset(keys)
365
return set(self._heads[keys])
367
heads = self.graph.heads(keys)
368
self._heads[keys] = heads
372
class HeadsCache(object):
373
"""A cache of results for graph heads calls."""
375
def __init__(self, graph):
379
def heads(self, keys):
380
"""Return the heads of keys.
382
:see also: Graph.heads.
383
:param keys: The keys to calculate heads for.
384
:return: A set containing the heads, which may be mutated without
385
affecting future lookups.
387
keys = frozenset(keys)
389
return set(self._heads[keys])
391
heads = self.graph.heads(keys)
392
self._heads[keys] = heads
372
396
class _BreadthFirstSearcher(object):
373
"""Parallel search the breadth-first the ancestry of revisions.
397
"""Parallel search breadth-first the ancestry of revisions.
375
399
This class implements the iterator protocol, but additionally
376
400
1. provides a set of seen ancestors, and
added
removed
bzrlib/graph.py
