Allow deque to handle incomplete types

[eugenis]

include/deque

288

This still requires complete type of _ValueType at deque instantiation.

[rsmith]

include/deque

288

This requires _ValueType to be complete when deque::iterator is instantiated, not when deque is instantiated. It's easy enough to remove this member, but that patch would be more intrusive, and it's not necessary to support the guarantees that N4510 provides. This patch passes all libc++ test cases with and without _LIBCPP_NEW_DEQUE_ABI defined, and is sufficient to support this:

#include <deque>
struct X {
  std::deque<X> dx;
};

[rsmith]

Turns out it's not actually invasive to support completing the iterator type with an incomplete value type.

[eugenis]

Add a test.

[eugenis]

.

[eugenis]

Review please?
This version is way simpler than the last one, and does not have ABI issues.

[eugenis]

ping

[eugenis]

Any opinions?

[eugenis]

ping

[EricWF]

@eugenis: Sorry for the long delay and multiple pings.

I don't feel comfortable adopting ABI changes until libc++ has a concrete plan for adopting, managing and testing these changes.

@mclow.lists proposed a method for managing these changes a while ago but it hasn't moved forward.
(see http://clang-developers.42468.n3.nabble.com/Proposal-Managing-ABI-changes-in-libc-td4042799.html)

What I want to avoid creating a disjoint set preprocessor macros that change the libc++ ABI. Until we have an idea about how to manage these changes I don't know what to do with this patch.

I am very sorry and thanks for the patch. Hopefully we will figure something out soon.

[eugenis]

Thanks for your comment!

That thread you point to seems to end with people agreeing with Chandler's plan. Could you update it please if you have any concerns?

This patch seem to be in line with that plan in general, modulo the preprocessor macro name, and the fact that the high-level version macros remain unimplemented. Would you like that implementation to be done first?

[eugenis]

Using new ABI version macros to enable this feature in unstable or future ABI only.
PTAL.

[EricWF]

For the most part this looks good. I'm a touch concerned though about the changes to the static initialization. The initializer is moved from within the function body to outside it. Could you have somebody confirm this won't affect the existing ABI?

include/__config

34

I think we need a short explanation of ever option added here. In this case could you just link to the bug report and a short explanaition?

ex.

// Fix deques iterator type in order to support incomplete types. See http://llvm.org/bugs/...
#define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE

include/deque

270–278

Please leave a note here explaining why the template parameter was kept even though its unused.

test/std/containers/sequences/deque/deque.cons/incomplete.pass.cpp

9 ↗

(On Diff #37310)

This test needs to go into test/libcxx not test/std because it's testing libc++ implementation details and not standard specified behavior.

[eugenis]

In D10677#266595, @EricWF wrote:

For the most part this looks good. I'm a touch concerned though about the changes to the static initialization. The initializer is moved from within the function body to outside it. Could you have somebody confirm this won't affect the existing ABI?

I'm pretty sure it only affects template evaluation order, and does not change the mangling of any name.

[EricWF]

I'm pretty sure it only affects template evaluation order, and does not

change the mangling of any name.

I agree it doesn't change the mangling of any name. I just want to make
sure that moving the initializer won't result in incompatible code gen.
I'm sure I'm insane for being concerned about this, but I just want
somebody to tell me I'm actually insane. It would make me feel better :)

Sorry
/Eric

[eugenis]

What kind of confirmation are you looking for?

I've compiled the following code with 2 versions of <deque>: one as in this review, another the same but with __block_size initializers moved back into respective classes. Resulting object files are identical.

#include <deque>

int main() {

std::deque<int> d;
d.push_back(1);
d.push_back(2);
for (auto x : d) (void)x;
return d.size();

}

[eugenis]

Hi Eric,

could you please clarify what exactly you are looking for here?

[EricWF]

I think I've cleared up my own confusion. LGTM.

[eugenis]

Thanks!
Landed as r252350.

include/__config

 
 #define _LIBCPP_VERSION 3800
 
 #ifndef _LIBCPP_ABI_VERSION
 #define _LIBCPP_ABI_VERSION 1
 #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
 #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/deque

 
 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
               __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
               __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 
+template <class _ValueType, class _DiffType>
+struct __deque_block_size {
+  static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
+};
+
 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
-          class _DiffType, _DiffType _BlockSize>
+          class _DiffType, _DiffType _BS =
+#ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
+// Keep template parameter to avoid changing all template declarations thoughout
+// this file.
+                               0
+#else
+                               __deque_block_size<_ValueType, _DiffType>::value
+#endif
+          >
 class _LIBCPP_TYPE_VIS_ONLY __deque_iterator
 {
     typedef _MapPointer __map_iterator;
 public:
     typedef _Pointer  pointer;
     typedef _DiffType difference_type;
 private:
     __map_iterator __m_iter_;
     pointer        __ptr_;
 
-    static const difference_type __block_size = _BlockSize;
+    static const difference_type __block_size;
 public:
     typedef _ValueType                  value_type;
     typedef random_access_iterator_tag  iterator_category;
     typedef _Reference                  reference;
 
     _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
      : __m_iter_(nullptr), __ptr_(nullptr)
 #endif
      {}
 
     template <class _Pp, class _Rp, class _MP>
     _LIBCPP_INLINE_VISIBILITY
-    __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, __block_size>& __it,
+    __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,
                 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT
         : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}
 
     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}
     _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}
 
     _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++()
     {
template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
               class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
     friend
     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
     move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
                   __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
                   __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
 };
 
