std::polymorphic_value + Duck Typing = Type Erasure

17 Jan 2020 by Jonathan

I recently had an insight about type erasure that I wanted to share. Type erasure is a combination of two techniques working together to achieve both polymorphism and value semantics: std::polymorphic_value, a proposed standard library type, and duck typing.

Let’s take the example I’ve used back in my visitor pattern post again: We want to model the AST of some markup language, like Markdown. It contains text, emphasis, code blocks, and so on. We parse the input, create the AST, and then need to convert it to HTML.

A natural approach of modelling it is with a class hierarchy: We have a node base class and derived classes like document, paragraph, text, emphasis etc. Some classes are containers of child nodes, like document, some are not, like text.

class node
{ 
public:
    virtual ~node() = default;
    virtual std::string render_html() const = 0;
};

class text final : public node
{
public:
    std::string render_html() const override
    {
        return sanitize_html(content_);
    }

private:
    std::string content_;
};

class document final : public node
{
public:
    std::string render_html() const override
    {
        std::string result = "<head>…</head>\n<body>\n";
        for (auto& child : children_)
            result += child->render_html(); 
        result += "</body>\n";
        return result;
    }

private:
    std::vector<std::unique_ptr<node>> children_;
};

…

I’ve followed my advice of making non-base classes final. This prevents various slicing issues.

This works well enough, and is similar to what I’ve done in standardese.

However, there are two things I don’t like.

Problem: Lack of Value Semantics

Scott Meyers once said that you should “do as the ints do” – write classes that behave like ints. And this makes a lot of sense, as the language makes it very convenient to work with int: You can just create them on the stack, pass them around, create a copy that is a completely separate entity, classes containing ints can follow the rule of zero, etc.

int do_something(int a, int b)
{
    int tmp = a + b;
    int copy = tmp;
    ++tmp;
    // copy is unaffected
    return tmp + copy;
}

Most standard library classes follow this advice, for example std::string. As such, all the same principles apply to it as well:

std::string do_something(std::string a, std::string b b)
{
    std::string tmp = a + b;
    std::string copy = tmp;
    tmp += "world";
    // copy is unaffected
    return tmp + copy;
}

This ability – to write classes that behave like built-in types – is one of the most important features of C++.

However, our class hierarchy does not behave like this! We can’t create a variable holding some type derived from node on the stack, we need to put it on the heap, requiring memory management. We can’t just pass them around (slicing), we need to pass references or (smart) pointers around. We can’t just copy them to get a separate entity, at most we can do reference counting. Classes containing arbitrary derived types of node, like our document, can’t follow the rule of zero, because of the additional burden of lifetime management for the pointer or reference to the actual object. For example, we would need to write our own copy constructor of document.

This makes them a bit awkward to use. It would be better, if they behaved just like ints do.

Solution: Value Semantic Wrapper

We can – of course – solve this problem by an extra layer of indirection. Instead of manually passing nodes around, we create a node_value that stores a heap-allocated node, but wraps it and provides value semantics.

At the most basic level, it just contains a std::unique_ptr again:

class node_value
{
public:
    template <typename T>
      requires std::is_base_of_v<node, T>
    node_value(T obj)
    : ptr_(std::make_unique<T>(std::move(obj))
    {}

    node* operator->() const
    {
        return ptr_.get();
    }
    node& operator*() const
    {
        return *ptr_;
    }

private:
    std::unique_ptr<node> ptr_;
};

We have a constructor that takes any object derived from node (constrained by a requires) and puts it on the heap. Then we provide the pointer like access that gives us a node. So far, this is not different from a plain std::unique_ptr, so what gives?

The trick is, we can now write a copy constructor if we add a clone() function to our class hierarchy:

class node
{ 
public:
    virtual std::unique_ptr<node> clone() const = 0;
};

class text final : public node
{
public:
    std::unique_ptr<node> clone() const override
    {
        return std::make_unique<text>(content_);
    }

private:
    std::string content_;
};

class document final : public node
{
public:
    std::unique_ptr<node> clone() const override
    {
        std::vector<std::unique_ptr<node>> children;
        for (auto& c : children_)
            children.push_back(c->clone());
        return std::make_unique<document>(std::move(children));
    }


private:
    std::vector<std::unique_ptr<node>> children_;
};

…

This clone() function is basically a virtual copy constructor. Then we can implement copy for node_value:

class node_value
{
public:
    node_value(const node_value& other)
    : ptr_(other->clone())
    {}

