/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): Jelmer Vernooij
  • Date: 2018-11-16 18:26:22 UTC
  • mfrom: (7167.1.4 run-flake8)
  • Revision ID: breezy.the.bot@gmail.com-20181116182622-qw3gan3hz78a2imw
Add a flake8 test.

Merged from https://code.launchpad.net/~jelmer/brz/run-flake8/+merge/358902

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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 bzrlib import (
 
21
from . import (
20
22
    debug,
21
23
    errors,
22
24
    osutils,
23
25
    revision,
24
26
    trace,
25
27
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
 
28
from .sixish import (
 
29
    viewitems,
 
30
    viewvalues,
 
31
    )
27
32
 
28
33
STEP_UNIQUE_SEARCHER_EVERY = 5
29
34
 
59
64
    def __repr__(self):
60
65
        return 'DictParentsProvider(%r)' % self.ancestry
61
66
 
 
67
    # Note: DictParentsProvider does not implement get_cached_parent_map
 
68
    #       Arguably, the data is clearly cached in memory. However, this class
 
69
    #       is mostly used for testing, and it keeps the tests clean to not
 
70
    #       change it.
 
71
 
62
72
    def get_parent_map(self, keys):
63
73
        """See StackedParentsProvider.get_parent_map"""
64
74
        ancestry = self.ancestry
65
 
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
 
75
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
66
76
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
77
 
71
78
class StackedParentsProvider(object):
72
79
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
 
80
 
74
81
    The providers are queries in the order of the provided parent_providers.
75
82
    """
76
 
    
 
83
 
77
84
    def __init__(self, parent_providers):
78
85
        self._parent_providers = parent_providers
79
86
 
95
102
        """
96
103
        found = {}
97
104
        remaining = set(keys)
98
 
        for parents_provider in self._parent_providers:
99
 
            new_found = parents_provider.get_parent_map(remaining)
 
105
        # This adds getattr() overhead to each get_parent_map call. However,
 
106
        # this is StackedParentsProvider, which means we're dealing with I/O
 
107
        # (either local indexes, or remote RPCs), so CPU overhead should be
 
108
        # minimal.
 
109
        for parents_provider in self._parent_providers:
 
110
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
 
111
                                 None)
 
112
            if get_cached is None:
 
113
                continue
 
114
            new_found = get_cached(remaining)
 
115
            found.update(new_found)
 
116
            remaining.difference_update(new_found)
 
117
            if not remaining:
 
118
                break
 
119
        if not remaining:
 
120
            return found
 
121
        for parents_provider in self._parent_providers:
 
122
            try:
 
123
                new_found = parents_provider.get_parent_map(remaining)
 
124
            except errors.UnsupportedOperation:
 
125
                continue
100
126
            found.update(new_found)
101
127
            remaining.difference_update(new_found)
102
128
            if not remaining:
154
180
            return None
155
181
        return dict(self._cache)
156
182
 
 
183
    def get_cached_parent_map(self, keys):
 
184
        """Return items from the cache.
 
185
 
 
186
        This returns the same info as get_parent_map, but explicitly does not
 
187
        invoke the supplied ParentsProvider to search for uncached values.
 
188
        """
 
189
        cache = self._cache
 
190
        if cache is None:
 
191
            return {}
 
192
        return dict([(key, cache[key]) for key in keys if key in cache])
 
193
 
157
194
    def get_parent_map(self, keys):
158
195
        """See StackedParentsProvider.get_parent_map."""
159
196
        cache = self._cache
183
220
            self.missing_keys.add(key)
184
221
 
185
222
 
 
223
class CallableToParentsProviderAdapter(object):
 
224
    """A parents provider that adapts any callable to the parents provider API.
 
225
 
 
226
    i.e. it accepts calls to self.get_parent_map and relays them to the
 
227
    callable it was constructed with.
 
228
    """
 
229
 
 
230
    def __init__(self, a_callable):
 
231
        self.callable = a_callable
 
232
 
 
233
    def __repr__(self):
 
234
        return "%s(%r)" % (self.__class__.__name__, self.callable)
 
235
 
 
236
    def get_parent_map(self, keys):
 
237
        return self.callable(keys)
 
238
 
 
239
 
186
240
class Graph(object):
187
241
    """Provide incremental access to revision graphs.
188
242
 
237
291
        common ancestor of all border ancestors, because this shows that it
238
292
        cannot be a descendant of any border ancestor.
239
293
 
240
 
        The scaling of this operation should be proportional to
 
294
        The scaling of this operation should be proportional to:
 
295
 
241
296
        1. The number of uncommon ancestors
242
297
        2. The number of border ancestors
243
298
        3. The length of the shortest path between a border ancestor and an
258
313
        right = searchers[1].seen
259
314
        return (left.difference(right), right.difference(left))
260
315
 
 
316
    def find_descendants(self, old_key, new_key):
 
317
        """Find descendants of old_key that are ancestors of new_key."""
 
318
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
319
            old_key, new_key))
 
320
        graph = Graph(DictParentsProvider(child_map))
 
321
        searcher = graph._make_breadth_first_searcher([old_key])
 
322
        list(searcher)
 
323
        return searcher.seen
 
324
 
 
325
    def _find_descendant_ancestors(self, old_key, new_key):
 
326
        """Find ancestors of new_key that may be descendants of old_key."""
 
327
        stop = self._make_breadth_first_searcher([old_key])
 
328
        descendants = self._make_breadth_first_searcher([new_key])
 
329
        for revisions in descendants:
 
330
            old_stop = stop.seen.intersection(revisions)
 
331
            descendants.stop_searching_any(old_stop)
 
332
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
333
            descendants.stop_searching_any(seen_stop)
 
334
        return descendants.seen.difference(stop.seen)
 
335
 
 
336
    def get_child_map(self, keys):
 
337
        """Get a mapping from parents to children of the specified keys.
 
338
 
 
339
        This is simply the inversion of get_parent_map.  Only supplied keys
 
340
        will be discovered as children.
 
341
        :return: a dict of key:child_list for keys.
 
342
        """
 
343
        parent_map = self._parents_provider.get_parent_map(keys)
 
344
        parent_child = {}
 
345
        for child, parents in sorted(viewitems(parent_map)):
 
346
            for parent in parents:
 
347
                parent_child.setdefault(parent, []).append(child)
 
348
        return parent_child
 
349
 
261
350
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
351
        """Find the left-hand distance to the NULL_REVISION.
263
352
 
276
365
        NULL_REVISION = revision.NULL_REVISION
277
366
        known_revnos[NULL_REVISION] = 0
278
367
 
279
 
        searching_known_tips = list(known_revnos.keys())
 
368
        searching_known_tips = list(known_revnos)
280
369
 
281
370
        unknown_searched = {}
282
371
 
283
372
        while cur_tip not in known_revnos:
284
373
            unknown_searched[cur_tip] = num_steps
285
374
            num_steps += 1
286
 
            to_search = set([cur_tip])
 
375
            to_search = {cur_tip}
287
376
            to_search.update(searching_known_tips)
288
377
            parent_map = self.get_parent_map(to_search)
289
378
            parents = parent_map.get(cur_tip, None)
341
430
 
342
431
        :param unique_revision: The revision_id whose ancestry we are
343
432
            interested in.
344
 
            XXX: Would this API be better if we allowed multiple revisions on
345
 
                 to be searched here?
 
433
            (XXX: Would this API be better if we allowed multiple revisions on
 
434
            to be searched here?)
346
435
        :param common_revisions: Revision_ids of ancestries to exclude.
347
436
        :return: A set of revisions in the ancestry of unique_revision
348
437
        """
399
488
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
400
489
        # we know that unique_revisions aren't in common_revisions, so skip
401
490
        # past them.
402
 
        unique_searcher.next()
 
491
        next(unique_searcher)
403
492
        common_searcher = self._make_breadth_first_searcher(common_revisions)
404
493
 
405
494
        # As long as we are still finding unique nodes, keep searching
563
652
        # TODO: it might be possible to collapse searchers faster when they
564
653
        #       only have *some* search tips in common.
565
654
        next_unique_searchers = []
566
 
        for searchers in unique_search_tips.itervalues():
 
655
        for searchers in viewvalues(unique_search_tips):
567
656
            if len(searchers) == 1:
568
657
                # Searching unique tips, go for it
569
658
                next_unique_searchers.append(searchers[0])
746
835
            # NULL_REVISION is only a head if it is the only entry
747
836
            candidate_heads.remove(revision.NULL_REVISION)
748
837
            if not candidate_heads:
749
 
                return set([revision.NULL_REVISION])
 
838
                return {revision.NULL_REVISION}
750
839
        if len(candidate_heads) < 2:
751
840
            return candidate_heads
752
841
        searchers = dict((c, self._make_breadth_first_searcher([c]))
753
842
                          for c in candidate_heads)
754
843
        active_searchers = dict(searchers)
755
844
        # skip over the actual candidate for each searcher
756
 
        for searcher in active_searchers.itervalues():
757
 
            searcher.next()
 
845
        for searcher in viewvalues(active_searchers):
 
846
            next(searcher)
758
847
        # The common walker finds nodes that are common to two or more of the
759
848
        # input keys, so that we don't access all history when a currently
760
849
        # uncommon search point actually meets up with something behind a
766
855
            ancestors = set()
767
856
            # advance searches
768
857
            try:
769
 
                common_walker.next()
 
858
                next(common_walker)
770
859
            except StopIteration:
771
860
                # No common points being searched at this time.
772
861
                pass
773
 
            for candidate in active_searchers.keys():
 
862
            for candidate in list(active_searchers):
774
863
                try:
775
864
                    searcher = active_searchers[candidate]
776
865
                except KeyError:
779
868
                    # a descendant of another candidate.
780
869
                    continue
781
870
                try:
782
 
                    ancestors.update(searcher.next())
 
871
                    ancestors.update(next(searcher))
783
872
                except StopIteration:
784
873
                    del active_searchers[candidate]
785
874
                    continue
795
884
                if ancestor in common_walker.seen:
796
885
                    # some searcher has encountered our known common nodes:
797
886
                    # just stop it
798
 
                    ancestor_set = set([ancestor])
799
 
                    for searcher in searchers.itervalues():
 
887
                    ancestor_set = {ancestor}
 
888
                    for searcher in viewvalues(searchers):
800
889
                        searcher.stop_searching_any(ancestor_set)
801
890
                else:
802
891
                    # or it may have been just reached by all the searchers:
803
 
                    for searcher in searchers.itervalues():
 
892
                    for searcher in viewvalues(searchers):
804
893
                        if ancestor not in searcher.seen:
805
894
                            break
806
895
                    else:
808
897
                        # making it be known as a descendant of all candidates,
809
898
                        # so we can stop searching it, and any seen ancestors
810
899
                        new_common.add(ancestor)
811
 
                        for searcher in searchers.itervalues():
 
900
                        for searcher in viewvalues(searchers):
812
901
                            seen_ancestors =\
813
902
                                searcher.find_seen_ancestors([ancestor])
814
903
                            searcher.stop_searching_any(seen_ancestors)
862
951
                stop.add(parent_id)
863
952
        return found
864
953
 
 
954
    def find_lefthand_merger(self, merged_key, tip_key):
 
955
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
956
 
 
957
        We do this by first finding the descendants of merged_key, then
 
958
        walking through the lefthand ancestry of tip_key until we find a key
 
959
        that doesn't descend from merged_key.  Its child is the key that
 
960
        merged merged_key.
 
961
 
 
962
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
963
            merged_key if it is a lefthand ancestor of tip_key.
 
964
            None if no ancestor of tip_key merged merged_key.
 
965
        """
 
966
        descendants = self.find_descendants(merged_key, tip_key)
 
967
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
968
        last_candidate = None
 
969
        for candidate in candidate_iterator:
 
970
            if candidate not in descendants:
 
971
                return last_candidate
 
972
            last_candidate = candidate
 
973
 
865
974
    def find_unique_lca(self, left_revision, right_revision,
866
975
                        count_steps=False):
867
976
        """Find a unique LCA.
911
1020
            processed.update(pending)
912
1021
            next_map = self.get_parent_map(pending)
913
1022
            next_pending = set()
914
 
            for item in next_map.iteritems():
 
1023
            for item in viewitems(next_map):
915
1024
                yield item
916
1025
                next_pending.update(p for p in item[1] if p not in processed)
917
1026
            ghosts = pending.difference(next_map)
919
1028
                yield (ghost, None)
920
1029
            pending = next_pending
921
1030
 
 
1031
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
1032
        if stop_keys is None:
 
1033
            stop_keys = ()
 
1034
        next_key = start_key
 
1035
        def get_parents(key):
 
1036
            try:
 
1037
                return self._parents_provider.get_parent_map([key])[key]
 
1038
            except KeyError:
 
1039
                raise errors.RevisionNotPresent(next_key, self)
 
1040
        while True:
 
1041
            if next_key in stop_keys:
 
1042
                return
 
1043
            parents = get_parents(next_key)
 
1044
            yield next_key
 
1045
            if len(parents) == 0:
 
1046
                return
 
1047
            else:
 
1048
                next_key = parents[0]
 
1049
 
922
1050
    def iter_topo_order(self, revisions):
923
1051
        """Iterate through the input revisions in topological order.
924
1052
 
926
1054
        An ancestor may sort after a descendant if the relationship is not
927
1055
        visible in the supplied list of revisions.
928
1056
        """
929
 
        from bzrlib import tsort
 
1057
        from breezy import tsort
930
1058
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
1059
        return sorter.iter_topo_order()
932
1060
 
937
1065
        smallest number of parent lookups to determine the ancestral
938
1066
        relationship between N revisions.
939
1067
        """
940
 
        return set([candidate_descendant]) == self.heads(
 
1068
        return {candidate_descendant} == self.heads(
941
1069
            [candidate_ancestor, candidate_descendant])
942
1070
 
943
1071
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1021
1149
                ancestor_all_unique = ancestor_all_unique.intersection(
1022
1150
                                            searcher.seen)
1023
1151
 
1024
 
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1152
        trace.mutter('Started %d unique searchers for %d unique revisions',
1025
1153
                     simple_unique, total_unique)
1026
1154
 
1027
1155
        while True: # If we have no more nodes we have nothing to do
1128
1256
        ## for revision in revisions.intersection(descendants):
1129
1257
        ##   simple_ancestors.difference_update(descendants[revision])
1130
1258
        ## return simple_ancestors
1131
 
        for revision, parent_ids in parent_map.iteritems():
 
1259
        for revision, parent_ids in viewitems(parent_map):
1132
1260
            if parent_ids is None:
1133
1261
                continue
1134
1262
            for parent_id in parent_ids:
1227
1355
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1228
1356
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1229
1357
 
1230
 
    def get_result(self):
1231
 
        """Get a SearchResult for the current state of this searcher.
 
1358
    def get_state(self):
 
1359
        """Get the current state of this searcher.
1232
1360
 
1233
 
        :return: A SearchResult for this search so far. The SearchResult is
1234
 
            static - the search can be advanced and the search result will not
1235
 
            be invalidated or altered.
 
1361
        :return: Tuple with started keys, excludes and included keys
1236
1362
        """
1237
1363
        if self._returning == 'next':
1238
1364
            # We have to know the current nodes children to be able to list the
1249
1375
            next_query = self._next_query
1250
1376
        excludes = self._stopped_keys.union(next_query)
1251
1377
        included_keys = self.seen.difference(excludes)
1252
 
        return SearchResult(self._started_keys, excludes, len(included_keys),
1253
 
            included_keys)
 
1378
        return self._started_keys, excludes, included_keys
1254
1379
 
1255
1380
    def step(self):
1256
1381
        try:
1257
 
            return self.next()
 
1382
            return next(self)
1258
1383
        except StopIteration:
1259
1384
            return ()
1260
1385
 
1261
 
    def next(self):
 
1386
    def __next__(self):
1262
1387
        """Return the next ancestors of this revision.
1263
1388
 
1264
1389
        Ancestors are returned in the order they are seen in a breadth-first
1284
1409
        self.seen.update(self._next_query)
1285
1410
        return self._next_query
1286
1411
 
 
1412
    next = __next__
 
1413
 
1287
1414
    def next_with_ghosts(self):
1288
1415
        """Return the next found ancestors, with ghosts split out.
1289
1416
 
1332
1459
        parents_of_found = set()
1333
1460
        # revisions may contain nodes that point to other nodes in revisions:
1334
1461
        # we want to filter them out.
1335
 
        self.seen.update(revisions)
 
1462
        seen = self.seen
 
1463
        seen.update(revisions)
1336
1464
        parent_map = self._parents_provider.get_parent_map(revisions)
1337
1465
        found_revisions.update(parent_map)
1338
 
        for rev_id, parents in parent_map.iteritems():
 
1466
        for rev_id, parents in viewitems(parent_map):
1339
1467
            if parents is None:
1340
1468
                continue
1341
 
            new_found_parents = [p for p in parents if p not in self.seen]
 
1469
            new_found_parents = [p for p in parents if p not in seen]
1342
1470
            if new_found_parents:
1343
1471
                # Calling set.update() with an empty generator is actually
1344
1472
                # rather expensive.
1378
1506
            all_parents = []
1379
1507
            # We don't care if it is a ghost, since it can't be seen if it is
1380
1508
            # a ghost
1381
 
            for parent_ids in parent_map.itervalues():
 
1509
            for parent_ids in viewvalues(parent_map):
1382
1510
                all_parents.extend(parent_ids)
1383
1511
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1384
1512
            seen_ancestors.update(next_pending)
1423
1551
                    stop_rev_references[parent_id] += 1
1424
1552
            # if only the stopped revisions reference it, the ref count will be
1425
1553
            # 0 after this loop
1426
 
            for parents in self._current_parents.itervalues():
 
1554
            for parents in viewvalues(self._current_parents):
1427
1555
                for parent_id in parents:
1428
1556
                    try:
1429
1557
                        stop_rev_references[parent_id] -= 1
1430
1558
                    except KeyError:
1431
1559
                        pass
1432
1560
            stop_parents = set()
1433
 
            for rev_id, refs in stop_rev_references.iteritems():
 
1561
            for rev_id, refs in viewitems(stop_rev_references):
1434
1562
                if refs == 0:
1435
1563
                    stop_parents.add(rev_id)
1436
1564
            self._next_query.difference_update(stop_parents)
1463
1591
            return revs, ghosts
1464
1592
 
1465
1593
 
1466
 
class SearchResult(object):
1467
 
    """The result of a breadth first search.
1468
 
 
1469
 
    A SearchResult provides the ability to reconstruct the search or access a
1470
 
    set of the keys the search found.
1471
 
    """
1472
 
 
1473
 
    def __init__(self, start_keys, exclude_keys, key_count, keys):
1474
 
        """Create a SearchResult.
1475
 
 
1476
 
        :param start_keys: The keys the search started at.
1477
 
        :param exclude_keys: The keys the search excludes.
1478
 
        :param key_count: The total number of keys (from start to but not
1479
 
            including exclude).
1480
 
        :param keys: The keys the search found. Note that in future we may get
1481
 
            a SearchResult from a smart server, in which case the keys list is
1482
 
            not necessarily immediately available.
1483
 
        """
1484
 
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
 
        self._keys = frozenset(keys)
1486
 
 
1487
 
    def get_recipe(self):
1488
 
        """Return a recipe that can be used to replay this search.
1489
 
 
1490
 
        The recipe allows reconstruction of the same results at a later date
1491
 
        without knowing all the found keys. The essential elements are a list
1492
 
        of keys to start and to stop at. In order to give reproducible
1493
 
        results when ghosts are encountered by a search they are automatically
1494
 
        added to the exclude list (or else ghost filling may alter the
1495
 
        results).
1496
 
 
1497
 
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
1498
 
            revision_count). To recreate the results of this search, create a
1499
 
            breadth first searcher on the same graph starting at start_keys.
1500
 
            Then call next() (or next_with_ghosts()) repeatedly, and on every
1501
 
            result, call stop_searching_any on any keys from the exclude_keys
1502
 
            set. The revision_count value acts as a trivial cross-check - the
1503
 
            found revisions of the new search should have as many elements as
1504
 
            revision_count. If it does not, then additional revisions have been
1505
 
            ghosted since the search was executed the first time and the second
1506
 
            time.
1507
 
        """
1508
 
        return self._recipe
1509
 
 
1510
 
    def get_keys(self):
1511
 
        """Return the keys found in this search.
1512
 
 
1513
 
        :return: A set of keys.
1514
 
        """
1515
 
        return self._keys
1516
 
 
1517
 
    def is_empty(self):
1518
 
        """Return false if the search lists 1 or more revisions."""
1519
 
        return self._recipe[3] == 0
1520
 
 
1521
 
    def refine(self, seen, referenced):
1522
 
        """Create a new search by refining this search.
1523
 
 
1524
 
        :param seen: Revisions that have been satisfied.
1525
 
        :param referenced: Revision references observed while satisfying some
1526
 
            of this search.
1527
 
        """
1528
 
        start = self._recipe[1]
1529
 
        exclude = self._recipe[2]
1530
 
        count = self._recipe[3]
1531
 
        keys = self.get_keys()
1532
 
        # New heads = referenced + old heads - seen things - exclude
1533
 
        pending_refs = set(referenced)
1534
 
        pending_refs.update(start)
1535
 
        pending_refs.difference_update(seen)
1536
 
        pending_refs.difference_update(exclude)
1537
 
        # New exclude = old exclude + satisfied heads
1538
 
        seen_heads = start.intersection(seen)
1539
 
        exclude.update(seen_heads)
1540
 
        # keys gets seen removed
1541
 
        keys = keys - seen
1542
 
        # length is reduced by len(seen)
1543
 
        count -= len(seen)
1544
 
        return SearchResult(pending_refs, exclude, count, keys)
1545
 
 
1546
 
 
1547
 
class PendingAncestryResult(object):
1548
 
    """A search result that will reconstruct the ancestry for some graph heads.
1549
 
 
1550
 
    Unlike SearchResult, this doesn't hold the complete search result in
1551
 
    memory, it just holds a description of how to generate it.
1552
 
    """
1553
 
 
1554
 
    def __init__(self, heads, repo):
1555
 
        """Constructor.
1556
 
 
1557
 
        :param heads: an iterable of graph heads.
1558
 
        :param repo: a repository to use to generate the ancestry for the given
1559
 
            heads.
1560
 
        """
1561
 
        self.heads = frozenset(heads)
1562
 
        self.repo = repo
1563
 
 
1564
 
    def get_recipe(self):
1565
 
        """Return a recipe that can be used to replay this search.
1566
 
 
1567
 
        The recipe allows reconstruction of the same results at a later date.
1568
 
 
1569
 
        :seealso SearchResult.get_recipe:
1570
 
 
1571
 
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
1572
 
            To recreate this result, create a PendingAncestryResult with the
1573
 
            start_keys_set.
1574
 
        """
1575
 
        return ('proxy-search', self.heads, set(), -1)
1576
 
 
1577
 
    def get_keys(self):
1578
 
        """See SearchResult.get_keys.
1579
 
 
1580
 
        Returns all the keys for the ancestry of the heads, excluding
1581
 
        NULL_REVISION.
1582
 
        """
1583
 
        return self._get_keys(self.repo.get_graph())
1584
 
 
1585
 
    def _get_keys(self, graph):
1586
 
        NULL_REVISION = revision.NULL_REVISION
1587
 
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1588
 
                if key != NULL_REVISION and parents is not None]
1589
 
        return keys
1590
 
 
1591
 
    def is_empty(self):
1592
 
        """Return false if the search lists 1 or more revisions."""
1593
 
        if revision.NULL_REVISION in self.heads:
1594
 
            return len(self.heads) == 1
1595
 
        else:
1596
 
            return len(self.heads) == 0
1597
 
 
1598
 
    def refine(self, seen, referenced):
1599
 
        """Create a new search by refining this search.
1600
 
 
1601
 
        :param seen: Revisions that have been satisfied.
1602
 
        :param referenced: Revision references observed while satisfying some
1603
 
            of this search.
1604
 
        """
1605
 
        referenced = self.heads.union(referenced)
1606
 
        return PendingAncestryResult(referenced - seen, self.repo)
 
1594
def invert_parent_map(parent_map):
 
1595
    """Given a map from child => parents, create a map of parent=>children"""
 
1596
    child_map = {}
 
1597
    for child, parents in viewitems(parent_map):
 
1598
        for p in parents:
 
1599
            # Any given parent is likely to have only a small handful
 
1600
            # of children, many will have only one. So we avoid mem overhead of
 
1601
            # a list, in exchange for extra copying of tuples
 
1602
            if p not in child_map:
 
1603
                child_map[p] = (child,)
 
1604
            else:
 
1605
                child_map[p] = child_map[p] + (child,)
 
1606
    return child_map
1607
1607
 
1608
1608
 
1609
1609
def collapse_linear_regions(parent_map):
1646
1646
    # Will not have any nodes removed, even though you do have an
1647
1647
    # 'uninteresting' linear D->B and E->C
1648
1648
    children = {}
1649
 
    for child, parents in parent_map.iteritems():
 
1649
    for child, parents in viewitems(parent_map):
1650
1650
        children.setdefault(child, [])
1651
1651
        for p in parents:
1652
1652
            children.setdefault(p, []).append(child)
1692
1692
        """See Graph.heads()"""
1693
1693
        as_keys = [(i,) for i in ids]
1694
1694
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
 
1695
        return {h[0] for h in head_keys}
1696
1696
 
1697
1697
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((tip_revision,))
1699
 
 
1700
 
 
1701
 
_counters = [0,0,0,0,0,0,0]
 
1698
        nodes = self._graph.merge_sort((tip_revision,))
 
1699
        for node in nodes:
 
1700
            node.key = node.key[0]
 
1701
        return nodes
 
1702
 
 
1703
    def add_node(self, revision, parents):
 
1704
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1705
 
 
1706
 
 
1707
_counters = [0, 0, 0, 0, 0, 0, 0]
1702
1708
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
 
1709
    from ._known_graph_pyx import KnownGraph
 
1710
except ImportError as e:
1705
1711
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph
 
1712
    from ._known_graph_py import KnownGraph  # noqa: F401