Inconsistencies with associative/unordered containers

[François Dumont]

Hi

     Here is the patch to fix the 2nd point of this mail below.

     I prefer to qualify _Rb_tree_impl move constructor based on 
std::is_nothrow_move_constructible<_Base_key_compare> so that the logic 
of copying _Compare rather than moving it stays an implementation detail 
of _Rb_tree_key_compare.

     libstdc++: Fix [multi]map/[multi]set move constructors noexcept 
qualification

     Container move constructors shall not consider their allocator move
     constructor qualification.

     libstdc++-v3/ChangeLog:

             * include/bits/stl_tree.h (_Rb_tree_impl(_Rb_tree_impl&&)): 
Add noexcept
             qualification based only on _Compare one.
             * 
testsuite/23_containers/map/cons/noexcept_move_construct.cc: Add
             static asserts.
             * 
testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
             Likewise.
             * 
testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
             Likewise.
             * 
testsuite/23_containers/set/cons/noexcept_move_construct.cc: Likewise.

New tests run under Linux x86_64, ok to commit after other tests complete ?

François

On 01/07/20 10:50 pm, Jonathan Wakely wrote:
> On 01/07/20 22:20 +0200, François Dumont wrote:
>> On 01/07/20 9:20 pm, Jonathan Wakely wrote:
>>> On 01/07/20 19:10 +0300, Никита Байков wrote:
>>>> Hello,
>>>>
>>>> I'm trying to make sense of associative and unordered containers' 
>>>> behavior. Some of the implementation details seem a little 
>>>> inconsistent to me. Could you please take a look?
>>>>
>>>> Most of my questions concern move constructors and assignments, and 
>>>> their noexcept specifications. To be more specific, let me list 
>>>> some examples.
>>>>
>>>> 1. Move constructor for unordered_set is explicitly defaulted on 
>>>> its first declaration:
>>>>
>>>>    /// Move constructor.
>>>>    unordered_set(unordered_set&&) = default;
>>>>
>>>> Since unordered_set has no base classes and has just one data 
>>>> member of type _Hashtable, its noexcept specification would be 
>>>> derived from the following:
>>>>
>>>>   template<typename _Key, typename _Value,
>>>>        typename _Alloc, typename _ExtractKey, typename _Equal,
>>>>        typename _H1, typename _H2, typename _Hash, typename 
>>>> _RehashPolicy,
>>>>        typename _Traits>
>>>>     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
>>>>            _H1, _H2, _Hash, _RehashPolicy, _Traits>::
>>>>     _Hashtable(_Hashtable&& __ht) noexcept
>>>>     : __hashtable_base(__ht),
>>>>    /* ... the of the initializer list and the constructor body */
>>>>
>>>> This move constructor is marked noexcept unconditionally despite 
>>>> the fact it has to copy hash function _H1 and function _Equal that 
>>>> compares the keys.
>>>
>>> Looks like a bug. It was introduced by
>>> https://gcc.gnu.org/g:0462b6aa20fd6734f7497f5eed9496d33701a952
>>>
>>> This program exited normally with GCC 4.8 and terminates since 4.9.0:
>>>
>>> #include <unordered_set>
>>>
>>> bool boom = false;
>>>
>>> struct Eq : std::equal_to<int>
>>> {
>>>   Eq() { }
>>>   Eq(const Eq&) { if (boom) throw 1; }
>>> };
>>>   int main()
>>> {
>>>   std::unordered_set<int, std::hash<int>, Eq> s;
>>>   try {
>>>     boom = true;
>>>     auto s2 = std::move(s);
>>>   } catch (int) {
>>>   }
>>> }
>>>
>> I had notice this one and submitted a patch as part of a series:
>>
>> https://gcc.gnu.org/pipermail/libstdc++/2019-November/049597.html
>>
>> I would prefer to commit in the submitted order but if you wish I can 
>> reorder those.
>
> I'll try to review the series tomorrow. Thanks for the reminder.
>
>>>
>>>> At the same time, its move assignment operator is also explicitly 
>>>> defaulted:
>>>>
>>>>    /// Move assignment operator
>>>>    unordered_set&
>>>>    operator=(unordered_set&&) = default;
>>>>
>>>> and therefore is conditionally noexcept, since the corresponding 
>>>> _Hashtable::operator= is declared as
>>>>
>>>> _Hashtable&
>>>>       operator=(_Hashtable&& __ht)
>>>> noexcept(__node_alloc_traits::_S_nothrow_move()
>>>>            && is_nothrow_move_assignable<_H1>::value
>>>>            && is_nothrow_move_assignable<_Equal>::value);
>>>>
>>>> So, the first question is why the copy assignment of _H1 and _Equal 
>>>> is considered to never throw, while the move assignment is not. As 
>>>> a side
>>>
>>> Looks like a bug.
>>>
>>>> question, why does the move constructor choose to copy _H1 and 
>>>> _Equal instead of moving them?
>>>
>>> Howard Hinnant asked me about that recently, because we do the same
>>> for maps and sets as well as for unordered maps and sets.
>>>
>>> It's probably wrong, but I don't really want to change it until
>>> https://cplusplus.github.io/LWG/issue2227 is resolved.
>>>
>>>> 2. Let's assume that there is nothing wrong with noexcept 
>>>> specifications in unordered containers, i.e., all constructors and 
>>>> assignment operators are marked noexcept as they ought to be. Why 
>>>> then are the associative containers not implemented the same way? 
>>>> As far as I can see in bits/stl_set.h and bits/stl_tree.h,
>>>>
>>>>    //  Move constructor
>>>>    set(set&&) = default;
>>>>
>>>>    // The only data member of set is _Rb_tree object, whose move 
>>>> constructor is explicitly defaulted
>>>>    _Rb_tree(_Rb_tree&&) = default;
>>>>
>>>>    // The only data member of _Rb_tree is _Rb_tree_impl<_Compare> 
>>>> object that is defined as
>>>>    template<typename _Key_compare,
>>>>          bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
>>>>       struct _Rb_tree_impl
>>>>       : public _Node_allocator
>>>>       , public _Rb_tree_key_compare<_Key_compare>
>>>>       , public _Rb_tree_header
>>>>      {
>>>>       _Rb_tree_impl() = default;
>>>>       _Rb_tree_impl(_Rb_tree_impl&&) = default;
>>>>
>>>>      /* the rest of the definition */
>>>>      };
>>>>
>>>>    // Finally, _Rb_tree_key_compare move constructor is defined as
>>>>    _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
>>>> noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
>>>>       : _M_key_compare(__x._M_key_compare)
>>>>       { }
>>>>
>>>> What is the difference between _Compare (for associative 
>>>> containers) and _Equal (for unordered containers) in regard to 
>>>> noexcept? Why we
>>>
>>> One is correct and the other isn't.
>>>
>>>> have to check is_nothrow_copy_constructible value in the case of 
>>>> _Compare but can ignore it in the case of _Equal?
>>>>
>>>>
>>>> 3. The move constructor declaration and the allocator-extended move 
>>>> constructor declaration for std::set result into different noexcept 
>>>> specifications. Isn't that a small defect of the class interface?
>>>>
>>>>    /// Allocator-extended move constructor.
>>>>    set(set&& __x, const allocator_type& __a)
>>>> noexcept(is_nothrow_copy_constructible<_Compare>::value
>>>>         && _Alloc_traits::_S_always_equal())
>>>>    : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
>>>>
>>>>    /// Move constructor
>>>>    set(set&&) = default;
>>>>
>>>> Given the declarations above, I reckon that noexcept specification 
>>>> of the explicitly defaulted constructor can be rewritten as
>>>>
>>>>    is_nothrow_copy_constructible<_Compare>::value && 
>>>> is_nothrow_move_constructible</*type of the rebinded 
>>>> allocator*/>::value
>>>
>>> Allocators aren't allowed to throw when copied or moved, so the
>>> is_nothrow_move_constructible check is not needed. The fact it's
>>> implied by the defaulted constructor does seem like a bug.
>>>
>>>> Let's say someone defined a custom empty allocator type but didn't 
>>>> mark its move constructor as noexcept (besides the fact that move 
>>>> constructors shall never throw). noexcept conditions evaluation 
>>>> yields different results.
>>>
>>> They should fix their allocator. Explicitly providing a move
>>> constructor for an allocator is silly anyway. Don't do that. If you
>>> insist on it, get the exception specification right.
>>>
>>>> P.S. Sorry if this is an inappropriate place to ask these 
>>>> questions. Since I am not truly convinced that any of these is a 
>>>> bug (more likely a kind of GCC's extension to the standard), I 
>>>> decided to not post them on the bug tracker. Hope that you would 
>>>> suggest the proper place then.
>>>
>>> Please do report it to bugzilla, because the assertion in the code
>>> below used to pass, but fails since GCC 7.1.0, due to the changes in
>>> https://gcc.gnu.org/g:a4dec0d6de97348e71932f7080fe4a3bb8730096
>>>
>>> #include <set>
>>>
>>> template<typename T>
>>> struct Alloc
>>> {
>>>   using value_type = T;
>>>
>>>   Alloc() { }
>>>   Alloc(const Alloc&) { }
>>>   template<typename U>
>>>     Alloc(const Alloc<U>&) { }
>>>
>>>   T* allocate(std::size_t n)
>>>   { return std::allocator<T>().allocate(n); }
>>>
>>>   void deallocate(T* p, std::size_t n)
>>>   { std::allocator<T>().deallocate(p, n); }
>>> };
>>>
>>> static_assert( std::is_nothrow_move_constructible<std::set<int, 
>>> std::less<>, Alloc<int>>>::value, "" );
>>>
>>>
>>> François, could you please take a look?
>>>
>>>
>> Yes, sure.
>>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: noexcept_asso_cont.patch
Type: text/x-patch
Size: 8344 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200703/da272d7f/attachment.bin>