← 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: Martin Pool
  • Date: 2009-07-10 06:46:10 UTC
  • mto: (4525.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4526.
  • Revision ID: mbp@sourcefrog.net-20090710064610-sqviksbqp5i34sw2
Rename to per_interrepository

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 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
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
 
20
 
from collections import deque
21
20
from bzrlib import (
22
 
    errors,
23
21
    revision,
24
22
    )
25
23
 
42
40
            self.parent_keys, self.child_keys)
43
41
 
44
42
 
45
 
class _MergeSortNode(object):
46
 
    """Information about a specific node in the merge graph."""
47
 
 
48
 
    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
49
 
 
50
 
    def __init__(self, key, merge_depth, revno, end_of_merge):
51
 
        self.key = key
52
 
        self.merge_depth = merge_depth
53
 
        self.revno = revno
54
 
        self.end_of_merge = end_of_merge
55
 
 
56
 
 
57
43
class KnownGraph(object):
58
44
    """This is a class which assumes we already know the full graph."""
59
45
 
63
49
        :param parent_map: A dictionary mapping key => parent_keys
64
50
        """
65
51
        self._nodes = {}
66
 
        # Maps {frozenset(revision_id, revision_id): heads}
 
52
        # Maps {sorted(revision_id, revision_id): heads}
67
53
        self._known_heads = {}
68
54
        self.do_cache = do_cache
69
55
        self._initialize_nodes(parent_map)
98
84
        return [node for node in self._nodes.itervalues()
99
85
                if not node.parent_keys]
100
86
 
101
 
    def _find_tips(self):
102
 
        return [node for node in self._nodes.itervalues()
103
 
                      if not node.child_keys]
104
 
 
105
87
    def _find_gdfo(self):
106
88
        nodes = self._nodes
107
89
        known_parent_gdfos = {}
133
115
                    # Update known_parent_gdfos for a key we couldn't process
134
116
                    known_parent_gdfos[child_key] = known_gdfo
135
117
 
136
 
    def add_node(self, key, parent_keys):
137
 
        """Add a new node to the graph.
138
 
 
139
 
        If this fills in a ghost, then the gdfos of all children will be
140
 
        updated accordingly.
141
 
        
142
 
        :param key: The node being added. If this is a duplicate, this is a
143
 
            no-op.
144
 
        :param parent_keys: The parents of the given node.
145
 
        :return: None (should we return if this was a ghost, etc?)
146
 
        """
147
 
        nodes = self._nodes
148
 
        if key in nodes:
149
 
            node = nodes[key]
150
 
            if node.parent_keys is None:
151
 
                node.parent_keys = parent_keys
152
 
                # A ghost is being added, we can no-longer trust the heads
153
 
                # cache, so clear it
154
 
                self._known_heads.clear()
155
 
            else:
156
 
                # Make sure we compare a list to a list, as tuple != list.
157
 
                parent_keys = list(parent_keys)
158
 
                existing_parent_keys = list(node.parent_keys)
159
 
                if parent_keys == existing_parent_keys:
160
 
                    return # Identical content
161
 
                else:
162
 
                    raise ValueError('Parent key mismatch, existing node %s'
163
 
                        ' has parents of %s not %s'
164
 
                        % (key, existing_parent_keys, parent_keys))
165
 
        else:
166
 
            node = _KnownGraphNode(key, parent_keys)
167
 
            nodes[key] = node
168
 
        parent_gdfo = 0
169
 
        for parent_key in parent_keys:
170
 
            try:
171
 
                parent_node = nodes[parent_key]
172
 
            except KeyError:
173
 
                parent_node = _KnownGraphNode(parent_key, None)
174
 
                # Ghosts and roots have gdfo 1
175
 
                parent_node.gdfo = 1
176
 
                nodes[parent_key] = parent_node
177
 
            if parent_gdfo < parent_node.gdfo:
178
 
                parent_gdfo = parent_node.gdfo
179
 
            parent_node.child_keys.append(key)
180
 
        node.gdfo = parent_gdfo + 1
181
 
        # Now fill the gdfo to all children
182
 
        # Note that this loop is slightly inefficient, in that we may visit the
183
 
        # same child (and its decendents) more than once, however, it is
184
 
        # 'efficient' in that we only walk to nodes that would be updated,
185
 
        # rather than all nodes
186
 
        # We use a deque rather than a simple list stack, to go for BFD rather
187
 
        # than DFD. So that if a longer path is possible, we walk it before we
188
 
        # get to the final child
189
 
        pending = deque([node])
190
 
        while pending:
191
 
            node = pending.popleft()
192
 
            next_gdfo = node.gdfo + 1
193
 
            for child_key in node.child_keys:
194
 
                child = nodes[child_key]
195
 
                if child.gdfo < next_gdfo:
196
 
                    # This child is being updated, we need to check its
197
 
                    # children
198
 
                    child.gdfo = next_gdfo
199
 
                    pending.append(child)
200
 
 
201
118
    def heads(self, keys):
202
119
        """Return the heads from amongst keys.
