/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-12-21 06:03:07 UTC
  • mfrom: (4665.7.3 serve-init)
  • Revision ID: pqm@pqm.ubuntu.com-20091221060307-uvja3vdy1o6dzzy0
(mbp) example debian init script

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
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 (
21
22
    errors,
22
23
    revision,
62
63
        :param parent_map: A dictionary mapping key => parent_keys
63
64
        """
64
65
        self._nodes = {}
65
 
        # Maps {sorted(revision_id, revision_id): heads}
 
66
        # Maps {frozenset(revision_id, revision_id): heads}
66
67
        self._known_heads = {}
67
68
        self.do_cache = do_cache
68
69
        self._initialize_nodes(parent_map)
97
98
        return [node for node in self._nodes.itervalues()
98
99
                if not node.parent_keys]
99
100
 
 
101
    def _find_tips(self):
 
102
        return [node for node in self._nodes.itervalues()
 
103
                      if not node.child_keys]
 
104
 
100
105
    def _find_gdfo(self):
101
106
        nodes = self._nodes
102
107
        known_parent_gdfos = {}
128
133
                    # Update known_parent_gdfos for a key we couldn't process
129
134
                    known_parent_gdfos[child_key] = known_gdfo
130
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
 
131
201
    def heads(self, keys):
132
202
        """Return the heads from amongst keys.
133
203
 
218
288
        # We started from the parents, so we don't need to do anymore work
219
289
        return topo_order
220
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
 
221
336
    def merge_sort(self, tip_key):
222
337
        """Compute the merge sorted graph output."""
223
338
        from bzrlib import tsort
232
347
                 in tsort.merge_sort(as_parent_map, tip_key,
233
348
                                     mainline_revisions=None,
234
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