<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/91308>91308</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Wrong type inference during recursive generic lambda
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          haruomaki
      </td>
    </tr>
</table>

<pre>
    Although the code below is quite complicated, it would be valid as C++20. g++ 13.2.1 accepts this code. But clang++ 18.0.0 fails, saying "return type of `self(n-2)` is `int`".

```c++
#include <iostream>
#include <map>

template <typename...>
struct LambdaTraits;

template <typename F>
struct LambdaTraits<F> : public LambdaTraits<decltype(&F::operator())> {};

template <typename F, typename... TArgs>
struct LambdaTraits<F, TArgs...> : LambdaTraits<decltype(&F::template operator()<TArgs...>)> {};

template <typename C, typename Ret, typename... Args>
struct LambdaTraits<Ret (C::*)(Args...) const> {
    using args_type = std::tuple<Args...>;
 using return_type = Ret;
};

struct Any {
    template <typename T>
    T operator()(T) const;
};

template <typename F>
struct MemoFix {
    F f;
    using Arg = std::tuple_element_t<1, typename LambdaTraits<F, Any>::args_type>;
    using Ret = LambdaTraits<F, Any>::return_type;
    std::map<Arg, Ret> cache{};

    Ret operator()(Arg x) {
        if (!cache.contains(x)) {
 cache[x] = f(std::ref(*this), x);
        }
        return cache[x];
    }
};

int main() {
    auto fibonacci = MemoFix{[&](auto self, int n) -> std::string {
        if (n <= 0) {
 return "0";
        }
        if (n == 1) {
 return "1";
        }

        std::string str = "(" + self(n - 2) + " + " + self(n - 1) + ")";
        return str;
    }};

 std::cout << fibonacci(5) << std::endl;
}
```

