/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 breezy/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007-2011 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
 
17
19
import time
18
20
 
19
 
from bzrlib import (
 
21
from . import (
20
22
    debug,
21
23
    errors,
22
24
    osutils,
23
25
    revision,
24
26
    trace,
25
27
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
 
28
from .sixish import (
 
29
    viewitems,
 
30
    viewvalues,
 
31
    )
27
32
 
28
33
STEP_UNIQUE_SEARCHER_EVERY = 5
29
34
 
59
64
    def __repr__(self):
60
65
        return 'DictParentsProvider(%r)' % self.ancestry
61
66
 
 
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
 
62
72
    def get_parent_map(self, keys):
63
73
        """See StackedParentsProvider.get_parent_map"""
64
74
        ancestry = self.ancestry
65
 
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
 
75
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
66
76
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
77
 
71
78
class StackedParentsProvider(object):
72
79
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
 
80
 
74
81
    The providers are queries in the order of the provided parent_providers.
75
82
    """
76
 
    
 
83
 
77
84
    def __init__(self, parent_providers):
78
85
        self._parent_providers = parent_providers
79
86
 
95
102
        """
96
103
        found = {}
97
104
        remaining = set(keys)
98
 
        for parents_provider in self._parent_providers:
99
 
            new_found = parents_provider.get_parent_map(remaining)
 
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
100
126
            found.update(new_found)
101
127
            remaining.difference_update(new_found)
102
128
            if not remaining:
115
141
 
116
142
    The cache is enabled by default, but may be disabled and re-enabled.
117
143
    """
 
144
 
118
145
    def __init__(self, parent_provider=None, get_parent_map=None):
119
146
        """Constructor.
120
147
 
154
181
            return None
155
182
        return dict(self._cache)
156
183
 
 
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
 
157
195
    def get_parent_map(self, keys):
158
196
        """See StackedParentsProvider.get_parent_map."""
159
197
        cache = self._cache
183
221
            self.missing_keys.add(key)
184
222
 
185
223
 
 
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
 
186
241
class Graph(object):
187
242
    """Provide incremental access to revision graphs.
188
243
 
237
292
        common ancestor of all border ancestors, because this shows that it
238
293
        cannot be a descendant of any border ancestor.
239
294
 
240
 
        The scaling of this operation should be proportional to
 
295
        The scaling of this operation should be proportional to:
 
296
 
241
297
        1. The number of uncommon ancestors
242
298
        2. The number of border ancestors
243
299
        3. The length of the shortest path between a border ancestor and an
258
314
        right = searchers[1].seen
259
315
        return (left.difference(right), right.difference(left))
260
316
 
 
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
 
261
351
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
352
        """Find the left-hand distance to the NULL_REVISION.
263
353
 
276
366
        NULL_REVISION = revision.NULL_REVISION
277
367
        known_revnos[NULL_REVISION] = 0
278
368
 
279
 
        searching_known_tips = list(known_revnos.keys())
 
369
        searching_known_tips = list(known_revnos)
280
370
 
281
371
        unknown_searched = {}
282
372
 
283
373
        while cur_tip not in known_revnos:
284
374
            unknown_searched[cur_tip] = num_steps
285
375
            num_steps += 1
286
 
            to_search = set([cur_tip])
 
376
            to_search = {cur_tip}
287
377
            to_search.update(searching_known_tips)
288
378
            parent_map = self.get_parent_map(to_search)
289
379
            parents = parent_map.get(cur_tip, None)
290
 
            if not parents: # An empty list or None is a ghost
 
380
            if not parents:  # An empty list or None is a ghost
291
381
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
292
382
                                                       cur_tip)
293
383
            cur_tip = parents[0]
319
409
        """
320
410
        # Optimisable by concurrent searching, but a random spread should get
321
411
        # some sort of hit rate.
322
 
        result = {}
323
412
        known_revnos = []
324
413
        ghosts = []
325
414
        for key in keys:
341
430
 
342
431
        :param unique_revision: The revision_id whose ancestry we are
343
432
            interested in.
344
 
            XXX: Would this API be better if we allowed multiple revisions on
345
 
                 to be searched here?
 
433
            (XXX: Would this API be better if we allowed multiple revisions on
 
434
            to be searched here?)
346
435
        :param common_revisions: Revision_ids of ancestries to exclude.
347
436
        :return: A set of revisions in the ancestry of unique_revision
348
437
        """
376
465
            return unique_nodes
377
466
 
378
467
        (all_unique_searcher,
379
 
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
380
 
                                    unique_searcher, common_searcher)
 
468
         unique_tip_searchers) = self._make_unique_searchers(
 
469
             unique_nodes, unique_searcher, common_searcher)
