[libc++] Introduce __fits_in_sso()

[philnik]

Summary

Introduce __fits_in_sso() to put the constexpr tests into a central place.

[• Quuxplusone]

libcxx/include/string

1469

IIUC, I think this should be named __is_less_than_sso_capacity(x), or at least __fits_in_sso(x). __use_sso reads like an imperative instruction, but what this is is a query.

Also, the commit message (PR summary) should explain where we're going with this. Are we going to change the body of this function to

return (!__libcpp_is_constant_evaluated()) && (__sz < __min_cap);

? If so, then you should preemptively put this function's body on its own line; otherwise you're just making the next diff more complicated. We want the next diff to be as simple as

 _LIBCPP_HIDE_FROM_ABI
 static bool __use_sso(size_type __sz) {
-    return __sz < __min_cap;
+    return (!__libcpp_is_constant_evaluated()) && (__sz < __min_cap);
 }

2358–2360

Here and line 2606, I think your change is correct, but it feels really subtle and someone-not-me should look really closely and see if they agree this is right.
IIUC, __assign_short doesn't necessarily mean "assign into the SSO buffer"; it means merely "assign into the currently active buffer," i.e. "I guarantee __n is definitely less than our current capacity() (because our capacity is invariably greater than __min_cap) and so you don't have to codegen any code for growing the buffer." It's a codegen hack. If we're constant-evaluated, then we're not generating code and so we don't need the hack (and also there is no invariant regarding __min_cap). So the hack becomes

if (!__libcpp_is_constant_evaluated() && __builtin_constant_p(__n) && __n < __min_cap)

which is equivalent to what you wrote. But I'd like the next reviewer to also check and see if they agree.

[philnik]

• Renamed to __fits_in_sso

[Mordante]

libcxx/include/string

1469

How about directly making the function constexpr and implement the final version? That avoids writing a commit message and modifying the code later.

[philnik]

• Implement final function

[ldionne]

Are there any tests that need to be modified? I would assume that tests that check for reallocation when a string is assigned-to (or similar stuff) will need to be conditionalized on whether the test is running inside a constexpr context too, right?

Finally, and most importantly -- is this implementation strategy really valid? I had thought about this when I originally wrote the constexpr string paper, and IIRC one of the issues was this:

constexpr std::string s = "short"; // Anything short enough to normally use the SSO. Since this is inside constexpr, though, SSO isn't used.

void use(std::string const& str) {
  // ...
}

int main() { use(s); }

The problem here is that when s is constructed, it is a constexpr context so we don't use the SSO. When we actually *use* s, though, it's not a constexpr context so if we check s's size and ask whether it is using SSO, we'll believe that yes, we are using it (because it would normally fit in the small buffer).

Is this not an issue somehow? It's been a while since I've thought about this.

Edit: Well, in the current state of things, this can't be an issue because __fits_in_sso is only used from code paths that mutate the string, and those code paths can't be called at runtime on a constexpr-created std::string. So this at least does seem correct to me in its current state. However, if we ever queried __fits_in_sso for a read-only operation, it would have the possibility to lie if called on a std::string created with a different constexpr-ness than the context in which __fits_in_sso is called. I think this merits at least a comment.

libcxx/include/string

1470

Can you add a comment saying something like "We never use the SSO in constexpr contexts because it requires some amount of reinterpret-casting, which is not constexpr-friendly"?

Otherwise, one would rightly wonder why a function named __fits_in_sso would return something different based on whether it is called in a constexpr context or not.

[philnik]

In D116487#3218176, @ldionne wrote:

Are there any tests that need to be modified? I would assume that tests that check for reallocation when a string is assigned-to (or similar stuff) will need to be conditionalized on whether the test is running inside a constexpr context too, right?

Finally, and most importantly -- is this implementation strategy really valid? I had thought about this when I originally wrote the constexpr string paper, and IIRC one of the issues was this:

constexpr std::string s = "short"; // Anything short enough to normally use the SSO. Since this is inside constexpr, though, SSO isn't used.

void use(std::string const* str) {
  // ...
}

int main() { use(s); }

The problem here is that when s is constructed, it is a constexpr context so we don't use the SSO. When we actually *use* s, though, it's not a constexpr context so if we check s's size and ask whether it is using SSO, we'll believe that yes, we are using it (because it would normally fit in the small buffer).

Is this not an issue somehow? It's been a while since I've thought about this.

