/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2020-03-22 01:35:14 UTC
  • mfrom: (7490.7.6 work)
  • mto: This revision was merged to the branch mainline in revision 7499.
  • Revision ID: jelmer@jelmer.uk-20200322013514-7vw1ntwho04rcuj3
merge lp:brz/3.1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
from __future__ import absolute_import
18
 
 
19
17
import time
20
18
 
21
19
from . import (
25
23
    revision,
26
24
    trace,
27
25
    )
28
 
from .sixish import (
29
 
    viewitems,
30
 
    viewvalues,
31
 
    )
32
26
 
33
27
STEP_UNIQUE_SEARCHER_EVERY = 5
34
28
 
119
113
        if not remaining:
120
114
            return found
121
115
        for parents_provider in self._parent_providers:
122
 
            new_found = parents_provider.get_parent_map(remaining)
 
116
            try:
 
117
                new_found = parents_provider.get_parent_map(remaining)
 
118
            except errors.UnsupportedOperation:
 
119
                continue
123
120
            found.update(new_found)
124
121
            remaining.difference_update(new_found)
125
122
            if not remaining:
138
135
 
139
136
    The cache is enabled by default, but may be disabled and re-enabled.
140
137
    """
 
138
 
141
139
    def __init__(self, parent_provider=None, get_parent_map=None):
142
140
        """Constructor.
143
141
 
339
337
        """
340
338
        parent_map = self._parents_provider.get_parent_map(keys)
341
339
        parent_child = {}
342
 
        for child, parents in sorted(viewitems(parent_map)):
 
340
        for child, parents in sorted(parent_map.items()):
343
341
            for parent in parents:
344
342
                parent_child.setdefault(parent, []).append(child)
345
343
        return parent_child
373
371
            to_search.update(searching_known_tips)
374
372
            parent_map = self.get_parent_map(to_search)
375
373
            parents = parent_map.get(cur_tip, None)
376
 
            if not parents: # An empty list or None is a ghost
 
374
            if not parents:  # An empty list or None is a ghost
377
375
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
378
376
                                                       cur_tip)
379
377
            cur_tip = parents[0]
405
403
        """
406
404
        # Optimisable by concurrent searching, but a random spread should get
407
405
        # some sort of hit rate.
408
 
        result = {}
409
406
        known_revnos = []
410
407
        ghosts = []
411
408
        for key in keys:
462
459
            return unique_nodes
463
460
 
464
461
        (all_unique_searcher,
465
 
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
466
 
                                    unique_searcher, common_searcher)
 
462
         unique_tip_searchers) = self._make_unique_searchers(
 
463
             unique_nodes, unique_searcher, common_searcher)
467
464
 
468
465
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
469
466
                                  unique_tip_searchers, common_searcher)
501
498
                next_common_nodes.intersection(unique_searcher.seen))
502
499
            if unique_are_common_nodes:
503
500
                ancestors = unique_searcher.find_seen_ancestors(
504
 
                                unique_are_common_nodes)
 
501
                    unique_are_common_nodes)
505
502
                # TODO: This is a bit overboard, we only really care about
506
503
                #       the ancestors of the tips because the rest we
507
504
                #       already know. This is *correct* but causes us to
508
505
                #       search too much ancestry.
509
 
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
506
                ancestors.update(
 
507
                    common_searcher.find_seen_ancestors(ancestors))
510
508
                unique_searcher.stop_searching_any(ancestors)
511
509
                common_searcher.start_searching(ancestors)
512
510
 
521
519
 
522
520
        :return: (all_unique_searcher, unique_tip_searchers)
