← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-08-03 07:15:11 UTC
  • mfrom: (4580.1.2 408199-check-2a)
  • Revision ID: pqm@pqm.ubuntu.com-20090803071511-dwb041qzak0vjzdk
(mbp) check blackbox tests now handle the root being included in the
        file-id count

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, 2008, 2009 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,
24
23
    trace,
 
24
    tsort,
25
25
    )
26
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
311
311
        # get there.
312
312
        return known_revnos[cur_tip] + num_steps
313
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
 
 
335
314
    def find_unique_ancestors(self, unique_revision, common_revisions):
336
315
        """Find the unique ancestors for a revision versus others.
337
316
 
926
905
        An ancestor may sort after a descendant if the relationship is not
927
906
        visible in the supplied list of revisions.
928
907
        """
929
 
        from bzrlib import tsort
930
908
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
909
        return sorter.iter_topo_order()
932
910
 
1679
1657
    return result
1680
1658
 
1681
1659
 
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
1660
_counters = [0,0,0,0,0,0,0]
1702
1661
try:
1703
1662
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
1705
 
    osutils.failed_to_load_extension(e)
 
1663
except ImportError:
1706
1664
    from bzrlib._known_graph_py import KnownGraph