/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 bzrlib/tsort.py

Make shure the faster topo_sort function is used where appropriate

When the calling code is iterating through the whole list, it is faster to use
topo_sort instead of TopoSorter.iter_topo_order.
Also update a blackbox test case to reflect the new ordering.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
18
18
"""Topological sorting routines."""
19
19
 
20
20
 
21
 
from bzrlib import (
22
 
    errors,
23
 
    graph as _mod_graph,
24
 
    revision as _mod_revision,
25
 
    )
 
21
from bzrlib import errors
 
22
import bzrlib.revision as _mod_revision
26
23
 
27
24
 
28
25
__all__ = ["topo_sort", "TopoSorter", "merge_sort", "MergeSorter"]
33
30
 
34
31
    graph -- sequence of pairs of node->parents_list.
35
32
 
36
 
    The result is a list of node names, such that all parents come before their
37
 
    children.
 
33
    The result is a list of node names, such that all parents come before
 
34
    their children.
38
35
 
39
36
    node identifiers can be any hashable object, and are typically strings.
40
37
 
41
38
    This function has the same purpose as the TopoSorter class, but uses a
42
 
    different algorithm to sort the graph. That means that while both return a
43
 
    list with parents before their child nodes, the exact ordering can be
44
 
    different.
 
39
    different algorithm to sort the graph. That means that while both return a list
 
40
    with parents before their child nodes, the exact ordering can be different.
45
41
 
46
 
    topo_sort is faster when the whole list is needed, while when iterating
47
 
    over a part of the list, TopoSorter.iter_topo_order should be used.
 
42
    topo_sort is faster when the whole list is needed, while when iterating over a
 
43
    part of the list, TopoSorter.iter_topo_order should be used.