523
521
        """
524
 
        unique_tips = self._remove_simple_descendants(unique_nodes,
525
 
                        self.get_parent_map(unique_nodes))
 
522
        unique_tips = self._remove_simple_descendants(
 
523
            unique_nodes, self.get_parent_map(unique_nodes))
526
524
 
527
525
        if len(unique_tips) == 1:
528
526
            unique_tip_searchers = []
529
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
527
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
 
528
                unique_tips)
530
529
        else:
531
530
            unique_tip_searchers = []
532
531
            for tip in unique_tips:
545
544
                    ancestor_all_unique = set(searcher.seen)
546
545
                else:
547
546
                    ancestor_all_unique = ancestor_all_unique.intersection(
548
 
                                                searcher.seen)
 
547
                        searcher.seen)
549
548
        # Collapse all the common nodes into a single searcher
550
549
        all_unique_searcher = self._make_breadth_first_searcher(
551
 
                                ancestor_all_unique)
 
550
            ancestor_all_unique)
552
551
        if ancestor_all_unique:
553
552
            # We've seen these nodes in all the searchers, so we'll just go to
554
553
            # the next
602
601
        for searcher in unique_tip_searchers:
603
602
            common_to_all_unique_nodes.intersection_update(searcher.seen)
604
603
        common_to_all_unique_nodes.intersection_update(
605
 
                                    all_unique_searcher.seen)
 
604
            all_unique_searcher.seen)
606
605
        # Step all-unique less frequently than the other searchers.
607
606
        # In the common case, we don't need to spider out far here, so
608
607
        # avoid doing extra work.
609
608
        if step_all_unique:
610
 
            tstart = time.clock()
 
609
            tstart = osutils.perf_counter()
611
610
            nodes = all_unique_searcher.step()
612
611
            common_to_all_unique_nodes.update(nodes)
613
612
            if 'graph' in debug.debug_flags:
614
 
                tdelta = time.clock() - tstart
 
613
                tdelta = osutils.perf_counter() - tstart
615
614
                trace.mutter('all_unique_searcher step() took %.3fs'
616
615
                             'for %d nodes (%d total), iteration: %s',
617
616
                             tdelta, len(nodes), len(all_unique_searcher.seen),
649
648
        # TODO: it might be possible to collapse searchers faster when they
650
649
        #       only have *some* search tips in common.
651
650
        next_unique_searchers = []
652
 
        for searchers in viewvalues(unique_search_tips):
 
651
        for searchers in unique_search_tips.values():
653
652
            if len(searchers) == 1:
654
653
                # Searching unique tips, go for it
655
654
                next_unique_searchers.append(searchers[0])
689
688
            # These nodes are common ancestors of all unique nodes
690
689
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
691
690
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
692
 
                step_all_unique_counter==0)
 
691
                step_all_unique_counter == 0)
693
692
            step_all_unique_counter = ((step_all_unique_counter + 1)
694
693
                                       % STEP_UNIQUE_SEARCHER_EVERY)
695
694
 
757
756
        common_ancestors = set()
758
757
        searchers = [self._make_breadth_first_searcher([r])
759
758
                     for r in revisions]
760
 
        active_searchers = searchers[:]
761
759
        border_ancestors = set()
762
760
 
763
761
        while True:
836
834
        if len(candidate_heads) < 2:
837
835
            return candidate_heads
838
836
        searchers = dict((c, self._make_breadth_first_searcher([c]))
839
 
                          for c in candidate_heads)
 
837
                         for c in candidate_heads)
840
838
        active_searchers = dict(searchers)
841
839
        # skip over the actual candidate for each searcher
842
 
        for searcher in viewvalues(active_searchers):
 
840
        for searcher in active_searchers.values():
843
841
            next(searcher)
844
842
        # The common walker finds nodes that are common to two or more of the
845
843
        # input keys, so that we don't access all history when a currently
882
880
                    # some searcher has encountered our known common nodes:
883
881
                    # just stop it
884
882
                    ancestor_set = {ancestor}
885
 
                    for searcher in viewvalues(searchers):
 
883
                    for searcher in searchers.values():
886
884
                        searcher.stop_searching_any(ancestor_set)
887
885
                else:
888
886
                    # or it may have been just reached by all the searchers:
889
 
                    for searcher in viewvalues(searchers):
 
887
                    for searcher in searchers.values():
890
888
                        if ancestor not in searcher.seen:
891
889
                            break
892
890
                    else:
894
892
                        # making it be known as a descendant of all candidates,
895
893
                        # so we can stop searching it, and any seen ancestors
896
894
                        new_common.add(ancestor)
897
 
                        for searcher in viewvalues(searchers):
 
895
                        for searcher in searchers.values():
898
896
                            seen_ancestors =\
899
897
                                searcher.find_seen_ancestors([ancestor])
900
898
                            searcher.stop_searching_any(seen_ancestors)
932
930
                    break
933
931
                continue
934
932
            parent_ids = self.get_parent_map([next]).get(next, None)
935
 
            if not parent_ids: # Ghost, nothing to search here
 
933
            if not parent_ids:  # Ghost, nothing to search here
936
934
                continue
937
935
            for parent_id in reversed(parent_ids):
938
936
                # TODO: (performance) We see the parent at this point, but we
1017
1015
            processed.update(pending)
1018
1016
            next_map = self.get_parent_map(pending)
1019
1017
            next_pending = set()
1020
 
            for item in viewitems(next_map):
 
1018
            for item in next_map.items():
1021
1019
                yield item
1022
1020
                next_pending.update(p for p in item[1] if p not in processed)
1023
1021
            ghosts = pending.difference(next_map)
1029
1027
        if stop_keys is None:
1030
1028
            stop_keys = ()
1031
1029
        next_key = start_key
 
1030
 
1032
1031
        def get_parents(key):
1033
1032
            try:
1034
1033
                return self._parents_provider.get_parent_map([key])[key]
1072
1071
        lower_bound_revid <= revid <= upper_bound_revid
1073
1072
        """
