[libcxx] Fix for ALL undefined behavior in <list>.

[EricWF]

Summary

This patch fixes std::list for builtin pointer types in the current ABI version and fixes std::list for all fancy pointer types in the next ABI version. The patch was designed to minimize the amount of code needed to support both ABI configurations. Currently only ~5 lines of code differ.

[awi]

Hello,
I like your patch very much. I looks similar to my patch from January, so I am confident it solves my problem, but it does so a little more elegantly at some places.
I tried it with my two sources files main.cpp and main2.cpp. While main.cpp works with or without your patch, main2.cpp fails with the current svn head, but succeeds with your patch.
After that I executed the libc++ test suite, using -std=c++1y as the language version. Here, a couple of tests failed to compile. This is not as bad as it may sound, though, because I could fix it by adding some missing calls to your new __list_node_base functions __as_base() and __as_node():

--- include/list	2015-08-25 20:35:00.769897378 +0200
+++ include/list.corr	2015-08-25 20:10:38.000000000 +0200
@@ -1362,9 +1362,9 @@
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get(), this);
+        __r = iterator(__hold.get()->__as_base(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold.get()->__as_base());
 #endif
         __hold.release();
         iterator __e = __r;
@@ -1376,7 +1376,7 @@
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_base();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
@@ -1388,7 +1388,7 @@
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
                 __node_base_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2

[EricWF]

Address failing test that @awi pointed out.

[mclow.lists]

So... what do we need to do to enumerate the "ABI breakage" of this patch?

I get that there's a couple of member variables that are changing type. Can they change (as a result of this patch) from a plain pointer to a fancy pointer (or vice versa)? Can they change size? Is this a header-only change (probably) with no need to ship a new dylib?

[EricWF]

I've spent some time testing this patch to see if it causes ABI problem. Here is what I did:

1. Add external instantiations of std::list into the libc++ dylib for the types used in the tests.
2. Compile libcxx-old.dylib with the external instantations but without this patch.
3. Apply this patch and compile libcxx-new.dylib.
4. For each test, T, in std/containers/sequences/list do the following:
   1. Compile and link T against the patched headers and libcxx-new.dylib. Run T using libcxx-old.dylib.
   2. Compile and link T against the original headers and libcxx-old.dylib`. Run T using libcxx-new.dylib.

I didn't see any issues arise when doing this but that doesn't mean there are none. I'm going to ensure this method actually would catch
a ABI breakage so I can have some more faith in the results.

[EricWF]

include/list

198

Possible ABI break here.

[EricWF]

Ping.

Originally I considered this change to be ABI breaking because we changed the type of the link pointers from __list_node_pointer to __list_node_base_pointer. However I now believe this change is ABI compatible in 99% of cases. I assert that this change is safe whenever __list_node_pointer and __list_node_base_pointer are builtin pointer types.

Unfortunately std::list supports fancy "class-like" pointers and we cannot guarantee that these fancy pointers will be ABI compatible in the same why builtin pointers are. Fancy pointers are free to have entirely different representations depending on the pointee type. For this reason I don't think we can fix std::list with fancy pointers until the next ABI version.

This patch fixes std::list for builtin pointer types in the current ABI version and fixes std::list for all fancy pointer types in the next ABI version. The patch was designed to minimize the amount of code needed to support both ABI configurations. Currently only ~5 lines of code differ.

The patch works by introducing a __link_pointer typedef that defines the type of pointers used to make the link list. __link_pointer is either __list_node_pointer or __list_node_base_pointer' depending on the ABI version. Instead of working with __node_pointer` or __node_base_pointer types in std::list we now only work with __link_pointer types except when we absolutely need to access the underlying node. When we need to convert between __node_pointer, __node_base_pointer or __link_pointer we use the conversion methods supplied defined in __list_node_base.

One problem with __link_pointer is that its easy to accidentally depend on it being defined as __node_pointer or __node_base_pointer. For example it would be incorrect to access __list_node::__value_ through a pointer declared as __link_pointer even though it will work when __link_pointer is an alias for __node_pointer. This code will compile

[EricWF]

Update with correct patch this time.

[EricWF]

Ping.

[mclow.lists]

Minor changes; other than that, LGTM.

include/__config

43

I would make this macro less generic than "fix". Maybe something like _LIBCPP_ABI_LIST_REMOVE_UB_NODEPTR

include/list

690

Do you really need __n here?
How about:

__node_pointer __np = __f->__as_node();
__f = __f->__next_;

[EricWF]

• Change ABI macro name to _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB.
• Remove unnecessary variable pointed out in review.
• Rename __node_pointer_traits to __list_node_pointer_traits to prevent name collisions.

include/__config

 #endif
 
 #if defined(_LIBCPP_ABI_UNSTABLE) || _LIBCPP_ABI_VERSION >= 2
 // Change short string represention so that string data starts at offset 0,
 // improving its alignment in some cases.
 #define _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 // Fix deque iterator type in order to support incomplete types.
 #define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
+// Fix undefined behavior in how std::list stores it's linked nodes.
+#define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB
 #endif
 
 #define _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_X##_LIBCPP_Y
 #define _LIBCPP_CONCAT(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y)
 
 #define _LIBCPP_NAMESPACE _LIBCPP_CONCAT(__,_LIBCPP_ABI_VERSION)
 
 

include/list

 
 #include <__config>
 
 #include <memory>
 #include <limits>
 #include <initializer_list>
 #include <iterator>
 #include <algorithm>
+#include <type_traits>
 
 #include <__undef_min_max>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp, class _VoidPtr> struct __list_node;
+template <class _Tp, class _VoidPtr> struct __list_node_base;
 
 template <class _Tp, class _VoidPtr>
-struct __list_node_base
-{
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        pointer;
-    typedef typename __rebind_pointer<_VoidPtr, __list_node_base>::type
+struct __list_node_pointer_traits {
+        __node_pointer;
+  typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
         __base_pointer;
 
-    pointer __prev_;
-    pointer __next_;
+#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
+  typedef __base_pointer __link_pointer;
+#else
+  typedef typename conditional<
+          is_pointer<_VoidPtr>::value,
+          __base_pointer,
+          __node_pointer
+  >::type __link_pointer;
+#endif
+
+};
+
+template <class _Tp, class _VoidPtr>
+struct __list_node_base
+{
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__node_pointer __node_pointer;
+    typedef typename _NodeTraits::__base_pointer __base_pointer;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
+
+    __link_pointer __prev_;
+    __link_pointer __next_;
 
     _LIBCPP_INLINE_VISIBILITY
-    __list_node_base() : __prev_(__self()), __next_(__self()) {}
+    __list_node_base() : __prev_(__as_link()), __next_(__as_link()) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    pointer __self()
-    {
-        return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this));
+    __base_pointer __as_base() {
+        return pointer_traits<__base_pointer>::pointer_to(*this);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __link_pointer __as_link() {
+        return static_cast<__link_pointer>(static_cast<_VoidPtr>(
+                __as_base()));
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __as_node() {
+        return static_cast<__node_pointer>(__as_base());
     }
 };
 
 template <class _Tp, class _VoidPtr>
 struct __list_node
     : public __list_node_base<_Tp, _VoidPtr>
 {
     _Tp __value_;
 };
 
 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY list;
 template <class _Tp, class _Alloc> class __list_imp;
 template <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator;
 
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_TYPE_VIS_ONLY __list_iterator
 {
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        __node_pointer;
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
 
-    __node_pointer __ptr_;
+    __link_pointer __ptr_;
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
+    explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
         : __ptr_(__p)
     {
         __get_db()->__insert_ic(this, __c);
     }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
 
 
     template<class, class> friend class list;
     template<class, class> friend class __list_imp;
     template<class, class> friend class __list_const_iterator;
 public:
#endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
     _LIBCPP_INLINE_VISIBILITY
     reference operator*() const
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return __ptr_->__value_;
+        return __ptr_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     pointer operator->() const
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
+        return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __list_iterator& operator++()
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to increment non-incrementable list::iterator");
#endif
     friend _LIBCPP_INLINE_VISIBILITY
      bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
         {return !(__x == __y);}
 };
 
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator
 {
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        __node_pointer;
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
 
-    __node_pointer __ptr_;
+    __link_pointer __ptr_;
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
+    explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
         : __ptr_(__p)
     {
         __get_db()->__insert_ic(this, __c);
     }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
     template<class, class> friend class list;
     template<class, class> friend class __list_imp;
 public:
     typedef bidirectional_iterator_tag       iterator_category;
     typedef _Tp                              value_type;
     typedef const value_type&                reference;

 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
     reference operator*() const
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::const_iterator");
 #endif
-        return __ptr_->__value_;
+        return __ptr_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     pointer operator->() const
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
+        return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __list_const_iterator& operator++()
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to increment non-incrementable list::const_iterator");
protected:
     typedef __list_iterator<value_type, __void_pointer>             iterator;
     typedef __list_const_iterator<value_type, __void_pointer>       const_iterator;
     typedef __list_node_base<value_type, __void_pointer>            __node_base;
     typedef __list_node<value_type, __void_pointer>                 __node;
     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
     typedef allocator_traits<__node_allocator>                       __node_alloc_traits;
     typedef typename __node_alloc_traits::pointer                    __node_pointer;
     typedef typename __node_alloc_traits::pointer                    __node_const_pointer;
+    typedef typename __list_node_pointer_traits<value_type, __void_pointer>::__link_pointer __link_pointer;
+    typedef __link_pointer __link_const_pointer;
     typedef typename __alloc_traits::pointer                         pointer;
     typedef typename __alloc_traits::const_pointer                   const_pointer;
     typedef typename __alloc_traits::difference_type                 difference_type;
 
     typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator;
     typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
 
     __node_base __end_;
     __compressed_pair<size_type, __node_allocator> __size_alloc_;
 
     _LIBCPP_INLINE_VISIBILITY
           size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
     _LIBCPP_INLINE_VISIBILITY
     const size_type& __sz() const _NOEXCEPT
         {return __size_alloc_.first();}
     _LIBCPP_INLINE_VISIBILITY
           __node_allocator& __node_alloc() _NOEXCEPT
           {return __size_alloc_.second();}
     _LIBCPP_INLINE_VISIBILITY
     const __node_allocator& __node_alloc() const _NOEXCEPT
         {return __size_alloc_.second();}
 
-    static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT;
+    static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
 
     __list_imp()
         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
     __list_imp(const allocator_type& __a);
     ~__list_imp();
     void clear() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     bool empty() const _NOEXCEPT {return __sz() == 0;}

 #else
         return const_iterator(__end_.__next_);
 #endif
     }
     _LIBCPP_INLINE_VISIBILITY
     iterator end() _NOEXCEPT
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        return iterator(static_cast<__node_pointer>(
-                pointer_traits<__node_base_pointer>::pointer_to(__end_)), this);
+        return iterator(__end_.__as_link(), this);
 #else
-        return iterator(static_cast<__node_pointer>(
-                      pointer_traits<__node_base_pointer>::pointer_to(__end_)));
+        return iterator(__end_.__as_link());
 #endif
     }
     _LIBCPP_INLINE_VISIBILITY
     const_iterator end() const _NOEXCEPT
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        return const_iterator(static_cast<__node_const_pointer>(
-        pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this);
+        return const_iterator(const_cast<__node_base&>(__end_).__as_link(), this);
 #else
-        return const_iterator(static_cast<__node_const_pointer>(
-        pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))));
+        return const_iterator(const_cast<__node_base&>(__end_).__as_link());
 #endif
     }
 
     void swap(__list_imp& __c)
 #if _LIBCPP_STD_VER >= 14
         _NOEXCEPT;
 #else
         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 
