type_info, vtable

[sks_cpp]

What is a type_info function, more particularly, what is a type_info node?
Are these related to the vtable by any means?
I have seen linker errors such as:
"undefined reference to SomeClass type_info node" or
"undefined reference to SomeClass type_info function"

What does that really mean? What is the linker looking for?

Thanks.

 

[Ivan Vecerina]

| What is a type_info function, more particularly, what is a type_info node?
| Are these related to the vtable by any means?

Somewhat. In several implementations, the vtable stores the address of
the type_info data structure.
This data structure is used to implement Run-Time Type Identification
(RTTI),
a feature which is required for exception handling, dynamic_cast calls,
and the implementation of the typeid operator (see header <typeinfo>).

| I have seen linker errors such as:
| "undefined reference to SomeClass type_info node" or
| "undefined reference to SomeClass type_info function"

Some C++ compiler implementations allow to enable/disable support
for RTTI. You probably need to enable it for some files...


hth

 

[Rolf Magnus]

This data structure is used to implement Run-Time Type Identification
(RTTI), a feature which is required for exception handling,

RTTI isn't need for exception handling, neither would it be sufficient.

 

[Ivan Vecerina]

| Ivan Vecerina wrote:
|
| > This data structure is used to implement Run-Time Type Identification
| > (RTTI), a feature which is required for exception handling,
|
| RTTI isn't need for exception handling, neither would it be sufficient.

I did not claim it was sufficient.

But RTTI is needed to match catch handlers with exceptions.
Consider:

#include <vector>
#include <string>
#include <iostream>
#include <exception>
int main()
{
try {
std::vector<std::string> tooBig(1UL<<31,"just some string");
}
catch(std::exception& x) {
std::cerr << "Failure: "<<x.what()<<std::endl;
}
}

How would the C++ run-time handle a failure of this memory allocation
without RTTI?


Regards,
Ivan

 

[Alf P. Steinbach]

Consider:

#include <vector>
#include <string>
#include <iostream>
#include <exception>
int main()
{
try {
std::vector<std::string> tooBig(1UL<<31,"just some string");
}
catch(std::exception& x) {

Preferably use

catch( std::exception const& x )

std::cerr << "Failure: "<<x.what()<<std::endl;
}
}

How would the C++ run-time handle a failure of this memory allocation
without RTTI?

The actual types are not needed at run-time, only the compatibility
matrix of catches and throws.

That abstract matrix can be optimized in umpteen ways.

One way, but not the only way, is to use RTTI.

 

[Alf P. Steinbach]

| On Tue, 19 Aug 2003 15:29:37 +0200, "Ivan Vecerina" <[email protected]>
wrote:
| > try {
| > std::vector<std::string> tooBig(1UL<<31,"just some string");
| > }
| > catch(std::exception& x) {
|
| Preferably use
|
| catch( std::exception const& x )
Agreed.

| > std::cerr << "Failure: "<<x.what()<<std::endl;
| > }
| > }
| >
| >How would the C++ run-time handle a failure of this memory allocation
| >without RTTI?
|
| The actual types are not needed at run-time, only the compatibility
| matrix of catches and throws.
|
| That abstract matrix can be optimized in umpteen ways.
|
| One way, but not the only way, is to use RTTI.

Actually, the exact same thing can be said of dynamic_cast:
you only need a compatibility matrix of source and destination types.

I see where the confusion stems from now.

No, dynamic cast is a very different. With 'throw' the compiler knows
the exact type of the argument. With 'dynamic_cast' the argument can
be a pointer to an object that according to the standard must have its
dynamic type checked (a pointer to 'throw' is not checked for dyntype).

Clearly, Exception Handling does require a form of run-time type
identification (albeit this RTTI does not formally need to
rely on a data structure known to the linker as 'type_info').
Nope.




Let's just put things in the context of the OP, who was requesting
information on why his linker reported missing 'type_info' nodes.
I explained which language features may "require" them, and that
enabling RTTI is probably the way to have them generated.