You have to deallocate anything that you allocated during constant evaluation. So using a constexpr string in a non-constexpr context is illegal IIUC. https://godbolt.org/z/KKv3YnP4a

[ldionne]

In D116487#3218194, @philnik wrote:

You have to deallocate anything that you allocated during constant evaluation. So using a constexpr string in a non-constexpr context is illegal IIUC. https://godbolt.org/z/KKv3YnP4a

Right, it looks like I got confused with promotion to static storage, which was pulled from the paper IIRC.

So I think this works, however if/when we allow something like constexpr std::string s = "hello"; at file scope (which entails that we'll do some sort of promotion of the constexpr-allocated memory to static storage), we'll have to tackle this problem cause the possibility of __fits_in_sso() lying is going to become real. For the time being, no problem though.

[philnik]

• Add comment to explain libcpp_is_constant_evaluated() in fits_in_sso()

[philnik]

ping

[ldionne]

This is not a NFC -- the commit shouldn't say NFC.

libcxx/include/string

2358–2360

That sounds right to me.

libcxx/include/string

#if _LIBCPP_DEBUG_LEVEL == 2
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
 
 #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();}
 
 #ifdef _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

 template <class _CharT, class _Traits, class _Allocator>
 void basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s,
                                                        size_type __sz,
                                                        size_type __reserve)
 {
     if (__reserve > max_size())
         this->__throw_length_error();
     pointer __p;
-    if (__reserve < __min_cap)
+    if (__fits_in_sso(__reserve))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__reserve);
         __p = __alloc_traits::allocate(__alloc(), __cap+1);
         __set_long_pointer(__p);
         __set_long_cap(__cap+1);
         __set_long_size(__sz);
     }
     traits_type::copy(_VSTD::__to_address(__p), __s, __sz);
     traits_type::assign(__p[__sz], value_type());
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz)
 {
     if (__sz > max_size())
         this->__throw_length_error();
     pointer __p;
-    if (__sz < __min_cap)
+    if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__sz);
         __p = __alloc_traits::allocate(__alloc(), __cap+1);
else
                                   __str.__get_long_size());
     _VSTD::__debug_db_insert_c(this);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 void basic_string<_CharT, _Traits, _Allocator>::__init_copy_ctor_external(
     const value_type* __s, size_type __sz) {
   pointer __p;
-  if (__sz < __min_cap) {
+  if (__fits_in_sso(__sz)) {
     __p = __get_short_pointer();
     __set_short_size(__sz);
   } else {
     if (__sz > max_size())
       this->__throw_length_error();
     size_t __cap = __recommend(__sz);
     __p = __alloc_traits::allocate(__alloc(), __cap + 1);
     __set_long_pointer(__p);

 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
 {
     if (__n > max_size())
         this->__throw_length_error();
     pointer __p;
-    if (__n < __min_cap)
+    if (__fits_in_sso(__n))
     {
         __set_short_size(__n);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__n);
         __p = __alloc_traits::allocate(__alloc(), __cap+1);
<
     __is_cpp17_forward_iterator<_ForwardIterator>::value
 >
 basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
 {
     size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last));
     if (__sz > max_size())
         this->__throw_length_error();
     pointer __p;
-    if (__sz < __min_cap)
+    if (__fits_in_sso(__sz))
     {
         __set_short_size(__sz);
         __p = __get_short_pointer();
     }
     else
     {
         size_type __cap = __recommend(__sz);
         __p = __alloc_traits::allocate(__alloc(), __cap+1);
basic_string<_CharT, _Traits, _Allocator>::__assign_external(
   }
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s, size_type __n)
 {
     _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::assign received nullptr");
-    return (__builtin_constant_p(__n) && __n < __min_cap)
+    return (__builtin_constant_p(__n) && __fits_in_sso(__n))
                ? __assign_short(__s, __n)
                : __assign_external(__s, __n);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
 {
     size_type __cap = capacity();
     if (__cap < __n)

 }
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&
 basic_string<_CharT, _Traits, _Allocator>::assign(const value_type* __s)
 {
     _LIBCPP_ASSERT(__s != nullptr, "string::assign received nullptr");
     return __builtin_constant_p(*__s)
-               ? (traits_type::length(__s) < __min_cap
+               ? (__fits_in_sso(traits_type::length(__s))
                       ? __assign_short(__s, traits_type::length(__s))
                       : __assign_external(__s, traits_type::length(__s)))
                : __assign_external(__s);
 }
 // append
 
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>&