/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: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2020-08-23 01:15:41 UTC
  • mfrom: (7520.1.4 merge-3.1)
  • Revision ID: breezy.the.bot@gmail.com-20200823011541-nv0oh7nzaganx2qy
Merge lp:brz/3.1.

Merged from https://code.launchpad.net/~jelmer/brz/merge-3.1/+merge/389690

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
try:
 
21
    from collections.abc import deque
 
22
except ImportError:  # python < 3.7
 
23
    from collections import deque
 
24
from . import (
22
25
    errors,
23
26
    revision,
24
27
    )
79
82
          child_keys,
80
83
        """
81
84
        nodes = self._nodes
82
 
        for key, parent_keys in parent_map.iteritems():
 
85
        for key, parent_keys in parent_map.items():
83
86
            if key in nodes:
84
87
                node = nodes[key]
85
88
                node.parent_keys = parent_keys
95
98
                parent_node.child_keys.append(key)
96
99
 
97
100
    def _find_tails(self):
98
 
        return [node for node in self._nodes.itervalues()
 
101
        return [node for node in self._nodes.values()
99
102
                if not node.parent_keys]
100
103
 
101
104
    def _find_tips(self):
102
 
        return [node for node in self._nodes.itervalues()
103
 
                      if not node.child_keys]
 
105
        return [node for node in self._nodes.values()
 
106
                if not node.child_keys]
104
107
 
105
108
    def _find_gdfo(self):
106
109
        nodes = self._nodes
138
141
 
139
142
        If this fills in a ghost, then the gdfos of all children will be
140
143
        updated accordingly.
141
 
        
 
144
 
142
145
        :param key: The node being added. If this is a duplicate, this is a
143
146
            no-op.
144
147
        :param parent_keys: The parents of the given node.
157
160
                parent_keys = list(parent_keys)
158
161
                existing_parent_keys = list(node.parent_keys)
159
162
                if parent_keys == existing_parent_keys:
160
 
                    return # Identical content
 
163
                    return  # Identical content
161
164
                else:
162
 
                    raise ValueError('Parent key mismatch, existing node %s'
 
165
                    raise ValueError(
 
166
                        'Parent key mismatch, existing node %s'
163
167
                        ' has parents of %s not %s'
164
168
                        % (key, existing_parent_keys, parent_keys))
165
169
        else:
259
263
 
260
264
        All parents must occur before all children.
261
265
        """
262
 
        for node in self._nodes.itervalues():
 
266
        for node in self._nodes.values():
263
267
            if node.gdfo is None:
264
268
                raise errors.GraphCycleError(self._nodes)
265
269
        pending = self._find_tails()
313
317
 
314
318
        result = []
315
319
        for prefix in sorted(prefix_tips):
316
 
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
320
            pending = sorted(prefix_tips[prefix], key=lambda n: n.key,
317
321
                             reverse=True)
318
322
            while pending:
319
323
                node = pending.pop()
335
339
 
336
340
    def merge_sort(self, tip_key):
337
341
        """Compute the merge sorted graph output."""
338
 
        from bzrlib import tsort
 
342
        from breezy import tsort
339
343
        as_parent_map = dict((node.key, node.parent_keys)
340
 
                             for node in self._nodes.itervalues()
341
 
                              if node.parent_keys is not None)
 
344
                             for node in self._nodes.values()
 
345
                             if node.parent_keys is not None)
342
346
        # We intentionally always generate revnos and never force the
343
347
        # mainline_revisions
344
348
        # Strip the sequence_number that merge_sort generates
345
349
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
346
350
                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
 
    
 
351
                in tsort.merge_sort(as_parent_map, tip_key,
 
352
                                    mainline_revisions=None,
 
353
                                    generate_revno=True)]
 
354
 
351
355
    def get_parent_keys(self, key):
352
356
        """Get the parents for a key
353
 
        
 
357
 
354
358
        Returns a list containg the parents keys. If the key is a ghost,
355
359
        None is returned. A KeyError will be raised if the key is not in
356
360
        the graph.
357
 
        
 
361
 
358
362
        :param keys: Key to check (eg revision_id)
359
363
        :return: A list of parents
360
364
        """
362
366
 
363
367
    def get_child_keys(self, key):
364
368
        """Get the children for a key
365
 
        
 
369
 
366
370
        Returns a list containg the children keys. A KeyError will be raised
367
371
        if the key is not in the graph.
368
 
        
 
372
 
369
373
        :param keys: Key to check (eg revision_id)
370
374
        :return: A list of children
371
375
        """