← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2007-08-06 22:26:54 UTC
  • mfrom: (2665 +trunk)
  • mto: This revision was merged to the branch mainline in revision 2733.
  • Revision ID: aaron.bentley@utoronto.ca-20070806222654-a96j4mysnih1ha8x
Merge bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
290
290
        sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
291
291
        return sorter.iter_topo_order()
292
292
 
 
293
    def is_ancestor(self, candidate_ancestor, candidate_descendant):
 
294
        """Determine whether a revision is an ancestor of another.
 
295
 
 
296
        There are two possible outcomes: True and False, but there are three
 
297
        possible relationships:
 
298
 
 
299
        a) candidate_ancestor is an ancestor of candidate_descendant
 
300
        b) candidate_ancestor is an descendant of candidate_descendant
 
301
        c) candidate_ancestor is an sibling of candidate_descendant
 
302
 
 
303
        To check for a, we walk from candidate_descendant, looking for
 
304
        candidate_ancestor.
 
305
 
 
306
        To check for b, we walk from candidate_ancestor, looking for
 
307
        candidate_descendant.
 
308
 
 
309
        To make a and b more efficient, we can stop any searches that hit
 
310
        common ancestors.
 
311
 
 
312
        If we exhaust our searches, but neither a or b is true, then c is true.
 
313
 
 
314
        In order to find c efficiently, we must avoid searching from
 
315
        candidate_descendant or candidate_ancestor into common ancestors.  But
 
316
        if we don't search common ancestors at all, we won't know if we hit
 
317
        common ancestors.  So we have a walker for common ancestors.  Note that
 
318
        its searches are not required to terminate in order to determine c to
 
319
        be true.
 
320
        """
 
321
        ancestor_walker = self._make_breadth_first_searcher(
 
322
            [candidate_ancestor])
 
323
        descendant_walker = self._make_breadth_first_searcher(
 
324
            [candidate_descendant])
 
325
        common_walker = self._make_breadth_first_searcher([])
 
326
        active_ancestor = True
 
327
        active_descendant = True
 
328
        while (active_ancestor or active_descendant):
 
329
            new_common = set()
 
330
            if active_descendant:
 
331
                try:
 
332
                    nodes = descendant_walker.next()
 
333
                except StopIteration:
 
334
                    active_descendant = False
 
335
                else:
 
336
                    if candidate_ancestor in nodes:
 
337
                        return True
 
338
                    new_common.update(nodes.intersection(ancestor_walker.seen))
 
339
            if active_ancestor:
 
340
                try:
 
341
                    nodes = ancestor_walker.next()
 
342
                except StopIteration:
 
343
                    active_ancestor = False
 
344
                else:
 
345
                    if candidate_descendant in nodes:
 
346
                        return False
 
347
                    new_common.update(nodes.intersection(
 
348
                        descendant_walker.seen))
 
349
            try:
 
350
                new_common.update(common_walker.next())
 
351
            except StopIteration:
 
352
                pass
 
353
            for walker in (ancestor_walker, descendant_walker):
 
354
                for node in new_common:
 
355
                    c_ancestors = walker.find_seen_ancestors(node)
 
356
                    walker.stop_searching_any(c_ancestors)
 
357
                common_walker.start_searching(new_common)
 
358
        return False
 
359
 
293
360
 
294
361
class _BreadthFirstSearcher(object):
295
362
    """Parallel search the breadth-first the ancestry of revisions.