Can SFINAE interfere with partial ordering?

Question

I'm working on a library that uses a pretty old C++ expression template (ET) engine named PETE. (I tried finding a link to its source code so I could cite it but I only found articles about it.)

Quick overview: With ET the C++ compiler builds from an expression using the operator infix-form (+,-,*,/) a C++ type which represents the expression and its operations. Central to PETE's approach is the ForEach class template that is used to later parse and evaluate the expression.

What I'm trying to do is to provide a specialized ForEach that gets used when its argument meet a specific condition. I'm trying this with partial specialisation and the use of enable_if but the compiler complains about 'ambiguous partial specialization'.

I'm happy to post other parts of the code if needed, but I'll stick to the direct class template in question (NB: I added the Enable parameter in order to make the later specializations selectable with enable_if. NB2: For the sake of a shorter post I don't include the implementation of the method):

template<class Expr, class FTag, class CTag, class Enable = void>
struct ForEach
{
  typedef typename LeafFunctor<Expr, FTag>::Type_t Type_t;
  inline static
  Type_t apply(const Expr &expr, const FTag &f, const CTag &)
  {
    // empty
  }
};

Then comes the first partial specialization (also part of standard PETE). This is what is later called number '1':

// 1
template<class Op, class A, class B, class FTag, class CTag>
struct ForEach<BinaryNode<Op, A, B>, FTag, CTag >
{
  typedef typename ForEach<A, FTag, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, FTag, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, Op, CTag>::Type_t Type_t;
  inline static
  Type_t apply(const BinaryNode<Op, A, B> &expr, const FTag &f,
           const CTag &c) 
  {
    // default implementation for BinaryNode
  }
};

Here comes my additional partial specialization where the compiler complains. It actually complains at number '2' being ambiguous with number '1':

// A
template<class A, class B, class CTag>
struct ForEach<BinaryNode<OpMultiply, A, B>, ViewSpinLeaf, CTag , enable_if_t< ! EvalToSpinMatrix<A>::value > >
{
  typedef typename ForEach<A, ViewSpinLeaf, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, ViewSpinLeaf, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, OpMultiply, CTag>::Type_t Type_t;
  inline static
  Type_t apply(const BinaryNode<OpMultiply, A, B> &expr, const ViewSpinLeaf &f,
           const CTag &c)
  {
    // default implementation for BinaryNode (this is the same as above)
  }
};


// 2
template<class A, class B, class CTag>
struct ForEach<BinaryNode<OpMultiply, A, B>, ViewSpinLeaf, CTag , enable_if_t< EvalToSpinMatrix<A>::value > >
{
  typedef typename ForEach<A, ViewSpinLeaf, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, ViewSpinLeaf, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, OpMultiply, CTag>::Type_t Type_t;

  inline static
  Type_t apply(const BinaryNode<OpMultiply, A, B> &expr, const ViewSpinLeaf &f, const CTag &c) 
  {
    // special implementation for when EvalToSpinMatrix<A>::value is true 
  }
};

The compiler error is as follows (NB: I reformatted it for enhanced readability)

  ambiguous template instantiation for ‘struct ForEach<BinaryNode<OpMultiply, Vector<double>, Vector<double> >, ViewSpinLeaf, OpCombine, void>’

  candidate '1':
    candidates are: template<class Op, class A, class B, class FTag, class CTag> struct ForEach<BinaryNode<Op, A, B>, FTag, CTag> ;
Op = OpMultiply;
A = Vector<double>;
B = Vector<double>;
FTag = ViewSpinLeaf;
CTag = OpCombine;

  candidate '2':
note:   template<class A, class B, class CTag> struct ForEach<BinaryNode<OpMultiply, T1, T2>, ViewSpinLeaf, CTag, typename std::enable_if<EvalToSpinMatrix<A>::value, void>::type>;
A = Vector<double>;
B = Vector<double>;
CTag = OpCombine;

From what I understand the standard applies what's called 'partial ordering' which says that a partial specialisation is more specialised than another if it is as least as specialised as the other but not the other way around. Applied to this example this says:

Number 2 is at least as specialised as number 1 since for each parameter set (for number 2) I can find a set (for number 1) that matches. But Number 1 is not at least as specialised as number 2. If I set FTag to anything but ViewSpinLeaf then number 2 cannot match. As a result, number 2 is more specialised. So, I don't understand why the compiler doesn't see it that way.

As a 2nd test I removed specialisation 'A' (the one with the negative enable_if) and removed the enable_if_t bit from specialisation '2'. This compiles fine, meaning that all the other statements/typedefs inside number '2' work. However, this is not what I need as this code path is then taken for all BinaryNode<OpMultiply,..> and not just for the specific case.

In case it matters. The compiler I'm using is g++ 9.3 on Ubuntu with standard C++14 enabled.

EDIT: As suggested in a comment there might be an ambiguity between BinaryNode<Op,..> and BinaryNode<OpMultiply,..>. I change number '2' to the following:

// 2
template<class Op, class A, class B, class CTag>
struct ForEach<BinaryNode<Op, A, B>, ViewSpinLeaf, CTag , enable_if_t< EvalToSpinMatrix<A>::value > >
{
  typedef typename ForEach<A, ViewSpinLeaf, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, ViewSpinLeaf, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, Op, CTag>::Type_t Type_t;

  inline static
  Type_t apply(const BinaryNode<OpMultiply, A, B> &expr, const ViewSpinLeaf &f, const CTag &c) 
  {
  }
  
  inline static
  Type_t apply(const BinaryNode<Op, A, B> &expr, const ViewSpinLeaf &f, const CTag &c)
  {
  }
};

Now there's only the FTag more specialised. The compiler complains about the same ambiguity:

note: candidates are: ‘template<class Op, class A, class B, class FTag, class CTag> struct ForEach<BinaryNode<Op, A, B>, FTag, CTag>;
Op = OpMultiply;
A = Vector<double>;
B = Vector<double>;
FTag = ViewSpinLeaf;
CTag = OpCombine;

‘template<class Op, class A, class B, class CTag> struct ForEach<BinaryNode<Op, A, B>, ViewSpinLeaf, CTag, typename std::enable_if<EvalToSpinMatrix<A>::value, void>::type>;
Op = OpMultiply;
A = Vector<double>;
B = Vector<double>;
CTag = OpCombine;

Number '2' is clearly more specialised.

EDIT2: Adding a minimal reproducer. There's an #if 0 which if left like this the program compiles and takes the default code path. However, when the partial specializations are turned on with #if 1 then the ambiguity is reproduced.

#include<type_traits>
#include<iostream>

using namespace std;


template<class T>        class Vector {};

struct ViewSpinLeaf {};
struct OpCombine {};

template<class LeafType, class LeafTag> struct LeafFunctor {};
template<class A, class B, class Op, class Tag> struct Combine2 {};


template<class T1, class T2, class Op>
struct BinaryReturn {
  typedef T1 Type_t;
};


template<class T>
struct LeafFunctor<Vector<T>, ViewSpinLeaf>
{
  typedef T Type_t;
  inline static
  Type_t apply(const Vector<T> & s, const ViewSpinLeaf& v)
  {
    return Type_t();
  }
};


template<class A,class B,class Op>
struct Combine2<A, B, Op, OpCombine>
{
  typedef typename BinaryReturn<A, B, Op>::Type_t Type_t;
  inline static
  Type_t combine(const A& a, const B& b, const Op& op, const OpCombine& do_not_use)
  {
    return op(a, b);
  }
};

struct OpMultiply
{
  template<class T1, class T2>
  inline typename BinaryReturn<T1, T2, OpMultiply >::Type_t
  operator()(const T1 &a, const T2 &b) const
  {
    return (a * b);
  }
};


template<class Op, class Left, class Right>
class BinaryNode
{
public:
  BinaryNode(const Op &o, const Left &l, const Right &r) : op_m(o), left_m(l), right_m(r) {}

private:
  Op    op_m;
  Left  left_m;
  Right right_m;
};





template<class Expr, class FTag, class CTag, class Enable = void >
struct ForEach
{
  typedef typename LeafFunctor<Expr, FTag>::Type_t Type_t;
  inline static
  Type_t apply(const Expr &expr, const FTag &f, const CTag &)
  {
    return LeafFunctor<Expr, FTag>::apply(expr, f);
  }
};



template<class Expr, class FTag, class CTag>
inline typename ForEach<Expr,FTag,CTag>::Type_t
forEach(const Expr &e, const FTag &f, const CTag &c)
{
  return ForEach<Expr, FTag, CTag>::apply(e, f, c);
}


template<class Op, class A, class B, class FTag, class CTag>
struct ForEach<BinaryNode<Op, A, B>, FTag, CTag >
{
  typedef typename ForEach<A, FTag, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, FTag, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, Op, CTag>::Type_t Type_t;
  inline static
  Type_t apply(const BinaryNode<Op, A, B> &expr, const FTag &f,
           const CTag &c) 
  {
    std::cout << "I don't want to be here. " << std::endl;
    return Type_t();
  }
};






#if 0

template<class A>
struct EvalToSpinMatrix
{
  constexpr static bool value = false;
};

template<>
struct EvalToSpinMatrix<Vector<double> >
{
  constexpr static bool value = true;
};



template<class A, class B, class CTag>
struct ForEach<BinaryNode<OpMultiply, A, B>, ViewSpinLeaf, CTag , enable_if_t< EvalToSpinMatrix<A>::value > >
{
  typedef typename ForEach<A, ViewSpinLeaf, CTag>::Type_t TypeA_t;
  typedef typename ForEach<B, ViewSpinLeaf, CTag>::Type_t TypeB_t;
  typedef typename Combine2<TypeA_t, TypeB_t, OpMultiply, CTag>::Type_t Type_t;

  inline static
  Type_t apply(const BinaryNode<OpMultiply, A, B> &expr, const ViewSpinLeaf &f, const CTag &c) 
  {
    std::cout << "I want to get here. " << std::endl;
    return Type_t();
  }
};
#endif



int main(int argc, char **argv)
{
  OpMultiply op;
  Vector<double> left;
  Vector<double> right;

  BinaryNode< OpMultiply , Vector<double> , Vector<double> > rhs(op,left,right);
  
  forEach( rhs , ViewSpinLeaf() , OpCombine() );
}

I should have said that it is important to select the partial specialization with the enable_if switch based on the EvalToSpinMatrix trait. Obviously in the real application this trait is more complicated. Good that it reproduces the ambiguity in this simple version.

Answer 1

First of all, I simplified the code to the minimum, by chopping off anything that wasn't needed to reproduce the error. It all boils down to why the partial specializations are ambiguous in the following (I'm sorry for having changed the name of the various bits, but un-bloating your code was not an easy task, at least for me):

