Remove undefined behavior from list::push_back/front, emplace_back/front.

[mclow.lists]

Summary

This is an attempt to fix http://llvm.org/bugs/show_bug.cgi?id=18488, where std::list shows undefined behavior by casting a pointer to a list_node_base to a list_node.

I have added two private routines to list: link_nodes_at_front and link_nodes_at_back, to deal with these cases.

For simplicity, I added a method self to list_node_base, because that expression was used all over the place.

This passes all tests for C++03/11/14, and with ASAN. However, the undefined behavior was observed only with gcc 4.7.2, which I don't have. I'll work on getting that set up.

Also, I am not 100% sure that there isn't a similar set of UB lurking in the insert* routines.

[awi]

Well, ehm, let's start with the good news: this patch actually solves the example main.cpp that I added to the bug report on January 15th. And it seems to me to be a valid fix for the functions push_front(), push_back(), emplace_front(), and emplace_back().

Here's the bad news: Unfortunately, this patch doesn't solve the actual problem that std::list has: The pointers in list_node_base still have the type pointer to list_node, although they can point to the anchor node which is not a list_node. The same is true for the ptr_ member variables in list_iterator and list_const_iterator. This leads to undefined behaviour whenever these pointers are dereferenced although they currently point to the anchor node, even if they are only dereferenced to access prev_ or next_.

I've slightly changed my example file to use splice() instead of push_front(). And then the described problem reappears:
{F50161}

Please note that I've used a more recent compiler this time: g++ (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1. Please note further, that the patch I have proposed on February 28th (in the bug entry, because I didn't know about phabricator) does fix the problem for main2.cpp, too.

[mclow.lists]

There are other suggested fixes for this problem, and this has gotten stale.

include/list

     pointer __next_;
 
     _LIBCPP_INLINE_VISIBILITY
-    __list_node_base()
-        : __prev_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this))),
-          __next_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this)))
-          {}
+    __list_node_base() : __prev_(__self()), __next_(__self()) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    pointer __self()
+    {
+      return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this));
+    }
 };
 
 template <class _Tp, class _VoidPtr>

     swap(__sz(), __c.__sz());
     swap(__end_, __c.__end_);
     if (__sz() == 0)
-        __end_.__next_ = __end_.__prev_ = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_));
+        __end_.__next_ = __end_.__prev_ = __end_.__self();
     else
-        __end_.__prev_->__next_ = __end_.__next_->__prev_
-                                = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_));
+        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self();
     if (__c.__sz() == 0)
-        __c.__end_.__next_ = __c.__end_.__prev_
-                           = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
+        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self();
     else
-        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_
-                                    = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
+        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self();
+
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __libcpp_db* __db = __get_db();
     __c_node* __cn1 = __db->__find_c_and_lock(this);

 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 private:
-    static void __link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l);
+    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);
     iterator __iterator(size_type __n);
     template <class _Comp>
         static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);

     __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)
+{
+  __f->__prev_ = base::__end_.__self();
+  __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)
+{
+  __l->__next_ = base::__end_.__self();
+  __f->__prev_ = base::__end_.__prev_;
+  __f->__prev_->__next_ = __f;
+  base::__end_.__prev_ = __l;
+}
+
+
+template <class _Tp, class _Alloc>
+inline _LIBCPP_INLINE_VISIBILITY
 typename list<_Tp, _Alloc>::iterator
 list<_Tp, _Alloc>::__iterator(size_type __n)
 {

     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(base::__end_.__next_, __hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

     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(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
-                         pointer_to(base::__end_)), __hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

     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(base::__end_.__next_, __hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

     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(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
-                         pointer_to(base::__end_)), __hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

     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(base::__end_.__next_, __hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

     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(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
-                         pointer_to(base::__end_)), __hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get(), __hold.get());
     ++base::__sz();
     __hold.release();
 }

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