/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: John Ferlito
  • Date: 2009-09-02 04:31:45 UTC
  • mto: (4665.7.1 serve-init)
  • mto: This revision was merged to the branch mainline in revision 4913.
  • Revision ID: johnf@inodes.org-20090902043145-gxdsfw03ilcwbyn5
Add a debian init script for bzr --serve

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, 2008, 2009 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 . import (
 
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
22
 
    osutils,
23
22
    revision,
24
23
    trace,
25
24
    )
 
25
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
26
26
 
27
27
STEP_UNIQUE_SEARCHER_EVERY = 5
28
28
 
58
58
    def __repr__(self):
59
59
        return 'DictParentsProvider(%r)' % self.ancestry
60
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
 
 
66
61
    def get_parent_map(self, keys):
67
62
        """See StackedParentsProvider.get_parent_map"""
68
63
        ancestry = self.ancestry
69
 
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
64
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
70
65
 
 
66
@deprecated_function(deprecated_in((1, 16, 0)))
 
67
def _StackedParentsProvider(*args, **kwargs):
 
68
    return StackedParentsProvider(*args, **kwargs)
71
69
 
72
70
class StackedParentsProvider(object):
73
71
    """A parents provider which stacks (or unions) multiple providers.
74
 
 
 
72
    
75
73
    The providers are queries in the order of the provided parent_providers.
76
74
    """
77
 
 
 
75
    
78
76
    def __init__(self, parent_providers):
79
77
        self._parent_providers = parent_providers
80
78
 
96
94
        """
97
95
        found = {}
98
96
        remaining = set(keys)
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
 
97
        for parents_provider in self._parent_providers:
 
98
            new_found = parents_provider.get_parent_map(remaining)
120
99
            found.update(new_found)
121
100
            remaining.difference_update(new_found)
122
101
            if not remaining:
135
114
 
136
115
    The cache is enabled by default, but may be disabled and re-enabled.
137
116
    """
138
 
 
139
117
    def __init__(self, parent_provider=None, get_parent_map=None):
140
118
        """Constructor.
141
119
 
175
153
            return None
176
154
        return dict(self._cache)
177
155
 
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
 
 
189
156
    def get_parent_map(self, keys):
190
157
        """See StackedParentsProvider.get_parent_map."""
191
158
        cache = self._cache
215
182
            self.missing_keys.add(key)
216
183
 
217
184
 
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
 
 
235
185
class Graph(object):
236
186
    """Provide incremental access to revision graphs.
237
187
 
286
236
        common ancestor of all border ancestors, because this shows that it
287
237
        cannot be a descendant of any border ancestor.
288
238
 
289
 
        The scaling of this operation should be proportional to:
290
 
 
 
239
        The scaling of this operation should be proportional to
291
240
        1. The number of uncommon ancestors
292
241
        2. The number of border ancestors
293
242
        3. The length of the shortest path between a border ancestor and an
308
257
        right = searchers[1].seen
309
258
        return (left.difference(right), right.difference(left))
310
259
 
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
 
 
345
260
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
346
261
        """Find the left-hand distance to the NULL_REVISION.
347
262
 
360
275
        NULL_REVISION = revision.NULL_REVISION
361
276
        known_revnos[NULL_REVISION] = 0
362
277
 
363
 
        searching_known_tips = list(known_revnos)
 
278
        searching_known_tips = list(known_revnos.keys())
364
279
 
365
280
        unknown_searched = {}
366
281
 
367
282
        while cur_tip not in known_revnos:
368
283
            unknown_searched[cur_tip] = num_steps
369
284
            num_steps += 1
370
 
            to_search = {cur_tip}
 
285
            to_search = set([cur_tip])
371
286
            to_search.update(searching_known_tips)
372
287
            parent_map = self.get_parent_map(to_search)
373
288
            parents = parent_map.get(cur_tip, None)
374
 
            if not parents:  # An empty list or None is a ghost
 
289
            if not parents: # An empty list or None is a ghost
375
290
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
376
291
                                                       cur_tip)
377
292
            cur_tip = parents[0]
403
318
        """
404
319
        # Optimisable by concurrent searching, but a random spread should get
405
320
        # some sort of hit rate.
 
321
        result = {}
406
322
        known_revnos = []
407
323
        ghosts = []
408
324
        for key in keys:
424
340
 
425
341
        :param unique_revision: The revision_id whose ancestry we are
426
342
            interested in.
