src/profiler/gprof2dot.py

   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
  26 import sys
  27 import math
  28 import os.path
  29 import re
  30 import textwrap
  31 import optparse
  32 import xml.parsers.expat
  33
  34
  35 try:
  36     # Debugging helper module
  37     import debug
  38 except ImportError:
  39     pass
  40
  41
  42 def percentage(p):
  43     return "%.02f%%" % (p*100.0,)
  44
  45 def add(a, b):
  46     return a + b
  47
  48 def equal(a, b):
  49     if a == b:
  50         return a
  51     else:
  52         return None
  53
  54 def fail(a, b):
  55     assert False
  56
  57
  58 tol = 2 ** -23
  59
  60 def ratio(numerator, denominator):
  61     try:
  62         ratio = float(numerator)/float(denominator)
  63     except ZeroDivisionError:
  64         # 0/0 is undefined, but 1.0 yields more useful results
  65         return 1.0
  66     if ratio < 0.0:
  67         if ratio < -tol:
  68             sys.stderr.write('warning: negative ratio (%s/%s)\n' % (numerator, denominator))
  69         return 0.0
  70     if ratio > 1.0:
  71         if ratio > 1.0 + tol:
  72             sys.stderr.write('warning: ratio greater than one (%s/%s)\n' % (numerator, denominator))
  73         return 1.0
  74     return ratio
  75
  76
  77 class UndefinedEvent(Exception):
  78     """Raised when attempting to get an event which is undefined."""
  79
  80     def __init__(self, event):
  81         Exception.__init__(self)
  82         self.event = event
  83
  84     def __str__(self):
  85         return 'unspecified event %s' % self.event.name
  86
  87
  88 class Event(object):
  89     """Describe a kind of event, and its basic operations."""
  90
  91     def __init__(self, name, null, aggregator, formatter = str):
  92         self.name = name
  93         self._null = null
  94         self._aggregator = aggregator
  95         self._formatter = formatter
  96
  97     def __eq__(self, other):
  98         return self is other
  99
 100     def __hash__(self):
 101         return id(self)
 102
 103     def null(self):
 104         return self._null
 105
 106     def aggregate(self, val1, val2):
 107         """Aggregate two event values."""
 108         assert val1 is not None
 109         assert val2 is not None
 110         return self._aggregator(val1, val2)
 111
 112     def format(self, val):
 113         """Format an event value."""
 114         assert val is not None
 115         return self._formatter(val)
 116
 117
 118 MODULE = Event("Module", None, equal)
 119 PROCESS = Event("Process", None, equal)
 120
 121 CALLS = Event("Calls", 0, add)
 122 SAMPLES = Event("Samples", 0, add)
 123 SAMPLES2 = Event("Samples", 0, add)
 124
 125 TIME = Event("Time", 0.0, add, lambda x: '(' + str(x) + ')')
 126 TIME_RATIO = Event("Time ratio", 0.0, add, lambda x: '(' + percentage(x) + ')')
 127 TOTAL_TIME = Event("Total time", 0.0, fail)
 128 TOTAL_TIME_RATIO = Event("Total time ratio", 0.0, fail, percentage)
 129
 130 CALL_RATIO = Event("Call ratio", 0.0, add, percentage)
 131
 132 PRUNE_RATIO = Event("Prune ratio", 0.0, add, percentage)
 133
 134
 135 class Object(object):
 136     """Base class for all objects in profile which can store events."""
 137
 138     def __init__(self, events=None):
 139         if events is None:
 140             self.events = {}
 141         else:
 142             self.events = events
 143
 144     def __hash__(self):
 145         return id(self)
 146
 147     def __eq__(self, other):
 148         return self is other
 149
 150     def __contains__(self, event):
 151         return event in self.events
 152
 153     def __getitem__(self, event):
 154         try:
 155             return self.events[event]
 156         except KeyError:
 157             raise UndefinedEvent(event)
 158
 159     def __setitem__(self, event, value):
 160         if value is None:
 161             if event in self.events:
 162                 del self.events[event]
 163         else:
 164             self.events[event] = value
 165
 166
 167 class Call(Object):
 168     """A call between functions.
 169
 170     There should be at most one call object for every pair of functions.
 171     """
 172
 173     def __init__(self, callee_id):
 174         Object.__init__(self)
 175         self.callee_id = callee_id
 176
 177
 178 class Function(Object):
 179     """A function."""
 180
 181     def __init__(self, id, name):
 182         Object.__init__(self)
 183         self.id = id
 184         self.name = name
 185         self.calls = {}
 186         self.cycle = None
 187
 188     def add_call(self, call):
 189         if call.callee_id in self.calls:
 190             sys.stderr.write('warning: overwriting call from function %s to %s\n' % (str(self.id), str(call.callee_id)))
 191         self.calls[call.callee_id] = call
 192
 193     # TODO: write utility functions
 194
 195     def __repr__(self):
 196         return self.name
 197
 198
 199 class Cycle(Object):
 200     """A cycle made from recursive function calls."""
 201
 202     def __init__(self):
 203         Object.__init__(self)
 204         # XXX: Do cycles need an id?
 205         self.functions = set()
 206
 207     def add_function(self, function):
 208         assert function not in self.functions
 209         self.functions.add(function)
 210         # XXX: Aggregate events?
 211         if function.cycle is not None:
 212             for other in function.cycle.functions:
 213                 if function not in self.functions:
 214                     self.add_function(other)
 215         function.cycle = self
 216
 217
 218 class Profile(Object):
 219     """The whole profile."""
 220
 221     def __init__(self):
 222         Object.__init__(self)
 223         self.functions = {}
 224         self.cycles = []
 225
 226     def add_function(self, function):
 227         if function.id in self.functions:
 228             sys.stderr.write('warning: overwriting function %s (id %s)\n' % (function.name, str(function.id)))
 229         self.functions[function.id] = function
 230
 231     def add_cycle(self, cycle):
 232         self.cycles.append(cycle)
 233
 234     def validate(self):
 235         """Validate the edges."""
 236
 237         for function in self.functions.itervalues():
 238             for callee_id in function.calls.keys():
 239                 assert function.calls[callee_id].callee_id == callee_id
 240                 if callee_id not in self.functions:
 241                     sys.stderr.write('warning: call to undefined function %s from function %s\n' % (str(callee_id), function.name))
 242                     del function.calls[callee_id]
 243
 244     def find_cycles(self):
 245         """Find cycles using Tarjan's strongly connected components algorithm."""
 246
 247         # Apply the Tarjan's algorithm successively until all functions are visited
 248         visited = set()
 249         for function in self.functions.itervalues():
 250             if function not in visited:
 251                 self._tarjan(function, 0, [], {}, {}, visited)
 252         cycles = []
 253         for function in self.functions.itervalues():
 254             if function.cycle is not None and function.cycle not in cycles:
 255                 cycles.append(function.cycle)
 256         self.cycles = cycles
 257         if 0:
 258             for cycle in cycles:
 259                 sys.stderr.write("Cycle:\n")
 260                 for member in cycle.functions:
 261                     sys.stderr.write("\t%s\n" % member.name)
 262
 263     def _tarjan(self, function, order, stack, orders, lowlinks, visited):
 264         """Tarjan's strongly connected components algorithm.
 265
 266         See also:
 267         - http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
 268         """
 269
 270         visited.add(function)
 271         orders[function] = order
 272         lowlinks[function] = order
 273         order += 1
 274         pos = len(stack)
 275         stack.append(function)
 276         for call in function.calls.itervalues():
 277             callee = self.functions[call.callee_id]
 278             # TODO: use a set to optimize lookup
 279             if callee not in orders:
 280                 order = self._tarjan(callee, order, stack, orders, lowlinks, visited)
 281                 lowlinks[function] = min(lowlinks[function], lowlinks[callee])
 282             elif callee in stack:
 283                 lowlinks[function] = min(lowlinks[function], orders[callee])
 284         if lowlinks[function] == orders[function]:
 285             # Strongly connected component found
 286             members = stack[pos:]
 287             del stack[pos:]
 288             if len(members) > 1:
 289                 cycle = Cycle()
 290                 for member in members:
 291                     cycle.add_function(member)
 292         return order
 293
 294     def call_ratios(self, event):
 295         # Aggregate for incoming calls
 296         cycle_totals = {}
 297         for cycle in self.cycles:
 298             cycle_totals[cycle] = 0.0
 299         function_totals = {}
 300         for function in self.functions.itervalues():
 301             function_totals[function] = 0.0
 302         for function in self.functions.itervalues():
 303             for call in function.calls.itervalues():
 304                 if call.callee_id != function.id:
 305                     callee = self.functions[call.callee_id]
 306                     function_totals[callee] += call[event]
 307                     if callee.cycle is not None and callee.cycle is not function.cycle:
 308                         cycle_totals[callee.cycle] += call[event]
 309
 310         # Compute the ratios
 311         for function in self.functions.itervalues():
 312             for call in function.calls.itervalues():
 313                 assert CALL_RATIO not in call
 314                 if call.callee_id != function.id:
 315                     callee = self.functions[call.callee_id]
 316                     if callee.cycle is not None and callee.cycle is not function.cycle:
 317                         total = cycle_totals[callee.cycle]
 318                     else:
 319                         total = function_totals[callee]
 320                     call[CALL_RATIO] = ratio(call[event], total)
 321
 322     def integrate(self, outevent, inevent):
 323         """Propagate function time ratio allong the function calls.
 324
 325         Must be called after finding the cycles.
 326
 327         See also:
 328         - http://citeseer.ist.psu.edu/graham82gprof.html
 329         """
 330
 331         # Sanity checking
 332         assert outevent not in self
 333         for function in self.functions.itervalues():
 334             assert outevent not in function
 335             assert inevent in function
 336             for call in function.calls.itervalues():
 337                 assert outevent not in call
 338                 if call.callee_id != function.id:
 339                     assert CALL_RATIO in call
 340
 341         # Aggregate the input for each cycle
 342         for cycle in self.cycles:
 343             total = inevent.null()
 344             for function in self.functions.itervalues():
 345                 total = inevent.aggregate(total, function[inevent])
 346             self[inevent] = total
 347
 348         # Integrate along the edges
 349         total = inevent.null()
 350         for function in self.functions.itervalues():
 351             total = inevent.aggregate(total, function[inevent])
 352             self._integrate_function(function, outevent, inevent)
 353         self[outevent] = total
 354
 355     def _integrate_function(self, function, outevent, inevent):
 356         if function.cycle is not None:
 357             return self._integrate_cycle(function.cycle, outevent, inevent)
 358         else:
 359             if outevent not in function:
 360                 total = function[inevent]
 361                 for call in function.calls.itervalues():
 362                     if call.callee_id != function.id:
 363                         total += self._integrate_call(call, outevent, inevent)
 364                 function[outevent] = total
 365             return function[outevent]
 366
 367     def _integrate_call(self, call, outevent, inevent):
 368         assert outevent not in call
 369         assert CALL_RATIO in call
 370         callee = self.functions[call.callee_id]
 371         subtotal = call[CALL_RATIO]*self._integrate_function(callee, outevent, inevent)
 372         call[outevent] = subtotal
 373         return subtotal
 374
 375     def _integrate_cycle(self, cycle, outevent, inevent):
 376         if outevent not in cycle:
 377
 378             total = inevent.null()
 379             for member in cycle.functions:
 380                 subtotal = member[inevent]
 381                 for call in member.calls.itervalues():
 382                     callee = self.functions[call.callee_id]
 383                     if callee.cycle is not cycle:
 384                         subtotal += self._integrate_call(call, outevent, inevent)
 385                 total += subtotal
 386             cycle[outevent] = total
 387
 388             callees = {}
 389             for function in self.functions.itervalues():
 390                 if function.cycle is not cycle:
 391                     for call in function.calls.itervalues():
 392                         callee = self.functions[call.callee_id]
 393                         if callee.cycle is cycle:
 394                             try:
 395                                 callees[callee] += call[CALL_RATIO]
 396                             except KeyError:
 397                                 callees[callee] = call[CALL_RATIO]
 398
 399             for callee, call_ratio in callees.iteritems():
 400                 ranks = {}
 401                 call_ratios = {}
 402                 partials = {}
 403                 self._rank_cycle_function(cycle, callee, 0, ranks)
 404                 self._call_ratios_cycle(cycle, callee, ranks, call_ratios, set())
 405                 partial = self._integrate_cycle_function(cycle, callee, call_ratio, partials, ranks, call_ratios, outevent, inevent)
 406                 assert partial == max(partials.values())
 407                 assert not total or abs(1.0 - partial/(call_ratio*total)) <= 0.001
 408
 409         return cycle[outevent]
 410
 411     def _rank_cycle_function(self, cycle, function, rank, ranks):
 412         if function not in ranks or ranks[function] > rank:
 413             ranks[function] = rank
 414             for call in function.calls.itervalues():
 415                 if call.callee_id != function.id:
 416                     callee = self.functions[call.callee_id]
 417                     if callee.cycle is cycle:
 418                         self._rank_cycle_function(cycle, callee, rank + 1, ranks)
 419
 420     def _call_ratios_cycle(self, cycle, function, ranks, call_ratios, visited):
 421         if function not in visited:
 422             visited.add(function)
 423             for call in function.calls.itervalues():
 424                 if call.callee_id != function.id:
 425                     callee = self.functions[call.callee_id]
 426                     if callee.cycle is cycle:
 427                         if ranks[callee] > ranks[function]:
 428                             call_ratios[callee] = call_ratios.get(callee, 0.0) + call[CALL_RATIO]
 429                             self._call_ratios_cycle(cycle, callee, ranks, call_ratios, visited)
 430
 431     def _integrate_cycle_function(self, cycle, function, partial_ratio, partials, ranks, call_ratios, outevent, inevent):
 432         if function not in partials:
 433             partial = partial_ratio*function[inevent]
 434             for call in function.calls.itervalues():
 435                 if call.callee_id != function.id:
 436                     callee = self.functions[call.callee_id]
 437                     if callee.cycle is not cycle:
 438                         assert outevent in call
 439                         partial += partial_ratio*call[outevent]
 440                     else:
 441                         if ranks[callee] > ranks[function]:
 442                             callee_partial = self._integrate_cycle_function(cycle, callee, partial_ratio, partials, ranks, call_ratios, outevent, inevent)
 443                             call_ratio = ratio(call[CALL_RATIO], call_ratios[callee])
 444                             call_partial = call_ratio*callee_partial
 445                             try:
 446                                 call[outevent] += call_partial
 447                             except UndefinedEvent:
 448                                 call[outevent] = call_partial
 449                             partial += call_partial
 450             partials[function] = partial
 451             try:
 452                 function[outevent] += partial
 453             except UndefinedEvent:
 454                 function[outevent] = partial
 455         return partials[function]
 456
 457     def aggregate(self, event):
 458         """Aggregate an event for the whole profile."""
 459
 460         total = event.null()
 461         for function in self.functions.itervalues():
 462             try:
 463                 total = event.aggregate(total, function[event])
 464             except UndefinedEvent:
 465                 return
 466         self[event] = total
 467
 468     def ratio(self, outevent, inevent):
 469         assert outevent not in self
 470         assert inevent in self
 471         for function in self.functions.itervalues():
 472             assert outevent not in function
 473             assert inevent in function
 474             function[outevent] = ratio(function[inevent], self[inevent])
 475             for call in function.calls.itervalues():
 476                 assert outevent not in call
 477                 if inevent in call:
 478                     call[outevent] = ratio(call[inevent], self[inevent])
 479         self[outevent] = 1.0
 480
 481     def prune(self, node_thres, edge_thres):
 482         """Prune the profile"""
 483
 484         # compute the prune ratios
 485         for function in self.functions.itervalues():
 486             try:
 487                 function[PRUNE_RATIO] = function[TOTAL_TIME_RATIO]
 488             except UndefinedEvent:
 489                 pass
 490
 491             for call in function.calls.itervalues():
 492                 callee = self.functions[call.callee_id]
 493
 494                 if TOTAL_TIME_RATIO in call:
 495                     # handle exact cases first
 496                     call[PRUNE_RATIO] = call[TOTAL_TIME_RATIO]
 497                 else:
 498                     try:
 499                         # make a safe estimate
 500                         call[PRUNE_RATIO] = min(function[TOTAL_TIME_RATIO], callee[TOTAL_TIME_RATIO])
 501                     except UndefinedEvent:
 502                         pass
 503
 504         # prune the nodes
 505         for function_id in self.functions.keys():
 506             function = self.functions[function_id]
 507             try:
 508                 if function[PRUNE_RATIO] < node_thres:
 509                     del self.functions[function_id]
 510             except UndefinedEvent:
 511                 pass
 512
 513         # prune the egdes
 514         for function in self.functions.itervalues():
 515             for callee_id in function.calls.keys():
 516                 call = function.calls[callee_id]
 517                 try:
 518                     if callee_id not in self.functions or call[PRUNE_RATIO] < edge_thres:
 519                         del function.calls[callee_id]
 520                 except UndefinedEvent:
 521                     pass
 522
 523     def dump(self):
 524         for function in self.functions.itervalues():
 525             sys.stderr.write('Function %s:\n' % (function.name,))
 526             self._dump_events(function.events)
 527             for call in function.calls.itervalues():
 528                 callee = self.functions[call.callee_id]
 529                 sys.stderr.write('  Call %s:\n' % (callee.name,))
 530                 self._dump_events(call.events)
 531
 532     def _dump_events(self, events):
 533         for event, value in events.iteritems():
 534             sys.stderr.write('    %s: %s\n' % (event.name, event.format(value)))
 535
 536
 537 class Struct:
 538     """Masquerade a dictionary with a structure-like behavior."""
 539
 540     def __init__(self, attrs = None):
 541         if attrs is None:
 542             attrs = {}
 543         self.__dict__['_attrs'] = attrs
 544
 545     def __getattr__(self, name):
 546         try:
 547             return self._attrs[name]
 548         except KeyError:
 549             raise AttributeError(name)
 550
 551     def __setattr__(self, name, value):
 552         self._attrs[name] = value
 553
 554     def __str__(self):
 555         return str(self._attrs)
 556
 557     def __repr__(self):
 558         return repr(self._attrs)
 559
 560
 561 class ParseError(Exception):
 562     """Raised when parsing to signal mismatches."""
 563
 564     def __init__(self, msg, line):
 565         self.msg = msg
 566         # TODO: store more source line information
 567         self.line = line
 568
 569     def __str__(self):
 570         return '%s: %r' % (self.msg, self.line)
 571
 572
 573 class Parser:
 574     """Parser interface."""
 575
 576     def __init__(self):
 577         pass
 578
 579     def parse(self):
 580         raise NotImplementedError
 581
 582
 583 class LineParser(Parser):
 584     """Base class for parsers that read line-based formats."""
 585
 586     def __init__(self, file):
 587         Parser.__init__(self)
 588         self._file = file
 589         self.__line = None
 590         self.__eof = False
 591
 592     def readline(self):
 593         line = self._file.readline()
 594         if not line:
 595             self.__line = ''
 596             self.__eof = True
 597         self.__line = line.rstrip('\r\n')
 598
 599     def lookahead(self):
 600         assert self.__line is not None
 601         return self.__line
 602
 603     def consume(self):
 604         assert self.__line is not None
 605         line = self.__line
 606         self.readline()
 607         return line
 608
 609     def eof(self):
 610         assert self.__line is not None
 611         return self.__eof
 612
 613
 614 XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF = range(4)
 615
 616
 617 class XmlToken:
 618
 619     def __init__(self, type, name_or_data, attrs = None, line = None, column = None):
 620         assert type in (XML_ELEMENT_START, XML_ELEMENT_END, XML_CHARACTER_DATA, XML_EOF)
 621         self.type = type
 622         self.name_or_data = name_or_data
 623         self.attrs = attrs
 624         self.line = line
 625         self.column = column
 626
 627     def __str__(self):
 628         if self.type == XML_ELEMENT_START:
 629             return '<' + self.name_or_data + ' ...>'
 630         if self.type == XML_ELEMENT_END:
 631             return '</' + self.name_or_data + '>'
 632         if self.type == XML_CHARACTER_DATA:
 633             return self.name_or_data
 634         if self.type == XML_EOF:
 635             return 'end of file'
 636         assert 0
 637
 638
 639 class XmlTokenizer:
 640     """Expat based XML tokenizer."""
 641
 642     def __init__(self, fp, skip_ws = True):
 643         self.fp = fp
 644         self.tokens = []
 645         self.index = 0
 646         self.final = False
 647         self.skip_ws = skip_ws
 648
 649         self.character_pos = 0, 0
 650         self.character_data = ''
 651
 652         self.parser = xml.parsers.expat.ParserCreate()
 653         self.parser.StartElementHandler  = self.handle_element_start
 654         self.parser.EndElementHandler    = self.handle_element_end
 655         self.parser.CharacterDataHandler = self.handle_character_data
 656
 657     def handle_element_start(self, name, attributes):
 658         self.finish_character_data()
 659         line, column = self.pos()
 660         token = XmlToken(XML_ELEMENT_START, name, attributes, line, column)
 661         self.tokens.append(token)
 662
 663     def handle_element_end(self, name):
 664         self.finish_character_data()
 665         line, column = self.pos()
 666         token = XmlToken(XML_ELEMENT_END, name, None, line, column)
 667         self.tokens.append(token)
 668
 669     def handle_character_data(self, data):
 670         if not self.character_data:
 671             self.character_pos = self.pos()
 672         self.character_data += data
 673
 674     def finish_character_data(self):
 675         if self.character_data:
 676             if not self.skip_ws or not self.character_data.isspace():
 677                 line, column = self.character_pos
 678                 token = XmlToken(XML_CHARACTER_DATA, self.character_data, None, line, column)
 679                 self.tokens.append(token)
 680             self.character_data = ''
 681
 682     def next(self):
 683         size = 16*1024
 684         while self.index >= len(self.tokens) and not self.final:
 685             self.tokens = []
 686             self.index = 0
 687             data = self.fp.read(size)
 688             self.final = len(data) < size
 689             try:
 690                 self.parser.Parse(data, self.final)
 691             except xml.parsers.expat.ExpatError, e:
 692                 #if e.code == xml.parsers.expat.errors.XML_ERROR_NO_ELEMENTS:
 693                 if e.code == 3:
 694                     pass
 695                 else:
 696                     raise e
 697         if self.index >= len(self.tokens):
 698             line, column = self.pos()
 699             token = XmlToken(XML_EOF, None, None, line, column)
 700         else:
 701             token = self.tokens[self.index]
 702             self.index += 1
 703         return token
 704
 705     def pos(self):
 706         return self.parser.CurrentLineNumber, self.parser.CurrentColumnNumber
 707
 708
 709 class XmlTokenMismatch(Exception):
 710
 711     def __init__(self, expected, found):
 712         self.expected = expected
 713         self.found = found
 714
 715     def __str__(self):
 716         return '%u:%u: %s expected, %s found' % (self.found.line, self.found.column, str(self.expected), str(self.found))
 717
 718
 719 class XmlParser(Parser):
 720     """Base XML document parser."""
 721
 722     def __init__(self, fp):
 723         Parser.__init__(self)
 724         self.tokenizer = XmlTokenizer(fp)
 725         self.consume()
 726
 727     def consume(self):
 728         self.token = self.tokenizer.next()
 729
 730     def match_element_start(self, name):
 731         return self.token.type == XML_ELEMENT_START and self.token.name_or_data == name
 732
 733     def match_element_end(self, name):
 734         return self.token.type == XML_ELEMENT_END and self.token.name_or_data == name
 735
 736     def element_start(self, name):
 737         while self.token.type == XML_CHARACTER_DATA:
 738             self.consume()
 739         if self.token.type != XML_ELEMENT_START:
 740             raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token)
 741         if self.token.name_or_data != name:
 742             raise XmlTokenMismatch(XmlToken(XML_ELEMENT_START, name), self.token)
 743         attrs = self.token.attrs
 744         self.consume()
 745         return attrs
 746
 747     def element_end(self, name):
 748         while self.token.type == XML_CHARACTER_DATA:
 749             self.consume()
 750         if self.token.type != XML_ELEMENT_END:
 751             raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token)
 752         if self.token.name_or_data != name:
 753             raise XmlTokenMismatch(XmlToken(XML_ELEMENT_END, name), self.token)
 754         self.consume()
 755
 756     def character_data(self, strip = True):
 757         data = ''
 758         while self.token.type == XML_CHARACTER_DATA:
 759             data += self.token.name_or_data
 760             self.consume()
 761         if strip:
 762             data = data.strip()
 763         return data
 764
 765
 766 class GprofParser(Parser):
 767     """Parser for GNU gprof output.
 768
 769     See also:
 770     - Chapter "Interpreting gprof's Output" from the GNU gprof manual
 771       http://sourceware.org/binutils/docs-2.18/gprof/Call-Graph.html#Call-Graph
 772     - File "cg_print.c" from the GNU gprof source code
 773       http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/gprof/cg_print.c?rev=1.12&cvsroot=src
 774     """
 775
 776     def __init__(self, fp):
 777         Parser.__init__(self)
 778         self.fp = fp
 779         self.functions = {}
 780         self.cycles = {}
 781
 782     def readline(self):
 783         line = self.fp.readline()
 784         if not line:
 785             sys.stderr.write('error: unexpected end of file\n')
 786             sys.exit(1)
 787         line = line.rstrip('\r\n')
 788         return line
 789
 790     _int_re = re.compile(r'^\d+$')
 791     _float_re = re.compile(r'^\d+\.\d+$')
 792
 793     def translate(self, mo):
 794         """Extract a structure from a match object, while translating the types in the process."""
 795         attrs = {}
 796         groupdict = mo.groupdict()
 797         for name, value in groupdict.iteritems():
 798             if value is None:
 799                 value = None
 800             elif self._int_re.match(value):
 801                 value = int(value)
 802             elif self._float_re.match(value):
 803                 value = float(value)
 804             attrs[name] = (value)
 805         return Struct(attrs)
 806
 807     _cg_header_re = re.compile(
 808         # original gprof header
 809         r'^\s+called/total\s+parents\s*$|' +
 810         r'^index\s+%time\s+self\s+descendents\s+called\+self\s+name\s+index\s*$|' +
 811         r'^\s+called/total\s+children\s*$|' +
 812         # GNU gprof header
 813         r'^index\s+%\s+time\s+self\s+children\s+called\s+name\s*$'
 814     )
 815
 816     _cg_ignore_re = re.compile(
 817         # spontaneous
 818         r'^\s+<spontaneous>\s*$|'
 819         # internal calls (such as "mcount")
 820         r'^.*\((\d+)\)$'
 821     )
 822
 823     _cg_primary_re = re.compile(
 824         r'^\[(?P<index>\d+)\]?' +
 825         r'\s+(?P<percentage_time>\d+\.\d+)' +
 826         r'\s+(?P<self>\d+\.\d+)' +
 827         r'\s+(?P<descendants>\d+\.\d+)' +
 828         r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' +
 829         r'\s+(?P<name>\S.*?)' +
 830         r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
 831         r'\s\[(\d+)\]$'
 832     )
 833
 834     _cg_parent_re = re.compile(
 835         r'^\s+(?P<self>\d+\.\d+)?' +
 836         r'\s+(?P<descendants>\d+\.\d+)?' +
 837         r'\s+(?P<called>\d+)(?:/(?P<called_total>\d+))?' +
 838         r'\s+(?P<name>\S.*?)' +
 839         r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
 840         r'\s\[(?P<index>\d+)\]$'
 841     )
 842
 843     _cg_child_re = _cg_parent_re
 844
 845     _cg_cycle_header_re = re.compile(
 846         r'^\[(?P<index>\d+)\]?' +
 847         r'\s+(?P<percentage_time>\d+\.\d+)' +
 848         r'\s+(?P<self>\d+\.\d+)' +
 849         r'\s+(?P<descendants>\d+\.\d+)' +
 850         r'\s+(?:(?P<called>\d+)(?:\+(?P<called_self>\d+))?)?' +
 851         r'\s+<cycle\s(?P<cycle>\d+)\sas\sa\swhole>' +
 852         r'\s\[(\d+)\]$'
 853     )
 854
 855     _cg_cycle_member_re = re.compile(
 856         r'^\s+(?P<self>\d+\.\d+)?' +
 857         r'\s+(?P<descendants>\d+\.\d+)?' +
 858         r'\s+(?P<called>\d+)(?:\+(?P<called_self>\d+))?' +
 859         r'\s+(?P<name>\S.*?)' +
 860         r'(?:\s+<cycle\s(?P<cycle>\d+)>)?' +
 861         r'\s\[(?P<index>\d+)\]$'
 862     )
 863
 864     _cg_sep_re = re.compile(r'^--+$')
 865
 866     def parse_function_entry(self, lines):
 867         parents = []
 868         children = []
 869
 870         while True:
 871             if not lines:
 872                 sys.stderr.write('warning: unexpected end of entry\n')
 873             line = lines.pop(0)
 874             if line.startswith('['):
 875                 break
 876
 877             # read function parent line
 878             mo = self._cg_parent_re.match(line)
 879             if not mo:
 880                 if self._cg_ignore_re.match(line):
 881                     continue
 882                 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
 883             else:
 884                 parent = self.translate(mo)
 885                 parents.append(parent)
 886
 887         # read primary line
 888         mo = self._cg_primary_re.match(line)
 889         if not mo:
 890             sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
 891             return
 892         else:
 893             function = self.translate(mo)
 894
 895         while lines:
 896             line = lines.pop(0)
 897
 898             # read function subroutine line
 899             mo = self._cg_child_re.match(line)
 900             if not mo:
 901                 if self._cg_ignore_re.match(line):
 902                     continue
 903                 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
 904             else:
 905                 child = self.translate(mo)
 906                 children.append(child)
 907
 908         function.parents = parents
 909         function.children = children
 910
 911         self.functions[function.index] = function
 912
 913     def parse_cycle_entry(self, lines):
 914
 915         # read cycle header line
 916         line = lines[0]
 917         mo = self._cg_cycle_header_re.match(line)
 918         if not mo:
 919             sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
 920             return
 921         cycle = self.translate(mo)
 922
 923         # read cycle member lines
 924         cycle.functions = []
 925         for line in lines[1:]:
 926             mo = self._cg_cycle_member_re.match(line)
 927             if not mo:
 928                 sys.stderr.write('warning: unrecognized call graph entry: %r\n' % line)
 929                 continue
 930             call = self.translate(mo)
 931             cycle.functions.append(call)
 932
 933         self.cycles[cycle.cycle] = cycle
 934
 935     def parse_cg_entry(self, lines):
 936         if lines[0].startswith("["):
 937             self.parse_cycle_entry(lines)
 938         else:
 939             self.parse_function_entry(lines)
 940
 941     def parse_cg(self):
 942         """Parse the call graph."""
 943
 944         # skip call graph header
 945         while not self._cg_header_re.match(self.readline()):
 946             pass
 947         line = self.readline()
 948         while self._cg_header_re.match(line):
 949             line = self.readline()
 950
 951         # process call graph entries
 952         entry_lines = []
 953         while line != '\014': # form feed
 954             if line and not line.isspace():
 955                 if self._cg_sep_re.match(line):
 956                     self.parse_cg_entry(entry_lines)
 957                     entry_lines = []
 958                 else:
 959                     entry_lines.append(line)
 960             line = self.readline()
 961
 962     def parse(self):
 963         self.parse_cg()
 964         self.fp.close()
 965
 966         profile = Profile()
 967         profile[TIME] = 0.0
 968
 969         cycles = {}
 970         for index in self.cycles.iterkeys():
 971             cycles[index] = Cycle()
 972
 973         for entry in self.functions.itervalues():
 974             # populate the function
 975             function = Function(entry.index, entry.name)
 976             function[TIME] = entry.self
 977             if entry.called is not None:
 978                 function[CALLS] = entry.called
 979             if entry.called_self is not None:
 980                 call = Call(entry.index)
 981                 call[CALLS] = entry.called_self
 982                 function[CALLS] += entry.called_self
 983
 984             # populate the function calls
 985             for child in entry.children:
 986                 call = Call(child.index)
 987
 988                 assert child.called is not None
 989                 call[CALLS] = child.called
 990
 991                 if child.index not in self.functions:
 992                     # NOTE: functions that were never called but were discovered by gprof's
 993                     # static call graph analysis dont have a call graph entry so we need
 994                     # to add them here
 995                     missing = Function(child.index, child.name)
 996                     function[TIME] = 0.0
 997                     function[CALLS] = 0
 998                     profile.add_function(missing)
 999
