← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2011-12-19 10:58:39 UTC
  • mfrom: (6383 +trunk)
  • mto: This revision was merged to the branch mainline in revision 6386.
  • Revision ID: jelmer@canonical.com-20111219105839-uji05ck4rkm1mj4j
Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007, 2008, 2009 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
26
    trace,
24
 
    tsort,
25
27
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
28
 
28
29
STEP_UNIQUE_SEARCHER_EVERY = 5
29
30
 
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
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)
 
71
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
66
72
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
73
 
71
74
class StackedParentsProvider(object):
72
75
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
 
76
 
74
77
    The providers are queries in the order of the provided parent_providers.
75
78
    """
76
 
    
 
79
 
77
80
    def __init__(self, parent_providers):
78
81
        self._parent_providers = parent_providers
79
82
 
95
98
        """
96
99
        found = {}
97
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
98
117
        for parents_provider in self._parent_providers:
99
118
            new_found = parents_provider.get_parent_map(remaining)
100
119
            found.update(new_found)
154
173
            return None
155
174
        return dict(self._cache)
156
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
 
157
187
    def get_parent_map(self, keys):
158
188
        """See StackedParentsProvider.get_parent_map."""
159
189
        cache = self._cache
183
213
            self.missing_keys.add(key)
184
214
 
185
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
 
186
233
class Graph(object):
187
234
    """Provide incremental access to revision graphs.
188
235
 
237
284
        common ancestor of all border ancestors, because this shows that it
238
285
        cannot be a descendant of any border ancestor.
239
286
 
240
 
        The scaling of this operation should be proportional to
 
287
        The scaling of this operation should be proportional to:
 
288
 
241
289
        1. The number of uncommon ancestors
242
290
        2. The number of border ancestors
243
291
        3. The length of the shortest path between a border ancestor and an
258
306
        right = searchers[1].seen
259
307
        return (left.difference(right), right.difference(left))
260
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
 
261
343
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
344
        """Find the left-hand distance to the NULL_REVISION.
263
345
 
311
393
        # get there.
312
394
        return known_revnos[cur_tip] + num_steps
313
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
 
314
417
    def find_unique_ancestors(self, unique_revision, common_revisions):
315
418
        """Find the unique ancestors for a revision versus others.
316
419
 
320
423
 
321
424
        :param unique_revision: The revision_id whose ancestry we are
322
425
            interested in.
323
 
            XXX: Would this API be better if we allowed multiple revisions on
324
 
                 to be searched here?
 
426
            (XXX: Would this API be better if we allowed multiple revisions on
 
427
            to be searched here?)
325
428
        :param common_revisions: Revision_ids of ancestries to exclude.
326
429
        :return: A set of revisions in the ancestry of unique_revision
327
430
        """
841
944
                stop.add(parent_id)
842
945
        return found
843
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
 
844
967
    def find_unique_lca(self, left_revision, right_revision,
845
968
                        count_steps=False):
846
969
        """Find a unique LCA.
898
1021
                yield (ghost, None)
899
1022
            pending = next_pending
900
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
 
901
1043
    def iter_topo_order(self, revisions):
902
1044
        """Iterate through the input revisions in topological order.
903
1045
 
905
1047
        An ancestor may sort after a descendant if the relationship is not
906
1048
        visible in the supplied list of revisions.
907
1049
        """
 
1050
        from bzrlib import tsort
908
1051
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
909
1052
        return sorter.iter_topo_order()
910
1053
 
1205
1348
        return ('_BreadthFirstSearcher(iterations=%d, %s,'
1206
1349
                ' seen=%r)' % (self._iterations, search, list(self.seen)))
1207
1350
 
1208
 
    def get_result(self):
1209
 
        """Get a SearchResult for the current state of this searcher.
 
1351
    def get_state(self):
 
