testing parent-child relations using only id's

[Suzanne Vogel]

Hi,

I've been trying to write a function to test whether one class is
derived from another class. I am given only id's of the two classes.
Therefore, direct use of template methods is not an option.

Let's call the id of a class "cid" (for "class id").

The function signature should look like this:
******************************************
bool isDerivedFrom(cid child, cid parent);
******************************************

I see two basic options:
(1) Test whether we can typecast from an instance of the child class to
an instance of the parent class. If the typecast fails (by returning
NULL or throwing an exception), then we know that the child is *not*
derived from the parent. eg,
(a) Use dynamic_cast<> (somehow), since it throws an exception if
you try to cast to a non-parent class.
(2) Manually (as preprocessing) build a tree structure of id's that
parallels the actual class hierarchy, to examine later during runtime.

I would *much* prefer option#1, since it is more extensible. However, it
is difficult to figure out how, since it requires templates under the
hood, and these must be abstracted away to cid's in the final function
signature. That is why I am writing to this newsgroup.

Perhaps under the hood, we can use dynamic_cast<> in a helper function:

template<class TChild, class TParent>
bool isDerivedFrom()
{
TChild* child = new TChild();
try
{ dynamic_cast<TParent*>(child);
}
catch(exception&) { return false; }

return true;
}

************************************************************************************
How can I get the 'isDerivedFrom(cid child, cid parent)' function to
call this templated version appropriately?
************************************************************************************

Here are the utilities that I have to work with:
(1) A generic IObj superclass, as parent to all classes in the system.
Each subclass has an associated cid and implements a virtual getter
function for it:
const cid IObj::getCID(); //get the cid for this class
(2) A mapping from cid's to create functions which return an instance of
the specified class, as an IObj* pointer:
IObj* getNewObj(cid c);
(3) (probably not useful in this case) A mapping from cid's to strings
representing class names:
string& getClassName(cid c);

Here are some problems I discovered in my implementation attempts, which
we need to be aware of:
(1) Casting from IObj* always fails via dynamic_cast<> (since IObj is
parent to every class, and dynamic_cast<> can only cast from child classes).
(2) Casting from void* always succeeds via C-cast (since it is totally
non-typesafe) and cannot be done at all via dynamic_cast<>.

For instance, I tried this, but it always fails due to #1:

template<class TParent>
bool isDerivedFrom(cid child)
{
IObj* childObj = getNewObj(child);
try
{ dynamic_cast<TParent*>(childObj); //always fails, since childObj
is a ptr to IObj, *not* a ptr to whatever its ultimate derived type is
}
catch(exception&) { return false; }

return true;
}

The real magic would be to use ***MACROS***, to temporarily forgo uses
of IObj.

************************************************************************************
How can I implement the macro(s) "MACRO_GET_CLASS_NAME" and/or
"MACRO_GET_CHILD_OBJ" below?
************************************************************************************

MAGIC #1. (How can I implement the macros here?)

bool isDerivedFrom(cid child, cid parent)
{
try
{
dynamic_cast<MACRO_GET_CLASS_NAME(parent)>(MACRO_GET_CHILD_OBJ(child));
}
catch(exception&) { return false; }

return true;
}

MAGIC #2. (How can I implement the macro here?)

template<class T>
class WrapperClass
{
static bool isDerivedFrom(cid child) // this func ptr can be stored
*non-templated* in a map of (cid, static funcs), so it's useful
{
try
{ dynamic_cast<T>(MACRO_GET_CHILD_OBJ(child));
}
catch(exception&) { return false; }

return true;
}
};

I tried the following, but attempting to use them in "MAGIC #1" and
"MAGIC#2" did not compile. I also *hate* them because they require
exhaustively listing class id's,

which is not very extensible (eg, if someone else wants to add classes
to my program).

#define MACRO_GET_CLASS_NAME(id) ( \
id == kCID_Foo ? Foo \
: id == kCID_Bar ? Bar \
: NILL )


