← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Tarmac
  • Author(s): Vincent Ladeuil
  • Date: 2017-01-30 14:42:05 UTC
  • mfrom: (6620.1.1 trunk)
  • Revision ID: tarmac-20170130144205-r8fh2xpmiuxyozpv
Merge  2.7 into trunk including fix for bug #1657238 [r=vila]

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007 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
21
from bzrlib import (
20
22
    debug,
21
23
    errors,
 
24
    osutils,
22
25
    revision,
23
 
    symbol_versioning,
24
26
    trace,
25
 
    tsort,
26
27
    )
27
28
 
28
29
STEP_UNIQUE_SEARCHER_EVERY = 5
59
60
    def __repr__(self):
60
61
        return 'DictParentsProvider(%r)' % self.ancestry
61
62
 
 
63
    # Note: DictParentsProvider does not implement get_cached_parent_map
 
64
    #       Arguably, the data is clearly cached in memory. However, this class
 
65
    #       is mostly used for testing, and it keeps the tests clean to not
 
66
    #       change it.
 
67
 
62
68
    def get_parent_map(self, keys):
63
 
        """See _StackedParentsProvider.get_parent_map"""
 
69
        """See StackedParentsProvider.get_parent_map"""
64
70
        ancestry = self.ancestry
65
 
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
 
 
67
 
 
68
 
class _StackedParentsProvider(object):
 
71
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
72
 
 
73
 
 
74
class StackedParentsProvider(object):
 
75
    """A parents provider which stacks (or unions) multiple providers.
 
76
 
 
77
    The providers are queries in the order of the provided parent_providers.
 
78
    """
69
79
 
70
80
    def __init__(self, parent_providers):
71
81
        self._parent_providers = parent_providers
72
82
 
73
83
    def __repr__(self):
74
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
84
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
85
 
76
86
    def get_parent_map(self, keys):
77
87
        """Get a mapping of keys => parents
88
98
        """
89
99
        found = {}
90
100
        remaining = set(keys)
 
101
        # This adds getattr() overhead to each get_parent_map call. However,
 
102
        # this is StackedParentsProvider, which means we're dealing with I/O
 
103
        # (either local indexes, or remote RPCs), so CPU overhead should be
 
104
        # minimal.
 
105
        for parents_provider in self._parent_providers:
 
106
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
 
107
                                 None)
 
108
            if get_cached is None:
 
109
                continue
 
110
            new_found = get_cached(remaining)
 
111
            found.update(new_found)
 
112
            remaining.difference_update(new_found)
 
113
            if not remaining:
 
114
                break
 
115
        if not remaining:
 
116
            return found
91
117
        for parents_provider in self._parent_providers:
92
118
            new_found = parents_provider.get_parent_map(remaining)
93
119
            found.update(new_found)
147
173
            return None
148
174
        return dict(self._cache)
149
175
 
 
176
    def get_cached_parent_map(self, keys):
 
177
        """Return items from the cache.
 
178
 
 
179
        This returns the same info as get_parent_map, but explicitly does not
 
180
        invoke the supplied ParentsProvider to search for uncached values.
 
181
        """
 
182
        cache = self._cache
 
183
        if cache is None:
 
184
            return {}
 
185
        return dict([(key, cache[key]) for key in keys if key in cache])
 
186
 
150
187
    def get_parent_map(self, keys):
151
 
        """See _StackedParentsProvider.get_parent_map."""
 
188
        """See StackedParentsProvider.get_parent_map."""
152
189
        cache = self._cache
153
190
        if cache is None:
154
191
            cache = self._get_parent_map(keys)
176
213
            self.missing_keys.add(key)
177
214
 
178
215
 
 
216
class CallableToParentsProviderAdapter(object):
 
217
    """A parents provider that adapts any callable to the parents provider API.
 
218
 
 
219
    i.e. it accepts calls to self.get_parent_map and relays them to the
 
220
    callable it was constructed with.
 
221
    """
 
222
 
 
223
    def __init__(self, a_callable):
 
224
        self.callable = a_callable
 
225
 
 
226
    def __repr__(self):
 
227
        return "%s(%r)" % (self.__class__.__name__, self.callable)
 
228
 
 
229
    def get_parent_map(self, keys):
 
