Bug 78830 - std::prev accepts ForwardIterator-s
Summary: std::prev accepts ForwardIterator-s
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 7.0
: P3 enhancement
Target Milestone: 10.0
Assignee: Not yet assigned to anyone
URL:
Keywords:
: 97232 (view as bug list)
Depends on:
Blocks:
 
Reported: 2016-12-16 08:03 UTC by Andrzej Krzemienski
Modified: 2020-09-28 17:26 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2016-12-16 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Andrzej Krzemienski 2016-12-16 08:03:32 UTC
The following code compiles, even though according to the C++ Standard it is ill-formed.

```
#include <forward_list>
#include <algorithm>

int main()
{
    std::forward_list<int> il = {1, 2, 3, 4, 5, 6, 7}; 
    auto iter = std::prev(il.end());
}
```

While the fix for 62039 mitigates the problem, according to the Standard this code should be rejected unconditionally. Clang does this by using enable_if trick. A static_assert would also work.
Comment 1 Jonathan Wakely 2016-12-16 10:46:27 UTC
Why is it ill-formed?

By my reading it's undefined, which does mean we can reject it anyway, but I don't see anything to make it ill-formed that would require rejecting it unconditionally.
Comment 2 Andrzej Krzemienski 2016-12-16 14:02:17 UTC
Sorry, you are correct. As per [res.on.functions], passing types that do not satisfy the requirements is a UB, and therefore a well formed program. GCC is standard-compliant in this respect.

So, I have lost my strongest argument, but I still feel this check should not be "opt-in". As a QOI matter, could a standard-allowed UB be implemented as a compile-time failure?
Comment 3 Jonathan Wakely 2016-12-16 16:25:34 UTC
Yes, we can certainly do that, and I agree it would be a good idea.

Marking as "Enhancement" then, rather than an accepts-invalid bug.
Comment 4 Andrzej Krzemienski 2016-12-19 11:56:47 UTC
Just to clarify, what I request for this "unconditional" check is not the existence of all operators, but only the check for the iterator_tag (we expect a bidirectional iterator).

That is, the problem that I believe needs immediate solution is not improving the error messages a la concepts, but preventing the current situation where GCC assumes that the iterator passed to prev() is at least BidirectionalIterator, and based on this assumption it tag-dispatches the call to advance() overload for ForwardIterators, where it calls operator++.
Comment 5 Piotr Nycz 2019-03-22 13:42:42 UTC
Still not "enhanced" (gcc9). 
CLANG with its std-lib correctly (IMO) does not compile it.

I understand this is UB - but implementation might suggest it is checked that iterator is biderectional (at least ) but this check has no effect.

```

  template<typename _BidirectionalIterator>
    inline _BidirectionalIterator
    prev(_BidirectionalIterator __x, typename
	 iterator_traits<_BidirectionalIterator>::difference_type __n = 1) 
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
				  _BidirectionalIterator>)
      std::advance(__x, -__n);
      return __x;
    }

``` 

it is very troublesome to realize that there is something wrong here - when you have UB="very long time consuming loop (LONG_MAX iteration probably)"