Was this incorrect?

That I don't know...

 

[Risto Lankinen]

The actual types are not needed at run-time, only the compatibility
matrix of catches and throws.

That abstract matrix can be optimized in umpteen ways.

One way, but not the only way, is to use RTTI.

Furthermore, exception handling uses compile-time types,
not run-time (e.g. dynamic) types. Try this example:

#include <iostream.h>

struct Base
{
virtual ~Base()
{
}
};

struct Derived : public Base
{
};

int main()
{
Base *p = new Derived;

try
{
throw *p;
}
catch( const Derived & )
{
cout << "Derived" << endl;
}
catch( const Base & )
{
cout << "Base" << endl;
}
catch( ... )
{
cout << "<unknown>" << endl;
}

delete p;

return 0;
}

This program prints "Base".

Cheers!

- Risto -

 

[Ivan Vecerina]

| On Tue, 19 Aug 2003 19:48:09 +0200, "Ivan Vecerina" <[email protected]>
wrote:
| >| >| The actual types are not needed at run-time, only the compatibility
| >| matrix of catches and throws.
| >|
| >| That abstract matrix can be optimized in umpteen ways.
| >|
| >| One way, but not the only way, is to use RTTI.
| >
| >Actually, the exact same thing can be said of dynamic_cast:
| >you only need a compatibility matrix of source and destination types.
|
| I see where the confusion stems from now.
|
| No, dynamic cast is a very different. With 'throw' the compiler knows
| the exact type of the argument.

Yes, just as when a new object is created (e.g. with the 'new' operator).

| With 'dynamic_cast' the argument can
| be a pointer to an object that according to the standard must have its
| dynamic type checked (a pointer to 'throw' is not checked for dyntype).

And when a catch clause is encountered during stack unwinding, the
dynamic type of the exception being thrown (and eventually re-thrown)
needs to be matched with the type of the catch clause.

For dynamic_cast as well, the compiler could make some static program
analysis and establish that the provided object has to be of a specific
type. The fact is, in practice, this would be too difficult.
And it would be about as difficult to pre-match try and catch clauses.

When compiling a throw clause, the catch handlers that will be on the
call stack are not known. Reciprocally, when compiling a try-catch block,
the throw statements that may be invoked are unknown. So the matching
of these two types somehow has to happen at run-time.

For dynamic_cast, RTTI involves the matching of a type identifier
which is defined during object creation (and typically stored within
the vtbl of an object, with a locally known type.
For Exception Handling, RTTI involves the matching of a type identifier
somehow defined at an unknown throw point, with the locally known
type of a catch clause (or reciprocally).
It just isn't that much different. And as far as I know (from the last
time I checked the internals of a C++ runtime core), the same kind of
type information is typically used to implement both these mechanisms.


Kind regards,
Ivan

 

[Alf P. Steinbach]

| On Tue, 19 Aug 2003 19:48:09 +0200, "Ivan Vecerina" <[email protected]>
wrote:
| >| >| The actual types are not needed at run-time, only the compatibility
| >| matrix of catches and throws.
| >|
| >| That abstract matrix can be optimized in umpteen ways.
| >|
| >| One way, but not the only way, is to use RTTI.
| >
| >Actually, the exact same thing can be said of dynamic_cast:
| >you only need a compatibility matrix of source and destination types.
|
| I see where the confusion stems from now.
|
| No, dynamic cast is a very different. With 'throw' the compiler knows
| the exact type of the argument.

Yes, just as when a new object is created (e.g. with the 'new' operator).

| With 'dynamic_cast' the argument can
| be a pointer to an object that according to the standard must have its
| dynamic type checked (a pointer to 'throw' is not checked for dyntype).

And when a catch clause is encountered during stack unwinding, the
dynamic type of the exception being thrown (and eventually re-thrown)
needs to be matched with the type of the catch clause.