427
 
            (XXX: Would this API be better if we allowed multiple revisions on
428
 
            to be searched here?)
 
343
            XXX: Would this API be better if we allowed multiple revisions on
 
344
                 to be searched here?
429
345
        :param common_revisions: Revision_ids of ancestries to exclude.
430
346
        :return: A set of revisions in the ancestry of unique_revision
431
347
        """
459
375
            return unique_nodes
460
376
 
461
377
        (all_unique_searcher,
462
 
         unique_tip_searchers) = self._make_unique_searchers(
463
 
             unique_nodes, unique_searcher, common_searcher)
 
378
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
379
                                    unique_searcher, common_searcher)
464
380
 
465
381
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
466
382
                                  unique_tip_searchers, common_searcher)
482
398
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
483
399
        # we know that unique_revisions aren't in common_revisions, so skip
484
400
        # past them.
485
 
        next(unique_searcher)
 
401
        unique_searcher.next()
486
402
        common_searcher = self._make_breadth_first_searcher(common_revisions)
487
403
 
488
404
        # As long as we are still finding unique nodes, keep searching
498
414
                next_common_nodes.intersection(unique_searcher.seen))
499
415
            if unique_are_common_nodes:
500
416
                ancestors = unique_searcher.find_seen_ancestors(
501
 
                    unique_are_common_nodes)
 
417
                                unique_are_common_nodes)
502
418
                # TODO: This is a bit overboard, we only really care about
503
419
                #       the ancestors of the tips because the rest we
504
420
                #       already know. This is *correct* but causes us to
505
421
                #       search too much ancestry.
506
 
                ancestors.update(
507
 
                    common_searcher.find_seen_ancestors(ancestors))
 
422
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
508
423
                unique_searcher.stop_searching_any(ancestors)
509
424
                common_searcher.start_searching(ancestors)
510
425
 
519
434
 
520
435
        :return: (all_unique_searcher, unique_tip_searchers)
521
436
        """
522
 
        unique_tips = self._remove_simple_descendants(
523
 
            unique_nodes, self.get_parent_map(unique_nodes))
 
437
        unique_tips = self._remove_simple_descendants(unique_nodes,
 
438
                        self.get_parent_map(unique_nodes))
524
439
 
525
440
        if len(unique_tips) == 1:
526
441
            unique_tip_searchers = []
527
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
528
 
                unique_tips)
 
442
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
529
443
        else:
530
444
            unique_tip_searchers = []
531
445
            for tip in unique_tips:
544
458
                    ancestor_all_unique = set(searcher.seen)
545
459
                else:
546
460
                    ancestor_all_unique = ancestor_all_unique.intersection(
547
 
                        searcher.seen)
 
461
                                                searcher.seen)
548
462
        # Collapse all the common nodes into a single searcher
549
463
        all_unique_searcher = self._make_breadth_first_searcher(
550
 
            ancestor_all_unique)
 
464
                                ancestor_all_unique)
551
465
        if ancestor_all_unique:
552
466
            # We've seen these nodes in all the searchers, so we'll just go to
553
467
            # the next
601
515
        for searcher in unique_tip_searchers:
602
516
            common_to_all_unique_nodes.intersection_update(searcher.seen)
603
517
        common_to_all_unique_nodes.intersection_update(
604
 
            all_unique_searcher.seen)
 
518
                                    all_unique_searcher.seen)
605
519
        # Step all-unique less frequently than the other searchers.
606
520
        # In the common case, we don't need to spider out far here, so
607
521
        # avoid doing extra work.
608
522
        if step_all_unique:
609
 
            tstart = osutils.perf_counter()
 
523
            tstart = time.clock()
610
524
            nodes = all_unique_searcher.step()
611
525
            common_to_all_unique_nodes.update(nodes)
612
526
            if 'graph' in debug.debug_flags:
613
 
                tdelta = osutils.perf_counter() - tstart
 
527
                tdelta = time.clock() - tstart
614
528
                trace.mutter('all_unique_searcher step() took %.3fs'
615
529
                             'for %d nodes (%d total), iteration: %s',
616
530
                             tdelta, len(nodes), len(all_unique_searcher.seen),
648
562
        # TODO: it might be possible to collapse searchers faster when they
649
563
        #       only have *some* search tips in common.
650
564
        next_unique_searchers = []
651
 
        for searchers in unique_search_tips.values():
 
565
        for searchers in unique_search_tips.itervalues():
652
566
            if len(searchers) == 1:
653
567
                # Searching unique tips, go for it
654
568
                next_unique_searchers.append(searchers[0])
688
602
            # These nodes are common ancestors of all unique nodes
689
603
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
690
604
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
691
 
                step_all_unique_counter == 0)
 
