← 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-06-18 20:25:52 UTC
  • mfrom: (4413.5.15 1.16-chk-direct)
  • Revision ID: pqm@pqm.ubuntu.com-20090618202552-xyl6tcvbxtm8bupf
(jam) Improve initial commit performance by creating a CHKMap in bulk,
        rather than via O(tree) map() calls.

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
 
258
258
        right = searchers[1].seen
259
259
        return (left.difference(right), right.difference(left))
260
260
 
261
 
    def find_descendants(self, old_key, new_key):
262
 
        """Find descendants of old_key that are ancestors of new_key."""
263
 
        child_map = self.get_child_map(self._find_descendant_ancestors(
264
 
            old_key, new_key))
265
 
        graph = Graph(DictParentsProvider(child_map))
266
 
        searcher = graph._make_breadth_first_searcher([old_key])
267
 
        list(searcher)
268
 
        return searcher.seen
269
 
 
270
 
    def _find_descendant_ancestors(self, old_key, new_key):
271
 
        """Find ancestors of new_key that may be descendants of old_key."""
272
 
        stop = self._make_breadth_first_searcher([old_key])
273
 
        descendants = self._make_breadth_first_searcher([new_key])
274
 
        for revisions in descendants:
275
 
            old_stop = stop.seen.intersection(revisions)
276
 
            descendants.stop_searching_any(old_stop)
277
 
            seen_stop = descendants.find_seen_ancestors(stop.step())
278
 
            descendants.stop_searching_any(seen_stop)
279
 
        return descendants.seen.difference(stop.seen)
280
 
 
281
 
    def get_child_map(self, keys):
282
 
        """Get a mapping from parents to children of the specified keys.
283
 
 
284
 
        This is simply the inversion of get_parent_map.  Only supplied keys
285
 
        will be discovered as children.
286
 
        :return: a dict of key:child_list for keys.
287
 
        """
288
 
        parent_map = self._parents_provider.get_parent_map(keys)
289
 
        parent_child = {}
290
 
        for child, parents in sorted(parent_map.items()):
291
 
            for parent in parents:
292
 
                parent_child.setdefault(parent, []).append(child)
293
 
        return parent_child
294
 
 
295
261
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
296
262
        """Find the left-hand distance to the NULL_REVISION.
297
263
 
345
311
        # get there.
346
312
        return known_revnos[cur_tip] + num_steps
347
313
 
348
 
    def find_lefthand_distances(self, keys):
349
 
        """Find the distance to null for all the keys in keys.
350
 
 
351
 
        :param keys: keys to lookup.
352
 
        :return: A dict key->distance for all of keys.
353
 
        """
354
 
        # Optimisable by concurrent searching, but a random spread should get
355
 
        # some sort of hit rate.
356
 
        result = {}
357
 
        known_revnos = []
358
 
        ghosts = []
359
 
        for key in keys:
360
 
            try:
361
 
                known_revnos.append(
362
 
                    (key, self.find_distance_to_null(key, known_revnos)))
363
 
            except errors.GhostRevisionsHaveNoRevno:
364
 
                ghosts.append(key)
365
 
        for key in ghosts:
366
 
            known_revnos.append((key, -1))
367
 
        return dict(known_revnos)
368
 
 
369
314
    def find_unique_ancestors(self, unique_revision, common_revisions):
370
315
        """Find the unique ancestors for a revision versus others.
371
316
 
896
841
                stop.add(parent_id)
897
842
        return found
898
843
 
899
 
    def find_lefthand_merger(self, merged_key, tip_key):
900
 
        """Find the first lefthand ancestor of tip_key that merged merged_key.
901
 
 
902
 
        We do this by first finding the descendants of merged_key, then
903
 
        walking through the lefthand ancestry of tip_key until we find a key
904
 
        that doesn't descend from merged_key.  Its child is the key that
905
 
        merged merged_key.
906
 
 
907
 
        :return: The first lefthand ancestor of tip_key to merge merged_key.
908
 
            merged_key if it is a lefthand ancestor of tip_key.
909
 
            None if no ancestor of tip_key merged merged_key.
910
 
        """
911
 
        descendants = self.find_descendants(merged_key, tip_key)
912
 
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
913
 
        last_candidate = None
914
 
        for candidate in candidate_iterator:
915
 
            if candidate not in descendants:
916
 
                return last_candidate
917
 
            last_candidate = candidate
918
 
 
919
844
    def find_unique_lca(self, left_revision, right_revision,
920
845
                        count_steps=False):
921
846
        """Find a unique LCA.
973
898
                yield (ghost, None)
974
899
            pending = next_pending
975
900
 
976
 
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
977
 
        if stop_keys is None:
978
 
            stop_keys = ()
979
 
        next_key = start_key
980
 
        def get_parents(key):
981
 
            try:
982
 
                return self._parents_provider.get_parent_map([key])[key]
983
 
            except KeyError:
984
 
                raise errors.RevisionNotPresent(next_key, self)
985
 
        while True:
986
 
            if next_key in stop_keys:
987
 
                return
988
 
            parents = get_parents(next_key)
989
 
            yield next_key
990
 
            if len(parents) == 0:
991
 
                return
992
 
            else:
993
 
                next_key = parents[0]
994
 
 
995
901
    def iter_topo_order(self, revisions):
996
902
        """Iterate through the input revisions in topological order.
997
903
 
999
905
        An ancestor may sort after a descendant if the relationship is not
1000
906
        visible in the supplied list of revisions.
1001
907
        """
1002
 
        from bzrlib import tsort
1003
908
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1004
909
        return sorter.iter_topo_order()
1005
910
 
1752
1657
    return result
1753
1658
 
1754
1659
 
1755
 
class GraphThunkIdsToKeys(object):
1756
 
    """Forwards calls about 'ids' to be about keys internally."""
1757
 
 
1758
 
    def __init__(self, graph):
1759
 
        self._graph = graph
1760
 
 
1761
 
    def topo_sort(self):
1762
 
        return [r for (r,) in self._graph.topo_sort()]
1763
 
 
1764
 
    def heads(self, ids):
1765
 
        """See Graph.heads()"""
1766
 
        as_keys = [(i,) for i in ids]
1767
 
        head_keys = self._graph.heads(as_keys)
1768
 
        return set([h[0] for h in head_keys])
1769
 
 
1770
 
    def merge_sort(self, tip_revision):
1771
 
        return self._graph.merge_sort((tip_revision,))
1772
 
 
1773
 
 
1774
1660
_counters = [0,0,0,0,0,0,0]
1775
1661
try:
1776
1662
    from bzrlib._known_graph_pyx import KnownGraph
1777
 
except ImportError, e:
1778
 
    osutils.failed_to_load_extension(e)
 
1663
except ImportError:
1779
1664
    from bzrlib._known_graph_py import KnownGraph