depgraph2dot.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright 2004      Toby Dickenson
   4 # Copyright 2008-2011 W. Trevor King
   5 #
   6 # Permission is hereby granted, free of charge, to any person obtaining
   7 # a copy of this software and associated documentation files (the
   8 # "Software"), to deal in the Software without restriction, including
   9 # without limitation the rights to use, copy, modify, merge, publish,
  10 # distribute, sublicense, and/or sell copies of the Software, and to
  11 # permit persons to whom the Software is furnished to do so, subject
  12 # to the following conditions:
  13 #
  14 # The above copyright notice and this permission notice shall be included
  15 # in all copies or substantial portions of the Software.
  16 #
  17 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  21 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  22 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  23 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24
  25 """Convert `py2depgraph` dependency data to Graphviz dot syntax.
  26 """
  27
  28 import colorsys
  29 from hashlib import md5
  30 import logging
  31 import imp
  32 from os import popen, getuid  # for finding C extension dependencies with system calls
  33 from pwd import getpwuid
  34 import re
  35 import sys
  36
  37
  38 LOG = logging.getLogger('depgraph2py')
  39 LOG.setLevel(logging.DEBUG)
  40 _STREAM_HANDLER = logging.StreamHandler()
  41 _STREAM_HANDLER.setLevel(logging.CRITICAL)
  42 _STREAM_HANDLER.setFormatter(
  43     logging.Formatter('%(levelname)s - %(message)s'))
  44 LOG.addHandler(_STREAM_HANDLER)
  45
  46 USER=getpwuid(getuid())[0] # get effective user name
  47
  48 INVISIBLE_MODS=('__future__','copy','doctest','glob','optparse','os','qt','re',
  49                 'StringIO','string','sys','textwrap','time','types','unittest')
  50 INVISIBLE_PATHS=(r'.*',)
  51 VISIBLE_PATHS=(r'.*%s.*' % USER,r'.*comedi.*')
  52
  53 def _pathmatch(regexp_tuple, path) :
  54     "Check if a regexp in regexp tuple matches the string path"
  55     for regexp in regexp_tuple :
  56         if re.match(regexp, path) != None :
  57             return True
  58     return False
  59
  60 class hooks (object) :
  61     """
  62     Modules show up if visible_mod_test(...) == True.
  63
  64     """
  65     def __init__(self,
  66                  invisible_mods=INVISIBLE_MODS,
  67                  invisible_paths=INVISIBLE_PATHS,
  68                  visible_paths=VISIBLE_PATHS,
  69                  link_outside_visited_nodes=True,
  70                  ignore_builtins=True) :
  71         self._invisible_mods = invisible_mods
  72         self._invisible_paths = invisible_paths
  73         self._visible_paths = visible_paths
  74         self._link_outside_visited_nodes = link_outside_visited_nodes
  75         self._ignore_builtins = ignore_builtins
  76         self._entered_bonus_nodes = {} # a dict of bonus nodes already printed
  77     def continue_test(self) :
  78         return True
  79     def visible_mod_test(self, mod_name, dep_dict, type, path,
  80                          check_external_link=True) :
  81         """
  82         Return true if this module is interesting and should be drawn.
  83         Return false if it should be completely omitted.
  84         """
  85         if self._invisible_name(mod_name) == True :
  86             LOG.debug('invisible module %s' % mod_name)
  87             return False
  88         if self._link_outside_visited_nodes == False \
  89                 and check_external_link == True \
  90                 and mod_name != '__main__' :
  91             if self.follow_edge_test('__main__', imp.PY_SOURCE, './dummy.py',
  92                                      mod_name, type, path) == False:
  93                 return False # don't draw nodes we wouldn't visit
  94         return True
  95     def follow_edge_test(self, module_name, type, path,
  96                          dname, dtype, dpath):
  97         LOG.debug('testing edge from %s %s %s to %s %s %s'
  98                   % (module_name, type, path, dname, dtype, dpath))
  99         if self.visible_mod_test(dname, None, dtype, dpath,
 100                                  check_external_link=False) == False :
 101             LOG.debug('invisible target module')
 102             return False # don't draw edges to invisible modules
 103         elif dname == '__main__':
 104             # references *to* __main__ are never interesting. omitting them means
 105             # that main floats to the top of the page
 106             LOG.debug('target is __main__')
 107             return False
 108         elif self._invisible_path(path) == True and module_name != '__main__' :
 109             # the path for __main__ seems to be it's filename
 110             LOG.debug('invisible module parent path %s' % path)
 111             return False # don't draw edges from invisible path modules
 112         elif self._link_outside_visited_nodes == False \
 113                 and self._invisible_path(dpath) == True :
 114             LOG.debug('invisible module path %s' % dpath)
 115             return False # don't draw edges to invisible path modules
 116         #elif dtype == imp.PKG_DIRECTORY:
 117         #    # don't draw edges to packages.
 118         #    LOG.debug('package')
 119         #    return False
 120         return True
 121     def _invisible_name(self, mod_name) :
 122         if mod_name in self._invisible_mods :
 123             # nearly all modules use all of these... more or less.
 124             # They add nothing to our diagram.
 125             return True
 126         return False
 127     def _invisible_path(self, path) :
 128         """
 129         Paths are visible by default.  Adding a regexp to invisible_paths hides
 130         matching paths, unless the path matches a regexp in visible_paths, in
 131         which case it is again visible.
 132         """
 133         if path == None and self._ignore_builtins :
 134             return True # ignore modules without paths (builtins, etc)
 135         if (_pathmatch(self._invisible_paths, path)
 136                 and not _pathmatch(self._visible_paths, path)):
 137             return True
 138         return False
 139
 140 class dotformat (object) :
 141     def __init__(self, colored=True, hooks_instance=None) :
 142         if hooks_instance != None :
 143             self._hooks = hooks_instance
 144         else :
 145             self._hooks = hooks()
 146         self._colored = colored
 147     def header(self):
 148         return ('digraph G {\n'
 149                 #'  concentrate = true;\n'
 150                 #'  ordering = out;\n'
 151                 '  ranksep=1.0;\n'
 152                 '  node [style=filled,fontname=Helvetica,fontsize=10];\n')
 153     def footer(self):
 154         return '}\n'
 155     def module(self, mod_name, dep_dict, type, path) :
 156         name = self._fix_name(mod_name)
 157         a = []
 158         if mod_name == '__main__' :
 159             # the path for __main__ seems to be it's filename
 160             a.append('label="%s"' % self._label(path))
 161         else :
 162             a.append('label="%s"' % self._label(mod_name))
 163         if self._colored:
 164             a.append('fillcolor="%s"' % self._color(mod_name,type))
 165         else:
 166             a.append('fillcolor=white')
 167         if self._hooks._invisible_path(path):
 168             # for printing `invisible' modules
 169             a.append('peripheries=2')
 170         return self._dot_node(name, a)
 171     def edge(self, mod_name, dep_dict, type, path,
 172              dep_name, dep_type, dep_path) :
 173         name = self._fix_name(mod_name)
 174         target = self._fix_name(dep_name)
 175         a = []
 176         weight = self._weight(mod_name,dep_name)
 177         if weight!=1:
 178             a.append('weight=%d' % weight)
 179         length = self._alien(mod_name)
 180         if length:
 181             a.append('minlen=%d' % length)
 182         return self._dot_edge(name, target, a)
 183
 184     def _fix_name(self, mod_name):
 185         # Convert a module name to a syntactically correct node name
 186         return mod_name.replace('.','_')
 187     def _label(self,s):
 188         # Convert a module name to a formatted node label.
 189         return '\\.\\n'.join(s.split('.'))
 190     def _weight(self, mod_name, target_name):
 191         # Return the weight of the dependency from a to b. Higher weights
 192         # usually have shorter straighter edges. Return 1 if it has normal weight.
 193         # A value of 4 is usually good for ensuring that a related pair of modules
 194         # are drawn next to each other.
 195         #
 196         if target_name.split('.')[-1].startswith('_'):
 197             # A module that starts with an underscore. You need a special reason to
 198             # import these (for example random imports _random), so draw them close
 199             # together
 200             return 4
 201         return 1
 202     def _alien(self, mod_name):
 203         # Return non-zero if references to this module are strange, and should be drawn
 204         # extra-long. the value defines the length, in rank. This is also good for putting some
 205         # vertical space between seperate subsystems.
 206         return 0
 207     def _color(self, mod_name, type):
 208         # Return the node color for this module name.
 209         if type == imp.C_EXTENSION:
 210             # make C extensions bluegreen
 211             # bluegreen is at 180 deg, see http://en.wikipedia.org/wiki/Image:HueScale.svg
 212             r,g,b = colorsys.hsv_to_rgb(180.0/360.0, .2, 1)
 213             return '#%02x%02x%02x' % (r*255,g*255,b*255)
 214         # Calculate a color systematically based on the hash of the module name. Modules in the
 215         # same package have the same color. Unpackaged modules are grey
 216         t = self._normalise_module_name_for_hash_coloring(mod_name,type)
 217         return self._color_from_name(t)
 218     def _normalise_module_name_for_hash_coloring(self,mod_name,type):
 219         if type==imp.PKG_DIRECTORY:
 220             return mod_name
 221         else:
 222             i = mod_name.rfind('.')
 223             if i<0:
 224                 return ''
 225             else:
 226                 return mod_name[:i]
 227     def _color_from_name(self,name):
 228         n = md5(name).digest()
 229         hf = float(ord(n[0])+ord(n[1])*0xff)/0xffff
 230         sf = float(ord(n[2]))/0xff
 231         vf = float(ord(n[3]))/0xff
 232         r,g,b = colorsys.hsv_to_rgb(hf, 0.3+0.6*sf, 0.8+0.2*vf)
 233         return '#%02x%02x%02x' % (r*256,g*256,b*256)
 234
 235     # abstract out most of the dot language for head and edge declarations
 236     def _dot_node(self, name, attrs) :
 237         string = '  %s' % self._fix_name(name)
 238         string += self._attribute_string(attrs)
 239         string += ';\n'
 240         return string
 241     def _dot_edge(self, source, target, attrs) :
 242         string = '  %s -> %s' % (source, target)
 243         string += self._attribute_string(attrs)
 244         string += ';\n'
 245         return string
 246     def _attribute_string(self, attributes):
 247         string = ''
 248         if attributes:
 249             string += ' [%s]' % (','.join(attributes))
 250         return string
 251
 252 class dotformat_Cext (dotformat) :
 253     # support for listing C-language extension code.
 254     _visible_paths = VISIBLE_PATHS
 255     def module(self, mod_name, dep_dict, type, path) :
 256         name = self._fix_name(mod_name)
 257         a = []
 258         if mod_name == '__main__' :
 259             # the path for __main__ seems to be it's filename
 260             a.append('label="%s"' % self._label(path))
 261         else :
 262             a.append('label="%s"' % self._label(mod_name))
 263         if self._colored:
 264             a.append('fillcolor="%s"' % self._color(mod_name,type))
 265         else:
 266             a.append('fillcolor=white')
 267         if self._hooks._invisible_path(path):
 268             # for printing `invisible' modules
 269             a.append('peripheries=2')
 270         string = self._dot_node(name, a)
 271         #print "type %s:\t%s\t(%s)" % (mod_name, type, imp.C_EXTENSION)
 272         if type == imp.C_EXTENSION:
 273             string += self._Cext_depend_dotstring(mod_name, path)
 274         return string
 275     def _Cext_depend_dotstring(self, mod_name, path) :
 276         deps = self._Cext_depends(mod_name, path)
 277         string = ""
 278         for dep in deps :
 279             edge_attrs = self._Cext_edge_attributes(mod_name, dep)
 280             string += self._dot_node(dep, self._Cext_node_attributes(dep))
 281             string += self._dot_edge(mod_name, dep, edge_attrs)
 282         return string
 283     def _Cext_depends(self, s, path):
 284         "Return a list of dependencies for a shared object file"
 285         # make sure the extension is a shared object file (sanity check)
 286         ret = []
 287         if path.find('.so') != len(path)-len('.so'):
 288             return ret
 289         for line in popen('ldd %s' % path, 'r') :
 290             try: # ldd line:  soname [=> path] (address)
 291                 soname = line.split('=>')[0].strip()
 292                 sopath = line.split('=>')[1].split('(')[0].strip()
 293             except IndexError:
 294                 continue # irregular dependency (kernel?)
 295             if _pathmatch(self._visible_paths, path) :
 296                 ret.append(soname)
 297         return ret
 298
 299     def _Cext_edge_attributes(self, mod_name, dep_name):
 300         return [] # nothing for now...
 301
 302     def _Cext_node_attributes(self, dep_name):
 303         a = []
 304         a.append('label="%s"' % self._label(dep_name))
 305         if self._colored:
 306             a.append('fillcolor="%s"' % self._Cext_depcolor(dep_name))
 307         else:
 308             a.append('fillcolor=white')
 309         return a
 310
 311     def _Cext_depcolor(self, dep_name):
 312         # make extension dependencies green
 313         r,g,b = colorsys.hsv_to_rgb(120.0/360.0, .2, 1) # green is at 120 deg, see http://en.wikipedia.org/wiki/Image:HueScale.svg
 314         return '#%02x%02x%02x' % (r*255,g*255,b*255)
 315
 316
 317
 318
 319 class pydepgraphdot (object) :
 320     def __init__(self, hooks_instance=None, dotformat_instance=None) :
 321         if dotformat_instance != None :
 322             self._dotformat = dotformat_instance
 323         else :
 324             self._dotformat = dotformat()
 325         if hooks_instance != None :
 326             self._hooks = hooks_instance
 327         else :
 328             self._hooks = hooks()
 329         self.reset()
 330
 331     def render(self, ifile, root_module='__main__'):
 332         depgraph,types,paths = self.get_data(ifile)
 333
 334         if root_module != None :
 335             self.add_module_target(root_module)
 336
 337         depgraph,type,paths = self.fill_missing_deps(depgraph, types, paths)
 338
 339         f = self.get_output_file()
 340
 341         f.write(self._dotformat.header())
 342
 343         while True :
 344             if self._hooks.continue_test() == False :
 345                 LOG.debug('continue_test() False')
 346                 break
 347             mod = self.next_module_target()
 348             if mod == None :
 349                 LOG.debug('out of modules')
 350                 break # out of modules
 351             # I don't know anything about the underlying implementation,
 352             # but I assume `key in dict` is more efficient than `key in list`
 353             # because dicts are inherently hashed.
 354             # That's my excuse for passing around deps with dummy values.
 355             deps = depgraph[mod]
 356             type = types[mod]
 357             path = paths[mod]
 358             if self._hooks.visible_mod_test(mod, deps, type, path) == False :
 359                 LOG.debug('invisible module')
 360                 continue
 361             f.write(self._dotformat.module(mod, deps, type, path))
 362             ds = deps.keys() # now we want a consistent ordering,
 363             ds.sort()        # so pull out the keys and sort them
 364             for d in ds :
 365                 if self._hooks.follow_edge_test(mod, type, path,
 366                                                 d, types[d], paths[d]) :
 367                     LOG.debug('follow to %s' % d)
 368                     #print "%s, %s, %s, %s, %s, %s, %s" % (mod, deps, type, path, d, types[d], paths[d])
 369                     f.write(self._dotformat.edge(mod, deps, type, path,
 370                                                  d, types[d], paths[d]))
 371                     self.add_module_target(d)
 372                 else :
 373                     LOG.debug("don't follow to %s" % d)
 374
 375         f.write(self._dotformat.footer())
 376
 377     # data processing methods (input, output, checking)
 378     def get_data(self, ifile):
 379         t = eval(ifile.read())
 380         return t['depgraph'],t['types'],t['paths']
 381     def get_output_file(self):
 382         return sys.stdout
 383     def fill_missing_deps(self, depgraph, types, paths) :
 384         # normalize our input data
 385         for mod,deps in depgraph.items(): # module and it's dependencies
 386             for dep in deps.keys():
 387                 if not depgraph.has_key(dep):
 388                     # if dep not listed in depgraph somehow...
 389                     # add it in, with no further dependencies
 390                     depgraph[dep] = {}
 391                     # add dummies to types and paths too, if neccessary
 392                     if not dep in types :
 393                         types[dep] = None
 394                     if not dep in paths :
 395                         paths[dep] = None
 396                     LOG.debug("Adding dummy entry for missing module '%s'"%dep)
 397         return (depgraph, types, paths)
 398
 399     # keep a list of modules for a breadth-first search.
 400     def reset(self) :
 401         # create stacks of nodes for traversing the mesh
 402         self._modules_todo = []
 403         self._modules_entered = []
 404     def add_module_target(self, target_module) :
 405         if not target_module in self._modules_entered :
 406             # add to the back of the stack
 407             LOG.debug('push %s' % target_module)
 408             self._modules_todo.append(target_module)
 409             self._modules_entered.append(target_module)
 410         # otherwise, it's already on the list, so don't worry about it.
 411     def next_module_target(self) :
 412         if len(self._modules_todo) > 0 :
 413             LOG.debug('pop %s' % self._modules_todo[0])
 414             return self._modules_todo.pop(0) # remove from front of the list
 415         else :
 416             return None # no more modules! we're done.
 417
 418
 419 if __name__=='__main__':
 420     from optparse import OptionParser
 421
 422     usage = '%prog [options]'
 423     p = OptionParser(usage=usage, description=__doc__)
 424     p.add_option('-v', '--verbose', default=0, action='count',
 425                  help='Increment verbosity.')
 426     p.add_option('-m', '--mono', dest='color', default=True,
 427                  action='store_false', help="Don't use color.")
 428     p.add_option('-i', '--input', dest='input', default='-',
 429                  help="Path to input file ('-' for stdin, %default).")
 430     options,args = p.parse_args()
 431
 432     log_level = logging.CRITICAL - 10*options.verbose
 433     _STREAM_HANDLER.setLevel(log_level)
 434
 435     # Fancyness with shared hooks instance so we can do slick thinks like
 436     # printing all modules just inside an invisible zone, since we'll need
 437     # the dotformatter to know which nodes are visible.
 438     hk = hooks(link_outside_visited_nodes=False)
 439     dt = dotformat_Cext(colored=options.color, hooks_instance=hk)
 440     py = pydepgraphdot(hooks_instance=hk, dotformat_instance=dt)
 441
 442     if options.input == '-':
 443         ifile = sys.stdin
 444     else:
 445         ifile = open(options.input, 'r')
 446
 447     try:
 448         py.render(ifile)
 449     finally:
 450         if options.input != '-':
 451             ifile.close()