Incorrect C++11 allocator model support

[glenfe]

Here is a preliminary list of issues:

• Your allocator template parameter should be just class AllocatorType = std::allocator<ValueType> instead of template<class U> class AllocatorType = std::allocator. i.e. Do not require that the allocator type is a class template with one template parameter.
• You only support stateless allocators; C++ allocators can be stateful. Your basic_json constructors should accept an optional allocator instance: basic_json(..., const AllocatorType& allocator = AllocatorType());
• Your get_allocator() member should return the value of that stored allocator instance.
• Don't use AllocatorType<Type> alloc;, instead rebind the stored allocator instance member variable with std::allocator_traits<AllocatorType>::rebind_alloc<Type> alloc(allocator);.
• Don't use alloc.construct(...) directly, instead use std::allocator_traits<AllocatorType>::rebind_traits<Type>::construct(alloc, ...). Allocators are not required to provide construct or destroy so all construction and destruction should go through std::allocator_traits.
• A given allocator is allowed to have complex types for pointer so preserve those (instead of T*) for the result of alloc.allocate(n). Use std::addressof with those pointers to obtain the value for use with construct(...).

You'll notice all the C++ standard library facilities which support allocators implement the above, so look to them (or to allocator aware types in Boost) for further examples.

[nlohmann]

@glenfe, thanks for your feedback! I copied your items to check them off once they are fixed:

• Your allocator template parameter should be just class AllocatorType = std::allocator<ValueType> instead of template<class U> class AllocatorType = std::allocator. i.e. Do not require that the allocator type is a class template with one template parameter.
• You only support stateless allocators; C++ allocators can be stateful. Your basic_json constructors should accept an optional allocator instance: basic_json(..., const AllocatorType& allocator = AllocatorType());
• Your get_allocator() member should return the value of that stored allocator instance.
• Don't use AllocatorType<Type> alloc;, instead rebind the stored allocator instance member variable with std::allocator_traits<AllocatorType>::rebind_alloc<Type> alloc(allocator);.
• Don't use alloc.construct(...) directly, instead use std::allocator_traits<AllocatorType>::rebind_traits<Type>::construct(alloc, ...). Allocators are not required to provide construct or destroy so all construction and destruction should go through std::allocator_traits.
• A given allocator is allowed to have complex types for pointer so preserve those (instead of T*) for the result of alloc.allocate(n). Use std::addressof with those pointers to obtain the value for use with construct(...).

[erichkeane]

@nlohmann : I will likely have time in the next week or so, I can start work on this as a part of the changes that were suggested on #164 if you so approve.

[erichkeane]

Started looking a little bit into this, gonna go through the list with questions:

Your allocator template parameter should be just class AllocatorType = std::allocator instead of template class AllocatorType = std::allocator. i.e. Do not require that the allocator type is a class template with one template parameter.

The issue I see trying this is 2 fold:
1- The reason for taking a template option was that the object & array types (not string interestingly) were given this allocator. Due to #169, this is no longer the case, so I suspect that isn't an issue.
2- The bigger issue is defining the default allocator correctly. Unlike most objects, the basic_json object contains values of itself, so in your example above, ValueType is actually equal to the 'self' type, which is obviously infinitely recursive. I don't see how to get this to happen correctly?

You only support stateless allocators; C++ allocators can be stateful. Your basic_json constructors should accept an optional allocator instance: basic_json(..., const AllocatorType& allocator = AllocatorType());

Seems easy enough

Your get_allocator() member should return the value of that stored allocator instance.

Currently this is static, I would imagine for a reason? It doesn't make sense to return the stored allocator in that situation, so I imagine that would need to be changed to non-static? What was the initial reason to make this static? Additionally, should this return a reference now?

Don't use AllocatorType alloc;, instead rebind the stored allocator instance member variable with std::allocator_traits::rebind_alloc alloc(allocator);.

Again, has recursiveness, which I suspect would be OK by now. That said, this increases the size of a the object by quite a bit. The basic_json type is now going to be std::allocator larger, which isn't too bad until you realize that each object contains many others potentially.

Don't use alloc.construct(...) directly, instead use std::allocator_traits::rebind_traits::construct(alloc, ...). Allocators are not required to provide construct or destroy so all construction and destruction should go through std::allocator_traits.

Easy enough

A given allocator is allowed to have complex types for pointer so preserve those (instead of T*) for the result of alloc.allocate(n). Use std::addressof with those pointers to obtain the value for use with construct(...).

