source: gprof2dot.py

Last change on this file was fda1c7b, checked in by Martin Kolman <martin.kolman@…>, 3 months ago

Some PEP8 for gprof2dot.py

  • Property mode set to 100755
File size: 78.6 KB
Line 
1#!/usr/bin/env python
2#
3# Copyright 2008-2009 Jose Fonseca
4#
5# This program is free software: you can redistribute it and/or modify it
6# under the terms of the GNU Lesser General Public License as published
7# by the Free Software Foundation, either version 3 of the License, or
8# (at your option) any later version.
9#
10# This program is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13# GNU Lesser General Public License for more details.
14#
15# You should have received a copy of the GNU Lesser General Public License
16# along with this program.  If not, see <http://www.gnu.org/licenses/>.
17#
18
19"""Generate a dot graph from the output of several profilers."""
20
21__author__ = "Jose Fonseca"
22
23__version__ = "1.0"
24
25
26import sys
27import math
28import os.path
29import re
30import textwrap
31import optparse
32import xml.parsers.expat
33
34
35try:
36    # Debugging helper module
37    import debug
38except ImportError:
39    pass
40
41
42def times(x):
43    return u"%u\xd7" % (x,)
44
45
46def percentage(p):
47    return "%.02f%%" % (p*100.0,)
48
49
50def add(a, b):
51    return a + b
52
53
54def equal(a, b):
55    if a == b:
56        return a
57    else:
58        return None
59
60
61def fail(a, b):
62    assert False
63
64
65tol = 2 ** -23
66
67
68def ratio(numerator, denominator):
69    try:
70        ratio = float(numerator)/float(denominator)
71    except ZeroDivisionError:
72        # 0/0 is undefined, but 1.0 yields more useful results
73        return 1.0
74    if ratio < 0.0:
75        if ratio < -tol:
76            sys.stderr.write('warning: negative ratio (%s/%s)\n' % (numerator, denominator))
77        return 0.0
78    if ratio > 1.0:
79        if ratio > 1.0 + tol:
80            sys.stderr.write('warning: ratio greater than one (%s/%s)\n' % (numerator, denominator))
81        return 1.0
82    return ratio
83
84
85class UndefinedEvent(Exception):
86    """Raised when attempting to get an event which is undefined."""
87
88    def __init__(self, event):
89        Exception.__init__(self)
90        self.event = event
91
92    def __str__(self):
93        return 'unspecified event %s' % self.event.name
94
95
96class Event(object):
97    """Describe a kind of event, and its basic operations."""
98
99    def __init__(self, name, null, aggregator, formatter=str):
100        self.name = name
101        self._null = null
102        self._aggregator = aggregator
103        self._formatter = formatter
104
105    def __eq__(self, other):
106        return self is other
107
108    def __hash__(self):
109        return id(self)
110
111    def null(self):
112        return self._null
113
114    def aggregate(self, val1, val2):
115        """Aggregate two event values."""
116        assert val1 is not None
117        assert val2 is not None
118        return self._aggregator(val1, val2)
119
120    def format(self, val):
121        """Format an event value."""
122        assert val is not None
123        return self._formatter(val)
124
125
126CALLS = Event("Calls", 0, add, times)
127SAMPLES = Event("Samples", 0, add)
128SAMPLES2 = Event("Samples", 0, add)
129
130TIME = Event("Time", 0.0, add, lambda x: '(' + str(x) + ')')
131TIME_RATIO = Event("Time ratio", 0.0, add, lambda x: '(' + percentage(x) + ')')
132TOTAL_TIME = Event("Total time", 0.0, fail)
133TOTAL_TIME_RATIO = Event("Total time ratio", 0.0, fail, percentage)
134
135
136class Object(object):
137    """Base class for all objects in profile which can store events."""
138
139    def __init__(self, events=None):
140        if events is None:
141            self.events = {}
142        else:
143            self.events = events
144
145    def __hash__(self):
146        return id(self)
147
148    def __eq__(self, other):
149        return self is other
150
151    def __contains__(self, event):
152        return event in self.events
153
154    def __getitem__(self, event):
155        try:
156            return self.events[event]
157        except KeyError:
158            raise UndefinedEvent(event)
159
160    def __setitem__(self, event, value):
161        if value is None:
162            if event in self.events:
163                del self.events[event]
164        else:
165            self.events[event] = value
166
167
168class Call(Object):
169    """A call between functions.
170
171    There should be at most one call object for every pair of functions.
172    """
173
174    def __init__(self, callee_id):
175        Object.__init__(self)
176        self.callee_id = callee_id
177        self.ratio = None
178        self.weight = None
179
180
181class Function(Object):
182    """A function."""
183
184    def __init__(self, id, name):
185        Object.__init__(self)
186        self.id = id
187        self.name = name
188        self.module = None
189        self.process = None
190        self.calls = {}
191        self.called = None
192        self.weight = None
193        self.cycle = None
194
195    def add_call(self, call):
196        if call.callee_id in self.calls:
197            sys.stderr.write('warning: overwriting call from function %s to %s\n' % (str(self.id), str(call.callee_id)))
198        self.calls[call.callee_id] = call
199
200    # TODO: write utility functions
201
202    def __repr__(self):
203        return self.name
204
205
206class Cycle(Object):
207    """A cycle made from recursive function calls."""
208
209    def __init__(self):
210        Object.__init__(self)
211        # XXX: Do cycles need an id?
212        self.functions = set()
213
214    def add_function(self, function):
215        assert function not in self.functions
216        self.functions.add(function)
217        # XXX: Aggregate events?
218        if function.cycle is not None:
219            for other in function.cycle.functions:
220                if function not in self.functions:
221                    self.add_function(other)
222        function.cycle = self
223
224
225class Profile(Object):
226    """The whole profile."""
227
228    def __init__(self):
229        Object.__init__(self)
230        self.functions = {}
231        self.cycles = []
232
233    def add_function(self, function):
234        if function.id in self.functions:
235            sys.stderr.write('warning: overwriting function %s (id %s)\n' % (function.name, str(function.id)))
236        self.functions[function.id] = function
237
238    def add_cycle(self, cycle):
239        self.cycles.append(cycle)
240
241    def validate(self):
242        """Validate the edges."""
243
244        for function in self.functions.itervalues():
245            for callee_id in function.calls.keys():
246                assert function.calls[callee_id].callee_id == callee_id
247                if callee_id not in self.functions:
248                    sys.stderr.write('warning: call to undefined function %s from function %s\n' % (str(callee_id), function.name))
249                    del function.calls[callee_id]
250
251    def find_cycles(self):
252        """Find cycles using Tarjan's strongly connected components algorithm."""
253
254        # Apply the Tarjan's algorithm successively until all functions are visited
255        visited = set()
256        for function in self.functions.itervalues():
257            if function not in visited:
258                self._tarjan(function, 0, [], {}, {}, visited)
259        cycles = []
260        for function in self.functions.itervalues():
261            if function.cycle is not None and function.cycle not in cycles:
262                cycles.append(function.cycle)
263        self.cycles = cycles
264        if 0:
265            for cycle in cycles:
266                sys.stderr.write("Cycle:\n")
267                for member in cycle.functions:
268                    sys.stderr.write("\tFunction %s\n" % member.name)
269
270    def _tarjan(self, function, order, stack, orders, lowlinks, visited):
271        """Tarjan's strongly connected components algorithm.
272
273        See also:
274        - http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
275        """
276
277        visited.add(function)
278        orders[function] = order
279        lowlinks[function] = order
280        order += 1
281        pos = len(stack)
282        stack.append(function)
283        for call in function.calls.itervalues():
284            callee = self.functions[call.callee_id]
285            # TODO: use a set to optimize lookup
286            if callee not in orders:
287                order = self._tarjan(callee, order, stack, orders, lowlinks, visited)
288                lowlinks[function] = min(lowlinks[function], lowlinks[callee])
289            elif callee in stack:
290                lowlinks[function] = min(lowlinks[function], orders[callee])
291        if lowlinks[function] == orders[function]:
292            # Strongly connected component found
293            members = stack[pos:]
294            del stack[pos:]
295            if len(members) > 1:
296                cycle = Cycle()
297                for member in members:
298                    cycle.add_function(member)
299        return order
300
301    def call_ratios(self, event):
302        # Aggregate for incoming calls
303        cycle_totals = {}
304        for cycle in self.cycles:
305            cycle_totals[cycle] = 0.0
306        function_totals = {}
307        for function in self.functions.itervalues():
308            function_totals[function] = 0.0
309        for function in self.functions.itervalues():
310            for call in function.calls.itervalues():
311                if call.callee_id != function.id:
312                    callee = self.functions[call.callee_id]
313                    function_totals[callee] += call[event]
314                    if callee.cycle is not None and callee.cycle is not function.cycle:
315                        cycle_totals[callee.cycle] += call[event]
316
317        # Compute the ratios
318        for function in self.functions.itervalues():
319            for call in function.calls.itervalues():
320                assert call.ratio is None
321                if call.callee_id != function.id:
322                    callee = self.functions[call.callee_id]
323                    if callee.cycle is not None and callee.cycle is not function.cycle:
324                        total = cycle_totals[callee.cycle]
325                    else:
326                        total = function_totals[callee]
327                    call.ratio = ratio(call[event], total)
328
329    def integrate(self, outevent, inevent):
330        """Propagate function time ratio allong the function calls.
331
332        Must be called after finding the cycles.
333
334        See also:
335        - http://citeseer.ist.psu.edu/graham82gprof.html
336        """
337
338        # Sanity checking
339        assert outevent not in self
340        for function in self.functions.itervalues():
341            assert outevent not in function
342            assert inevent in function
343            for call in function.calls.itervalues():
344                assert outevent not in call
345                if call.callee_id != function.id:
346                    assert call.ratio is not None
347
348        # Aggregate the input for each cycle
349        for cycle in self.cycles:
350            total = inevent.null()
351            for function in self.functions.itervalues():
352                total = inevent.aggregate(total, function[inevent])
353            self[inevent] = total
354
355        # Integrate along the edges
356        total = inevent.null()
357        for function in self.functions.itervalues():
358            total = inevent.aggregate(total, function[inevent])
359            self._integrate_function(function, outevent, inevent)
360        self[outevent] = total
361
362    def _integrate_function(self, function, outevent, inevent):
363        if function.cycle is not None:
364            return self._integrate_cycle(function.cycle, outevent, inevent)
365        else:
366            if outevent not in function:
367                total = function[inevent]
368                for call in function.calls.itervalues():
369                    if call.callee_id != function.id:
370                        total += self._integrate_call(call, outevent, inevent)
371                function[outevent] = total
372            return function[outevent]
373
374    def _integrate_call(self, call, outevent, inevent):
375        assert outevent not in call
376        assert call.ratio is not None
377        callee = self.functions[call.callee_id]
378        subtotal = call.ratio * self._integrate_function(callee, outevent, inevent)
379        call[outevent] = subtotal
380        return subtotal
381
382    def _integrate_cycle(self, cycle, outevent, inevent):
383        if outevent not in cycle:
384
385            # Compute the outevent for the whole cycle
386            total = inevent.null()
387            for member in cycle.functions:
388                subtotal = member[inevent]
389                for call in member.calls.itervalues():
390                    callee = self.functions[call.callee_id]
391                    if callee.cycle is not cycle:
392                        subtotal += self._integrate_call(call, outevent, inevent)
393                total += subtotal
394            cycle[outevent] = total
395
396            # Compute the time propagated to callers of this cycle
397            callees = {}
398            for function in self.functions.itervalues():
399                if function.cycle is not cycle:
400                    for call in function.calls.itervalues():
401                        callee = self.functions[call.callee_id]
402                        if callee.cycle is cycle:
403                            try:
404                                callees[callee] += call.ratio
405                            except KeyError:
406                                callees[callee] = call.ratio
407
408            for member in cycle.functions:
409                member[outevent] = outevent.null()
410
411            for callee, call_ratio in callees.items():
412                ranks = {}
413                call_ratios = {}
414                partials = {}
415                self._rank_cycle_function(cycle, callee, 0, ranks)
416                self._call_ratios_cycle(cycle, callee, ranks, call_ratios, set())
417                partial = self._integrate_cycle_function(cycle, callee, call_ratio, partials, ranks, call_ratios, outevent, inevent)
418                assert partial == max(partials.values())
419                assert not total or abs(1.0 - partial/(call_ratio*total)) <= 0.001
420
421        return cycle[outevent]
422
423    def _rank_cycle_function(self, cycle, function, rank, ranks):
424        if function not in ranks or ranks[function] > rank:
425            ranks[function] = rank
426            for call in function.calls.itervalues():
427                if call.callee_id != function.id:
428                    callee = self.functions[call.callee_id]
429                    if callee.cycle is cycle:
430                        self._rank_cycle_function(cycle, callee, rank + 1, ranks)
431
432    def _call_ratios_cycle(self, cycle, function, ranks, call_ratios, visited):
433        if function not in visited:
434            visited.add(function)
435            for call in function.calls.itervalues():
436                if call.callee_id != function.id:
437                    callee = self.functions[call.callee_id]
438                    if callee.cycle is cycle:
439                        if ranks[callee] > ranks[function]:
440                            call_ratios[callee] = call_ratios.get(callee, 0.0) + call.ratio
441                            self._call_ratios_cycle(cycle, callee, ranks, call_ratios, visited)
442
443    def _integrate_cycle_function(self, cycle, function, partial_ratio, partials, ranks, call_ratios, outevent, inevent):
444        if function not in partials:
445            partial = partial_ratio*function[inevent]
446            for call in function.calls.itervalues():
447                if call.callee_id != function.id:
448                    callee = self.functions[call.callee_id]
449                    if callee.cycle is not cycle:
450                        assert outevent in call
451                        partial += partial_ratio*call[outevent]
452                    else:
453                        if ranks[callee] > ranks[function]:
454                            callee_partial = self._integrate_cycle_function(cycle, callee, partial_ratio, partials, ranks, call_ratios, outevent, inevent)
455                            call_ratio = ratio(call.ratio, call_ratios[callee])
456                            call_partial = call_ratio*callee_partial
457                            try:
458                                call[outevent] += call_partial
459                            except UndefinedEvent:
460                                call[outevent] = call_partial
461                            partial += call_partial
462            partials[function] = partial
463            try:
464                function[outevent] += partial
465            except UndefinedEvent:
466                function[outevent] = partial
467        return partials[function]
468
469    def aggregate(self, event):
470        """Aggregate an event for the whole profile."""
471
472        total = event.null()
473        for function in self.functions.itervalues():
474            try:
475                total = event.aggregate(total, function[event])
476            except UndefinedEvent:
477                return
478        self[event] = total
479
480    def ratio(self, outevent, inevent):
481        assert outevent not in self
482        assert inevent in self
483        for function in self.functions.itervalues():
484            assert outevent not in function
485            assert inevent in function
486            function[outevent] = ratio(function[inevent], self[inevent])
487            for call in function.calls.itervalues():
488                assert outevent not in call
489                if inevent in call:
490                    call[outevent] = ratio(call[inevent], self[inevent])
491        self[outevent] = 1.0
492
493    def prune(self, node_thres, edge_thres):
494        """Prune the profile"""
495
496        # compute the prune ratios
497        for function in self.functions.itervalues():
498            try:
499                function.weight = function[TOTAL_TIME_RATIO]
500            except UndefinedEvent:
501                pass
502
503            for call in function.calls.itervalues():
504                callee = self.functions[call.callee_id]
505
506                if TOTAL_TIME_RATIO in call:
507                    # handle exact cases first
508                    call.weight = call[TOTAL_TIME_RATIO]
509                else:
510                    try:
511                        # make a safe estimate
512                        call.weight = min(function[TOTAL_TIME_RATIO], callee[TOTAL_TIME_RATIO])
513                    except UndefinedEvent:
514                        pass
515
516        # prune the nodes
517        for function_id in self.functions.keys():
518            function = self.functions[function_id]
519            if function.weight is not None:
520                if function.weight < node_thres:
521                    del self.functions[function_id]
522
523        # prune the egdes
524        for function in self.functions.itervalues():
525            for callee_id in function.calls.keys():
526                call = function.calls[callee_id]
527                if callee_id not in self.functions or call.weight is not None and call.weight < edge_thres:
528                    del function.calls[callee_id]
529
530    def dump(self):
531        for function in self.functions.itervalues():
532            sys.stderr.write('Function %s:\n' % (function.name,))
533            self._dump_events(function.events)
534            for call in function.calls.itervalues():
535                callee = self.functions[call.callee_id]
536                sys.stderr.write('  Call %s:\n' % (callee.name,))
537                self._dump_events(call.events)
538        for cycle in self.cycles:
539            sys.stderr.write('Cycle:\n')
540            self._dump_events(cycle.events)
541            for function in cycle.functions:
542                sys.stderr.write('  Function %s\n' % (function.name,))
543
544    def _dump_events(self, events):
545        for event, value in events.items():
546            sys.stderr.write('    %s: %s\n' % (event.name, event.format(value)))
547
548
549class Struct:
550    """Masquerade a dictionary with a structure-like behavior."""
551
552    def __init__(self, attrs=None):
553        if attrs is None:
554            attrs = {}
555        self.__dict__['_attrs'] = attrs
556
557    def __getattr__(self, name):
558        try:
559            return self._attrs[name]
560        except KeyError:
561            raise AttributeError(name)
562
563    def __setattr__(self, name, value):
564        self._attrs[name] = value
565
566    def __str__(self):
567        return str(self._attrs)
568
569    def __repr__(self):
570        return repr(self._attrs)
571
572
573class ParseError(Exception):
574    """Raised when parsing to signal mismatches."""
575
576    def __init__(self, msg, line):
577        self.msg = msg
578        # TODO: store more source line information
579        self.line = line
580
581    def __str__(self):
582        return '%s: %r' % (self.msg, self.line)
583
584
585class Parser:
586    """Parser interface."""
587
588    def __init__(self):
589        pass
590
591    def parse(self):
592        raise NotImplementedError
593
594
595class LineParser(Parser):
596    """Base class for parsers that read line-based formats."""
597
598    def __init__(self, file):
599        Parser.__init__(self)
600        self._file = file
601        self.__line = None
602        self.__eof = False
603
604    def readline(self):
605        line = self._file.readline()
606        if not line:
607            self.__line = ''
608            self.__eof = True
609        self.__line = line.rstrip('\r\n')
610
611    def lookahead(self):
612        assert self.__line is not None
613        return self.__line
614
615    def consume(self):
616        assert self.__line is not None
617        line = self.__line
618        self.readline()
619        return line
620
621    def eof(self):
622        assert self.__line is not None
623        return self.__eof
624
625
626XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF = range(4)
627
628
629class XmlToken:
630
631    def __init__(self, type, name_or_data, attrs=None, line=None, column=None):
632        assert type in (XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF)
633        self.type = type
634        self.name_or_data = name_or_data
635        self.attrs = attrs
636        self.line = line
637        self.column = column
638
639    def __str__(self):
640        if self.type == XML_ELEMENT_START:
641            return '<' + self.name_or_data + ' ...>'
642        if self.type == XML_ELEMENT_END:
643            return '</' + self.name_or_data + '>'
644        if self.type == XML_CHARACTER_DATA:
645            return self.name_or_data
646        if self.type == XML_EOF:
647            return 'end of file'
648        assert 0
649
650
651class XmlTokenizer:
652    """Expat based XML tokenizer."""
653
654    def __init__(self, fp, skip_ws=True):
655        self.fp = fp
656        self.tokens = []
657        self.index = 0
658        self.final = False
659        self.skip_ws = skip_ws
660
661        self.character_pos = 0, 0
662        self.character_data = ''
663       
664        self.parser = xml.parsers.expat.ParserCreate()
665        self.parser.StartElementHandler  = self.handle_element_start
666        self.parser.EndElementHandler    = self.handle_element_end
667        self.parser.CharacterDataHandler = self.handle_character_data
668   
669    def handle_element_start(self, name, attributes):
670        self.finish_character_data()
671        line, column = self.pos()
672        token = XmlToken(XML_ELEMENT_START, name, attributes, line, column)
673        self.tokens.append(token)
674
675    def handle_element_end(self, name):
676        self.finish_character_data()
677        line, column = self.pos()
678        token = XmlToken(XML_ELEMENT_END, name, None, line, column)
679        self.tokens.append(token)
680
681    def handle_character_data(self, data):
682        if not self.character_data:
683            self.character_pos = self.pos()
684        self.character_data += data
685   
686    def finish_character_data(self):
687        if self.character_data:
688            if not self.skip_ws or not self.character_data.isspace():
689                line, column = self.character_pos
690                token = XmlToken(XML_CHARACTER_DATA, self.character_data, None, line, column)
691                self.tokens.append(token)
692            self.character_data = ''
693
694    def next(self):
695        size = 16*1024
696        while self.index >= len(self.tokens) and not self.final:
697            self.tokens = []
698            self.index = 0
699            data = self.fp.read(size)
700            self.final = len(data) < size
701            try:
702                self.parser.Parse(data, self.final)
703            except xml.parsers.expat.ExpatError, e:
704                # if e.code == xml.parsers.expat.errors.XML_ERROR_NO_ELEMENTS:
705                if e.code == 3:
706                    pass
707                else:
708                    raise e
709        if self.index >= len(self.tokens):
710            line, column = self.pos()
711            token = XmlToken(XML_EOF, None, None, line, column)
712        else:
713            token = self.tokens[self.index]
714            self.index += 1
715        return token
716
717    def pos(self):
718        return self.parser.CurrentLineNumber, self.parser.CurrentColumnNumber
719
720
721class XmlTokenMismatch(Exception):
722
723    def __init__(self, expected, found):
724        self.expected = expected
725        self.found = found
726
727    def __str__(self):
728        return '%u:%u: %s expected, %s found' % (self.found.line, self.found.column, str(self.expected), str(self.found))
729
730
731class XmlParser(Parser):
732    """Base XML document parser."""
733
734    def __init__(self, fp):
735        Parser.__init__(self)
736        self.tokenizer = XmlTokenizer(fp)
737        self.consume()
738
739    def consume(self):
740        self.token = self.tokenizer.next()
741
742    def match_element_start(self, name):
743        return self.token.type == XML_ELEMENT_START and self.token.name_or_data == name
744
745    def match_element_end(self, name):
746        return self.token.type == XML_ELEMENT_END and self.token.name_or_data == name
747
748    def element_start(self, name):
749        while self.token.type == XML_CHARACTER_DATA:
750            self.consume()
751        if self.token.type != XML_ELEMENT_START:
752            raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token)
753        if self.token.name_or_data != name:
754            raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token)
755        attrs = self.token.attrs
756        self.consume()
757        return attrs
758
759    def element_end(self, name):
760        while self.token.type == XML_CHARACTER_DATA:
761            self.consume()
762        if self.token.type != XML_ELEMENT_END:
763            raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token)
764        if self.token.name_or_data != name:
765            raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token)
766        self.consume()
767
768    def character_data(self, strip=True):
769        data = ''
770        while self.token.type == XML_CHARACTER_DATA:
771            data += self.token.name_or_data
772            self.consume()
773        if strip:
774            data = data.strip()
775        return data
776
777
778class GprofParser(Parser):
779    """Parser for GNU gprof output.
780
781    See also:
782    - Chapter "Interpreting gprof's Output" from the GNU gprof manual
783      http://sourceware.org/binutils/docs-2.18/gprof/Call-Graph.html#Call-Graph
784    - File "cg_print.c" from the GNU gprof source code
785      http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/gprof/cg_print.c?rev=1.12&cvsroot=src
786    """
787
788    def __init__(self, fp):
789        Parser.__init__(self)
790        self.fp = fp
791        self.functions = {}
792        self.cycles = {}
793
794    def readline(self):
795        line = self.fp.readline()
796        if not line:
797            sys.stderr.write('error: unexpected end of file\n')
798            sys.exit(1)
799        line = line.rstrip('\r\n')
800        return line
801
802    _int_re = re.compile(r'^\d+$')
803    _float_re = re.compile(r'^\d+\.\d+$')
804
805    def translate(self, mo):
806        """Extract a structure from a match object, while translating the types in the process."""
807        attrs = {}
808        groupdict = mo.groupdict()
809        for name, value in groupdict.items():
810            if value is None:
811                value = None
812            elif self._int_re.match(value):
813                value = int(value)
814            elif self._float_re.match(value):
815                value = float(value)
816            attrs[name] = (value)
817        return Struct(attrs)
818
819    _cg_header_re = re.compile(
820        # original gprof header
821        r'^\s+called/total\s+parents\s*$|' +
822        r'^index\s+%time\s+self\s+descendents\s+called\+self\s+name\s+index\s*$|' +
823        r'^\s+called/total\s+children\s*$|' +
824        # GNU gprof header
825        r'^index\s+%\s+time\s+self\s+children\s+called\s+name\s*$'
826    )
827
828    _cg_ignore_re = re.compile(
829        # spontaneous
830        r'^\s+<spontaneous>\s*$|'
831        # internal calls (such as "mcount")
832        r'^.*\((\d+)\)$'
833    )
834
835    _cg_primary_re = re.compile(
836        r'^\[(?P<index>\d+)\]?' +
837        r'\s+(?P<percentage_time>\d+\.\d+)' +
838        r'\s+(?P<self>\d+\.\d+)' +
839        r'\s+(?P<descendants>\d+\.\d+)' +
840        r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' +
841        r'\s+(?P<name>\S.*?)' +
842        r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
843        r'\s\[(\d+)\]$'
844    )
845
846    _cg_parent_re = re.compile(
847        r'^\s+(?P<self>\d+\.\d+)?' +
848        r'\s+(?P<descendants>\d+\.\d+)?' +
849        r'\s+(?P<called>\d+)(?:/(?P<called_total>\d+))?' +
850        r'\s+(?P<name>\S.*?)' +
851        r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
852        r'\s\[(?P<index>\d+)\]$'
853    )
854
855    _cg_child_re = _cg_parent_re
856
857    _cg_cycle_header_re = re.compile(
858        r'^\[(?P<index>\d+)\]?' +
859        r'\s+(?P<percentage_time>\d+\.\d+)' +
860        r'\s+(?P<self>\d+\.\d+)' +
861        r'\s+(?P<descendants>\d+\.\d+)' +
862        r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' +
863        r'\s+<cycle\s(?P<cycle>\d+)\sas\sa\swhole>' +
864        r'\s\[(\d+)\]$'
865    )
866
867    _cg_cycle_member_re = re.compile(
868        r'^\s+(?P<self>\d+\.\d+)?' +
869        r'\s+(?P<descendants>\d+\.\d+)?' +
870        r'\s+(?P<called>\d+)(?:\+(?P<called_self>\d+))?' +
871        r'\s+(?P<name>\S.*?)' +
872        r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
873        r'\s\[(?P<index>\d+)\]$'
874    )
875
876    _cg_sep_re = re.compile(r'^--+$')
877
878    def parse_function_entry(self, lines):
879        parents = []
880        children = []
881
882        while True:
883            if not lines:
884                sys.stderr.write('warning: unexpected end of entry\n')
885            line = lines.pop(0)
886            if line.startswith('['):
887                break
888
889            # read function parent line
890            mo = self._cg_parent_re.match(line)
891            if not mo:
892                if self._cg_ignore_re.match(line):
893                    continue
894                sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
895            else:
896                parent = self.translate(mo)
897                parents.append(parent)
898
899        # read primary line
900        mo = self._cg_primary_re.match(line)
901        if not mo:
902            sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
903            return
904        else:
905            function = self.translate(mo)
906
907        while lines:
908            line = lines.pop(0)
909
910            # read function subroutine line
911            mo = self._cg_child_re.match(line)
912            if not mo:
913                if self._cg_ignore_re.match(line):
914                    continue
915                sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
916            else:
917                child = self.translate(mo)
918                children.append(child)
919
920        function.parents = parents
921        function.children = children
922
923        self.functions[function.index] = function
924
925    def parse_cycle_entry(self, lines):
926
927        # read cycle header line
928        line = lines[0]
929        mo = self._cg_cycle_header_re.match(line)
930        if not mo:
931            sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
932            return
933        cycle = self.translate(mo)
934
935        # read cycle member lines
936        cycle.functions = []
937        for line in lines[1:]:
938            mo = self._cg_cycle_member_re.match(line)
939            if not mo:
940                sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
941                continue
942            call = self.translate(mo)
943            cycle.functions.append(call)
944
945        self.cycles[cycle.cycle] = cycle
946
947    def parse_cg_entry(self, lines):
948        if lines[0].startswith("["):
949            self.parse_cycle_entry(lines)
950        else:
951            self.parse_function_entry(lines)
952
953    def parse_cg(self):
954        """Parse the call graph."""
955
956        # skip call graph header
957        while not self._cg_header_re.match(self.readline()):
958            pass
959        line = self.readline()
960        while self._cg_header_re.match(line):
961            line = self.readline()
962
963        # process call graph entries
964        entry_lines = []
965        while line != '\014':  # form feed
966            if line and not line.isspace():
967                if self._cg_sep_re.match(line):
968                    self.parse_cg_entry(entry_lines)
969                    entry_lines = []
970                else:
971                    entry_lines.append(line)
972            line = self.readline()
973
974    def parse(self):
975        self.parse_cg()
976        self.fp.close()
977
978        profile = Profile()
979        profile[TIME] = 0.0
980
981        cycles = {}
982        for index in self.cycles.iterkeys():
983            cycles[index] = Cycle()
984
985        for entry in self.functions.itervalues():
986            # populate the function
987            function = Function(entry.index, entry.name)
988            function[TIME] = entry.self
989            if entry.called is not None:
990                function.called = entry.called
991            if entry.called_self is not None:
992                call = Call(entry.index)
993                call[CALLS] = entry.called_self
994                function.called += entry.called_self
995
996            # populate the function calls
997            for child in entry.children:
998                call = Call(child.index)
999
1000                assert child.called is not None
1001                call[CALLS] = child.called
1002
1003                if child.index not in self.functions:
1004                    # NOTE: functions that were never called but were discovered by gprof's
1005                    # static call graph analysis dont have a call graph entry so we need
1006                    # to add them here
1007                    missing = Function(child.index, child.name)
1008                    function[TIME] = 0.0
1009                    function.called = 0
1010                    profile.add_function(missing)
1011
1012                function.add_call(call)
1013
1014            profile.add_function(function)
1015
1016            if entry.cycle is not None:
1017                try:
1018                    cycle = cycles[entry.cycle]
1019                except KeyError:
1020                    sys.stderr.write('warning: <cycle %u as a whole> entry missing\n' % entry.cycle)
1021                    cycle = Cycle()
1022                    cycles[entry.cycle] = cycle
1023                cycle.add_function(function)
1024
1025            profile[TIME] = profile[TIME] + function[TIME]
1026
1027        for cycle in cycles.itervalues():
1028            profile.add_cycle(cycle)
1029
1030        # Compute derived events
1031        profile.validate()
1032        profile.ratio(TIME_RATIO, TIME)
1033        profile.call_ratios(CALLS)
1034        profile.integrate(TOTAL_TIME, TIME)
1035        profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
1036
1037        return profile
1038
1039
1040class CallgrindParser(LineParser):
1041    """Parser for valgrind's callgrind tool.
1042
1043    See also:
1044    - http://valgrind.org/docs/manual/cl-format.html
1045    """
1046
1047    _call_re = re.compile('^calls=\s*(\d+)\s+((\d+|\+\d+|-\d+|\*)\s+)+$')
1048
1049    def __init__(self, infile):
1050        LineParser.__init__(self, infile)
1051
1052        # Textual positions
1053        self.position_ids = {}
1054        self.positions = {}
1055
1056        # Numeric positions
1057        self.num_positions = 1
1058        self.cost_positions = ['line']
1059        self.last_positions = [0]
1060
1061        # Events
1062        self.num_events = 0
1063        self.cost_events = []
1064
1065        self.profile = Profile()
1066        self.profile[SAMPLES] = 0
1067
1068    def parse(self):
1069        # read lookahead
1070        self.readline()
1071
1072        self.parse_key('version')
1073        self.parse_key('creator')
1074        self.parse_part()
1075
1076        # compute derived data
1077        self.profile.validate()
1078        self.profile.find_cycles()
1079        self.profile.ratio(TIME_RATIO, SAMPLES)
1080        self.profile.call_ratios(CALLS)
1081        self.profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1082
1083        return self.profile
1084
1085    def parse_part(self):
1086        while self.parse_header_line():
1087            pass
1088        while self.parse_body_line():
1089            pass
1090        return True
1091
1092    def parse_header_line(self):
1093        return \
1094            self.parse_empty() or \
1095            self.parse_comment() or \
1096            self.parse_part_detail() or \
1097            self.parse_description() or \
1098            self.parse_event_specification() or \
1099            self.parse_cost_line_def() or \
1100            self.parse_cost_summary()
1101
1102    _detail_keys = set(('cmd', 'pid', 'thread', 'part'))
1103
1104    def parse_part_detail(self):
1105        return self.parse_keys(self._detail_keys)
1106
1107    def parse_description(self):
1108        return self.parse_key('desc') is not None
1109
1110    def parse_event_specification(self):
1111        event = self.parse_key('event')
1112        if event is None:
1113            return False
1114        return True
1115
1116    def parse_cost_line_def(self):
1117        pair = self.parse_keys(('events', 'positions'))
1118        if pair is None:
1119            return False
1120        key, value = pair
1121        items = value.split()
1122        if key == 'events':
1123            self.num_events = len(items)
1124            self.cost_events = items
1125        if key == 'positions':
1126            self.num_positions = len(items)
1127            self.cost_positions = items
1128            self.last_positions = [0]*self.num_positions
1129        return True
1130
1131    def parse_cost_summary(self):
1132        pair = self.parse_keys(('summary', 'totals'))
1133        if pair is None:
1134            return False
1135        return True
1136
1137    def parse_body_line(self):
1138        return \
1139            self.parse_empty() or \
1140            self.parse_comment() or \
1141            self.parse_cost_line() or \
1142            self.parse_position_spec() or \
1143            self.parse_association_spec()
1144
1145    _cost_re = re.compile(r'^(\d+|\+\d+|-\d+|\*)( \d+)+$')
1146
1147    def parse_cost_line(self, calls=None):
1148        line = self.lookahead()
1149        mo = self._cost_re.match(line)
1150        if not mo:
1151            return False
1152
1153        function = self.get_function()
1154
1155        values = line.split(' ')
1156        assert len(values) == self.num_positions + self.num_events
1157
1158        positions = values[0: self.num_positions]
1159        events = values[self.num_positions:]
1160
1161        for i in range(self.num_positions):
1162            position = positions[i]
1163            if position == '*':
1164                position = self.last_positions[i]
1165            elif position[0] in '-+':
1166                position = self.last_positions[i] + int(position)
1167            else:
1168                position = int(position)
1169            self.last_positions[i] = position
1170
1171        events = map(float, events)
1172
1173        if calls is None:
1174            function[SAMPLES] += events[0]
1175            self.profile[SAMPLES] += events[0]
1176        else:
1177            callee = self.get_callee()
1178            callee.called += calls
1179
1180            try:
1181                call = function.calls[callee.id]
1182            except KeyError:
1183                call = Call(callee.id)
1184                call[CALLS] = calls
1185                call[SAMPLES] = events[0]
1186                function.add_call(call)
1187            else:
1188                call[CALLS] += calls
1189                call[SAMPLES] += events[0]
1190
1191        self.consume()
1192        return True
1193
1194    def parse_association_spec(self):
1195        line = self.lookahead()
1196        if not line.startswith('calls='):
1197            return False
1198
1199        _, values = line.split('=', 1)
1200        values = values.strip().split()
1201        calls = int(values[0])
1202        call_position = values[1:]
1203        self.consume()
1204
1205        self.parse_cost_line(calls)
1206
1207        return True
1208
1209    _position_re = re.compile('^(?P<position>c?(?:ob|fl|fi|fe|fn))=\s*(?:\((?P<id>\d+)\))?(?:\s*(?P<name>.+))?')
1210
1211    _position_table_map = {
1212        'ob': 'ob',
1213        'fl': 'fl',
1214        'fi': 'fl',
1215        'fe': 'fl',
1216        'fn': 'fn',
1217        'cob': 'ob',
1218        'cfl': 'fl',
1219        'cfi': 'fl',
1220        'cfe': 'fl',
1221        'cfn': 'fn',
1222    }
1223
1224    _position_map = {
1225        'ob': 'ob',
1226        'fl': 'fl',
1227        'fi': 'fl',
1228        'fe': 'fl',
1229        'fn': 'fn',
1230        'cob': 'cob',
1231        'cfl': 'cfl',
1232        'cfi': 'cfl',
1233        'cfe': 'cfl',
1234        'cfn': 'cfn',
1235    }
1236
1237    def parse_position_spec(self):
1238        line = self.lookahead()
1239        mo = self._position_re.match(line)
1240        if not mo:
1241            return False
1242
1243        position, id, name = mo.groups()
1244        if id:
1245            table = self._position_table_map[position]
1246            if name:
1247                self.position_ids[(table, id)] = name
1248            else:
1249                name = self.position_ids.get((table, id), '')
1250        self.positions[self._position_map[position]] = name
1251        self.consume()
1252        return True
1253
1254    def parse_empty(self):
1255        line = self.lookahead()
1256        if line.strip():
1257            return False
1258        self.consume()
1259        return True
1260
1261    def parse_comment(self):
1262        line = self.lookahead()
1263        if not line.startswith('#'):
1264            return False
1265        self.consume()
1266        return True
1267
1268    _key_re = re.compile(r'^(\w+):')
1269
1270    def parse_key(self, key):
1271        pair = self.parse_keys((key,))
1272        if not pair:
1273            return None
1274        key, value = pair
1275        return value
1276        line = self.lookahead()
1277        mo = self._key_re.match(line)
1278        if not mo:
1279            return None
1280        key, value = line.split(':', 1)
1281        if key not in keys:
1282            return None
1283        value = value.strip()
1284        self.consume()
1285        return key, value
1286
1287    def parse_keys(self, keys):
1288        line = self.lookahead()
1289        mo = self._key_re.match(line)
1290        if not mo:
1291            return None
1292        key, value = line.split(':', 1)
1293        if key not in keys:
1294            return None
1295        value = value.strip()
1296        self.consume()
1297        return key, value
1298
1299    def make_function(self, module, filename, name):
1300        # FIXME: module and filename are not being tracked reliably
1301        #id = '|'.join((module, filename, name))
1302        id = name
1303        try:
1304            function = self.profile.functions[id]
1305        except KeyError:
1306            function = Function(id, name)
1307            function[SAMPLES] = 0
1308            function.called = 0
1309            self.profile.add_function(function)
1310        return function
1311
1312    def get_function(self):
1313        module = self.positions.get('ob', '')
1314        filename = self.positions.get('fl', '')
1315        function = self.positions.get('fn', '')
1316        return self.make_function(module, filename, function)
1317
1318    def get_callee(self):
1319        module = self.positions.get('cob', '')
1320        filename = self.positions.get('cfi', '')
1321        function = self.positions.get('cfn', '')
1322        return self.make_function(module, filename, function)
1323
1324
1325class OprofileParser(LineParser):
1326    """Parser for oprofile callgraph output.
1327
1328    See also:
1329    - http://oprofile.sourceforge.net/doc/opreport.html#opreport-callgraph
1330    """
1331
1332    _fields_re = {
1333        'samples': r'(\d+)',
1334        '%': r'(\S+)',
1335        'linenr info': r'(?P<source>\(no location information\)|\S+:\d+)',
1336        'image name': r'(?P<image>\S+(?:\s\(tgid:[^)]*\))?)',
1337        'app name': r'(?P<application>\S+)',
1338        'symbol name': r'(?P<symbol>\(no symbols\)|.+?)',
1339    }
1340
1341    def __init__(self, infile):
1342        LineParser.__init__(self, infile)
1343        self.entries = {}
1344        self.entry_re = None
1345
1346    def add_entry(self, callers, function, callees):
1347        try:
1348            entry = self.entries[function.id]
1349        except KeyError:
1350            self.entries[function.id] = (callers, function, callees)
1351        else:
1352            callers_total, function_total, callees_total = entry
1353            self.update_subentries_dict(callers_total, callers)
1354            function_total.samples += function.samples
1355            self.update_subentries_dict(callees_total, callees)
1356
1357    def update_subentries_dict(self, totals, partials):
1358        for partial in partials.itervalues():
1359            try:
1360                total = totals[partial.id]
1361            except KeyError:
1362                totals[partial.id] = partial
1363            else:
1364                total.samples += partial.samples
1365
1366    def parse(self):
1367        # read lookahead
1368        self.readline()
1369
1370        self.parse_header()
1371        while self.lookahead():
1372            self.parse_entry()
1373
1374        profile = Profile()
1375
1376        reverse_call_samples = {}
1377
1378        # populate the profile
1379        profile[SAMPLES] = 0
1380        for _callers, _function, _callees in self.entries.itervalues():
1381            function = Function(_function.id, _function.name)
1382            function[SAMPLES] = _function.samples
1383            profile.add_function(function)
1384            profile[SAMPLES] += _function.samples
1385
1386            if _function.application:
1387                function.process = os.path.basename(_function.application)
1388            if _function.image:
1389                function.module = os.path.basename(_function.image)
1390
1391            total_callee_samples = 0
1392            for _callee in _callees.itervalues():
1393                total_callee_samples += _callee.samples
1394
1395            for _callee in _callees.itervalues():
1396                if not _callee.self:
1397                    call = Call(_callee.id)
1398                    call[SAMPLES2] = _callee.samples
1399                    function.add_call(call)
1400
1401        # compute derived data
1402        profile.validate()
1403        profile.find_cycles()
1404        profile.ratio(TIME_RATIO, SAMPLES)
1405        profile.call_ratios(SAMPLES2)
1406        profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1407
1408        return profile
1409
1410    def parse_header(self):
1411        while not self.match_header():
1412            self.consume()
1413        line = self.lookahead()
1414        fields = re.split(r'\s\s+', line)
1415        entry_re = r'^\s*' + r'\s+'.join([self._fields_re[field] for field in fields]) + r'(?P<self>\s+\[self\])?$'
1416        self.entry_re = re.compile(entry_re)
1417        self.skip_separator()
1418
1419    def parse_entry(self):
1420        callers = self.parse_subentries()
1421        if self.match_primary():
1422            function = self.parse_subentry()
1423            if function is not None:
1424                callees = self.parse_subentries()
1425                self.add_entry(callers, function, callees)
1426        self.skip_separator()
1427
1428    def parse_subentries(self):
1429        subentries = {}
1430        while self.match_secondary():
1431            subentry = self.parse_subentry()
1432            subentries[subentry.id] = subentry
1433        return subentries
1434
1435    def parse_subentry(self):
1436        entry = Struct()
1437        line = self.consume()
1438        mo = self.entry_re.match(line)
1439        if not mo:
1440            raise ParseError('failed to parse', line)
1441        fields = mo.groupdict()
1442        entry.samples = int(mo.group(1))
1443        if 'source' in fields and fields['source'] != '(no location information)':
1444            source = fields['source']
1445            filename, lineno = source.split(':')
1446            entry.filename = filename
1447            entry.lineno = int(lineno)
1448        else:
1449            source = ''
1450            entry.filename = None
1451            entry.lineno = None
1452        entry.image = fields.get('image', '')
1453        entry.application = fields.get('application', '')
1454        if 'symbol' in fields and fields['symbol'] != '(no symbols)':
1455            entry.symbol = fields['symbol']
1456        else:
1457            entry.symbol = ''
1458        if entry.symbol.startswith('"') and entry.symbol.endswith('"'):
1459            entry.symbol = entry.symbol[1:-1]
1460        entry.id = ':'.join((entry.application, entry.image, source, entry.symbol))
1461        entry.self = fields.get('self', None) != None
1462        if entry.self:
1463            entry.id += ':self'
1464        if entry.symbol:
1465            entry.name = entry.symbol
1466        else:
1467            entry.name = entry.image
1468        return entry
1469
1470    def skip_separator(self):
1471        while not self.match_separator():
1472            self.consume()
1473        self.consume()
1474
1475    def match_header(self):
1476        line = self.lookahead()
1477        return line.startswith('samples')
1478
1479    def match_separator(self):
1480        line = self.lookahead()
1481        return line == '-'*len(line)
1482
1483    def match_primary(self):
1484        line = self.lookahead()
1485        return not line[:1].isspace()
1486
1487    def match_secondary(self):
1488        line = self.lookahead()
1489        return line[:1].isspace()
1490
1491
1492class SysprofParser(XmlParser):
1493
1494    def __init__(self, stream):
1495        XmlParser.__init__(self, stream)
1496
1497    def parse(self):
1498        objects = {}
1499        nodes = {}
1500
1501        self.element_start('profile')
1502        while self.token.type == XML_ELEMENT_START:
1503            if self.token.name_or_data == 'objects':
1504                assert not objects
1505                objects = self.parse_items('objects')
1506            elif self.token.name_or_data == 'nodes':
1507                assert not nodes
1508                nodes = self.parse_items('nodes')
1509            else:
1510                self.parse_value(self.token.name_or_data)
1511        self.element_end('profile')
1512
1513        return self.build_profile(objects, nodes)
1514
1515    def parse_items(self, name):
1516        assert name[-1] == 's'
1517        items = {}
1518        self.element_start(name)
1519        while self.token.type == XML_ELEMENT_START:
1520            id, values = self.parse_item(name[:-1])
1521            assert id not in items
1522            items[id] = values
1523        self.element_end(name)
1524        return items
1525
1526    def parse_item(self, name):
1527        attrs = self.element_start(name)
1528        id = int(attrs['id'])
1529        values = self.parse_values()
1530        self.element_end(name)
1531        return id, values
1532
1533    def parse_values(self):
1534        values = {}
1535        while self.token.type == XML_ELEMENT_START:
1536            name = self.token.name_or_data
1537            value = self.parse_value(name)
1538            assert name not in values
1539            values[name] = value
1540        return values
1541
1542    def parse_value(self, tag):
1543        self.element_start(tag)
1544        value = self.character_data()
1545        self.element_end(tag)
1546        if value.isdigit():
1547            return int(value)
1548        if value.startswith('"') and value.endswith('"'):
1549            return value[1:-1]
1550        return value
1551
1552    def build_profile(self, objects, nodes):
1553        profile = Profile()
1554
1555        profile[SAMPLES] = 0
1556        for id, object in objects.items():
1557            # Ignore fake objects (process names, modules, "Everything", "kernel", etc.)
1558            if object['self'] == 0:
1559                continue
1560
1561            function = Function(id, object['name'])
1562            function[SAMPLES] = object['self']
1563            profile.add_function(function)
1564            profile[SAMPLES] += function[SAMPLES]
1565
1566        for id, node in nodes.items():
1567            # Ignore fake calls
1568            if node['self'] == 0:
1569                continue
1570
1571            # Find a non-ignored parent
1572            parent_id = node['parent']
1573            while parent_id != 0:
1574                parent = nodes[parent_id]
1575                caller_id = parent['object']
1576                if objects[caller_id]['self'] != 0:
1577                    break
1578                parent_id = parent['parent']
1579            if parent_id == 0:
1580                continue
1581
1582            callee_id = node['object']
1583
1584            assert objects[caller_id]['self']
1585            assert objects[callee_id]['self']
1586
1587            function = profile.functions[caller_id]
1588
1589            samples = node['self']
1590            try:
1591                call = function.calls[callee_id]
1592            except KeyError:
1593                call = Call(callee_id)
1594                call[SAMPLES2] = samples
1595                function.add_call(call)
1596            else:
1597                call[SAMPLES2] += samples
1598
1599        # Compute derived events
1600        profile.validate()
1601        profile.find_cycles()
1602        profile.ratio(TIME_RATIO, SAMPLES)
1603        profile.call_ratios(SAMPLES2)
1604        profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1605
1606        return profile
1607
1608
1609class SharkParser(LineParser):
1610    """Parser for MacOSX Shark output.
1611
1612    Author: tom@dbservice.com
1613    """
1614
1615    def __init__(self, infile):
1616        LineParser.__init__(self, infile)
1617        self.stack = []
1618        self.entries = {}
1619
1620    def add_entry(self, function):
1621        try:
1622            entry = self.entries[function.id]
1623        except KeyError:
1624            self.entries[function.id] = (function, {})
1625        else:
1626            function_total, callees_total = entry
1627            function_total.samples += function.samples
1628
1629    def add_callee(self, function, callee):
1630        func, callees = self.entries[function.id]
1631        try:
1632            entry = callees[callee.id]
1633        except KeyError:
1634            callees[callee.id] = callee
1635        else:
1636            entry.samples += callee.samples
1637
1638    def parse(self):
1639        self.readline()
1640        self.readline()
1641        self.readline()
1642        self.readline()
1643
1644        match = re.compile(r'(?P<prefix>[|+ ]*)(?P<samples>\d+), (?P<symbol>[^,]+), (?P<image>.*)')
1645
1646        while self.lookahead():
1647            line = self.consume()
1648            mo = match.match(line)
1649            if not mo:
1650                raise ParseError('failed to parse', line)
1651
1652            fields = mo.groupdict()
1653            prefix = len(fields.get('prefix', 0)) / 2 - 1
1654
1655            symbol = str(fields.get('symbol', 0))
1656            image = str(fields.get('image', 0))
1657
1658            entry = Struct()
1659            entry.id = ':'.join([symbol, image])
1660            entry.samples = int(fields.get('samples', 0))
1661
1662            entry.name = symbol
1663            entry.image = image
1664
1665            # adjust the callstack
1666            if prefix < len(self.stack):
1667                del self.stack[prefix:]
1668
1669            if prefix == len(self.stack):
1670                self.stack.append(entry)
1671
1672            # if the callstack has had an entry, it's this functions caller
1673            if prefix > 0:
1674                self.add_callee(self.stack[prefix - 1], entry)
1675
1676            self.add_entry(entry)
1677
1678        profile = Profile()
1679        profile[SAMPLES] = 0
1680        for _function, _callees in self.entries.itervalues():
1681            function = Function(_function.id, _function.name)
1682            function[SAMPLES] = _function.samples
1683            profile.add_function(function)
1684            profile[SAMPLES] += _function.samples
1685
1686            if _function.image:
1687                function.module = os.path.basename(_function.image)
1688
1689            for _callee in _callees.itervalues():
1690                call = Call(_callee.id)
1691                call[SAMPLES] = _callee.samples
1692                function.add_call(call)
1693
1694        # compute derived data
1695        profile.validate()
1696        profile.find_cycles()
1697        profile.ratio(TIME_RATIO, SAMPLES)
1698        profile.call_ratios(SAMPLES)
1699        profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1700
1701        return profile
1702
1703
1704class SleepyParser(Parser):
1705    """Parser for GNU gprof output.
1706
1707    See also:
1708    - http://www.codersnotes.com/sleepy/
1709    - http://sleepygraph.sourceforge.net/
1710    """
1711
1712    def __init__(self, filename):
1713        Parser.__init__(self)
1714
1715        from zipfile import ZipFile
1716
1717        self.database = ZipFile(filename)
1718
1719        self.symbols = {}
1720        self.calls = {}
1721
1722        self.profile = Profile()
1723
1724    _symbol_re = re.compile(
1725        r'^(?P<id>\w+)' +
1726        r'\s+"(?P<module>[^"]*)"' +
1727        r'\s+"(?P<procname>[^"]*)"' +
1728        r'\s+"(?P<sourcefile>[^"]*)"' +
1729        r'\s+(?P<sourceline>\d+)$'
1730    )
1731
1732    def parse_symbols(self):
1733        lines = self.database.read('symbols.txt').splitlines()
1734        for line in lines:
1735            mo = self._symbol_re.match(line)
1736            if mo:
1737                symbol_id, module, procname, sourcefile, sourceline = mo.groups()
1738
1739                function_id = ':'.join([module, procname])
1740
1741                try:
1742                    function = self.profile.functions[function_id]
1743                except KeyError:
1744                    function = Function(function_id, procname)
1745                    function[SAMPLES] = 0
1746                    self.profile.add_function(function)
1747
1748                self.symbols[symbol_id] = function
1749
1750    def parse_callstacks(self):
1751        lines = self.database.read("callstacks.txt").splitlines()
1752        for line in lines:
1753            fields = line.split()
1754            samples = int(fields[0])
1755            callstack = fields[1:]
1756
1757            callstack = [self.symbols[symbol_id] for symbol_id in callstack]
1758
1759            callee = callstack[0]
1760
1761            callee[SAMPLES] += samples
1762            self.profile[SAMPLES] += samples
1763
1764            for caller in callstack[1:]:
1765                try:
1766                    call = caller.calls[callee.id]
1767                except KeyError:
1768                    call = Call(callee.id)
1769                    call[SAMPLES2] = samples
1770                    caller.add_call(call)
1771                else:
1772                    call[SAMPLES2] += samples
1773
1774                callee = caller
1775
1776    def parse(self):
1777        profile = self.profile
1778        profile[SAMPLES] = 0
1779
1780        self.parse_symbols()
1781        self.parse_callstacks()
1782
1783        # Compute derived events
1784        profile.validate()
1785        profile.find_cycles()
1786        profile.ratio(TIME_RATIO, SAMPLES)
1787        profile.call_ratios(SAMPLES2)
1788        profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1789
1790        return profile
1791
1792
1793class AQtimeTable:
1794
1795    def __init__(self, name, fields):
1796        self.name = name
1797
1798        self.fields = fields
1799        self.field_column = {}
1800        for column in range(len(fields)):
1801            self.field_column[fields[column]] = column
1802        self.rows = []
1803
1804    def __len__(self):
1805        return len(self.rows)
1806
1807    def __iter__(self):
1808        for values, children in self.rows:
1809            fields = {}
1810            for name, value in zip(self.fields, values):
1811                fields[name] = value
1812            children = dict([(child.name, child) for child in children])
1813            yield fields, children
1814        raise StopIteration
1815
1816    def add_row(self, values, children=()):
1817        self.rows.append((values, children))
1818
1819
1820class AQtimeParser(XmlParser):
1821
1822    def __init__(self, stream):
1823        XmlParser.__init__(self, stream)
1824        self.tables = {}
1825
1826    def parse(self):
1827        self.element_start('AQtime_Results')
1828        self.parse_headers()
1829        results = self.parse_results()
1830        self.element_end('AQtime_Results')
1831        return self.build_profile(results)
1832
1833    def parse_headers(self):
1834        self.element_start('HEADERS')
1835        while self.token.type == XML_ELEMENT_START:
1836            self.parse_table_header()
1837        self.element_end('HEADERS')
1838
1839    def parse_table_header(self):
1840        attrs = self.element_start('TABLE_HEADER')
1841        name = attrs['NAME']
1842        id = int(attrs['ID'])
1843        field_types = []
1844        field_names = []
1845        while self.token.type == XML_ELEMENT_START:
1846            field_type, field_name = self.parse_table_field()
1847            field_types.append(field_type)
1848            field_names.append(field_name)
1849        self.element_end('TABLE_HEADER')
1850        self.tables[id] = name, field_types, field_names
1851
1852    def parse_table_field(self):
1853        attrs = self.element_start('TABLE_FIELD')
1854        type = attrs['TYPE']
1855        name = self.character_data()
1856        self.element_end('TABLE_FIELD')
1857        return type, name
1858
1859    def parse_results(self):
1860        self.element_start('RESULTS')
1861        table = self.parse_data()
1862        self.element_end('RESULTS')
1863        return table
1864
1865    def parse_data(self):
1866        rows = []
1867        attrs = self.element_start('DATA')
1868        table_id = int(attrs['TABLE_ID'])
1869        table_name, field_types, field_names = self.tables[table_id]
1870        table = AQtimeTable(table_name, field_names)
1871        while self.token.type == XML_ELEMENT_START:
1872            row, children = self.parse_row(field_types)
1873            table.add_row(row, children)
1874        self.element_end('DATA')
1875        return table
1876
1877    def parse_row(self, field_types):
1878        row = [None]*len(field_types)
1879        children = []
1880        self.element_start('ROW')
1881        while self.token.type == XML_ELEMENT_START:
1882            if self.token.name_or_data == 'FIELD':
1883                field_id, field_value = self.parse_field(field_types)
1884                row[field_id] = field_value
1885            elif self.token.name_or_data == 'CHILDREN':
1886                children = self.parse_children()
1887            else:
1888                raise XmlTokenMismatch("<FIELD ...> or <CHILDREN ...>", self.token)
1889        self.element_end('ROW')
1890        return row, children
1891
1892    def parse_field(self, field_types):
1893        attrs = self.element_start('FIELD')
1894        id = int(attrs['ID'])
1895        type = field_types[id]
1896        value = self.character_data()
1897        if type == 'Integer':
1898            value = int(value)
1899        elif type == 'Float':
1900            value = float(value)
1901        elif type == 'Address':
1902            value = int(value)
1903        elif type == 'String':
1904            pass
1905        else:
1906            assert False
1907        self.element_end('FIELD')
1908        return id, value
1909
1910    def parse_children(self):
1911        children = []
1912        self.element_start('CHILDREN')
1913        while self.token.type == XML_ELEMENT_START:
1914            table = self.parse_data()
1915            assert table.name not in children
1916            children.append(table)
1917        self.element_end('CHILDREN')
1918        return children
1919
1920    def build_profile(self, results):
1921        assert results.name == 'Routines'
1922        profile = Profile()
1923        profile[TIME] = 0.0
1924        for fields, tables in results:
1925            function = self.build_function(fields)
1926            children = tables['Children']
1927            for fields, _ in children:
1928                call = self.build_call(fields)
1929                function.add_call(call)
1930            profile.add_function(function)
1931            profile[TIME] = profile[TIME] + function[TIME]
1932        profile[TOTAL_TIME] = profile[TIME]
1933        profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
1934        return profile
1935
1936    def build_function(self, fields):
1937        function = Function(self.build_id(fields), self.build_name(fields))
1938        function[TIME] = fields['Time']
1939        function[TOTAL_TIME] = fields['Time with Children']
1940        #function[TIME_RATIO] = fields['% Time']/100.0
1941        #function[TOTAL_TIME_RATIO] = fields['% with Children']/100.0
1942        return function
1943
1944    def build_call(self, fields):
1945        call = Call(self.build_id(fields))
1946        call[TIME] = fields['Time']
1947        call[TOTAL_TIME] = fields['Time with Children']
1948        #call[TIME_RATIO] = fields['% Time']/100.0
1949        #call[TOTAL_TIME_RATIO] = fields['% with Children']/100.0
1950        return call
1951
1952    def build_id(self, fields):
1953        return ':'.join([fields['Module Name'], fields['Unit Name'], fields['Routine Name']])
1954
1955    def build_name(self, fields):
1956        # TODO: use more fields
1957        return fields['Routine Name']
1958
1959
1960class PstatsParser:
1961    """Parser python profiling statistics saved with te pstats module."""
1962
1963    def __init__(self, *filename):
1964        import pstats
1965        try:
1966            self.stats = pstats.Stats(*filename)
1967        except ValueError:
1968            import hotshot.stats
1969            self.stats = hotshot.stats.load(filename[0])
1970        self.profile = Profile()
1971        self.function_ids = {}
1972
1973    def get_function_name(self, (filename, line, name)):
1974        module = os.path.splitext(filename)[0]
1975        module = os.path.basename(module)
1976        return "%s:%d:%s" % (module, line, name)
1977
1978    def get_function(self, key):
1979        try:
1980            id = self.function_ids[key]
1981        except KeyError:
1982            id = len(self.function_ids)
1983            name = self.get_function_name(key)
1984            function = Function(id, name)
1985            self.profile.functions[id] = function
1986            self.function_ids[key] = id
1987        else:
1988            function = self.profile.functions[id]
1989        return function
1990
1991    def parse(self):
1992        self.profile[TIME] = 0.0
1993        self.profile[TOTAL_TIME] = self.stats.total_tt
1994        for fn, (cc, nc, tt, ct, callers) in self.stats.stats.items():
1995            callee = self.get_function(fn)
1996            callee.called = nc
1997            callee[TOTAL_TIME] = ct
1998            callee[TIME] = tt
1999            self.profile[TIME] += tt
2000            self.profile[TOTAL_TIME] = max(self.profile[TOTAL_TIME], ct)
2001            for fn, value in callers.items():
2002                caller = self.get_function(fn)
2003                call = Call(callee.id)
2004                if isinstance(value, tuple):
2005                    for i in xrange(0, len(value), 4):
2006                        nc, cc, tt, ct = value[i:i+4]
2007                        if CALLS in call:
2008                            call[CALLS] += cc
2009                        else:
2010                            call[CALLS] = cc
2011
2012                        if TOTAL_TIME in call:
2013                            call[TOTAL_TIME] += ct
2014                        else:
2015                            call[TOTAL_TIME] = ct
2016
2017                else:
2018                    call[CALLS] = value
2019                    call[TOTAL_TIME] = ratio(value, nc)*ct
2020
2021                caller.add_call(call)
2022        # self.stats.print_stats()
2023        # self.stats.print_callees()
2024
2025        # Compute derived events
2026        self.profile.validate()
2027        self.profile.ratio(TIME_RATIO, TIME)
2028        self.profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
2029
2030        return self.profile
2031
2032
2033class Theme:
2034
2035    def __init__(self, 
2036            bgcolor = (0.0, 0.0, 1.0),
2037            mincolor = (0.0, 0.0, 0.0),
2038            maxcolor = (0.0, 0.0, 1.0),
2039            fontname = "Arial",
2040            minfontsize = 10.0,
2041            maxfontsize = 10.0,
2042            minpenwidth = 0.5,
2043            maxpenwidth = 4.0,
2044            gamma = 2.2,
2045            skew = 1.0):
2046        self.bgcolor = bgcolor
2047        self.mincolor = mincolor
2048        self.maxcolor = maxcolor
2049        self.fontname = fontname
2050        self.minfontsize = minfontsize
2051        self.maxfontsize = maxfontsize
2052        self.minpenwidth = minpenwidth
2053        self.maxpenwidth = maxpenwidth
2054        self.gamma = gamma
2055        self.skew = skew
2056
2057    def graph_bgcolor(self):
2058        return self.hsl_to_rgb(*self.bgcolor)
2059
2060    def graph_fontname(self):
2061        return self.fontname
2062
2063    def graph_fontsize(self):
2064        return self.minfontsize
2065
2066    def node_bgcolor(self, weight):
2067        return self.color(weight)
2068
2069    def node_fgcolor(self, weight):
2070        return self.graph_bgcolor()
2071
2072    def node_fontsize(self, weight):
2073        return self.fontsize(weight)
2074
2075    def edge_color(self, weight):
2076        return self.color(weight)
2077
2078    def edge_fontsize(self, weight):
2079        return self.fontsize(weight)
2080
2081    def edge_penwidth(self, weight):
2082        return max(weight*self.maxpenwidth, self.minpenwidth)
2083
2084    def edge_arrowsize(self, weight):
2085        return 0.5 * math.sqrt(self.edge_penwidth(weight))
2086
2087    def fontsize(self, weight):
2088        return max(weight**2 * self.maxfontsize, self.minfontsize)
2089
2090    def color(self, weight):
2091        weight = min(max(weight, 0.0), 1.0)
2092
2093        hmin, smin, lmin = self.mincolor
2094        hmax, smax, lmax = self.maxcolor
2095
2096        if self.skew < 0:
2097            raise ValueError("Skew must be greater than 0")
2098        elif self.skew == 1.0:
2099            h = hmin + weight*(hmax - hmin)
2100            s = smin + weight*(smax - smin)
2101            l = lmin + weight*(lmax - lmin)
2102        else:
2103            base = self.skew
2104            h = hmin + ((hmax-hmin)*(-1.0 + (base ** weight)) / (base - 1.0))
2105            s = smin + ((smax-smin)*(-1.0 + (base ** weight)) / (base - 1.0))
2106            l = lmin + ((lmax-lmin)*(-1.0 + (base ** weight)) / (base - 1.0))
2107
2108        return self.hsl_to_rgb(h, s, l)
2109
2110    def hsl_to_rgb(self, h, s, l):
2111        """Convert a color from HSL color-model to RGB.
2112
2113        See also:
2114        - http://www.w3.org/TR/css3-color/#hsl-color
2115        """
2116
2117        h = h % 1.0
2118        s = min(max(s, 0.0), 1.0)
2119        l = min(max(l, 0.0), 1.0)
2120
2121        if l <= 0.5:
2122            m2 = l*(s + 1.0)
2123        else:
2124            m2 = l + s - l*s
2125        m1 = l*2.0 - m2
2126        r = self._hue_to_rgb(m1, m2, h + 1.0/3.0)
2127        g = self._hue_to_rgb(m1, m2, h)
2128        b = self._hue_to_rgb(m1, m2, h - 1.0/3.0)
2129
2130        # Apply gamma correction
2131        r **= self.gamma
2132        g **= self.gamma
2133        b **= self.gamma
2134
2135        return (r, g, b)
2136
2137    def _hue_to_rgb(self, m1, m2, h):
2138        if h < 0.0:
2139            h += 1.0
2140        elif h > 1.0:
2141            h -= 1.0
2142        if h*6 < 1.0:
2143            return m1 + (m2 - m1)*h*6.0
2144        elif h*2 < 1.0:
2145            return m2
2146        elif h*3 < 2.0:
2147            return m1 + (m2 - m1)*(2.0/3.0 - h)*6.0
2148        else:
2149            return m1
2150
2151
2152TEMPERATURE_COLORMAP = Theme(
2153    mincolor=(2.0/3.0, 0.80, 0.25),  # dark blue
2154    maxcolor=(0.0, 1.0, 0.5),  # satured red
2155    gamma=1.0
2156)
2157
2158PINK_COLORMAP = Theme(
2159    mincolor=(0.0, 1.0, 0.90),  # pink
2160    maxcolor=(0.0, 1.0, 0.5),  # satured red
2161)
2162
2163GRAY_COLORMAP = Theme(
2164    mincolor=(0.0, 0.0, 0.85),  # light gray
2165    maxcolor=(0.0, 0.0, 0.0),  # black
2166)
2167
2168BW_COLORMAP = Theme(
2169    minfontsize=8.0,
2170    maxfontsize=24.0,
2171    mincolor=(0.0, 0.0, 0.0),  # black
2172    maxcolor=(0.0, 0.0, 0.0),  # black
2173    minpenwidth=0.1,
2174    maxpenwidth=8.0,
2175)
2176
2177
2178class DotWriter:
2179    """Writer for the DOT language.
2180
2181    See also:
2182    - "The DOT Language" specification
2183      http://www.graphviz.org/doc/info/lang.html
2184    """
2185
2186    def __init__(self, fp):
2187        self.fp = fp
2188
2189    def graph(self, profile, theme):
2190        self.begin_graph()
2191
2192        fontname = theme.graph_fontname()
2193
2194        self.attr('graph', fontname=fontname, ranksep=0.25, nodesep=0.125)
2195        self.attr('node', fontname=fontname, shape="box", style="filled", fontcolor="white", width=0, height=0)
2196        self.attr('edge', fontname=fontname)
2197
2198        for function in profile.functions.itervalues():
2199            labels = []
2200            if function.process is not None:
2201                labels.append(function.process)
2202            if function.module is not None:
2203                labels.append(function.module)
2204            labels.append(function.name)
2205            for event in TOTAL_TIME_RATIO, TIME_RATIO:
2206                if event in function.events:
2207                    label = event.format(function[event])
2208                    labels.append(label)
2209            if function.called is not None:
2210                labels.append(u"%u\xd7" % (function.called,))
2211
2212            if function.weight is not None:
2213                weight = function.weight
2214            else:
2215                weight = 0.0
2216
2217            label = '\n'.join(labels)
2218            self.node(function.id,
2219                      label=label,
2220                      color=self.color(theme.node_bgcolor(weight)),
2221                      fontcolor=self.color(theme.node_fgcolor(weight)),
2222                      fontsize="%.2f" % theme.node_fontsize(weight),
2223                      )
2224
2225            for call in function.calls.itervalues():
2226                callee = profile.functions[call.callee_id]
2227
2228                labels = []
2229                for event in TOTAL_TIME_RATIO, CALLS:
2230                    if event in call.events:
2231                        label = event.format(call[event])
2232                        labels.append(label)
2233
2234                if call.weight is not None:
2235                    weight = call.weight
2236                elif callee.weight is not None:
2237                    weight = callee.weight
2238                else:
2239                    weight = 0.0
2240
2241                label = '\n'.join(labels)
2242
2243                self.edge(function.id, call.callee_id,
2244                          label=label,
2245                          color=self.color(theme.edge_color(weight)),
2246                          fontcolor=self.color(theme.edge_color(weight)),
2247                          fontsize="%.2f" % theme.edge_fontsize(weight),
2248                          penwidth="%.2f" % theme.edge_penwidth(weight),
2249                          labeldistance="%.2f" % theme.edge_penwidth(weight),
2250                          arrowsize="%.2f" % theme.edge_arrowsize(weight),
2251                          )
2252
2253        self.end_graph()
2254
2255    def begin_graph(self):
2256        self.write('digraph {\n')
2257
2258    def end_graph(self):
2259        self.write('}\n')
2260
2261    def attr(self, what, **attrs):
2262        self.write("\t")
2263        self.write(what)
2264        self.attr_list(attrs)
2265        self.write(";\n")
2266
2267    def node(self, node, **attrs):
2268        self.write("\t")
2269        self.id(node)
2270        self.attr_list(attrs)
2271        self.write(";\n")
2272
2273    def edge(self, src, dst, **attrs):
2274        self.write("\t")
2275        self.id(src)
2276        self.write(" -> ")
2277        self.id(dst)
2278        self.attr_list(attrs)
2279        self.write(";\n")
2280
2281    def attr_list(self, attrs):
2282        if not attrs:
2283            return
2284        self.write(' [')
2285        first = True
2286        for name, value in attrs.items():
2287            if first:
2288                first = False
2289            else:
2290                self.write(", ")
2291            self.id(name)
2292            self.write('=')
2293            self.id(value)
2294        self.write(']')
2295
2296    def id(self, id):
2297        if isinstance(id, (int, float)):
2298            s = str(id)
2299        elif isinstance(id, basestring):
2300            if id.isalnum() and not id.startswith('0x'):
2301                s = id
2302            else:
2303                s = self.escape(id)
2304        else:
2305            raise TypeError
2306        self.write(s)
2307
2308    def color(self, (r, g, b)):
2309
2310        def float2int(f):
2311            if f <= 0.0:
2312                return 0
2313            if f >= 1.0:
2314                return 255
2315            return int(255.0*f + 0.5)
2316
2317        return "#" + "".join(["%02x" % float2int(c) for c in (r, g, b)])
2318
2319    def escape(self, s):
2320        s = s.encode('utf-8')
2321        s = s.replace('\\', r'\\')
2322        s = s.replace('\n', r'\n')
2323        s = s.replace('\t', r'\t')
2324        s = s.replace('"', r'\"')
2325        return '"' + s + '"'
2326
2327    def write(self, s):
2328        self.fp.write(s)
2329
2330
2331class Main:
2332    """Main program."""
2333
2334    themes = {
2335            "color": TEMPERATURE_COLORMAP,
2336            "pink": PINK_COLORMAP,
2337            "gray": GRAY_COLORMAP,
2338            "bw": BW_COLORMAP,
2339    }
2340
2341    def main(self):
2342        """Main program."""
2343
2344        parser = optparse.OptionParser(
2345            usage="\n\t%prog [options] [file] ...",
2346            version="%%prog %s" % __version__)
2347        parser.add_option(
2348            '-o', '--output', metavar='FILE',
2349            type="string", dest="output",
2350            help="output filename [stdout]")
2351        parser.add_option(
2352            '-n', '--node-thres', metavar='PERCENTAGE',
2353            type="float", dest="node_thres", default=0.5,
2354            help="eliminate nodes below this threshold [default: %default]")
2355        parser.add_option(
2356            '-e', '--edge-thres', metavar='PERCENTAGE',
2357            type="float", dest="edge_thres", default=0.1,
2358            help="eliminate edges below this threshold [default: %default]")
2359        parser.add_option(
2360            '-f', '--format',
2361            type="choice", choices=('prof', 'callgrind', 'oprofile', 'sysprof', 'pstats', 'shark', 'sleepy', 'aqtime'),
2362            dest="format", default="prof",
2363            help="profile format: prof, callgrind, oprofile, sysprof, shark, sleepy, aqtime, or pstats [default: %default]")
2364        parser.add_option(
2365            '-c', '--colormap',
2366            type="choice", choices=('color', 'pink', 'gray', 'bw'),
2367            dest="theme", default="color",
2368            help="color map: color, pink, gray, or bw [default: %default]")
2369        parser.add_option(
2370            '-s', '--strip',
2371            action="store_true",
2372            dest="strip", default=False,
2373            help="strip function parameters, template parameters, and const modifiers from demangled C++ function names")
2374        parser.add_option(
2375            '-w', '--wrap',
2376            action="store_true",
2377            dest="wrap", default=False,
2378            help="wrap function names")
2379        # add a new option to control skew of the colorization curve
2380        parser.add_option(
2381            '--skew',
2382            type="float", dest="theme_skew", default=1.0,
2383            help="skew the colorization curve.  Values < 1.0 give more variety to lower percentages.  Value > 1.0 give less variety to lower percentages")
2384        (self.options, self.args) = parser.parse_args(sys.argv[1:])
2385
2386        if len(self.args) > 1 and self.options.format != 'pstats':
2387            parser.error('incorrect number of arguments')
2388
2389        try:
2390            self.theme = self.themes[self.options.theme]
2391        except KeyError:
2392            parser.error('invalid colormap \'%s\'' % self.options.theme)
2393       
2394        # set skew on the theme now that it has been picked.
2395        if self.options.theme_skew:
2396            self.theme.skew = self.options.theme_skew
2397
2398        if self.options.format == 'prof':
2399            if not self.args:
2400                fp = sys.stdin
2401            else:
2402                fp = open(self.args[0], 'rt')
2403            parser = GprofParser(fp)
2404        elif self.options.format == 'callgrind':
2405            if not self.args:
2406                fp = sys.stdin
2407            else:
2408                fp = open(self.args[0], 'rt')
2409            parser = CallgrindParser(fp)
2410        elif self.options.format == 'oprofile':
2411            if not self.args:
2412                fp = sys.stdin
2413            else:
2414                fp = open(self.args[0], 'rt')
2415            parser = OprofileParser(fp)
2416        elif self.options.format == 'sysprof':
2417            if not self.args:
2418                fp = sys.stdin
2419            else:
2420                fp = open(self.args[0], 'rt')
2421            parser = SysprofParser(fp)
2422        elif self.options.format == 'pstats':
2423            if not self.args:
2424                parser.error('at least a file must be specified for pstats input')
2425            parser = PstatsParser(*self.args)
2426        elif self.options.format == 'shark':
2427            if not self.args:
2428                fp = sys.stdin
2429            else:
2430                fp = open(self.args[0], 'rt')
2431            parser = SharkParser(fp)
2432        elif self.options.format == 'sleepy':
2433            if len(self.args) != 1:
2434                parser.error('exactly one file must be specified for sleepy input')
2435            parser = SleepyParser(self.args[0])
2436        elif self.options.format == 'aqtime':
2437            if not self.args:
2438                fp = sys.stdin
2439            else:
2440                fp = open(self.args[0], 'rt')
2441            parser = AQtimeParser(fp)
2442        else:
2443            parser.error('invalid format \'%s\'' % self.options.format)
2444
2445        self.profile = parser.parse()
2446
2447        if self.options.output is None:
2448            self.output = sys.stdout
2449        else:
2450            self.output = open(self.options.output, 'wt')
2451
2452        self.write_graph()
2453
2454    _parenthesis_re = re.compile(r'\([^()]*\)')
2455    _angles_re = re.compile(r'<[^<>]*>')
2456    _const_re = re.compile(r'\s+const$')
2457
2458    def strip_function_name(self, name):
2459        """Remove extraneous information from C++ demangled function names."""
2460
2461        # Strip function parameters from name by recursively removing paired parenthesis
2462        while True:
2463            name, n = self._parenthesis_re.subn('', name)
2464            if not n:
2465                break
2466
2467        # Strip const qualifier
2468        name = self._const_re.sub('', name)
2469
2470        # Strip template parameters from name by recursively removing paired angles
2471        while True:
2472            name, n = self._angles_re.subn('', name)
2473            if not n:
2474                break
2475
2476        return name
2477
2478    def wrap_function_name(self, name):
2479        """Split the function name on multiple lines."""
2480
2481        if len(name) > 32:
2482            ratio = 2.0/3.0
2483            height = max(int(len(name)/(1.0 - ratio) + 0.5), 1)
2484            width = max(len(name)/height, 32)
2485            # TODO: break lines in symbols
2486            name = textwrap.fill(name, width, break_long_words=False)
2487
2488        # Take away spaces
2489        name = name.replace(", ", ",")
2490        name = name.replace("> >", ">>")
2491        name = name.replace("> >", ">>")  # catch consecutive
2492
2493        return name
2494
2495    def compress_function_name(self, name):
2496        """Compress function name according to the user preferences."""
2497
2498        if self.options.strip:
2499            name = self.strip_function_name(name)
2500
2501        if self.options.wrap:
2502            name = self.wrap_function_name(name)
2503
2504        # TODO: merge functions with same resulting name
2505
2506        return name
2507
2508    def write_graph(self):
2509        dot = DotWriter(self.output)
2510        profile = self.profile
2511        profile.prune(self.options.node_thres/100.0, self.options.edge_thres/100.0)
2512
2513        for function in profile.functions.itervalues():
2514            function.name = self.compress_function_name(function.name)
2515
2516        dot.graph(profile, self.theme)
2517
2518
2519if __name__ == '__main__':
2520    Main().main()
Note: See TracBrowser for help on using the repository browser.