605
                step_all_unique_counter==0)
692
606
            step_all_unique_counter = ((step_all_unique_counter + 1)
693
607
                                       % STEP_UNIQUE_SEARCHER_EVERY)
694
608
 
756
670
        common_ancestors = set()
757
671
        searchers = [self._make_breadth_first_searcher([r])
758
672
                     for r in revisions]
 
673
        active_searchers = searchers[:]
759
674
        border_ancestors = set()
760
675
 
761
676
        while True:
830
745
            # NULL_REVISION is only a head if it is the only entry
831
746
            candidate_heads.remove(revision.NULL_REVISION)
832
747
            if not candidate_heads:
833
 
                return {revision.NULL_REVISION}
 
748
                return set([revision.NULL_REVISION])
834
749
        if len(candidate_heads) < 2:
835
750
            return candidate_heads
836
751
        searchers = dict((c, self._make_breadth_first_searcher([c]))
837
 
                         for c in candidate_heads)
 
752
                          for c in candidate_heads)
838
753
        active_searchers = dict(searchers)
839
754
        # skip over the actual candidate for each searcher
840
 
        for searcher in active_searchers.values():
841
 
            next(searcher)
 
755
        for searcher in active_searchers.itervalues():
 
756
            searcher.next()
842
757
        # The common walker finds nodes that are common to two or more of the
843
758
        # input keys, so that we don't access all history when a currently
844
759
        # uncommon search point actually meets up with something behind a
850
765
            ancestors = set()
851
766
            # advance searches
852
767
            try:
853
 
                next(common_walker)
 
768
                common_walker.next()
854
769
            except StopIteration:
855
770
                # No common points being searched at this time.
856
771
                pass
857
 
            for candidate in list(active_searchers):
 
772
            for candidate in active_searchers.keys():
858
773
                try:
859
774
                    searcher = active_searchers[candidate]
860
775
                except KeyError:
863
778
                    # a descendant of another candidate.
864
779
                    continue
865
780
                try:
866
 
                    ancestors.update(next(searcher))
 
781
                    ancestors.update(searcher.next())
867
782
                except StopIteration:
868
783
                    del active_searchers[candidate]
869
784
                    continue
879
794
                if ancestor in common_walker.seen:
880
795
                    # some searcher has encountered our known common nodes:
881
796
                    # just stop it
882
 
                    ancestor_set = {ancestor}
883
 
                    for searcher in searchers.values():
 
797
                    ancestor_set = set([ancestor])
 
798
                    for searcher in searchers.itervalues():
884
799
                        searcher.stop_searching_any(ancestor_set)
885
800
                else:
886
801
                    # or it may have been just reached by all the searchers:
887
 
                    for searcher in searchers.values():
 
802
                    for searcher in searchers.itervalues():
888
803
                        if ancestor not in searcher.seen:
889
804
                            break
890
805
                    else:
892
807
                        # making it be known as a descendant of all candidates,
893
808
                        # so we can stop searching it, and any seen ancestors
894
809
                        new_common.add(ancestor)
895
 
                        for searcher in searchers.values():
 
810
                        for searcher in searchers.itervalues():
896
811
                            seen_ancestors =\
897
812
                                searcher.find_seen_ancestors([ancestor])
898
813
                            searcher.stop_searching_any(seen_ancestors)
930
845
                    break
931
846
                continue
932
847
            parent_ids = self.get_parent_map([next]).get(next, None)
933
 
            if not parent_ids:  # Ghost, nothing to search here
 
848
            if not parent_ids: # Ghost, nothing to search here
934
849
                continue
935
850
            for parent_id in reversed(parent_ids):
936
851
                # TODO: (performance) We see the parent at this point, but we
946
861
                stop.add(parent_id)
947
862
        return found
948
863
 
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
 
 
969
864
    def find_unique_lca(self, left_revision, right_revision,
970
865
                        count_steps=False):