1352
        """Get the current state of this searcher.
1210
1353
 
1211
 
        :return: A SearchResult for this search so far. The SearchResult is
1212
 
            static - the search can be advanced and the search result will not
1213
 
            be invalidated or altered.
 
1354
        :return: Tuple with started keys, excludes and included keys
1214
1355
        """
1215
1356
        if self._returning == 'next':
1216
1357
            # We have to know the current nodes children to be able to list the
1227
1368
            next_query = self._next_query
1228
1369
        excludes = self._stopped_keys.union(next_query)
1229
1370
        included_keys = self.seen.difference(excludes)
1230
 
        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),
1231
1383
            included_keys)
1232
1384
 
1233
1385
    def step(self):
1310
1462
        parents_of_found = set()
1311
1463
        # revisions may contain nodes that point to other nodes in revisions:
1312
1464
        # we want to filter them out.
1313
 
        self.seen.update(revisions)
 
1465
        seen = self.seen
 
1466
        seen.update(revisions)
1314
1467
        parent_map = self._parents_provider.get_parent_map(revisions)
1315
1468
        found_revisions.update(parent_map)
1316
1469
        for rev_id, parents in parent_map.iteritems():
1317
1470
            if parents is None:
1318
1471
                continue
1319
 
            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]
1320
1473
            if new_found_parents:
1321
1474
                # Calling set.update() with an empty generator is actually
1322
1475
                # rather expensive.
1441
1594
            return revs, ghosts
1442
1595
 
1443
1596
 
1444
 
class SearchResult(object):
1445
 
    """The result of a breadth first search.
1446
 
 
1447
 
    A SearchResult provides the ability to reconstruct the search or access a
1448
 
    set of the keys the search found.
1449
 
    """
1450
 
 
1451
 
    def __init__(self, start_keys, exclude_keys, key_count, keys):
1452
 
        """Create a SearchResult.
1453
 
 
1454
 
        :param start_keys: The keys the search started at.
1455
 
        :param exclude_keys: The keys the search excludes.
1456
 
        :param key_count: The total number of keys (from start to but not
1457
 
            including exclude).
1458
 
        :param keys: The keys the search found. Note that in future we may get
1459
 
            a SearchResult from a smart server, in which case the keys list is
1460
 
            not necessarily immediately available.
1461
 
        """
1462
 
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1463
 
        self._keys = frozenset(keys)
1464
 
 
1465
 
    def get_recipe(self):
1466
 
        """Return a recipe that can be used to replay this search.
1467
 
 
1468
 
        The recipe allows reconstruction of the same results at a later date
1469
 
        without knowing all the found keys. The essential elements are a list
1470
 
        of keys to start and to stop at. In order to give reproducible
1471
 
        results when ghosts are encountered by a search they are automatically
1472
 
        added to the exclude list (or else ghost filling may alter the
1473
 
        results).
1474
 
 
1475
 
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
1476
 
            revision_count). To recreate the results of this search, create a
1477
 
            breadth first searcher on the same graph starting at start_keys.
1478
 
            Then call next() (or next_with_ghosts()) repeatedly, and on every
1479
 
            result, call stop_searching_any on any keys from the exclude_keys
1480
 
            set. The revision_count value acts as a trivial cross-check - the
1481
 
            found revisions of the new search should have as many elements as
1482
 
            revision_count. If it does not, then additional revisions have been
1483
 
            ghosted since the search was executed the first time and the second
1484
 
            time.
1485
 
        """
1486
 
        return self._recipe
1487
 
 
1488
 
    def get_keys(self):
1489
 
        """Return the keys found in this search.
1490
 
 
1491
 
        :return: A set of keys.
1492
 
        """
1493
 
        return self._keys
1494
 
 
1495
 
    def is_empty(self):
1496
 
        """Return false if the search lists 1 or more revisions."""
1497
 
        return self._recipe[3] == 0
1498
 
 
1499
 
    def refine(self, seen, referenced):
