« back to all changes in this revision
Viewing changes to bzrlib/graph.py
- browse files at revision 2929
- compare with another revision
- download diff
- download tarball
- view history from revision 2929
- Committer: Canonical.com Patch Queue Manager
- Date: 2007-10-23 08:21:11 UTC
- mfrom: (2921.3.5 graph)
- Revision ID: pqm@pqm.ubuntu.com-20071023082111-h6u34i4gvlb2nwch
(robertc) Prevent heads() calls from accessing all history unnecessarily. (Robert Collins)
- files modified:
- NEWS
added
removed
bzrlib/graph.py
91
91
specialized implementations for particular repository types. See
92
92
Repository.get_graph()
93
93
94
:param parents_func: an object providing a get_parents call
94
:param parents_provider: An object providing a get_parents call
95
95
conforming to the behavior of StackedParentsProvider.get_parents
96
96
"""
97
97
self.get_parents = parents_provider.get_parents
239
239
# skip over the actual candidate for each searcher
240
240
for searcher in active_searchers.itervalues():
241
241
searcher.next()
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:
250
ancestors = set()
251
# advance searches
252
try:
253
common_walker.next()
254
except StopIteration:
255
# No common points being searched at this time.
256
pass
243
257
for candidate in active_searchers.keys():
244
258
try:
245
259
searcher = active_searchers[candidate]
249
263
# a descendant of another candidate.
250
264
continue
251
265
try:
252
ancestors = searcher.next()
266
ancestors.update(searcher.next())
253
267
except StopIteration:
254
268
del active_searchers[candidate]
255
269
continue
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]
270
# process found nodes
271
new_common = set()
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:
281
# just stop it
282
ancestor_set = set([ancestor])
283
for searcher in searchers.itervalues():
284
searcher.stop_searching_any(ancestor_set)
285
else:
286
# or it may have been just reached by all the searchers:
262
287
for searcher in searchers.itervalues():
263
288
if ancestor not in searcher.seen:
264
289
break
265
290
else:
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
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)
269
295
for searcher in searchers.itervalues():
270
296
seen_ancestors =\
271
297
searcher.find_seen_ancestors(ancestor)
272
298
searcher.stop_searching_any(seen_ancestors)
299
common_walker.start_searching(new_common)
273
300
return candidate_heads
274
301
275
302
def find_unique_lca(self, left_revision, right_revision):
306
333
def is_ancestor(self, candidate_ancestor, candidate_descendant):
307
334
"""Determine whether a revision is an ancestor of another.
308
335
309
There are two possible outcomes: True and False, but there are three
310
possible relationships:
311
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
315
316
To check for a, we walk from candidate_descendant, looking for
317
candidate_ancestor.
318
319
To check for b, we walk from candidate_ancestor, looking for
320
candidate_descendant.
321
322
To make a and b more efficient, we can stop any searches that hit
323
common ancestors.
324
325
If we exhaust our searches, but neither a or b is true, then c is true.
326
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
332
be true.
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.
333
339
"""
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):
342
new_common = set()
343
if active_descendant:
344
try:
345
nodes = descendant_walker.next()
346
except StopIteration:
347
active_descendant = False
348
else:
349
if candidate_ancestor in nodes:
350
return True
351
new_common.update(nodes.intersection(ancestor_walker.seen))
352
if active_ancestor:
353
try:
354
nodes = ancestor_walker.next()
355
except StopIteration:
356
active_ancestor = False
357
else:
358
if candidate_descendant in nodes:
359
return False
360
new_common.update(nodes.intersection(
361
descendant_walker.seen))
362
try:
363
new_common.update(common_walker.next())
364
except StopIteration:
365
pass
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)
371
return False
340
return set([candidate_descendant]) == self.heads(
341
[candidate_ancestor, candidate_descendant])
372
342
373
343
374
344
class HeadsCache(object):
400
370
401
371
402
372
class _BreadthFirstSearcher(object):
403
"""Parallel search the breadth-first the ancestry of revisions.
373
"""Parallel search breadth-first the ancestry of revisions.
404
374
405
375
This class implements the iterator protocol, but additionally
406
376
1. provides a set of seen ancestors, and
Loggerhead is a web-based interface for Breezy
Version: 2.0.1