← 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: Benoît Pierre
  • Date: 2009-11-02 22:24:29 UTC
  • mto: (4634.96.1 integration-2.0)
  • mto: This revision was merged to the branch mainline in revision 4798.
  • Revision ID: benoit.pierre@gmail.com-20091102222429-xqdyo6n8odh3xbbd
Small fix for handling of short option names in shellcomplete_on_options.

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
21
    errors,
23
22
    revision,
63
62
        :param parent_map: A dictionary mapping key => parent_keys
64
63
        """
65
64
        self._nodes = {}
66
 
        # Maps {frozenset(revision_id, revision_id): heads}
 
65
        # Maps {sorted(revision_id, revision_id): heads}
67
66
        self._known_heads = {}
68
67
        self.do_cache = do_cache
69
68
        self._initialize_nodes(parent_map)
133
132
                    # Update known_parent_gdfos for a key we couldn't process
134
133
                    known_parent_gdfos[child_key] = known_gdfo
135
134
 
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
135
    def heads(self, keys):
202
136
        """Return the heads from amongst keys.
203
137
 
347
281
                 in tsort.merge_sort(as_parent_map, tip_key,
348
282
                                     mainline_revisions=None,
349
283
                                     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