Categories?

One of the most useful features I’ve used in object-oriented programming languages is the “category”. A category is a way of adding methods to a class dynamically. Take, for example Objective C’s “NSAttributedString” class. As defined in the Foundation framework, it is simply a string where you can attach key-value pairs to a range of it.

Only a category in the GUI framework AppKit actually defines the methods and constants that define what key to use for “bold”, and let you draw such a string to the screen. Yet in everyday use with AppKit, these two disparate parts feel like one homogeneous whole. And, more importantly, anyone who wants to write a text-processing command line tool can use NSAttributedString without having to drag in all that unneeded drawing code.

How C++ objects work

But C++ does not have this feature. So let’s come up with an implementation of this concept that a compiler vendor could implement, and that stays true to the core of C++, mainly its compile-time determination of as much as possible. But of course we want to be able to add a category to a system class or a class in another module, and want to define virtual methods in a category, and override them in a category on a subclass. So, of course we want to end up at something that looks like this in C++:

category BarSupport : MyObject // extend class MyObject with some methods.
{
    void doBar( MyObject baz );
};

and can be called just like any other method on MyObject, e.g.

MyObject foo, dodo;
foo.doBar( dodo );

If we didn’t have to support virtual methods, things would be trivial. A non-virtual method call like

MyObject foo;
foo.doBar(baz);

compiles to something like

MyObject_doBar( foo, baz );

Where the this pointer is simply passed in as the first parameter before the first parameter you defined. So all we’d have to do is tell the parser about these new methods, compile the functions that implement them, and call them.

But virtual methods work differently. First, there is a virtual function table, something like this:

struct MyObjectVTable
{
    void (*doFoo)( struct MyObject* this ); // defined by user as doFoo(void).
};

And whenever you define a new class, what it actually does is add a hidden instance variable at the start:

struct MyObject
{
    struct MyObjectVTable *vtable;
    int                   firstInstanceVariable;
};

And it declares a global variable containing the vtable once, for all objects created with this class, and stashes it in each new object’s vtable instance variable:

struct MyObjectVTable gMyObjectSharedVTable = { MyObject_doFoo };

...

// Equivalent code to MyObject* foo = new MyObject :
struct MyObject* foo = malloc(sizeof(struct MyObject));
foo->vtable = &gMyObjectSharedVTable;
MyObject_Constructor( foo );

Here, MyObject_doFoo() is a function just like our 

MyObject_doBar()

above. But when a virtual method is called, it is done slightly differently:

foo.vtable->doFoo( &foo );

This means that a subclass that wants to override doFoo() can provide its own gMySubclassSharedVTable that is also a struct MyObjectVTable, but contains a pointer to MySubclass_doFoo instead, and thus overrides the behaviour of doFoo() for all MySubclass objects. And if it wants to define additional virtual methods in its subclass, it can simply declare a struct MySubclassVTable that starts with the same fields in the same order as struct MyObjectVTable, and contains the additional methods after that. That way, anyone who expects an object for the base class doesn’t even have an inkling that there is more stuff after the methods it knows.

Applying that to Categories

Our categories also want to add methods, but the problem is we can’t just add new fields to the struct. The system classes like std::string have already been compiled, and we can’t just change their code to add these ivars. But what we can do is declare a parallel class hierarchy for our categories. So, first we declare a struct for our category:

struct MyObject_BarSupportVTable
{
    void (*doBar)( struct MyObject* this, struct MyObject* baz );
};

Then we extend the vtable to list categories:

struct CategoryEntry
{
    MyObject_BarSupportVTable* catVTable; // Simplified, each category's vtable is really a different struct.
};

struct MyObjectVTable
{
    struct CategoryEntry *cattable;
    void (*doFoo)( struct MyObject* this ); // defined by user as doFoo(void).
};

When a class is first built, the cattable array is empty, but as soon as someone declares a category, it gets added to that list. We just add some initialization code at the start of main() that mallocs the list. But how do we look up the vtable for a category? We could store its name, but then we’d have to loop over this list on each call and compare category names until we find it. How can we make that more efficient?

Simple: When we add the category to the class, we remember the index into the array where we added this category in the list, cache it in a global variable int gMyObject_BarSupport_Index; and then we can call a virtual method in a category like:

foo.vtable->cattable[gMyObject_BarSupport_Index].catVTable->doBar( &foo, baz );

Again, a subclass-category that overrides this method can just provide its own doBar method in the struct MyObject_BarSupportVTable.

The cost of categories

Of course this means that, just like with C++ virtual methods, and a bit more so, you pay a price for calling a virtual method in a category. You also pay with a little bit of overhead at startup, when the categories are added to the base class vtable. And just like with C++ virtual methods, to override a category method in a subclass, you have to know that the category exists on the base class. And if your program uses threads and you load a dynamic library that contains a category on a system class, bad things could happen while the category lists change under your running code’s rear.

Another gotcha with this approach is that the category list has to be built from the base class to the subclasses, because once a subclass locks down an index in the table for its first category vtable, you can’t add another category to the base class (it would have the index of the subclass’s category). But even that can be fixed:

We can just give every subclass its own categories table. So it only deals with the base class table when it wants to call a method inherited from the base class. E.g.:

struct MySubclassVTable
{
    struct CategoryEntry *cattable;
    void (*doFoo)( struct MyObject* this ); // defined by user as doFoo(void).
    struct CategoryEntry2 *cattable2;
    void (*doBar)( struct MyObject* this, struct MyObject baz ); // defined by user as doBar( MyObject baz ).
};

And now, calling a method in a category specific to the subclass simply goes through the cattable2.

Thoughts, suggestions, additional runtime geekery?