← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-04-23 22:13:09 UTC
  • mto: This revision was merged to the branch mainline in revision 3407.
  • Revision ID: john@arbash-meinel.com-20080423221309-etwdaic43iytt8n1
Keep track of the intersection of unique ancestry,
rather than checking it again all the time.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
515
515
        left_searcher = searchers[0]
516
516
        right_searcher = searchers[1]
517
517
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
 
518
        if not unique: # No unique nodes, nothing to do
 
519
            return
518
520
        total_unique = len(unique)
519
521
        unique = self._remove_simple_descendants(unique,
520
522
                    self.get_parent_map(unique))
541
543
        #   properties of the original searchers
542
544
        common_ancestors_unique = set()
543
545
 
 
546
        ancestor_all_unique = None
 
547
        for searcher in unique_searchers:
 
548
            if ancestor_all_unique is None:
 
549
                ancestor_all_unique = set(searcher.seen)
 
550
            else:
 
551
                ancestor_all_unique = ancestor_all_unique.intersection(
 
552
                                            searcher.seen)
 
553
 
544
554
        while True: # If we have no more nodes we have nothing to do
545
555
            newly_seen_common = set()
546
556
            for searcher in common_searchers:
575
585
                for searcher in common_searchers:
576
586
                    searcher.start_searching(newly_seen_common)
577
587
 
578
 
                # If a 'common' node has been found by a unique searcher, we
 
588
                # If a 'common' node is an ancestor of all unique searchers, we
579
589
                # can stop searching it.
580
 
                stop_searching_common = None
581
 
                for searcher in unique_searchers:
582
 
                    if stop_searching_common is None:
583
 
                        stop_searching_common = searcher.find_seen_ancestors(newly_seen_common)
584
 
                    else:
585
 
                        stop_searching_common = stop_searching_common.intersection(
586
 
                            searcher.find_seen_ancestors(newly_seen_common))
 
590
                stop_searching_common = ancestor_all_unique.intersection(
 
591
                                            newly_seen_common)
587
592
                if stop_searching_common:
588
593
                    for searcher in common_searchers:
589
594
                        searcher.stop_searching_any(stop_searching_common)
609
614
                for searcher in common_searchers:
610
615
                    searcher.stop_searching_any(new_common_unique)
611
616
                common_ancestors_unique.update(new_common_unique)
 
617
                ancestor_all_unique.update(new_common_unique)
612
618
            for searcher in common_searchers:
613
619
                if searcher._next_query:
614
620
                    break