Dependency Injection in C++ Using Variadic Templates

A few days ago I was reading up on variadic templates and it occurred to me that they could be used to automate dependency injection. So I started playing with some code and here's what I got. Note: this post assumes at least some level of familiarity with the newer C++ features in general, and variadic templates in particular.

Some Background

The idea behind dependency injection really is quite simple. You have a bunch of objects (I'll refer to them as "services"), some of which depend on the others. Each service explicitly declares its dependencies in some way (for example, by listing them as parameters to its constructor). An external piece of code (the so-called injector) creates and provides the dependencies accordingly, based on these declarations. This is a nice improvement over having everything be a singleton or passing around a huge service locator.

The trickier part is automating all of this (wiring all the dependencies manually is very boring). If your language has introspection/reflection, you can write some code that looks at the list of a constructor's parameters and figures out what dependencies it needs. All the frameworks like PHP-DI use introspection to work their magic.

Unlike other higher-level languages, C++ has no introspection (unless you count typeid, which is very limited). However, it is possible to use variadic templates to extract information about a function's parameters. This is enough to automate dependency injection.

An Example of Client Code

First, I'll show you what the client code that uses DI looks like and in the following sections, I'll explain what I did to get this result.

Each service has to provide an "instance factory" function. The parameters of this function should be the service's dependencies. It should return a new instance of the service.

struct  Service1 { // Our service
  Service1(Service2*, Service3*){} // Service2 and Service3 declared elsewhere
};

std::unique_ptr<Service1> Service1Factory(Service2* s2, Service3* s3) {
  return std::make_unique<Service1>(s2, s3); // Just pass the arguments to Service1's ctor.
}

You have to configure dependency injection by registering your instance factories (the order of registration doesn't matter).

di_config cfg;
cfg.add(Service1Factory);
cfg.add(Service2Factory);
cgf.add(Service3Factory);

Finally, after all instance factories are registered, we can build an injector object. The injector will contain instances of all the services with their dependencies wired properly.

injector i = cfg.build_injector();

We'll be able to get a pointer to the instance of a particular service from the injector like this:

Service1* svc = i.get_instance<Service1>();

We'll also be able to "inject" the services into a function like this:

std::unique_ptr<Widget> WidgetFactory(Service1 *s1, Service3 *s3) {
  return std::make_unique<Widget>(s1, s3->gadget());
}
//...
// Create a new Widget using services from the previously built injector.
std::unique_ptr<Widget> w = i.inject(WidgetFactory);

Injector Implementation

First, let's look at how the injector class is implemented. Here is its interface:

template <class InstanceType, class Deleter, class ...Deps>
using instance_factory_function =
  std::unique_ptr<InstanceType, Deleter>(*)(Deps*...);

class injector {
  friend class di_config;
public:
  injector(injector &&other) { *this = std::move(other); }
  injector& operator=(injector &&other);

  template <class T, class Dependent = std::nullptr_t>
  T* get_instance() const;

  template <class InstanceType, class Deleter, class ...Deps>
  std::unique_ptr<InstanceType, Deleter> inject(
    instance_factory_function<InstanceType, Deleter, Deps...> instance_factory) const;

private:
  injector() = default;
};

instance_factory_function is an alias template for a pointer to a function accepting a bunch of parameters and returning a unique_ptr.

injector::get_instance is a function template that returns a pointer to the instance of a service in the injector. Calling i.get_instance<T>(); will return a pointer to the service of type T (it will throw an exception if the injector doesn't have the service of the given type). Don't think too much about the second template parameter, Dependent, yet. It is needed to produce a more useful error message in case of messed up configuration.

injector::inject is the most interesting function. It invokes the given instance factory function with each of its parameters bound to the appropriate service from the injector and returns the result produced by the instance factory.

Let's look at how the services are stored within the injector. We need to be able to query services by type. I will use a type map for that purpose. Think of type maps as a special kind of hash tables, in which the keys are types. I have talked about type maps in more detail in one of the previous posts. For the sake of completeness, here is the implementation of the type map that we'll use:

namespace detail {
// Maps types to objects of ValueType
template <class ValueType>
class type_map {
  using Container = std::unordered_map<int, ValueType>;
public:
  using iterator = typename Container::iterator;
  using const_iterator = typename Container::const_iterator;

  iterator begin() { return container_.begin(); }
  iterator end() { return container_.end(); }
  const_iterator begin() const { return container_.begin(); }
  const_iterator end() const { return container_.end(); }
  const_iterator cbegin() const { return container_.cbegin(); }
  const_iterator cend() const { return container_.cend(); }

  template <class Key>
  iterator find() { return container_.find(type_id<Key>()); }
  template <class Key>
  const_iterator find() const { return container_.find(type_id<Key>()); }
  template <class Key>
  void put(ValueType &&value) {
    container_[type_id<Key>()] = std::forward<ValueType>(value);
  }

  template <class Key>
  static int type_id() {
    static int id = ++last_type_id_;
    return id;
  }

private:
  static std::atomic<int> last_type_id_;
  Container container_;
};

template <class T>
std::atomic<int> type_map<T>::last_type_id_(0);
} // namespace detail

The question now is, what type of values should we store in the type map? The services are all of different types, but the type map can only store values of a single type. Maybe there is a better solution, but here is the one I came up with: just wrap the pointers to services into a single type, abstract_instance_container.

class abstract_instance_container {
public:
  virtual ~abstract_instance_container() = default;

  // The type_map holding the instance container has the
  // type information, so we'll be able to safely convert
  // the pointer from void* back to its original type.
  void* get() { return raw_ptr_; }

  abstract_instance_container(abstract_instance_container &&other) {
    *this = std::move(other);
  }

  abstract_instance_container& operator=(
    abstract_instance_container &&other) {
    raw_ptr_ = other.raw_ptr_;
    other.raw_ptr_ = nullptr;
    return *this;
  }

protected:
  explicit abstract_instance_container(void *raw_ptr) :
    raw_ptr_(raw_ptr) {}

private:
  void *raw_ptr_;
};

Unfortunately, this does nothing to control the lifetime of the service. I'd like injector to own all the services. To do that, we need our instance container to store a unique_ptr to the service instance. Of course, unique_pointers to different service instances will have different types, but we can have a class template that inherits from abstract_instance_container and stores the unique pointer of the appropriate type:

template <class T, class Deleter>
class instance_container : public abstract_instance_container {
public:
  ~instance_container() override = default;

  explicit instance_container(std::unique_ptr<T, Deleter> &&p) :
    abstract_instance_container(p.get()),
    pointer_(std::move(p)) {}

  instance_container(instance_container &&other) {
    *this = std::move(other);
  }

  instance_container& operator=(instance_container &&other) {
    pointer_ = std::move(other);
    abstract_instance_container::operator=(std::move(other));
    return *this;
  }

private:
  std::unique_ptr<T, Deleter> pointer_;
};

Finally, let's have a helper function to wrap a unique_ptr into an abstract_instance_container.

template <class T, class Deleter>
std::unique_ptr<abstract_instance_container>
  wrap_into_instance_container(
  std::unique_ptr<T, Deleter> &&ptr) {
  return std::make_unique<instance_container<T, Deleter>>(
    std::move(ptr));
}

Okay, we can finally update our definition of injector and add the type map data member:

class injector {
  friend class di_config;
public:
  injector(injector &&other) { *this = std::move(other); }
  injector& operator=(injector &&other) { instance_map_ = std::move(other.instance_map_); }

  template <class T, class Dependent = std::nullptr_t>
  T* get_instance() const;

  template <class InstanceType, class Deleter, class ...Deps>
  std::unique_ptr<InstanceType, Deleter> inject(
    instance_factory_function<InstanceType, Deleter, Deps...> instance_factory) const;

private:
  injector() = default;
  using instance_map =
    detail::type_map<std::unique_ptr<
      detail::abstract_instance_container>>;
  instance_map instance_map_;
};

With this in place, I can proceed to reveal the implementation of injector::get_instance:

template <class T, class Dependent>
T* injector::get_instance() const {
    auto it = instance_map_.find<T>();
    if (it == instance_map_.end()) {
      throw std::runtime_error(
        std::string(typeid(T).name()) + ": unsatisfied dependency of " + std::string(typeid(Dependent).name()));
    }
    return static_cast<T*>(it->second->get());
}

As you can see, it just does a lookup in the type map and returns the pointer to the found instance, and throws if it can't find whatever it's looking for.

Now let's look at the implementation of inject:

template <class InstanceType, class Deleter, class ...Deps>
std::unique_ptr<InstanceType, Deleter> injector::inject(
  instance_factory_function<InstanceType, Deleter, Deps...>
    instance_factory) const {
  return
    instance_factory(
      get_instance<typename std::remove_const<Deps>::type,
                   typename std::remove_const<InstanceType>::type>()...);
}

This invokes the function pointed to by instance_factory with each of its parameters bound to the appropriate service instance. The instances are located by calling get_instance. Note the ellipsis at the end of the call. In the context of a variadic template, the ellipsis occurring to the right of an expression causes the expression to be repeated for each element in the parameter pack (Deps in this case). So, if the instance factory passed to inject looks like this:

std::unique_ptr<Service1> Service1Factory(Service2* s2, Service3* s3) {
  return std::make_unique<Service1>(s2, s3);
}

Then the call inside inject will be equivalent to the following:

instance_factory(
  get_instance<typename std::remove_const<Service2>::type,
               typename std::remove_const<Service1>::type>(),
  get_instance<typename std::remove_const<Service3>::type,
               typename std::remove_const<Service1>::type>());

You might have noticed that there is no method to actually add a service instance into the injector. This is intentional. The thing is, services need to be added in the correct order. Adding a service before its dependencies have been added will result in an error. Ensuring the correct order manually is annoying and error-prone, so this task is automated by di_config. The client code can't create an injector object directly or add services to it. Instead, it has to set up a di_config object and ask it to create an injector. We will examine the implementation of di_config next.

Implementation of di_config

Here is the interface that di_config provides:

class di_config {
public:
  template <class InstanceType, class Deleter, class ...Deps>
  void add(instance_factory_function<InstanceType, Deleter, Deps...> instance_factory);
  injector build_injector();
};

di_config::add registers a new instance factory. Instance factories can be registered in arbitrary order: no instances are created at the time of registration.

di_config::build_injector creates a new injector with services created by the registered instance factories. The method ensures that instances are created in the correct order: if Service1 depends on Service2 and Service3, it will be created after Service2 and Service3, and both Service2 and Service3 will be provided as arguments to Service1's instance factory.

Internally, di_config maintains a graph of dependencies. The nodes in this graph are the instance factories. There is an edge between nodes A and B iff the instance factory B requires the service produced by instance factory A. The order in which services are added to the injector is determined by doing a topological sort of the dependency graph. Let's update the definition of di_config:

class di_config {
public:
  template <class InstanceType, class Deleter, class ...Deps>
  void add(
    instance_factory_function<InstanceType, Deleter, Deps...>
      instance_factory);
  injector build_injector();
private:
  using initializer_fn = std::function<void(injector&)>;
  struct node_info {
    // Mark is needed for the toposort algorithm.
    enum class mark {
      UNMARKED, TEMP, PERM
    };
    mark mark_;

    // Name of the service class, 
    // needed to display more useful error messages
    std::string debug_type_name_;
    
    // A function that invokes the instance factory
    // and adds the created service to the given
    // injector.
    initializer_fn initializer_;
    bool has_iniliatizer_ = false;
    
    // List of nodes adjacent to this one.
    std::unordered_set<int> dependents_;
  };

  std::unordered_map<int, node_info> graph_;
};

So, let's examine the implementation of di_config::add

template <class ...Args>
inline void passthru(Args... args) {}

template <class InstanceType, class Deleter, class ...Deps>
void di_config::add(
  instance_factory_function<InstanceType, Deleter, Deps...>
    instance_factory) {
  int instance_type_id =
    detail::type_map<node_info>::type_id<typename std::remove_const<InstanceType>::type>();
  node_info &new_node_info = graph_[instance_type_id];
  new_node_info.initializer_ =
    [instance_factory](injector &inj) {
      auto instance = detail::wrap_into_instance_container(inj.inject(instance_factory));
      inj.instance_map_.put<InstanceType>(std::move(instance));
    };
  new_node_info.has_iniliatizer_ = true;
  new_node_info.debug_type_name_ = typeid(typename std::remove_const<InstanceType>::type).name();
  passthru(
    graph_[detail::type_map<node_info>::type_id<typename std::remove_const<Deps>::type>()]
      .dependents_
      .insert(instance_type_id)...);
}

This might be a bit hard to follow, so let's break it down. First, we locate the graph node corresponding to InstanceType (the type of our service). If the node doesn't exist yet, it will be created. Then, we assign an "initializer function" to the node. An initializer function is a callable that creates the service and places it into the given injector. Finally, we add the edges between the new node and the nodes corresponding to the dependencies in the graph (the weird passthru function is needed if we want to do something with each parameter in the parameter pack).

Now let's look at the implementation of di_config::build_injector

injector di_config::build_injector() {
  injector inj;
  std::stack<initializer_fn*> initializers;

  std::unordered_set<int> unmarked_nodes;
  for (auto &node : graph_) {
    node.second.mark_ = node_info::mark::UNMARKED;
    unmarked_nodes.insert(node.first);
  }
  while (!unmarked_nodes.empty()) {
    int node_id = *unmarked_nodes.begin();
    toposort_visit_node(node_id, &unmarked_nodes, &initializers);
  }

  while (!initializers.empty()) {
    (*initializers.top())(inj);
    initializers.pop();
  }
  return std::move(inj);
}

It does two things: determines the correct order for calling the initializers by using topological sort on the graph, and calls the initializers in that order. I won't go into the details of the sorting algorithm, you can read about it on Wikipedia. For the sake of completeness, here is the implementation of toposort_visit_node:

void di_config::toposort_visit_node(
  int node_id,
  std::unordered_set<int> *unmarked_nodes,
  std::stack <di_config::initializer_fn*> *output) {
  node_info &info = graph_[node_id];
  if (info.mark_ == node_info::mark::TEMP) {
    throw std::runtime_error(info.debug_type_name_ + " appears to be part of a cycle");
  }
  else if (info.mark_ == node_info::mark::UNMARKED) {
    unmarked_nodes->erase(node_id);
    info.mark_ = node_info::mark::TEMP;
    for (int dependent : info.dependents_) {
      toposort_visit_node(dependent, unmarked_nodes, output);
    }
    info.mark_ = node_info::mark::PERM;
    if (info.has_iniliatizer_) {
      // if has_initializer_ is false, it means someone depends on this
      // node, but an instance factory for this node has not been provided.
      // This will result in an injection error later.
      output->push(&info.initializer_);
    }
  }
}  

Conclusion

The implementation is fairly involved and full of angle brackets, but the good news is, you don't have to deal with those details to use it. The client code ends up looking pretty simple. By the way, if you don't want to write an instance factory function for each service, you can write a generic instance factory that forwards its arguments to the constructor of your class:

template <class InstanceType, class ...Deps>
std::unique_ptr<InstanceType> generic_instance_factory(Deps*... deps) {
  return std::make_unique<InstanceType>(deps...);
}

The only catch here is that you have to explicitly specify the types of parameters during configuration, to indicate which constructor should be used:

di_config cfg;
cfg.add(generic_instance_factory<Service1, Service2, Service3>);
cfg.add(generic_instance_factory<Service2>);
cfg.add(generic_instance_factory<Service3>);
injector inj = cfg.build_injector();

Like this post? Follow this blog on Twitter for more!