← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2005-09-23 03:08:27 UTC
  • Revision ID: aaron.bentley@utoronto.ca-20050923030827-bd5a4ebd3440daff
prevented accidental overwrites from push

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
1
 
# Copyright (C) 2005, 2008 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
 
 
18
 
 
 
1
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
 
2
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
 
3
from bzrlib.branch import Branch
 
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
 
9
from datetime import datetime
 
10
import bzrlib.errors
 
11
import re
 
12
import os.path
19
13
import time
20
14
 
21
 
from bzrlib.branch import Branch
22
 
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
 
from bzrlib.deprecated_graph import node_distances, select_farthest
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
 
 
40
 
 
41
15
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
42
16
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
43
17
            'abentley@lappy'                : 'Aaron Bentley',
47
21
            }
48
22
 
49
23
committer_alias = {'abentley': 'Aaron Bentley'}
 
24
def short_committer(committer):
 
25
    new_committer = re.sub('<.*>', '', committer).strip(' ')
 
26
    if len(new_committer) < 2:
 
27
        return committer
 
28
    return new_committer
 
29
 
50
30
def can_skip(rev_id, descendants, ancestors):
51
31
    if rev_id not in descendants:
52
32
        return False
67
47
    for me, my_parents in ancestors.iteritems():
68
48
        if me in skip:
69
49
            continue
70
 
        new_ancestors[me] = {}
 
50
        new_ancestors[me] = {} 
71
51
        for parent in my_parents:
72
 
            new_parent = parent
 
52
            new_parent = parent 
73
53
            distance = 0
74
54
            while can_skip(new_parent, descendants, ancestors):
75
55
                if new_parent in exceptions:
80
60
                new_parent = list(ancestors[new_parent])[0]
81
61
                distance += 1
82
62
            new_ancestors[me][new_parent] = distance
83
 
    return new_ancestors
 
63
    return new_ancestors    
84
64
 
85
65
def get_rev_info(rev_id, source):
86
66
    """Return the committer, message, and date of a revision."""
88
68
    message = None
89
69
    date = None
90
70
    if rev_id == 'null:':
91
 
        return None, 'Null Revision', None, None
 
71
        return None, 'Null Revision', None
92
72
    try:
93
73
        rev = source.get_revision(rev_id)
94
74
    except NoSuchRevision:
95
75
        try:
96
76
            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')
97
77
            if committer == '':
98
 
                return None, None, None, None
 
78
                return None, None, None
99
79
        except ValueError:
100
 
            return None, None, None, None
 
80
            return None, None, None
101
81
    else:
102
82
        committer = short_committer(rev.committer)
103
83
        if rev.message is not None:
104
84
            message = rev.message.split('\n')[0]
105
85
        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))
106
 
        date = time.strftime('%Y/%m/%d', gmtime)
107
 
        nick = rev.properties.get('branch-nick')
 
86
        date = time.strftime('%Y-%m-%d', gmtime)
108
87
    if '@' in committer:
109
88
        try:
110
89
            committer = mail_map[committer]
114
93
        committer = committer_alias[committer]
115
94
    except KeyError:
116
95
        pass
117
 
    return committer, message, nick, date
 
96
    return committer, message, date
118
97
 
119
98
class Grapher(object):
120
 
 
121
99
    def __init__(self, branch, other_branch=None):
122
100
        object.__init__(self)
123
101
        self.branch = branch
124
102
        self.other_branch = other_branch
 
103
        revision_a = self.branch.last_patch()
125
104
        if other_branch is not None:
126
 
            other_repo = other_branch.repository
127
 
            revision_b = self.other_branch.last_revision()
 
105
            greedy_fetch(branch, other_branch)
 
106
            revision_b = self.other_branch.last_patch()
 
107
            try:
 
108
                self.root, self.ancestors, self.descendants, self.common = \
 
109
                    combined_graph(revision_a, revision_b, self.branch)
 
110
            except bzrlib.errors.NoCommonRoot:
 
111
                raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
128
112
        else:
129
 
            other_repo = None
130
 
            revision_b = None
131
 
        self.graph = self.branch.repository.get_graph(other_repo)
132
 
        revision_a = self.branch.last_revision()
133
 
        self.scan_graph(revision_a, revision_b)
 
113
            self.root, self.ancestors, self.descendants = \
 
114
                revision_graph(revision_a, branch)
 
115
            self.common = []
 
116
 
134
117
        self.n_history = branch.revision_history()
135
 
        self.n_revnos = branch.get_revision_id_to_revno_map()
136
 
        self.distances = node_distances(self.descendants, self.ancestors,
 
118
        self.distances = node_distances(self.descendants, self.ancestors, 
137
119
                                        self.root)
138
120
        if other_branch is not None:
139
121
            self.base = select_farthest(self.distances, self.common)
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)
 
122
            self.m_history = other_branch.revision_history() 
145
123
        else:
146
124
            self.base = None
147
 
            self.new_base = None
148
 
            self.lcas = set()
149
125
            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))
183
126
 
184
127
    def dot_node(self, node, num):
185
128
        try:
191
134
        except ValueError:
192
135
            m_rev = None
