public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/96029] New: Inconsistencies with associative/unordered containers
@ 2020-07-02 11:38 nknikita at niisi dot ras.ru
  2020-07-02 12:44 ` [Bug libstdc++/96029] [8/9/10/11 Regression] " redi at gcc dot gnu.org
                   ` (12 more replies)
  0 siblings, 13 replies; 14+ messages in thread
From: nknikita at niisi dot ras.ru @ 2020-07-02 11:38 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96029

            Bug ID: 96029
           Summary: Inconsistencies with associative/unordered containers
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nknikita at niisi dot ras.ru
  Target Milestone: ---

Well, it seems that there some problems with noexcept specification of
associative and unordered containers' move constructors and move assignment
operators. The following is the reply that I have received from Jonathan Wakely
via GCC's mailing list.

------------------------------------------------------------------------------

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) {
  }
}


> 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?

^ permalink raw reply	[flat|nested] 14+ messages in thread
end of thread, other threads:[~2021-05-14 13:58 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-07-02 11:38 [Bug libstdc++/96029] New: Inconsistencies with associative/unordered containers nknikita at niisi dot ras.ru
2020-07-02 12:44 ` [Bug libstdc++/96029] [8/9/10/11 Regression] " redi at gcc dot gnu.org
2020-07-02 13:24 ` rguenth at gcc dot gnu.org
2020-10-12 12:50 ` rguenth at gcc dot gnu.org
2021-04-08 14:35 ` [Bug libstdc++/96029] [8/9/10 " redi at gcc dot gnu.org
2021-04-08 17:00 ` cvs-commit at gcc dot gnu.org
2021-04-08 17:00 ` cvs-commit at gcc dot gnu.org
2021-04-08 17:43 ` [Bug libstdc++/96029] [8/9 " redi at gcc dot gnu.org
2021-04-08 23:37 ` cvs-commit at gcc dot gnu.org
2021-04-08 23:37 ` cvs-commit at gcc dot gnu.org
2021-04-08 23:38 ` [Bug libstdc++/96029] [8 " redi at gcc dot gnu.org
2021-04-09 14:04 ` vvinayag at arm dot com
2021-04-09 14:22 ` redi at gcc dot gnu.org
2021-05-14 13:58 ` jakub at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).