/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-10 02:09:46 UTC
  • mto: This revision was merged to the branch mainline in revision 6690.
  • Revision ID: jelmer@jelmer.uk-20170610020946-nxnwagf535b3lctb
Move breezy.repofmt contents to  breezy.bzr.

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)
 
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
98
121
        for parents_provider in self._parent_providers:
99
122
            new_found = parents_provider.get_parent_map(remaining)
100
123
            found.update(new_found)
154
177
            return None
155
178
        return dict(self._cache)
156
179
 
 
180
    def get_cached_parent_map(self, keys):
 
181
        """Return items from the cache.
 
182
 
 
183
        This returns the same info as get_parent_map, but explicitly does not
 
184
        invoke the supplied ParentsProvider to search for uncached values.
 
185
        """
 
186
        cache = self._cache
 
187
        if cache is None:
 
188
            return {}
 
189
        return dict([(key, cache[key]) for key in keys if key in cache])
 
190
 
157
191
    def get_parent_map(self, keys):
158
192
        """See StackedParentsProvider.get_parent_map."""
159
193
        cache = self._cache
183
217
            self.missing_keys.add(key)
184
218
 
185
219
 
 
220
class CallableToParentsProviderAdapter(object):
 
221
    """A parents provider that adapts any callable to the parents provider API.
 
222
 
 
223
    i.e. it accepts calls to self.get_parent_map and relays them to the
 
224
    callable it was constructed with.
 
225
    """
 
226
 
 
227
    def __init__(self, a_callable):
 
228
        self.callable = a_callable
 
229
 
 
230
    def __repr__(self):
 
231
        return "%s(%r)" % (self.__class__.__name__, self.callable)
 
232
 
 
233
    def get_parent_map(self, keys):
 
234
        return self.callable(keys)
 
235
 
 
236
 
186
237
class Graph(object):
187
238
    """Provide incremental access to revision graphs.
188
239
 
237
288
        common ancestor of all border ancestors, because this shows that it
238
289
        cannot be a descendant of any border ancestor.
239
290
 
240
 
        The scaling of this operation should be proportional to
 
291
        The scaling of this operation should be proportional to:
 
292
 
241
293
        1. The number of uncommon ancestors
242
294
        2. The number of border ancestors
243
295
        3. The length of the shortest path between a border ancestor and an
258
310
        right = searchers[1].seen
259
311
        return (left.difference(right), right.difference(left))
260
312
 
 
313
    def find_descendants(self, old_key, new_key):
 
314
        """Find descendants of old_key that are ancestors of new_key."""
 
315
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
316
            old_key, new_key))
 
317
        graph = Graph(DictParentsProvider(child_map))
 
318
        searcher = graph._make_breadth_first_searcher([old_key])
 
319
        list(searcher)
 
320
        return searcher.seen
 
321
 
 
322
    def _find_descendant_ancestors(self, old_key, new_key):
 
323
        """Find ancestors of new_key that may be descendants of old_key."""
 
324
        stop = self._make_breadth_first_searcher([old_key])
 
325
        descendants = self._make_breadth_first_searcher([new_key])
 
326
        for revisions in descendants:
 
327
            old_stop = stop.seen.intersection(revisions)
 
328
            descendants.stop_searching_any(old_stop)
 
329
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
330
            descendants.stop_searching_any(seen_stop)
 
331
        return descendants.seen.difference(stop.seen)
 
332
 
 
333
    def get_child_map(self, keys):
 
334
        """Get a mapping from parents to children of the specified keys.
 
335
 
 
336
        This is simply the inversion of get_parent_map.  Only supplied keys
 
337
        will be discovered as children.
 
338
        :return: a dict of key:child_list for keys.
 
339
        """
 
340
        parent_map = self._parents_provider.get_parent_map(keys)
 
341
        parent_child = {}
 
342
        for child, parents in sorted(viewitems(parent_map)):
 
343
            for parent in parents:
 
344
                parent_child.setdefault(parent, []).append(child)
 
345
        return parent_child
 
346
 
261
347
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
348
        """Find the left-hand distance to the NULL_REVISION.
263
349
 
276
362
        NULL_REVISION = revision.NULL_REVISION
277
363
        known_revnos[NULL_REVISION] = 0
278
364
 
279
 
        searching_known_tips = list(known_revnos.keys())
 
365
        searching_known_tips = list(known_revnos)
280
366
 
281
367
        unknown_searched = {}
282
368
 
283
369
        while cur_tip not in known_revnos:
