Ambiguous recursive template function

Question

In C++11, I need to call a function recursively from 0,...,n (where n is a compile time constant). This is the structure of the problem, which appears to be fatally flawed:

#include "Eigen/Dense"

template<size_t i>
struct Int {
};

template<size_t d, typename C, typename X>
constexpr X eval(const C &c, const X &x, const Int<d> &, const Int<C::SizeAtCompileTime - 1 - d> &) {
    return 1;
}

template<size_t d, typename C, typename X, size_t i>
constexpr X eval(const C &c, const X &x, const Int<d> &, const Int<i> &) {
    return x * eval(c, x, Int<d>(), Int<i + 1>());
}

int main() {
    const size_t d = 1;
    const Eigen::Matrix<double, 1, 7> c = Eigen::Matrix<double,1,7>::Zero();
    const double x = 5;
    eval(c, x, Int<d>(), Int<0>());
}

and the full error message:

/usr/bin/cmake --build /mnt/c/Dropbox/clion/recursion/cmake-build-debug --target recursion -- -j 4
Scanning dependencies of target recursion
[ 50%] Building CXX object CMakeFiles/recursion.dir/main.cpp.o
/mnt/c/Dropbox/clion/recursion/main.cpp: In instantiation of 'constexpr X eval(const C&, const X&, const Int<d>&, const Int<i>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double; long unsigned int i = 4ul]':
/mnt/c/Dropbox/clion/recursion/main.cpp:14:20:   recursively required from 'constexpr X eval(const C&, const X&, const Int<d>&, const Int<i>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double; long unsigned int i = 1ul]'
/mnt/c/Dropbox/clion/recursion/main.cpp:14:20:   required from 'constexpr X eval(const C&, const X&, const Int<d>&, const Int<i>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double; long unsigned int i = 0ul]'
/mnt/c/Dropbox/clion/recursion/main.cpp:21:34:   required from here
/mnt/c/Dropbox/clion/recursion/main.cpp:14:20: error: call of overloaded 'eval(const Eigen::Matrix<double, 1, 7>&, const double&, Int<1ul>, Int<5ul>)' is ambiguous
     return x * eval(c, x, Int<d>(), Int<i + 1>());
                    ^
/mnt/c/Dropbox/clion/recursion/main.cpp:8:13: note: candidate: constexpr X eval(const C&, const X&, const Int<d>&, const Int<((C:: SizeAtCompileTime - 1) - d)>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double]
 constexpr X eval(const C &c, const X &x, const Int<d> &, const Int<C::SizeAtCompileTime - 1 - d> &) {
             ^
/mnt/c/Dropbox/clion/recursion/main.cpp:13:13: note: candidate: constexpr X eval(const C&, const X&, const Int<d>&, const Int<i>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double; long unsigned int i = 5ul]
 constexpr X eval(const C &c, const X &x, const Int<d> &, const Int<i> &) {
             ^
/mnt/c/Dropbox/clion/recursion/main.cpp:15:1: error: body of constexpr function 'constexpr X eval(const C&, const X&, const Int<d>&, const Int<i>&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double; long unsigned int i = 4ul]' not a return-statement
 }

My understanding was that in the last line, x * eval(c, x, Int<d>(), Int<i + 1>());, when i+1 = n, then the first function which returns 1 would be chosen, but the compiler says that the call is ambiguous. Could somebody explain why? and how to fix this?

Note: I am aware that you cannot partially specialize a template function. I am trying to mimic the behavior instead with overloading.

---

EDIT

It seems that the issue lies in the expansion of C::SizeAtCompileTime. When I hard-code that constant, the program compiles. Is there a general C++ rule indicating why that is happening? or is that something that is Eigen specific?

Aronarondel

Mh... it is maybe an SFINAE situation? Nice question I think I will follow this one... – Baddie

I cannot reproduce that error. At least not with just the code you show. coliru.stacked-crooked.com/a/24f15d19b053ea01 – Anitaanitra

No. I was just trying to make the code nicer to read. I will edit with more complete code. – Aronarondel

I thought there was something wrong with the logic – Aronarondel

@StoryTeller I posted a complete code to reproduce the problem. – Aronarondel

This is pretty much as expected. When i increases to 5, both versions satisfy, thus ambiguity. – Demurral

The thing that doesn't make sense to me is that we are talking about an overload here, and in my mind that should mean that the specifc overload takes precendence – Aronarondel

I am not 100% sure, but rules for choosing a better fit for template resolution are not super simple. My guess would be, that when you hard code it, there is one less parameter in the set to be matched, and the less parameters the better the fit is. C::SizeAtCompileTime is dependent on C so it probably counts. Exact rules are gathered here: en.cppreference.com/w/cpp/language/… – Simper

Deciphering that is the hard part. Good link – Aronarondel

I see that @StoryTeller already did that. I didn't know whether dependent type counts toward the accepted types or the compiler gives it up altogether calling ambiguity. – Simper

Answer 1

The cause of the ambiguity, on one leg, is that you have two function templates that are equally as good as far as partial ordering is concerned. When the template argument of the first overload is not a dependent value (n in your original question), partial ordering can decide it just fine. But C::SizeAtCompileTime is dependent, and therefore partial ordering can no longer come to our rescue.

We can sort it out ourselves with SFINAE, however. All we need to do is to remove the second overload from the overload set when i is such that we may have a conflict. This can be done with a simple std::enable_if:

template<size_t d, typename C, typename X, size_t i>
constexpr auto eval(const C &c, const X &x, const Int<d> &, const Int<i> &)
  -> typename std::enable_if<i != C::SizeAtCompileTime - 1 - d, X>::type {
    return x * eval(c, x, Int<d>(), Int<i + 1>());
}

Anitaanitra

The alternative was to reverse the flow backwards from n...0, since in that case, I could hard-code a 0. But this saved me a lot of logic re-writing. Thanks – Aronarondel

I think my hunch was right, but is the exact reason for ambiguity just the presence of the dependent type, or that it just counts towards accepted types and both overloads are determined equivalent? In other words, does the compiler gives up partial ordering and calls the ambiguity just because one parameter is dependent? Or does partial ordering deem them equivalent? – Simper

@Simper - Partial ordering deems them equivalent. The argument being dependent alone is fine, or SFINAE wouldn't work at all. At least, that's my understanding of it. – Anitaanitra

I didn't mea that substitution should fail, only whether the dependent type counts as just one more type to match for ordering, or does it break the ordering and calls for ambiguity. I don't see how that would break SFINAE, only selecting best viable overload. But I can experiment by adding more template params. I've hoped you'd know it form the top of the head. Thanks anyways. – Simper