[Bug libstdc++/33490] New: parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[Bug libstdc++/33490] New: parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[bangerth at dealii dot org]

The parallel version of std::accumulate assumes that iterator_traits
are declared for the iterator arguments. However, the standard only
requires them to be of kind InputIterator, and the table that describes
what types of this kind have to satisfy does not include the necessity
to declare a specialization of std::iterator_traits.

Example in point: this doesn't compile with current parallel v3:
--------------------
#include <numeric>

struct X {
    int operator* () const;
    bool operator != (const X&) const;
    X operator ++ ();
};

void f () {
  X p, q;
  std::accumulate (p, q, 0);
}
---------------------

4.3.0/bits/stl_iterator_base_types.h: In instantiation of
'std::iterator_traits<X>':
4.3.0/parallel/numeric:83:   instantiated from 'T
std::__parallel::accumulate(_IIter, _IIter, T, __gnu_parallel::parallelism)
[with _IIter = X, T = int]'
x.cc:11:   instantiated from here
4.3.0/bits/stl_iterator_base_types.h:133: error: no type named
'iterator_category' in 'struct X'
4.3.0/bits/stl_iterator_base_types.h:134: error: no type named 'value_type' in
'struct X'
4.3.0/bits/stl_iterator_base_types.h:135: error: no type named
'difference_type' in 'struct X'
4.3.0/bits/stl_iterator_base_types.h:136: error: no type named 'pointer' in
'struct X'
4.3.0/bits/stl_iterator_base_types.h:137: error: no type named 'reference' in
'struct X'


-- 
           Summary: parallel v3: std::accumulate assumes iterators have
                    std::iterator_traits declared
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: rejects-valid
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bangerth at dealii dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[bkoz at gcc dot gnu dot org]

-- 

bkoz at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bkoz at redhat dot com
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-09-19 17:08:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[singler at ira dot uka dot de]

------- Comment #1 from singler at ira dot uka dot de  2007-09-19 18:42 -------
The standard states clearly (24.3.1):

"Accordingly, it is required that if Iterator is the type of an iterator, the
types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category

be defined as..."

That this is missing in the requirement lists in 24.1.1 and 24.1.2 is probably
due to the fact that it does not concern the Iterator class itself, but
iterator_traits<Iterator>.

The Sun SGI documentation also states:

"If you are defining a new iterator type I, then you must ensure that
iterator_traits<I> is defined properly."

Thus, struct X is an invalid iterator.


-- 

singler at ira dot uka dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |singler at ira dot uka dot
                   |                            |de


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[bangerth at dealii dot org]

------- Comment #2 from bangerth at dealii dot org  2007-09-19 19:11 -------
(In reply to comment #1)

> That this is missing in the requirement lists in 24.1.1 and 24.1.2 is probably
> due to the fact that it does not concern the Iterator class itself, but
> iterator_traits<Iterator>.

I disagree with this interpretation. For me, Table 72 states the requirements
that InputIterators have to satisfy. It doesn't list defining iterator_traits,
and I don't think 24.3.1 wants to come back and add this requirement.

This also appears to be the interpretation that libstdc++ takes in most
places.

What do others think about this?

W.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[bkoz at gcc dot gnu dot org]

------- Comment #3 from bkoz at gcc dot gnu dot org  2007-10-18 16:18 -------

Current mainline in parallel mode still has this fail, for the record.

Looking at the concepts code.... 

From:
http://www.generic-programming.org/software/ConceptGCC/

include/bits/stl_numeric.h:

  template<_GLIBCXX_REQ_PARM(InputIterator, _Iter), 
           _GLIBCXX_REQ_PARM(CopyConstructible, _Tp)>
    _GLIBCXX_WHERE(Addable<_Tp, _Iter::value_type>, 
                   Assignable<_Tp, 
                              Addable<_Tp, _Iter::value_type>::result_type>)
    _Tp
    accumulate(_Iter __first, _Iter __last, _Tp __init)
    {
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
        __init = __init + *__first;
      return __init;
    }

which is also assuming iterator_traits::value_type....

-benjamin


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[singler at ira dot uka dot de]

------- Comment #4 from singler at ira dot uka dot de  2007-10-19 08:39 -------
There are other places in regular stl_algo.h where
iterator_traits<It>::value_type is assumed, not only for concept checking, but
for actual functionality, e. g. 

  template<typename _InputIterator, typename _OutputIterator>
    _OutputIterator
    __unique_copy(_InputIterator __first, _InputIterator __last,
                  _OutputIterator __result,
                  input_iterator_tag, output_iterator_tag)
    {
      // concept requirements -- taken care of in dispatching function
      typename iterator_traits<_InputIterator>::value_type __value = *__first;
      *__result = __value;
      while (++__first != __last)
        if (!(__value == *__first))
          {
            __value = *__first;
            *++__result = __value;
          }
      return ++__result;
    }



  template<typename _RandomAccessIterator>
    void
    __rotate(_RandomAccessIterator __first,
             _RandomAccessIterator __middle,
             _RandomAccessIterator __last,
             random_access_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                                  _RandomAccessIterator>)

      if (__first == __middle || __last  == __middle)
        return;

      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
        _Distance;
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        _ValueType;

      const _Distance __n = __last   - __first;
      const _Distance __k = __middle - __first;
      const _Distance __l = __n - __k;

      if (__k == __l)
        {
          std::swap_ranges(__first, __middle, __middle);
          return;
        }

      const _Distance __d = std::__gcd(__n, __k);

      for (_Distance __i = 0; __i < __d; __i++)
        {
          _ValueType __tmp = _GLIBCXX_MOVE(*__first);
...

  template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    stable_partition(_ForwardIterator __first, _ForwardIterator __last,
                     _Predicate __pred)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
                                  _ForwardIterator>)
      __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
            typename iterator_traits<_ForwardIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
        return __first;
      else
        {
          typedef typename iterator_traits<_ForwardIterator>::value_type
            _ValueType;
          typedef typename iterator_traits<_ForwardIterator>::difference_type
            _DistanceType;

          _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
                                                                __last);
...

and many more...

-- Johannes


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[singler at gcc dot gnu dot org]

-- 

singler at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[pcarlini at suse dot de]

------- Comment #5 from pcarlini at suse dot de  2008-01-02 16:01 -------
I think Johannes' analysis is completely right. And, e.g., "STL Tutorial and
Reference Guide", 20.6, or "The C++ Programming Language", 19, evidently also
agrees with that reading of the standard.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490

[Bug libstdc++/33490] parallel v3: std::accumulate assumes iterators have std::iterator_traits declared

[singler at gcc dot gnu dot org]

------- Comment #6 from singler at gcc dot gnu dot org  2008-01-15 13:05 -------
No further objections.


-- 

singler at gcc dot gnu dot org changed:

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


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33490