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