File: Synopsis/Formatters/ClassTree.py 1
2
3
4
5
6
7
8
9"""Contains the utility class ClassTree, for creating inheritance trees."""
10
11from Synopsis import ASG
12
13
14class ClassTree(ASG.Visitor):
15 """Maintains a tree of classes directed by inheritance. This object always
16 exists in HTML, since it is used for other things such as printing class bases."""
17
18
19 def __init__(self):
20 self.__superclasses = {}
21 self.__subclasses = {}
22 self.__classes = []
23
24 self.__buckets = []
25
26 def add_inheritance(self, supername, subname):
27 """Adds an edge to the graph. Supername and subname are the scoped
28 names of the two classes involved in the edge, and are copied before
29 being stored."""
30 self.add_class(supername)
31 if not self.__subclasses.has_key(supername):
32 subs = self.__subclasses[supername] = []
33 else:
34 subs = self.__subclasses[supername]
35 if subname not in subs:
36 subs.append(subname)
37 subs.sort()
38 if not self.__superclasses.has_key(subname):
39 sups = self.__superclasses[subname] = []
40 else:
41 sups = self.__superclasses[subname]
42 if supername not in sups:
43 sups.append(supername)
44 sups.sort()
45
46 def subclasses(self, classname):
47 """Returns a sorted list of all classes derived from the given
48 class"""
49
50 if self.__subclasses.has_key(classname):
51 return self.__subclasses[classname]
52 else:
53 return []
54
55 def superclasses(self, classname):
56 """Returns a sorted list of all classes the given class derives
57 from. The classes are returned as scoped names, which you may use to
58 lookup the class declarations in the 'types' dictionary if you need
59 to."""
60
61 if self.__superclasses.has_key(classname):
62 return self.__superclasses[classname]
63 else:
64 return []
65
66 def classes(self):
67 """Returns a sorted list of all class names"""
68
69 return self.__classes
70
71 def add_class(self, name):
72 """Adds a class to the list of classes by name"""
73
74 if name not in self.__classes:
75 self.__classes.append(name)
76 self.__classes.sort()
77
78 def roots(self):
79 """Returns a list of classes that have no superclasses"""
80
81 return [c for c in self.classes() if c not in self.__superclasses]
82
83
84
85
86 def graphs(self):
87 """Returns a list of graphs. Each graph is just a list of connected
88 classes."""
89
90 self._make_graphs()
91 return self.__buckets
92
93 def leaves(self, graph):
94 """Returns a list of leaves in the given graph. A leaf is a class with
95 no subclasses"""
96
97 return [c for c in graph if c not in self.__subclasses]
98
99 def _make_graphs(self):
100
101 processed = {}
102 for root in self.roots():
103 if root in processed:
104 continue
105 bucket = []
106 self.__buckets.append(bucket)
107 classes = [root]
108 while len(classes):
109 name = classes.pop()
110 if name in processed:
111 continue
112
113 bucket.append(name)
114 processed[name] = True
115
116 classes.extend(self.superclasses(name))
117 classes.extend(self.subclasses(name))
118
119
120
121
122 def visit_scope(self, scope):
123 for d in scope.declarations:
124 d.accept(self)
125
126 def visit_class(self, class_):
127 """Adds this class and all edges to the lists"""
128
129 self.add_class(class_.name)
130 for inheritance in class_.parents:
131 parent = inheritance.parent
132 if hasattr(parent, 'declaration'):
133 self.add_inheritance(parent.declaration.name, class_.name)
134 elif isinstance(parent, ASG.ParametrizedTypeId) and parent.template:
135 self.add_inheritance(parent.template.name, class_.name)
136 elif isinstance(parent, ASG.UnknownTypeId):
137 self.add_inheritance(parent.link, class_.name)
138 for d in class_.declarations:
139 d.accept(self)
140
Generated on Thu Apr 16 16:27:13 2009 by
synopsis (version devel)