971
866
        """Find a unique LCA.
1015
910
            processed.update(pending)
1016
911
            next_map = self.get_parent_map(pending)
1017
912
            next_pending = set()
1018
 
            for item in next_map.items():
 
913
            for item in next_map.iteritems():
1019
914
                yield item
1020
915
                next_pending.update(p for p in item[1] if p not in processed)
1021
916
            ghosts = pending.difference(next_map)
1023
918
                yield (ghost, None)
1024
919
            pending = next_pending
1025
920
 
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
 
 
1046
921
    def iter_topo_order(self, revisions):
1047
922
        """Iterate through the input revisions in topological order.
1048
923
 
1050
925
        An ancestor may sort after a descendant if the relationship is not
1051
926
        visible in the supplied list of revisions.
1052
927
        """
1053
 
        from breezy import tsort
 
928
        from bzrlib import tsort
1054
929
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1055
930
        return sorter.iter_topo_order()
1056
931
 
1061
936
        smallest number of parent lookups to determine the ancestral
1062
937
        relationship between N revisions.
1063
938
        """
1064
 
        return {candidate_descendant} == self.heads(
 
939
        return set([candidate_descendant]) == self.heads(
1065
940
            [candidate_ancestor, candidate_descendant])
1066
941
 
1067
942
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1071
946
        lower_bound_revid <= revid <= upper_bound_revid
1072
947
        """
1073
948
        return ((upper_bound_revid is None or
1074
 
                 self.is_ancestor(revid, upper_bound_revid)) and
1075
 
                (lower_bound_revid is None or
1076
 
                 self.is_ancestor(lower_bound_revid, revid)))
 
949
                    self.is_ancestor(revid, upper_bound_revid)) and
 
950
               (lower_bound_revid is None or
 
951
                    self.is_ancestor(lower_bound_revid, revid)))
1077
952
 
1078
953
    def _search_for_extra_common(self, common, searchers):
1079
954
        """Make sure that unique nodes are genuinely unique.
1112
987
        left_searcher = searchers[0]
1113
988
        right_searcher = searchers[1]
1114
989
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1115
 
        if not unique:  # No unique nodes, nothing to do
 
990
        if not unique: # No unique nodes, nothing to do
1116
991
            return
1117
992
        total_unique = len(unique)
1118
993
        unique = self._remove_simple_descendants(unique,
1119
 
                                                 self.get_parent_map(unique))
 
994
                    self.get_parent_map(unique))
1120
995
        simple_unique = len(unique)
1121
996
 
1122
997
        unique_searchers = []
1126
1001
            else:
1127
1002
                parent_searcher = right_searcher
1128
1003
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1129
 
            if not revs_to_search:  # XXX: This shouldn't be possible
 
1004
            if not revs_to_search: # XXX: This shouldn't be possible
1130
1005
                revs_to_search = [revision_id]
1131
1006
            searcher = self._make_breadth_first_searcher(revs_to_search)
1132
1007
            # We don't care about the starting nodes.
1143
1018
                ancestor_all_unique = set(searcher.seen)
1144
1019
            else:
1145
1020
                ancestor_all_unique = ancestor_all_unique.intersection(
1146
 
                    searcher.seen)
 
1021
                                            searcher.seen)
1147
1022
 
1148
 
        trace.mutter('Started %d unique searchers for %d unique revisions',
 
1023
        trace.mutter('Started %s unique searchers for %s unique revisions',
1149
1024
                     simple_unique, total_unique)
1150
1025
 
1151
 
        while True:  # If we have no more nodes we have nothing to do
 
1026
        while True: # If we have no more nodes we have nothing to do
1152
1027
            newly_seen_common = set()
1153
1028
            for searcher in common_searchers:
1154
1029
                newly_seen_common.update(searcher.step())
1181
1056
                # If a 'common' node is an ancestor of all unique searchers, we
1182
1057
                # can stop searching it.
1183
1058
                stop_searching_common = ancestor_all_unique.intersection(
1184
 
                    newly_seen_common)
 
1059
                                            newly_seen_common)
1185
1060
                if stop_searching_common:
1186
1061
                    for searcher in common_searchers:
1187
1062
                        searcher.stop_searching_any(stop_searching_common)
1212
1087
                for searcher in unique_searchers:
1213
1088
                    will_search_set = frozenset(searcher._next_query)
1214
1089
                    if will_search_set not in unique_search_sets:
1215
 
                        # This searcher is searching a unique set of nodes, let
1216
 
                        # it
 
1090
                        # This searcher is searching a unique set of nodes, let it
1217
1091
                        unique_search_sets.add(will_search_set)