381
470
 
382
471
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
383
472
                                  unique_tip_searchers, common_searcher)
399
488
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
400
489
        # we know that unique_revisions aren't in common_revisions, so skip
401
490
        # past them.
402
 
        unique_searcher.next()
 
491
        next(unique_searcher)
403
492
        common_searcher = self._make_breadth_first_searcher(common_revisions)
404
493
 
405
494
        # As long as we are still finding unique nodes, keep searching
415
504
                next_common_nodes.intersection(unique_searcher.seen))
416
505
            if unique_are_common_nodes:
417
506
                ancestors = unique_searcher.find_seen_ancestors(
418
 
                                unique_are_common_nodes)
 
507
                    unique_are_common_nodes)
419
508
                # TODO: This is a bit overboard, we only really care about
420
509
                #       the ancestors of the tips because the rest we
421
510
                #       already know. This is *correct* but causes us to
422
511
                #       search too much ancestry.
423
 
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
512
                ancestors.update(
 
513
                    common_searcher.find_seen_ancestors(ancestors))
424
514
                unique_searcher.stop_searching_any(ancestors)
425
515
                common_searcher.start_searching(ancestors)
426
516
 
435
525
 
436
526
        :return: (all_unique_searcher, unique_tip_searchers)
437
527
        """
438
 
        unique_tips = self._remove_simple_descendants(unique_nodes,
439
 
                        self.get_parent_map(unique_nodes))
 
528
        unique_tips = self._remove_simple_descendants(
 
529
            unique_nodes, self.get_parent_map(unique_nodes))
440
530
 
441
531
        if len(unique_tips) == 1:
442
532
            unique_tip_searchers = []
443
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
533
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
 
534
                unique_tips)
444
535
        else:
445
536
            unique_tip_searchers = []
446
537
            for tip in unique_tips:
459
550
                    ancestor_all_unique = set(searcher.seen)
460
551
                else:
461
552
                    ancestor_all_unique = ancestor_all_unique.intersection(
462
 
                                                searcher.seen)
 
553
                        searcher.seen)
463
554
        # Collapse all the common nodes into a single searcher
464
555
        all_unique_searcher = self._make_breadth_first_searcher(
465
 
                                ancestor_all_unique)
 
556
            ancestor_all_unique)
466
557
        if ancestor_all_unique:
467
558
            # We've seen these nodes in all the searchers, so we'll just go to
468
559
            # the next
516
607
        for searcher in unique_tip_searchers:
517
608
            common_to_all_unique_nodes.intersection_update(searcher.seen)
518
609
        common_to_all_unique_nodes.intersection_update(
519
 
                                    all_unique_searcher.seen)
 
610
            all_unique_searcher.seen)
520
611
        # Step all-unique less frequently than the other searchers.
521
612
        # In the common case, we don't need to spider out far here, so
522
613
        # avoid doing extra work.
523
614
        if step_all_unique:
524
 
            tstart = time.clock()
 
615
            tstart = osutils.perf_counter()
525
616
            nodes = all_unique_searcher.step()
526
617
            common_to_all_unique_nodes.update(nodes)
527
618
            if 'graph' in debug.debug_flags:
528
 
                tdelta = time.clock() - tstart
 
619
                tdelta = osutils.perf_counter() - tstart
529
620
                trace.mutter('all_unique_searcher step() took %.3fs'
530
621
                             'for %d nodes (%d total), iteration: %s',
531
622
                             tdelta, len(nodes), len(all_unique_searcher.seen),
563
654
        # TODO: it might be possible to collapse searchers faster when they
564
655
        #       only have *some* search tips in common.
565
656
        next_unique_searchers = []
566
 
        for searchers in unique_search_tips.itervalues():
 
657
        for searchers in viewvalues(unique_search_tips):
567
658
            if len(searchers) == 1:
568
659
                # Searching unique tips, go for it
569
660
                next_unique_searchers.append(searchers[0])
603
694
            # These nodes are common ancestors of all unique nodes
604
695
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
605
696
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
606
 
                step_all_unique_counter==0)
 
697
                step_all_unique_counter == 0)
607
698
            step_all_unique_counter = ((step_all_unique_counter + 1)
608
699
                                       % STEP_UNIQUE_SEARCHER_EVERY)
609
700
 
671
762
        common_ancestors = set()
672
763
        searchers = [self._make_breadth_first_searcher([r])
673
764
                     for r in revisions]
674
 
        active_searchers = searchers[:]
675
765
        border_ancestors = set()
676
766
 
677
767
        while True:
746
836
            # NULL_REVISION is only a head if it is the only entry
747
837
            candidate_heads.remove(revision.NULL_REVISION)
748
838
            if not candidate_heads:
749
 
                return set([revision.NULL_REVISION])
 
839
                return {revision.NULL_REVISION}
750
840
        if len(candidate_heads) < 2:
751
841
            return candidate_heads
752
842
        searchers = dict((c, self._make_breadth_first_searcher([c]))
753
 
                          for c in candidate_heads)
 
843
                         for c in candidate_heads)
754
844
        active_searchers = dict(searchers)
755
845
        # skip over the actual candidate for each searcher
756
 
        for searcher in active_searchers.itervalues():
757
 
            searcher.next()
 
846
        for searcher in viewvalues(active_searchers):
 
847
            next(searcher)
758
848
        # The common walker finds nodes that are common to two or more of the
759
849
        # input keys, so that we don't access all history when a currently
760
850
        # uncommon search point actually meets up with something behind a
766
856
            ancestors = set()
767
857
            # advance searches
768
858
            try:
769
 
                common_walker.next()
 
859
                next(common_walker)
770
860
            except StopIteration:
771
861
                # No common points being searched at this time.
772
862
                pass
773
 
            for candidate in active_searchers.keys():
 
863
            for candidate in list(active_searchers):
774
864
                try:
775
865
                    searcher = active_searchers[candidate]
776
866
                except KeyError:
779
869
                    # a descendant of another candidate.
780
870
                    continue
781
871
                try:
782
 
                    ancestors.update(searcher.next())
 
872
                    ancestors.update(next(searcher))
783
873
                except StopIteration:
784
874
                    del active_searchers[candidate]
785
875
                    continue
795
885
                if ancestor in common_walker.seen:
796
886
                    # some searcher has encountered our known common nodes:
797
887
                    # just stop it
798
 
                    ancestor_set = set([ancestor])
799
 
                    for searcher in searchers.itervalues():
 
888
                    ancestor_set = {ancestor}
 
889
                    for searcher in viewvalues(searchers):
800
890
                        searcher.stop_searching_any(ancestor_set)
801
891
                else:
802
892
                    # or it may have been just reached by all the searchers:
803
 
                    for searcher in searchers.itervalues():
 
893
                    for searcher in viewvalues(searchers):
804
894
                        if ancestor not in searcher.seen:
805
895
                            break
806
896
                    else:
808
898
                        # making it be known as a descendant of all candidates,
809
899
                        # so we can stop searching it, and any seen ancestors
810
900
                        new_common.add(ancestor)
811
 
                        for searcher in searchers.itervalues():
 
901
                        for searcher in viewvalues(searchers):
812
902
                            seen_ancestors =\
813
903
                                searcher.find_seen_ancestors([ancestor])
814
904
                            searcher.stop_searching_any(seen_ancestors)
846
936
                    break
847
937
                continue
848
938
            parent_ids = self.get_parent_map([next]).get(next, None)
849
 
            if not parent_ids: # Ghost, nothing to search here
 
939
            if not parent_ids:  # Ghost, nothing to search here
850
940
                continue
851
941
            for parent_id in reversed(parent_ids):
852
942
                # TODO: (performance) We see the parent at this point, but we
862
952
                stop.add(parent_id)
863
953
        return found
864
954
 
 
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
 
865
975
    def find_unique_lca(self, left_revision, right_revision,
866
976
                        count_steps=False):
867
977
        """Find a unique LCA.
