[Bug libstdc++/53339] New: unordered_map::iterator requires Value to be complete type

[Bug libstdc++/53339] New: unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

             Bug #: 53339
           Summary: unordered_map::iterator requires Value to be complete
                    type
    Classification: Unclassified
           Product: gcc
           Version: 4.6.3
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: eltoder@gmail.com


Created attachment 27393
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27393
Simple test case

Sometimes it's useful to refer to map's iterator from map's value, e.g.:

#include <string>
#include <tr1/unordered_map>

struct LinkedHashMap
{
    struct Entry;
    typedef std::tr1::unordered_map<std::string, Entry> Storage;
    typedef Storage::iterator EntryPtr; // <-- fails here
    struct Entry
    {
        EntryPtr prev, next;
    };

    Storage  storage_;
    EntryPtr head_;
};

(here we combine hash map with linked list implemented via iterators).
It doesn't seem unreasonable to expect this to compile, however it doesn't:

In file included from /usr/include/c++/4.6/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/4.6/bits/char_traits.h:41,
                 from /usr/include/c++/4.6/string:42,
                 from linkedhash.cc:1:
/usr/include/c++/4.6/bits/stl_pair.h: In instantiation of 'std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>':
/usr/include/c++/4.6/bits/stl_function.h:486:12:   instantiated from
'std::_Select1st<std::pair<const std::basic_string<char>, LinkedHashMap::Entry>
>'
/usr/include/c++/4.6/tr1/hashtable_policy.h:708:20:   instantiated from
'std::tr1::__detail::_Hash_code_base<std::basic_string<char>, std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>, std::_Select1st<std::pair<const
std::basic_string<char>, LinkedHashMap::Entry> >,
std::equal_to<std::basic_string<char> >, std::tr1::hash<std::basic_string<char>
>, std::tr1::__detail::_Mod_range_hashing,
std::tr1::__detail::_Default_ranged_hash, false>'
/usr/include/c++/4.6/tr1/hashtable.h:108:11:   instantiated from
'std::tr1::_Hashtable<std::basic_string<char>, std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>, std::allocator<std::pair<const
std::basic_string<char>, LinkedHashMap::Entry> >,
std::_Select1st<std::pair<const std::basic_string<char>, LinkedHashMap::Entry>
>, std::equal_to<std::basic_string<char> >,
std::tr1::hash<std::basic_string<char> >,
std::tr1::__detail::_Mod_range_hashing,
std::tr1::__detail::_Default_ranged_hash,
std::tr1::__detail::_Prime_rehash_policy, false, false, true>'
/usr/include/c++/4.6/tr1/unordered_map.h:43:11:   instantiated from
'std::tr1::__unordered_map<std::basic_string<char>, LinkedHashMap::Entry,
std::tr1::hash<std::basic_string<char> >, std::equal_to<std::basic_string<char>
>, std::allocator<std::pair<const std::basic_string<char>,
LinkedHashMap::Entry> >, false>'
/usr/include/c++/4.6/tr1/unordered_map.h:180:11:   instantiated from
'std::tr1::unordered_map<std::basic_string<char>, LinkedHashMap::Entry>'
linkedhash.cc:8:20:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:93:11: error: 'std::pair<_T1,
_T2>::second' has incomplete type
linkedhash.cc:6:12: error: forward declaration of 'struct LinkedHashMap::Entry'

The problem is that _Select1st<pair<Key,Value> > forces instantiation of pair
when trying to declare its return type:

template<typename _Pair>
struct _Select1st : public unary_function<_Pair,
                                          typename _Pair::first_type> // <--

