libstdc++/86: map & set iterator comparisons are not type-safe

[bgarcia at laurelnetworks dot com]

>Number:         86
>Category:       libstdc++
>Synopsis:       map & set iterator comparisons are not type-safe
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Sep 07 04:27:00 PDT 2000
>Closed-Date:
>Last-Modified:
>Originator:     bgarcia@laurelnetworks.com
>Release:        2.90.8 & CVS
>Organization:
>Environment:
all
>Description:
There is a bug in bits/stl_tree.h that allows you to
compare two iterators (map or set iterators) of arbitrary
types.  An example program containing incorrect code that
compiles and runs is included in the How-To-Repeat section.

The problem is that operator==() and operator!=() are
defined to take _Rb_tree_base_iterator arguments.
The fix is to make these functions templates that take
_Rb_tree_iterator<> arguments instead.  This should not
result in any less efficiency, since in both cases these
functions are declared inline.


The appropriate diff for libstdc++-2.90.8 follows.
The CVS version of the file does not appear to have
changed significantly, so this should also be applicable
to the head-of-line code.

>How-To-Repeat:
And here's a little test program that exposes the bug:

#include <map>
#include <iostream>
#include <string>

int main(int argc, char** argv)
{
    std::map<unsigned, int> mapByIndex;
    std::map<std::string, unsigned> mapByName;

    (void)mapByIndex.insert(std::pair<unsigned, int>(0,1));
    (void)mapByIndex.insert(std::pair<unsigned, int>(6,5));

    unsigned i(0);

    std::map<unsigned, int>::iterator itr(mapByIndex.begin());

    while (itr != mapByName.end())  // XXX - notice, it's not mapByIndex!!
    {
	std::cout << "In loop, " << i << std::endl;
	std::cout.flush();
	++i;
	++itr;
    }

    return 0;
}
>Fix:
*** original/bits/stl_tree.h        Mon May  8 09:57:34 2000
--- new/bits/stl_tree.h             Fri Aug 25 08:02:47 2000
***************
*** 184,196 ****
    }
  };
  
! inline bool operator==(const _Rb_tree_base_iterator& __x,
!                        const _Rb_tree_base_iterator& __y) {
    return __x._M_node == __y._M_node;
  }
  
! inline bool operator!=(const _Rb_tree_base_iterator& __x,
!                        const _Rb_tree_base_iterator& __y) {
    return __x._M_node != __y._M_node;
  }
  
--- 184,198 ----
    }
  };
  
! template <class _Value, class _Ref, class _Ptr>
! inline bool operator==(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x,
!                        const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) {
    return __x._M_node == __y._M_node;
  }
  
! template <class _Value, class _Ref, class _Ptr>
! inline bool operator!=(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x,
!                        const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) {
    return __x._M_node != __y._M_node;
  }
>Release-Note:
>Audit-Trail:
>Unformatted: