Covariant, Templatized Virtual Copy Constructors

8 June 2009 @ 22:39
 in Programming

One problem that programmers new to C++ often run into when they begin to write non-trivial programs is that of slicing.

In object-oriented programming, a subclass often holds more information than its superclass. Thus, if we assign an instance of the subclass to a variable of type superclass, there is not enough space to store the extra information, and it is sliced off.

The simple way to avoid slicing is to avoid making copies. Simply pass polymorphic objects around by reference (or by pointer) rather than by value, and one never has to worry about slicing. But sometimes the need to copy is unavoidable. In particular, when the need arises to make a copy of a derived object and all you have is a base pointer, things get hairy. How do you know which derived class the pointer’s target really belongs to, in order to make a proper, deep, non-sliced copy?

Fortunately, this problem has a well-known solution pattern called the virtual copy constructor idiom. One implements a virtual clone() method that makes a proper deep, non-sliced copy. There’s nothing wrong with this idiom, but it does entail the inelegance of having to repeat near-identical code for the clone() method in each derived class.

C++ programmers encountering this pattern for the first time often get the bright idea that this code can be centralized through the use of templates. Doing this while maintaining all the advantages of a non-templatized virtual copy constructor turns out to be much trickier than it first appears. This post will explain the problem, and how to do something that I have not yet found described on the Internet: implement the virtual copy constructor idiom using templates without sacrificing covariance.

First, let’s take a look at a simple, straightforward use of the virtual copy constructor idiom

  1. class Base
  2. {
  3.   public:
  4.   Base() {};
  5.   Base(const Base& copy) {};
  6.   virtual Base* clone() const = 0;
  7. };
  8.  
  9. class Derived : public Base
  10. {
  11.   public:
  12.   Derived() {};
  13.   Derived(const Derived& copy) : Base(copy) {};
  14.   virtual Derived* clone() const
  15.     { return new Derived(*this); };
  16. };

(Virtual destructors, while extremely necessary in real code like this, have been omitted for space). This allows a proper deep copy to be made in this situation:

  1. void foo(const Base* b)
  2. {
  3.   Base* b_copy = b->clone();
  4.   // etc
  5. }

Here, b_copy will point to an object of whatever Base-derived class b originally pointed to, and no information will be sliced.

Note something that might seem peculiar about the signature of the clone() method. In Base it is declared to return a Base*, but in Derived it is declared to return a Derived*. This is made possible by a feature of C++ called covariant return types. Without these, the following would not be possible, even though it is obviously desirable.

  1. Derived d;
  2. Derived* d2 = d.clone();

So now to the question of how we implement clone() in a generic way that does not require its implementation to be repeated in each derived class. This can be done using a templatized Cloneable mix-in class.

  1. template <typename B, typename T> class Cloneable
  2. {
  3.   public:
  4.   virtual B* clone() const
  5.     { return new T(static_cast<const T&>(*this)); }
  6. };

Now, all Derived has to do is inherit from Cloneable<Base, Derived> in addition to Base directly, and the clone() method is automatically added

  1. class Base
  2. {
  3.   public:
  4.   Base() {};
  5.   Base(const Base& copy) {};
  6.   virtual Base* clone() const = 0;
  7. };
  8.  
  9. class Derived : public Base, public Cloneable<Base, Derived>
  10. {
  11.   public:
  12.   Derived() {};
  13.   Derived(const Derived& copy) : Base(copy) {};
  14. };

You can go further by defining a purely abstract ICloneable interface and having Base and Cloneable both inherit virtually from it, but we’ll save on complexity and avoid that here.

The practice of a derived class inheriting from a templatized class where the derived class itself is one of the template arguments is known as the curiously-recurring template pattern. This works great, except for one thing – we’ve lost covariancy.

  1. Derived d;
  2. Derived* d2 = d.clone(); // Doesn’t work anymore
  3. Derived* d2 = static_cast<Derived*>(d.clone()); // Works, but ugly!

If you don’t really care about this, then the above implementation of the virtual constructor idiom is by far the cleanest solution to the slicing problem. But a lack of covariancy in the clone() method pretty annoying not to have in a lot of cases, so you would be right to want it back.

As you might guess, the obvious solution of defining the Cloneable mix-in as

  1. template <typename T> class Cloneable
  2. {
  3.   public:
  4.   virtual T* clone() const
  5.     { return new T(static_cast<const T&>(*this)); }
  6. };

