/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 breezy/_known_graph_py.py

  • Committer: Jelmer Vernooij
  • Date: 2018-07-08 14:45:27 UTC
  • mto: This revision was merged to the branch mainline in revision 7036.
  • Revision ID: jelmer@jelmer.uk-20180708144527-codhlvdcdg9y0nji
Fix a bunch of merge tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
 
20
 
from collections import deque
21
 
from bzrlib import (
 
20
from __future__ import absolute_import
 
21
 
 
22
import collections
 
23
from . import (
22
24
    errors,
23
25
    revision,
24
26
    )
 
27
from .sixish import (
 
28
    viewitems,
 
29
    viewvalues,
 
30
    )
25
31
 
26
32
 
27
33
class _KnownGraphNode(object):
79
85
          child_keys,
80
86
        """
81
87
        nodes = self._nodes
82
 
        for key, parent_keys in parent_map.iteritems():
 
88
        for key, parent_keys in viewitems(parent_map):
83
89
            if key in nodes:
84
90
                node = nodes[key]
85
91
                node.parent_keys = parent_keys
95
101
                parent_node.child_keys.append(key)
96
102
 
97
103
    def _find_tails(self):
98
 
        return [node for node in self._nodes.itervalues()
 
104
        return [node for node in viewvalues(self._nodes)
99
105
                if not node.parent_keys]
100
106
 
101
107
    def _find_tips(self):
102
 
        return [node for node in self._nodes.itervalues()
 
108
        return [node for node in viewvalues(self._nodes)
103
109
                      if not node.child_keys]
104
110
 
105
111
    def _find_gdfo(self):
186
192
        # We use a deque rather than a simple list stack, to go for BFD rather
187
193
        # than DFD. So that if a longer path is possible, we walk it before we
188
194
        # get to the final child
189
 
        pending = deque([node])
 
195
        pending = collections.deque([node])
190
196
        while pending:
191
197
            node = pending.popleft()
192
198
            next_gdfo = node.gdfo + 1
232
238
        seen = set()
233
239
        pending = []
234
240
        min_gdfo = None
235
 
        for node in candidate_nodes.values():
 
241
        for node in viewvalues(candidate_nodes):
236
242
            if node.parent_keys:
237
243
                pending.extend(node.parent_keys)
238
244
            if min_gdfo is None or node.gdfo < min_gdfo:
259
265
 
260
266
        All parents must occur before all children.
261
267
        """
262
 
        for node in self._nodes.itervalues():
 
268
        for node in viewvalues(self._nodes):
263
269
            if node.gdfo is None:
264
270
                raise errors.GraphCycleError(self._nodes)
265
271
        pending = self._find_tails()
335
341
 
336
342
    def merge_sort(self, tip_key):
337
343
        """Compute the merge sorted graph output."""
338
 
        from bzrlib import tsort
 
344
        from breezy import tsort
339
345
        as_parent_map = dict((node.key, node.parent_keys)
340
 
                             for node in self._nodes.itervalues()
 
346
                             for node in viewvalues(self._nodes)
341
347
                              if node.parent_keys is not None)
342
348
        # We intentionally always generate revnos and never force the
343
349
        # mainline_revisions