284
370
            unknown_searched[cur_tip] = num_steps
285
371
            num_steps += 1
286
 
            to_search = set([cur_tip])
 
372
            to_search = {cur_tip}
287
373
            to_search.update(searching_known_tips)
288
374
            parent_map = self.get_parent_map(to_search)
289
375
            parents = parent_map.get(cur_tip, None)
341
427
 
342
428
        :param unique_revision: The revision_id whose ancestry we are
343
429
            interested in.
344
 
            XXX: Would this API be better if we allowed multiple revisions on
345
 
                 to be searched here?
 
430
            (XXX: Would this API be better if we allowed multiple revisions on
 
431
            to be searched here?)
346
432
        :param common_revisions: Revision_ids of ancestries to exclude.
347
433
        :return: A set of revisions in the ancestry of unique_revision
348
434
        """
399
485
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
400
486
        # we know that unique_revisions aren't in common_revisions, so skip
401
487
        # past them.
402
 
        unique_searcher.next()
 
488
        next(unique_searcher)
403
489
        common_searcher = self._make_breadth_first_searcher(common_revisions)
404
490
 
405
491
        # As long as we are still finding unique nodes, keep searching
563
649
        # TODO: it might be possible to collapse searchers faster when they
564
650
        #       only have *some* search tips in common.
565
651
        next_unique_searchers = []
566
 
        for searchers in unique_search_tips.itervalues():
 
652
        for searchers in viewvalues(unique_search_tips):
567
653
            if len(searchers) == 1:
568
654
                # Searching unique tips, go for it
569
655
                next_unique_searchers.append(searchers[0])
746
832
            # NULL_REVISION is only a head if it is the only entry
747
833
            candidate_heads.remove(revision.NULL_REVISION)
748
834
            if not candidate_heads:
749
 
                return set([revision.NULL_REVISION])
 
835
                return {revision.NULL_REVISION}
750
836
        if len(candidate_heads) < 2:
751
837
            return candidate_heads
752
838
        searchers = dict((c, self._make_breadth_first_searcher([c]))
753
839
                          for c in candidate_heads)
754
840
        active_searchers = dict(searchers)
755
841
        # skip over the actual candidate for each searcher
756
 
        for searcher in active_searchers.itervalues():
757
 
            searcher.next()
 
842
        for searcher in viewvalues(active_searchers):
 
843
            next(searcher)
758
844
        # The common walker finds nodes that are common to two or more of the
759
845
        # input keys, so that we don't access all history when a currently
760
846
        # uncommon search point actually meets up with something behind a
766
852
            ancestors = set()
767
853
            # advance searches
768
854
            try:
769
 
                common_walker.next()
 
855
                next(common_walker)
770
856
            except StopIteration:
771
857
                # No common points being searched at this time.
772
858
                pass
773
 
            for candidate in active_searchers.keys():
 
859
            for candidate in list(active_searchers):
774
860
                try:
775
861
                    searcher = active_searchers[candidate]
776
862
                except KeyError:
779
865
                    # a descendant of another candidate.
780
866
                    continue
781
867
                try:
782
 
                    ancestors.update(searcher.next())
 
868
                    ancestors.update(next(searcher))
783
869
                except StopIteration:
784
870
                    del active_searchers[candidate]
785
871
                    continue
795
881
                if ancestor in common_walker.seen:
796
882
                    # some searcher has encountered our known common nodes:
797
883
                    # just stop it
798
 
                    ancestor_set = set([ancestor])
799
 
                    for searcher in searchers.itervalues():
 
884
                    ancestor_set = {ancestor}
 
885
                    for searcher in viewvalues(searchers):
800
886
                        searcher.stop_searching_any(ancestor_set)
801
887
                else:
802
888
                    # or it may have been just reached by all the searchers:
803
 
                    for searcher in searchers.itervalues():
 
889
                    for searcher in viewvalues(searchers):
804
890
                        if ancestor not in searcher.seen:
805
891
                            break
806
892
                    else:
808
894
                        # making it be known as a descendant of all candidates,
809
895
                        # so we can stop searching it, and any seen ancestors
810
896
                        new_common.add(ancestor)
811
 
                        for searcher in searchers.itervalues():
 
897
                        for searcher in viewvalues(searchers):
812
898
                            seen_ancestors =\
813
899
                                searcher.find_seen_ancestors([ancestor])
814
900
                            searcher.stop_searching_any(seen_ancestors)
862
948
                stop.add(parent_id)
863
949
        return found
864
950
 
 
951
    def find_lefthand_merger(self, merged_key, tip_key):
 
952
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
953
 
 
954
        We do this by first finding the descendants of merged_key, then
 
955
        walking through the lefthand ancestry of tip_key until we find a key
 
956
        that doesn't descend from merged_key.  Its child is the key that
 
957
        merged merged_key.
 
958
 
 
959
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
960
            merged_key if it is a lefthand ancestor of tip_key.
 
961
            None if no ancestor of tip_key merged merged_key.
 
962
        """
 
