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

    <tr>
        <th>Summary</th>
        <td>
            [libc++][PSTL] Dispatching to default algorithms is broken in some cases (at least std::any_of)
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

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

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

<pre>
    The default implementation of `std::none_of` in the PSTL is ([here](https://github.com/llvm/llvm-project/blob/68c384676cf92289d823576f915ed296d209354f/libcxx/include/__algorithm/pstl_any_all_none_of.h#L118-L123)):

```
 [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) -> optional<bool> {
        auto __res = std::__any_of(__policy, __g_first, __g_last, __g_pred);
        if (!__res)
          return nullopt;
        return !*__res;
      },
```

Notice how this calls `std::__any_of` with lvalues `__g_first, __g_last, __g_pred`. Now, `__any_of` is implemented like ([here](https://github.com/llvm/llvm-project/blob/68c384676cf92289d823576f915ed296d209354f/libcxx/include/__algorithm/pstl_any_all_none_of.h#L38-L51)):

```
template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate, ...>
optional<bool>
__any_of(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Predicate&& __pred) {
  return std::__pstl_frontend_dispatch(
 _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_any_of, _RawPolicy),
 [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) -> optional<bool> {
        auto __res = std::__find_if(__policy, __g_first, __g_last, __g_pred);
        if (!__res)
          return nullopt;
        return *__res != __g_last;
      },
      std::move(__first),
 std::move(__last),
      std::move(__pred));
}
```

Since `__any_of` is called with lvalues and we're taking universal references, when `none_of` calls `__any_of` we get the following deduction: `_ForwardIterator&& == _Iter& &&` for some ref-unqualified type `_Iter`. As a result, the lambda declaration inside `__any_of` basically has signature `[&](_Iter&, _Iter&, _Predicate)` and that doesn't work since we're trying to pass it a rvalue (`std::move(__first)` & al).

This issue happens whenever the default implementation of `std::any_of` is used. It can be seen by removing:

```
libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
```

Normally, things should work even in that case because `any_of` is not a mandatory algorithm for general backends.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUVs1u4zYQfhr6MoghU5YsHXxw7DUQIM0G3fTSi0CJI4sNTaokZa_fviAlO_I6u5sCe2gDQbH4MzPfzDc_zFqxU4hLktyTZDNhnWu0WUoutFI4KTU_LV8aBI4166QDsW8l7lE55oRWoGsgaWQdJ_GKxCulFRa6JmkEQoFrEJ6_vDyCsEBoRpL7Bg2SZENo1jjXWn-Jbgnd7oRrunJa6T2hWykP5393rdF_YeUI3ZZSl4Ru06yKs3m6SKs6pzTLeUbjZJHW-SxBTvOU0yiPk3ntBYiy-vqV0K1Qlew4ErotCiZ32gjXeA2tdbJg6lQwKYvB9GlDaPw4m2V3jzMaE5r7J16RaEOi8zuNhid8gvccTXtYxVabIzP8waFhThsoil1RC2MdoWt4d1eyYfPZIA8rrUFOaA53JP4EuvWOZpLE61Jr6ZfI4n5QPfyxzmkoCoMWSLyBSziKgE7X3rCi1VJUp6DpyqaxCW_KSfyNDlGHGNJZ0ONPXG0DGHSdUaA6KXXrbu4P24TOCF31Mq6PkMWG0PW7Lu7fT9qJCqHRR3CNsFAxKe0V_S540wiOwjUgD0x2GA79HHQaTeFJH_1aOP8mS9g33iMHKV7xf0boOLt7TGYfobPDfSuZQyDxupLMWig-fcWq8yx8vlBo2PmGz6MdT2ZRMYd-bTqdkvhTL_-Wz_36mKs3ClNCU7ii8I3m4ch3c-1y4irfBhPP8ofEGyXYQNsRxYKTa6OVQ8ULLmzLXNV4OvRXiseH-_Xzc-ErX7H-48vL598e_ly9PHx-Kp4_Pzy99Ml4jpQHvIbid3Y8Y80vWfBLK0tA-qvLSy0UL8R_q76sBkvpzBt7Uf_9YtOvXFDt9QEDoAHCKB63Z3pk-U9lnVGPgHsTvl_svghV4Tt1yBc95NfVjSkORyR0YRAcexVqB50SBzSWSTBYo0FVeZ-u4dig8lJHjfpSRq-qJ8IOXejgtZZSH71QjryrPF1IvAoX3k8xEm-C5_1y-A7LXmqtDVi9R2_UXaf-7pgUtUAO7tT2YMMdX4hXFhgYtJ0MzPGGSLYvOQOOlWSmHz-EsoLfuKlkVnhUJ2iYBT_fMNeZcOwqowYDAzPHv0eFIffyvH9dwxxwjVYRunBw1OYVbIjRxfPm5J3kNLS-AgrnAYQIBWKP2tQtw9LIewmYJDSfjmnw4hudsLZDaFjborIhhHhAE3zysbHsikGdRT6FBwcVU1AiWEQF5QkM7vVBqN2P28PHelDJqldU3BK6rdpu_NmbMm1-2OfN3kevj7tQOwu20Z3kvdfxgKqfLpnHYBFKrFhnQ3yvkCrtY7Bnint2nuBiZiDiDhUaJuFs3HTClzHP45xNcDlL8yzNF2mUTJpljekMMa8zlnMeJTmmGc3TLEc653xO-UQsaUTjWRRHNKLpPJkyLDGdxzMeJSWNy5jMI9wzIad-Bphqs5uEmC4X0WKWTSQrUdowgVPqHUzofXion8jNMgwOZbezZB5JYZ19E-OEk2F2H11LNiS5992HJBvYDP1poOaZLxdXeHZBafRr79SQnd6pYWJnDiQy6-BbJtF80hm5_NczT0DtaRCA_xMAAP__XiLa8w">