/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Robert Collins
  • Date: 2007-08-07 22:59:45 UTC
  • mfrom: (2681 +trunk)
  • mto: This revision was merged to the branch mainline in revision 2682.
  • Revision ID: robertc@robertcollins.net-20070807225945-dlxppeb3we4lh897
Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
234
234
        for searcher in active_searchers.itervalues():
235
235
            searcher.next()
236
236
        while len(active_searchers) > 0:
237
 
            for candidate, searcher in list(active_searchers.iteritems()):
 
237
            for candidate in active_searchers.keys():
 
238
                try:
 
239
                    searcher = active_searchers[candidate]
 
240
                except KeyError:
 
241
                    # rare case: we deleted candidate in a previous iteration
 
242
                    # through this for loop, because it was determined to be
 
243
                    # a descendant of another candidate.
 
244
                    continue
238
245
                try:
239
246
                    ancestors = searcher.next()
240
247
                except StopIteration:
290
297
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
291
298
        return sorter.iter_topo_order()
292
299
 
 
300
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
 
301
        """Determine whether a revision is an ancestor of another.
 
302
 
 
303
        There are two possible outcomes: True and False, but there are three
 
304
        possible relationships:
 
305
 
 
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
 
309
 
 
310
        To check for a, we walk from candidate_descendant, looking for
 
311
        candidate_ancestor.
 
312
 
 
313
        To check for b, we walk from candidate_ancestor, looking for
 
314
        candidate_descendant.
 
315
 
 
316
        To make a and b more efficient, we can stop any searches that hit
 
317
        common ancestors.
 
318
 
 
319
        If we exhaust our searches, but neither a or b is true, then c is true.
 
320
 
 
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
 
326
        be true.
 
327
        """
 
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):
 
336
            new_common = set()
 
337
            if active_descendant:
 
338
                try:
 
339
                    nodes = descendant_walker.next()
 
340
                except StopIteration:
 
341
                    active_descendant = False
 
342
                else:
 
343
                    if candidate_ancestor in nodes:
 
344
                        return True
 
345
                    new_common.update(nodes.intersection(ancestor_walker.seen))
 
346
            if active_ancestor:
 
347
                try:
 
348
                    nodes = ancestor_walker.next()
 
349
                except StopIteration:
 
350
                    active_ancestor = False
 
351
                else:
 
352
                    if candidate_descendant in nodes:
 
353
                        return False
 
354
                    new_common.update(nodes.intersection(
 
355
                        descendant_walker.seen))
 
356
            try:
 
357
                new_common.update(common_walker.next())
 
358
            except StopIteration:
 
359
                pass
 
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)
 
365
        return False
 
366
 
293
367
 
294
368
class _BreadthFirstSearcher(object):
295
369
    """Parallel search the breadth-first the ancestry of revisions.