/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 bzrlib/graph.py

  • Committer: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

Show diffs side-by-side

added added

removed removed

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