[Bug libstdc++/96029] New: Inconsistencies with associative/unordered containers

[Bug libstdc++/96029] New: Inconsistencies with associative/unordered containers

[nknikita at niisi dot ras.ru]

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?

[Bug libstdc++/96029] [8/9/10/11 Regression] Inconsistencies with associative/unordered containers

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |6.5.0
            Version|unknown                     |10.1.0
            Summary|Inconsistencies with        |[8/9/10/11 Regression]
                   |associative/unordered       |Inconsistencies with
                   |containers                  |associative/unordered
                   |                            |containers
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-07-02
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
There are two separate regressions here, the unordered_xxx one starting with
4.9.0 and the RB tree one starting with 7.1.0

[Bug libstdc++/96029] [8/9/10/11 Regression] Inconsistencies with associative/unordered containers

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |8.5

[Bug libstdc++/96029] [8/9/10/11 Regression] Inconsistencies with associative/unordered containers

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug libstdc++/96029] [8/9/10 Regression] Inconsistencies with associative/unordered containers

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10/11 Regression]      |[8/9/10 Regression]
                   |Inconsistencies with        |Inconsistencies with
                   |associative/unordered       |associative/unordered
                   |containers                  |containers

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The RB tree regression was fixed on trunk by r11-1910.

The unordered_xxx one was fixed on trunk by r11-2397.

[Bug libstdc++/96029] [8/9/10 Regression] Inconsistencies with associative/unordered containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:2feec6285c304d33c72e42e022d9e42d561a7607

commit r10-9672-g2feec6285c304d33c72e42e022d9e42d561a7607
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Fri Jul 3 08:13:19 2020 +0200

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

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

    libstdc++-v3/ChangeLog:

            PR libstdc++/96029
            * 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.

    (cherry picked from commit c832cf1c1d114aed70c2f84566cf4d63de0a56d0)

[Bug libstdc++/96029] [8/9/10 Regression] Inconsistencies with associative/unordered containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:1c4e8a96cd695c03ff85299bf2392476feae99bb

commit r10-9673-g1c4e8a96cd695c03ff85299bf2392476feae99bb
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Mon Jan 20 19:15:43 2020 +0100

    libstdc++: Fix unordered containers move constructors noexcept
qualification

    _Hashtable move constructor is wrongly qualified as noexcept(true)
regardless of
    _Equal and _H1 copy constructor qualifications.
    _Hashtable allocator-aware move constructor is missing its noexcept
    qualification like the depending unordered containers ones.

    This backport also includes the changes from r11-8062.

    libstdc++-v3/ChangeLog:

            PR libstdc++/96029
            * include/bits/hashtable.h
            (_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
true_type)):
            Add noexcept qualification.
            (_Hashtable(_Hashtable&&)): Fix noexcept qualification.
            (_Hashtable(_Hashtable&&, const allocator_type&)): Add noexcept
            qualification.
            * include/bits/unordered_map.h
            (unordered_map(unordered_map&&, const allocator_type&)): Add
noexcept
            qualification.
            (unordered_multimap(unordered_multimap&&, const allocator_type&)):
            Likewise.
            * include/bits/unordered_set.h
            (unordered_set(unordered_set&&, const allocator_type&)): Likewise.
            (unordered_multiset(unordered_multiset&&, const allocator_type&)):
            Likewise.
            * include/debug/unordered_map
            (unordered_map(unordered_map&&, const allocator_type&)): Likewise.
            (unordered_multimap(unordered_multimap&&, const allocator_type&)):
            Likewise.
            * include/debug/unordered_set
            (unordered_set(unordered_set&&, const allocator_type&)): Likewise.
            (unordered_multiset(unordered_multiset&&, const allocator_type&)):
            Likewise.
            * testsuite/23_containers/unordered_map/allocator/default_init.cc:
            New test.
            *
testsuite/23_containers/unordered_map/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_map/cons/noexcept_move_construct.cc:
            New test.
            * testsuite/23_containers/unordered_map/modifiers/move_assign.cc:
            New test.
            *
testsuite/23_containers/unordered_multimap/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multimap/cons/noexcept_move_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multiset/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multiset/cons/noexcept_move_construct.cc:
            New test.
            * testsuite/23_containers/unordered_set/allocator/default_init.cc:
            New test.
            *
testsuite/23_containers/unordered_set/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_set/cons/noexcept_move_construct.cc:
            New test.

    (cherry picked from commit 12324b9a934654a5c3bf4a614853ded2e0a958af)

[Bug libstdc++/96029] [8/9 Regression] Inconsistencies with associative/unordered containers

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10 Regression]         |[8/9 Regression]
                   |Inconsistencies with        |Inconsistencies with
                   |associative/unordered       |associative/unordered
                   |containers                  |containers

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 10.4 too.

[Bug libstdc++/96029] [8/9 Regression] Inconsistencies with associative/unordered containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:1228154b8726a3bc903f1967f9b3aac8fd192e46

commit r9-9327-g1228154b8726a3bc903f1967f9b3aac8fd192e46
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Fri Jul 3 08:13:19 2020 +0200

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

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

    For the backport to gcc-9 the _Rb_tree_impl move constructor must be
    user-provided, because prior to the implementation of P1286R2 in
    r10-4094, a defaulted special member with a different exception would be
    deleted.

    libstdc++-v3/ChangeLog:

            PR libstdc++/96029
            * 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.

    (cherry picked from commit c832cf1c1d114aed70c2f84566cf4d63de0a56d0)

