Cloners

By | 2013-07-18
0 Comment

Let’s say we are reading tagged blocks from within some sort of packet. The blocks being tagged means we won’t care whether they’re present, what order they come in, and can have each tag be a different length.

<tag2> <tag2_data0> <tag2_data1> ... <tag2_data11>
<tag1> <tag1_data0> <tag1_data1> ... <tag1_data8>
<tag6> <tag6_data0> <tag6_data1> ... <tag6_data20>
<tag3> <tag3_data0> <tag3_data1> ... <tag3_data6>
<tag0> <tag0_data0> <tag0_data1> ... <tag0_data10>
<tag5> <tag5_data0> <tag5_data1> ... <tag5_data7>
<tag4> <tag4_data0> <tag4_data1> ... <tag4_data3>

Each tag might represent data for a particular sensor, say.

We want to write an object-oriented reader. Let’s first consider a naive implementation:

    list<TTag*> TagList;
    while(stream) {
        tag_code = stream.read(1);
        switch( tag_code ) {
            case tag_0:
                TagList.push_back(new TTag0);
                break;
            case tag_1:
                TagList.push_back(new TTag1);
                break;
            // ... etc ...
            default:
                throw tag_read_error();
                break;
        }
        TagList.back().read(stream);
    }

We’ve made the tag objects derive from TTag, and each implements a virtual read() member that knows how to read itself from a stream. The tag will know its own length, so will leave the stream pointing at the next tag_code.

It’s a naive implementation because it’s putting information about the tag, outside the TTag object – i.e. the tag_code. We shouldn’t break layering by having any knowledge of the code outside the TTag child. Let’s make an improvement then:

    tag_code = stream.read(1);
    switch( tag_code ) {
        case TTag0::tag_code:
            TTagList.push_back(new TTag0);
        case TTag1::tag_code:
            TTagList.push_back(new TTag1);
        // ... etc ...
    }

This is better, but not much. We’ve made a little use of object orientation, but not enough. In fact, as a rule, any time you see a switch() in C++, you should ask whether or not you can push what its doing into an object.

Here’s a solution I end up using a lot. This code would go in some sort of factory class:

    list<const TTag*> TagTemplates;
    TagTemplate.push_back(new TTag0);
    TagTemplate.push_back(new TTag2);
    // ... etc ...
    TagTemplate.push_back(new TTag6);

    list<TTag*> TagList;
    tag_code = stream.read(1);
    for( auto tag : TagTemplates ) {
        if( tag->isThisYourCode(tag_code) ) {
            TagList.push_back(tag);
            tag->read(stream);
        }
    }

Very nice. We’ve replaced a hard-coded list, with an iteration. The template tags can be loaded elsewhere (probably the factory constructor) and could be different for different factory classes. The problem is that the above won’t work. In particular note:

    TagList.push_back(tag);
    tag->read(stream);

Here tag is a const TTag* from the TagTemplate list; and is being pushed onto a TTag* list. The compiler will block it. Worse, we’re trying to read from the stream into our one-and-only template TTag. What we need instead is the ability to copy the tag template to give us a modifiable instance that is independent.

That poses its own difficulty. What we have is a const TTag*, point at (say) a TTag0, we might wish we could do this:

    TTag *copyTag = new TTag;
    *copyTag = *tag;

This absolutely won’t work. We’ve made a new TTag, when we wanted a TTag0. We probably won’t even get as far as compilation because TTag is bound to be abstract, and so it’s not possible to make a new one. Even if we could, *copyTag = *tag would use TTag::operator=() not TTag0::operator=(). In short: a mess.

The solution in cases like this is to think about what it is you want: the ability to copy a derived class via a pointer with base-class type. Just like any other operation where we have a base-class pointer to access derived-class functionality, we use a virtual. This is often called the Virtual Constructor Idiom.

class TTag {
  public:
    virtual TTag *clone() const = 0;
};

class TTag0 {
  public:
    TTag0(const TTag&) { /* ... your implementation ... */ }
    TTag0 *clone() const override { return new TTag0(*this); }
};

Some points:

  • We’re using the derived class copy-constructor within the derived class. This is perfectly acceptable, it knows its own type.
  • Note the change of return type. C++ lets you use the fact that a function signature doesn’t include the return type to change the base class pointer type to a compatible derived-type return. TTag0* is a valid TTag*. This is a language feature called co-variant return types.

Our factory code then becomes:

    list<const TTag*> TagTemplates;
    TagTemplate.push_back(new TTag0);
    TagTemplate.push_back(new TTag2);
    // ... etc ...
    TagTemplate.push_back(new TTag6);

    list<TTag*> TagList;
    tag_code = stream.read(1);
    for( auto tag : TagTemplates ) {
        if( tag->isThisYourCode(tag_code) ) {
            TTag *copyTag = tag->clone();
            copyTag->read(stream);
            TagList.push_back(copyTag);
        }
    }

This code will work. This is approximately the solution I’ve been using for problems like this for a while now. You can see it in action for implementing handlers for multiple versions of the bitcoin protocol in my (incomplete) bitcoin client additup on github.

C++11 offers us some improvements. We should note that we have a classic instance of the Resource Return Problem. We are returning a resource and there is, as things are, no way to force the caller to return that resource when they are done with it. The solution is, of course, not to use naked pointers. We should return a unique_ptr<>. That unfortunately then denies us the use of a covariant return types, but that’s only really important if we want to use one of our derived classes as another base class.

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

class TTag0 {
  public:
    TTag0(const TTag&) { /* ... your implementation ... */ }
    unique_ptr<TTag> clone() const override {
        return unique_ptr<TTag>(new TTag0(*this));
    }
};

Note that this only works because C++11 offers us move semantics for unique_ptr<>, otherwise when it went out of scope the clone would be destroyed as soon as it is made.

Let’s see one final extension. Implementing the clone() method for every single class is a chore. We can make use of the Curiously Recurring Template Pattern (CRTP) to save ourselves that trouble.

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

template <typename TTag_t>
class TTagClonable : public TTag {
  public:
    unique_ptr<TTag> clone() const override {
        return unique_ptr<TTag>(
            new TTag_t(
                static_cast<const TTag_t&>(*this)
                );
    }
};

class TTag0 : public TTagCloneable<TTag0> {
  public:
    TTag0(const TTag&) { /* ... your implementation ... */ }
};

The CRTP is clever because rather than put a clone() in every derived class, we have the template system automatically create an intermediate class with a clone() that calls the derived class copy-constructor.

      TTag
       ^
       |
TTagClonable<TTag0>
       ^
       |
     TTag0

The clone() itself is a little messy because a cast is needed to force the compiler to pick the correct copy constructor; but the advantage is that we never need to write another clone() for any derived class.

There is a disadvantage: it only works for one level of derivation; if you derive again from TTag0 you’ll have to make another CRTP-implementing class.

Leave a Reply