/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: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
from __future__ import absolute_import
18
 
 
19
17
import time
20
18
 
21
 
from . import (
 
19
from bzrlib import (
22
20
    debug,
23
21
    errors,
24
22
    osutils,
25
23
    revision,
26
24
    trace,
27
25
    )
28
 
from .sixish import (
29
 
    viewitems,
30
 
    viewvalues,
31
 
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
32
27
 
33
28
STEP_UNIQUE_SEARCHER_EVERY = 5
34
29
 
64
59
    def __repr__(self):
65
60
        return 'DictParentsProvider(%r)' % self.ancestry
66
61
 
67
 
    # Note: DictParentsProvider does not implement get_cached_parent_map
68
 
    #       Arguably, the data is clearly cached in memory. However, this class
69
 
    #       is mostly used for testing, and it keeps the tests clean to not
70
 
    #       change it.
71
 
 
72
62
    def get_parent_map(self, keys):
73
63
        """See StackedParentsProvider.get_parent_map"""
74
64
        ancestry = self.ancestry
75
 
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
76
66
 
 
67
@deprecated_function(deprecated_in((1, 16, 0)))
 
68
def _StackedParentsProvider(*args, **kwargs):
 
69
    return StackedParentsProvider(*args, **kwargs)
77
70
 
78
71
class StackedParentsProvider(object):
79
72
    """A parents provider which stacks (or unions) multiple providers.
80
 
 
 
73
    
81
74
    The providers are queries in the order of the provided parent_providers.
82
75
    """
83
 
 
 
76
    
84
77
    def __init__(self, parent_providers):
85
78
        self._parent_providers = parent_providers
86
79
 
102
95
        """
103
96
        found = {}
104
97
        remaining = set(keys)
105
 
        # This adds getattr() overhead to each get_parent_map call. However,
106
 
        # this is StackedParentsProvider, which means we're dealing with I/O
107
 
        # (either local indexes, or remote RPCs), so CPU overhead should be
108
 
        # minimal.
109
 
        for parents_provider in self._parent_providers:
110
 
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
111
 
                                 None)
112
 
            if get_cached is None:
113
 
                continue
114
 
            new_found = get_cached(remaining)
115
 
            found.update(new_found)
116
 
            remaining.difference_update(new_found)
117
 
            if not remaining:
118
 
                break
119
 
        if not remaining:
120
 
            return found
121
 
        for parents_provider in self._parent_providers:
122
 
            try:
123
 
                new_found = parents_provider.get_parent_map(remaining)
124
 
            except errors.UnsupportedOperation:
125
 
                continue
 
98
        for parents_provider in self._parent_providers:
 
99
            new_found = parents_provider.get_parent_map(remaining)
126
100
            found.update(new_found)
127
101
            remaining.difference_update(new_found)
128
102
            if not remaining:
141
115
 
142
116
    The cache is enabled by default, but may be disabled and re-enabled.
143
117
    """
144
 
 
145
118
    def __init__(self, parent_provider=None, get_parent_map=None):
146
119
        """Constructor.
147
120
 
181
154
            return None
182
155
        return dict(self._cache)
183
156
 
184
 
    def get_cached_parent_map(self, keys):
185
 
        """Return items from the cache.
186
 
 
187
 
        This returns the same info as get_parent_map, but explicitly does not
188
 
        invoke the supplied ParentsProvider to search for uncached values.
189
 
        """
190
 
        cache = self._cache
191
 
        if cache is None:
192
 
            return {}
193
 
        return dict([(key, cache[key]) for key in keys if key in cache])
194
 
 
195
157
    def get_parent_map(self, keys):
196
158
        """See StackedParentsProvider.get_parent_map."""
197
159
        cache = self._cache
221
183
            self.missing_keys.add(key)
222
184
 
223
185
 
224
 
class CallableToParentsProviderAdapter(object):
225
 
    """A parents provider that adapts any callable to the parents provider API.
226
 
 
227
 
    i.e. it accepts calls to self.get_parent_map and relays them to the
228
 
    callable it was constructed with.
229
 
    """
230
 
 
231
 
    def __init__(self, a_callable):
232
 
        self.callable = a_callable
233
 
 
234
 
    def __repr__(self):
235
 
        return "%s(%r)" % (self.__class__.__name__, self.callable)
236
 
 
237
 
    def get_parent_map(self, keys):
238
 
        return self.callable(keys)
239
 
 
240
 
 
241
186
class Graph(object):
242
187
    """Provide incremental access to revision graphs.
243
188
 
292
237
        common ancestor of all border ancestors, because this shows that it
293
238
        cannot be a descendant of any border ancestor.
294
239
 
295
 
        The scaling of this operation should be proportional to:
296
 
 
 
240
        The scaling of this operation should be proportional to
297
241
        1. The number of uncommon ancestors
298
242
        2. The number of border ancestors
299
243
        3. The length of the shortest path between a border ancestor and an
314
258
        right = searchers[1].seen
315
259
        return (left.difference(right), right.difference(left))
316
260
 
317
 
    def find_descendants(self, old_key, new_key):
318
 
        """Find descendants of old_key that are ancestors of new_key."""
319
 
        child_map = self.get_child_map(self._find_descendant_ancestors(
320
 
            old_key, new_key))
321
 
        graph = Graph(DictParentsProvider(child_map))
322
 
        searcher = graph._make_breadth_first_searcher([old_key])
323
 
        list(searcher)
324
 
        return searcher.seen
325
 
 
326
 
    def _find_descendant_ancestors(self, old_key, new_key):
327
 
        """Find ancestors of new_key that may be descendants of old_key."""
328
 
        stop = self._make_breadth_first_searcher([old_key])
329
 
        descendants = self._make_breadth_first_searcher([new_key])
330
 
        for revisions in descendants:
331
 
            old_stop = stop.seen.intersection(revisions)
332
 
            descendants.stop_searching_any(old_stop)
333
 
            seen_stop = descendants.find_seen_ancestors(stop.step())
334
 
            descendants.stop_searching_any(seen_stop)
335
 
        return descendants.seen.difference(stop.seen)
336
 
 
337
 
    def get_child_map(self, keys):
338
 
        """Get a mapping from parents to children of the specified keys.
339
 
 
340
 
        This is simply the inversion of get_parent_map.  Only supplied keys
341
 
        will be discovered as children.
342
 
        :return: a dict of key:child_list for keys.
343
 
        """
344
 
        parent_map = self._parents_provider.get_parent_map(keys)
345
 
        parent_child = {}
346
 
        for child, parents in sorted(viewitems(parent_map)):
347
 
            for parent in parents:
348
 
                parent_child.setdefault(parent, []).append(child)
349
 
        return parent_child
350
 
 
351
261
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
352
262
        """Find the left-hand distance to the NULL_REVISION.
353
263
 
366
276
        NULL_REVISION = revision.NULL_REVISION
367
277
        known_revnos[NULL_REVISION] = 0
368
278
 
369
 
        searching_known_tips = list(known_revnos)
 
279
        searching_known_tips = list(known_revnos.keys())
370
280
 
371
281
        unknown_searched = {}
372
282
 
373
283
        while cur_tip not in known_revnos:
374
284
            unknown_searched[cur_tip] = num_steps
375
285
            num_steps += 1
376
 
            to_search = {cur_tip}
 
286
            to_search = set([cur_tip])
377
287
            to_search.update(searching_known_tips)
378
288
            parent_map = self.get_parent_map(to_search)
379
289
            parents = parent_map.get(cur_tip, None)
380
 
            if not parents:  # An empty list or None is a ghost
 
290
            if not parents: # An empty list or None is a ghost
381
291
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
382
292
                                                       cur_tip)
383
293
            cur_tip = parents[0]
409
319
        """
410
320
        # Optimisable by concurrent searching, but a random spread should get
411
321
        # some sort of hit rate.
 
322
        result = {}
412
323
        known_revnos = []
413
324
        ghosts = []
414
325
        for key in keys:
430
341
 
431
342
        :param unique_revision: The revision_id whose ancestry we are
432
343
            interested in.
433
 
            (XXX: Would this API be better if we allowed multiple revisions on
434
 
            to be searched here?)
 
344
            XXX: Would this API be better if we allowed multiple revisions on
 
345
                 to be searched here?
435
346
        :param common_revisions: Revision_ids of ancestries to exclude.
436
347
        :return: A set of revisions in the ancestry of unique_revision
437
348
        """
465
376
            return unique_nodes
466
377
 
467
378
        (all_unique_searcher,
468
 
         unique_tip_searchers) = self._make_unique_searchers(
469
 
             unique_nodes, unique_searcher, common_searcher)
 
379
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
380
                                    unique_searcher, common_searcher)
470
381
 
471
382
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
472
383
                                  unique_tip_searchers, common_searcher)
488
399
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
489
400
        # we know that unique_revisions aren't in common_revisions, so skip
490
401
        # past them.
491
 
        next(unique_searcher)
 
402
        unique_searcher.next()
492
403
        common_searcher = self._make_breadth_first_searcher(common_revisions)
493
404
 
494
405
        # As long as we are still finding unique nodes, keep searching
504
415
                next_common_nodes.intersection(unique_searcher.seen))
505
416
            if unique_are_common_nodes:
506
417
                ancestors = unique_searcher.find_seen_ancestors(
507
 
                    unique_are_common_nodes)
 
418
                                unique_are_common_nodes)
508
419
                # TODO: This is a bit overboard, we only really care about
509
420
                #       the ancestors of the tips because the rest we
510
421
                #       already know. This is *correct* but causes us to
511
422
                #       search too much ancestry.
512
 
                ancestors.update(
513
 
                    common_searcher.find_seen_ancestors(ancestors))
 
423
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
514
424
                unique_searcher.stop_searching_any(ancestors)
515
425
                common_searcher.start_searching(ancestors)
516
426
 
525
435
 
526
436
        :return: (all_unique_searcher, unique_tip_searchers)
527
437
        """
528
 
        unique_tips = self._remove_simple_descendants(
529
 
            unique_nodes, self.get_parent_map(unique_nodes))
 
438
        unique_tips = self._remove_simple_descendants(unique_nodes,
 
439
                        self.get_parent_map(unique_nodes))
530
440
 
531
441
        if len(unique_tips) == 1:
532
442
            unique_tip_searchers = []
533
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
534
 
                unique_tips)
 
443
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
535
444
        else:
536
445
            unique_tip_searchers = []
537
446
            for tip in unique_tips:
550
459
                    ancestor_all_unique = set(searcher.seen)
551
460
                else:
552
461
                    ancestor_all_unique = ancestor_all_unique.intersection(
553
 
                        searcher.seen)
 
462
                                                searcher.seen)