1218
1092
                        next_unique_searchers.append(searcher)
1219
1093
                unique_searchers = next_unique_searchers
1241
1115
 
1242
1116
        # This is the same as the following loop. I don't know that it is any
1243
1117
        # faster.
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
 
1118
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
 
1119
        ##     if p_ids is not None and revisions.intersection(p_ids))
 
1120
        ## return simple_ancestors
1247
1121
 
1248
1122
        # Yet Another Way, invert the parent map (which can be cached)
1249
1123
        ## descendants = {}
1250
 
        # for revision_id, parent_ids in parent_map.iteritems():
1251
 
        # for p_id in parent_ids:
 
1124
        ## for revision_id, parent_ids in parent_map.iteritems():
 
1125
        ##   for p_id in parent_ids:
1252
1126
        ##       descendants.setdefault(p_id, []).append(revision_id)
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():
 
1127
        ## for revision in revisions.intersection(descendants):
 
1128
        ##   simple_ancestors.difference_update(descendants[revision])
 
1129
        ## return simple_ancestors
 
1130
        for revision, parent_ids in parent_map.iteritems():
1257
1131
            if parent_ids is None:
1258
1132
                continue
1259
1133
            for parent_id in parent_ids:
1352
1226
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1353
1227
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1354
1228
 
1355
 
    def get_state(self):
1356
 
        """Get the current state of this searcher.
 
1229
    def get_result(self):
 
1230
        """Get a SearchResult for the current state of this searcher.
1357
1231
 
1358
 
        :return: Tuple with started keys, excludes and included keys
 
1232
        :return: A SearchResult for this search so far. The SearchResult is
 
1233
            static - the search can be advanced and the search result will not
 
1234
            be invalidated or altered.
1359
1235
        """
1360
1236
        if self._returning == 'next':
1361
1237
            # We have to know the current nodes children to be able to list the
1372
1248
            next_query = self._next_query
1373
1249
        excludes = self._stopped_keys.union(next_query)
1374
1250
        included_keys = self.seen.difference(excludes)
1375
 
        return self._started_keys, excludes, included_keys
 
1251
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
1252
            included_keys)
1376
1253
 
1377
1254
    def step(self):
1378
1255
        try:
1379
 
            return next(self)
 
1256
            return self.next()
1380
1257
        except StopIteration:
1381
1258
            return ()
1382
1259
 
1383
 
    def __next__(self):
 
1260
    def next(self):
1384
1261
        """Return the next ancestors of this revision.
1385
1262
 
1386
1263
        Ancestors are returned in the order they are seen in a breadth-first
1406
1283
        self.seen.update(self._next_query)
1407
1284
        return self._next_query
1408
1285
 
1409
 
    next = __next__
1410
 
 
1411
1286
    def next_with_ghosts(self):
1412
1287
        """Return the next found ancestors, with ghosts split out.
1413
1288
 
1456
1331
        parents_of_found = set()
1457
1332
        # revisions may contain nodes that point to other nodes in revisions:
1458
1333
        # we want to filter them out.
1459
 
        seen = self.seen
1460
 
        seen.update(revisions)
 
1334
        self.seen.update(revisions)
1461
1335
        parent_map = self._parents_provider.get_parent_map(revisions)
1462
1336
        found_revisions.update(parent_map)
1463
 
        for rev_id, parents in parent_map.items():
 
1337
        for rev_id, parents in parent_map.iteritems():
1464
1338
            if parents is None:
1465
1339
                continue
1466
 
            new_found_parents = [p for p in parents if p not in seen]
 
1340
            new_found_parents = [p for p in parents if p not in self.seen]
1467
1341
            if new_found_parents:
1468
1342
                # Calling set.update() with an empty generator is actually
1469
1343
                # rather expensive.
1503
1377
            all_parents = []
1504
1378
            # We don't care if it is a ghost, since it can't be seen if it is
1505
1379
            # a ghost
1506
 
            for parent_ids in parent_map.values():
 
1380
            for parent_ids in parent_map.itervalues():
1507
1381
                all_parents.extend(parent_ids)
1508
 
            next_pending = all_seen.intersection(
1509
 
                all_parents).difference(seen_ancestors)
 
1382
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1510
1383
            seen_ancestors.update(next_pending)
1511
1384
            next_pending.difference_update(not_searched_yet)
1512
1385
            pending = next_pending
1549
1422
                    stop_rev_references[parent_id] += 1
1550
1423
            # if only the stopped revisions reference it, the ref count will be
1551
1424
            # 0 after this loop
1552
 
            for parents in self._current_parents.values():
 
1425
            for parents in self._current_parents.itervalues():
1553
1426
                for parent_id in parents:
1554
1427
                    try:
1555
1428
                        stop_rev_references[parent_id] -= 1
1556
1429
                    except KeyError:
1557
1430
                        pass
1558
1431
            stop_parents = set()
1559
 
            for rev_id, refs in stop_rev_references.items():
 
1432
            for rev_id, refs in stop_rev_references.iteritems():
1560
1433
                if refs == 0:
1561
1434
                    stop_parents.add(rev_id)
1562
1435
            self._next_query.difference_update(stop_parents)
1589
1462
            return revs, ghosts
1590
1463
 
1591
1464
 
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
 
1465
class SearchResult(object):
 
1466
    """The result of a breadth first search.
 
