c++templatesabstract-syntax-treecovariance

Invalid covariant return type with class templates


This question is for a personal compiler project I've been working on. It takes an EBNF grammar and compiles it to C++, flex, and bison code that automatically builds an AST for the described grammar.

I'm using inheritance to model the generated AST, which has lead me to use pointers. I'm working on a non-nullable smart pointer class with inheritance similar to the AST.

For example, if I have this AST inheritance model:

Node
├── Terminal
└── Nonterminal
    ├── Expression
    │   ├── Operator
    │   │   ├── Binary
    │   │   │   ├── Add
    │   │   │   └── Multiply
    │   │   └── Unary
    │   └── FunctionCall
    └── Statement
        └── Conditional
            ├── Loop
            │   ├── For
            │   └── While
            ├── Select
            └── If

The smart pointer class inheritance model would look like this:

Pointer<Node>
├── Pointer<Terminal>
└── Pointer<Nonterminal>
    ├── Pointer<Expression>
    │   ├── Pointer<Operator>
    │   │   ├── Pointer<Binary>
    │   │   │   ├── Pointer<Add>
    │   │   │   └── Pointer<Multiply>
    │   │   └── Pointer<Unary>
    │   └── Pointer<FunctionCall>
    └── Pointer<Statement>
        └── Pointer<Conditional>
            ├── Pointer<Loop>
            │   ├── Pointer<For>
            │   └── Pointer<While>
            ├── Pointer<Select>
            └── Pointer<If>

My goal is to have a virtual clone method for each type of AST node that returns a smart pointer to its own type. I want to use these methods for making a copy-constructor. A binary expression (like Add for example) would have two operands, both of which would be Pointer<Expression>. In order to define a copy-constructor for Add, I need to be able to copy a virtually-bound Expression, or any Node for that matter. The class Node would a define virtual method like so:

class Node {
public:
  virtual Pointer<Node> clone() const = 0;
};

which would be overriden like so:

class Token : public Node {
public:
  Pointer<Token> clone() override;
};

so I could do this:

int main() {
  Pointer<Token> token = Pointer<Token>::New();
  Pointer<Node> tokenDynamic = new Pointer<Token>::New();

  Pointer<Token> tokenClone = token.clone();
  Pointer<Node> tokenDynamicClone = tokenDynamic.clone();
}

and I am running into an issue.

I've tried to simplify as much as possible into this example, and I still can't get it to work:

#include <memory>
#include <tr2/type_traits>

class Base;
class Derived;

template<typename T>
class Template : public Template<typename T::Parent> {};

template<>
class Template<Base> {};

class Base {
public:
  virtual std::string name() const { return "Node"; }
  virtual Template<Base> clone() const = 0;
};

class Derived : public Base {
public:
  using Parent = Base;

  std::string name() const { return "Token"; }
  Template<Derived> clone() const override { return Template<Derived>(); }
};

template<typename T>
using base_t = typename std::tr2::bases<T>::type::first::type;

int main()
{
  auto base = Template<Base>();
  auto derived = Template<Derived>();
  base = Template<Derived>();
  static_assert(std::is_same_v<Template<Base>, base_t<Template<Derived>>>);
}

I thought that virtual functions could be overridden with covariant/narrowing return types. The static_assert in the above code does not fail, meaning that Template<Derived> does inherit Template<Base>. However, the compiler fails with these messages:

./test2.cpp:24:21: error: invalid covariant return type for ‘virtual Template<Derived> Derived::clone() const’
   24 |   Template<Derived> clone() const override { return Template<Derived>(); }
      |                     ^~~~~
./test2.cpp:16:26: note: overridden function is ‘virtual Template<Base> Base::clone() const’
   16 |   virtual Template<Base> clone() const = 0;
      |                          ^~~~~


Solution

  • Only functions that return (built-in) pointers or references may have covariant return types.

    [class.virtual] If a function D::f overrides a function B::f, the return types of the functions are covariant if they satisfy the following criteria:

    • (8.1) — both are pointers to classes, both are lvalue references to classes, or both are rvalue references to classes

    Not all is lost however. It is possible to simulate covariance using the non-virtual interface idiom. The technique is described in several SO questions and answers so I won't repeat it here. For more information, see this.

    On an unrelated note, it is probably not a good idea to make smart pointers inherit one another. If you only need this for covariant return types, you can safely get rid of this inheritance and probably of the entire smart pointer template, and use std::shared_ptr or std::unique_ptr instead.