911
1021
            processed.update(pending)
912
1022
            next_map = self.get_parent_map(pending)
913
1023
            next_pending = set()
914
 
            for item in next_map.iteritems():
 
1024
            for item in viewitems(next_map):
915
1025
                yield item
916
1026
                next_pending.update(p for p in item[1] if p not in processed)
917
1027
            ghosts = pending.difference(next_map)
919
1029
                yield (ghost, None)
920
1030
            pending = next_pending
921
1031
 
 
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
 
922
1052
    def iter_topo_order(self, revisions):
923
1053
        """Iterate through the input revisions in topological order.
924
1054
 
926
1056
        An ancestor may sort after a descendant if the relationship is not
927
1057
        visible in the supplied list of revisions.
928
1058
        """
929
 
        from bzrlib import tsort
 
1059
        from breezy import tsort
930
1060
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
1061
        return sorter.iter_topo_order()
932
1062
 
937
1067
        smallest number of parent lookups to determine the ancestral
938
1068
        relationship between N revisions.
939
1069
        """
940
 
        return set([candidate_descendant]) == self.heads(
 
1070
        return {candidate_descendant} == self.heads(
941
1071
            [candidate_ancestor, candidate_descendant])
942
1072
 
943
1073
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
947
1077
        lower_bound_revid <= revid <= upper_bound_revid
948
1078
        """