#define MACRO_GET_CHILD_OBJ(id) ( \
( id == kCID_Foo ? new Foo() \
: id == kCID_Bar ? new Bar() \
: NULL ) )

(Please ignore the memory leaks resulting from using "new" without using
"delete" here. I had a solution to prevent that, but it's not worth
cluttering my questions here by presenting it. )

Aaargh! Where's a hack when you need one? :-( I'm about to hack out my
brains.

Thanks for any suggestions.

Suzanne

 

[Jeff Schwab]

Hi,

I've been trying to write a function to test whether one class is
derived from another class. I am given only id's of the two classes.

What do you mean by "id's?" At first I thought you meant the type_info
objects returned by the typeid operator, but after reading below, I
guess you mean integer constants.

Therefore, direct use of template methods is not an option.

Let's call the id of a class "cid" (for "class id").

The function signature should look like this:
******************************************
bool isDerivedFrom(cid child, cid parent);
******************************************

I see two basic options:
(1) Test whether we can typecast from an instance of the child class to
an instance of the parent class. If the typecast fails (by returning
NULL or throwing an exception), then we know that the child is *not*
derived from the parent. eg,
(a) Use dynamic_cast<> (somehow), since it throws an exception if
you try to cast to a non-parent class.
(2) Manually (as preprocessing) build a tree structure of id's that
parallels the actual class hierarchy, to examine later during runtime.

Why does that need to be done as preprocessing? Anyway, I think such a
"tree structure" is what you need. TC++PL has a similar example (p.
416) using a std::map, with class names as the keys.

I would *much* prefer option#1, since it is more extensible. However, it
is difficult to figure out how, since it requires templates under the
hood,

It does?

and these must be abstracted away to cid's in the final function
signature. That is why I am writing to this newsgroup.

Perhaps under the hood, we can use dynamic_cast<> in a helper function:

template<class TChild, class TParent>
bool isDerivedFrom()
{
TChild* child = new TChild();
try
{ dynamic_cast<TParent*>(child);

That cast will never throw. dynamic_cast only throws when you try to
cast to a reference; if a cast to a pointer type fails, dynamic_cast
just returns 0. Anyway, no cast is needed in this situation; a pointer
to a child class always can be assigned to a pointer to any of the
child's public base classes. In your example, if TChild does *not* have
TParent as a public base, you'll get a compile-time error.

}
catch(exception&) { return false; }

Why are you trying to catch a temporary by non-const reference?

return true;
}

************************************************************************************

How can I get the 'isDerivedFrom(cid child, cid parent)' function to
call this templated version appropriately?
************************************************************************************


Here are the utilities that I have to work with:
(1) A generic IObj superclass, as parent to all classes in the system.
Each subclass has an associated cid and implements a virtual getter
function for it:
const cid IObj::getCID(); //get the cid for this class
(2) A mapping from cid's to create functions which return an instance of
the specified class, as an IObj* pointer:
IObj* getNewObj(cid c);
(3) (probably not useful in this case) A mapping from cid's to strings
representing class names:
string& getClassName(cid c);
Here are some problems I discovered in my implementation attempts, which
we need to be aware of:
(1) Casting from IObj* always fails via dynamic_cast<> (since IObj is
parent to every class, and dynamic_cast<> can only cast from child
classes).

I think you've got it backwards: dynamic_cast is used to cast from
parent classes to their children.

(2) Casting from void* always succeeds via C-cast (since it is totally
non-typesafe) and cannot be done at all via dynamic_cast<>.

For instance, I tried this, but it always fails due to #1:

template<class TParent>
bool isDerivedFrom(cid child)
{
IObj* childObj = getNewObj(child);
try
{ dynamic_cast<TParent*>(childObj); //always fails, since childObj is
a ptr to IObj, *not* a ptr to whatever its ultimate derived type is
}
catch(exception&) { return false; }

return true;
}

