Removed pathological case

[mvels]

Summary

Merge branch 'master' into string-optimize-assign-string

Add basic_string::__assign_str_noalias_external(const value_type* s, size_type n)

This change introduces the __assign_str_noalias_external which is invoked on the slow path from basic_string::operator=(const basic_string&).

The function is optimized for the source never aliassing the destination, the size always being inside the max_size, and have well predicted branches for non pathological assignments, i.e.: short --> long.

Merge branch 'master' into string-optimize-assign-string

Add basic_string::__string_assign_str_noalias_external

This changes adds the __string_assign_str_noalias_external function which is now used by the operator=(const basic_string&) method as a slow path if either of the strings is a long string.

__string_assign_str_noalias_external is optimized for being called from the operator= method: no alias into this, input has terminating zero as s[n], and size does not exceed max size. The branch in the external instantiated code should be well predicted.

libcxx/include/__string

#define _LIBCPP_STRING_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
   _Func(_LIBCPP_FUNC_VIS int basic_string<_CharType>::compare(size_type, size_type, value_type const*, size_type) const) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::operator=(basic_string const&)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::append(value_type const*)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::replace(size_type, size_type, basic_string const&, size_type, size_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>::iterator basic_string<_CharType>::insert(basic_string::const_iterator, value_type)) \
   _Func(_LIBCPP_FUNC_VIS void basic_string<_CharType>::resize(size_type, value_type)) \
   _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::insert(size_type, basic_string const&, size_type, size_type))
 
+#define _LIBCPP_V2_STRING_EXTERN_TEMPLATE_LIST(_Func, _CharType) \
+  _Func(_LIBCPP_FUNC_VIS basic_string<_CharType>& basic_string<_CharType>::__assign_str_noalias_external(value_type const*, size_type))
 
 // char_traits
 
 template <class _CharT>
 struct _LIBCPP_TEMPLATE_VIS char_traits
 {
     typedef _CharT    char_type;
     typedef int       int_type;

libcxx/include/string

size_type __recommend(size_type __s) _NOEXCEPT
         {
         if (__s < __min_cap) return static_cast<size_type>(__min_cap) - 1;
         size_type __guess = __align_it<sizeof(value_type) < __alignment ?
                      __alignment/sizeof(value_type) : 1 > (__s+1) - 1;
         if (__guess == __min_cap) ++__guess;
         return __guess;
         }
 
+    static _LIBCPP_INLINE_VISIBILITY
+    size_type __recommend_cap(size_type __sz) _NOEXCEPT {
+      if (__sz < __min_cap) __sz = __min_cap;
+      return __align_it < sizeof(value_type) < __alignment
+          ? __alignment / sizeof(value_type)
+          : 1 > (__sz + 1);
+    }
+
     inline
     void __init(const value_type* __s, size_type __sz, size_type __reserve);
     inline
     void __init(const value_type* __s, size_type __sz);
     inline
     void __init(size_type __n, value_type __c);
 
     // Identical to __init(s, sz), except that this function is always
#endif  // _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
     __init(_ForwardIterator __first, _ForwardIterator __last);
 
     void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                    size_type __n_copy,  size_type __n_del,     size_type __n_add = 0);
     void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                size_type __n_copy,  size_type __n_del,
                                size_type __n_add, const value_type* __p_new_stuff);
 
+    // Slow path for non-aliased string assignment. Requires:
+    //   `__s` has a terminating zero at __s[__sz]
+    //   `__s` does not reference (alias) any content in `this`
+    basic_string& __assign_str_noalias_external(const value_type* __s, size_type __sz);
+
     _LIBCPP_INLINE_VISIBILITY
     void __erase_to_end(size_type __pos);
 
     _LIBCPP_INLINE_VISIBILITY
     void __copy_assign_alloc(const basic_string& __str)
         {__copy_assign_alloc(__str, integral_constant<bool,
                       __alloc_traits::propagate_on_container_copy_assignment::value>());}
 

 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__erase_c(this);
 #endif
     if (__is_long())
         __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
+basic_string<_CharT, _Traits, _Allocator>&
+basic_string<_CharT, _Traits, _Allocator>::__assign_str_noalias_external(
+    const value_type* __s, size_type __sz) {
+  pointer __p;
+  size_type __cap;
+  if (!__is_long()) {
+    if (__sz < __min_cap) {
+      traits_type::copy(_VSTD::__to_address(__get_short_pointer()), __s, __sz + 1);
+      __set_short_size(__sz);
+      return *this;
+    }
+    __cap = __recommend_cap(__sz);
+    __p = __alloc_traits::allocate(__alloc(), __cap);
+  } else {
+    __cap = __get_long_cap();
+    __p = __get_long_pointer();
+    if (__sz >= __cap) {
+      size_type __new_cap = __recommend_cap(__sz);
+      pointer __new_p = __alloc_traits::allocate(__alloc(), __new_cap);
+      __alloc_traits::deallocate(__alloc(), __p, __cap);
+      __p = __new_p;
+      __cap = __new_cap;
+    }
+  }
+  traits_type::copy(_VSTD::__to_address(__p), __s, __sz + 1);
+  __set_long_pointer(__p);
+  __set_long_size(__sz);
+  __set_long_cap(__cap);
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
     (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
      size_type __n_copy,  size_type __n_del,     size_type __n_add, const value_type* __p_new_stuff)
 {
     size_type __ms = max_size();
     if (__delta_cap > __ms - __old_cap - 1)
         this->__throw_length_error();

 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
 {
     if (this != &__str)
     {
         __copy_assign_alloc(__str);
         const bool __str_is_long = __str.__is_long(); // Force single branch
         if (__is_long() || __str_is_long) {
-          return assign(__str.data(), __str.size());
+          return __assign_str_noalias_external(__str.data(), __str.size());
         }
         __r_.first().__r = __str.__r_.first().__r;
     }
     return *this;
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 

libcxx/src/string.cpp

 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template class _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS __basic_string_common<true>;
 
 _LIBCPP_STRING_EXTERN_TEMPLATE_LIST(_LIBCPP_EXTERN_TEMPLATE_DEFINE, char)
 _LIBCPP_STRING_EXTERN_TEMPLATE_LIST(_LIBCPP_EXTERN_TEMPLATE_DEFINE, wchar_t)
 
+_LIBCPP_V2_STRING_EXTERN_TEMPLATE_LIST(_LIBCPP_EXTERN_TEMPLATE_DEFINE, char)
+_LIBCPP_V2_STRING_EXTERN_TEMPLATE_LIST(_LIBCPP_EXTERN_TEMPLATE_DEFINE, wchar_t)
+
 template
     string
     operator+<char, char_traits<char>, allocator<char> >(char const*, string const&);
 
 namespace
 {
 
 template<typename T>