[libcxx] Optimize vectors construction of trivial types from an iterator range with const-ness mismatch.

We already have a specialization that will use memcpy for construction
of trivial types from an iterator range like

    std::vector<int>(int *, int *);

But if we have const-ness mismatch like

    std::vector<int>(const int *, const int *);

we would use a slow path that copies each element individually. This change
enables the optimal specialization for const-ness mismatch. Fixes PR37574.

Contributions to the patch are made by Arthur O'Dwyer, Louis Dionne.

rdar://problem/40485845

Reviewers: mclow.lists, EricWF, ldionne, scanon

Reviewed By: ldionne

Subscribers: christof, ldionne, howard.hinnant, cfe-commits

Differential Revision: https://reviews.llvm.org/D48342

2 files changed, 48 insertions, 9 deletions

diff --git a/libcxx/include/memory b/libcxx/include/memory
index b012f5bce32..93f04c6faff 100644
--- a/libcxx/include/memory
+++ b/libcxx/include/memory
@@ -1502,6 +1502,12 @@ struct __alloc_traits_difference_type<_Alloc, _Ptr, true>
     typedef typename _Alloc::difference_type type;
 };
 
+template <class _Tp>
+struct __is_default_allocator : false_type {};
+
+template <class _Tp>
+struct __is_default_allocator<_VSTD::allocator<_Tp> > : true_type {};
+
 template <class _Alloc>
 struct _LIBCPP_TEMPLATE_VIS allocator_traits
 {
@@ -1615,7 +1621,7 @@ struct _LIBCPP_TEMPLATE_VIS allocator_traits
         static
         typename enable_if
         <
-            (is_same<allocator_type, allocator<_Tp> >::value
+            (__is_default_allocator<allocator_type>::value
                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
              is_trivially_move_constructible<_Tp>::value,
             void
@@ -1640,23 +1646,25 @@ struct _LIBCPP_TEMPLATE_VIS allocator_traits
                 construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);
         }
 
-    template <class _Tp>
+    template <class _SourceTp, class _DestTp,
+              class _RawSourceTp = typename remove_const<_SourceTp>::type,
+              class _RawDestTp = typename remove_const<_DestTp>::type>
         _LIBCPP_INLINE_VISIBILITY
         static
         typename enable_if
         <
-            (is_same<allocator_type, allocator<_Tp> >::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
+            is_trivially_move_constructible<_DestTp>::value &&
+            is_same<_RawSourceTp, _RawDestTp>::value &&
+            (__is_default_allocator<allocator_type>::value ||
+             !__has_construct<allocator_type, _DestTp*, _SourceTp&>::value),
             void
         >::type
-        __construct_range_forward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
+        __construct_range_forward(allocator_type&, _SourceTp* __begin1, _SourceTp* __end1, _DestTp*& __begin2)
         {
-            typedef typename remove_const<_Tp>::type _Vp;
             ptrdiff_t _Np = __end1 - __begin1;
             if (_Np > 0)
             {
-                _VSTD::memcpy(const_cast<_Vp*>(__begin2), __begin1, _Np * sizeof(_Tp));
+                _VSTD::memcpy(const_cast<_RawDestTp*>(__begin2), __begin1, _Np * sizeof(_DestTp));
                 __begin2 += _Np;
             }
         }
@@ -1679,7 +1687,7 @@ struct _LIBCPP_TEMPLATE_VIS allocator_traits
         static
         typename enable_if
         <
-            (is_same<allocator_type, allocator<_Tp> >::value
+            (__is_default_allocator<allocator_type>::value
                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
              is_trivially_move_constructible<_Tp>::value,
             void
diff --git a/libcxx/test/std/containers/sequences/vector/vector.cons/construct_iter_iter.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.cons/construct_iter_iter.pass.cpp
index 21a7df4a7f0..60fe2899ac2 100644
--- a/libcxx/test/std/containers/sequences/vector/vector.cons/construct_iter_iter.pass.cpp
+++ b/libcxx/test/std/containers/sequences/vector/vector.cons/construct_iter_iter.pass.cpp
@@ -146,9 +146,40 @@ void test_ctor_under_alloc() {
 #endif
 }
 
+// Initialize a vector with a different value type.
+void test_ctor_with_different_value_type() {
+  {
+    // Make sure initialization is performed with each element value, not with
+    // a memory blob.
+    float array[3] = {0.0f, 1.0f, 2.0f};
+    std::vector<int> v(array, array + 3);
+    assert(v[0] == 0);
+    assert(v[1] == 1);
+    assert(v[2] == 2);
+  }
+  struct X { int x; };
+  struct Y { int y; };
+  struct Z : X, Y { int z; };
+  {
+    Z z;
+    Z *array[1] = { &z };
+    // Though the types Z* and Y* are very similar, initialization still cannot
+    // be done with `memcpy`.
+    std::vector<Y*> v(array, array + 1);
+    assert(v[0] == &z);
+  }
+  {
+    // Though the types are different, initialization can be done with `memcpy`.
+    int32_t array[1] = { -1 };
+    std::vector<uint32_t> v(array, array + 1);
+    assert(v[0] == 4294967295);
+  }
+}
+
 
 int main() {
   basic_test_cases();
   emplaceable_concept_tests(); // See PR34898
   test_ctor_under_alloc();
+  test_ctor_with_different_value_type();
 }