[PATCH] libstdc++: Don't dereference past-the-end iterator with overloaded operator&& [PR125981]
Jonathan Wakely
jwakely@redhat.com
Thu Jun 25 09:57:50 GMT 2026
On Thu, 25 Jun 2026 at 10:29, Yan Churkin <yanchurkin@gmail.com> 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 <yanchurkin@gmail.com>
> ---
> 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
>
More information about the Libstdc++
mailing list