← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2008-05-12 04:14:21 UTC
  • Revision ID: aaron@aaronbentley.com-20080512041421-hunspdyev3rxqx7u
Avoid using deprecated interface for heads

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
 
1
# Copyright (C) 2005 Aaron Bentley
 
2
# <aaron@aaronbentley.com>
 
3
#
 
4
#    This program is free software; you can redistribute it and/or modify
 
5
#    it under the terms of the GNU General Public License as published by
 
6
#    the Free Software Foundation; either version 2 of the License, or
 
7
#    (at your option) any later version.
 
8
#
 
9
#    This program is distributed in the hope that it will be useful,
 
10
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
12
#    GNU General Public License for more details.
 
13
#
 
14
#    You should have received a copy of the GNU General Public License
 
15
#    along with this program; if not, write to the Free Software
 
16
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
17
from bzrtools import short_committer
 
18
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
 
19
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
 
20
from bzrlib.branch import Branch
 
21
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
 
22
from bzrlib.graph import node_distances, select_farthest
 
23
from bzrlib.revision import combined_graph, revision_graph, NULL_REVISION
 
24
from bzrlib.revision import MultipleRevisionSources
 
25
import bzrlib.errors
 
26
import re
 
27
import os.path
 
28
import time
 
29
 
 
30
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
 
31
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
 
32
            'abentley@lappy'                : 'Aaron Bentley',
 
33
            'john@arbash-meinel.com'        : 'John Arbash Meinel',
 
34
            'mbp@sourcefrog.net'            : 'Martin Pool',
 
35
            'robertc@robertcollins.net'     : 'Robert Collins',
 
36
            }
 
37
 
 
38
committer_alias = {'abentley': 'Aaron Bentley'}
 
39
def can_skip(rev_id, descendants, ancestors):
 
40
    if rev_id not in descendants:
 
41
        return False
 
42
    elif rev_id not in ancestors:
 
43
        return False
 
44
    elif len(ancestors[rev_id]) != 1:
 
45
        return False
 
46
    elif len(descendants[list(ancestors[rev_id])[0]]) != 1:
 
47
        return False
 
48
    elif len(descendants[rev_id]) != 1:
 
49
        return False
 
50
    else:
 
51
        return True
 
52
 
 
53
def compact_ancestors(descendants, ancestors, exceptions=()):
 
54
    new_ancestors={}
 
55
    skip = set()
 
56
    for me, my_parents in ancestors.iteritems():
 
57
        if me in skip:
 
58
            continue
 
59
        new_ancestors[me] = {}
 
60
        for parent in my_parents:
 
61
            new_parent = parent
 
62
            distance = 0
 
63
            while can_skip(new_parent, descendants, ancestors):
 
64
                if new_parent in exceptions:
 
65
                    break
 
66
                skip.add(new_parent)
 
67
                if new_parent in new_ancestors:
 
68
                    del new_ancestors[new_parent]
 
69
                new_parent = list(ancestors[new_parent])[0]
 
70
                distance += 1
 
71
            new_ancestors[me][new_parent] = distance
 
72
    return new_ancestors
 
73
 
 
74
def get_rev_info(rev_id, source):
 
75
    """Return the committer, message, and date of a revision."""
 
76
    committer = None
 
77
    message = None
 
78
    date = None
 
79
    if rev_id == 'null:':
 
80
        return None, 'Null Revision', None, None
 
81
    try:
 
82
        rev = source.get_revision(rev_id)
 
83
    except NoSuchRevision:
 
84
        try:
 
85
            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
 
86
            if committer == '':
 
87
                return None, None, None, None
 
88
        except ValueError:
 
89
            return None, None, None, None
 
90
    else:
 
91
        committer = short_committer(rev.committer)
 
92
        if rev.message is not None:
 
93
            message = rev.message.split('\n')[0]
 
94
        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
 
95
        date = time.strftime('%Y/%m/%d', gmtime)
 
96
        nick = rev.properties.get('branch-nick')
 
97
    if '@' in committer:
 
98
        try:
 
99
            committer = mail_map[committer]
 
100
        except KeyError:
 
101
            pass
 
102
    try:
 
103
        committer = committer_alias[committer]
 
104
    except KeyError:
 
105
        pass
 
106
    return committer, message, nick, date
 
107
 
 
108
class Grapher(object):
 
109
 
 
110
    def __init__(self, branch, other_branch=None):
 
111
        object.__init__(self)
 
112
        self.branch = branch
 
113
        self.other_branch = other_branch
 
