[Bug c++/14039] New: bug in std::find

[Bug c++/14039] New: bug in std::find

[jsiek at osl dot iu dot edu]

The expression (*__first == __val) appears in the implementation
std::find. However, __first is only required to be an input iterator,
so *__first is required to be convertible to the value type
but not necessarily comparable with the value type. So
const value_type& x = *__first;
x == __value
would be a valid alternative.

The following program demonstrates the problem.


#include <algorithm>

namespace detail {
  class dummy_constructor { };
}

template <class T = int>
class null_archetype {
private:
  null_archetype() { }
  null_archetype(const null_archetype&) { }
  null_archetype& operator=(const null_archetype&) { return *this; }
public:
  null_archetype(detail::dummy_constructor) { }
  template <class TT>
  friend void dummy_friend(); // just to avoid warnings
};

class boolean_archetype {
public:
  boolean_archetype(const boolean_archetype&) { }
  operator bool() const { return true; }
  boolean_archetype(detail::dummy_constructor) { }
private:
  boolean_archetype() { }
  boolean_archetype& operator=(const boolean_archetype&) { return *this; }
};

template <class T>
class static_object
{
public:
    static T& get()
    {
        static char d[sizeof(T)];
        return *reinterpret_cast<T*>(d);
    }
};

template <class Base = null_archetype<> >
class equality_comparable2_first_archetype : public Base {
public:
  equality_comparable2_first_archetype(detail::dummy_constructor x) 
    : Base(x) { }
};
template <class Base = null_archetype<> >
class equality_comparable2_second_archetype : public Base {
public:
  equality_comparable2_second_archetype(detail::dummy_constructor x) 
    : Base(x) { }
};
template <class Base1, class Base2>
boolean_archetype
operator==(const equality_comparable2_first_archetype<Base1>&,
           const equality_comparable2_second_archetype<Base2>&) 
{
  return boolean_archetype(static_object<detail::dummy_constructor>::get());
}
template <class Base1, class Base2>
boolean_archetype
operator!=(const equality_comparable2_first_archetype<Base1>&,
           const equality_comparable2_second_archetype<Base2>&)
{
  return boolean_archetype(static_object<detail::dummy_constructor>::get());
}


template <class T, int I = 0>
class input_iterator_archetype
{
private:
  typedef input_iterator_archetype self;
public:
  typedef std::input_iterator_tag iterator_category;
  typedef T value_type;
  struct reference {
    operator const value_type&() const { return static_object<T>::get(); }
  };
  typedef const T* pointer;
  typedef std::ptrdiff_t difference_type;
  self& operator=(const self&) { return *this;  }
  bool operator==(const self&) const { return true; }
  bool operator!=(const self&) const { return true; }
  reference operator*() const { return reference(); }
  self& operator++() { return *this; }
  self operator++(int) { return *this; }
};


int main()
{
  typedef equality_comparable2_first_archetype<> Left;
  input_iterator_archetype< Left > in;
  detail::dummy_constructor dummy_cons;
  equality_comparable2_second_archetype<> value(dummy_cons);
  in = std::find(in, in, value);
}

-- 
           Summary: bug in std::find
           Product: gcc
           Version: 3.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jsiek at osl dot iu dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug c++/14039] bug in std::find

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-02-06 09:22 -------
Ok.

-- 
           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         |2004-02-06 09:22:01
               date|                            |


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

[Bug c++/14039] bug in std::find

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-02-06 09:57 -------
... but, isn't the standard a little misleading when, in 25.1.2, p2 talks about
*i == value? I think that the problem stems from the implementors (too) closely 
following 25.1.2, p2!

-- 


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

[Bug c++/14039] bug in std::find

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-02-06 10:06 -------
... also, consider DR 244 (NAD): the implementation discussed is identical to
ours, and nobody apparently objected to the correctness of *begin != x1 there...

I'm really unsure that we really want to "fix" this barring a clarification in
the standard.

-- 


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

[Bug libstdc++/14039] bug in std::find

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-02-06 14:23 -------
We consider our implementation conforming.

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


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