void __move_assign_alloc(__list_imp& __c, false_type)
         _NOEXCEPT
         {}
 };
 
 // Unlink nodes [__f, __l]
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l)
+__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
     _NOEXCEPT
 {
     __f->__prev_->__next_ = __l->__next_;
     __l->__next_->__prev_ = __f->__prev_;
 }
 
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY

 
 template <class _Tp, class _Alloc>
 void
 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
 {
     if (!empty())
     {
         __node_allocator& __na = __node_alloc();
-        __node_pointer __f = __end_.__next_;
-        __node_pointer __l = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_));
+        __link_pointer __f = __end_.__next_;
+        __link_pointer __l = __end_.__as_link();
         __unlink_nodes(__f, __l->__prev_);
         __sz() = 0;
         while (__f != __l)
         {
-            __node_pointer __n = __f;
+            __node_pointer __np = __f->__as_node();
             __f = __f->__next_;
-            __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-            __node_alloc_traits::deallocate(__na, __n, 1);
+            __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+            __node_alloc_traits::deallocate(__na, __np, 1);
         }
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __c_node* __c = __get_db()->__find_c_and_lock(this);
         for (__i_node** __p = __c->end_; __p != __c->beg_; )
         {
             --__p;
             const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
             if (__i->__ptr_ != __l)
_LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
                    this->__node_alloc() == __c.__node_alloc(),
                    "list::swap: Either propagate_on_container_swap must be true"
                    " or the allocators must compare equal");
     using _VSTD::swap;
     __swap_allocator(__node_alloc(), __c.__node_alloc());
     swap(__sz(), __c.__sz());
     swap(__end_, __c.__end_);
     if (__sz() == 0)
