<algorithm>: ranges::find_if_not's help lambda should return bool

[hewillk]

llvm-project/libcxx/include/__algorithm/ranges_find_if_not.h

Lines 46 to 51 in 8dd3bc1

	template <input_range _Rp, class _Proj = identity, indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
	_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Rp>
	operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
	auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward<decltype(__e)>(__e)); };
	return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred2, __proj);
	}

The lambda here should specify the return type as bool, such as [&](auto&& __e) -> bool because the type that satisfies boolean-testable does not necessarily have to be bool:

#include <algorithm>

const struct Boolean {
  Boolean() = default;
  Boolean(Boolean&&) = delete;
  operator bool() const;
  const Boolean& operator!() const;
} boolean;

#ifdef __clang__
static_assert(std::__boolean_testable<Boolean>);
#endif

int main() {
  // libc++ rejects
  auto it = std::ranges::find_if_not(" ", [&](char) -> auto& { return boolean; });
}

https://godbolt.org/z/4M15cvarx

[philnik777]

Did you encounter this in real code?

[hewillk]

Did you encounter this in real code?

No, just like I have never encountered an iterator that overloads the comma operator in real life.
This example is highly artificial.

Note that chunk_by_view::iterator::operator-- has the same issue, not sure if this is worth opening a new issue as the two are highly similar.

[ldionne]

I suspect @philnik777 was asking out of curiosity. I agree this is kinda pedantic but it's worth fixing.

[hewillk]

I suspect @philnik777 was asking out of curiosity. I agree this is kinda pedantic but it's worth fixing.

I believe there are still helper lambdas like this in libc++, such as ranges::max (demo).
Should we open a specific issue to address these issues or do we need to open a new one each time?

[ldionne]

I think we could/should tackle all of them via this issue and #69378.

Can you think of a good way to find all of them? I guess we need to look at all the ranges algorithms that take a predicate, since they all expect the predicate to return a boolean-testable?

[hewillk]

I think we could/should tackle all of them via this issue and #69378.

Can you think of a good way to find all of them? I guess we need to look at all the ranges algorithms that take a predicate, since they all expect the predicate to return a boolean-testable?

Sadly that seems to be the case.
I think this situation mostly occurs when creating a helper lambda in the form of [&](auto&& lhs, auto&& rhs) { return some-boolean-expression; }.
In addition to <algorithm>, we may also need to check whether there is such a lambda in <ranges> as range adaptors can also accept predicate and sentinel_for and random_access_iterator both imply boolean-testable.

[ldionne]

Sadly that seems to be the case. I think this situation mostly occurs when creating a helper lambda in the form of [&](auto&& lhs, auto&& rhs) { return some-boolean-expression; }.

I was looking at what we do in __make_projected and I think it is conforming. Mandated RVO kicks in and it's really as-if we used

std::invoke(__comp,
            std::invoke(__proj1, std::forward<decltype(__lhs)>(__lhs)),
            std::invoke(__proj2, std::forward<decltype(__rhs)>(__rhs)))

directly in the calling algorithm. Are you able to find a case where e.g. ranges::set_difference fails with a conforming boolean-testable?

[ldionne]

Edit: Sorry I am on a plane and connection is flaky, I thought I had lost my previous comment. Anyway, I did a full survey of everything in <ranges> and <algorithm> and I think we're in the clear, except the following headers which contain patterns like the above (we need to determine whether that's conforming):

libcxx/include/__algorithm/ranges_max_element.h
libcxx/include/__algorithm/ranges_max.h
libcxx/include/__algorithm/ranges_remove_copy.h
libcxx/include/__algorithm/ranges_remove.h
libcxx/include/__algorithm/ranges_replace_copy.h
libcxx/include/__algorithm/ranges_replace.h

[hewillk]

Are you able to find a case where e.g. ranges::set_difference fails with a conforming boolean-testable?

Yes, I can find it. testcase: https://godbolt.org/z/sPzo6o565

Anyway, I did a full survey of everything in and and I think we're in the clear, except the following headers which contain patterns like the above (we need to determine whether that's conforming):

At least I think chunk_by_view::iterator::operator-- should too. (Not sure about other places in <ranges> I haven't looked into yet).
testcase: https://godbolt.org/z/9bezbdaTv

[hewillk]

we may also need to check whether there is such a lambda in as range adaptors can also accept predicate and sentinel_for and random_access_iterator both imply boolean-testable.

The following test is the sentinel_for part I am referring to, using ranges::uninitialized_copy as an example: https://godbolt.org/z/ndxGd48hT

[ldionne]

@hewillk I just updated #69378. I think that version of the patch should handle everything. Would you like to take a look?

[hewillk]

@hewillk I just updated #69378. I think that version of the patch should handle everything. Would you like to take a look?

LGTM. Thanks.