/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-11-17 17:17:02 UTC
  • mto: This revision was merged to the branch mainline in revision 7187.
  • Revision ID: jelmer@jelmer.uk-20181117171702-4tm0yznbaw3rq3es
More beees.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/_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
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()
103
 
                      if not node.child_keys]
 
108
        return [node for node in viewvalues(self._nodes)
 
109
                if not node.child_keys]
104
110
 
105
111
    def _find_gdfo(self):
106
112
        nodes = self._nodes
138
144
 
139
145
        If this fills in a ghost, then the gdfos of all children will be
140
146
        updated accordingly.
141
 
        
 
147
 
142
148
        :param key: The node being added. If this is a duplicate, this is a
143
149
            no-op.
144
150
        :param parent_keys: The parents of the given node.
157
163
                parent_keys = list(parent_keys)
158
164
                existing_parent_keys = list(node.parent_keys)
159
165
                if parent_keys == existing_parent_keys:
160
 
                    return # Identical content
 
166
                    return  # Identical content
161
167
                else:
162
 
                    raise ValueError('Parent key mismatch, existing node %s'
 
168
                    raise ValueError(
 
169
                        'Parent key mismatch, existing node %s'
163
170
                        ' has parents of %s not %s'
164
171
                        % (key, existing_parent_keys, parent_keys))
165
172
        else:
186
193
        # We use a deque rather than a simple list stack, to go for BFD rather
187
194
        # than DFD. So that if a longer path is possible, we walk it before we
188
195
        # get to the final child
189
 
        pending = deque([node])
 
196
        pending = collections.deque([node])
190
197
        while pending:
191
198
            node = pending.popleft()
192
199
            next_gdfo = node.gdfo + 1
232
239
        seen = set()
233
240
        pending = []
234
241
        min_gdfo = None
235
 
        for node in candidate_nodes.values():
 
242
        for node in viewvalues(candidate_nodes):
236
243
            if node.parent_keys:
237
244
                pending.extend(node.parent_keys)
238
245
            if min_gdfo is None or node.gdfo < min_gdfo:
259
266
 
260
267
        All parents must occur before all children.
261
268
        """
262
 
        for node in self._nodes.itervalues():
 
269
        for node in viewvalues(self._nodes):
263
270
            if node.gdfo is None:
264
271
                raise errors.GraphCycleError(self._nodes)
265
272
        pending = self._find_tails()
313
320
 
314
321
        result = []
315
322
        for prefix in sorted(prefix_tips):
316
 
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
323
            pending = sorted(prefix_tips[prefix], key=lambda n: n.key,
317
324
                             reverse=True)
318
325
            while pending:
319
326
                node = pending.pop()
335
342
 
336
343
    def merge_sort(self, tip_key):
337
344
        """Compute the merge sorted graph output."""
338
 
        from bzrlib import tsort
 
345
        from breezy import tsort
339
346
        as_parent_map = dict((node.key, node.parent_keys)
340
 
                             for node in self._nodes.itervalues()
341
 
                              if node.parent_keys is not None)
 
347
                             for node in viewvalues(self._nodes)
 
348
                             if node.parent_keys is not None)
342
349
        # We intentionally always generate revnos and never force the
343
350
        # mainline_revisions
344
351
        # Strip the sequence_number that merge_sort generates
345
352
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
346
353
                for _, key, merge_depth, revno, end_of_merge
347
 
                 in tsort.merge_sort(as_parent_map, tip_key,
348
 
                                     mainline_revisions=None,
349
 
                                     generate_revno=True)]
350
 
    
 
354
                in tsort.merge_sort(as_parent_map, tip_key,
 
355
                                    mainline_revisions=None,
 
356
                                    generate_revno=True)]
 
357
 
351
358
    def get_parent_keys(self, key):
352
359
        """Get the parents for a key
353
 
        
 
360
 
354
361
        Returns a list containg the parents keys. If the key is a ghost,
355
362
        None is returned. A KeyError will be raised if the key is not in
356
363
        the graph.
357
 
        
 
364
 
358
365
        :param keys: Key to check (eg revision_id)
359
366
        :return: A list of parents
360
367
        """
362
369
 
363
370
    def get_child_keys(self, key):
364
371
        """Get the children for a key
365
 
        
 
372
 
366
373
        Returns a list containg the children keys. A KeyError will be raised
367
374
        if the key is not in the graph.
368
 
        
 
375
 
369
376
        :param keys: Key to check (eg revision_id)
370
377
        :return: A list of children
371
378
        """