554
463
        # Collapse all the common nodes into a single searcher
555
464
        all_unique_searcher = self._make_breadth_first_searcher(
556
 
            ancestor_all_unique)
 
465
                                ancestor_all_unique)
557
466
        if ancestor_all_unique:
558
467
            # We've seen these nodes in all the searchers, so we'll just go to
559
468
            # the next
607
516
        for searcher in unique_tip_searchers:
608
517
            common_to_all_unique_nodes.intersection_update(searcher.seen)
609
518
        common_to_all_unique_nodes.intersection_update(
610
 
            all_unique_searcher.seen)
 
519
                                    all_unique_searcher.seen)
611
520
        # Step all-unique less frequently than the other searchers.
612
521
        # In the common case, we don't need to spider out far here, so
613
522
        # avoid doing extra work.
614
523
        if step_all_unique:
615
 
            tstart = osutils.perf_counter()
 
524
            tstart = time.clock()
616
525
            nodes = all_unique_searcher.step()
617
526
            common_to_all_unique_nodes.update(nodes)
618
527
            if 'graph' in debug.debug_flags:
619
 
                tdelta = osutils.perf_counter() - tstart
 
528
                tdelta = time.clock() - tstart
620
529
                trace.mutter('all_unique_searcher step() took %.3fs'
621
530
                             'for %d nodes (%d total), iteration: %s',
622
531
                             tdelta, len(nodes), len(all_unique_searcher.seen),
654
563
        # TODO: it might be possible to collapse searchers faster when they
655
564
        #       only have *some* search tips in common.
656
565
        next_unique_searchers = []
657
 
        for searchers in viewvalues(unique_search_tips):
 
566
        for searchers in unique_search_tips.itervalues():
658
567
            if len(searchers) == 1:
659
568
                # Searching unique tips, go for it
660
569
                next_unique_searchers.append(searchers[0])
694
603
            # These nodes are common ancestors of all unique nodes
695
604
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
696
605
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
697
 
                step_all_unique_counter == 0)
 