1500
 
        """Create a new search by refining this search.
1501
 
 
1502
 
        :param seen: Revisions that have been satisfied.
1503
 
        :param referenced: Revision references observed while satisfying some
1504
 
            of this search.
1505
 
        """
1506
 
        start = self._recipe[1]
1507
 
        exclude = self._recipe[2]
1508
 
        count = self._recipe[3]
1509
 
        keys = self.get_keys()
1510
 
        # New heads = referenced + old heads - seen things - exclude
1511
 
        pending_refs = set(referenced)
1512
 
        pending_refs.update(start)
1513
 
        pending_refs.difference_update(seen)
1514
 
        pending_refs.difference_update(exclude)
1515
 
        # New exclude = old exclude + satisfied heads
1516
 
        seen_heads = start.intersection(seen)
1517
 
        exclude.update(seen_heads)
1518
 
        # keys gets seen removed
1519
 
        keys = keys - seen
1520
 
        # length is reduced by len(seen)
1521
 
        count -= len(seen)
1522
 
        return SearchResult(pending_refs, exclude, count, keys)
1523
 
 
1524
 
 
1525
 
class PendingAncestryResult(object):
1526
 
    """A search result that will reconstruct the ancestry for some graph heads.
1527
 
 
1528
 
    Unlike SearchResult, this doesn't hold the complete search result in
1529
 
    memory, it just holds a description of how to generate it.
1530
 
    """
1531
 
 
1532
 
    def __init__(self, heads, repo):
1533
 
        """Constructor.
1534
 
 
1535
 
        :param heads: an iterable of graph heads.
1536
 
        :param repo: a repository to use to generate the ancestry for the given
1537
 
            heads.
1538
 
        """
1539
 
        self.heads = frozenset(heads)
1540
 
        self.repo = repo
1541
 
 
1542
 
    def get_recipe(self):
1543
 
        """Return a recipe that can be used to replay this search.
1544
 
 
1545
 
        The recipe allows reconstruction of the same results at a later date.
1546
 
 
1547
 
        :seealso SearchResult.get_recipe:
1548
 
 
1549
 
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
1550
 
            To recreate this result, create a PendingAncestryResult with the
1551
 
            start_keys_set.
1552
 
        """
1553
 
        return ('proxy-search', self.heads, set(), -1)
1554
 
 
1555
 
    def get_keys(self):
1556
 
        """See SearchResult.get_keys.
1557
 
 
1558
 
        Returns all the keys for the ancestry of the heads, excluding
1559
 
        NULL_REVISION.
1560
 
        """
1561
 
        return self._get_keys(self.repo.get_graph())
1562
 
 
1563
 
    def _get_keys(self, graph):
1564
 
        NULL_REVISION = revision.NULL_REVISION
1565
 
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1566
 
                if key != NULL_REVISION and parents is not None]
1567
 
        return keys
1568
 
 
1569
 
    def is_empty(self):
1570
 
        """Return false if the search lists 1 or more revisions."""
1571
 
        if revision.NULL_REVISION in self.heads:
1572
 
            return len(self.heads) == 1
1573
 
        else:
1574
 
            return len(self.heads) == 0
1575
 
 
1576
 
    def refine(self, seen, referenced):
1577
 
        """Create a new search by refining this search.
1578
 
 
1579
 
        :param seen: Revisions that have been satisfied.
1580
 
        :param referenced: Revision references observed while satisfying some
1581
 
            of this search.
1582
 
        """
1583
 
        referenced = self.heads.union(referenced)
1584
 
        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
1585
1610
 
1586
1611
 
1587
1612
def collapse_linear_regions(parent_map):
1657
1682
    return result
1658
1683
 
1659
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
 
1660
1710
_counters = [0,0,0,0,0,0,0]
1661
1711
try:
1662
1712
    from bzrlib._known_graph_pyx import KnownGraph
1663
 
except ImportError:
 
1713
except ImportError, e:
 
1714
    osutils.failed_to_load_extension(e)
1664
1715
    from bzrlib._known_graph_py import KnownGraph