← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Robert Collins
  • Date: 2005-09-28 05:50:54 UTC
  • mfrom: (201)
  • mto: (147.2.6) (364.1.3 bzrtools)
  • mto: This revision was merged to the branch mainline in revision 324.
  • Revision ID: robertc@robertcollins.net-20050928055054-dbbd7d7169db3a72
merge from abentley

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
1
1
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
2
 
from dotgraph import mail_map
 
2
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
3
3
from bzrlib.branch import Branch
4
 
from bzrlib.errors import BzrCommandError
 
4
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
 
5
from bzrlib.fetch import greedy_fetch
 
6
from bzrlib.graph import node_distances, select_farthest
 
7
from bzrlib.revision import combined_graph, revision_graph
 
8
from bzrlib.revision import MultipleRevisionSources
5
9
import bzrlib.errors
6
10
import re
7
11
import os.path
8
 
 
9
 
mail_map.update({'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
10
 
                 'abentley@panoramicfeedback.com': 'Aaron Bentley',
11
 
                 'abentley@lappy'                : 'Aaron Bentley',
12
 
                 'john@arbash-meinel.com'        : 'John Arbash Meinel',
13
 
                 'mbp@sourcefrog.net'            : 'Martin Pool',
14
 
                 'robertc@robertcollins.net'     : 'Robert Collins',
15
 
                })
16
 
 
17
 
def add_relations(rev_id):
18
 
    if rev_id in ancestors:
19
 
        return
20
 
    print rev_id
21
 
    if rev_id not in nodes:
22
 
        nodes[rev_id] = Node("n%d" % counter, label = rev_id)
23
 
        counter += 1
24
 
    revision = branch.get_revision(rev_id)
25
 
    ancestors [rev_id] = []
26
 
    for p in (p.revision_id for p in revision.parents):
27
 
        add_relations(p)
28
 
        if p not in descendants:
29
 
            descendants[p] = []
30
 
        descendants[p].append(rev_id)
31
 
        ancestors [rev_id].append(rev_id)
32
 
 
 
12
import time
 
13
 
 
14
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
 
15
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
 
16
            'abentley@lappy'                : 'Aaron Bentley',
 
17
            'john@arbash-meinel.com'        : 'John Arbash Meinel',
 
18
            'mbp@sourcefrog.net'            : 'Martin Pool',
 
19
            'robertc@robertcollins.net'     : 'Robert Collins',
 
20
            }
 
21
 
 
22
committer_alias = {'abentley': 'Aaron Bentley'}
33
23
def short_committer(committer):
34
24
    new_committer = re.sub('<.*>', '', committer).strip(' ')
35
25
    if len(new_committer) < 2:
39
29
def can_skip(rev_id, descendants, ancestors):
40
30
    if rev_id not in descendants:
41
31
        return False
 
32
    elif rev_id not in ancestors:
 
33
        return False
42
34
    elif len(ancestors[rev_id]) != 1:
43
35
        return False
44
 
    elif len(descendants[ancestors[rev_id][0]]) != 1:
 
36
    elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
45
37
        return False
46
38
    elif len(descendants[rev_id]) != 1:
47
39
        return False
48
40
    else:
49
41
        return True
50
42
 
51
 
def compact_descendants(descendants, ancestors):
52
 
    new_descendants={}
 
43
def compact_ancestors(descendants, ancestors, exceptions=()):
 
44
    new_ancestors={}
53
45
    skip = set()
54
 
    for me, my_descendants in descendants.iteritems():
 
46
    for me, my_parents in ancestors.iteritems():
55
47
        if me in skip:
56
48
            continue
57
 
        new_descendants[me] = []
58
 
        for descendant in my_descendants:
59
 
            new_descendant = descendant
60
 
            while can_skip(new_descendant, descendants, ancestors):
61
 
                skip.add(new_descendant)
62
 
                if new_descendant in new_descendants:
63
 
                    del new_descendants[new_descendant]
64
 
                new_descendant = descendants[new_descendant][0]
65
 
            new_descendants[me].append(new_descendant)
66
 
    return new_descendants    
67
 
 
68
 
 
69
 
def graph_ancestry(branch, collapse=True):
70
 
    nodes = {}
71
 
    q = ((i+1, n) for (i, n) in enumerate(branch.revision_history()))
72
 
    r = 1
73
 
    try:
74
 
        branch_name = os.path.basename(branch.base)
75
 
    except AttributeError:
76
 
        branch_name = "main"
77
 
    for (revno, rev_id) in q:
78
 
        nodes[rev_id] = Node("R%d" % revno, color="#ffff00", rev_id=rev_id, 
79
 
                             cluster=branch_name)
80
 
 
81
 
    ancestors = {} 
82
 
    descendants = {}
83
 
    counter = 0
84
 
    lines = [branch.last_patch()]
85
 
    while len(lines) > 0:
86
 
        new_lines = set()
87
 
        for rev_id in lines:
88
 
            if rev_id not in nodes:
89
 
                nodes[rev_id] = Node("n%d" % counter, label=rev_id, 
90
 
                                     rev_id=rev_id)
91
 
                counter+=1
92
 
                
 
49
        new_ancestors[me] = {} 
 
50
        for parent in my_parents:
 
51
            new_parent = parent 
 
52
            distance = 0
 
53
            while can_skip(new_parent, descendants, ancestors):
 
54
                if new_parent in exceptions:
 
55
                    break
 
56
                skip.add(new_parent)
 
57
                if new_parent in new_ancestors:
 
58
                    del new_ancestors[new_parent]
 
59
                new_parent = list(ancestors[new_parent])[0]
 
60
                distance += 1
 
61
            new_ancestors[me][new_parent] = distance
 
62
    return new_ancestors    
 
63
 
 
64
def get_rev_info(rev_id, source):
 
65
    """Return the committer, message, and date of a revision."""
 
66
    committer = None
 
67
    message = None
 
68
    date = None
 
69
    if rev_id == 'null:':
 
70
        return None, 'Null Revision', None
 
71
    try:
 
72
        rev = source.get_revision(rev_id)
 
73
    except NoSuchRevision:
 
74
        try:
 
75
            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
 
76
            if committer == '':
 
77
                return None, None, None
 
78
        except ValueError:
 
79
            return None, None, None
 
80
    else:
 
81
        committer = short_committer(rev.committer)
 
82
        if rev.message is not None:
 
83
            message = rev.message.split('\n')[0]
 
84
        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
 
85
        date = time.strftime('%Y/%m/%d', gmtime)
 
86
    if '@' in committer:
 
87
        try:
 
88
            committer = mail_map[committer]
 
89
        except KeyError:
 
90
            pass
 
91
    try:
 
92
        committer = committer_alias[committer]
 
93
    except KeyError:
 
94
        pass
 
95
    return committer, message, date
 
96
 
 
97
class Grapher(object):
 
98
    def __init__(self, branch, other_branch=None):
 
99
        object.__init__(self)
 
100
        self.branch = branch
 
101
        self.other_branch = other_branch
 
102
        revision_a = self.branch.last_patch()
 
103
        if other_branch is not None:
 
104
            greedy_fetch(branch, other_branch)
 
105
            revision_b = self.other_branch.last_patch()
93
106
            try:
94
 
                revision = branch.get_revision(rev_id)
95
 
            except bzrlib.errors.NoSuchRevision:
96
 
                nodes[rev_id].node_style.append('dotted')
97
 
                continue
98
 
            if nodes[rev_id].committer is None:
99
 
                nodes[rev_id].committer = short_committer(revision.committer)
100
 
            parent_ids = [r.revision_id for r in revision.parents]
101
 
            ancestors [rev_id] = parent_ids
