type_info, vtable

[Ivan Vecerina]

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

From what I saw on google, there seems to have been some bugs with
EH when RTTI was disabled. And it's for the best if these were
fixed.

An implementation could also offer a compile mode where dynamic_cast
is supported, but not type_info.

But yes, it would be nice if a compiler writer/maintainer could tell
us if run-time type identification in EH and dynamic_cast share
some common code...


Regards,

 

[Alf P. Steinbach]

A runtime lookup, best implemented on types

Pascal is "better" than Java. So there!

is required to implement exception handling. This is also true of
dynamic_cast.

Similarity again. Yada yada yada. Did you know, both the earthworm and
George W. are lifeforms, and even more surprising, both are (to the best
of my knowledge) based on an incredibly complex molecule called DNA?

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?

Of course not, since it's illogical.

If you replace "will no doubt" with "can", and "is very similar to" with
"has some similarity with", then yes.

And you think I'm trolling!?

Yep, I'm 99% sure now. ;-)

...
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).

As we have established, they are very different.

Matching a throw with a catch involves a stack walk; using a dynamic_cast
does not. Checking whether a given throw is compatible with a given catch
can always be done at compile time. That is not the case for a dynamic_cast.
And so on and so forth. How can this be so difficult to grasp?

You'll have to quote the statement of mine which was sufficiently
unclear about that that it could be interpreted as something else.

They aren't - they are conceptually very similar

No. See immediately above, and the thread in general. However, checking
whether a given throw is compatible with a given catch is conceptually
somewhat similar to a dynamic_cast.

But again, similarity at an abstract level between a part of A and
a part of B does not make A necessary for B.

and
implementing the infrastructure for one should give you quite a lot of
the infrastructure required by the other.

No. It can, but won't necessarily. In particular, a simple throw/catch
compatibility table, computed from compile-time symbol table information,
is presumably of little or no use in implementing dynamic_cast.

 

[Alf P. Steinbach]

dynamic_cast and type matching in EH both require that instances of
types that derive from each other can be identified.

That's correct.

As both of these very similar mechanisms require type identification
at run time,

That's incorrect.

is it unreasonable to call them both "RTTI mechanisms" ?

Yes.

 

[Ivan Vecerina]

That's incorrect. ....

Yes.

Again, what seems to define type identification for you is
the use of a type identifier associated with an object instance;
using a type identifier associated with a catch block on
the call stack is not.

This is your own definition - feel free:

 

[Alf P. Steinbach]

Again, what seems to define type identification for you is
the use of a type identifier associated with an object instance;
using a type identifier associated with a catch block on
the call stack is not.

Funny, we seem to have posted new replies at the same time...

See my other (new) reply here for what I hope is a clarification.

Of course, it may be that it will only muddle waters even more.

This is your own definition - feel free:

Wasn't that _your_ definition?

 

[tom_usenet]

