/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: Breezy landing bot
  • Author(s): Colin Watson
  • Date: 2020-11-16 21:47:08 UTC
  • mfrom: (7521.1.1 remove-lp-workaround)
  • Revision ID: breezy.the.bot@gmail.com-20201116214708-jos209mgxi41oy15
Remove breezy.git workaround for bazaar.launchpad.net.

Merged from https://code.launchpad.net/~cjwatson/brz/remove-lp-workaround/+merge/393710

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
 
from bzrlib import (
 
19
from . import (
22
20
    debug,
23
21
    errors,
24
22
    osutils,
115
113
        if not remaining:
116
114
            return found
117
115
        for parents_provider in self._parent_providers:
118
 
            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
119
120
            found.update(new_found)
120
121
            remaining.difference_update(new_found)
121
122
            if not remaining:
134
135
 
135
136
    The cache is enabled by default, but may be disabled and re-enabled.
136
137
    """
 
138
 
137
139
    def __init__(self, parent_provider=None, get_parent_map=None):
138
140
        """Constructor.
139
141
 
358
360
        NULL_REVISION = revision.NULL_REVISION
359
361
        known_revnos[NULL_REVISION] = 0
360
362
 
361
 
        searching_known_tips = list(known_revnos.keys())
 
363
        searching_known_tips = list(known_revnos)
362
364
 
363
365
        unknown_searched = {}
364
366
 
365
367
        while cur_tip not in known_revnos:
366
368
            unknown_searched[cur_tip] = num_steps
367
369
            num_steps += 1
368
 
            to_search = set([cur_tip])
 
370
            to_search = {cur_tip}
369
371
            to_search.update(searching_known_tips)
370
372
            parent_map = self.get_parent_map(to_search)
371
373
            parents = parent_map.get(cur_tip, None)
372
 
            if not parents: # An empty list or None is a ghost
 
374
            if not parents:  # An empty list or None is a ghost
373
375
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
374
376
                                                       cur_tip)
375
377
            cur_tip = parents[0]
401
403
        """
402
404
        # Optimisable by concurrent searching, but a random spread should get
403
405
        # some sort of hit rate.
404
 
        result = {}
405
406
        known_revnos = []
406
407
        ghosts = []
407
408
        for key in keys:
458
459
            return unique_nodes
459
460
 
460
461
        (all_unique_searcher,
461
 
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
462
 
                                    unique_searcher, common_searcher)
 
462
         unique_tip_searchers) = self._make_unique_searchers(
 
463
             unique_nodes, unique_searcher, common_searcher)
463
464
 
464
465
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
465
466
                                  unique_tip_searchers, common_searcher)
481
482
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
482
483
        # we know that unique_revisions aren't in common_revisions, so skip
483
484
        # past them.
484
 
        unique_searcher.next()
 
485
        next(unique_searcher)
485
486
        common_searcher = self._make_breadth_first_searcher(common_revisions)
486
487
 
487
488
        # As long as we are still finding unique nodes, keep searching
497
498
                next_common_nodes.intersection(unique_searcher.seen))
498
499
            if unique_are_common_nodes:
499
500
                ancestors = unique_searcher.find_seen_ancestors(
500
 
                                unique_are_common_nodes)
 
501
                    unique_are_common_nodes)
501
502
                # TODO: This is a bit overboard, we only really care about
502
503
                #       the ancestors of the tips because the rest we
503
504
                #       already know. This is *correct* but causes us to
504
505
                #       search too much ancestry.
505
 
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
506
                ancestors.update(
 
507
                    common_searcher.find_seen_ancestors(ancestors))
506
508
                unique_searcher.stop_searching_any(ancestors)
507
509
                common_searcher.start_searching(ancestors)
508
510
 
517
519
 
518
520
        :return: (all_unique_searcher, unique_tip_searchers)
519
521
        """
520
 
        unique_tips = self._remove_simple_descendants(unique_nodes,
521
 
                        self.get_parent_map(unique_nodes))
 
522
        unique_tips = self._remove_simple_descendants(
 
523
            unique_nodes, self.get_parent_map(unique_nodes))
522
524
 
523
525
        if len(unique_tips) == 1:
524
526
            unique_tip_searchers = []
525
 
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
527
            ancestor_all_unique = unique_searcher.find_seen_ancestors(
 
528
                unique_tips)
526
529
        else:
527
530
            unique_tip_searchers = []
528
531
            for tip in unique_tips:
541
544
                    ancestor_all_unique = set(searcher.seen)
542
545
                else:
543
546
                    ancestor_all_unique = ancestor_all_unique.intersection(
544
 
                                                searcher.seen)
 
547
                        searcher.seen)
