Compile-time Data Structures in C++17: Part 3, Map of Values

There is no such thing as ‘O(0)’ time complexity of a function (hence quotes) because time complexity implies that some action will be actually performed during the program execution. Here we are asking the compiler to perform all the actions required by the function (or more accurately, a meta-function) during the compilation itself, which allows us to use the result as an input for further compilation.

A meta-function might be a function with a constexpr specifier, but typically we will use either a template type (wrapped in a using type alias if nested inside a template type) or a constexpr static variable template (also nested inside a template type). In the former case, a result of a meta-function is a type, and in the latter, it is a value.

A tag type is a type which is meant to be used as a name – it has no data members and no useful member functions. The only purpose of objects of such types is the deduction of their type. Examples in the C++ standard library include std::nothrow_t or types defined for various overloads of std::unique_lock constructor.

A pure function is a function which has no side effects and, for any valid and identical set of inputs, always produces the same output. For example, any deterministic mathematical function is also a pure function. A function which takes no input, but always produces the same result and has no side-effect is also a pure function. Mathematical functions in C++ standard library are not pure functions, but this is about to change [ P0533R3 ]. We can view many meta-functions as pure functions.

A limitation of meta-functions is that they do not have a stack in any traditional sense (they have template instantiation depth instead), and cannot manipulate variables. They can produce (immutable) variables or types, which means that they can be used to implement recursive algorithms. Such implementation will be typically a template type, where at least one specialisation implements the general algorithm, while another specialisation implements the recursion terminating condition. The compiler selects the required ‘execution path’ of the recursive algorithm utilising template specialisation matching.

A higher order function is a function which consumes (or produces, or both) a function. Since in our case a (meta)function is a template, we can implement a higher order (meta)function consuming a (meta)function, as a template consuming template parameter (or in other words, a ‘template template parameter’). Since template types can naturally output a template type, any meta-function which is a type can trivially produce a meta-function.

A selector is some entity mapped to another – in a C++ standard library, a selector in std::map<int, std::string> is some value of type int . One way to perform such mapping during compilation is to employ overloading, which makes tag types an obvious choice of the selector. Mapping result could be either a type (deduced with the help of decltype keyword) or actual value, returned from an overloaded function. To avoid instantiating arbitrary types, we are going to use a small wrapper template when only a type is needed.

// copy the definition of set in Listing 6 from
// https://accu.org/index.php/journals/2531
// to here
namespace val_impl {
template <typename T> struct wrap {
  constexpr explicit wrap() = default;
  using type = T;
};

template <template <typename> typename CheckT,
  template <typename> typename CheckV,
  typename... L> struct impl;
template <template <typename> typename CheckT,
  template <typename> typename CheckV>
struct impl<CheckT, CheckV> {
  using selectors = set<CheckT>;
  constexpr explicit impl() = default;
  constexpr static void pair() noexcept;
  constexpr static void type() noexcept;
};
template <template <typename> typename CheckT,
  template <typename> typename CheckV, typename T,
  typename V, typename... L>
struct impl<CheckT, CheckV, T, V, L...> 
  : impl<CheckT, CheckV, L...> {
  using check = typename CheckV<V>::type;
  using base = impl<CheckT, CheckV, L...>;
  using selectors = 
    typename base::selectors::template insert<T>;
  static_assert
    (not base::selectors ::template test<T>);
  constexpr impl(const impl<CheckT, CheckV, L...>&
    b, const check& v) : base(b), val_(v) {}
  using base::pair;
  constexpr const auto& pair(wrap<T>) const
    noexcept { return val_; }
  using base::type;
  constexpr auto type(wrap<T>) const noexcept {
    return wrap<V>{}; }
	
private:
  check val_;
};
}
template <template <typename> typename CheckT,
  template <typename> typename CheckV, 
  typename... L>
class val {
  template <template <typename> typename, 
    template <typename> typename, typename...>
  friend class val;
  using impl = val_impl::impl<CheckT, CheckV,
    L...>;
  impl val_;
  constexpr explicit val(const impl& v) : val_(v)
  {}
public:
  constexpr val() = default;
  template <typename T, typename V> constexpr auto
    insert(const V& v) const noexcept
  {
    using result = val<CheckT, CheckV, T, V,
      L...>;
    using rimpl = typename result::impl;
    return result(rimpl(val_, v));
  }
  using set = typename impl::selectors;
  template <typename U> using type = 
    typename decltype(impl::type
      (val_impl::wrap<U>()))::type;
  template <typename U> constexpr const 
    auto& get() const noexcept
  {
    return val_.pair(val_impl::wrap<U>());
  }
  template <typename U, typename... A> constexpr
  auto run(A&&... a) const -> decltype(auto)
  {
    return get<U>()(std::forward<A>(a)...);
  }
};
			

