[Bug c++/23767] New: std::vector iterator implementation wrong

[Bug c++/23767] New: std::vector iterator implementation wrong

[afra at cs dot stanford dot edu]

The following code does not compile.  According to the compiler, 
't' is overloaded ambiguously.

#include <vector>

struct T {
  typedef std::vector<int> Vector;
  typedef Vector::iterator iterator;
  typedef Vector::const_iterator const_iterator;

  int t( iterator f)             { return *f; }
  int t( const_iterator f) const { return *f; }
};

int main(int, char*[])
{
  std::vector<int> v;
  T t;
  T::const_iterator i = v.begin();

  t.t(i);

  return 0;

}

We've seen this on gcc 3.2.2., 3.4.3, 4.0.1.  Basically, the
const_iterator matches both the iterator and the const_iterator at function
resolution time.  This seems to stem from the implementation of iterator in
std::vector using __normal_iterator.  There is a template copy constructor that
appears to allow this illegal conversion.

Error on:  gcc version 4.0.1 20050727 (Red Hat 4.0.1-5)
----------
test.cc: In function int main(int, char**):
test.cc:18: error: ISO C++ says that these are ambiguous, even though
the
worst conversion for the first is better than the worst conversion for
the
second:
test.cc:10: note: candidate 1: int
T::t(__gnu_cxx::__normal_iterator<const
int*, std::vector<int, std::allocator<int> > >) const
test.cc:9: note: candidate 2: int
T::t(__gnu_cxx::__normal_iterator<int*,
std::vector<int, std::allocator<int> > >)

-- 
           Summary: std::vector iterator implementation wrong
           Product: gcc
           Version: 4.0.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: afra at cs dot stanford dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug c++/23767] std::vector iterator implementation wrong

[afra at cs dot stanford dot edu]

------- Additional Comments From afra at cs dot stanford dot edu  2005-09-07 17:04 -------
Created an attachment (id=9688)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9688&action=view)
complete program showing bug


-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[afra at cs dot stanford dot edu]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |libstdc++


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |3.0.4 3.3.3 3.4.0 4.0.0
      Known to work|                            |2.95.3


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-07 19:22 -------
Hmm.. this is I believe a bug, but a very hard one to trigger.

1) This bug is very sensitive. It only occurs if the const_iterator member function is const and the 
iterator member function isn't. It doesn't appear for a pair of normal functions.

2) Just to point it out, if you try only allowing the first function t(iterator f), then the code won't compile, 
as it tries and fails to instansiated the templated constructor.