    node_value& operator=(const node_value& other)
    {
        ptr_ = other->clone();
        return *this;
    }

private:
    std::unique_ptr<node> ptr_;
};

And now, while node still does not behave like ints, node_value does: we can freely create it on the stack, copy it around, and so on. We have wrapped a type that does not provide value semantics into one that does - but at the cost of boilerplate.

Luckily, there is a proposal for basically a generic node_value: std::polymorphic_value. A std::polymorphic_value<node> behaves exactly like our node_value.

std::polymorphic_value<node> n = …;
auto html = n->render_html();

std::polymorphic_value<node> copy = n;
…

It is even able to perform correct copies without the need for a clone() member function! You can find a reference implementation here: github.com/jbcoe/polymorphic_value.

Problem: No Implicit Extensibility

The second problem with our node class hierarchy is a common one for all class hierarchy: You need to be aware of the base class in order to take part in it.

What if some third party library just happens to provide a class with a render_html() function? We can’t use it, because it doesn’t derived from node.

Granted, this is probably unlikely in our example, but bear with me.

Solution: Duck Typing

We can solve it by providing a wrapper, that takes an arbitrary object that happens to provide a render_html() function, but inherits from node:

template <typename T>
class node_like final : public node
{
public:
    node_like(T obj)
    : obj_(std::move(obj))
    {}

    // We can provide cloning by simply using T's copy constructor,
    // if it is still required.
    std::unique_ptr<node> clone() const override
    {
        return std::make_unique<node_like<T>>(obj_); 
    }

    std::string render_html() const override
    {
        return obj_.render_html();
    }

private:
    T obj_;
};

That way, an arbitrary type can be part of the node hierarchy.

Note that we’re able to implement clone() by forwarding to T’s copy constructor. The same trick is also done by polymorphic_value: when storing a T, we remember the copy constructor and invoke it on copy.

Combination: Type Erasure

What happens when we combine node_value and node_like?

Well, given node_like, text, document, and so on don’t really need to inherit from node anymore - they just need to be wrapped in node_like. And because we only store nodes in a node_value, we can let it do all of the wrapping:

class node_value
{
public:
    template <typename T>
    node_value(T obj)
    : ptr_(std::make_unique<node_like<T>>(std::move(obj)))
    {}

    // dereference and copy as before

private:
    std::unique_ptr<node> ptr_;
};

At this point, our node_value can just handle any type that happens to provide a render_html() function. Now, do we really need to keep the node base class or node_like public? Functions that work with arbitrary nodes can just take node_value, and node_like is a mere wrapper required by node_value.

So we can go one step further and make the two classes implementation details of node_value. That also frees up the name node, so we can rename node_value to simply node. Instead of providing dereference, we just manually implement the interface node originally has - because that’s what we can do with node anyway!

class node // formerly node value
{
    class base // formerly node
    {
    public:
      virtual ~base() = default;
      virtual std::unique_ptr<base> clone() const = 0;
      virtual std::string render_html() const = 0;
    };

    template <typename T>
    class wrapper final : public base // formely node_like
    {
    public:
        wrapper(T obj)
        : obj_(std::move(obj))
        {}

        std::unique_ptr<base> clone() const override
        {
            return std::make_unique<wrapper<T>>(obj_); 
        }
        std::string render_html() const override
        {
            return obj_.render_html();
        }

    private:
        T obj_;
    };

public:
    template <typename T>
    node(T obj)
    : ptr_(std::make_unique<wrapper<T>>(std::move(obj)))
    {}

    node(const node& other)
    : ptr_(other.ptr_->clone())
    {}

    node& operator=(const node& other)
    {
        ptr_ = other.ptr_->clone();
        return *this;
    }

    std::string render_html() const
    {
        return ptr_->render_html();
    }

private:
    std::unique_ptr<base> ptr_;
};

Now our text and document classes are just regular classes with a render_html() function:

class text 
{
public:
    std::string render_html() const
    {
        return sanitize_html(content_);
    }

private:
    std::string content_;
};

class document
{
public:
    std::string render_html() const
    {
        std::string result = "<head>…</head>\n<body>\n";
        for (auto& child : children_)
            result += child.render_html(); 
        result += "</body>\n";
        return result;
    }

private:
    std::vector<node> children_;
};

No need to inherit from anything, no need to store other nodes in a pointer, copy works out of the box and so on.

By combining a value semantics wrapper and duck typing, we no longer have a class hierarchy requiring the awkward use of smart pointers, but instead simple types with value semantics. In addition, it works with every type we throw at it, as long as it has the required function. This makes extension very easy.

This technique is type erasure – it combines polymorphic behavior, value semantics, and duck-typing. std::function uses type erasure; the required interface is the operator() (and copy constructor). std::any also provides type erasure; it only requires copy constructors and a destructor. And even std::polymorphic_value does type erasure to provide copies.

The only downside to type erasure the boilerplate: We need to create a base class with the required virtual functions, a templated wrapper that just forwards, and then a public interface forwarding to the base class – this is annoying. However, if the type is used often enough, it can be worth it. There are also libraries that use meta programming techniques to eliminate a lot of the boilerplate. And metaclasses can even eliminate it completely.

And even if you don’t use type erasure, consider using something like std::polymorphic_value instead: it gives you a lot of the benefits with no boilerplate whatsoever.