namespace set_impl {

template <template <typename> typename Check,
  typename... L> struct unique;
template <template <typename> typename Check>
  struct unique<Check> {
// add this to set_impl::unique<Check> code :
  template <typename F> constexpr static bool
    apply(const F&) noexcept { return true; }
};

template <template <typename> typename Check,
  typename T, typename... L>
struct unique<Check, T, L...> {
// add this to set_impl::unique<Check, T, L...> :
template <typename F> constexpr static bool
    apply(const F& fn) noexcept
  {
    if constexpr (not std::is_void_v<T> && not
      contains_detail<Check, T, L...>::value) {
      if (not fn((T*)nullptr)) return false;
    }
    return unique<Check, L...>::apply(fn);
  }
};
} // namespace set_impl

template <template <typename> typename Check,
  typename... L> class set {
  using impl = set_impl::unique<Check, L...>;

public:
// add this to set<Check, L...> :
  template <typename F>
  constexpr static bool for_each(const F& fn)
  { return impl::apply(fn); }
};

int main()
{
  constexpr static auto s1 = set<PlainTypes>
    ::insert<int>::insert<Baz>::insert<Fuz>();
  decltype(s1)::for_each([](auto* d) -> bool {
    using type = decltype(*d);
    std::cout << typeid(type).name() << std::endl;
    return true;
  });
}
			

template <typename Val>
void foo(const Val& v)
{
  auto fuz = v.template run<Fuz>(
    v.template get<Baz>());
  // ...
}
int main()
{
  constexpr static auto m1 = 
    val<PlainTypes, PlainNotVoid>{}
    .insert<Fuz>([](int v){ return Fuzzer(v); })
    .insert<Baz>(13);
  foo(m1);
};
			

template <typename T> void foo(T);

template <typename... L>
void foo(const val<PlainTypes, Plain, L...>& v)
{ /* ... */ }

template <typename... L>
void foo(const val<DataSel, Plain, L...>& v)
{ /* ... */ }

template <typename... L>
auto foo(const val<PlatformSel, Plain, L...>& v)
  -> std::enable_if_t<std::decay_t<decltype(v)>
    ::set::template test<Ver1>>
{ /* ... */ }

template <typename... L>
auto foo(const val<PlatformSel, Plain, L...>& v)
  -> std::enable_if_t<std::decay_t<decltype(v)>
    ::set::template test<Ver2>>
{ /* ... */ }
			

template <typename Factory> 
void baz(const Factory& f) 
{
  auto a = f.logger(); // . . .
}
struct MyFactory {
  Logger logger() const;
};
int main()
{
  MyFactory factory;
  baz(factory);
}
			

template <typename Context>
void baz(const Context& c)
{
  auto& a = c.logger; // ...
}
struct MyContext {
  Logger& logger;
};
int main()
{
  Logger logger;
  MyContext context {logger};
  baz(context);
}
			

struct CommandLine {
  CommandLine(int argv, char* const* argc);
};
enum ConfigurationSelector {};
struct Configuration {
  explicit Configuration(const CommandLine& cmd);
};
enum PlatformServicesSelector {};
struct PlatformServices {
  template <typename... L>
  explicit PlatformServices(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      *v.template get<ConfigurationSelector>();
    // ...
  }
};
enum MarketPriceInputsSelector {};
struct MarketPriceInputs {
  template <typename... L>
  explicit MarketPriceInputs(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      *v.template get<ConfigurationSelector>();
    const auto& plat =
      *v.template get<PlatformServicesSelector>();
    // ...
  }
};
enum ClientPriceCalcSelector {};
struct ClientPriceCalc {
  template <typename... L>
  explicit ClientPriceCalc(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      *v.template get<ConfigurationSelector>();
    const auto& mark =
     *v.template get<MarketPriceInputsSelector>();
    // ...
  }
};
enum NetworkOutputSelector {};
struct NetworkOutput {
  template <typename... L>
  explicit NetworkOutput(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      *v.template get<ConfigurationSelector>();
    // ...
  }
};

struct ClientPriceOutput {
  template <typename... L>
  explicit ClientPriceOutput(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      *v.template get<ConfigurationSelector>();
    const auto& price =
      *v.template get<ClientPriceCalcSelector>();
    auto& out =
      *v.template get<NetworkOutputSelector>();
    // ...
  }
};