The question is : what is the defining characteristic/s of RTTI?
Pure RTTI seems to be exactly equivalent to 'dynamic_downcast', like,
say, the Eiffel assignment attempt. But what about that is it that
makes it "Run Time" (which we've had such a hard time pinning down),
and what about that is it that makes it "Type Information" (ditto)?

That's a bit subtle, and I agree with Tom Usenet that that is probably
why we have not managed to agree.

As I see it:


"Run Time" --> Only _knowable_ at run time, i.e. potentially
changing over time for the same code snippet.

"Type Info" --> An _explicit representation_ of a type.


I think you all agree with the "Run Time" definition, and probably
associate "potentially changing" in the context of exception handling
with "changing catch statement" depending on how a 'throw' is reached.

The "Type Info" is a bit harder, but here's an example, namely the
'throw'/'catch' compatibility matrix revisited. This matrix is in its most
basic form indexed by 'throw' statements and 'catch' statements. But in
typical code the number of thrown types tends to be very small, a handful
or so, and likewise for the number of caught types. And so all rows
representing 'throw' statements of the same type can essentially be
collapsed into one common row, plus an external vector that maps 'throw'
statements to rows. And ditto for columns indexed by 'catch' statements.

In this optimization a single row that represents a set of 'throw'
statements of the same type is in effect an identification of that type
in the sense that there is a one-to-one mapping between the relevant
types and corresponding rows. But it is not an explicit representation,
for given the (index to) a row one cannot obtain any information about
the type except via additional otherwise unnecessary stored associations,
nor can the row be used for anything but 'catch'/'throw' compatibility
checking. And the row is not "only knowable at run-time"; it can be (and
must, in order to practically useful, be) constructed at compile time.

For columns the situation is more complex, for a column index is only
available when a stack frame with a containing 'catch' has been found.
So isn't this column index then both an explicit representation of a
type (the 'catch' type), and only knowable at run-time? Yes to the last,
but no to the first: it's not an explicit representation, it cannot be
used to determine anything about the type involved (except via additional
and otherwise unnecessary information).

In short, all that's necessary for C++ exception handling is _implicit_
type representation that cannot be used for any other purpose. And so
it's not surprising that C++ EH cannot emulate 'dynamic_cast'. Or that
the functionality of 'dynamic_cast', or basic RTTI, is not required.

The end result of this analysis-by-example is that the concept of RTTI
hinges crucially on _explicit_ type representation.

No, you've shown that exception handling *doesn't* hinge on explicit
type representation. This is also true of dynamic_cast. Here's a
rewrite of your example:

The "Type Info" is a bit harder, but here's an example, namely the
'constructor call'/'dynamic_cast' compatibility matrix revisited. This
matrix is in its most basic form indexed by 'constructor call'
statements and 'dynamic_cast' statements. In typical code the number
of created types tends to be quite large, but the number of types
dynamically casted to tends to be small. And so all rows representing
'constructor call' statements of the same type can essentially be
collapsed into one common row, plus an external vector that maps
'constructor call' statements to rows. And ditto for columns indexed
by 'dynamic_cast' statements.

In this optimization a single row that represents a set of
'constructor call' statements of the same type is in effect an
identification of that type in the sense that there is a one-to-one
mapping between the relevant types and corresponding rows. But it is
not an explicit representation, for given the (index to) a row one
cannot obtain any information about the type except via additional
otherwise unnecessary stored associations, nor can the row be used for
anything but 'dynamic_cast' compatibility checking.

For columns the situation is simple. The column index is known for a
particular 'dynamic_cast' statement at compile time. For rows the
situation is more complex. The row index is only found when the object
begin passed to the 'dynamic_cast' statement is known, and this is
only knowable in general at runtime. So isn't this row index then both
an explicit representation of a type (the 'constructor call' type),
and only knowable at run-time? Yes to the last, but no to the first:
it's not an explicit representation, it cannot be used to determine
anything about the type involved (except via additional and otherwise
unnecessary information).

In short, all that's necessary for C++ dynamic_cast is _implicit_
type representation that cannot be used for any other purpose.


Some very thinking-

circuit-activating books have been written about just that little
crucial but hard-to-pin-down difference. Hofstadter's "Gödel, Escher,
Bach" comes to mind, as well as Scott Fahlman's "NETL", not to mention
Wolfram's "A new kind of physics". It's no wonder that we find it hard
to agree on the dividing line...

Your argument is specious, since the fact that exception handling does
not require RTTI can be simply extended to an argument that
dynamic_cast doesn't require RTTI. Either your definition of RTTI is
wrong, or dynamic_cast doesn't require RTTI.

However, neither of these arguments change the fact that matching
catch blocks and performing dynamic_casts both conceptually involve
taking a type, and checking it to see whether it is derived from
another type, and performing this check at runtime.

If your position is simply that you choose not to call that RTTI, we
can agree to disagree.

Tom

 

[Buster Copley]

Dynamic_cast can't be made to work that way.

Exception handling is different. What happens when an exception is
thrown? We know what row of the matrix we need (this information is
encoded in the 'throw', not in the exception object) and we know what
stack frame we are in. We move up a frame until we reach a stack frame
with a catch clause. That gives us a column of the matrix. If the throw
and catch match according to the matrix, we stop. Otherwise we carry on.

Try to use a matrix of object creations to dynamic_casts to emulate
dynamic cast in a similar way. What happens when a constructor is
invoked? What doesn't and couldn't happen is a systematic search for a
dynamic_cast. We know at the point of construction what row of the
matrix to look at, but if we still know that at the dynamic_cast then we
have associated a row-index with each object. Since there is a one-one
correspondence between rows and types, this information can be said to
be type information.

The matrix of object creations and dynamic_casts along with the
row-index to object association could certainly be used to implement
exception handling, but the converse fails. The throw-catch matrix
cannot emulate dynamic_cast, even if extended to include all object
creations and dynamic_casts, because the row-index is not known at the
site of the dynamic_cast.

Corrections are welcome.

Regards,
Buster

 

[tom_usenet]

As we have established, they are very different.

Matching a throw with a catch involves a stack walk; using a dynamic_cast
does not. Checking whether a given throw is compatible with a given catch
can always be done at compile time. That is not the case for a dynamic_cast.

You can check, at compile time, whether any particular call to an
object constructor is compatible with any particular dynamic_cast.

And so on and so forth. How can this be so difficult to grasp?

Because it is factually incorrect! (the bit about dynamic_cast, not
the bit about exceptions).

You'll have to quote the statement of mine which was sufficiently
unclear about that that it could be interpreted as something else.

To clarify, the statements that you have made that I disagree with:

"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)."

This is inconsistent. The "dynamic type" does not need to be looked up
to perform a dynamic_cast - only an index into a matrix needs to be
computed. According to your definition, this does not count as "having
its dynamic type checked".

Here's another quote (from me and then your response):

"

What I mean is that there is no fundamental difference between the
runtime check required by dynamic_cast and the runtime check required
to select a catch block.

For dynamic cast the compiler could build up a matrix of every use of
a type in dynamic cast, and every creation of an object.

For exception handling, the compiler could build up a matrix of every
use of a type in a throw, and every use in a catch.

What's the difference?

The first is nonsense since the type of *p cannot be predicted in the
general case.
"

I disagree with this too.

Your assertion that the type of *p cannot be predicted at compile time
is true. But why do you think that leads to "the first is nonsense"?

My equivalent statement about your throw/catch matrix would be:
"The second is nonsense since the type caught cannot be predicted in
the general case."

But in fact, neither statement is nonsense.

No. See immediately above, and the thread in general. However, checking
whether a given throw is compatible with a given catch is conceptually
somewhat similar to a dynamic_cast.

But again, similarity at an abstract level between a part of A and
a part of B does not make A necessary for B.

We're agreed there, but that was never what I was disagreeing with.

No. It can, but won't necessarily. In particular, a simple throw/catch
compatibility table, computed from compile-time symbol table information,
is presumably of little or no use in implementing dynamic_cast.

On the contrary, the same matrix (with an extra column for each
dynamic_cast target type and an extra row for each created object
type) is fine for dynamic_cast compatibility checks too (ignoring
virtual inheritence for now).

Tom

 

[Alf P. Steinbach]

For columns the situation is simple. The column index is known for a
particular 'dynamic_cast' statement at compile time. For rows the
situation is more complex. The row index is only found when the object
begin passed to the 'dynamic_cast' statement is known, and this is
only knowable in general at runtime. So isn't this row index then both
an explicit representation of a type (the 'constructor call' type),
and only knowable at run-time? Yes to the last, but no to the first:
it's not an explicit representation, it cannot be used to determine
anything about the type involved (except via additional and otherwise
unnecessary information).

Just to pin down our differences, it's the "but no to the first", and
the following justification, that I don't agree with.

In my view an address of the constructor call stored in each (non-POD)
object _is_ an explicit type representation, RTTI "Type Information".

And it can easily be used to obtain information about the type, namely
via 'dynamic_cast' to various destination types -- I just note in
passing that if it were not so (which it is) it would not be a working
implementation of 'dynamic_cast'.

Your argument is specious, since the fact that exception handling does
not require RTTI can be simply extended to an argument that
dynamic_cast doesn't require RTTI. Either your definition of RTTI is
wrong, or dynamic_cast doesn't require RTTI.

Your assertion that dynamic_cast cannot be used to obtain information
about the dynamic type is incorrect, and so that argument is a fallacy.

But that does not mean that the definitions I know of RTTI are
in some sense "correct".

It does, however, mean that any definition of RTTI that doesn't
require storage of an explicit type representation is a practically
useless definition, void of meaning.

However, neither of these arguments change the fact that matching
catch blocks and performing dynamic_casts both conceptually involve
taking a type, and checking it to see whether it is derived from
another type, and performing this check at runtime.

In my considered opinion George W. requires earthworms, since they
are somewhat similar at the genetic level. Bright insight! Perhaps
he's going fishing?

If your position is simply that you choose not to call that RTTI, we
can agree to disagree.

That seems to be the case, yes.

 

[tom_usenet]

Dynamic_cast can't be made to work that way.

Exception handling is different. What happens when an exception is
thrown? We know what row of the matrix we need (this information is
encoded in the 'throw', not in the exception object) and we know what
stack frame we are in. We move up a frame until we reach a stack frame
with a catch clause. That gives us a column of the matrix. If the throw
and catch match according to the matrix, we stop. Otherwise we carry on.
Right.


Try to use a matrix of object creations to dynamic_casts to emulate
dynamic cast in a similar way. What happens when a constructor is
invoked? What doesn't and couldn't happen is a systematic search for a
dynamic_cast.

Of course not. Two options - either the row number is placed inside
the object, or the address of the object is added to a map of object
address - to row number.

We know at the point of construction what row of the

matrix to look at, but if we still know that at the dynamic_cast then we
have associated a row-index with each object. Since there is a one-one
correspondence between rows and types, this information can be said to
be type information.

There isn't necessarily such a one-to-one correspondence. If you have
one row per type, then some of the rows may be identical, which makes
the correspondance only many-to-one, strictly speaking.

The matrix of object creations and dynamic_casts along with the
row-index to object association could certainly be used to implement
exception handling, but the converse fails. The throw-catch matrix
cannot emulate dynamic_cast, even if extended to include all object
creations and dynamic_casts, because the row-index is not known at the
site of the dynamic_cast.

It is if the row index is placed inside the object (or its vtable), or
if a map of object address to row index is maintained. This was my
point, that the matrix bit that was being bandied around could also
provide the basis of a dynamic_cast implementation, just as it could
provide the basis of an exception handling implementation. This is
because the matrix is just an implementation of type compatibility,
something that is central to both dynamic_cast and throw/catch
matching.

For an exception, you have to walk the stack to find the column index.
For a dynamic_cast you have to lookup the row index for the object in
question (either inside the object, or in an object address indexed
map). There are different operations, but they are both still runtime
operations (hence my disagreement with assertions about exceptions
being compile time, and dynamic_cast being runtime).

Tom

 

[tom_usenet]

Just to pin down our differences, it's the "but no to the first", and
the following justification, that I don't agree with.

In my view an address of the constructor call stored in each (non-POD)
object _is_ an explicit type representation, RTTI "Type Information".

Why is that an explicit type representation, while your throw row
index is not? You realise what I mean by a constructor call statement?
I don't mean the address of the constructor call (which would
identifiy a type directly), I just mean the instruction address of a
jump statement to that constructor. e.g.