114
        if other_branch is not None:
 
115
            other_repo = other_branch.repository
 
116
            revision_b = self.other_branch.last_revision()
 
117
        else:
 
118
            other_repo = None
 
119
            revision_b = None
 
120
        self.graph = self.branch.repository.get_graph(other_repo)
 
121
        revision_a = self.branch.last_revision()
 
122
        self.scan_graph(revision_a, revision_b)
 
123
        self.n_history = branch.revision_history()
 
124
        self.n_revnos = branch.get_revision_id_to_revno_map()
 
125
        self.distances = node_distances(self.descendants, self.ancestors,
 
126
                                        self.root)
 
127
        if other_branch is not None:
 
128
            self.base = select_farthest(self.distances, self.common)
 
129
            self.m_history = other_branch.revision_history()
 
130
            self.m_revnos = other_branch.get_revision_id_to_revno_map()
 
131
            self.new_base = self.graph.find_unique_lca(revision_a,
 
132
                                                       revision_b)
 
133
            self.lcas = self.graph.find_lca(revision_a, revision_b)
 
134
        else:
 
135
            self.base = None
 
136
            self.new_base = None
 
137
            self.lcas = set()
 
138
            self.m_history = []
 
139
            self.m_revnos = {}
 
140
 
 
141
    def scan_graph(self, revision_a, revision_b):
 
142
        a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
 
143
        self.ancestors = a_ancestors
 
144
        self.root = NULL_REVISION
 
145
        if revision_b is not None:
 
146
            b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
 
147
            self.common = set(a_ancestors.keys())
 
148
            self.common.intersection_update(b_ancestors)
 
149
            self.ancestors.update(b_ancestors)
 
150
        else:
 
151
            self.common = []
 
152
            revision_b = None
 
153
        self.descendants = {}
 
154
        ghosts = set()
 
155
        for revision, parents in self.ancestors.iteritems():
 
156
            self.descendants.setdefault(revision, [])
 
157
            if parents is None:
 
158
                ghosts.add(revision)
 
159
                parents = [NULL_REVISION]
 
160
            for parent in parents:
 
161
                self.descendants.setdefault(parent, []).append(revision)
 
162
        for ghost in ghosts:
 
163
            self.ancestors[ghost] = [NULL_REVISION]
 
164
 
 
165
    @staticmethod
 
166
    def _get_revno_str(prefix, revno_map, revision_id):
 
167
        try:
 
168
            revno = revno_map[revision_id]
 
169
        except KeyError:
 
170
            return None
 
171
        return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
 
172
 
 
173
    def dot_node(self, node, num):
 
174
        try:
 
175
            n_rev = self.n_history.index(node) + 1
 
176
        except ValueError:
 
177
            n_rev = None
 
178
        try:
 
179
            m_rev = self.m_history.index(node) + 1
 
180
        except ValueError:
 
181
            m_rev = None
 
182
        if (n_rev, m_rev) == (None, None):
 
183
            name = self._get_revno_str('r', self.n_revnos, node)
 
184
            if name is None:
 
185
                name = self._get_revno_str('R', self.m_revnos, node)
 
186
            if name is None:
 
187
                name = node[-5:]
 
188
            cluster = None
 
189
        elif n_rev == m_rev:
 
190
            name = "rR%d" % n_rev
 
191
        else:
 
192
            namelist = []
 
193
            for prefix, revno in (('r', n_rev), ('R', m_rev)):
 
194
                if revno is not None:
 
195
                    namelist.append("%s%d" % (prefix, revno))
 
196
            name = ' '.join(namelist)
 
197
        if None not in (n_rev, m_rev):
 
198
            cluster = "common_history"
 
199
            color = "#ff9900"
 
200
        elif (None, None) == (n_rev, m_rev):
 
201
            cluster = None
 
202
            if node in self.common:
 
203
                color = "#6699ff"
 
204
            else:
 
205
                color = "white"
 
206
        elif n_rev is not None:
 
207
            cluster = "my_history"
 
208
            color = "#ffff00"
 
209
        else:
 
210
            assert m_rev is not None
 
211
            cluster = "other_history"
 
212
            color = "#ff0000"
 
213
        if node in self.lcas:
 
214
            color = "#9933cc"
 
215
        if node == self.base:
 
216
            color = "#669933"
 
217
            if node == self.new_base:
 
218
                color = "#33ff33"
 
219
        if node == self.new_base:
 
220
            color = '#33cc99'
 
221
 
 
222
        label = [name]
 