int main(int argv, char** argc)
{
  const auto v0 = val<PlainTypes, PlainNotVoid>{};
  try {
    const auto cmdln = CommandLine(argv, argc);
    const auto config = Configuration(cmdln);
    const auto v1 =
      v0.insert<ConfigurationSelector>(&config);
    const auto plsrv = PlatformServices(v1);
    const auto v2 =
      v1.insert<PlatformServicesSelector>(&plsrv);
    const auto input = MarketPriceInputs(v2);
    const auto v3 =
     v2.insert<MarketPriceInputsSelector>(&input);
    const auto price = ClientPriceCalc(v3);
    auto       output = NetworkOutput(v3);
    const auto v4 =
      v3.insert<ClientPriceCalcSelector>(&price)
        .insert<NetworkOutputSelector>(&output);
    const auto clout = ClientPriceOutput(v4);
    // ...
  }
  catch (...) {
    // ...
  }
  return 0;
}
			

enum ConfigurationSelector {};
struct Configuration {
  template <typename... L>
  explicit Configuration(const val<PlainTypes,
    PlainNotVoid, L...>& v,
    const CommandLine& cmdln)
    { /* ... */ }
  };
// use template run<...> as appropriate, e.g. :
enum NetworkOutputSelector {};
struct NetworkOutput {
  NetworkOutput(const NetworkOutput&) = delete;
  template <typename... L>
  explicit NetworkOutput(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  {
    const auto& conf =
      v.template run<ConfigurationSelector>(v);
    const auto& plat =
      v.template run<PlatformServicesSelector>(v);
    // ...
  }
};
template <typename Out> struct ClientPriceOutput {
  Out out_;
  template <typename... L>
  explicit ClientPriceOutput(const val<PlainTypes,
    PlainNotVoid, L...>& v)
  : out_(v.template run<NetworkOutputSelector>(v))
  {
    const auto& conf =
      v.template run<ConfigurationSelector>(v);
    const auto& price =
      v.template run<ClientPriceCalcSelector>(v);
    // ...
  }
}
int main(int argv, char** argc)
{
  try {
    const auto cmdln = CommandLine(argv, argc);
    const auto v = val<PlainTypes, PlainNotVoid>{}
    .insert<ConfigurationSelector>([cmdln]
      (const auto& v) -> const Configuration& {
        static auto config = Configuration(
          v, cmdln);
        return config;
    }).insert<PlatformServicesSelector>([]
      (const auto& v) -> const PlatformServices& {
        static auto plsrv = PlatformServices(v);
        return plsrv;
    }).insert<MarketPriceInputsSelector>([]
      (const auto& v) -> const MarketPriceIputs& {
        static auto input = MarketPriceInputs(v);
        return input;
    }).insert<ClientPriceCalcSelector>([]
      (const auto& v) -> const ClientPriceCalc& {
        static auto price = ClientPriceCalc(v);
        return price;
    }).insert<NetworkOutputSelector>([]
      (const auto& v) -> NetworkOutput {
        return NetworkOutput(v);
    });
    const auto clout =
      ClientPriceOutput<NetworkOutput>(v);
    // ...
  }
  catch (...) {
    // ...
  }
  return 0;
}
			

Users coming from other languages may have some difficulty with static variables defined inside a lambda. Here is how Anthony Williams explained this on the accu-general mailing list:

A lambda is an object of an unnamed type. The lambda body is the operator() member function of this type. For any given lambda expression there is only one such type and one such member function, so there is only one copy of each static object declared within the lambda body.

In practice, this means that the lambdas which make use of static variable will ‘cache’ the once-created object, making them equivalent to accessors of the context pattern with lazy evaluation. The afflictions of static objects do apply (e.g. static object lifetime, the accidental coupling of points of use if the object passed as a mutable reference) but are moderated by the fact that each lambda is its own type.

TEST("Test MarketPriceInputs")
{
  const auto config = MockConfiguration();
  auto       plsrv = MockPlatformServices();
  const auto v1 = val<PlainTypes, PlainNotVoid>{}
    .insert<ConfigurationSelector>(&config)
    .insert<PlatformServicesSelector,
      const MockPlaformServices*>(&plsrv);
  auto input = MarketPriceInputs(v1);
  plsrv.push("Some test inputs");
  // ...
}
			

TEST("Test MarketPriceInputs")
{
  auto       plsrv = MockPlatformServices();
  const auto v = val<PlainTypes, PlainNotVoid>{}
    .insert<ConfigurationSelector>([](auto&){
      static auto config = MockConfiguration();
      return config;
    }).insert<PlatformServicesSelector>([&plsrv]
      (auto&) -> const MockPlatformServices&
      { return plsrv; });
  auto input = MarketPriceInputs(v);
  plsrv.push("Some test inputs");
  // ...
}