/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: 2010-01-14 00:01:32 UTC
  • mfrom: (4957.1.1 jam-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100114000132-3p3rabnonjw3gzqb
(jam) Merge bzr.stable, bringing in bug fixes #175839, #504390

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)
132
133
                    # Update known_parent_gdfos for a key we couldn't process
133
134
                    known_parent_gdfos[child_key] = known_gdfo
134
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
 
135
201
    def heads(self, keys):
136
202
        """Return the heads from amongst keys.
137
203
 
281
347
                 in tsort.merge_sort(as_parent_map, tip_key,
282
348
                                     mainline_revisions=None,
283
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