/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-05-06 11:48:54 UTC
  • mto: This revision was merged to the branch mainline in revision 6960.
  • Revision ID: jelmer@jelmer.uk-20180506114854-h4qd9ojaqy8wxjsd
Move .mailmap to root.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/graph.py
119
119
        if not remaining:
120
120
            return found
121
121
        for parents_provider in self._parent_providers:
122
 
            try:
123
 
                new_found = parents_provider.get_parent_map(remaining)
124
 
            except errors.UnsupportedOperation:
125
 
                continue
 
122
            new_found = parents_provider.get_parent_map(remaining)
126
123
            found.update(new_found)
127
124
            remaining.difference_update(new_found)
128
125
            if not remaining:
141
138
 
142
139
    The cache is enabled by default, but may be disabled and re-enabled.
143
140
    """
144
 
 
145
141
    def __init__(self, parent_provider=None, get_parent_map=None):
146
142
        """Constructor.
147
143
 
377
373
            to_search.update(searching_known_tips)
378
374
            parent_map = self.get_parent_map(to_search)
379
375
            parents = parent_map.get(cur_tip, None)
380
 
            if not parents:  # An empty list or None is a ghost
 
376
            if not parents: # An empty list or None is a ghost
381
377
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
382
378
                                                       cur_tip)
383
379
            cur_tip = parents[0]
409
405
        """
410
406
        # Optimisable by concurrent searching, but a random spread should get
411
407
        # some sort of hit rate.
 
408
        result = {}
412
409
        known_revnos = []
413
410
        ghosts = []
414
411
        for key in keys:
465
462
            return unique_nodes
466
463
 
467
464
        (all_unique_searcher,
468
 
         unique_tip_searchers) = self._make_unique_searchers(
469
 
             unique_nodes, unique_searcher, common_searcher)
 
465
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
466
                                    unique_searcher, common_searcher)
470
467
 
471
468
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
472
469
                                  unique_tip_searchers, common_searcher)
504
501
                next_common_nodes.intersection(unique_searcher.seen))
505
502
            if unique_are_common_nodes:
506
503
                ancestors = unique_searcher.find_seen_ancestors(
507
 
                    unique_are_common_nodes)
 
504
                                unique_are_common_nodes)
508
505
                # TODO: This is a bit overboard, we only really care about
509
506
                #       the ancestors of the tips because the rest we
510
507
                #       already know. This is *correct* but causes us to
511
508
                #       search too much ancestry.
512
 
                ancestors.update(
513
 
                    common_searcher.find_seen_ancestors(ancestors))
 
509
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
514
510
                unique_searcher.stop_searching_any(ancestors)
515
511
                common_searcher.start_searching(ancestors)
516
512
 
525
521
 
526
522
        :return: (all_unique_searcher, unique_tip_searchers)
527
523
        """
528
 
        unique_tips = self._remove_simple_descendants(
529
 
            unique_nodes, self.get_parent_map(unique_nodes))
 
524
        unique_tips = self._remove_simple_descendants(unique_nodes,
 
525
                        self.get_parent_map(unique_nodes))
530
526
 
531
527
        if len(unique_tips) == 1:
532
528
            unique_tip_searchers = []
533
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
534
 
                unique_tips)
 
529
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
535
530
        else:
536
531
            unique_tip_searchers = []
537
532
            for tip in unique_tips:
550
545
                    ancestor_all_unique = set(searcher.seen)
551
546
                else:
552
547
                    ancestor_all_unique = ancestor_all_unique.intersection(
553
 
                        searcher.seen)
 
548
                                                searcher.seen)
554
549
        # Collapse all the common nodes into a single searcher
555
550
        all_unique_searcher = self._make_breadth_first_searcher(
556
 
            ancestor_all_unique)
 
551
                                ancestor_all_unique)
557
552
        if ancestor_all_unique:
558
553
            # We've seen these nodes in all the searchers, so we'll just go to
559
554
            # the next
607
602
        for searcher in unique_tip_searchers:
608
603
            common_to_all_unique_nodes.intersection_update(searcher.seen)
609
604
        common_to_all_unique_nodes.intersection_update(
610
 
            all_unique_searcher.seen)
 