-        __end_.__next_ = __end_.__prev_ = __end_.__self();
+        __end_.__next_ = __end_.__prev_ = __end_.__as_link();
     else
-        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self();
+        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__as_link();
     if (__c.__sz() == 0)
-        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self();
+        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__as_link();
     else
-        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self();
+        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__as_link();
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __libcpp_db* __db = __get_db();
     __c_node* __cn1 = __db->__find_c_and_lock(this);
     __c_node* __cn2 = __db->__find_c(&__c);
     std::swap(__cn1->beg_, __cn2->beg_);
     std::swap(__cn1->end_, __cn2->end_);
     std::swap(__cn1->cap_, __cn2->cap_);
     for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
     {
         --__p;
         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
-        if (__i->__ptr_ == static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+        if (__i->__ptr_ == __c.__end_.__as_link())
         {
             __cn2->__add(*__p);
             if (--__cn1->end_ != __p)
                 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
         }
         else
             (*__p)->__c_ = __cn1;
     }
     for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
     {
         --__p;
         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
-        if (__i->__ptr_ == static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_)))
+        if (__i->__ptr_ == __end_.__as_link())
         {
             __cn1->__add(*__p);
             if (--__cn2->end_ != __p)
                 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
         }
         else
             (*__p)->__c_ = __cn2;
     }
     __db->unlock();
 #endif
 }
 
 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
 class _LIBCPP_TYPE_VIS_ONLY list
     : private __list_imp<_Tp, _Alloc>
 {
     typedef __list_imp<_Tp, _Alloc> base;
     typedef typename base::__node              __node;
     typedef typename base::__node_allocator    __node_allocator;
     typedef typename base::__node_pointer      __node_pointer;
     typedef typename base::__node_alloc_traits __node_alloc_traits;
     typedef typename base::__node_base         __node_base;
     typedef typename base::__node_base_pointer __node_base_pointer;
+    typedef typename base::__link_pointer __link_pointer;
 
 public:
     typedef _Tp                                      value_type;
     typedef _Alloc                                   allocator_type;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
     _LIBCPP_INLINE_VISIBILITY
     const_reverse_iterator crend()   const _NOEXCEPT
         {return const_reverse_iterator(begin());}
 
     _LIBCPP_INLINE_VISIBILITY
     reference front()
     {
         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
-        return base::__end_.__next_->__value_;
+        return base::__end_.__next_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     const_reference front() const
     {
         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
-        return base::__end_.__next_->__value_;
+        return base::__end_.__next_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     reference back()
     {
         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
-        return base::__end_.__prev_->__value_;
+        return base::__end_.__prev_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     const_reference back() const
     {
         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
-        return base::__end_.__prev_->__value_;
+        return base::__end_.__prev_->__as_node()->__value_;
     }
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     void push_front(value_type&& __x);
     void push_back(value_type&& __x);
 #ifndef _LIBCPP_HAS_NO_VARIADICS
     template <class... _Args>
        void emplace_front(_Args&&... __args);
#if _LIBCPP_DEBUG_LEVEL >= 2
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
 
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 private:
-    static void __link_nodes  (__node_pointer __p, __node_pointer __f, __node_pointer __l);
-    void __link_nodes_at_front(__node_pointer __f, __node_pointer __l);
-    void __link_nodes_at_back (__node_pointer __f, __node_pointer __l);
+    static void __link_nodes  (__link_pointer __p, __link_pointer __f, __link_pointer __l);
+    void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
+    void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
     iterator __iterator(size_type __n);
     template <class _Comp>
         static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
 
     void __move_assign(list& __c, true_type)
         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
     void __move_assign(list& __c, false_type);
 };
 
 // Link in nodes [__f, __l] just prior to __p
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
 {
     __p->__prev_->__next_ = __f;
     __f->__prev_ = __p->__prev_;
     __p->__prev_ = __l;
     __l->__next_ = __p;
 }
 
 // Link in nodes [__f, __l] at the front of the list
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
 {
-    __f->__prev_ = base::__end_.__self();
+    __f->__prev_ = base::__end_.__as_link();
     __l->__next_ = base::__end_.__next_;
     __l->__next_->__prev_ = __l;
     base::__end_.__next_ = __f;
 }
 
 // Link in nodes [__f, __l] at the front of the list
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes_at_back(__node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
 {
-    __l->__next_ = base::__end_.__self();
+    __l->__next_ = base::__end_.__as_link();
     __f->__prev_ = base::__end_.__prev_;
     __f->__prev_->__next_ = __f;
     base::__end_.__prev_ = __l;
 }
 
 
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
_LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::insert(iterator, x) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
     ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__hold.release()->__as_link(), this);
 #else
-    return iterator(__hold.release());
+    return iterator(__hold.release()->__as_link());
 #endif
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
if (__n > 0)
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get(), this);
+        __r = iterator(__hold->__as_link(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold->__as_link());
 #endif
         __hold.release();
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }
if (__f != __l)
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get(), this);
+        __r = iterator(__hold.get()->__as_link(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold.get()->__as_link());
 #endif
         __hold.release();
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }

 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_front(const value_type& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes_at_front(__nl, __nl);
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_back(const value_type& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_front(value_type&& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::push_back(value_type&& __x)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
 
 #ifndef _LIBCPP_HAS_NO_VARIADICS
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 void
 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 void
 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
 {
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes_at_back(__nl, __nl);
     ++base::__sz();
     __hold.release();
 }
 
 template <class _Tp, class _Alloc>
 template <class... _Args>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::emplace(iterator, args...) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_pointer __nl = __hold.get()->__as_link();
+    __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
+    __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__nl, this);
 #else
-    return iterator(__hold.release());
+    return iterator(__nl);
 #endif
 }
 
 #endif  // _LIBCPP_HAS_NO_VARIADICS
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::insert(iterator, x) called with an iterator not"
         " referring to this list");
 #endif
     __node_allocator& __na = base::__node_alloc();
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
+    __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__nl, this);
 #else