545
548
        # Collapse all the common nodes into a single searcher
546
549
        all_unique_searcher = self._make_breadth_first_searcher(
547
 
                                ancestor_all_unique)
 
550
            ancestor_all_unique)
548
551
        if ancestor_all_unique:
549
552
            # We've seen these nodes in all the searchers, so we'll just go to
550
553
            # the next
598
601
        for searcher in unique_tip_searchers:
599
602
            common_to_all_unique_nodes.intersection_update(searcher.seen)
600
603
        common_to_all_unique_nodes.intersection_update(
601
 
                                    all_unique_searcher.seen)
 
604
            all_unique_searcher.seen)
602
605
        # Step all-unique less frequently than the other searchers.
603
606
        # In the common case, we don't need to spider out far here, so
604
607
        # avoid doing extra work.
605
608
        if step_all_unique:
606
 
            tstart = time.clock()
 
609
            tstart = osutils.perf_counter()
607
610
            nodes = all_unique_searcher.step()
608
611
            common_to_all_unique_nodes.update(nodes)
609
612
            if 'graph' in debug.debug_flags:
610
 
                tdelta = time.clock() - tstart
 
613
                tdelta = osutils.perf_counter() - tstart
611
614
                trace.mutter('all_unique_searcher step() took %.3fs'
612
615
                             'for %d nodes (%d total), iteration: %s',
613
616
                             tdelta, len(nodes), len(all_unique_searcher.seen),
645
648
        # TODO: it might be possible to collapse searchers faster when they
646
649
        #       only have *some* search tips in common.
647
650
        next_unique_searchers = []
648
 
        for searchers in unique_search_tips.itervalues():
 
651
        for searchers in unique_search_tips.values():
649
652
            if len(searchers) == 1:
650
653
                # Searching unique tips, go for it
651
654
                next_unique_searchers.append(searchers[0])
685
688
            # These nodes are common ancestors of all unique nodes
686
689
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
687
690
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
688
 
                step_all_unique_counter==0)
 
691
                step_all_unique_counter == 0)
689
692
            step_all_unique_counter = ((step_all_unique_counter + 1)
690
693
                                       % STEP_UNIQUE_SEARCHER_EVERY)
691
694
 
753
756
        common_ancestors = set()
754
757
        searchers = [self._make_breadth_first_searcher([r])
755
758
                     for r in revisions]
756
 
        active_searchers = searchers[:]
757
759
        border_ancestors = set()
758
760
 
759
761
        while True:
828
830
            # NULL_REVISION is only a head if it is the only entry
829
831
            candidate_heads.remove(revision.NULL_REVISION)
830
832
            if not candidate_heads:
831
 
                return set([revision.NULL_REVISION])
 
833
                return {revision.NULL_REVISION}
832
834
        if len(candidate_heads) < 2:
833
835
            return candidate_heads
834
836
        searchers = dict((c, self._make_breadth_first_searcher([c]))
835
 
                          for c in candidate_heads)
 
837
                         for c in candidate_heads)
836
838
        active_searchers = dict(searchers)
837
839
        # skip over the actual candidate for each searcher
838
 
        for searcher in active_searchers.itervalues():
839
 
            searcher.next()
 
840
        for searcher in active_searchers.values():
 
841
            next(searcher)
840
842
        # The common walker finds nodes that are common to two or more of the
841
843
        # input keys, so that we don't access all history when a currently
842
844
        # uncommon search point actually meets up with something behind a
848
850
            ancestors = set()
849
851
            # advance searches
850
852
            try:
851
 
                common_walker.next()
 
853
                next(common_walker)
852
854
            except StopIteration:
853
855
                # No common points being searched at this time.
854
856
                pass
855
 
            for candidate in active_searchers.keys():
 
857
            for candidate in list(active_searchers):
856
858
                try:
