← 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: 2009-03-27 22:29:55 UTC
  • mto: (3735.39.2 clean)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090327222955-utifmfm888zerixt
Implement apply_delta_to_source which doesn't have to malloc another string.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 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,
23
22
    revision,
 
23
    symbol_versioning,
24
24
    trace,
 
25
    tsort,
25
26
    )
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
 
@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
 
    
 
67
 
 
68
class _StackedParentsProvider(object):
 
69
 
77
70
    def __init__(self, parent_providers):
78
71
        self._parent_providers = parent_providers
79
72
 
80
73
    def __repr__(self):
81
 
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
 
74
        return "_StackedParentsProvider(%r)" % self._parent_providers
82
75
 
83
76
    def get_parent_map(self, keys):
84
77
        """Get a mapping of keys => parents
155
148
        return dict(self._cache)
156
149
 
157
150
    def get_parent_map(self, keys):
158
 
        """See StackedParentsProvider.get_parent_map."""
 
151
        """See _StackedParentsProvider.get_parent_map."""
159
152
        cache = self._cache
160
153
        if cache is None:
161
154
            cache = self._get_parent_map(keys)
311
304
        # get there.
312
305
        return known_revnos[cur_tip] + num_steps
313
306
 
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
 
 
335
307
    def find_unique_ancestors(self, unique_revision, common_revisions):
336
308
        """Find the unique ancestors for a revision versus others.
337
309
 
926
898
        An ancestor may sort after a descendant if the relationship is not
927
899
        visible in the supplied list of revisions.
928
900
        """
929
 
        from bzrlib import tsort
930
901
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
902
        return sorter.iter_topo_order()
932
903
 
1489
1460
 
1490
1461
        The recipe allows reconstruction of the same results at a later date
1491
1462
        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
 
1463
        of keys to start and and to stop at. In order to give reproducible
1493
1464
        results when ghosts are encountered by a search they are automatically
1494
1465
        added to the exclude list (or else ghost filling may alter the
1495
1466
        results).
1515
1486
        return self._keys
1516
1487
 
1517
1488
    def is_empty(self):
1518
 
        """Return false if the search lists 1 or more revisions."""
 
1489
        """Return true if the search lists 1 or more revisions."""
1519
1490
        return self._recipe[3] == 0
1520
1491
 
1521
1492
    def refine(self, seen, referenced):
1585
1556
    def _get_keys(self, graph):
1586
1557
        NULL_REVISION = revision.NULL_REVISION
1587
1558
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1588
 
                if key != NULL_REVISION and parents is not None]
 
1559
                if key != NULL_REVISION]
1589
1560
        return keys
1590
1561
 
1591
1562
    def is_empty(self):
1592
 
        """Return false if the search lists 1 or more revisions."""
 
1563
        """Return true if the search lists 1 or more revisions."""
1593
1564
        if revision.NULL_REVISION in self.heads:
1594
1565
            return len(self.heads) == 1
1595
1566
        else:
1677
1648
            removed.add(node)
1678
1649
 
1679
1650
    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