Part of bzrlib.tsort View In Hierarchy

No class docstring

Method | __init__ | Merge-aware topological sorting of a graph. |

Method | sorted | Sort the graph and return as a list. |

Method | iter_topo_order | Yield the nodes of the graph in a topological order. |

Method | _push_node | Add node_name to the pending node stack. |

Method | _pop_node | Pop the top node off the stack |

def
__init__(self, graph, branch_tip, mainline_revisions=None, generate_revno=False):

Merge-aware topological sorting of a graph. :param graph: sequence of pairs of node_name->parent_names_list. i.e. [('C', ['B']), ('B', ['A']), ('A', [])] For this input the output from the sort or iter_topo_order routines will be: 'A', 'B', 'C' :param branch_tip: the tip of the branch to graph. Revisions not reachable from branch_tip are not included in the output. :param mainline_revisions: If not None this forces a mainline to be used rather than synthesised from the graph. This must be a valid path through some part of the graph. If the mainline does not cover all the revisions, output stops at the start of the old revision listed in the mainline revisions list. The order for this parameter is oldest-first. :param generate_revno: Optional parameter controlling the generation of revision number sequences in the output. See the output description for more details. The result is a list sorted so that all parents come before their children. Each element of the list is a tuple containing: (sequence_number, node_name, merge_depth, end_of_merge) * sequence_number: The sequence of this row in the output. Useful for GUIs. * node_name: The node name: opaque text to the merge routine. * merge_depth: How many levels of merging deep this node has been found. * revno_sequence: When requested this field provides a sequence of revision numbers for all revisions. The format is: (REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM is the number of the branch that the revno is on. From left to right the REVNO numbers are the sequence numbers within that branch of the revision. For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,). This should be read as 'A is the first commit in the trunk', 'B is the first commit on the first branch made from A', 'C is the second commit in the trunk'. * end_of_merge: When True the next node is part of a different merge. node identifiers can be any hashable object, and are typically strings. If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use one of the two values for 'a'. The graph is sorted lazily: until you iterate or sort the input is not processed other than to create an internal representation. iteration or sorting may raise GraphCycleError if a cycle is present in the graph. Background information on the design: ------------------------------------- definition: the end of any cluster or 'merge' occurs when: 1 - the next revision has a lower merge depth than we do. i.e. A 0 B 1 C 2 D 1 E 0 C, D are the ends of clusters, E might be but we need more data. 2 - or the next revision at our merge depth is not our left most ancestor. This is required to handle multiple-merges in one commit. i.e. A 0 [F, B, E] B 1 [D, C] C 2 [D] D 1 [F] E 1 [F] F 0 C is the end of a cluster due to rule 1. D is not the end of a cluster from rule 1, but is from rule 2: E is not its left most ancestor E is the end of a cluster due to rule 1 F might be but we need more data. we show connecting lines to a parent when: - The parent is the start of a merge within this cluster. That is, the merge was not done to the mainline before this cluster was merged to the mainline. This can be detected thus: * The parent has a higher merge depth and is the next revision in the list. The next revision in the list constraint is needed for this case: A 0 [D, B] B 1 [C, F] # we do not want to show a line to F which is depth 2 but not a merge C 1 [H] # note that this is a long line to show back to the ancestor - see the end of merge rules. D 0 [G, E] E 1 [G, F] F 2 [G] G 1 [H] H 0 - Part of this merges 'branch': The parent has the same merge depth and is our left most parent and we are not the end of the cluster. A 0 [C, B] lines: [B, C] B 1 [E, C] lines: [C] C 0 [D] lines: [D] D 0 [F, E] lines: [E, F] E 1 [F] lines: [F] F 0 - The end of this merge/cluster: we can ONLY have multiple parents at the end of a cluster if this branch was previously merged into the 'mainline'. - if we have one and only one parent, show it Note that this may be to a greater merge depth - for instance if this branch continued from a deeply nested branch to add something to it. - if we have more than one parent - show the second oldest (older == further down the list) parent with an equal or lower merge depth XXXX revisit when awake. ddaa asks about the relevance of each one - maybe more than one parent is relevant

def
sorted(self):

Sort the graph and return as a list.

After calling this the sorter is empty and you must create a new one.

def
iter_topo_order(self):

Yield the nodes of the graph in a topological order.

After finishing iteration the sorter is empty and you cannot continue iteration.