1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
# $Id: ClassTree.py,v 1.8 2003/11/13 17:30:06 stefan Exp $
#
# Copyright (C) 2000 Stefan Seefeld
# Copyright (C) 2000 Stephen Davies
# All rights reserved.
# Licensed to the public under the terms of the GNU LGPL (>= 2),
# see the file COPYING for details.
#
"""Contains the utility class ClassTree, for creating inheritance trees."""
from Synopsis import AST, Type
def sort(list):
"Utility func to sort and return the given list"
list.sort()
return list
class ClassTree(AST.Visitor):
"""Maintains a tree of classes directed by inheritance. This object always
exists in HTML, since it is used for other things such as printing class bases."""
# TODO - only create if needed (if Info tells us to)
def __init__(self):
self.__superclasses = {}
self.__subclasses = {}
self.__classes = []
# Graph stuffs:
self.__buckets = [] # List of buckets, each a list of classnames
self.__processed = {} # Map of processed class names
def add_inheritance(self, supername, subname):
"""Adds an edge to the graph. Supername and subname are the scoped
names of the two classes involved in the edge, and are copied before
being stored."""
supername, subname = tuple(supername), tuple(subname)
self.add_class(supername)
if not self.__subclasses.has_key(supername):
subs = self.__subclasses[supername] = []
else:
subs = self.__subclasses[supername]
if subname not in subs:
subs.append(subname)
if not self.__superclasses.has_key(subname):
sups = self.__superclasses[subname] = []
else:
sups = self.__superclasses[subname]
if supername not in sups:
sups.append(supername)
def subclasses(self, classname):
"""Returns a sorted list of all classes derived from the given
class"""
classname = tuple(classname)
if self.__subclasses.has_key(classname):
return sort(self.__subclasses[classname])
return []
def superclasses(self, classname):
"""Returns a sorted list of all classes the given class derives
from. The classes are returned as scoped names, which you may use to
lookup the class declarations in the 'types' dictionary if you need
to."""
classname = tuple(classname)
if self.__superclasses.has_key(classname):
return sort(self.__superclasses[classname])
return []
def classes(self):
"""Returns a sorted list of all class names"""
return sort(self.__classes)
def add_class(self, name):
"""Adds a class to the list of classes by name"""
name = tuple(name)
if name not in self.__classes:
self.__classes.append(tuple(name))
def _is_root(self, name): return not self.__superclasses.has_key(name)
def _is_leaf(self, name): return not self.__subclasses.has_key(name)
def roots(self):
"""Returns a list of classes that have no superclasses"""
return filter(self._is_root, self.classes())
#
# Graph methods
#
def graphs(self):
"""Returns a list of graphs. Each graph is just a list of connected
classes."""
self._make_graphs()
return self.__buckets
def leaves(self, graph):
"""Returns a list of leaves in the given graph. A leaf is a class with
no subclasses"""
return filter(self._is_leaf, graph)
def _make_graphs(self):
for root in self.roots():
if self.__processed.has_key(root):
# Already processed this class
continue
bucket = [] ; self.__buckets.append(bucket)
classes = [root]
while len(classes):
name = classes.pop()
if self.__processed.has_key(name):
# Already processed this class
continue
# Add to bucket
bucket.append(name)
self.__processed[name] = None
# Add super- and sub-classes
classes.extend( self.superclasses(name) )
classes.extend( self.subclasses(name) )
#
# AST Visitor
#
def visitAST(self, ast):
for decl in ast.declarations():
decl.accept(self)
def visitScope(self, scope):
for decl in scope.declarations():
decl.accept(self)
def visitClass(self, clas):
"""Adds this class and all edges to the lists"""
name = clas.name()
self.add_class(name)
for inheritance in clas.parents():
parent = inheritance.parent()
if hasattr(parent, 'declaration'):
self.add_inheritance(parent.declaration().name(), name)
elif isinstance(parent, Type.Parametrized) and parent.template():
self.add_inheritance(parent.template().name(), name)
elif isinstance(parent, Type.Unknown):
self.add_inheritance(parent.link(), name)
for decl in clas.declarations():
decl.accept(self)
|