203
120
 
254
171
            self._known_heads[heads_key] = heads
255
172
        return heads
256
173
 
257
 
    def topo_sort(self):
258
 
        """Return the nodes in topological order.
259
 
 
260
 
        All parents must occur before all children.
261
 
        """
262
 
        for node in self._nodes.itervalues():
263
 
            if node.gdfo is None:
264
 
                raise errors.GraphCycleError(self._nodes)
265
 
        pending = self._find_tails()
266
 
        pending_pop = pending.pop
267
 
        pending_append = pending.append
268
 
 
269
 
        topo_order = []
270
 
        topo_order_append = topo_order.append
271
 
 
272
 
        num_seen_parents = dict.fromkeys(self._nodes, 0)
273
 
        while pending:
274
 
            node = pending_pop()
275
 
            if node.parent_keys is not None:
276
 
                # We don't include ghost parents
277
 
                topo_order_append(node.key)
278
 
            for child_key in node.child_keys:
279
 
                child_node = self._nodes[child_key]
280
 
                seen_parents = num_seen_parents[child_key] + 1
281
 
                if seen_parents == len(child_node.parent_keys):
282
 
                    # All parents have been processed, enqueue this child
283
 
                    pending_append(child_node)
284
 
                    # This has been queued up, stop tracking it
285
 
                    del num_seen_parents[child_key]
286
 
                else:
287
 
                    num_seen_parents[child_key] = seen_parents
288
 
        # We started from the parents, so we don't need to do anymore work
289
 
        return topo_order
290
 
 
291
 
    def gc_sort(self):
292
 
        """Return a reverse topological ordering which is 'stable'.
293
 
 
294
 
        There are a few constraints:
295
 
          1) Reverse topological (all children before all parents)
296
 
          2) Grouped by prefix
297
 
          3) 'stable' sorting, so that we get the same result, independent of
298
 
             machine, or extra data.
299
 
        To do this, we use the same basic algorithm as topo_sort, but when we
300
 
        aren't sure what node to access next, we sort them lexicographically.
301
 
        """
302
 
        tips = self._find_tips()
303
 
        # Split the tips based on prefix
304
 
        prefix_tips = {}
305
 
        for node in tips:
306
 
            if node.key.__class__ is str or len(node.key) == 1:
307
 
                prefix = ''
308
 
            else:
309
 
                prefix = node.key[0]
310
 
            prefix_tips.setdefault(prefix, []).append(node)
311
 
 
312
 
        num_seen_children = dict.fromkeys(self._nodes, 0)
313
 
 
314
 
        result = []
315
 
        for prefix in sorted(prefix_tips):
316
 
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
317
 
                             reverse=True)
318
 
            while pending:
319
 
                node = pending.pop()
320
 
                if node.parent_keys is None:
321
 
                    # Ghost node, skip it
322
 
                    continue
323
 
                result.append(node.key)
324
 
                for parent_key in sorted(node.parent_keys, reverse=True):
325
 
                    parent_node = self._nodes[parent_key]
326
 
                    seen_children = num_seen_children[parent_key] + 1
327
 
                    if seen_children == len(parent_node.child_keys):
328
 
                        # All children have been processed, enqueue this parent
329
 
                        pending.append(parent_node)
330
 
                        # This has been queued up, stop tracking it
331
 
                        del num_seen_children[parent_key]
332
 
                    else:
333
 
                        num_seen_children[parent_key] = seen_children
334
 
        return result
335
 
 
336
 
    def merge_sort(self, tip_key):
337
 
        """Compute the merge sorted graph output."""
338
 
        from bzrlib import tsort
339
 
        as_parent_map = dict((node.key, node.parent_keys)
340
 
                             for node in self._nodes.itervalues()
341
 
                              if node.parent_keys is not None)
342
 
        # We intentionally always generate revnos and never force the
343
 
        # mainline_revisions
344
 
        # Strip the sequence_number that merge_sort generates
345
 
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
346
 
                for _, key, merge_depth, revno, end_of_merge
347
 
                 in tsort.merge_sort(as_parent_map, tip_key,
348
 
                                     mainline_revisions=None,
349
 
                                     generate_revno=True)]
350
 
    
351
 
    def get_parent_keys(self, key):
352
 
        """Get the parents for a key
353
 
        
354
 
        Returns a list containg the parents keys. If the key is a ghost,
355
 
        None is returned. A KeyError will be raised if the key is not in
356
 
        the graph.
357
 
        
358
 
        :param keys: Key to check (eg revision_id)
359
 
        :return: A list of parents
360
 
        """
361
 
        return self._nodes[key].parent_keys
362
 
 
363
 
    def get_child_keys(self, key):
364
 
        """Get the children for a key
365
 
        
366
 
        Returns a list containg the children keys. A KeyError will be raised
367
 
        if the key is not in the graph.
368
 
        
369
 
        :param keys: Key to check (eg revision_id)
370
 
        :return: A list of children
371
 
        """
372
 
        return self._nodes[key].child_keys