102
 
            for parent in parent_ids:
103
 
                if parent not in ancestors:
104
 
                    new_lines.add(parent)
105
 
                    descendants[parent] = []
106
 
                descendants[parent].append(rev_id)
107
 
        lines = new_lines
108
 
    node_relations = []
109
 
 
110
 
    if collapse:
111
 
        visible_descendants = compact_descendants(descendants, ancestors)
 
107
                self.root, self.ancestors, self.descendants, self.common = \
 
108
                    combined_graph(revision_a, revision_b, self.branch)
 
109
            except bzrlib.errors.NoCommonRoot:
 
110
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
 
111
        else:
 
112
            self.root, self.ancestors, self.descendants = \
 
113
                revision_graph(revision_a, branch)
 
114
            self.common = []
 
115
 
 
116
        self.n_history = branch.revision_history()
 
117
        self.distances = node_distances(self.descendants, self.ancestors, 
 
118
                                        self.root)
 
119
        if other_branch is not None:
 
120
            self.base = select_farthest(self.distances, self.common)
 
121
            self.m_history = other_branch.revision_history() 
 
122
        else:
 
123
            self.base = None
 
124
            self.m_history = []
 
125
 
 
126
    def dot_node(self, node, num):
 
127
        try:
 
128
            n_rev = self.n_history.index(node) + 1
 
129
        except ValueError:
 
130
            n_rev = None
 
131
        try:
 
132
            m_rev = self.m_history.index(node) + 1
 
133
        except ValueError:
 
134
            m_rev = None
 
135
        if (n_rev, m_rev) == (None, None):
 
136
            name = node[-5:]
 
137
            cluster = None
 
138
        elif n_rev == m_rev:
 
139
            name = "rR%d" % n_rev
 
140
        else:
 
141
            namelist = []
 
142
            for prefix, revno in (('r', n_rev), ('R', m_rev)):
 
143
                if revno is not None:
 
144
                    namelist.append("%s%d" % (prefix, revno))
 
145
            name = ' '.join(namelist)
 
146
        if None not in (n_rev, m_rev):
 
147
            cluster = "common_history"
 
148
            color = "#ff9900"
 
149
        elif (None, None) == (n_rev, m_rev):
 
150
            cluster = None
 
151
            if node in self.common:
 
152
                color = "#6699ff"
 
153
            else:
 
154
                color = "white"
 
155
        elif n_rev is not None:
 
156
            cluster = "my_history"
 
157
            color = "#ffff00"
 
158
        else:
 
159
            assert m_rev is not None
 
160
            cluster = "other_history"
 
161
            color = "#ff0000"
 
162
        if node == self.base:
 
163
            color = "#33ff99"
 
164
 
 
165
        label = [name]
 
166
        committer, message, date = get_rev_info(node, self.branch)
 
167
        if committer is not None:
 
168
            label.append(committer)
 
169
 
 
170
        if date is not None:
 
171
            label.append(date)
 
172
 
 
173
        if node in self.distances:
 
174
            rank = self.distances[node]
 
175
            label.append('d%d' % self.distances[node])
 
176
        else:
 
177
            rank = None
 
178
 
 
179
        d_node = Node("n%d" % num, color=color, label="\\n".join(label), 
 
180
                    rev_id=node, cluster=cluster, message=message,
 
181
                    date=date)
 
182
        d_node.rank = rank
 
183
 
 
184
        if node not in self.ancestors:
 
185
            d_node.node_style.append('dotted')
 
186
 
 
187
        return d_node
 
188
        
 
189
    def get_relations(self, collapse=False):
 
190
        dot_nodes = {}
 
191
        node_relations = []
 
192
        num = 0
 
193
        if collapse:
 
194
            visible_ancestors = compact_ancestors(self.descendants, 
 
195
                                                  self.ancestors, (self.base,))
 
196
        else:
 
