[libcxx] Fix undefined behavior in forward_list

Summary:
This patch is similar to the <list> fix but it has a few differences. This patch doesn't use a `__link_pointer` typedef because we don't need to change the linked list pointers because `forward_list` never stores a  `__forward_begin_node` in the linked list itself. 

The issue with `forward_list` is that the iterators store pointers to `__forward_list_node` and not `__forward_begin_node`. This is incorrect because `before_begin()` and `cbefore_begin()` return iterators that point to a `__forward_begin_node`. This means we incorrectly downcast the `__forward_begin_node` pointer to a `__node_pointer`. This downcast itself is sometimes UB but it cannot be safely removed until ABI v2. The more common cause of UB is when we deference the downcast pointer. (for example `__ptr_->__next_`). This can be fixed without an ABI break by upcasting `__ptr_` before accessing it.

The fix is as follows:

1. Introduce a `__iter_node_pointer` typedef that works  similar to `__link_pointer` in the last patch. In ABI v2 it is always a typedef for `__begin_node_pointer`.
2. Change the `__before_begin()` method to return the correct pointer type (`__begin_node_pointer`),
    Previously it incorrectly downcasted  the  `__forward_begin_node` to a `__node_pointer`  so it could be used to constructor the iterator types.
3. Change `__forward_list_iterator` and `__forward_list_const_iterator`  in the following way:
    1. Change `__node_pointer __ptr_;` member to  have the `__iter_node_pointer` type instead. 
    2. Add additional private constructors that accept `__begin_node_pointer` in addition to `__node_pointer` and then correctly cast them to the stored `__iter_node_pointer` type. 
    3. Add  `__get_begin()` and `__get_node_unchecked()` accessor methods that correctly cast `__ptr_` to the expected pointer type. `__get_begin()` is always safe to use and should be 
       preferred. `__get_node_unchecked()` can only be used on a deferencible iterator.
4. Replace direct access to `__forward_list_iterator::__ptr_`  with the safe accessor methods.
  


Reviewers: mclow.lists, EricWF

Subscribers: cfe-commits

Differential Revision: http://reviews.llvm.org/D15836

llvm-svn: 258888

1 files changed, 53 insertions, 0 deletions

diff --git a/libcxx/test/std/containers/sequences/forwardlist/incomplete.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/incomplete.pass.cpp
new file mode 100644
index 00000000000..df273449eac
--- /dev/null
+++ b/libcxx/test/std/containers/sequences/forwardlist/incomplete.pass.cpp
@@ -0,0 +1,53 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <forward_list>
+
+// forward_list()
+// forward_list::iterator()
+// forward_list::const_iterator()
+
+#include <forward_list>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+struct A {
+  std::forward_list<A> d;
+  std::forward_list<A>::iterator it;
+  std::forward_list<A>::const_iterator it2;
+};
+
+#if TEST_STD_VER >= 11
+struct B {
+  typedef std::forward_list<B, min_allocator<B>> FList;
+  FList d;
+  FList::iterator it;
+  FList::const_iterator it2;
+};
+#endif
+
+int main()
+{
+  {
+    A a;
+    assert(a.d.empty());
+    a.it = a.d.begin();
+    a.it2 = a.d.cbefore_begin();
+  }
+#if TEST_STD_VER >= 11
+  {
+    B b;
+    assert(b.d.empty());
+    b.it = b.d.begin();
+    b.it2 = b.d.cbefore_begin();
+  }
+#endif
+}