857
859
                    searcher = active_searchers[candidate]
858
860
                except KeyError:
861
863
                    # a descendant of another candidate.
862
864
                    continue
863
865
                try:
864
 
                    ancestors.update(searcher.next())
 
866
                    ancestors.update(next(searcher))
865
867
                except StopIteration:
866
868
                    del active_searchers[candidate]
867
869
                    continue
877
879
                if ancestor in common_walker.seen:
878
880
                    # some searcher has encountered our known common nodes:
879
881
                    # just stop it
880
 
                    ancestor_set = set([ancestor])
881
 
                    for searcher in searchers.itervalues():
 
882
                    ancestor_set = {ancestor}
 
883
                    for searcher in searchers.values():
882
884
                        searcher.stop_searching_any(ancestor_set)
883
885
                else:
884
886
                    # or it may have been just reached by all the searchers:
885
 
                    for searcher in searchers.itervalues():
 
887
                    for searcher in searchers.values():
886
888
                        if ancestor not in searcher.seen:
887
889
                            break
888
890
                    else:
890
892
                        # making it be known as a descendant of all candidates,
891
893
                        # so we can stop searching it, and any seen ancestors
892
894
                        new_common.add(ancestor)
893
 
                        for searcher in searchers.itervalues():
 
895
                        for searcher in searchers.values():
894
896
                            seen_ancestors =\
895
897
                                searcher.find_seen_ancestors([ancestor])
896
898
                            searcher.stop_searching_any(seen_ancestors)
928
930
                    break
929
931
                continue
930
932
            parent_ids = self.get_parent_map([next]).get(next, None)
931
 
            if not parent_ids: # Ghost, nothing to search here
 
933
            if not parent_ids:  # Ghost, nothing to search here
932
934
                continue
933
935
            for parent_id in reversed(parent_ids):
934
936
                # TODO: (performance) We see the parent at this point, but we
1013
1015
            processed.update(pending)
1014
1016
            next_map = self.get_parent_map(pending)
1015
1017
            next_pending = set()
1016
 
            for item in next_map.iteritems():
 
1018
            for item in next_map.items():
1017
1019
                yield item
1018
1020
                next_pending.update(p for p in item[1] if p not in processed)
1019
1021
            ghosts = pending.difference(next_map)
1025
1027
        if stop_keys is None:
1026
1028
            stop_keys = ()
1027
1029
        next_key = start_key
 
1030
 
1028
1031
        def get_parents(key):
1029
1032
            try:
1030
1033
                return self._parents_provider.get_parent_map([key])[key]
1047
1050
        An ancestor may sort after a descendant if the relationship is not
1048
1051
        visible in the supplied list of revisions.
1049
1052
        """
1050
 
        from bzrlib import tsort
 
1053
        from breezy import tsort
1051
1054
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1052
1055
        return sorter.iter_topo_order()
1053
1056
 
1058
1061
        smallest number of parent lookups to determine the ancestral
1059
1062
        relationship between N revisions.
1060
1063
        """
1061
 
        return set([candidate_descendant]) == self.heads(
 
1064
        return {candidate_descendant} == self.heads(
1062
1065
            [candidate_ancestor, candidate_descendant])
1063
1066
 
1064
1067
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1068
1071
        lower_bound_revid <= revid <= upper_bound_revid
1069
1072
        """
1070
1073
        return ((upper_bound_revid is None or
1071
 
                    self.is_ancestor(revid, upper_bound_revid)) and
1072
 
               (lower_bound_revid is None or
1073
 
                    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)))
1074
1077
 
1075
1078
    def _search_for_extra_common(self, common, searchers):
1076
1079
        """Make sure that unique nodes are genuinely unique.
1109
1112
        left_searcher = searchers[0]
1110
1113
        right_searcher = searchers[1]
1111
1114
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
1112
 
        if not unique: # No unique nodes, nothing to do
 
1115
        if not unique:  # No unique nodes, nothing to do
1113
1116
            return
1114
1117
        total_unique = len(unique)
1115
1118
        unique = self._remove_simple_descendants(unique,
1116
 
                    self.get_parent_map(unique))
 
1119
                                                 self.get_parent_map(unique))
1117
1120
        simple_unique = len(unique)
1118
1121
 
1119
1122
        unique_searchers = []
