/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: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

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