Type 'smudging' in C++

type_smudging.md

Setting the scene

Suppose we're building an animation library. It works like this: a scene consists of a tree of nodes. As each frame of the animation is processed, the scene is updated, then each node is rendered into an image. Those images are then layered to make a complete frame of animation. The process repeats for every frame.

Each node stores its children in some collection, say a std::vector:

struct node {
  //...
  vector<node> children;
};

We'd like for our scene to have different types of nodes -- perhaps a text_node and a shape_node. But we must store the nodes in a container (children), and C++ doesn't allow us to store different types in the same container. The natural solution is for text_node and shape_node to inherit from node. We then store pointers to node in children:

struct node {
  //...
  vector<shared_ptr<node>> children;
};

struct text_node : public node {};
struct shape_node : public node {};

Now we need to be able to render a node. One approach is to add a virtual render function to the node class and override it with specific rendering procdures for each subclass:

struct image {};

struct node {
  //...
  virtual image render() {
    // code for rendering a node
  }
  vector<shared_ptr<node>> children;
};

struct text_node : public node {
  virtual image render() override {
    // code for rendering a text_node
  }
};

struct shape_node : public node {
  virtual image render() override {
    // code for rendering a shape_node
  }
};

We can then render an entire scene by rendering the nodes recursively, starting at the root node:

image recursive_render(shared_ptr<node> n) {
  image output = n->render();
  for (auto child : n->children) {
    image child_image = child->render();
    // layer child_image onto output...
  }
  return output;
}

image render_scene() {
  return recursive_render(root);
}

This approach works, but it is limiting. What happens if we want to be able to render the scene in a couple of different ways, say color and grayscale? We could write separate color_render and grayscale_render methods in all of our node classes, but that quickly becomes tedious and unwieldy. We would need to make adjustments in many places in the code every time we wanted to change rendering systems (which method do we call in recursive_render, for instance?). It would be better store the rendering procedures outside of the nodes entirely, in separate renderer classes with suitable render overloads:

struct color_renderer {
  image render(node &n) {/* color-render a node... */}
  image render(text_node &n) {/* ... */}
  image render(shape_node &n) {/* ... */}
};

struct grayscale_renderer {
  image render(node &n) {/* grayscale-render a node... */}
  image render(text_node &n) {/* ... */}
  image render(shape_node &n) {/* ... */}
};

But then how do we write recursive_render? Since the render behavior depends on the type of the renderer, we could template the recursive_render function and pass it a RENDERER:

template <class RENDERER>
image recursive_render(shared_ptr<node> n, RENDERER r) {
  image output = r.render(n);
  for (auto child : n->children) {
    image child_image = r.render(*child);
    // layer child_image onto output...
  }
  return output;
}

But here we run into another problem. What happens if we recursive_render a text_node?

  color_renderer r{};
  shared_ptr<node> my_node = make_shared<text_node>();
  recursive_render(my_node,r); // calls r::render(node &), not r::render(text_node&)

We call the wrong overload of r::render. Why? The dynamic type of *my_node is text_node, but its static type is node. Overload resolution is done based on static types, not dynamic types. For polymorphism based on the dynamic type of the node, we need to use virtual functions. But a virtual function call is selected based on the type of the object on which the function is called. So our virtual render() function must be a member of node. Doesn't this put us back where we started, with the rendering information stuck in node?

Not if we are a little clever.

Templates + single dispatch

We place our virtual render() function back into node, but this time we implement it by calling RENDERER::render(*this):

template <class RENDERER>
struct node {
  //...
  virtual image render(RENDERER r) {
    r->render(*this);
  }
};

template <class RENDERER>
struct text_node : public node<RENDERER> {
  //...
  virtual image render(RENDERER r) override {
    r->render(*this);
  }
};

template <class RENDERER>
struct shape_node : public node<RENDERER> {
  //...
  virtual image render(RENDERER r) override {
    r->render(*this);
  }
};

template <class RENDERER>
image recursive_render(shared_ptr<node<RENDERER>> n, RENDERER r) {
  image output = n->render(r);
  for (auto child : n->children) {
    image child_image = child->render(r);
    // layer child_image onto output...
  }
  return output;
}