1467
 
 
1468
    A SearchResult provides the ability to reconstruct the search or access a
 
1469
    set of the keys the search found.
 
1470
    """
 
1471
 
 
1472
    def __init__(self, start_keys, exclude_keys, key_count, keys):
 
1473
        """Create a SearchResult.
 
1474
 
 
1475
        :param start_keys: The keys the search started at.
 
1476
        :param exclude_keys: The keys the search excludes.
 
1477
        :param key_count: The total number of keys (from start to but not
 
1478
            including exclude).
 
1479
        :param keys: The keys the search found. Note that in future we may get
 
1480
            a SearchResult from a smart server, in which case the keys list is
 
1481
            not necessarily immediately available.
 
1482
        """
 
1483
        self._recipe = ('search', start_keys, exclude_keys, key_count)
 
1484
        self._keys = frozenset(keys)
 
1485
 
 
1486
    def get_recipe(self):
 
1487
        """Return a recipe that can be used to replay this search.
 
1488
 
 
1489
        The recipe allows reconstruction of the same results at a later date
 
1490
        without knowing all the found keys. The essential elements are a list
 
1491
        of keys to start and to stop at. In order to give reproducible
 
1492
        results when ghosts are encountered by a search they are automatically
 
1493
        added to the exclude list (or else ghost filling may alter the
 
1494
        results).
 
1495
 
 
1496
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1497
            revision_count). To recreate the results of this search, create a
 
1498
            breadth first searcher on the same graph starting at start_keys.
 
1499
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1500
            result, call stop_searching_any on any keys from the exclude_keys
 
1501
            set. The revision_count value acts as a trivial cross-check - the
 
1502
            found revisions of the new search should have as many elements as
 
1503
            revision_count. If it does not, then additional revisions have been
 
1504
            ghosted since the search was executed the first time and the second
 
1505
            time.
 
1506
        """
 
1507
        return self._recipe
 
1508
 
 
1509
    def get_keys(self):
 
1510
        """Return the keys found in this search.
 
1511
 
 
1512
        :return: A set of keys.
 
1513
        """
 
1514
        return self._keys
 
1515
 
 
1516
    def is_empty(self):
 
1517
        """Return false if the search lists 1 or more revisions."""
 
1518
        return self._recipe[3] == 0
 
1519
 
 
1520
    def refine(self, seen, referenced):
 
1521
        """Create a new search by refining this search.
 
1522
 
 
1523
        :param seen: Revisions that have been satisfied.
 
1524
        :param referenced: Revision references observed while satisfying some
 
1525
            of this search.
 
1526
        """
 
1527
        start = self._recipe[1]
 
1528
        exclude = self._recipe[2]
 
1529
        count = self._recipe[3]
 
1530
        keys = self.get_keys()
 
1531
        # New heads = referenced + old heads - seen things - exclude
 
1532
        pending_refs = set(referenced)
 
1533
        pending_refs.update(start)
 
1534
        pending_refs.difference_update(seen)
 
1535
        pending_refs.difference_update(exclude)
 
1536
        # New exclude = old exclude + satisfied heads
 
1537
        seen_heads = start.intersection(seen)
 
1538
        exclude.update(seen_heads)
 
1539
        # keys gets seen removed
 
1540
        keys = keys - seen
 
1541
        # length is reduced by len(seen)
 
1542
        count -= len(seen)
 
1543
        return SearchResult(pending_refs, exclude, count, keys)
 
1544
 
 
1545
 
 
1546
class PendingAncestryResult(object):
 
1547
    """A search result that will reconstruct the ancestry for some graph heads.
 
