1 #!/usr/bin/env python

     2 #

     3 # Copyright 2008 the Melange authors.

     4 #

     5 # Licensed under the Apache License, Version 2.0 (the "License");

     6 # you may not use this file except in compliance with the License.

     7 # You may obtain a copy of the License at

     8 #

     9 #   http://www.apache.org/licenses/LICENSE-2.0

    10 #

    11 # Unless required by applicable law or agreed to in writing, software

    12 # distributed under the License is distributed on an "AS IS" BASIS,

    13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

    14 # See the License for the specific language governing permissions and

    15 # limitations under the License.

    16 

    17 """TODO(SRabbelier) Update __doc__ string

    18 """

    19 

    20 __authors__ = [

    21   '"Sverre Rabbelier" <sverre@rabbelier.nl>',

    22   ]

    23 

    24 

    25 import sys

    26 

    27 import cPickle

    28 import os

    29 import graph

    30 

    31 

    32 ROOTDIR = "soc"

    33 

    34 

    35 def parseFile(file_name):

    36   if os.path.exists("imports.dat"):

    37     log = open("imports.dat", "r")

    38     all_imports = cPickle.load(log)

    39     log.close()

    40   else:

    41     all_imports = {}

    42 

    43   if file_name in all_imports:

    44     print "Overwriting previous data on '%s'." % file_name

    45 

    46   imports = []

    47 

    48   file = open(file_name)

    49 

    50   for line in file:

    51     if line.lstrip().startswith('import soc'):

    52       splitline = line[:-1].split(' ')

    53       mod = splitline[1]

    54       imports.append(mod)

    55 

    56     if line.lstrip().startswith('from soc'):

    57       splitline = line[:-1].split(' ')

    58       mod = splitline[1] + '.' + splitline[3]

    59       imports.append(mod)

    60 

    61   for idx, imp in enumerate(imports):

    62     if imp in set(imports[idx+1:]):

    63       sys.stderr.write("Warning: file '%s' has a redundant import: '%s'.\n" % (file_name, imp))

    64 

    65   if file_name.endswith("__init__.py"):

    66     normalized = file_name[:-12].replace('/', '.')

    67   else:

    68     normalized = file_name[:-3].replace('/', '.')

    69 

    70   print "Writing imports for file %s (%s)." % (file_name, normalized)

    71   all_imports[normalized] = imports

    72 

    73   log = open("imports.dat", "w")

    74   cPickle.dump(all_imports, log)

    75   log.close()

    76 

    77   return 0

    78 

    79 

    80 def buildGraph():

    81   if not os.path.exists("imports.dat"):

    82     sys.stderr.write("Missing imports.dat file, run 'build' first\n")

    83     return

    84 

    85   log = open("imports.dat", "r")

    86   all_imports = cPickle.load(log)

    87 

    88   gr = graph.digraph()

    89 

    90   gr.add_nodes(all_imports.keys())

    91 

    92   for file_name, imports in all_imports.iteritems():

    93     for imp in imports:

    94       gr.add_edge(file_name, imp)

    95 

    96   return gr

    97 

    98 

    99 def showGraph(gr):

   100   for node in gr:

   101     print "%s: " % node

   102     for edge in gr[node]:

   103       print "\t%s" % edge

   104 

   105   return 0

   106 

   107 

   108 def getParents(gst, target):

   109   parents = []

   110   current = target

   111 

   112   while True:

   113     for node in gst:

   114       if current in gst[node]:

   115         parents.append(node)

   116         current = node

   117         break

   118     else:

   119       break

   120 

   121   return parents

   122 

   123 

   124 def pathFrom(parents, first, target):

   125   idx = parents.index(first)

   126   path = parents[idx::-1]

   127   return [target] + path + [target]

   128 

   129 

   130 def findCycle(gr, gst, target):

   131   parents = getParents(gst, target)

   132   cycles = []

   133 

   134   for node in gr[target]:

   135     if node in parents:

   136       cycles.append(pathFrom(parents, node, target))

   137 

   138   return cycles

   139 

   140 

   141 def findCycles(gr):

   142   st, pre, post = gr.depth_first_search()

   143   gst = graph.digraph()

   144   gst.add_spanning_tree(st)

   145 

   146   cycles = []

   147 

   148   for node in gr:

   149     cycles += findCycle(gr, gst, node)

   150 

   151   return cycles

   152 

   153 

   154 def drawGraph(gr):

   155   st, pre, post = gr.depth_first_search()

   156   gst = graph.digraph()

   157   gst.add_spanning_tree(st)

   158 

   159   sys.path.append('/usr/lib/graphviz/python/')

   160   import gv

   161   dot = gst.write(fmt='dot')

   162   gvv = gv.readstring(dot)

   163   gv.layout(gvv,'dot')

   164   gv.render(gvv,'png','imports.png')

   165 

   166 

   167 def accumulate(arg, dirname, fnames):

   168   for fname in fnames:

   169     if not fname.endswith(".py"):

   170       continue

   171 

   172     arg.append(os.path.join(dirname, fname))

   173 

   174 

   175 def main(args):

   176   if len(args) != 1:

   177     print "Supported options: 'print', 'build', 'find', and 'draw'."

   178     return -1

   179 

   180   action = args[0]

   181 

   182   if action == "build":

   183     fnames = []

   184     os.path.walk(ROOTDIR, accumulate, fnames)

   185 

   186     for fname in fnames:

   187       parseFile(fname)

   188 

   189     print "Done parsing."

   190     return 0

   191 

   192   gr = buildGraph()

   193   if not gr:

   194     return 1

   195 

   196   if action == "show":

   197     return showGraph(gr)

   198 

   199   if action == "draw":

   200     return drawGraph(gr)

   201 

   202   if action == "find":

   203     cycles = findCycles(gr)

   204     for cycle in cycles:

   205       print cycle

   206     return 0

   207 

   208   print "Unknown option."

   209   return -1

   210 

   211 

   212 if __name__ == '__main__':

   213   import sys

   214   os.chdir("../app")

   215   res = main(sys.argv[1:])

   216   sys.exit(0)