← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2009-04-10 20:07:41 UTC
  • Revision ID: aaron@aaronbentley.com-20090410200741-qg98vn5l50mcwzd1
Get conflict-diff under test.

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
 
 
18
 
 
19
import time
 
20
 
 
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
 
17
26
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
24
 
from bzrlib.revision import MultipleRevisionSources
25
 
import bzrlib.errors
26
 
import re
27
 
import os.path
28
 
import time
 
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