949
1079
        return ((upper_bound_revid is None or
950
 
                    self.is_ancestor(revid, upper_bound_revid)) and
951
 
               (lower_bound_revid is None or
952
 
                    self.is_ancestor(lower_bound_revid, revid)))
 
1080
                 self.is_ancestor(revid, upper_bound_revid)) and
 
1081
                (lower_bound_revid is None or
 
1082
                 self.is_ancestor(lower_bound_revid, revid)))
953
1083
 
954
1084
    def _search_for_extra_common(self, common, searchers):
955
1085
        """Make sure that unique nodes are genuinely unique.
988
1118
        left_searcher = searchers[0]
989
1119
        right_searcher = searchers[1]
990
1120
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
991
 
        if not unique: # No unique nodes, nothing to do
 
1121
        if not unique:  # No unique nodes, nothing to do
992
1122
            return
993
1123
        total_unique = len(unique)
994
1124
        unique = self._remove_simple_descendants(unique,
995
 
                    self.get_parent_map(unique))
 
1125
                                                 self.get_parent_map(unique))
996
1126
        simple_unique = len(unique)
997
1127
 
998
1128
        unique_searchers = []
1002
1132
            else:
1003
1133
                parent_searcher = right_searcher
1004
1134
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1005
 
            if not revs_to_search: # XXX: This shouldn't be possible
 
1135
            if not revs_to_search:  # XXX: This shouldn't be possible
1006
1136
                revs_to_search = [revision_id]
1007
1137
            searcher = self._make_breadth_first_searcher(revs_to_search)
1008
1138
            # We don't care about the starting nodes.
1019
1149
                ancestor_all_unique = set(searcher.seen)
1020
1150
            else:
1021
1151
                ancestor_all_unique = ancestor_all_unique.intersection(
1022
 
                                            searcher.seen)
 
1152
                    searcher.seen)
1023
1153
 
1024
 
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1154
        trace.mutter('Started %d unique searchers for %d unique revisions',
1025
1155
                     simple_unique, total_unique)
1026
1156
 
1027
 
        while True: # If we have no more nodes we have nothing to do
 
1157
        while True:  # If we have no more nodes we have nothing to do
1028
1158
            newly_seen_common = set()
1029
1159
            for searcher in common_searchers:
1030
1160
                newly_seen_common.update(searcher.step())
1057
1187
                # If a 'common' node is an ancestor of all unique searchers, we
1058
1188
                # can stop searching it.
1059
1189
                stop_searching_common = ancestor_all_unique.intersection(
1060
 
                                            newly_seen_common)
 
1190
                    newly_seen_common)
1061
1191
                if stop_searching_common:
1062
1192
                    for searcher in common_searchers:
1063
1193
                        searcher.stop_searching_any(stop_searching_common)
1088
1218
                for searcher in unique_searchers:
1089
1219
                    will_search_set = frozenset(searcher._next_query)
1090
1220
                    if will_search_set not in unique_search_sets:
1091
 
                        # This searcher is searching a unique set of nodes, let it
 
1221
                        # This searcher is searching a unique set of nodes, let
 
1222
                        # it
1092
1223
                        unique_search_sets.add(will_search_set)
1093
1224
                        next_unique_searchers.append(searcher)
1094
1225
                unique_searchers = next_unique_searchers
1116
1247
 
1117
1248
        # This is the same as the following loop. I don't know that it is any
1118
1249
        # faster.
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
 
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
1122
1253
 
1123
1254
        # Yet Another Way, invert the parent map (which can be cached)
1124
1255
        ## descendants = {}
1125
 
        ## for revision_id, parent_ids in parent_map.iteritems():
1126
 
        ##   for p_id in parent_ids:
 
1256
        # for revision_id, parent_ids in parent_map.iteritems():
 
1257
        # for p_id in parent_ids:
1127
1258
        ##       descendants.setdefault(p_id, []).append(revision_id)
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():
 
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):
1132
1263
            if parent_ids is None:
1133
1264
                continue
1134
1265
            for parent_id in parent_ids:
1227
1358
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1228
1359
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1229
1360
 
1230
 
    def get_result(self):
1231
 
        """Get a SearchResult for the current state of this searcher.
 
