[Bug libstdc++/64096] New: std::list, set and map violate a rule about allocator::construct

["palpatin91 at mail dot ru" <gcc-bugzilla at gcc dot gnu dot org>]

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

            Bug ID: 64096
           Summary: std::list, set and map violate a rule about
                    allocator::construct
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: palpatin91 at mail dot ru

According to the 23.2.1p3 C++11 Standard:
===========================================
For the components affected by this subclause that declare an allocator_type,
objects stored in these components shall be constructed using the
allocator_traits<allocator_type>::construct function and destroyed using the
allocator_traits<allocator_type>::destroy function (20.6.8.2). These functions
are called only for the containerâs element type, not for internal types used
by the container. [ Note: This means, for example, that a node-based container
might need to construct nodes containing aligned buffers and call construct to
place the element into the buffer. âend note ]
===========================================

Here allocator_type is a direct template's type argument, and allocator_traits
just call allocator's construct method, if it exists. However, std::list, set
and map (and also multiset and multimap) violate this rule and call construct
method from an allocator of rebinded type, not of an original one. I know, that
we need rebinding for memory allocation, but for construct call we should use
original one. 23.2.1p13 also proves this:
===========================================
Given a container type X having an allocator_type identical to A and a
value_type identical to T and given an lvalue m of type A, a pointer p of type
T*, an expression v of type T, and an rvalue rv of type T, the following terms
are defined. (If X is not allocator-aware, the terms below are defined as if A
were std::allocator<T>.)
â T is CopyInsertable into X means that the following expression is
well-formed: allocator_traits<A>::construct(m, p, v);
â T is MoveInsertable into X means that the following expression is
well-formed: allocator_traits<A>::construct(m, p, rv);
â T is EmplaceConstructible into X from args, for zero or more arguments args,
means that the following expression is well-formed:
allocator_traits<A>::construct(m, p, args);
===========================================

Now some code that confirms a bug:
===========================================
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <type_traits>

template<typename T>
struct my_allocator : public std::allocator<T> {
    my_allocator() noexcept {}

    template<typename U>
    my_allocator(const my_allocator<U>& source) noexcept
        : std::allocator<T>(source) {}

    template<typename U>
    struct rebind {
        using other = my_allocator<U>;
    };

    template<typename U, typename... Args>
    void construct(U*, Args&&...) {
        static_assert(!std::is_same<U, U>::value, "Wrong construct");
    }
};

template <typename T, typename U>
bool operator==(const my_allocator<T>&, const my_allocator<U>&)
    { return true; }

template <typename T, typename U>
bool operator!=(const my_allocator<T>&, const my_allocator<U>&)
    { return false; }

template<>
struct my_allocator<int> : public std::allocator<int> {
    my_allocator() noexcept {}

    template<typename U>
    my_allocator(const my_allocator<U>& source) noexcept
        : std::allocator<int>(source) {}

    template<typename U>
    struct rebind {
        using other = my_allocator<U>;
    };
};

using map_int_int_value_type = std::map<int, int>::value_type;

template<>
struct my_allocator<map_int_int_value_type>
: public std::allocator<map_int_int_value_type> {
    my_allocator() noexcept {}

    template<typename U>
    my_allocator(const my_allocator<U>& source) noexcept
        : std::allocator<map_int_int_value_type>(source) {}

    template<typename U>
    struct rebind {
        using other = my_allocator<U>;
    };
};

int main()
{
    {
        using container = std::vector<int, my_allocator<int>>;
        container c;
        c.emplace_back(0);
    }
    {
        using container = std::list<int, my_allocator<int>>;
        container c;
        c.emplace_back(0);
    }
    {
        using container = std::set<int, std::less<int>, my_allocator<int>>;
        container c;
        c.emplace(0);
    }
    {
        using container = std::multiset<int, std::less<int>,
my_allocator<int>>;
        container c;
        c.emplace(0);
    }
    {
        using container = std::unordered_set<int, std::hash<int>,
                std::equal_to<int>, my_allocator<int>>;
        container c;
        c.emplace(0);
    }
    {
        using container = std::unordered_multiset<int, std::hash<int>,
                std::equal_to<int>, my_allocator<int>>;
        container c;
        c.emplace(0);
    }
    {
        using container = std::map<int, int, std::less<int>,
                my_allocator<map_int_int_value_type>>;
        container c;
        c.emplace(0, 0);
    }
    {
        using container = std::multimap<int, int, std::less<int>,
                my_allocator<map_int_int_value_type>>;
        container c;
        c.emplace(0, 0);
    }
    {
        using container = std::unordered_map<int, int, std::hash<int>,
                std::equal_to<int>, my_allocator<map_int_int_value_type>>;
        container c;
        c.emplace(0, 0);
    }
    {
        using container = std::unordered_multimap<int, int, std::hash<int>,
                std::equal_to<int>, my_allocator<map_int_int_value_type>>;
        container c;
        c.emplace(0, 0);
    }
    {
        using container = std::deque<int, my_allocator<int>>;
        container c;
        c.emplace_back(0);
    }
}
===========================================

We make a template allocator class, that print static_assert error message,
when someone try to instantiate his construct method, and then make 2
specializations of this class template (for int and for std::pair<const int,
int>), which inherit construct method from std::allocator and so don't generate
any error. The compiler's output is (I leave only important lines):
===========================================
main.cpp: In instantiation of 'void my_allocator<T>::construct(U*, Args&& ...)
[with U = std::_List_node<int> Args = {int}; T = std::_List_node<int>]':
...
main.cpp:24:9: error: static assertion failed: Wrong construct


main.cpp: In instantiation of 'void my_allocator<T>::construct(U*, Args&& ...)
[with U = int; Args = {int}; T = std::_Rb_tree_node<int>]':
...
main.cpp:24:9: error: static assertion failed: Wrong construct


main.cpp: In instantiation of 'void my_allocator<T>::construct(U*, Args&& ...)
[with U = std::pair<const int, int> Args = {int, int}; T =
std::_Rb_tree_node<std::pair<const int, int> >]':
...
main.cpp:24:9: error: static assertion failed: Wrong construct
===========================================

As we can see, std::list implementation tries to call construct for whole list
node (U = std::_List_node<int>), and std::set and map (and also multiset and
multimap) call it for right type (int or std::pair<const int, int>), but from
rebinded allocator (T = std::_Rb_tree_node<int>). All other containers
(std::vector, std::deque and unordered ones) do everything right.