"revolutionary" custom RTTI system - article :)

Started by
8 comments, last by FxMazter 19 years, 8 months ago
Hey guys! I have gotten so much from this community that I feel it's time I contribute something back as well :) So, I've seen alot people asking about making custom rtti systems etc... And recently I wanted to do just the same, and soon I realized that I could'nt find any info on how to implement a fast one and especially one that has a very CLEAN syntax for the users. The summary of what I wanted: 1. Clean syntax! 2. Fast dynamic_cast So I ended up experimenting for about two to three weeks making different implementations of what I wanted. And this is the final one I, if I may say so, "invented". Supports: 1. Multiple inheritanse. 2. Static type checking. 3. Dynamic type checking - aka dynamic_cast, but 4 to 13 times faster. 4. MUCH cleaner syntax than the standard rtti sollutions out there :) OK. This is how the standard sollutions I have found works:

//The usual sollution of a rtti system supporting dynamic cast
class BaseClass : public support DYNAMIC_CAST {
EXPOSE_CLASS;
};
RTTI_CLASS BaseClass::RTTI_OBJECT rtti_info("BaseClass");
//Ok that one is not so bad...
//BUT how about when having templates as well? IT GETS UGLY AND UNREADABLE!

template <class T, U, V>
class Derived1: public BaseClass {
EXPOSE_CLASS;
};
template <class T, U, V>
RTTI_CLASS Derived1<T,U,V>::RTTI_OBJECT rtti_info("Derived1", BaseClass::info);



Ok, Now this is how MY sollutions would be:

class BaseClass : public custom_rtti {
};

template <class T,U,V>
class Derived1 : public BaseClass {
_SUPER<BaseClass>CLASSES_
}

template <class T,U,V>
class Derived2  : public Derived1 {
_SUPER< Derived1<T,U,V> >CLASSES_
}



Nice and clean, eh? So, are you one of the people that so wanted to use dynamic_cast in some speed critical place... but couldn't because of the impact of speed and the extra size of the virtual function table? Well, now I would say you can! :) If enough people are intrested I could write an article on it. If not, I could just post main parts of the sollution right here... C ya guys [/source]
Advertisement
Quote:IT GETS UGLY AND UNREADABLE!


As far as templates go, that's pretty tame.

Quote:and the extra size of the virtual function table


There's only one vtbl per class so it's not like there's a real size issue.

But yeah, show your stuff, I'm interested - if only from an academic point of view (arguing about code is one of my hobbies [grin]).
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Oh well, seems like noone is actually really intrested in this...

Anyway, Fruny. I'll explain the basic stuff. The implementation
is actually quite complex with a lot of compiletime calculations.


I didn't mean to sount so cocky in my previous post, I was just
so excited about writing an article and getting some response...
since it's my first time doing this :) But I just noticed
that it might sound a bit cocky :/
And since I actually "invented" this myself, I felt even more
excited about it...

Here it goes:

First off we define some classes to make a dynamic cast
possible.

The only way by figuring out which type a pointer is
pointing to is by returning an ID by a virtual function:

//This class will contain ID info about a class//later on... for now, lets keep it emptyclass RttiInfo {};//Each class that wants to support dynamic_cast//needs to derive from this class.class CustomRtti {public:	//This function will return the most "derived"	//objects class info - the ID - actually a list	//of dynamically created RttiInfo* objects.	virtual RttiInfo** GetRttiInfo() = 0;};


Ok, so now we could use it like this:

//MyBase will now support our RTTI system... //and especially our dynamic castclass MyBase : public CustomRtti {};



Ok, Lets fill the RttiInfo with some usefull information!
I decided to use an unsigned int as an ID for each class,
since it can easily be used together with templates
for some nice tricks.