1361
    def get_state(self):
 
1362
        """Get the current state of this searcher.
1232
1363
 
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.
 
1364
        :return: Tuple with started keys, excludes and included keys
1236
1365
        """
1237
1366
        if self._returning == 'next':
1238
1367
            # We have to know the current nodes children to be able to list the
1249
1378
            next_query = self._next_query
1250
1379
        excludes = self._stopped_keys.union(next_query)
1251
1380
        included_keys = self.seen.difference(excludes)
1252
 
        return SearchResult(self._started_keys, excludes, len(included_keys),
1253
 
            included_keys)
 
1381
        return self._started_keys, excludes, included_keys
1254
1382
 
1255
1383
    def step(self):
1256
1384
        try:
1257
 
            return self.next()
 
1385
            return next(self)
1258
1386
        except StopIteration:
1259
1387
            return ()
1260
1388
 
1261
 
    def next(self):
 
1389
    def __next__(self):
1262
1390
        """Return the next ancestors of this revision.
1263
1391
 
1264
1392
        Ancestors are returned in the order they are seen in a breadth-first
1284
1412
        self.seen.update(self._next_query)
1285
1413
        return self._next_query
1286
1414
 
 
1415
    next = __next__
 
1416
 
1287
1417
    def next_with_ghosts(self):
1288
1418
        """Return the next found ancestors, with ghosts split out.