This approach works, but it's unfortunate that we need to template each node class. It makes the code a bit ugly because we'll need to supply a template argument every time we want to use nodes generically. Functions that take or return a node must be templated on the RENDERER type (see recursive_render above, for instance). Ditto for any container that stores nodes, any class with a node member, etc. Otherwise, those functions, containers, and classes would only support nodes with a particular renderer. Templating the nodes also prevents us from using different renderers on different nodes within a scene, since all children in the scene must have the same static type. It would be nice if we could template just the render() function, but C++ doesn't allow us to template virtual functions.

We'll illustrate some different techniques to try to address these issues. But first, you might be wondering what the term 'single dispatch' I used in the heading is about. It refers to the fact that a call to render() on a node reference requires only one use of C++'s virtual function dispatcher. Since node::render() is virtual, a call to render() on a node reference is dispatched to the appropriate subclass override at runtime.

color_renderer cr{};
shared_ptr<node> n = make_shared<text_node>();
n->render(cr)); // virtual function dispatcher invoked here

The appropriate function to call is determined on the basis of only one dynamic type - that of n. It happens that the implementation of text_node::render() depends on the static type of r, but virtual function dispatch is unnecessary for static polymorphism. So the call to n->render(cr) requires only 'single dispatch.'

Double Dispatch

One solution to the templating ugliness is a technique called "double dispatch," or, more accurately, simulated double dispatch via the visitor pattern. Using this approach, we supply a base renderer type from which color_renderer and grayscale_renderer inherit:

struct renderer {
  /* overloads of 'render' for all node types must be declared here */
  virtual image render(node&) = 0;
  virtual image render(text_node&) = 0;
  virtual image render(shape_node&) = 0;
};

struct color_renderer : public renderer {
  image render(node &n) override {/* color-render a node... */}
  image render(text_node &n) override {/* ... */}
  image render(shape_node &n) override {/* ... */}
};

// similar for grayscale_renderer...

struct node {
  //...
  virtual image render(renderer &r) {
    r->render(*this);
  }
};

struct text_node : public node {
  //...
  virtual image render(renderer &r) override {
    r->render(*this);
  }
};

// similar for shape_node...

image recursive_render(shared_ptr<node> n, renderer &r) {
  image output = n->render(r);
  for (auto child : n->children) {
    image child_image = child->render(r);
    // layer child_image onto output...
  }
  return output;
}

We call this approach 'double dispatch' because it requires two virtual-function dispatches. Suppose we call render as follows:

color_renderer cr{};
shared_ptr<node> n = make_shared<text_node>();
n->render(cr);

First, the dispatcher looks up the dynamic type of n, which is text_node. It finds an override of render in text_node itself, which it calls. Then, within text_node::render(r), the dispatcher encounters the call r->render(*this). Since renderer::render is also virtual, it looks up the appropriate override based on the dynamic type of r, which is color_renderer. It finds an override of render in color_renderer and calls it. The whole process takes two virtual dispatches, so we call it 'double dispatch.'

As promised, this approach eliminates the ugly templating. It has a significant shortcoming, though.

We are writing a library that provides general animation functionality. Let's put ourselves in the shoes of a user of the library for a moment. We don't want to mess with the inner workings of the library, but we want to make our own node types and procedures for rendering them. We try adding a custom_node type, with a custom_renderer that knows how to render it.

#include "the_animation_library.h" // header that contains node, renderer, etc

struct custom_node : public node {
  virtual image render(renderer r) override {
    return r.render(*this);
  }
};

struct custom_renderer : public color_renderer {
  virtual void image render(custom_node) {/* ... */}
};

This looks like it might work. But then we try actually making a custom_node and rendering it.

custom_renderer r{};
shared_ptr<node> n = make_shared<custom_node>();
n->render(r); // error!  no matching overload of 'render'

We get an error because the static type of n is a pointer to node, and node lacks an overload of render that takes an argument of type custom_renderer. If node had a matching virtual overload, even a deleted one, then virtual dispatch would find the desired override custom_node::render(custom_renderer). But since node has no matching overload at all, no virtual dispatch occurs. We could solve this problem by providing node with the necessary overload of render, but this would require that the user edit the included library header the_animation_library.h, possibly recompiling the library along the way. Yuck! The user should be able to the extend the library without editing its source.

To recap so far: templates + single dispatch does the job, but we want to avoid template ugliness. We can't use double dispatch because it destroys the encapsulation of the library. What next?

Type Erasure

What if we eliminate the node inheritance hierarchy altogether? Instead of text_node and shape_node subtypes of node, we define independent text and shape types. Then we store a pointer to the backing text or shape type in node, and provide our renderer types with methods for rendering text or shape objects.

