1

I often write code to implement the dispatching and handling of "messages." My requirements are usually:

  1. I should be able to add new types of messages AND/OR new types of handlers without affecting the existing messages or handlers (i.e., loose coupling).
  2. Every handler can choose which subset of messages to "handle" (i.e., every handler need to handle every message type)

I have researched far and wide the various methods of dispatching. Below are the two main ones I have encountered. NOTE: These are not working code samples; I have only included enough to illustrate the idea.

Option 1 - The if/switch and cast pattern

class IMessage
{
public:
    virtual TypeId type() const = 0;
};

class IHandler
{
public:
    virtual void handle(IMessage&) = 0;
};

class MyHandler : public IHandler
{
public:
    void handle(IMessage& msg) override
    {
        const auto t = msg.type();
        if (t == MessageA::kType)
        {
            handleA(static_cast<MessageA&>(msg));
        }
        //...
    }

protected:
    void handleA(MessageA& msg);
};

Many different flavors of this pattern exist (e.g., dynamic_cast, typeid(), a virtual function, etc...) but in essence, they are all the same.

Option 2 - The Visitor Pattern

I have seen the Visitor pattern recommended far and wide as an appropriate (and preferred) solution to these types of problems. Having implemented it myself many times, I understand its merits as well as its downsides. The worst problem is that it does not meet my requirement to be able to add messages and visitors without affecting the others (i.e., it introduces tight coupling). Worse, the tight coupling is often obscured by all the virtual methods, files, and classes. Also, it can result in inheritance nightmares.

class IVisitor
{
public:
    virtual void visit(MessageA&) {}
    virtual void visit(MessageB&) {}
    virtual void visit(MessageC&) {}
};

class IMessage
{
public:
   virtual void accept(IVisitor&) = 0;
};

class MessageA : public IMessage
{
public:
    void accept(IVisitor& v) override
    {
        v.visit(*this);
    }
};

Option 3 - std::variant and std::visit

Another option I have tried is using std::visit on an std::variant to dispatch based upon the type of the message.

using Messages = std::variant<MessageA, MessageB, MessageC>;

class MyHandler
{
public:
    void handle(Messages& m)
    {
        std::visit([this](auto&& arg){
            this->handle(arg);
        }, m);
    }

protected:
    void handle(MessageA&);
    void handle(MessageB&);
    void handle(MessageC&);
};

However, this has the same coupling problem as the visitor (every new message changes the variant type). I believe std::visit might also implemented as a vtable under the hood.


I have compiled examples with all options to compare them side-by-side. The binary size ends up being about the same. I believe that option 1 is more readable and I can add new messages and/or handles without affecting the others.

Why should I choose the Visitor method above a good old fashion if statement? Are there other options that would be a better fit?

5
  • Option 1 is the only one that gives you your decoupling, at the cost of type safety / totality – you get no guarantee that any handler will know about a message. But you should really use dynamic_cast there, a static_cast can easily be UB, e.g. if the user-provided typeid is incorrect. Options 2/3 are largely equivalent, but can be desirable if you want stronger static type checks – not all coupling is bad. My Rust-afflicted brain would choose option 3 when messages and handlers are part of one software project so that all handlers can be recompiled when Messages or IVisitor are modified.
    – amon
    Commented Nov 1, 2023 at 10:17
  • @amon I should mention that in the applications I am thinking of, I don't really care if every handler knows about every message. It is up to the programmer to add the new message types to existing (and new) handlers if he/she wants to handle the message. Otherwise, the handler should work the same as before (which is why I wasn't using pure virtual methods in the visitor example). Commented Nov 1, 2023 at 13:51
  • @amon The only reason I prefer static_cast over dynamic_cast is that I am an embedded developer. RTTI is typically disabled due to its overhead. Embedded systems are a controlled environment (in terms of the code being written) so I can guarantee the static_cast to be safe by writing safe code. I also tend to use template base classes to ensure the type() functions are implemented in a standard way. Commented Nov 1, 2023 at 14:00
  • The ObjVLisp model (implemented in RefPerSys ....) could be relevant to your question Commented Nov 1, 2023 at 17:54
  • @PatrickWright yeah the space used for class names might be problematic on embedded, and you're completely right that you can encapsulate this pattern fairly safely using templates. But my point about "knowing about a message" is more about evolution of the software system. Someone else pointed out the expression problem, which is relevant for static type systems. If you downcast as per option 1 you are throwing static checks away, requiring that the programmer knows whether existing handlers would have to be changed when adding a new message.
    – amon
    Commented Nov 4, 2023 at 15:22

