docs/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 EdgeType.cyclic = EdgeType(7)
 101 # Invalid dependency
 102 EdgeType.undocumented = EdgeType(8)
 103
 104 class Edge(object):
 105
 106     """Graph edge between two Node objects in 'dot' graph.
 107
 108     Signifies an include dependency between the two nodes, and manages types
 109     associated with the dependencies.
 110     """
 111
 112     def __init__(self, fromnode, tonode, edgetype):
 113         """Create edge between given Nodes with given type."""
 114         self._fromnode = fromnode
 115         self._tonode = tonode
 116         self._edgetype = edgetype
 117
 118     def merge_edge(self, other):
 119         """Merge another edge into this one and choose an appropriate type.
 120
 121         Updates the type of this edge based on the types of the merged edges.
 122         """
 123         self._edgetype = max(self._edgetype, other._edgetype)
 124
 125     def format(self):
 126         """Format this edge for 'dot'."""
 127         if self._fromnode.is_file_node() and self._tonode.is_file_node():
 128             properties = ''
 129         elif self._edgetype == EdgeType.intramodule:
 130             properties = ''
 131         elif self._edgetype == EdgeType.test:
 132             properties = 'color=".33 .8 .8", style=dashed'
 133         elif self._edgetype == EdgeType.libimpl:
 134             properties = 'color=".66 .8 .8", style=dashed'
 135         elif self._edgetype == EdgeType.pubimpl:
 136             properties = 'color=black, style=dashed'
 137         elif self._edgetype == EdgeType.library:
 138             properties = 'color=".66 .8 .8"'
 139         elif self._edgetype == EdgeType.public:
 140             properties = 'color=black'
 141         elif self._edgetype == EdgeType.legacy:
 142             properties = 'color=grey75'
 143         elif self._edgetype == EdgeType.cyclic:
 144             properties = 'color=red, constraint=no'
 145         else: # undocumented
 146             properties = 'color=red'
 147         return '{0} -> {1} [{2}]'.format(self._fromnode.get_nodename(),
 148                                          self._tonode.get_nodename(),
 149                                          properties)
 150
 151 class Node(object):
 152
 153     """Node in 'dot' graph."""
 154
 155     def __init__(self, nodename, label, style=None, properties=None, is_file=False):
 156         """Create node with given attributes.
 157
 158         is_file does not affect the appearance of the node, but is used for
 159         formatting edges between two files differently from other edges.
 160         style and properties should be iterables with graphviz attributes for
 161         the node.
 162
 163         Node can have child nodes.  Such nodes are rendered as cluster
 164         subgraphs for 'dot'.
 165         """
 166         self._nodename = nodename
 167         self._label = label
 168         if style:
 169             self._style = ','.join(style)
 170         else:
 171             self._style = None
 172         if properties:
 173             self._properties = ', '.join(properties)
 174         else:
 175             self._properties = None
 176         self._is_file = is_file
 177         self._children = []
 178
 179     def add_child(self, child):
 180         """Add a child node."""
 181         self._children.append(child)
 182
 183     def clear_children(self):
 184         """Remove all children from the node."""
 185         self._children = []
 186
 187     def is_file_node(self):
 188         """Return True if the node was created with is_file=True."""
 189         return self._is_file
 190
 191     def get_nodename(self):
 192         """Get internal name of the node in 'dot'."""
 193         return self._nodename
 194
 195     def get_children(self, recursive=False):
 196         """Get list of child nodes."""
 197         if recursive:
 198             result = list(self._children)
 199             for child in self._children:
 200                 result.extend(child.get_children(recursive=True))
 201             return result
 202         else:
 203             return self._children
 204
 205     def format(self):
 206         """Format this node for 'dot'."""
 207         # TODO: Take indent as a parameter to make output marginally nicer.
 208         result = ''
 209         if self._children:
 210             result += '    subgraph cluster_{0} {{\n' \
 211                           .format(self._nodename)
 212             result += '        label = "{0}"\n'.format(self._label)
 213             for child in self._children:
 214                 result += child.format()
 215             result += '    }\n'
 216         else:
 217             properties = 'label="{0}"'.format(self._label)
 218             if self._properties:
 219                 properties += ', ' + self._properties
 220             if self._style:
 221                 properties += ', style="{0}"'.format(self._style)
 222             result += '    {0} [{1}]\n'.format(self._nodename, properties)
 223         return result
 224
 225
 226 class Graph(object):
 227
 228     """Graph for 'dot'."""
 229
 230     def __init__(self, nodes, edges):
 231         """Create graph with given nodes and edges."""
 232         self._nodes = set(nodes)
 233         self._edges = edges
 234         self._left_to_right = False
 235         self._concentrate = True
 236
 237     def set_options(self, left_to_right=None, concentrate=None):
 238         """Set output options for the graph."""
 239         if left_to_right != None:
 240             self._left_to_right = left_to_right
 241         if concentrate != None:
 242             self._concentrate = concentrate
 243
 244     def merge_nodes(self, nodes, target):
 245         """Merge a set of nodes into a single node.
 246
 247         All nodes from the list nodes are merged into the target node.
 248         All edges to or from the merged nodes are rerouted to/from target
 249         instead.  Duplicate edges are not created.  Instead, if an edge already
 250         exists, the edge types are merged.  All nodes from the list nodes are
 251         removed from the graph after the merge is done.
 252         """
 253         nodes = set(nodes)
 254         nodes.add(target)
 255         newedges = []
 256         edgesto = dict()
 257         edgesfrom = dict()
 258         for edge in self._edges:
 259             isfrom = (edge._fromnode in nodes)
 260             isto = (edge._tonode in nodes)
 261             if isfrom and isto:
 262                 pass
 263             elif isfrom:
 264                 if not edge._tonode in edgesfrom:
 265                     edgesfrom[edge._tonode] = \
 266                             Edge(target, edge._tonode, edge._edgetype)
 267                 else:
 268                     edgesfrom[edge._tonode].merge_edge(edge)
 269             elif isto:
 270                 if not edge._fromnode in edgesto:
 271                     edgesto[edge._fromnode] = \
 272                             Edge(edge._fromnode, target, edge._edgetype)
 273                 else:
 274                     edgesto[edge._fromnode].merge_edge(edge)
 275             else:
 276                 newedges.append(edge)
 277         newedges.extend(edgesfrom.values())
 278         newedges.extend(edgesto.values())
 279         self._edges = newedges
 280
 281     def collapse_node(self, node):
 282         """Merge all children of a node into the node.
 283
 284         All child nodes are removed after the merge is done.
 285         """
 286         nodes = node.get_children(recursive=True)
 287         self.merge_nodes(nodes, node)
 288         node.clear_children()
 289
 290     def write(self, outfile):
 291         """Write the graph in 'dot' format."""
 292         outfile.write('digraph includedeps {\n')
 293         if self._left_to_right:
 294             outfile.write('    rankdir = LR\n')
 295         if self._concentrate:
 296             outfile.write('    concentrate = true\n')
 297         outfile.write('    node [fontname="FreeSans",fontsize=10,height=.2,'
 298                                  'shape=box]\n')
 299         for node in self._nodes:
 300             outfile.write(node.format())
 301         for edge in self._edges:
 302             outfile.write('    ' + edge.format() + '\n')
 303         outfile.write('}\n')
 304
 305 class GraphBuilder(object):
 306
 307     """Builder for Graph objects from gmxtree.GromacsTree representation."""
 308
 309     def __init__(self, tree):
 310         """Initialize builder for a given tree representation."""
 311         self._tree = tree
 312
 313     def _create_file_node(self, fileobj, filenodes):
 314         """Create graph node for a file object.
 315
 316         filenodes is a dict() that maps file objects to their nodes, and is
 317         updated by this call.
 318         """
 319         nodename = re.subn(r'[-./]', '_', fileobj.get_relpath())[0]
 320         style = []
 321         properties = []
 322         properties.append('URL="\\ref {0}"'.format(fileobj.get_name()))
 323         if not fileobj.get_module():
 324             style.append('bold')
 325             properties.append('color=red')
 326         if fileobj.is_test_file():
 327             style.append('filled')
 328             properties.append('fillcolor=".33 .2 1"')
 329         elif fileobj.is_source_file():
 330             style.append('filled')
 331             properties.append('fillcolor=grey75')
 332         elif fileobj.get_api_type() == DocType.public:
 333             style.append('filled')
 334             properties.append('fillcolor=".66 .2 1"')
 335         elif fileobj.get_api_type() == DocType.library:
 336             style.append('filled')
 337             properties.append('fillcolor=".66 .5 1"')
 338         node = Node(nodename, fileobj.get_name(), style, properties, is_file=True)
 339         filenodes[fileobj] = node
 340         return node
 341
 342     def _get_file_edge_type(self, fromfile, tofile):
 343         """Get EdgeType for an edge between two file objects.
 344
 345         Determines the type for the edge from the information provided by
 346         gmxtree.
 347         """
 348         intramodule = (fromfile.get_module() == tofile.get_module())
 349         is_legacy = not tofile.api_type_is_reliable()
 350         if fromfile.get_module() == tofile.get_module():
 351             return EdgeType.intramodule
 352         elif tofile.get_api_type() == DocType.internal and not tofile.is_public():
 353             if is_legacy:
 354                 return EdgeType.legacy
 355             else:
 356                 return EdgeType.undocumented
 357         elif fromfile.is_test_file():
 358             return EdgeType.test
 359         elif tofile.is_test_file():
 360             return EdgeType.undocumented
 361         elif fromfile.is_module_internal():
 362             if tofile.is_public():
 363                 return EdgeType.pubimpl
 364             elif tofile.get_api_type() == DocType.library:
 365                 return EdgeType.libimpl
 366             elif is_legacy:
 367                 return EdgeType.legacy
 368             elif not tofile.is_documented():
 369                 return EdgeType.undocumented
 370             else:
 371                 raise ValueError('Unknown edge type between {0} and {1}'
 372                         .format(fromfile.get_relpath(), tofile.get_relpath()))
 373         elif fromfile.get_api_type() == DocType.library:
 374             return EdgeType.library
 375         elif fromfile.is_public() or fromfile.is_installed():
 376             if tofile.is_public() or tofile.is_installed():
 377                 return EdgeType.public
 378             else:
 379                 return EdgeType.undocumented
 380         elif is_legacy:
 381             return EdgeType.legacy
 382         else:
 383             raise ValueError('Unknown edge type between {0} and {1}'
 384                     .format(fromfile.get_relpath(), tofile.get_relpath()))
 385
 386     def _create_file_edge(self, fromfile, tofile, filenodes):
 387         """Create edge between two file objects.
 388
 389         Determines the type for the edge from the information provided by
 390         gmxtree.
 391         """
 392         edgetype = self._get_file_edge_type(fromfile, tofile)
 393         return Edge(filenodes[fromfile], filenodes[tofile], edgetype)
 394
 395     def _create_file_edges(self, filenodes):
 396         """Create edges between all file nodes.
 397
 398         Create edges between file nodes specified in filenodes from all include
 399         dependencies.  An edge is created only if both ends of the dependency
 400         are in the list of nodes.
 401         """
 402         edges = []
 403         for fileobj in filenodes.iterkeys():
 404             for includedfile in fileobj.get_includes():
 405                 otherfile = includedfile.get_file()
 406                 if otherfile and otherfile in filenodes:
 407                     edge = self._create_file_edge(fileobj, otherfile, filenodes)
 408                     edges.append(edge)
 409         return edges
 410
 411     def _get_module_color(self, modulegroup):
 412         if modulegroup == 'legacy':
 413             return 'fillcolor=grey75'
 414         elif modulegroup == 'analysismodules':
 415             return 'fillcolor="0 .2 1"'
 416         elif modulegroup == 'utilitymodules':
 417             return 'fillcolor=".08 .2 1"'
 418         elif modulegroup == 'mdrun':
 419             return 'fillcolor=".75 .2 1"'
 420         return None
 421
 422     def _create_module_node(self, module):
 423         """Create node for a module."""
 424         style = []
 425         properties = []
 426         properties.append('shape=ellipse')
 427         properties.append('URL="\\ref module_{0}"'.format(module.get_name()))
 428         if not module.is_documented():
 429             fillcolor = self._get_module_color('legacy')
 430         else:
 431             fillcolor = self._get_module_color(module.get_group())
 432         if fillcolor:
 433             style.append('filled')
 434             properties.append(fillcolor)
 435         rootdir = module.get_root_dir()
 436         if rootdir.has_installed_files():
 437             properties.append('color=".66 .5 1"')
 438             properties.append('penwidth=3')
 439         nodename = 'module_' + re.subn(r'[-./]', '_', rootdir.get_relpath())[0]
 440         label = module.get_name()[7:]
 441         node = Node(nodename, label, style, properties)
 442         return node
 443
 444     def _create_module_edges(self, modulenodes):
 445         """Create edges between all module nodes.
 446
 447         Create edges between module nodes specified in modulenodes from all
 448         include dependencies.  An edge is created only if both ends of the
 449         dependency are in the list of nodes.
 450         """
 451         edges = []
 452         for moduleobj in modulenodes.iterkeys():
 453             for dep in moduleobj.get_dependencies():
 454                 othermodule = dep.get_other_module()
 455                 if othermodule and othermodule in modulenodes:
 456                     if dep.is_cycle_suppressed():
 457                         edgetype = EdgeType.cyclic
 458                     else:
 459                         edgetype = max([
 460                             self._get_file_edge_type(x.get_including_file(), x.get_file())
 461                             for x in dep.get_included_files()])
 462                     edge = Edge(modulenodes[moduleobj], modulenodes[othermodule], edgetype)
 463                     edges.append(edge)
 464         return edges
 465
 466
 467     def _create_legend_node(self, label, modulegroup):
 468         if modulegroup:
 469             nodename = 'legend_' + modulegroup
 470             fillcolor = self._get_module_color(modulegroup)
 471         else:
 472             nodename = 'legend_' + label
 473             fillcolor = None
 474         style = []
 475         properties = []
 476         if fillcolor:
 477             style.append('filled')
 478             properties.append(fillcolor)
 479         return Node(nodename, label, style, properties)
 480
 481     def create_modules_graph(self):
 482         """Create module dependency graph."""
 483         nodes = []
 484         modulenodes = dict()
 485         libgromacsnode = Node('libgromacs', 'libgromacs')
 486         nodes.append(libgromacsnode)
 487         for moduleobj in self._tree.get_modules():
 488             node = self._create_module_node(moduleobj)
 489             if moduleobj.get_root_dir().get_relpath().startswith('src/gromacs'):
 490                 libgromacsnode.add_child(node)
 491             else:
 492                 nodes.append(node)
 493             modulenodes[moduleobj] = node
 494         edges = self._create_module_edges(modulenodes)
 495         # TODO: Consider adding invisible edges to order the nodes better.
 496         # TODO: Consider adding legend for the edge types as well.
 497         legendnode = Node('legend', 'legend')
 498         legendnode.add_child(self._create_legend_node('legacy', 'legacy'))
 499         legendnode.add_child(self._create_legend_node('analysis', 'analysismodules'))
 500         legendnode.add_child(self._create_legend_node('utility', 'utilitymodules'))
 501         legendnode.add_child(self._create_legend_node('mdrun', 'mdrun'))
 502         legendnode.add_child(Node('legend_installed', 'installed', properties=['color=".66 .5 1"', 'penwidth=3']))
 503         nodes.append(legendnode)
 504         graph = Graph(nodes, edges)
 505         graph.set_options(concentrate=False)
 506         return graph
 507
 508     def create_module_file_graph(self, module):
 509         """Create file dependency graph for files within a module."""
 510         filenodes = dict()
 511         nodes = []
 512         for fileobj in module.get_files():
 513             nodes.append(self._create_file_node(fileobj, filenodes))
 514         edges = self._create_file_edges(filenodes)
 515         graph = Graph(nodes, edges)
 516         graph.set_options(left_to_right=True)
 517         return graph
 518
 519 def main():
 520     """Run the graph generation script."""
 521     import os
 522     import sys
 523
 524     from optparse import OptionParser
 525
 526     from gmxtree import GromacsTree
 527     from reporter import Reporter
 528
 529     parser = OptionParser()
 530     parser.add_option('-S', '--source-root',
 531                       help='Source tree root directory')
 532     parser.add_option('-B', '--build-root',
 533                       help='Build tree root directory')
 534     parser.add_option('--ignore-cycles',
 535                       help='Set file with module dependencies to ignore in cycles')
 536     parser.add_option('-o', '--outdir', default='.',
 537                       help='Specify output directory for graphs')
 538     parser.add_option('-q', '--quiet', action='store_true',
 539                       help='Do not write status messages')
 540     options, args = parser.parse_args()
 541
 542     reporter = Reporter(quiet=True)
 543
 544     if not options.quiet:
 545         sys.stderr.write('Scanning source tree...\n')
 546     tree = GromacsTree(options.source_root, options.build_root, reporter)
 547     tree.load_installed_file_list()
 548     if not options.quiet:
 549         sys.stderr.write('Reading source files...\n')
 550     tree.scan_files()
 551     if options.ignore_cycles:
 552         tree.load_cycle_suppression_list(options.ignore_cycles)
 553     if not options.quiet:
 554         sys.stderr.write('Reading Doxygen XML files...\n')
 555     tree.load_xml(only_files=True)
 556
 557     if not options.quiet:
 558         sys.stderr.write('Writing graphs...\n')
 559     graphbuilder = GraphBuilder(tree)
 560     if not os.path.exists(options.outdir):
 561         os.mkdir(options.outdir)
 562
 563     filename = os.path.join(options.outdir, 'module-deps.dot')
 564     graph = graphbuilder.create_modules_graph()
 565     with open(filename, 'w') as outfile:
 566         graph.write(outfile)
 567
 568     # Skip some modules that are too big to make any sense
 569     skippedmodules = ('legacyheaders', 'gmxlib', 'mdlib', 'gmxana', 'gmxpreprocess')
 570     for module in tree.get_modules():
 571         if not module.get_name()[7:] in skippedmodules:
 572             filename = '{0}-deps.dot'.format(module.get_name())
 573             filename = os.path.join(options.outdir, filename)
 574             graph = graphbuilder.create_module_file_graph(module)
 575             with open(filename, 'w') as outfile:
 576                 graph.write(outfile)
 577
 578 if __name__ == '__main__':
 579     main()