Polymorphism without Planning (under the hood)

Introduction

My previous article, Polymorphism without Planning, discussed how the OOTL (Object Oriented Template Library) uses a technique implemented by the BIL (Boost Interfaces Library) which is included with the OOTL release version 0.1. This left a lot of people curious about what was going on under the hood.

Background

The BIL allows any object that implements a set of functions which match those of a declared interface, to be referred to using a single type:

class Dog {
  public:
    const char* MakeSound() { return "woof"; }
};

class Duck {
  public:
    const char* MakeSound() { return "quack"; }
};

BOOST_IDL_BEGIN(IAnimal)
  BOOST_IDL_FXN0(MakeSound, const char*)
BOOST_IDL_END(IAnimal)

int main() {
  Dog dog;
  Duck duck;
  IAnimal animal = dog;
  puts(animal.MakeSound()); // prints woof
  animal = duck;
  puts(animal.MakeSound()); // prints quack
  return 0;
};

The question that I am asked frequently, is how in fact can we have statically typed interfaces in C++, without placing any extra information in the object?

Double-Width Pointers

In order to achieve any kind of dynamic dispatch, we require a function table lookup somewhere in our code, otherwise we wouldn't be able to have run-time polymorphism. The interface reference is then represented internally as a double width pointer; one pointer points to the object, while the other object points to a function table. This function table is created statically at compile-time using templates.

A function table is created for every class-to-interface type-cast in the code. This is done using template versions of the assignment operator and initializing constructor.

Creating Interfaces Reference Types by Hand

Dave Abrahams of Boost-Consulting.com posted the following code to comp.std.c++ on 2004-04-25 which was an improvement on my original proposal, and the technique used by the interface code generating tool HeronFront.

// a baz "interface"
class baz
{
 private:
    // forward declarations
    template <class T>
    struct functions;

 public:
    // interface
    template <class T>
    baz(T& x) : _m_a(&x), _m_t(&functions<T>::table)
    {}

    int foo(int x)
    { return _m_t->foo(const_cast<void*>(_m_a), x); }

    int bar(char const* x)
    { return _m_t->bar(const_cast<void*>(_m_a), x); }

 private:
    // Function table type for the baz interface
    struct table_type
    {
        int (*foo)(void*, int x);
        int (*bar)(void*, char const*);
    };

    // For a given referenced type T, generates functions for the
    // function table and a static instance of the table.
    template <class T>
    struct functions
    {
        static baz::table_type const table;

        static int foo(void* p, int x)
        { return static_cast<T*>(p)->foo(x); }

        static int bar(void* p, char const* x)
        { return static_cast<T*>(p)->bar(x); }
    };

    void const* _m_a;
    table const* _m_t;
};

template <class T>
baz::table_type const
baz::functions<T>::table = {
    &baz::functions<T>::foo
  , &baz::functions<T>::bar
};

struct some_baz {
    int foo(int x) { return x + 1; }
    int bar(char const* s) { return std::strlen(s); }
};

struct another_baz {
    int foo(int x) { return x - 1; }
    int bar(char const* s) { return -std::strlen(s); }
};

int main()
{
    some_baz f;
    another_baz f2;
    baz p = f; 
    std::printf("p.foo(3) = %d\n", p.foo(3));
    std::printf("p.bar('hi') = %d\n", p.bar("hi"));
    p = f2;
    std::printf("p.foo(3) = %d\n", p.foo(3));
    std::printf("p.bar('hi') = %d\n", p.bar("hi"));
}

About the Code

The above code defines an interface reference named baz manually, which can refer to any type which provides functions matching the function pointers in the baz::table.

Every interface reference variable stores a pointer to its function table through the variable baz::_m_t and stores a pointer to the object in baz::_m_a.

What the code does is generate a static function table for every class T that is passed to a baz. These static function tables have type baz::table_type and are named baz::function<T>::table. Even though there is only one name, because it is a static template variable of baz::function, there is a separate one created for every instance of baz::function. To put it another way, we use the compiler to generate a function table for every class - interface pair possibility at compile-time.

Summary

The technique described, even though it is sophisticated, is still a simplification of how the BIL is implemented. The BIL is considerably more complex because it also provides support for a wide range of techniques such as Aspect Oriented Programming, Delegations, Generic Programming, and more. The BIL is also required to work around certain limitations of the C++ pre-processor. I will write more in the future about the BIL as it matures, and is released officially into the public domain. Hopefully, this article does help explain the theory behind the technique and can provide you with some insight into the interface reference types.