doxygen/graphbuilder.py

   1 #!/usr/bin/python
   2 #
   3 # This file is part of the GROMACS molecular simulation package.
   4 #
   5 # Copyright (c) 2012,2013,2014, by the GROMACS development team, led by
   6 # Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   7 # and including many others, as listed in the AUTHORS file in the
   8 # top-level source directory and at http://www.gromacs.org.
   9 #
  10 # GROMACS is free software; you can redistribute it and/or
  11 # modify it under the terms of the GNU Lesser General Public License
  12 # as published by the Free Software Foundation; either version 2.1
  13 # of the License, or (at your option) any later version.
  14 #
  15 # GROMACS is distributed in the hope that it will be useful,
  16 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18 # Lesser General Public License for more details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public
  21 # License along with GROMACS; if not, see
  22 # http://www.gnu.org/licenses, or write to the Free Software Foundation,
  23 # Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  24 #
  25 # If you want to redistribute modifications to GROMACS, please
  26 # consider that scientific software is very special. Version
  27 # control is crucial - bugs must be traceable. We will be happy to
  28 # consider code for inclusion in the official distribution, but
  29 # derived work must not be called official GROMACS. Details are found
  30 # in the README & COPYING files - if they are missing, get the
  31 # official version at http://www.gromacs.org.
  32 #
  33 # To help us fund GROMACS development, we humbly ask that you cite
  34 # the research papers on the package. Check out http://www.gromacs.org.
  35
  36 """Generate include dependency graphs.
  37
  38 This script generates include dependency graphs from the GROMACS source tree.
  39 One graph is generated to show inter-module dependencies, and separate graphs
  40 for each module to show file-level dependencies within the module.
  41
  42 Output format for the graphs is suitable for processing with 'dot' in graphviz.
  43
  44 The graphs are built from the source tree representation constructed in
  45 gmxtree.py.
  46
  47 Classes Graph, Node, Edge, and EdgeType provide a relatively general
  48 implementation for constructing 'dot' graphs.  GraphBuilder is used to
  49 create Graph instances from a gmxtree.GromacsTree object; the actual graph
  50 objects will not contain any references to the gmxtree objects.
  51
  52 When run in script mode, the GromacsTree object is first constructed, and then
  53 GraphBuilder is used to construct the necessary graphs, which are then written
  54 out.
  55
  56 The produced graphs are documented in doxygen.md.
  57 """
  58
  59 import os.path
  60 import re
  61
  62 from gmxtree import DocType
  63
  64 class EdgeType(object):
  65
  66     """Enumeration type for edge types in include dependency graphs."""
  67
  68     # Mapping to string representation for the internal integer values
  69     _names = ['test', 'pubimpl', 'libimpl', 'library', 'public',
  70             'intramodule', 'legacy', 'undocumented']
  71
  72     def __init__(self, value):
  73         """Initialize a EdgeType instance.
  74
  75         EdgeType.{test,pubimpl,...,undocumented} should be used outside the
  76         class instead of calling the constructor.
  77         """
  78         self._value = value
  79
  80     def __str__(self):
  81         """Return string representation for the edge type (for debugging)."""
  82         return self._names[self._value]
  83
  84     def __cmp__(self, other):
  85         """Order edge types in the order of increasing coupling."""
  86         return cmp(self._value, other._value)
  87
  88 # Tests depend on test
  89 EdgeType.test = EdgeType(0)
  90 # Implementation depends on public/library headers
  91 EdgeType.pubimpl = EdgeType(1)
  92 EdgeType.libimpl = EdgeType(2)
  93 # Library header depends on other module
  94 EdgeType.library = EdgeType(3)
  95 # Public header depends on other module
  96 EdgeType.public = EdgeType(4)
  97 # Intramodule dependency
  98 EdgeType.intramodule = EdgeType(5)
  99 EdgeType.legacy = EdgeType(6)
 100 # Invalid dependency
 101 EdgeType.undocumented = EdgeType(7)
 102
 103 class Edge(object):
 104
 105     """Graph edge between two Node objects in 'dot' graph.
 106
 107     Signifies an include dependency between the two nodes, and manages types
 108     associated with the dependencies.
 109     """
 110
 111     def __init__(self, fromnode, tonode, edgetype):
 112         """Create edge between given Nodes with given type."""
 113         self._fromnode = fromnode
 114         self._tonode = tonode
 115         self._edgetype = edgetype
 116
 117     def merge_edge(self, other):
 118         """Merge another edge into this one and choose an appropriate type.
 119
 120         Updates the type of this edge based on the types of the merged edges.
 121         """
 122         self._edgetype = max(self._edgetype, other._edgetype)
 123
 124     def format(self):
 125         """Format this edge for 'dot'."""
 126         if self._fromnode.is_file_node() and self._tonode.is_file_node():
 127             properties = ''
 128         elif self._edgetype == EdgeType.intramodule:
 129             properties = ''
 130         elif self._edgetype == EdgeType.test:
 131             properties = 'color=".33 .8 .8", style=dashed'
 132         elif self._edgetype == EdgeType.libimpl:
 133             properties = 'color=".66 .8 .8", style=dashed'
 134         elif self._edgetype == EdgeType.pubimpl:
 135             properties = 'color=black, style=dashed'
 136         elif self._edgetype == EdgeType.library:
 137             properties = 'color=".66 .8 .8"'
 138         elif self._edgetype == EdgeType.public:
 139             properties = 'color=black'
 140         elif self._edgetype == EdgeType.legacy:
 141             properties = 'color=grey75'
 142         else: # undocumented
 143             properties = 'color=red'
 144         return '{0} -> {1} [{2}]'.format(self._fromnode.get_nodename(),
 145                                          self._tonode.get_nodename(),
 146                                          properties)
 147
 148 class Node(object):
 149
 150     """Node in 'dot' graph."""
 151
 152     def __init__(self, nodename, label, style=None, properties=None, is_file=False):
 153         """Create node with given attributes.
 154
 155         is_file does not affect the appearance of the node, but is used for
 156         formatting edges between two files differently from other edges.
 157         style and properties should be iterables with graphviz attributes for
 158         the node.
 159
 160         Node can have child nodes.  Such nodes are rendered as cluster
 161         subgraphs for 'dot'.
 162         """
 163         self._nodename = nodename
 164         self._label = label
 165         if style:
 166             self._style = ','.join(style)
 167         else:
 168             self._style = None
 169         if properties:
 170             self._properties = ', '.join(properties)
 171         else:
 172             self._properties = None
 173         self._is_file = is_file
 174         self._children = []
 175
 176     def add_child(self, child):
 177         """Add a child node."""
 178         self._children.append(child)
 179
 180     def clear_children(self):
 181         """Remove all children from the node."""
 182         self._children = []
 183
 184     def is_file_node(self):
 185         """Return True if the node was created with is_file=True."""
 186         return self._is_file
 187
 188     def get_nodename(self):
 189         """Get internal name of the node in 'dot'."""
 190         return self._nodename
 191
 192     def get_children(self, recursive=False):
 193         """Get list of child nodes."""
 194         if recursive:
 195             result = list(self._children)
 196             for child in self._children:
 197                 result.extend(child.get_children(recursive=True))
 198             return result
 199         else:
 200             return self._children
 201
 202     def format(self):
 203         """Format this node for 'dot'."""
 204         # TODO: Take indent as a parameter to make output marginally nicer.
 205         result = ''
 206         if self._children:
 207             result += '    subgraph cluster_{0} {{\n' \
 208                           .format(self._nodename)
 209             result += '        label = "{0}"\n'.format(self._label)
 210             for child in self._children:
 211                 result += child.format()
 212             result += '    }\n'
 213         else:
 214             properties = 'label="{0}"'.format(self._label)
 215             if self._properties:
 216                 properties += ', ' + self._properties
 217             if self._style:
 218                 properties += ', style="{0}"'.format(self._style)
 219             result += '    {0} [{1}]\n'.format(self._nodename, properties)
 220         return result
 221
 222
 223 class Graph(object):
 224
 225     """Graph for 'dot'."""
 226
 227     def __init__(self, nodes, edges):
 228         """Create graph with given nodes and edges."""
 229         self._nodes = set(nodes)
 230         self._edges = edges
 231         self._left_to_right = False
 232         self._concentrate = True
 233
 234     def set_options(self, left_to_right=None, concentrate=None):
 235         """Set output options for the graph."""
 236         if left_to_right != None:
 237             self._left_to_right = left_to_right
 238         if concentrate != None:
 239             self._concentrate = concentrate
 240
 241     def merge_nodes(self, nodes, target):
 242         """Merge a set of nodes into a single node.
 243
 244         All nodes from the list nodes are merged into the target node.
 245         All edges to or from the merged nodes are rerouted to/from target
 246         instead.  Duplicate edges are not created.  Instead, if an edge already
 247         exists, the edge types are merged.  All nodes from the list nodes are
 248         removed from the graph after the merge is done.
 249         """
 250         nodes = set(nodes)
 251         nodes.add(target)
 252         newedges = []
 253         edgesto = dict()
 254         edgesfrom = dict()
 255         for edge in self._edges:
 256             isfrom = (edge._fromnode in nodes)
 257             isto = (edge._tonode in nodes)
 258             if isfrom and isto:
 259                 pass
 260             elif isfrom:
 261                 if not edge._tonode in edgesfrom:
 262                     edgesfrom[edge._tonode] = \
 263                             Edge(target, edge._tonode, edge._edgetype)
 264                 else:
 265                     edgesfrom[edge._tonode].merge_edge(edge)
 266             elif isto:
 267                 if not edge._fromnode in edgesto:
 268                     edgesto[edge._fromnode] = \
 269                             Edge(edge._fromnode, target, edge._edgetype)
 270                 else:
 271                     edgesto[edge._fromnode].merge_edge(edge)
 272             else:
 273                 newedges.append(edge)
 274         newedges.extend(edgesfrom.values())
 275         newedges.extend(edgesto.values())
 276         self._edges = newedges
 277
 278     def collapse_node(self, node):
 279         """Merge all children of a node into the node.
 280
 281         All child nodes are removed after the merge is done.
 282         """
 283         nodes = node.get_children(recursive=True)
 284         self.merge_nodes(nodes, node)
 285         node.clear_children()
 286
 287     def write(self, outfile):
 288         """Write the graph in 'dot' format."""
 289         outfile.write('digraph includedeps {\n')
 290         if self._left_to_right:
 291             outfile.write('    rankdir = LR\n')
 292         if self._concentrate:
 293             outfile.write('    concentrate = true\n')
 294         outfile.write('    node [fontname="FreeSans",fontsize=10,height=.2,'
 295                                  'shape=box]\n')
 296         for node in self._nodes:
 297             outfile.write(node.format())
 298         for edge in self._edges:
 299             outfile.write('    ' + edge.format() + '\n')
 300         outfile.write('}\n')
 301
 302 class GraphBuilder(object):
 303
 304     """Builder for Graph objects from gmxtree.GromacsTree representation."""
 305
 306     def __init__(self, tree):
 307         """Initialize builder for a given tree representation."""
 308         self._tree = tree
 309
 310     def _create_file_node(self, fileobj, filenodes):
 311         """Create graph node for a file object.
 312
 313         filenodes is a dict() that maps file objects to their nodes, and is
 314         updated by this call.
 315         """
 316         nodename = re.subn(r'[-./]', '_', fileobj.get_relpath())[0]
 317         style = []
 318         properties = []
 319         properties.append('URL="\\ref {0}"'.format(fileobj.get_name()))
 320         if not fileobj.get_module():
 321             style.append('bold')
 322             properties.append('color=red')
 323         if fileobj.is_test_file():
 324             style.append('filled')
 325             properties.append('fillcolor=".33 .2 1"')
 326         elif fileobj.is_source_file():
 327             style.append('filled')
 328             properties.append('fillcolor=grey75')
 329         elif fileobj.get_api_type() == DocType.public:
 330             style.append('filled')
 331             properties.append('fillcolor=".66 .2 1"')
 332         elif fileobj.get_api_type() == DocType.library:
 333             style.append('filled')
 334             properties.append('fillcolor=".66 .5 1"')
 335         node = Node(nodename, fileobj.get_name(), style, properties, is_file=True)
 336         filenodes[fileobj] = node
 337         return node
 338
 339     def _create_file_edge(self, fromfile, tofile, filenodes):
 340         """Create edge between two file objects.
 341
 342         Determines the type for the edge from the information provided by
 343         gmxtree.
 344         """
 345         intramodule = (fromfile.get_module() == tofile.get_module())
 346         is_legacy = not tofile.api_type_is_reliable()
 347         if fromfile.get_module() == tofile.get_module():
 348             edgetype = EdgeType.intramodule
 349         elif tofile.get_api_type() == DocType.internal and not tofile.is_public():
 350             if is_legacy:
 351                 edgetype = EdgeType.legacy
 352             else:
 353                 edgetype = EdgeType.undocumented
 354         elif fromfile.is_test_file():
 355             edgetype = EdgeType.test
 356         elif tofile.is_test_file():
 357             edgetype = EdgeType.undocumented
 358         elif fromfile.is_module_internal():
 359             if tofile.is_public():
 360                 edgetype = EdgeType.pubimpl
 361             elif tofile.get_api_type() == DocType.library:
 362                 edgetype = EdgeType.libimpl
 363             elif is_legacy:
 364                 edgetype = EdgeType.legacy
 365             elif not tofile.is_documented():
 366                 edgetype = EdgeType.undocumented
 367             else:
 368                 raise ValueError('Unknown edge type between {0} and {1}'
 369                         .format(fromfile.get_relpath(), tofile.get_relpath()))
 370         elif fromfile.get_api_type() == DocType.library:
 371             edgetype = EdgeType.library
 372         elif fromfile.is_public() or fromfile.is_installed():
 373             if tofile.is_public() or tofile.is_installed():
 374                 edgetype = EdgeType.public
 375             else:
 376                 edgetype = EdgeType.undocumented
 377         elif is_legacy:
 378             edgetype = EdgeType.legacy
 379         else:
 380             raise ValueError('Unknown edge type between {0} and {1}'
 381                     .format(fromfile.get_relpath(), tofile.get_relpath()))
 382         return Edge(filenodes[fromfile], filenodes[tofile], edgetype)
 383
 384     def _create_file_edges(self, filenodes):
 385         """Create edges between all file nodes.
 386
 387         Create edges between file nodes specified in filenodes from all include
 388         dependencies.  An edge is created only if both ends of the dependency
 389         are in the list of nodes.
 390         """
 391         edges = []
 392         for fileobj in filenodes.iterkeys():
 393             for includedfile in fileobj.get_includes():
 394                 otherfile = includedfile.get_file()
 395                 if otherfile and otherfile in filenodes:
 396                     edge = self._create_file_edge(fileobj, otherfile, filenodes)
 397                     edges.append(edge)
 398         return edges
 399
 400     def _get_module_color(self, modulegroup):
 401         if modulegroup == 'legacy':
 402             return 'fillcolor=grey75'
 403         elif modulegroup == 'analysismodules':
 404             return 'fillcolor="0 .2 1"'
 405         elif modulegroup == 'utilitymodules':
 406             return 'fillcolor=".08 .2 1"'
 407         elif modulegroup == 'mdrun':
 408             return 'fillcolor=".75 .2 1"'
 409         return None
 410
 411     def _create_module_node(self, module, filenodes):
 412         """Create node for a module.
 413
 414         The created node will have all files in the module as its child nodes.
 415         All created file nodes are added to the filenodes dict.
 416         """
 417         style = []
 418         properties = []
 419         properties.append('shape=ellipse')
 420         properties.append('URL="\\ref module_{0}"'.format(module.get_name()))
 421         if not module.is_documented():
 422             fillcolor = self._get_module_color('legacy')
 423         else:
 424             fillcolor = self._get_module_color(module.get_group())
 425         if fillcolor:
 426             style.append('filled')
 427             properties.append(fillcolor)
 428         rootdir = module.get_root_dir()
 429         if rootdir.has_installed_files():
 430             properties.append('color=".66 .5 1"')
 431             properties.append('penwidth=3')
 432         nodename = 'module_' + re.subn(r'[-./]', '_', rootdir.get_relpath())[0]
 433         label = module.get_name()[7:]
 434         node = Node(nodename, label, style, properties)
 435         for childfile in module.get_files():
 436             node.add_child(self._create_file_node(childfile, filenodes))
 437         return node
 438
 439     def _create_legend_node(self, label, modulegroup):
 440         if modulegroup:
 441             nodename = 'legend_' + modulegroup
 442             fillcolor = self._get_module_color(modulegroup)
 443         else:
 444             nodename = 'legend_' + label
 445             fillcolor = None
 446         style = []
 447         properties = []
 448         if fillcolor:
 449             style.append('filled')
 450             properties.append(fillcolor)
 451         return Node(nodename, label, style, properties)
 452
 453     def create_modules_graph(self):
 454         """Create module dependency graph."""
 455         filenodes = dict()
 456         nodes = []
 457         modulenodes = []
 458         libgromacsnode = Node('libgromacs', 'libgromacs')
 459         nodes.append(libgromacsnode)
 460         for moduleobj in self._tree.get_modules():
 461             node = self._create_module_node(moduleobj, filenodes)
 462             if moduleobj.get_root_dir().get_relpath().startswith('src/gromacs'):
 463                 libgromacsnode.add_child(node)
 464             else:
 465                 nodes.append(node)
 466             modulenodes.append(node)
 467         edges = self._create_file_edges(filenodes)
 468         # TODO: Consider adding invisible edges to order the nodes better.
 469         # TODO: Consider adding legend for the edge types as well.
 470         legendnode = Node('legend', 'legend')
 471         legendnode.add_child(self._create_legend_node('legacy', 'legacy'))
 472         legendnode.add_child(self._create_legend_node('analysis', 'analysismodules'))
 473         legendnode.add_child(self._create_legend_node('utility', 'utilitymodules'))
 474         legendnode.add_child(self._create_legend_node('mdrun', 'mdrun'))
 475         legendnode.add_child(Node('legend_installed', 'installed', properties=['color=".66 .5 1"', 'penwidth=3']))
 476         nodes.append(legendnode)
 477         graph = Graph(nodes, edges)
 478         for node in modulenodes:
 479             graph.collapse_node(node)
 480         graph.set_options(concentrate=False)
 481         return graph
 482
 483     def create_module_file_graph(self, module):
 484         """Create file dependency graph for files within a module."""
 485         filenodes = dict()
 486         nodes = []
 487         for fileobj in module.get_files():
 488             nodes.append(self._create_file_node(fileobj, filenodes))
 489         edges = self._create_file_edges(filenodes)
 490         graph = Graph(nodes, edges)
 491         graph.set_options(left_to_right=True)
 492         return graph
 493
 494 def main():
 495     """Run the graph generation script."""
 496     import os
 497     import sys
 498
 499     from optparse import OptionParser
 500
 501     from gmxtree import GromacsTree
 502     from reporter import Reporter
 503
 504     parser = OptionParser()
 505     parser.add_option('-S', '--source-root',
 506                       help='Source tree root directory')
 507     parser.add_option('-B', '--build-root',
 508                       help='Build tree root directory')
 509     parser.add_option('--installed',
 510                       help='Read list of installed files from given file')
 511     parser.add_option('-o', '--outdir', default='.',
 512                       help='Specify output directory for graphs')
 513     parser.add_option('-q', '--quiet', action='store_true',
 514                       help='Do not write status messages')
 515     options, args = parser.parse_args()
 516
 517     installedlist = []
 518     if options.installed:
 519         with open(options.installed, 'r') as outfile:
 520             for line in outfile:
 521                 installedlist.append(line.strip())
 522
 523     reporter = Reporter(quiet=True)
 524
 525     if not options.quiet:
 526         sys.stderr.write('Scanning source tree...\n')
 527     tree = GromacsTree(options.source_root, options.build_root, reporter)
 528     tree.set_installed_file_list(installedlist)
 529     if not options.quiet:
 530         sys.stderr.write('Reading source files...\n')
 531     tree.scan_files()
 532     if not options.quiet:
 533         sys.stderr.write('Reading Doxygen XML files...\n')
 534     tree.load_xml(only_files=True)
 535
 536     if not options.quiet:
 537         sys.stderr.write('Writing graphs...\n')
 538     graphbuilder = GraphBuilder(tree)
 539     if not os.path.exists(options.outdir):
 540         os.mkdir(options.outdir)
 541
 542     filename = os.path.join(options.outdir, 'module-deps.dot')
 543     graph = graphbuilder.create_modules_graph()
 544     with open(filename, 'w') as outfile:
 545         graph.write(outfile)
 546
 547     # Skip some modules that are too big to make any sense
 548     skippedmodules = ('legacyheaders', 'gmxlib', 'mdlib', 'gmxana', 'gmxpreprocess')
 549     for module in tree.get_modules():
 550         if not module.get_name()[7:] in skippedmodules:
 551             filename = '{0}-deps.dot'.format(module.get_name())
 552             filename = os.path.join(options.outdir, filename)
 553             graph = graphbuilder.create_module_file_graph(module)
 554             with open(filename, 'w') as outfile:
 555                 graph.write(outfile)
 556
 557 if __name__ == '__main__':
 558     main()