[libc++] Implement P1072R10 (std::basic_string::resize_and_overwrite)

[philnik]

• Remove unused includes

[Mordante]

Thanks for working on this!
Please mark the feature complete in libcxx/docs/Status/Cxx2bPapers.csv.

Please update libcxx/utils/generate_feature_test_macro_components.py with the new feature-test macro __cpp_lib_string_resize_and_overwrite; its values should be 202110L and run this script to update the appropriate tests.

I didn't have enough time to do a thorough review; I'll have a closer look after all issues have been addressed.

libcxx/include/string

160

Please update the synopsis.

template<class Operation>
constexpr void resize_and_overwrite(size_type n, Operation op); // since C++23

997

This looks wrong. "Implementations should avoid unnecessary copies and allocations" This may allocate more than required. The paper 3. Implementation refers to __resize_default_init as example.

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

14

Please use the entire signature of the function.

21

All tests are now done on an empty string. Please also test with non-empty strings.

65

It would be good to test with all string types. libcxx/test/support/make_string.h has a helper to create the same string for all supported string types. Then the test function can be templated on the string type.

77

Please use int main(int, char**).

80

Please return 0; Some of our supported platforms require this even for main.

[philnik]

• Using __resize_default_init now and extended tests

[• Quuxplusone]

libcxx/include/string

994

Line-break after constexpr, please.
Also, I certainly wouldn't complain if s/_Operation/_Op/.

995

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1072r10.html doesn't mention any Constraints, only a Mandates that std::move(__o)(declval<_CharT*&>(), __n) should have an integer-like type. I don't think "integer-like-ness" is expressible in C++, but prove me wrong. :)
Anyway, this function definitely should not be constrained, because (1) the standard says it shouldn't be, and (2) if we get our constraint wrong then we're needlessly preventing valid use-cases.

...Hm, I guess [p1072r10] has a minor wording bug, because obviously they intended to mandate the type of std::move(op)(std::move(p), std::move(n)), not std::move(op)(p, n). I think we should "do what they mean, not what they say."

999

Forgot the std::move here. Please add a test case that catches this (e.g. use an _Op with a &&-ref-qualified operator(), and/or one where operator()() && and operator()() & do different things).

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

77

I question the usefulness of all of the "nonsense" strings. I understand "" and "Banane" (i.e. "short") and "long long string so no SSO", but the other five seem calculated only to make the z/OS folks unhappy. ;) If they're redundant, please eliminate them.

[philnik]

• Added move only tests

libcxx/include/string

994

What do you mean by

Also, I certainly wouldn't complain if s/_Operation/_Op/.

?

995

I think the paper is right. What would be the point of moving a raw pointer or a size_type?

[• Quuxplusone]

libcxx/include/string

994

"I wouldn't complain if X" means "I'm not asking for X, but I'd be pleased if X were to happen anyway." Okay, usually it means I'm asking for X. ;)
s/foo/bar/ is awk/sed-speak for "replace foo with bar."
As usual, the further down in the review I got, the more strongly I liked _Op over _Operation.

995

The question is whether it is permissible for libc++ to reject

std::string s;
s.resize_and_overwrite(100, [](char *p, int& n) {
    return 0;
});

or, vice versa, whether it is permissible for us to accept

std::string s;
s.resize_and_overwrite(100, [](char *p, int&& n) {
    return 0;
});

That is, it's not so much about the machine code generated as it is about the value-categories of things.

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

23–39

For the ref-qualification/value-category issue, this simple non-template test will suffice; you can get rid of move_only_functor.

void test_value_categories() {
    std::string s;
    s.resize_and_overwrite(10, [](char*&, size_t&) { return 0; });
    struct RefQual {
        int operator()(char *, size_t) && { return 0; }
    };
    s.resize_and_overwrite(10, RefQual());
}

