1
\$\begingroup\$

Context:

Within a template expression library (link for reference; warning: work in progress), each expression has a number of traits associated with it. These traits are looked up through simple template specialization:

template<>
struct expr_traits<IntConstant> {
  enum {
    TRAIT_A = true,
    TRAIT_B = true,
  };
};

template<typename LHS, typename RHS>
struct expr_traits<BinopPlus<LHS, RHS>> {
  enum {
    TRAIT_A = expr_traits<LHS>::TRAIT_A,
    TRAIT_B = expr_traits<LHS>::TRAIT_B || expr_traits<RHS>::TRAIT_B,
  };
};

This was working just fine until I had to implement the recursivity expression. In order to prevent the compiler from running into a dependency loop, I came up with a hare-brained scheme.

The loops are broken up by "tagging" the trait lookup type when we first evaluate it, so that we can select a different specialization the second time it's evaluated during a cycle. So far, so good.

However, since recursive expressions can invoke other recursive expressions, that tag must be maintained as a list of types. To top it all off, dependency order is not guaranteed to be stack-like (There can be a A->B->A cycle). So the end result is, frankly, too convoluted for my taste, even if it does work.

Edit: Specifically, I don't like that someone implementing a new expression type needs to deal with a mysterious RECUR_TAG template parameter he/she would have to propagate. The Recur<> expression is just spilling accross the entire code base, which breaks the compartmentalization I've been bale to maintain up to now.

(Note: the code is not quite identical as found in the linked project for the sake of isolating the feature I want reviewed, and removing the project-specific lingo and complexity)

#include <type_traits>
#include <tuple>
#include <memory>

using std::is_same;
using std::tuple;
using std::tuple_element_t;
using std::enable_if_t;

template <typename T, typename... ARGS_T>
struct is_one_of : public std::false_type {};

template <typename T, typename U, typename... REST_T>
struct is_one_of<T, U, REST_T...>
  : public std::conditional_t<std::is_same<T, U>::value, std::true_type,
  is_one_of<T, REST_T...>> {};
struct IntConstant {};

template<typename LHS_T, typename RHS_T>
struct BinopPlus {
  BinopPlus(LHS_T const&, RHS_T const&) {}
};

template<typename RECUR_CHILD_T>
struct Recur {
  Recur() : child_(std::make_shared<std::unique_ptr<RECUR_CHILD_T>>()) {}
  Recur(Recur const& rhs) : child_(rhs.child_) {}

  Recur& operator=(RECUR_CHILD_T const& rhs) {
    *child_ = std::make_unique<RECUR_CHILD_T>(rhs);
    return *this;
  }

  Recur& operator=(RECUR_CHILD_T && rhs) {
    *child_ = std::make_unique<RECUR_CHILD_T>(std::move(rhs));
    return *this;
  }

private:
  // This way, all existing copies of this instance will be updated
  // once the child is assigned.
  std::shared_ptr<std::unique_ptr<RECUR_CHILD_T>> child_;
};

#define ASSIGN_RECUR(local_var, RECUR_CHILD_T, expr) \
      struct RECUR_CHILD_T : public decltype(expr) {     \
        using expr_t = decltype(expr);                   \
        RECUR_CHILD_T(expr_t const& e) : expr_t(e) {}    \
        RECUR_CHILD_T(expr_t && e) : expr_t(e) {}        \
      };                                                 \
      local_var = expr;

// Main trait lookup template is updated with a *TAG* type
template <typename EXPR_T, typename RECUR_TAG_T, typename Enable = void>
struct expr_traits;

template<typename RECUR_TAG>
struct expr_traits<IntConstant, RECUR_TAG> {
  enum {
    TRAIT_A = true,
    TRAIT_B = true,
  };
};

template<typename LHS, typename RHS, typename RECUR_TAG_T>
struct expr_traits<BinopPlus<LHS, RHS>, RECUR_TAG_T> {
  enum {
    // recur tags are propagated as-is through the dependency chain.
    TRAIT_A = expr_traits<LHS, RECUR_TAG_T>::TRAIT_A,
    TRAIT_B = expr_traits<LHS, RECUR_TAG_T>::TRAIT_B || expr_traits<RHS, RECUR_TAG_T>::TRAIT_B,
  };
};


// Recur specializations of `expr_traits<>`

// Main entry point of attribute resolution for recursive expressions.
// A straight propagation of the recur's assigned traits, However, RECUR_TAG
// gets set to tuple<THIS_Type>

template <typename RECUR_CHILD>
struct expr_traits<Recur<RECUR_CHILD>, void> {
  using sub_traits =
    expr_traits<typename RECUR_CHILD::expr_t, std::tuple<RECUR_CHILD>>;

  enum {
    TRAIT_A = sub_traits::TRAIT_A,
    TRAIT_B = sub_traits::TRAIT_B,
  };
};

