/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: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

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