48
44
    """
49
 
    kg = _mod_graph.KnownGraph(dict(graph))
50
 
    return kg.topo_sort()
 
45
    # store a dict of the graph.
 
46
    graph = dict(graph)
 
47
    # this is the stack storing on which the sorted nodes are pushed.
 
48
    node_name_stack = []
 
49
 
 
50
    # count the number of children for every node in the graph
 
51
    nchildren = dict.fromkeys(graph.iterkeys(), 0)
 
52
    for parents in graph.itervalues():
 
53
        for parent in parents:
 
54
            if parent in nchildren:
 
55
                nchildren[parent] += 1
 
56
    # keep track of nodes without children in a separate list
 
57
    nochildnodes = [node for (node, n) in nchildren.iteritems() if n == 0]
 
58
 
 
59
    while nochildnodes:
 
60
        # pick a node without a child and add it to the stack.
 
61
        node_name = nochildnodes.pop()
 
62
        node_name_stack.append(node_name)
 
63
 
 
64
        # the parents of the node lose it as a child; if it was the last
 
65
        # child, add the parent to the list of childless nodes.
 
66
        parents = graph.pop(node_name)
 
67
        for parent in parents:
 
68
            if parent in nchildren:
 
69
                nchildren[parent] -= 1
 
70
                if nchildren[parent] == 0:
 
71
                    nochildnodes.append(parent)
 
72
 
 
73
    # if there are still nodes left in the graph,
 
74
    # that means that there is a cycle
 
75
    if graph:
 
76
        raise errors.GraphCycleError(graph)
 
77
 
 
78
    # the nodes where pushed on the stack child first, so this list needs to be
 
79
    # reversed before returning it.
 
80
    node_name_stack.reverse()
 
81
    return node_name_stack
51
82
 
52
83
 
53
84
class TopoSorter(object):
409
440
 
410
441
        # seed the search with the tip of the branch
411
442
        if (branch_tip is not None and
412
 
            branch_tip != _mod_revision.NULL_REVISION and
413
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
443
            branch_tip != _mod_revision.NULL_REVISION):
414
444
            parents = self._graph.pop(branch_tip)
415
445
            self._push_node(branch_tip, 0, parents)
416
446
 
459
489
            left_subtree_pushed_stack_append(False)
460
490
            pending_parents_stack_append(list(parents))
461
491
            # as we push it, check if it is the first child
462
 
            parent_info = None
463
492
            if parents:
464
493
                # node has parents, assign from the left most parent.
465
 
                try:
466
 
                    parent_info = revnos[parents[0]]
467
 
                except KeyError:
468
 
                    # Left-hand parent is a ghost, consider it not to exist
469
 
                    pass
470
 
            if parent_info is not None:
 
494
                parent_info = revnos[parents[0]]
471
495
                first_child = parent_info[1]
472
496
                parent_info[1] = False
473
497
            else:
501
525
            pending_parents_stack_pop()
502
526
 
503
527
            parents = original_graph[node_name]
504
 
            parent_revno = None
505
528
            if parents:
506
529
                # node has parents, assign from the left most parent.
507
 
                try:
508
 
                    parent_revno = revnos[parents[0]][0]
509
 
                except KeyError:
510
 
                    # left-hand parent is a ghost, treat it as not existing
511
 
                    pass
512
 
            if parent_revno is not None:
 
530
                parent_revno = revnos[parents[0]][0]
513
531
                if not first_child:
514
532
                    # not the first child, make a new branch
515
533
                    base_revno = parent_revno[0]
553
571
                    if not left_subtree_pushed_stack[-1]:
554
572
                        # recurse depth first into the primary parent
555
573
                        next_node_name = pending_parents_stack[-1].pop(0)
556
 
                        is_left_subtree = True
557
 
                        left_subtree_pushed_stack[-1] = True
558
574
                    else:
559
575
                        # place any merges in right-to-left order for scheduling
560
576
                        # which gives us left-to-right order after we reverse
564
580
                        # display nicely (you get smaller trees at the top
565
581
                        # of the combined merge).
566
582
                        next_node_name = pending_parents_stack[-1].pop()
567
 
                        is_left_subtree = False
568
583
                    if next_node_name in completed_node_names:
569
584
                        # this parent was completed by a child on the
570
585
                        # call stack. skip it.
579
594
                        # current search stack (but not completed or we would
580
595
                        # have hit the continue 4 lines up.
581
596
                        # this indicates a cycle.
582
 
                        if next_node_name in self._original_graph:
583
 
                            raise errors.GraphCycleError(node_name_stack)
584
 
                        else:
585
 
                            # This is just a ghost parent, ignore it
586
 
                            continue
 
597
                        raise errors.GraphCycleError(node_name_stack)
587
598
                    next_merge_depth = 0
588
 
                    if is_left_subtree:
 
599
                    if left_subtree_pushed_stack[-1]:
589
600
                        # a new child branch from name_stack[-1]
 
601
                        next_merge_depth = 1
 
602
                    else:
590
603
                        next_merge_depth = 0
591
 
                    else:
592
 
                        next_merge_depth = 1
 
604
                        left_subtree_pushed_stack[-1] = True
593
605
                    next_merge_depth = (
594
606
                        node_merge_depth_stack[-1] + next_merge_depth)
595
607
                    push_node(
640
652
        self._left_subtree_pushed_stack.append(False)
641
653
        self._pending_parents_stack.append(list(parents))
642
654
        # as we push it, figure out if this is the first child
643
 
        parent_info = None
 
655
        parents = self._original_graph[node_name]
644
656
        if parents:
645
657
            # node has parents, assign from the left most parent.
646
 
            try:
647
 
                parent_info = self._revnos[parents[0]]
648
 
            except KeyError:
649
 
                # Left-hand parent is a ghost, consider it not to exist
650
 
                pass
651
 
        if parent_info is not None:
 
658
            parent_info = self._revnos[parents[0]]
652
659
            first_child = parent_info[1]
653
660
            parent_info[1] = False
654
661
        else:
672
679
        self._pending_parents_stack.pop()
673
680
 
674
681
        parents = self._original_graph[node_name]
675
 
        parent_revno = None
676
682
        if parents:
677
683
            # node has parents, assign from the left most parent.
678
 
            try:
679
 
                parent_revno = self._revnos[parents[0]][0]
680
 
            except KeyError:
681
 
                # left-hand parent is a ghost, treat it as not existing
682
 
                pass
683
 
        if parent_revno is not None:
 
684
            parent_revno = self._revnos[parents[0]][0]
684
685
            if not first_child:
685
686
                # not the first child, make a new branch
686
687
                base_revno = parent_revno[0]
696
697
        else:
697
698
            # no parents, use the root sequence
698
699
            root_count = self._revno_to_branch_count.get(0, 0)
699
 
            root_count = self._revno_to_branch_count.get(0, -1)
700
 
            root_count += 1
701
700
            if root_count:
702
701
                revno = (0, root_count, 1)
703
702
            else:
704
703
                revno = (1,)
 
704
            root_count += 1
705
705
            self._revno_to_branch_count[0] = root_count
706
706
 
707
707
        # store the revno for this node for future reference