struct text { // no inheritance
  // let's have a member that stores the text to be displayed
  string val;
};
struct shape {}; // no inheritance
struct node {
  unique_ptr<?> backing;  // oops!  what type should we point to?
  image render(renderer r) {
    r->render(*backing);
  }
  vector<node> children;
};

struct color_renderer {
  image render(text &);
  image render(shape &);
};

What type should backing point to? Let's make an abstract base class renderable_concept and wrap our types text and shape into subclasses:

struct renderable_concept {
  virtual image render();
};

struct wrapped_text : public renderable_concept {
  text w;
  virtual image render() override {
    // ?
  }
};

struct wrapped_shape : public renderable_concept {
  shape w;
  virtual image render() override {
    // ?
  }
};

struct node {
  unique_ptr<renderable_concept> p_renderable;
  image render() {
    p_renderable->render();
  }
  // ....
};

But how do we implement the render methods? We need to choose a renderer type, but we can't pass it as a parameter to render without (a) templating our renderable_concept, which would require templating our type node, which we are trying to avoid, or (b) deriving our renderer types from a common base, which leads us down the double dispatch path. Instead, we could make separate subclasses for each combination of wrapped type and renderer type:

struct wrapped_text_color : public renderable_concept {
  text w;
  color_renderer r;
  virtual image render() override {
    return r->render(w);
  }
};

struct wrapped_shape_color : public renderable_concept {
  shape w;
  color_renderer r;
  virtual image render() override {
    r->render(w);
  }
};

struct wrapped_text_grayscale : public renderable_concept {
  text w;
  grayscale_renderer r;
  virtual image render() override {
    r->render(w);
  }
};

struct wrapped_shape_grayscale : public renderable_concept {
  shape w;
  grayscale_renderer r;
  virtual image render() override {
    r->render(w);
  }
};

This quickly becomes tedious. The number of structs we need to write is the product of the number of wrapped types and renderer types. Since all the wrapped structs follow the same format, we can describe all of them with a single template. Following the conventions of the type erasure idiom, we will call this template renderable_model.

template <class WRAPPED, class RENDERER>
struct renderable_model : public renderable_concept {
  WRAPPED w;
  RENDERER r;
  virtual image render() override {
    r->render(w);
  }
  // let's add a constructor, too:
  renderable_model(WRAPPED w_, RENDERER r_) : w(w_), r(r_) {}
};

Finally we need a means of storing a pointer to the desired renderable_model in our node class. We'll do so in a templated node constructor.

struct node {
  // ...
  template <class WRAPPED, class RENDERER>
  node(WRAPPED w, RENDERER r) :
    p_renderable(new renderable_model<WRAPPED, RENDERER>(w,r))
    {}
  // ...
};

This completes our sketch of a type-erasure approach to nodes and renderering. But why do we call it 'type erasure' anyway? Notice that a node actually stores a pointer to data of varying types. If we construct a node from a shape and a color_renderer, p_renderable points to an object whose dynamic type is renderable_model<shape,color_renderer> but whose static types is renderable_concept. If we construct a node from a text and a grayscale_renderer, p_renderable points to an object whose dynamic type is renderable_model<text,grayscale_renderer> but whose static type is still renderable_concept. Thus, after node construction, information about the underlying types text,shape,color_renderer, and grayscale_renderer is no longer present in the node itself. Those types have been erased. All a node knows is that it has a pointer to something that is renderable. It retains no knowledge of what the renderable thing is.

Type erasure solves the problems we have mentioned up to this point. It