A a; //constructor call statement 100, say.
A b; //constructor call statement 101, say.

At runtime, this map is built up:
(a's runtime address)->100
(b's runtime address)->101

This has nothing to do with the type. e.g. In another program:

A a; //statement 100
B b; //statement 101

And it can easily be used to obtain information about the type, namely
via 'dynamic_cast' to various destination types -- I just note in
passing that if it were not so (which it is) it would not be a working
implementation of 'dynamic_cast'.

Yes, this is true. However, equivalently, catch blocks can be used to
gain information about the runtime type of exceptions:

try
{
f();
}
catch(Type1& t)
{
}
catch(Type2& t)
{
}
//etc.

In the example above, at compile time you have no information at all
about the runtime type of the exception that will come through, if any
(except that it is one that is thrown somewhere), but you can use the
catch blocks to find out its runtime type.

Your assertion that dynamic_cast cannot be used to obtain information
about the dynamic type is incorrect, and so that argument is a fallacy.

But that does not mean that the definitions I know of RTTI are
in some sense "correct".

It does, however, mean that any definition of RTTI that doesn't
require storage of an explicit type representation is a practically
useless definition, void of meaning.

Ahh, now we're getting somewhere. You now say RTTI involves storing
along with an object information relating to its dynamic type, and I
agree that that is a reasonable definition. However, note that a
identical kind of type representation has to be stored along side a
thrown exception (say its throw statement "number", its type, or
whatever strange implementation you go for).

I'm starting to think that my argument is too subtle...

Tom

 

[Alf P. Steinbach]

Why is that an explicit type representation, while your throw row
index is not?

Because the dynamic_cast information can be usefully employed by any
code it's passed to, e.g. to check whether it represents some given
type, or a type that is derived from some type, and so on. So one
difference between an explicit and an implicit representation is the
functionality available. Another difference for this particular
example is the memory consumption, O(K) versus O(n).

You realise what I mean by a constructor call statement?

Yep, but I don't think the details of representation matter much.

... catch blocks can be used to
gain information about the runtime type of exceptions:

try
{
f();
}
catch(Type1& t)
{
}
catch(Type2& t)
{
}
//etc.

In some weird sense, disregarding everything of relevance, this is
true.

But much more true: exception handling can only _lose_ explicit type
knowledge, not _gain_ more explicit knowledge than what was present
in the first place.

To perhaps better see this (or see it all, I'm beginning get exasperated),
consider a piece of code that is passed a pointer p. Via RTTI this code
can gain more explicit knowledge about the type of *p. Via exception
handling it can only lose some of the explicit knowledge it has.

This is the fundamental reason why exception handling cannot emulate
'dynamic_cast'.

Haven't we established that enough times?

Ahh, now we're getting somewhere. You now say RTTI involves storing
along with an object information relating to its dynamic type, and I
agree that that is a reasonable definition.
Goody.



However, note that a identical kind of type representation has to
be stored along side a thrown exception (say its throw statement
"number", its type, or whatever strange implementation you go for).

Not identical except in its direct representation. There is a difference
in available functionality, due to what is known _about_ that piece of
information. For 'dynamic_cast' maintaining that knowledge "about"
requires O(n) memory consumption, where n is the (maximum) number of
(simultanously existing) objects, so it's very real, and quantifiable.

I'm starting to think that my argument is too subtle...

From my point of view, your argument is just a little bit confused. ;-)

Hardly surprising given the common misunderstanding that RTTI is
necessary for exception handling.

 

[tom_usenet]

Strictly speaking that holds only for row contents; for row indexes
the correspondence (with the optimized/reduced table) would be o.t.o.

Yes, I was assuming that with the optimized/reduced table, each row is
unique, so several types map to the same row. IOW, several types have
the same row index, and many object creations have the same row index.
How the compiler automagically works out the row index for a
particular bit of code that creates an object isn't really important,
as long as you note it doesn't have to be dependent on the type of the
object.

Buster mentioned that earlier, so presumably the above paragraph refers
to the situation sans explicit type information. Get it?



For exception handling the total amount of memory needed in addition
to the matrix is constant.

Right, you can only throw one exception at a time. So you only need
the explicit type representation of that one exception (be that
representation in the form of a row index, a type_info object, or
whatever).

For dynamic_cast it is O(n), where n is maximum number of simultanously
existing objects.

Right. So you only need the explicit type representation of every
object (be that representation in the form of a row index, a type_info
object, or whatever).

To me (but mind you, I'm not very sophisticated) that looks like a
difference of some sort. _Could_ it be that it has something to do with
explicit type representation? I just ask.

No, it is the difference between 1 "explicit type representation" and
n "explicit type representation"s, as I've stated in various ways in
various posts.

That is, if you choose to consider your row index thing an "explicit
type representation".

Tom

 

[Alf P. Steinbach]

No, it is the difference between 1 "explicit type representation" and
n "explicit type representation"s, as I've stated in various ways in
various posts.

That is, if you choose to consider your row index thing an "explicit
type representation".

No, that's incorrect. Formally the reason is that exactly one
possibility (the case for exception handling) has _zero_ information
content, log 1 = 0; the case of 1 is very, very special. And so the
case of exactly one possibility makes an implicit representation
possible; it's not possible with more than one possibility, where
the non-zero information content must be explicit in some way.

Practically, ah, how can I phrase this?

Practically (searching, searching, searching) the throw statement id
in the compatibility matrix implementation of exception handling is
like an x86 16-bit "near" pointer, where the relevant memory segment is
implicit via both usage of the pointer and processor state, whereas
explicit type information in each object is like a full 32 or 48 bit
pointer, specifying all there is to know explicitly and in a way that
can easily be copied (without losing the implicit context), compared,
and so forth -- the functionality I spoke of earlier.

 

[Rob Williscroft]

tom_usenet wrote in

Right, you can only throw one exception at a time. So you only need
the explicit type representation of that one exception (be that
representation in the form of a row index, a type_info object, or
whatever).


Right. So you only need the explicit type representation of every
object (be that representation in the form of a row index, a type_info
object, or whatever).

Maybe I'm confused about dynamic_cast, but doesn't it require
a pointer or reference to an object with at least one virtual
function to work.

So it should only be nesaasaery to associate a dynamic typeid
with the vtable (or whatever is used) in order to do the
dynamic_cast.

I.e. the overhead would be O(n) where n is the number of dynamic
types (*) in the program, which is a constant.

(*) possibly ? plus the number of times they are inherited.

Rob.

 

[Ron Natalie]

Maybe I'm confused about dynamic_cast, but doesn't it require
a pointer or reference to an object with at least one virtual
function to work.

Well in some cases it doesn't, but in most of the interesting cases
it does. Your observation is correct. All the places where RTTI
behaves polymorhically (dynamic_cast or typeinfo) requires a
polymorphic class (at least one virtual function). This is not a
coincidence, the idea was to not require the overhead of RTTI unless
the user was doing something polymorhically anyhow.

I.e. the overhead would be O(n) where n is the number of dynamic
types (*) in the program, which is a constant.

The incremental overhead to already polymorhic classes is a small
constant added to each types vtable. The overhead to non-polymorphic
class is the cost of including some typing feature (notably the vtable
pointer) which may be large if the objects are already small.

 

[Alf P. Steinbach]

If you call a particular function, all you know about the exception
escaping is that it is restricted by the throw clause of that
function. You can proceed to narrow down that type using catch blocks.

"That type" being the static type of the throw statement -- and what
is the point?

 

[tom_usenet]

"That type" being the static type of the throw statement -- and what
is the point?

Yes, but all dynamic_cast can do is give you the static type of the
object when it was created. What is the point?

Tom

 

[Ivan Vecerina]

| ............ All the places where RTTI
| behaves polymorhically ..............

You mean that there is such a thing as non-polymorphic RTTI ?

As I understand this usage, it seems to support that the type
matching mechanisms involved in EH may be labelled as "RTTI".

Do we owe this whole thread to a terminology misunderstanding?

Best regards,
Ivan

 

[Alf P. Steinbach]

The functionality available is identical - you can check the "thing"
(exception or object) to see whether it is derived from a particular
type.

And George W. _is_ an earthworm.

Yes, you can check whether the "thing" is derived from a particular
type T, as long as that happens in the context of exception handling,
and type T happens to be the type of the 'catch' clause of the currently
examined frame, or a base class of that type.

No, you cannot check the "thing" to see whether it is derived from
any arbitrary type T, for to do that you need some way to obtain the
column index for any arbitrary type T, assuming a matrix that needlessly
contain information about all types. And exception handling does _not_
require this functionality, nor the complete all-types matrix, which is
required for RTTI. Hence, again, exception handling does not require
RTTI, and it can use optimizations that renders the mechanism unsuitable
as a platform for implementing RTTI.

I'm not sure whether the implied question was about that, though.

If the question is still about the difference between explicit and
implicit, consider that with the ability to obtain the matrix index
of any arbitrary type T, call that function <g> 'typeid', the code
can know that a particular index represents a particular type. And
furthermore, it can check whether an index represent any particular
type. That is an explicit representation; via the added functionality
of the 'typeid' function the index contains enough information to be
meaningful on its own, not just in a particular, limited context.