← 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-12-13 16:54:59 UTC
  • Revision ID: abentley@panoramicfeedback.com-20051213165459-e7785dda3c5605c6
Updated docs

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