← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

(vila) Fix test failures blocking package builds. (Vincent Ladeuil)

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 __future__ import absolute_import
 
21
 
 
22
from collections import deque
20
23
from bzrlib import (
21
24
    errors,
22
25
    revision,
62
65
        :param parent_map: A dictionary mapping key => parent_keys
63
66
        """
64
67
        self._nodes = {}
65
 
        # Maps {sorted(revision_id, revision_id): heads}
 
68
        # Maps {frozenset(revision_id, revision_id): heads}
66
69
        self._known_heads = {}
67
70
        self.do_cache = do_cache
68
71
        self._initialize_nodes(parent_map)
97
100
        return [node for node in self._nodes.itervalues()
98
101
                if not node.parent_keys]
99
102
 
 
103
    def _find_tips(self):
 
104
        return [node for node in self._nodes.itervalues()
 
105
                      if not node.child_keys]
 
106
 
100
107
    def _find_gdfo(self):
101
108
        nodes = self._nodes
102
109
        known_parent_gdfos = {}
128
135
                    # Update known_parent_gdfos for a key we couldn't process
129
136
                    known_parent_gdfos[child_key] = known_gdfo
130
137
 
 
138
    def add_node(self, key, parent_keys):
 
139
        """Add a new node to the graph.
 
140
 
 
141
        If this fills in a ghost, then the gdfos of all children will be
 
142
        updated accordingly.
 
143
        
 
144
        :param key: The node being added. If this is a duplicate, this is a
 
145
            no-op.
 
146
        :param parent_keys: The parents of the given node.
 
147
        :return: None (should we return if this was a ghost, etc?)
 
148
        """
 
149
        nodes = self._nodes
 
150
        if key in nodes:
 
151
            node = nodes[key]
 
152
            if node.parent_keys is None:
 
153
                node.parent_keys = parent_keys
 
154
                # A ghost is being added, we can no-longer trust the heads
 
155
                # cache, so clear it
 
156
                self._known_heads.clear()
 
157
            else:
 
158
                # Make sure we compare a list to a list, as tuple != list.
 
159
                parent_keys = list(parent_keys)
 
160
                existing_parent_keys = list(node.parent_keys)
 
161
                if parent_keys == existing_parent_keys:
 
162
                    return # Identical content
 
163
                else:
 
164
                    raise ValueError('Parent key mismatch, existing node %s'
 
165
                        ' has parents of %s not %s'
 
166
                        % (key, existing_parent_keys, parent_keys))
 
167
        else:
 
168
            node = _KnownGraphNode(key, parent_keys)
 
169
            nodes[key] = node
 
170
        parent_gdfo = 0
 
171
        for parent_key in parent_keys:
 
172
            try:
 
173
                parent_node = nodes[parent_key]
 
174
            except KeyError:
 
175
                parent_node = _KnownGraphNode(parent_key, None)
 
176
                # Ghosts and roots have gdfo 1
 
177
                parent_node.gdfo = 1
 
178
                nodes[parent_key] = parent_node
 
179
            if parent_gdfo < parent_node.gdfo:
 
180
                parent_gdfo = parent_node.gdfo
 
181
            parent_node.child_keys.append(key)
 
182
        node.gdfo = parent_gdfo + 1
 
183
        # Now fill the gdfo to all children
 
184
        # Note that this loop is slightly inefficient, in that we may visit the
 
185
        # same child (and its decendents) more than once, however, it is
 
186
        # 'efficient' in that we only walk to nodes that would be updated,
 
187
        # rather than all nodes
 
188
        # We use a deque rather than a simple list stack, to go for BFD rather
 
189
        # than DFD. So that if a longer path is possible, we walk it before we
 
190
        # get to the final child
 
191
        pending = deque([node])
 
192
        while pending:
 
193
            node = pending.popleft()
 
194
            next_gdfo = node.gdfo + 1
 
195
            for child_key in node.child_keys:
 
196
                child = nodes[child_key]
 
197
                if child.gdfo < next_gdfo:
 
198
                    # This child is being updated, we need to check its
 
199
                    # children
 
200
                    child.gdfo = next_gdfo
 
201
                    pending.append(child)
 
202
 
131
203
    def heads(self, keys):
132
204
        """Return the heads from amongst keys.
133
205
 
218
290
        # We started from the parents, so we don't need to do anymore work
219
291
        return topo_order
220
292
 
 
293
    def gc_sort(self):
 
294
        """Return a reverse topological ordering which is 'stable'.
 
295
 
 
296
        There are a few constraints:
 
297
          1) Reverse topological (all children before all parents)
 
298
          2) Grouped by prefix
 
299
          3) 'stable' sorting, so that we get the same result, independent of
 
300
             machine, or extra data.
 
301
        To do this, we use the same basic algorithm as topo_sort, but when we
 
302
        aren't sure what node to access next, we sort them lexicographically.
 
303
        """
 
304
        tips = self._find_tips()
 
305
        # Split the tips based on prefix
 
306
        prefix_tips = {}
 
307
        for node in tips:
 
308
            if node.key.__class__ is str or len(node.key) == 1:
 
309
                prefix = ''
 
310
            else:
 
311
                prefix = node.key[0]
 
312
            prefix_tips.setdefault(prefix, []).append(node)
 
313
 
 
314
        num_seen_children = dict.fromkeys(self._nodes, 0)
 
315
 
 
316
        result = []
 
317
        for prefix in sorted(prefix_tips):
 
318
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
319
                             reverse=True)
 
320
            while pending:
 
321
                node = pending.pop()
 
322
                if node.parent_keys is None:
 
323
                    # Ghost node, skip it
 
324
                    continue
 
325
                result.append(node.key)
 
326
                for parent_key in sorted(node.parent_keys, reverse=True):
 
327
                    parent_node = self._nodes[parent_key]
 
328
                    seen_children = num_seen_children[parent_key] + 1
 
329
                    if seen_children == len(parent_node.child_keys):
 
330
                        # All children have been processed, enqueue this parent
 
331
                        pending.append(parent_node)
 
332
                        # This has been queued up, stop tracking it
 
333
                        del num_seen_children[parent_key]
 
334
                    else:
 
335
                        num_seen_children[parent_key] = seen_children
 
336
        return result
 
337
 
221
338
    def merge_sort(self, tip_key):
222
339
        """Compute the merge sorted graph output."""
223
340
        from bzrlib import tsort
232
349
                 in tsort.merge_sort(as_parent_map, tip_key,
233
350
                                     mainline_revisions=None,
234
351
                                     generate_revno=True)]
 
352
    
 
353
    def get_parent_keys(self, key):
 
354
        """Get the parents for a key
 
355
        
 
356
        Returns a list containg the parents keys. If the key is a ghost,
 
357
        None is returned. A KeyError will be raised if the key is not in
 
358
        the graph.
 
359
        
 
360
        :param keys: Key to check (eg revision_id)
 
361
        :return: A list of parents
 
362
        """
 
363
        return self._nodes[key].parent_keys
 
364
 
 
365
    def get_child_keys(self, key):
 
366
        """Get the children for a key
 
367
        
 
368
        Returns a list containg the children keys. A KeyError will be raised
 
369
        if the key is not in the graph.
 
370
        
 
371
        :param keys: Key to check (eg revision_id)
 
372
        :return: A list of children
 
373
        """
 
374
        return self._nodes[key].child_keys