At run-time there is no need for _type_ matching to determine the relevant
catch-clause, if any; only compatibility is relevant, and as mentioned the
compatibility matrix can be optimized and implemented in umpteen ways.

RTTI means "Run-Time Type Information", which isn't necessarily involved.

 

[tom_usenet]

At run-time there is no need for _type_ matching to determine the relevant
catch-clause, if any; only compatibility

Do you mean type compatibility? Or what?

is relevant, and as mentioned the

compatibility matrix can be optimized and implemented in umpteen ways.

This is true for dynamic cast too - you only need to check the
compatibility of the source and destination types. In practice, may
dynamic_cast calls can be realized using a "compatibility matrix",
since the compiler can sometimes statically determine the type of the
object. Just as with exceptions, when it can *sometimes* statically
determine the call stack associated with a particular throw.

RTTI means "Run-Time Type Information", which isn't necessarily involved.

Some processing has to be done at runtime that involves types. What do
you call it?

Tom

 

[Alf P. Steinbach]

Do you mean type compatibility? Or what?

That was further up the tread. From the programmer's point of view
it is type compatibility. But wrt. to what happens at run-time it
is throw/catch statement compatibility; no types _need_ to be
examined or compared at run-time.

is relevant, and as mentioned the

This is true for dynamic cast too - you only need to check the
compatibility of the source and destination types.

That disregards when (compile time, run time) the check wrt. type
needs to be done, which is the question debated.

In practice, may
dynamic_cast calls can be realized using a "compatibility matrix",
since the compiler can sometimes statically determine the type of the
object. Just as with exceptions, when it can *sometimes* statically
determine the call stack associated with a particular throw.


Some processing has to be done at runtime that involves types.

Nope. Unless you mean that information is used that the compiler derived
from types. Everything in the compiled program is in some way derived
from or associated with types, so that is a meaningless argument.

What do you call it?

Exception handling?

 

[Ivan Vecerina]

....

At run-time there is no need for _type_ matching to determine the relevant
catch-clause, if any; only compatibility is relevant, and as mentioned the
compatibility matrix can be optimized and implemented in umpteen ways.

Can you clarify the fundamental difference you see between the type
compatibility tests performed by calls to dynamic_cast, and the type
compatibility tests required by EH to find catch handlers ?

RTTI means "Run-Time Type Information", which isn't necessarily involved.

Given separate compilation and dynamically linked library, can you
explain how an exception thrown by one library can be matched with
a catch handler in another library without performing a run-time
test based on some type of type identifier ?

Do you know of a compiler where dynamic_cast and EH do not share a
common infrastructure for checking the compatibility of types ?

Have you heard that RTTI had been adopted by the C++ committee in
spite of Stroustrup's reservations (leads to bad coding style...),
and that one of the strong arguments in favor of RTTI's adoption
was that the underlying mechanisms where required by EH anyway ?


Sincerely,
Ivan

 

[Ivan Vecerina]

I thought I did: the former can only be performed at run-time, hence
"Run Time Type Information", because no compiler can even _in principle_
predict the dynamic type of *p in the general case. The latter, compatibility
between throw statements and catch statements, can in principle be computed
at compile time as a huge matrix. The huge matrix is not very practical so
various optimizations are used, including RTTI, but that does not make
RTTI _required_; it's just one option among many.

But again: if you assume global program analysis, dynamic_cast may also
rely on a compatibility matrix between the locations were object instances
are created, and the calls to dynamic_cast. A huge matrix which may also
be 'optimized' in various ways.
The mechanism is still the same: some source type needs to be checked
for compatibility with some destination type, and a pointer offset has
to be applied.
The only difference I see is that, for dynamic_cast, the object's type
is typically stored with the object (e.g. in the vtbl). For EH, the
thrown type needs to be stored somewhere so that it can be matched
during stack-unwinding (to be accessible to catch()-handling code).
Or reciprocally, try-catch() blocks that are on the call stack need
to somehow be identified at run-time -- as you can't always know at
compile time where a throwing function has been called from.