The "obvious" way to fix this would be to change the templated constructor so that it only took the 
const version of the iterator. Unfortunatly I don't believe thats possible without passing extra 
information by more template parameters, which would break binary compatability.

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 19:33 -------
(In reply to comment #2)
>               Unfortunatly I don't believe thats possible without passing
> extra information by more template parameters, which would break binary
> compatability.

I'm not going to discuss now the substance of this issue (hopefully soon!)
but I don't think the binary compatibility thing is obviously true. When
two different object modules are built, each one can use the appropriate
constructor, and there are no risks of mixups when (possible) weak symbols
are merged because the signatures would be different in this case (a very
nasty issue instead is when you change *only* the return type of a function,
in that case, as Geoff kindly reminded us, there are risks because the sig
is the same!)

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 19:37 -------
(In reply to comment #3)
> Unfortunatly I don't believe thats possible without passing extra 
> information by more template parameters, which would break binary compatability.

In short, in my preliminary opinion, we can well envisage this assuming anything
we do actually changes the signature of the constructor.



-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pcarlini at suse dot de


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-07 20:06 -------
You are right, I previously didn't think it was possible without adding some more template parameters. 
However, I should have known there is nothing you can't do with a few templates :)

How about something like:

template<typename _Iter>
        inline __normal_iterator(const __normal_iterator<_Iter,
				 _Container>& __i,
				 typename std::__enable_if<int,
				 std::tr1::is_convertible<_Iter, _Iterator>::value>::__type  = 0)
	: _M_current(__i.base()) { }

Which shouldn't effect any existing code, as unless _Iter is convertable to _Iterator, _M_current(__i.base
()) isn't going to compile. I'm adding
#include<cpp_type_traits.h>
#include<tr1/type_traits>
to do this, and of course I imagine we'll have to cut is_convertable out of type_traits...

I haven't done a full test of this yet, but it seems reasonable at first glance.

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 20:14 -------
(In reply to comment #5)
> How about something like:

Yes, in my mind earlier today I considered that solution. In principle should
work. However, there are issues, I'm afraid: optimization issues with the
extra dummy parameter (right?) and, well, maybe we can figure out something
cleaner (in particular, I'm under the impression that, as a policy, we do our
best to minimize the enable_if-isms) 

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2005-09-07 20:19 -------
If you add a third argument to the constructor, don't you somehow have to 
add the old constructor with its two-argument signature to the library to 
allow old programs to link against the new library? 
 
How would you do that in this case? 
 
W. 

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 20:26 -------
(In reply to comment #7)
> If you add a third argument to the constructor, don't you somehow have to 
> add the old constructor with its two-argument signature to the library to 
> allow old programs to link against the new library? 

Why? As far as I can see there are *no* instantiations of the iterator 
class inside the library proper (*.so or *.a). 

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-07 20:39 -------
Actually, __normal_iterator is what std::string uses for it's iterator class, so
we could be in trouble.



On the note of removing enable_if, my only other thought is something like:

template<class _Iterator, typename _Container, bool __is_const>

then change the problem constructor to:

template<typename _Iter>
  inline __normal_iterator(const __normal_iterator<_Iter, _Container, true>&..)

and add 
That worries me more than the enable_if however...

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 20:45 -------
(In reply to comment #9)
> Actually, __normal_iterator is what std::string uses for it's iterator class,
> so we could be in trouble.

As long as no user code expects instantiations of members of __normal_iterator
inside the library proper to link against I don't think there are any risks (At
least, this is my present understanding of these torny matters)

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-07 20:51 -------
I just tried adding a template parameter, and it does break things unfortunatly.
In an "old" file define something like:

void f(vector<int>::iterator v) {..}

and then try to call it from a file that includes the new definition, and they
won't link together.

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2005-09-07 20:55 -------
What I had meant was liba.so containing an explicit specialization of  
std::vector<int> and libb.so using it while being compiled with  
-fno-implicit-instantiations (or whatever the correct name for that 
flag was). If you only re-compile libb.so, this won't work any more. 
Likewise the other way round. If, however, std/vector.h contained both 
the old and the new signature, the latter case would still work. 
 
This sounds like a pretty academic case, though (but hey, that's the kind 
of work I'm paid for :-), so I don't think it's worth bothering about... 
 
W. 

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 20:58 -------
(In reply to comment #11)
> I just tried adding a template parameter,
You mean, to the __normal_iterator class itself? That does not work, of course.


-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 21:04 -------
(In reply to comment #12)
> What I had meant was liba.so containing an explicit specialization of  
> std::vector<int> and libb.so using it while being compiled with  
> -fno-implicit-instantiations (or whatever the correct name for that 
> flag was). If you only re-compile libb.so, this won't work any more. 
> Likewise the other way round. If, however, std/vector.h contained both 
> the old and the new signature, the latter case would still work.

Thanks for the explanation, I'm still trying to digest it fully ;)
 
> This sounds like a pretty academic case, though (but hey, that's the kind 
> of work I'm paid for :-), so I don't think it's worth bothering about... 

Well, at some point we have to make a tradeoff, between fixing bugs and
providing every possible sort of compatibility guarantee. Maybe we can delay
as much as possible the choice, maybe this PR will be a turning point.

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-07 21:07 -------
Actually for inline functions, even with -fno-implicit-templates, instansiations are still generated (I can 
kind of see why. You could argue they shouldn't be, but they are)

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2005-09-07 21:27 -------
I guess then there is no danger involved. 
 
BTW, I'm not one of the corporate folks, so I have few problems with 
breaking ABI compatibility :-) I was just too fast raising a point that 
in the end didn't turn out to be very interesting... 
 
W. 

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-07 21:36 -------
(In reply to comment #16)
> I guess then there is no danger involved.

Yeah! ;)
 
> BTW, I'm not one of the corporate folks, so I have few problems with 
> breaking ABI compatibility :-) I was just too fast raising a point that 
> in the end didn't turn out to be very interesting... 

Very interesting, in fact. You know what, Wolfgang? Sooner or later we should
write a FAQ/guidelines/whatever about those topics. Personally, I learned a lot
of it by trial and error, without a clear guide, and whereas there are some
good docs around about C, a lot less is available for the C++-specific issues.
In my opinion would be very useful!

-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2005-09-07 22:40 -------
Yea, but I guess I'll leave this to you guys, that sounds too complicated 
for me. I'll just stick my head out every once in a while and try to find 
a loophope in your reasoning and to invent ways to show that a proposed 
change is, in fact, not ABI compatible :-) Like, I guess, it should be 
possible to find some way around if the proposed addition of a new 
parameter was for a regular function (for which one can take the address), 
rather than a constructor... 
 
In the meantime, I go back to solving partial differential equations -- that's 
simpler. 
 
W. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bangerth at dealii dot org


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[fang at csl dot cornell dot edu]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fang at csl dot cornell dot
                   |                            |edu


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-09-11 14:32:44
               date|                            |


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-09-12 09:44 -------
Subject: Bug 23767

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	paolo@gcc.gnu.org	2005-09-12 09:42:36

Modified files:
	libstdc++-v3   : ChangeLog 
	libstdc++-v3/include/bits: stl_iterator.h 
Added files:
	libstdc++-v3/testsuite/23_containers/vector/types: 23767.cc 
	libstdc++-v3/testsuite/21_strings/basic_string/types: 23767.cc 
	libstdc++-v3/testsuite/ext/vstring/types: 23767.cc 

Log message:
	2005-09-12  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/23767
	* include/bits/stl_iterator.h (__normal_iterator::
	__normal_iterator<>(const __normal_iterator<_Iter, _Container>&)):
	Enable only when _Iter is equal to _Container::pointer.
	* testsuite/21_strings/basic_string/types/23767.cc: New.
	* testsuite/23_containers/vector/types/23767.cc: Likewise.
	* testsuite/ext/vstring/types/23767.cc: Likewise.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.3096&r2=1.3097
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/bits/stl_iterator.h.diff?cvsroot=gcc&r1=1.28&r2=1.29
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/23_containers/vector/types/23767.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/21_strings/basic_string/types/23767.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/ext/vstring/types/23767.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-12 09:45 -------
Fixed for 4.1.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

[Bug libstdc++/23767] std::vector iterator implementation wrong

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-09-12 09:46 -------
Fixed for 4.1.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.0


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