class RttiInfo {	unsigned int&	m_ruiID;			//The UNIQUE id for a class	String			m_strClassName;		//The class namepublic:	RttiInfo(unsigned int& uiID, const String& strClassName) 		: m_ruiID(uiID), m_strClassName(strClassName) 	{}	//Get the ID...	inline	unsigned int GetID() { return m_ruiID; };};



Ok, we got some basic info in our RttiInfo class, which really
doesn't have to be larger than that...


Next on, we will use templates to generate UNIQUE id's which are needed
for our RttiInfo class.

//This class will just work as a counterclass Counter {public:	static unsigned int GetNextID() {		static unsigned int the_next_id = 0;		return the_next_id++;	}};//This is the class... for each parameter T a unique int value will//be generated.template <class T>class UniqueClassID {public:	//Get the unique ID!	static unsigned int& GetID() {		static unsigned int the_id = Counter::GetNextID();		return the_id;	}};


So now we will use the same template technique to generate UNIQUE RttiInfo objects!

//This is the class... for each parameter T a unique int value will//be generated.template <class T>class RttiInfoCreator {public:	//Get the RttiInfo object.	static RttiInfo& GetRttiInfo() {		//OK!, now you remember that an unsigned int was required to create a RttiInfo		//This value is later used to identify classes, so it REALLY needs to be unique		//Yep, you're right lets use our UniqueClassID class!		static RttiInfo the_rtti_info = new RttiInfo(UniqueClassID<T>::GetID(), "NO CLASS NAME");		return the_rtti_info;	}};


There you go, It's a nice start :)
Here I'll show you how to use it:

//RttiInfoCreator<MyClass>::GetRttiInfo() will ALWAYS return the same//RttiInfo, no matter where/how/when you call it.RttiInfo& MyClassInfo = RttiInfoCreator<MyClass>::GetRttiInfo();//Same object will be retrieved here:RttiInfo& MyClassInfo2 = RttiInfoCreator<MyClass>::GetRttiInfo();//Another RttiInfo:RttiInfo& MyOtherClassInfo = RttiInfoCreator<MyOtherClass>::GetRttiInfo();//etc...


Yup, It's beginning to look like something :)
So, now you have probabilly figured out how you
could use this kind of technique to retrieve the
RttiInfo object from a most derived class.

Lets look at an example of how we could do that:

//If our CustomRtti would look like this:class CustomRtti {public:	//This function will return the RttiInfo	//object from the most derived class:	virtual RttiInfo& GetRttiInfo() = 0;};//Lets make a test:class MyBaseClass : public CustomRtti {public:	//This is how it COULD look... but it's not how we	//will do it...	virtual RttiInfo& GetRttiInfo() {		return RttiInfoCreator<MyBaseClass>::GetRttiInfo();	}};//Could be used like this:CustomRtti* pSomeClass = new MyBaseClass();RttiInfo& pClassInfo = pSomeClass->GetRttiInfo();//And now check the id to know what class we got...


Ok, indeed it's beginning to look like something.
BUT, unfortunately that was the easy part figuring out :)


Now If you don't have good/excellent knowledge of templates
this part might be hard to understand. I won't be going into
every detail about the stuff I'll be talking about :(


The heart of the RTTI system are templated TYPE LISTS !
Yes, thats right. When I first got the hang of typelists
I immediately understood that this could be something
to improve custom rtti systems.

So let's take a look at what you could do with typelists:

//A typelist containing Class1, Class2, Class3typedef TypeList<Class1, TypeList<Class2, TypeList<Class3, NullClass> > > CLASS1_CLASS2_CLASS3_LIST;


Aha! what If I could use similar syntax to define what classes
I want to DERIVE from !?

Yup, that would be GREAT! :)

So here we go... having our last version of CustomRtti
we try something like this:

//Lets make a test:class MyBaseClass : public CustomRtti {	//Now here we want to define the classes	//we want to derive from! But any of you	//guys that have been working with typelists	//know that some "ugly" macros are needed,	//depending on the number of entrys in the typelist:	// TYPE_LIST_1(Class1);	// TYPE_LIST_2(Class1, Class2);	// TYPE_LIST_3(Class1, Class2, Class3);	//etc...		//So we could do like this:	typedef TYPE_LIST_1(CustomRtti) DERIVED_CLASSES_LIST;	//Now we have defined a typelist with only one entry	//namely the class MyBaseClass is derived from.	//If MyBaseClass would be derived from more than one class	//we would have to use another macro:	typedef TYPE_LIST_2(CustomRtti, SomeOtherBaseClass) DERIVED_CLASSES_LIST_2;	//you get the point right :)public:	//Aha! now we just create a RttiInfo object from the 	//first TYPE in our DERIVED_CLASSES_LIST!	// thats piece a cake!	//... well unfortunately not... you will have to use	//some templated functions.	//Look at the CreateRttiInfoFromTypeList class...	virtual RttiInfo& GetRttiInfo() {		//First read about CreateRttiInfoFromTypeList below...		//Then look at this again.		//Aha! here we use the above defined typelist DERIVED_CLASSES_LIST		//To EXTRACT the first TYPE from it and create a RttiInfo		//object from it :)		return CreateRttiInfoFromTypeList<DERIVED_CLASSES_LIST>::CreateRttiInfo();	}};//This class just encapsulates the CreateRttiInfo function//which is used to "extract" the first TYPE from the TypeList//And then create a RttiInfo from this TYPE!//Here goes the templated definition:template <class TList>class CreateRttiInfoFromTypeList {public:	//This one wont be used anyway...	inline	static RttiInfo& CreateRttiInfo();};//And here we explicitly define the class for a TypeList//So if we use CreateRttiInfoFromTypeLista<SomeClass>//with SomeClass = TypeList<....> this one will be//used://The Head is the first entry in the TypeList//And the Tail is the REST of the TypeList, which//is a TypeList that to. So we could recurse this//If we would want to by calling CreateRttiInfoFromTypeList<Tail> ...template <class Head, class Tail>class CreateRttiInfoFromTypeList<TypeList<Head,Tail> > {public:	//Create the RttiInfo object from the first entry	//in the TypeList -> the Head type.	inline	static RttiInfo& CreateRttiInfo() {		return RttiInfoCreator<Head>::GetRttiInfo();	}};