606
                step_all_unique_counter==0)
698
607
            step_all_unique_counter = ((step_all_unique_counter + 1)
699
608
                                       % STEP_UNIQUE_SEARCHER_EVERY)
700
609
 
762
671
        common_ancestors = set()
763
672
        searchers = [self._make_breadth_first_searcher([r])
764
673
                     for r in revisions]
 
674
        active_searchers = searchers[:]
765
675
        border_ancestors = set()
766
676
 
767
677
        while True:
836
746
            # NULL_REVISION is only a head if it is the only entry
837
747
            candidate_heads.remove(revision.NULL_REVISION)
838
748
            if not candidate_heads:
839
 
                return {revision.NULL_REVISION}
 
749
                return set([revision.NULL_REVISION])
840
750
        if len(candidate_heads) < 2:
841
751
            return candidate_heads
842
752
        searchers = dict((c, self._make_breadth_first_searcher([c]))
843
 
                         for c in candidate_heads)
 
753
                          for c in candidate_heads)
844
754
        active_searchers = dict(searchers)
845
755
        # skip over the actual candidate for each searcher
846
 
        for searcher in viewvalues(active_searchers):
847
 
            next(searcher)
 
756
        for searcher in active_searchers.itervalues():
 
757
            searcher.next()
848
758
        # The common walker finds nodes that are common to two or more of the
