Re: Help needed debugging std::is_convertible problem (PR 65760)

[Daniel Krügler <daniel dot kruegler at gmail dot com>]

2015-04-16 14:33 GMT+02:00 Jonathan Wakely <jwakely.gcc@gmail.com>:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65760
>
> I don't understand why commenting out *any one* of the lines marked
> (1), (2), (3), (4) causes this to compile:
>
> #include <functional>
>
> struct C {
>     C() = default;
>
>     C(std::function<C(int)>);  // (1)
>     C(std::function<C(int, int)>); // (2)
>     template <class T> C operator () (T&&); // (3)
>     template <class T> C operator () (T&&, T&&); // (4)
> };

My current understanding of the state of affairs is still complete in
some details, but let me still throw in my 2 cents: The compiler sees
an object of C constructed by an rvalue of C. Now we have - in
addition to the copy/move constructors - two corresponding pairs of
function call operator and converting constructor to consider. Let me
simplify the situation a bit more by removing the additional layer of
template deduction of the call operators to:

struct C
{
  C() = default;

  C(std::function<C(int)>);  // (1)
  C(std::function<C(int, int)>); // (2)
  C operator()(int); // (3)
  C operator()(int, int); // (4)
};

In the presence of all four members the compiler is allowed (I think
by [temp.inst] p7) to instantiate one or both of the different
std::function specializations, because it has to respect possible
conversions. When this happens, the converting template constructor
declaration of std::function also needs to be instantiated. While
doing this, we come to the point where within the SFINAE condition
std::is_convertible<C, C> needs to be instantiated, effectively
leading to a situation that we have two different contexts, in which
the compiler needs to evaluate the result the self-conversion of C, C
never becoming completed to realize that during that attempt.

If *any* of the four members is missing, we don't have the situation
that two conversion sequences based on function template deduction
need to be partially ordered, we have only the non-template copy/move
constructor against exactly one possible function template. For this
to order, the compiler doesn't require instantiation of the converting
constructor of std::function.

[I strongly hope that someone will correct me, if this part of the
analysis is incorrect!]

> int main() {
>     C c = C();

Alternatively replace this line by the following one to demonstrate the problem:

static_assert(std::is_convertible<C, C>::value, "");

[The problem is *not* due to std::is_convertible specifically, because
you would observe the same problem with a completely independently
written my::is_convertible]

I have added two small attachments that further reduce the example
situation and make it completely library-free.

a) demo_1.cpp corresponds to the smallest case that I could realize to
simulate the behaviour of the example. Not all types are exactly
identical to the existing libstdc++ implementation, because I
intentionally refactored it a bit to be sure that there exist the best
possible separation of the templates I could think of. I see not
essentially no way how the library could be better as it currently is
(ignoring your fix suggestion, I will return to that a bit later
below) in this situation given the existing library requirements.

b) demo_2.cpp get's even rid of the call operators of C. By
eliminating the "callable" properties of C, it only looks at the two
converting constructors of C (taking a function value) and needs to
perform partial ordering of the two possible conversions, where in
each case the converting constructor template declaration of function
is allowed to to be instantiated (see above), which happens and leads
to the same problem as before. If only one of these C constructors
exists, the ordering can be decided directly without need to
instantiate the template c'tor declaration.

> My understanding is that the SFINAE constraint on the std::function
> constructor needs to check std::is_convertible<C, C> which requires C
> to be complete, but why does it only complain that C is incomplete
> when all of (1) - (4) are present?
>
> G++, Clang and EDG all agree on this behaviour, so I don't think it's
> a compiler bug. The libc++ std::function works fine in this case, I
> don't know what it does differently so that it works.
>
> To fix it I am considering short-circuiting the constraint to not use
> is_convertible<C, C>, by doing:
>
> __or_<is_same<From, To>, is_convertible<From, To>>
>
> which doesn't require the types to be complete when they're the same.
> Before doing that I'd really like to understand the problem properly.

Above I tried to present my current understanding, although I'm sure
that I described some details of this incorrectly.

Nonetheless, my understanding of your fix is that it actually is not
conforming to what the standard currently requires (This seems to
match you own thinking expressed above), because [func.wrap.func.con]
p8 requires:

"shall not participate in overload resolution unless f is Callable
(20.9.12.2) for argument types ArgTypes... and return type R."

and if we unroll this against the definition Callable (ending in
[func.require] p2) we finally end up in a required test whether the
return type of the invokable thingee has a value of
std::is_convertible<C, C>::value == true (C has the role of the return
type R). This is so, *even*, if LWG issue

http://cplusplus.github.io/LWG/lwg-active.html#2420

would be fixed as described, because we have no void return type involved here.

My current position is that we presumably have a Standard Library
issue lurking around, because I see no way how any library can
implement std::function without breaking this seemingly valid example
case. Either the Standard Library needs to express stronger
constraints on the return type R of std::function<R(ArgTypes...)> (so
to make the example invalid), or - what I would currently prefer - the
library would need to reduce the SFINAE constraints of the
std::function template constructor basically ending in not requiring
that R is complete, or in other words: not requiring the final part of
the Callable test involving the implicit conversion of the functor
result to the described result type R of
std::function<R(ArgTypes...)>.

To follow the intention of std::functions design, the Library could
require that when the constructor definition of

template<class F> function(F);

