/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: Andrew Bennetts
  • Date: 2008-01-21 00:46:32 UTC
  • mfrom: (3193 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3194.
  • Revision ID: andrew.bennetts@canonical.com-20080121004632-wvpox6g9j7czn4vk
Merge from bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
46
46
 
47
47
 
48
48
class DictParentsProvider(object):
 
49
    """A parents provider for Graph objects."""
49
50
 
50
51
    def __init__(self, ancestry):
51
52
        self.ancestry = ancestry
53
54
    def __repr__(self):
54
55
        return 'DictParentsProvider(%r)' % self.ancestry
55
56
 
56
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
57
 
    def get_parents(self, revisions):
58
 
        return [self.ancestry.get(r, None) for r in revisions]
59
 
 
60
57
    def get_parent_map(self, keys):
61
58
        """See _StackedParentsProvider.get_parent_map"""
62
59
        ancestry = self.ancestry
71
68
    def __repr__(self):
72
69
        return "_StackedParentsProvider(%r)" % self._parent_providers
73
70
 
74
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
75
 
    def get_parents(self, revision_ids):
76
 
        """Find revision ids of the parents of a list of revisions
77
 
 
78
 
        A list is returned of the same length as the input.  Each entry
79
 
        is a list of parent ids for the corresponding input revision.
80
 
 
81
 
        [NULL_REVISION] is used as the parent of the first user-committed
82
 
        revision.  Its parent list is empty.
83
 
 
84
 
        If the revision is not present (i.e. a ghost), None is used in place
85
 
        of the list of parents.
86
 
        """
87
 
        found = self.get_parent_map(revision_ids)
88
 
        return [found.get(r, None) for r in revision_ids]
89
 
 
90
71
    def get_parent_map(self, keys):
91
72
        """Get a mapping of keys => parents
92
73
 
125
106
    def __repr__(self):
126
107
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
127
108
 
128
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
129
 
    def get_parents(self, revision_ids):
130
 
        """See _StackedParentsProvider.get_parents"""
131
 
        found = self.get_parent_map(revision_ids)
132
 
        return [found.get(r, None) for r in revision_ids]
133
 
 
134
109
    def get_parent_map(self, keys):
135
110
        """See _StackedParentsProvider.get_parent_map"""
136
111
        needed = set()
168
143
 
169
144
        This should not normally be invoked directly, because there may be
170
145
        specialized implementations for particular repository types.  See
171
 
        Repository.get_graph()
 
146
        Repository.get_graph().
172
147
 
173
 
        :param parents_provider: An object providing a get_parents call
174
 
            conforming to the behavior of StackedParentsProvider.get_parents
 
148
        :param parents_provider: An object providing a get_parent_map call
 
149
            conforming to the behavior of
 
150
            StackedParentsProvider.get_parent_map.
175
151
        """
176
 
        self.get_parents = parents_provider.get_parents
177
 
        self.get_parent_map = parents_provider.get_parent_map
 
152
        if getattr(parents_provider, 'get_parents', None) is not None:
 
153
            self.get_parents = parents_provider.get_parents
 
154
        if getattr(parents_provider, 'get_parent_map', None) is not None:
 
155
            self.get_parent_map = parents_provider.get_parent_map
178
156
        self._parents_provider = parents_provider
179
157
 
180
158
    def __repr__(self):
226
204
        return (left.difference(right).difference(common),
227
205
                right.difference(left).difference(common))
228
206
 
 
207
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
 
208
    def get_parents(self, revisions):
 
209
        """Find revision ids of the parents of a list of revisions
 
210
 
 
211
        A list is returned of the same length as the input.  Each entry
 
212
        is a list of parent ids for the corresponding input revision.
 
213
 
 
214
        [NULL_REVISION] is used as the parent of the first user-committed
 
215
        revision.  Its parent list is empty.
 
216
 
 
217
        If the revision is not present (i.e. a ghost), None is used in place
 
218
        of the list of parents.
 
219
 
 
220
        Deprecated in bzr 1.2 - please see get_parent_map.
 
221
        """
 
222
        parents = self.get_parent_map(revisions)
 
223
        return [parent.get(r, None) for r in revisions]
 
224
 
 
225
    def get_parent_map(self, revisions):
 
226
        """Get a map of key:parent_list for revisions.
 
227
 
 
228
        This implementation delegates to get_parents, for old parent_providers
 
229
        that do not supply get_parent_map.
 
230
        """
 
231
        result = {}
 
232
        for rev, parents in self.get_parents(revisions):
 
233
            if parents is not None:
 
234
                result[rev] = parents
 
235
        return result
 
236
 
229
237
    def _make_breadth_first_searcher(self, revisions):
230
238
        return _BreadthFirstSearcher(revisions, self)
231
239
 
498
506
    """
499
507
 
500
508
    def __init__(self, revisions, parents_provider):
501
 
        self._start = set(revisions)
502
 
        self._search_revisions = None
503
 
        self.seen = set(revisions)
 
509
        self._iterations = 0
 
510
        self._next_query = set(revisions)
 
511
        self.seen = set()
 
512
        self._started_keys = set(self._next_query)
 
513
        self._stopped_keys = set()
504
514
        self._parents_provider = parents_provider
 
515
        self._returning = 'next_with_ghosts'
 
516
        self._current_present = set()
 
517
        self._current_ghosts = set()
 
518
        self._current_parents = {}
505
519
 
506
520
    def __repr__(self):
507
 
        if self._search_revisions is not None:
508
 
            search = 'searching=%r' % (list(self._search_revisions),)
509
 
        else:
510
 
            search = 'starting=%r' % (list(self._start),)
511
 
        return ('_BreadthFirstSearcher(%s,'
512
 
                ' seen=%r)' % (search, list(self.seen)))
 
521
        if self._iterations:
 
522
            prefix = "searching"
 
523
        else:
 
524
            prefix = "starting"
 
525
        search = '%s=%r' % (prefix, list(self._next_query))
 
526
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
 
527
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
 
528
 
 
529
    def get_result(self):
 
530
        """Get a SearchResult for the current state of this searcher.
 
531
        
 
532
        :return: A SearchResult for this search so far. The SearchResult is
 
533
            static - the search can be advanced and the search result will not
 
534
            be invalidated or altered.
 
535
        """
 
536
        if self._returning == 'next':
 
537
            # We have to know the current nodes children to be able to list the
 
538
            # exclude keys for them. However, while we could have a second
 
539
            # look-ahead result buffer and shuffle things around, this method
 
540
            # is typically only called once per search - when memoising the
 
541
            # results of the search.
 
542
            found, ghosts, next, parents = self._do_query(self._next_query)
 
543
            # pretend we didn't query: perhaps we should tweak _do_query to be
 
544
            # entirely stateless?
 
545
            self.seen.difference_update(next)
 
546
            next_query = next.union(ghosts)
 
547
        else:
 
548
            next_query = self._next_query
 
549
        excludes = self._stopped_keys.union(next_query)
 
550
        included_keys = self.seen.difference(excludes)
 
551
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
552
            included_keys)
513
553
 
514
554
    def next(self):
515
555
        """Return the next ancestors of this revision.
516
556
 
517
557
        Ancestors are returned in the order they are seen in a breadth-first
518
 
        traversal.  No ancestor will be returned more than once.
 
558
        traversal.  No ancestor will be returned more than once. Ancestors are
 
559
        returned before their parentage is queried, so ghosts and missing
 
560
        revisions (including the start revisions) are included in the result.
 
561
        This can save a round trip in LCA style calculation by allowing
 
562
        convergence to be detected without reading the data for the revision
 
563
        the convergence occurs on.
 
564
 
 
565
        :return: A set of revision_ids.
519
566
        """
520
 
        if self._search_revisions is None:
521
 
            self._search_revisions = self._start
 
567
        if self._returning != 'next':
 
568
            # switch to returning the query, not the results.
 
569
            self._returning = 'next'
 
570
            self._iterations += 1
522
571
        else:
523
 
            new_search_revisions = set()
524
 
            parent_map = self._parents_provider.get_parent_map(
525
 
                            self._search_revisions)
526
 
            for parents in parent_map.itervalues():
527
 
                new_search_revisions.update(p for p in parents if
528
 
                                            p not in self.seen)
529
 
            self._search_revisions = new_search_revisions
530
 
        if len(self._search_revisions) == 0:
531
 
            raise StopIteration()
532
 
        self.seen.update(self._search_revisions)
533
 
        return self._search_revisions
 
572
            self._advance()
 
573
        if len(self._next_query) == 0:
 
574
            raise StopIteration()
 
575
        # We have seen what we're querying at this point as we are returning
 
576
        # the query, not the results.
 
577
        self.seen.update(self._next_query)
 
578
        return self._next_query
 
579
 
 
580
    def next_with_ghosts(self):
 
581
        """Return the next found ancestors, with ghosts split out.
 
582
        
 
583
        Ancestors are returned in the order they are seen in a breadth-first
 
584
        traversal.  No ancestor will be returned more than once. Ancestors are
 
585
        returned only after asking for their parents, which allows us to detect
 
586
        which revisions are ghosts and which are not.
 
587
 
 
588
        :return: A tuple with (present ancestors, ghost ancestors) sets.
 
589
        """
 
590
        if self._returning != 'next_with_ghosts':
 
591
            # switch to returning the results, not the current query.
 
592
            self._returning = 'next_with_ghosts'
 
593
            self._advance()
 
594
        if len(self._next_query) == 0:
 
595
            raise StopIteration()
 
596
        self._advance()
 
597
        return self._current_present, self._current_ghosts
 
598
 
 
599
    def _advance(self):
 
600
        """Advance the search.
 
601
 
 
602
        Updates self.seen, self._next_query, self._current_present,
 
603
        self._current_ghosts, self._current_parents and self._iterations.
 
604
        """
 
605
        self._iterations += 1
 
606
        found, ghosts, next, parents = self._do_query(self._next_query)
 
607
        self._current_present = found
 
608
        self._current_ghosts = ghosts
 
609
        self._next_query = next
 
610
        self._current_parents = parents
 
611
        # ghosts are implicit stop points, otherwise the search cannot be
 
612
        # repeated when ghosts are filled.
 
613
        self._stopped_keys.update(ghosts)
 
614
 
 
615
    def _do_query(self, revisions):
 
616
        """Query for revisions.
 
617
 
 
618
        Adds revisions to the seen set.
 
619
 
 
620
        :param revisions: Revisions to query.
 
621
        :return: A tuple: (set(found_revisions), set(ghost_revisions),
 
622
           set(parents_of_found_revisions), dict(found_revisions:parents)).
 
623
        """
 
624
        found_parents = set()
 
625
        parents_of_found = set()
 
626
        # revisions may contain nodes that point to other nodes in revisions:
 
627
        # we want to filter them out.
 
628
        self.seen.update(revisions)
 
629
        parent_map = self._parents_provider.get_parent_map(revisions)
 
630
        for rev_id, parents in parent_map.iteritems():
 
631
            found_parents.add(rev_id)
 
632
            parents_of_found.update(p for p in parents if p not in self.seen)
 
633
        ghost_parents = revisions - found_parents
 
634
        return found_parents, ghost_parents, parents_of_found, parent_map
534
635
 
535
636
    def __iter__(self):
536
637
        return self
554
655
        None of the specified revisions are required to be present in the
555
656
        search list.  In this case, the call is a no-op.
556
657
        """
557
 
        stopped = self._search_revisions.intersection(revisions)
558
 
        self._search_revisions = self._search_revisions.difference(revisions)
 
658
        revisions = frozenset(revisions)
 
659
        if self._returning == 'next':
 
660
            stopped = self._next_query.intersection(revisions)
 
661
            self._next_query = self._next_query.difference(revisions)
 
662
        else:
 
663
            stopped_present = self._current_present.intersection(revisions)
 
664
            stopped = stopped_present.union(
 
665
                self._current_ghosts.intersection(revisions))
 
666
            self._current_present.difference_update(stopped)
 
667
            self._current_ghosts.difference_update(stopped)
 
668
            # stopping 'x' should stop returning parents of 'x', but 
 
669
            # not if 'y' always references those same parents
 
670
            stop_rev_references = {}
 
671
            for rev in stopped_present:
 
672
                for parent_id in self._current_parents[rev]:
 
673
                    if parent_id not in stop_rev_references:
 
674
                        stop_rev_references[parent_id] = 0
 
675
                    stop_rev_references[parent_id] += 1
 
676
            # if only the stopped revisions reference it, the ref count will be
 
677
            # 0 after this loop
 
678
            for parents in self._current_parents.itervalues():
 
679
                for parent_id in parents:
 
680
                    try:
 
681
                        stop_rev_references[parent_id] -= 1
 
682
                    except KeyError:
 
683
                        pass
 
684
            stop_parents = set()
 
685
            for rev_id, refs in stop_rev_references.iteritems():
 
686
                if refs == 0:
 
687
                    stop_parents.add(rev_id)
 
688
            self._next_query.difference_update(stop_parents)
 
689
        self._stopped_keys.update(stopped)
559
690
        return stopped
560
691
 
561
692
    def start_searching(self, revisions):
562
 
        if self._search_revisions is None:
563
 
            self._start = set(revisions)
 
693
        """Add revisions to the search.
 
694
 
 
695
        The parents of revisions will be returned from the next call to next()
 
696
        or next_with_ghosts(). If next_with_ghosts was the most recently used
 
697
        next* call then the return value is the result of looking up the
 
698
        ghost/not ghost status of revisions. (A tuple (present, ghosted)).
 
699
        """
 
700
        revisions = frozenset(revisions)
 
701
        self._started_keys.update(revisions)
 
702
        new_revisions = revisions.difference(self.seen)
 
703
        revs, ghosts, query, parents = self._do_query(revisions)
 
704
        self._stopped_keys.update(ghosts)
 
705
        if self._returning == 'next':
 
706
            self._next_query.update(new_revisions)
564
707
        else:
565
 
            self._search_revisions.update(revisions.difference(self.seen))
566
 
        self.seen.update(revisions)
 
708
            # perform a query on revisions
 
709
            self._current_present.update(revs)
 
710
            self._current_ghosts.update(ghosts)
 
711
            self._next_query.update(query)
 
712
            self._current_parents.update(parents)
 
713
            return revs, ghosts
 
714
 
 
715
 
 
716
class SearchResult(object):
 
717
    """The result of a breadth first search.
 
718
 
 
719
    A SearchResult provides the ability to reconstruct the search or access a
 
720
    set of the keys the search found.
 
721
    """
 
722
 
 
723
    def __init__(self, start_keys, exclude_keys, key_count, keys):
 
724
        """Create a SearchResult.
 
725
 
 
726
        :param start_keys: The keys the search started at.
 
727
        :param exclude_keys: The keys the search excludes.
 
728
        :param key_count: The total number of keys (from start to but not
 
729
            including exclude).
 
730
        :param keys: The keys the search found. Note that in future we may get
 
731
            a SearchResult from a smart server, in which case the keys list is
 
732
            not necessarily immediately available.
 
733
        """
 
734
        self._recipe = (start_keys, exclude_keys, key_count)
 
735
        self._keys = frozenset(keys)
 
736
 
 
737
    def get_recipe(self):
 
738
        """Return a recipe that can be used to replay this search.
 
739
        
 
740
        The recipe allows reconstruction of the same results at a later date
 
741
        without knowing all the found keys. The essential elements are a list
 
742
        of keys to start and and to stop at. In order to give reproducible
 
743
        results when ghosts are encountered by a search they are automatically
 
744
        added to the exclude list (or else ghost filling may alter the
 
745
        results).
 
746
 
 
747
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
 
748
            recreate the results of this search, create a breadth first
 
749
            searcher on the same graph starting at start_keys. Then call next()
 
750
            (or next_with_ghosts()) repeatedly, and on every result, call
 
751
            stop_searching_any on any keys from the exclude_keys set. The
 
752
            revision_count value acts as a trivial cross-check - the found
 
753
            revisions of the new search should have as many elements as
 
754
            revision_count. If it does not, then additional revisions have been
 
755
            ghosted since the search was executed the first time and the second
 
756
            time.
 
757
        """
 
758
        return self._recipe
 
759
 
 
760
    def get_keys(self):
 
761
        """Return the keys found in this search.
 
762
 
 
763
        :return: A set of keys.
 
764
        """
 
765
        return self._keys
 
766