// This handles "simple" cases, where a recursive expression depends on itself.
// This is determined by the front of the TAG tuple being RECUR_CHILD_T    
// In that scenario, we choose optimistic values that may be overriden by the
// parent evaluator.
template <typename RECUR_CHILD_T, typename... TYPES>
struct expr_traits<
  Recur<RECUR_CHILD_T>, std::tuple<TYPES...>,
  enable_if_t< is_same<
      tuple_element_t<0, tuple<TYPES...>>,
      RECUR_CHILD_T
    >::value>> {
  // These are provisional flags, only used for the first pass
  enum {
    TRAIT_A = true,
    TRAIT_B = false,
  };
};


// If RECUR_CHILD_T is not in the tag tuple, then we have a recur depending on a recur,
// we treat this as if we initially entered the evaluation, however, we keep the
// existing recurs in the tuple so that we can catch cyclical loops.
template <typename RECUR_CHILD_T, typename... TYPES>
struct expr_traits<
  Recur<RECUR_CHILD_T>, std::tuple<TYPES...>,
  enable_if_t<!is_one_of<RECUR_CHILD_T, TYPES...>::value>> {
  using sub_traits =
    expr_traits<typename RECUR_CHILD_T::expr_t, std::tuple<RECUR_CHILD_T, TYPES...>>;

  enum {
    TRAIT_A = sub_traits::TRAIT_A,
    TRAIT_B = sub_traits::TRAIT_B,
  };
};


// Finally, this is trouble. If we get here, it means we have a scenario where
// expr A depends on expr B that depends on exprA. In that scenario,
// we can't recurse down, and we have to be pessimistic about our initial guess
// of the traits (unfortunately).
template <typename RECUR_CHILD_T, typename... TYPES>
struct expr_traits<
  Recur<RECUR_CHILD_T>, std::tuple<TYPES...>,
  enable_if_t<is_one_of<RECUR_CHILD_T, TYPES...>::value &&
      !is_same<
        tuple_element_t<0, tuple<TYPES...>>,
        RECUR_CHILD_T
      >::value>> {
  enum {
    TRAIT_A = false,
    TRAIT_B = true,
  };
};


// Usage
int main() {
  IntConstant a;
  IntConstant b;
  BinopPlus<IntConstant, IntConstant> c(a, b);

  // No actual recursion
  {
    Recur<struct ABC> recur_a;
    ASSIGN_RECUR(recur_a, ABC, c);

    int tmp = expr_traits<decltype(recur_a), void>::TRAIT_A;
  }

  // simple recursion
  {
    Recur<struct ABC> recur_a;

    auto expr = BinopPlus<Recur<struct ABC>, IntConstant>(recur_a, a);

    ASSIGN_RECUR(recur_a, ABC, expr);
    int tmp = expr_traits<decltype(recur_a), void>::TRAIT_A;
  }

  // stacking recursion
  {
    Recur<struct ABC> recur_a;
    Recur<struct DEF> recur_b;

    auto expr_a = BinopPlus<Recur<struct ABC>, IntConstant>(recur_a, a);
    auto expr_b = BinopPlus<Recur<struct ABC>, Recur<struct DEF>>(recur_a, recur_b);

    ASSIGN_RECUR(recur_a, ABC, expr_a);
    ASSIGN_RECUR(recur_b, DEF, expr_b);

    int tmp_a = expr_traits<decltype(recur_a), void>::TRAIT_A;
    int tmp_b = expr_traits<decltype(recur_b), void>::TRAIT_A;
  }

  // chained recursion
  {
    Recur<struct ABC> recur_a;
    Recur<struct DEF> recur_b;

    auto expr_a = BinopPlus<Recur<struct DEF>, IntConstant>(recur_b, a);
    auto expr_b = BinopPlus<Recur<struct ABC>, IntConstant>(recur_a, a);

    ASSIGN_RECUR(recur_a, ABC, expr_a);
    ASSIGN_RECUR(recur_b, DEF, expr_b);

    int tmp_a = expr_traits<decltype(recur_a), void>::TRAIT_A;
    int tmp_b = expr_traits<decltype(recur_b), void>::TRAIT_A;
  }

  return 0;
}

Obviously, the library makes aggressive use of operator overloading, so the user-facing API is actually much nicer. However, adding that feature to this snippet would have added a whole lot of boilerplate that would draw focus away from the part I need reviewed. If you want to see actual usage of this, you can find it in the tests/patterns/test_recur.cpp file in the linked github project

What I'm looking for

  1. A review of the way the 4 specilizations of expr_traits<Recur<...>> are built
  2. While we are at it, I would welcome any suggestions on how to improve the jankiness around using the ASSIGN_RECUR macro.
  3. As usual, any comments/suggestions about the code in general.
\$\endgroup\$
  • \$\begingroup\$ Can you explain what a std::shared_ptr<std::unique_ptr<T>> gives you that's not provided by plain std::shared_ptr<T>? I've never seen such a construct required anywhere before. \$\endgroup\$ – Toby Speight Sep 21 '17 at 17:35
  • \$\begingroup\$ @TobySpeight the stacking recursion example illustrates this, recur_a gets assigned by value to both expr_a and expr_b. However, recur_a only gets its payload assigned afterwards. That constructs essentially propagates the assignment to all instances of Recur<> that were created from recur_a originally. It's similar to old-school C handles implemented via double-pointers. \$\endgroup\$ – Frank Sep 21 '17 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.