230
        return self.callable(keys)
 
231
 
 
232
 
179
233
class Graph(object):
180
234
    """Provide incremental access to revision graphs.
181
235
 
230
284
        common ancestor of all border ancestors, because this shows that it
231
285
        cannot be a descendant of any border ancestor.
232
286
 
233
 
        The scaling of this operation should be proportional to
 
287
        The scaling of this operation should be proportional to:
 
288
 
234
289
        1. The number of uncommon ancestors
235
290
        2. The number of border ancestors
236
291
        3. The length of the shortest path between a border ancestor and an
251
306
        right = searchers[1].seen
252
307
        return (left.difference(right), right.difference(left))
253
308
 
 
309
    def find_descendants(self, old_key, new_key):
 
310
        """Find descendants of old_key that are ancestors of new_key."""
 
311
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
312
            old_key, new_key))
 
313
        graph = Graph(DictParentsProvider(child_map))
 
314
        searcher = graph._make_breadth_first_searcher([old_key])
 
315
        list(searcher)
 
316
        return searcher.seen
 
317
 
 
318
    def _find_descendant_ancestors(self, old_key, new_key):
 
319
        """Find ancestors of new_key that may be descendants of old_key."""
 
320
        stop = self._make_breadth_first_searcher([old_key])
 
321
        descendants = self._make_breadth_first_searcher([new_key])
 
322
        for revisions in descendants:
 
323
            old_stop = stop.seen.intersection(revisions)
 
324
            descendants.stop_searching_any(old_stop)
 
325
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
326
            descendants.stop_searching_any(seen_stop)
 
327
        return descendants.seen.difference(stop.seen)
 
328
 
 
329
    def get_child_map(self, keys):
 
330
        """Get a mapping from parents to children of the specified keys.
 
331
 
 
332
        This is simply the inversion of get_parent_map.  Only supplied keys
 
333
        will be discovered as children.
 
334
        :return: a dict of key:child_list for keys.
 
335
        """
 
336
        parent_map = self._parents_provider.get_parent_map(keys)
 
337
        parent_child = {}
 
338
        for child, parents in sorted(parent_map.items()):
 
339
            for parent in parents:
 
340
                parent_child.setdefault(parent, []).append(child)
 
341
        return parent_child
 
342
 
254
343
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
255
344
        """Find the left-hand distance to the NULL_REVISION.
256
345
 
304
393
        # get there.
305
394
        return known_revnos[cur_tip] + num_steps
306
395
 
 
396
    def find_lefthand_distances(self, keys):
 
397
        """Find the distance to null for all the keys in keys.
 
398
 
 
399
        :param keys: keys to lookup.
 
400
        :return: A dict key->distance for all of keys.
 
401
        """
 
402
        # Optimisable by concurrent searching, but a random spread should get
 
403
        # some sort of hit rate.
 
404
        result = {}
 
405
        known_revnos = []
 
406
        ghosts = []
 
407
        for key in keys:
 
408
            try:
 
409
                known_revnos.append(
 
410
                    (key, self.find_distance_to_null(key, known_revnos)))
 
411
            except errors.GhostRevisionsHaveNoRevno:
 
412
                ghosts.append(key)
 
413
        for key in ghosts:
 
414
            known_revnos.append((key, -1))
 
415
        return dict(known_revnos)
 
416
 
307
417
    def find_unique_ancestors(self, unique_revision, common_revisions):
308
418
        """Find the unique ancestors for a revision versus others.
309
419
 
313
423
 
314
424
        :param unique_revision: The revision_id whose ancestry we are
315
425
            interested in.
316
 
            XXX: Would this API be better if we allowed multiple revisions on
317
 
                 to be searched here?
 
426
            (XXX: Would this API be better if we allowed multiple revisions on
 
427
            to be searched here?)
318
428
        :param common_revisions: Revision_ids of ancestries to exclude.
319
429
        :return: A set of revisions in the ancestry of unique_revision
320
430
        """
834
944
                stop.add(parent_id)
835
945
        return found
836
946
 
 
947
    def find_lefthand_merger(self, merged_key, tip_key):
 
948
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
949
 
 
950
        We do this by first finding the descendants of merged_key, then
 
