1
# Copyright (C) 2009 Canonical Ltd
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.
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.
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
17
"""Implementation of Graph algorithms when we have already loaded everything.
26
class _KnownGraphNode(object):
27
"""Represents a single object in the known graph."""
29
__slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
31
def __init__(self, key, parent_keys):
33
self.parent_keys = parent_keys
35
# Greatest distance from origin
39
return '%s(%s gdfo:%s par:%s child:%s)' % (
40
self.__class__.__name__, self.key, self.gdfo,
41
self.parent_keys, self.child_keys)
44
class _MergeSortNode(object):
45
"""Information about a specific node in the merge graph."""
47
__slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
49
def __init__(self, key, merge_depth, revno, end_of_merge):
51
self.merge_depth = merge_depth
53
self.end_of_merge = end_of_merge
56
class KnownGraph(object):
57
"""This is a class which assumes we already know the full graph."""
59
def __init__(self, parent_map, do_cache=True):
60
"""Create a new KnownGraph instance.
62
:param parent_map: A dictionary mapping key => parent_keys
65
# Maps {sorted(revision_id, revision_id): heads}
66
self._known_heads = {}
67
self.do_cache = do_cache
68
self._initialize_nodes(parent_map)
71
def _initialize_nodes(self, parent_map):
72
"""Populate self._nodes.
74
After this has finished:
75
- self._nodes will have an entry for every entry in parent_map.
76
- ghosts will have a parent_keys = None,
77
- all nodes found will also have .child_keys populated with all known
81
for key, parent_keys in parent_map.iteritems():
84
node.parent_keys = parent_keys
86
node = _KnownGraphNode(key, parent_keys)
88
for parent_key in parent_keys:
90
parent_node = nodes[parent_key]
92
parent_node = _KnownGraphNode(parent_key, None)
93
nodes[parent_key] = parent_node
94
parent_node.child_keys.append(key)
96
def _find_tails(self):
97
return [node for node in self._nodes.itervalues()
98
if not node.parent_keys]
100
def _find_gdfo(self):
102
known_parent_gdfos = {}
105
for node in self._find_tails():
111
for child_key in node.child_keys:
112
child = nodes[child_key]
113
if child_key in known_parent_gdfos:
114
known_gdfo = known_parent_gdfos[child_key] + 1
119
if child.gdfo is None or node.gdfo + 1 > child.gdfo:
120
child.gdfo = node.gdfo + 1
121
if known_gdfo == len(child.parent_keys):
122
# We are the last parent updating that node, we can
123
# continue from there
124
pending.append(child)
126
del known_parent_gdfos[child_key]
128
# Update known_parent_gdfos for a key we couldn't process
129
known_parent_gdfos[child_key] = known_gdfo
131
def heads(self, keys):
132
"""Return the heads from amongst keys.
134
This is done by searching the ancestries of each key. Any key that is
135
reachable from another key is not returned; all the others are.
137
This operation scales with the relative depth between any two keys. It
138
uses gdfo to avoid walking all ancestry.
140
:param keys: An iterable of keys.
141
:return: A set of the heads. Note that as a set there is no ordering
142
information. Callers will need to filter their input to create
143
order if they need it.
145
candidate_nodes = dict((key, self._nodes[key]) for key in keys)
146
if revision.NULL_REVISION in candidate_nodes:
147
# NULL_REVISION is only a head if it is the only entry
148
candidate_nodes.pop(revision.NULL_REVISION)
149
if not candidate_nodes:
150
return frozenset([revision.NULL_REVISION])
151
if len(candidate_nodes) < 2:
152
# No or only one candidate
153
return frozenset(candidate_nodes)
154
heads_key = frozenset(candidate_nodes)
155
# Do we have a cached result ?
157
heads = self._known_heads[heads_key]
161
# Let's compute the heads
165
for node in candidate_nodes.values():
167
pending.extend(node.parent_keys)
168
if min_gdfo is None or node.gdfo < min_gdfo:
172
node_key = pending.pop()
174
# node already appears in some ancestry
177
node = nodes[node_key]
178
if node.gdfo <= min_gdfo:
181
pending.extend(node.parent_keys)
182
heads = heads_key.difference(seen)
184
self._known_heads[heads_key] = heads
188
"""Return the nodes in topological order.
190
All parents must occur before all children.
192
for node in self._nodes.itervalues():
193
if node.gdfo is None:
194
raise errors.GraphCycleError(self._nodes)
195
pending = self._find_tails()
196
pending_pop = pending.pop
197
pending_append = pending.append
200
topo_order_append = topo_order.append
202
num_seen_parents = dict.fromkeys(self._nodes, 0)
205
if node.parent_keys is not None:
206
# We don't include ghost parents
207
topo_order_append(node.key)
208
for child_key in node.child_keys:
209
child_node = self._nodes[child_key]
210
seen_parents = num_seen_parents[child_key] + 1
211
if seen_parents == len(child_node.parent_keys):
212
# All parents have been processed, enqueue this child
213
pending_append(child_node)
214
# This has been queued up, stop tracking it
215
del num_seen_parents[child_key]
217
num_seen_parents[child_key] = seen_parents
218
# We started from the parents, so we don't need to do anymore work
221
def merge_sort(self, tip_key):
222
"""Compute the merge sorted graph output."""
223
from bzrlib import tsort
224
as_parent_map = dict((node.key, node.parent_keys)
225
for node in self._nodes.itervalues()
226
if node.parent_keys is not None)
227
# We intentionally always generate revnos and never force the
229
# Strip the sequence_number that merge_sort generates
230
return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
231
for _, key, merge_depth, revno, end_of_merge
232
in tsort.merge_sort(as_parent_map, tip_key,
233
mainline_revisions=None,
234
generate_revno=True)]
added
removed
bzrlib/_known_graph_py.py