The real magic would be to use ***MACROS***, to temporarily forgo uses
of IObj.

If you can't write the code by hand, what makes you think the
preprocessor can? Repeat after me: screw macros... screw macros...

Aaargh! Where's a hack when you need one? :-( I'm about to hack out my
brains.

I know how you feel. I'm not sure you need a "hack" just yet, though.

Try creating a bunch of class templates, one for CID, that defines the
exact type of the corresponding class. Then, use a dynamic_cast as a
"blood test" to figure out whether "parent" really is the daddy. In
fact, you can just return the result of the dynamic cast.

Good luck,
Jeff

Btw, if that all sounds like gibberish, say the word.

 

[Jeff Schwab]

Try creating a bunch of class templates, one for each CID to define the
exact type of the corresponding class. Then, use a dynamic_cast as a
"blood test" to figure out whether "parent" really is the daddy. In
fact, you can just return the result of the dynamic cast.

Just realized this will only work if the CID's with which your function
is called are known at compile time. Do you know whether this is the
case? Do you know exactly how the function will be called?

Thanks,
Jeff

 

[Jeff Schwab]

Just realized this will only work if the CID's with which your function
is called are known at compile time. Do you know whether this is the
case? Do you know exactly how the function will be called?

Oh, and one more thing...

Are the CID's consecutive? If so, there's a straightforward, run-time
approach that will work in constant time and requires no templates.
Create an array of pointers to objects of abstract class "Comparator,"
or some such name. For each class with a CID, derive a class from both
Comparator and the class with the CID, and add it to the array at an
index corresponding to the CID. Your function can use the CID's as
indices into the array, and call methods of the Comparator-derived
objects. Inside those methods, the exact type of each object will be known.

Better yet, if you know the whole hierarchy ahead of time, you could
just build a big table of bool's. Even if the CID's aren't consecutive,
you could build a map with std:air< CID, CID > as keys and bool's as
values.

 

[Martin Eisenberg]

Hi,

Better yet, if you know the whole hierarchy ahead of time, you
could just build a big table of bool's. Even if the CID's
aren't consecutive, you could build a map with std:air< CID,
CID > as keys and bool's as values.

How does that compare to a multimap<CID, CID> where the presence of a
particular ID pair would tell what your bool does?


Martin

 

[Jeff Schwab]

Hi,

Jeff Schwab wrote:




How does that compare to a multimap<CID, CID> where the presence of a
particular ID pair would tell what your bool does?


Martin

Since the keys are unique, I don't think a multimap makes sense here.
On the other hand, your idea of testing for the very presence of keys
(rather than mapping them to boolean values) is a good one, and will
have a smaller footprint in memory. Instead of a std::map, a std::set<
std:air< CID, CID > > probably makes the most sense.

-Jeff

 

[Suzanne Vogel]

What do you mean by "id's?" At first I thought you meant the type_info
objects returned by the typeid operator, but after reading below, I
guess you mean integer constants.

Yes, integer constants.

Why does that need to be done as preprocessing? Anyway, I think such a
"tree structure" is what you need.

