[libc++] Make sure basic_string::reserve never shrinks in all standard modes

[ldionne]

Summary

Since basic_string::reserve is instantiated in the shared library but also
available to the compiler for inlining, its definition should not depend on
things like the Standard mode in use. Indeed, that flag may not match between
how the shared library is compiled and how users are compiling their own code,
resulting in ODR violations.

A valid implementation of reserve() has always been to never shrink,
even before C++20. This patch uses that implementation freedom to resolve
the issue by always implementing the C++20 behavior.

Fixes llvm-project#53170

[ldionne]

Note that we could technically have made the change only for reserve(n), while leaving reserve() to actually perform shrink_to_fit. However, my opinion is that reserve() should be equivalent to reserve(0) (which is how it used to be specified before C++20), and so it should behave consistently with it.

[ldionne]

Add XFAIL for older Apple dylibs and rebase onto main.

[ldionne]

Gentle ping -- I'd like to get other people's eyes on this and ship this quickly since this is a pretty bad bug.

[Mordante]

LGTM! I really like the amount of comments.

libcxx/include/string

3269

[• Quuxplusone]

Everything here makes sense except the decision to make s.reserve() nonequivalent to s.shrink_to_fit(). I don't see any ABI issue with that, so that part of the patch is orthogonal to the rest — and it seems to be altering behavior that is both useful and cppreference-documented. I suggest doing everything else you're doing, but not that specific one-line diff, because I don't see its upside.

libcxx/docs/ReleaseNotes.rst

111–115

Consider reflowing to fit in Phab's column count. :)
"so that both these calls never shrink the string consistently in all Standard modes" — so they always shrink it inconsistently? 😛 Suggestion:

