[Bug libstdc++/56112] New: [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[Bug libstdc++/56112] New: [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[redi at gcc dot gnu.org]

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

             Bug #: 56112
           Summary: [4.8 Regression] cannot create unordered_map from
                    range of types convertible to value_type
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: rejects-valid
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: redi@gcc.gnu.org


#include <unordered_map>

struct S
{
    operator std::pair<const int, int>() const { return {}; }
};

int main()
{
    S s[1];
    std::unordered_map<int, int> m(s, s+1);   // error

    std::pair<const int, int> p = *s;  // OK
    m.insert(s, s+1);  // OK
}


This is valid (value_type is EmplaceConstructible into the container from s[0])
but it fails to compile because of the change to use std::__detail::_Select1st
instead of std::_Select1st<value_type>

The template argument for _Select1st::operator() cannot be deduced from the
object of type S. The problem boils down to this:

#include <utility>

struct S
{
    operator std::pair<const int, int>() const { return {}; }
};

void f()
{
    S s;
    std::get<0>(s);
}

This is not valid, but the range constructors of unordered_map and
unordered_multimap assume using std::get<0> on the iterator's value type will
work, which is not a valid assumption.

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.0

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 07:15:39 UTC ---
Bother. Now it's annoying to go back to the various options (some aren't even
discussed in Bugzilla entries). Maybe you did a bit of that already as part of
filing the PR and have a specific solution in mind? Should we go back to
something like Comment #5 in PR53339? But I don't like so much the idea of
adding stuff to stl_function.h

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 07:32:59 UTC ---
I guess we could have in __detail the specialization that submitter proposed to
add to stl_function.h as primary.

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 08:12:41 UTC ---
Or what about something like the attached (very lightly tested)?

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 08:13:43 UTC ---
Created attachment 29284
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29284
draft

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 08:35:37 UTC ---
Uhhmm, I wasn't considering the fact that the testcases added for 53339 are now
xfailed?!? So what? If that's the case (for now at least) we could as well
revert the core of the 53339 changes, that is go back to the 4.7 situation and
just use std::_Select1st<value_type>?!?

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-27 16:25:36 UTC ---
(In reply to comment #5)
> Uhhmm, I wasn't considering the fact that the testcases added for 53339 are now
> xfailed?!?

That was me: http://gcc.gnu.org/ml/libstdc++/2013-01/msg00035.html


> So what? If that's the case (for now at least) we could as well
> revert the core of the 53339 changes, that is go back to the 4.7 situation and
> just use std::_Select1st<value_type>?!?

Yes, I suppose we could, but we'd need to revert the changes to stl_function.h
so that it doesn't derive from unary_function in C++11 mode.  I think having a
simple __detail::_Select1st<_Pair> that just does what the hash tables need is
cleaner, and it can be made simpler than your patch because it doesn't need to
use perfect forwarding:

  template<typename _Pair>
    struct _Select1st
    {
      auto
      operator()(const _Pair& __x) const
      -> decltype(std::get<0>(__x))
      { return std::get<0>(__x); }
    };

Or we could simplify it even further

      const typename _Pair::first_type&
      operator()(const _Pair& __x) const
      { return __x.first); }

This would prevent fancy custom uses of _Hashtable, for example
_Hashtable<int, std::tuple<int, int, int>, ...>, but I don't think we need or
want to do that anyway.

My testcase for this bug reveals another problem in an area we've had recurring
problems:

      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
         _H1, _H2, _Hash, _RehashPolicy, _Traits>::
      _M_insert(_Arg&& __v, std::true_type)
      {
    const key_type& __k = this->_M_extract()(__v);
    __hash_code __code = this->_M_hash_code(__k);
    size_type __bkt = _M_bucket_index(__k, __code);

    __node_type* __n = _M_find_node(__bkt, __k, __code);

With my testcase __k is a dangling reference, because the call to _M_extract
creates a temporary, __k binds to a member of that temporary, then the
temporary goes out of scope.

Valgrind will show errors for this modified testcase which allocates memory in
the temporary:

#include <unordered_map>
#include <string>

struct S
{
    operator std::pair<const std::string, int>() const { return {"a", 0}; }
};

int main()
{
    S s[1];
    std::unordered_map<std::string, int> m(s, s+1);   // error
}


To fix this we need to extract the key and set __code, __bkt and __n in a
single statement before the temporary goes out of scope, e.g. using a lambda
just for a proof of concept:

    __hash_code __code;
    size_type __bkt;
    __node_type* __n;
    auto __find_node = [&](const key_type& __k) {
      __code = this->_M_hash_code(__k);
      __bkt = _M_bucket_index(__k, __code);
      __n = _M_find_node(__bkt, __k, __code);
    };
    __find_node(this->_M_extract()(value_type(__v)));

So I think we want something like your comment 4 attachment, with a simpler
_Select1st, and fixing the memory bug.  I'm testing that now ...

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-27 17:18:03 UTC ---
Good, good, thanks for handling this.

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-28 23:07:59 UTC ---
Author: redi
Date: Mon Jan 28 23:07:35 2013
New Revision: 195520

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195520
Log:
    PR libstdc++/56112
    * include/bits/hashtable_policy.h (insert(_Pair&&)): Use _M_emplace
    to construct value_type explicitly before trying to extract the key.
    * testsuite/23_containers/unordered_map/cons/56112.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable_policy.h

[Bug libstdc++/56112] [4.8 Regression] cannot create unordered_map from range of types convertible to value_type

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

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

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-28 23:09:06 UTC ---
fixed