/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: Robert Collins
  • Date: 2010-05-06 11:08:10 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506110810-h3j07fh5gmw54s25
Cleaner matcher matching revised unlocking protocol.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007-2010 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
 
 
19
17
import time
20
18
 
21
 
from . import (
 
19
from bzrlib import (
22
20
    debug,
23
21
    errors,
24
22
    osutils,
25
23
    revision,
26
24
    trace,
27
25
    )
28
 
from .sixish import (
29
 
    viewitems,
30
 
    viewvalues,
31
 
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
32
27
 
33
28
STEP_UNIQUE_SEARCHER_EVERY = 5
34
29
 
64
59
    def __repr__(self):
65
60
        return 'DictParentsProvider(%r)' % self.ancestry
66
61
 
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
 
 
72
62
    def get_parent_map(self, keys):
73
63
        """See StackedParentsProvider.get_parent_map"""
74
64
        ancestry = self.ancestry
75
 
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
76
66
 
 
67
@deprecated_function(deprecated_in((1, 16, 0)))
 
68
def _StackedParentsProvider(*args, **kwargs):
 
69
    return StackedParentsProvider(*args, **kwargs)
77
70
 
78
71
class StackedParentsProvider(object):
79
72
    """A parents provider which stacks (or unions) multiple providers.
80
 
 
 
73
    
81
74
    The providers are queries in the order of the provided parent_providers.
82
75
    """
83
 
 
 
76
    
84
77
    def __init__(self, parent_providers):
85
78
        self._parent_providers = parent_providers
86
79
 
102
95
        """
103
96
        found = {}
104
97
        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
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
 
98
        for parents_provider in self._parent_providers:
 
99
            new_found = parents_provider.get_parent_map(remaining)
126
100
            found.update(new_found)
127
101
            remaining.difference_update(new_found)
128
102
            if not remaining:
180
154
            return None
181
155
        return dict(self._cache)
182
156
 
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
 
 
194
157
    def get_parent_map(self, keys):
195
158
        """See StackedParentsProvider.get_parent_map."""
196
159
        cache = self._cache
220
183
            self.missing_keys.add(key)
221
184
 
222
185
 
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
 
 
240
186
class Graph(object):
241
187
    """Provide incremental access to revision graphs.
242
188
 
291
237
        common ancestor of all border ancestors, because this shows that it
292
238
        cannot be a descendant of any border ancestor.
293
239
 
294
 
        The scaling of this operation should be proportional to:
295
 
 
 
240
        The scaling of this operation should be proportional to
296
241
        1. The number of uncommon ancestors
297
242
        2. The number of border ancestors
298
243
        3. The length of the shortest path between a border ancestor and an
313
258
        right = searchers[1].seen
314
259
        return (left.difference(right), right.difference(left))
315
260
 
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
 
 
350
261
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
351
262
        """Find the left-hand distance to the NULL_REVISION.
352
263
 
365
276
        NULL_REVISION = revision.NULL_REVISION
366
277
        known_revnos[NULL_REVISION] = 0
367
278
 
368
 
        searching_known_tips = list(known_revnos)
 
279
        searching_known_tips = list(known_revnos.keys())
369
280
 
370
281
        unknown_searched = {}
371
282
 
372
283
        while cur_tip not in known_revnos:
373
284
            unknown_searched[cur_tip] = num_steps
374
285
            num_steps += 1
375
 
            to_search = {cur_tip}
 
286
            to_search = set([cur_tip])
376
287
            to_search.update(searching_known_tips)
377
288
            parent_map = self.get_parent_map(to_search)
378
289
            parents = parent_map.get(cur_tip, None)
430
341
 
431
342
        :param unique_revision: The revision_id whose ancestry we are
432
343
            interested in.
433
 
            (XXX: Would this API be better if we allowed multiple revisions on
434
 
            to be searched here?)
 
344
            XXX: Would this API be better if we allowed multiple revisions on
 
345
                 to be searched here?
435
346
        :param common_revisions: Revision_ids of ancestries to exclude.
436
347
        :return: A set of revisions in the ancestry of unique_revision
437
348
        """
488
399
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
489
400
        # we know that unique_revisions aren't in common_revisions, so skip
490
401
        # past them.
491
 
        next(unique_searcher)
 
402
        unique_searcher.next()
492
403
        common_searcher = self._make_breadth_first_searcher(common_revisions)
493
404
 
494
405
        # As long as we are still finding unique nodes, keep searching
652
563
        # TODO: it might be possible to collapse searchers faster when they
653
564
        #       only have *some* search tips in common.
654
565
        next_unique_searchers = []
655
 
        for searchers in viewvalues(unique_search_tips):
 
566
        for searchers in unique_search_tips.itervalues():
656
567
            if len(searchers) == 1:
657
568
                # Searching unique tips, go for it
658
569
                next_unique_searchers.append(searchers[0])
835
746
            # NULL_REVISION is only a head if it is the only entry
836
747
            candidate_heads.remove(revision.NULL_REVISION)
837
748
            if not candidate_heads:
838
 
                return {revision.NULL_REVISION}
 
749
                return set([revision.NULL_REVISION])
839
750
        if len(candidate_heads) < 2:
840
751
            return candidate_heads
841
752
        searchers = dict((c, self._make_breadth_first_searcher([c]))
842
753
                          for c in candidate_heads)
843
754
        active_searchers = dict(searchers)
844
755
        # skip over the actual candidate for each searcher
845
 
        for searcher in viewvalues(active_searchers):
846
 
            next(searcher)
 
756
        for searcher in active_searchers.itervalues():
 
757
            searcher.next()
847
758
        # The common walker finds nodes that are common to two or more of the
848
759
        # input keys, so that we don't access all history when a currently
849
760
        # uncommon search point actually meets up with something behind a
855
766
            ancestors = set()
856
767
            # advance searches
857
768
            try:
858
 
                next(common_walker)
 
769
                common_walker.next()
859
770
            except StopIteration:
860
771
                # No common points being searched at this time.
861
772
                pass
862
 
            for candidate in list(active_searchers):
 
773
            for candidate in active_searchers.keys():
863
774
                try:
864
775
                    searcher = active_searchers[candidate]
865
776
                except KeyError:
868
779
                    # a descendant of another candidate.
869
780
                    continue
870
781
                try:
871
 
                    ancestors.update(next(searcher))
 
782
                    ancestors.update(searcher.next())
872
783
                except StopIteration:
873
784
                    del active_searchers[candidate]
874
785
                    continue
884
795
                if ancestor in common_walker.seen:
885
796
                    # some searcher has encountered our known common nodes:
886
797
                    # just stop it
887
 
                    ancestor_set = {ancestor}
888
 
                    for searcher in viewvalues(searchers):
 
798
                    ancestor_set = set([ancestor])
 
799
                    for searcher in searchers.itervalues():
889
800
                        searcher.stop_searching_any(ancestor_set)
890
801
                else:
891
802
                    # or it may have been just reached by all the searchers:
892
 
                    for searcher in viewvalues(searchers):
 
803
                    for searcher in searchers.itervalues():
893
804
                        if ancestor not in searcher.seen:
894
805
                            break
895
806
                    else:
897
808
                        # making it be known as a descendant of all candidates,
898
809
                        # so we can stop searching it, and any seen ancestors
899
810
                        new_common.add(ancestor)
900
 
                        for searcher in viewvalues(searchers):
 
811
                        for searcher in searchers.itervalues():
901
812
                            seen_ancestors =\
902
813
                                searcher.find_seen_ancestors([ancestor])
903
814
                            searcher.stop_searching_any(seen_ancestors)
951
862
                stop.add(parent_id)
952
863
        return found
953
864
 
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
 
 
974
865
    def find_unique_lca(self, left_revision, right_revision,
975
866
                        count_steps=False):
976
867
        """Find a unique LCA.
1020
911
            processed.update(pending)
1021
912
            next_map = self.get_parent_map(pending)
1022
913
            next_pending = set()
1023
 
            for item in viewitems(next_map):
 
914
            for item in next_map.iteritems():
1024
915
                yield item
1025
916
                next_pending.update(p for p in item[1] if p not in processed)
1026
917
            ghosts = pending.difference(next_map)
1028
919
                yield (ghost, None)
1029
920
            pending = next_pending
1030
921
 
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
 
 
1050
922
    def iter_topo_order(self, revisions):
1051
923
        """Iterate through the input revisions in topological order.
1052
924
 
1054
926
        An ancestor may sort after a descendant if the relationship is not
1055
927
        visible in the supplied list of revisions.
1056
928
        """
1057
 
        from breezy import tsort
 
929
        from bzrlib import tsort
1058
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1059
931
        return sorter.iter_topo_order()
1060
932
 
1065
937
        smallest number of parent lookups to determine the ancestral
1066
938
        relationship between N revisions.
1067
939
        """
1068
 
        return {candidate_descendant} == self.heads(
 
940
        return set([candidate_descendant]) == self.heads(
1069
941
            [candidate_ancestor, candidate_descendant])
1070
942
 
1071
943
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1149
1021
                ancestor_all_unique = ancestor_all_unique.intersection(
1150
1022
                                            searcher.seen)
1151
1023
 
1152
 
        trace.mutter('Started %d unique searchers for %d unique revisions',
 
1024
        trace.mutter('Started %s unique searchers for %s unique revisions',
1153
1025
                     simple_unique, total_unique)
1154
1026
 
1155
1027
        while True: # If we have no more nodes we have nothing to do
1256
1128
        ## for revision in revisions.intersection(descendants):
1257
1129
        ##   simple_ancestors.difference_update(descendants[revision])
1258
1130
        ## return simple_ancestors
1259
 
        for revision, parent_ids in viewitems(parent_map):
 
1131
        for revision, parent_ids in parent_map.iteritems():
1260
1132
            if parent_ids is None:
1261
1133
                continue
1262
1134
            for parent_id in parent_ids:
1355
1227
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1356
1228
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1357
1229
 
1358
 
    def get_state(self):
1359
 
        """Get the current state of this searcher.
 
1230
    def get_result(self):
 
1231
        """Get a SearchResult for the current state of this searcher.
1360
1232
 
1361
 
        :return: Tuple with started keys, excludes and included keys
 
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.
1362
1236
        """
1363
1237
        if self._returning == 'next':
1364
1238
            # We have to know the current nodes children to be able to list the
1375
1249
            next_query = self._next_query
1376
1250
        excludes = self._stopped_keys.union(next_query)
1377
1251
        included_keys = self.seen.difference(excludes)
1378
 
        return self._started_keys, excludes, included_keys
 
1252
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
1253
            included_keys)
1379
1254
 
1380
1255
    def step(self):
1381
1256
        try:
1382
 
            return next(self)
 
1257
            return self.next()
1383
1258
        except StopIteration:
1384
1259
            return ()
1385
1260
 
1386
 
    def __next__(self):
 
1261
    def next(self):
1387
1262
        """Return the next ancestors of this revision.
1388
1263
 
1389
1264
        Ancestors are returned in the order they are seen in a breadth-first
1409
1284
        self.seen.update(self._next_query)
1410
1285
        return self._next_query
1411
1286
 
1412
 
    next = __next__
1413
 
 
1414
1287
    def next_with_ghosts(self):
1415
1288
        """Return the next found ancestors, with ghosts split out.
1416
1289
 
1459
1332
        parents_of_found = set()
1460
1333
        # revisions may contain nodes that point to other nodes in revisions:
1461
1334
        # we want to filter them out.
1462
 
        seen = self.seen
1463
 
        seen.update(revisions)
 
1335
        self.seen.update(revisions)
1464
1336
        parent_map = self._parents_provider.get_parent_map(revisions)
1465
1337
        found_revisions.update(parent_map)
1466
 
        for rev_id, parents in viewitems(parent_map):
 
1338
        for rev_id, parents in parent_map.iteritems():
1467
1339
            if parents is None:
1468
1340
                continue
1469
 
            new_found_parents = [p for p in parents if p not in seen]
 
1341
            new_found_parents = [p for p in parents if p not in self.seen]
1470
1342
            if new_found_parents:
1471
1343
                # Calling set.update() with an empty generator is actually
1472
1344
                # rather expensive.
1506
1378
            all_parents = []
1507
1379
            # We don't care if it is a ghost, since it can't be seen if it is
1508
1380
            # a ghost
1509
 
            for parent_ids in viewvalues(parent_map):
 
1381
            for parent_ids in parent_map.itervalues():
1510
1382
                all_parents.extend(parent_ids)
1511
1383
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1512
1384
            seen_ancestors.update(next_pending)
1551
1423
                    stop_rev_references[parent_id] += 1
1552
1424
            # if only the stopped revisions reference it, the ref count will be
1553
1425
            # 0 after this loop
1554
 
            for parents in viewvalues(self._current_parents):
 
1426
            for parents in self._current_parents.itervalues():
1555
1427
                for parent_id in parents:
1556
1428
                    try:
1557
1429
                        stop_rev_references[parent_id] -= 1
1558
1430
                    except KeyError:
1559
1431
                        pass
1560
1432
            stop_parents = set()
1561
 
            for rev_id, refs in viewitems(stop_rev_references):
 
1433
            for rev_id, refs in stop_rev_references.iteritems():
1562
1434
                if refs == 0:
1563
1435
                    stop_parents.add(rev_id)
1564
1436
            self._next_query.difference_update(stop_parents)
1591
1463
            return revs, ghosts
1592
1464
 
1593
1465
 
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
 
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)
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 viewitems(parent_map):
 
1649
    for child, parents in parent_map.iteritems():
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 {h[0] for h in head_keys}
 
1695
        return set([h[0] for h in head_keys])
1696
1696
 
1697
1697
    def merge_sort(self, tip_revision):
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]
 
1698
        return self._graph.merge_sort((tip_revision,))
 
1699
 
 
1700
 
 
1701
_counters = [0,0,0,0,0,0,0]
1708
1702
try:
1709
 
    from ._known_graph_pyx import KnownGraph
1710
 
except ImportError as e:
 
1703
    from bzrlib._known_graph_pyx import KnownGraph
 
1704
except ImportError, e:
1711
1705
    osutils.failed_to_load_extension(e)
1712
 
    from ._known_graph_py import KnownGraph
 
1706
    from bzrlib._known_graph_py import KnownGraph