2 Answers 2

4

I should be able to add new types of messages AND/OR new types of handlers without affecting the existing messages or handlers (i.e., loose coupling).

So, what you might be running into here is known in the CS community as the "expression problem". The gist of it is, there are two main ways to approach data abstraction, with different tradeoffs.

One is message passing in the OOP sense, where it's hard to extend the interface (add new types of messages, add new abstract operations), but easy to add new implementations (easy to add new kinds of handlers, new derived classes). The reason is, the implementations are all tightly coupled to the interface (the set of abstract operations), so if you change it, and you want to make sure that there are no surprises in clients that use it polymorphically, you have to track down all the implementations, and add support for the new method/message. But adding a new derivative doesn't affect the interface, or the other implementations.

The other is the the abstract data type approach (in the sense used by William R. Cook [1]), where it's hard to add new concrete types, but easy to add support for new abstract operations (over that set of concrete types). If/switch/cast, and the traditional visitor pattern, the C++ std::visit, and algebraic data types common in functional programming fall under this category. Here, the abstract type represents a finite set of concrete types (that may be just a set of mutually exclusive data structures, or may combined into various structures), and the client code works by calling operations on the abstract type. The implementations of the operations are aware and internally coupled to the concrete types, though, and generally have to support all variants. So if you add a new concrete type (like a new Element in the Visitor pattern), you generally have to update all the implemented operations, but adding a new operation (a new Visitor, or a new function that internally dispatches on the concrete type) doesn't affect anything else.

You'd choose one or the other based on your expectation of what's likelier to change more frequently - the set of handlers/implementations (go for OOP), or the set of operations (go for an ADT), or conversely based on what's more stable (the core abstraction that everything depends on should be the more stable thing).

The book Structure and Interpretation of Computer Programs covers these two approaches as well, but it also suggests a third possible approach that they call "data-directed programming". The idea is that you can do a sort of a 2D table lookup, where the set of operations forms one axis, and the set of concrete types the other - you'd then dispatch to a concrete implementation based on those two keys. So you'd either have to go outside the type system and represent the types and the operations as data, or somehow arm-twist the compiler into doing this for you, if that is at all possible with the language you're using. So while this can work, and gives you a lot of flexibility in one sense, it's also likely to be unwieldy to use/maintain, and shouldn't be your go-to solution, IMO.

P.S. I'm not 100% sure if I understood your description well, but depending on what you're actually trying to do, it might be that the problem is that you're attributing the wrong role to your messages. For example, in the visitor pattern, instead of representing them through the IElement hierarchy, perhaps they should be a part of the IVisitor hierarchy (remember, it's the concrete visitors that represent concrete implementations of operations, and their type represents the abstract operation itself - i.e. your message). So, something like (pseudocode):


class IVisitor
{
public:
    virtual void visit(DataStructA&) { /* ... */ }
    virtual void visit(DataStructB&) { /* ... */ }
};

class MessageA : public IVisitor { /* ... */ };
class MessageB : public IVisitor { /* ... */ };
class MessageC : public IVisitor { /* ... */ };

class IElement
{
public:
   virtual void accept(IVisitor&) = 0;
};

class DataStructA: public IElement
{
public:
    void accept(IVisitor& v) override
    {
        v.visit(*this);
    }
};

class DataStructB: public IElement { /* ... */ };

...

// client code:
// -----------------------------------------------
element.accept(message);   
// you can also read it as: element.do(operation)

Here, you can add new types of messages and handlers just by creating a new IVisitor derivative, but the tradeoff is that it's tricky to add new kinds of data structures that they can handle. I chose the Visitor pattern as an example, but you can do this with if/switch, or with std::visit, the important part is the conceptual switch.