becomes instantiated, the current SFINAE requirements are to be
tested, possibly making this definition instantiation ill-formed.

Summarizing this, I consider your suggested resolution as useful for
practical reasons.

Sorry for the length of this write-up,

- Daniel

template<bool __v>
struct bool_constant { enum { value = __v} ; };

typedef bool_constant<true> true_type;
typedef bool_constant<false> false_type;

template<typename _Pp>
struct __not_ : bool_constant<!_Pp::value> { };

template<bool, typename, typename>
struct conditional;

template<typename _Iftrue, typename _Iffalse>
struct conditional<true, _Iftrue, _Iffalse>
{ typedef _Iftrue type; };

template<typename _Iftrue, typename _Iffalse>
struct conditional<false, _Iftrue, _Iffalse>
{ typedef _Iffalse type; };

template<typename...>
struct __and_;

template<typename _B1, typename _B2>
struct __and_<_B1, _B2> : conditional<_B1::value, _B2, _B1>::type { };

template<typename...>
struct __or_;

template<typename _B1, typename _B2>
struct __or_<_B1, _B2> : conditional<_B1::value, _B1, _B2>::type { };

template<class T>
T&& declval();
 
template<bool, class = void>
struct enable_if {};
 
template<class T>
struct enable_if<true, T> { typedef T type; };
 
template<class, class>
struct is_same : false_type {};
 
template<class T>
struct is_same<T, T> : true_type {};
 
template<typename _To1>
void __test_aux(_To1);

struct __is_convertible_helper
{
  template<typename _From1, typename _To1,
    typename = decltype(__test_aux<_To1>(declval<_From1>()))>
  static true_type __test(int);

  template<typename, typename>
  static false_type __test(...);
};

template<typename _From, typename _To>
struct is_convertible :
  decltype(__is_convertible_helper::__test<_From, _To>(0))
{ };

template<typename _From, typename _To>
using __check_func_return_type = is_convertible<_From, _To>;

template<typename _Cond>
using _Requires = typename enable_if<_Cond::value>::type;

template<typename _Functor, typename... _ArgTypes>
using _Invoke = decltype(declval<_Functor&>()(declval<_ArgTypes>()...));

template<typename _Functor, typename _Res, typename... _ArgTypes>
using _Callable = __check_func_return_type<_Invoke<_Functor, _ArgTypes...>, _Res>;

template<typename>
struct function;

template<typename _Res, typename... _ArgTypes>
struct function<_Res(_ArgTypes...)>
{
  template<typename _Functor,
    typename = _Requires<
      __and_<
        __not_<is_same<_Functor, function>>,
	    _Callable<_Functor, _Res, _ArgTypes...>
      >
    >
  >
  function(_Functor);
};

struct C 
{
  C() = default;

  C(function<C(int)>);  // (1)
  C(function<C(int, int)>); // (2)
  template <class T> C operator()(T&&); // (3)
  template <class T> C operator()(T&&, T&&); // (4)
};

int main() 
{
  C c = C();
}

template<bool __v>
struct bool_constant { enum { value = __v} ; };

typedef bool_constant<true> true_type;
typedef bool_constant<false> false_type;

template<typename _Pp>
struct __not_ : bool_constant<!_Pp::value> { };

template<bool, typename, typename>
struct conditional;

template<typename _Iftrue, typename _Iffalse>
struct conditional<true, _Iftrue, _Iffalse>
{ typedef _Iftrue type; };

template<typename _Iftrue, typename _Iffalse>
struct conditional<false, _Iftrue, _Iffalse>
{ typedef _Iffalse type; };

template<typename...>
struct __and_;

template<typename _B1, typename _B2>
struct __and_<_B1, _B2> : conditional<_B1::value, _B2, _B1>::type { };

template<typename...>
struct __or_;

template<typename _B1, typename _B2>
struct __or_<_B1, _B2> : conditional<_B1::value, _B1, _B2>::type { };

template<class T>
T&& declval();
 
template<bool, class = void>
struct enable_if {};
 
template<class T>
struct enable_if<true, T> { typedef T type; };
 
template<class, class>
struct is_same : false_type {};
 
template<class T>
struct is_same<T, T> : true_type {};
 
template<typename _To1>
void __test_aux(_To1);

struct __is_convertible_helper
{
  template<typename _From1, typename _To1,
    typename = decltype(__test_aux<_To1>(declval<_From1>()))>
  static true_type __test(int);

  template<typename, typename>
  static false_type __test(...);
};

template<typename _From, typename _To>
struct is_convertible :
  decltype(__is_convertible_helper::__test<_From, _To>(0))
{ };

template<typename _Cond>
using _Requires = typename enable_if<_Cond::value>::type;

template<typename _Functor, typename, typename...>
using _Callable = is_convertible<_Functor, _Functor>;

template<typename>
struct function;

template<typename _Res, typename... _ArgTypes>
struct function<_Res(_ArgTypes...)>
{
  template<typename _Functor,
    typename = _Requires<
      __and_<
        __not_<is_same<_Functor, function>>,
	    _Callable<_Functor, _Res, _ArgTypes...>
      >
    >
  >
  function(_Functor);
};

struct C 
{
  C() = default;

  C(function<C(int)>);  // (1)
  C(function<C(int, int)>); // (2)
};

int main() 
{
  C c = C();
}