← 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: John Arbash Meinel
  • Date: 2010-01-13 16:23:07 UTC
  • mto: (4634.119.7 2.0)
  • mto: This revision was merged to the branch mainline in revision 4959.
  • Revision ID: john@arbash-meinel.com-20100113162307-0bs82td16gzih827
Update the MANIFEST.in file.

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
 
349
281
                 in tsort.merge_sort(as_parent_map, tip_key,
350
282
                                     mainline_revisions=None,
351
283
                                     generate_revno=True)]
352
 
    
353
 
    def get_parent_keys(self, key):
354
 
        """Get the parents for a key
355
 
        
356
 
        Returns a list containg the parents keys. If the key is a ghost,
357
 
        None is returned. A KeyError will be raised if the key is not in
358
 
        the graph.
359
 
        
360
 
        :param keys: Key to check (eg revision_id)
361
 
        :return: A list of parents
362
 
        """
363
 
        return self._nodes[key].parent_keys
364
 
 
365
 
    def get_child_keys(self, key):
366
 
        """Get the children for a key
367
 
        
368
 
        Returns a list containg the children keys. A KeyError will be raised
369
 
        if the key is not in the graph.
370
 
        
371
 
        :param keys: Key to check (eg revision_id)
372
 
        :return: A list of children
373
 
        """
374
 
        return self._nodes[key].child_keys