-    return iterator(__hold.release());
+    return iterator(__nl);
 #endif
 }
 
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::pop_front()
 {
     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__next_;
+    __link_pointer __n = base::__end_.__next_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __c_node* __c = __get_db()->__find_c_and_lock(this);
     for (__i_node** __p = __c->end_; __p != __c->beg_; )
     {
         --__p;
         iterator* __i = static_cast<iterator*>((*__p)->__i_);
         if (__i->__ptr_ == __n)
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::pop_back()
 {
     _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__prev_;
+    __link_pointer __n = base::__end_.__prev_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __c_node* __c = __get_db()->__find_c_and_lock(this);
     for (__i_node** __p = __c->end_; __p != __c->beg_; )
     {
         --__p;
         iterator* __i = static_cast<iterator*>((*__p)->__i_);
         if (__i->__ptr_ == __n)
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::erase(const_iterator __p)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::erase(iterator) called with an iterator not"
         " referring to this list");
 #endif
     _LIBCPP_ASSERT(__p != end(),
         "list::erase(iterator) called with a non-dereferenceable iterator");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = __p.__ptr_;
-    __node_pointer __r = __n->__next_;
+    __link_pointer __n = __p.__ptr_;
+    __link_pointer __r = __n->__next_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __c_node* __c = __get_db()->__find_c_and_lock(this);
     for (__i_node** __p = __c->end_; __p != __c->beg_; )
     {
         --__p;
         iterator* __i = static_cast<iterator*>((*__p)->__i_);
         if (__i->__ptr_ == __n)
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__r, this);
 #else
     return iterator(__r);
 #endif
 }
 
 template <class _Tp, class _Alloc>
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
         "list::erase(iterator, iterator) called with an iterator not"
         " referring to this list");
 #endif
     if (__f != __l)
     {
         __node_allocator& __na = base::__node_alloc();
         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
         while (__f != __l)
         {
-            __node_pointer __n = __f.__ptr_;
+            __link_pointer __n = __f.__ptr_;
             ++__f;
             --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __c_node* __c = __get_db()->__find_c_and_lock(this);
             for (__i_node** __p = __c->end_; __p != __c->beg_; )
             {
                 --__p;
                 iterator* __i = static_cast<iterator*>((*__p)->__i_);
                 if (__i->__ptr_ == __n)
                 {
                     (*__p)->__c_ = nullptr;
                     if (--__c->end_ != __p)
                         memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
                 }
             }
             __get_db()->unlock();
 #endif
-            __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-            __node_alloc_traits::deallocate(__na, __n, 1);
+            __node_pointer __np = __n->__as_node();
+            __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+            __node_alloc_traits::deallocate(__na, __np, 1);
         }
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__l.__ptr_, this);
 #else
     return iterator(__l.__ptr_);
 #endif
 }
