/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: Gustav Hartvigsson
  • Date: 2021-01-09 21:36:27 UTC
  • Revision ID: gustav.hartvigsson@gmail.com-20210109213627-h1xwcutzy9m7a99b
Added 'Case Preserving Working Tree Use Cases' from Canonical Wiki

* Addod a page from the Canonical Bazaar wiki
  with information on the scmeatics of case
  perserving filesystems an a case insensitive
  filesystem works.
  
  * Needs re-work, but this will do as it is the
    same inforamoton as what was on the linked
    page in the currint documentation.

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
16
16
 
17
17
import time
18
18
 
19
 
from bzrlib import (
 
19
from . import (
20
20
    debug,
21
21
    errors,
22
22
    osutils,
23
23
    revision,
24
24
    trace,
25
25
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
26
 
28
27
STEP_UNIQUE_SEARCHER_EVERY = 5
29
28
 
59
58
    def __repr__(self):
60
59
        return 'DictParentsProvider(%r)' % self.ancestry
61
60
 
 
61
    # Note: DictParentsProvider does not implement get_cached_parent_map
 
62
    #       Arguably, the data is clearly cached in memory. However, this class
 
63
    #       is mostly used for testing, and it keeps the tests clean to not
 
64
    #       change it.
 
65
 
62
66
    def get_parent_map(self, keys):
63
67
        """See StackedParentsProvider.get_parent_map"""
64
68
        ancestry = self.ancestry
65
 
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
 
69
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
66
70
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
71
 
71
72
class StackedParentsProvider(object):
72
73
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
 
74
 
74
75
    The providers are queries in the order of the provided parent_providers.
75
76
    """
76
 
    
 
77
 
77
78
    def __init__(self, parent_providers):
78
79
        self._parent_providers = parent_providers
79
80
 
95
96
        """
96
97
        found = {}
97
98
        remaining = set(keys)
98
 
        for parents_provider in self._parent_providers:
99
 
            new_found = parents_provider.get_parent_map(remaining)
 
99
        # This adds getattr() overhead to each get_parent_map call. However,
 
100
        # this is StackedParentsProvider, which means we're dealing with I/O
 
101
        # (either local indexes, or remote RPCs), so CPU overhead should be
 
102
        # minimal.
 
103
        for parents_provider in self._parent_providers:
 
104
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
 
105
                                 None)
 
106
            if get_cached is None:
 
107
                continue
 
108
            new_found = get_cached(remaining)
 
109
            found.update(new_found)
 
110
            remaining.difference_update(new_found)
 
111
            if not remaining:
 
112
                break
 
113
        if not remaining:
 
114
            return found
 
115
        for parents_provider in self._parent_providers:
 
116
            try:
 
117
                new_found = parents_provider.get_parent_map(remaining)
 
118
            except errors.UnsupportedOperation:
 
119
                continue
100
120
            found.update(new_found)
101
121
            remaining.difference_update(new_found)
102
122
            if not remaining:
115
135
 
116
136
    The cache is enabled by default, but may be disabled and re-enabled.
117
137
    """
 
138
 
118
139
    def __init__(self, parent_provider=None, get_parent_map=None):
119
140
        """Constructor.
120
141
 
154
175
            return None
155
176
        return dict(self._cache)
156
177
 
 
178
    def get_cached_parent_map(self, keys):
 
179
        """Return items from the cache.
 
180
 
 
181
        This returns the same info as get_parent_map, but explicitly does not
 
182
        invoke the supplied ParentsProvider to search for uncached values.
 
183
        """
 
184
        cache = self._cache
 
185
        if cache is None:
 
186
            return {}
 
187
        return dict([(key, cache[key]) for key in keys if key in cache])
 
188
 
157
189
    def get_parent_map(self, keys):
158
190
        """See StackedParentsProvider.get_parent_map."""
159
191
        cache = self._cache
183
215
            self.missing_keys.add(key)
184
216
 
185
217
 
 
218
class CallableToParentsProviderAdapter(object):
 
219
    """A parents provider that adapts any callable to the parents provider API.
 
220
 
 
221
    i.e. it accepts calls to self.get_parent_map and relays them to the
 
222
    callable it was constructed with.
 
223
    """
 
224
 
 
225
    def __init__(self, a_callable):
 
226
        self.callable = a_callable
 
227
 
 
228
    def __repr__(self):
 
229
        return "%s(%r)" % (self.__class__.__name__, self.callable)
 
230
 
 
231
    def get_parent_map(self, keys):
 
232
        return self.callable(keys)
 
233
 
 
234
 
186
235
class Graph(object):
187
236
    """Provide incremental access to revision graphs.
188
237
 
237
286
        common ancestor of all border ancestors, because this shows that it
238
287
        cannot be a descendant of any border ancestor.
239
288
 
240
 
        The scaling of this operation should be proportional to
 
289
        The scaling of this operation should be proportional to:
 
290
 
241
291
        1. The number of uncommon ancestors
242
292
        2. The number of border ancestors
243
293
        3. The length of the shortest path between a border ancestor and an
258
308
        right = searchers[1].seen
259
309
        return (left.difference(right), right.difference(left))
260
310
 
 
311
    def find_descendants(self, old_key, new_key):
 
312
        """Find descendants of old_key that are ancestors of new_key."""
 
313
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
314
            old_key, new_key))
 
315
        graph = Graph(DictParentsProvider(child_map))
 
316
        searcher = graph._make_breadth_first_searcher([old_key])
 
317
        list(searcher)
 
318
        return searcher.seen
 
319
 
 
320
    def _find_descendant_ancestors(self, old_key, new_key):
 
321
        """Find ancestors of new_key that may be descendants of old_key."""
 
322
        stop = self._make_breadth_first_searcher([old_key])
 
323
        descendants = self._make_breadth_first_searcher([new_key])
 
324
        for revisions in descendants:
 
325
            old_stop = stop.seen.intersection(revisions)
 
326
            descendants.stop_searching_any(old_stop)
 
327
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
328
            descendants.stop_searching_any(seen_stop)
 
329
        return descendants.seen.difference(stop.seen)
 
330
 
 
331
    def get_child_map(self, keys):
 
332
        """Get a mapping from parents to children of the specified keys.
 
333
 
 
334
        This is simply the inversion of get_parent_map.  Only supplied keys
 
335
        will be discovered as children.
 
336
        :return: a dict of key:child_list for keys.
 
337
        """
 
338
        parent_map = self._parents_provider.get_parent_map(keys)
 
339
        parent_child = {}
 
340
        for child, parents in sorted(parent_map.items()):
 
341
            for parent in parents:
 
342
                parent_child.setdefault(parent, []).append(child)
 
343
        return parent_child
 
344
 
261
345
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
346
        """Find the left-hand distance to the NULL_REVISION.
263
347
 
276
360
        NULL_REVISION = revision.NULL_REVISION
277
361
        known_revnos[NULL_REVISION] = 0
278
362
 
279
 
        searching_known_tips = list(known_revnos.keys())
 
363
        searching_known_tips = list(known_revnos)
280
364
 
281
365
        unknown_searched = {}
282
366
 
283
367
        while cur_tip not in known_revnos:
284
368
            unknown_searched[cur_tip] = num_steps
285
369
            num_steps += 1
286
 
            to_search = set([cur_tip])
 
370
            to_search = {cur_tip}
287
371
            to_search.update(searching_known_tips)
288
372
            parent_map = self.get_parent_map(to_search)
289
373
            parents = parent_map.get(cur_tip, None)
290
 
            if not parents: # An empty list or None is a ghost
 
374
            if not parents:  # An empty list or None is a ghost
291
375
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
292
376
                                                       cur_tip)
