← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

(vila) Fix test failures blocking package builds. (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
 
18
17
"""Topological sorting routines."""
19
18
 
 
19
from __future__ import absolute_import
 
20
 
20
21
 
21
22
from bzrlib import (
22
23
    errors,
177
178
        revision number sequences in the output. See the output description of
178
179
        the MergeSorter docstring for details.
179
180
    :result: See the MergeSorter docstring for details.
180
 
    node identifiers can be any hashable object, and are typically strings.
 
181
 
 
182
    Node identifiers can be any hashable object, and are typically strings.
181
183
    """
182
184
    return MergeSorter(graph, branch_tip, mainline_revisions,
183
185
        generate_revno).sorted()
459
461
            left_subtree_pushed_stack_append(False)
460
462
            pending_parents_stack_append(list(parents))
461
463
            # as we push it, check if it is the first child
 
464
            parent_info = None
462
465
            if parents:
463
466
                # node has parents, assign from the left most parent.
464
 
                parent_info = revnos[parents[0]]
 
467
                try:
 
468
                    parent_info = revnos[parents[0]]
 
469
                except KeyError:
 
470
                    # Left-hand parent is a ghost, consider it not to exist
 
471
                    pass
 
472
            if parent_info is not None:
465
473
                first_child = parent_info[1]
466
474
                parent_info[1] = False
467
475
            else:
495
503
            pending_parents_stack_pop()
496
504
 
497
505
            parents = original_graph[node_name]
 
506
            parent_revno = None
498
507
            if parents:
499
508
                # node has parents, assign from the left most parent.
500
 
                parent_revno = revnos[parents[0]][0]
 
509
                try:
 
510
                    parent_revno = revnos[parents[0]][0]
 
511
                except KeyError:
 
512
                    # left-hand parent is a ghost, treat it as not existing
 
513
                    pass
 
514
            if parent_revno is not None:
501
515
                if not first_child:
502
516
                    # not the first child, make a new branch
503
517
                    base_revno = parent_revno[0]
628
642
        self._left_subtree_pushed_stack.append(False)
629
643
        self._pending_parents_stack.append(list(parents))
630
644
        # as we push it, figure out if this is the first child
631
 
        parents = self._original_graph[node_name]
 
645
        parent_info = None
632
646
        if parents:
633
647
            # node has parents, assign from the left most parent.
634
 
            parent_info = self._revnos[parents[0]]
 
648
            try:
 
649
                parent_info = self._revnos[parents[0]]
 
650
            except KeyError:
 
651
                # Left-hand parent is a ghost, consider it not to exist
 
652
                pass
 
653
        if parent_info is not None:
635
654
            first_child = parent_info[1]
636
655
            parent_info[1] = False
637
656
        else:
655
674
        self._pending_parents_stack.pop()
656
675
 
657
676
        parents = self._original_graph[node_name]
 
677
        parent_revno = None
658
678
        if parents:
659
679
            # node has parents, assign from the left most parent.
660
 
            parent_revno = self._revnos[parents[0]][0]
 
680
            try:
 
681
                parent_revno = self._revnos[parents[0]][0]
 
682
            except KeyError:
 
683
                # left-hand parent is a ghost, treat it as not existing
 
684
                pass
 
685
        if parent_revno is not None:
661
686
            if not first_child:
662
687
                # not the first child, make a new branch
663
688
                base_revno = parent_revno[0]