Yes, I decided on (2). :-( Here's how:

Register classes as (cid, set<cid>) pairs at the beginning of the
program, where set<cid> represents all the direct parents of cid. After
registering all classes, "preprocess" (okay, sorry: misuse of
terminology) by transforming into (cid, set<cid>) pairs, where set<cid>
represents *all* predecessors (parents, grandparents, great-,...) of
cid. Then, start the main program loop which uses this inheritance
structure. If class A is derived from class B, then the cid of A has a
set<cid> which contains the cid of B.

It works. I could've done it before, but I so wanted to use

It does?


That cast will never throw.

It does in my test program. It works.

dynamic_cast only throws when you try to
cast to a reference;

Or to a pointer.

if a cast to a pointer type fails, dynamic_cast
just returns 0.

No, it throws an exception.

Anyway, no cast is needed in this situation; a pointer
to a child class always can be assigned to a pointer to any of the
child's public base classes.

I know, but I want to *test* whether TChild is *truely* a child of
TParent. I don't know that it is. I know that in some situations it
won't be, and the cast will fail. (And it does fail.)

In your example, if TChild does *not* have
TParent as a public base, you'll get a compile-time error.


Why are you trying to catch a temporary by non-const reference?

I don't care about the exception itself. All I care is that one was raised.

I think you've got it backwards: dynamic_cast is used to cast from
parent classes to their children.

No, I tried it again: dynamic_cast<> casts child to parent. Which makes
sense, since parents are smaller than children, and you'd certainly want
to cast to something smaller than yourself so as not to exceed memory
allocation.

If you can't write the code by hand, what makes you think the
preprocessor can? Repeat after me: screw macros... screw macros...

Macros are beautiful. I like macros and cheese. Okay, macros don't
work here.

I know how you feel. I'm not sure you need a "hack" just yet, though.

Thanks for your suggestions. I dehackified my solution. Boring old

Try creating a bunch of class templates, one for CID, that defines the
exact type of the corresponding class. Then, use a dynamic_cast as a
"blood test" to figure out whether "parent" really is the daddy. In
fact, you can just return the result of the dynamic cast.

I thought about that... Wasn't exactly sure what it meant, didn't want
to create one class corresponding to each class in my program...
Realized that it was just beating around the bush and not solving the

Good luck,

Jeff

Btw, if that all sounds like gibberish, say the word.

Nah. Thanks.

Suzanne

 

[Suzanne Vogel]

Better yet, if you know the whole hierarchy ahead of time, you

How does that compare to a multimap<CID, CID> where the presence of a
particular ID pair would tell what your bool does?

That's kinda what I decided on. I'm using hashmap<cid, set<cid> >, where
cid represents the child and set<cid> represents all its descendents. I
figured it saves space over the map<pair<cid,cid>, bool> idea suggested
above.

(I've never used multimap before. Thanks for the tip.)

Suzanne

 

[Martin Eisenberg]

Since the keys are unique, I don't think a multimap makes sense

It turns out that my notion of retrieval from the multiset was wrong.

here. On the other hand, your idea of testing for the very
presence of keys (rather than mapping them to boolean values) is
a good one, and will have a smaller footprint in memory.
Instead of a std::map, a std::set< std:air< CID, CID > >
probably makes the most sense.

I like that the set of pairs is just the definition of a relation.
It needs only one lookup where Suzanne needs two, but in a larger
set. Would that noticeably affect speed? I also tried to figure out
which would be larger, but the results were nonsensical.


Martin

 

[Jeff Schwab]

Jeff Schwab wrote:




It turns out that my notion of retrieval from the multiset was wrong.



I like that the set of pairs is just the definition of a relation.
It needs only one lookup where Suzanne needs two, but in a larger
set. Would that noticeably affect speed? I also tried to figure out
which would be larger, but the results were nonsensical.


Martin

Each set carries some overhead. But creating a separate set for each
CID, the overhead has been multiplied by the number of CID's. That's
one reason I prefer the single-set approach. I don't like the added
complication of having two separate containers, either. Both approaches
have logarithmic complexity; which is faster probably depends on the
number of CID's present. A straight table lookup would be faster and
more compact than either of these approaches, if the difference between
the highest and lowest CID's isn't too big.

-Jeff

 

[Jeff Schwab]

Yeah, it sounds like you've got it under control, Suzanne. You go right
ahead waiting for exceptions from dynamic_cast's of pointer types, and
trying to catch those exceptions by non-const reference. Keep on using
dynamic_cast to go from child* to parent*, too; it adds such local
flavor to your code! Oh, and you're absolutely right about macros.
Aren't you sick of these hippies whining about type safety? Ignore
those enviro-nuts who keep screaming about pollution of the global
namespace, whatever that is. Keep hope alive, Suzanne, and keep chasing
that rainbow!

-Jeff

 

[Jeff Schwab]

Yeah, it sounds like you've got it under control, Suzanne. You go right
ahead waiting for exceptions from dynamic_cast's of pointer types, and
trying to catch those exceptions by non-const reference. Keep on using
dynamic_cast to go from child* to parent*, too; it adds such local
flavor to your code! Oh, and you're absolutely right about macros.
Aren't you sick of these hippies whining about type safety? Ignore
those enviro-nuts who keep screaming about pollution of the global
namespace, whatever that is. Keep hope alive, Suzanne, and keep chasing
that rainbow!

-Jeff

Oh, and by the way, dynamic_cast is not "templated," whatever that
means. Casts are built into the language; they just look like templates
to make them easier to read and to parse.

 

[Suzanne Vogel]

Jeff,

Thanks for your help. No need to be sarcastic. This is a forum where
those who ware *confused*, like I am somewhat, go to ask for help. I've
given help to people, too. Geez. If you want to flame people, visit an
obnoxious chatroom. I don't care how much knowledge you have if you're
not civil.

Yeah, it sounds like you've got it under control, Suzanne. You go right
ahead waiting for exceptions from dynamic_cast's of pointer types

Well, this works. And exceptions are *necessary*: Without them, the
program crashes.

#include <iostream>
//#include <windows.h>

//-------------------------------------------

#define COUT std::cout
#define OSTREAM std:stream

//-------------------------------------------

class A {
public:
virtual ~A() {}
};

class B : public A {
public:
virtual ~B() {}
};

class C : public B {
public:
virtual ~C() {}
};

class D {
public:
virtual ~D() {}
};

//-------------------------------------------

template<class TChild, class TParent>
static bool isDerivedFrom()
{
bool result = true;
TChild* obj = new TChild();

try {
dynamic_cast<TParent*>(obj);
} catch(exception&) { result = false;}

// if (!dynamic_cast<TParent*>(obj)) // CRASH
// result = false;

delete obj;
return result;
}

//-------------------------------------------

int main(int argc, char** argv)
{
COUT << isDerivedFrom<B,A>() << "\n"; //true
COUT << isDerivedFrom<C,A>() << "\n"; //true
COUT << isDerivedFrom<C,B>() << "\n"; //true

COUT << isDerivedFrom<A,B>() << "\n"; //false
COUT << isDerivedFrom<A,C>() << "\n"; //false
COUT << isDerivedFrom<B,C>() << "\n"; //false

COUT << isDerivedFrom<A,D>() << "\n"; //false
COUT << isDerivedFrom<D,A>() << "\n"; //false

int x; std::cin >> x;
}

, and

trying to catch those exceptions by non-const reference.

Seriously now:
Why should I be concerned about whether exceptions are non-const?

I don't care about the exceptions *themselves*; I only care that they're
thrown. Which they are.

Keep on using
dynamic_cast to go from child* to parent*, too; it adds such local
flavor to your code! Oh, and you're absolutely right about macros.

You know, I was kidding a bit about the wonders of macros. They're good
sometimes and bad sometimes. Good: Changing syntax (eg, from
Ogre::Root::getSingletonPtr()->startRendering() to
ROOT->startRendering()), using __LINE__ and __FILE__ for debugging (to
know what line & file you're on), redefining operator new (as in Ogre).
Yep, I was inspired by Ogre: ogre.sourceforge.net. Those guys rock. You
should try to flame in their forum; I'll bet you'd get stomped on.

Aren't you sick of these hippies whining about type safety? Ignore
those enviro-nuts who keep screaming about pollution of the global
namespace, whatever that is.

Okay. I listen to nuts who scream about pollution of the typing space.
Macros keep things short.

Keep hope alive, Suzanne, and keep chasing
that rainbow!

-Jeff

Suzanne

 

[Ron Natalie]

Jeff,

Thanks for your help. No need to be sarcastic. This is a forum where
those who ware *confused*, like I am somewhat, go to ask for help.

You need to tone down the arrogance. People try to help, and you are rude
to them and that's what causes them to be sarcastic.

Well, this works. And exceptions are *necessary*: Without them, the
program crashes.

Something is wrong with your compiler. The dynamic_cast of pointers shouldn't
ever throw. I suspect that you are are using VC++ and neglected to turn on the
/GR flag (RTTI). VC++ does not produce proper code without this in the case
where you are dynamic_casting to something other than a public base class.
Whenl VC++ detects that RTTI was disabled and it was needed (for things like
dynamic cast) it throws one of it's own exceptions called __non_rtti_object.

Did you actually check to see what the exception was?

Seriously now:
Why should I be concerned about whether exceptions are non-const?

You do not need to be. Jeff is confused. The temporary copy of the exception
is not an rvalue and can be bound to non-const reference. It also is guaranteed
to persist until the end of the handler.

I don't care about the exceptions *themselves*; I only care that they're
thrown. Which they are.

Well, I suspect you ought to be concerned. Because if my hunch is rigtht,
if you move try more than your trivial case you may get exceptions for classes
that your function really wants to return true for.

 

[Jeff Schwab]

Sorry for the reply. It's frustrating to see other folks make some of
the same mistakes I have. In particular, I've found that it is usually
a bad idea to assume something is guaranteed to work a particular way
just because it does in one (or more than one) compiler. You may find
it useful to find a good book that explains the reason behind items like
dynamic_cast, so you'll know how they were meant to be used. Do you
have a good book on C++? If not, you may want to read the recent thread
in alt.comp.lang.learn.c-c++ with the subject "Best book on learning C++?"

You do not need to be. Jeff is confused. The temporary copy of the exception
is not an rvalue and can be bound to non-const reference. It also is guaranteed
to persist until the end of the handler.

Thanks for correcting me; that's interesting. This seems to extend the
life of a temporary far beyond what I would have expected. For example,
compiling this program with GCC:


#include <iostream>

struct X {
X( ) { std::cerr << "default\n"; }
X( X const& ) { std::cerr << "copy\n"; }
};

void f( X& x ) { std::cerr << "f\n"; }

int main( ) try {
// f( X( ) ); // Would cause compile-time error.
throw X( );
}
catch( X& x ) {
f( x ); // Fine!
}

The output is:
default
f

I take this to mean that the X did not have to be copied into any
persistent memory; rather, the original, temporary X was caught by
reference. Why is it okay for the exception handler to receive its
argument this way, but not the function call?

Thanks,
Jeff

 

[Ron Natalie]

I take this to mean that the X did not have to be copied into any
persistent memory; rather, the original, temporary X was caught by
reference. Why is it okay for the exception handler to receive its
argument this way, but not the function call?

The value you throw is copied into some storage in an implementation
defined location. It's guaranteed to exist for the duration of the handlers.
There is no implicit copy involved in initializing function arguments.

On the other hand, the language specifically allows the compiler to not
make a copy (for example, if you really did catch a const refererence
this is a strong possibility) if the behavior is the same as if it had made
the copy (other than the non-invocation of the copy consturctor).

-Ron

 

[Jeff Schwab]

The value you throw is copied into some storage in an implementation
defined location. It's guaranteed to exist for the duration of the handlers.
There is no implicit copy involved in initializing function arguments.

On the other hand, the language specifically allows the compiler to not
make a copy (for example, if you really did catch a const refererence
this is a strong possibility) if the behavior is the same as if it had made
the copy (other than the non-invocation of the copy consturctor).

-Ron

Thanks for explaining. One more question, though; in this example:

#include <iostream>

struct X {
X( ) { print_this( ); }
void print_this( ) const { std::cerr << this << '\n'; }
};

int main( )
try { throw X( ); }
catch( X& x ) { x.print_this( ); }

Will the output of the two calls to print_this always be the same?

Thanks again,
Jeff