293
377
            cur_tip = parents[0]
319
403
        """
320
404
        # Optimisable by concurrent searching, but a random spread should get
321
405
        # some sort of hit rate.
322
 
        result = {}
323
406
        known_revnos = []
324
407
        ghosts = []
325
408
        for key in keys:
341
424
 
342
425
        :param unique_revision: The revision_id whose ancestry we are
343
426
            interested in.
344
 
            XXX: Would this API be better if we allowed multiple revisions on
345
 
                 to be searched here?
 
427
            (XXX: Would this API be better if we allowed multiple revisions on
 
428
            to be searched here?)
346
429
        :param common_revisions: Revision_ids of ancestries to exclude.
347
430
        :return: A set of revisions in the ancestry of unique_revision
348
431
        """
376
459
            return unique_nodes
377
460
 
378
461
        (all_unique_searcher,
379
 
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
380
 
                                    unique_searcher, common_searcher)
 
462
         unique_tip_searchers) = self._make_unique_searchers(
 
463
             unique_nodes, unique_searcher, common_searcher)
381
464
 
382
465
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
383
466
                                  unique_tip_searchers, common_searcher)
399
482
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
400
483
        # we know that unique_revisions aren't in common_revisions, so skip
401
484
        # past them.
402
 
        unique_searcher.next()
 
