← 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: Ian Clatworthy
  • Date: 2010-02-19 03:02:07 UTC
  • mto: (4797.23.1 integration-2.1)
  • mto: This revision was merged to the branch mainline in revision 5055.
  • Revision ID: ian.clatworthy@canonical.com-20100219030207-zpbzx021zavx4sqt
What's New in 2.1 - a summary of changes since 2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 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
20
21
from bzrlib import (
 
22
    errors,
21
23
    revision,
22
24
    )
23
25
 
40
42
            self.parent_keys, self.child_keys)
41
43
 
42
44
 
 
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
 
43
57
class KnownGraph(object):
44
58
    """This is a class which assumes we already know the full graph."""
45
59
 
49
63
        :param parent_map: A dictionary mapping key => parent_keys
50
64
        """
51
65
        self._nodes = {}
52
 
        # Maps {sorted(revision_id, revision_id): heads}
 
66
        # Maps {frozenset(revision_id, revision_id): heads}
53
67
        self._known_heads = {}
54
68
        self.do_cache = do_cache
55
69
        self._initialize_nodes(parent_map)
84
98
        return [node for node in self._nodes.itervalues()
85
99
                if not node.parent_keys]
86
100
 
 
101
    def _find_tips(self):
 
102
        return [node for node in self._nodes.itervalues()
 
103
                      if not node.child_keys]
 
104
 
87
105
    def _find_gdfo(self):
88
106
        nodes = self._nodes
89
107
        known_parent_gdfos = {}
115
133
                    # Update known_parent_gdfos for a key we couldn't process
116
134
                    known_parent_gdfos[child_key] = known_gdfo
117
135
 
 
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
 
118
201
    def heads(self, keys):
119
202
        """Return the heads from amongst keys.
120
203
 
171
254
            self._known_heads[heads_key] = heads
172
255
        return heads
173
256
 
 
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