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 >