No. Dynamically linked libraries are not part of C++. In a C++
implementation that supports dynamically linked libraries the most
natural way would be to use some form of RTTI, but I fail to see
any proof that RTTI is required in this case (with some more constraints
imposed, e.g. current linker technology, such a proof may be possible).

The reality of C/C++ today is separate compilation and limited
support for whole program optimization. But I agree that the standard
says very little about separate compilation.
Maybe in the informative annex about C compatibility (C1.6/2):
"When comparing types in different compilation units, C++ relies on
name equivalence when C relies on structural equivalence."

....
Do you have any references for that rumour?

I have no concrete information about what these 'reservations' were.
But I remember reading about the common underlying mechanism in
several instances.
What a quick google search brings:

Bruce Eckel's Thinking in C++, 2nd ed., Volume 2, Revision 2:
About RTTI:
"When exception handling was added to C++, it required the exact type
information about objects. It became an easy next step to build access
to that information into the language."
http://nicolas.blancpain.free.fr/Documents/Cpp/onlinev2/Chapter08.html

Some random web doc:
"Why might RTTI be useful?
Input of objects (what kind is it?), OODBs, debugging
Despite Stroustrup's reservations, RTTI adopted by
ANSI/ISO committee (Borland 4.0)
Why is RTTI already implied by exception handling?
catch needs to discriminate types"
http://www.eecs.lehigh.edu/~glennb/oose/13exRTTI.doc

NB: BS actually proposed RTTI in the form of dynamic_cast:
"BS: Yes, I was the one who invented the dynamic_cast syntax to
parallel the syntax for explicitly qualified template function calls.
Together with Dmitry Lenkov from HP, I was the proposer of the
runtime type identification (RTTI) mechanisms.
RTTI is easily overused. However, ...."
http://www.research.att.com/~bs/omo_interview.html


Nothing that authoritative indeed. I don't have BS's D&E
or his other books here to look for a quote.
Maybe some committee member could help here...


Kind regards,
Ivan

 

[Alf P. Steinbach]

But again: if you assume global program analysis, dynamic_cast may also
rely on a compatibility matrix between the locations were object instances
are created, and the calls to dynamic_cast.

That's pure nonsense. After an object is created pointers to it are passed
around in an unpredictable way, and it's the pointers you cast.

Now I just saw Tom Usenet's reply with an example of what could be
unpredictable _control flow_ -- which btw. is irrelevant to RTTI.

Perhaps you're confusing stack unwinding (where information about which
throw statement has been executed is directly available) with checking
the dynamic type of *p?

I have no concrete information about what these 'reservations' were.
But I remember reading about the common underlying mechanism in
several instances.
What a quick google search brings:

Bruce Eckel's Thinking in C++, 2nd ed., Volume 2, Revision 2:
About RTTI:
"When exception handling was added to C++, it required the exact type
information about objects. It became an easy next step to build access
to that information into the language."
http://nicolas.blancpain.free.fr/Documents/Cpp/onlinev2/Chapter08.html

Don't rely on such rumors for technical or accurate information.

Some random web doc:

And don't rely on random web documents for what you only need
logic to resolve.

Nothing that authoritative indeed.

And don't rely on authority as a substitute for logic.

I don't have BS's D&E
or his other books here to look for a quote.
Maybe some committee member could help here...

Uh, again, don't rely on authority as a substitute for logic.


Hth.,

- Alf

 

[Rolf Magnus]

Furthermore, exception handling uses compile-time types,
not run-time (e.g. dynamic) types. Try this example:

#include <iostream.h>

struct Base
{
virtual ~Base()
{
}
};

struct Derived : public Base
{
};