1123
1126
            else:
1124
1127
                parent_searcher = right_searcher
1125
1128
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
1126
 
            if not revs_to_search: # XXX: This shouldn't be possible
 
1129
            if not revs_to_search:  # XXX: This shouldn't be possible
1127
1130
                revs_to_search = [revision_id]
1128
1131
            searcher = self._make_breadth_first_searcher(revs_to_search)
1129
1132
            # We don't care about the starting nodes.
1140
1143
                ancestor_all_unique = set(searcher.seen)
1141
1144
            else:
1142
1145
                ancestor_all_unique = ancestor_all_unique.intersection(
1143
 
                                            searcher.seen)
 
1146
                    searcher.seen)
1144
1147
 
1145
 
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1148
        trace.mutter('Started %d unique searchers for %d unique revisions',
1146
1149
                     simple_unique, total_unique)
1147
1150
 
1148
 
        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
1149
1152
            newly_seen_common = set()
1150
1153
            for searcher in common_searchers:
1151
1154
                newly_seen_common.update(searcher.step())
1178
1181
                # If a 'common' node is an ancestor of all unique searchers, we
1179
1182
                # can stop searching it.
1180
1183
                stop_searching_common = ancestor_all_unique.intersection(
1181
 
                                            newly_seen_common)
 
1184
                    newly_seen_common)
1182
1185
                if stop_searching_common:
1183
1186
                    for searcher in common_searchers:
1184
1187
                        searcher.stop_searching_any(stop_searching_common)
1209
1212
                for searcher in unique_searchers:
1210
1213
                    will_search_set = frozenset(searcher._next_query)
1211
1214
                    if will_search_set not in unique_search_sets:
1212
 
                        # This searcher is searching a unique set of nodes, let it
 
1215
                        # This searcher is searching a unique set of nodes, let
 
1216
                        # it
1213
1217
                        unique_search_sets.add(will_search_set)
1214
1218
                        next_unique_searchers.append(searcher)
1215
1219
                unique_searchers = next_unique_searchers
1237
1241
 
1238
1242
        # This is the same as the following loop. I don't know that it is any
1239
1243
        # faster.
1240
 
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
1241
 
        ##     if p_ids is not None and revisions.intersection(p_ids))
1242
 
        ## 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
1243
1247
 
1244
1248
        # Yet Another Way, invert the parent map (which can be cached)
1245
1249
        ## descendants = {}
1246
 
        ## for revision_id, parent_ids in parent_map.iteritems():
1247
 
        ##   for p_id in parent_ids:
 
1250
        # for revision_id, parent_ids in parent_map.iteritems():
 
1251
        # for p_id in parent_ids:
1248
1252
        ##       descendants.setdefault(p_id, []).append(revision_id)
1249
 
        ## for revision in revisions.intersection(descendants):
1250
 
        ##   simple_ancestors.difference_update(descendants[revision])
1251
 
        ## return simple_ancestors
1252
 
        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():
1253
1257
            if parent_ids is None:
1254
1258
                continue
1255
1259
            for parent_id in parent_ids:
1370
1374
        included_keys = self.seen.difference(excludes)
1371
1375
        return self._started_keys, excludes, included_keys
1372
1376
 
1373
 
    def _get_result(self):
1374
 
        """Get a SearchResult for the current state of this searcher.
1375
 
 
1376
 
        :return: A SearchResult for this search so far. The SearchResult is
1377
 
            static - the search can be advanced and the search result will not
1378
 
            be invalidated or altered.
1379
 
        """
1380
 
        from bzrlib.vf_search import SearchResult
1381
 
        (started_keys, excludes, included_keys) = self.get_state()
1382
 
        return SearchResult(started_keys, excludes, len(included_keys),
1383
 
            included_keys)
1384
 
 
1385
1377
    def step(self):
1386
1378
        try:
1387
 
            return self.next()
 
1379
            return next(self)
1388
1380
        except StopIteration:
1389
1381
            return ()
1390
1382
 
1391
 
    def next(self):
 
1383
    def __next__(self):
