← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2010-05-11 10:45:26 UTC
  • mto: This revision was merged to the branch mainline in revision 5225.
  • Revision ID: john@arbash-meinel.com-20100511104526-zxnstcxta22hzw2n
Implement a compiled extension for parsing the text key out of a CHKInventory value.

Related to bug #562666. This seems to shave 5-10% out of the time spent doing a complete
branch of bzr.dev/launchpad/etc.

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-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
19
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
 
22
    osutils,
22
23
    revision,
23
 
    symbol_versioning,
24
24
    trace,
25
 
    tsort,
26
25
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
28
28
STEP_UNIQUE_SEARCHER_EVERY = 5
29
29
 
60
60
        return 'DictParentsProvider(%r)' % self.ancestry
61
61
 
62
62
    def get_parent_map(self, keys):
63
 
        """See _StackedParentsProvider.get_parent_map"""
 
63
        """See StackedParentsProvider.get_parent_map"""
64
64
        ancestry = self.ancestry
65
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
66
 
67
 
 
68
 
class _StackedParentsProvider(object):
69
 
 
 
67
@deprecated_function(deprecated_in((1, 16, 0)))
 
68
def _StackedParentsProvider(*args, **kwargs):
 
69
    return StackedParentsProvider(*args, **kwargs)
 
70
 
 
71
class StackedParentsProvider(object):
 
72
    """A parents provider which stacks (or unions) multiple providers.
 
73
    
 
74
    The providers are queries in the order of the provided parent_providers.
 
75
    """
 
76
    
70
77
    def __init__(self, parent_providers):
71
78
        self._parent_providers = parent_providers
72
79
 
73
80
    def __repr__(self):
74
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
81
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
82
 
76
83
    def get_parent_map(self, keys):
77
84
        """Get a mapping of keys => parents
148
155
        return dict(self._cache)
149
156
 
150
157
    def get_parent_map(self, keys):
151
 
        """See _StackedParentsProvider.get_parent_map."""
 
158
        """See StackedParentsProvider.get_parent_map."""
152
159
        cache = self._cache
153
160
        if cache is None:
154
161
            cache = self._get_parent_map(keys)
304
311
        # get there.
305
312
        return known_revnos[cur_tip] + num_steps
306
313
 
 
314
    def find_lefthand_distances(self, keys):
 
315
        """Find the distance to null for all the keys in keys.
 
316
 
 
317
        :param keys: keys to lookup.
 
318
        :return: A dict key->distance for all of keys.
 
319
        """
 
320
        # Optimisable by concurrent searching, but a random spread should get
 
321
        # some sort of hit rate.
 
322
        result = {}
 
323
        known_revnos = []
 
324
        ghosts = []
 
325
        for key in keys:
 
326
            try:
 
327
                known_revnos.append(
 
328
                    (key, self.find_distance_to_null(key, known_revnos)))
 
329
            except errors.GhostRevisionsHaveNoRevno:
 
330
                ghosts.append(key)
 
331
        for key in ghosts:
 
332
            known_revnos.append((key, -1))
 
333
        return dict(known_revnos)
 
334
 
307
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
308
336
        """Find the unique ancestors for a revision versus others.
309
337
 
898
926
        An ancestor may sort after a descendant if the relationship is not
899
927
        visible in the supplied list of revisions.
900
928
        """
 
929
        from bzrlib import tsort
901
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
902
931
        return sorter.iter_topo_order()
903
932
 
1460
1489
 
1461
1490
        The recipe allows reconstruction of the same results at a later date
1462
1491
        without knowing all the found keys. The essential elements are a list
1463
 
        of keys to start and and to stop at. In order to give reproducible
 
1492
        of keys to start and to stop at. In order to give reproducible
1464
1493
        results when ghosts are encountered by a search they are automatically
1465
1494
        added to the exclude list (or else ghost filling may alter the
1466
1495
        results).
1486
1515
        return self._keys
1487
1516
 
1488
1517
    def is_empty(self):
1489
 
        """Return true if the search lists 1 or more revisions."""
 
1518
        """Return false if the search lists 1 or more revisions."""
1490
1519
        return self._recipe[3] == 0
1491
1520
 
1492
1521
    def refine(self, seen, referenced):
1556
1585
    def _get_keys(self, graph):
1557
1586
        NULL_REVISION = revision.NULL_REVISION
1558
1587
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1559
 
                if key != NULL_REVISION]
 
1588
                if key != NULL_REVISION and parents is not None]
1560
1589
        return keys
1561
1590
 
1562
1591
    def is_empty(self):
1563
 
        """Return true if the search lists 1 or more revisions."""
 
1592
        """Return false if the search lists 1 or more revisions."""
1564
1593
        if revision.NULL_REVISION in self.heads:
1565
1594
            return len(self.heads) == 1
1566
1595
        else:
1648
1677
            removed.add(node)
1649
1678
 
1650
1679
    return result
 
1680
 
 
1681
 
 
1682
class GraphThunkIdsToKeys(object):
 
1683
    """Forwards calls about 'ids' to be about keys internally."""
 
1684
 
 
1685
    def __init__(self, graph):
 
1686
        self._graph = graph
 
1687
 
 
1688
    def topo_sort(self):
 
1689
        return [r for (r,) in self._graph.topo_sort()]
 
1690
 
 
1691
    def heads(self, ids):
 
1692
        """See Graph.heads()"""
 
1693
        as_keys = [(i,) for i in ids]
 
1694
        head_keys = self._graph.heads(as_keys)
 
1695
        return set([h[0] for h in head_keys])
 
1696
 
 
1697
    def merge_sort(self, tip_revision):
 
1698
        return self._graph.merge_sort((tip_revision,))
 
1699
 
 
1700
 
 
1701
_counters = [0,0,0,0,0,0,0]
 
1702
try:
 
1703
    from bzrlib._known_graph_pyx import KnownGraph
 
1704
except ImportError, e:
 
1705
    osutils.failed_to_load_extension(e)
 
1706
    from bzrlib._known_graph_py import KnownGraph