(Here I'm following libstdc++ in assuming that p, n are passed as lvalues, even though I said above that they really ought to be passed as rvalues. If we hear that rvalues were intended, then just change & to && above.)

90–95

Throughout: I see your reason for using the names begin, size for Op's parameters, but I think it will be clearer to use p, n the same way the standard does. Also, speaking of s.begin() and s.size(), it looks like you're assuming things about their values without asserting those things. Could we assert them instead?

constexpr void test_undersized(S src, S orig)
{
  S dst = orig;
  size_t new_size = 1.5 * src.size();
  auto func = [&](auto *p, size_t n) {
    assert(n == new_size);
    assert(dst.size() == new_size);
    p = std::copy_n(src.begin(), src.size(), p);
    std::copy_n(src.begin(), src.size() / 2, p);
    return n;
  };
  dst.resize_and_overwrite(new_size, func);
  assert(dst == src + src.substr(0, src.size() / 2);
}

But, writing it out this way, I just don't see the point of this test. What is orig doing there (your former s3)? Why does your func overwrite not just the new space but the original contents of the string too? What is the significance of the division in size() / 2 as opposed to using a constant like 42?
Could test_undersized and test_oversized both be replaced with something like...?

template<class S>
constexpr void test_appending(int k, int N) {
    assert(N > k);
    auto s = S(k, 'a');
    s.resize_and_overwrite(N, [&](char *p, int n) {
        assert(n == N);
        LIBCPP_ASSERT(s.size() == n);
        LIBCPP_ASSERT(s.begin() == p);
        assert(std::all_of(p, p+k, [](auto ch) { return ch == 'a'; }));
        LIBCPP_ASSERT(p[k] == '\0');
        std::fill(p+k, p+n, 'b');
        p[n] = 'c';  // will be overwritten
        return n;
    });
    auto expected = S(k, 'a') + S(N-k, 'b');
    assert(s == expected);
}

template<class S>
constexpr void test_truncating(int o, int N) {
    assert(N < o);
    auto s = S(o, 'a');
    s.resize_and_overwrite(N, [&](char *p, int n) {
        assert(n == N);
        LIBCPP_ASSERT(s.size() == n);
        LIBCPP_ASSERT(s.begin() == p);
        assert(std::all_of(p, p+n, [](auto ch) { return ch == 'a'; }));
        LIBCPP_ASSERT(p[n] == 'a');
        p[n-1] = 'b';
        p[n] = 'c';  // will be overwritten
        return n;
    });
    auto expected = S(N-1, 'a') + 'b';
    assert(s == expected);
}

However, this is still missing any coverage for what happens when op(p, n) < n. We should have coverage for that.

108–113

Throughout: IIUC, s1 means dest and s2 means src. (On line 87, s means dest and s3 means src. And so on.) Please consistent-ize the parameter names.

124

template<class CharT> — it's not a String.
Likewise on line 114 — class CharT, class S — although in that case, S is invariably basic_string<CharT>, so I don't see why it needs to be a parameter at all. Just using S = basic_string<CharT> in the body of the function is good enough.

133–135

(Moot) These lines are too long.
(1) Unless @ldionne asked for this (in which case his preference can overrule mine), I'd much much prefer to see the usual libc++ style of test_x(); static_assert(test_x()); written out longhand. It's only 10 lines of tests (as opposed to what you have here: 5 lines of tests plus 3 lines of macros).
(2) I don't understand why test_overwrite_str calls test_copy_strings calls test_all calls test_{exact_size, oversized, undersized}. These names don't seem to reflect any sort of hierarchy. I think it should just be that test<CharT> calls all the different tests, period.
(3) Only the one function that you're static_assert'ing on needs to return true; the rest should have return type void. (I suggest that that one bool-returning function should be named test<CharT>().)

[philnik]

Rebased and updated test

[• Quuxplusone]

LGTM at this point, mod minor comments.

libcxx/include/string

336–337

Please move this up to between resize and capacity, to match https://eel.is/c++draft/basic.string
...er, I guess we have some pre-existing issues in that ordering. Either just move this up to between resize and reserve, or else redistribute our synopses of reserve-thru-empty to match the Standard's synopsis ordering. (But I wouldn't recommend anything more drastic than that.)

2766

Here and line 3495, since we're changing it anyway, I'd prefer to see

_LIBCPP_CONSTEXPR_AFTER_CXX17 void

We shouldn't need the inline keyword at all, because this is a template; and constexpr void reads better than void constexpr.
https://quuxplusone.github.io/blog/2021/04/03/static-constexpr-whittling-knife/

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

24

Neat. Perhaps resizeSize should be named newCapacity? (The ultimate size of the final string will be N.)

62

I think you're missing an interesting case: something like test_appending<S>(10, 30, 15), where the original string fits in SSO, then we need to allocate for the lambda call, and then the final string would again fit in SSO (but IIUC we do not actually put it back into SSO — we just leave it with the extra allocated capacity, right? This is fine).

[Mordante]

In general this looks good! I've some minor nit. It also seems you missed some of my "bookkeeping" remarks. I added these as comments.

libcxx/include/string

336–337

Basically where my original request for updating the synopsis is ;-)

