[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

204

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 ↗

(On Diff #42612)

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/list

 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
-        __base_pointer;
+        __node_base_pointer;
+    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
+        __node_pointer;
+    __node_base_pointer __prev_;
+    __node_base_pointer __next_;
 
-    pointer __prev_;
-    pointer __next_;
+#if _LIBCPP_ABI_VERSION == 1 && !defined(_LIBCPP_ABI_UNSTABLE)
+    static_assert(
+        sizeof(__node_base_pointer) == sizeof(__node_pointer) &&
+        __alignof__(__node_base_pointer) == __alignof__(__node_pointer),
+        "The ABI of std::list was broken by http://reviews.llvm.org/D12299. "
+        "Please report this issue at llvm.org/bugs"
+    );
+#endif
 
     _LIBCPP_INLINE_VISIBILITY
-    __list_node_base() : __prev_(__self()), __next_(__self()) {}
+    __list_node_base() : __prev_(__as_base()), __next_(__as_base()) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    pointer __self()
-    {
-        return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this));
+    __node_base_pointer __as_base() {
+        return pointer_traits<__node_base_pointer>::pointer_to(*this);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __as_node() {
+        return static_cast<__node_pointer>(__as_base());
     }
 };
 

 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 typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
+        __node_base_pointer;
 
-    __node_pointer __ptr_;
+    __node_base_pointer __ptr_;
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
+    explicit __list_iterator(__node_base_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(__node_base_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
 

         _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

         _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

 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 typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
+        __node_base_pointer;
 
-    __node_pointer __ptr_;
+    __node_base_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(__node_base_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(__node_base_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
     template<class, class> friend class list;

         _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

         _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

     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(__node_base_pointer __f, __node_base_pointer __l) _NOEXCEPT;
+    static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT {
+        return __unlink_nodes(__f->__as_base(), __l->__as_base());
+    }
 
     __list_imp()
         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);

     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_base(), this);
 #else
-        return iterator(static_cast<__node_pointer>(
-                      pointer_traits<__node_base_pointer>::pointer_to(__end_)));
+        return iterator(__end_.__as_base());
 #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_base(), 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_base());
 #endif
     }
 

 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(__node_base_pointer __f, __node_base_pointer __l)
     _NOEXCEPT
 {
     __f->__prev_->__next_ = __l->__next_;

     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_));
+        __node_base_pointer __f = __end_.__next_;
+        __node_base_pointer __l = __end_.__as_base();
         __unlink_nodes(__f, __l->__prev_);
         __sz() = 0;
         while (__f != __l)
         {
-            __node_pointer __n = __f;
+            __node_pointer __n = __f->__as_node();
             __f = __f->__next_;
             __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
             __node_alloc_traits::deallocate(__na, __n, 1);

     swap(__sz(), __c.__sz());
     swap(__end_, __c.__end_);
     if (__sz() == 0)
-        __end_.__next_ = __end_.__prev_ = __end_.__self();
+        __end_.__next_ = __end_.__prev_ = __end_.__as_base();
     else
-        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self();
+        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__as_base();
     if (__c.__sz() == 0)
-        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self();
+        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__as_base();
     else
-        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self();
+        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__as_base();
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __libcpp_db* __db = __get_db();

     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

 #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  (__node_base_pointer __p, __node_base_pointer __f, __node_base_pointer __l);
+    void __link_nodes_at_front(__node_base_pointer __f, __node_base_pointer __l);
+    void __link_nodes_at_front(__node_pointer __f, __node_pointer __l) {
+        return __link_nodes_at_front(__f->__as_base(), __l->__as_base());
+    }
+    void __link_nodes_at_back (__node_base_pointer __f, __node_base_pointer __l);
+    void __link_nodes_at_back(__node_pointer __f, __node_pointer __l) {
+        return __link_nodes_at_back(__f->__as_base(), __l->__as_base());
+    }
     iterator __iterator(size_type __n);
     template <class _Comp>
         static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);

 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(__node_base_pointer __p, __node_base_pointer __f, __node_base_pointer __l)
 {
     __p->__prev_->__next_ = __f;
     __f->__prev_ = __p->__prev_;

 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(__node_base_pointer __f, __node_base_pointer __l)
 {
-    __f->__prev_ = base::__end_.__self();
+    __f->__prev_ = base::__end_.__as_base();
     __l->__next_ = base::__end_.__next_;
     __l->__next_->__prev_ = __l;
     base::__end_.__next_ = __f;

 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(__node_base_pointer __f, __node_base_pointer __l)
 {
-    __l->__next_ = base::__end_.__self();
+    __l->__next_ = base::__end_.__as_base();
     __f->__prev_ = base::__end_.__prev_;
     __f->__prev_->__next_ = __f;
     base::__end_.__prev_ = __l;

         __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;

             {
                 __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();
             }

             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __node_base_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);
+                __e = iterator(__prev->__as_base(), this);
 #else
-                __e = iterator(__prev);
+                __e = iterator(__prev->__as_base());
 #endif
             }
             throw;

         __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_base(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold.get()->__as_base());
 #endif
         __hold.release();
         iterator __e = __r;

             {
                 __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_base();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }

             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __node_base_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2

     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_nodes(__p.__ptr_, __hold.get()->__as_base(), __hold.get()->__as_base());
     ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__hold.release()->__as_base(), this);
 #else
-    return iterator(__hold.release());
+    return iterator(__hold.release()->__as_base());
 #endif
 }
 

     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_nodes(__p.__ptr_, __hold.get()->__as_base(), __hold.get()->__as_base());
     ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__hold.release()->__as_base(), this);
 #else
