← 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: Andrew Bennetts
  • Date: 2009-12-03 05:57:41 UTC
  • mfrom: (4857 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4869.
  • Revision ID: andrew.bennetts@canonical.com-20091203055741-vmmg0fmjgjw2pwvu
Merge lp:bzr.

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