Perhaps I'm being a little slow, but I don't really get what you mean here?

Edit to add: I'll note that since the #169 pull request pushes the allocate-specification onto the user defining the ObjectType/ArrayType/StringType, would we perhaps be better off just removing the "create" mechanism entirely? Could we do without the AllocatorType entirely, and just ensure we recursively define the types of ObjectType/ArrayType/StringType such that their allocators will be used for all children?

[gregmarr]

"rebind the stored allocator instance member variable"

"This increases the size of a the object by quite a bit. The basic_json type is now going to be std::allocator larger"

The way to avoid that is to derive from it instead of having it as a member. Then the empty base class optimization would cause it to take up no space when it is stateless.

[glenfe]

The basic_json type is now going to be std::allocator larger, which isn't too bad until you realize that each object contains many others potentially.

As Greg said, the way to avoid increasing storage by sizeof(Allocator) for when Allocator is stateless, is to use the empty base optimization.

You could achieve that via inheritance, or by pairing the allocator instance with another member by leveraging a type like compressed_pair. (Where compressed_pair uses the empty base optimization via inheritance). See Boost's implementation for inspiration.

[glenfe]

Perhaps I'm being a little slow, but I don't really get what you mean here?

In C++11 and above, the pointer type of a given allocator is not required to be value_type* or even of the form T*. That is, an allocator's pointer type could be a smart pointer. So if you support the C++ allocator model, you have to:

• Not assume that an allcoator's allocate() returns raw pointers
• Store the return value of allocate() in an object of pointer type
• Pass it in pointer object form to the allocator's deallocate()

Now, given an object, p, of this type pointer, if you need to obtain a raw pointer from it (e.g. for use with std::allocator_traits<A>::construct() or other similar functions), you should do this via std::addressof(*p).

[glenfe]

I don't see how to get this to happen correctly?

Even class Allocator = std::allocator<void> is fine if you don't know the desired value_type a priori (or there are multiple). You're going to rebind the allocator as needed for every allocation, so the initial value_type of the allocator isn't important then. The main thing is that Allocator is not restricted to being a class template with one template parameter.

[palacaze]

I updated my #170 branch to implement @glenfe empty base optimization idea, and I think the use of allocator_traits is now correct.
I had to change one constructor into a static array constructor in order to avoid an ambiguous constructor call resolution.

All tests pass with gcc 5.3 and clang 3.7.

[vinniefalco]

This utility class facilitates use of the empty base optimization idiom:
https://github.com/vinniefalco/Beast/blob/dd02097d265857c3cfca435317f06f7af701a012/include/beast/core/detail/empty_base_optimization.hpp

[nlohmann]

Update: I created a feature branch for custom allocators.

[jwakely]

@glenfe

So if you support the C++ allocator model, you have to:

IMHO it's reasonable to omit support for "fancy pointers" i.e. pointers that aren't just T*. The rest of the C++11 Allocator model (indirection through allocator_traits and stateful allocators) is still useful, even without fancy pointers. And it makes life much simpler.

Now, given an object, p, of this type pointer, if you need to obtain a raw pointer from it (e.g. for use with std::allocator_traits<A>::construct() or other similar functions), you should do this via std::addressof(*p).

No, because if there's no object constructed there yet then *p is undefined. There are ways to get a raw pointer from something that might be a raw pointer or might be a "fancy pointer", but it's simpler to just ignore fancy pointers.

static_assert( std::is_pointer<typename Allocator::pointer>::value, "Allocator's pointer type must be a real pointer" );

[glenfe]

@jwakely Good point. There is probably some acceptable approach involving p.operator->() when applicable (as I have observed Howard doing, in this place).

The rest of the C++11 Allocator model (indirection through allocator_traits and stateful allocators) is still useful, even without fancy pointers. And it makes life much simpler.

Agreed. Which is why I hope the wontfix resolution attached to the issue isn't permanent.

[jwakely]

There is probably some acceptable approach involving p.operator->() when applicable (as I have observed Howard doing, in this place).

Yep, that's the trick :-) Two overloads, one for raw pointers which just returns its argument, and one for everything else, which returns p.operator->().

[AraHaan]

@nlohmann what you think about what @glenfe and what @jwakely discussed here?

[nlohmann]

I have too little understanding of allocators. I started to incorporate the mentioned fixes a long time ago, but the library is a complex beast and I had to give up at some point. Any help is greatly appreciated, be it a pull request or any concrete idea how move forward on this issue.