• mantains separation of modeling of the scene (the node tree) and rendering procedures.
• avoids templating of nodes (only templating of node's constructor)
• allows for encapsulation of the library while preserving extensibility. A user of the library can make a custom_node as follows

struct custom_node {};
struct custom_renderer : public color_renderer {
  image render(custom_node &);
};
shared_ptr<node> n = make_shared<node>(custom_node{},custom_renderer{});

Unfortunately, type erasure introduces a new problem. Suppose we construct a node n from a text and a color_renderer:

shared_ptr<node> n = make_shared<node>(text{},color_renderer{});

Later, we want to update the string val stored in n.

n->val = "New string value!"; // oops!  node has no member val

It's impossible to do so! We erased the underlying type text. We have no good means of accessing the text object wrapped inside the renderable_model that n points to. If we want to be able to modify our nodes after construction, this is a significant problem.

Type Smudging

Our next and final stop is a technique that I will affectionately call 'type smudging.' The idea is to combine inheritance with type erasure in such a way that wrapped types aren't totally erased — just 'smudged' a bit.

The key idea is not to store a full wrapped object in renderable_model, but rather a pointer to the wrapped object:

template <class WRAPPED, class RENDERER>
struct renderable_model : public renderable_concept {
  WRAPPED *w;
  RENDERER r;
  virtual image render() override {
    r.render(*w);
  }
  renderable_model(WRAPPED *w_, RENDERER r_) : w(w_), r(r_) {}
};

Then we introduce two new constructors to our node type.

struct node {
  template <class WRAPPED, class RENDERER>
  node(WRAPPED *w_, RENDERER r_) :
    p_renderable(new renderable_model<WRAPPED,RENDERER>(w_,r_)) {}

  template <class RENDERER>
  node(RENDERER r_) : node(this,r_) {}

  image render() {return p_renderable->render();}
  vector<shared_ptr<node>> children;
  unique_ptr<renderable_concept> p_renderable;
};

The first constructor node(WRAPPED *w_, RENDERER r_) is nearly identical to the constructor from our type-erasure implementation. It just takes a pointer instead of a value. The second constructor node(RENDERER r_) is more interesting: when we construct a node n without giving it a wrapped pointer, the constructor supplies this as the wrapped pointer. That is, n's renderable_model points back to n itself!

Now we reinstate our inheritance hierarchy, as promised: text_node and shape_node both subclass node.

struct text_node : public node {
  template<class RENDERER>
  text_node(RENDERER r) : node(this,r) {}
};

struct shape_node : public node {
  template<class RENDERER>
  shape_node(RENDERER r) : node(this,r) {}
};

How do these new constructors work? Consider the following code:

color_renderer cr{};
shared_ptr<node> my_text_node = std::make_shared<text_node>(cr);
my_text_node->render();

The resulting call to text_node's constructor works as follows:

• the type of RENDERER is deduced to be color_renderer
• the base object node is constructed with the call node(&my_text_node,cr)
• within the call to node(WRAPPED *w_, RENDERER r_) the type of WRAPPED is deduced as text_node and the type of RENDERER is deduced as color_renderer. Thus the runtime type of *my_text_node.p_renderable is renderable_model<text_node,color_renderer>.

The call my_text_node.render() results in a call to cr.render(my_text_node) inside renderable_model::render(). Therefore, all we need to do is teach a color_renderer to render a text_node object:

struct color_renderer {
  image render(text_node &) {/*implementation*/};
  // other rendering methods...
};

This approach solves the problem we ran into with type erasure. As before, we construct a node n from a text and a color_renderer.

shared_ptr<text_node> n = make_shared<text_node>(color_renderer{});

But, unlike in our earlier type-erasure solution, we can easily access and update n's member val.

n->val = "New string value!"; // works!

The library remains encapsulated, but a user can still make custom_node and custom_renderer types easily, inheriting from library types as desired.

struct custom_node : public node {
  template<class RENDERER>
  custom_node(RENDERER r) : node(this,r) {}
};

struct custom_renderer : public color_renderer {
  image render(custom_node &) {/* implementation */}
};

Furthermore, nodes don't have to be templated as in the templates + single dispatch approach. Thus, we don't have to template containers that store nodes, or classes that have such containers as members.

struct scene { // look ma, no templates!
  node root;
};

And different nodes within a scene can be rendered with different renderers.

node root{color_renderer{}};
shared_ptr<node> tn = make_shared<text_node>(grayscale_renderer{});
shared_ptr<node> sn = make_shared<shape_node>(color_renderer{});
root.children = {tn,sn}; // ok

Complete code for the type smudging approach can be found here.

Summary

The selection of an appropriate rendering method depends on two types, the type of the node to be rendered and the type of the renderer.

With templates + single dispatch, both pieces of type information are encoded in any reference to a node. The type to be rendered is the (dynamic) type of the node itself, and the renderer type is stored in the nodes template parameter.

Type erasure erases the type and the address of both the wrapped object and the renderer; given a reference to a node, both the wrapped object and the renderer are completely inaccessible except implicitly through the the render function.

Type smudging erases the renderer's type and address, but it preserves the type and the address of the node to be rendered. I use the terminology 'smudge' to indicate that type and address information has been only partially erased. Given a reference to a node n, the renderer is inaccessible, but the wrapped object is n itself, so we have immediate access to it.