485
        next(unique_searcher)
403
486
        common_searcher = self._make_breadth_first_searcher(common_revisions)
404
487
 
405
488
        # As long as we are still finding unique nodes, keep searching
415
498
                next_common_nodes.intersection(unique_searcher.seen))
416
499
            if unique_are_common_nodes:
417
500
                ancestors = unique_searcher.find_seen_ancestors(
418
 
                                unique_are_common_nodes)
 
501
                    unique_are_common_nodes)
419
502
                # TODO: This is a bit overboard, we only really care about
420
503
                #       the ancestors of the tips because the rest we
421
504
                #       already know. This is *correct* but causes us to
422
505
                #       search too much ancestry.
423
 
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
506
                ancestors.update(
 
507
                    common_searcher.find_seen_ancestors(ancestors))
424
508
                unique_searcher.stop_searching_any(ancestors)
425
509
                common_searcher.start_searching(ancestors)
426
510
 
435
519
 
436
520
        :return: (all_unique_searcher, unique_tip_searchers)
437
521
        """
438
 
        unique_tips = self._remove_simple_descendants(unique_nodes,
439
 
                        self.get_parent_map(unique_nodes))
 
522
        unique_tips = self._remove_simple_descendants(
 
523
            unique_nodes, self.get_parent_map(unique_nodes))
440
524
 
441
525
        if len(unique_tips) == 1:
442
526
            unique_tip_searchers = []
443
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
527
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
 
528
                unique_tips)
444
529
        else:
445
530
            unique_tip_searchers = []
446
531
            for tip in unique_tips:
459
544
                    ancestor_all_unique = set(searcher.seen)
460
545
                else:
461
546
                    ancestor_all_unique = ancestor_all_unique.intersection(
462
 
                                                searcher.seen)
 
547
                        searcher.seen)
463
548
        # Collapse all the common nodes into a single searcher
464
549
        all_unique_searcher = self._make_breadth_first_searcher(
465
 
                                ancestor_all_unique)
 
550
            ancestor_all_unique)
466
551
        if ancestor_all_unique:
467
552
            # We've seen these nodes in all the searchers, so we'll just go to
468
553
            # the next
516
601
        for searcher in unique_tip_searchers:
517
602
            common_to_all_unique_nodes.intersection_update(searcher.seen)
518
603
        common_to_all_unique_nodes.intersection_update(
519
 
                                    all_unique_searcher.seen)
 
604
            all_unique_searcher.seen)
520
605
        # Step all-unique less frequently than the other searchers.
521
606
        # In the common case, we don't need to spider out far here, so
522
607
        # avoid doing extra work.
523
608
        if step_all_unique:
524
 
            tstart = time.clock()
 
609
            tstart = osutils.perf_counter()
525
610
            nodes = all_unique_searcher.step()
526
611
            common_to_all_unique_nodes.update(nodes)
527
612
            if 'graph' in debug.debug_flags:
528
 
                tdelta = time.clock() - tstart
 
613
                tdelta = osutils.perf_counter() - tstart
529
614
                trace.mutter('all_unique_searcher step() took %.3fs'
530
615
                             'for %d nodes (%d total), iteration: %s',
531
616
                             tdelta, len(nodes), len(all_unique_searcher.seen),
563
648
        # TODO: it might be possible to collapse searchers faster when they
564
649
        #       only have *some* search tips in common.
565
650
        next_unique_searchers = []
566
 
        for searchers in unique_search_tips.itervalues():
 
651
        for searchers in unique_search_tips.values():
567
652
            if len(searchers) == 1:
568
653
                # Searching unique tips, go for it
569
654
                next_unique_searchers.append(searchers[0])
603
688
            # These nodes are common ancestors of all unique nodes
604
689
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
605
690
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
606
 
                step_all_unique_counter==0)
 
691
                step_all_unique_counter == 0)
607
692
            step_all_unique_counter = ((step_all_unique_counter + 1)
608
693
                                       % STEP_UNIQUE_SEARCHER_EVERY)
609
694
 
671
756
        common_ancestors = set()
672
757
        searchers = [self._make_breadth_first_searcher([r])
673
758
                     for r in revisions]
674
 
        active_searchers = searchers[:]
675
759
        border_ancestors = set()
676
760
 
677
761
        while True:
746
830
            # NULL_REVISION is only a head if it is the only entry
747
831
            candidate_heads.remove(revision.NULL_REVISION)
748
832
            if not candidate_heads:
749
 
                return set([revision.NULL_REVISION])
 
833
                return {revision.NULL_REVISION}
750
834
        if len(candidate_heads) < 2:
751
835
            return candidate_heads
752
836
        searchers = dict((c, self._make_breadth_first_searcher([c]))
753
 
                          for c in candidate_heads)
 
837
                         for c in candidate_heads)
754
838
        active_searchers = dict(searchers)
755
839
        # skip over the actual candidate for each searcher
756
 
        for searcher in active_searchers.itervalues():
757
 
            searcher.next()
 
840
        for searcher in active_searchers.values():
 
841
            next(searcher)
758
842
        # The common walker finds nodes that are common to two or more of the
759
843
        # input keys, so that we don't access all history when a currently
760
844
        # uncommon search point actually meets up with something behind a
766
850
            ancestors = set()
767
851
            # advance searches
768
852
            try:
769
 
                common_walker.next()
 
853
                next(common_walker)
770
854
            except StopIteration:
771
855
                # No common points being searched at this time.
772
856
                pass
773
 
            for candidate in active_searchers.keys():
 
857
            for candidate in list(active_searchers):
774
858
                try:
775
859
                    searcher = active_searchers[candidate]
776
860
                except KeyError:
779
863
                    # a descendant of another candidate.
780
864
                    continue
781
865
                try:
782
 
                    ancestors.update(searcher.next())
 
866
                    ancestors.update(next(searcher))
783
867
                except StopIteration:
784
868
                    del active_searchers[candidate]
785
869
                    continue
795
879
                if ancestor in common_walker.seen:
796
880
                    # some searcher has encountered our known common nodes:
797
881
                    # just stop it
798
 
                    ancestor_set = set([ancestor])
799
 
                    for searcher in searchers.itervalues():
 
882
                    ancestor_set = {ancestor}
 
883
                    for searcher in searchers.values():
800
884
                        searcher.stop_searching_any(ancestor_set)
801
885
                else:
802
886
                    # or it may have been just reached by all the searchers:
803
 
                    for searcher in searchers.itervalues():
 
887
                    for searcher in searchers.values():
804
888
                        if ancestor not in searcher.seen:
805
889
                            break
806
890
                    else:
808
892
                        # making it be known as a descendant of all candidates,
809
893
                        # so we can stop searching it, and any seen ancestors
810
894
                        new_common.add(ancestor)
811
 
                        for searcher in searchers.itervalues():
 
895
                        for searcher in searchers.values():
812
896
                            seen_ancestors =\
813
897
                                searcher.find_seen_ancestors([ancestor])
814
898
                            searcher.stop_searching_any(seen_ancestors)
846
930
                    break
847
931
                continue
848
932
            parent_ids = self.get_parent_map([next]).get(next, None)
849
 
            if not parent_ids: # Ghost, nothing to search here
 
933
            if not parent_ids:  # Ghost, nothing to search here
850
934
                continue
851
935
            for parent_id in reversed(parent_ids):
852
936
                # TODO: (performance) We see the parent at this point, but we
862
946
                stop.add(parent_id)
863
947
        return found
864
948
 
 
949
    def find_lefthand_merger(self, merged_key, tip_key):
 
950
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
951
 
 
952
        We do this by first finding the descendants of merged_key, then
 
953
        walking through the lefthand ancestry of tip_key until we find a key
 
954
        that doesn't descend from merged_key.  Its child is the key that
 
955
        merged merged_key.
 
956
 
 
957
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
958
            merged_key if it is a lefthand ancestor of tip_key.
 
959
            None if no ancestor of tip_key merged merged_key.
 
960
        """
 
