[Bug libstdc++/113202] New: std::find does not work with the maximum range of pointers

[Bug libstdc++/113202] New: std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

            Bug ID: 113202
           Summary: std::find does not work with the maximum range of
                    pointers
           Product: gcc
           Version: 13.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: carsten.schmidt-achim at gmx dot de
  Target Milestone: ---

When using std::find() to operate on a range of pointers that is delimited by
the maximum pointer value possible, AKA std::numeric_limits<void*>::max(),
std::find() returns unreasonable results; cf. the attached example.

When implementing the same functionality using std::ranges::find(), the
returned results are reasonable.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #1 from Carsten Schmidt <carsten.schmidt-achim at gmx dot de> ---
Created attachment 56977
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56977&action=edit
A demonstration of the description.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #2 from Carsten Schmidt <carsten.schmidt-achim at gmx dot de> ---
Created attachment 56978
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56978&action=edit
Output of the compilation.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #3 from Carsten Schmidt <carsten.schmidt-achim at gmx dot de> ---
Created attachment 56979
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56979&action=edit
Output when executing the program.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #4 from Carsten Schmidt <carsten.schmidt-achim at gmx dot de> ---
NOTE: My .ii file exceeds the size limit, so I attached the originating code
instead.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Why do you think this is a bug?
I suspect this is due to `ptr-ptr` returns a signed value and max is (void*)-1
so it that returns a negative value and things just don't work.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[carsten.schmidt-achim at gmx dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #6 from Carsten Schmidt <carsten.schmidt-achim at gmx dot de> ---
> Why do you think this is a bug?

1. Considering the "possible implementation" of cppreference.com, pointer
   arithmetic, e.g. ptr-ptr, should not be an issue when searching for the
   sentinel.

2. Using ranges::find() does not show the observed behavior.

3. Other implementations of the libstdc++, e.g. MSVC, work properly.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |INVALID
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note doing std::find(a, max) where max is outside of the array (or one element
more than the array) is undefined code.

Which means libstdc++ is working correctly. 

I suspect you should just use strlen if you want to find the null character in
an unbounded array.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The assumption is first and last are part of the same iterator which means in
the case of pointers, it needs to be addresses inside the array or one element
past the array. Everything else is undefined.

It just happens to work for msvc's library does not mean it is defined code.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #9 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
(In reply to Carsten Schmidt from comment #6)
> > Why do you think this is a bug?
> 
> 1. Considering the "possible implementation" of cppreference.com, pointer
>    arithmetic, e.g. ptr-ptr, should not be an issue when searching for the
>    sentinel.

Quoting from https://en.cppreference.com/w/cpp/iterator:

<quote>
An iterator j is called reachable from an iterator i if and only if there is a
finite sequence of applications of the expression ++i that makes i == j. If j
is reachable from i, they refer to elements of the same sequence.

A range is a pair of iterators that designate the beginning and end of the
computation. A range [i, i) is an empty range; in general, a range [i, j)
refers to the elements in the data structure starting with the element pointed
to by i and up to but not including the element pointed to by j.

Range [i, j) is valid if and only if j is reachable from i.
</quote>

Here there is no finite sequences of applications of the expression ++i that
makes i == j because running ++i will invoke undefined behavior far before i ==
j.  Thus this range is invalid.

And:

<quote>
The result of the application of functions in the standard library to invalid
ranges is undefined.
</quote>

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

Xi Ruoyao <xry111 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xry111 at gcc dot gnu.org

--- Comment #10 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
And "possible implementation" is just one of the infinite allowed
implementations.  libstdc++ can use a different implementation for
speed/simplicity/whatever as long as it does not violate the standard.

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
s + OFFSET has undefined behaviour.

With -O2 or -O3 GCC even tells you where the problem is:

find_bug.cpp: In function 'int main(int, char**)':
find_bug.cpp:39:61: warning: array subscript 1048576 is outside array bounds of
'const char [6]' [-Warray-bounds=]
   39 |   std::cout << "strlen = " << strlen_no_ranges(s, s + OFFSET) << ", no
ranges, OFFSET = " << OFFSET << std::endl;
      |                                                             ^
find_bug.cpp:40:58: warning: array subscript 1048576 is outside array bounds of
'const char [6]' [-Warray-bounds=]
   40 |   std::cout << "strlen = " << strlen_ranges(s, s + OFFSET)    << ",
ranges,    OFFSET = " << OFFSET << std::endl;
      |

[Bug libstdc++/113202] std::find does not work with the maximum range of pointers

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113202

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #11)
> s + OFFSET has undefined behaviour.

... and iterating from s to <invalid pointer value> has undefined behaviour
too, as explained above. Nothing the program does is valid.