605
                                    all_unique_searcher.seen)
611
606
        # Step all-unique less frequently than the other searchers.
612
607
        # In the common case, we don't need to spider out far here, so
613
608
        # avoid doing extra work.
614
609
        if step_all_unique:
615
 
            tstart = osutils.perf_counter()
 
610
            tstart = time.clock()
616
611
            nodes = all_unique_searcher.step()
617
612
            common_to_all_unique_nodes.update(nodes)
618
613
            if 'graph' in debug.debug_flags:
619
 
                tdelta = osutils.perf_counter() - tstart
 
614
                tdelta = time.clock() - tstart
620
615
                trace.mutter('all_unique_searcher step() took %.3fs'
621
616
                             'for %d nodes (%d total), iteration: %s',
622
617
                             tdelta, len(nodes), len(all_unique_searcher.seen),
694
689
            # These nodes are common ancestors of all unique nodes
695
690
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
696
691
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
697
 
                step_all_unique_counter == 0)
 
692
                step_all_unique_counter==0)
698
693
            step_all_unique_counter = ((step_all_unique_counter + 1)
699
694
                                       % STEP_UNIQUE_SEARCHER_EVERY)
700
695
 
762
757
        common_ancestors = set()
763
758
        searchers = [self._make_breadth_first_searcher([r])
764
759
                     for r in revisions]
 
760
        active_searchers = searchers[:]
765
761
        border_ancestors = set()
766
762
 
767
763
        while True:
840
836
        if len(candidate_heads) < 2:
841
837
            return candidate_heads
842
838
        searchers = dict((c, self._make_breadth_first_searcher([c]))
843
 
                         for c in candidate_heads)
 
839
                          for c in candidate_heads)
844
840
        active_searchers = dict(searchers)
845
841
        # skip over the actual candidate for each searcher
846
842
        for searcher in viewvalues(active_searchers):
936
932
                    break
937
933
                continue
938
934
            parent_ids = self.get_parent_map([next]).get(next, None)
939
 
            if not parent_ids:  # Ghost, nothing to search here
 
935
            if not parent_ids: # Ghost, nothing to search here
940
936
                continue
941
937
            for parent_id in reversed(parent_ids):
942
938
                # TODO: (performance) We see the parent at this point, but we
1033
1029
        if stop_keys is None:
1034
1030
            stop_keys = ()
1035
1031
        next_key = start_key
1036
 
 
1037
1032
        def get_parents(key):
1038
1033
            try:
1039
1034
                return self._parents_provider.get_parent_map([key])[key]
1077
1072
        lower_bound_revid <= revid <= upper_bound_revid
1078
1073
        """
1079
1074
        return ((upper_bound_revid is None or
1080
 
                 self.is_ancestor(revid, upper_bound_revid)) and
1081
 
                (lower_bound_revid is None or
1082
 
                 self.is_ancestor(lower_bound_revid, revid)))
 
1075
                    self.is_ancestor(revid, upper_bound_revid)) and
 
1076
               (lower_bound_revid is None or
 
1077
                    self.is_ancestor(lower_bound_revid, revid)))
1083
1078
 
1084
1079
    def _search_for_extra_common(self, common, searchers):
1085
1080
        """Make sure that unique nodes are genuinely unique.
1118
1113
        left_searcher = searchers[0]
1119
1114
        right_searcher = searchers[1]
1120
1115
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1121
 
        if not unique:  # No unique nodes, nothing to do
 
1116
        if not unique: # No unique nodes, nothing to do
1122
1117
            return
1123
1118
        total_unique = len(unique)
1124
1119
        unique = self._remove_simple_descendants(unique,
1125
 
                                                 self.get_parent_map(unique))
 
1120
                    self.get_parent_map(unique))
1126
1121
        simple_unique = len(unique)
1127
1122
 
1128
1123
        unique_searchers = []
1132
1127
            else:
1133
1128
                parent_searcher = right_searcher
1134
1129
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1135
 
            if not revs_to_search:  # XXX: This shouldn't be possible
 
1130
            if not revs_to_search: # XXX: This shouldn't be possible
1136
1131
                revs_to_search = [revision_id]
