← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-07-30 14:24:06 UTC
  • mfrom: (4576.1.1 export-to-dir)
  • Revision ID: pqm@pqm.ubuntu.com-20090730142406-wg8gmxpcjz4c1z00
(bialix) Allow 'bzr export' to export into an existing (but empty)
        directory

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
 
1
# Copyright (C) 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Implementation of Graph algorithms when we have already loaded everything.
 
18
"""
 
19
 
 
20
from bzrlib import (
 
21
    revision,
 
22
    )
 
23
 
 
24
 
 
25
class _KnownGraphNode(object):
 
26
    """Represents a single object in the known graph."""
 
27
 
 
28
    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
 
29
 
 
30
    def __init__(self, key, parent_keys):
 
31
        self.key = key
 
32
        self.parent_keys = parent_keys
 
33
        self.child_keys = []
 
34
        # Greatest distance from origin
 
35
        self.gdfo = None
 
36
 
 
37
    def __repr__(self):
 
38
        return '%s(%s  gdfo:%s par:%s child:%s)' % (
 
39
            self.__class__.__name__, self.key, self.gdfo,
 
40
            self.parent_keys, self.child_keys)
 
41
 
 
42
 
 
43
class KnownGraph(object):
 
44
    """This is a class which assumes we already know the full graph."""
 
45
 
 
46
    def __init__(self, parent_map, do_cache=True):
 
47
        """Create a new KnownGraph instance.
 
48
 
 
49
        :param parent_map: A dictionary mapping key => parent_keys
 
50
        """
 
51
        self._nodes = {}
 
52
        # Maps {sorted(revision_id, revision_id): heads}
 
53
        self._known_heads = {}
 
54
        self.do_cache = do_cache
 
55
        self._initialize_nodes(parent_map)
 
56
        self._find_gdfo()
 
57
 
 
58
    def _initialize_nodes(self, parent_map):
 
59
        """Populate self._nodes.
 
60
 
 
61
        After this has finished:
 
62
        - self._nodes will have an entry for every entry in parent_map.
 
63
        - ghosts will have a parent_keys = None,
 
64
        - all nodes found will also have .child_keys populated with all known
 
65
          child_keys,
 
66
        """
 
67
        nodes = self._nodes
 
68
        for key, parent_keys in parent_map.iteritems():
 
69
            if key in nodes:
 
70
                node = nodes[key]
 
71
                node.parent_keys = parent_keys
 
72
            else:
 
73
                node = _KnownGraphNode(key, parent_keys)
 
74
                nodes[key] = node
 
75
            for parent_key in parent_keys:
 
76
                try:
 
77
                    parent_node = nodes[parent_key]
 
78
                except KeyError:
 
79
                    parent_node = _KnownGraphNode(parent_key, None)
 
80
                    nodes[parent_key] = parent_node
 
81
                parent_node.child_keys.append(key)
 
82
 
 
83
    def _find_tails(self):
 
84
        return [node for node in self._nodes.itervalues()
 
85
                if not node.parent_keys]
 
86
 
 
87
    def _find_gdfo(self):
 
88
        nodes = self._nodes
 
89
        known_parent_gdfos = {}
 
90
        pending = []
 
91
 
 
92
        for node in self._find_tails():
 
93
            node.gdfo = 1
 
94
            pending.append(node)
 
95
 
 
96
        while pending:
 
97
            node = pending.pop()
 
98
            for child_key in node.child_keys:
 
99
                child = nodes[child_key]
 
100
                if child_key in known_parent_gdfos:
 
101
                    known_gdfo = known_parent_gdfos[child_key] + 1
 
102
                    present = True
 
103
                else:
 
104
                    known_gdfo = 1
 
105
                    present = False
 
106
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
 
107
                    child.gdfo = node.gdfo + 1
 
108
                if known_gdfo == len(child.parent_keys):
 
109
                    # We are the last parent updating that node, we can
 
110
                    # continue from there
 
111
                    pending.append(child)
 
112
                    if present:
 
113
                        del known_parent_gdfos[child_key]
 
114
                else:
 
115
                    # Update known_parent_gdfos for a key we couldn't process
 
116
                    known_parent_gdfos[child_key] = known_gdfo
 
117
 
 
118
    def heads(self, keys):
 
119
        """Return the heads from amongst keys.
 
120
 
 
121
        This is done by searching the ancestries of each key.  Any key that is
 
122
        reachable from another key is not returned; all the others are.
 
123
 
 
124
        This operation scales with the relative depth between any two keys. It
 
125
        uses gdfo to avoid walking all ancestry.
 
126
 
 
127
        :param keys: An iterable of keys.
 
128
        :return: A set of the heads. Note that as a set there is no ordering
 
129
            information. Callers will need to filter their input to create
 
130
            order if they need it.
 
131
        """
 
132
        candidate_nodes = dict((key, self._nodes[key]) for key in keys)
 
133
        if revision.NULL_REVISION in candidate_nodes:
 
134
            # NULL_REVISION is only a head if it is the only entry
 
135
            candidate_nodes.pop(revision.NULL_REVISION)
 
136
            if not candidate_nodes:
 
137
                return frozenset([revision.NULL_REVISION])
 
138
        if len(candidate_nodes) < 2:
 
139
            # No or only one candidate
 
140
            return frozenset(candidate_nodes)
 
141
        heads_key = frozenset(candidate_nodes)
 
142
        # Do we have a cached result ?
 
143
        try:
 
144
            heads = self._known_heads[heads_key]
 
145
            return heads
 
146
        except KeyError:
 
147
            pass
 
148
        # Let's compute the heads
 
149
        seen = set()
 
150
        pending = []
 
151
        min_gdfo = None
 
152
        for node in candidate_nodes.values():
 
153
            if node.parent_keys:
 
154
                pending.extend(node.parent_keys)
 
155
            if min_gdfo is None or node.gdfo < min_gdfo:
 
156
                min_gdfo = node.gdfo
 
157
        nodes = self._nodes
 
158
        while pending:
 
159
            node_key = pending.pop()
 
160
            if node_key in seen:
 
161
                # node already appears in some ancestry
 
162
                continue
 
163
            seen.add(node_key)
 
164
            node = nodes[node_key]
 
165
            if node.gdfo <= min_gdfo:
 
166
                continue
 
167
            if node.parent_keys:
 
168
                pending.extend(node.parent_keys)
 
169
        heads = heads_key.difference(seen)
 
170
        if self.do_cache:
 
171
            self._known_heads[heads_key] = heads
 
172
        return heads
 
173