← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Robert Collins
  • Date: 2005-10-24 07:01:08 UTC
  • mto: (147.1.42) (364.1.3 bzrtools)
  • mto: This revision was merged to the branch mainline in revision 324.
  • Revision ID: robertc@robertcollins.net-20051024070108-f85025066b05f809
use sets and strings to optimise finding indirect merges somewhat

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