1548
 
 
1549
    Unlike SearchResult, this doesn't hold the complete search result in
 
1550
    memory, it just holds a description of how to generate it.
 
1551
    """
 
1552
 
 
1553
    def __init__(self, heads, repo):
 
1554
        """Constructor.
 
1555
 
 
1556
        :param heads: an iterable of graph heads.
 
1557
        :param repo: a repository to use to generate the ancestry for the given
 
1558
            heads.
 
1559
        """
 
1560
        self.heads = frozenset(heads)
 
1561
        self.repo = repo
 
1562
 
 
1563
    def get_recipe(self):
 
1564
        """Return a recipe that can be used to replay this search.
 
1565
 
 
1566
        The recipe allows reconstruction of the same results at a later date.
 
1567
 
 
1568
        :seealso SearchResult.get_recipe:
 
1569
 
 
1570
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1571
            To recreate this result, create a PendingAncestryResult with the
 
1572
            start_keys_set.
 
1573
        """
 
1574
        return ('proxy-search', self.heads, set(), -1)
 
1575
 
 
1576
    def get_keys(self):
 
1577
        """See SearchResult.get_keys.
 
1578
 
 
1579
        Returns all the keys for the ancestry of the heads, excluding
 
1580
        NULL_REVISION.
 
1581
        """
 
1582
        return self._get_keys(self.repo.get_graph())
 
1583
 
 
1584
    def _get_keys(self, graph):
 
1585
        NULL_REVISION = revision.NULL_REVISION
 
1586
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1587
                if key != NULL_REVISION and parents is not None]
 
1588
        return keys
 
1589
 
 
1590
    def is_empty(self):
 
1591
        """Return false if the search lists 1 or more revisions."""
 
1592
        if revision.NULL_REVISION in self.heads:
 
1593
            return len(self.heads) == 1
 
1594
        else:
 
1595
            return len(self.heads) == 0
 
1596
 
 
1597
    def refine(self, seen, referenced):
 
1598
        """Create a new search by refining this search.
 
1599
 
 
1600
        :param seen: Revisions that have been satisfied.
 
1601
        :param referenced: Revision references observed while satisfying some
 
1602
            of this search.
 
1603
        """
 
1604
        referenced = self.heads.union(referenced)
 
1605
        return PendingAncestryResult(referenced - seen, self.repo)
1605
1606
 
1606
1607
 
1607
1608
def collapse_linear_regions(parent_map):
1644
1645
    # Will not have any nodes removed, even though you do have an
1645
1646
    # 'uninteresting' linear D->B and E->C
1646
1647
    children = {}
1647
 
    for child, parents in parent_map.items():
 
1648
    for child, parents in parent_map.iteritems():
1648
1649
        children.setdefault(child, [])
1649
1650
        for p in parents:
1650
1651
            children.setdefault(p, []).append(child)
1651
1652
 
 
1653
    orig_children = dict(children)
1652
1654
    removed = set()
1653
1655
    result = dict(parent_map)
1654
1656
    for node in parent_map:
1676
1678
    return result
1677
1679
 
1678
1680
 
1679
 
class GraphThunkIdsToKeys(object):
1680
 
    """Forwards calls about 'ids' to be about keys internally."""
1681
 
 
1682
 
    def __init__(self, graph):
1683
 
        self._graph = graph
1684
 
 
1685
 
    def topo_sort(self):
1686
 
        return [r for (r,) in self._graph.topo_sort()]
1687
 
 
1688
 
    def heads(self, ids):
1689
 
        """See Graph.heads()"""
1690
 
        as_keys = [(i,) for i in ids]
1691
 
        head_keys = self._graph.heads(as_keys)
1692
 
        return {h[0] for h in head_keys}
1693
 
 
1694
 
    def merge_sort(self, tip_revision):
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]
 
1681
_counters = [0,0,0,0,0,0,0]
1705
1682
try:
1706
 
    from ._known_graph_pyx import KnownGraph
1707
 
except ImportError as e:
1708
 
    osutils.failed_to_load_extension(e)
1709
 
    from ._known_graph_py import KnownGraph  # noqa: F401
 
1683
    from bzrlib._known_graph_pyx import KnownGraph
 
1684
except ImportError:
 
1685
    from bzrlib._known_graph_py import KnownGraph