1000                 function.add_call(call)
1001
1002             profile.add_function(function)
1003
1004             if entry.cycle is not None:
1005                 cycles[entry.cycle].add_function(function)
1006
1007             profile[TIME] = profile[TIME] + function[TIME]
1008
1009         for cycle in cycles.itervalues():
1010             profile.add_cycle(cycle)
1011
1012         # Compute derived events
1013         profile.validate()
1014         profile.ratio(TIME_RATIO, TIME)
1015         profile.call_ratios(CALLS)
1016         profile.integrate(TOTAL_TIME, TIME)
1017         profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
1018
1019         return profile
1020
1021
1022 class OprofileParser(LineParser):
1023     """Parser for oprofile callgraph output.
1024
1025     See also:
1026     - http://oprofile.sourceforge.net/doc/opreport.html#opreport-callgraph
1027     """
1028
1029     _fields_re = {
1030         'samples': r'(?P<samples>\d+)',
1031         '%': r'(?P<percentage>\S+)',
1032         'linenr info': r'(?P<source>\(no location information\)|\S+:\d+)',
1033         'image name': r'(?P<image>\S+(?:\s\(tgid:[^)]*\))?)',
1034         'app name': r'(?P<application>\S+)',
1035         'symbol name': r'(?P<symbol>\(no symbols\)|.+?)',
1036     }
1037
1038     def __init__(self, infile):
1039         LineParser.__init__(self, infile)
1040         self.entries = {}
1041         self.entry_re = None
1042
1043     def add_entry(self, callers, function, callees):
1044         try:
1045             entry = self.entries[function.id]
1046         except KeyError:
1047             self.entries[function.id] = (callers, function, callees)
1048         else:
1049             callers_total, function_total, callees_total = entry
1050             self.update_subentries_dict(callers_total, callers)
1051             function_total.samples += function.samples
1052             self.update_subentries_dict(callees_total, callees)
1053
1054     def update_subentries_dict(self, totals, partials):
1055         for partial in partials.itervalues():
1056             try:
1057                 total = totals[partial.id]
1058             except KeyError:
1059                 totals[partial.id] = partial
1060             else:
1061                 total.samples += partial.samples
1062
1063     def parse(self):
1064         # read lookahead
1065         self.readline()
1066
1067         self.parse_header()
1068         while self.lookahead():
1069             self.parse_entry()
1070
1071         profile = Profile()
1072
1073         reverse_call_samples = {}
1074
1075         # populate the profile
1076         profile[SAMPLES] = 0
1077         for _callers, _function, _callees in self.entries.itervalues():
1078             function = Function(_function.id, _function.name)
1079             function[SAMPLES] = _function.samples
1080             profile.add_function(function)
1081             profile[SAMPLES] += _function.samples
1082
1083             if _function.application:
1084                 function[PROCESS] = os.path.basename(_function.application)
1085             if _function.image:
1086                 function[MODULE] = os.path.basename(_function.image)
1087
1088             total_callee_samples = 0
1089             for _callee in _callees.itervalues():
1090                 total_callee_samples += _callee.samples
1091
1092             for _callee in _callees.itervalues():
1093                 if not _callee.self:
1094                     call = Call(_callee.id)
1095                     call[SAMPLES2] = _callee.samples
1096                     function.add_call(call)
1097
1098         # compute derived data
1099         profile.validate()
1100         profile.find_cycles()
1101         profile.ratio(TIME_RATIO, SAMPLES)
1102         profile.call_ratios(SAMPLES2)
1103         profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1104
1105         return profile
1106
1107     def parse_header(self):
1108         while not self.match_header():
1109             self.consume()
1110         line = self.lookahead()
1111         fields = re.split(r'\s\s+', line)
1112         entry_re = r'^\s*' + r'\s+'.join([self._fields_re[field] for field in fields]) + r'(?P<self>\s+\[self\])?$'
1113         self.entry_re = re.compile(entry_re)
1114         self.skip_separator()
1115
1116     def parse_entry(self):
1117         callers = self.parse_subentries()
1118         if self.match_primary():
1119             function = self.parse_subentry()
1120             if function is not None:
1121                 callees = self.parse_subentries()
1122                 self.add_entry(callers, function, callees)
1123         self.skip_separator()
1124
1125     def parse_subentries(self):
1126         subentries = {}
1127         while self.match_secondary():
1128             subentry = self.parse_subentry()
1129             subentries[subentry.id] = subentry
1130         return subentries
1131
1132     def parse_subentry(self):
1133         entry = Struct()
1134         line = self.consume()
1135         mo = self.entry_re.match(line)
1136         if not mo:
1137             raise ParseError('failed to parse', line)
1138         fields = mo.groupdict()
1139         entry.samples = int(fields.get('samples', 0))
1140         entry.percentage = float(fields.get('percentage', 0.0))
1141         if 'source' in fields and fields['source'] != '(no location information)':
1142             source = fields['source']
1143             filename, lineno = source.split(':')
1144             entry.filename = filename
1145             entry.lineno = int(lineno)
1146         else:
1147             source = ''
1148             entry.filename = None
1149             entry.lineno = None
1150         entry.image = fields.get('image', '')
1151         entry.application = fields.get('application', '')
1152         if 'symbol' in fields and fields['symbol'] != '(no symbols)':
1153             entry.symbol = fields['symbol']
1154         else:
1155             entry.symbol = ''
1156         if entry.symbol.startswith('"') and entry.symbol.endswith('"'):
1157             entry.symbol = entry.symbol[1:-1]
1158         entry.id = ':'.join((entry.application, entry.image, source, entry.symbol))
1159         entry.self = fields.get('self', None) != None
1160         if entry.self:
1161             entry.id += ':self'
1162         if entry.symbol:
1163             entry.name = entry.symbol
1164         else:
1165             entry.name = entry.image
1166         return entry
1167
1168     def skip_separator(self):
1169         while not self.match_separator():
1170             self.consume()
1171         self.consume()
1172
1173     def match_header(self):
1174         line = self.lookahead()
1175         return line.startswith('samples')
1176
1177     def match_separator(self):
1178         line = self.lookahead()
1179         return line == '-'*len(line)
1180
1181     def match_primary(self):
1182         line = self.lookahead()
1183         return not line[:1].isspace()
1184
1185     def match_secondary(self):
1186         line = self.lookahead()
1187         return line[:1].isspace()
1188
1189
1190 class SharkParser(LineParser):
1191     """Parser for MacOSX Shark output.
1192
1193     Author: tom@dbservice.com
1194     """
1195
1196     def __init__(self, infile):
1197         LineParser.__init__(self, infile)
1198         self.stack = []
1199         self.entries = {}
1200
1201     def add_entry(self, function):
1202         try:
1203             entry = self.entries[function.id]
1204         except KeyError:
1205             self.entries[function.id] = (function, { })
1206         else:
1207             function_total, callees_total = entry
1208             function_total.samples += function.samples
1209
1210     def add_callee(self, function, callee):
1211         func, callees = self.entries[function.id]
1212         try:
1213             entry = callees[callee.id]
1214         except KeyError:
1215             callees[callee.id] = callee
1216         else:
1217             entry.samples += callee.samples
1218
1219     def parse(self):
1220         self.readline()
1221         self.readline()
1222         self.readline()
1223         self.readline()
1224
1225         match = re.compile(r'(?P<prefix>[|+ ]*)(?P<samples>\d+), (?P<symbol>[^,]+), (?P<image>.*)')
1226
1227         while self.lookahead():
1228             line = self.consume()
1229             mo = match.match(line)
1230             if not mo:
1231                 raise ParseError('failed to parse', line)
1232
1233             fields = mo.groupdict()
1234             prefix = len(fields.get('prefix', 0)) / 2 - 1
1235
1236             symbol = str(fields.get('symbol', 0))
1237             image = str(fields.get('image', 0))
1238
1239             entry = Struct()
1240             entry.id = ':'.join([symbol, image])
1241             entry.samples = int(fields.get('samples', 0))
1242
1243             entry.name = symbol
1244             entry.image = image
1245
1246             # adjust the callstack
1247             if prefix < len(self.stack):
1248                 del self.stack[prefix:]
1249
1250             if prefix == len(self.stack):
1251                 self.stack.append(entry)
1252
1253             # if the callstack has had an entry, it's this functions caller
1254             if prefix > 0:
1255                 self.add_callee(self.stack[prefix - 1], entry)
1256
1257             self.add_entry(entry)
1258
1259         profile = Profile()
1260         profile[SAMPLES] = 0
1261         for _function, _callees in self.entries.itervalues():
1262             function = Function(_function.id, _function.name)
1263             function[SAMPLES] = _function.samples
1264             profile.add_function(function)
1265             profile[SAMPLES] += _function.samples
1266
1267             if _function.image:
1268                 function[MODULE] = os.path.basename(_function.image)
1269
1270             for _callee in _callees.itervalues():
1271                 call = Call(_callee.id)
1272                 call[SAMPLES] = _callee.samples
1273                 function.add_call(call)
1274
1275         # compute derived data
1276         profile.validate()
1277         profile.find_cycles()
1278         profile.ratio(TIME_RATIO, SAMPLES)
1279         profile.call_ratios(SAMPLES)
1280         profile.integrate(TOTAL_TIME_RATIO, TIME_RATIO)
1281
1282         return profile
1283
1284
1285 class AQtimeTable:
1286
1287     def __init__(self, name, fields):
1288         self.name = name
1289
1290         self.fields = fields
1291         self.field_column = {}
1292         for column in range(len(fields)):
1293             self.field_column[fields[column]] = column
1294         self.rows = []
1295
1296     def __len__(self):
1297         return len(self.rows)
1298
1299     def __iter__(self):
1300         for values, children in self.rows:
1301             fields = {}
1302             for name, value in zip(self.fields, values):
1303                 fields[name] = value
1304             children = dict([(child.name, child) for child in children])
1305             yield fields, children
1306         raise StopIteration
1307
1308     def add_row(self, values, children=()):
1309         self.rows.append((values, children))
1310
1311
1312 class AQtimeParser(XmlParser):
1313
1314     def __init__(self, stream):
1315         XmlParser.__init__(self, stream)
1316         self.tables = {}
1317
1318     def parse(self):
1319         self.element_start('AQtime_Results')
1320         self.parse_headers()
1321         results = self.parse_results()
1322         self.element_end('AQtime_Results')
1323         return self.build_profile(results)
1324
1325     def parse_headers(self):
1326         self.element_start('HEADERS')
1327         while self.token.type == XML_ELEMENT_START:
1328             self.parse_table_header()
1329         self.element_end('HEADERS')
1330
1331     def parse_table_header(self):
1332         attrs = self.element_start('TABLE_HEADER')
1333         name = attrs['NAME']
1334         id = int(attrs['ID'])
1335         field_types = []
1336         field_names = []
1337         while self.token.type == XML_ELEMENT_START:
1338             field_type, field_name = self.parse_table_field()
1339             field_types.append(field_type)
1340             field_names.append(field_name)
1341         self.element_end('TABLE_HEADER')
1342         self.tables[id] = name, field_types, field_names
1343
1344     def parse_table_field(self):
1345         attrs = self.element_start('TABLE_FIELD')
1346         type = attrs['TYPE']
1347         name = self.character_data()
1348         self.element_end('TABLE_FIELD')
1349         return type, name
1350
1351     def parse_results(self):
1352         self.element_start('RESULTS')
1353         table = self.parse_data()
1354         self.element_end('RESULTS')
1355         return table
1356
1357     def parse_data(self):
1358         rows = []
1359         attrs = self.element_start('DATA')
1360         table_id = int(attrs['TABLE_ID'])
1361         table_name, field_types, field_names = self.tables[table_id]
1362         table = AQtimeTable(table_name, field_names)
1363         while self.token.type == XML_ELEMENT_START:
1364             row, children = self.parse_row(field_types)
1365             table.add_row(row, children)
1366         self.element_end('DATA')
1367         return table
1368
1369     def parse_row(self, field_types):
1370         row = [None]*len(field_types)
1371         children = []
1372         self.element_start('ROW')
1373         while self.token.type == XML_ELEMENT_START:
1374             if self.token.name_or_data == 'FIELD':
1375                 field_id, field_value = self.parse_field(field_types)
1376                 row[field_id] = field_value
1377             elif self.token.name_or_data == 'CHILDREN':
1378                 children = self.parse_children()
1379             else:
1380                 raise XmlTokenMismatch("<FIELD ...> or <CHILDREN ...>", self.token)
1381         self.element_end('ROW')
1382         return row, children
1383
1384     def parse_field(self, field_types):
1385         attrs = self.element_start('FIELD')
1386         id = int(attrs['ID'])
1387         type = field_types[id]
1388         value = self.character_data()
1389         if type == 'Integer':
1390             value = int(value)
1391         elif type == 'Float':
1392             value = float(value)
1393         elif type == 'Address':
1394             value = int(value)
1395         elif type == 'String':
1396             pass
1397         else:
1398             assert False
1399         self.element_end('FIELD')
1400         return id, value
1401
1402     def parse_children(self):
1403         children = []
1404         self.element_start('CHILDREN')
1405         while self.token.type == XML_ELEMENT_START:
1406             table = self.parse_data()
1407             assert table.name not in children
1408             children.append(table)
1409         self.element_end('CHILDREN')
1410         return children
1411
1412     def build_profile(self, results):
1413         assert results.name == 'Routines'
1414         profile = Profile()
1415         profile[TIME] = 0.0
1416         for fields, tables in results:
1417             function = self.build_function(fields)
1418             children = tables['Children']
1419             for fields, _ in children:
1420                 call = self.build_call(fields)
1421                 function.add_call(call)
1422             profile.add_function(function)
1423             profile[TIME] = profile[TIME] + function[TIME]
1424         profile[TOTAL_TIME] = profile[TIME]
1425         profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
1426         return profile
1427
1428     def build_function(self, fields):
1429         function = Function(self.build_id(fields), self.build_name(fields))
1430         function[TIME] = fields['Time']
1431         function[TOTAL_TIME] = fields['Time with Children']
1432         #function[TIME_RATIO] = fields['% Time']/100.0
1433         #function[TOTAL_TIME_RATIO] = fields['% with Children']/100.0
1434         return function
1435
1436     def build_call(self, fields):
1437         call = Call(self.build_id(fields))
1438         call[TIME] = fields['Time']
1439         call[TOTAL_TIME] = fields['Time with Children']
1440         #call[TIME_RATIO] = fields['% Time']/100.0
1441         #call[TOTAL_TIME_RATIO] = fields['% with Children']/100.0
1442         return call
1443
1444     def build_id(self, fields):
1445         return ':'.join([fields['Module Name'], fields['Unit Name'], fields['Routine Name']])
1446
1447     def build_name(self, fields):
1448         # TODO: use more fields
1449         return fields['Routine Name']
1450
1451
1452 class PstatsParser:
1453     """Parser python profiling statistics saved with te pstats module."""
1454
1455     def __init__(self, *filename):
1456         import pstats
1457         try:
1458             self.stats = pstats.Stats(*filename)
1459         except ValueError:
1460             import hotshot.stats
1461             self.stats = hotshot.stats.load(filename[0])
1462         self.profile = Profile()
1463         self.function_ids = {}
1464
1465     def get_function_name(self, (filename, line, name)):
1466         module = os.path.splitext(filename)[0]
1467         module = os.path.basename(module)
1468         return "%s:%d:%s" % (module, line, name)
1469
1470     def get_function(self, key):
1471         try:
1472             id = self.function_ids[key]
1473         except KeyError:
1474             id = len(self.function_ids)
1475             name = self.get_function_name(key)
1476             function = Function(id, name)
1477             self.profile.functions[id] = function
1478             self.function_ids[key] = id
1479         else:
1480             function = self.profile.functions[id]
1481         return function
1482
1483     def parse(self):
1484         self.profile[TIME] = 0.0
1485         self.profile[TOTAL_TIME] = self.stats.total_tt
1486         for fn, (cc, nc, tt, ct, callers) in self.stats.stats.iteritems():
1487             callee = self.get_function(fn)
1488             callee[CALLS] = nc
1489             callee[TOTAL_TIME] = ct
1490             callee[TIME] = tt
1491             self.profile[TIME] += tt
1492             self.profile[TOTAL_TIME] = max(self.profile[TOTAL_TIME], ct)
1493             for fn, value in callers.iteritems():
1494                 caller = self.get_function(fn)
1495                 call = Call(callee.id)
1496                 if isinstance(value, tuple):
1497                     for i in xrange(0, len(value), 4):
1498                         nc, cc, tt, ct = value[i:i+4]
1499                         if CALLS in call:
1500                             call[CALLS] += cc
1501                         else:
1502                             call[CALLS] = cc
1503
1504                         if TOTAL_TIME in call:
1505                             call[TOTAL_TIME] += ct
1506                         else:
1507                             call[TOTAL_TIME] = ct
1508
1509                 else:
1510                     call[CALLS] = value
1511                     call[TOTAL_TIME] = ratio(value, nc)*ct
1512
1513                 caller.add_call(call)
1514         #self.stats.print_stats()
1515         #self.stats.print_callees()
1516
1517         # Compute derived events
1518         self.profile.validate()
1519         self.profile.ratio(TIME_RATIO, TIME)
1520         self.profile.ratio(TOTAL_TIME_RATIO, TOTAL_TIME)
1521
1522         return self.profile
1523
1524
1525 class Theme:
1526
1527     def __init__(self,
1528             bgcolor = (0.0, 0.0, 1.0),
1529             mincolor = (0.0, 0.0, 0.0),
1530             maxcolor = (0.0, 0.0, 1.0),
1531             fontname = "Arial",
1532             minfontsize = 10.0,
1533             maxfontsize = 10.0,
1534             minpenwidth = 0.5,
1535             maxpenwidth = 4.0,
1536             gamma = 2.2):
1537         self.bgcolor = bgcolor
1538         self.mincolor = mincolor
1539         self.maxcolor = maxcolor
1540         self.fontname = fontname
1541         self.minfontsize = minfontsize
1542         self.maxfontsize = maxfontsize
1543         self.minpenwidth = minpenwidth
1544         self.maxpenwidth = maxpenwidth
1545         self.gamma = gamma
1546
1547     def graph_bgcolor(self):
1548         return self.hsl_to_rgb(*self.bgcolor)
1549
1550     def graph_fontname(self):
1551         return self.fontname
1552
1553     def graph_fontsize(self):
1554         return self.minfontsize
1555
1556     def node_bgcolor(self, weight):
1557         return self.color(weight)
1558
1559     def node_fgcolor(self, weight):
1560         return self.graph_bgcolor()
1561
1562     def node_fontsize(self, weight):
1563         return self.fontsize(weight)
1564
1565     def edge_color(self, weight):
1566         return self.color(weight)
1567
1568     def edge_fontsize(self, weight):
1569         return self.fontsize(weight)
1570
1571     def edge_penwidth(self, weight):
1572         return max(weight*self.maxpenwidth, self.minpenwidth)
1573
1574     def edge_arrowsize(self, weight):
1575         return 0.5 * math.sqrt(self.edge_penwidth(weight))
1576
1577     def fontsize(self, weight):
1578         return max(weight**2 * self.maxfontsize, self.minfontsize)
1579
1580     def color(self, weight):
1581         weight = min(max(weight, 0.0), 1.0)
1582
1583         hmin, smin, lmin = self.mincolor
1584         hmax, smax, lmax = self.maxcolor
1585
1586         h = hmin + weight*(hmax - hmin)
1587         s = smin + weight*(smax - smin)
1588         l = lmin + weight*(lmax - lmin)
1589
1590         return self.hsl_to_rgb(h, s, l)
1591
1592     def hsl_to_rgb(self, h, s, l):
1593         """Convert a color from HSL color-model to RGB.
1594
1595         See also:
1596         - http://www.w3.org/TR/css3-color/#hsl-color
1597         """
1598
1599         h = h % 1.0
1600         s = min(max(s, 0.0), 1.0)
1601         l = min(max(l, 0.0), 1.0)
1602
1603         if l <= 0.5:
1604             m2 = l*(s + 1.0)
1605         else:
1606             m2 = l + s - l*s
1607         m1 = l*2.0 - m2
1608         r = self._hue_to_rgb(m1, m2, h + 1.0/3.0)
1609         g = self._hue_to_rgb(m1, m2, h)
1610         b = self._hue_to_rgb(m1, m2, h - 1.0/3.0)
1611
1612         # Apply gamma correction
1613         r **= self.gamma
1614         g **= self.gamma
1615         b **= self.gamma
1616
1617         return (r, g, b)
1618
1619     def _hue_to_rgb(self, m1, m2, h):
1620         if h < 0.0:
1621             h += 1.0
1622         elif h > 1.0:
1623             h -= 1.0
1624         if h*6 < 1.0:
1625             return m1 + (m2 - m1)*h*6.0
1626         elif h*2 < 1.0:
1627             return m2
1628         elif h*3 < 2.0:
1629             return m1 + (m2 - m1)*(2.0/3.0 - h)*6.0
1630         else:
1631             return m1
1632
1633
1634 TEMPERATURE_COLORMAP = Theme(
1635     mincolor = (2.0/3.0, 0.80, 0.25), # dark blue
1636     maxcolor = (0.0, 1.0, 0.5), # satured red
1637     gamma = 1.0
1638 )
1639
1640 PINK_COLORMAP = Theme(
1641     mincolor = (0.0, 1.0, 0.90), # pink
1642     maxcolor = (0.0, 1.0, 0.5), # satured red
1643 )
1644
1645 GRAY_COLORMAP = Theme(
1646     mincolor = (0.0, 0.0, 0.85), # light gray
1647     maxcolor = (0.0, 0.0, 0.0), # black
1648 )
1649
1650 BW_COLORMAP = Theme(
1651     minfontsize = 8.0,
1652     maxfontsize = 24.0,
1653     mincolor = (0.0, 0.0, 0.0), # black
1654     maxcolor = (0.0, 0.0, 0.0), # black
1655     minpenwidth = 0.1,
1656     maxpenwidth = 8.0,
1657 )
1658
1659
1660 class DotWriter:
1661     """Writer for the DOT language.
1662
1663     See also:
1664     - "The DOT Language" specification
1665       http://www.graphviz.org/doc/info/lang.html
1666     """
1667
1668     def __init__(self, fp):
1669         self.fp = fp
1670
1671     def graph(self, profile, theme):
1672         self.begin_graph()
1673
1674         fontname = theme.graph_fontname()
1675
1676         self.attr('graph', fontname=fontname, ranksep=0.25, nodesep=0.125)
1677         self.attr('node', fontname=fontname, shape="box", style="filled,rounded", fontcolor="white", width=0, height=0)
1678         self.attr('edge', fontname=fontname)
1679
1680         for function in profile.functions.itervalues():
1681             labels = []
1682             for event in PROCESS, MODULE:
1683                 if event in function.events:
1684                     label = event.format(function[event])
1685                     labels.append(label)
1686             labels.append(function.name)
1687             for event in TOTAL_TIME_RATIO, TIME_RATIO, CALLS:
1688                 if event in function.events:
1689                     label = event.format(function[event])
1690                     labels.append(label)
1691
1692             try:
1693                 weight = function[PRUNE_RATIO]
1694             except UndefinedEvent:
1695                 weight = 0.0
1696
1697             label = '\n'.join(labels)
1698             self.node(function.id,
1699                 label = label,
1700                 color = self.color(theme.node_bgcolor(weight)),
1701                 fontcolor = self.color(theme.node_fgcolor(weight)),
1702                 fontsize = "%.2f" % theme.node_fontsize(weight),
1703             )
1704
1705             for call in function.calls.itervalues():
1706                 callee = profile.functions[call.callee_id]
1707
1708                 labels = []
1709                 for event in TOTAL_TIME_RATIO, CALLS:
1710                     if event in call.events:
1711                         label = event.format(call[event])
1712                         labels.append(label)
1713
1714                 try:
1715                     weight = call[PRUNE_RATIO]
1716                 except UndefinedEvent:
1717                     try:
1718                         weight = callee[PRUNE_RATIO]
1719                     except UndefinedEvent:
1720                         weight = 0.0
1721
1722                 label = '\n'.join(labels)
1723
1724                 self.edge(function.id, call.callee_id,
1725                     label = label,
1726                     color = self.color(theme.edge_color(weight)),
1727                     fontcolor = self.color(theme.edge_color(weight)),
1728                     fontsize = "%.2f" % theme.edge_fontsize(weight),
1729                     penwidth = "%.2f" % theme.edge_penwidth(weight),
1730                     labeldistance = "%.2f" % theme.edge_penwidth(weight),
1731                     arrowsize = "%.2f" % theme.edge_arrowsize(weight),
1732                 )
1733
1734         self.end_graph()
1735
1736     def begin_graph(self):
1737         self.write('digraph {\n')
1738
1739     def end_graph(self):
1740         self.write('}\n')
1741
1742     def attr(self, what, **attrs):
1743         self.write("\t")
1744         self.write(what)
1745         self.attr_list(attrs)
1746         self.write(";\n")
1747
1748     def node(self, node, **attrs):
1749         self.write("\t")
1750         self.id(node)
1751         self.attr_list(attrs)
1752         self.write(";\n")
1753
1754     def edge(self, src, dst, **attrs):
1755         self.write("\t")
1756         self.id(src)
1757         self.write(" -> ")
1758         self.id(dst)
1759         self.attr_list(attrs)
1760         self.write(";\n")
1761
1762     def attr_list(self, attrs):
1763         if not attrs:
1764             return
1765         self.write(' [')
1766         first = True
1767         for name, value in attrs.iteritems():
1768             if first:
1769                 first = False
1770             else:
1771                 self.write(", ")
1772             self.id(name)
1773             self.write('=')
1774             self.id(value)
1775         self.write(']')
1776
1777     def id(self, id):
1778         if isinstance(id, (int, float)):
1779             s = str(id)
1780         elif isinstance(id, basestring):
1781             if id.isalnum():
1782                 s = id
1783             else:
1784                 s = self.escape(id)
1785         else:
1786             raise TypeError
1787         self.write(s)
1788
1789     def color(self, (r, g, b)):
1790
1791         def float2int(f):
1792             if f <= 0.0:
1793                 return 0
1794             if f >= 1.0:
1795                 return 255
1796             return int(255.0*f + 0.5)
1797
1798         return "#" + "".join(["%02x" % float2int(c) for c in (r, g, b)])
1799
1800     def escape(self, s):
1801         s = s.encode('utf-8')
1802         s = s.replace('\\', r'\\')
1803         s = s.replace('\n', r'\n')
1804         s = s.replace('\t', r'\t')
1805         s = s.replace('"', r'\"')
1806         return '"' + s + '"'
1807
1808     def write(self, s):
1809         self.fp.write(s)
1810
1811
1812 class Main:
1813     """Main program."""
1814
1815     themes = {
1816             "color": TEMPERATURE_COLORMAP,
1817             "pink": PINK_COLORMAP,
1818             "gray": GRAY_COLORMAP,
1819             "bw": BW_COLORMAP,
1820     }
1821
1822     def main(self):
1823         """Main program."""
1824
1825         parser = optparse.OptionParser(
1826             usage="\n\t%prog [options] [file] ...",
1827             version="%%prog %s" % __version__)
1828         parser.add_option(
1829             '-o', '--output', metavar='FILE',
1830             type="string", dest="output",
1831             help="output filename [stdout]")
1832         parser.add_option(
1833             '-n', '--node-thres', metavar='PERCENTAGE',
1834             type="float", dest="node_thres", default=0.5,
1835             help="eliminate nodes below this threshold [default: %default]")
1836         parser.add_option(
1837             '-e', '--edge-thres', metavar='PERCENTAGE',
1838             type="float", dest="edge_thres", default=0.1,
1839             help="eliminate edges below this threshold [default: %default]")
1840         parser.add_option(
1841             '-f', '--format',
1842             type="choice", choices=('prof', 'oprofile', 'pstats', 'shark', 'aqtime'),
1843             dest="format", default="prof",
1844             help="profile format: prof, oprofile, shark, aqtime, or pstats [default: %default]")
1845         parser.add_option(
1846             '-c', '--colormap',
1847             type="choice", choices=('color', 'pink', 'gray', 'bw'),
1848             dest="theme", default="color",
1849             help="color map: color, pink, gray, or bw [default: %default]")
1850         parser.add_option(
1851             '-s', '--strip',
1852             action="store_true",
1853             dest="strip", default=False,
1854             help="strip function parameters, template parameters, and const modifiers from demangled C++ function names")
1855         parser.add_option(
1856             '-w', '--wrap',
1857             action="store_true",
1858             dest="wrap", default=False,
1859             help="wrap function names")
1860         (self.options, self.args) = parser.parse_args(sys.argv[1:])
1861
1862         if len(self.args) > 1 and self.options.format != 'pstats':
1863             parser.error('incorrect number of arguments')
1864
1865         try:
1866             self.theme = self.themes[self.options.theme]
1867         except KeyError:
1868             parser.error('invalid colormap \'%s\'' % self.options.theme)
1869
1870         if self.options.format == 'prof':
1871             if not self.args:
1872                 fp = sys.stdin
1873             else:
1874                 fp = open(self.args[0], 'rt')
1875             parser = GprofParser(fp)
1876         elif self.options.format == 'oprofile':
1877             if not self.args:
1878                 fp = sys.stdin
1879             else:
1880                 fp = open(self.args[0], 'rt')
1881             parser = OprofileParser(fp)
1882         elif self.options.format == 'pstats':
1883             if not self.args:
1884                 parser.error('at least a file must be specified for pstats input')
1885             parser = PstatsParser(*self.args)
1886         elif self.options.format == 'shark':
1887             if not self.args:
1888                 fp = sys.stdin
1889             else:
1890                 fp = open(self.args[0], 'rt')
1891             parser = SharkParser(fp)
1892         elif self.options.format == 'aqtime':
1893             if not self.args:
1894                 fp = sys.stdin
1895             else:
1896                 fp = open(self.args[0], 'rt')
1897             parser = AQtimeParser(fp)
1898         else:
1899             parser.error('invalid format \'%s\'' % self.options.format)
1900
1901         self.profile = parser.parse()
1902
1903         if self.options.output is None:
1904             self.output = sys.stdout
1905         else:
1906             self.output = open(self.options.output, 'wt')
1907
1908         self.write_graph()
1909
1910     _parenthesis_re = re.compile(r'\([^()]*\)')
1911     _angles_re = re.compile(r'<[^<>]*>')
1912     _const_re = re.compile(r'\s+const$')
1913
1914     def strip_function_name(self, name):
1915         """Remove extraneous information from C++ demangled function names."""
1916
1917         # Strip function parameters from name by recursively removing paired parenthesis
1918         while True:
1919             name, n = self._parenthesis_re.subn('', name)
1920             if not n:
1921                 break
1922
1923         # Strip const qualifier
1924         name = self._const_re.sub('', name)
1925
1926         # Strip template parameters from name by recursively removing paired angles
1927         while True:
1928             name, n = self._angles_re.subn('', name)
1929             if not n:
1930                 break
1931
1932         return name
1933
1934     def wrap_function_name(self, name):
1935         """Split the function name on multiple lines."""
1936
1937         if len(name) > 32:
1938             ratio = 2.0/3.0
1939             height = max(int(len(name)/(1.0 - ratio) + 0.5), 1)
1940             width = max(len(name)/height, 32)
1941             # TODO: break lines in symbols
1942             name = textwrap.fill(name, width, break_long_words=False)
1943
1944         # Take away spaces
1945         name = name.replace(", ", ",")
1946         name = name.replace("> >", ">>")
1947         name = name.replace("> >", ">>") # catch consecutive
1948
1949         return name
1950
1951     def compress_function_name(self, name):
1952         """Compress function name according to the user preferences."""
1953
1954         if self.options.strip:
1955             name = self.strip_function_name(name)
1956
1957         if self.options.wrap:
1958             name = self.wrap_function_name(name)
1959
1960         # TODO: merge functions with same resulting name
1961
1962         return name
1963
1964     def write_graph(self):
1965         dot = DotWriter(self.output)
1966         profile = self.profile
1967         profile.prune(self.options.node_thres/100.0, self.options.edge_thres/100.0)
1968
1969         for function in profile.functions.itervalues():
1970             function.name = self.compress_function_name(function.name)
1971
1972         dot.graph(profile, self.theme)
1973
1974
1975 if __name__ == '__main__':
1976     Main().main()