递归函数的返回类型推导

Question

最近，我阅读了Barry对这个问题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>;

基本上，y_combinator允许更轻松地编写递归 lambda 表达式（例如，无需 delcare a std::function）。当我玩的时候y_combinator，我发现了一些奇怪的东西：

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);
}  

案例#1 和案例#3 编译得很好，而案例#2 无法编译。我在 Clang 10.0 和 GCC 9.3 上得到了相同的结果。对于案例#2，Clang 说

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. 案例#1 和案例#2 的结果有何不同？
2. 为什么尾随返回类型会在案例 #2 和案例 #3 之间产生差异？

您可以在Wandbox上查看。

Answer 1

不同之处在于，在#1 中，初始调用和递归调用具有y_combinator不同的参数类型，而在#2 中，它们具有相同的参数类型（包括值类别）。

在 #1 中，初始参数(1, 2)都是 int prvalue，而递归参数g(a + 1, b)分别是 int prvalue 和 int lvalue。同时，在 #2 中，初始参数(1)和递归参数g(a + 1)都是 int prvalue。您可以检查对 #1 进行更改，使两个递归参数都是 int 纯右值（例如调用g(a + 1, b + 0)）会破坏它，而更改 #2 以传递 int 左值作为递归参数（例如g(++a)）将修复它。

这意味着初始调用的返回类型推导是自引用的，因为它取决于完全相同的调用的类型y_combinator<lambda #2>::operator()<int>(int&&)（而在 #1 中，初始调用y_combinator<lambda #1>::operator()<int, int>(int&&, int&&)取决于y_combinator<lambda #1>::operator()<int, int&>(int&&, int&)）。

如 #3 中那样显式提供返回类型意味着没有自引用类型推导，并且一切都很好。

您可能会问，鉴于递归情况仍然是自引用（请注意所有 3 个编译器都同意），为什么 #1 可以。这是因为一旦我们可以进入 lambda 自己的类型推导，[dcl.spec.auto]/10就会启动，并且第一个return语句为 lambda 提供返回类型，因此当它递归调用 时g，类型推导已经成功。

图表通常有助于：

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
  }

修复（感谢@aschepler）是记住已经调用 lambda 的参数列表，并提供一个“干净”的包装器，其函数调用运算符尚未对每个新参数集进行返回类型推导类型：

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>;