849
759
        # input keys, so that we don't access all history when a currently
850
760
        # uncommon search point actually meets up with something behind a
856
766
            ancestors = set()
857
767
            # advance searches
858
768
            try:
859
 
                next(common_walker)
 
769
                common_walker.next()
860
770
            except StopIteration:
861
771
                # No common points being searched at this time.
862
772
                pass
863
 
            for candidate in list(active_searchers):
 
773
            for candidate in active_searchers.keys():
864
774
                try:
865
775
                    searcher = active_searchers[candidate]
866
776
                except KeyError:
869
779
                    # a descendant of another candidate.
870
780
                    continue
871
781
                try:
872
 
                    ancestors.update(next(searcher))
 
782
                    ancestors.update(searcher.next())
873
783
                except StopIteration:
874
784
                    del active_searchers[candidate]
875
785
                    continue
885
795
                if ancestor in common_walker.seen:
886
796
                    # some searcher has encountered our known common nodes:
887
797
                    # just stop it
888
 
                    ancestor_set = {ancestor}
889
 
                    for searcher in viewvalues(searchers):
 
798
                    ancestor_set = set([ancestor])
 
799
                    for searcher in searchers.itervalues():
890
800
                        searcher.stop_searching_any(ancestor_set)
891
801
                else:
892
802
                    # or it may have been just reached by all the searchers:
893
 
                    for searcher in viewvalues(searchers):
 
803
                    for searcher in searchers.itervalues():
894
804
                        if ancestor not in searcher.seen:
895
805
                            break
896
806
                    else:
898
808
                        # making it be known as a descendant of all candidates,
899
809
                        # so we can stop searching it, and any seen ancestors
900
810
                        new_common.add(ancestor)
901
 
                        for searcher in viewvalues(searchers):
 
811
                        for searcher in searchers.itervalues():
902
812
                            seen_ancestors =\
903
813
                                searcher.find_seen_ancestors([ancestor])
904
814
                            searcher.stop_searching_any(seen_ancestors)
936
846
                    break
937
847
                continue
938
848
            parent_ids = self.get_parent_map([next]).get(next, None)
939
 
            if not parent_ids:  # Ghost, nothing to search here
 
849
            if not parent_ids: # Ghost, nothing to search here
940
850
                continue
941
851
            for parent_id in reversed(parent_ids):
942
852
                # TODO: (performance) We see the parent at this point, but we
952
862
                stop.add(parent_id)
953
863
        return found
954
864
 
955
 
    def find_lefthand_merger(self, merged_key, tip_key):
956
 
        """Find the first lefthand ancestor of tip_key that merged merged_key.
957
 
 
958
 
        We do this by first finding the descendants of merged_key, then
959
 
        walking through the lefthand ancestry of tip_key until we find a key
960
 
        that doesn't descend from merged_key.  Its child is the key that
961
 
        merged merged_key.
962
 
 
963
 
        :return: The first lefthand ancestor of tip_key to merge merged_key.
964
 
            merged_key if it is a lefthand ancestor of tip_key.
965
 
            None if no ancestor of tip_key merged merged_key.
966
 
        """
967
 
        descendants = self.find_descendants(merged_key, tip_key)
968
 
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
969
 
        last_candidate = None
970
 
        for candidate in candidate_iterator:
971
 
            if candidate not in descendants:
972
 
                return last_candidate
973
 
            last_candidate = candidate
974
 
 
975
865
    def find_unique_lca(self, left_revision, right_revision,
976
866
                        count_steps=False):
977
867
        """Find a unique LCA.
1021
911
            processed.update(pending)
1022
912
            next_map = self.get_parent_map(pending)
1023
913
            next_pending = set()
1024
 
            for item in viewitems(next_map):
 
914
            for item in next_map.iteritems():
1025
915
                yield item
1026
916
                next_pending.update(p for p in item[1] if p not in processed)
1027
917
            ghosts = pending.difference(next_map)
1029
919
                yield (ghost, None)
1030
920
            pending = next_pending
1031
921
 
1032
 
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1033
 
        if stop_keys is None:
1034
 
            stop_keys = ()
1035
 
        next_key = start_key
1036
 
 
1037
 
        def get_parents(key):
1038
 
            try:
1039
 
                return self._parents_provider.get_parent_map([key])[key]
1040
 
            except KeyError:
1041
 
                raise errors.RevisionNotPresent(next_key, self)
1042
 
        while True:
1043
 
            if next_key in stop_keys:
1044
 
                return
1045
 
            parents = get_parents(next_key)
1046
 
            yield next_key
1047
 
            if len(parents) == 0:
1048
 
                return
1049
 
            else:
1050
 
                next_key = parents[0]
1051
 
 
1052
922
    def iter_topo_order(self, revisions):
1053
923
        """Iterate through the input revisions in topological order.