but pair cannot be instantiated until both types are complete. This is can be
worked around by using unordered_set or using _Hashtable directly, but
* This code compiles if unordered_map is replaced by map. Would be nice to keep
them consistent.
* There doesn't seem to be any fundamental reason why this doesn't work -- it
comes from a minor implementation choice and seems very easy to fix.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #1 from Eugene Toder <eltoder at gmail dot com> 2012-05-13 22:22:54 UTC ---
Created attachment 27394
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27394
Quick and dirty proof-of-concept patch

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|minor                       |enhancement

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bkoz at redhat dot com

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-14 02:24:14 UTC ---
But things seem not so easy in mainline (this is an enhancement which can go
only in mainline): in any case we fail at the line:

  using mapped_type = typename _Pair::second_type;

in hashtable_policy.h, because, afaics, with the code reworked to use alias
templates we end up instantiating everything down to __detail::_Map_base.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #3 from Eugene Toder <eltoder at gmail dot com> 2012-05-14 02:40:03 UTC ---
Can you point me to where libstdc++ mainline lives these days? trunk and a
couple other branches I've checked don't have that line in hashtable_policy.h

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #4 from Eugene Toder <eltoder at gmail dot com> 2012-05-14 04:41:19 UTC ---
Created attachment 27395
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27395
POC for mainline

Never mind, I was looking in tr1 instead of bits.

Yes, it's a bit more tricky in mainline, because hashtable_policy.h now makes
assumptions that _ExtractKey is always _Select1st. Is there a good reason for
that? At least it feels strange to allow specifying arbitrary _ExtractKey if
only _Select1st will actually compile.

Anyway, a very minimal quick and dirty patch attached.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #5 from Eugene Toder <eltoder at gmail dot com> 2012-05-14 05:05:58 UTC ---
Created attachment 27396
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27396
Another approach

Actually, a much simpler and cleaner change might be along these lines.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-14 10:52:28 UTC ---
Can we avoid deriving from unary_function and binary_function, no big deal as
an implementation detail, but are deprecated in C++11, I would rather *remove*
uses. Also, did you run the testsuite? Because normally we want the operators
to be templates because of some move semantics details.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-14 10:59:15 UTC ---
I really do believe that we want to leave the stuff in stl_function.h alone and
have something very neat in namespace __detail, in hashtable_policy.h, probably
a single overloaded templated operator taking a && would be enough.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-14 13:12:38 UTC ---
Created attachment 27402
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27402
Draft

Something like this, very lightly tested so far.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jwakely.gcc at gmail dot
                   |                            |com

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-14 13:13:54 UTC ---
Jon, can we simplify __detail::_Identity and __detail::_Select1st?

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #27402|0                           |1
        is obsolete|                            |

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-15 01:04:30 UTC ---
Created attachment 27406
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27406
Draft 2

This is my current best, uses std::get and std::tuple_element. Passes testing.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #11 from Eugene Toder <eltoder at gmail dot com> 2012-05-15 02:03:34 UTC ---
Created attachment 27407
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27407
Another simple test case

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

Eugene Toder <eltoder at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #27395|0                           |1
        is obsolete|                            |

--- Comment #12 from Eugene Toder <eltoder at gmail dot com> 2012-05-15 04:05:22 UTC ---
Created attachment 27408
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27408
Remove _Select1st hard-coding

This works for me. Although it's a bit annoying that _Select1st is hard coded
in quite a few places. What do you think of this change (on top of your latest
patch) to rely on std::pair instead of __detail::_Select1st in template
specialization? It seems it's closer to what the comment says:

   *  If the hashtable has a value type of the form pair<T1, T2> and a
   *  key extraction policy (_ExtractKey) that returns the first part
   *  of the pair, the hashtable gets a mapped_type typedef.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-05-15
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com
   Target Milestone|---                         |4.8.0
     Ever Confirmed|0                           |1

--- Comment #13 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-15 09:25:47 UTC ---
May be a good idea. But at this point I think you want to send further
improvements beyond the PR proper to the mailing list for large exposure. And
of course beyond a few lines, if you are interested in contributing (which
would be great!) you should do the Copyright assignment paperwork, I have to
tell you.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo at gcc dot gnu.org]

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

