/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: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

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 __future__ import absolute_import
21
 
 
22
 
try:
23
 
    from collections.abc import deque
24
 
except ImportError:  # python < 3.7
25
 
    from collections import deque
26
 
from . import (
 
20
from collections import deque
 
21
from bzrlib import (
27
22
    errors,
28
23
    revision,
29
24
    )
30
 
from .sixish import (
31
 
    viewitems,
32
 
    viewvalues,
33
 
    )
34
25
 
35
26
 
36
27
class _KnownGraphNode(object):
88
79
          child_keys,
89
80
        """
90
81
        nodes = self._nodes
91
 
        for key, parent_keys in viewitems(parent_map):
 
82
        for key, parent_keys in parent_map.iteritems():
92
83
            if key in nodes:
93
84
                node = nodes[key]
94
85
                node.parent_keys = parent_keys
104
95
                parent_node.child_keys.append(key)
105
96
 
106
97
    def _find_tails(self):
107
 
        return [node for node in viewvalues(self._nodes)
 
98
        return [node for node in self._nodes.itervalues()
108
99
                if not node.parent_keys]
109
100
 
110
101
    def _find_tips(self):
111
 
        return [node for node in viewvalues(self._nodes)
112
 
                if not node.child_keys]
 
102
        return [node for node in self._nodes.itervalues()
 
103
                      if not node.child_keys]
113
104
 
114
105
    def _find_gdfo(self):
115
106
        nodes = self._nodes
147
138
 
148
139
        If this fills in a ghost, then the gdfos of all children will be
149
140
        updated accordingly.
150
 
 
 
141
        
151
142
        :param key: The node being added. If this is a duplicate, this is a
152
143
            no-op.
153
144
        :param parent_keys: The parents of the given node.
166
157
                parent_keys = list(parent_keys)
167
158
                existing_parent_keys = list(node.parent_keys)
168
159
                if parent_keys == existing_parent_keys:
169
 
                    return  # Identical content
 
160
                    return # Identical content
170
161
                else:
171
 
                    raise ValueError(
172
 
                        'Parent key mismatch, existing node %s'
 
162
                    raise ValueError('Parent key mismatch, existing node %s'
173
163
                        ' has parents of %s not %s'
174
164
                        % (key, existing_parent_keys, parent_keys))
175
165
        else:
242
232
        seen = set()
243
233
        pending = []
244
234
        min_gdfo = None
245
 
        for node in viewvalues(candidate_nodes):
 
235
        for node in candidate_nodes.values():
246
236
            if node.parent_keys:
247
237
                pending.extend(node.parent_keys)
248
238
            if min_gdfo is None or node.gdfo < min_gdfo:
269
259
 
270
260
        All parents must occur before all children.
271
261
        """
272
 
        for node in viewvalues(self._nodes):
 
262
        for node in self._nodes.itervalues():
273
263
            if node.gdfo is None:
274
264
                raise errors.GraphCycleError(self._nodes)
275
265
        pending = self._find_tails()
323
313
 
324
314
        result = []
325
315
        for prefix in sorted(prefix_tips):
326
 
            pending = sorted(prefix_tips[prefix], key=lambda n: n.key,
 
316
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
327
317
                             reverse=True)
328
318
            while pending:
329
319
                node = pending.pop()
345
335
 
346
336
    def merge_sort(self, tip_key):
347
337
        """Compute the merge sorted graph output."""
348
 
        from breezy import tsort
 
338
        from bzrlib import tsort
349
339
        as_parent_map = dict((node.key, node.parent_keys)
350
 
                             for node in viewvalues(self._nodes)
351
 
                             if node.parent_keys is not None)
 
340
                             for node in self._nodes.itervalues()
 
341
                              if node.parent_keys is not None)
352
342
        # We intentionally always generate revnos and never force the
353
343
        # mainline_revisions
354
344
        # Strip the sequence_number that merge_sort generates
355
345
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
356
346
                for _, key, merge_depth, revno, end_of_merge
357
 
                in tsort.merge_sort(as_parent_map, tip_key,
358
 
                                    mainline_revisions=None,
359
 
                                    generate_revno=True)]
360
 
 
 
347
                 in tsort.merge_sort(as_parent_map, tip_key,
 
348
                                     mainline_revisions=None,
 
349
                                     generate_revno=True)]
 
350
    
361
351
    def get_parent_keys(self, key):
362
352
        """Get the parents for a key
363
 
 
 
353
        
364
354
        Returns a list containg the parents keys. If the key is a ghost,
365
355
        None is returned. A KeyError will be raised if the key is not in
366
356
        the graph.
367
 
 
 
357
        
368
358
        :param keys: Key to check (eg revision_id)
369
359
        :return: A list of parents
370
360
        """
372
362
 
373
363
    def get_child_keys(self, key):
374
364
        """Get the children for a key
375
 
 
 
365
        
376
366
        Returns a list containg the children keys. A KeyError will be raised
377
367
        if the key is not in the graph.
378
 
 
 
368
        
379
369
        :param keys: Key to check (eg revision_id)
380
370
        :return: A list of children
381
371
        """