951
        walking through the lefthand ancestry of tip_key until we find a key
 
952
        that doesn't descend from merged_key.  Its child is the key that
 
953
        merged merged_key.
 
954
 
 
955
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
956
            merged_key if it is a lefthand ancestor of tip_key.
 
957
            None if no ancestor of tip_key merged merged_key.
 
958
        """
 
959
        descendants = self.find_descendants(merged_key, tip_key)
 
960
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
961
        last_candidate = None
 
962
        for candidate in candidate_iterator:
 
963
            if candidate not in descendants:
 
964
                return last_candidate
 
965
            last_candidate = candidate
 
966
 
837
967
    def find_unique_lca(self, left_revision, right_revision,
838
968
                        count_steps=False):
839
969
        """Find a unique LCA.
891
1021
                yield (ghost, None)
892
1022
            pending = next_pending
893
1023
 
 
1024
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
1025
        if stop_keys is None:
 
1026
            stop_keys = ()
 
1027
        next_key = start_key
 
1028
        def get_parents(key):
 
1029
            try:
 
1030
                return self._parents_provider.get_parent_map([key])[key]
 
1031
            except KeyError:
 
1032
                raise errors.RevisionNotPresent(next_key, self)
 
1033
        while True:
 
1034
            if next_key in stop_keys:
 
1035
                return
 
1036
            parents = get_parents(next_key)
 
1037
            yield next_key
 
1038
            if len(parents) == 0:
 
1039
                return
 
1040
            else:
 
1041
                next_key = parents[0]
 
1042
 
894
1043
    def iter_topo_order(self, revisions):
895
1044
        """Iterate through the input revisions in topological order.
896
1045
 
898
1047
        An ancestor may sort after a descendant if the relationship is not
899
1048
        visible in the supplied list of revisions.
900
1049
        """
 
1050
        from bzrlib import tsort
901
1051
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
902
1052
        return sorter.iter_topo_order()
903
1053
 
1198
1348
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1199
1349
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1200
1350
 
1201
 
    def get_result(self):
1202
 
        """Get a SearchResult for the current state of this searcher.
 
1351
    def get_state(self):
 
1352
        """Get the current state of this searcher.
1203
1353
 
1204
 
        :return: A SearchResult for this search so far. The SearchResult is
1205
 
            static - the search can be advanced and the search result will not
1206
 
            be invalidated or altered.
 
1354
        :return: Tuple with started keys, excludes and included keys
1207
1355
        """
1208
1356
        if self._returning == 'next':
1209
1357
            # We have to know the current nodes children to be able to list the
1220
1368
            next_query = self._next_query
1221
1369
        excludes = self._stopped_keys.union(next_query)
1222
1370
        included_keys = self.seen.difference(excludes)
1223
 
        return SearchResult(self._started_keys, excludes, len(included_keys),
 
1371
        return self._started_keys, excludes, included_keys
 
1372
 
 
1373
    def _get_result(self):
 
1374
        """Get a SearchResult for the current state of this searcher.
 
1375
 
 
1376
        :return: A SearchResult for this search so far. The SearchResult is
 
1377
            static - the search can be advanced and the search result will not
 
1378
            be invalidated or altered.
 
1379
        """
 
1380
        from bzrlib.vf_search import SearchResult
 
1381
        (started_keys, excludes, included_keys) = self.get_state()
 
1382
        return SearchResult(started_keys, excludes, len(included_keys),
1224
1383
            included_keys)
1225
1384
 
1226
1385
    def step(self):
1303
1462
        parents_of_found = set()
1304
1463
        # revisions may contain nodes that point to other nodes in revisions:
1305
1464
        # we want to filter them out.
1306
 
        self.seen.update(revisions)
 
1465
        seen = self.seen
 
1466
        seen.update(revisions)
1307
1467
        parent_map = self._parents_provider.get_parent_map(revisions)
1308
1468
        found_revisions.update(parent_map)
1309
1469
        for rev_id, parents in parent_map.iteritems():
1310
1470
            if parents is None:
1311
1471
                continue
1312
 
            new_found_parents = [p for p in parents if p not in self.seen]
 
1472
            new_found_parents = [p for p in parents if p not in seen]
1313
1473
            if new_found_parents:
1314
1474
                # Calling set.update() with an empty generator is actually
1315
1475
                # rather expensive.
1434
1594
            return revs, ghosts
1435
1595
 
1436
1596
 
1437
 
class SearchResult(object):
1438
 
    """The result of a breadth first search.
