shang@corp.mot.com (David (Lujun) Shang) writes:

>In article <1992Jul19.151041.5458@taumet.com> steve@taumet.com (Steve Clamage)
>> The proposals have been to allow runtime type information only for types
>> with virtual functions.  (Some questions were raised this past week at the
>> C++ meeting about type information for built-in types, but that doesn't
>> apply to this discussion.)  Type information would then be tied to the
>> virtual table for the type.  There would be no space overhead in any
>> object.  (The type information is per class type, not per object.)
>>

>You still need reverse information for classes with virtual functions for a
>proper downcast from a virtual base to the derived.

That is part of the RTTI, not necessarily stored in the object.  Example:

class b1 { ... };
class b2 { ... };
class d : virtual public b1, virtual public b2 { ... };
class e : virtual public b1, public d { ... };

b1 *p = ...;

Variable p will point to some object of type b1, d, or e.  To cast from
b1* to e*, we use a "checked cast", which looks up the type information
at run time.  The data needed for the conversion is part of the type
info.  Typically, the virtual base is contiguous with the rest of the
object, so only an offset is needed.  Non-contiguous virtual bases
cause a number of problems which the implementation would have to
solve, including this problem.

We don't need to specify in the standard something which turns out to
be perfectly efficient for any conceivable implementation.  The
standard does not require virtual tables or pointers to them, for
example, but merely allows them.  Less-efficient implementations are
possible and allowable.  More efficient implementations might be
possible with smarter compilers and linkers, and would likewise be
allowable.

An implementation which required reverse pointers in objects would
still be allowable, but users would probably vote with their purchase
orders for other implementations.
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

shang@corp.mot.com (David (Lujun) Shang) writes:


>Interesting. Run time type check can provide a type safe downcast, that's true.
>But to make the pointer to a virtual base adjusted to the actual position of
>the derived object, we need an overhead: a reverse pointer, that is, a pointer
>pointing to the derived object where it is a virtual base. But only one reverse
>pointer cannot sove the whole problem, since there is not only one derived
>object that can be downcast.

The proposals have been to allow runtime type information only for types
with virtual functions.  (Some questions were raised this past week at the
C++ meeting about type information for built-in types, but that doesn't
apply to this discussion.)  Type information would then be tied to the
virtual table for the type.  There would be no space overhead in any
object.  (The type information is per class type, not per object.)

Another justification for the virtual-function requirement is that the
need to downcast non-polymorphic pointers seems less compelling.

These are the possible outcomes for a "checked cast":
1.  No type information available for this class -- fail.
2.  Requested type is not in the hierarchy -- fail.
3.  Requested type is a base class -- OK if unambiguous, else fail.
4.  Requested type is a derived class -- OK if unambiguous, else fail.

This subject is undergoing considerable research and development, and
we don't know what the final form will be.  Each successive paper on
the subject has differed from the last, and we expect to see a
description of a completely different approach at the next meeting.
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

In article <1992Jul19.151041.5458@taumet.com> steve@taumet.com (Steve Clamage)
writes:
> shang@corp.mot.com (David (Lujun) Shang) writes:
>
> >Interesting. Run time type check can provide a type safe downcast, that's
> >true.
> >But to make the pointer to a virtual base adjusted to the actual position of
> >the derived object, we need an overhead: a reverse pointer, that is, a
> >pointer pointing to the derived object where it is a virtual base.
>
>
> The proposals have been to allow runtime type information only for types
> with virtual functions.  (Some questions were raised this past week at the
> C++ meeting about type information for built-in types, but that doesn't
> apply to this discussion.)  Type information would then be tied to the
> virtual table for the type.  There would be no space overhead in any
> object.  (The type information is per class type, not per object.)
>

You still need reverse information for classes with virtual functions for a
proper downcast from a virtual base to the derived.

David Shang

I am having a problem casting from a base class to a derived class, when
the derived class has declared the base class as virtual.

Consider:

class Object{}

class ClassA : virtual public Object {};
class ClassB : virtual public Object {};
class ClassC : public ClassA, public ClassB {};

...
{
Object *obj;
ClassC c;
ClassC *cPtr;

obj = &c; // OK
cPtr = ( ClassC * )obj; // Error - Object is virtual base.
}


