On Thu, 25 Jun 2026 at 19:16, Ян Чуркин <[email protected]> wrote: > > > Your predicate fails to meet the boolean-testable requirements, so the > > case you are describing has undefined behaviour. This is not a bug. > > > We could decide to do this anyway, but we aren't required to. > > > See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2167r3.html > > for how the standard was changed to clarify that algorithms do not > > have to cope with malicious predicates. > > Fair enough, I won't argue the conformance point. > Would you take it as a "quality of implementation" change instead? > std::equal, std::binary_search and std::__partition already force the > predicate result to bool. This patch just does the same for __find_if, > __mismatch and __push_heap. It is a one-token change per loop without > behaviour change for normal predicates and it avoids a past-the-end > dereference. > > If you would rather not and I will drop it and will close the issue. > > Thank you so much for your review! > > > Was this patch produced with the assistance of an LLM? > > Yes, a bit - only for translating and clarifying text from my native language > in complex contexts that is difficult for me to translate myself to say > clearly what I want, because the common machine translators make my english > incomprehensible and also for recommendation how to make a patch in terms of > gcc policies. > > > We don't need the comment, especially not repeated every time you cast to > > bool. > > > Anybody working on this code should be able to understand the purpose. > > I can remove unnecessary comments and resend the patch If needed.
Yes please, remove all the code comments. Remove the license headers in the new tests and add comments in the tests saying what they test is undefined behaviour and we allow it as QoI. > > > We do not need or want copyright and license headers on new tests. > > LLMs have not learned this yet: > > https://gcc.gnu.org/onlinedocs/libstdc++/manual/test.html#test.new_tests > > This one I will remove too. > > Thank you, > Yan Churkin > > чт, 25 июн. 2026 г. в 12:58, Jonathan Wakely <[email protected]>: >> >> On Thu, 25 Jun 2026 at 10:29, Yan Churkin <[email protected]> wrote: >> > >> > Several internal algorithms drove their main loop with a condition of the >> > form >> > >> > while (__first != __last && PREDICATE_CALL(...)) >> > >> > where the predicate/comparator is the user-supplied functor, passed >> > through unwrapped. When that functor returns a class type and the >> > program declares a namespace-scope operator&&(bool, T) (or operator!) >> > reachable by ADL, overload resolution selects the user operator&& for >> > the loop condition. >> >> Your predicate fails to meet the boolean-testable requirements, so the >> case you are describing has undefined behaviour. This is not a bug. >> >> We could decide to do this anyway, but we aren't required to. >> >> See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2167r3.html >> for how the standard was changed to clarify that algorithms do not >> have to cope with malicious predicates. >> >> > An overloaded operator&& does not short-circuit, so >> > the right-hand operand -- which dereferences *__first -- is evaluated >> > even when __first == __last. For an empty range (or once the scan >> > reaches the end) this dereferences the past-the-end iterator; >> > AddressSanitizer reports it as a stack-buffer-overflow read for e.g. an >> > empty std::list, and UBSan as a null/ invalid reference binding. >> > >> > Force the predicate result to bool in these loop conditions (the same >> > idiom already used elsewhere, e.g. in lower_bound and search_n), so the >> > '&&' is the built-in, short-circuiting operator and the iterator is >> > never dereferenced once __first == __last. The ranges:: versions are >> > unaffected because their comparator/predicate wrappers already return >> > bool. >> >> Was this patch produced with the assistance of an LLM? >> >> >> > >> > PR libstdc++/125981 >> > >> > libstdc++-v3/ChangeLog: >> > >> > * include/bits/stl_algobase.h (__find_if): Convert the predicate >> > result to bool so an ADL-found, non-short-circuiting operator&& / >> > operator! cannot dereference the past-the-end iterator. >> > (__mismatch): Likewise for both overloads. >> > * include/bits/stl_heap.h (__push_heap): Likewise for the >> > comparator result. >> > * testsuite/25_algorithms/find_if/overloaded_logical_ops.cc: New >> > test. >> > * testsuite/25_algorithms/mismatch/overloaded_logical_ops.cc: New >> > test. >> > >> > Signed-off-by: Yan Churkin <[email protected]> >> > --- >> > libstdc++-v3/include/bits/stl_algobase.h | 14 +++- >> > libstdc++-v3/include/bits/stl_heap.h | 5 +- >> > .../find_if/overloaded_logical_ops.cc | 76 ++++++++++++++++++ >> > .../mismatch/overloaded_logical_ops.cc | 80 +++++++++++++++++++ >> > 4 files changed, 171 insertions(+), 4 deletions(-) >> > create mode 100644 >> > libstdc++-v3/testsuite/25_algorithms/find_if/overloaded_logical_ops.cc >> > create mode 100644 >> > libstdc++-v3/testsuite/25_algorithms/mismatch/overloaded_logical_ops.cc >> > >> > diff --git a/libstdc++-v3/include/bits/stl_algobase.h >> > b/libstdc++-v3/include/bits/stl_algobase.h >> > index 1350736a8..a4090cb70 100644 >> > --- a/libstdc++-v3/include/bits/stl_algobase.h >> > +++ b/libstdc++-v3/include/bits/stl_algobase.h >> > @@ -1930,7 +1930,10 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO >> > __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, >> > _InputIterator2 __first2, _BinaryPredicate __binary_pred) >> > { >> > - while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) >> > + // The bool conversion prevents an ADL-reachable operator&& from >> > making >> > + // '&&' non-short-circuiting and dereferencing past-the-end >> > iterators >> > + // (see std::__find_if). >> >> We don't need the comment, especially not repeated every time you cast to >> bool. >> >> Anybody working on this code should be able to understand the purpose. >> >> > + while (__first1 != __last1 && bool(__binary_pred(*__first1, >> > *__first2))) >> > { >> > ++__first1; >> > ++__first2; >> > @@ -2010,8 +2013,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO >> > _InputIterator2 __first2, _InputIterator2 __last2, >> > _BinaryPredicate __binary_pred) >> > { >> > + // See the __mismatch overload above for the bool conversion. >> > while (__first1 != __last1 && __first2 != __last2 >> > - && __binary_pred(*__first1, *__first2)) >> > + && bool(__binary_pred(*__first1, *__first2))) >> > { >> > ++__first1; >> > ++__first2; >> > @@ -2097,7 +2101,11 @@ _GLIBCXX_END_NAMESPACE_ALGO >> > __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) >> > { >> > #pragma GCC unroll 4 >> > - while (__first != __last && !__pred(*__first)) >> > + // Convert the predicate result to bool: if its type has an >> > + // ADL-reachable operator&& or operator!, those overloads are not >> > + // short-circuiting and would evaluate (and so dereference) the >> > + // past-the-end iterator even when __first == __last. >> > + while (__first != __last && !bool(__pred(*__first))) >> > ++__first; >> > return __first; >> > } >> > diff --git a/libstdc++-v3/include/bits/stl_heap.h >> > b/libstdc++-v3/include/bits/stl_heap.h >> > index 8c5c5df52..bb6a3d159 100644 >> > --- a/libstdc++-v3/include/bits/stl_heap.h >> > +++ b/libstdc++-v3/include/bits/stl_heap.h >> > @@ -143,7 +143,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> > _Compare& __comp) >> > { >> > _Distance __parent = (__holeIndex - 1) / 2; >> > - while (__holeIndex > __topIndex && __comp(*(__first + __parent), >> > __value)) >> > + // The bool conversion prevents an ADL-reachable operator&& from >> > making >> > + // '&&' non-short-circuiting (see std::__find_if). >> > + while (__holeIndex > __topIndex >> > + && bool(__comp(*(__first + __parent), __value))) >> > { >> > *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); >> > __holeIndex = __parent; >> > diff --git >> > a/libstdc++-v3/testsuite/25_algorithms/find_if/overloaded_logical_ops.cc >> > b/libstdc++-v3/testsuite/25_algorithms/find_if/overloaded_logical_ops.cc >> > new file mode 100644 >> > index 000000000..bb7c197f1 >> > --- /dev/null >> > +++ >> > b/libstdc++-v3/testsuite/25_algorithms/find_if/overloaded_logical_ops.cc >> > @@ -0,0 +1,76 @@ >> > +// Copyright (C) 2026 Free Software Foundation, Inc. >> >> We do not need or want copyright and license headers on new tests. >> LLMs have not learned this yet: >> https://gcc.gnu.org/onlinedocs/libstdc++/manual/test.html#test.new_tests >> >> > +// >> > +// This file is part of the GNU ISO C++ Library. This library is free >> > +// software; you can redistribute it and/or modify it under the >> > +// terms of the GNU General Public License as published by the >> > +// Free Software Foundation; either version 3, or (at your option) >> > +// any later version. >> > + >> > +// This library is distributed in the hope that it will be useful, >> > +// but WITHOUT ANY WARRANTY; without even the implied warranty of >> > +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the >> > +// GNU General Public License for more details. >> > + >> > +// You should have received a copy of the GNU General Public License along >> > +// with this library; see the file COPYING3. If not see >> > +// <http://www.gnu.org/licenses/>. >> > + >> > +// 25.5.5 [alg.find] find_if >> > + >> > +// The internal std::__find_if must not dereference the past-the-end >> > +// iterator. It used to combine the loop guard with the predicate as >> > +// 'first != last && !pred(*first)'. When the predicate returns a class >> > +// type with a user-provided operator! and there is a namespace-scope >> > +// operator&&(bool, T) findable by ADL, that operator&& is selected and is >> > +// *not* short-circuiting, so '!pred(*first)' (and hence '*first') was >> > +// evaluated even when first == last. >> > + >> > +#include <algorithm> >> > +#include <testsuite_hooks.h> >> > +#include <testsuite_iterators.h> >> > + >> > +using __gnu_test::test_container; >> > +using __gnu_test::forward_iterator_wrapper; >> > + >> > +int truth = 0; >> > + >> > +struct Logic >> > +{ >> > + Logic operator!() const { return Logic(); } >> > + operator bool() const { return truth != 0; } >> > +}; >> > + >> > +struct Value >> > +{ >> > + Logic operator>(Value) const { return Logic(); } >> > +}; >> > + >> > +// Non-short-circuiting operator&& findable by ADL on Logic. >> > +bool operator&&(bool, Logic) { return false; } >> > + >> > +struct Pred >> > +{ >> > + Logic operator()(Value v) const { return v > v; } >> > +}; >> > + >> > +void >> > +test01() >> > +{ >> > + Value arr[1] = { }; >> > + >> > + // Empty range: the predicate must never be applied and *first (the >> > + // past-the-end iterator) must never be dereferenced. >> > + test_container<Value, forward_iterator_wrapper> empty(arr, arr); >> > + VERIFY( std::find_if(empty.begin(), empty.end(), Pred()).ptr == arr ); >> > + >> > + // No match: scanning reaches last; *last must not be dereferenced. >> > + test_container<Value, forward_iterator_wrapper> con(arr, arr + 1); >> > + VERIFY( std::find_if(con.begin(), con.end(), Pred()).ptr == arr + 1 ); >> > +} >> > + >> > +int >> > +main() >> > +{ >> > + test01(); >> > + return 0; >> > +} >> > diff --git >> > a/libstdc++-v3/testsuite/25_algorithms/mismatch/overloaded_logical_ops.cc >> > b/libstdc++-v3/testsuite/25_algorithms/mismatch/overloaded_logical_ops.cc >> > new file mode 100644 >> > index 000000000..55de86c79 >> > --- /dev/null >> > +++ >> > b/libstdc++-v3/testsuite/25_algorithms/mismatch/overloaded_logical_ops.cc >> > @@ -0,0 +1,80 @@ >> > +// Copyright (C) 2026 Free Software Foundation, Inc. >> > +// >> > +// This file is part of the GNU ISO C++ Library. This library is free >> > +// software; you can redistribute it and/or modify it under the >> > +// terms of the GNU General Public License as published by the >> > +// Free Software Foundation; either version 3, or (at your option) >> > +// any later version. >> > + >> > +// This library is distributed in the hope that it will be useful, >> > +// but WITHOUT ANY WARRANTY; without even the implied warranty of >> > +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the >> > +// GNU General Public License for more details. >> > + >> > +// You should have received a copy of the GNU General Public License along >> > +// with this library; see the file COPYING3. If not see >> > +// <http://www.gnu.org/licenses/>. >> > + >> > +// 25.5.9 [mismatch] >> > + >> > +// std::__mismatch must not dereference the past-the-end iterator. It >> > used >> > +// to combine the loop guard with the predicate as >> > +// 'first1 != last1 && pred(*first1, *first2)'. When the predicate >> > returns >> > +// a class type and a namespace-scope operator&&(bool, T) is findable by >> > +// ADL, that operator&& is selected and is *not* short-circuiting, so >> > +// 'pred(*first1, *first2)' (and hence the dereferences) was evaluated >> > even >> > +// when first1 == last1. >> > + >> > +#include <algorithm> >> > +#include <testsuite_hooks.h> >> > +#include <testsuite_iterators.h> >> > + >> > +using __gnu_test::test_container; >> > +using __gnu_test::forward_iterator_wrapper; >> > + >> > +int truth = 0; >> > + >> > +struct Logic >> > +{ >> > + Logic operator!() const { return Logic(); } >> > + operator bool() const { return truth != 0; } >> > +}; >> > + >> > +struct Value { }; >> > + >> > +// Non-short-circuiting operator&& findable by ADL on Logic. >> > +bool operator&&(bool, Logic) { return false; } >> > + >> > +struct Eq >> > +{ >> > + Logic operator()(Value, Value) const { return Logic(); } >> > +}; >> > + >> > +void >> > +test01() >> > +{ >> > + Value arr[1] = { }; >> > + >> > + // Empty first range: the predicate must never be applied and the >> > + // past-the-end iterators must never be dereferenced. >> > + test_container<Value, forward_iterator_wrapper> empty(arr, arr); >> > + test_container<Value, forward_iterator_wrapper> other(arr, arr + 1); >> > + auto r = std::mismatch(empty.begin(), empty.end(), other.begin(), Eq()); >> > + VERIFY( r.first.ptr == arr ); >> > + >> > +#if __cplusplus >= 201402L >> > + // Four-argument form: stop when either range is exhausted, without >> > + // dereferencing the past-the-end iterator of the shorter range. >> > + test_container<Value, forward_iterator_wrapper> e2(arr, arr); >> > + test_container<Value, forward_iterator_wrapper> o2(arr, arr + 1); >> > + auto r2 = std::mismatch(e2.begin(), e2.end(), o2.begin(), o2.end(), >> > Eq()); >> > + VERIFY( r2.first.ptr == arr ); >> > +#endif >> > +} >> > + >> > +int >> > +main() >> > +{ >> > + test01(); >> > + return 0; >> > +} >> > -- >> > 2.43.0 >> > >>
