← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Add basic get_recipe to the graph breadth first searcher.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
509
509
        self._iterations = 0
510
510
        self._next_query = set(revisions)
511
511
        self.seen = set()
 
512
        self._started_keys = set(self._next_query)
 
513
        self._stopped_keys = set()
512
514
        self._parents_provider = parents_provider
513
515
        self._returning = 'next_with_ghosts'
514
516
 
521
523
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
522
524
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
523
525
 
 
526
    def get_recipe(self):
 
527
        """Return a recipe that can be used to replay this search.
 
528
        
 
529
        :return: A tuple (start_keys_set, exclude_keys_set). To recreate the
 
530
            results of this search, create a breadth first searcher on the same
 
531
            graph starting at start_keys. Then call next() (or
 
532
            next_with_ghosts()) repeatedly, and on every result, call
 
533
            stop_searching_any on any keys from the exclude_keys set.
 
534
        """
 
535
        if self._returning == 'next':
 
536
            # We have to know the current nodes children to be able to list the
 
537
            # exclude keys for them. However, while we could have a second
 
538
            # look-ahead result buffer and shuffle things around, this method
 
539
            # is typically only called once per search - when memoising the
 
540
            # results of the search.
 
541
            found, ghosts, next, parents = self._do_query(self._next_query)
 
542
            # pretend we didn't query: perhaps we should tweak _do_query to be
 
543
            # entirely stateless?
 
544
            self.seen.difference_update(next)
 
545
            next_query = next
 
546
        else:
 
547
            next_query = self._next_query
 
548
        return self._started_keys, self._stopped_keys.union(next_query)
 
549
 
524
550
    def next(self):
525
551
        """Return the next ancestors of this revision.
526
552
 
538
564
            # switch to returning the query, not the results.
539
565
            self._returning = 'next'
540
566
            self._iterations += 1
541
 
            self.seen.update(self._next_query)
542
567
        else:
543
568
            self._advance()
544
569
        if len(self._next_query) == 0:
545
570
            raise StopIteration()
 
571
        # We have seen what we're querying at this point as we are returning
 
572
        # the query, not the results.
 
573
        self.seen.update(self._next_query)
546
574
        return self._next_query
547
575
 
548
576
    def next_with_ghosts(self):
586
614
        """
587
615
        found_parents = set()
588
616
        parents_of_found = set()
 
617
        # revisions may contain nodes that point to other nodes in revisions:
 
618
        # we want to filter them out.
 
619
        self.seen.update(revisions)
589
620
        parent_map = self._parents_provider.get_parent_map(revisions)
590
621
        for rev_id, parents in parent_map.iteritems():
591
622
            found_parents.add(rev_id)
592
623
            parents_of_found.update(p for p in parents if p not in self.seen)
593
624
        ghost_parents = revisions - found_parents
594
 
        self.seen.update(parents_of_found)
595
625
        return found_parents, ghost_parents, parents_of_found, parent_map
596
626
 
597
627
    def __iter__(self):