← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Max Bowsher
  • Date: 2009-11-13 00:43:08 UTC
  • mto: This revision was merged to the branch mainline in revision 739.
  • Revision ID: maxb@f2s.com-20091113004308-4dcwu1kwt3lhf1kp
Having discovered that bzr-builddeb import_dsc.py is a horrid copy-paste job of bzrtools upstream_import.py, restructure the change to minimize divergence from it.

Show diffs side-by-side

added added

removed removed

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