I do not have the ARM with me today, but I do have Lippman's book. It
does not address this( or if it does I can't find it ).

How do you do this? I want to be able to do this so I can retain the
lowest common class interface.

Thanks.

glenn

In article <1992Jul10.204342.11788@advtech.uswest.com> glw@io.uswest.com (Glenn Williams) writes:
>I am having a problem casting from a base class to a derived class, when
>the derived class has declared the base class as virtual.
>
>Consider:
>
>class Object{}
>
>class ClassA : virtual public Object {};
>class ClassB : virtual public Object {};
>class ClassC : public ClassA, public ClassB {};
>
>...
>{
>Object *obj;
>ClassC c;
>ClassC *cPtr;
>
>obj = &c; // OK
>cPtr = ( ClassC * )obj; // Error - Object is virtual base.
>}
>
>
>I do not have the ARM with me today, but I do have Lippman's book. It
>does not address this( or if it does I can't find it ).
>
>How do you do this? I want to be able to do this so I can retain the
>lowest common class interface.
>
>Thanks.
>
>glenn

 You cant. It is illegal.  There is no way the compiler can
 know where the object is, so the pointer cannot be
 adjusted as for non-virtual bases.

 Casting to ANY derived class is usually an indication
 of flawed design. [Even with non-virtual bases]

 Why do you want to do it? You want to retain the
lowest common class interface --- then you say you don't.
Make up you mind. You can't have it both ways.


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

glw@io.uswest.com (Glenn Williams) writes:

>I am having a problem casting from a base class to a derived class, when
>the derived class has declared the base class as virtual.

It is presently illegal to cast from a virtual base class to any
derived class.

The C++ committee is considering proposals to allow "safe downcasts",
coupled with run-time type identification.  If adopted in something
like the form of the most recent proposal, it would then be
possible to cast from a virtual base class to a derived class.
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

> glw@io.uswest.com (Glenn Williams) writes:
>
> >I am having a problem casting from a base class to a derived class, when
> >the derived class has declared the base class as virtual.
>
> It is presently illegal to cast from a virtual base class to any
> derived class.

In article <1992Jul11.171039.25619@taumet.com> steve@taumet.com (Steve Clamage)
replies:
>
> The C++ committee is considering proposals to allow "safe downcasts",
> coupled with run-time type identification.  If adopted in something
> like the form of the most recent proposal, it would then be
> possible to cast from a virtual base class to a derived class.
> --

Interesting. Run time type check can provide a type safe downcast, that's true.
But to make the pointer to a virtual base adjusted to the actual position of
the derived object, we need an overhead: a reverse pointer, that is, a pointer
pointing to the derived object where it is a virtual base. But only one reverse
pointer cannot sove the whole problem, since there is not only one derived
object that can be downcast. If we extend the example given by Glenn Williams
by:

class Object{}

class ClassA : virtual public Object {};
class ClassB : virtual public Object {};
class ClassC : public ClassA, public ClassB {};

class ClassD : public SomeClass, public ClassC, public ClassA {};

ClassD *dPtr;

Object *obj = new ClassD;
dPtr = ( ClassD * )obj; // down cast (Object *) to (ClassD *)

ClassC *cPtr = new ClassD;
dPtr = ( ClassD * )cPtr; // down cast (ClassC *) to (ClassD *)

ClassA *aPtr = new ClassD;
dPtr = ( ClassD * )aPtr; // down cast (ClassA *) to (ClassD *)

Note that if run time type check and type inference is provided by the
language, the compiler should know that the above downcasts are type safe since
the current object pointed by obj, cPtr, and aPtr are in the type of ClassD.
The programmer is even not necessarily to write the explicit cast expression,
i.e. (ClassD*).

But, in order to make all the downcasts possible, the object code ClassD must
have three reverse pointers prefixed at the code of the virtual base. A
concrete implementation technique may vary. For example, you can encode the
reverse pointers into a vtable (in this case, although the virtual base's
object code is single-copied, the vtable of the virtual base should be
duplicated for each different derived class). But you have to have the
information somewhere.

David Shang

In article <1992Jul14.001414.17603@cadsun.corp.mot.com> shang@corp.mot.com writes:
>Interesting. Run time type check can provide a type safe downcast, that's
>true.  But to make the pointer to a virtual base adjusted to the actual
>position of the derived object, we need an overhead: a reverse pointer,
>that is, a pointer pointing to the derived object where it is a virtual
>base. But only one reverse pointer cannot sove the whole problem, since
>there is not only one derived object that can be downcast.

Which shows that reverse pointers aren't the way to solve the problem.
No one is proposing such a solution, for there is another way that works
fine when restricted to classes that have virtual functions.

Consider the operation

 ptr_cast(dtype,ptr)

where type is the name of some type, and ptr is a pointer to some other
type (some basetype of dtype, say).  If ptr is "really" a pointer to
a dtype object, ptr_cast should return a pointer to it.  If not, it
should return 0 (a null pointer).  (Syntax from Stroustrup's C++
Programming Language, 2nd Edition; I think the syntax currently being
considered may have changed some).

A more efficient solution is to generate, for each class that has virtual
functions, a single extra virtual function.  Pretend that every class that
has one or more virtual functions has a common abstract base class, Any,
and that Any has declared

 void * Any::typeConvert(const char* typeName) = 0;

The class Any would not actually exist; I'm only using it to explain
the implementation.  Imagine it exists.

The compiler would generate an implementation of typeConvert for
each class that returns the right type of pointer when handed the name
of its class or that of any baseclass, and otherwise return 0.
The reason for "void *" is so that the cast to (dtype*) below
doesn't repeat the same problem I was trying to solve in the first place.

ptr_cast could then be implemented as if the following C preprocessor
macro appeared:

#define ptr_cast(dtype,ptr) (ptr ? (dtype*)ptr->typeConvert(#dtype) : 0)

No per-object storage would be required.  One function would be needed
per baseclass, but because of the regular structure of the inheritance
lattice, it would only be necessary to store the forest of inheritance
trees together with offsets; a common, small routine could be used to
"do the right thing" for any class.  Given this, we need not implement
it exactly as a function call; perhaps the vtable stores a pointer into
the type identification hierarchy (a tree of base type names and offsets)
and this tree is searched to find either the right offset or that the
cast is invalid.

Anyone whose mouth is watering over prospects like these should read
p. 450 of Stroustrup, the section "Uses and Misuses of Run-time Type
Inquiry", before getting carried away.





--
Joe Buck jbuck@ohm.berkeley.edu

In article <1992Jul14.001414.17603@cadsun.corp.mot.com> shang@corp.mot.com
(David (Lujun) Shang) writes:
> Run time type check can provide a type safe downcast, that's true.
> But to make the pointer to a virtual base adjusted to the actual position of
> the derived object, we need an overhead: a reverse pointer, that is, a
> pointer pointing to the derived object where it is a virtual base. But only
> one reverse pointer cannot sove the whole problem, since there is not only
> one derived object that can be downcast. If we extend the example given by
> Glenn Williams
>
> class Object{}
>
> class ClassA : virtual public Object {};
> class ClassB : virtual public Object {};
> class ClassC : public ClassA, public ClassB {};
>
> class ClassD : public SomeClass, public ClassC, public ClassA {};
>
> ClassD *dPtr;
>
> Object *obj = new ClassD;
> dPtr = ( ClassD * )obj; // down cast (Object *) to (ClassD *)
>
> ClassC *cPtr = new ClassD;
> dPtr = ( ClassD * )cPtr; // down cast (ClassC *) to (ClassD *)
>
> ClassA *aPtr = new ClassD;
> dPtr = ( ClassD * )aPtr; // down cast (ClassA *) to (ClassD *)

Sorry, the above example should be written as:

Object *obj = new ClassD;
ClassD *dPtr = ( ClassD * )obj; // down cast (Object *) to (ClassD *)
ClassC *cPtr = ( ClassC * )obj; // down cast (Object *) to (ClassC *)
ClassA *aPtr = ( ClassC::ClassA * )obj;
                                // down cast (Object *) to (ClassC::ClassA *)
ClassB *bPtr = ( ClassC::ClassB * )obj;
                                // down cast (Object *) to (ClassC::ClassB *)



> But, in order to make all the downcasts possible, the object code ClassD must
> have three reverse pointers prefixed at the code of the virtual base.

Should be five reverse pointers.

A sencond thought makes me clear that the above example need not any reverse
pointers since the compiler should know the the shift of a virtual base to a
specific class.

The reverse information is needed only if we downcast a virtual base to a
derived class which is unknown to the compiler. How could this happen? In the
current C++, this problem can not happen. But when we incorparate the run time
type check into C++, this problem will happen. The problem is basically caused
by typeof operator. For example:

void foo (ClassC *cPtr, Object *objp)
{ Object *objp;
  objp = cPtr;
  ...
  if (typeof(objp)==typeof(cPtr)) cPtr = (typeof(cPtr)) objp;
}

where typeof(cPtr) is not the type of (ClassC*), it should be the pointer to
the type of the object currently pointed by cPtr; This kind of downcast must
use the dynamic reverse information.

> A
> concrete implementation technique may vary. For example, you can encode the
> reverse pointers into a vtable (in this case, although the virtual base's
> object code is single-copied, the vtable of the virtual base should be
> duplicated for each different derived class). But you have to have the
> information somewhere.
>

I prefer to reverse pointer, or back shift encoded in vtable. If we encode
reverse pointer into object code, we will have the trouble to determine which
reverse pointer should be used.

David Shang

> In article <1992Jul14.001414.17603@cadsun.corp.mot.com> shang@corp.mot.com
writes:
> >Interesting. Run time type check can provide a type safe downcast, that's
> >true.  But to make the pointer to a virtual base adjusted to the actual
> >position of the derived object, we need an overhead: a reverse pointer,
> >that is, a pointer pointing to the derived object where it is a virtual
> >base. But only one reverse pointer cannot sove the whole problem, since
> >there is not only one derived object that can be downcast.

In article <13thioINN8c7@agate.berkeley.edu> jbuck@forney.berkeley.edu (Joe
Buck) replies:
>
> Which shows that reverse pointers aren't the way to solve the problem.

Which shows that *single* reverse pointer aren't the way to solve the problem.

> No one is proposing such a solution, for there is another way that works
> fine when restricted to classes that have virtual functions.
>
> Consider the operation
>
>  ptr_cast(dtype,ptr)
>
> where type is the name of some type, and ptr is a pointer to some other
> type (some basetype of dtype, say).  If ptr is "really" a pointer to
> a dtype object, ptr_cast should return a pointer to it.  If not, it
> should return 0 (a null pointer).  (Syntax from Stroustrup's C++
> Programming Language, 2nd Edition; I think the syntax currently being
> considered may have changed some).
>

A solution restricted only to those classes that have virtual functions is not
a complete solution.

> A more efficient solution is to generate, for each class that has virtual
> functions, a single extra virtual function.

Again, a solution restricted only to those classes that have virtual functions
is not a complete solution.

> Pretend that every class that

-- every class that has vitual function --

> has one or more virtual functions has a common abstract base class, Any,
> and that Any has declared
>
>  void * Any::typeConvert(const char* typeName) = 0;
>
> The class Any would not actually exist; I'm only using it to explain
> the implementation.  Imagine it exists.
>

Though the function TypeConvert does not actually exist, its input as a
character string is not the right way to specify a type convert function which
will take a derived class which is unknown (needless to say its name) to the
compiler. Yes, the proposal of run time type info contains a character string
as the identifier to the class and you can use it. But don't you think that it
is a less efficient solution? Even the implementation of SmallTalk does not use
character string to identify a class internally. In summary, we must treat type
as first class object and use an efficient internal code to represent the class
for run time type checking.

>
> The compiler would generate an implementation of typeConvert for
> each class that returns the right type of pointer when handed the name
> of its class or that of any baseclass, and otherwise return 0.
> The reason for "void *" is so that the cast to (dtype*) below
> doesn't repeat the same problem I was trying to solve in the first place.
>
> ptr_cast could then be implemented as if the following C preprocessor
> macro appeared:
>
> #define ptr_cast(dtype,ptr) (ptr ? (dtype*)ptr->typeConvert(#dtype) : 0)
>
> No per-object storage would be required.  One function would be needed
> per baseclass, but because of the regular structure of the inheritance
> lattice, it would only be necessary to store the forest of inheritance
> trees together with offsets; a common, small routine could be used to
> "do the right thing" for any class.  Given this, we need not implement
> it exactly as a function call; perhaps the vtable stores a pointer into
> the type identification hierarchy (a tree of base type names and offsets)
> and this tree is searched to find either the right offset or that the
> cast is invalid.
>

This makes C++ become SmallTalk: searching through class hierarchy. A useful
mechanism in distinguishing whether a class is a base class of some class for
untyped language. For a typed language, should we take a great pain to do so?

David Shang

In article <1992Jul14.133457.23086@cadsun.corp.mot.com> shang@corp.mot.com writes:
>In article <13thioINN8c7@agate.berkeley.edu> jbuck@forney.berkeley.edu (Joe
>Buck) replies:
>>
>> Which shows that reverse pointers aren't the way to solve the problem.
>
>Which shows that *single* reverse pointer aren't the way to solve the problem.
>
>
>A solution restricted only to those classes that have virtual functions is not
>a complete solution.

 It is the best that can possiblt be done, if there are no
virtual functions (or virtual bases) then there can't be any hidden data else
C compatibilty is out the window. We wouldn't want that woudl we?

 Besides, the real problem is with virtual bases, and these
are usually used when there are virtual functions. They already
introduce a hidden pointer.

>Though the function TypeConvert does not actually exist, its input as a
>character string is not the right way to specify a type convert function which
>will take a derived class which is unknown (needless to say its name) to the
>compiler.

 A char* to a string with the exact same name as the class
is the ONLY way I can think of doing it that preserves the names
across runs and compiles. Any other ways?


>Yes, the proposal of run time type info contains a character string
>as the identifier to the class and you can use it. But don't you think that it
>is a less efficient solution? Even the implementation of SmallTalk does not use
>character string to identify a class internally.

 Its not a compiler either.

>In summary, we must treat type
>as first class object and use an efficient internal code to represent the class
>for run time type checking.

 How to generate this magic code? It would have to be
done at link time, at that wouldnot work for dynamic linkage
or persistence, and maybe not across networks.
>
>This makes C++ become SmallTalk: searching through class hierarchy. A useful
>mechanism in distinguishing whether a class is a base class of some class for
>untyped language. For a typed language, should we take a great pain to do so?

 You only incur the overhead if you use it.

 Any better way of doing it than a run-time search through
the class DAG?

>
>David Shang
--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------