1054
924
 
1056
926
        An ancestor may sort after a descendant if the relationship is not
1057
927
        visible in the supplied list of revisions.
1058
928
        """
1059
 
        from breezy import tsort
 
929
        from bzrlib import tsort
1060
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1061
931
        return sorter.iter_topo_order()
1062
932
 
1067
937
        smallest number of parent lookups to determine the ancestral
1068
938
        relationship between N revisions.
1069
939
        """
1070
 
        return {candidate_descendant} == self.heads(
 
940
        return set([candidate_descendant]) == self.heads(
1071
941
            [candidate_ancestor, candidate_descendant])
1072
942
 
1073
943
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1077
947
        lower_bound_revid <= revid <= upper_bound_revid
1078
948
        """
1079
949
        return ((upper_bound_revid is None or
1080
 
                 self.is_ancestor(revid, upper_bound_revid)) and
1081
 
                (lower_bound_revid is None or
1082
 
                 self.is_ancestor(lower_bound_revid, revid)))
 
950
                    self.is_ancestor(revid, upper_bound_revid)) and
 
951
               (lower_bound_revid is None or
 
952
                    self.is_ancestor(lower_bound_revid, revid)))
1083
953
 
1084
954
    def _search_for_extra_common(self, common, searchers):
1085
955
        """Make sure that unique nodes are genuinely unique.
1118
988
        left_searcher = searchers[0]
1119
989
        right_searcher = searchers[1]
1120
990
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1121
 
        if not unique:  # No unique nodes, nothing to do
 
991
        if not unique: # No unique nodes, nothing to do
1122
992
            return
1123
993
        total_unique = len(unique)
1124
994
        unique = self._remove_simple_descendants(unique,
1125
 
                                                 self.get_parent_map(unique))
 
995
                    self.get_parent_map(unique))
1126
996
        simple_unique = len(unique)
1127
997
 
1128
998
        unique_searchers = []
1132
1002
            else:
1133
1003
                parent_searcher = right_searcher
1134
1004
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1135
 
            if not revs_to_search:  # XXX: This shouldn't be possible
 
1005
            if not revs_to_search: # XXX: This shouldn't be possible
1136
1006
                revs_to_search = [revision_id]
1137
1007
            searcher = self._make_breadth_first_searcher(revs_to_search)
1138
1008
            # We don't care about the starting nodes.
1149
1019
                ancestor_all_unique = set(searcher.seen)
1150
1020
            else:
1151
1021
                ancestor_all_unique = ancestor_all_unique.intersection(
1152
 
                    searcher.seen)
 
1022
                                            searcher.seen)
1153
1023
 
1154
 
        trace.mutter('Started %d unique searchers for %d unique revisions',
 
1024
        trace.mutter('Started %s unique searchers for %s unique revisions',
1155
1025
                     simple_unique, total_unique)
1156
1026
 
1157
 
        while True:  # If we have no more nodes we have nothing to do
 
1027
        while True: # If we have no more nodes we have nothing to do
1158
1028
            newly_seen_common = set()
1159
1029
            for searcher in common_searchers:
1160
1030
                newly_seen_common.update(searcher.step())
1187
1057
                # If a 'common' node is an ancestor of all unique searchers, we
1188
1058
                # can stop searching it.
1189
1059
                stop_searching_common = ancestor_all_unique.intersection(
1190
 
                    newly_seen_common)
 
1060
                                            newly_seen_common)
1191
1061
                if stop_searching_common:
1192
1062
                    for searcher in common_searchers:
1193
1063
                        searcher.stop_searching_any(stop_searching_common)
1218
1088
                for searcher in unique_searchers:
1219
1089
                    will_search_set = frozenset(searcher._next_query)
1220
1090
                    if will_search_set not in unique_search_sets:
1221
 
                        # This searcher is searching a unique set of nodes, let
1222
 
                        # it
 
1091
                        # This searcher is searching a unique set of nodes, let it
1223
1092
                        unique_search_sets.add(will_search_set)
1224
1093
                        next_unique_searchers.append(searcher)
1225
1094
                unique_searchers = next_unique_searchers
1247
1116
 
1248
1117
        # This is the same as the following loop. I don't know that it is any
1249
1118
        # faster.
1250
 
        # simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1251
 
        # if p_ids is not None and revisions.intersection(p_ids))
