← 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-10-08 13:55:13 UTC
  • Revision ID: aaron@aaronbentley.com-20081008135513-wjxlb9sgh9ua0edb
Publish getchar

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
1
 
# Copyright (C) 2005 Aaron Bentley
2
 
# <aaron.bentley@utoronto.ca>
 
1
# Copyright (C) 2005, 2008 Aaron Bentley
 
2
# <aaron@aaronbentley.com>
3
3
#
4
4
#    This program is free software; you can redistribute it and/or modify
5
5
#    it under the terms of the GNU General Public License as published by
14
14
#    You should have received a copy of the GNU General Public License
15
15
#    along with this program; if not, write to the Free Software
16
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
 
17
 
 
18
 
 
19
import time
 
20
 
20
21
from bzrlib.branch import Branch
21
 
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
 
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
22
23
from bzrlib.graph import node_distances, select_farthest
23
 
from bzrlib.revision import combined_graph, revision_graph
24
 
from bzrlib.revision import MultipleRevisionSources
25
 
import bzrlib.errors
26
 
import re
27
 
import os.path
28
 
import time
 
24
from bzrlib.revision import NULL_REVISION
 
25
 
 
26
from bzrtools import short_committer
 
27
from dotgraph import (
 
28
    dot_output,
 
29
    DOT_OUTPUT_TYPES,
 
30
    Edge,
 
31
    invoke_dot,
 
32
    invoke_dot_aa,
 
33
    invoke_dot_html,
 
34
    Node,
 
35
    NoDot,
 
36
    NoRsvg,
 
37
    RSVG_OUTPUT_TYPES,
 
38
    )
 
39
 
29
40
 
30
41
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
31
42
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
56
67
    for me, my_parents in ancestors.iteritems():
57
68
        if me in skip:
58
69
            continue
59
 
        new_ancestors[me] = {} 
 
70
        new_ancestors[me] = {}
60
71
        for parent in my_parents:
61
 
            new_parent = parent 
 
72
            new_parent = parent
62
73
            distance = 0
63
74
            while can_skip(new_parent, descendants, ancestors):
64
75
                if new_parent in exceptions:
69
80
                new_parent = list(ancestors[new_parent])[0]
70
81
                distance += 1
71
82
            new_ancestors[me][new_parent] = distance
72
 
    return new_ancestors    
 
83
    return new_ancestors
73
84
 
74
85
def get_rev_info(rev_id, source):
75
86
    """Return the committer, message, and date of a revision."""
77
88
    message = None
78
89
    date = None
79
90
    if rev_id == 'null:':
80
 
        return None, 'Null Revision', None
 
91
        return None, 'Null Revision', None, None
81
92
    try:
82
93
        rev = source.get_revision(rev_id)
83
94
    except NoSuchRevision:
84
95
        try:
85
96
            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
86
97
            if committer == '':
87
 
                return None, None, None
 
98
                return None, None, None, None
88
99
        except ValueError:
89
 
            return None, None, None
 
100
            return None, None, None, None
90
101
    else:
91
102
        committer = short_committer(rev.committer)
92
103
        if rev.message is not None:
93
104
            message = rev.message.split('\n')[0]
94
105
        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
95
106
        date = time.strftime('%Y/%m/%d', gmtime)
 
107
        nick = rev.properties.get('branch-nick')
96
108
    if '@' in committer:
97
109
        try:
98
110
            committer = mail_map[committer]
102
114
        committer = committer_alias[committer]
103
115
    except KeyError:
104
116
        pass
105
 
    return committer, message, date
 
117
    return committer, message, nick, date
106
118
 
107
119
class Grapher(object):
 
120
 
108
121
    def __init__(self, branch, other_branch=None):
109
122
        object.__init__(self)
110
123
        self.branch = branch
111
124
        self.other_branch = other_branch
 
125
        if other_branch is not None:
 
126
            other_repo = other_branch.repository
 
127
            revision_b = self.other_branch.last_revision()
 
128
        else:
 
129
            other_repo = None
 
130
            revision_b = None
 
131
        self.graph = self.branch.repository.get_graph(other_repo)
