pransr.in

Needle in a Haystack

Posted on May 14, 2022

I was at work this week when I saw some nice spaghetti code that essentially had this structure:

int func_arg1(int a, float b, float c, float d, float e, float f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg2(float a, int b, float c, float d, float e, float f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg3(float a, float b, int c, float d, float e, float f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg4(float a, float b, float c, int d, float e, float f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg5(float a, float b, float c, float d, int e, float f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg6(float a, float b, float c, float d, float e, int f, float g) {
    return a + b + c + d + e + f + g;
}

int func_arg7(float a, float b, float c, float d, float e, float f, int g) {
    return a + b + c + d + e + f + g;
}

This had to be templateable right? The implementations were identical, if there were ever a time for generics, this was it. Moreover, another family of functions followed, with floats and ints being replaced with other types, but the same structure, and, again, the same implementation. Something had to be done.

The Problem

Broadly, what I wanted was a templated function that produced the entire family of functions above for free. The constraint I wanted enforced was

  • All arguments are of one of two types, a Needle or a Haystack.
  • There was precisely one Needle, and the index of the Needle could be enforced via another template parameter.

Effectively, I wanted to reimplement all of these functions as

template <typename Needle, typename Haystack, size_t idx>

so that they could be invoked as such:

//int test1 = func_arg1(1, 2.0, 3.0);
int test1 = func<int, float, 1>(1, 2.0, 3.0);

//int test2 = func_arg2(1.0, 2, 3.0);
int test1 = func<int, float, 2>(1.0, 2, 3.0);

And get compile-time errors for type errors for bad indices or misconfigured arguments. I encourage you to go out and get something working! I’m always curious to hear other solutions that might be cleaner than what I came up with. Otherwise, read on to see a few of the approaches I took.

The Failed Variadic Experiment

My initial thoughts were to use variadic templates to generalize the number of arguments in addition to creating the full family. I’m by no means a variadic template expert, so my initial solution made the cardinal sin of attempting to include two sets of variadic arguments in the same template, by doing something like this:

template <typename Needle, typename Haystack, 
          typename... PreArgs, typename...PostArgs>
int func(PreArgs... pre_args, Needle n, PostArgs... post_args);

I ran into specialization errors when attempting to use multiple sets of parameters to represent the Haystack types before and after the needle. I messed around with different approaches to try and separate at the first Needle to no avail – as I couldn’t enforce any guarantees on the PreArgs or PostArgs, the binding inevitably ended up consuming the Needle being passed in. So, my initial approach was a bit more limited: I’d fix the number of arguments to the function.

Step 1: No variadics, std::conditional

By losing the variadic component, it was pretty easy to create a function that does what we want with std::conditional to enforce the type of the argument based on the index.

#include <type_traits>

template <typename Needle, typename Haystack, size_t idx>
int func(
    std::conditional_t<idx == 1, Needle, Haystack> a,
    std::conditional_t<idx == 2, Needle, Haystack> b,
    std::conditional_t<idx == 3, Needle, Haystack> c,
    std::conditional_t<idx == 4, Needle, Haystack> d,
    static_assert(0 < idx && idx <= 4);
    a + b + c + d;
}

This worked basically as I wanted:

struct NeedleS {
  int x;
};

template <typename T>
int operator + (NeedleS const& lhs, T const& t) {
  return lhs.x + t;
}
template <typename T>
int operator + (T const& t, NeedleS const& rhs) {
  return rhs.x + t;
}

int main() {
    NeedleS x = {4};
    int test1 = func<NeedleS, int, 1>(x,1,2,3);
    int test2 = func<NeedleS, int, 2>(3,x,5,6);
    int test3 = func<NeedleS, int, 3>(7,5,x,6);
    int test4 = func<NeedleS, int, 4>(1,2,3,x);

    // fails to compile
    // int test5 = func<NeedleS, int, 2>(1,x,x,4);

    //ideally want this to fail, but float gets converted to int...
    // int test5 = func<NeedleS, int, 2>(1,x,2.0,4);
    return 0;
}

But had some obvious drawbacks:

  • Boilerplate index comparison code
  • Fixed number of arguments
  • As the arguments were conditionals, standard casting went uncaught and I could pass a float in for an int without a compilation error.

To fix this, it was clear that variadics needed to be reintegrated, but the initial problem of binding the type information also needed to be enforced – enter the C++ concept.

Step 2: Variadics and C++20 concepts

Our hardcoded example basically conveyed the strategy – we wanted to create an index-based concept that enforced the appropriate type information on the argument based on the index. Inspired by stack exchange, I started with this:

template <typename Needle, typename Haystack, size_t idx, typename... Args>
concept needle_in_haystack = 
        std::conjunction_v<
            std::is_same<
                std::tuple_element_t<idx, std::tuple<Args...>>,
                std::conditional_t<(idx == ???), Needle, Haystack>
            >...
        >;

Perhaps you can spot the problem. We need the indices of the arguments to be available as well, so that we could complete the comparison. However, as we learned before, something like template <typename Needle, typename Haystack, size_t idx, typename... Args, size_t... indices> wouldn’t work because of the same double variadic binding problem. For this, we needed a workaround with tuple-based wrapping. So, lets start at the base. The function simply bundles its (variable) number of arguments into a single tuple argument.

// base implementation. calls into a tupled version.
// Can't have both indices and args as variadic as then the indices
// are matched into the args
template <typename Needle, typename Haystack, size_t idx, typename... Args>
int func(Args... args) {
    return func_tuple<Needle, Haystack, idx, std::tuple<Args...>>
        (std::make_tuple(args...));
}

The tuple-based version does a nice trick with a std::index_sequence. We create a default template parameter that creates an index sequence based on the size of the tuple:

// receives the variadic args as a tuple, and passes a default
// template argument of indices for expansion
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, 
          typename indices = std::make_index_sequence<std::tuple_size_v<ArgTuple>>>
int func_tuple(ArgTuple t) {
    return func_seq<Needle, Haystack, idx, ArgTuple>(t, indices{});
}

Now, we can expand the indices into our variadic arguments, while having the arguments prepacked into a tuple already:

// expands the indices into a variadic sequence in template
// also calculates the sum
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, size_t... Is>
int func_seq(ArgTuple t, std::index_sequence<Is...> i) {
    return (std::get<Is>(t) + ...);
}

From here, we can create our concept with our indices arriving variadically and our tuple being packed (the same argument structure as func_seq()), and complete our implementation. The only change is the pre-created tuple being parsed in std::tuple_element_t as opposed a tuple we make on the fly, and we use the indices to do the parameter pack expansion.

// index based concept. conjunction on index check for type
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, size_t... Is>
concept needle_in_haystack = 
  std::conjunction_v<
    std::is_same<
      std::tuple_element_t <Is, ArgTuple >,
      std::conditional_t<idx - 1 == Is, Needle, Haystack>
    >...
  >;

Finally, we enforce our concept on the previous func_seq() function:

// expands the indices into a variadic sequence in template
// also calculates the sum
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, size_t... Is>
   requires needle_in_haystack<Needle, Haystack, idx, ArgTuple, Is...>
int func_seq(ArgTuple t, std::index_sequence<Is...> i) {
    return (std::get<Is>(t) + ...);
}

And it’s done! Here’s the full code along with the test cases:

#include <cstddef>
#include <tuple>
#include <type_traits>
#include <utility>

// index based concept. conjunction on index check for type
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, size_t... Is>
concept needle_in_haystack = 
  std::conjunction_v<
    std::is_same<
      std::tuple_element_t <Is, ArgTuple >,
      std::conditional_t<idx - 1 == Is, Needle, Haystack>
    >...
  >;

// expands the indices into a variadic sequence in template
// also calculates the sum
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, size_t... Is>
   requires needle_in_haystack<Needle, Haystack, idx, ArgTuple, Is...>
int func_seq(ArgTuple t, std::index_sequence<Is...> i) {
    return (std::get<Is>(t) + ...);
}

// receives the variadic args as a tuple, and passes a default
// template argument of indices for expansion
template <typename Needle, typename Haystack, size_t idx, typename ArgTuple, 
          typename indices = std::make_index_sequence<std::tuple_size_v<ArgTuple>>>
int func_tuple(ArgTuple t) {
    return func_seq<Needle, Haystack, idx, ArgTuple>(t, indices{});
}

// base implementation. calls into a tupled version.
// Can't have both indices and args as variadic as then the indices
// are matched into the args
template <typename Needle, typename Haystack, size_t idx, typename... Args>
int func(Args... args) {
    return func_tuple<Needle, Haystack, idx, std::tuple<Args...>>
        (std::make_tuple(args...));
}

// test class
struct NeedleS {
    int x;
};

template <typename T>
int operator + (NeedleS const& lhs, T const& t) {
    return lhs.x + t;
}
template <typename T>
int operator + (T const& t, NeedleS const& rhs) {
    return rhs.x + t;
}

int main() {
    NeedleS x = {4};
    int test = func<NeedleS, int, 1>(x,1,2,3);
    int test2 = func<NeedleS, int, 2>(3,x,5,6);
    int test3 = func<NeedleS, int, 3>(7,5,x,6);
    int test4 = func<NeedleS, int, 4>(1,2,3,x);

    // fails to compile (double)
    // int test5 = func<NeedleS, int, 2> (1,x,2.0,4);

    //fails to compile (two needles)
    // int test6 = func<NeedleS, int, 2> (1,x,x,4);

    //fails to compile (wrong idx)
    // int test7 = func<NeedleS, int, 3>(1,2,3,x);
    return 0;
}

Notice here we’ve solved all of our problems: we support a variable number of arguments, we iteratively perform the std::conditional check, and, as a nice bonus, the strictness of std::is_same prevents the casting problem we encountered in our previous approach.

Conclusion

I picked up a decent bit of knowledge about template binding and static type-checking, but I’m by no means an expert – there are probably cleaner ways to express the above family of functions. Using static_assert to start with a generic function and restricting the arguments coming in is another approach to this problem, but I wanted to stick with the “explicit description of the type signature” approach that led me to the above solution. I’d love to see other ways of producing this family of functions. For now, I have some code cleanup to do…