Saturday, September 22, 2012

Improving on Tuples

In the previous article, we saw how a tuple is really just a struct disguised as an array. A tuple simply maps a struct's types to an index. Just as we can iterate over an array at run-time, we can iterate over a tuple's elements at compile-time. For example, we can implement a simple linear search and iterate over the tuple until an element of the given type parameter is selected. If no element of that type is found, then the code won't compile. Because all of this happens at compile-time, there is very little run-time overhead.
//------------------------------------------------------------------------------
// Recursively iterate over tuple
template <int N, typename A> 
struct TupleGetType {  
  typedef typename std::tuple_element<N, A>::type ElementN;
  template <typename T>
  typename std::enable_if<std::is_same<T, ElementN>::value, T&>::type
  static getType(A& tuple) {
    return std::get<N>(tuple);
  }

  template <typename T>
  typename std::enable_if<!std::is_same<T, ElementN>::value, T&>::type
  static getType(A& tuple) {
    return TupleGetType<N-1, A>::template getType<T>(tuple);
  }
};

//------------------------------------------------------------------------------
// Terminate at first element
template <typename A> 
struct TupleGetType<0, A> {
  typedef typename std::tuple_element<0, A>::type Element0;

  template <typename T>
  typename std::enable_if< std::is_same<T, Element0>::value, T&>::type
  static getType(A& tuple) {
    return std::get<0>(tuple);
  }

  template <typename T>
  typename std::enable_if<!std::is_same<T, Element0>::value, T&>::type
  static getType(A& tuple) {
    static_assert(std::is_same<T, Element0>::value, 
                  "No element of type T in std::tuple");
  }
};

//------------------------------------------------------------------------------
// Convenient wrapper
template <typename E, typename T> 
E& getType (T& tuple) {
  return TupleGetType<std::tuple_size<T>::value-1, T>::template getType<E>(tuple);
}

Now we don't have to worry about the positions of elements within the tuple. Although this isn't the prettiest or most readable code, the stink is safely encapsulated by the getType function. Of course, there is an obvious limitation: if the tuple has more than one element with the same type, only one will ever be returned by getType. We will explore the upside of this limitation in a moment.

We've already mentioned that tuples are basically equivalent to structs. More importantly, they allow us to define a collection of heterogeneous types using template parameters at compile-time. Because of this parameterization, tuples are incredibly useful when writing abstractions. A great example is a type-safe publish/subscribe mechanism:
//------------------------------------------------------------------------------
// Simple event handler interface
template <typename Event>
struct Handler {
  virtual void onEvent(Event event) = 0;
};

//------------------------------------------------------------------------------
// Our main event registrar
template <typename... Events>
struct EventRegistrar {
  // Publish an event of event type E
  template <typename E>
  void pub(E event) {
    for (Handler<E>* e : handlers_<E>()) {
      e->onEvent(event);
    }
  }

  // Subscribe to the event type E
  template <typename E>
  void sub(Handler<E>* pHandler) {
    handlers_<E>().push_back(pHandler);
  } 

private:
  // Get the list of Handler<E>s
  template <typename E>
  std::list<Handler<E>*>& 
  handlers_() {
    return getType<
      std::list<Handler<E>*>
    >(eventHandlers_);
  }

  // tuple of lists of handler<> pointers
  std::tuple<
    std::list<Handler<Events>*>...
  > eventHandlers_;
};
And its usage:
//------------------------------------------------------------------------------
// Some trivial event definitions.
struct EventA {};
struct EventB {};
struct EventC {};

//------------------------------------------------------------------------------
// Handler for EventA
struct HandlerA : public Handler<EventA> {
  void onEvent(EventA a) {
    std::cout << "EventA Fired!!!" << std::endl;
  }
};

//------------------------------------------------------------------------------
// This one handles two events
struct HandlerBC : public Handler<EventB>
                 , public Handler<EventC> {
  void onEvent(EventB b) {
    std::cout << "EventB Fired!!!" << std::endl;
  }

  void onEvent(EventC c) {
    std::cout << "EventC Fired!!!" << std::endl;
  }
};

//------------------------------------------------------------------------------

int main () {
  // Define an event registrar for events A, B and C
  EventRegistrar<
    EventA, 
    EventB, 
    EventC
  > reg;

  // Define two handlers, one for handlers event A, and one for events 
  // A and B.
  HandlerA  handlerA;
  HandlerBC handlerBC;

  // Subscribe to event types
  reg.sub(&handlerA);
  // We must tell the registrar which event we want to register
  // in this case because otherwise it is ambiguous
  reg.sub<EventB>(&handlerBC);

  // Publish some events
  reg.pub(EventA()); // triggers event
  reg.pub(EventB()); // triggers event
  reg.pub(EventC()); // no event triggered

  // Nothing was subscribed to EventC (our handlerBC had
  // only been added to the EventB registry).  Subscribe
  // to EventC
  reg.sub<EventC>(&handlerBC);

  // Publish another EventC  
  reg.pub(EventC()); // triggered event

  // The following should fail with compiler errors
  #ifdef FAIL_SUB
  reg.sub<EventC>(handlerA);
  #endif

  #ifdef FAIL_PUB
  struct EventZ {};
  reg.pub(EventZ());
  #endif
  
  return 0;
}

Everything is parameterized by type. As you can see, type parameters "flow" more easily between the different layers of our abstractions. There is little syntactic noise. Parameterizing by types also gives us type safety. The pieces of code guarded by FAIL_SUB and FAIL_PUB will actually provide compiler errors: handlerA can't possibly subscribe to EventC and the registrar has no clue what EventZ is.

What if we do want to store multiple elements of the same type in a tuple? We could revert and use tuple indices to address these elements; but as we saw previously, this is ugly and error-prone. Throwing away all of this context makes it far too easy to mix up variables when using the tuple. What if instead, we wrap the type in a struct and create an entirely distinct type? We can even provide some constructors and casts to make this new type more natural to use.
template <typename T, typename N>
struct NewType {
  NewType()
  :  value_() {
  }

  NewType(const T& value)
  :  value_(value) {
  }

  T& operator=(const T& value) {
    return value_;
  }

  operator T& () {
    return value_;
  }

  typedef T Type;  
  T         value_;
};

template <int N>
struct Tag;
Now we have a way to provide context other than with named variables. The Tag<> template just provides an easy way to define anonymous tags.
typedef NewType<float, Tag<0>> Position;
typedef NewType<float, Tag<1>> Velocity;

std::tuple<Position, Velocity> mv(0.0f, 10.0f);
getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;
We can also use named tags if there is a concern of clashing types later on:
struct PosTag;
struct VelTag;
typedef NewType<float, PosTag> Position;
typedef NewType<float, VelTag> Velocity;

std::tuple<Position, Velocity> mv(0.0f, 10.0f);
getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;
These type names can provide just as much context as variable name, but this obviously doesn't mean that every struct should be replaced with a tuple. Tuples really only have an advantage when building parameterized abstractions. In the next article, we will look at defining some key operations that can be used to create a basic type-safe relational algebra in C++11.

1 comment:

  1. This has been a really good read, do you have any eta on the follow up post? I am really looking forward to it! Henrik

    ReplyDelete