int main()
{
Base *p = new Derived;

try
{
throw *p;
}
catch( const Derived & )
{
cout << "Derived" << endl;
}
catch( const Base & )
{
cout << "Base" << endl;
}
catch( ... )
{
cout << "<unknown>" << endl;
}

delete p;

return 0;
}

This program prints "Base".

I guess that "throw *p;" actually creates a copy of the base class part
of the object (i.e. it slices it off) and throws that. That's why a
Base is caught instead of a Derived. Try this example instead:

#include <iostream>

using namespace std;

struct Base
{
virtual ~Base()
{
}
};

struct Derived : public Base
{
};

int main()
{
Derived d;

try
{
throw d;
}
catch( const Base & b)
{
cout << "reference to Base caught" << endl;
if (typeid(b) == typeid(Derived))
cout << "but the actual class is Derived" << endl;
}
catch( ... )
{
cout << "not a base" << endl;
}

return 0;
}

 

[Rolf Magnus]

| RTTI isn't need for exception handling, neither would it be
| sufficient.

I did not claim it was sufficient.

But RTTI is needed to match catch handlers with exceptions.
Consider:

#include <vector>
#include <string>
#include <iostream>
#include <exception>
int main()
{
try {
std::vector<std::string> tooBig(1UL<<31,"just some string");
}
catch(std::exception& x) {
std::cerr << "Failure: "<<x.what()<<std::endl;
}
}

How would the C++ run-time handle a failure of this memory allocation
without RTTI?

I don't know. Maybe you should ask the gcc developers, since you can
disable RTTI and still use exceptions in g++.

 

[tom_usenet]

It seems your thinking is _very_ confused here. Am I right in assuming
that the term 'check', as used above, includes stack unwinding?

Stack unwinding cannot be done at compile time; there is no stack at
that time.

I assumed you misunderstood this. Your posts seemed to imply that you
thought that the catch associated with each throw could be resolved at
compile time, given whole program analysis.

Stack unwinding has nothing to do with RTTI.

No, of course not.

Now, I think I have the source of our misunderstanding. You seem to
think that the fact that the compiler knows the type of an object at
the throw site is somehow different from the compiler knowing the type
when it calls a constructor to create an object.

The only difference is that for exceptions, you only have one active
exception at a time (well, per thread), whereas you can have any
number of active objects at a time. The nature of the checking
required to match that global exception type against a catch block
though is identical to the checking required in a dynamic cast.

So, it seems that all you are saying is that you don't need to embed
type information in your exception objects, and I don't think anyone
has disagreed with this.

Tom

 

[Alf P. Steinbach]

I assumed you misunderstood this. Your posts seemed to imply that you
thought that the catch associated with each throw could be resolved at
compile time, given whole program analysis.


No, of course not.

Now, I think I have the source of our misunderstanding. You seem to
think that the fact that the compiler knows the type of an object at
the throw site is somehow different from the compiler knowing the type
when it calls a constructor to create an object.

Could you translate that to English?

I fail to see any difference between statically knowing the type of
an object and statically knowing the type of an object.

Furthermore, I fail to see any connection to the question of whether
RTTI is necessary for exception handling.

The only difference is that for exceptions, you only have one active
exception at a time (well, per thread), whereas you can have any
number of active objects at a time.

Heya, "Tom Usenet", I used to think that you were a rational being,
perhaps someone well-known in the C++ community. But I can't make
head or tail of this statement. Since when did active objects become
part of standard C++ (yes, I do know there are extensions)?

The nature of the checking
required to match that global exception type against a catch block
though is identical to the checking required in a dynamic cast.

That's incorrect, because one can be done at compile time, the other
not.

N'th recap: for exception handling the only necessary information is
whether any given 'throw' is compatible with any given 'catch', and that
information can be deduced at compile time; abstractly it's a boolean
matrix indexed by 'throw'-statements and 'catch'-statements; a bit more
concretely it's a matrix of stubs indexed the same way.

