Bug 40497

Summary: [C++0x] troubles with std::next / std::prev declarations
Product: gcc Reporter: e28773 <e28773>
Component: libstdc++Assignee: Paolo Carlini <paolo.carlini>
Status: RESOLVED FIXED    
Severity: normal CC: fang, gcc-bugs, jwakely.gcc
Priority: P3 Keywords: rejects-valid
Version: 4.4.0   
Target Milestone: 4.5.1   
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2009-06-20 13:04:18
Attachments: test-case
testcase - ii

Description e28773 2009-06-20 01:04:55 UTC
Hello

using gcc 4.4 with -std=c++0x and libstdc++ off the trunk, I get several errors on old code.
When calling next(X) with a user defined class type X, adl does not seem to prefer the next function defined in the namespace of X.

Testcase from boost:
http://www.boost.org/development/tests/trunk/developer/output/Sandia-gcc-boost-bin-v2-libs-fusion-test-cons-test-gcc-4-4-0_gnu++0x-debug-sequence.html

changing the types of the second arguments of std::next/std::prev from typename iterator_traits<Iterator>::difference_type to typename Iterator::difference_type (as proposed in 24.4p4) does work. I assume this is a bug.
Comment 1 Richard Biener 2009-06-20 10:13:54 UTC
We need preprocessed source as a testcase.
Comment 2 e28773 2009-06-20 12:30:08 UTC
Created attachment 18029 [details]
test-case
Comment 3 e28773 2009-06-20 12:31:09 UTC
Created attachment 18030 [details]
testcase - ii
Comment 4 e28773 2009-06-20 12:32:02 UTC
Comment on attachment 18029 [details]
test-case

namespace X
{
	class C
	{
	};

	template<class T>void next(T)
	{
	}
}
using namespace X;

#include <string>
using namespace std;

int main()
{
	C c;
	next(c);
}
Comment 5 e28773 2009-06-20 12:33:47 UTC
here we go ;)

