[libc++] Remove recursion in basic_string::insert(const_iterator, ForwardIterator, ForwardIterator)

[philnik]

Summary

__addr_in_range is a non-constexpr function, so we can't call it during constant evaluation.

[miscco]

That was one of the things that pained me the most. We should really have something like __builtin_ranges_overlap without all the UB

[• Quuxplusone]

I think this code looks correct enough, but it would be a lot less scary if you could just make __addr_in_range a non-constexpr function, instead of having it "lie" during constexpr evaluation and get us into infinite loops. E.g.:

if (__libcpp_is_constant_evaluated() || !__string_is_trivial_iterator<_ForwardIterator>::value || __addr_in_range(*__first)) {
    // Make a copy and then insert from the copy.
    const basic_string __temp(__first, __last, __alloc());
    return __insert_from_safe_copy(__n, __ip, __temp.begin(), __temp.end());
} else {
    return __insert_from_safe_copy(__n, __ip, __first, __last);
}

Note that __insert_from_safe_copy might be a better name than __insert_not_in_range, because being overlapping is just one of the many failure modes we need to guard against here.

Read (or re-read) https://quuxplusone.github.io/blog/2021/04/17/pathological-string-appends/ before deciding on this approach. "Burn the whole thing to the ground and rewrite it" might be a reasonable alternative, especially if the alternative is increasing the complexity of this already-complex code.

[philnik]

In D119633#3317770, @Quuxplusone wrote:

I think this code looks correct enough, but it would be a lot less scary if you could just make __addr_in_range a non-constexpr function, instead of having it "lie" during constexpr evaluation and get us into infinite loops. E.g.:

if (__libcpp_is_constant_evaluated() || !__string_is_trivial_iterator<_ForwardIterator>::value || __addr_in_range(*__first)) {
    // Make a copy and then insert from the copy.
    const basic_string __temp(__first, __last, __alloc());
    return __insert_from_safe_copy(__n, __ip, __temp.begin(), __temp.end());
} else {
    return __insert_from_safe_copy(__n, __ip, __first, __last);
}

Note that __insert_from_safe_copy might be a better name than __insert_not_in_range, because being overlapping is just one of the many failure modes we need to guard against here.

Read (or re-read) https://quuxplusone.github.io/blog/2021/04/17/pathological-string-appends/ before deciding on this approach. "Burn the whole thing to the ground and rewrite it" might be a reasonable alternative, especially if the alternative is increasing the complexity of this already-complex code.

What would you like to see changed, other than the name? I don't really see a way to make this code simpler.

[• Quuxplusone]

In D119633#3323305, @philnik wrote:

In D119633#3317770, @Quuxplusone wrote:

Note that __insert_from_safe_copy might be a better name than __insert_not_in_range, because being overlapping is just one of the many failure modes we need to guard against here.

Read (or re-read) https://quuxplusone.github.io/blog/2021/04/17/pathological-string-appends/ before deciding on this approach. "Burn the whole thing to the ground and rewrite it" might be a reasonable alternative, especially if the alternative is increasing the complexity of this already-complex code.

What would you like to see changed, other than the name? I don't really see a way to make this code simpler.

Yeah, simplifying might not be possible, and on closer inspection is at least not low-hanging fruit. Microsoft's insert is about as complicated these days: https://github.com/microsoft/STL/blob/8096a27/stl/inc/xstring#L3437-L3455

And __addr_in_range is already non-constexpr; let's keep it that way. My comment was based on your commit message, which said "__addr_in_range cannot be known during constant evaluation, so it has to always return true during constant evaluation" — that's incorrect. __addr_in_range is simply a non-constexpr function; it doesn't return anything during constant evaluation because it can't be called. (And this is as it should be.) Please update the commit message to say something like "__addr_in_range is a non-constexpr function, so we shouldn't call it during constant evaluation" or something like that.

[philnik]

• rename to __insert_from_safe_copy

[ldionne]

Woops, I just saw this after I landed 5c53afe5aac0d295a9345cd439c6caf3ac5eb8ba. You'll want to rebase onto main.

[philnik]

Rebased

[philnik]

ping

[• Quuxplusone]

LGTM; some remaining nits but they're all optional IIUC.

libcxx/include/string

