Repository: ashvardanian/StringZilla (language: rust)

Issue:
Missing `sz::string::shrink_to_fit`
The C layer defines the `sz_string_shrink_to_fit`, that is not covered by tests and is not yet used by the C++ API to implement the `shrink_to_fit`.


Discussion / hints:
Hey @ashvardanian can you please explain this issue a more
@Riyazul555, at the second glance, this issue is trickier then I thought, as I don't yet have a `sz_string_shrink_to_fit` implementation even in the C layer. It may not be a good fit for a beginner, but if you are interested, [cppreference.com describes the operation in more detail](https://en.cppreference.com/w/cpp/string/basic_string/shrink_to_fit).

Fix patch:
diff --git a/.github/workflows/release.yml b/.github/workflows/release.yml
index b540f95d..33e768cf 100644
--- a/.github/workflows/release.yml
+++ b/.github/workflows/release.yml
@@ -178,7 +178,7 @@ jobs:
           ref: "main"
 
       - name: Get version
-        id: version
+        id: set_version
         run: |
           version=$(cat VERSION)
           echo "version=$version" >> $GITHUB_OUTPUT
@@ -211,7 +211,7 @@ jobs:
           mkdir "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}/usr/local/include"
           cp include/stringzilla/stringzilla.h "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}/usr/local/include/"
           cp build_release/libstringzillite.so "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}/usr/local/lib/"
-          echo "Package: stringzilla\nVersion: ${{ steps.set_version.outputs.version }}\nMaintainer: Ash Vardanian\nArchitecture: ${{ matrix.arch }}\nDescription: SIMD-accelerated string search, sort, hashes, fingerprints, & edit distances" > "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}/DEBIAN/control"
+          echo -e "Package: stringzilla\nVersion: ${{ steps.set_version.outputs.version }}\nMaintainer: Ash Vardanian\nArchitecture: ${{ matrix.arch }}\nDescription: SIMD-accelerated string search, sort, hashes, fingerprints, & edit distances" > "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}/DEBIAN/control"
           dpkg-deb --build "stringzillite_linux_${{ matrix.arch }}_${{ steps.set_version.outputs.version }}"
 
       - name: Upload library
@@ -291,7 +291,7 @@ jobs:
       - run: git submodule update --init --recursive
 
       - name: Get version
-        id: version
+        id: set_version
         run: |
           version=$(cat VERSION)
           echo "version=$version" >> $GITHUB_OUTPUT
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index f8f156d0..f0f9af6e 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -112,7 +112,7 @@ brew install libomp llvm # MacOS
 Using modern syntax, this is how you build and run the test suite:
 
 ```bash
-cmake -DSTRINGZILLA_BUILD_TEST=1 -B build_debug
+cmake -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_BUILD_TYPE=Debug -B build_debug
 cmake --build build_debug --config Debug          # Which will produce the following targets:
 build_debug/stringzilla_test_cpp20                # Unit test for the entire library compiled for current hardware
 build_debug/stringzilla_test_cpp20_x86_serial     # x86 variant compiled for IvyBridge - last arch. before AVX2
@@ -224,7 +224,7 @@ The base image is only ~3 MB, and it's based on musl libc, which is different fr
 sudo docker run -it --rm -v "$(pwd)":/workspace/StringZilla alpine:latest /bin/ash
 cd /workspace/StringZilla
 apk add --update make cmake g++ gcc
-cmake -DSTRINGZILLA_BUILD_TEST=1 -B build_debug
+cmake -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_BUILD_TYPE=Debug -B build_debug
 cmake --build build_debug --config Debug
 build_debug/stringzilla_test_cpp20
 ```
@@ -240,7 +240,7 @@ sudo docker run -it --rm -v "$(pwd)":/workspace/StringZilla clearlinux:latest /b
 cd /workspace/StringZilla
 swupd update
 swupd bundle-add c-basic dev-utils
