/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 brzlib/_known_graph_py.py

  • Committer: Jelmer Vernooij
  • Date: 2017-05-21 12:41:27 UTC
  • mto: This revision was merged to the branch mainline in revision 6623.
  • Revision ID: jelmer@jelmer.uk-20170521124127-iv8etg0vwymyai6y
s/bzr/brz/ in apport config.

Show diffs side-by-side

added added

removed removed

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