337

In my original reply I mentioned some not yet done things. For clarity I add them here to it's easier to tick the box once done.

Please mark the feature complete in libcxx/docs/Status/Cxx2bPapers.csv.

Please update libcxx/utils/generate_feature_test_macro_components.py with the new feature-test macro __cpp_lib_string_resize_and_overwrite; its values should be 202110L and run this script to update the appropriate tests.

997

Is there a reason to use variable instead of calling data() in __erase_to_end.
The LLVM coding convention doesn't like auto when the type isn't clear.

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

24

Also please use snake_case.

37

Please don't use auto.

38

Can you test whether s.c_str() contains a proper NUL-terminated string. The same for the truncating test.

87

Next time it would be better to make a helper function that calls all 5 variants, just to keep main simpler.

[• Quuxplusone]

libcxx/include/string

997

Sadly yes, OP's parameters are overspecified as lvalues, not prvalues. I've just requested an LWG issue number for this.
https://eel.is/c++draft/basic.string#string.capacity-7

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

38

Ah, +1; I'd been implicitly assuming that s == expected would also check the null byte, but I guess it doesn't necessarily have to.

const S expected = S(k, 'a') + S(N - k, 'b');
assert(s == expected);
assert(s.c_str()[N] == '\0');

87

I forget if I specifically requested the current status quo, but I very well might have — personally I like <10 LOC of code repetition in main better than a second layer of test functions. :)

[Mordante]

libcxx/include/string

997

In that case once you have a number, can you provide it here. Then we can add a comment why this is required. (And clean it up once the issue is resolved.)

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

87

I prefer the extra layer, especially due to the duplication for static_assert.
However I don't object against this version.

[philnik]

Added feature-test macro and some minor changes

[Mordante]

LGTM, assuming the CI passes.

[• Quuxplusone]

libcxx/include/string

997

@mzeren-vmw @ckennelly (paper authors), thoughts? Shall we even just go ahead and do the sane thing here, on the assumption that LWG will catch up to us? :)

[philnik]

• Remove _LIBCPP_CONSTEXPR_AFTER_CXX17
• Disable constexpr test

@Quuxplusone, @Mordante do you want to take another look before I land it?

[• Quuxplusone]

libcxx/include/string

997