compile command ([godbolt](https://godbolt.org/z/bxc4sqzrs)): `clang++ -std=c++20 -g -Wall -Wextra main.cpp -o main && ./main`

outputs:
```
main.cpp:48:31: warning: adding 'int' to a string does not append to the string [-Wstring-plus-int]
   48 |         std::string str = "(" + self(n - 2) + " + " + self(n - 1) + ")";
      | ~~~~^~~~~~~~~~~~~
main.cpp:11:71: note: in instantiation of function template specialization 'main()::(anonymous class)::operator()<Any>' requested here
   11 | struct LambdaTraits<F, TArgs...> : LambdaTraits<decltype(&F::template operator()<TArgs...>)> {};
      | ^
main.cpp:27:50: note: in instantiation of template class 'LambdaTraits<(lambda at main.cpp:40:30), Any>' requested here
   27 | using Arg = std::tuple_element_t<1, typename LambdaTraits<F, Any>::args_type>;
      | ^
main.cpp:40:22: note: in instantiation of template class 'MemoFix<(lambda at main.cpp:40:30)>' requested here
   40 |     auto fibonacci = MemoFix{[&](auto self, int n) -> std::string {
      | ^
main.cpp:48:31: note: use array indexing to silence this warning
   48 |         std::string str = "(" + self(n - 2) + " + " + self(n - 1) + ")";
      |                               ^
      | &   [            ]
main.cpp:48:45: error: invalid operands to binary expression ('const char *' and 'const char[4]')
   48 | std::string str = "(" + self(n - 2) + " + " + self(n - 1) + ")";
      |                           ~~~~~~~~~~~~~~~~~ ^ ~~~~~
1 warning and 1 error generated.
```

g++ compiles this code correctly. compile command ([godbolt](https://godbolt.org/z/Y1Gd53Pz5)): `g++ -std=c++20 -g -Wall -Wextra main.cpp -o main && ./main`

and outputs:
```
((1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))))
```


# Details
This program displays the calculation process of the Fibonacci sequence.

- `LambdaTraits` is a metafunction that parses the received lambda type and returns the argument type and return value type.
- `MemoFix` is a class that combines a fixed point combinator and memoization using std::map.
- `F` is a lambda type.
- `Arg` should be deduced to `int`.
- `Ret` should be deduced to `std::string`.
- The `auto self` argument in the lambda expression is actually a value of type MemoFix, so `self(n-2)` or `self(n-1)` should return a value of `std::string`.

However, for some reason, clang++ seems to incorrectly infer that the return value of `self(n-2)` is `int`.

Sorry for the complicated code; this bug only occurs when a lot of type inference is involved, so I think this is the minimal case. I hope someone can narrow down the problem more clearly.

Thanks!
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMWF9v47gR_zTMy8CGRPmP8pAH_1m3B7RAcQ2w6NOBlsY2exSpJakk3od89mJISZYcb5ID2usKhiwMyZnf_DiaGVE4J48a8YHN12y-vRONPxn7cBK2MZX4Xd7tTXl-WCl_Ms3xBP6EUJgSYY_KPIN08K2RnmRVrWQhPJaMb0B6eDaNKmGP8CSULEE42DC-ZnzNkykc4yOk2ZRPUxBFgbV34E_SBfVTWDceCiV0PzOfJtMEDkIqRxacOEt9BMa5Rd9YDf5cI5gDsEXiUB0Yz_WEM37PFgnBZItEas8WCeN8ypItS1btfZHEXxEttVKeSV2opkRg2UYa5y2KimVfbg1Xor6MhLvHqlbCh1ECpkWF0-m0n-W8bQoPfxPVvhSPVkjvWLb-SAPs3lewoXFg2QrqZq9kcT1cYqFIF-M544sdy1YsW5karfDGBuE9_UjHcs2W289B4hsYuAiPK3t0H-LkmzgxkhIwfwZsD-EKdbYZaPvDPmyGPsCv6K99-oRLv6IHxvNNxMn4KpCZd6j4PRRGO98BC5oAABpHYSzs0f0WIphlW3C-bN1taoUs2wx869xpF8bgvywl8L3Hb7xvoa_0eQziJiuPvcc05fGacp4_Drz6ocnPxfHfsTI7-TJGtYPDxd2eqpU93iDpN1RYofa_eZZt0tF-3oq9lT4HMml9z_2I3t5e2Nhs-6GawU6MtPQ4Q5agraSVYZ--QCGKE94MVFpKpt-wTv6_EPMjruiSBwiz0qB1WhjthdSO8fwlvtmDJdHwfP3C5tvgHiXMHqrFQ9C0ooQc1m6CzZFjdBHukaBNxkP1o0X9grceS-2hElJHT8fuicYbOMi90aIoZADchgxNm68ZX5AlnoeJMf9vgDRq0jUhrnvvnLehdNzmT1OkkoFkjKL1jHFOJeRjJi7atqQt_ZG29F1tY_G1C87bwAWpINY4UKnsyh9MgAerfA3d2I056WBO2Ou3cFq0zts3m_k2cHuQhWl8JHNz2TvG83kwGOX9ZNSlGqWRcXEeWqBeQ6rQc1RClyHo5-ujKfdG-RgGJ-9rF_LwjvFdOzQ19O7tvjO-278UM_ftu3VdyVtRgzDsNyYB2bboehaYHGHyVSgFk6_44q0IsTot6homJjwDBSFfwJTxXYjjMWrT-LrxAdQt1zptLFvNcpatspRAPQurpT7SoyjL2PAsqY_hS_AGBLSBUBp0oI0HUdeoSxqjTq2L9Pl68jU-T2rVuAlpmF_idZYDW27g_xtlhOD19fWVzb-8Dq437KREzDKwo41H-pcapHZeaC-Fl0ZTG3hodBGe-wLkaiykUPJ7nMP48pJtuqqdC230uTKNo-bTuX7oTb_Rpn6-BIvfGnQeSzihxd6lNA0u_TwN0IVmNv_yhla-ZNlqnnxEa28_0EMkXqFmPFdBAsLDMKhJdZa0xeRD9vgyIP2zS_6P-Qn4KWj_KD9dnfoUNe9yMkv61_RPqIc_JOKSnToiGocgrBVnkLrEF1JGVqVCXWD8qOsS2U-Xct6_egIGnPBFGFiP521vEzWbE0ForbExZOLXcHh7demIp73Uwp4BX2qLzsXUlDO-DJ01FCdhIXxOLCEWu8EAm69nYZ-X5N8Vtz8jp6_XFzEMg0SfdpESnE0jc3BETdkOy-k7bUFXudv2YHCaAIWxFguvzlP4LzQP_0r_Us6zf3yfj5qH_1njQCg_aB7CfuZpuzF5Eh7SrumPwpG8E95e0v5-THV_CAJb9OFEJggeifDamqMVFZTS1UqcXTwyEqpoVMyStTUFOhey5Qlh12cxR2lPFzg6npkQt6N8Hs9zBFToxaXKn4SHWliH0aDFAuUTltBm3PCBTEzGVjZOEvbYUAW5HoUnoRoM0ukARZdhOwAxxQfLhan2UiNJD_IFS6gNJdsopjIdtFdYma79iJVt-HE4NLXrjQzwDyfQZ-QiAXfqTtlKLJsCQ-fXH3UNF9AH5zsLrpLFcPHjCWnGpZIskgtzUgcmW5SDHEbgC98Ipc4gWkJpx4npjki-AWduHtgZOxKnrbhF3-7SQO17HsT7X80zPqElmwdjwZmKgkQ4o0k07PwdYhUSs9R93gCpD2jjXsfwGsTJJw4dR1D-aaw9BxTxNLU_OQ3JimXrmLn2zRGMVmcwRdFYB88nJJ-V8T2RAVUostJRbTHqKZ6_OgO_kBb9e9QlY8BXUstKKCiEwyn8AidTY6DCaHpHNWhhrXmG0jzHfa2t2SusoDKWWhoUVp1HvjyehP7dMZ7elQ9ZeZ_dizt8SJfpPFmms2V-d3pAvljOZvus2CPy8v6wzA_5fi4W-xnmaTkr7uQDT_gsmSfLJJ_NsnyazJJC5Pf7WTKfYXHI2SzBSkg1Veqpojx8J51r8OE-zZL8Tok9KheOrznX-AxhkArTfHtnH2jNZN8cHZslSjrvLlq89AofvlpD_cqYzrKx8XSNmJdPGCuQLNpAv2usergqE9Kfmv20MBXjOzLR_k1qa_6NhWd8F4A5xncB-H8CAAD__132wnY">