961
        descendants = self.find_descendants(merged_key, tip_key)
 
962
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
963
        last_candidate = None
 
964
        for candidate in candidate_iterator:
 
965
            if candidate not in descendants:
 
966
                return last_candidate
 
967
            last_candidate = candidate
 
968
 
865
969
    def find_unique_lca(self, left_revision, right_revision,
866
970
                        count_steps=False):
867
971
        """Find a unique LCA.
911
1015
            processed.update(pending)
912
1016
            next_map = self.get_parent_map(pending)
913
1017
            next_pending = set()
914
 
            for item in next_map.iteritems():
 
1018
            for item in next_map.items():
915
1019
                yield item
916
1020
                next_pending.update(p for p in item[1] if p not in processed)
917
1021
            ghosts = pending.difference(next_map)
919
1023
                yield (ghost, None)
920
1024
            pending = next_pending
921
1025
 
 
1026
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
1027
        if stop_keys is None:
 
1028
            stop_keys = ()
 
1029
        next_key = start_key
 
1030
 
 
1031
        def get_parents(key):
 
1032
            try:
 
1033
                return self._parents_provider.get_parent_map([key])[key]
 
1034
            except KeyError:
 
1035
                raise errors.RevisionNotPresent(next_key, self)
 
1036
        while True:
 
1037
            if next_key in stop_keys:
 
1038
                return
 
1039
            parents = get_parents(next_key)
 
1040
            yield next_key
 
1041
            if len(parents) == 0:
 
1042
                return
 
1043
            else:
 
1044
                next_key = parents[0]
 
1045
 
922
1046
    def iter_topo_order(self, revisions):
923
1047
        """Iterate through the input revisions in topological order.