112
132
        revision_a = self.branch.last_revision()
113
 
        if other_branch is not None:
114
 
            branch.fetch(other_branch)
115
 
            revision_b = self.other_branch.last_revision()
116
 
            try:
117
 
                self.root, self.ancestors, self.descendants, self.common = \
118
 
                    combined_graph(revision_a, revision_b,
119
 
                                   self.branch.repository)
120
 
            except bzrlib.errors.NoCommonRoot:
121
 
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
122
 
        else:
123
 
            self.root, self.ancestors, self.descendants = \
124
 
                revision_graph(revision_a, branch.repository)
125
 
            self.common = []
126
 
 
 
133
        self.scan_graph(revision_a, revision_b)
127
134
        self.n_history = branch.revision_history()
128
 
        self.distances = node_distances(self.descendants, self.ancestors, 
 
135
        self.n_revnos = branch.get_revision_id_to_revno_map()
 
136
        self.distances = node_distances(self.descendants, self.ancestors,
129
137
                                        self.root)
130
138
        if other_branch is not None:
131
139
            self.base = select_farthest(self.distances, self.common)
132
 
            self.m_history = other_branch.revision_history() 
 
140
            self.m_history = other_branch.revision_history()
 
141
            self.m_revnos = other_branch.get_revision_id_to_revno_map()
 
142
            self.new_base = self.graph.find_unique_lca(revision_a,
 
143
                                                       revision_b)
 
144
            self.lcas = self.graph.find_lca(revision_a, revision_b)
133
145
        else:
134
146
            self.base = None
 
147
            self.new_base = None
 
148
            self.lcas = set()
135
149
            self.m_history = []
 
150
            self.m_revnos = {}
 
151
 
 
152
    def scan_graph(self, revision_a, revision_b):
 
153
        a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
 
154
        self.ancestors = a_ancestors
 
155
        self.root = NULL_REVISION
 
156
        if revision_b is not None:
 
157
            b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
 
158
            self.common = set(a_ancestors.keys())
 
159
            self.common.intersection_update(b_ancestors)
 
160
            self.ancestors.update(b_ancestors)
 
161
        else:
 
162
            self.common = []
 
163
            revision_b = None
 
164
        self.descendants = {}
 
165
        ghosts = set()
 
166
        for revision, parents in self.ancestors.iteritems():
 
167
            self.descendants.setdefault(revision, [])
 
168
            if parents is None:
 
169
                ghosts.add(revision)
 
170
                parents = [NULL_REVISION]
 
171
            for parent in parents:
 
172
                self.descendants.setdefault(parent, []).append(revision)
 
173
        for ghost in ghosts:
 
174
            self.ancestors[ghost] = [NULL_REVISION]
 
175
 
 
176
    @staticmethod
 
177
    def _get_revno_str(prefix, revno_map, revision_id):
 
178
        try:
 
179
            revno = revno_map[revision_id]
 
180
        except KeyError:
 
181
            return None
 
182
        return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
136
183
 
137
184
    def dot_node(self, node, num):
138
185
        try:
144
191
        except ValueError:
145
192
            m_rev = None
146
193
        if (n_rev, m_rev) == (None, None):
147
 
            name = node[-5:]
 
194
            name = self._get_revno_str('r', self.n_revnos, node)
 
195
            if name is None:
 
196
                name = self._get_revno_str('R', self.m_revnos, node)
 
197
            if name is None:
 
198
                name = node[-5:]
148
199
            cluster = None
149
200
        elif n_rev == m_rev:
150
201
            name = "rR%d" % n_rev
170
221
            assert m_rev is not None
171
222
            cluster = "other_history"
172
223
            color = "#ff0000"
 
224
        if node in self.lcas:
 
225
            color = "#9933cc"
173
226
        if node == self.base:
174
 
            color = "#33ff99"
 
227
            color = "#669933"
 
228
            if node == self.new_base:
 
229
                color = "#33ff33"
 
230
        if node == self.new_base:
 
231
            color = '#33cc99'
175
232
 
176
233
        label = [name]
177
 
        committer, message, date = get_rev_info(node, self.branch.repository)
 
234
        committer, message, nick, date = get_rev_info(node,
 
235
                                                      self.branch.repository)
178
236
        if committer is not None:
179
237
            label.append(committer)
180
238
 
 
239
        if nick is not None:
 
240
            label.append(nick)
 
241
 
181
242
        if date is not None:
182
243
            label.append(date)
183
244
 
187
248
        else:
188
249
            rank = None
189
250
 
190
 
        d_node = Node("n%d" % num, color=color, label="\\n".join(label), 
 
251
        d_node = Node("n%d" % num, color=color, label="\\n".join(label),
191
252
                    rev_id=node, cluster=cluster, message=message,
192
253
                    date=date)
193
254
        d_node.rank = rank
196
257
            d_node.node_style.append('dotted')
197
258
 
198
259
        return d_node
199
 
        
200
 
    def get_relations(self, collapse=False):
 
260
 
 
261
    def get_relations(self, collapse=False, max_distance=None):
201
262
        dot_nodes = {}
202
263
        node_relations = []
203
264
        num = 0
204
265
        if collapse:
205
 
            visible_ancestors = compact_ancestors(self.descendants, 
206
 
                                                  self.ancestors, (self.base,))
 
266
            exceptions = self.lcas.union([self.base, self.new_base])
 
267
            visible_ancestors = compact_ancestors(self.descendants,
 
268
                                                  self.ancestors,
 
269
                                                  exceptions)
207
270
        else:
208
 
            visible_ancestors = self.ancestors
 
271
            visible_ancestors = {}
 
272
            for revision, parents in self.ancestors.iteritems():
 
273
                visible_ancestors[revision] = dict((p, 0) for p in parents)
 
274
        if max_distance is not None:
 
275
            min_distance = max(self.distances.values()) - max_distance
 
276
            visible_ancestors = dict((n, p) for n, p in
 
277
                                     visible_ancestors.iteritems() if
 
278
                                     self.distances[n] >= min_distance)
209
279
        for node, parents in visible_ancestors.iteritems():
210
280
            if node not in dot_nodes:
211
281
                dot_nodes[node] = self.dot_node(node, num)
212
282
                num += 1
213
 
            if visible_ancestors is self.ancestors:
214
 
                parent_iter = ((f, 0) for f in parents)
215
 
            else:
216
 
                parent_iter = (f for f in parents.iteritems())
217
 
            for parent, skipped in parent_iter:
 
283
            for parent, skipped in parents.iteritems():
218
284
                if parent not in dot_nodes:
219
285
                    dot_nodes[parent] = self.dot_node(parent, num)
220
286
                    num += 1
226
292
 
227
293
 
228
294
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
229
 
                        merge_branch=None, ranking="forced"):
 
295
                        merge_branch=None, ranking="forced", max_distance=None):
