[PATCH] libstdc++: Don't dereference past-the-end iterator with overloaded operator&& [PR125981]
Ян Чуркин
yanchurkin@gmail.com
Thu Jun 25 18:16:41 GMT 2026
> 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.
> 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 <jwakely@redhat.com>:
> 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
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260625/f473c0ea/attachment-0001.htm>
More information about the Libstdc++
mailing list