Whew... It's beginning to look more and more complicated. Told ya,
If you don't have good knowledge about templates and especially
TypeList's, then my friend you will be lost :(


Okidoki, you who have understood this probabilly see where we are
going :)

For this article I will cover one more thing.
We are NOT satisfied with having to define a typelist ourselves
each time we create a new class...
This part:

typedef TYPE_LIST_1(CustomRtti) DERIVED_CLASSES_LIST;

is NOT ACCEPTABLE we say :)

So after a couple of hours of braingymnastics we figure out this
somewhat "ugly" sollution:

template <class Class1 = NullClass, class Class2 = NullClass, class Class3 = NullClass> // you could continue here...class TypeListCreationHelper {public:	//The template parameters could look like this:	//<X,	NullClass,	NullClass>	//<X,	X,			NullClass>	//<X,	X,			X>	//We just define our typelist here...	//Just check out DerivedClassesTypeList to know what I mean :)	typedef DerivedClassesTypeList<Class1, Class2, Class3>::the_list	DERIVED_CLASSES_LIST;};//This class will encapulate the ugly TYPE_LIST_X macros we so wanted to avoid!template <class Class1, Class2, Class3>DerivedClassesTypeList {}//For each combination the template parameters could occure in TypeListCreationHelper<Class1, Class2, Class3>//we define a specialization of DerivedClassesTypeList:template <class Class1>DerivedClassesTypeList<Class1, NullClass, NullClass> {public:	typedef TYPE_LIST_1(Class1)		the_list;}template <class Class1, Class2>DerivedClassesTypeList<Class1, Class2, NullClass> {public:	typedef TYPE_LIST_1(Class1, Class2)		the_list;}template <class Class1, Class2, Class3>DerivedClassesTypeList<Class1, Class2, Class3> {public:	typedef TYPE_LIST_1(Class1, Class2, Class3)		the_list;}//etc...



Whew, just take a look at how we could define our derived classes now:


//Lets make a test:class MyBaseClass : public CustomRtti {	typedef TypeListCreationHelper<CustomRtti>::the_list	DERIVED_CLASSES_LIST;	//Oh yeh baby... now there is no need for the ugly TYPE_LIST_X(...) macros	//anymore ! :) Just beautiful :)	// another example:	// typedef TypeListCreationHelper<CustomRtti, SomeOtherBaseClass>::the_list	DERIVED_CLASSES_LIST;public:	//This is how it COULD look... but it's not how we	//will do it...	virtual RttiInfo& GetRttiInfo() {		return CreateRttiInfoFromTypeList<DERIVED_CLASSES_LIST>::CreateRttiInfo();	}};




Oh well... I think it's enough for this time. With the stuff I covered above,
you have a simple system for defining classes that can return a RttiInfo
object containing the CLASS id of the most recently derived class.

Next time I'll try to explain how to extend this into multiple inheritance,
and not just returning a SINGLE RttiInfo, but rather a LIST of RttiInfo
objects - All Derived classes for some Class.

But some of you guys prolly already have figured out how to do it already :)

I will also explain how to make all the creation of the RttiInfo list be done
during compiletime and during the static initialization of objects - that is
before the main() is reached. Hence, therefore the speed of this system.

A dynamic_cast operator will only need to iterate through a list of RttiInfo
objects to check if some Class's ID is anyone among the ones in the list...


C ya later guys!
Why reinvent the wheel, when c++ has that already?
Quote:Original post by Anonymous Poster
Why reinvent the wheel, when c++ has that already?


A fast dynamic convertibility test isn't quite reinventing the wheel. And many people do acknowledge limitations in typeid/typeinfo, so writing your own can be useful. I do have reservations as to whether a full dynamic_cast replacement is a good idea (or even feasible) though.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Well.

1. You can do this on any compiler that supports inner templates.

2. 4-13 times faster than the standard dynamic_cast.

