[gcc r16-4564] libstdc++: Avoid incrementing input iterators with std::prev [PR122224]

[Jonathan Wakely]

https://gcc.gnu.org/g:02797a4eeb9453a1c640171d00e52837c5b3de42

commit r16-4564-g02797a4eeb9453a1c640171d00e52837c5b3de42
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Oct 21 17:06:49 2025 +0100

    libstdc++: Avoid incrementing input iterators with std::prev [PR122224]
    
    As explained in PR libstdc++/122224 we do not make it ill-formed to call
    std::prev with a non-Cpp17BidirectionalIterator. Instead we just use a
    runtime assertion to check the std::advance precondition that the
    distance is not negative.
    
    This allows us to support std::prev on types which model the C++20
    std::bidirectional_iterator concept but do not meet the
    Cpp17BidirectionalIterator requirements, e.g. iota_view's iterators.
    
    It also allows us to support std::prev(iter, -1) which is admittedly
    weird, but there's no reason it shouldn't be equivalent to
    std::next(iter), which is perfectly fine to use on non-bidirectional
    iterators. In other words, "reverse decrementing" is valid for
    non-bidirectional iterators.
    
    However, the current implementation of std::advance for
    non-bidirectional iterators uses a loop that does `while (n--) ++i;`
    which assumes that n is not negative and so will eventually reach zero.
    When the assertion for the precondition is not enabled, incrementing the
    iterator while n is non-zero means that using std::prev(iter) or
    std::next(iter, -1) on a non-bidirectional iterator will keep
    incrementing the iterator until n reaches INT_MIN, overflows, and then
    keeps decrementing until it eventually reaches zero. Incrementing most
    iterators that many times will cause memory safety errors long before
    the integer reaches zero and terminates the loop.
    
    This commit changes the loop to use `while (n-- > 0)` which means that
    the loop doesn't execute at all if a negative n is used. We still
    consider such calls to be erroneous, but when the precondition isn't
    checked by an assertion, the function now has no effects. The undefined
    behaviour resulting from incrementing the iterator is prevented.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/122224
            * include/bits/stl_iterator_base_funcs.h (prev): Compare
            distance as n > 0 instead of n != 0.
            * testsuite/24_iterators/range_operations/122224.cc: New test.
    
    Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

Diff:
---
 .../include/bits/stl_iterator_base_funcs.h         |   2 +-
 .../24_iterators/range_operations/122224.cc        | 100 +++++++++++++++++++++
 2 files changed, 101 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
index fb7b6b0aa36c..7c80e1423e45 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
@@ -201,7 +201,7 @@ namespace __detail
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_assert(__n >= 0);
-      while (__n--)
+      while (__n-- > 0)
 	++__i;
     }
 
diff --git a/libstdc++-v3/testsuite/24_iterators/range_operations/122224.cc b/libstdc++-v3/testsuite/24_iterators/range_operations/122224.cc
new file mode 100644
index 000000000000..62bea92481c7
--- /dev/null
+++ b/libstdc++-v3/testsuite/24_iterators/range_operations/122224.cc
@@ -0,0 +1,100 @@
+// { dg-do run { target c++11 } }
+// { dg-add-options no_pch }
+
+// Undefine these if present in runtest flags.
+#undef _GLIBCXX_ASSERTIONS
+#undef _GLIBCXX_DEBUG
+
+// Prevent assertions from being automatically enabled at -O0
+#define _GLIBCXX_NO_ASSERTIONS
+
+#include <iterator>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test_advance()
+{
+  int a[] = { 1, 2, 3 };
+  Container c(a);
+  auto iter = c.begin();
+
+  // This call violates the precondition for std::advance,
+  // but with assertions disabled we do not diagnose it.
+  std::advance(iter, -1);
+
+  // However we do guarantee that erroneously decrementing
+  // an input iterator is a no-op and does no harm.
+  VERIFY( *iter == 1 );
+
+  ++iter;
+  std::advance(iter, -999);
+  VERIFY( *iter == 2 );
+
+  std::advance(iter, 0);
+  VERIFY( *iter == 2 );
+  std::advance(iter, 1);
+  VERIFY( *iter == 3 );
+}
+
+template<typename Container>
+void
+test_prev()
+{
+  int a[] = { 1, 2, 3 };
+  Container c(a);
+  auto iter = c.begin();
+
+  // This calls std::advance(iter, -1), which violates the precondition.
+  iter = std::prev(iter);
+
+  // As above, we turn the std::prev call into a no-op.
+  VERIFY( *iter == 1 );
+
+  ++iter;
+  iter = std::prev(iter, 999);
+  VERIFY( *iter == 2 );
+
+  iter = std::prev(iter, 0);
+  VERIFY( *iter == 2 );
+  iter = std::prev(iter, -1);
+  VERIFY( *iter == 3 );
+}
+
+template<typename Container>
+void
+test_next()
+{
+  int a[] = { 1, 2, 3 };
+  Container c(a);
+  auto iter = c.begin();
+
+  // This calls std::advance(iter, -1), which violates the precondition.
+  iter = std::next(iter, -1);
+
+  // As above, we turn the std::prev call into a no-op.
+  VERIFY( *iter == 1 );
+
+  ++iter;
+  iter = std::next(iter, -999);
+  VERIFY( *iter == 2 );
+
+  iter = std::next(iter, 0);
+  VERIFY( *iter == 2 );
+  iter = std::next(iter);
+  VERIFY( *iter == 3 );
+}
+
+int main()
+{
+  using InputContainer = __gnu_test::input_container<int>;
+  test_advance<InputContainer>();
+  test_prev<InputContainer>();
+  test_next<InputContainer>();
+
+  using ForwardContainer = __gnu_test::forward_container<int>;
+  test_advance<ForwardContainer>();
+  test_prev<ForwardContainer>();
+  test_next<ForwardContainer>();
+}