-cmake -DSTRINGZILLA_BUILD_TEST=1 -B build_debug
+cmake -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_BUILD_TYPE=Debug -B build_debug
 cmake --build build_debug --config Debug
 build_debug/stringzilla_test_cpp20
 ```
@@ -260,7 +260,9 @@ For CentOS-based __Amazon Linux 2023__:
 sudo docker run -it --rm -v "$(pwd)":/workspace/StringZilla amazonlinux:2023 bash
 cd /workspace/StringZilla
 yum install -y make cmake3 gcc g++
-cmake3 -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DSTRINGZILLA_TARGET_ARCH="ivybridge" -B build_debug
+cmake3 -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_BUILD_TYPE=Debug \
+    -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DSTRINGZILLA_TARGET_ARCH="ivybridge" \
+    -B build_debug
 cmake3 --build build_debug --config Debug --target stringzilla_test_cpp11
 build_debug/stringzilla_test_cpp11
 ```
@@ -272,7 +274,9 @@ Sadly, the newest GCC version it supports is 10, and it can't handle AVX-512 ins
 sudo docker run -it --rm -v "$(pwd)":/workspace/StringZilla amazonlinux:2 bash
 cd /workspace/StringZilla
 yum install -y make cmake3 gcc10 gcc10-c++
-cmake3 -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DSTRINGZILLA_TARGET_ARCH="ivybridge" -B build_debug
+cmake3 -DSTRINGZILLA_BUILD_TEST=1 -DCMAKE_BUILD_TYPE=Debug \
+    -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DSTRINGZILLA_TARGET_ARCH="ivybridge" \
+    -B build_debug
 cmake3 --build build_debug --config Debug --target stringzilla_test_cpp11
 build_debug/stringzilla_test_cpp11
 ```
diff --git a/include/stringzilla/stringzilla.h b/include/stringzilla/stringzilla.h
index 0b079948..cb84f15a 100644
--- a/include/stringzilla/stringzilla.h
+++ b/include/stringzilla/stringzilla.h
@@ -651,11 +651,12 @@ SZ_PUBLIC sz_size_t sz_string_erase(sz_string_t *string, sz_size_t offset, sz_si
 
 /**
  *  @brief  Shrinks the string to fit the current length, if it's allocated on the heap.
- *          Teh reverse operation of ::sz_string_reserve.
+ *          It's the reverse operation of ::sz_string_reserve.
  *
  *  @param string       String to shrink.
  *  @param allocator    Memory allocator to use for the allocation.
  *  @return             Whether the operation was successful. The only failures can come from the allocator.
+ *                      On failure, the string will remain unchanged.
  */
 SZ_PUBLIC sz_ptr_t sz_string_shrink_to_fit(sz_string_t *string, sz_memory_allocator_t *allocator);
 
@@ -3217,7 +3218,7 @@ SZ_PUBLIC sz_ptr_t sz_string_init_length(sz_string_t *string, sz_size_t length,
 
 SZ_PUBLIC sz_ptr_t sz_string_reserve(sz_string_t *string, sz_size_t new_capacity, sz_memory_allocator_t *allocator) {
 
-    sz_assert(string && "String can't be SZ_NULL.");
+    sz_assert(string && allocator && "Strings and allocators can't be SZ_NULL.");
 
     sz_size_t new_space = new_capacity + 1;
     if (new_space <= SZ_STRING_INTERNAL_SPACE) return string->external.start;
@@ -3243,6 +3244,34 @@ SZ_PUBLIC sz_ptr_t sz_string_reserve(sz_string_t *string, sz_size_t new_capacity
     return string->external.start;
 }
 
+SZ_PUBLIC sz_ptr_t sz_string_shrink_to_fit(sz_string_t *string, sz_memory_allocator_t *allocator) {
+
+    sz_assert(string && allocator && "Strings and allocators can't be SZ_NULL.");
+
+    sz_ptr_t string_start;
+    sz_size_t string_length;
+    sz_size_t string_space;
+    sz_bool_t string_is_external;
+    sz_string_unpack(string, &string_start, &string_length, &string_space, &string_is_external);
+
+    // We may already be space-optimal, and in that case we don't need to do anything.
+    sz_size_t new_space = string_length + 1;
+    if (string_space == new_space || !string_is_external) return string->external.start;
+
+    sz_ptr_t new_start = (sz_ptr_t)allocator->allocate(new_space, allocator->handle);
+    if (!new_start) return SZ_NULL_CHAR;
+
+    sz_copy(new_start, string_start, string_length);
+    string->external.start = new_start;
+    string->external.space = new_space;
+    string->external.padding = 0;
+    string->external.length = string_length;
+
+    // Deallocate the old string.
+    if (string_is_external) allocator->free(string_start, string_space, allocator->handle);
+    return string->external.start;
+}
+
 SZ_PUBLIC sz_ptr_t sz_string_expand(sz_string_t *string, sz_size_t offset, sz_size_t added_length,
                                     sz_memory_allocator_t *allocator) {
 
@@ -3333,7 +3362,7 @@ SZ_PUBLIC void sz_fill_serial(sz_ptr_t target, sz_size_t length, sz_u8_t value)
 
     // In case of long strings, skip unaligned bytes, and then fill the rest in 64-bit chunks.
     else {
-        sz_u64_t value64 = (sz_u64_t)(value) * 0x0101010101010101ull;
+        sz_u64_t value64 = (sz_u64_t)value * 0x0101010101010101ull;
         while ((sz_size_t)target & 7ull) *(target++) = value;
         while (target + 8 <= end) *(sz_u64_t *)target = value64, target += 8;
         while (target != end) *(target++) = value;
diff --git a/include/stringzilla/stringzilla.hpp b/include/stringzilla/stringzilla.hpp
index e64ebc44..8082e96d 100644
--- a/include/stringzilla/stringzilla.hpp
+++ b/include/stringzilla/stringzilla.hpp
@@ -1972,6 +1972,12 @@ class basic_string {
      */
     static constexpr size_type npos = SZ_SSIZE_MAX;
 
+    /**
+     *  @brief  The number of characters that can be stored in the internal buffer.
+     *          Depends on the size of the internal buffer for the "Small String Optimization".
+     */
+    static constexpr size_type min_capacity = SZ_STRING_INTERNAL_SPACE - 1;
+
 #pragma region Constructors and STL Utilities
 
     sz_constexpr_if_cpp20 basic_string() noexcept {
@@ -2604,23 +2610,77 @@ class basic_string {
 #pragma region Modifiers
 #pragma region Non-STL API
 
+    /**
+     *  @brief  Resizes the string to a specified number of characters, padding with the specified character if needed.
+     *  @param  count The new size of the string.
+     *  @param  character The character to fill new elements with, if expanding. Defaults to null character.
+     *  @return `true` if the resizing was successful, `false` otherwise.
+     */
     bool try_resize(size_type count, value_type character = '\0') noexcept;
 
+    /**
+     *  @brief  Attempts to reduce memory usage by freeing unused memory.
+     *  @return `true` if the operation was successful and potentially reduced the memory footprint, `false` otherwise.
+     */
+    bool try_shrink_to_fit() noexcept {
+        return _with_alloc([&](sz_alloc_type &alloc) { return sz_string_shrink_to_fit(&string_, &alloc); });
+    }
+
+    /**
+     *  @brief  Attempts to reserve enough space for a specified number of characters.
+     *  @param  capacity The new capacity to reserve.
+     *  @return `true` if the reservation was successful, `false` otherwise.
+     */
     bool try_reserve(size_type capacity) noexcept {
         return _with_alloc([&](sz_alloc_type &alloc) { return sz_string_reserve(&string_, capacity, &alloc); });
     }
 
+    /**
+     *  @brief  Assigns a new value to the string, replacing its current contents.
+     *  @param  other The string view whose contents to assign.
+     *  @return `true` if the assignment was successful, `false` otherwise.
+     */
     bool try_assign(string_view other) noexcept;
 
+    /**
+     *  @brief  Assigns a concatenated sequence to the string, replacing its current contents.
+     *  @param  other The concatenation object representing the sequence to assign.
+     *  @return `true` if the assignment was successful, `false` otherwise.
+     */
     template <typename first_type, typename second_type>
     bool try_assign(concatenation<first_type, second_type> const &other) noexcept;
 
+    /**
+     *  @brief  Attempts to add a single character to the end of the string.
+     *  @param  c The character to add.
+     *  @return `true` if the character was successfully added, `false` otherwise.
+     */
     bool try_push_back(char_type c) noexcept;
 
+    /**
+     *  @brief  Attempts to append a given character array to the string.
+     *  @param  str The pointer to the array of characters to append.
+     *  @param  length The number of characters to append.
+     *  @return `true` if the append operation was successful, `false` otherwise.
+     */
     bool try_append(const_pointer str, size_type length) noexcept;
 
+    /**
+     *  @brief  Attempts to append a string view to the string.
+     *  @param  str The string view to append.
+     *  @return `true` if the append operation was successful, `false` otherwise.
+     */
     bool try_append(string_view str) noexcept { return try_append(str.data(), str.size()); }
 
+    /**
+     *  @brief  Clears the contents of the string and resets its length to 0.
+     *  @return Always returns `true` as this operation cannot fail under normal conditions.
+     */
+    bool try_clear() noexcept {
+        clear();
+        return true;
+    }
+
     /**
      *  @brief  Erases ( @b in-place ) a range of characters defined with signed offsets.
      *  @return Number of characters removed.
@@ -2658,7 +2718,7 @@ class basic_string {
 
         sz_size_t normalized_offset, normalized_length;
         sz_ssize_clamp_interval(size(), signed_start_offset, signed_end_offset, &normalized_offset, &normalized_length);
-        if (!try_preparing_replacement(normalized_offset, normalized_length, replacement)) return false;
+        if (!try_preparing_replacement(normalized_offset, normalized_length, replacement.size())) return false;
         sz_copy(data() + normalized_offset, replacement.data(), replacement.size());
         return true;
     }
@@ -2683,6 +2743,14 @@ class basic_string {
         if (!try_resize(count, character)) throw std::bad_alloc();
     }
 
+    /**
+     *  @brief  Reclaims the unused memory, if any.
+     *  @throw  `std::bad_alloc` if the allocation fails.
+     */
+    void shrink_to_fit() noexcept(false) {
+        if (!try_shrink_to_fit()) throw std::bad_alloc();
+    }
+
     /**
      *  @brief  Informs the string object of a planned change in size, so that it pre-allocate once.
      *  @throw  `std::length_error` if the string is too long.
@@ -3300,10 +3368,19 @@ bool basic_string<char_type_, allocator_>::try_assign(string_view other) noexcep
     sz_size_t string_length;
     sz_string_range(&string_, &string_start, &string_length);
 
-    if (string_length >= other.length()) {
+    // One nasty special case is when the other string is a substring of this string.
+    // We need to handle that separately, as the `sz_string_expand` may invalidate the `other` pointer.
+    if (other.data() >= string_start && other.data() < string_start + string_length) {
+        auto offset_in_this = other.data() - string_start;
+        sz_string_erase(&string_, 0, offset_in_this);
+        sz_string_erase(&string_, other.length(), SZ_SIZE_MAX);
+    }
+    // In some of the other cases, when the assigned string is short, we don't need to re-allocate.
+    else if (string_length >= other.length()) {
         other.copy(string_start, other.length());
         sz_string_erase(&string_, other.length(), SZ_SIZE_MAX);
     }
+    // In the common case, however, we need to allocate.
     else {
         if (!_with_alloc([&](sz_alloc_type &alloc) {
                 string_start = sz_string_expand(&string_, SZ_SIZE_MAX, other.length(), &alloc);
@@ -3330,10 +3407,21 @@ bool basic_string<char_type_, allocator_>::try_push_back(char_type c) noexcept {
 template <typename char_type_, typename allocator_>
 bool basic_string<char_type_, allocator_>::try_append(const_pointer str, size_type length) noexcept {
     return _with_alloc([&](sz_alloc_type &alloc) {
-        auto old_size = size();
+        // Sometimes we are inserting part of this string into itself.
+        // By the time `sz_string_expand` finished, the old `str` pointer may be invalidated,
+        // so we need to handle that special case separately.
+        auto this_span = span();
+        if (str >= this_span.begin() && str < this_span.end()) {
+            auto str_offset_in_this = str - data();
         sz_ptr_t start = sz_string_expand(&string_, SZ_SIZE_MAX, length, &alloc);
         if (!start) return false;
-        sz_copy(start + old_size, str, length);
+            sz_copy(start + this_span.size(), start + str_offset_in_this, length);
+        }
+        else {
+            sz_ptr_t start = sz_string_expand(&string_, SZ_SIZE_MAX, length, &alloc);
+            if (!start) return false;
+            sz_copy(start + this_span.size(), str, length);
+        }
         return true;
     });
 }


Test patch:
diff --git a/scripts/test.cpp b/scripts/test.cpp
index 38fe1ea8..12465c94 100644
--- a/scripts/test.cpp
+++ b/scripts/test.cpp
@@ -431,6 +431,12 @@ static void test_api_mutable() {
     assert_scoped(str s = "obsolete", s.assign(s, 4), s == "lete");                   // Partial self-assignment
     assert_scoped(str s = "obsolete", s.assign(s, 4, 3), s == "let");                 // Partial self-assignment
 
+    // Self-assignment is a special case of assignment.
+    assert_scoped(str s = "obsolete", s = s, s == "obsolete");
+    assert_scoped(str s = "obsolete", s.assign(s), s == "obsolete");
+    assert_scoped(str s = "obsolete", s.assign(s.data(), 2), s == "ob");
+    assert_scoped(str s = "obsolete", s.assign(s.data(), s.size()), s == "obsolete");
+
     // Allocations, capacity and memory management.
     assert_scoped(str s, s.reserve(10), s.capacity() >= 10);
     assert_scoped(str s, s.resize(10), s.size() == 10);
@@ -438,6 +444,7 @@ static void test_api_mutable() {
     assert(str().max_size() > 0);
     assert(str().get_allocator() == std::allocator<char>());
     assert(std::strcmp(str("c_str").c_str(), "c_str") == 0);
+    assert_scoped(str s = "hello", s.shrink_to_fit(), s.capacity() <= sz::string::min_capacity);
 
     // Concatenation.
     // Following are missing in strings, but are present in vectors.
@@ -627,6 +634,28 @@ static void test_api_readonly_extensions() {
 void test_api_mutable_extensions() {
     using str = sz::string;
 
+    // Try methods.
+    assert(str("obsolete").try_assign("hello"));
+    assert(str().try_reserve(10));
+    assert(str().try_resize(10));
+    assert(str("__").try_insert(1, "test"));
+    assert(str("test").try_erase(1, 2));
+    assert(str("test").try_clear());
+    assert(str("test").try_replace(1, 2, "aaaa"));
+    assert(str("test").try_push_back('a'));
+    assert(str("test").try_shrink_to_fit());
+
+    // Self-referencing methods.
+    assert_scoped(str s = "test", s.try_assign(s.view()), s == "test");
+    assert_scoped(str s = "test", s.try_assign(s.view().sub(1, 2)), s == "e");
+    assert_scoped(str s = "test", s.try_append(s.view().sub(1, 2)), s == "teste");
+
+    // Try methods going beyond and beneath capacity threshold.
+    assert_scoped(str s = "0123456789012345678901234567890123456789012345678901234567890123", // 64 symbols at start
+                  s.try_append(s) && s.try_append(s) && s.try_append(s) && s.try_append(s) && s.try_clear() &&
+                      s.try_shrink_to_fit(),
+                  s.capacity() < sz::string::min_capacity);
+
     // Same length replacements.
     assert_scoped(str s = "hello", s.replace_all("xx", "xx"), s == "hello");
     assert_scoped(str s = "hello", s.replace_all("l", "1"), s == "he11o");