1439
 
 
1440
 
    A SearchResult provides the ability to reconstruct the search or access a
1441
 
    set of the keys the search found.
1442
 
    """
1443
 
 
1444
 
    def __init__(self, start_keys, exclude_keys, key_count, keys):
1445
 
        """Create a SearchResult.
1446
 
 
1447
 
        :param start_keys: The keys the search started at.
1448
 
        :param exclude_keys: The keys the search excludes.
1449
 
        :param key_count: The total number of keys (from start to but not
1450
 
            including exclude).
1451
 
        :param keys: The keys the search found. Note that in future we may get
1452
 
            a SearchResult from a smart server, in which case the keys list is
1453
 
            not necessarily immediately available.
1454
 
        """
1455
 
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1456
 
        self._keys = frozenset(keys)
1457
 
 
1458
 
    def get_recipe(self):
1459
 
        """Return a recipe that can be used to replay this search.
1460
 
 
1461
 
        The recipe allows reconstruction of the same results at a later date
1462
 
        without knowing all the found keys. The essential elements are a list
1463
 
        of keys to start and to stop at. In order to give reproducible
1464
 
        results when ghosts are encountered by a search they are automatically
1465
 
        added to the exclude list (or else ghost filling may alter the
1466
 
        results).
1467
 
 
1468
 
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
1469
 
            revision_count). To recreate the results of this search, create a
1470
 
            breadth first searcher on the same graph starting at start_keys.
1471
 
            Then call next() (or next_with_ghosts()) repeatedly, and on every
1472
 
            result, call stop_searching_any on any keys from the exclude_keys
1473
 
            set. The revision_count value acts as a trivial cross-check - the
1474
 
            found revisions of the new search should have as many elements as
1475
 
            revision_count. If it does not, then additional revisions have been
1476
 
            ghosted since the search was executed the first time and the second
1477
 
            time.
1478
 
        """
1479
 
        return self._recipe
1480
 
 
1481
 
    def get_keys(self):
1482
 
        """Return the keys found in this search.
1483
 
 
1484
 
        :return: A set of keys.
1485
 
        """
1486
 
        return self._keys
1487
 
 
1488
 
    def is_empty(self):
1489
 
        """Return false if the search lists 1 or more revisions."""
1490
 
        return self._recipe[3] == 0
1491
 
 
1492
 
    def refine(self, seen, referenced):
1493
 
        """Create a new search by refining this search.
1494
 
 
1495
 
        :param seen: Revisions that have been satisfied.
1496
 
        :param referenced: Revision references observed while satisfying some
1497
 
            of this search.
1498
 
        """
1499
 
        start = self._recipe[1]
1500
 
        exclude = self._recipe[2]
1501
 
        count = self._recipe[3]
1502
 
        keys = self.get_keys()
1503
 
        # New heads = referenced + old heads - seen things - exclude
1504
 
        pending_refs = set(referenced)
1505
 
        pending_refs.update(start)
1506
 
        pending_refs.difference_update(seen)
1507
 
        pending_refs.difference_update(exclude)
1508
 
        # New exclude = old exclude + satisfied heads
1509
 
        seen_heads = start.intersection(seen)
1510
 
        exclude.update(seen_heads)
1511
 
        # keys gets seen removed
1512
 
        keys = keys - seen
1513
 
        # length is reduced by len(seen)
1514
 
        count -= len(seen)
1515
 
        return SearchResult(pending_refs, exclude, count, keys)
1516
 
 
1517
 
 
1518
 
class PendingAncestryResult(object):
1519
 
    """A search result that will reconstruct the ancestry for some graph heads.
1520
 
 
1521
 
    Unlike SearchResult, this doesn't hold the complete search result in
1522
 
    memory, it just holds a description of how to generate it.
1523
 
    """
1524
 
 
1525
 
    def __init__(self, heads, repo):
1526
 
        """Constructor.
1527
 
 
1528
 
        :param heads: an iterable of graph heads.
