← 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: 2009-09-09 11:43:10 UTC
  • mto: (4634.37.2 prepare-2.0)
  • mto: This revision was merged to the branch mainline in revision 4689.
  • Revision ID: ian.clatworthy@canonical.com-20090909114310-glw7tv76i5gnx9pt
put rules back in Makefile supporting plain-style docs

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
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