I forgot a ';' in line 5 of the main.cpp-file
Comment 6 Richard Biener 2009-06-20 13:04:18 UTC
Confirmed (testcase from comment #4 with -std=c++0x).

It looks like a failure to honor SFINAE?

$ g++-4.4 -S -std=c++0x t.C
In file included from /usr/include/c++/4.4/bits/stl_algobase.h:67,
                 from /usr/include/c++/4.4/bits/char_traits.h:41,
                 from /usr/include/c++/4.4/string:42,
                 from t.C:13:
/usr/include/c++/4.4/bits/stl_iterator_base_types.h: In instantiation of ‘std::iterator_traits<X::C>’:
t.C:19:   instantiated from here
/usr/include/c++/4.4/bits/stl_iterator_base_types.h:127: error: no type named ‘iterator_category’ in ‘class X::C’
/usr/include/c++/4.4/bits/stl_iterator_base_types.h:128: error: no type named ‘value_type’ in ‘class X::C’
/usr/include/c++/4.4/bits/stl_iterator_base_types.h:129: error: no type named ‘difference_type’ in ‘class X::C’
/usr/include/c++/4.4/bits/stl_iterator_base_types.h:130: error: no type named ‘pointer’ in ‘class X::C’
/usr/include/c++/4.4/bits/stl_iterator_base_types.h:131: error: no type named ‘reference’ in ‘class X::C’
Comment 7 Paolo Carlini 2009-06-20 21:35:51 UTC
Ok, implementing the letter of the current draft (n2857) seems trivial to do (note: at some point, in particular for extensive changes, we will stop doing that in the release branch).
Comment 8 paolo@gcc.gnu.org 2009-06-20 22:27:26 UTC
Subject: Bug 40497

Author: paolo
Date: Sat Jun 20 22:27:04 2009
New Revision: 148751

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=148751
Log:
2009-06-20  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/40497
	* include/bits/stl_iterator_base_funcs.h (next, prev): Fix the
	signature per the current C++1x draft (N2857).
	* testsuite/24_iterators/operations/40497.cc: Add.

Added:
    trunk/libstdc++-v3/testsuite/24_iterators/operations/40497.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_iterator_base_funcs.h

Comment 9 paolo@gcc.gnu.org 2009-06-20 22:27:36 UTC
Subject: Bug 40497

Author: paolo
Date: Sat Jun 20 22:27:21 2009
New Revision: 148752

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=148752
Log:
2009-06-20  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/40497
	* include/bits/stl_iterator_base_funcs.h (next, prev): Fix the
	signature per the current C++1x draft (N2857).
	* testsuite/24_iterators/operations/40497.cc: Add.

Added:
    branches/gcc-4_4-branch/libstdc++-v3/testsuite/24_iterators/operations/40497.cc
Modified:
    branches/gcc-4_4-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_4-branch/libstdc++-v3/include/bits/stl_iterator_base_funcs.h

Comment 10 Paolo Carlini 2009-06-20 22:29:06 UTC
Fixed for 4.4.1.
Comment 11 e28773 2009-06-20 23:21:29 UTC
(In reply to comment #10)
> Fixed for 4.4.1.
> 
After all, this is still a bug of ADL/SFINAE? Even if the declaration of next/prev does not match with the one proposed in the current draft, the right function (that is in the namespace of the argument) should still be chosen?!
Comment 12 Paolo Carlini 2009-06-21 01:03:59 UTC
Yes, either that or wontfix until we have concepts as a library issue.
Comment 13 Paolo Carlini 2009-06-21 01:05:23 UTC
See: http://gcc.gnu.org/ml/libstdc++/2009-06/msg00057.html
Comment 14 Richard Biener 2009-06-21 10:38:06 UTC
Testcase w/o std=c++0x:

template <typename I> struct T { typedef typename I::d d; };
template <typename I> I next(I __x, typename T<I>::d __n = 1);
namespace X
{
  class C { };
  template<class T> void next(T) { }
}
int main()
{
  X::C c;
  next(c);
}

but EDG rejects this also:

t.C(1): error: class "X::C" has no member "d"
  template <typename I> struct T { typedef typename I::d d; };
                                                       ^
          detected during instantiation of class "T<I> [with I=X::C]" at line 11

t.C(11): error: more than one instance of function template "next" matches the argument list:
            function template "void X::next(T)"
            function template "I next(I, T<I>::d)"
            argument types are: (X::C)
    next(c);
    ^

I'm not sure SFINAE applies here as the substitution T<I> succeeds.

With the 'typename' removed in the decl for next we get

t.C(2): error: nontype "T<I>::d [with I=I]" is not a type name
  template <typename I> I next(I __x, T<I>::d __n = 1);
                                      ^

t.C(11): error: more than one instance of function template "next" matches the argument list:
            function template "void X::next(T)"
            function template "I next(I, <error-type>)"
            argument types are: (X::C)
    next(c);
    ^

with

template <typename I> I next(typename T<I>::d __n);

we finally get SFINAE and X::next is chosen.

The issue here seems to be that the default value for the argument somehow
gets in the way and so the 2nd argument isn't checked properly?

So an implementation workaround would be to use overloading for the
default argument case like

template <typename I> I next(I __x, typename T<I>::d __n);
template <typename I> I next(I __x);

with the first arg obfuscated so that SFINAE applies,
typename iterator_traits<_InputIterator>::_InputIterator

or something like this?
Comment 15 Richard Biener 2009-06-21 10:41:18 UTC
Bah, of course the template param isn't forwarded as a type in iterator_traits
nor is it required as a type for iterator implementations.
Comment 16 Paolo Carlini 2009-06-21 11:08:25 UTC
This is interesting and indeed, I'm not at all sure it's a C++ bug, but I seem to remember an open PR about SFINAE vs defaults, we should check. As regards the library side, anyway, I'm against putting in place ugly workarounds, do not really make sense in this case. These next/prev are supposed to be very straightforward facilities, straightforward to implement when concepts are available. If it turns out they just make more difficult testing the other C++0x bits we already have in place we'll simply remove the code for now: let's make sure we don't ship 4.4.1 with this issue open.
Comment 17 Paolo Carlini 2009-07-26 14:46:20 UTC
Maybe Jason can help confirming that we don't have a C++ issue here?!? In that case, however, since Concepts are gone, I think we should probably file a library DR or raise the issue vs the rolled-back Draft. Opinions about that?

Anyway, something consistent with the C++03 advance, would be probably ok, in a non-Concepts context:

  template<typename _InputIterator, typename _Distance>
    inline _InputIterator 
    next(_InputIterator __x, _Distance __n = 1)
    {
      std::advance(__x, __n);
      return __x;
    }

I'm thinking of changing the libstdc++ code like this, for now, instead of removing it completely to be safe.
Comment 18 Paolo Carlini 2009-07-26 15:45:42 UTC
Never mind the draft next, of course doesn't work, grunt (_Distance?)
Comment 19 Jason Merrill 2009-07-27 01:08:20 UTC
That does seem like a SFINAE bug.
Comment 20 Jason Merrill 2009-07-27 05:46:53 UTC
Actually, no.  It seems that T<X::C> being invalid doesn't result in a SFINAE situation.

14.9.2/8:
  Only invalid types and expressions in the immediate context of the function type and its template parameter types can result in a deduction failure. [ Note: The evaluation of the substituted types and expressions can result in side effects such as the instantiation of class template specializations and/or function template specializations, the generation of implicitly-defined functions, etc. Such side effects are not in the “immediate context” and can result in the program being ill-formed. — end note ]
Comment 21 Paolo Carlini 2009-07-27 09:34:19 UTC
Thanks Jason. I'm tentatively recategorizing as libstdc++, then. In general, I'm not at all sure what we should do about it, however, now that Concepts are gone. I don't think we can hope to avoid, here and elsewhere, all the typical problems caused by unconstrained templates. Certainly, having the two separate overloads:

  template<typename InputIterator, typename Distance>
    InputIterator next(InputIterator, Distance);

  template<typename InputIterator>
    InputIterator next(InputIterator);
 
would lead to cleaner error messages in case of ambiguities, but I'm not sure we can in general achieve much more than this.
Comment 22 Paolo Carlini 2009-12-16 16:15:29 UTC
Jon, what's your opinion about this one, now that concepts are gone? Frankly, I don't think we can do much to avoid this type of problem.
Comment 23 Jonathan Wakely 2009-12-17 11:55:30 UTC
I can't see any 100% reliable way to prevent this problem, because the catch-all specialisation of iterator_traits can be instantiated with non-iterator types.

We could try tricks like this to restrict std::next to things that look like iterators:

// deduction fails if _Iter doesn't meet InputIterator requirements
template<typename _Iter,
  typename _Sfinae1 = decltype(*std::declval<_Iter&>()),
  typename _Sfinae2 = decltype(++std::declval<_Iter&>()),
  typename _Sfinae3 = decltype(std::declval<_Iter&>()++),
  typename _Sfinae4 = decltype(*std::declval<_Iter&>()++),
  typename _Sfinae5 = decltype(std::declval<_Iter&>()==std::declval<_Iter&>())
  >
  typename iterator_traits<_Iter>::difference_type
  __safe_iterator_diff_type(_Iter);

template<typename _InputIterator>
  inline _InputIterator
  next(_InputIterator __x, decltype(__safe_iterator_diff_type(__x)) __n = 1)
  {
    std::advance(__x, __n);
    return __x;
  }

But that will still fail for types that have an iterator-like interface.  Then again, I think such types would be detected as iterators even with concepts.
Comment 24 Jonathan Wakely 2009-12-17 12:01:22 UTC
Although that breaks if any of the iterator-like operators exists but is not accessible - I think concepts would have worked in that case, but I'm not sure
Comment 25 Paolo Carlini 2009-12-17 12:07:21 UTC
Interesting trick, really, the power of extended SFINAE ;) I think we should keep that in mind, for the DO THE RIGHT THING clause of the containers too, for example (some time ago Howard told me that in his Metrowerks implementation, it is *much* better than the minimum requirements of the standard, it almost always actually does the right thing ;) but he did that a lot of time ago, it's probably just a jungle of enable_ifs + "something"). So... What do you think, shall we have an "__is_iterator" trait and use it where it's useful? For post-4.5.0, in any case...
Comment 26 Paolo Carlini 2009-12-17 12:11:11 UTC
Yeah, the usual accessibility issue: in Santa Cruz I discussed that briefly with Doug, he pretended to convince people that with extended SFINAE you can implement trivially *any* introspection trait, then somebody (me too) pointed out the accessibility issue and he said "bah, I don't care, accessibility is "broken" n  C++ anyway" ;)
Comment 27 Jonathan Wakely 2009-12-17 12:23:17 UTC
ha!