197
            visible_ancestors = self.ancestors
 
198
        for node, parents in visible_ancestors.iteritems():
 
199
            if node not in dot_nodes:
 
200
                dot_nodes[node] = self.dot_node(node, num)
 
201
                num += 1
 
202
            if visible_ancestors is self.ancestors:
 
203
                parent_iter = ((f, 0) for f in parents)
 
204
            else:
 
205
                parent_iter = (f for f in parents.iteritems())
 
206
            for parent, skipped in parent_iter:
 
207
                if parent not in dot_nodes:
 
208
                    dot_nodes[parent] = self.dot_node(parent, num)
 
209
                    num += 1
 
210
                edge = Edge(dot_nodes[parent], dot_nodes[node])
 
211
                if skipped != 0:
 
212
                    edge.label = "%d" % skipped
 
213
                node_relations.append(edge)
 
214
        return node_relations
 
215
 
 
216
 
 
217
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
 
218
                        merge_branch=None, ranking="forced"):
 
219
    b = Branch.open_containing(branch)
 
220
    if merge_branch is not None:
 
221
        m = Branch.open_containing(merge_branch)
112
222
    else:
113
 
        visible_descendants = descendants
114
 
                
115
 
    for key, values in visible_descendants.iteritems():
116
 
        for value in values:
117
 
            node_relations.append((nodes[key], nodes[value]))
118
 
    return node_relations
 
223
        m = None
 
224
    grapher = Grapher(b, m)
 
225
    relations = grapher.get_relations(collapse)
119
226
 
120
 
def write_ancestry_file(branch, filename, collapse=True, antialias=True):
121
 
    b = Branch(branch)
122
 
    relations = graph_ancestry(b, collapse)
123
227
    ext = filename.split('.')[-1]
124
 
    if antialias and ext in ('png', 'jpg'):
 
228
    output = dot_output(relations, ranking)
 
229
    done = False
 
230
    if ext not in RSVG_OUTPUT_TYPES:
 
231
        antialias = False
 
232
    if antialias: 
 
233
        output = list(output)
125
234
        try:
126
 
            invoke_dot_aa(dot_output(relations), filename, ext)
 
235
            invoke_dot_aa(output, filename, ext)
 
236
            done = True
127
237
        except NoDot, e:
128
238
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
129
239
                " is installed correctly.")
130
240
        except NoRsvg, e:
131
 
            raise BzrCommandError("Can't find 'rsvg'.  Please ensure "\
132
 
                "librsvg-bin is installed correctly, or use --noantialias.")
133
 
    elif ext in ('svg', 'svgz', 'gif', 'jpg', 'ps', 'fig', 'mif', 'png'):
134
 
        try:
135
 
            invoke_dot(dot_output(relations), filename, ext)
136
 
        except NoDot, e:
137
 
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
138
 
                " is installed correctly, or use --noantialias")
139
 
    elif ext=='dot':
140
 
        file(filename, 'wb').write("".join(list(dot_output(relations))))
141
 
    else:
 
241
            print "Not antialiasing because rsvg (from librsvg-bin) is not"\
 
242
                " installed."
 
243
            antialias = False
 
244
    if ext in DOT_OUTPUT_TYPES and not antialias and not done:
 
245
        try:
 
246
            invoke_dot(output, filename, ext)
 
247
            done = True
 
248
        except NoDot, e:
 
249
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
 
250
                " is installed correctly, or use --noantialias")
 
251
    elif ext == 'dot' and not done:
 
252
        my_file = file(filename, 'wb')
 
253
        for fragment in output:
 
254
            my_file.write(fragment)
 
255
    elif ext == 'html':
 
256
        try:
 
257
            invoke_dot_html(output, filename)
 
258
        except NoDot, e:
 
259
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
 
260
                " is installed correctly, or use --noantialias")
 
261
    elif not done:
142
262
        print "Unknown file extension: %s" % ext
143
263