[Bug libstdc++/96029] [8/9 Regression] Inconsistencies with associative/unordered containers

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-9 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:5f63261c3e54995b45dd411ad76526870c4b8be3

commit r9-9328-g5f63261c3e54995b45dd411ad76526870c4b8be3
Author: François Dumont <fdumont@gcc.gnu.org>
Date:   Mon Jan 20 19:15:43 2020 +0100

    libstdc++: Fix unordered containers move constructors noexcept
qualification

    _Hashtable move constructor is wrongly qualified as noexcept(true)
regardless of
    _Equal and _H1 copy constructor qualifications.
    _Hashtable allocator-aware move constructor is missing its noexcept
    qualification like the depending unordered containers ones.

    This backport also includes the changes from r11-8062 and r11-2438.

    libstdc++-v3/ChangeLog:

            PR libstdc++/96029
            * include/bits/hashtable.h
            (_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
true_type)):
            Add noexcept qualification.
            (_Hashtable(_Hashtable&&)): Fix noexcept qualification.
            (_Hashtable(_Hashtable&&, const allocator_type&)): Add noexcept
            qualification.
            * include/bits/unordered_map.h
            (unordered_map(unordered_map&&, const allocator_type&)): Add
noexcept
            qualification.
            (unordered_multimap(unordered_multimap&&, const allocator_type&)):
            Likewise.
            * include/bits/unordered_set.h
            (unordered_set(unordered_set&&, const allocator_type&)): Likewise.
            (unordered_multiset(unordered_multiset&&, const allocator_type&)):
            Likewise.
            * include/debug/unordered_map
            (unordered_map(unordered_map&&, const allocator_type&)): Likewise.
            (unordered_multimap(unordered_multimap&&, const allocator_type&)):
            Likewise.
            * include/debug/unordered_set
            (unordered_set(unordered_set&&, const allocator_type&)): Likewise.
            (unordered_multiset(unordered_multiset&&, const allocator_type&)):
            Likewise.
            * testsuite/23_containers/unordered_map/allocator/default_init.cc:
            New test.
            *
testsuite/23_containers/unordered_map/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_map/cons/noexcept_move_construct.cc:
            New test.
            * testsuite/23_containers/unordered_map/modifiers/move_assign.cc:
            New test.
            *
testsuite/23_containers/unordered_multimap/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multimap/cons/noexcept_move_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multiset/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_multiset/cons/noexcept_move_construct.cc:
            New test.
            * testsuite/23_containers/unordered_set/allocator/default_init.cc:
            New test.
            *
testsuite/23_containers/unordered_set/cons/noexcept_default_construct.cc:
            New test.
            *
testsuite/23_containers/unordered_set/cons/noexcept_move_construct.cc:
            New test.

    (cherry picked from commit 12324b9a934654a5c3bf4a614853ded2e0a958af)

[Bug libstdc++/96029] [8 Regression] Inconsistencies with associative/unordered containers

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9 Regression]            |[8 Regression]
                   |Inconsistencies with        |Inconsistencies with
                   |associative/unordered       |associative/unordered
                   |containers                  |containers
      Known to fail|                            |10.3.0, 8.4.0, 9.3.0

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
And 9.4 too.

[Bug libstdc++/96029] [8 Regression] Inconsistencies with associative/unordered containers

[vvinayag at arm dot com]

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

vvinayag at arm dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vvinayag at arm dot com

--- Comment #9 from vvinayag at arm dot com ---
After commit [1] in gcc-10, the following internal compiler error is present:

In file included from 
/build-aarch64-none-elf/obj/gcc2/aarch64-none-elf/libstdc++-v3/include/unordered_map:46,
                 from /src/gcc/libstdc++-v3/include/precompiled/stdc++.h:117:
/build-aarch64-none-elf/obj/gcc2/aarch64-none-elf/libstdc++-v3/include/bits/hashtable.h:1317:56:
internal compiler error: in merge_exception_specifiers, at cp/typeck2.c:2566
 1317 |       std::is_nothrow_copy_constructible<_Equal>::value)
      |                                                        ^
0x9b85f8 merge_exception_specifiers(tree_node*, tree_node*)
        /src/gcc/gcc/cp/typeck2.c:2564
0x99ba1e merge_types(tree_node*, tree_node*)
        /src/gcc/gcc/cp/typeck.c:874


[1]
commit 1c4e8a96cd695c03ff85299bf2392476feae99bb
Author:     François Dumont <fdumont@gcc.gnu.org>
AuthorDate: Mon Jan 20 19:15:43 2020 +0100
Commit:     Jonathan Wakely <jwakely@redhat.com>
CommitDate: Thu Apr 8 17:28:31 2021 +0100

    libstdc++: Fix unordered containers move constructors noexcept
qualification



The build/host/target setup is:
Build: x86_64 (Linux)
Host: : x86_64 (Linux)
Target: arm-none-eabi / arm-none-linux-gnueabi  / aarch64-none-elf /
aarch64-none-linux-gnu

[Bug libstdc++/96029] [8 Regression] Inconsistencies with associative/unordered containers

[redi at gcc dot gnu.org]

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

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
See Bug 99983

[Bug libstdc++/96029] [8 Regression] Inconsistencies with associative/unordered containers

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
             Status|NEW                         |RESOLVED
   Target Milestone|8.5                         |9.4
         Resolution|---                         |FIXED

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The GCC 8 branch is being closed, fixed in GCC 9.4.