/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: 2018-11-16 23:15:15 UTC
  • mfrom: (7180 work)
  • mto: This revision was merged to the branch mainline in revision 7183.
  • Revision ID: jelmer@jelmer.uk-20181116231515-zqd2yn6kj8lfydyp
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
141
141
 
142
142
    The cache is enabled by default, but may be disabled and re-enabled.
143
143
    """
 
144
 
144
145
    def __init__(self, parent_provider=None, get_parent_map=None):
145
146
        """Constructor.
146
147
 
376
377
            to_search.update(searching_known_tips)
377
378
            parent_map = self.get_parent_map(to_search)
378
379
            parents = parent_map.get(cur_tip, None)
379
 
            if not parents: # An empty list or None is a ghost
 
380
            if not parents:  # An empty list or None is a ghost
380
381
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
381
382
                                                       cur_tip)
382
383
            cur_tip = parents[0]
408
409
        """
409
410
        # Optimisable by concurrent searching, but a random spread should get
410
411
        # some sort of hit rate.
411
 
        result = {}
412
412
        known_revnos = []
413
413
        ghosts = []
414
414
        for key in keys:
465
465
            return unique_nodes
466
466
 
467
467
        (all_unique_searcher,
468
 
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
469
 
                                    unique_searcher, common_searcher)
 
468
         unique_tip_searchers) = self._make_unique_searchers(
 
469
             unique_nodes, unique_searcher, common_searcher)
470
470
 
471
471
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
472
472
                                  unique_tip_searchers, common_searcher)
504
504
                next_common_nodes.intersection(unique_searcher.seen))
505
505
            if unique_are_common_nodes:
506
506
                ancestors = unique_searcher.find_seen_ancestors(
507
 
                                unique_are_common_nodes)
 
507
                    unique_are_common_nodes)
508
508
                # TODO: This is a bit overboard, we only really care about
509
509
                #       the ancestors of the tips because the rest we
510
510
                #       already know. This is *correct* but causes us to
511
511
                #       search too much ancestry.
512
 
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
512
                ancestors.update(
 
513
                    common_searcher.find_seen_ancestors(ancestors))
513
514
                unique_searcher.stop_searching_any(ancestors)
514
515
                common_searcher.start_searching(ancestors)
515
516
 
524
525
 
525
526
        :return: (all_unique_searcher, unique_tip_searchers)
526
527
        """
527
 
        unique_tips = self._remove_simple_descendants(unique_nodes,
528
 
                        self.get_parent_map(unique_nodes))
 
528
        unique_tips = self._remove_simple_descendants(
 
529
            unique_nodes, self.get_parent_map(unique_nodes))
529
530
 
530
531
        if len(unique_tips) == 1:
531
532
            unique_tip_searchers = []
532
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
533
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
 
534
                unique_tips)
533
535
        else:
534
536
            unique_tip_searchers = []
535
537
            for tip in unique_tips:
548
550
                    ancestor_all_unique = set(searcher.seen)
549
551
                else:
550
552
                    ancestor_all_unique = ancestor_all_unique.intersection(
551
 
                                                searcher.seen)
 
553
                        searcher.seen)
552
554
        # Collapse all the common nodes into a single searcher
553
555
        all_unique_searcher = self._make_breadth_first_searcher(
554
 
                                ancestor_all_unique)
 
556
            ancestor_all_unique)
555
557
        if ancestor_all_unique:
556
558
            # We've seen these nodes in all the searchers, so we'll just go to
557
559
            # the next
605
607
        for searcher in unique_tip_searchers:
606
608
            common_to_all_unique_nodes.intersection_update(searcher.seen)
607
609
        common_to_all_unique_nodes.intersection_update(
608
 
                                    all_unique_searcher.seen)
 
610
            all_unique_searcher.seen)
609
611
        # Step all-unique less frequently than the other searchers.
610
612
        # In the common case, we don't need to spider out far here, so
611
613
        # avoid doing extra work.
692
694
            # These nodes are common ancestors of all unique nodes
693
695
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
694
696
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
695
 
                step_all_unique_counter==0)
 
697
                step_all_unique_counter == 0)
696
698
            step_all_unique_counter = ((step_all_unique_counter + 1)
697
699
                                       % STEP_UNIQUE_SEARCHER_EVERY)
698
700
 
760
762
        common_ancestors = set()
761
763
        searchers = [self._make_breadth_first_searcher([r])
762
764
                     for r in revisions]
763
 
        active_searchers = searchers[:]
764
765
        border_ancestors = set()
765
766
 
766
767
        while True:
839
840
        if len(candidate_heads) < 2:
840
841
            return candidate_heads
841
842
        searchers = dict((c, self._make_breadth_first_searcher([c]))
842
 
                          for c in candidate_heads)
 
843
                         for c in candidate_heads)
843
844
        active_searchers = dict(searchers)
844
845
        # skip over the actual candidate for each searcher
845
846
        for searcher in viewvalues(active_searchers):
935
936
                    break
936
937
                continue
937
938
            parent_ids = self.get_parent_map([next]).get(next, None)
938
 
            if not parent_ids: # Ghost, nothing to search here
 
939
            if not parent_ids:  # Ghost, nothing to search here
939
940
                continue
940
941
            for parent_id in reversed(parent_ids):
