fragile topological sort in c++ templates

topsort.cpp

#include <cstddef>
#include <iostream>
#include <sstream>
#include <type_traits>

struct nil { };

template <typename H, class T>
struct cons
{
  using head = H;
  using tail = T;
};

template <typename... Args>
struct mklist;

template <>
struct mklist<>
{
  using list = nil;
};

template <typename First, typename... Args>
struct mklist<First, Args...>
{
  using list = cons<First, typename mklist<Args...>::list>;
};

template <typename Target, typename List>
struct contains;

template <typename H, typename T>
struct contains<H, cons<H, T>>
{
  static constexpr bool value = true;
};

template <typename NotH, typename H, typename T>
struct contains<NotH, cons<H, T>>
{
  static constexpr bool value = contains<NotH, T>::value;
};

template <typename Value>
struct contains<Value, nil>
{
  static constexpr bool value = false;
};

template <typename List, typename Value>
struct append;

template <typename Value>
struct append<nil, Value>
{
  using value = cons<Value, nil>;
};

template <typename Head, typename Tail, typename Value>
struct append<cons<Head, Tail>, Value>
{
  using value = cons<
    Head,
    typename append<Tail, Value>::value>;
};

template <typename Value, typename List>
struct remove_one;

// intentionally left undefined. Means value not found for removal
template <typename Value>
struct remove_one<Value, nil>;

template <typename Head, typename Tail>
struct remove_one<Head, cons<Head, Tail>>
{
  using list = Tail;
};

template <typename Value, typename Head, typename Tail>
struct remove_one<Value, cons<Head, Tail>>
{
  static_assert(!std::is_same<Head, Value>::value, "something went wrong");
  using list = cons<Head, typename remove_one<Value, Tail>::list>;
};

template <typename List, ssize_t idx, ssize_t current = 0>
struct get_idx;

template <typename Head, typename Tail, ssize_t idx>
struct get_idx<cons<Head, Tail>, idx, idx>
{
  using value = Head;
};

template <typename Head, typename Tail, ssize_t idx, ssize_t current>
struct get_idx<cons<Head, Tail>, idx, current>
{
  static_assert(idx != current, "something is written incorrectly");
  using value = typename get_idx<Tail, idx, current + 1>::value;
};

template <typename List1, typename List2>
struct concat;

template <typename Head1, typename List2>
struct concat<cons<Head1, nil>, List2>
{
  using list = cons<Head1, List2>;
};

template <typename Head1, typename Tail1, typename List2>
struct concat<cons<Head1, Tail1>, List2>
{
  using list = cons<Head1, typename concat<Tail1, List2>::list>;
};

template <typename List2>
struct concat<nil, List2>
{
  using list = List2;
};

namespace test {
  struct A { }; struct B { }; struct C { };

  static_assert(
      std::is_same<
        cons<A, cons<B, nil>>,
        mklist<A, B>::list
      >::value, "!");

  static_assert(std::is_same<append<nil, A>::value, cons<A, nil>>::value, "!");

  static_assert(std::is_same<
      append<cons<A, nil>, B>::value,
      cons<A, cons<B, nil>>
      >::value, "!");

  static_assert(std::is_same<
      append<cons<A, cons<B, nil>>, C>::value,
      cons<A, cons<B, cons<C, nil>>>
      >::value, "!");

  using testlist = cons<A, cons<B, cons<C, nil>>>;

  static_assert(
      std::is_same<
        typename remove_one<C, testlist>::list,
        cons<A, cons<B, nil>>
      >::value, "!");

  static_assert(std::is_same<get_idx<testlist, 2>::value, C >::value, "!");

  static_assert(
      std::is_same<
        concat<cons<A, nil>, cons<B, cons<C, nil>>>::list,
        testlist
      >::value, "!");
}

template <typename T>
struct FieldInfo;

template <typename T, size_t offset_>
struct Field
{
  using type = T;
  static constexpr size_t offset = offset_;
};

template <typename T>
struct View
{
  using info = FieldInfo<T>;

  View(T& s) : s_(s) { }
  T& ref() { return s_; }

  private:
  T& s_;
};

template <typename Dependencies, typename Done>
struct all_satisifed;

template <typename Done>
struct all_satisifed<nil, Done>
{
  static constexpr bool value = true;
};

template <typename Dep, typename Rest, typename Done>
struct all_satisifed<cons<Dep, Rest>, Done>
{
  static constexpr bool value =
    contains<Dep, Done>::value && all_satisifed<Rest, Done>::value;
};

template <size_t i, typename PassList, typename Done>
struct find_satisfied_idx;

template <size_t i, typename Done>
struct find_satisfied_idx<i, nil, Done>
{
  static constexpr ssize_t value = -1;
};

template <size_t i, typename Pass, typename PassList, typename Done>
struct find_satisfied_idx<i, cons<Pass, PassList>, Done>
{
  static constexpr ssize_t value =
    all_satisifed<typename Pass::depends, Done>::value ?
      i
      : find_satisfied_idx<i + 1, PassList, Done>::value;
};

template <typename PassList, typename Done = nil>
struct top_sort
{
  static constexpr ssize_t current = find_satisfied_idx<0, PassList, Done>::value;
  static_assert(current != -1, "Dependencies not satisfied");

  using new_head     = typename get_idx<PassList, current>::value;
  using new_done     = typename concat<Done, typename new_head::provides>::list;
  using list_removed = typename remove_one<new_head, PassList>::list;