924
1048
 
926
1050
        An ancestor may sort after a descendant if the relationship is not
927
1051
        visible in the supplied list of revisions.
928
1052
        """
929
 
        from bzrlib import tsort
 
1053
        from breezy import tsort
930
1054
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
1055
        return sorter.iter_topo_order()
932
1056
 
937
1061
        smallest number of parent lookups to determine the ancestral
938
1062
        relationship between N revisions.
939
1063
        """
940
 
        return set([candidate_descendant]) == self.heads(
 
1064
        return {candidate_descendant} == self.heads(
941
1065
            [candidate_ancestor, candidate_descendant])
942
1066
 
943
1067
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
947
1071
        lower_bound_revid <= revid <= upper_bound_revid
948
1072
        """
949
1073
        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)))
 
1074
                 self.is_ancestor(revid, upper_bound_revid)) and
 
1075
                (lower_bound_revid is None or
 
1076
                 self.is_ancestor(lower_bound_revid, revid)))
953
1077
 
954
1078
    def _search_for_extra_common(self, common, searchers):
955
1079
        """Make sure that unique nodes are genuinely unique.
988
1112
        left_searcher = searchers[0]
989
1113
        right_searcher = searchers[1]
990
1114
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
991
 
        if not unique: # No unique nodes, nothing to do
 
1115
        if not unique:  # No unique nodes, nothing to do
992
1116
            return
993
1117
        total_unique = len(unique)
994
1118
        unique = self._remove_simple_descendants(unique,
995
 
                    self.get_parent_map(unique))
 
1119
                                                 self.get_parent_map(unique))
996
1120
        simple_unique = len(unique)
997
1121
 
998
1122
        unique_searchers = []
1002
1126
            else:
1003
1127
                parent_searcher = right_searcher
1004
1128
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1005
 
            if not revs_to_search: # XXX: This shouldn't be possible
 
1129
            if not revs_to_search:  # XXX: This shouldn't be possible
1006
1130
                revs_to_search = [revision_id]
1007
1131
            searcher = self._make_breadth_first_searcher(revs_to_search)
1008
1132
            # We don't care about the starting nodes.
1019
1143
                ancestor_all_unique = set(searcher.seen)
1020
1144
            else:
1021
1145
                ancestor_all_unique = ancestor_all_unique.intersection(
1022
 
                                            searcher.seen)
 
1146
                    searcher.seen)
1023
1147
 
