return type deduction of recursive function

Question

Recently, I read Barry's answer to this question Recursive lambda functions in C++11:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};
// deduction guide
template <class F> y_combinator(F) -> y_combinator<F>;

Basically, y_combinator allows one to write a recursive lambda expression more easily (e.g. without having to delcare a std::function). When I played with y_combinator, I found something strange:

int main() {
   // Case #1 compiles fine
   y_combinator{[](auto g, int a, int b) {
      if (a >= b) return 0;
      return 1 + g(a + 1, b);
    }}(1, 2);

    // Case #2 deos not compile
    y_combinator{[](auto g, int a) {
      if (a >= 0) return 0;
      return 1 + g(a + 1);
    }}(1);

    // Case #3 compiles just fine
    y_combinator{[](auto g, int a)->int {
      if (a >= 0) return 0;
      return 1 + g(a + 1);
    }}(1);
}  

Case #1 and Case #3 compile fine while Case #2 does not compile. I got the same result with Clang 10.0 and GCC 9.3. For Case #2, Clang says

prog.cc:25:18: error: no matching function for call to object of type 'std::__1::reference_wrapper<const y_combinator<(lambda at prog.cc:23:18)> >'
      return 1 + g(a + 1);
                 ^

1. How is the different results between Case #1 and Case #2?
2. Why does the trailing return type make a difference between Case #2 and Case #3?

You can check it on Wandbox.

Answer 1

The difference is that in #1 the initial and recursive calls to y_combinator have different argument types, whereas in #2 they have the same argument types (including value category).

In #1, the initial arguments (1, 2) are both int prvalue, whereas the recursive arguments g(a + 1, b) are respectively int prvalue and int lvalue. Meanwhile in #2 the initial argument (1) and recursive argument g(a + 1) are both int prvalue. You can check that making a change to #1 such that both recursive arguments are int prvalue (e.g. calling g(a + 1, b + 0)) will break it, while changing #2 to pass int lvalue as the recursive argument (e.g. g(++a)) will fix it.

This means that the return type deduction for the initial call is self-referential, in that it depends on the type of precisely the same call to y_combinator<lambda #2>::operator()<int>(int&&) (whereas in #1 the initial call to y_combinator<lambda #1>::operator()<int, int>(int&&, int&&) depends on y_combinator<lambda #1>::operator()<int, int&>(int&&, int&)).

Supplying the return type explicitly as in #3 means there is no self-referential type deduction, and everything is fine.

You might ask, why is #1 OK given that the recursive case is still self-referential (noting that all 3 compilers agree). This is because once we can get into the lambda's own type deduction, [dcl.spec.auto]/10 kicks in and the first return statement gives a return type to the lambda, so when it recursively calls g, that type deduction has already succeeded.

A diagram usually helps:

y_combinator<lambda #1>::operator()<int, int>
 -> forwards to [lambda #1]::operator()<y_combinator<lambda #1>> {
     has return type int by [dcl.spec.auto]/10
     calls y_combinator<lambda #1>::operator()<int, int&> (not previously seen)
      -> forwards to [lambda #1]::operator()<y_combinator<lambda #1>>
      -> already deduced to return int
      -> this is OK
 }

y_combinator<lambda #2>::operator()<int>
  -> forwards to [lambda #2]::operator()<y_combinator<lambda #2>> {
     has return type int by [dcl.spec.auto]/10
     calls y_combinator<lambda #2>::operator()<int>
     but y_combinator<lambda #2>::operator()<int> has incomplete return type at this point
      -> error
  }

A fix (thanks to @aschepler) is to remember the argument lists that the lambda has been called with already, and provide a "clean" wrapper whose functional call operator(s) are not yet undergoing return type deduction for each new set of argument types:

template<class...> struct typelist {};

template<class T, class... Ts>
constexpr bool any_same = (std::is_same_v<T, Ts> || ...);

template <class F>
struct y_combinator {
    template <class... TLs>
    struct ref {
        y_combinator& self;
        template <class... Args>
        decltype(auto) operator()(Args&&... args) const {
            using G = std::conditional_t<
                any_same<typelist<Args...>, TLs...>,
                ref<TLs...>,
                ref<TLs..., typelist<Args...>>>;
            return self.f(G{self}, std::forward<Args>(args)...);
        }
    };
    F f;
    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return ref<>{*this}(std::forward<Args>(args)...);
    }
};
template <class F> y_combinator(F) -> y_combinator<F>;