1137
1132
            searcher = self._make_breadth_first_searcher(revs_to_search)
1138
1133
            # We don't care about the starting nodes.
1149
1144
                ancestor_all_unique = set(searcher.seen)
1150
1145
            else:
1151
1146
                ancestor_all_unique = ancestor_all_unique.intersection(
1152
 
                    searcher.seen)
 
1147
                                            searcher.seen)
1153
1148
 
1154
 
        trace.mutter('Started %d unique searchers for %d unique revisions',
 
1149
        trace.mutter('Started %s unique searchers for %s unique revisions',
1155
1150
                     simple_unique, total_unique)
1156
1151
 
1157
 
        while True:  # If we have no more nodes we have nothing to do
 
1152
        while True: # If we have no more nodes we have nothing to do
1158
1153
            newly_seen_common = set()
1159
1154
            for searcher in common_searchers:
1160
1155
                newly_seen_common.update(searcher.step())
1187
1182
                # If a 'common' node is an ancestor of all unique searchers, we
1188
1183
                # can stop searching it.
1189
1184
                stop_searching_common = ancestor_all_unique.intersection(
1190
 
                    newly_seen_common)
 
1185
                                            newly_seen_common)
1191
1186
                if stop_searching_common:
1192
1187
                    for searcher in common_searchers:
1193
1188
                        searcher.stop_searching_any(stop_searching_common)
1218
1213
                for searcher in unique_searchers:
1219
1214
                    will_search_set = frozenset(searcher._next_query)
1220
1215
                    if will_search_set not in unique_search_sets:
1221
 
                        # This searcher is searching a unique set of nodes, let
1222
 
                        # it
 
1216
                        # This searcher is searching a unique set of nodes, let it
1223
1217
                        unique_search_sets.add(will_search_set)
1224
1218
                        next_unique_searchers.append(searcher)
1225
1219
                unique_searchers = next_unique_searchers
1247
1241
 
1248
1242
        # This is the same as the following loop. I don't know that it is any
1249
1243
        # faster.
1250
 
        # simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1251
 
        # if p_ids is not None and revisions.intersection(p_ids))
1252
 
        # return simple_ancestors
 
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
1253
1247
 
1254
1248
        # Yet Another Way, invert the parent map (which can be cached)
1255
1249
        ## descendants = {}
1256
 
        # for revision_id, parent_ids in parent_map.iteritems():
1257
 
        # for p_id in parent_ids:
 
1250
        ## for revision_id, parent_ids in parent_map.iteritems():
 
1251
        ##   for p_id in parent_ids:
1258
1252
        ##       descendants.setdefault(p_id, []).append(revision_id)
1259
 
        # for revision in revisions.intersection(descendants):
1260
 
        # simple_ancestors.difference_update(descendants[revision])
1261
 
        # return simple_ancestors
 
1253
        ## for revision in revisions.intersection(descendants):
 
1254
        ##   simple_ancestors.difference_update(descendants[revision])
 
1255
        ## return simple_ancestors
1262
1256
        for revision, parent_ids in viewitems(parent_map):
1263
1257
            if parent_ids is None:
1264
1258
                continue
1511
1505
            # a ghost
1512
1506
            for parent_ids in viewvalues(parent_map):
1513
1507
                all_parents.extend(parent_ids)
1514
 
            next_pending = all_seen.intersection(
1515
 
                all_parents).difference(seen_ancestors)
 
1508
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1516
1509
            seen_ancestors.update(next_pending)
1517
1510
            next_pending.difference_update(not_searched_yet)
1518
1511
            pending = next_pending
1655
1648
        for p in parents:
1656
1649
            children.setdefault(p, []).append(child)
1657
1650
 
 
1651
    orig_children = dict(children)
1658
1652
    removed = set()
1659
1653
    result = dict(parent_map)
1660
1654
    for node in parent_map:
1712
1706
    from ._known_graph_pyx import KnownGraph
1713
1707
except ImportError as e:
1714
1708
    osutils.failed_to_load_extension(e)
1715
 
    from ._known_graph_py import KnownGraph  # noqa: F401
 
1709
    from ._known_graph_py import KnownGraph