doesn’t work, otherwise we would have done that in the first place. The error you will get if you try this is that the compiler will complain that it is illegal override clone() returning Base* with clone() returning Derived*. That seems odd, since we did that successfully in the very first non-templatized example.

The reason why this doesn’t work has to do with the “timing” involved in how the curiously-recurring template pattern works. In short, when we declare Derived to derive from Cloneable<Derived>, the compiler doesn’t necessarily know that Derived also derives from Base and so can’t be sure that covariancy between Base* and Derived* is legal.

In order to get around this – and this is, from what I can tell, the novel part of this post – we must instead add the clone() method after we have already defined a complete Derived class that is fully recognizable as a subclass of Base. We do this by inverting the mixin pattern. Instead of having a Derived inherit from a Cloneable, we instead have a Cloneable class inherit from a Derived. Or, to be more generic, we define a templatized Cloneable class that can inherit from any copy-constructable class.

  1. template <typename T>
  2. class AbstractCloneable : public T
  3. {
  4. public:
  5.   AbstractCloneable() {};
  6.   AbstractCloneable(const T& copy) : T(copy) {};
  7.   virtual ~AbstractCloneable() {};
  8.  
  9.   virtual AbstractCloneable<T>* clone() const = 0;
  10. };
  11.  
  12. template <typename T>
  13. class Cloneable : virtual public AbstractCloneable<T>
  14. {
  15. public:
  16.   Cloneable() {};
  17.   Cloneable(const T& copy) : AbstractCloneable<T>(copy) {};
  18.   virtual ~Cloneable() {};
  19.  
  20.   virtual Cloneable<T>* clone() const
  21.     { return new Cloneable<T>(static_cast<const T&>(*this)); }
  22. };

The AbstractCloneable class exists so that we can also use this pattern on abstract base classes that cannot be directly instantiated, as the clone() method’s implementation requires.

Now, instead of having Derived inherit from Base and from Cloneable<Derived> we invert the pattern and define an intermediate Derived_ class that inherits from Base, and then use a typedef to make Cloneable<Derived_> masquerade as Derived. We also do this analogously with Base and AbstractCloneable.

  1. class Base_
  2. {
  3. protected:
  4.   Base_() {};
  5.   Base_(const Base_& copy) {};
  6. };
  7.  
  8. typedef AbstractCloneable<Base_> Base;
  9.  
  10. class Derived_ : public Base
  11. {
  12. protected:
  13.   Derived_() {};
  14.   Derived_(const Derived_& copy) : Base(copy) {};
  15. };
  16.  
  17. typedef Cloneable<Derived_> Derived;

If you don’t like the appended-underscore convention, you can use whatever convention of your own you like, or even a separate namespace.

Covariancy is accepted by the compiler in this case because the initially-declared return type of clone() is AbstractCloneable<Base_>, and the return types of all overrides are types that are fully and unambiguously defined to be subclasses of AbstractCloneable<Base_> before being used as template arguments.

This implementation conquers the problem we set out to solve: we now have a way to add virtual copy constructors to a class hierarchy while avoiding re-implementing the clone() method for each derived class, and without sacrificing covariancy. All you have to do is add a typedef after each derived class. This is quite convenient, assuming you don’t mind too much the slight obfuscation of class names involved in using this method. With the above pattern, all of the following work

  1. Derived d;
  2. Derived* d2 = d.clone();
  3. Base* b_d = &d;
  4. Base* b_d2 = b_d->clone();
  5. Base* b_d3 = d.clone();

However, there is a large caveat that you may have noticed. Due to the the inversion of the inheritance hierarchy around the cloning mixins, we have completely lost the ability to construct derived objects using anything but the default constructor. If you need to construct a Derived (which is really a Cloneable<Derived_>) and pass an argument to the Derived_ constructor, you cannot. Therefore, this pattern is completely inappropriate unless you are using a factory pattern to construct your derived objects, and the factory is aware of the quirky type hierarchy. Fortunately, using a factory pattern is quite common in cases where one would run into this problem, so this restriction does not entirely defeat the point of this exercise. [Ed: you may want to read the addendum to this article that I posted, which further addresses this issue.]