3. Cleaner user syntax than any other similar system
I have seen out there.

4. You can decide which classes should take advantage
of rtti... not all classes like enabling RTTI in VC++

5. It's not exactly like dynamic_cast... consider this design:

//We will fake A derived class here:class BaseClass : public CustomRtti {};template <class T>class DerivedClass : public BaseClass {//We don't inherit the class T, but we still//can FAKE it... enabling us some intresting//designe features :)_SUPER<T>CLASSES_};BaseClass* pBase = new DerivedClass<Class1>();if(rtti_system::my_dynamic_cast<Class1>(pBase) != 0) {//we have tested if pBase "supports" a "faked" inherited//class...}


Consider a TYPE SAFE FACTORY INTERFACE:

class IFactoryCreator : public CustomRtti {public:	virtual void* Create() = 0;};template <class T>class CFactoryCreator : public IFactoryCreator {	//We fake inheritance from the type T	//Will be used to test if a IFactoryCreator supports a 	//specific interface...	_SUPER<T>CLASSES_public:	virtual void* Create() {		return new T;	}};class IFactory {public:	virtual bool AddCreator(ID id, IFactoryCreator* pCreator) = 0;	virtual IFactoryCreator* GetCreator(ID id) = 0;	template <class T>	T* Create(ID id) {		IFactoryCreator* pCreator = GetCreator(id);		if(rtti_system::my_dynamic_cast<T>(pCreator) != 0) {			//OK... now we can go on and create the object!			//We didnt have to CREATE the object to test if it supports			//the T interface:			return pCreator->Create();		}	}};template <class T>class CFactory {public:	virtual bool AddCreator(ID id, IFactoryCreator* pCreator) {		if(rtti_system::my_dynamic_cast<T>(pCreator) != 0) {			//The Creator is compatible with this Factory!			//So go on and add it....		}	}	virtual IFactoryCreator* GetCreator(ID id) {		//find the IFactoryCreator corresponding to the ID	}};


You see... that lets us do some quite powerful design :)

You could for example make a Factory fith Factorys.
And since everything is with INTERFACES... you can
simply plug in a new factory but STILL NOT lose
the TYPE INFORMATION!

I wouldn't exactly call that reinvent the wheel :) ?

If you have seen this feature anywhere else, please
tell me where :)

C ya. And please feel free to add responses here, that
just makes this all more exciting for me :)
Fruny, If you want to test the RTTI system I have made,
Feel free to add me on msn and I'll send you over the code
and explain how to use it.

Then you could check how it works :)

I'm sure your scepticism will be like blown away.

Just kidding :) ... no really, add me on msn and I'll show
it to you.

master_of_ice@hotmail.com

C ya
It's making my head hurt. Does it work with MI/virtual bases? Whacked out hierarchies? Is RTTI really a performance critical part of software?
Quote:Original post by fallenang3l
It's making my head hurt. Does it work with MI/virtual bases? Whacked out hierarchies? Is RTTI really a performance critical part of software?


Of some systems, it's quite possible. After all, there was a thread awhile ago where a linux kernel module design was endlessly flamed for even daring to think about trying to use virtual functions, when the designed actually was quite suited to said virtual functions.
I'm not sure what you mean with MI/virtual bases or Whacked out hierarchies ?

But as I said it's 4 -13 times faster when I did some benchmark testing on some heavy class hierarchys.

class Interface_1 {
};

class Interface_2 : public Interface_1 : public CustomRtti {
_SUPER<Interface_1>CLASSES_
};

class Interface_3 : public CustomRtti {
};

class RealClass : public Interface_3, Interface_2 {
_SUPER<Interface_3, Interface_2>CLASSES_
};


You could now do:
Interface_2* pI2 = new RealClass();
RealClass* pReal = rtti_system::my_dynamic_cast<RealClass>(pI2);
if(pReal != 0) {
//Control flow should pass through here...
}

With Some smart pointers you could even do like this, even
though Interface_1 isn't part of the RttiSystem:

Interface<Interface_1> pI1 = new RealClass();
Interface<RealClass> pReal = pI1.QueryInterface<RealClass>();
if(pReal.IsValid()) {
//Control flow should pass here...
}


The Rtti system works like this:
Each class has a defined TypeList with the desired classes
it inherits from.

1. Get the TypeList
-- 1.2 For each entry in the TypeList:
----1.3 IF(entry is derived from CustomRtti type)
----1.3 THEN Get that class's defined TypeList and start with 1.2 on it.
----1.3 ELSE Make an RttiInfo object from the type and continue with next entry...
2. Return the RttiInfo array

This topic is closed to new replies.

Advertisement