-    return iterator(__hold.release());
+    return iterator(__hold.release()->__as_base());
 #endif
 }
 

 {
     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__next_;
+    __node_pointer __n = base::__end_.__next_->__as_node();
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2

 {
     _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__prev_;
+    __node_pointer __n = base::__end_.__prev_->__as_node();
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2

     _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_;
-    base::__unlink_nodes(__n, __n);
+    __node_pointer __n = __p.__ptr_->__as_node();
+    __node_base_pointer __r = __n->__next_;
+    base::__unlink_nodes(__n->__as_base(), __n->__as_base());
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __c_node* __c = __get_db()->__find_c_and_lock(this);

         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
         while (__f != __l)
         {
-            __node_pointer __n = __f.__ptr_;
+            __node_pointer __n = __f.__ptr_->__as_node();
             ++__f;
             --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2

         __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_base(), this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__hold.release()->__as_base());
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS

             {
                 __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_base();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }

             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __node_base_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2

         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release(), this);
+        iterator __r = iterator(__hold.release()->__as_base(), this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__hold.release()->__as_base());
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS

             {
                 __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();
             }

             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __node_base_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2

             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_base(), __r.__ptr_, __e.__ptr_);
         base::__sz() += __ds;
     }
 }

 #endif
     if (!__c.empty())
     {
-        __node_pointer __f = __c.__end_.__next_;
-        __node_pointer __l = __c.__end_.__prev_;
+        __node_base_pointer __f = __c.__end_.__next_;
+        __node_base_pointer __l = __c.__end_.__prev_;
         base::__unlink_nodes(__f, __l);
         __link_nodes(__p.__ptr_, __f, __l);
         base::__sz() += __c.__sz();

 #endif
     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
     {
-        __node_pointer __f = __i.__ptr_;
+        __node_base_pointer __f = __i.__ptr_;
         base::__unlink_nodes(__f, __f);
         __link_nodes(__p.__ptr_, __f, __f);
         --__c.__sz();

             __c.__sz() -= __s;
             base::__sz() += __s;
         }
-        __node_pointer __first = __f.__ptr_;
+        __node_base_pointer __first = __f.__ptr_;
         --__l;
-        __node_pointer __last = __l.__ptr_;
+        __node_base_pointer __last = __l.__ptr_;
         base::__unlink_nodes(__first, __last);
         __link_nodes(__p.__ptr_, __first, __last);
 #if _LIBCPP_DEBUG_LEVEL >= 2

                     ;
                 base::__sz() += __ds;
                 __c.__sz() -= __ds;
-                __node_pointer __f = __f2.__ptr_;
-                __node_pointer __l = __m2.__ptr_->__prev_;
+                __node_base_pointer __f = __f2.__ptr_;
+                __node_base_pointer __l = __m2.__ptr_->__prev_;
                 __f2 = __m2;
                 base::__unlink_nodes(__f, __l);
                 __m2 = _VSTD::next(__f1);

     case 2:
         if (__comp(*--__e2, *__f1))
         {
-            __node_pointer __f = __e2.__ptr_;
+            __node_base_pointer __f = __e2.__ptr_;
             base::__unlink_nodes(__f, __f);
             __link_nodes(__f1.__ptr_, __f, __f);
             return __e2;

         iterator __m2 = _VSTD::next(__f2);
         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
             ;
-        __node_pointer __f = __f2.__ptr_;
-        __node_pointer __l = __m2.__ptr_->__prev_;
+        __node_base_pointer __f = __f2.__ptr_;
+        __node_base_pointer __l = __m2.__ptr_->__prev_;
         __r = __f2;
         __e1 = __f2 = __m2;
         base::__unlink_nodes(__f, __l);

             iterator __m2 = _VSTD::next(__f2);
             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
                 ;
-            __node_pointer __f = __f2.__ptr_;
-            __node_pointer __l = __m2.__ptr_->__prev_;
+            __node_base_pointer __f = __f2.__ptr_;
+            __node_base_pointer __l = __m2.__ptr_->__prev_;
             if (__e1 == __f2)
                 __e1 = __m2;
             __f2 = __m2;