← 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: Canonical.com Patch Queue Manager
  • Date: 2009-10-13 06:08:53 UTC
  • mfrom: (4737.1.1 merge-2.0-into-devel)
  • Revision ID: pqm@pqm.ubuntu.com-20091013060853-erk2aaj80fnkrv25
(andrew) Merge lp:bzr/2.0 into lp:bzr, including fixes for #322807,
        #389413, #402623 and documentation improvements.

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 __future__ import absolute_import
21
 
 
22
 
from collections import deque
23
20
from bzrlib import (
24
21
    errors,
25
22
    revision,
65
62
        :param parent_map: A dictionary mapping key => parent_keys
66
63
        """
67
64
        self._nodes = {}
68
 
        # Maps {frozenset(revision_id, revision_id): heads}
 
65
        # Maps {sorted(revision_id, revision_id): heads}
69
66
        self._known_heads = {}
70
67
        self.do_cache = do_cache
71
68
        self._initialize_nodes(parent_map)
135
132
                    # Update known_parent_gdfos for a key we couldn't process
136
133
                    known_parent_gdfos[child_key] = known_gdfo
137
134
 
138
 
    def add_node(self, key, parent_keys):
139
 
        """Add a new node to the graph.
140
 
 
141
 
        If this fills in a ghost, then the gdfos of all children will be
142
 
        updated accordingly.
143
 
        
144
 
        :param key: The node being added. If this is a duplicate, this is a
145
 
            no-op.
146
 
        :param parent_keys: The parents of the given node.
147
 
        :return: None (should we return if this was a ghost, etc?)
148
 
        """
149
 
        nodes = self._nodes
150
 
        if key in nodes:
151
 
            node = nodes[key]
152
 
            if node.parent_keys is None:
153
 
                node.parent_keys = parent_keys
154
 
                # A ghost is being added, we can no-longer trust the heads
155
 
                # cache, so clear it
156
 
                self._known_heads.clear()
157
 
            else:
158
 
                # Make sure we compare a list to a list, as tuple != list.
159
 
                parent_keys = list(parent_keys)
160
 
                existing_parent_keys = list(node.parent_keys)
161
 
                if parent_keys == existing_parent_keys:
162
 
                    return # Identical content
163
 
                else:
164
 
                    raise ValueError('Parent key mismatch, existing node %s'
165
 
                        ' has parents of %s not %s'
166
 
                        % (key, existing_parent_keys, parent_keys))
167
 
        else:
168
 
            node = _KnownGraphNode(key, parent_keys)
169
 
            nodes[key] = node
170
 
        parent_gdfo = 0
171
 
        for parent_key in parent_keys:
172
 
            try:
173
 
                parent_node = nodes[parent_key]
174
 
            except KeyError:
175
 
                parent_node = _KnownGraphNode(parent_key, None)
176
 
                # Ghosts and roots have gdfo 1
177
 
                parent_node.gdfo = 1
178
 
                nodes[parent_key] = parent_node
179
 
            if parent_gdfo < parent_node.gdfo:
180
 
                parent_gdfo = parent_node.gdfo
181
 
            parent_node.child_keys.append(key)
182
 
        node.gdfo = parent_gdfo + 1
183
 
        # Now fill the gdfo to all children
184
 
        # Note that this loop is slightly inefficient, in that we may visit the
185
 
        # same child (and its decendents) more than once, however, it is
186
 
        # 'efficient' in that we only walk to nodes that would be updated,
187
 
        # rather than all nodes
188
 
        # We use a deque rather than a simple list stack, to go for BFD rather
189
 
        # than DFD. So that if a longer path is possible, we walk it before we
190
 
        # get to the final child
191
 
        pending = deque([node])
192
 
        while pending:
193
 
            node = pending.popleft()
194
 
            next_gdfo = node.gdfo + 1
195
 
            for child_key in node.child_keys:
196
 
                child = nodes[child_key]
197
 
                if child.gdfo < next_gdfo:
198
 
                    # This child is being updated, we need to check its
199
 
                    # children
200
 
                    child.gdfo = next_gdfo
201
 
                    pending.append(child)
202
 
 
203
135
    def heads(self, keys):
204
136
        """Return the heads from amongst keys.
205
137