1#!/usr/bin/env python
2
3'''
4This program takes a list of module files and creates a (possibly disjoint)
5directed graph of the modules and their dependencies. Arrows on the
6directed graph point to the dependent module.
7
8Typical usage would be as follows:
9 VisualizeModuleDependencies.py VTKSourceDir vtkFiltersSources,vtkInteractionStyle,vtkRenderingOpenGL2
10
11'''
12
13import os, sys
14from collections import defaultdict
15import vtk
16
17def GetProgramParameters():
18    import argparse
19    description = 'Creates a directed graph of the modules and their dependencies.'
20    epilogue = '''
21        This program takes a list of module files and creates a
22        (possibly disjoint) directed graph of the modules and their
23        dependencies. Arrows on the directed graph point to the dependent module.
24        By default, dependencies of a given module are followed to their maximum
25        depth. However you can restrict the depth by specifying the depth to
26        which dependent modules are searched.
27        The moduleList is a comma-separated list of module names with no
28        spaces between the names.
29        The treeDepth defaults to 0, this means that for a given module all
30        dependent modules will be found. If non-zero, then trees will be only
31        searched to that depth.
32    '''
33    parser = argparse.ArgumentParser(description=description, epilog=epilogue)
34    parser.add_argument('vtkSourceDir', help='The path to the vtk Source Directory.')
35    parser.add_argument('moduleList', help='The list of modules.')
36    parser.add_argument('moduleTreeDepth', help='The depth of the module trees', nargs='?', default=0, type=int)
37    args = parser.parse_args()
38    vtkSourceDir = args.vtkSourceDir
39    moduleList = [x.strip() for x in args.moduleList.split(',')]
40    moduleTreeDepth = args.moduleTreeDepth
41    return (vtkSourceDir, moduleList, moduleTreeDepth)
42
43def GetProgramParametersOld():
44    '''
45    Used for Python versions < 2.7
46    '''
47    if len(sys.argv) < 3:
48        s = 'Usage: ' + sys.argv[0] + ' vtkSourceDir moduleList [moduleTreeDepth]'
49        print(s)
50        exit(0)
51    args = dict()
52    args['vtkSourceDir'] = sys.argv[1]
53    args['moduleList'] = sys.argv[2]
54    args['moduleTreeDepth'] = 0
55    if len(sys.argv) > 3:
56        args['moduleTreeDepth'] = int(sys.argv[3])
57    vtkSourceDir = args['vtkSourceDir']
58    moduleList = [x.strip() for x in args['moduleList'].split(',')]
59    moduleTreeDepth = args['moduleTreeDepth']
60    return (vtkSourceDir, moduleList, moduleTreeDepth)
61
62def FindModuleFiles(path):
63    '''
64    Get a list of module files in the VTK directory.
65    '''
66    moduleFiles = [os.path.join(root, name)
67                 for root, dirs, files in os.walk(path)
68                 for name in files
69                 if name == ("module.cmake")]
70    return moduleFiles
71
72def ParseModuleFile(fileName):
73    '''
74    Read each module file returning the module name and what
75    it depends on or implements.
76    '''
77    fh = open(fileName, 'rb')
78    lines = []
79    for line in fh:
80        line = line.strip()
81        if line.startswith('$'):  # Skip CMake variable names
82            continue
83        if line.startswith('#'):
84            continue
85        line = line.split('#')[0].strip()  # inline comments
86        if line == "":
87            continue
88        line = line.split(')')[0].strip()  # closing brace with no space
89        if line == "":
90            continue
91        for l in line.split(" "):
92            lines.append(l)
93    languages = ['PYTHON', 'JAVA']
94    keywords = ['BACKEND', 'COMPILE_DEPENDS', 'DEPENDS', 'EXCLUDE_FROM_ALL',
95                'EXCLUDE_FROM_WRAPPING', 'GROUPS', 'IMPLEMENTS', 'KIT', 'LEGACY',
96                'PRIVATE_DEPENDS', 'TEST_DEPENDS', 'OPTIONAL_PYTHON_LINK'
97                'IMPLEMENTATION_REQUIRED_BY_BACKEND'] + \
98               map(lambda l: 'EXCLUDE_FROM_%s_WRAPPING' % l, languages)
99    moduleName = ""
100    depends = []
101    implements = []
102    state = "START";
103    for item in lines:
104        if state == "START" and item.startswith("vtk_module("):
105            moduleName = item.split("(")[1]
106            continue
107        if item in keywords:
108            state = item
109            continue
110        if state == 'DEPENDS' and item != ')':
111            depends.append(item)
112            continue
113        if state == 'IMPLEMENTS' and item != ')':
114            implements.append(item)
115            continue
116    return [moduleName, depends + implements]
117
118def FindAllNeededModules(modules, foundModules, moduleDepencencies):
119    '''
120    Recursively search moduleDependencies finding all modules.
121    '''
122    if modules != None and len(modules) > 0:
123        for m in modules:
124            foundModules.add(m)
125            foundModules = foundModules | set(moduleDepencencies[m])  # Set union
126            foundModules = FindAllNeededModules(moduleDepencencies[m],
127                                                foundModules, moduleDepencencies)
128    return foundModules
129
130def MakeModuleTree(module, index, tree, moduleDependencies, treeDepth, level=0):
131    '''
132    For a given module make a tree with the module as the root and the
133    dependent modules as children.
134    '''
135    if module:
136        index = index + [module]
137        if treeDepth == 0 or level < treeDepth:
138            for m in moduleDependencies[module]:
139                level += 1
140                MakeModuleTree(m, index, tree, moduleDependencies, treeDepth, level)
141                level -= 1
142    Add(tree, index)
143
144# One-line Tree in Python
145# See: https:gist.github.com/hrldcpr/2012250
146def Tree(): return defaultdict(Tree)
147
148def Add(tree, keys):
149    for key in keys:
150        tree = tree[key]
151
152def PrettyPrint(tree, level=0):
153    '''
154    Useful to visualize the tree.
155    '''
156    result = ''
157    for k, v in tree.iteritems():
158        s = '  ' * level + k + '\n'
159        result += s
160        level += 1
161        result += PrettyPrint(v, level)
162        level -= 1
163    return result
164
165def GetAllKeys(tree):
166    '''
167    Return all the modules in the tree as a set.
168    '''
169    modules = set()
170    for key in tree:
171        modules = set(list(modules) + [key] + list(GetAllKeys(tree[key])))
172    return modules
173
174def MakeEdgeList(t):
175    '''
176    Return a set that represents the edges in the tree.
177    '''
178    edgeList = set()
179    for k, v in t.iteritems():
180        subKeys = v.keys()
181        if subKeys:
182            for kk in subKeys:
183                edgeList.add((k, kk))
184        edg = MakeEdgeList(v)
185        if edg:
186            edgeList.update(edg)
187    return edgeList
188
189def MakeGraph(t, parent='', level=0):
190    '''
191    Returns a list that has two elements, the vertices and the edge list.
192    '''
193    return [GetAllKeys(t), MakeEdgeList(t)]
194
195def GenerateGraph(moduleList, moduleDepencencies, moduleTreeDepth):
196    '''
197    Generate a graph from the module list.
198    The resultant graph is a list consisting of two sets, the first set
199    is the set of vertices and the second set is the edge list.
200    '''
201    graph = [set(), set()]
202    for m in moduleList:
203        t = Tree()
204        MakeModuleTree(m, [], t, moduleDepencencies, moduleTreeDepth)
205        g = MakeGraph(t)
206        graph[0].update(g[0])
207        if g[1]:
208            graph[1].update(g[1])
209    return graph
210
211def GenerateVTKGraph(graph):
212    '''
213    Take the vertices and edge list in the graph parameter
214    and return a VTK graph.
215    '''
216    g = vtk.vtkMutableDirectedGraph()
217    # Label the vertices
218    labels = vtk.vtkStringArray()
219    labels.SetNumberOfComponents(1)
220    labels.SetName("Labels")
221
222    index = dict()
223    l = list(graph[0])
224    # Make the vertex labels and create a dictionary with the
225    # keys as labels and the vertex ids as the values.
226    for i in range(0, len(l)):
227        # Set the vertex labels
228        labels.InsertNextValue(l[i])
229        index[l[i]] = g.AddVertex()
230    g.GetVertexData().AddArray(labels)
231    # Add edges
232    l = list(graph[1])
233    for i in range(0, len(l)):
234        ll = list(l[i])
235        g.AddGraphEdge(index[ll[0]], index[ll[1]])
236#    g.Dump()
237    return g
238
239def DisplayGraph(graph):
240    '''
241    Display the graph.
242    '''
243    theme = vtk.vtkViewTheme()
244    theme.SetBackgroundColor(0, 0, .1)
245    theme.SetBackgroundColor2(0, 0, .5)
246
247    # Layout the graph
248    # Pick a strategy you like.
249    # strategy = vtk.vtkCircularLayoutStrategy()
250    strategy = vtk.vtkSimple2DLayoutStrategy()
251    # strategy = vtk.vtkRandomLayoutStrategy()
252    layout = vtk.vtkGraphLayout()
253    layout.SetLayoutStrategy(strategy)
254    layout.SetInputData(graph)
255
256    view = vtk.vtkGraphLayoutView()
257    view.AddRepresentationFromInputConnection(layout.GetOutputPort())
258    # Tell the view to use the vertex layout we provide.
259    view.SetLayoutStrategyToPassThrough()
260    view.SetEdgeLabelVisibility(True)
261    view.SetVertexLabelArrayName("Labels")
262    view.SetVertexLabelVisibility(True)
263    view.ApplyViewTheme(theme)
264
265    # Manually create an actor containing the glyphed arrows.
266    # Get the edge geometry
267    edgeGeom = vtk.vtkGraphToPolyData()
268    edgeGeom.SetInputConnection(layout.GetOutputPort())
269    edgeGeom.EdgeGlyphOutputOn()
270
271    # Set the position (0: edge start, 1: edge end) where
272    # the edge arrows should go.
273#        edgeGeom.SetEdgeGlyphPosition(0.8)
274    edgeGeom.SetEdgeGlyphPosition(0.85)
275
276    # Make a simple edge arrow for glyphing.
277#        arrowSource = vtk.vtkGlyphSource2D()
278#        arrowSource.SetGlyphTypeToEdgeArrow()
279#        arrowSource.SetScale(0.075)
280    # Or use a cone.
281    coneSource = vtk.vtkConeSource()
282    coneSource.SetRadius(0.025)
283    coneSource.SetHeight(0.1)
284    coneSource.SetResolution(12)
285
286    # Use Glyph3D to repeat the glyph on all edges.
287    arrowGlyph = vtk.vtkGlyph3D()
288    arrowGlyph.SetInputConnection(0, edgeGeom.GetOutputPort(1))
289#        arrowGlyph.SetInputConnection(1, arrowSource.GetOutputPort())
290    arrowGlyph.SetInputConnection(1, coneSource.GetOutputPort())
291
292    # Add the edge arrow actor to the view.
293    arrowMapper = vtk.vtkPolyDataMapper()
294    arrowMapper.SetInputConnection(arrowGlyph.GetOutputPort())
295    arrowActor = vtk.vtkActor()
296    arrowActor.SetMapper(arrowMapper)
297    view.GetRenderer().AddActor(arrowActor)
298
299    view.ResetCamera()
300    view.Render()
301
302    view.SetInteractionModeTo3D()
303    view.GetInteractor().Initialize()
304    view.GetInteractor().Start()
305
306def main():
307    ver = list(sys.version_info[0:2])
308    ver = ver[0] + ver[1] / 10.0
309    if ver >= 2.7:
310        vtkSourceDir, moduleList, moduleTreeDepth = GetProgramParameters()
311    else:
312        vtkSourceDir, moduleList, moduleTreeDepth = GetProgramParametersOld()
313
314    # Parse the module files making a dictionary of each module and its
315    # dependencies or what it implements.
316    moduleDepencencies = dict()
317    moduleFiles = FindModuleFiles(vtkSourceDir + "/")
318    for fname in moduleFiles:
319        m = ParseModuleFile(fname)
320        moduleDepencencies[m[0]] = m[1]
321
322    # Generate a graph from the module list.
323    graph = GenerateGraph(moduleList, moduleDepencencies, moduleTreeDepth)
324
325    # Now build a vtk graph.
326    g = GenerateVTKGraph(graph)
327
328    # Display it.
329    DisplayGraph(g)
330
331if __name__ == '__main__':
332    main()
333