The LWG issue for this is https://timsong-cpp.github.io/lwg-issues/3645
@philnik, I suggest that you land D113013 as-is (with the lvalue __data); but then (if you don't mind the extra work) I think you should immediately submit another PR that changes the offending line to __erase_to_end(_VSTD::move(__op)(data(), +__n)); with a message something like "[libc++] resize_and_overwrite: Adopt the P/R for LWG3645." I can't vouch for @ldionne, but personally I'd accept such a PR right away. :)

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

32

Nit: remove const, or add &, depending on your intent

[Mordante]

I don't mind landing it now, but let's make sure we show the correct state. In the followup patch you can then update the state to fully implemented.

libcxx/docs/Status/Cxx2bPapers.csv

29 ↗

(On Diff #397650)

Please add a note the constexpr part isn't done yet.
The LLVM 14 branching will happen later this month, so it's not certain the complete version will be in LLVM 14. So let's make the state correct.

libcxx/utils/generate_feature_test_macro_components.py

626 ↗

(On Diff #397650)

Likewise show the correct state.

[philnik]

@Mordante I'd argue that it is fully implemented. The function signature is complete. It only doesn't work, because the rest of string isn't constexpr yet. And P1679R3 is also marked complete, including feature test macro.

[Mordante]

Good point, then lets keep it as is.

[philnik]

• Address Arthur's nit

libcxx/include/string

// types:
 
     size_type size() const noexcept;
     size_type length() const noexcept;
     size_type max_size() const noexcept;
     size_type capacity() const noexcept;
 
     void resize(size_type n, value_type c);
     void resize(size_type n);
 
     void reserve(size_type res_arg);
     void reserve(); // deprecated in C++20
     void shrink_to_fit();
     void clear() noexcept;
     bool empty() const noexcept;
 
     const_reference operator[](size_type pos) const;
     reference       operator[](size_type pos);
// types:
     bool ends_with(basic_string_view<charT, traits> sv) const noexcept;   // C++20
     bool ends_with(charT c) const noexcept;                               // C++20
     bool ends_with(const charT* s) const;                                 // C++20
 
     constexpr bool contains(basic_string_view<charT, traits> sv) const noexcept; // C++2b
     constexpr bool contains(charT c) const noexcept;                             // C++2b
     constexpr bool contains(const charT* s) const;                               // C++2b
 
+    template<class Operation>
+    constexpr void resize_and_overwrite(size_type n, Operation op); // since C++23
+
     bool __invariants() const;
 };
 
 template<class InputIterator,
          class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 basic_string(InputIterator, InputIterator, Allocator = Allocator())
    -> basic_string<typename iterator_traits<InputIterator>::value_type,
                   char_traits<typename iterator_traits<InputIterator>::value_type>,
#endif // _LIBCPP_DEBUG_LEVEL == 2
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type capacity() const _NOEXCEPT
         {return (__is_long() ? __get_long_cap() : static_cast<size_type>(__min_cap)) - 1;}
 
     _LIBCPP_CONSTEXPR_AFTER_CXX17 void resize(size_type __n, value_type __c);
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void resize(size_type __n) {resize(__n, value_type());}
 
     _LIBCPP_CONSTEXPR_AFTER_CXX17 void reserve(size_type __requested_capacity);
-    _LIBCPP_INLINE_VISIBILITY void __resize_default_init(size_type __n);
+
+#if _LIBCPP_STD_VER > 20
+    template <class _Operation>
+    _LIBCPP_HIDE_FROM_ABI constexpr void resize_and_overwrite(size_type __n, _Operation __op)
+        requires requires(_Operation __o) { {__o(pointer{}, size_type{})} -> _VSTD::convertible_to<size_type>; } {
+      if (__n > capacity())
+        __resize_default_init(__n);
+
+      __erase_to_end(__op(data(), __n));
+    }
+#endif
+
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __resize_default_init(size_type __n);
 
     _LIBCPP_DEPRECATED_IN_CXX20 _LIBCPP_INLINE_VISIBILITY void reserve() _NOEXCEPT {shrink_to_fit();}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void shrink_to_fit() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void clear() _NOEXCEPT;
 
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
     bool empty() const _NOEXCEPT {return size() == 0;}
 
__enable_if_t
             && !__is_same_uncvref<_Tp, basic_string>::value,
             basic_string&
         >
                   append(const _Tp& __t, size_type __pos, size_type __n=npos);
     _LIBCPP_CONSTEXPR_AFTER_CXX17 basic_string& append(const value_type* __s, size_type __n);
     _LIBCPP_CONSTEXPR_AFTER_CXX17 basic_string& append(const value_type* __s);
     _LIBCPP_CONSTEXPR_AFTER_CXX17 basic_string& append(size_type __n, value_type __c);
 
-    _LIBCPP_INLINE_VISIBILITY
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
     void __append_default_init(size_type __n);
 
     template<class _InputIterator>
     _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
     __enable_if_t
         <
             __is_exactly_cpp17_input_iterator<_InputIterator>::value,
             basic_string&
if (__n)
         __sz += __n;
         __set_size(__sz);
         traits_type::assign(__p[__sz], value_type());
     }
     return *this;
 }
 
 template <class _CharT, class _Traits, class _Allocator>