1529
 
        :param repo: a repository to use to generate the ancestry for the given
1530
 
            heads.
1531
 
        """
1532
 
        self.heads = frozenset(heads)
1533
 
        self.repo = repo
1534
 
 
1535
 
    def get_recipe(self):
1536
 
        """Return a recipe that can be used to replay this search.
1537
 
 
1538
 
        The recipe allows reconstruction of the same results at a later date.
1539
 
 
1540
 
        :seealso SearchResult.get_recipe:
1541
 
 
1542
 
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
1543
 
            To recreate this result, create a PendingAncestryResult with the
1544
 
            start_keys_set.
1545
 
        """
1546
 
        return ('proxy-search', self.heads, set(), -1)
1547
 
 
1548
 
    def get_keys(self):
1549
 
        """See SearchResult.get_keys.
1550
 
 
1551
 
        Returns all the keys for the ancestry of the heads, excluding
1552
 
        NULL_REVISION.
1553
 
        """
1554
 
        return self._get_keys(self.repo.get_graph())
1555
 
 
1556
 
    def _get_keys(self, graph):
1557
 
        NULL_REVISION = revision.NULL_REVISION
1558
 
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1559
 
                if key != NULL_REVISION]
1560
 
        return keys
1561
 
 
1562
 
    def is_empty(self):
1563
 
        """Return false if the search lists 1 or more revisions."""
1564
 
        if revision.NULL_REVISION in self.heads:
1565
 
            return len(self.heads) == 1
1566
 
        else:
1567
 
            return len(self.heads) == 0
1568
 
 
1569
 
    def refine(self, seen, referenced):
1570
 
        """Create a new search by refining this search.
1571
 
 
1572
 
        :param seen: Revisions that have been satisfied.
1573
 
        :param referenced: Revision references observed while satisfying some
1574
 
            of this search.
1575
 
        """
1576
 
        referenced = self.heads.union(referenced)
1577
 
        return PendingAncestryResult(referenced - seen, self.repo)
 
1597
def invert_parent_map(parent_map):
 
1598
    """Given a map from child => parents, create a map of parent=>children"""
 
1599
    child_map = {}
 
1600
    for child, parents in parent_map.iteritems():
 
1601
        for p in parents:
 
1602
            # Any given parent is likely to have only a small handful
 
1603
            # of children, many will have only one. So we avoid mem overhead of
 
1604
            # a list, in exchange for extra copying of tuples
 
1605
            if p not in child_map:
 
1606
                child_map[p] = (child,)
 
1607
            else:
 
1608
                child_map[p] = child_map[p] + (child,)
 
1609
    return child_map
1578
1610
 
1579
1611
 
1580
1612
def collapse_linear_regions(parent_map):
1648
1680
            removed.add(node)
1649
1681
 
1650
1682
    return result
 
1683
 
 
1684
 
 
1685
class GraphThunkIdsToKeys(object):
 
1686
    """Forwards calls about 'ids' to be about keys internally."""
 
1687
 
 
1688
    def __init__(self, graph):
 
1689
        self._graph = graph
 
1690
 
 
1691
    def topo_sort(self):
 
1692
        return [r for (r,) in self._graph.topo_sort()]
 
1693
 
 
1694
    def heads(self, ids):
 
1695
        """See Graph.heads()"""
 
1696
        as_keys = [(i,) for i in ids]
 
1697
        head_keys = self._graph.heads(as_keys)
 
1698
        return set([h[0] for h in head_keys])
 
1699
 
 
1700
    def merge_sort(self, tip_revision):
 
1701
        nodes = self._graph.merge_sort((tip_revision,))
 
1702
        for node in nodes:
 
1703
            node.key = node.key[0]
 
1704
        return nodes
 
1705
 
 
1706
    def add_node(self, revision, parents):
 
1707
        self._graph.add_node((revision,), [(p,) for p in parents])
 
1708
 
 
1709
 
 
1710
_counters = [0,0,0,0,0,0,0]
 
1711
try:
 
1712
    from bzrlib._known_graph_pyx import KnownGraph
 
1713
except ImportError, e:
 
1714
    osutils.failed_to_load_extension(e)
 
1715
    from bzrlib._known_graph_py import KnownGraph