Шаблонная виртуальная функция

#cpp #cpp11

Поясните, пожалуйста, почему нельзя создать виртуальную шаблонную функцию?

Нашел следующее объяснение:


  Member function templates cannot be declared virtual. This constraint
  is imposed because the usual implementation of the virtual function
  call mechanism uses a fixed-size table with one entry per virtual
  function. However, the number of instantiations of a member function
  template is not fixed until the entire program has been translated.
  Hence, supporting virtual member function templates would require
  support for a whole new kind of mechanism in C++ compilers and
  linkers. In contrast, the ordinary members of class templates can be
  virtual because their number is fixed when a class is instantiated


То есть теоретически такой функционал реализовать можно, но это потребует серьезного
изменения принципов работы существующих компилятор и линковщиков. Или есть и другие
причины?
    

Ответы

Ответ 1

Простой ответ:

В С++ шаблон функции не является функцией, поэтому шаблон не может быть виртуальным.

В C#/Java/etc используются не шаблоны, а generics. Generic-функция это (одна) функция,
поэтому там такой проблемы нет.

Сложный ответ:

В С++ виртуальные функции сделаны так, что их количество прописано в определении
базового класса.
Это позволяет присвоить функции некоторый индекс в базовом классе и быстро находить
ее по этому индексу.  

struct Base {            
  func_t* vft;  // скрытый член класса - массив виртуальных функций
  virtual void f();   
};                    

Base* x = new Derived;         
x->f();
// компилируется в
x->vft[0]();


Если шаблоны будут виртуальными, то вместо перечисления функций в базовом классе
надо искать все подстановки шаблона при вызовах функции.
Для этого вместо индексов надо использовать имена, и искать эти имена в хеш-таблице.

struct Base {            
  hash_map vft;  // скрытый член класса - хеш-таблица виртуальных функций
  template virtual void f();   
};                    

Base* x = new Derived;         
x->f();
// компилируется в
x->vft["f"]();


Скорость вызова значительно упадет, т.к. надо будет разрешать коллизии. 

Можно использовать идеальную хеш-функцию (без коллизий).

struct Base {            
  func_t* vft;  // скрытый член класса - массив (sic!) виртуальных функций
  virtual void f();   
};                    

Base* x = new Derived;         
x->f();
// компилируется в
x->vft[ideal_hash("f")]();
// ideal_hash(name) выдает индекс массива, без коллизий


Но из-за динамической линковки (.so/.dll) весь исходный код программы недоступен,
и при каждой загрузке SO/DLL надо останавливать всю программу, менять хеш-функцию и
перестраивать все таблицы, чтобы учитывались типы, которые добавились в этой SO/DLL.



Использование JIT-компилятора может заменять виртуальные вызовы на обычные, и тогда
никаких проблем с производительностью вызова не будет.

// вместо x->f(); генерируется
x->Derived::f();
// если доказано что тут может быть только Derived


Но девиртуализация работает только если количество классов мало, и на данный момент
эффективных JIT-компиляторов нет. (Те что есть, например в LLVM, не показывают хороших
результатов.)


Ответ 2

Это невозможно сделать в рамках существующих реализаций С++. Так как виртуальные
функции реализованы через таблицы указателей на них, компилятор должен иметь возможность
сгенерировать функцию при ее определении - чтобы получить указатель.

Так как код шаблонных функций генерируется только при инстанциировании шаблона, компилятор
не может заполнить таблицу - у него просто нет указателя.

Шаблонные виртуальные функции потребовали бы полного пересмотра подхода к полиморфизму,
и для полной реализации потребовали бы "исполняющей машины" - примерно как Java или С#. 

Простой пример (не компилирующийся, естественно):

// file base.h
struct Base {
    template 
    virtual void foo(T ) { }
};

// file derived.h
#include 
struct Derived : Base {
   template 
   virtual void foo(T ) { };
};

// file foo.cpp 
#include 
void foo(Base* b) {
    base->foo(42);
}

// file main.cpp
#include 
int main() {
    Base* d = new Derived;
    foo(d);
}


В приведенном примере очевидно, что компилятор не может сформировать правильный вызов
функции foo().

В комментариях приводится такой аргумент - "А давайте заставим пользователя включать
все заголовки всех потомков перед использованием шаблонной функции, а компилятор генерировать
все таблицы виртуальных методов для всего дерева base которое он увидел in-place".
Но у переданного foo() указателя уже должны быть сформированная таблица. Переформировать
ее уже не получится!