To be even more clear (I strive, I strive), consider what must happen
when an exception is thrown. The run-time support must first of all
determine the dynamically innermost enclosing matching 'catch'. One
way to do that is to walk the stack frames and for each frame, check
whether that frame has a compatible and enclosing 'catch'. To do each
such check it can use RTTI. Alternatively, it can simply check a compile-
time generated table that does not involve types at all, just machine
code addresses for 'throw' and 'catch' statements; no RTTI.

Having found a handler (assuming one exists), the stack must be unwound,
calling destructors of local objects. This does not involve RTTI.

Then, the thrown object (or a copy of it) must be passed to the handler.

Again, this does not or need not involve RTTI.

For a dynamic cast source/destination compatibility can in general not
be established at compile time, even _in principle_, and so run-time
type information, RTTI, is required for that, different from exception
handling.

So, it seems that all you are saying is that you don't need to embed
type information in your exception objects, and I don't think anyone
has disagreed with this.

What I'm saying is that RTTI is not necessary for exception handling.

If that parses the same as the intended meaning of the above statement,
then we're in agreement.

If not, then what does that statement mean (in clear English)?

 

[tom_usenet]

So in your view the similarity of a possible implementation of one
aspect of RTTI, one the one hand, and the requirements of exception
handling, on the other, makes RTTI necessary for exception handling?

How?

A runtime lookup, best implemented on types, is required to implement
exception handling. This is also true of dynamic_cast.

I'm not saying that dynamic_cast is used to implement exception
handling, but that the implementation of both will no doubt use common
facilities, since matching a catch block is very similar to checking a
dynamic_cast. Do you agree?

I just have to say it, because it's so appropriate: since the doll is
so similar to the person, sticking needles into the doll will harm the
person. *Sticking needle into a Tom Usenet doll*. Uh, troll?

And you think I'm trolling!?

Yeah, yeah, similarity: something happens at run-time in both cases,
hence, RTTI is necessary for exception handling.

Not just something, but something very similar happens in both cases.
I never said that RTTI is required to implement exception handling
(Ivan did at first, although he clarified that he wasn't referring to
the specific features of type_info and dynamic_cast), just that the
two involve very similar concepts, and can share a lot of
implementation.

Perhaps, if you're not just trolling.
No.


In my view, RTTI means "Run-Time Type Information":

No disagreement there.

having available

at run-time the following functionality:

- dynamic_cast
- std::typeinfo

And typeid.

How is dynamic_cast, in your view, necessary for exception handling?
Consider that we've already established that it's not necessary for
finding an exception handler.

Alternatively, how is std::typeinfo necessary for exception handling?

Alternatively, how is a mechanism that for all practical purposes make
this functionality trivial, _necessary_ for exception handling?

I was simply disagreeing with your earlier assertions that matching
throws with catches, and using dynamic_cast, are completely different
(something about compile time vs runtime that Ivan and I disagreed
with). They aren't - they are conceptually very similar, and
implementing the infrastructure for one should give you quite a lot of
the infrastructure required by the other.

Tom

 

[Ivan Vecerina]

So in your view the similarity of a possible implementation of one
aspect of RTTI, one the one hand, and the requirements of exception
handling, on the other, makes RTTI necessary for exception handling?

dynamic_cast and type matching in EH both require that instances of
types that derive from each other can be identified.
As both of these very similar mechanisms require type identification
at run time, is it unreasonable to call them both "RTTI mechanisms" ?

How is dynamic_cast, in your view, necessary for exception handling?
Consider that we've already established that it's not necessary for
finding an exception handler.

Alternatively, how is std::typeinfo necessary for exception handling?

And how is std::typeinfo necessary for dynamic_cast ?

You seem to have your very own specific definition of what RTTI is.
Somehow it seems to include dynamic_cast, but excludes the
equivalent mechanism needed to support exception handling.

Since "RTTI" is not a term formally defined in the standard,
I think it is just pointless to keep arguing.


Regards,