/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: 2017-06-08 23:30:31 UTC
  • mto: This revision was merged to the branch mainline in revision 6690.
  • Revision ID: jelmer@jelmer.uk-20170608233031-3qavls2o7a1pqllj
Update imports.

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