Siemel Naran wrote:
>
> On 19 Apr 99 18:20:55 GMT, LR <lruss@superlink.net> wrote:
> >Siemel Naran wrote:
>
> >>    struct X { ... };
> >>    struct Y : X { ... };
> >>    int f1(X * x) { return x->f(3); }
> >> then the compiler must generate
> >>    X::template f<int>(int);
> >>    Y::template f<int>(int);
> >
> >I'm not sure I follow.  Shouldn't that generated member of X be:
> >       virtual X::template f<int>(int) const = 0;
> >(I'm not really sure where the X:: would go, but that's not my question,
> >since this won't compile anyway)
>
> No.  The object 'x' might have actual type X or Y.  Eg,
>    int main() { X x; Y y; f(&x); f(&y); }
> So both X::f<int> and Y::f<int> are needed.  To recap, this is one
> problem with virtual member templates.  The compiler has to do
> extensive flow analysis to see which instantiations might be needed.
> In this case, it is not sufficient to generate just X::f<int>.  The
> compiler needs to look at the entire hierarchy at link time and
> deduce that it needs Y::f<int>, Z::f<int>, and so on.  (Here, the
> hypothetical Z derives from Y.)
>

But in article  <slrn7hk71g.sjj.sbnaran@localhost.localdomain> where the
function f in struct X was:
 template <class T> virtual T f(T) const = 0;
Why would the compiler need to make an instance of a pure virtual
function?  Section 10.4 seems to say that you can't make an instance of
type X if it has a pure virtual function.  Or maybe I just snipped too
much?

Ahh, yes, that's what I was trying to ask about: The compiler has to
look at the enire hierarchy at link time.  But doesn't it have to do
that now anyway?  And deduce what entries will be in the vtable? (Please
see what I hope is a clarification of my other question below.)

>
>
> >>[snip]
>
> >But isn't there a similar problem now with template member functions?
> >Consider:
> >       //file xl.h
> >       class XL {
> >       public:
> >               template<class T> T f(T t) { return t; }
> >       };
> >
> >       // file yl.cpp
> >       #include "xl.h"
> >       static void yl() {
> >               int i;
> >               int r = XL().f(i);
> >       }
> >
> >       // file zl.cpp
> >       #include "xl.h"
> >       static void zl() {
> >               double d;
> >               double r = XL().f(d);
> >       }
> >
> >Now after we compile yl.cpp and zl.cpp, their object files (or what ever
> >they get turned into) will have different info about what members stuct
> >XL has.  Doesn't that have to get resolved by the linker too?
>
> Nope, class XL has no data members.
>
> The non-virtual member template has no problems.  This is because it
> is not virtual.  The common implementation of virtual functions is
> as follows.  Say you call a virtual function F.
>    void F(X * x) { x->F(2); }
> If the function 'F' is the 2nd entry in the virtual table, the above
> code translates to:
>    void F(X * x) { (x->vptr)[2](x,1); }
> The call is to a function with signature "void ()(X *const this, int)".

I suspect that I wasn't clear enough in the above.  Let's say that we
compile yl.cpp to yl.obj and xl.cpp to xl.obj.  During compilation of
yl.cpp the compiler sees that we are using the <int> specialzation of
f() and during compilation of xl.cpp the compiler sees that we are using
the <double> specialization of f().  So during compilation of yl the
vtable will be thought to be of size 1 and during compilation of xl the
compiler may think it's the same size.  The compiler can't know that the
size of the vtable after the link process should be two.  How could it?
I should be able to compile these on different computers, in different
countries even, and the two obj files should still be able to link
(assumes the same compiler, os, and all options the same,  etc.).  Nor
can it be the case that the compiler will, or even can, create a vtable
that will contain calls for all possible classes.  How could it know?
So, doesn't this have to be resolved by the linker?
>
> [snip]
> All these problems can be solved, but it's extremely difficult.  To
> summarize, here are three problems:
>    [X] linker: identify full hierarchies to see which instantiations
>        may be needed (eg, need X::f<int> and Y::f<int>).
>    [X] compiler needs different methods for calling non-template and
>        template virtual members.
>    [X] the order of the virtual member template members is important
>        too.
>
>[snip]

I'm begining to think that all these problems can be handled at run
time, with logic that may not be so different from what may exist now.

LR.










































.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 25 Apr 99 16:02:31 GMT, LR <lruss@superlink.net> wrote:
>Siemel Naran wrote:

> template <class T> virtual T f(T) const = 0;
>Why would the compiler need to make an instance of a pure virtual
>function?  Section 10.4 seems to say that you can't make an instance of
>type X if it has a pure virtual function.  Or maybe I just snipped too
>much?

But you can call a pure virtual function!  Eg:
   struct X { virtual ~X(); virtual int f() const = 0; }
   struct Y : X { int f() const; };
Now the definitions of the member functions
   int X::f() const { return 1; }; // define pure virtual function
   int Y::f() const { return 3+X::f(); }; // call pure virtual function
And then
   int main() { Y y; cout << y.f(); } // print "4"

Why on earth anyone would want to make X::f() pure virtual is another
matter.  Perhaps the member function represents some incomplete
functionality, and the derived class version of the function is meant
to complete the functionality -- ie, call the base class version of
the function through the scope resolution operator and do some
additional stuff related to the derived class.  A realistic example of
this sort of function is
   /*virtual*/ bool Base::equal(const Base&) const /*= 0*/;


>Ahh, yes, that's what I was trying to ask about: The compiler has to
>look at the enire hierarchy at link time.  But doesn't it have to do
>that now anyway?  And deduce what entries will be in the vtable? (Please
>see what I hope is a clarification of my other question below.)

No, the compiler is not required to do anything this complicated.  If
you instantiate a class, then all virtual functions in that class should
be instantiated, even if they are not used.  Eg,
   template <class T>
   struct X { virtual ~X(); virtual int f() const = 0; };
   template <class T> struct Y : X<T> { int f() const; };
Instantiating Y<int> as in
   int main() { Y<int>(); }
forces the instantiation of
   int X<int>::f() const;
   int Y<int>::f() const;
The compiler may do complex analysis to determine if these functions
are used and discard the instantiations if it turns out that they are
not used.  The analysis is complex because it requires the compiler to
look at each line of source code and study the inheritance hierarchy
at link time.  No compiler is required to do this analysis.


>> >       //file xl.h
>> >       class XL {
>> >       public:
>> >               template<class T> T f(T t) { return t; }
>> >       };

>I suspect that I wasn't clear enough in the above.  Let's say that we
>compile yl.cpp to yl.obj and xl.cpp to xl.obj.  During compilation of
>yl.cpp the compiler sees that we are using the <int> specialzation of
>f() and during compilation of xl.cpp the compiler sees that we are using
>the <double> specialization of f().  So during compilation of yl the
>vtable will be thought to be of size 1 and during compilation of xl the
>compiler may think it's the same size.  The compiler can't know that the
>size of the vtable after the link process should be two.  How could it?
>I should be able to compile these on different computers, in different
>countries even, and the two obj files should still be able to link
>(assumes the same compiler, os, and all options the same,  etc.).  Nor
>can it be the case that the compiler will, or even can, create a vtable
>that will contain calls for all possible classes.  How could it know?
>So, doesn't this have to be resolved by the linker?

No.  Your function XL::f(T) is not virtual!  So it is never placed in
the virtual table.

As the standard only allows non-template member functions to be virtual,
the size of the virtual table is known once and for all as soon as the
compiler parses file XL.h.  Eg,
   // XL.h
   struct XL {
      virtual ~XL();
      template <class T> void f(T) const;
      virtual void g() const;
   };
And vtable<XL> is known to have size 2 -- for the destructor and g().


>> All these problems can be solved, but it's extremely difficult.  To
>> summarize, here are three problems:
>>    [X] linker: identify full hierarchies to see which instantiations
>>        may be needed (eg, need X::f<int> and Y::f<int>).
>>    [X] compiler needs different methods for calling non-template and
>>        template virtual members.
>>    [X] the order of the virtual member template members is important
>>        too.
>
>I'm begining to think that all these problems can be handled at run
>time, with logic that may not be so different from what may exist now.

That's a possibility too.  Of course, it means that while the program
is running, the program may have to invoke the compiler to compile
the instantiations as needed!  That's going to be quite slow.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3720EA75.2BC13F82@iro.umontreal.ca>,
  n.chapados@ieee-n-o-s-p-a-m.ca wrote:
>
> James.Kanze@dresdner-bank.com wrote:
>
> > > The obvious alternative would be to provide entries only for the
> > > versions of g that are actually instantiated, but such an implementation
> > > would have to defer the assignment of vtable indices to those functions
> > > until the program is actually linked, making it a lot more complicated.
> >
> > I don't think it would be that difficult to differ building the vtbl, or
> > at least the part of the vtbl which concerned template functions, until
> > link time.  Now explain what the generated code to call the functions
> > will look like -- you'll either have to generate the offsets into the
> > vtbl at link time as well, or you'll have to use some sort of map, which
> > is filled at link time (or with a pseudo-static constructor?).

> The vtbl problem could be solved reasonably easily if we allow for
> *nested* vtbls.  In other words, in the vtbl slot where a regular
> (non-template) virtual function normally goes, we now put a pointer to
> a *second* vtbl that contains the virtual functions instantiated for
> the member template.

> Of course, calling a virtual member template function requires two
> indirections instead of just one, but this might be deemed reasonable
> overhead for that feature.  The overhead for normal (non-template)
> virtual functions remains the same.  The problems with semantics are
> harder to solve: a derived class has to know all the instantiations
> for the base member template in order for the overrides to be inserted
> properly in the vtable.

This is the real problem.  The offsets into the table cannot be known
until link time.  So the linker has to set up the table, patch up the
offsets at the call site, etc.

The problem becomes even more difficult if we remember that most systems
support dynamically linked libraries.

--
James Kanze                         mailto: James.Kanze@dresdner-bank.com
Conseils en informatique orientie objet/
                        Beratung in objekt orientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany  Tel. +49 (069) 63 19 86 27

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

LR wrote in message <7flebi$2mp$1@earth.superlink.net>...
>
>Ahh, yes, that's what I was trying to ask about: The compiler has to
>look at the enire hierarchy at link time.  But doesn't it have to do
>that now anyway?  And deduce what entries will be in the vtable? (Please
>see what I hope is a clarification of my other question below.)


I don't think so. To generate calls to virtual functions, the compiler only has
to see the class and its bases. To link it, the linker only has to have the object
or library files for these. Both are, loosely speaking, closed problems.

To generate templatised virtual functions, we'd also need to see all the classes
derived *from* this one. The compiler would have to send the function call into
some run-time library function which queried which instantiations had been
provided. This comparison would have to be a best fit against the provided
parameters. I would hate to get a "function not found" error because I had passed
a derived class argument but only instantiated for a base class parameter.
(Now worry about integral promotions and multiple inheritance.)

The linker would have to build the data which that function used. Many OSes
allow some form of dynamic linking, and so this data would change from
moment to moment. (Now add multiple threads.)

These issues remind me of past discussions on "double dispatch".

I expect there are various possible ways of performing the function lookup
and
organising the data, and that each is probably "best" for certain
applications.
The language already provides dynamic_cast and typeid, so apart from the
(optional?) complication of accomodating integral promotions, I don't see
that the
implementation is much better placed to provide such a feature than you are.




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James.Kanze@dresdner-bank.com wrote:

> > The obvious alternative would be to provide entries only for the
> > versions of g that are actually instantiated, but such an implementation
> > would have to defer the assignment of vtable indices to those functions
> > until the program is actually linked, making it a lot more complicated.
>
> I don't think it would be that difficult to differ building the vtbl, or
> at least the part of the vtbl which concerned template functions, until
> link time.  Now explain what the generated code to call the functions
> will look like -- you'll either have to generate the offsets into the
> vtbl at link time as well, or you'll have to use some sort of map, which
> is filled at link time (or with a pseudo-static constructor?).

The vtbl problem could be solved reasonably easily if we allow for *nested*
vtbls.  In other words, in the vtbl slot where a regular (non-template) virtual
function normally goes, we now put a pointer to a *second* vtbl that contains
the virtual functions instantiated for the member template.

Of course, calling a virtual member template function requires two indirections
instead of just one, but this might be deemed reasonable overhead for that feature.
The overhead for normal (non-template) virtual functions remains the same.

The problems with semantics are harder to solve: a derived class has to know all
the instantiations for the base member template in order for the overrides to be
inserted properly in the vtable.

---
Nicolas Chapados                http://www.iro.umontreal.ca/~chapados
Universit    de Montr   al / Labo. d'informatique des syst   mes adaptatifs



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> In article <7f6de0$t1t$1@nnrp1.dejanews.com>,
>   "AllanW {formerly AllanW@my-dejanews.com}" <allan_w@my-dejanews.com> wrote:
> > See D&E for more details on how the vtable works.

In article <7f7mkd$sh$1@nnrp1.dejanews.com>,
  lruss7332@my-dejanews.com wrote:
> D&E?  Sorry, I'm not familiar with that.

"The Design and Evolution of C++", Addison-Wesley, ISBN 0-201-54330-3.
Written by Bjarne Stroustrup, the designer of C++, this book presents
the definitive insider's guide to the design and development of the
C++ programming language. Without omitting critical details or getting
bogged down in technicalities, Stroustrup presents his unique insights
into the decisions that shaped C++. Every C++ programmer will benefit
from Stroustrup's explanations of the 'why's' behind the language.
See http://www.research.att.com/~bs/dne.html for more.

----
Allan_W@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> Siemel Naran wrote:
> > If there's sufficient demand for this feature, it may appear in the
> > next standard.

In article <7f7mhc$h6l$1@earth.superlink.net>,
  lruss@superlink.net wrote:
>  Hmmm, Ok, I'll ask; Anyone else out there who would like this?

Of course I would like it, if the price wasn't too high! And it's not
even that I currently have a problem that this would solve, it's just
that the current restriction *might* cause a problem someday, and I
would like to remove all restrictions that reasonably can be removed.

But you asked the wrong question. The question isn't "Who would like
this?" because hardly anyone would object to removing a restriction
from the language. The valid question is "Who would like this feature
if the cost was <insert cost here>."

Here's an example. It's neccesarily contrived because I don't have a
lot of experience writing compilers. However, for all we know, a real
proposal could be even more draconian than this. Let's say that it's
possible to implement a virtual template function MyClass::foo. But
let's also say that calling MyClass::foo (or MyChildClass::foo, or
any other foo in a class derived from MyClass) EVEN ONCE from ANYWHERE
in the program, with ANY argument type, caused foo to be instanciated
for EVERY SINGLE DATA TYPE that has EVER been entered into the compiler
data-type tables in ANY of the modules which were compiled for this
program. This not only includes fundamental types such as char, int,
unsigned long, etc., but also int*, const int*, int**, const int **,
int * const *, int***, const int***, int * const **, ..., plus
int(*)(char*) and all other function signatures for all external
functions in your program or in header files, as well as MyClass,
MyChildClass, every other class you've used, an even every possible
instanciation of ostream<T>, istream<T>, numeric_limits<T>,
vector<T>, list<T>, etc., etc., etc.... Dump a symbol table after a
reasonably complex C++ program compiles, and how many different data
types do you have? 10,000? 50,000? 500,000? More?