1289
1419
 
1332
1462
        parents_of_found = set()
1333
1463
        # revisions may contain nodes that point to other nodes in revisions:
1334
1464
        # we want to filter them out.
1335
 
        self.seen.update(revisions)
 
1465
        seen = self.seen
 
1466
        seen.update(revisions)
1336
1467
        parent_map = self._parents_provider.get_parent_map(revisions)
1337
1468
        found_revisions.update(parent_map)
1338
 
        for rev_id, parents in parent_map.iteritems():
 
1469
        for rev_id, parents in viewitems(parent_map):
1339
1470
            if parents is None:
1340
1471
                continue
1341
 
            new_found_parents = [p for p in parents if p not in self.seen]
 
1472
            new_found_parents = [p for p in parents if p not in seen]
1342
1473
            if new_found_parents:
1343
1474
                # Calling set.update() with an empty generator is actually
1344
1475
                # rather expensive.
1378
1509
            all_parents = []
1379
1510
            # We don't care if it is a ghost, since it can't be seen if it is
1380
1511
            # a ghost
1381
 
            for parent_ids in parent_map.itervalues():
 
1512
            for parent_ids in viewvalues(parent_map):
1382
1513
                all_parents.extend(parent_ids)
1383
 
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1514
            next_pending = all_seen.intersection(
 
1515
                all_parents).difference(seen_ancestors)
1384
1516
            seen_ancestors.update(next_pending)
1385
1517
            next_pending.difference_update(not_searched_yet)
1386
1518
            pending = next_pending
1423
1555
                    stop_rev_references[parent_id] += 1
1424
1556
            # if only the stopped revisions reference it, the ref count will be
1425
1557
            # 0 after this loop
1426
 
            for parents in self._current_parents.itervalues():
 
1558
            for parents in viewvalues(self._current_parents):
1427
1559
                for parent_id in parents:
1428
1560
                    try:
1429
1561
                        stop_rev_references[parent_id] -= 1
1430
1562
                    except KeyError:
1431
1563
                        pass
1432
1564
            stop_parents = set()
1433
 
            for rev_id, refs in stop_rev_references.iteritems():
 
1565
            for rev_id, refs in viewitems(stop_rev_references):
1434
1566
                if refs == 0:
1435
1567
                    stop_parents.add(rev_id)
1436
1568
            self._next_query.difference_update(stop_parents)
1463
1595
            return revs, ghosts
1464
1596
 
1465
1597
 
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)
 
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
1607
1611
 
1608
1612
 
1609
1613
def collapse_linear_regions(parent_map):
1646
1650
    # Will not have any nodes removed, even though you do have an
1647
1651
    # 'uninteresting' linear D->B and E->C
1648
1652
    children = {}
1649
 
    for child, parents in parent_map.iteritems():
 
1653
    for child, parents in viewitems(parent_map):
1650
1654
        children.setdefault(child, [])
1651
1655
        for p in parents:
1652
1656
            children.setdefault(p, []).append(child)
1653
1657
 
1654
 
    orig_children = dict(children)
1655
1658
    removed = set()
1656
1659
    result = dict(parent_map)
1657
1660
    for node in parent_map:
1692
1695
        """See Graph.heads()"""
1693
1696
        as_keys = [(i,) for i in ids]
1694
1697
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
 
1698
        return {h[0] for h in head_keys}
1696
1699
 
1697
1700
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((tip_revision,))
1699
 
 
1700
 
 
1701
 
_counters = [0,0,0,0,0,0,0]
 
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]
1702
1711
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
 
1712
    from ._known_graph_pyx import KnownGraph
 
1713
except ImportError as e:
1705
1714
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph
 
1715
    from ._known_graph_py import KnownGraph  # noqa: F401