[Bug libstdc++/51866] New: [c++0x][4.7 Regression] unordered_set compares moved-out values

[Bug libstdc++/51866] New: [c++0x][4.7 Regression] unordered_set compares moved-out values

[roman at binarylife dot net]

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

             Bug #: 51866
           Summary: [c++0x][4.7 Regression] unordered_set compares
                    moved-out values
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: roman@binarylife.net


$ cat test.cpp 
#include <unordered_set>
#include <iostream>
#include <cstdlib>

struct num {
  int value;
  num(int n)                 : value(n) {}
  num(num const&)            = default;
  num& operator=(num const&) = default;
  num(num&& o)               : value(o.value) { o.value=-1; }
  num& operator=(num&& o)    { if (this!=&o) { value=o.value; o.value=-1; }
return *this; }
};

struct num_hash {
  size_t operator()(num const& a)const {
    if (a.value<0) std::cout<<"hash of moved value"<<std::endl;
    return 0;
  }
};

struct num_equal {
  bool operator()(num const& a,num const& b)const {
    if (a.value<0 || b.value<0) {
      std::cout<<"compare of moved value: a="<<a.value<<",
b="<<b.value<<std::endl;
      return false;
    }
    return a.value==b.value;
  }
};

int main() {
  std::unordered_multiset<num,num_hash,num_equal> mset;
  mset.insert(num(1));
  mset.insert(num(2));
  mset.insert(num(1));
  mset.insert(num(2));
  if (mset.size()!=4) abort();
  auto iter=mset.cbegin();
  int x0=(iter++)->value;
  int x1=(iter++)->value;
  int x2=(iter++)->value;
  int x3=(iter++)->value;
  if ((x0==1 && x1==1 && x2==2 && x3==2) ||
      (x0==2 && x1==2 && x2==1 && x3==1)) return 0;
  std::cout<<x0<<' '<<x1<<' '<<x2<<' '<<x3<<std::endl;
  abort();
}

$ g++ -std=c++0x test.cpp && ./a.out 
compare of moved value: a=-1, b=1
compare of moved value: a=-1, b=2
compare of moved value: a=-1, b=1
compare of moved value: a=-1, b=1
compare of moved value: a=-1, b=2
compare of moved value: a=-1, b=1
2 1 2 1
Aborted

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_set compares moved-out values

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-01-16 01:39:55 UTC ---
Please provide details about the specific Rev, thanks.

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[roman at binarylife dot net]

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

--- Comment #2 from Roman Kononov <roman at binarylife dot net> 2012-01-16 01:50:37 UTC ---
it is been bisected...
r183180 is bad
r170936 is good

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[paolo.carlini at oracle dot com]

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

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-01-16 01:52:47 UTC ---
If we are lucky, this issue is even the same as 51845. Thanks for the neat
testcase.

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-01-16
                 CC|fdumont at gcc dot gnu.org  |
         AssignedTo|unassigned at gcc dot       |fdumont at gcc dot gnu.org
                   |gnu.org                     |
   Target Milestone|---                         |4.7.0
     Ever Confirmed|0                           |1

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-16 12:33:35 UTC ---
in _Hashtable::_M_insert(Arg&&, false_type):

    const key_type& __k = this->_M_extract()(__v);

that takes a reference to the key part of the value, then:

        __new_node = _M_allocate_node(std::forward<_Arg>(__v));

that invalidates the value, while __k stills refers to the moved-from object.

then:

        size_type __n = _M_bucket_index(__k, __code);
        _BaseNode* __prev = _M_find_before_node(__n, __k, __code);

that uses the invalid key

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-16 12:38:56 UTC ---
the fix is to move the declaration of __k later, initializing it from the value
in the new node, where it's been moved to:

   this->_M_extract()(__new_node->_M_v)

computing the hash code above can be done from 

   this->_M_hash_code(this->_M_extract()(__v))

instead of this->_M_hash_code(__k)

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-16 12:41:04 UTC ---
P.S. it looks as though the python pretty printers need to be updated to
support the new hashtable code

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[fdumont at gcc dot gnu.org]

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

--- Comment #7 from François Dumont <fdumont at gcc dot gnu.org> 2012-01-18 20:18:20 UTC ---
Author: fdumont
Date: Wed Jan 18 20:17:57 2012
New Revision: 183285

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=183285
Log:
2012-01-18  François Dumont  <fdumont@gcc.gnu.org>
        Roman Kononov  <roman@binarylife.net>

    PR libstdc++/51866
    * include/bits/hashtable.h (_Hashtable<>::_M_insert(_Arg, false_type)):
    Do not keep a reference to a potentially moved instance.
    * testsuite/23_containers/unordered_multiset/insert/51866.cc: New.
    * testsuite/23_containers/unordered_multimap/insert/51866.cc: New.

Added:
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/51866.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/51866.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable.h

[Bug libstdc++/51866] [c++0x][4.7 Regression] unordered_multiset compares moved-out values

[fdumont at gcc dot gnu.org]

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

François Dumont <fdumont at gcc dot gnu.org> changed:

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

--- Comment #8 from François Dumont <fdumont at gcc dot gnu.org> 2012-01-18 20:36:47 UTC ---
This issue is solved now.

Thanks for the great test case.