1392
1384
        """Return the next ancestors of this revision.
1393
1385
 
1394
1386
        Ancestors are returned in the order they are seen in a breadth-first
1414
1406
        self.seen.update(self._next_query)
1415
1407
        return self._next_query
1416
1408
 
 
1409
    next = __next__
 
1410
 
1417
1411
    def next_with_ghosts(self):
1418
1412
        """Return the next found ancestors, with ghosts split out.
1419
1413
 
1466
1460
        seen.update(revisions)
1467
1461
        parent_map = self._parents_provider.get_parent_map(revisions)
1468
1462
        found_revisions.update(parent_map)
1469
 
        for rev_id, parents in parent_map.iteritems():
 
1463
        for rev_id, parents in parent_map.items():
1470
1464
            if parents is None:
1471
1465
                continue
1472
1466
            new_found_parents = [p for p in parents if p not in seen]
1509
1503
            all_parents = []
1510
1504
            # We don't care if it is a ghost, since it can't be seen if it is
1511
1505
            # a ghost
1512
 
            for parent_ids in parent_map.itervalues():
 
1506
            for parent_ids in parent_map.values():
1513
1507
                all_parents.extend(parent_ids)
1514
 
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1508
            next_pending = all_seen.intersection(
 
1509
                all_parents).difference(seen_ancestors)
1515
1510
            seen_ancestors.update(next_pending)
1516
1511
            next_pending.difference_update(not_searched_yet)
1517
1512
            pending = next_pending
1554
1549
                    stop_rev_references[parent_id] += 1
1555
1550
            # if only the stopped revisions reference it, the ref count will be
1556
1551
            # 0 after this loop
1557
 
            for parents in self._current_parents.itervalues():
 
1552
            for parents in self._current_parents.values():
1558
1553
                for parent_id in parents:
1559
1554
                    try:
1560
1555
                        stop_rev_references[parent_id] -= 1
1561
1556
                    except KeyError:
1562
1557
                        pass
1563
1558
            stop_parents = set()
1564
 
            for rev_id, refs in stop_rev_references.iteritems():
 
1559
            for rev_id, refs in stop_rev_references.items():
1565
1560
                if refs == 0:
1566
1561
                    stop_parents.add(rev_id)
1567
1562
            self._next_query.difference_update(stop_parents)
1597
1592
def invert_parent_map(parent_map):
1598
1593
    """Given a map from child => parents, create a map of parent=>children"""
1599
1594
    child_map = {}
1600
 
    for child, parents in parent_map.iteritems():
 
1595
    for child, parents in parent_map.items():
1601
1596
        for p in parents:
1602
1597
            # Any given parent is likely to have only a small handful
1603
1598
            # of children, many will have only one. So we avoid mem overhead of
1649
1644
    # Will not have any nodes removed, even though you do have an
1650
1645
    # 'uninteresting' linear D->B and E->C
1651
1646
    children = {}
1652
 
    for child, parents in parent_map.iteritems():
 
1647
    for child, parents in parent_map.items():
1653
1648
        children.setdefault(child, [])
1654
1649
        for p in parents:
1655
1650
            children.setdefault(p, []).append(child)
1656
1651
 
1657
 
    orig_children = dict(children)
1658
1652
    removed = set()
1659
1653
    result = dict(parent_map)
1660
1654
    for node in parent_map:
1695
1689
        """See Graph.heads()"""
1696
1690
        as_keys = [(i,) for i in ids]
1697
1691
        head_keys = self._graph.heads(as_keys)
1698
 
        return set([h[0] for h in head_keys])
 
1692
        return {h[0] for h in head_keys}
1699
1693
 
1700
1694
    def merge_sort(self, tip_revision):
1701
1695
        nodes = self._graph.merge_sort((tip_revision,))
1707
1701
        self._graph.add_node((revision,), [(p,) for p in parents])
1708
1702
 
1709
1703
 
1710
 
_counters = [0,0,0,0,0,0,0]
 
1704
_counters = [0, 0, 0, 0, 0, 0, 0]
1711
1705
try:
1712
 
    from bzrlib._known_graph_pyx import KnownGraph
1713
 
except ImportError, e:
 
1706
    from ._known_graph_pyx import KnownGraph
 
1707
except ImportError as e:
1714
1708
    osutils.failed_to_load_extension(e)
1715
 
    from bzrlib._known_graph_py import KnownGraph
 
1709
    from ._known_graph_py import KnownGraph  # noqa: F401