1024
 
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1148
        trace.mutter('Started %d unique searchers for %d unique revisions',
1025
1149
                     simple_unique, total_unique)
1026
1150
 
1027
 
        while True: # If we have no more nodes we have nothing to do
 
1151
        while True:  # If we have no more nodes we have nothing to do
1028
1152
            newly_seen_common = set()
1029
1153
            for searcher in common_searchers:
1030
1154
                newly_seen_common.update(searcher.step())
1057
1181
                # If a 'common' node is an ancestor of all unique searchers, we
1058
1182
                # can stop searching it.
1059
1183
                stop_searching_common = ancestor_all_unique.intersection(
1060
 
                                            newly_seen_common)
 
1184
                    newly_seen_common)
1061
1185
                if stop_searching_common:
1062
1186
                    for searcher in common_searchers:
1063
1187
                        searcher.stop_searching_any(stop_searching_common)
1088
1212
                for searcher in unique_searchers:
1089
1213
                    will_search_set = frozenset(searcher._next_query)
1090
1214
                    if will_search_set not in unique_search_sets:
1091
 
                        # This searcher is searching a unique set of nodes, let it
 
1215
                        # This searcher is searching a unique set of nodes, let
 
1216
                        # it
1092
1217
                        unique_search_sets.add(will_search_set)
1093
1218
                        next_unique_searchers.append(searcher)
1094
1219
                unique_searchers = next_unique_searchers
1116
1241
 
1117
1242
        # This is the same as the following loop. I don't know that it is any
1118
1243
        # 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
 
1244
        # simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
 
1245
        # if p_ids is not None and revisions.intersection(p_ids))
 
1246
        # return simple_ancestors
1122
1247
 
1123
1248
        # Yet Another Way, invert the parent map (which can be cached)
1124
1249
        ## descendants = {}
1125
 
        ## for revision_id, parent_ids in parent_map.iteritems():
1126
 
        ##   for p_id in parent_ids:
 
1250
        # for revision_id, parent_ids in parent_map.iteritems():
 
1251
        # for p_id in parent_ids:
1127
1252
        ##       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():
 
1253
        # for revision in revisions.intersection(descendants):
 
1254
        # simple_ancestors.difference_update(descendants[revision])
 
1255
        # return simple_ancestors
 
1256
        for revision, parent_ids in parent_map.items():
1132
1257
            if parent_ids is None:
1133
1258
                continue
1134
1259
            for parent_id in parent_ids:
1227
1352
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1228
1353
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1229
1354
 
1230
 
    def get_result(self):
1231
 
        """Get a SearchResult for the current state of this searcher.
 
1355
    def get_state(self):
 
1356
        """Get the current state of this searcher.
1232
1357
 
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.
 
1358
        :return: Tuple with started keys, excludes and included keys
1236
1359
        """
1237
1360
        if self._returning == 'next':
1238
1361
            # We have to know the current nodes children to be able to list the
1249
1372
            next_query = self._next_query
1250
1373
        excludes = self._stopped_keys.union(next_query)
1251
1374
        included_keys = self.seen.difference(excludes)
1252
 
        return SearchResult(self._started_keys, excludes, len(included_keys),
1253
 
            included_keys)
 
1375
        return self._started_keys, excludes, included_keys
1254
1376
 
1255
1377
    def step(self):
1256
1378
        try:
1257
 
            return self.next()
 
1379
            return next(self)
1258
1380
        except StopIteration:
1259
1381
            return ()
1260
1382
 
1261
 
    def next(self):
 
1383
    def __next__(self):
1262
1384
        """Return the next ancestors of this revision.
1263
1385
 
1264
1386
        Ancestors are returned in the order they are seen in a breadth-first
1284
1406
        self.seen.update(self._next_query)
1285
1407
        return self._next_query
1286
1408
 
 
1409
    next = __next__
 
1410
 
1287
1411
    def next_with_ghosts(self):
