« back to all changes in this revision
Viewing changes to bzrlib/_known_graph_py.py
- browse files at revision 4465.1.3
- compare with another revision
- compare with revision 6020
- download diff
- download tarball
- view history from revision 4465.1.3
- Committer: Aaron Bentley
- Date: 2009-06-26 03:44:30 UTC
- mfrom: (4481 +trunk)
- mto: This revision was merged to the branch mainline in revision 4482.
- Revision ID: aaron@aaronbentley.com-20090626034430-5btbqa44ikywccsu
Merge bzr.dev into vpipe
- files renamed:
- bzrlib/_btree_serializer_c.pyx => bzrlib/_btree_serializer_pyx.pyx
- bzrlib/_dirstate_helpers_c.h => bzrlib/_dirstate_helpers_pyx.h
- bzrlib/_dirstate_helpers_c.pyx => bzrlib/_dirstate_helpers_pyx.pyx
- bzrlib/_knit_load_data_c.pyx => bzrlib/_knit_load_data_pyx.pyx
- files modified:
- .bzrignore
added
removed
bzrlib/_known_graph_py.py
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
20
import heapq
21
22
20
from bzrlib import (
23
21
revision,
24
22
)
27
25
class _KnownGraphNode(object):
28
26
"""Represents a single object in the known graph."""
29
27
30
__slots__ = ('key', 'parent_keys', 'child_keys', 'linear_dominator',
31
'gdfo', 'ancestor_of')
28
__slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
32
29
33
30
def __init__(self, key, parent_keys):
34
31
self.key = key
35
32
self.parent_keys = parent_keys
36
33
self.child_keys = []
37
# oldest ancestor, such that no parents between here and there have >1
38
# child or >1 parent.
39
self.linear_dominator = None
40
34
# Greatest distance from origin
41
35
self.gdfo = None
42
# This will become a tuple of known heads that have this node as an
43
# ancestor
44
self.ancestor_of = None
45
36
46
37
def __repr__(self):
47
return '%s(%s gdfo:%s par:%s child:%s %s)' % (
38
return '%s(%s gdfo:%s par:%s child:%s)' % (
48
39
self.__class__.__name__, self.key, self.gdfo,
49
self.parent_keys, self.child_keys,
50
self.linear_dominator)
40
self.parent_keys, self.child_keys)
51
41
52
42
53
43
class KnownGraph(object):
63
53
self._known_heads = {}
64
54
self.do_cache = do_cache
65
55
self._initialize_nodes(parent_map)
66
self._find_linear_dominators()
67
56
self._find_gdfo()
68
57
69
58
def _initialize_nodes(self, parent_map):
70
59
"""Populate self._nodes.
71
60
72
After this has finished, self._nodes will have an entry for every entry
73
in parent_map. Ghosts will have a parent_keys = None, all nodes found
74
will also have .child_keys populated with all known child_keys.
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
- self._tails will list all the nodes without parents.
75
67
"""
68
tails = self._tails = set()
76
69
nodes = self._nodes
77
70
for key, parent_keys in parent_map.iteritems():
78
71
if key in nodes:
79
72
node = nodes[key]
80
73
node.parent_keys = parent_keys
74
if parent_keys:
75
# This node has been added before being seen in parent_map
76
# (see below)
77
tails.remove(node)
81
78
else:
82
79
node = _KnownGraphNode(key, parent_keys)
83
80
nodes[key] = node
87
84
except KeyError:
88
85
parent_node = _KnownGraphNode(parent_key, None)
89
86
nodes[parent_key] = parent_node
87
# Potentially a tail, if we're wrong we'll remove it later
88
# (see above)
89
tails.add(parent_node)
90
90
parent_node.child_keys.append(key)
91
91
92
def _find_linear_dominators(self):
93
"""For each node in the set, find any linear dominators.
94
95
For any given node, the 'linear dominator' is an ancestor, such that
96
all parents between this node and that one have a single parent, and a
97
single child. So if A->B->C->D then B,C,D all have a linear dominator
98
of A.
99
100
There are two main benefits:
101
1) When walking the graph, we can jump to the nearest linear dominator,
102
rather than walking all of the nodes inbetween.
103
2) When caching heads() results, dominators give the "same" results as
104
their children. (If the dominator is a head, then the descendant is
105
a head, if the dominator is not a head, then the child isn't
106
either.)
107
"""
108
def check_node(node):
109
if node.parent_keys is None or len(node.parent_keys) != 1:
110
# This node is either a ghost, a tail, or has multiple parents
111
# It its own dominator
112
node.linear_dominator = node.key
113
return None
114
parent_node = self._nodes[node.parent_keys[0]]
115
if len(parent_node.child_keys) > 1:
116
# The parent has multiple children, so *this* node is the
117
# dominator
118
node.linear_dominator = node.key
119
return None
120
# The parent is already filled in, so add and continue
121
if parent_node.linear_dominator is not None:
122
node.linear_dominator = parent_node.linear_dominator
123
return None
124
# We don't know this node, or its parent node, so start walking to
125
# next
126
return parent_node
127
128
for node in self._nodes.itervalues():
129
# The parent is not filled in, so walk until we get somewhere
130
if node.linear_dominator is not None: #already done
131
continue
132
next_node = check_node(node)
133
if next_node is None:
134
# Nothing more needs to be done
135
continue
136
stack = []
137
while next_node is not None:
138
stack.append(node)
139
node = next_node
140
next_node = check_node(node)
141
# The stack now contains the linear chain, and 'node' should have
142
# been labeled
143
dominator = node.linear_dominator
144
while stack:
145
next_node = stack.pop()
146
next_node.linear_dominator = dominator
147
node = next_node
148
149
92
def _find_gdfo(self):
150
def find_tails():
151
return [node for node in self._nodes.itervalues()
152
if not node.parent_keys]
153
tails = find_tails()
154
todo = []
155
heappush = heapq.heappush
156
heappop = heapq.heappop
157
93
nodes = self._nodes
158
for node in tails:
94
known_parent_gdfos = {}
95
pending = []
96
97
for node in self._tails:
159
98
node.gdfo = 1
160
heappush(todo, (1, node))
161
processed = 0
162
while todo:
163
gdfo, next = heappop(todo)
164
processed += 1
165
if next.gdfo is not None and gdfo < next.gdfo:
166
# This node was reached from a longer path, we assume it was
167
# enqued correctly with the longer gdfo, so don't continue
168
# processing now
169
continue
170
next_gdfo = gdfo + 1
171
for child_key in next.child_keys:
172
child_node = nodes[child_key]
173
if child_node.gdfo is None or child_node.gdfo < next_gdfo:
174
# Only enque children when all of their parents have been
175
# resolved
176
for parent_key in child_node.parent_keys:
177
# We know that 'this' parent is counted
178
if parent_key != next.key:
179
parent_node = nodes[parent_key]
180
if parent_node.gdfo is None:
181
break
182
else:
183
child_node.gdfo = next_gdfo
184
heappush(todo, (next_gdfo, child_node))
185
186
def _get_dominators_to_nodes(self, candidate_nodes):
187
"""Get the reverse mapping from dominator_key => candidate_nodes.
188
189
As a side effect, this can also remove potential candidate nodes if we
190
determine that they share a dominator.
191
"""
192
dom_to_node = {}
193
keys_to_remove = []
194
for node in candidate_nodes.values():
195
if node.linear_dominator in dom_to_node:
196
# This node already exists, resolve which node supersedes the
197
# other
198
other_node = dom_to_node[node.linear_dominator]
199
# There should be no way that nodes sharing a dominator could
200
# 'tie' for gdfo
201
if other_node.gdfo > node.gdfo:
202
# The other node has this node as an ancestor
203
keys_to_remove.append(node.key)
204
else:
205
# Replace the other node, and set this as the new key
206
keys_to_remove.append(other_node.key)
207
dom_to_node[node.linear_dominator] = node
208
else:
209
dom_to_node[node.linear_dominator] = node
210
for key in keys_to_remove:
211
candidate_nodes.pop(key)
212
return dom_to_node
99
pending.append(node)
100
101
while pending:
102
node = pending.pop()
103
for child_key in node.child_keys:
104
child = nodes[child_key]
105
if child_key in known_parent_gdfos:
106
known_gdfo = known_parent_gdfos[child_key] + 1
107
present = True
108
else:
109
known_gdfo = 1
110
present = False
111
if child.gdfo is None or node.gdfo + 1 > child.gdfo:
112
child.gdfo = node.gdfo + 1
113
if known_gdfo == len(child.parent_keys):
114
# We are the last parent updating that node, we can
115
# continue from there
116
pending.append(child)
117
if present:
118
del known_parent_gdfos[child_key]
119
else:
120
# Update known_parent_gdfos for a key we couldn't process
121
known_parent_gdfos[child_key] = known_gdfo
213
122
214
123
def heads(self, keys):
215
124
"""Return the heads from amongst keys.
217
126
This is done by searching the ancestries of each key. Any key that is
218
127
reachable from another key is not returned; all the others are.
219
128
220
This operation scales with the relative depth between any two keys. If
221
any two keys are completely disconnected all ancestry of both sides
222
will be retrieved.
129
This operation scales with the relative depth between any two keys. It
130
uses gdfo to avoid walking all ancestry.
223
131
224
132
:param keys: An iterable of keys.
225
133
:return: A set of the heads. Note that as a set there is no ordering
231
139
# NULL_REVISION is only a head if it is the only entry
232
140
candidate_nodes.pop(revision.NULL_REVISION)
233
141
if not candidate_nodes:
234
return set([revision.NULL_REVISION])
142
return frozenset([revision.NULL_REVISION])
235
143
if len(candidate_nodes) < 2:
144
# No or only one candidate
236
145
return frozenset(candidate_nodes)
237
146
heads_key = frozenset(candidate_nodes)
238
147
if heads_key != frozenset(keys):
148
# Mention duplicates
239
149
note('%s != %s', heads_key, frozenset(keys))
150
# Do we have a cached result ?
240
151
try:
241
152
heads = self._known_heads[heads_key]
242
153
return heads
243
154
except KeyError:
244
pass # compute it ourselves
245
dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
246
if len(candidate_nodes) < 2:
247
# We shrunk candidate_nodes and determined a new head
248
return frozenset(candidate_nodes)
249
dom_heads_key = None
250
# Check the linear dominators of these keys, to see if we already
251
# know the heads answer
252
dom_heads_key = frozenset([node.linear_dominator
253
for node in candidate_nodes.itervalues()])
254
if dom_heads_key in self._known_heads:
255
# map back into the original keys
256
heads = self._known_heads[dom_heads_key]
257
heads = frozenset([dom_to_node[key].key for key in heads])
258
return heads
259
heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
155
pass
156
# Let's compute the heads
157
seen = set()
158
pending = []
159
min_gdfo = None
160
for node in candidate_nodes.values():
161
if node.parent_keys:
162
pending.extend(node.parent_keys)
163
if min_gdfo is None or node.gdfo < min_gdfo:
164
min_gdfo = node.gdfo
165
nodes = self._nodes
166
while pending:
167
node_key = pending.pop()
168
if node_key in seen:
169
# node already appears in some ancestry
170
continue
171
seen.add(node_key)
172
node = nodes[node_key]
173
if node.gdfo <= min_gdfo:
174
continue
175
if node.parent_keys:
176
pending.extend(node.parent_keys)
177
heads = heads_key.difference(seen)
260
178
if self.do_cache:
261
179
self._known_heads[heads_key] = heads
262
# Cache the dominator heads
263
if dom_heads_key is not None:
264
dom_heads = frozenset([candidate_nodes[key].linear_dominator
265
for key in heads])
266
self._known_heads[dom_heads_key] = dom_heads
267
180
return heads
268
181
269
def _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
270
queue = []
271
to_cleanup = []
272
to_cleanup_append = to_cleanup.append
273
for node in candidate_nodes.itervalues():
274
node.ancestor_of = (node.key,)
275
queue.append((-node.gdfo, node))
276
to_cleanup_append(node)
277
heapq.heapify(queue)
278
# These are nodes that we determined are 'common' that we are no longer
279
# walking
280
# Now we walk nodes until all nodes that are being walked are 'common'
281
num_candidates = len(candidate_nodes)
282
nodes = self._nodes
283
heappop = heapq.heappop
284
heappush = heapq.heappush
285
while queue and len(candidate_nodes) > 1:
286
_, node = heappop(queue)
287
next_ancestor_of = node.ancestor_of
288
if len(next_ancestor_of) == num_candidates:
289
# This node is now considered 'common'
290
# Make sure all parent nodes are marked as such
291
for parent_key in node.parent_keys:
292
parent_node = nodes[parent_key]
293
if parent_node.ancestor_of is not None:
294
parent_node.ancestor_of = next_ancestor_of
295
if node.linear_dominator != node.key:
296
parent_node = nodes[node.linear_dominator]
297
if parent_node.ancestor_of is not None:
298
parent_node.ancestor_of = next_ancestor_of
299
continue
300
if node.parent_keys is None:
301
# This is a ghost
302
continue
303
# Now project the current nodes ancestor list to the parent nodes,
304
# and queue them up to be walked
305
# Note: using linear_dominator speeds things up quite a bit
306
# enough that we actually start to be slightly faster
307
# than the default heads() implementation
308
if node.linear_dominator != node.key:
309
# We are at the tip of a long linear region
310
# We know that there is nothing between here and the tail
311
# that is interesting, so skip to the end
312
parent_keys = [node.linear_dominator]
313
else:
314
parent_keys = node.parent_keys
315
for parent_key in parent_keys:
316
if parent_key in candidate_nodes:
317
candidate_nodes.pop(parent_key)
318
if len(candidate_nodes) <= 1:
319
break
320
elif parent_key in dom_to_node:
321
orig_node = dom_to_node[parent_key]
322
if orig_node is not node:
323
if orig_node.key in candidate_nodes:
324
candidate_nodes.pop(orig_node.key)
325
if len(candidate_nodes) <= 1:
326
break
327
parent_node = nodes[parent_key]
328
ancestor_of = parent_node.ancestor_of
329
if ancestor_of is None:
330
# This node hasn't been walked yet
331
parent_node.ancestor_of = next_ancestor_of
332
# Enqueue this node
333
heappush(queue, (-parent_node.gdfo, parent_node))
334
to_cleanup_append(parent_node)
335
elif ancestor_of != next_ancestor_of:
336
# Combine to get the full set of parents
337
all_ancestors = set(ancestor_of)
338
all_ancestors.update(next_ancestor_of)
339
parent_node.ancestor_of = tuple(sorted(all_ancestors))
340
def cleanup():
341
for node in to_cleanup:
342
node.ancestor_of = None
343
cleanup()
344
return frozenset(candidate_nodes)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1