941
942
                # TODO: (performance) We see the parent at this point, but we
1032
1033
        if stop_keys is None:
1033
1034
            stop_keys = ()
1034
1035
        next_key = start_key
 
1036
 
1035
1037
        def get_parents(key):
1036
1038
            try:
1037
1039
                return self._parents_provider.get_parent_map([key])[key]
1075
1077
        lower_bound_revid <= revid <= upper_bound_revid
1076
1078
        """
1077
1079
        return ((upper_bound_revid is None or
1078
 
                    self.is_ancestor(revid, upper_bound_revid)) and
1079
 
               (lower_bound_revid is None or
1080
 
                    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)))
1081
1083
 
1082
1084
    def _search_for_extra_common(self, common, searchers):
1083
1085
        """Make sure that unique nodes are genuinely unique.
1116
1118
        left_searcher = searchers[0]
1117
1119
        right_searcher = searchers[1]
1118
1120
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1119
 
        if not unique: # No unique nodes, nothing to do
 
1121
        if not unique:  # No unique nodes, nothing to do
1120
1122
            return
1121
1123
        total_unique = len(unique)
1122
1124
        unique = self._remove_simple_descendants(unique,
1123
 
                    self.get_parent_map(unique))
 
1125
                                                 self.get_parent_map(unique))
1124
1126
        simple_unique = len(unique)
1125
1127
 
1126
1128
        unique_searchers = []
1130
1132
            else:
1131
1133
                parent_searcher = right_searcher
1132
1134
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1133
 
            if not revs_to_search: # XXX: This shouldn't be possible
 
1135
            if not revs_to_search:  # XXX: This shouldn't be possible
1134
1136
                revs_to_search = [revision_id]
1135
1137
            searcher = self._make_breadth_first_searcher(revs_to_search)
1136
1138
            # We don't care about the starting nodes.
1147
1149
                ancestor_all_unique = set(searcher.seen)
1148
1150
            else:
1149
1151
                ancestor_all_unique = ancestor_all_unique.intersection(
1150
 
                                            searcher.seen)
 
1152
                    searcher.seen)
1151
1153
 
1152
1154
        trace.mutter('Started %d unique searchers for %d unique revisions',
1153
1155
                     simple_unique, total_unique)
1154
1156
 
1155
 
        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
1156
1158
            newly_seen_common = set()
1157
1159
            for searcher in common_searchers:
1158
1160
                newly_seen_common.update(searcher.step())
1185
1187
                # If a 'common' node is an ancestor of all unique searchers, we
1186
1188
                # can stop searching it.
1187
1189
                stop_searching_common = ancestor_all_unique.intersection(
1188
 
                                            newly_seen_common)
 
1190
                    newly_seen_common)
1189
1191
                if stop_searching_common:
1190
1192
                    for searcher in common_searchers:
1191
1193
                        searcher.stop_searching_any(stop_searching_common)
1216
1218
                for searcher in unique_searchers:
1217
1219
                    will_search_set = frozenset(searcher._next_query)
1218
1220
                    if will_search_set not in unique_search_sets:
1219
 
                        # This searcher is searching a unique set of nodes, let it
 
1221
                        # This searcher is searching a unique set of nodes, let
 
1222
                        # it
1220
1223
                        unique_search_sets.add(will_search_set)
1221
1224
                        next_unique_searchers.append(searcher)
1222
1225
                unique_searchers = next_unique_searchers
1244
1247
 
1245
1248
        # This is the same as the following loop. I don't know that it is any
1246
1249
        # faster.
1247
 
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1248
 
        ##     if p_ids is not None and revisions.intersection(p_ids))
1249
 
        ## 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
1250
1253
 
1251
1254
        # Yet Another Way, invert the parent map (which can be cached)
1252
1255
        ## descendants = {}
1253
 
        ## for revision_id, parent_ids in parent_map.iteritems():
1254
 
        ##   for p_id in parent_ids:
 
1256
        # for revision_id, parent_ids in parent_map.iteritems():
 
1257
        # for p_id in parent_ids:
1255
1258
        ##       descendants.setdefault(p_id, []).append(revision_id)
1256
 
        ## for revision in revisions.intersection(descendants):
1257
 
        ##   simple_ancestors.difference_update(descendants[revision])
1258
 
        ## return simple_ancestors
 
1259
        # for revision in revisions.intersection(descendants):
 
1260
        # simple_ancestors.difference_update(descendants[revision])
 
1261
        # return simple_ancestors
1259
1262
        for revision, parent_ids in viewitems(parent_map):
1260
1263
            if parent_ids is None:
1261
1264
                continue
1508
1511
            # a ghost
1509
1512
            for parent_ids in viewvalues(parent_map):
1510
1513
                all_parents.extend(parent_ids)
1511
 
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1514
            next_pending = all_seen.intersection(
 
1515
                all_parents).difference(seen_ancestors)
1512
1516
            seen_ancestors.update(next_pending)
1513
1517
            next_pending.difference_update(not_searched_yet)
1514
1518
            pending = next_pending
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:
1709
1712
    from ._known_graph_pyx import KnownGraph
1710
1713
except ImportError as e:
1711
1714
    osutils.failed_to_load_extension(e)
1712
 
    from ._known_graph_py import KnownGraph
 
1715
    from ._known_graph_py import KnownGraph  # noqa: F401