/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: John Arbash Meinel
  • Date: 2008-04-22 22:58:28 UTC
  • mto: This revision was merged to the branch mainline in revision 3407.
  • Revision ID: john@arbash-meinel.com-20080422225828-l6qigns5f4t81dbi
Tweak _BreadthFirstSearcher.find_seen_ancestors()

The old function stepped too far. It would query for the very tip nodes,
which had not actually been probed for yet. This was further exacerbated,
because it was using a _BreadthFirstSearcher to do the sub-iteration,
which probably had the same problem.

Overall, seems to be considerably faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
18
18
    errors,
19
19
    revision,
20
20
    symbol_versioning,
 
21
    trace,
21
22
    tsort,
22
23
    )
23
24
from bzrlib.deprecated_graph import (node_distances, select_farthest)
481
482
    def _search_for_extra_common(self, common, searchers):
482
483
        """Make sure that unique nodes are genuinely unique.
483
484
 
484
 
        After a simple search, we end up with genuine common nodes, but some
485
 
        uncommon nodes might actually be descended from common nodes, and we
486
 
        just didn't search far enough.
 
485
        After _find_border_ancestors, all nodes marked "common" are indeed
 
486
        common. Some of the nodes considered unique are not, due to history
 
487
        shortcuts stopping the searches early.
487
488
 
488
489
        We know that we have searched enough when all common search tips are
489
490
        descended from all unique (uncommon) nodes because we know that a node
500
501
        #      "unique" nodes for each side.
501
502
        #   C) We do a quick culling so that we only start searching from the
502
503
        #      more interesting unique nodes. (A unique ancestor is more
503
 
        #      interesting that any of its children.)
 
504
        #      interesting than any of its children.)
504
505
        #   D) We start searching for ancestors common to all unique nodes.
505
506
        #   E) We have the common searchers stop searching any ancestors of
506
507
        #      nodes found by (D)
507
508
        #   F) When there are no more common search tips, we stop
 
509
 
 
510
        # TODO: We need a way to remove unique_searchers when they overlap with
 
511
        #       other unique searchers.
508
512
        assert len(searchers) == 2, (
509
513
            "Algorithm not yet implemented for > 2 searchers")
510
514
        common_searchers = searchers
511
515
        left_searcher = searchers[0]
512
516
        right_searcher = searchers[1]
513
517
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
 
518
        total_unique = len(unique)
514
519
        unique = self._remove_simple_descendants(unique,
515
520
                    self.get_parent_map(unique))
 
521
        simple_unique = len(unique)
 
522
        trace.mutter('Starting %s unique searchers for %s unique revisions',
 
523
                     simple_unique, total_unique)
516
524
        # TODO: jam 20071214 Would it be possible to seed these searchers with
517
525
        #       the revisions that we have already seen on each side?
518
526
        #       Maybe something like:
568
576
            if new_common_unique:
569
577
                # We found some ancestors that are common, jump all the way to
570
578
                # their most ancestral node that we have already seen.
571
 
                try:
572
 
                    for searcher in unique_searchers:
573
 
                        new_common_unique.update(searcher.find_seen_ancestors(new_common_unique))
574
 
                except TypeError:
575
 
                    import pdb; pdb.set_trace()
576
 
                    raise
 
579
                for searcher in unique_searchers:
 
580
                    new_common_unique.update(searcher.find_seen_ancestors(new_common_unique))
577
581
                # Since these are common, we can grab another set of ancestors
578
582
                # that we have seen
579
583
                for searcher in common_searchers:
854
858
 
855
859
    def find_seen_ancestors(self, revisions):
856
860
        """Find ancestors of these revisions that have already been seen."""
857
 
        searcher = _BreadthFirstSearcher(revisions, self._parents_provider)
858
 
        seen_ancestors = set()
859
 
        for ancestors in searcher:
860
 
            stop_nodes = set()
861
 
            for ancestor in ancestors:
862
 
                if ancestor not in self.seen:
863
 
                    stop_nodes.add(ancestor)
864
 
                else:
865
 
                    seen_ancestors.add(ancestor)
866
 
            searcher.stop_searching_any(stop_nodes)
 
861
        all_seen = self.seen
 
862
        pending = set(revisions).intersection(all_seen)
 
863
        seen_ancestors = set(pending)
 
864
 
 
865
        if self._returning == 'next':
 
866
            # self.seen contains what nodes have been returned, not what nodes
 
867
            # have been queried. We don't want to probe for nodes that haven't
 
868
            # been searched yet.
 
869
            not_searched_yet = self._next_query
 
870
        else:
 
871
            not_searched_yet = ()
 
872
        get_parent_map = self._parents_provider.get_parent_map
 
873
        while pending:
 
874
            parent_map = get_parent_map(pending)
 
875
            all_parents = []
 
876
            # We don't care if it is a ghost, since it can't be seen if it is
 
877
            # a ghost
 
878
            for parent_ids in parent_map.itervalues():
 
879
                all_parents.extend(parent_ids)
 
880
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
881
            seen_ancestors.update(next_pending)
 
882
            next_pending.difference_update(not_searched_yet)
 
883
            pending = next_pending
 
884
 
867
885
        return seen_ancestors
868
886
 
869
887
    def stop_searching_any(self, revisions):