[Bug libstdc++/65861] New: libstdc++ is silently generating wrong code when its std::search is given an input iterator

[Bug libstdc++/65861] New: libstdc++ is silently generating wrong code when its std::search is given an input iterator

[howarth.at.gcc at gmail dot com]

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

            Bug ID: 65861
           Summary: libstdc++ is silently generating wrong code when its
                    std::search is given an input iterator
           Product: gcc
           Version: 5.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: howarth.at.gcc at gmail dot com

While porting rstudio 0.98.1103 to build under clang/libc++, I uncovered a
defect in the libstdc++ handling of input iterators by std::search
(https://llvm.org/bugs/show_bug.cgi?id=23307). The reduced test case is
silently generating wrong code when its std::search is given an input iterator
(it assumes it can save the iterator position and backtrack).

#include <string>
#include <iterator>
#include <algorithm>
void f(std::istream &s, std::string x) {
      std::istreambuf_iterator<char> eod;
      std::search(std::istreambuf_iterator<char>(s),
                  eod,
                  x.begin(),
                  x.end());
}

Clang with libc++ properly rejects this with the error...

In file included from test3.cpp:1:
In file included from
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/string:439:
In file included from
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:628:
In file included from
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:604:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:849:22:
error: 
      implicit instantiation of undefined template
'std::__1::basic_istream<char, std::__1::char_traits<char> >'
        : __sbuf_(__s.rdbuf()) {}
                     ^
test3.cpp:6:19: note: in instantiation of member function
'std::__1::istreambuf_iterator<char,
      std::__1::char_traits<char> >::istreambuf_iterator' requested here
      std::search(std::istreambuf_iterator<char>(s),
                  ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iosfwd:109:33:
note: 
      template is declared here
    class _LIBCPP_TYPE_VIS_ONLY basic_istream;
                                ^
In file included from test3.cpp:1:
In file included from
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/string:439:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:1572:12:
error: 
      no matching function for call to '__search'
    return _VSTD::__search<typename
add_lvalue_reference<_BinaryPredicate>::type>
          
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__config:358:15:
note: 
      expanded from macro '_VSTD'
#define _VSTD std::_LIBCPP_NAMESPACE
              ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:1586:19:
note: 
      in instantiation of function template specialization
'std::__1::search<std::__1::istreambuf_iterator<char,
      std::__1::char_traits<char> >, std::__1::__wrap_iter<char *>,
std::__1::__equal_to<char, char> >' requested here
    return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1,
__v2>());
                  ^
test3.cpp:6:12: note: in instantiation of function template specialization
      'std::__1::search<std::__1::istreambuf_iterator<char,
std::__1::char_traits<char> >, std::__1::__wrap_iter<char *>
      >' requested here
      std::search(std::istreambuf_iterator<char>(s),
           ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:1456:1:
note: 
      candidate function [with _BinaryPredicate = std::__1::__equal_to<char,
char> &, _RandomAccessIterator1 =
      std::__1::istreambuf_iterator<char, std::__1::char_traits<char> >,
_RandomAccessIterator2 =
      std::__1::__wrap_iter<char *>] not viable: no known conversion from
'typename
      std::iterator_traits<istreambuf_iterator<char, char_traits<char> >
>::iterator_category'
      (aka 'std::__1::input_iterator_tag') to
'std::__1::random_access_iterator_tag' for 6th argument
__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:1419:1:
note: 
      candidate function [with _BinaryPredicate = std::__1::__equal_to<char,
char> &, _ForwardIterator1 =
      std::__1::istreambuf_iterator<char, std::__1::char_traits<char> >,
_ForwardIterator2 = std::__1::__wrap_iter<char
      *>] not viable: no known conversion from 'typename
std::iterator_traits<istreambuf_iterator<char, char_traits<char>
      > >::iterator_category' (aka 'std::__1::input_iterator_tag') to
'std::__1::forward_iterator_tag' for 6th argument
__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
^
2 errors generated.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_compile_checks.html

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This is user error, std::search() requires forward iterators and the library is
not required to diagnose it.  Defining _GLIBCXX_CONCEPT_CHECKS causes it to be
rejected.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[howarth.at.gcc at gmail dot com]

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

--- Comment #3 from Jack Howarth <howarth.at.gcc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #2)
> This is user error, std::search() requires forward iterators and the library
> is not required to diagnose it.  Defining _GLIBCXX_CONCEPT_CHECKS causes it
> to be rejected.

Is the use of _GLIBCXX_CONCEPT_CHECKS well enough advertised in the
documentation that we can expect the average developer to know to invoke it?

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[howarth.at.gcc at gmail dot com]

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

--- Comment #4 from Jack Howarth <howarth.at.gcc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #2)
> This is user error, std::search() requires forward iterators and the library
> is not required to diagnose it.  Defining _GLIBCXX_CONCEPT_CHECKS causes it
> to be rejected.

Also, is there a simple fix to the test case which avoids the user error or
does the code have to be rewritten in a major way.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jack Howarth from comment #3)
> Is the use of _GLIBCXX_CONCEPT_CHECKS well enough advertised in the
> documentation that we can expect the average developer to know to invoke it?

It's documented three times! :-)

https://gcc.gnu.org/onlinedocs/libstdc++/manual/using_macros.html
https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_compile_checks.html
https://gcc.gnu.org/onlinedocs/libstdc++/manual/concept_checking.html

(In reply to Jack Howarth from comment #4)
> Also, is there a simple fix to the test case which avoids the user error or
> does the code have to be rewritten in a major way.

Don't try to std::search in a streambuf, copy the data elsewhere and search in
the copy.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
And even if they don't read the libstdc++ documentation, std::search doesn't
work with input iterators, that's always been true:

https://www.sgi.com/tech/stl/search.html
http://en.cppreference.com/w/cpp/algorithm/search

The code is simply broken and should be fixed.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[howarth.at.gcc at gmail dot com]

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

--- Comment #7 from Jack Howarth <howarth.at.gcc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #6)
> And even if they don't read the libstdc++ documentation, std::search doesn't
> work with input iterators, that's always been true:
> 
> https://www.sgi.com/tech/stl/search.html
> http://en.cppreference.com/w/cpp/algorithm/search
> 
> The code is simply broken and should be fixed.

Is there e reason for gcc not to detect such wrong code issues by default?
Perhaps gcc 6 should finally default to --enable-concept-checks.

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jack Howarth from comment #7)
> Is there e reason for gcc not to detect such wrong code issues by default?

Read the docs, the concept checks only enforce C++03 requirements, so turning
them on by default would erroneously reject valid C++11 programs that rely on
the relaxed 

> Perhaps gcc 6 should finally default to --enable-concept-checks.

Definitely not.

The reason I haven't just closed this as INVALID is that in C++11 mode we could
add unconditional static assertions, but someone needs to do the work of adding
those assertions, and making sure they test the right concepts (which may
differ from the existing C++03 checks).

[Bug libstdc++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
There are actually good reasons *not* to reject input iterators at
compile-time.

You could have an iterator which meets most, but not all, the forward iterator
requirements, and so must have input_iterator_tag as its category. Such as
iterator could work fine with std::search, if we don't reject it via a static
assertion.

(istreambuf_iterator is not such an iterator, as it's genuinely a single-pass
iterator, and so can't be used ... but we can't reliably detect that as the
only property we can test is the iterator_category tag).

[Bug c++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |accepts-invalid
         Resolution|---                         |FIXED
          Component|libstdc++                   |c++
                URL|https://llvm.org/bugs/show_ |
                   |bug.cgi?id=23307            |
             Status|UNCONFIRMED                 |RESOLVED
           See Also|                            |https://llvm.org/bugs/show_
                   |                            |bug.cgi?id=23307
   Target Milestone|---                         |10.0

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
GCC 10+ started to reject the code just the same as CLANG does.

So I am going to close this as fixed for GCC 10 and leave it that way.

[Bug c++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-12-06
             Status|RESOLVED                    |NEW
         Resolution|FIXED                       |---

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #10)
> GCC 10+ started to reject the code just the same as CLANG does.

Clang doesn't reject it, libc++ does. Clang with libstdc++ accepts it, and so
does GCC trunk (you just need some more headers for recent versions):

#include <string>
#include <streambuf>
#include <istream>
#include <iterator>
#include <algorithm>
void f(std::istream &s, std::string x) {
      std::istreambuf_iterator<char> eod;
      std::search(std::istreambuf_iterator<char>(s),
                  eod,
                  x.begin(),
                  x.end());
}

Reopened.

[Bug c++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[redi at gcc dot gnu.org]

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

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #9)
> There are actually good reasons *not* to reject input iterators at
> compile-time.
> 
> You could have an iterator which meets most, but not all, the forward
> iterator requirements, and so must have input_iterator_tag as its category.
> Such as iterator could work fine with std::search, if we don't reject it via
> a static assertion.
> 
> (istreambuf_iterator is not such an iterator, as it's genuinely a
> single-pass iterator, and so can't be used ... but we can't reliably detect
> that as the only property we can test is the iterator_category tag).

Since C++20 we can also check the iterator_concept tag. That means we can allow
iterators that identify as input iterators according to iterator_category, but
forward iterators (or stronger) according to iterator_concept.

[Bug c++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[pinskia at gcc dot gnu.org]

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #11)
> (In reply to Andrew Pinski from comment #10)
> > GCC 10+ started to reject the code just the same as CLANG does.
> 
> Clang doesn't reject it, libc++ does. Clang with libstdc++ accepts it, and
> so does GCC trunk (you just need some more headers for recent versions):

I should have known the more headers for recent versions :).

[Bug c++/65861] libstdc++ is silently generating wrong code when its std::search is given an input iterator

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.0                        |---