1252
 
        # return simple_ancestors
 
1119
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
 
1120
        ##     if p_ids is not None and revisions.intersection(p_ids))
 
1121
        ## return simple_ancestors
1253
1122
 
1254
1123
        # Yet Another Way, invert the parent map (which can be cached)
1255
1124
        ## descendants = {}
1256
 
        # for revision_id, parent_ids in parent_map.iteritems():
1257
 
        # for p_id in parent_ids:
 
1125
        ## for revision_id, parent_ids in parent_map.iteritems():
 
1126
        ##   for p_id in parent_ids:
1258
1127
        ##       descendants.setdefault(p_id, []).append(revision_id)
1259
 
        # for revision in revisions.intersection(descendants):
1260
 
        # simple_ancestors.difference_update(descendants[revision])
1261
 
        # return simple_ancestors
1262
 
        for revision, parent_ids in viewitems(parent_map):
 
1128
        ## for revision in revisions.intersection(descendants):
 
1129
        ##   simple_ancestors.difference_update(descendants[revision])
 
1130
        ## return simple_ancestors
 
1131
        for revision, parent_ids in parent_map.iteritems():
1263
1132
            if parent_ids is None:
1264
1133
                continue
1265
1134
            for parent_id in parent_ids:
1358
1227
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1359
1228
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1360
1229
 
1361
 
    def get_state(self):
1362
 
        """Get the current state of this searcher.
 
1230
    def get_result(self):
 
1231
        """Get a SearchResult for the current state of this searcher.
1363
1232
 
1364
 
        :return: Tuple with started keys, excludes and included keys
 
1233
        :return: A SearchResult for this search so far. The SearchResult is
 
1234
            static - the search can be advanced and the search result will not
 
1235
            be invalidated or altered.
1365
1236
        """
1366
1237
        if self._returning == 'next':
1367
1238
            # We have to know the current nodes children to be able to list the
1378
1249
            next_query = self._next_query
1379
1250
        excludes = self._stopped_keys.union(next_query)
1380
1251
        included_keys = self.seen.difference(excludes)
1381
 
        return self._started_keys, excludes, included_keys
 
1252
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
1253
            included_keys)
1382
1254
 
1383
1255
    def step(self):
1384
1256
        try:
1385
 
            return next(self)
 
1257
            return self.next()
1386
1258
        except StopIteration:
1387
1259
            return ()
1388
1260
 
1389
 
    def __next__(self):
 
1261
    def next(self):
1390
1262
        """Return the next ancestors of this revision.
1391
1263
 
1392
1264
        Ancestors are returned in the order they are seen in a breadth-first
1412
1284
        self.seen.update(self._next_query)
1413
1285
        return self._next_query
1414
1286
 
1415
 
    next = __next__
1416
 
 
1417
1287
    def next_with_ghosts(self):
1418
1288
        """Return the next found ancestors, with ghosts split out.
1419
1289
 
1462
1332
        parents_of_found = set()
1463
1333
        # revisions may contain nodes that point to other nodes in revisions:
1464
1334
        # we want to filter them out.
1465
 
        seen = self.seen
1466
 
        seen.update(revisions)
 
1335
        self.seen.update(revisions)
1467
1336
        parent_map = self._parents_provider.get_parent_map(revisions)
1468
1337
        found_revisions.update(parent_map)
1469
 
        for rev_id, parents in viewitems(parent_map):
 
1338
        for rev_id, parents in parent_map.iteritems():
1470
1339
            if parents is None:
1471
1340
                continue
1472
 
            new_found_parents = [p for p in parents if p not in seen]
 
1341
            new_found_parents = [p for p in parents if p not in self.seen]
1473
1342
            if new_found_parents:
1474
1343
                # Calling set.update() with an empty generator is actually
1475
1344
                # rather expensive.
1509
1378
            all_parents = []
1510
1379
            # We don't care if it is a ghost, since it can't be seen if it is
1511
1380
            # a ghost
1512
 
            for parent_ids in viewvalues(parent_map):
 
1381
            for parent_ids in parent_map.itervalues():
1513
1382
                all_parents.extend(parent_ids)
1514
 
            next_pending = all_seen.intersection(
1515
 
                all_parents).difference(seen_ancestors)
 
1383
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1516
1384
            seen_ancestors.update(next_pending)
1517
1385
            next_pending.difference_update(not_searched_yet)
1518
1386
            pending = next_pending
1555
1423
                    stop_rev_references[parent_id] += 1
1556
1424
            # if only the stopped revisions reference it, the ref count will be
1557
1425
            # 0 after this loop
1558
 
            for parents in viewvalues(self._current_parents):
 
1426
            for parents in self._current_parents.itervalues():
1559
1427
                for parent_id in parents:
1560
1428
                    try:
1561
1429
                        stop_rev_references[parent_id] -= 1
1562
1430
                    except KeyError:
1563
1431
                        pass
1564
1432
            stop_parents = set()
1565
 
            for rev_id, refs in viewitems(stop_rev_references):
 
1433
            for rev_id, refs in stop_rev_references.iteritems():
1566
1434
                if refs == 0:
1567
1435
                    stop_parents.add(rev_id)
1568
1436
            self._next_query.difference_update(stop_parents)
1595
1463
            return revs, ghosts
1596
1464
 
1597
1465
 
1598
 
def invert_parent_map(parent_map):
1599
 
    """Given a map from child => parents, create a map of parent=>children"""
1600
 
    child_map = {}
1601
 
    for child, parents in viewitems(parent_map):
1602
 
        for p in parents:
1603
 
            # Any given parent is likely to have only a small handful
1604
 
            # of children, many will have only one. So we avoid mem overhead of
1605
 
            # a list, in exchange for extra copying of tuples
1606
 
            if p not in child_map:
1607
 
                child_map[p] = (child,)
1608
 
            else:
1609
 
                child_map[p] = child_map[p] + (child,)
1610
 
    return child_map
 
1466
class SearchResult(object):
 
1467
    """The result of a breadth first search.
 