If you had asked "Who would like this feature if the cost was 50,000
extra instanciations which not only take up space but also must be
syntactically correct?" you would find very few takers indeed.

----
Allan_W@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 22 Apr 99 15:28:23 GMT, AllanW

>"The Design and Evolution of C++", Addison-Wesley, ISBN 0-201-54330-3.
>Written by Bjarne Stroustrup, the designer of C++, this book presents
>the definitive insider's guide to the design and development of the
>C++ programming language. Without omitting critical details or getting
>bogged down in technicalities, Stroustrup presents his unique insights
>into the decisions that shaped C++. Every C++ programmer will benefit
>from Stroustrup's explanations of the 'why's' behind the language.
>See http://www.research.att.com/~bs/dne.html for more.

One problem with the book is that it hardly discusses the standard
template library.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7hc9rc.a7u.sbnaran@localhost.localdomain>,
  sbnaran@uiuc.edu wrote:

    [Concerning virtual template member functions...]
> If there's sufficient demand for this feature, it may appear in the
> next standard.

I'd suggest implementing it first; without some sort of proof that the
idea is implementable (and IMHO, it is complicated enough that the only
real proof would be an implementation), it's chances of making it in any
version of the standard are just about nil.

--
James Kanze                         mailto: James.Kanze@dresdner-bank.com
Conseils en informatique orientie objet/
                        Beratung in objekt orientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany  Tel. +49 (069) 63 19 86 27

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <37167926.4FFBB544@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> LR wrote:
> >
> > Hi,
> > Could someone please tell me the reasoning behind not allowing virtual
> > template functions?
> > TIA.
> > LR.
>
> The problem with something like:
>
> struct AA {
>  template <class C> virtual void g(C);
> };
>
> is that g() doesn't represent a single function, but rather an infinite
> set of possible functions. In a typical implementation of C++, the
> vtable for struct AA would have to have a different entry for each such
> function. An infinitely long vtable is a bit of a problems!
>
> The obvious alternative would be to provide entries only for the
> versions of g that are actually instantiated, but such an implementation
> would have to defer the assignment of vtable indices to those functions
> until the program is actually linked, making it a lot more complicated.

