3 # Copyright 2004 Toby Dickenson
4 # Copyright 2008-2011 W. Trevor King
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:
14 # The above copyright notice and this permission notice shall be included
15 # in all copies or substantial portions of the Software.
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.
25 """Convert `py2depgraph` dependency data to Graphviz dot syntax.
29 from hashlib import md5
32 from os import popen, getuid # for finding C extension dependencies with system calls
33 from pwd import getpwuid
38 LOG = logging.getLogger('get_css')
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)
46 USER=getpwuid(getuid())[0] # get effective user name
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.*')
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 :
60 class hooks (object) :
62 Modules show up if visible_mod_test(...) == True.
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) :
79 def visible_mod_test(self, mod_name, dep_dict, type, path,
80 check_external_link=True) :
82 Return true if this module is interesting and should be drawn.
83 Return false if it should be completely omitted.
85 if self._invisible_name(mod_name) == True :
86 LOG.debug('invisible module %s' % mod_name)
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
95 def follow_edge_test(self, module_name, type, path,
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__')
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')
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.
127 def _invisible_path(self, path) :
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.
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)):
140 class dotformat (object) :
141 def __init__(self, colored=True, hooks_instance=None) :
142 if hooks_instance != None :
143 self._hooks = hooks_instance
145 self._hooks = hooks()
146 self._colored = colored
148 return ('digraph G {\n'
149 #' concentrate = true;\n'
150 #' ordering = out;\n'
152 ' node [style=filled,fontname=Helvetica,fontsize=10];\n')
155 def module(self, mod_name, dep_dict, type, path) :
156 name = self._fix_name(mod_name)
158 if mod_name == '__main__' :
159 # the path for __main__ seems to be it's filename
160 a.append('label="%s"' % self._label(path))
162 a.append('label="%s"' % self._label(mod_name))
164 a.append('fillcolor="%s"' % self._color(mod_name,type))
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)
176 weight = self._weight(mod_name,dep_name)
178 a.append('weight=%d' % weight)
179 length = self._alien(mod_name)
181 a.append('minlen=%d' % length)
182 return self._dot_edge(name, target, a)
184 def _fix_name(self, mod_name):
185 # Convert a module name to a syntactically correct node name
186 return mod_name.replace('.','_')
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.
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
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.
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:
222 i = mod_name.rfind('.')
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)
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)
241 def _dot_edge(self, source, target, attrs) :
242 string = ' %s -> %s' % (source, target)
243 string += self._attribute_string(attrs)
246 def _attribute_string(self, attributes):
249 string += ' [%s]' % (','.join(attributes))
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)
258 if mod_name == '__main__' :
259 # the path for __main__ seems to be it's filename
260 a.append('label="%s"' % self._label(path))
262 a.append('label="%s"' % self._label(mod_name))
264 a.append('fillcolor="%s"' % self._color(mod_name,type))
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)
275 def _Cext_depend_dotstring(self, mod_name, path) :
276 deps = self._Cext_depends(mod_name, path)
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)
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)
287 if path.find('.so') != len(path)-len('.so'):
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()
294 continue # irregular dependency (kernel?)
295 if _pathmatch(self._visible_paths, path) :
299 def _Cext_edge_attributes(self, mod_name, dep_name):
300 return [] # nothing for now...
302 def _Cext_node_attributes(self, dep_name):
304 a.append('label="%s"' % self._label(dep_name))
306 a.append('fillcolor="%s"' % self._Cext_depcolor(dep_name))
308 a.append('fillcolor=white')
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)
319 class pydepgraphdot (object) :
320 def __init__(self, hooks_instance=None, dotformat_instance=None) :
321 if dotformat_instance != None :
322 self._dotformat = dotformat_instance
324 self._dotformat = dotformat()
325 if hooks_instance != None :
326 self._hooks = hooks_instance
328 self._hooks = hooks()
331 def render(self, ifile, root_module='__main__'):
332 depgraph,types,paths = self.get_data(ifile)
334 if root_module != None :
335 self.add_module_target(root_module)
337 depgraph,type,paths = self.fill_missing_deps(depgraph, types, paths)
339 f = self.get_output_file()
341 f.write(self._dotformat.header())
344 if self._hooks.continue_test() == False :
345 LOG.debug('continue_test() False')
347 mod = self.next_module_target()
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.
358 if self._hooks.visible_mod_test(mod, deps, type, path) == False :
359 LOG.debug('invisible module')
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
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)
373 LOG.debug("don't follow to %s" % d)
375 f.write(self._dotformat.footer())
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):
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
391 # add dummies to types and paths too, if neccessary
392 if not dep in types :
394 if not dep in paths :
396 LOG.debug("Adding dummy entry for missing module '%s'"%dep)
397 return (depgraph, types, paths)
399 # keep a list of modules for a breadth-first search.
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
416 return None # no more modules! we're done.
419 if __name__=='__main__':
420 from optparse import OptionParser
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()
432 log_level = logging.CRITICAL - 10*options.verbose
433 _STREAM_HANDLER.setLevel(log_level)
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)
442 if options.input == '-':
445 ifile = open(options.input, 'r')
450 if options.input != '-':