1| # $Id: ClassTree.py,v 1.6 2003/02/01 05:38:17 chalky Exp $
    2| #
    3| # This file is a part of Synopsis.
    4| # Copyright (C) 2000, 2001 Stephen Davies
    5| # Copyright (C) 2000, 2001 Stefan Seefeld
    6| #
    7| # Synopsis is free software; you can redistribute it and/or modify it
    8| # under the terms of the GNU General Public License as published by
    9| # the Free Software Foundation; either version 2 of the License, or
   10| # (at your option) any later version.
   11| #
   12| # This program is distributed in the hope that it will be useful,
   13| # but WITHOUT ANY WARRANTY; without even the implied warranty of
   14| # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   15| # General Public License for more details.
   16| #
   17| # You should have received a copy of the GNU General Public License
   18| # along with this program; if not, write to the Free Software
   19| # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   20| # 02111-1307, USA.
   21| #
   22| # $Log: ClassTree.py,v $
   23| # Revision 1.6  2003/02/01 05:38:17  chalky
   24| # Include Unknown parents in the class tree, so they appear in the inheritance
   25| # graphs
   26| #
   27| # Revision 1.5  2002/09/20 10:37:07  chalky
   28| # Fix a crash bug
   29| #
   30| # Revision 1.4  2002/01/09 11:43:41  chalky
   31| # Inheritance pics
   32| #
   33| # Revision 1.3  2001/07/04 08:18:04  uid20151
   34| # Comments
   35| #
   36| # Revision 1.2  2001/04/06 02:37:08  chalky
   37| # Add all superclasses to classes list, so that Unknown superclasses are in
   38| # graphs too (and hence, if they are roots, make sure we dont miss subgraphs!)
   39| #
   40| # Revision 1.1  2001/02/05 05:53:04  chalky
   41| # Moved from HTML/core.py. Added graphs()
   42| #
   43| #
   44| 
   45| """Contains the utility class ClassTree, for creating inheritance trees."""
   46| 
   47| # Synopsis modules
   48| from Synopsis.Core import AST, Type
   49| 
   50| 
   51| def sort(list):
   52|     "Utility func to sort and return the given list"
   53|     list.sort()
   54|     return list
   55| 
   56| 
   57| 
   58| class ClassTree(AST.Visitor):
   59|     """Maintains a tree of classes directed by inheritance. This object always
   60|     exists in HTML, since it is used for other things such as printing class bases."""
   61|     # TODO - only create if needed (if Info tells us to)
   62|     def __init__(self):
   63|         self.__superclasses = {}
   64|         self.__subclasses = {}
   65|         self.__classes = []
   66|         # Graph stuffs:
   67|         self.__buckets = [] # List of buckets, each a list of classnames
   68|         self.__processed = {} # Map of processed class names
   69|     
   70|     def add_inheritance(self, supername, subname):
   71|         """Adds an edge to the graph. Supername and subname are the scoped
   72|         names of the two classes involved in the edge, and are copied before
   73|         being stored."""
   74|         supername, subname = tuple(supername), tuple(subname)
   75|         self.add_class(supername)
   76|         if not self.__subclasses.has_key(supername):
   77|             subs = self.__subclasses[supername] = []
   78|         else:
   79|             subs = self.__subclasses[supername]
   80|         if subname not in subs:
   81|             subs.append(subname)
   82|         if not self.__superclasses.has_key(subname):
   83|             sups = self.__superclasses[subname] = []
   84|         else:
   85|             sups = self.__superclasses[subname]
   86|         if supername not in sups:
   87|             sups.append(supername)
   88|     
   89|     def subclasses(self, classname):
   90|         """Returns a sorted list of all classes derived from the given
   91|         class"""
   92|         classname = tuple(classname)
   93|         if self.__subclasses.has_key(classname):
   94|             return sort(self.__subclasses[classname])
   95|         return []
   96|     def superclasses(self, classname):
   97|         """Returns a sorted list of all classes the given class derives
   98|         from. The classes are returned as scoped names, which you may use to
   99|         lookup the class declarations in the 'types' dictionary if you need
  100|         to."""
  101|         classname = tuple(classname)
  102|         if self.__superclasses.has_key(classname):
  103|             return sort(self.__superclasses[classname])
  104|         return []
  105|     
  106|     def classes(self):
  107|         """Returns a sorted list of all class names"""
  108|         return sort(self.__classes)
  109|     def add_class(self, name):
  110|         """Adds a class to the list of classes by name"""
  111|         name = tuple(name)
  112|         if name not in self.__classes:
  113|             self.__classes.append(tuple(name))
  114|     
  115|     def _is_root(self, name): return not self.__superclasses.has_key(name)
  116|     def _is_leaf(self, name): return not self.__subclasses.has_key(name)
  117|     def roots(self):
  118|         """Returns a list of classes that have no superclasses"""
  119|         return filter(self._is_root, self.classes())
  120| 
  121|     #
  122|     # Graph methods
  123|     #
  124|     def graphs(self):
  125|         """Returns a list of graphs. Each graph is just a list of connected
  126|         classes."""
  127|         self._make_graphs()
  128|         return self.__buckets
  129| 
  130|     def leaves(self, graph):
  131|         """Returns a list of leaves in the given graph. A leaf is a class with
  132|         no subclasses"""
  133|         return filter(self._is_leaf, graph)
  134| 
  135|     def _make_graphs(self):
  136|         for root in self.roots():
  137|             if self.__processed.has_key(root):
  138|                # Already processed this class
  139|                continue
  140|             bucket = [] ; self.__buckets.append(bucket)
  141|             classes = [root]
  142|             while len(classes):
  143|                name = classes.pop()
  144|                if self.__processed.has_key(name):
  145|                    # Already processed this class
  146|                continue
  147|                # Add to bucket
  148|                bucket.append(name)
  149|                self.__processed[name] = None
  150|                # Add super- and sub-classes
  151|                classes.extend( self.superclasses(name) )
  152|                classes.extend( self.subclasses(name) )
  153|     #
  154|     # AST Visitor
  155|     #
  156| 
  157|     def visitAST(self, ast):
  158|         for decl in ast.declarations():
  159|             decl.accept(self)
  160|     def visitScope(self, scope):
  161|         for decl in scope.declarations():
  162|             decl.accept(self)
  163|     def visitClass(self, clas):
  164|         """Adds this class and all edges to the lists"""
  165|         name = clas.name()
  166|         self.add_class(name)
  167|         for inheritance in clas.parents():
  168|             parent = inheritance.parent()
  169|             if hasattr(parent, 'declaration'): 
  170|                self.add_inheritance(parent.declaration().name(), name)
  171|             elif isinstance(parent, Type.Parametrized) and parent.template():
  172|                self.add_inheritance(parent.template().name(), name)
  173|             elif isinstance(parent, Type.Unknown):
  174|                self.add_inheritance(parent.link(), name)
  175|         for decl in clas.declarations():
  176|             decl.accept(self)
  177| 
  178|