/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-05-06 02:13:25 UTC
  • mfrom: (7490.7.21 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200506021325-awbmmqu1zyorz7sj
Merge 3.1 branch.

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 __future__ import absolute_import
21
 
 
22
 
import collections
 
20
try:
 
21
    from collections.abc import deque
 
22
except ImportError:  # python < 3.7
 
23
    from collections import deque
23
24
from . import (
24
25
    errors,
25
26
    revision,
26
27
    )
27
 
from .sixish import (
28
 
    viewitems,
29
 
    viewvalues,
30
 
    )
31
28
 
32
29
 
33
30
class _KnownGraphNode(object):
85
82
          child_keys,
86
83
        """
87
84
        nodes = self._nodes
88
 
        for key, parent_keys in viewitems(parent_map):
 
85
        for key, parent_keys in parent_map.items():
89
86
            if key in nodes:
90
87
                node = nodes[key]
91
88
                node.parent_keys = parent_keys
101
98
                parent_node.child_keys.append(key)
102
99
 
103
100
    def _find_tails(self):
104
 
        return [node for node in viewvalues(self._nodes)
 
101
        return [node for node in self._nodes.values()
105
102
                if not node.parent_keys]
106
103
 
107
104
    def _find_tips(self):
108
 
        return [node for node in viewvalues(self._nodes)
109
 
                      if not node.child_keys]
 
105
        return [node for node in self._nodes.values()
 
106
                if not node.child_keys]
110
107
 
111
108
    def _find_gdfo(self):
112
109
        nodes = self._nodes
144
141
 
145
142
        If this fills in a ghost, then the gdfos of all children will be
146
143
        updated accordingly.
147
 
        
 
144
 
148
145
        :param key: The node being added. If this is a duplicate, this is a
149
146
            no-op.
150
147
        :param parent_keys: The parents of the given node.
163
160
                parent_keys = list(parent_keys)
164
161
                existing_parent_keys = list(node.parent_keys)
165
162
                if parent_keys == existing_parent_keys:
166
 
                    return # Identical content
 
163
                    return  # Identical content
167
164
                else:
168
 
                    raise ValueError('Parent key mismatch, existing node %s'
 
165
                    raise ValueError(
 
166
                        'Parent key mismatch, existing node %s'
169
167
                        ' has parents of %s not %s'
170
168
                        % (key, existing_parent_keys, parent_keys))
171
169
        else:
192
190
        # We use a deque rather than a simple list stack, to go for BFD rather
193
191
        # than DFD. So that if a longer path is possible, we walk it before we
194
192
        # get to the final child
195
 
        pending = collections.deque([node])
 
193
        pending = deque([node])
196
194
        while pending:
197
195
            node = pending.popleft()
198
196
            next_gdfo = node.gdfo + 1
238
236
        seen = set()
239
237
        pending = []
240
238
        min_gdfo = None
241
 
        for node in viewvalues(candidate_nodes):
 
239
        for node in candidate_nodes.values():
242
240
            if node.parent_keys:
243
241
                pending.extend(node.parent_keys)
244
242
            if min_gdfo is None or node.gdfo < min_gdfo:
265
263
 
266
264
        All parents must occur before all children.
267
265
        """
268
 
        for node in viewvalues(self._nodes):
 
266
        for node in self._nodes.values():
269
267
            if node.gdfo is None:
270
268
                raise errors.GraphCycleError(self._nodes)
271
269
        pending = self._find_tails()
319
317
 
320
318
        result = []
321
319
        for prefix in sorted(prefix_tips):
322
 
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
320
            pending = sorted(prefix_tips[prefix], key=lambda n: n.key,
323
321
                             reverse=True)
324
322
            while pending:
325
323
                node = pending.pop()
343
341
        """Compute the merge sorted graph output."""
344
342
        from breezy import tsort
345
343
        as_parent_map = dict((node.key, node.parent_keys)
346
 
                             for node in viewvalues(self._nodes)
347
 
                              if node.parent_keys is not None)
 
344
                             for node in self._nodes.values()
 
345
                             if node.parent_keys is not None)
348
346
        # We intentionally always generate revnos and never force the
349
347
        # mainline_revisions
350
348
        # Strip the sequence_number that merge_sort generates
351
349
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
352
350
                for _, key, merge_depth, revno, end_of_merge
353
 
                 in tsort.merge_sort(as_parent_map, tip_key,
354
 
                                     mainline_revisions=None,
355
 
                                     generate_revno=True)]
356
 
    
 
351
                in tsort.merge_sort(as_parent_map, tip_key,
 
352
                                    mainline_revisions=None,
 
353
                                    generate_revno=True)]
 
354
 
357
355
    def get_parent_keys(self, key):
358
356
        """Get the parents for a key
359
 
        
 
357
 
360
358
        Returns a list containg the parents keys. If the key is a ghost,
361
359
        None is returned. A KeyError will be raised if the key is not in
362
360
        the graph.
363
 
        
 
361
 
364
362
        :param keys: Key to check (eg revision_id)
365
363
        :return: A list of parents
366
364
        """
368
366
 
369
367
    def get_child_keys(self, key):
370
368
        """Get the children for a key
371
 
        
 
369
 
372
370
        Returns a list containg the children keys. A KeyError will be raised
373
371
        if the key is not in the graph.
374
 
        
 
372
 
375
373
        :param keys: Key to check (eg revision_id)
376
374
        :return: A list of children
377
375
        """