963
        descendants = self.find_descendants(merged_key, tip_key)
 
964
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
965
        last_candidate = None
 
966
        for candidate in candidate_iterator:
 
967
            if candidate not in descendants:
 
968
                return last_candidate
 
969
            last_candidate = candidate
 
970
 
865
971
    def find_unique_lca(self, left_revision, right_revision,
866
972
                        count_steps=False):
867
973
        """Find a unique LCA.
911
1017
            processed.update(pending)
912
1018
            next_map = self.get_parent_map(pending)
913
1019
            next_pending = set()
914
 
            for item in next_map.iteritems():
 
1020
            for item in viewitems(next_map):
915
1021
                yield item
916
1022
                next_pending.update(p for p in item[1] if p not in processed)
917
1023
            ghosts = pending.difference(next_map)
919
1025
                yield (ghost, None)
920
1026
            pending = next_pending
921
1027
 
 
1028
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
1029
        if stop_keys is None:
 
1030
            stop_keys = ()
 
1031
        next_key = start_key
 
1032
        def get_parents(key):
 
1033
            try:
 
1034
                return self._parents_provider.get_parent_map([key])[key]
 
1035
            except KeyError:
 
1036
                raise errors.RevisionNotPresent(next_key, self)
 
1037
        while True:
 
1038
            if next_key in stop_keys:
 
1039
                return
 
1040
            parents = get_parents(next_key)
 
1041
            yield next_key
 
1042
            if len(parents) == 0:
 
1043
                return
 
1044
            else:
 
1045
                next_key = parents[0]
 
1046
 
922
1047
    def iter_topo_order(self, revisions):
923
1048
        """Iterate through the input revisions in topological order.
924
1049
 
926
1051
        An ancestor may sort after a descendant if the relationship is not
927
1052
        visible in the supplied list of revisions.
928
1053
        """
929
 
        from bzrlib import tsort
 
1054
        from breezy import tsort
930
1055
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
1056
        return sorter.iter_topo_order()
932
1057
 
937
1062
        smallest number of parent lookups to determine the ancestral
938
1063
        relationship between N revisions.
939
1064
        """