else if (__n > base::__sz())
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release(), this);
+        iterator __r = iterator(__hold.release()->__as_link(), this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__hold.release()->__as_link());
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }
else if (__n > base::__sz())
         __n -= base::__sz();
         size_type __ds = 0;
         __node_allocator& __na = base::__node_alloc();
         typedef __allocator_destructor<__node_allocator> _Dp;
         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
+        __link_pointer __nl = __hold.release()->__as_link();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release(), this);
+        iterator __r = iterator(__nl, this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__nl);
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (--__n; __n != 0; --__n, ++__e, ++__ds)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
                 __e = iterator(__prev, this);
 #else
                 __e = iterator(__prev);
 #endif
             }
             throw;
         }
 #endif  // _LIBCPP_NO_EXCEPTIONS
-        __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
-                         pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
+        __link_nodes(base::__end_.__as_link(), __r.__ptr_, __e.__ptr_);
         base::__sz() += __ds;
     }
 }
 
 template <class _Tp, class _Alloc>
 void
 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
 {
     _LIBCPP_ASSERT(this != &__c,
                    "list::splice(iterator, list) called with this == &list");
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "list::splice(iterator, list) called with an iterator not"
         " referring to this list");
 #endif
     if (!__c.empty())
     {
-        __node_pointer __f = __c.__end_.__next_;
-        __node_pointer __l = __c.__end_.__prev_;
+        __link_pointer __f = __c.__end_.__next_;
+        __link_pointer __l = __c.__end_.__prev_;
         base::__unlink_nodes(__f, __l);
         __link_nodes(__p.__ptr_, __f, __l);
         base::__sz() += __c.__sz();
         __c.__sz() = 0;
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __libcpp_db* __db = __get_db();
         __c_node* __cn1 = __db->__find_c_and_lock(this);
         __c_node* __cn2 = __db->__find_c(&__c);
         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
-            if (__i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+            if (__i->__ptr_ != __c.__end_.__as_link())
             {
                 __cn1->__add(*__p);
                 (*__p)->__c_ = __cn1;
                 if (--__cn2->end_ != __p)
                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
             }
         }
         __db->unlock();
_LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
         "list::splice(iterator, list, iterator) called with second iterator not"
         " referring to list argument");
     _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
         "list::splice(iterator, list, iterator) called with second iterator not"
         " derefereceable");
 #endif
     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
     {
-        __node_pointer __f = __i.__ptr_;
+        __link_pointer __f = __i.__ptr_;
         base::__unlink_nodes(__f, __f);
         __link_nodes(__p.__ptr_, __f, __f);
         --__c.__sz();
         ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __libcpp_db* __db = __get_db();
         __c_node* __cn1 = __db->__find_c_and_lock(this);
         __c_node* __cn2 = __db->__find_c(&__c);
#endif
     if (__f != __l)
     {
         if (this != &__c)
         {
             size_type __s = _VSTD::distance(__f, __l);
             __c.__sz() -= __s;
             base::__sz() += __s;
         }
-        __node_pointer __first = __f.__ptr_;
+        __link_pointer __first = __f.__ptr_;
         --__l;
-        __node_pointer __last = __l.__ptr_;
+        __link_pointer __last = __l.__ptr_;
         base::__unlink_nodes(__first, __last);
         __link_nodes(__p.__ptr_, __first, __last);
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __libcpp_db* __db = __get_db();
         __c_node* __cn1 = __db->__find_c_and_lock(this);
         __c_node* __cn2 = __db->__find_c(&__c);
         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
         {
             --__p;
             iterator* __j = static_cast<iterator*>((*__p)->__i_);
-            for (__node_pointer __k = __f.__ptr_;
+            for (__link_pointer __k = __f.__ptr_;
                                           __k != __l.__ptr_; __k = __k->__next_)
             {
                 if (__j->__ptr_ == __k)
                 {
                     __cn1->__add(*__p);
                     (*__p)->__c_ = __cn1;
                     if (--__cn2->end_ != __p)
                         memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
if (this != &__c)
             if (__comp(*__f2, *__f1))
             {
                 size_type __ds = 1;
                 iterator __m2 = _VSTD::next(__f2);
                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
                     ;
                 base::__sz() += __ds;
                 __c.__sz() -= __ds;
-                __node_pointer __f = __f2.__ptr_;
-                __node_pointer __l = __m2.__ptr_->__prev_;
+                __link_pointer __f = __f2.__ptr_;
+                __link_pointer __l = __m2.__ptr_->__prev_;
                 __f2 = __m2;
                 base::__unlink_nodes(__f, __l);
                 __m2 = _VSTD::next(__f1);
                 __link_nodes(__f1.__ptr_, __f, __l);
                 __f1 = __m2;
             }
             else
                 ++__f1;
         }
         splice(__e1, __c);
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __libcpp_db* __db = __get_db();
         __c_node* __cn1 = __db->__find_c_and_lock(this);
         __c_node* __cn2 = __db->__find_c(&__c);
         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
-            if (__i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+            if (__i->__ptr_ != __c.__end_.__as_link())
             {
                 __cn1->__add(*__p);
                 (*__p)->__c_ = __cn1;
                 if (--__cn2->end_ != __p)
                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
             }
         }
         __db->unlock();
list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
     switch (__n)
     {
     case 0:
     case 1:
         return __f1;
     case 2:
         if (__comp(*--__e2, *__f1))
         {
-            __node_pointer __f = __e2.__ptr_;
+            __link_pointer __f = __e2.__ptr_;
             base::__unlink_nodes(__f, __f);
             __link_nodes(__f1.__ptr_, __f, __f);
             return __e2;
         }
         return __f1;
     }
     size_type __n2 = __n / 2;
     iterator __e1 = _VSTD::next(__f1, __n2);
     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
     if (__comp(*__f2, *__f1))
     {
         iterator __m2 = _VSTD::next(__f2);
         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
             ;
-        __node_pointer __f = __f2.__ptr_;
-        __node_pointer __l = __m2.__ptr_->__prev_;
+        __link_pointer __f = __f2.__ptr_;
+        __link_pointer __l = __m2.__ptr_->__prev_;
         __r = __f2;
         __e1 = __f2 = __m2;
         base::__unlink_nodes(__f, __l);
         __m2 = _VSTD::next(__f1);
         __link_nodes(__f1.__ptr_, __f, __l);
         __f1 = __m2;
     }
     else
         ++__f1;
     while (__f1 != __e1 && __f2 != __e2)
     {
         if (__comp(*__f2, *__f1))
         {
             iterator __m2 = _VSTD::next(__f2);
             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
                 ;
-            __node_pointer __f = __f2.__ptr_;
-            __node_pointer __l = __m2.__ptr_->__prev_;
+            __link_pointer __f = __f2.__ptr_;
+            __link_pointer __l = __m2.__ptr_->__prev_;
             if (__e1 == __f2)
                 __e1 = __m2;
             __f2 = __m2;
             base::__unlink_nodes(__f, __l);
             __m2 = _VSTD::next(__f1);
             __link_nodes(__f1.__ptr_, __f, __l);
             __f1 = __m2;
         }

 }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
 
 template <class _Tp, class _Alloc>
 bool
 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
 {
-    return __i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_)));
+    return __i->__ptr_ != const_cast<__node_base&>(this->__end_).__as_link();
 }
 
 template <class _Tp, class _Alloc>
 bool
 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
 {
     return !empty() &&  __i->__ptr_ != base::__end_.__next_;
 }