1288
1412
        """Return the next found ancestors, with ghosts split out.
1289
1413
 
1332
1456
        parents_of_found = set()
1333
1457
        # revisions may contain nodes that point to other nodes in revisions:
1334
1458
        # we want to filter them out.
1335
 
        self.seen.update(revisions)
 
1459
        seen = self.seen
 
1460
        seen.update(revisions)
1336
1461
        parent_map = self._parents_provider.get_parent_map(revisions)
1337
1462
        found_revisions.update(parent_map)
1338
 
        for rev_id, parents in parent_map.iteritems():
 
1463
        for rev_id, parents in parent_map.items():
1339
1464
            if parents is None:
1340
1465
                continue
1341
 
            new_found_parents = [p for p in parents if p not in self.seen]
 
1466
            new_found_parents = [p for p in parents if p not in seen]
1342
1467
            if new_found_parents:
1343
1468
                # Calling set.update() with an empty generator is actually
1344
1469
                # rather expensive.
1378
1503
            all_parents = []
1379
1504
            # We don't care if it is a ghost, since it can't be seen if it is
1380
1505
            # a ghost
1381
 
            for parent_ids in parent_map.itervalues():
 
1506
            for parent_ids in parent_map.values():
1382
1507
                all_parents.extend(parent_ids)
1383
 
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1508
            next_pending = all_seen.intersection(
 
1509
                all_parents).difference(seen_ancestors)
1384
1510
            seen_ancestors.update(next_pending)
1385
1511
            next_pending.difference_update(not_searched_yet)
1386
1512
            pending = next_pending
1423
1549
                    stop_rev_references[parent_id] += 1
1424
1550
            # if only the stopped revisions reference it, the ref count will be
1425
1551
            # 0 after this loop
1426
 
            for parents in self._current_parents.itervalues():
 
1552
            for parents in self._current_parents.values():
1427
1553
                for parent_id in parents:
1428
1554
                    try:
1429
1555
                        stop_rev_references[parent_id] -= 1
1430
1556
                    except KeyError:
1431
1557
                        pass
1432
1558
            stop_parents = set()
1433
 
            for rev_id, refs in stop_rev_references.iteritems():
 
1559
            for rev_id, refs in stop_rev_references.items():
1434
1560
                if refs == 0:
1435
1561
                    stop_parents.add(rev_id)
1436
1562
            self._next_query.difference_update(stop_parents)
1463
1589
            return revs, ghosts
1464
1590
 
1465
1591
 
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)
 
1592
def invert_parent_map(parent_map):
 
1593
    """Given a map from child => parents, create a map of parent=>children"""
 
1594
    child_map = {}
 
1595
    for child, parents in parent_map.items():
 
1596
        for p in parents:
 
1597
            # Any given parent is likely to have only a small handful
 
1598
            # of children, many will have only one. So we avoid mem overhead of
 
1599
            # a list, in exchange for extra copying of tuples
 
1600
            if p not in child_map:
 
1601
                child_map[p] = (child,)
 
1602
            else:
 
1603
                child_map[p] = child_map[p] + (child,)
 
1604
    return child_map
1607
1605
 
1608
1606
 
1609
1607
def collapse_linear_regions(parent_map):
1646
1644
    # Will not have any nodes removed, even though you do have an
1647
1645
    # 'uninteresting' linear D->B and E->C
1648
1646
    children = {}
1649
 
    for child, parents in parent_map.iteritems():
 
1647
    for child, parents in parent_map.items():
1650
1648
        children.setdefault(child, [])
1651
1649
        for p in parents:
1652
1650
            children.setdefault(p, []).append(child)
1653
1651
 
1654
 
    orig_children = dict(children)
1655
1652
    removed = set()
1656
1653
    result = dict(parent_map)
1657
1654
    for node in parent_map:
1692
1689
        """See Graph.heads()"""
1693
1690
        as_keys = [(i,) for i in ids]
1694
1691
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
 
1692
        return {h[0] for h in head_keys}
1696
1693
 
1697
1694
    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]
 
1695
        nodes = self._graph.merge_sort((tip_revision,))
 
1696
        for node in nodes:
 
1697
            node.key = node.key[0]
 
1698
        return nodes
 
1699
 
 
1700
    def add_node(self, revision, parents):
 
1701
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1702
 
 
1703
 
 
1704
_counters = [0, 0, 0, 0, 0, 0, 0]
1702
1705
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
 
1706
    from ._known_graph_pyx import KnownGraph
 
1707
except ImportError as e:
1705
1708
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph
 
1709
    from ._known_graph_py import KnownGraph  # noqa: F401