193
136
        if (n_rev, m_rev) == (None, None):
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:]
 
137
            name = node[-5:]
199
138
            cluster = None
200
139
        elif n_rev == m_rev:
201
140
            name = "rR%d" % n_rev
221
160
            assert m_rev is not None
222
161
            cluster = "other_history"
223
162
            color = "#ff0000"
224
 
        if node in self.lcas:
225
 
            color = "#9933cc"
226
163
        if node == self.base:
227
 
            color = "#669933"
228
 
            if node == self.new_base:
229
 
                color = "#33ff33"
230
 
        if node == self.new_base:
231
 
            color = '#33cc99'
 
164
            color = "#33ff99"
232
165
 
233
166
        label = [name]
234
 
        committer, message, nick, date = get_rev_info(node,
235
 
                                                      self.branch.repository)
 
167
        committer, message, date = get_rev_info(node, self.branch)
236
168
        if committer is not None:
237
169
            label.append(committer)
238
170
 
239
 
        if nick is not None:
240
 
            label.append(nick)
241
 
 
242
171
        if date is not None:
243
172
            label.append(date)
244
173
 
248
177
        else:
249
178
            rank = None
250
179
 
251
 
        d_node = Node("n%d" % num, color=color, label="\\n".join(label),
 
180
        d_node = Node("n%d" % num, color=color, label="\\n".join(label), 
252
181
                    rev_id=node, cluster=cluster, message=message,
253
182
                    date=date)
254
183
        d_node.rank = rank
257
186
            d_node.node_style.append('dotted')
258
187
 
259
188
        return d_node
260
 
 
261
 
    def get_relations(self, collapse=False, max_distance=None):
 
189
        
 
190
    def get_relations(self, collapse=False):
262
191
        dot_nodes = {}
263
192
        node_relations = []
264
193
        num = 0
265
194
        if collapse:
266
 
            exceptions = self.lcas.union([self.base, self.new_base])
267
 
            visible_ancestors = compact_ancestors(self.descendants,
268
 
                                                  self.ancestors,
269
 
                                                  exceptions)
 
195
            visible_ancestors = compact_ancestors(self.descendants, 
 
196
                                                  self.ancestors, (self.base,))
270
197
        else:
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)
 
198
            visible_ancestors = self.ancestors
279
199
        for node, parents in visible_ancestors.iteritems():
280
200
            if node not in dot_nodes:
281
201
                dot_nodes[node] = self.dot_node(node, num)
282
202
                num += 1
283
 
            for parent, skipped in parents.iteritems():
 
203
            if visible_ancestors is self.ancestors:
 
204
                parent_iter = ((f, 0) for f in parents)
 
205
            else:
 
206
                parent_iter = (f for f in parents.iteritems())
 
207
            for parent, skipped in parent_iter:
284
208
                if parent not in dot_nodes:
285
209
                    dot_nodes[parent] = self.dot_node(parent, num)
286
210
                    num += 1
292
216
 
293
217
 
294
218
def write_ancestry_file(branch, filename, collapse=True, antialias=True,
295
 
                        merge_branch=None, ranking="forced", max_distance=None):
296
 
    b = Branch.open_containing(branch)[0]
 
219
                        merge_branch=None, ranking="forced"):
 
220
    b = Branch.open_containing(branch)
297
221
    if merge_branch is not None:
298
 
        m = Branch.open_containing(merge_branch)[0]
 
222
        m = Branch.open_containing(merge_branch)
299
223
    else:
300
224
        m = None
301
 
    b.lock_write()
302
 
    try:
303
 
        if m is not None:
304
 
            m.lock_read()
305
 
        try:
306
 
            grapher = Grapher(b, m)
307
 
            relations = grapher.get_relations(collapse, max_distance)
308
 
        finally:
309
 
            if m is not None:
310
 
                m.unlock()
311
 
    finally:
312
 
        b.unlock()
 
225
    grapher = Grapher(b, m)
 
226
    relations = grapher.get_relations(collapse)
313
227
 
314
228
    ext = filename.split('.')[-1]
315
229
    output = dot_output(relations, ranking)
316
230
    done = False
317
231
    if ext not in RSVG_OUTPUT_TYPES:
318
232
        antialias = False
319
 
    if antialias:
 
233
    if antialias: 
320
234
        output = list(output)
321
235
        try:
322
236
            invoke_dot_aa(output, filename, ext)
334
248
            done = True
335
249
        except NoDot, e:
336
250
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
337
 
                " is installed correctly.")
 
251
                " is installed correctly, or use --noantialias")
338
252
    elif ext == 'dot' and not done:
339
253
        my_file = file(filename, 'wb')
340
254
        for fragment in output:
341
 
            my_file.write(fragment.encode('utf-8'))
 
255
            my_file.write(fragment)
342
256
    elif ext == 'html':
343
257
        try:
344
258
            invoke_dot_html(output, filename)
345
259
        except NoDot, e:
346
260
            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\
347
 
                " is installed correctly.")
 
261
                " is installed correctly, or use --noantialias")
348
262
    elif not done:
349
263
        print "Unknown file extension: %s" % ext
 
264