+template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
+          class _DiffType, _DiffType _BlockSize>
+const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
+                                 _DiffType, _BlockSize>::__block_size =
+    __deque_block_size<_ValueType, _DiffType>::value;
+
 // copy
 
 template <class _RAIter,
           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 copy(_RAIter __f,
      _RAIter __l,
      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 {
     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
     while (__f != __l)
     {
         pointer __rb = __r.__ptr_;
-        pointer __re = *__r.__m_iter_ + _B2;
+        pointer __re = *__r.__m_iter_ + __block_size;
         difference_type __bs = __re - __rb;
         difference_type __n = __l - __f;
         _RAIter __m = __l;
         if (__n > __bs)
         {
             __n = __bs;
             __m = __f + __n;
         }
         _VSTD::copy(__f, __m, __rb);
         __f = __m;
         __r += __n;
     }
     return __r;
 }
 
 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
           class _OutputIterator>
 _OutputIterator
 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
      _OutputIterator __r)
 {
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + _B1;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         __r = _VSTD::copy(__fb, __fe, __r);
         __n -= __bs;
         __f += __bs;
     }
     return __r;
 }
 
 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 {
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + _B1;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         __r = _VSTD::copy(__fb, __fe, __r);
         __n -= __bs;

 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 move(_RAIter __f,
      _RAIter __l,
      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
      typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*)
 {
     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
     typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
     while (__f != __l)
     {
         pointer __rb = __r.__ptr_;
-        pointer __re = *__r.__m_iter_ + _B2;
+        pointer __re = *__r.__m_iter_ + __block_size;
         difference_type __bs = __re - __rb;
         difference_type __n = __l - __f;
         _RAIter __m = __l;
         if (__n > __bs)
         {
             __n = __bs;
             __m = __f + __n;
         }
         _VSTD::move(__f, __m, __rb);
         __f = __m;
         __r += __n;
     }
     return __r;
 }
 
 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
           class _OutputIterator>
 _OutputIterator
 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
      _OutputIterator __r)
 {
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + _B1;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         __r = _VSTD::move(__fb, __fe, __r);
         __n -= __bs;
         __f += __bs;
     }
     return __r;
 }
 
 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
           class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
      __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
      __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
 {
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
     typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
+    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
     difference_type __n = __l - __f;
     while (__n > 0)
     {
         pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + _B1;
+        pointer __fe = *__f.__m_iter_ + __block_size;
         difference_type __bs = __fe - __fb;
         if (__bs > __n)
         {
             __bs = __n;
             __fe = __fb + __bs;
         }
         __r = _VSTD::move(__fb, __fe, __r);
         __n -= __bs;
protected:
     typedef allocator_traits<allocator_type>         __alloc_traits;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
     typedef typename __alloc_traits::size_type       size_type;
     typedef typename __alloc_traits::difference_type difference_type;
     typedef typename __alloc_traits::pointer         pointer;
     typedef typename __alloc_traits::const_pointer   const_pointer;
 
-    static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16;
+    static const difference_type __block_size;
 
     typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;
     typedef allocator_traits<__pointer_allocator>        __map_traits;
     typedef typename __map_traits::pointer               __map_pointer;
     typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;
     typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
     typedef __split_buffer<pointer, __pointer_allocator> __map;
 
     typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
-                             difference_type, __block_size>    iterator;
+                             difference_type>    iterator;
     typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
-                             difference_type, __block_size>    const_iterator;
+                             difference_type>    const_iterator;
 
     __map __map_;
     size_type __start_;
     __compressed_pair<size_type, allocator_type> __size_;
 
     iterator       begin() _NOEXCEPT;
     const_iterator begin() const _NOEXCEPT;
     iterator       end() _NOEXCEPT;
void __move_assign_alloc(__deque_base& __c, true_type)
         }
 
     _LIBCPP_INLINE_VISIBILITY
     void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT
         {}
 };
 
 template <class _Tp, class _Allocator>
+const typename __deque_base<_Tp, _Allocator>::difference_type
+    __deque_base<_Tp, _Allocator>::__block_size =
+        __deque_block_size<value_type, difference_type>::value;
+
+template <class _Tp, class _Allocator>
 bool
 __deque_base<_Tp, _Allocator>::__invariants() const
 {
     if (!__map_.__invariants())
         return false;
     if (__map_.size() >= size_type(-1) / __block_size)
         return false;
     for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();

test/libcxx/containers/sequences/deque/incomplete.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     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.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// deque()
+// deque::iterator()
+
+#define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
+#include <deque>
+#include <cassert>
+
+struct A {
+  std::deque<A> d;
+  std::deque<A>::iterator it;
+  std::deque<A>::reverse_iterator it2;
+};
+
+int main()
+{
+  A a;
+  assert(a.d.size() == 0);
+  a.it = a.d.begin();
+  a.it2 = a.d.rend();
+}