Whether this new pattern is useful or not is debatable. It adds a fair bit of complexity and obfuscation in order to eliminate a relatively small amount of code duplication. It may be more useful if the code necessary to clone an object were for some reason more complex than simply calling a copy constructor, but I cannot immediately think of a situation in which this might be the case. Nevertheless, the above demonstrates that covariant, templatized virtual copy constructors are at least possible in C++ under a not-unreasonably-restrictive set of circumstances.

5 Comments »

  1. [...] thought of a quick addendum to Monday’s article on covariant, templatized copy constructors. The end of that article said [T]here is a large caveat that you may have noticed. Due to the the [...]

    Pingback by No Factories Necessary Nerdland — 12 June 2009 @ 05:08

  2. Very nice summary of a recurring problem!

    But wouldn’t it be possible to keep covariance by simply adding a second
    template parameter with the base type to the cloneable class template?

    Here is an example taken from [1]:

    template <typename Derived, typename Base>
    class clonable : public Base
    {
    public:
        Base* clone() const
        {
            return new Derived(static_cast<const Derived&>(*this));
        }
    }
    
    class graphic
    {
    public:
        virtual graphic* clone() const = 0;
    };
    
    class rectangle : public cloneable<rectangle, graphic>
    {
    public:
        rectangle(const rectangle &);
        ...
    }; 
    
    class ellipse : public cloneable<ellipse, graphic>
    {
    public:
        ellipse(const ellipse &);
        ...
    };
    

    Another benefit is that it removes redundancy in the class inheritance
    definition. That is,

    class Derived : public Base, public Cloneable<Base, Derived>
    

    becomes

    class Derived : public Base, public Cloneable<Base, Derived
    

    in your example.

    [1] http://www.two-sdg.demon.co.uk/curbralan/papers/accu/CloneAlone.pdf

    Comment by Matthias Vallentin — 13 July 2009 @ 18:23

  3. To complete my earlier post, here is a small compiling example:

    template <typename Derived, typename Base>
    class cloneable : public Base
    {
    public:
        Base* clone() const
        {
            return new Derived(static_cast<const Derived&>(*this));
        }
    };
    
    class graphic
    {
    public:
        graphic(const graphic& rhs)
        {
        }
    
        virtual graphic* clone() const = 0;
    };
    
    class rectangle : public cloneable<rectangle, graphic>
    {
    public:
        rectangle()
          : cloneable<rectangle, graphic>(*this)
        {
        }
    
        rectangle(const rectangle& rhs)
          : cloneable<rectangle, graphic>(rhs)
        {
        }
    };
    
    class square : public cloneable<square, rectangle>
    {
    public:
        square()
          : cloneable<square, rectangle>(*this)
        {
        }
    
        square(const square& rhs)
          : cloneable<square, rectangle>(rhs)
        {
        }
    };
    
    int main()
    {
        graphic* r = new rectangle;
        graphic* rc = r->clone();
    
        graphic* s = new square;
        graphic* sc = s->clone();
    
        delete r;
        delete rc;
        delete s;
        delete sc;
    
        return 0;
    }
    

    Hope this helps,

    Matthias

    Comment by Matthias Vallentin — 13 July 2009 @ 19:53

  4. Thanks for the comments, Matthias. What you posted is indeed a bit more elegant for the case of simple virtual copy construction, since you don’t have to inherit Base directly in addition to Cloneable.

    It doesn’t, however, provide covariancy. In this context, “covariant” means that if have an object whose static (aka compile-time) type is Derived, you should be able to call clone() on it and get back a Derived*, not a Base*.

    Doing this is simple if you build each class by hand, but it gets trick with templates because the compiler does not know about the inheritance relationship between Base and Derived when it is instantiating Cloneable<Base, Derived>, so it won’t let you have Cloneable::clone() return a Derived*, which is what you would need to have covariancy, because it doesn’t know that that is legal.

    Try changing the return type of Cloneable::clone() to Derived*, in your example and see how the compiler complains.

    Comment by Tyler McHenry — 13 July 2009 @ 21:43

  5. [...] Covariant, Templatized Virtual Copy Constructors Nerdland [...]

    Pingback by Java Tutorial : The super and this Keywords – Rocking Team | Java WebDev Insider — 19 March 2010 @ 16:43

RSS feed for comments on this post. TrackBack URL

Leave a comment