I don't think it would be that difficult to differ building the vtbl, or
at least the part of the vtbl which concerned template functions, until
link time.  Now explain what the generated code to call the functions
will look like -- you'll either have to generate the offsets into the
vtbl at link time as well, or you'll have to use some sort of map, which
is filled at link time (or with a pseudo-static constructor?).

Now go back and redo the exercise with shared, dynamicall linked
libraries.

--
James Kanze                         mailto: James.Kanze@dresdner-bank.com
Conseils en informatique orientie objet/
                        Beratung in objekt orientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany  Tel. +49 (069) 63 19 86 27

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 19 Apr 99 18:20:55 GMT, LR <lruss@superlink.net> wrote:
>Siemel Naran wrote:

>>    struct X { ... };
>>    struct Y : X { ... };
>>    int f1(X * x) { return x->f(3); }
>> then the compiler must generate
>>    X::template f<int>(int);
>>    Y::template f<int>(int);
>
>I'm not sure I follow.  Shouldn't that generated member of X be:
> virtual X::template f<int>(int) const = 0;
>(I'm not really sure where the X:: would go, but that's not my question,
>since this won't compile anyway)

No.  The object 'x' might have actual type X or Y.  Eg,
   int main() { X x; Y y; f(&x); f(&y); }
So both X::f<int> and Y::f<int> are needed.  To recap, this is one
problem with virtual member templates.  The compiler has to do
extensive flow analysis to see which instantiations might be needed.
In this case, it is not sufficient to generate just X::f<int>.  The
compiler needs to look at the entire hierarchy at link time and
deduce that it needs Y::f<int>, Z::f<int>, and so on.  (Here, the
hypothetical Z derives from Y.)



>>[snip]

>But isn't there a similar problem now with template member functions?
>Consider:
> //file xl.h
> class XL {
> public:
>  template<class T> T f(T t) { return t; }
> };
>
> // file yl.cpp
> #include "xl.h"
> static void yl() {
>  int i;
>  int r = XL().f(i);
> }
>
> // file zl.cpp
> #include "xl.h"
> static void zl() {
>  double d;
>  double r = XL().f(d);
> }
>
>Now after we compile yl.cpp and zl.cpp, their object files (or what ever
>they get turned into) will have different info about what members stuct
>XL has.  Doesn't that have to get resolved by the linker too?

Nope, class XL has no data members.

The non-virtual member template has no problems.  This is because it
is not virtual.  The common implementation of virtual functions is
as follows.  Say you call a virtual function F.
   void F(X * x) { x->F(2); }
If the function 'F' is the 2nd entry in the virtual table, the above
code translates to:
   void F(X * x) { (x->vptr)[2](x,1); }
The call is to a function with signature "void ()(X *const this, int)".

What I was saying was that if you allowed virtual member templates,
then the virtual table would have a variable size.  So in one compile,
the function F might be the 2nd function.  But in another compile, the
function F might be the 3rd function.  Eg,

// X.h
struct X {
   virtual ~X(); virtual template <class T> void V(); virtual void F(); };

// file1.c
void f1(X * x) { x->template V<int>(); x->F(); }
   // vtable[0]=destructor, vtable[1]=V<int>, vtable[2]=F

// file2.c
void f2(X * x) { x->template V<int>(); x->template V<double>(); x->F(); }
   // vtable[0]=destructor, vtable[1]=V<int>, vtable[2]=V<double>, vtable[3]=F


We see that when we compiled file1.c into file1.o, the index of F was
hard coded as 2.  (The index is usually hard coded at compile time.)

But after compiling file2.c into file2.obj, the index of F becomes 3.
So this means that file1.obj has to recompile to reflect the new index.
But .c files are supposed to be independent.  Changing one is not
supposed to force another to compile.

The solution is to adopt two conventions for calling virtual functions:
(1) the usual one for non-template members, (2) a fancy one for template
members.

And there's also the order of virtual member templates to worry about.
Do we put V<int> first or V<double>.

All these problems can be solved, but it's extremely difficult.  To
summarize, here are three problems:
   [X] linker: identify full hierarchies to see which instantiations
       may be needed (eg, need X::f<int> and Y::f<int>).
   [X] compiler needs different methods for calling non-template and
       template virtual members.
   [X] the order of the virtual member template members is important
       too.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:

[...]

> All these problems can be solved, but it's extremely difficult.  To
> summarize, here are three problems:
>    [X] linker: identify full hierarchies to see which instantiations
>        may be needed (eg, need X::f<int> and Y::f<int>).
>    [X] compiler needs different methods for calling non-template and
>        template virtual members.
>    [X] the order of the virtual member template members is important
>        too.

There are also problems to solve with the semantics.

Given the following hierarchy:

struct X
{
  template<class T1, class T2>
   virtual void f(T1, T2);
};

struct Y: X
{
  template<class T>
   virtual void f(T, T);
}

Now, does Y::f<int> override X::f<int, int>?

One can argue that it doesn't, since the number of template
parameters is different; in this case, a special syntax for
overriding special cases would be needed, f.ex.

struct Z: X
{
  template<class T>
   virtual void f<T, T>(T, T);
  // syntax follows partial specialisation syntax
};

Probably this is the better solution, since otherwise, it will
be a very complex task to determine which template overrides
which other template. For example:

struct W: X
{
  template<class T1, class T2>
   virtual void f(T1, T2);
  template<class T>
   virtual void f(T, T);
}

A direct call call to someWobject.f(1, 1) calls the second
function. However - which of the functions overrides X::f?
Note that you can use _both_ with

W.f<int>(3, 5); W.f<int, int>(3, 5);

I guess that more semantic problems can be found if looking
further at it.

About the practical problems you noted:

I don't think the vtbl problem is serious. If you think about it,
an address is just an index into memory (on some systems, this
index can consist of several parts). Now, putting objects (in this
case: object files) together and filling in indices (in this case:
memory addresses) is exactly what linkers are about. Therefore
it should IMHO be trivial to extend this scheme to vtbls
(especially given that vtbl entries are all the same size).
Also, the calling sequence needs not be different for virtual
templates/non-templates (the linker fills in the vtbl indices,
just as it fills in the memory addresses).

The remaining problem is then to instantiate all needed functions.
This probably is the hard part (besides getting the semantics right).


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 18 Apr 99 13:13:24 GMT, LR <lruss@superlink.net> wrote:
>Siemel Naran wrote:

>> I think there are ways to make template virtual functions work.  In
>> the virtual table, store whether the function is a non-template or
>> template, and if it is a template, store template argument
>> information.  With the new implementation, non-template virtual
>> functions would be as fast as before!  This is because the compiler
>> knows at compile time whether the virtual function is a template or
>> not, so it can take steps to call it appropriately.
>
> Sorry, I'm not sure what you mean here.  When you say that non-template
>virtual functions would be as fast as before, do you mean that the
>template virtual functions will be slower because some kind of look up
>will be done at runtime? But wouldn't you still have to resolve the
>function address in the child class vtable? How can that be done at
>runtime? Will each class have somekind of invisible lookup that all it's
>children will have?  What about multiple and/or virtual inheritence?

I think you're right: member template virtual functions need not be
slower.  If the compiler can determine which templates are needed, then
all is ok.  Eg, if you have
   struct X {
      virtual ~X();
      virtual void dummy1() const = 0;
      template <class T> virtual T f(T) const = 0;
      virtual void dummy2() const = 0;
   };
   struct Y : X { ... };
and you call
   int f1(X * x) { return x->f(3); }
then the compiler must generate
   X::template f<int>(int);
   Y::template f<int>(int);

This requires complex flow analysis from the compiler!  For the
compiler must examine the code to see which functions are
potentially used.

(Note the word 'potentially'.  It is possible that X::f(int) is not
used because the object 'x' may never have dynamic type X.  Indeed,
this is the case if class X is abstract.  Anyway, function Y::f(int)
may call X::f(int) through the scope resolution operator, so both
may be needed.)

Anyway, what is the layout of the virtual table?
   vtable<X>[0]=destructor
   vtable<X>[1]=dummy1
   vtable<X>[2]=f<int>
   vtable<X>[3]=dummy2

What if you later add this function?
   double f1(X * x) { return x->f(3.0); }
Now we need X::template f<double>(double), and similar for Y.

So the new virtual table should be
   vtable<X>[0]=destructor
   vtable<X>[1]=dummy1
   vtable<X>[2]=f<int>
   vtable<X>[3]=f<double>
   vtable<X>[4]=dummy2
We see that the index of 'dummy2' has changed.

Here's the problem.  Consider this file:
   // dummy2.cpp
   #include "dummy2.h"
   void myspace::dummy2(X * x) { x->dummy2(); }
Suppose we compile this file when dummy2 has index==3.  So file
dummy2.obj has the index 3 hardcoded into it.

Now suppose in some other .cpp file we use f<double>.  Eg:
   // somefile.cpp
   #include "somefile.h"
   double myspace::f1(X * x) { return x->f(3.0); }
Now file somefile.obj is using the index 3 for X::f(double).
Which means that file dummy2.obj needs to recompile.  But how can
changing one .cpp file force another to recompile?!

To end the problem, we go with this layout
   vtable<X>[0]=destructor
   vtable<X>[1]=dummy1
   vtable<X>[2]=f<T>
   vtable<X>[3]=f<double>
   vtable<X><f<T>>[0]=f<int>(int)
   vtable<X><f<T>>[1]=f<double>(double)
We see that there are two virtual tables.

Now when we call "x->f(3)", the compiler has to traverse two virtual
tables instead of one.  This is why member template virtual functions
are more expensive.

There's also the problem of ordering.  Should we have
   vtable<X><f<T>>[0]=f<int>(int)
   vtable<X><f<T>>[1]=f<double>(double)
or
   vtable<X><f<T>>[0]=f<double>(double)
   vtable<X><f<T>>[1]=f<int>(int)

I suppose the indexing can be resolved at link time.  But what a
complex linker!



>> If there's sufficient demand for this feature, it may appear in the
>> next standard.

> Hmmm, Ok, I'll ask; Anyone else out there who would like this?

I haven't had the need for it yet.  But then again, my projects and
number of years programming are small.


>   And, does getting it in the standard mean that it will be in the
>compiler that I'm using too? ;)

Eventually.  If it's a hot feature, it's likely to appear quickly in
your compiler.  Like non-virtual member templates; it seems that most
compilers support these now.  But the return value optimization is not
that hot.  The time saved eliding a call to the copy constructor and
destructor is usually small compared to the time in the function
itself.  At least this is my theory why the return value optimization
hasn't made it into compilers.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
Thanks very much for your answer, I have two more questions.

Siemel Naran wrote:
>
>[snip]
>
> I think you're right: member template virtual functions need not be
> slower.  If the compiler can determine which templates are needed, then
> all is ok.  Eg, if you have
>    struct X {
>       virtual ~X();
>       virtual void dummy1() const = 0;
>       template <class T> virtual T f(T) const = 0;
>       virtual void dummy2() const = 0;
>    };
>    struct Y : X { ... };
> and you call
>    int f1(X * x) { return x->f(3); }
> then the compiler must generate
>    X::template f<int>(int);
>    Y::template f<int>(int);

I'm not sure I follow.  Shouldn't that generated member of X be:
 virtual X::template f<int>(int) const = 0;
(I'm not really sure where the X:: would go, but that's not my question,
since this won't compile anyway)



> This requires complex flow analysis from the compiler!  For the
> compiler must examine the code to see which functions are
> potentially used.

> Here's the problem.  Consider this file:
>    // dummy2.cpp
>    #include "dummy2.h"
>    void myspace::dummy2(X * x) { x->dummy2(); }
> Suppose we compile this file when dummy2 has index==3.  So file
> dummy2.obj has the index 3 hardcoded into it.
>
> Now suppose in some other .cpp file we use f<double>.  Eg:
>    // somefile.cpp
>    #include "somefile.h"
>    double myspace::f1(X * x) { return x->f(3.0); }
> Now file somefile.obj is using the index 3 for X::f(double).
> Which means that file dummy2.obj needs to recompile.  But how can
> changing one .cpp file force another to recompile?!
>
> To end the problem, we go with this layout
>    vtable<X>[0]=destructor
>    vtable<X>[1]=dummy1
>    vtable<X>[2]=f<T>
>    vtable<X>[3]=f<double>
>    vtable<X><f<T>>[0]=f<int>(int)
>    vtable<X><f<T>>[1]=f<double>(double)
> We see that there are two virtual tables.
>
> Now when we call "x->f(3)", the compiler has to traverse two virtual
> tables instead of one.  This is why member template virtual functions
> are more expensive.
>
> There's also the problem of ordering.  Should we have
>    vtable<X><f<T>>[0]=f<int>(int)
>    vtable<X><f<T>>[1]=f<double>(double)
> or
>    vtable<X><f<T>>[0]=f<double>(double)
>    vtable<X><f<T>>[1]=f<int>(int)
>
> I suppose the indexing can be resolved at link time.  But what a
> complex linker!
>
> [snip]

But isn't there a similar problem now with template member functions?
Consider:
 //file xl.h
 class XL {
 public:
  template<class T> T f(T t) { return t; }
 };

 // file yl.cpp
 #include "xl.h"
 static void yl() {
  int i;
  int r = XL().f(i);
 }

 // file zl.cpp
 #include "xl.h"
 static void zl() {
  double d;
  double r = XL().f(d);
 }

Now after we compile yl.cpp and zl.cpp, their object files (or what ever
they get turned into) will have different info about what members stuct
XL has.  Doesn't that have to get resolved by the linker too?

And yes I agree, there is plenty of complexity here.


LR.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

   >Could someone please tell me the reasoning behind
   >not allowing virtual template functions?

Since when aren't template functions allowed to be
virtual? Template member functions of classes can't
be virtual (14.5.2.3); this latter limitation makes
sense, if you think about how virtual functions are
implemented.

The standard nowhere explicitly says template functions
can't be virtual. It does refer to virtual template
functions in a number of places (14.7.1.7, 14.7.1.10).
It makes sense that a template can have virtual functions
if you think about how virtual functions are implemented.
It just requires some compiler/linker smarts to be
implemented -- or better yet, to be implemented well.

Paul
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Paul Pedriana wrote:
>
>    >Could someone please tell me the reasoning behind
>    >not allowing virtual template functions?
>
> Since when aren't template functions allowed to be
> virtual? Template member functions of classes can't
> be virtual (14.5.2.3); this latter limitation makes

There is no such section: 14.5.2 has no subsections. It does have 8
paragraphs, but you should always distiguish paragraph numbers from
subsection numbers. This may sound pedantic, but there are sections
which have both paragraphs and subsections, and it's confusing if you
use the same scheme for both. Example: does 14.5.4.3 refer to paragraph
3 or subsection 3?

> sense, if you think about how virtual functions are
> implemented.
>
> The standard nowhere explicitly says template functions
> can't be virtual. It does refer to virtual template

You've already noted that member functions can't be virtual. What would
it mean for a template function that wasn't a member function to be
virtual? There's no class object for it to be connected with, and hence
no virtual invocation process.

> functions in a number of places (14.7.1.7, 14.7.1.10).

Which version of the standard are you using? In the final published
version of the standard, 14.7.1 has no sub-sections, and paragraphs 7
and 10 of 14.7.1 say nothing about virtual functions.

> It makes sense that a template can have virtual functions

Sure, but those functions are not template functions. They're ordinary
member functions of a template class.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:
>[snip]
> I think there are ways to make template virtual functions work.  In
> the virtual table, store whether the function is a non-template or
> template, and if it is a template, store template argument
> information.  With the new implementation, non-template virtual
> functions would be as fast as before!  This is because the compiler
> knows at compile time whether the virtual function is a template or
> not, so it can take steps to call it appropriately.

 Sorry, I'm not sure what you mean here.  When you say that non-template
virtual functions would be as fast as before, do you mean that the
template virtual functions will be slower because some kind of look up
will be done at runtime? But wouldn't you still have to resolve the
function address in the child class vtable? How can that be done at
runtime? Will each class have somekind of invisible lookup that all it's
children will have?  What about multiple and/or virtual inheritence?
>
> If there's sufficient demand for this feature, it may appear in the
> next standard.
 Hmmm, Ok, I'll ask; Anyone else out there who would like this?

   And, does getting it in the standard mean that it will be in the
compiler that I'm using too? ;)
>
> [snip]
LR.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7f6de0$t1t$1@nnrp1.dejanews.com>,
  "AllanW {formerly AllanW@my-dejanews.com}" <allan_w@my-dejanews.com> wrote:
> In article <7f374r$1im$1@earth.superlink.net>,
>   lruss@superlink.net wrote:
> [snip]
>
> A template function represents a large number of functions; we don't
> know how many until every instanciation has been created. Therefore
> we cannot know until link time how many entries to allocate in the
> vtable.
So, could this be done by adding a third step in between the compilation link?
Or making the linker _much_more_ sophisticated? I know that it would be
difficult.
>
> See D&E for more details on how the vtable works.
> [snip]
D&E?  Sorry, I'm not familiar with that.
LR.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

There may have been a slight misunderstanding on this.
I now believe the original posted question referred to
virtual template member functions, not virtual functions
of template classes. I took it to mean the latter, when
he probably meant the former.

Paul



>   >Could someone please tell me the reasoning behind
>   >not allowing virtual template functions?
>
>Since when aren't template functions allowed to be
>virtual? Template member functions of classes can't
>be virtual (14.5.2.3); this latter limitation makes
>sense, if you think about how virtual functions are
>implemented.
>
>The standard nowhere explicitly says template functions
>can't be virtual. It does refer to virtual template
>functions in a number of places (14.7.1.7, 14.7.1.10).
>It makes sense that a template can have virtual functions
>if you think about how virtual functions are implemented.
>It just requires some compiler/linker smarts to be
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
Could someone please tell me the reasoning behind not allowing virtual
template functions?
TIA.
LR.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

LR wrote:
>
> Hi,
> Could someone please tell me the reasoning behind not allowing virtual
> template functions?
> TIA.
> LR.

The problem with something like:

struct AA {
 template <class C> virtual void g(C);
};

is that g() doesn't represent a single function, but rather an infinite
set of possible functions. In a typical implementation of C++, the
vtable for struct AA would have to have a different entry for each such
function. An infinitely long vtable is a bit of a problems!

The obvious alternative would be to provide entries only for the
versions of g that are actually instantiated, but such an implementation
would have to defer the assignment of vtable indices to those functions
until the program is actually linked, making it a lot more complicated.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7f374r$1im$1@earth.superlink.net>,
  lruss@superlink.net wrote:
> Hi,
Hi!

> Could someone please tell me the reasoning behind not allowing virtual
> template functions?

The common implementation of virtual functions requires the compiler to
create an entry in the "vtable" (or "Virtual Table") for every function
that the program possibly might call.

A template function represents a large number of functions; we don't
know how many until every instanciation has been created. Therefore
we cannot know until link time how many entries to allocate in the
vtable.

See D&E for more details on how the vtable works.

----
Allan_W@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 15 Apr 99 13:32:16 GMT, LR <lruss@superlink.net> wrote:

>Could someone please tell me the reasoning behind not allowing virtual
>template functions?

The normal implementation of virtual pointers and virtual tables would
be much more difficult.  Currently, if a class X has 8 virtual
functions, its virtual table has 8 pointers to functions.  But now if
one of these virtual functions is a template virtual function, then
the virtual table has 7+inifinity pointers to functions.

I think there are ways to make template virtual functions work.  In
the virtual table, store whether the function is a non-template or
template, and if it is a template, store template argument
information.  With the new implementation, non-template virtual
functions would be as fast as before!  This is because the compiler
knows at compile time whether the virtual function is a template or
not, so it can take steps to call it appropriately.

If there's sufficient demand for this feature, it may appear in the
next standard.


--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]