223
        committer, message, nick, date = get_rev_info(node,
 
224
                                                      self.branch.repository)
 
225
        if committer is not None:
 
226
            label.append(committer)
 
227
 
 
228
        if nick is not None:
 
229
            label.append(nick)
 
230
 
 
231
        if date is not None:
 
232
            label.append(date)
 
233
 
 
234
        if node in self.distances:
 
235
            rank = self.distances[node]
 
236
            label.append('d%d' % self.distances[node])
 
237
        else:
 
238
            rank = None
 
239
 
 
240
        d_node = Node("n%d" % num, color=color, label="\\n".join(label),
 
241
                    rev_id=node, cluster=cluster, message=message,
 
242
                    date=date)
 
243
        d_node.rank = rank
 
244
 
 
245
        if node not in self.ancestors:
 
246
            d_node.node_style.append('dotted')
 
247
 
 
248
        return d_node
 
249
 
 
250
    def get_relations(self, collapse=False, max_distance=None):
 
251
        dot_nodes = {}
 
252
        node_relations = []
 
253
        num = 0
 
254
        if collapse:
 
255
            exceptions = self.lcas.union([self.base, self.new_base])
 
256
            visible_ancestors = compact_ancestors(self.descendants,
 
257
                                                  self.ancestors,
 
258
                                                  exceptions)
 
259
        else:
 
260
            visible_ancestors = {}
 
261
            for revision, parents in self.ancestors.iteritems():
 
262
                visible_ancestors[revision] = dict((p, 0) for p in parents)
 
263
        if max_distance is not None:
 
264
            min_distance = max(self.distances.values()) - max_distance
 
265
            visible_ancestors = dict((n, p) for n, p in
 
266
                                     visible_ancestors.iteritems() if
 
267
                                     self.distances[n] >= min_distance)
 
268
        for node, parents in visible_ancestors.iteritems():
 
269
            if node not in dot_nodes:
 
270
                dot_nodes[node] = self.dot_node(node, num)
 
271
                num += 1
 
272
            for parent, skipped in parents.iteritems():
 
273
                if parent not in dot_nodes:
 
274
                    dot_nodes[parent] = self.dot_node(parent, num)
 
275
                    num += 1
 
276
                edge = Edge(dot_nodes[parent], dot_nodes[node])
 
277
                if skipped != 0:
 
278
                    edge.label = "%d" % skipped
 
279
                node_relations.append(edge)
 
280
        return node_relations
 
281
 
 
282
 
 
283
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
 
284
                        merge_branch=None, ranking="forced", max_distance=None):
 
285
    b = Branch.open_containing(branch)[0]
 
286
    if merge_branch is not None:
 
287
        m = Branch.open_containing(merge_branch)[0]
 
288
    else:
 
289
        m = None
 
290
    b.lock_write()
 
291
    try:
 
292
        if m is not None:
 
293
            m.lock_read()
 
294
        try:
 
295
            grapher = Grapher(b, m)
 
296
            relations = grapher.get_relations(collapse, max_distance)
 
297
        finally:
 
298
            if m is not None:
 
299
                m.unlock()
 
300
    finally:
 
301
        b.unlock()
 
302
 
 
303
    ext = filename.split('.')[-1]
 
304
    output = dot_output(relations, ranking)
 
305
    done = False
 
306
    if ext not in RSVG_OUTPUT_TYPES:
 
307
        antialias = False
 
308
    if antialias:
 
309
        output = list(output)
 
310
        try:
 
311
            invoke_dot_aa(output, filename, ext)
 
312
            done = True
 
313
        except NoDot, e:
 
314
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
 
315
                " is installed correctly.")
 
316
        except NoRsvg, e:
 
317
            print "Not antialiasing because rsvg (from librsvg-bin) is not"\
 
318
                " installed."
 
319
            antialias = False
 
320
    if ext in DOT_OUTPUT_TYPES and not antialias and not done:
 
321
        try:
 
322
            invoke_dot(output, filename, ext)
 
323
            done = True
 
324
        except NoDot, e:
 
325
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
 
326
                " is installed correctly.")
 
327
    elif ext == 'dot' and not done:
 
328
        my_file = file(filename, 'wb')
 
329
        for fragment in output:
 
330
            my_file.write(fragment.encode('utf-8'))
 
331
    elif ext == 'html':
 
332
        try:
 
333
            invoke_dot_html(output, filename)
 
334
        except NoDot, e:
 
335
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
 
336
                " is installed correctly.")
 
337
    elif not done:
 
338
        print "Unknown file extension: %s" % ext