libstdc++: Add fancy pointer support to std::list [PR57272]

Currently std::list uses raw pointers to connect its nodes, which is
non-conforming. We should use the allocator's pointer type everywhere
that a "pointer" is needed.

Because the existing types like _List_node<T> are part of the ABI now,
we can't change them. To support nodes that are connected by fancy
pointers we need a parallel hierarchy of node types. This change
introduces new class templates parameterized on the allocator's
void_pointer type, __list::_Node_base and __list::_Node_header, and new
class templates parameterized on the allocator's pointer type,
__list::Node, __list::_Iterator. The iterator class template is used for
both iterator and const_iterator. Whether std::list<T, A> should use the
old _List_node<T> or new _list::_Node<A::pointer> type family internally
is controlled by a new __list::_Node_traits traits template.

Because std::pointer_traits and std::__to_address are not defined for
C++98, there is no way to support fancy pointers in C++98. For C++98 the
_Node_traits traits always choose the old _List_node family.

In case anybody is currently using std::list with an allocator that has
a fancy pointer, this change would be an ABI break, because their
std::list instantiations would start to (correctly) use the fancy
pointer type. If the fancy pointer just contains a single pointer and so
has the same size, layout, and object represenation as a raw pointer,
the code might still work (despite being an ODR violation). But if their
fancy pointer has a different representation, they would need to
recompile all their code using that allocator with std::list. Because
std::list will never use fancy pointers in C++98 mode, recompiling
everything to use fancy pointers isn't even possible if mixing C++98 and
C++11 code that uses std::list. To alleviate this problem, compiling
with -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=0 will force std::list to have
the old, non-conforming behaviour and use raw pointers internally. For
testing purposes, compiling with -D_GLIBCXX_USE_ALLOC_PTR_FOR_LIST=9001
will force std::list to always use the new node types.  This macro is
currently undocumented, which needs to be fixed.

The original _List_node<T> type is trivially constructible and trivially
destructible, but the new __list::_Node<Ptr> type might not be,
depending on the fancy pointer data members in _Node_base. This means
that std::list needs to explicitly construct and destroy the node
object, not just the value that it contains. This commit adds a new
__allocated_obj helper which wraps an __allocated_ptr and additionally
constructs and destroys an object in the allocated storage.

Pretty printers for std::list need to be updated to handle the new node
types. Potentially we just can't pretty print them, because we don't
know how to follow the fancy pointers to traverse the list.

libstdc++-v3/ChangeLog:

	PR libstdc++/57272
	PR libstdc++/110952
	* include/bits/allocated_ptr.h (__allocated_ptr::get): Add
	const.
	(__allocated_ptr::operator bool, __allocated_ptr::release): New
	member functions.
	(__allocate_guarded): Add inline.
	(__allocated_obj): New class template.
	(__allocate_guarded_obj): New function template.
	* include/bits/list.tcc (_List_base::_M_clear()): Replace uses
	of raw pointers. Use _M_destroy_node.
	(list::emplace, list::insert): Likewise.
	(list::sort): Adjust check for 0 or 1 wsize. Use template
	argument list for _Scratch_list.
	* include/bits/stl_list.h (_GLIBCXX_USE_ALLOC_PTR_FOR_LIST):
	Define.
	(_List_node_base::_Base_ptr): New typedef.
	(_List_node_base::_M_base): New member functions.
	(_List_node_header::_M_base): Make public and add
	using-declaration for base class overload.
	(__list::_Node_traits, __list::_Node_base)
	(__list::_Node_header, __list::_Node, __list::_Iterator): New
	class templates.
	(_Scratch_list): Turn class into class template. Use _Base_ptr
	typedef instead of _List_node_base*.
	(_List_node::_Node_ptr): New typedef.
	(_List_node::_M_node_ptr): New member function.
	(_List_base, _List_impl): Use _Node_traits to get node types.
	(_List_base::_M_put_node): Convert to fancy pointer if needed.
	(_List_base::_M_destroy_node): New member function.
	(_List_base(_List_base&&, _Node_alloc_type&&)): Use if constexpr
	to make function a no-op for fancy pointers.
	(_List_base::_S_distance, _List_base::_M_distance)
	(_List_base::_M_node_count): Likewise.
	(list): Use _Node_traits to get iterator, node and pointer
	types.
	(list::_M_create_node): Use _Node_ptr typedef instead of _Node*.
	Use __allocate_guarded_obj instead of _M_get_node.
	(list::end, list::cend, list::empty): Use node header's
	_M_base() function instead of taking its address.
	(list::swap): Use _Node_traits to get node base type.
	(list::_M_create_node, list::_M_insert): Use _Node_ptr instead
	of _Node*.
	(list::_M_erase): Likewise. Use _M_destroy_node.
	(__distance): Overload for __list::_Iterator.
	(_Node_base::swap, _Node_base::_M_transfer): Define non-inline
	member functions of class templates.
	(_Node_header::_M_reverse): Likewise.
	* testsuite/23_containers/list/capacity/29134.cc: Check max_size
	for allocator of new node type.
	* testsuite/23_containers/list/capacity/node_sizes.cc: New test.
	* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr.cc:
	New test.
	* testsuite/23_containers/list/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
	New test.

0 files changed, 0 insertions, 0 deletions