Re: [boost] AllocatorAwareContainers (was: Review of PolyCollection starts today (May 3rd))

Subject: Re: [boost] AllocatorAwareContainers (was: Review of PolyCollection starts today (May 3rd))
From: Gavin Lambert (gavinl_at_[hidden])
Date: 2017-06-15 08:17:59

On 15/05/2017 11:12, Glen Fernandes wrote:
> On Sun, May 14, 2017 at 7:02 PM, Gavin Lambert wrote:
>>
>> In particular, these rules seem to basically require that the node type be
>> trivially-constructible, because you can't legally call the node constructor
>> and then call the value constructor where the value is a field of the node;
>> you'd have to construct the node, destroy the value, then re-construct the
>> value, which seems well over the line into crazypants territory.
>>
>> It all seems very arbitrary to me.
> 
> No. You could also design the node type to contain a
> std::aligned_storage_t<sizeof(value_type), alignof(value_type)>
> object (instead of containing a value_type object).
> 
> That way after you construct the Node type with ::new(x)
> Node(args...); you an use std::allocator_traits<U>::construct(u,
> address, args...) with the address of that aligned storage.

Apologies for the delayed response, but I was distracted by other things.

If the node actually contains aligned_storage rather than T, doesn't 
that then require reinterpret_casting everywhere (since everything will 
expect a T*, not an aligned_storage_t<>*)?  Isn't that usually 
considered a bad thing?

It also seems really error-prone, since 
allocator_traits::construct/destroy accept pointers of all types, not 
just their parameterised type, and then act based on the received type.

So given:

     struct node
     {
         node* next;
         std::aligned_storage_t<sizeof(T), alignof(T)> storage;
     };
     using alloc_traits = std::allocator_traits<T>;
     using node_traits = typename alloc_traits::
             template rebind_traits<node>;

     alloc_traits::allocator_type m_alloc;
     node_traits::allocator_type m_node_alloc; // m_node_alloc(m_alloc)

This code looks correct at a glance, but is horribly horribly wrong:

     node* n = node_traits::allocate(m_node_alloc, 1);
     ::new(n) node({ nullptr });  // not allowed to call construct?
     alloc_traits::construct(m_alloc, std::addressof(n->storage));
     // ...
     alloc_traits::destroy(m_alloc, std::addressof(n->storage));
     n->~node();       // not allowed to call destroy?
     node_traits::destroy(m_node_alloc, n, 1);

(The double-construction of storage isn't the wrong part -- we're 
relying on it being a trivially-constructible type.)

This compiles, and it default-constructs and then destroys a T inside 
node, right?  No, since storage is the wrong type it ends up calling the 
storage-POD constructor and destructor, not T's.  Despite alloc_traits 
supposedly being the traits for T.  Why is the allocator even templated 
on this type when it doesn't actually use it?

To make that code actually behave as expected, you need to 
reinterpret_cast<T&>(n->storage).  And you need to remember to do that 
everywhere, and the compiler won't help you because it will happily 
compile with the wrong behaviour if you forget.  (Only the allocator 
parameter is type-checked, not the address parameter.)

Am I missing something?  This seems a bit broken.

Granted it's easy enough to make this safe once you're aware of it, but 
it seems like a way-too-easy trap to fall into.  eg. this would be a 
"safe" node:

     struct node
     {
         explicit node(node* n = nullptr) : next(n) {}

         node* next;
         T& value() { return reinterpret_cast<T&>(storage); }

     private:
         std::aligned_storage_t<sizeof(T), alignof(T)> storage;
     };

But of course now it's not a POD.

One other thing that the lax type-checking does allow is this:

     node* n = node_traits::allocate(m_node_alloc, 1);
     ::new(n) node();  // not allowed to call construct?
     node_traits::construct(m_node_alloc, std::addressof(n->value()));
     // ...
     node_traits::destroy(m_node_alloc, std::addressof(n->value()));
     n->~node();       // not allowed to call destroy?
     node_traits::destroy(m_node_alloc, n, 1);

(Specifically not actually using m_alloc or alloc_traits any more.)
Which seems like it should be illegal (despite being convenient, since 
it means storing only one allocator), although a StackOverflow thread 
claims that it's intended behaviour.