std::next would want is_input_iterator and std::prev would ideally want is_bidi_iterator, so maybe more than one trait
Comment 28 Paolo Carlini 2009-12-17 12:25:13 UTC
Actually, details, std::next now wants _ForwardIterator, don't ask me to lookup the DR ;)
Comment 29 Jonathan Wakely 2009-12-18 00:15:43 UTC
I think it might be worth opening an issue about these functions, it's far too easy for them to cause problems and make the names "next" and "prev" unusable for user functions:

// simplified version of <iterator> and <string>
namespace std {
template<class Iterator> struct iterator_traits {
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};

template <class InputIterator>
InputIterator next(InputIterator x,
typename std::iterator_traits<InputIterator>::difference_type n = 1);

struct string { };
}


// user code

struct C { };
void next(C, std::string) { }

int main()
{
  C c;
  next(c, std::string());
}

For a user-declared function with an argument of type from namespace std, ADL finds std::next and we get the same error due to instantiating iterator_traits<C>
Comment 30 Paolo Carlini 2009-12-18 00:58:52 UTC
I agree. In general, however, I'm not sure how general the issue is, now that concepts are gone. For example, consider the case of the various classification functions (from C99): you can still find a PR filed by Howard a lot of time ago, where he complained that we weren't restricting the templates and that could cause problems with some user functions, which arguably were not supposed to conflict with those C99 extensions (in strict C++03 mode). Thus we added the enable_ifs. Now, if you look at the WP, those use just unrestricted templates and indeed user functions can be affected, similarly to next and prev. Outside the few places in the WP where the famous "does not participate to overload resolution" is used, there are in my opinion far too many grey areas where, missing real concepts, some sort of restriction is supposed to be enforced for QoI to counteract the obnoxious ADL problems, without however stating that clearly anywhere: if you talk to Howard he more or less assumes by default, irrespective of the actual WP, that all the templates in the library are somewhat restricted via enable_ifs, for instance all the mathematical functions for arithmetic types only, etc, otherwise the users can complain *rightfully* about ADL-caused problems at any time. Well, I'm not sure that is correct, I don't think the library has necessarily to battle this futile war against ADL ;) with tons of enable_ifs even where the standard definitely does not say that explicitly. To finish, a remark is in order about the *tough* cases, like *iterator* exactly, where you can't really replace concepts, via SFINAE & co, for the reasons which we just discussed. What should the standard say? Should it try to do better than C++03 now that we know about enable_if and extended SFINAE, etc, or not, in the famous futile war with ADL?
Comment 31 Jonathan Wakely 2010-05-27 10:21:10 UTC
(In reply to comment #23)
> I can't see any 100% reliable way to prevent this problem, because the
> catch-all specialisation of iterator_traits can be instantiated with
> non-iterator types.

I was under the impression that the default specialisation of iterator_traits was meant to be catch-all, but Alisdair Meredith described his implementation and I realised that the definition in [iterator.traits]/2 applies to type "Iterator" and [iterator.traits]/1 says "if Iterator is the type of an iterator"

So now I believe that we can (and should) restrict that specialisation to types that really are iterators. If iterator_traits<NotAnIterator>::difference_type doesn't exist then SFINAE will apply and std::next/std::prev will not cause invalid instantiations.

Comment 32 Paolo Carlini 2010-05-27 10:51:19 UTC
You mean, in practice, we should only check that difference_type exists?
Comment 33 Jonathan Wakely 2010-05-27 11:54:29 UTC
Alisdair checks for Iterator::iterator_category, which seems a very sensible way of checking if a type wants to be recognised by iterator_traits

If iterator_category exists, then assume difference_type and the other nested types do too.
Comment 34 Paolo Carlini 2010-05-27 11:58:43 UTC
Ok, let's do this, seems definitely an improvement, and since affects only C++0x and enables more people to test it, I think should go in 4_5-branch too. By the way, if I remember correctly, Howard used to do something very similar.
Comment 35 Paolo Carlini 2010-05-27 16:25:08 UTC
Note, plain pointers and pointers to const must be dealt with separately.
Comment 36 paolo@gcc.gnu.org 2010-05-27 17:37:36 UTC
Subject: Bug 40497

Author: paolo
Date: Thu May 27 17:37:11 2010
New Revision: 159933

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159933
Log:
2010-05-27  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/40497
	* include/bits/cpp_type_traits.h (__is_iterator): Add.
	* include/bits/stl_iterator_base_funcs.h (next, prev): Use it.
	* testsuite/24_iterators/operations/40497.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/24_iterators/operations/40497.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/cpp_type_traits.h
    trunk/libstdc++-v3/include/bits/stl_iterator_base_funcs.h

Comment 37 paolo@gcc.gnu.org 2010-05-27 17:45:28 UTC
Subject: Bug 40497

Author: paolo
Date: Thu May 27 17:44:59 2010
New Revision: 159934

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159934
Log:
2010-05-27  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/40497
	* include/bits/cpp_type_traits.h (__is_iterator): Add.
	* include/bits/stl_iterator_base_funcs.h (next, prev): Use it.
	* testsuite/24_iterators/operations/40497.cc: New.

Added:
    branches/gcc-4_5-branch/libstdc++-v3/testsuite/24_iterators/operations/40497.cc
Modified:
    branches/gcc-4_5-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_5-branch/libstdc++-v3/include/bits/cpp_type_traits.h
    branches/gcc-4_5-branch/libstdc++-v3/include/bits/stl_iterator_base_funcs.h

Comment 38 Paolo Carlini 2010-05-27 17:46:27 UTC
Fixed for 4.5.1.