940
 
        return set([candidate_descendant]) == self.heads(
 
1065
        return {candidate_descendant} == self.heads(
941
1066
            [candidate_ancestor, candidate_descendant])
942
1067
 
943
1068
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1128
1253
        ## for revision in revisions.intersection(descendants):
1129
1254
        ##   simple_ancestors.difference_update(descendants[revision])
1130
1255
        ## return simple_ancestors
1131
 
        for revision, parent_ids in parent_map.iteritems():
 
1256
        for revision, parent_ids in viewitems(parent_map):
1132
1257
            if parent_ids is None:
1133
1258
                continue
1134
1259
            for parent_id in parent_ids:
1227
1352
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1228
1353
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1229
1354
 
1230
 
    def get_result(self):
1231
 
        """Get a SearchResult for the current state of this searcher.
 
1355
    def get_state(self):
 
1356
        """Get the current state of this searcher.
1232
1357
 
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.
 
1358
        :return: Tuple with started keys, excludes and included keys
1236
1359
        """
1237
1360
        if self._returning == 'next':
1238
1361
            # We have to know the current nodes children to be able to list the
1249
1372
            next_query = self._next_query
1250
1373
        excludes = self._stopped_keys.union(next_query)
1251
1374
        included_keys = self.seen.difference(excludes)
1252
 
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
1375
        return self._started_keys, excludes, included_keys
 
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),
1253
1387
            included_keys)
1254
1388
 
1255
1389
    def step(self):
1256
1390
        try:
1257
 
            return self.next()
 
1391
            return next(self)
1258
1392
        except StopIteration:
1259
1393
            return ()
1260
1394
 
1261
 
    def next(self):
 
1395
    def __next__(self):
1262
1396
        """Return the next ancestors of this revision.
1263
1397
 
1264
1398
        Ancestors are returned in the order they are seen in a breadth-first
1284
1418
        self.seen.update(self._next_query)
1285
1419
        return self._next_query
1286
1420
 
 
1421
    next = __next__
 
1422
 
1287
1423
    def next_with_ghosts(self):
1288
1424
        """Return the next found ancestors, with ghosts split out.
1289
1425
 
1332
1468
        parents_of_found = set()
1333
1469
        # revisions may contain nodes that point to other nodes in revisions:
1334
1470
        # we want to filter them out.
1335
 
        self.seen.update(revisions)
 
1471
        seen = self.seen
 
1472
        seen.update(revisions)
1336
1473
        parent_map = self._parents_provider.get_parent_map(revisions)
1337
1474
        found_revisions.update(parent_map)
1338
 
        for rev_id, parents in parent_map.iteritems():
 
1475
        for rev_id, parents in viewitems(parent_map):
1339
1476
            if parents is None:
1340
1477
                continue
1341
 
            new_found_parents = [p for p in parents if p not in self.seen]
 
1478
            new_found_parents = [p for p in parents if p not in seen]
1342
1479
            if new_found_parents:
1343
1480
                # Calling set.update() with an empty generator is actually
1344
1481
                # rather expensive.
1378
1515
            all_parents = []
1379
1516
            # We don't care if it is a ghost, since it can't be seen if it is
1380
1517
            # a ghost
1381
 
            for parent_ids in parent_map.itervalues():
 
1518
            for parent_ids in viewvalues(parent_map):
1382
1519
                all_parents.extend(parent_ids)
1383
1520
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1384
1521
            seen_ancestors.update(next_pending)
1423
1560
                    stop_rev_references[parent_id] += 1
1424
1561
            # if only the stopped revisions reference it, the ref count will be
1425
1562
            # 0 after this loop
1426
 
            for parents in self._current_parents.itervalues():
 
1563
            for parents in viewvalues(self._current_parents):
1427
1564
                for parent_id in parents:
1428
1565
                    try:
1429
1566
                        stop_rev_references[parent_id] -= 1
1430
1567
                    except KeyError:
1431
1568
                        pass
1432
1569
            stop_parents = set()
1433
 
            for rev_id, refs in stop_rev_references.iteritems():
 
1570
            for rev_id, refs in viewitems(stop_rev_references):
1434
1571
                if refs == 0:
1435
1572
                    stop_parents.add(rev_id)
1436
1573
            self._next_query.difference_update(stop_parents)
1463
1600
            return revs, ghosts
1464
1601
 
1465
1602
 
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)
 
1603
def invert_parent_map(parent_map):
 
1604
    """Given a map from child => parents, create a map of parent=>children"""
 
1605
    child_map = {}
 
1606
    for child, parents in viewitems(parent_map):
 
1607
        for p in parents:
 
1608
            # Any given parent is likely to have only a small handful
 
1609
            # of children, many will have only one. So we avoid mem overhead of
 
1610
            # a list, in exchange for extra copying of tuples
 
1611
            if p not in child_map:
 
1612
                child_map[p] = (child,)
 
1613
            else:
 
1614
                child_map[p] = child_map[p] + (child,)
 
1615
    return child_map
1607
1616
 
1608
1617
 
1609
1618
def collapse_linear_regions(parent_map):
1646
1655
    # Will not have any nodes removed, even though you do have an
1647
1656
    # 'uninteresting' linear D->B and E->C
1648
1657
    children = {}
1649
 
    for child, parents in parent_map.iteritems():
 
1658
    for child, parents in viewitems(parent_map):
1650
1659
        children.setdefault(child, [])
1651
1660
        for p in parents:
1652
1661
            children.setdefault(p, []).append(child)
1692
1701
        """See Graph.heads()"""
1693
1702
        as_keys = [(i,) for i in ids]
1694
1703
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
 
1704
        return {h[0] for h in head_keys}
1696
1705
 
1697
1706
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((tip_revision,))
 
1707
        nodes = self._graph.merge_sort((tip_revision,))
 
1708
        for node in nodes:
 
1709
            node.key = node.key[0]
 
1710
        return nodes
 
1711
 
 
1712
    def add_node(self, revision, parents):
 
1713
        self._graph.add_node((revision,), [(p,) for p in parents])
1699
1714
 
1700
1715
 
1701
1716
_counters = [0,0,0,0,0,0,0]
1702
1717
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
 
1718
    from ._known_graph_pyx import KnownGraph
 
1719
except ImportError as e:
1705
1720
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph
 
1721
    from ._known_graph_py import KnownGraph