1
# -*- coding: UTF-8 -*-
2
"""Directed graph production.
4
This module contains the code to produce an ordered directed graph of a
5
bzr branch, such as we display in the tree view at the top of the bzrk
9
__copyright__ = "Copyright © 2005 Canonical Ltd."
10
__author__ = "Scott James Remnant <scott@ubuntu.com>"
12
from bzrlib.tsort import merge_sort
14
def linegraph(branch, start, maxnum):
15
"""Produce a directed graph of a bzr branch.
17
Returns a list of tuples of (revid,
24
Node is a tuple of (column, colour) with column being a zero-indexed
25
column number of the graph that this revision represents and colour
26
being a zero-indexed colour (which doesn't specify any actual colour
27
in particular) to draw the node in.
29
Lines is a list of tuples which represent lines you should draw away
30
from the revision, if you also need to draw lines into the revision
31
you should use the lines list from the previous iteration. Each
32
typle in the list is in the form (start, end, colour) with start and
33
end being zero-indexed column numbers and colour as in node.
35
It's up to you how to actually draw the nodes and lines (straight,
36
curved, kinked, etc.) and to pick the actual colours for each index.
39
mainline = branch.revision_history()
40
graph_parents = branch.repository.get_revision_graph(start)
42
for revid in graph_parents.keys():
43
graph_children[revid] = []
45
merge_sorted_revisions = merge_sort(
56
for (rev_index, (sequence_number,
60
end_of_merge)) in enumerate(merge_sorted_revisions):
62
revid_index[revid] = rev_index
63
revno_index[revno_sequence] = rev_index
65
branch_id = revno_sequence[0:-1]
68
if branch_id not in branch_lines:
69
branch_line = {"line_type": "branch_line",
70
"branch_id": branch_id,
72
"min_index": rev_index,
74
branch_lines[branch_id] = branch_line
76
branch_line = branch_lines[branch_id]
77
branch_line["rev_indexes"].append(rev_index)
78
if rev_index > branch_line["max_index"]:
79
branch_line["max_index"] = rev_index
81
parents = graph_parents[revid]
82
for parent_revid in parents:
83
graph_children[parent_revid].append(revid)
85
linegraph.append([revid,
92
branch_ids = branch_lines.keys()
93
def branch_id_cmp(x, y):
98
return cmp(len_x, len_y)
100
branch_ids.sort(branch_id_cmp)
104
for branch_id in branch_ids:
105
branch_line = branch_lines[branch_id]
107
append_line(columns, branch_line)
108
branch_id = branch_line["branch_id"]
109
color = reduce(lambda x, y: x+y, branch_id, 0)
110
col_index = branch_line["col_index"]
111
node = (col_index, color)
113
for rev_index in branch_line["rev_indexes"]:
118
end_of_merge) = merge_sorted_revisions[rev_index]
120
linegraph[rev_index][1] = node
121
linegraph[rev_index][4] = graph_children[revid]
123
for parent_revid in graph_parents[revid]:
124
if parent_revid in revid_index:
125
parent_index = revid_index[parent_revid]
126
parent_revno = merge_sorted_revisions[parent_index][3]
127
parent_branch_id = parent_revno[0:-1]
128
line = {"line_type": "inter_branch_line",
129
"min_index": rev_index,
130
"max_index": parent_index}
132
if branch_id != parent_branch_id and \
133
parent_index - rev_index > 1:
134
append_line(columns, line)
137
parent_index = line["max_index"]
138
parent_node = linegraph[parent_index][1]
139
parent_col_index = parent_node[0]
140
color = parent_node[1]
142
child_index = line["min_index"]
143
child_col_index = linegraph[child_index][1][0]
145
if "col_index" in line:
146
line_col_index = line["col_index"]
147
linegraph[child_index][2].append(
151
for line_part_index in range(child_index+1, parent_index-1):
152
linegraph[line_part_index][2].append(
156
linegraph[parent_index-1][2].append(
161
linegraph[child_index][2].append(
165
for line_part_index in range(child_index+1, parent_index):
166
linegraph[line_part_index][2].append(
172
return (linegraph, revid_index)
174
def append_line(columns, line):
175
for col_index, column in enumerate(columns):
176
has_overlaping_line = False
177
for col_line in column:
178
if not (col_line["min_index"] >= line["max_index"] or \
179
col_line["max_index"] <= line["min_index"]):
180
has_overlaping_line = True
182
if not has_overlaping_line:
185
col_index = len(columns)
187
line["col_index"] = col_index
188
columns[col_index].append(line)
192
def same_branch(a, b):
193
"""Return whether we think revisions a and b are on the same branch."""
194
if len(a.parent_ids) == 1:
195
# Defacto same branch if only parent
197
elif a.committer == b.committer:
198
# Same committer so may as well be
added
removed
viz/linegraph.py