Is there anything that can be done to increase importance of this enhancement?
Comment 6 Jonathan Wakely 2019-03-22 13:51:25 UTC
(In reply to Piotr Nycz from comment #5)
> CLANG with its std-lib correctly (IMO) does not compile it.

As explained above, GCC is already correct here.

> I understand this is UB - but implementation might suggest it is checked
> that iterator is biderectional (at least ) but this check has no effect.

It does if you compile with -D_GLIBCXX_CONCEPT_CHECKS

 
> Is there anything that can be done to increase importance of this
> enhancement?

Write a patch?

https://gcc.gnu.org/contribute.html
Comment 7 Jonathan Wakely 2019-03-22 13:58:30 UTC
(In reply to Jonathan Wakely from comment #6)
> (In reply to Piotr Nycz from comment #5)
> > CLANG with its std-lib correctly (IMO) does not compile it.
> 
> As explained above, GCC is already correct here.
> 
> > I understand this is UB - but implementation might suggest it is checked
> > that iterator is biderectional (at least ) but this check has no effect.
> 
> It does if you compile with -D_GLIBCXX_CONCEPT_CHECKS

If you enable concept checks it will fail to compile:

In file included from /usr/include/c++/8/bits/concept_check.h:56,
                 from /usr/include/c++/8/bits/move.h:34,
                 from /usr/include/c++/8/bits/stl_iterator.h:65,
                 from /usr/include/c++/8/bits/forward_list.h:37,
                 from /usr/include/c++/8/forward_list:38,
                 from prev.cc:1:
/usr/include/c++/8/bits/boost_concept_check.h: In instantiation of ‘void __gnu_cxx::_BidirectionalIteratorConcept<_Tp>::__constraints() [with _Tp = std::_Fwd_list_iterator<int>]’:
/usr/include/c++/8/bits/boost_concept_check.h:62:39:   required from ‘void __gnu_cxx::__function_requires() [with _Concept = __gnu_cxx::_BidirectionalIteratorConcept<std::_Fwd_list_iterator<int> >]’
/usr/include/c++/8/bits/stl_iterator_base_funcs.h:228:7:   required from ‘_BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type) [with _BidirectionalIterator = std::_Fwd_list_iterator<int>; typename std::iterator_traits<_Iter>::difference_type = long int]’
prev.cc:7:35:   required from here
/usr/include/c++/8/bits/boost_concept_check.h:506:7: error: no match for ‘operator--’ (operand type is ‘std::_Fwd_list_iterator<int>’)
       --__i;                            // require predecrement operator
       ^~~~~
/usr/include/c++/8/bits/boost_concept_check.h:507:10: error: no ‘operator--(int)’ declared for postfix ‘--’ [-fpermissive]
       __i--;                            // require postdecrement operator
       ~~~^~
/usr/include/c++/8/bits/boost_concept_check.h: In instantiation of ‘void __gnu_cxx::_ConvertibleConcept<_From, _To>::__constraints() [with _From = std::forward_iterator_tag; _To = std::bidirectional_iterator_tag]’:
/usr/include/c++/8/bits/boost_concept_check.h:62:39:   required from ‘void __gnu_cxx::__function_requires() [with _Concept = __gnu_cxx::_ConvertibleConcept<std::forward_iterator_tag, std::bidirectional_iterator_tag>]’
/usr/include/c++/8/bits/boost_concept_check.h:505:43:   required from ‘void __gnu_cxx::_BidirectionalIteratorConcept<_Tp>::__constraints() [with _Tp = std::_Fwd_list_iterator<int>]’
/usr/include/c++/8/bits/boost_concept_check.h:62:39:   required from ‘void __gnu_cxx::__function_requires() [with _Concept = __gnu_cxx::_BidirectionalIteratorConcept<std::_Fwd_list_iterator<int> >]’
/usr/include/c++/8/bits/stl_iterator_base_funcs.h:228:7:   required from ‘_BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type) [with _BidirectionalIterator = std::_Fwd_list_iterator<int>; typename std::iterator_traits<_Iter>::difference_type = long int]’
prev.cc:7:35:   required from here
/usr/include/c++/8/bits/boost_concept_check.h:223:27: error: conversion from ‘std::forward_iterator_tag’ to non-scalar type ‘std::bidirectional_iterator_tag’ requested
       _To __y _IsUnused = __x;
                           ^~~

But I don't recommend using those concepts checks for C++11 or later, because some of the checks are outdated and only enforce the C++98 requirements, so they're wrong for the current standard.

If you compile with -D_GLIBCXX_ASSERTIONS (or -D_GLIBCXX_DEBUG which also enables the former) then it will fail at runtime when trying to advance a non-bidirectional iterator by a negative number:

/usr/include/c++/8/bits/stl_iterator_base_funcs.h:151: constexpr void std::__advance(_InputIterator&, _Distance, std::input_iterator_tag) [with _InputIterator = std::_Fwd_list_iterator<int>; _Distance = long int]: Assertion '__n >= 0' failed.
Aborted (core dumped)

So we actually already provide two ways to prevent this UB.
Comment 8 Jonathan Wakely 2019-03-22 14:44:48 UTC
I don't think it's conforming to reject this at compile-time, because std::prev(it, -1) is equivalent to std::advance(it, 1) which is valid for forward iterators. So libc++ has a bug, it is not allowed to reject forward iterators unconditionally (only when it can prove the argument to prev is greater than zero).

The best we can do is check for negative values at runtime and abort, which we already do.

One day I hope to be able to enhance those assertions to warn at compile-time if the compiler can tell the assertion will fail, but that is not currently possible.
Comment 9 Jonathan Wakely 2019-03-22 14:48:23 UTC
P.S. in C++2a std::ranges::prev does make it ill-formed to pass arguments that don't satisfy the BidirectionalIterator concept. But std::prev doesn't.
Comment 10 Andrzej Krzemienski 2019-03-22 15:21:59 UTC
For `std::prev()` it is UB, but by my reading of UB (http://eel.is/c++draft/intro.defs#defns.undefined) it is legal for the implementation to respond with "terminating a translation" "with the issuance of a diagnostic message", given that the UB in question can be detected statically.
Comment 11 Jonathan Wakely 2019-03-22 15:34:39 UTC
As I already said:

(In reply to Jonathan Wakely from comment #8)
> One day I hope to be able to enhance those assertions to warn at
> compile-time if the compiler can tell the assertion will fail, but that is
> not currently possible.
Comment 12 Jonathan Wakely 2019-03-22 15:36:13 UTC
Finally, with -Waggressive-loop-optimizations -Wsystem-headers -O1 it does terminate translation:

/usr/include/c++/8/bits/stl_iterator_base_funcs.h: In function ‘int main()’:
/usr/include/c++/8/bits/stl_iterator_base_funcs.h:152:7: error: iteration 9223372036854775807 invokes undefined behavior [-Werror=aggressive-loop-optimizations]
       while (__n--)
       ^~~~~
/usr/include/c++/8/bits/stl_iterator_base_funcs.h:152:7: note: within this loop

It's not currently possible to make this work automatically, without -Wsystem-headers.
Comment 13 Jonathan Wakely 2020-09-28 16:11:04 UTC
*** Bug 97232 has been marked as a duplicate of this bug. ***
Comment 14 Jonathan Wakely 2020-09-28 16:46:16 UTC
There is an LWG issue requesting clarification in the standard:
https://wg21.link/lwg3197

Option B is consistent with the interpretation of libstdc++ (and recent versions of libc++). If Option A or C is accepted, I will change libstdc++ accordingly. Until then, I maintain that we conform to the standard as currently written.
Comment 15 Andrzej Krzemienski 2020-09-28 17:19:06 UTC
How come? 
[algorithms.requirements], paragraph 4, bullet 5 (http://eel.is/c++draft/algorithms#requirements-4.5) says:

If an algorithm's template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall meet the Cpp17BidirectionalIterator requirements
Comment 16 Andrzej Krzemienski 2020-09-28 17:26:50 UTC
Oh, I see. The above requirement applies only to chapter Algorithms library. Not Iterators library. Sorry.