-inline void
+inline void _LIBCPP_CONSTEXPR_AFTER_CXX17
 basic_string<_CharT, _Traits, _Allocator>::__append_default_init(size_type __n)
 {
     if (__n)
     {
         size_type __cap = capacity();
         size_type __sz = size();
         if (__cap - __sz < __n)
             __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
     size_type __sz = size();
     if (__n > __sz)
         append(__n - __sz, __c);
     else
         __erase_to_end(__n);
 }
 
 template <class _CharT, class _Traits, class _Allocator>
-inline void
+inline void _LIBCPP_CONSTEXPR_AFTER_CXX17
 basic_string<_CharT, _Traits, _Allocator>::__resize_default_init(size_type __n)
 {
     size_type __sz = size();
     if (__n > __sz) {
        __append_default_init(__n - __sz);
     } else
         __erase_to_end(__n);
 }

libcxx/test/std/strings/basic.string/string.capacity/resize_and_overwrite.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <string>
+
+// template<class Operation>
+// void resize_and_overwrite(size_type n, Operation op)
+
+#include <cassert>
+#include <string>
+
+#include "make_string.h"
+
+template <class S>
+constexpr void test_exact_size(S s, S s2) {
+  const auto new_size = s.size() * 2;
+  s2.resize_and_overwrite(new_size, [&](auto* begin, size_t size) {
+    assert(size == new_size);
+    std::copy(s.begin(), s.end(), begin);
+    std::copy(s.begin(), s.end(), begin + s.size());
+    return new_size;
+  });
+  assert(s2 == s + s);
+}
+
+template <class S>
+constexpr void test_oversized(S s, S s2) {
+  const auto new_size = s.size() * 3;
+  const auto actual_size = s.size() * 2;
+  s2.resize_and_overwrite(new_size, [&](auto* begin, size_t size) {
+    assert(size == new_size);
+    std::copy(s.begin(), s.end(), begin);
+    std::copy(s.begin(), s.end(), begin + s.size());
+    return actual_size;
+  });
+  assert(s2.size() == actual_size);
+  assert(s2.capacity() >= new_size);
+  assert(s2 == s + s);
+}
+
+template <class S>
+constexpr void test_undersized(S s, S s2) {
+  const auto new_size = s.size() + s.size() / 2;
+  s2.resize_and_overwrite(new_size, [&](auto* begin, size_t size) {
+    assert(size == new_size);
+    std::copy(s.begin(), s.end(), begin);
+    std::copy(s.begin(), s.begin() + s.size() / 2, begin + s.size());
+    return size;
+  });
+  assert(s2 == s + s.substr(0, s.size() / 2));
+}
+
+template <class S>
+constexpr void test_all(S s1, S s2) {
+  test_exact_size(s1, s2);
+  test_oversized(s1, s2);
+  test_undersized(s1, s2);
+}
+
+template <class S, class S2>
+constexpr bool test_copy_strings(S2 s) {
+  test_all(MAKE_STRING(S, ""), s);
+  test_all(MAKE_STRING(S, "Banane"), s);
+  test_all(MAKE_STRING(S, "a+sgpion"), s);
+  test_all(MAKE_STRING(S, "dafgiudpfm12"), s);
+  test_all(MAKE_STRING(S, "adfpoguharsüoginasfdü23"), s);
+  test_all(MAKE_STRING(S, "asoriübsfogiabsdfgoüif24"), s);
+  test_all(MAKE_STRING(S, "long long string so no SSO"), s);
+  test_all(MAKE_STRING(S, "pioegarsipasngipnadfgipkonadfpioknadfgöpaionge48"), s);
+
+  return true;
+}
+
+template <class S>
+constexpr bool test_overwrite_str() {
+  test_copy_strings<S, std::basic_string<S>>({});
+  test_copy_strings<S, std::basic_string<S>>(MAKE_STRING(S, "short string"));
+  test_copy_strings<S, std::basic_string<S>>(MAKE_STRING(S, "long long string so no SSO"));
+
+  return true;
+}
+
+#define CONSTEXPR_TEST(...)                                                                                            \
+  __VA_ARGS__;                                                                                                         \
+  static_assert(__VA_ARGS__)
+
+void test() {
+  CONSTEXPR_TEST(test_overwrite_str<char>());
+  CONSTEXPR_TEST(test_overwrite_str<char8_t>());
+#ifndef TEST_HAS_NO_WIDE_CHARACTERS
+  CONSTEXPR_TEST(test_overwrite_str<wchar_t>());
+#endif
+  CONSTEXPR_TEST(test_overwrite_str<char16_t>());
+  CONSTEXPR_TEST(test_overwrite_str<char32_t>());
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}