1440

Nit: I suggest following the guideline "Use the most aggressive constexpr possible for internal details," and I see no reason this couldn't be constexpr in C++14, right?

1466–1467

Personally I wouldn't have touched these lines. But I don't really care.

2819

Should you make my suggested change right now? Or are you planning to make it in whatever subsequent PR adds _LIBCPP_CONSTEXPR_AFTER_CXX17 to this insert method?

libcxx/include/string

 #endif // _LIBCPP_DEBUG_LEVEL == 2
 
 private:
     _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI static bool __fits_in_sso(size_type __sz) {
         // SSO is disabled during constant evaluation because `__is_long` isn't constexpr friendly
         return !__libcpp_is_constant_evaluated() && (__sz < __min_cap);
     }
 
-    _LIBCPP_INLINE_VISIBILITY
-    allocator_type& __alloc() _NOEXCEPT
-        {return __r_.second();}
-    _LIBCPP_INLINE_VISIBILITY
-    const allocator_type& __alloc() const _NOEXCEPT
-        {return __r_.second();}
+    template <class _ForwardIterator>
+    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+    iterator __insert_from_safe_copy(size_type __n, size_type __ip, _ForwardIterator __first, _ForwardIterator __last) {
+        size_type __sz = size();
+        size_type __cap = capacity();
+        value_type* __p;
+        if (__cap - __sz >= __n)
+        {
+            __p = std::__to_address(__get_pointer());
+            size_type __n_move = __sz - __ip;
+            if (__n_move != 0)
+                traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
+        }
+        else
+        {
+            __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
+            __p = std::__to_address(__get_long_pointer());
+        }
+        __sz += __n;
+        __set_size(__sz);
+        traits_type::assign(__p[__sz], value_type());
+        for (__p += __ip; __first != __last; ++__p, ++__first)
+            traits_type::assign(*__p, *__first);
+
+        return begin() + __ip;
+    }
+
+    _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __r_.second(); }
+    _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __r_.second(); }
 
 #ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 
     _LIBCPP_INLINE_VISIBILITY
     void __set_short_size(size_type __s) _NOEXCEPT
 #   ifdef _LIBCPP_BIG_ENDIAN
         {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
 #   else

 template<class _ForwardIterator>
 __enable_if_t
 <
     __is_cpp17_forward_iterator<_ForwardIterator>::value,
     typename basic_string<_CharT, _Traits, _Allocator>::iterator
 >
 basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last)
 {
     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this,
-                       "string::insert(iterator, range) called with an iterator not"
-                       " referring to this string");
+                         "string::insert(iterator, range) called with an iterator not referring to this string");
 
     size_type __ip = static_cast<size_type>(__pos - begin());
-    size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
-    if (__n)
-    {
-        if (__string_is_trivial_iterator<_ForwardIterator>::value &&
-            !__addr_in_range(*__first))
-        {
-            size_type __sz = size();
-            size_type __cap = capacity();
-            value_type* __p;
-            if (__cap - __sz >= __n)
-            {
-                __p = _VSTD::__to_address(__get_pointer());
-                size_type __n_move = __sz - __ip;
-                if (__n_move != 0)
-                    traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
-            }
-            else
-            {
-                __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
-                __p = _VSTD::__to_address(__get_long_pointer());
-            }
-            __sz += __n;
-            __set_size(__sz);
-            traits_type::assign(__p[__sz], value_type());
-            for (__p += __ip; __first != __last; ++__p, (void) ++__first)
-                traits_type::assign(*__p, *__first);
-        }
-        else
-        {
-            const basic_string __temp(__first, __last, __alloc());
-            return insert(__pos, __temp.data(), __temp.data() + __temp.size());
-        }
+    size_type __n = static_cast<size_type>(std::distance(__first, __last));
+    if (__n == 0)
+        return begin() + __ip;
+
+    if (__string_is_trivial_iterator<_ForwardIterator>::value && !__addr_in_range(*__first))
+        return __insert_from_safe_copy(__n, __ip, __first, __last);
+        return __insert_from_safe_copy(__n, __ip, __temp.begin(), __temp.end());
     }
-    return begin() + __ip;
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 inline
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str)
 {
     return insert(__pos1, __str.data(), __str.size());