3
  • In your example above, if I am understanding correctly, you are essentially "flipping" the problem around so that the messages themselves are the "visitors." Maybe I am thinking completely wrong, but in my applications, a "message" is usually "routed" to one (or more) "visitors"/handlers. It is then up to these to handle the message how they see fit. But, the handlers must use the concrete types (not the abstract interface) thus the "problem." Commented Nov 1, 2023 at 13:57
  • @PatrickWright Essentially. I'm not so much flipping the problem, I'm saying that the concrete visitors were conceptualized as operations by the Go4 in the first place. The handlers here would more specifically be the individual visit methods that each concrete visitor has to implement, but that means you're tightly coupled to the set of classes deriving from IElement, which may or may not work for what you're trying to do. The dispatch itself happens through polymorphism and overload resolution (the Visitor pattern kind of sets this up for you so that you don't have to dispatch manually). Commented Nov 1, 2023 at 15:59
  • But part of my point was that, unless you're willing to go down the table-lookup route, it might not be possible to design a system in a way that allows for the same degree of flexibility for both the messages and the handlers - you might have to make a choice. Commented Nov 1, 2023 at 16:04
3

There are a load of ways to at least partly decouple visitation, but they're effectively different ways to implement Double Dispatch.

This really just means you have a function that is dispatched on two parameters.

Single dispatch, for comparison, is trivially implemented with virtual in C++ - the version of the function that gets called is decided completely by the dynamic type of the single (implicit) parameter this.

1 - Double dispatch with mixin visitors

struct IVisitor {
    virtual ~IVisitor();
};

struct IMessage
{
   virtual void accept(IVisitor&) = 0;
};

struct MessageA : public IMessage
{
    struct AVisitor: public IVisitor {
        virtual void visit(MessageA&) = 0;
    };
        
    void accept(IVisitor& v) override
    {
        auto av = dynamic_cast<AVisitor*>(&v);
        if (av)
            av->visit(*this);
    }
};

This is double-dispatch because the eventual visit method called depends on two runtime types: the type of the message, and the type of the visitor.

Visitors can derive from as many of those message-specific visitor interfaces they care about (this is "mixin" inheritance - it's not essential for double-dispatch, but for your decoupling requirement).

You can add a base "not-implemented" visitor to IVisitor if you want to handle that case, and you can automate production of the per-message-type boilerplate (the visitor interface and the acceptor) with CRTP if you want.

2 - Data-driven double dispatch

We need the dynamic types of two objects to perform double dispatch (the visitor, and the visited). The alternative to using virtual is to use std::type_info directly.

class IMessage;
class IVisitor;
class MessageDispatcher
{
    using DDKey = std::pair<std::type_index, std::type_index>;
    using DDFunc = std::function<void(IVisitor&, IMessage&)>;

    std::unordered_map<DDKey, DDFunc, boost::hash<DDKey>> table_;

public:
    // it's ugly, but you only need to write it once
    template <typename Visitor, typename Message>
    void add(void (Visitor::*visit)(Message&))
    {
        DDKey key{typeid(Visitor), typeid(Message)};
        table_[key] = [visit](IVisitor& basev, IMessage& basem)
                      {
                          Visitor *v = dynamic_cast<Visitor*>(&basev);
                          Message *m = dynamic_cast<Message*>(&basem);
                          v->*visit(m);
                      };
    }

    // the actual double-dispatch is just a single lookup
    void apply(IVisitor& v, IMessage& m)
    {
        DDKey key{typeid(v), typeid(m)};
        auto dd = table_.find(key);
        if (dd != table_.end())
            (dd->second)(v, m);
        // else unhandled
    }
};

Pros:

  • none of the visitors are coupled to any messages they don't handle
  • none of the messages have to know anything at all about visitors

Cons:

  • lots of calls like add(&MyVisitor::visit_my_message), add(&OtherVisitor::visit_other_message)
  • need to keep a MessageDispatcher around somewhere
  • only dispatches to the most derived type, so multiple levels of inheritance will make your visitors behave oddly

It only even uses IVisitor and IMessage so we have something convenient to downcast from - we could make apply a template too and do away with both of them.


NB. You can absolutely replace typeid with your custom embedded TypeId, so long as it supports hashing and equality testing. I've stuck with the standard typeid/std::type_info/std::type_index system here so I don't have to reinvent your existing implementation.

2
  • Nice answer, especially because it demonstrates the table-based approach I mentioned: your data-driven double dispatch is essentially a C++ realization of SICPs "data-directed programming" idea (which is great for the OP, because I believe they use Scheme in the book). Commented Nov 2, 2023 at 11:30
  • Thanks! Most of the time people seem to compromise on "slightly less coupling" because the data-directed approach sounds hard. I wanted to demonstrate it isn't actually that much work.
    – Useless
    Commented Nov 2, 2023 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.