#include <utility>

template<typename T, typename = void>
struct A {};

template<typename T, typename U>
struct A<std::pair<T,U>> {};

template<typename U>
struct A<std::pair<int,U>, std::enable_if_t<std::is_same_v<int,U>>> {};

int main() {
  A<std::pair<int, int>> x;
}

It looks a lot like the second partial specialization is more specialized then the first, but it actually isn't.

Let's go to the Partial ordering section on cppreference and let's read all of that:

Informally "A is more specialized than B" means "A accepts a subset of the types that B accepts".

Formally, to establish more-specialized-than relationship between partial specializations, each is first converted to a fictitious function template as follows:

• the first function template has the same template parameters as the first partial specialization and has just one function parameter, whose type is a class template specialization with all the template arguments from the first partial specialization
• [the same as above, but s/first/second/g].

The function templates are then ranked as if for function template overloading.

Then an interseting example follows.

In the case of the simplified code, this means that the fictitious function template corresponding to the first specialization has signature

template<typename T, typename U>
void f(A<std::pair<T,U>>);

whereas the one corresponding to the second specialization has signature

template<typename U>
void f(A<std::pair<int,U>, std::enable_if_t<std::is_same_v<int,U>>>) {}

and these are two distinct overloads of a function template. So the question has been shifted to which of them is preferred via the rules described at the second link above.

Honestly, at this point I was a bit lost, so I asked a question, and the answer is that even though the second overload is fixing the first template argument of std::pair to int, the first overload is fixing the second template argument of A to void, so none of them is more specialized than the other. And std::enable_if/std::enable_if_t doesn't alter the situation, because it's used as the type (void, as we're not passing a second template argument to it) of a function parameter, not as a template type parameter.