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

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

[palpatin91 at mail dot ru]

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.
>From gcc-bugs-return-468789-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Nov 27 17:08:06 2014
Return-Path: <gcc-bugs-return-468789-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 30831 invoked by alias); 27 Nov 2014 17:08:06 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 30797 invoked by uid 48); 27 Nov 2014 17:08:01 -0000
From: "ams at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug middle-end/64032] [5 Regression] FAIL: gcc.dg/undefined-loop-2.c  (test for warnings, line 18)
Date: Thu, 27 Nov 2014 17:08:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: middle-end
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: ams at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: ams at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 5.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-64032-4-6IArSwj0hE@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-64032-4@http.gcc.gnu.org/bugzilla/>
References: <bug-64032-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-11/txt/msg03261.txt.bz2
Content-length: 651

https://gcc.gnu.org/bugzilla/show_bug.cgi?idd032

--- Comment #2 from Andrew Stubbs <ams at gcc dot gnu.org> ---
When I configure for powerpc-linux-gnu, undefined-loop-2.c.003t.original
contains this:

  if (((p != 0 ? (unsigned char) array1[i] != 0 : (unsigned char) array2[i] !0) && i <= 4) && i <= 99) goto <D.2332>; else goto <D.2334>;


When I configure for x86_64-linux-gnu, the same command and dump file contains
this:

  if ((p != 0 ? (signed char) array1[i] != 0 : (signed char) array2[i] != 0) &&
i <= 4) goto <D.1837>; else goto <D.1839>;

It looks like something has started optimizing the code really very early. This
surprises me!

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

[palpatin91 at mail dot ru]

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

rylai <palpatin91 at mail dot ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |WONTFIX

--- Comment #2 from rylai <palpatin91 at mail dot ru> ---
Known issues

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

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|WONTFIX                     |FIXED

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I'm going to mark it fixed, since std::list is fixed, and the other part of the
report is not a bug.

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

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |5.0

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

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
For completeness, the error for std::list now shows:

a.cc: In instantiation of ‘void my_allocator<T>::construct(U*, Args&& ...)
[with U = int; Args = {int}; T = std::_Rb_tree_node<int>]’:

which is consistent with maps and sets now.

I actually consider it a bug that you don't get the assertion for other
containers too! The unordered containers and forward_list should not bother
constructing a rebound allocator to call construct/destroy.
>From gcc-bugs-return-469207-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Dec 02 13:35:49 2014
Return-Path: <gcc-bugs-return-469207-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 24656 invoked by alias); 2 Dec 2014 13:35:48 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 24636 invoked by uid 55); 2 Dec 2014 13:35:45 -0000
From: "vries at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/63718] [5 Regression] ARM Thumb1 bootstrap fail after fuse-caller-save info in cprop-hardreg
Date: Tue, 02 Dec 2014 13:35:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords: patch, wrong-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: vries at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P1
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 5.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-63718-4-W29ArTIngS@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63718-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63718-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-12/txt/msg00214.txt.bz2
Content-length: 470

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc718

--- Comment #16 from vries at gcc dot gnu.org ---
Author: vries
Date: Tue Dec  2 13:35:10 2014
New Revision: 218271

URL: https://gcc.gnu.org/viewcvs?rev!8271&root=gcc&view=rev
Log:
2014-12-02  Tom de Vries  <tom@codesourcery.com>

    PR rtl-optimization/63718
    * config/arm/arm.c (arm_option_override): Disable fuse-caller-save for
    Thumb1.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/arm/arm.c