1468
 
 
1469
    A SearchResult provides the ability to reconstruct the search or access a
 
1470
    set of the keys the search found.
 
1471
    """
 
1472
 
 
1473
    def __init__(self, start_keys, exclude_keys, key_count, keys):
 
1474
        """Create a SearchResult.
 
1475
 
 
1476
        :param start_keys: The keys the search started at.
 
1477
        :param exclude_keys: The keys the search excludes.
 
1478
        :param key_count: The total number of keys (from start to but not
 
1479
            including exclude).
 
1480
        :param keys: The keys the search found. Note that in future we may get
 
1481
            a SearchResult from a smart server, in which case the keys list is
 
1482
            not necessarily immediately available.
 
1483
        """
 
1484
        self._recipe = ('search', start_keys, exclude_keys, key_count)
 
1485
        self._keys = frozenset(keys)
 
1486
 
 
1487
    def get_recipe(self):
 
1488
        """Return a recipe that can be used to replay this search.
 
1489
 
 
1490
        The recipe allows reconstruction of the same results at a later date
 
1491
        without knowing all the found keys. The essential elements are a list
 
1492
        of keys to start and to stop at. In order to give reproducible
 
1493
        results when ghosts are encountered by a search they are automatically
 
1494
        added to the exclude list (or else ghost filling may alter the
 
1495
        results).
 
1496
 
 
1497
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1498
            revision_count). To recreate the results of this search, create a
 
1499
            breadth first searcher on the same graph starting at start_keys.
 
1500
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1501
            result, call stop_searching_any on any keys from the exclude_keys
 
1502
            set. The revision_count value acts as a trivial cross-check - the
 
1503
            found revisions of the new search should have as many elements as
 
1504
            revision_count. If it does not, then additional revisions have been
 
1505
            ghosted since the search was executed the first time and the second
 
1506
            time.
 
1507
        """
 
1508
        return self._recipe
 
1509
 
 
1510
    def get_keys(self):
 
1511
        """Return the keys found in this search.
 
1512
 
 
1513
        :return: A set of keys.
 
1514
        """
 
1515
        return self._keys
 
1516
 
 
1517
    def is_empty(self):
 
1518
        """Return false if the search lists 1 or more revisions."""
 
1519
        return self._recipe[3] == 0
 
1520
 
 
1521
    def refine(self, seen, referenced):
 
1522
        """Create a new search by refining this search.
 
1523
 
 
1524
        :param seen: Revisions that have been satisfied.
 
1525
        :param referenced: Revision references observed while satisfying some
 
1526
            of this search.
 
1527
        """
 
1528
        start = self._recipe[1]
 
1529
        exclude = self._recipe[2]
 
1530
        count = self._recipe[3]
 
1531
        keys = self.get_keys()
 
1532
        # New heads = referenced + old heads - seen things - exclude
 
1533
        pending_refs = set(referenced)
 
1534
        pending_refs.update(start)
 
1535
        pending_refs.difference_update(seen)
 
1536
        pending_refs.difference_update(exclude)
 
1537
        # New exclude = old exclude + satisfied heads
 
1538
        seen_heads = start.intersection(seen)
 
1539
        exclude.update(seen_heads)
 
1540
        # keys gets seen removed
 
1541
        keys = keys - seen
 
1542
        # length is reduced by len(seen)
 
1543
        count -= len(seen)
 
1544
        return SearchResult(pending_refs, exclude, count, keys)
 
1545
 
 
1546
 
 
1547
class PendingAncestryResult(object):
 
1548
    """A search result that will reconstruct the ancestry for some graph heads.
 