--- Comment #14 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2012-05-15 10:00:28 UTC ---
Author: paolo
Date: Tue May 15 10:00:19 2012
New Revision: 187515

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187515
Log:
2012-05-15  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/53339
    * include/bits/hashtable_policy.h (__detail::_Identity,
    __detail::_Select1st): Add.
    (_Map_base, _Hashtable_base): Use the latter, adjust parameters.
    * include/bits/hashtable.h (_Hashtable::__key_extract): Adjust.
    * include/bits/unordered_set.h (__uset_hashtable, __umset_hashtable):
    Likewise.
    * include/bits/unordered_map.h (__umap_hashtable, __ummap_hashtable):
    Likewise.
    * include/bits/stl_function.h (_Identity, _Select1st, _Select2nd)
    Unconditionally derive from unary_function.
    * include/ext/functional (identity, select1st, select2nd): Remove
    #ifdef __GXX_EXPERIMENTAL_CXX0X__ bits.
    * testsuite/23_containers/unordered_map/requirements/53339.cc: New.
    * testsuite/23_containers/unordered_multimap/requirements/
    53339.cc: Likewise.

Added:
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53339.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/53339.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable.h
    trunk/libstdc++-v3/include/bits/hashtable_policy.h
    trunk/libstdc++-v3/include/bits/stl_function.h
    trunk/libstdc++-v3/include/bits/unordered_map.h
    trunk/libstdc++-v3/include/bits/unordered_set.h
    trunk/libstdc++-v3/include/ext/functional
    trunk/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

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

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

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-15 10:06:24 UTC ---
Fixed for 4.8.0.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #16 from Eugene Toder <eltoder at gmail dot com> 2012-05-15 12:30:55 UTC ---
Makes sense. I was hoping to avoid copyright assignment by having someone else
do the work :) Thank you.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

--- Comment #17 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-15 13:11:55 UTC ---
Still, if you mean to contribute, something else maybe, just let use (me) know:
it's just matter of filling a form and waiting a bit. You do it once and then
you are set forever.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[redi at gcc dot gnu.org]

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

--- Comment #18 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-05-16 02:12:31 UTC ---
(In reply to comment #16)
> I was hoping to avoid copyright assignment by having someone else
> do the work :) 

That's OK, but in that case I think (and this is just IMHO) it's better if you
don't post a series of patches.

Ideally we'd like you to sign a copyright assignment and contribute, but if you
won't or can't contribute your code then IMHO you shouldn't offer it in the
form of patches, because if we can't accept it then even reviewing your patch
might make it tricky for us to implement the suggestion in a similar way (did
we use your code? copy your idea? do we need to get a lawyer to decide if a
change we make is based on your non-assigned work? ... I don't want to have to
even ask those questions, let alone answer them!)

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[eltoder at gmail dot com]

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

--- Comment #19 from Eugene Toder <eltoder at gmail dot com> 2012-05-16 02:21:07 UTC ---
Fair point, noted. I believe ideas are not copyrightable, though.

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[redi at gcc dot gnu.org]

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

--- Comment #20 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-05-16 02:52:26 UTC ---
So please feel free to share ideas.  A patch is not an idea though, it's an
implementation. In any case last time I checked the law is not based just on
what you believe ;)
Please don't take my comment the wrong way, I'm grateful for your report and
help fixing it (and I'm sure others are too) but if you don't want to do the
work (which is fine) then don't do it, share the results, then say you won't do
the (admittedly complicated) paperwork needed to make that work usable - it's
easier all round just to suggest an idea not provide an unusable
implementation.

If you do want to complete the copyright assignment paperwork then the
situation wouldn't arise anyway :)

[Bug libstdc++/53339] unordered_map::iterator requires Value to be complete type

[paolo.carlini at oracle dot com]

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

--- Comment #21 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-16 09:11:06 UTC ---
Jon, I totally agree with everything you found the time to explain, thanks! In
my opinion should even be a FAQ or something!