- C++20 requires that ``std::basic_string::reserve`` never reduce the capacity
  of the string. (For that, use ``shrink_to_fit``.) Prior to this release, libc++'s
  ``std::basic_string::reserve(n)`` could reduce capacity in C++17 and before,
  but not in C++20 and later. This caused ODR violations when mixing code compiled
  under different Standard modes. After this change,
  ``std::basic_string::reserve(n)`` never reduces capacity, even in C++17 
  and before.
  Also, after this change, `std::basic_string::reserve()`` is treated as a no-op,
  rather than as a synonym for ``shrink_to_fit()``. [Arthur says: Why?]

libcxx/include/string

989

Why not? https://en.cppreference.com/w/cpp/string/basic_string/reserve specifically says that the zero-argument overload (which is deprecated in C++20) is supposed to be a synonym for shrink_to_fit. Why wouldn't we just do that?

[ldionne]

In D117332#3252167, @Quuxplusone wrote:

Everything here makes sense except the decision to make s.reserve() nonequivalent to s.shrink_to_fit(). I don't see any ABI issue with that, so that part of the patch is orthogonal to the rest — and it seems to be altering behavior that is both useful and cppreference-documented. I suggest doing everything else you're doing, but not that specific one-line diff, because I don't see its upside.

The rationale is that reserve() is supposed to be the same as reserve(0) -- actually in C++03 reserve is specified as a single overload with a default argument: reserve(int = 0). If I make reserve() a synonym for shrink_to_fit(), it won't be equivalent to reserve(0) anymore. I think we have to pick our poison here: either reserve() and reserve(0) are inconsistent, or reserve() and reserve(0) are consistent but reserve() is inconsistent with what the Standard suggests.

Thoughts? Does that change your opinion?

[• Quuxplusone]

libcxx/docs/ReleaseNotes.rst

111–115

The rationale is that reserve() is supposed to be the same as reserve(0) -- actually in C++03 reserve is specified as a single overload with a default argument: reserve(int = 0). If I make reserve() a synonym for shrink_to_fit(), it won't be equivalent to reserve(0) anymore.

reserve() is explicitly supposed to not-be-equivalent to reserve(0), in C++20 and later... but, at the same time, it's also explicitly deprecated. Okay, I buy that. I'd explain it like this:

- C++20 requires that ``std::basic_string::reserve(n)`` never reduce the capacity
  of the string. (For that, use ``shrink_to_fit``.) Prior to this release, libc++'s
  ``std::basic_string::reserve`` could reduce capacity in C++17 and before,
  but not in C++20 and later. This caused ODR violations when mixing code compiled
  under different Standard modes. After this change, libc++'s
  ``std::basic_string::reserve`` never reduces capacity, even in C++17 
  and before.
  C++20 deprecates the zero-argument overload of ``std::basic_string::reserve()``,
  but specifically permits it to reduce capacity. libc++ does not take advantage
  of this permission: we treat ``reserve()`` as a synonym for ``reserve(0)``
  in all Standard modes.

[ldionne]

I am reconsidering my decision now. Let's put ourselves in the shoes of a programmer that wrote code in C++03 when the standard did say "if n < size(), this is a non-binding shrink-to-fit request". They most likely used str.reserve() with the exact expectation that it was going to shrink_to_fit.

API consistency is relevant for new code being written, however new code being written won't use reserve() because it's deprecated. So my opinion is now that if we change reserve() to never shrink, we're making the wrong tradeoff - existing code may change performance characteristics, and new code won't benefit from the consistency because new code won't use reserve() anyways.

Thoughts? If you agree, I'll turn this patch around and make reserve(n) never shrink in all standard modes, but I won't touch reserve() (so that it shrinks to fit in all standard modes).

[• Quuxplusone]

In D117332#3261316, @ldionne wrote:

I am reconsidering my decision now. Let's put ourselves in the shoes of a programmer that wrote code in C++03 when the standard did say "if n < size(), this is a non-binding shrink-to-fit request". They most likely used str.reserve() with the exact expectation that it was going to shrink_to_fit.

API consistency is relevant for new code being written, however new code being written won't use reserve() because it's deprecated. So my opinion is now that if we change reserve() to never shrink, we're making the wrong tradeoff - existing code may change performance characteristics, and new code won't benefit from the consistency because new code won't use reserve() anyways.

Thoughts? If you agree, I'll turn this patch around and make reserve(n) never shrink in all standard modes, but I won't touch reserve() (so that it shrinks to fit in all standard modes).

Sounds like I convinced you right as you convinced me? 😛 I think part of my confusion is that there are like three different things we might be worried about:
(A) Behavior change between s.reserve() compiled with Clang 14 -std=c++17 versus the same source code compiled with Clang 14 -std=c++20 (which leads to ODR violation when linked together).
(B) Behavior change between C++17 s.reserve() compiled with Clang 13, versus the same source code compiled with Clang 14.
(C) Behavior change between C++17 s.reserve() compiled with Clang 13 -O0 and linked against the Clang 13 dylib, versus the same object file linked against the Clang 14 dylib.
(D) Behavior change between s.reserve() (compiled with Clang 14 in any mode), versus s.reserve(0) (ditto).

Prior to D91778, libc++ used the default-argument implementation (Default arguments are the devil!), so a source-level call to s.reserve() in old code would have been secretly calling basic_string::reserve(0).

What @rsmith was complaining about was (A). Your original proposal (and what I was agreeing to when I clicked "Accept" :)) fixes (A) and (D) but breaks (B) and (C).
My proposal to leave C++20 .reserve() as shrink-to-fit (and what you just offered to do, IIUC) fixes (A) and (B) but breaks (C) and (D).

I think we cannot avoid breaking (C), because the dylib must implement the C++20 behavior for basic_string::reserve(0), so a compiled call to basic_string::reserve(0) must not shrink, and in Clang 13 s.reserve() was secretly a call to basic_string::reserve(0).

Anyway, you can go with the solution I suggested or the solution I accepted — I guess I have no call to be unhappy either way. ;)

[Mordante]

I've no strong preference to which solution we take.

[ldionne]

Don't change the behavior of basic_string::reserve().

[• Quuxplusone]

libcxx/docs/ReleaseNotes.rst

124

[ldionne]

Applying Arthur's comment upon committing. The AIX CI failure is unrelated, so I'll ignore it.

libcxx/docs/ReleaseNotes.rst

- ``std::filesystem::path::iterator``, which (in our implementation) stashes
   so that it is a conforming input iterator in C++17 and a conforming
   ``std::bidirectional_iterator`` in C++20. Before this release, it had set its
   ``reference`` type to ``const path&`` and its ``iterator_category`` to
   ``bidirectional_iterator_tag``, making it a non-conforming bidirectional iterator.
   After this change, ``for`` loops of the form ``for (auto& c : path)`` must be rewritten
   as either ``for (auto&& c : path)`` or ``for (const auto& c : path)``.
   ``std::reverse_iterator<path::iterator>`` is no longer rejected.
 
 - Removed the nonstandard default constructor from ``std::chrono::month_weekday``.
   You must now explicitly initialize with a ``chrono::month`` and
   ``chrono::weekday_indexed`` instead of "meh, whenever".
 
+- C++20 requires that ``std::basic_string::reserve(n)`` never reduce the capacity
+  of the string. (For that, use ``shrink_to_fit()``.) Prior to this release, libc++'s
+  ``std::basic_string::reserve(n)`` could reduce capacity in C++17 and before, but
+  not in C++20 and later. This caused ODR violations when mixing code compiled under
+  different Standard modes. After this change, libc++'s ``std::basic_string::reserve(n)``
+  never reduces capacity, even in C++17 and before.
+  C++20 deprecates the zero-argument overload of ``std::basic_string::reserve()``,
+  but specifically permits it to reduce capacity. To avoid breaking existing code
+  assuming that ``std::basic_string::reserve()`` will shrink, libc++ maintains
+  the behavior to shrink even though it makes ``std::basic_string::reserve()`` not
+  a synonym for ``std::basic_string::reserve(0)`` in any Standard mode anymore.
+
 ABI Changes
 -----------
 
 - The C++17 variable templates ``is_error_code_enum_v`` and
   ``is_error_condition_enum_v`` are now of type ``bool`` instead of ``size_t``.
 
 - The C++03 emulation type for ``std::nullptr_t`` has been removed in favor of
   using ``decltype(nullptr)`` in all standard modes. This is an ABI break for

libcxx/include/string

void resize_and_overwrite(size_type __n, _Op __op) {
       __resize_default_init(__n);
       __erase_to_end(_VSTD::move(__op)(data(), _LIBCPP_AUTO_CAST(__n)));
     }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY void __resize_default_init(size_type __n);
 
     _LIBCPP_DEPRECATED_IN_CXX20 _LIBCPP_INLINE_VISIBILITY
     void reserve() _NOEXCEPT {shrink_to_fit();}
     _LIBCPP_INLINE_VISIBILITY
     void shrink_to_fit() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT;
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
     bool empty() const _NOEXCEPT {return size() == 0;}
 
     _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const _NOEXCEPT;

 
 template <class _CharT, class _Traits, class _Allocator>
 void
 basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __requested_capacity)
 {
     if (__requested_capacity > max_size())
         this->__throw_length_error();
 
-#if _LIBCPP_STD_VER > 17
-    // Reserve never shrinks as of C++20.
-    if (__requested_capacity <= capacity()) return;
-#endif
+    // Make sure reserve(n) never shrinks. This is technically only required in C++20
+    // and later (since P0966R1), however we provide consistent behavior in all Standard
+    // modes because this function is instantiated in the shared library.
+    if (__requested_capacity <= capacity())
+        return;
 
     size_type __target_capacity = _VSTD::max(__requested_capacity, size());
     __target_capacity = __recommend(__target_capacity);
     if (__target_capacity == capacity()) return;
 
     __shrink_or_extend(__target_capacity);
 }
 

libcxx/test/libcxx/strings/basic.string/string.capacity/PR53170.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
+//
+//===----------------------------------------------------------------------===//
+
+// <string>
+
+// void reserve(); // Deprecated in C++20.
+// void reserve(size_type);
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DISABLE_DEPRECATION_WARNINGS
+
+// This test ensures that libc++ implements https://wg21.link/P0966R1 (reserve never shrinks)
+// even before C++20. This is required in order to avoid ODR violations because basic_string::reserve(size)
+// is compiled into the shared library. Hence, it needs to have the same definition in all Standard modes.
+//
+// However, note that reserve() does shrink, and it does so in all Standard modes.
+//
+// Reported as https://llvm.org/PR53170.
+
+// reserve(n) used to shrink the string until https://llvm.org/D117332 was shipped.
+// XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
+// XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx{{11|12}}
+
+#include <string>
+#include <stdexcept>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+template <class S>
+void test() {
+    // Test that a call to reserve() does shrink the string.
+    {
+        S s(1000, 'a');
+        typename S::size_type old_cap = s.capacity();
+        s.resize(20);
+        assert(s.capacity() == old_cap);
+
+        s.reserve();
+        assert(s.capacity() < old_cap);
+    }
+
+    // Test that a call to reserve(smaller-than-capacity) never shrinks the string.
+    {
+        S s(1000, 'a');
+        typename S::size_type old_cap = s.capacity();
+        s.resize(20);
+        assert(s.capacity() == old_cap);
+
+        s.reserve(10);
+        assert(s.capacity() == old_cap);
+    }
+
+    // In particular, test that reserve(0) does NOT shrink the string.
+    {
+        S s(1000, 'a');
+        typename S::size_type old_cap = s.capacity();
+        s.resize(20);
+        assert(s.capacity() == old_cap);
+
+        s.reserve(0);
+        assert(s.capacity() == old_cap);
+    }
+}
+
+int main(int, char**) {
+    test<std::string>();
+
+#if TEST_STD_VER >= 11
+    test<std::basic_string<char, std::char_traits<char>, min_allocator<char> > >();
+#endif
+
+    return 0;
+}

libcxx/test/libcxx/strings/basic.string/string.capacity/reserve.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
-//
-//===----------------------------------------------------------------------===//
-
-// <string>
-
-// void reserve(); // Deprecated in C++20.
-
-// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DISABLE_DEPRECATION_WARNINGS
-
-#include <string>
-#include <stdexcept>
-#include <cassert>
-
-#include "test_macros.h"
-#include "min_allocator.h"
-
-template <class S>
-void
-test()
-{
-    // Tests that a call to reserve() on a long string is equivalent to shrink_to_fit().
-    S s(1000, 'a');
-    typename S::size_type old_cap = s.capacity();
-    s.resize(20);
-    assert(s.capacity() == old_cap);
-    s.reserve();
-    assert(s.capacity() < old_cap);
-}
-
-int main(int, char**)
-{
-    {
-    typedef std::string S;
-    test<S>();
-    }
-#if TEST_STD_VER >= 11
-    {
-    typedef min_allocator<char> A;
-    typedef std::basic_string<char, std::char_traits<char>, A> S;
-    test<S>();
-    }
-#endif
-
-    return 0;
-}