  using sorted = cons<new_head, typename top_sort<list_removed, new_done>::sorted>;
};

template <typename Done>
struct top_sort<nil, Done>
{
  using sorted = nil;
};

namespace top_sort_test
{
  struct F1 {}; struct F2 {};

  struct A {
    using depends = nil;
    using provides = mklist<F1>::list;
  };

  struct B {
    using depends = mklist<F1>::list;
    using provides = mklist<F2>::list;
  };

  static_assert(std::is_same<top_sort<nil>::sorted, nil>::value, "!");

  using l1 = mklist<A, B>::list;
  static_assert(std::is_same<top_sort<l1>::sorted, l1>::value, "!");

  using l2 = mklist<B, A>::list;
  static_assert(std::is_same<top_sort<l2>::sorted, l1>::value, "!");
}

template <typename Field, typename View>
typename std::enable_if_t<
contains<Field, typename View::writable>::value,
  typename Field::type&>
get(View& v)
{
  auto& ref = v.ref();
  char* hack = reinterpret_cast<char*>(&ref);
  return *reinterpret_cast<typename Field::type*>(hack + Field::offset);
}

template <typename Field, typename View>
typename std::enable_if_t<
contains<Field, typename View::readonly>::value,
  const typename Field::type&>
get(View& v)
{
  auto& ref = v.ref();
  const char* hack = reinterpret_cast<char*>(&ref);
  return *reinterpret_cast<const typename Field::type*>(hack + Field::offset);
}

#define GET(s, f, v) get<FieldInfo<s>::f>(v)

template <typename Data, typename Depends, typename Provides>
class Pass
{
  public:
    using data_type = Data;
    using depends = Depends;
    using provides = Provides;

    // must be public so the top sort can access it (unless I intern top sort)
    struct MyView : public View<Data>
  {
    MyView(Data& s) : View<Data>(s) { }

    using readonly = Depends;
    using writable = Provides;
  };

    void run(Data& d)
    {
      MyView view(d);
      runImpl(view);
    }

  protected:
    virtual void runImpl(MyView&) = 0;
};

template <typename Data, typename PassList>
class PreparedPassList;

template <typename Data>
class PreparedPassList<Data, nil>
{
  public:
    void run(Data&) { /* all done */ }
};

template <typename Data, typename Head, typename Tail>
class PreparedPassList<Data, cons<Head, Tail>>
{
  public:
    void run(Data& d)
    {
      auto next = PreparedPassList<Data, Tail>();
      Head pass;
      pass.run(d);
      next.run(d);
    }
};

template <typename Data, typename PassList = nil>
class PassManager
{
public:
  using data_type = Data;
  using passes = PassList;

  template <typename Pass>
    std::enable_if_t<
      std::is_same<typename Pass::data_type, Data>::value,
    PassManager<Data, cons<Pass, PassList>>>
      addPass() { return {}; }
};

template <typename PassManager>
PreparedPassList<
  typename PassManager::data_type,
  typename top_sort<typename PassManager::passes>::sorted>
createPrepared(PassManager)
{
  return {};
}

// example usage

struct MyStruct
{
  int a;
  double b;
  std::string c;
};

template <>
struct FieldInfo<MyStruct>
{
  using a = Field<int,         offsetof(MyStruct, a)>;
  using b = Field<double,      offsetof(MyStruct, b)>;
  using c = Field<std::string, offsetof(MyStruct, c)>;
};

class PassZero : public Pass<MyStruct,
  // requires
  nil,
  // provides
  mklist<FieldInfo<MyStruct>::a, FieldInfo<MyStruct>::b>::list>
{

  protected:
    void runImpl(MyView& v) override
    {
      std::cout << "Ran Zero" << std::endl;
      GET(MyStruct, a, v) = 10;
      GET(MyStruct, b, v) = 10.10;

      // can't read (or write) c here
      // GET(MyStruct, c, v);
    }
};

class PassOne : public Pass<MyStruct,
  // requires
  mklist<FieldInfo<MyStruct>::a, FieldInfo<MyStruct>::b>::list,
  // provides
  mklist<FieldInfo<MyStruct>::c>::list>
{

  protected:
    void runImpl(MyView& v) override
    {
      std::cout << "Ran One" << std::endl;
      std::stringstream ss;
      ss << GET(MyStruct, a, v) << " : " << GET(MyStruct, b, v);
      GET(MyStruct, c, v) = ss.str();

      // can only write to c
    }
};

struct Empty { };

class PassEmpty : public Pass<Empty, nil, nil>
{
  protected:
    void runImpl(MyView& v) override { }
};

int main()
{
  MyStruct s{12, 1.1, "cats and dogs"};

  // create a pass builder and add the passes.
  // Order doesn't matter! The pass manager reorders the passes so that all
  // dependencies are satisfied before any passes which required them are needed
  PassManager<MyStruct> start;
  auto p1 = start.addPass<PassOne>();

  // Cannot create prepared pass list at this point. Will error with
  // "Dependencies not satisfied"
  // auto prepared = createPrepared(p2);

  auto p2 = p1.addPass<PassZero>();

  // cannot add PassEmpty to the pass manager (wrong data type)

  auto prepared = createPrepared(p2);
  prepared.run(s);

  // prints "PassZero", then "PassOne", even though passes added in a different
  // order
}