[gcc r15-1880] libstdc++: Fix std::find for non-contiguous iterators [PR115799]

[Jonathan Wakely]

https://gcc.gnu.org/g:ce34fcc572a0dceebcffef76e98064546feebb38

commit r15-1880-gce34fcc572a0dceebcffef76e98064546feebb38
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Sat Jul 6 21:34:29 2024 +0100

    libstdc++: Fix std::find for non-contiguous iterators [PR115799]
    
    The r15-1857 change didn't correctly restrict the new optimization to
    contiguous iterators.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/115799
            * include/bits/stl_algo.h (find): Use 'if constexpr' so that
            memchr optimization is a discarded statement for non-contiguous
            iterators.
            * testsuite/25_algorithms/find/bytes.cc: Check with input
            iterators.

Diff:
---
 libstdc++-v3/include/bits/stl_algo.h               | 44 ++++++++++------------
 libstdc++-v3/testsuite/25_algorithms/find/bytes.cc |  7 ++++
 2 files changed, 27 insertions(+), 24 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 45c3b591326..d250b2e04d4 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3849,32 +3849,28 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 #if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
       using _ValT = typename iterator_traits<_InputIterator>::value_type;
       if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
-	{
-	  // If converting the value to the 1-byte value_type alters its value,
-	  // then it would not be found by std::find using equality comparison.
-	  // We need to check this here, because otherwise something like
-	  // memchr("a", 'a'+256, 1) would give a false positive match.
-	  if (!(static_cast<_ValT>(__val) == __val))
-	    return __last;
-	  else if (!__is_constant_evaluated())
-	    {
-	      const void* __p0 = nullptr;
-	      if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>)
-		__p0 = std::__niter_base(__first);
+	if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
 #if __cpp_lib_concepts
-	      else if constexpr (contiguous_iterator<_InputIterator>)
-		__p0 = std::to_address(__first);
+			|| contiguous_iterator<_InputIterator>
 #endif
-	      if (__p0)
-		{
-		  const int __ival = static_cast<int>(__val);
-		  if (auto __n = std::distance(__first, __last); __n > 0)
-		    if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
-		      return __first + ((const char*)__p1 - (const char*)__p0);
-		  return __last;
-		}
-	    }
-	}
+		     )
+	  {
+	    // If conversion to the 1-byte value_type alters the value,
+	    // it would not be found by std::find using equality comparison.
+	    // We need to check this here, because otherwise something like
+	    // memchr("a", 'a'+256, 1) would give a false positive match.
+	    if (!(static_cast<_ValT>(__val) == __val))
+	      return __last;
+	    else if (!__is_constant_evaluated())
+	      {
+		const void* __p0 = std::__to_address(__first);
+		const int __ival = static_cast<int>(__val);
+		if (auto __n = std::distance(__first, __last); __n > 0)
+		  if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
+		    return __first + ((const char*)__p1 - (const char*)__p0);
+		return __last;
+	      }
+	  }
 #endif
 
       return std::__find_if(__first, __last,
diff --git a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
index f4ac5d4018d..e1d6c01ab21 100644
--- a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
@@ -3,6 +3,7 @@
 #include <algorithm>
 #include <cstddef> // std::byte
 #include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
 
 // PR libstdc++/88545 made std::find use memchr as an optimization.
 // This test verifies that it didn't change any semantics.
@@ -113,6 +114,12 @@ test_non_characters()
 #endif
 }
 
+void
+test_pr115799c2(__gnu_test::input_iterator_wrapper<char> i)
+{
+  (void) std::find(i, i, 'a');
+}
+
 int main()
 {
   test_char<char>();