Panda3D

typeRegistryNode.cxx
Go to the documentation of this file.
1 /**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file typeRegistryNode.cxx
10 * @author drose
11 * @date 2001-08-06
12 */
13
14 #include "typeRegistryNode.h"
15
16 #include <algorithm>
17 #include <string.h>
18
19 bool TypeRegistryNode::_paranoid_inheritance = false;
20
21 /**
22 *
23 */
24 TypeRegistryNode::
25 TypeRegistryNode(TypeHandle handle, const std::string &name, TypeHandle &ref) :
26 _handle(handle), _name(name), _ref(ref)
27 {
28 clear_subtree();
29 memset(_memory_usage, 0, sizeof(_memory_usage));
30 }
31
32 /**
33 * Returns true if the child RegistryNode represents a class that inherits
34 * directly or indirectly from the class represented by the base RegistryNode.
35 */
36 bool TypeRegistryNode::
37 is_derived_from(const TypeRegistryNode *child, const TypeRegistryNode *base) {
38 // This function is the basis for TypedObject::is_of_type(), which gets used
39 // quite frequently within Panda, often in inner-loop code. Therefore, we
40 // go through some pains to make this function as efficient as possible.
41
42 // First, compare the subtree tops. If they are the same, then this node
43 // and the base node are within the same single-inheritance subtree, and we
44 // can use our bitmask trick to determine the relationship with no
45 // additional work. (See r_build_subtrees()).
46
47 if (child->_inherit._top == base->_inherit._top) {
48 assert(child->_inherit._top != nullptr);
49
50 bool derives =
51 Inherit::is_derived_from(child->_inherit, base->_inherit);
52
53 #ifndef NDEBUG
54 if (_paranoid_inheritance) {
55 bool paranoid_derives = check_derived_from(child, base);
56 if (derives != paranoid_derives) {
57 std::cerr
58 << "Inheritance test for " << child->_name
59 << " from " << base->_name << " failed!\n"
60 << "Result: " << derives << " should have been: "
61 << paranoid_derives << "\n"
62 << "Classes are in the same single inheritance subtree, children of "
63 << child->_inherit._top->_name << "\n"
64 << std::hex
65 << child->_name << " has mask " << child->_inherit._mask
66 << " and bits " << child->_inherit._bits << "\n"
67 << base->_name << " has mask " << base->_inherit._mask
68 << " and bits " << base->_inherit._bits << "\n"
69 << std::dec;
70 return paranoid_derives;
71 }
72 }
73 #endif
74
75 /*
76 cerr << "trivial: " << child->_name << " vs. " << base->_name
77 << " (" << child->_inherit._top->_name << ") = " << derives << "\n";
78 */
79
80 return derives;
81 }
82
83 // The two nodes are not within the same single-inheritance subtree. This
84 // complicates things a bit.
85
86 // First, we should check whether the subtree tops of the two nodes inherit
87 // from each other.
88 TypeRegistryNode *child_top = child->_inherit._top;
89 TypeRegistryNode *base_top = base->_inherit._top;
90
91 bool derives = false;
92
93 // If child_top does not inherit from base_top, it follows that child does
94 // not inherit from base.
95 TopInheritance::const_iterator ti =
96 lower_bound(child_top->_top_inheritance.begin(),
97 child_top->_top_inheritance.end(),
98 Inherit(base_top, 0, 0));
99
100 while (ti != child_top->_top_inheritance.end() &&
101 (*ti)._top == base_top &&
102 !derives) {
103 // If child_top *does* inherit from base_top, then child may or may not
104 // inherit from base. This depends on the exact path of inheritance.
105 // Since there might be multiple paths from child_top to base_top, we have
106 // to examine all of them.
107 const Inherit &connection = (*ti);
108
109 // Here is one inheritance from child_top to base_top. If the connecting
110 // node inherits from base, then child also inherits from base. If the
111 // connecting node does not inherit from base, we must keep looking.
112 derives = Inherit::is_derived_from(connection, base->_inherit);
113
114 ++ti;
115 }
116
117 #ifndef NDEBUG
118 if (_paranoid_inheritance) {
119 bool paranoid_derives = check_derived_from(child, base);
120 if (derives != paranoid_derives) {
121 std::cerr
122 << "Inheritance test for " << child->_name
123 << " from " << base->_name << " failed!\n"
124 << "Result: " << derives << " should have been: "
125 << paranoid_derives << "\n"
126 << child->_name << " is a descendent of "
127 << child_top->_name << "\n"
128 << base->_name << " is a descendent of "
129 << base_top->_name << "\n";
130 return paranoid_derives;
131 }
132 }
133 #endif
134
135 /*
136 cerr << "complex: " << child->_name << " (" << child->_inherit._top->_name
137 << ") vs. " << base->_name << " (" << base->_inherit._top->_name
138 << ") = " << derives << "\n";
139 */
140 return derives;
141 }
142
143 /**
144 * Returns the first parent class of child that is a descendant of the
145 * indicated base class.
146 */
147 TypeHandle TypeRegistryNode::
148 get_parent_towards(const TypeRegistryNode *child,
149 const TypeRegistryNode *base) {
150 if (child == base) {
151 return child->_handle;
152 }
153
154 Classes::const_iterator ni;
155 for (ni = child->_parent_classes.begin();
156 ni != child->_parent_classes.end(); ++ni) {
157 if (is_derived_from((*ni), base)) {
158 return (*ni)->_handle;
159 }
160 }
161
162 return TypeHandle::none();
163 }
164
165
166 /**
167 * Removes any subtree definition previously set up via define_subtree(), in
168 * preparation for rebuilding the subtree data.
169 */
170 void TypeRegistryNode::
171 clear_subtree() {
172 _inherit = Inherit();
173 _top_inheritance.clear();
174 _visit_count = 0;
175 }
176
177 /**
178 * Indicates that this TypeRegistryNode is the top of a subtree within the
179 * inheritance graph (typically, this indicates a multiple-inheritance node).
180 * Builds all the subtree_mask etc. flags for nodes at this level and below.
181 */
182 void TypeRegistryNode::
183 define_subtree() {
184 // cerr << "Building subtree for " << _name << ", top inheritance is:\n";
185
186 /*
187 TopInheritance::const_iterator ti;
188 for (ti = _top_inheritance.begin(); ti != _top_inheritance.end(); ++ti) {
189 const Inherit &t = (*ti);
190 cerr << " from " << t._top->_name << " via "
191 << hex << t._bits << " / " << t._mask << dec << "\n";
192 }
193 */
194
195 r_build_subtrees(this, 0, 0);
196 }
197
198 /**
199 * Recursively builds up all the subtree cache information for this node and
200 * the ones below. This information is used to quickly determine class
201 * inheritance.
202 */
203 void TypeRegistryNode::
204 r_build_subtrees(TypeRegistryNode *top, int bit_count,
205 TypeRegistryNode::SubtreeMaskType bits) {
206 // The idea with these bits is to optimize the common case of a single-
207 // inheritance graph (that is, an inheritance tree), or a single-inheritance
208 // subgraph of the full multiple-inheritance graph (i.e. a subtree of the
209 // inheritance graph).
210
211 /*
212 * When we have just single inheritance, we can define a unique number for
213 * each node in the inheritance tree that allows us to immediately determine
214 * the inheritance relationship between any two nodes in the tree. We choose
215 * a number such that for a given node whose number has n bits, each child
216 * node has m + n bits where the low-order n bits are the same as the parent
217 * node's bits, and the high-order m bits are unique among each sibling. The
218 * node at the top of the tree has zero bits.
219 */
220
221 // That way, we can simply compare bitmasks to determine if class A inherits
222 // from class B. If the low-order bits are the same, they have some
223 // ancestry in common. The highest-order bit that still matches corresponds
224 // to the lowest node in the tree that they have in common; i.e. the node
225 // from which they both inherit.
226
227 // To put it more formally, let count(A) be the number of bits in A's
228 // number, and count(B) be the number of bits in B's number. A inherits
229 // from B if and only if count(B) <= count(A), and the lower count(B) bits
230 // of A's number are the same as those in B's number.
231
232 // This algorithm breaks down in the presence of multiple inheritance, since
233 // we can't make up a single number for each node any more. We still take
234 // advantage of the algorithm by considering each single-inheritance
235 // subgraph separately.
236
237 // To handle multiple inheritance, we reset the numbers to zero every time
238 // we come across a multiple-inheritance node (this begins a new subtree).
239 // There are relatively few of these "subtree top" nodes, and we record the
240 // explicit inheritance of each one from all of its ancestor "subtree top"
241 // nodes within the node itself.
242
243 if (top != this && _parent_classes.size() != 1) {
244 assert(!_parent_classes.empty());
245
246 // This class multiply inherits; it therefore begins a new subtree.
247
248 // Copy in the inheritance relations from our parent subtree tops.
249 _top_inheritance.insert(_top_inheritance.end(),
250 top->_top_inheritance.begin(),
251 top->_top_inheritance.end());
252 _top_inheritance.push_back(Inherit(top, bit_count, bits));
253
254 _visit_count++;
255 if (_visit_count == (int)_parent_classes.size()) {
256 // This is the last time we'll visit this node, so continue the
257 // recursion now.
258 assert(_inherit._top == nullptr);
259 sort(_top_inheritance.begin(), _top_inheritance.end());
260 define_subtree();
261 }
262
263 } else {
264 // This class singly inherits, so this had better be the only time this
265 // function is called on it since clear_subtree().
266 assert(_inherit._top == nullptr);
267
268 assert(bit_count < (int)(sizeof(SubtreeMaskType) * 8));
269
270 _inherit = Inherit(top, bit_count, bits);
271
272 // Now, how many more bits do we need to encode each of our children?
273 int num_children = (int)_child_classes.size();
274 int more_bits = 0;
275 int i = num_children - 1;
276 while (i > 0) {
277 more_bits++;
278 i >>= 1;
279 }
280
281 // We need at least one bit, even if there is only one child, so we can
282 // differentiate parent from child.
283 more_bits = std::max(more_bits, 1);
284
285 assert(more_bits < (int)(sizeof(SubtreeMaskType) * 8));
286
287 if (bit_count + more_bits > (int)(sizeof(SubtreeMaskType) * 8)) {
288 // Too many bits; we need to start a new subtree right here. This node
289 // becomes a subtree top node, even though it's not a multiple-
290 // inheritance node.
291 assert(top != this);
292 _top_inheritance = top->_top_inheritance;
293 _top_inheritance.push_back(_inherit);
294 sort(_top_inheritance.begin(), _top_inheritance.end());
295 _inherit = Inherit();
296 define_subtree();
297
298 } else {
299 // Still plenty of bits, so keep going.
300 for (i = 0; i < num_children; i++) {
301 TypeRegistryNode *child = _child_classes[i];
302 SubtreeMaskType next_bits = ((SubtreeMaskType)i << bit_count);
303
304 child->r_build_subtrees(top, bit_count + more_bits,
305 bits | next_bits);
306 }
307 }
308 }
309 }
310
311 /**
312 * Recurses through the parent nodes to find the best Python type object to
313 * represent objects of this type.
314 */
315 PyObject *TypeRegistryNode::
316 r_get_python_type() const {
317 Classes::const_iterator ni;
318 for (ni = _parent_classes.begin(); ni != _parent_classes.end(); ++ni) {
319 const TypeRegistryNode *parent = *ni;
320 if (parent->_python_type != nullptr) {
321 return parent->_python_type;
322
323 } else if (!parent->_parent_classes.empty()) {
324 PyObject *py_type = parent->r_get_python_type();
325 if (py_type != nullptr) {
326 return py_type;
327 }
328 }
329 }
330
331 return nullptr;
332 }
333
334 /**
335 * A recursive function to double-check the result of is_derived_from(). This
336 * is the slow, examine-the-whole-graph approach, as opposed to the clever and
337 * optimal algorithm of is_derived_from(); it's intended to be used only for
338 * debugging said clever algorithm.
339 */
340 bool TypeRegistryNode::
341 check_derived_from(const TypeRegistryNode *child,
342 const TypeRegistryNode *base) {
343 if (child == base) {
344 return true;
345 }
346
347 Classes::const_iterator ni;
348 for (ni = child->_parent_classes.begin();
349 ni != child->_parent_classes.end();
350 ++ni) {
351 if (check_derived_from(*ni, base)) {
352 return true;
353 }
354 }
355
356 return false;
357 }
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
TypeRegistryNode
This is a single entry in the TypeRegistry.
Definition: typeRegistryNode.h:30
TypeRegistryNode::is_derived_from
static bool is_derived_from(const TypeRegistryNode *child, const TypeRegistryNode *base)
Returns true if the child RegistryNode represents a class that inherits directly or indirectly from t...
Definition: typeRegistryNode.cxx:37
TypeRegistryNode::clear_subtree
void clear_subtree()
Removes any subtree definition previously set up via define_subtree(), in preparation for rebuilding ...
Definition: typeRegistryNode.cxx:171
TypeRegistryNode::get_parent_towards
static TypeHandle get_parent_towards(const TypeRegistryNode *child, const TypeRegistryNode *base)
Returns the first parent class of child that is a descendant of the indicated base class.
Definition: typeRegistryNode.cxx:148
TypeRegistryNode::define_subtree
void define_subtree()
Indicates that this TypeRegistryNode is the top of a subtree within the inheritance graph (typically,...
Definition: typeRegistryNode.cxx:183
typeRegistryNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.