1549
 
 
1550
    Unlike SearchResult, this doesn't hold the complete search result in
 
1551
    memory, it just holds a description of how to generate it.
 
1552
    """
 
1553
 
 
1554
    def __init__(self, heads, repo):
 
1555
        """Constructor.
 
1556
 
 
1557
        :param heads: an iterable of graph heads.
 
1558
        :param repo: a repository to use to generate the ancestry for the given
 
1559
            heads.
 
1560
        """
 
1561
        self.heads = frozenset(heads)
 
1562
        self.repo = repo
 
1563
 
 
1564
    def get_recipe(self):
 
1565
        """Return a recipe that can be used to replay this search.
 
1566
 
 
1567
        The recipe allows reconstruction of the same results at a later date.
 
1568
 
 
1569
        :seealso SearchResult.get_recipe:
 
1570
 
 
1571
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1572
            To recreate this result, create a PendingAncestryResult with the
 
1573
            start_keys_set.
 
1574
        """
 
1575
        return ('proxy-search', self.heads, set(), -1)
 
1576
 
 
1577
    def get_keys(self):
 
1578
        """See SearchResult.get_keys.
 
1579
 
 
1580
        Returns all the keys for the ancestry of the heads, excluding
 
1581
        NULL_REVISION.
 
1582
        """
 
1583
        return self._get_keys(self.repo.get_graph())
 
1584
 
 
1585
    def _get_keys(self, graph):
 
1586
        NULL_REVISION = revision.NULL_REVISION
 
1587
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1588
                if key != NULL_REVISION and parents is not None]
 
1589
        return keys
 
1590
 
 
1591
    def is_empty(self):
 
1592
        """Return false if the search lists 1 or more revisions."""
 
1593
        if revision.NULL_REVISION in self.heads:
 
1594
            return len(self.heads) == 1
 
1595
        else:
 
1596
            return len(self.heads) == 0
 
1597
 
 
1598
    def refine(self, seen, referenced):
 
1599
        """Create a new search by refining this search.
 
1600
 
 
1601
        :param seen: Revisions that have been satisfied.
 
1602
        :param referenced: Revision references observed while satisfying some
 
1603
            of this search.
 
1604
        """
 
1605
        referenced = self.heads.union(referenced)
 
1606
        return PendingAncestryResult(referenced - seen, self.repo)
1611
1607
 
1612
1608
 
1613
1609
def collapse_linear_regions(parent_map):
1650
1646
    # Will not have any nodes removed, even though you do have an
1651
1647
    # 'uninteresting' linear D->B and E->C
1652
1648
    children = {}
1653
 
    for child, parents in viewitems(parent_map):
 
1649
    for child, parents in parent_map.iteritems():
1654
1650
        children.setdefault(child, [])
1655
1651
        for p in parents:
1656
1652
            children.setdefault(p, []).append(child)
1657
1653
 
 
1654
    orig_children = dict(children)
1658
1655
    removed = set()
1659
1656
    result = dict(parent_map)
1660
1657
    for node in parent_map:
1695
1692
        """See Graph.heads()"""
1696
1693
        as_keys = [(i,) for i in ids]
1697
1694
        head_keys = self._graph.heads(as_keys)
1698
 
        return {h[0] for h in head_keys}
 
1695
        return set([h[0] for h in head_keys])
1699
1696
 
1700
1697
    def merge_sort(self, tip_revision):
1701
 
        nodes = self._graph.merge_sort((tip_revision,))
1702
 
        for node in nodes:
1703
 
            node.key = node.key[0]
1704
 
        return nodes
1705
 
 
1706
 
    def add_node(self, revision, parents):
1707
 
        self._graph.add_node((revision,), [(p,) for p in parents])
1708
 
 
1709
 
 
1710
 
_counters = [0, 0, 0, 0, 0, 0, 0]
 
1698
        return self._graph.merge_sort((tip_revision,))
 
1699
 
 
1700
 
 
1701
_counters = [0,0,0,0,0,0,0]
1711
1702
try:
1712
 
    from ._known_graph_pyx import KnownGraph
1713
 
except ImportError as e:
 
1703
    from bzrlib._known_graph_pyx import KnownGraph
 
1704
except ImportError, e:
1714
1705
    osutils.failed_to_load_extension(e)
1715
 
    from ._known_graph_py import KnownGraph  # noqa: F401
 
1706
    from bzrlib._known_graph_py import KnownGraph