boostorg / boostorg/hana

hana::fix doesn't (consistently) work on lambdas with deduced return type

Open
#467 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
1.9k
Forks
225
PR merge metrics
No merged PRs in 30d

Description

[Consider ](https://godbolt.org/z/vzZVqA) a recursive lambda with deduced return type and multiple return statements:

auto twice= fix([](auto f, int i) {
if (i <= 0)
return 0;
return 2 + f(i - 1);
});
auto i = twice(1);

This doesn't work; gcc reports

error: use of 'constexpr decltype(auto) boost::hana::fix_t::operator()(X&& ...) & [with X = {int}; F = ]' before deduction of 'auto'
38 | return 2 + f(i - 1);
| ~^~~~~~~

But if `twice` is const or rvalue, it does work. This is [confusing and inconsistent](https://stackoverflow.com/questions/62161963/return-type-deduction-of-recursive-function).

By [dcl.spec.auto]/10, the return type of the lambda itself (rather, of a particular instantiation of its call operator template) is determined by the first return statement and is available thereafter within that call operator; all three compilers agree that this holds for recursive calls to that same instantiation of the call operator template. The problem is that the return type of `fix_t::operator() &` is also undergoing type deduction at this point, and because it only has a single return statement [dcl.spec.auto]/10 can't help.

The first step in a solution is to look at why the const (and rvalue) cases work. This is because when `fix_t::operator() const&` calls the lambda, its call to `fix(f)` does not apply const qualification to the result, so the lambda receives a `fix_t` as its first argument and its recursive call invokes `fix_t::operator() &`, which is not yet undergoing return type deduction. Then, when the compiler does attempt return type deduction on `fix_t::operator() &` it notes that its call is to `F::operator(), int>` which has already been deduced as returning `int` by [dcl.spec.auto]/10.

Adding a `bool` template parameter would work for the simple case, but more complicated cases are possible where the lambda has other polymorphic arguments. The general solution, due to aschepler on SO, is to record all the argument lists seen so far and, for each new argument list (including the initial call), generate a new fixpoint wrapper (whose `operator()`s are not yet undergoing return type deduction and are therefore safe to call from the lambda). (Note that the initial call must supply a fixpoint wrapper distinct from itself to the lambda.) Conversely, if the argument list has already been seen in a particular call chain, we know the lambda has already been called with the current fixpoint wrapper and argument types, so if it has a stable return type at all this will already have been deduced and so it is safe to reenter with the same current fixpoint wrapper. The elegant if obvious trick is to use the list of argument lists themselves as the uniquifying parameter:

```
template
struct fix_t {
template
struct ref {
Ff ff;
template
constexpr decltype(auto) operator()(Args&&... args) const {
using G = std::conditional_t<(std::is_same_v || ...), ref, ref>;
return static_cast(ff)(G{static_cast(ff)}, std::forward(args)...);
}
};
F f;
template
constexpr decltype(auto) operator()(Args&&... args) const& {
return ref{f}(std::forward(args)...);
}
template
constexpr decltype(auto) operator()(Args&&... args) & {
return ref{f}(std::forward(args)...);
}
template
constexpr decltype(auto) operator()(Args&&... args) && {
return ref{std::move(f)}(std::forward(args)...);
}
};
```

I'm happy to submit a PR but would appreciate direction on naming and on whether the above using function types for argument lists and `` to generate new fixpoint wrappers is an acceptable implementation.

Contributor guide

Open the contributing guide

Research direction

Start at the hana::fix/fix_t implementation and compare its lvalue, const-lvalue, and rvalue operator() paths with the recursive lambda example and the proposed ref wrapper. Verify behavior for deduced return types and polymorphic argument lists across the cases described; done means recursive lambdas behave consistently without relying on const or rvalue calls.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
tooling
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.