1074
1073
        return ((upper_bound_revid is None or
1075
 
                    self.is_ancestor(revid, upper_bound_revid)) and
1076
 
               (lower_bound_revid is None or
1077
 
                    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)))
1078
1077
 
1079
1078
    def _search_for_extra_common(self, common, searchers):
1080
1079
        """Make sure that unique nodes are genuinely unique.
1113
1112
        left_searcher = searchers[0]
1114
1113
        right_searcher = searchers[1]
1115
1114
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1116
 
        if not unique: # No unique nodes, nothing to do
 
1115
        if not unique:  # No unique nodes, nothing to do
1117
1116
            return
1118
1117
        total_unique = len(unique)
1119
1118
        unique = self._remove_simple_descendants(unique,
1120
 
                    self.get_parent_map(unique))
 
1119
                                                 self.get_parent_map(unique))
1121
1120
        simple_unique = len(unique)
1122
1121
 
1123
1122
        unique_searchers = []
1127
1126
            else:
1128
1127
                parent_searcher = right_searcher
1129
1128
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1130
 
            if not revs_to_search: # XXX: This shouldn't be possible
 
1129
            if not revs_to_search:  # XXX: This shouldn't be possible
1131
1130
                revs_to_search = [revision_id]
1132
1131
            searcher = self._make_breadth_first_searcher(revs_to_search)
1133
1132
            # We don't care about the starting nodes.
1144
1143
                ancestor_all_unique = set(searcher.seen)
1145
1144
            else:
1146
1145
                ancestor_all_unique = ancestor_all_unique.intersection(
1147
 
                                            searcher.seen)
 
1146
                    searcher.seen)
1148
1147
 
1149
 
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1148
        trace.mutter('Started %d unique searchers for %d unique revisions',
1150
1149
                     simple_unique, total_unique)
1151
1150
 
1152
 
        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
1153
1152
            newly_seen_common = set()
1154
1153
            for searcher in common_searchers:
1155
1154
                newly_seen_common.update(searcher.step())
1182
1181
                # If a 'common' node is an ancestor of all unique searchers, we
1183
1182
                # can stop searching it.
1184
1183
                stop_searching_common = ancestor_all_unique.intersection(
1185
 
                                            newly_seen_common)
 
1184
                    newly_seen_common)
1186
1185
                if stop_searching_common:
1187
1186
                    for searcher in common_searchers:
1188
1187
                        searcher.stop_searching_any(stop_searching_common)
1213
1212
                for searcher in unique_searchers:
1214
1213
                    will_search_set = frozenset(searcher._next_query)
1215
1214
                    if will_search_set not in unique_search_sets:
1216
 
                        # This searcher is searching a unique set of nodes, let it
 
1215
                        # This searcher is searching a unique set of nodes, let
 
1216
                        # it
1217
1217
                        unique_search_sets.add(will_search_set)
1218
1218
                        next_unique_searchers.append(searcher)
1219
1219
                unique_searchers = next_unique_searchers
1241
1241
 
1242
1242
        # This is the same as the following loop. I don't know that it is any
1243
1243
        # 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
 
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
1247
1247
 
1248
1248
        # Yet Another Way, invert the parent map (which can be cached)
1249
1249
        ## descendants = {}
1250
 
        ## for revision_id, parent_ids in parent_map.iteritems():
1251
 
        ##   for p_id in parent_ids:
 
1250
        # for revision_id, parent_ids in parent_map.iteritems():
 
1251
        # for p_id in parent_ids:
1252
1252
        ##       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 viewitems(parent_map):
 
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():
1257
1257
            if parent_ids is None:
1258
1258
                continue
1259
1259
            for parent_id in parent_ids:
1460
1460
        seen.update(revisions)
1461
1461
        parent_map = self._parents_provider.get_parent_map(revisions)
1462
1462
        found_revisions.update(parent_map)
1463
 
        for rev_id, parents in viewitems(parent_map):
 
1463
        for rev_id, parents in parent_map.items():
1464
1464
            if parents is None:
1465
1465
                continue
1466
1466
            new_found_parents = [p for p in parents if p not in seen]
1503
1503
            all_parents = []
1504
1504
            # We don't care if it is a ghost, since it can't be seen if it is
1505
1505
            # a ghost
1506
 
            for parent_ids in viewvalues(parent_map):
 
1506
            for parent_ids in parent_map.values():
1507
1507
                all_parents.extend(parent_ids)
1508
 
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1508
            next_pending = all_seen.intersection(
 
1509
                all_parents).difference(seen_ancestors)
1509
1510
            seen_ancestors.update(next_pending)
1510
1511
            next_pending.difference_update(not_searched_yet)
1511
1512
            pending = next_pending
1548
1549
                    stop_rev_references[parent_id] += 1
1549
1550
            # if only the stopped revisions reference it, the ref count will be
1550
1551
            # 0 after this loop
1551
 
            for parents in viewvalues(self._current_parents):
 
1552
            for parents in self._current_parents.values():
1552
1553
                for parent_id in parents:
1553
1554
                    try:
1554
1555
                        stop_rev_references[parent_id] -= 1
1555
1556
                    except KeyError:
1556
1557
                        pass
1557
1558
            stop_parents = set()
1558
 
            for rev_id, refs in viewitems(stop_rev_references):
 
1559
            for rev_id, refs in stop_rev_references.items():
1559
1560
                if refs == 0:
1560
1561
                    stop_parents.add(rev_id)
1561
1562
            self._next_query.difference_update(stop_parents)
1591
1592
def invert_parent_map(parent_map):
1592
1593
    """Given a map from child => parents, create a map of parent=>children"""
1593
1594
    child_map = {}
1594
 
    for child, parents in viewitems(parent_map):
 
1595
    for child, parents in parent_map.items():
1595
1596
        for p in parents:
1596
1597
            # Any given parent is likely to have only a small handful
1597
1598
            # of children, many will have only one. So we avoid mem overhead of
1643
1644
    # Will not have any nodes removed, even though you do have an
1644
1645
    # 'uninteresting' linear D->B and E->C
1645
1646
    children = {}
1646
 
    for child, parents in viewitems(parent_map):
 
1647
    for child, parents in parent_map.items():
1647
1648
        children.setdefault(child, [])
1648
1649
        for p in parents:
1649
1650
            children.setdefault(p, []).append(child)
1650
1651
 
1651
 
    orig_children = dict(children)
1652
1652
    removed = set()
1653
1653
    result = dict(parent_map)
1654
1654
    for node in parent_map:
1706
1706
    from ._known_graph_pyx import KnownGraph
1707
1707
except ImportError as e:
1708
1708
    osutils.failed_to_load_extension(e)
1709
 
    from ._known_graph_py import KnownGraph
 
1709
    from ._known_graph_py import KnownGraph  # noqa: F401