230
296
    b = Branch.open_containing(branch)[0]
231
297
    if merge_branch is not None:
232
298
        m = Branch.open_containing(merge_branch)[0]
238
304
            m.lock_read()
239
305
        try:
240
306
            grapher = Grapher(b, m)
241
 
            relations = grapher.get_relations(collapse)
 
307
            relations = grapher.get_relations(collapse, max_distance)
242
308
        finally:
243
309
            if m is not None:
244
310
                m.unlock()
250
316
    done = False
251
317
    if ext not in RSVG_OUTPUT_TYPES:
252
318
        antialias = False
253
 
    if antialias: 
 
319
    if antialias:
254
320
        output = list(output)
255
321
        try:
256
322
            invoke_dot_aa(output, filename, ext)
268
334
            done = True
269
335
        except NoDot, e:
270
336
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
271
 
                " is installed correctly, or use --noantialias")
 
337
                " is installed correctly.")
272
338
    elif ext == 'dot' and not done:
273
339
        my_file = file(filename, 'wb')
274
340
        for fragment in output:
278
344
            invoke_dot_html(output, filename)
279
345
        except NoDot, e:
280
346
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
281
 
                " is installed correctly, or use --noantialias")
 
347
                " is installed correctly.")
282
348
    elif not done:
283
349
        print "Unknown file extension: %s" % ext
284