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