diff options
Diffstat (limited to 'libs/kstd')
| -rw-r--r-- | libs/kstd/CMakeLists.txt | 8 | ||||
| -rw-r--r-- | libs/kstd/gdb/__init__.py | 2 | ||||
| -rw-r--r-- | libs/kstd/gdb/string.py | 16 | ||||
| -rw-r--r-- | libs/kstd/kstd/bits/basic_string.hpp | 1404 | ||||
| -rw-r--r-- | libs/kstd/kstd/string | 320 | ||||
| -rw-r--r-- | libs/kstd/kstd/string.test.cpp | 2090 |
6 files changed, 3413 insertions, 427 deletions
diff --git a/libs/kstd/CMakeLists.txt b/libs/kstd/CMakeLists.txt index 0f647614..5a957573 100644 --- a/libs/kstd/CMakeLists.txt +++ b/libs/kstd/CMakeLists.txt @@ -96,5 +96,11 @@ if(BUILD_TESTING) enable_coverage("kstd_tests") endif() - catch_discover_tests("kstd::tests" ${CATCH_TEST_ARGS}) + file(MAKE_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/bht_results") + + catch_discover_tests("kstd::tests" + REPORTER junit + OUTPUT_DIR "${CMAKE_CURRENT_BINARY_DIR}/bht_results" + OUTPUT_SUFFIX ".xml" + ) endif()
\ No newline at end of file diff --git a/libs/kstd/gdb/__init__.py b/libs/kstd/gdb/__init__.py index c5d1e539..4c4b3415 100644 --- a/libs/kstd/gdb/__init__.py +++ b/libs/kstd/gdb/__init__.py @@ -12,7 +12,7 @@ from .smart_pointers import ( def build_pretty_printers(): pp = gdb.printing.RegexpCollectionPrettyPrinter("kstd") pp.add_printer("vector", "^kstd::vector<.*>$", KstdVectorPrinter) - pp.add_printer("string", "^kstd::string$", KstdStringPrinter) + pp.add_printer("string", "^kstd::basic_string<.*>$", KstdStringPrinter) pp.add_printer("unique_ptr", "^kstd::unique_ptr<.*>$", KstdUniquePtrPrinter) pp.add_printer("shared_ptr", "^kstd::shared_ptr<.*>$", KstdSharedPtrPrinter) pp.add_printer("observer_ptr", "^kstd::observer_ptr<.*>$", KstdObserverPtrPrinter) diff --git a/libs/kstd/gdb/string.py b/libs/kstd/gdb/string.py index 73c22d64..b60cbe67 100644 --- a/libs/kstd/gdb/string.py +++ b/libs/kstd/gdb/string.py @@ -5,21 +5,17 @@ class KstdStringPrinter(gdb.ValuePrinter): def __init__(self, val): self.__val = val + self.__data = val["m_data"] + self.__length = val["m_length"] def to_string(self): - storage = self.__val["m_storage"] - storage_size = int(storage["m_size"]) - - if storage_size <= 0: + if int(self.__length) <= 0: return '""' - data_pointer = storage["m_data"] - string_length = storage_size - 1 - try: - if hasattr(data_pointer, "lazy_string"): - return data_pointer.lazy_string(encoding="utf-8", length=string_length) - return data_pointer.string(encoding="utf-8", length=string_length) + if hasattr(self.__data, "lazy_string"): + return self.__data.lazy_string(encoding="utf-8", length=self.__length) + return self.__data.string(encoding="utf-8", length=self.__length) except gdb.error: return "<unreadable memory>" diff --git a/libs/kstd/kstd/bits/basic_string.hpp b/libs/kstd/kstd/bits/basic_string.hpp new file mode 100644 index 00000000..5d2eecd7 --- /dev/null +++ b/libs/kstd/kstd/bits/basic_string.hpp @@ -0,0 +1,1404 @@ +#ifndef KSTD_BITS_BASIC_STRING_HPP +#define KSTD_BITS_BASIC_STRING_HPP + +#include <kstd/allocator> +#include <kstd/bits/concepts.hpp> +#include <kstd/os/error.hpp> +#include <kstd/ranges> + +#include <algorithm> +#include <array> +#include <compare> +#include <cstddef> +#include <initializer_list> +#include <iterator> +#include <limits> +#include <memory> +#include <span> +#include <string_view> +#include <type_traits> +#include <utility> + +namespace kstd +{ + + template<typename CharacterType> + using char_traits = std::char_traits<CharacterType>; // NOLINT + + template<typename CharacterType, typename Traits = kstd::char_traits<CharacterType>, + typename Allocator = kstd::allocator<CharacterType>> + struct basic_string + + { + //! The character traits of this string. + using traits_type = Traits; + //! The type of character stored in this string. + using value_type = CharacterType; + //! The allocator type used for memory allocations by this string. + using allocator_type = Allocator; + //! The type of all sizes in this string. + using size_type = std::allocator_traits<Allocator>::size_type; + //! The integer type used to represent differences in positions in this string. + using difference_type = std::allocator_traits<Allocator>::difference_type; + //! The type of a reference to an element of this string. + using reference = value_type &; + //! The type of a reference to a constant element of this string. + using const_reference = value_type const &; + //! The type of a pointer to an element of this string. + using pointer = std::allocator_traits<Allocator>::pointer; + //! The type of a pointer to a constant element of this string. + using const_pointer = std::allocator_traits<Allocator>::const_pointer; + //! The type of an iterator to elements of this string. + using iterator = pointer; + //! The type of an iterator to constant elements of this string. + using const_iterator = const_pointer; + //! The type of an iterator to elements of this string, preseting the in reverse order. + using reverse_iterator = std::reverse_iterator<iterator>; + //! The type of an iterator to constant elements of this string, preseting the in reverse order. + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + //! A constant representing a non-existant position in this string. + constexpr auto static inline npos = static_cast<size_type>(-1); + + //! Construct an empty string. + basic_string() noexcept(noexcept(Allocator{})) + : basic_string{Allocator{}} + {} + + //! Construct an empty basic string with the given allocator + //! + //! @param allocator The allocator to use for memory allocations in this string. + explicit basic_string(Allocator const & allocator) + : m_allocator{allocator} + , m_data{m_sso_buffer} + { + update_length(0); + } + + //! Construct a string with a single character. + //! + //! @param character The character to initialize the string with. + explicit constexpr basic_string(value_type character) + : basic_string{Allocator{}} + { + m_data[0] = character; + update_length(1); + } + + //! Construct a string with a given number of copies of a given character. + //! + //! @param count The number of characters. + //! @param value The value to use. + //! @param allocator The allocator to use for memory allocations in this string. + constexpr basic_string(size_type count, CharacterType value, Allocator const & allocator = Allocator{}) + : basic_string{allocator} + { + if (count > capacity()) + { + update_data(allocate_buffer(count, true)); + } + + std::ranges::fill_n(m_data, count, value); + update_length(count); + } + + //! Construct a string with the elements in the range denoted by two given iterators. + //! + //! @param first The iterator to the first element. + //! @param last The iterator beyond the last element. + //! @param allocator The allocator to use for memory allocation in this string. + //! @tparam InputIterator an iterator type satisfying the InputIterator concept. + template<typename InputIterator> + constexpr basic_string(InputIterator first, InputIterator last, Allocator const & allocator = Allocator{}) + : basic_string{allocator} + { + forward_from(first, last); + } + + //! Construct a string with the contents of a given range. + //! + //! @param range The range to use elements from. + //! @param allocator The allocator to use for memory allocation in this string. + template<bits::container_compatible_range<CharacterType> Range> + constexpr basic_string(kstd::from_range_t, Range && range, Allocator const & allocator = Allocator{}) + : basic_string{allocator} + { + forward_from(std::ranges::begin(std::forward<Range>(range)), std::ranges::end(std::forward<Range>(range))); + } + + //! Construct a string with the contents of a given range. + //! + //! @param source The start of the source range. + //! @param count The number of elements to copy. + //! @param allocator The allocator to use for memory allocation in this string. + constexpr basic_string(CharacterType const * source, size_type count, Allocator const & allocator = Allocator{}) + : basic_string{allocator} + { + if (!source && count) + { + os::panic("Tried to construct string from null pointer!"); + } + + if (count > capacity()) + { + update_data(allocate_buffer(count, true)); + } + + traits_type::copy(m_data, source, count); + update_length(count); + } + + //! Construct a string from a given null-terminated, C-style string. + constexpr basic_string(CharacterType const * string, Allocator const & allocator = Allocator{}) + : basic_string{string, traits_type::length(string), allocator} + {} + + //! Construction from nullptr is prohibited. + constexpr basic_string(std::nullptr_t) = delete; + + //! Construct a string from a string view like object. + //! + //! @param view_like An object that is implicitly convertible to a string view. + //! @param allocator The allocator to use for memory allocation in this string. + template<typename StringViewLike> + requires(std::is_convertible_v<StringViewLike const &, std::basic_string_view<CharacterType, Traits>> && + !std::is_convertible_v<StringViewLike const &, CharacterType const *>) + explicit constexpr basic_string(StringViewLike const & view_like, Allocator const & allocator = Allocator{}) + : basic_string{allocator} + { + auto converted = std::basic_string_view<value_type, traits_type>{view_like}; + forward_from(std::ranges::begin(converted), std::ranges::end(converted)); + } + + //! Construct a string from a substring of a string view like object. + //! + //! @param view_like An object that is implicitly convertible to a string view. + //! @param from The starting position in the string view like object. + //! @param count The maximum number of character to copy from the string view like object. + //! @param allocator The allocator to use for memory allocation in this string. + template<typename StringViewLike> + requires std::is_convertible_v<StringViewLike const &, std::basic_string_view<CharacterType, Traits>> + constexpr basic_string(StringViewLike const & view_like, size_type from, size_type count, + Allocator const & allocator = Allocator{}) + : basic_string{std::basic_string_view<value_type, traits_type>{view_like}.substr(from, count), allocator} + {} + + //! Construct a new string as a copy of an existing one. + //! + //! @param other The string to copy from. + constexpr basic_string(basic_string const & other) + : basic_string{other.data(), other.size(), + std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.m_allocator)} + {} + + //! Construct a new string by moving from an existing one. + //! + //! @param other The string to move from. + constexpr basic_string(basic_string && other) noexcept + : m_allocator{std::move(other.m_allocator)} + , m_length{other.m_length} + { + if (other.in_sso_state()) + { + m_data = m_sso_buffer; + traits_type::copy(m_data, other.m_data, m_length + 1); + } + else + { + m_data = other.m_data; + other.m_data = other.m_sso_buffer; + m_heap_capacity = other.m_heap_capacity; + } + + other.update_length(0); + } + + //! Destroy a string, releasing all resources. + constexpr ~basic_string() + { + release_buffer(); + } + + //! Replace the contents of this string with a copy of the contents of another one. + //! + //! @param other The string to copy from. + //! @return A reference to this string. + constexpr auto operator=(basic_string const & other) -> basic_string & + { + if (this == &other) + { + return *this; + } + + if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value) + { + if (m_allocator != other.m_allocator) + { + release_buffer(); + m_data = m_sso_buffer; + } + m_allocator = other.m_allocator; + } + + if (other.in_sso_state()) + { + if (!in_sso_state()) + { + release_buffer(); + m_data = m_sso_buffer; + } + traits_type::copy(m_sso_buffer, other.m_sso_buffer, other.m_length + 1); + } + else + { + if (in_sso_state() || m_heap_capacity < other.m_length) + { + update_data(allocate_buffer(other.m_length, true)); + traits_type::copy(m_data, other.m_data, other.m_length + 1); + } + else + { + traits_type::copy(m_data, other.m_data, other.m_length + 1); + } + } + + update_length(other.m_length); + return *this; + } + + //! Replace the contents of this string by moving from another one. + //! + //! @param other The string to move from. + //! @return A reference to this string. + constexpr auto operator=(basic_string && other) noexcept( + std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value || + std::allocator_traits<allocator_type>::is_always_equal::value) -> basic_string & + { + if (this == &other) + { + return *this; + } + + if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value) + { + if (m_allocator != other.m_allocator) + { + release_buffer(); + m_data = m_sso_buffer; + } + m_allocator = std::move(other.m_allocator); + } + + if (other.in_sso_state()) + { + if (!in_sso_state()) + { + release_buffer(); + m_data = m_sso_buffer; + } + traits_type::copy(m_sso_buffer, other.m_sso_buffer, other.m_length + 1); + } + else if (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value || + m_allocator == other.m_allocator) + { + release_buffer(); + m_data = std::exchange(other.m_data, other.m_sso_buffer); + m_heap_capacity = other.m_heap_capacity; + } + else + { + if (in_sso_state() || m_heap_capacity < other.m_length) + { + update_data(allocate_buffer(other.m_length, true)); + traits_type::copy(m_data, other.m_data, other.m_length + 1); + } + else + { + traits_type::copy(m_data, other.m_data, other.m_length + 1); + } + } + + update_length(other.m_length); + other.update_length(0); + + return *this; + } + + //! Replace the contents of this string with a copy of a given C-style string. + //! + //! @param string The C-style string to copy from. + //! @return A reference to this string. + constexpr auto operator=(CharacterType const * string) -> basic_string & + { + if (string == nullptr) + { + os::panic("Tried to construct string from null pointer!"); + } + + auto incoming_length = traits_type::length(string); + + if (capacity() < incoming_length) + { + auto new_buffer = allocate_buffer(incoming_length, true); + traits_type::copy(new_buffer.data(), string, incoming_length + 1); + update_data(new_buffer); + } + else + { + traits_type::move(m_data, string, incoming_length); + } + + update_length(incoming_length); + return *this; + } + + //! Replace the contents of this string with a given character. + //! + //! @param character The character to use to replace the contents of this string. + //! @return A reference to this string. + constexpr auto operator=(CharacterType character) -> basic_string & + { + m_data[0] = character; + update_length(1); + return *this; + } + + //! Replace the contents of this string with the elements of a given initializer list. + //! + //! @param list The initializer list to copy from. + //! @return A reference to this string. + constexpr auto operator=(std::initializer_list<CharacterType> list) -> basic_string & + { + if (list.size() > capacity()) + { + update_data(allocate_buffer(list.size(), true)); + } + + for (auto i = 0uz; auto elem : list) + { + traits_type::assign(m_data[i], elem); + } + + update_length(list.size()); + return *this; + } + + //! Replace the contents of this string with the one from a given strinv view like object. + //! + //! @param view_like The string view like object to copy from. + //! @return A reference to this string. + template<typename StringViewLike> + requires(std::is_convertible_v<StringViewLike const &, std::basic_string_view<CharacterType, Traits>> && + !std::is_convertible_v<StringViewLike const &, CharacterType const *>) + constexpr auto operator=(StringViewLike const & view_like) -> basic_string & + { + auto converted = std::basic_string_view<value_type, traits_type>{view_like}; + + if (converted.size() > capacity()) + { + update_data(allocate_buffer(converted.size(), true)); + } + + traits_type::copy(m_data, converted.data(), converted.size()); + update_length(converted.size()); + return *this; + } + + //! Assignment from nullptr is prohibited. + constexpr auto operator=(std::nullptr_t) = delete; + + //! Get the allocator used by this string. + //! + //! @return A copy of the allocator used by this string. + [[nodiscard]] constexpr auto get_allocator() const noexcept(noexcept(Allocator{Allocator{}})) -> allocator_type + { + return m_allocator; + } + + //! Get the element at the given position in this string. + //! + //! @param position The position from which to retrieve the element. + //! @return A reference to the character at the given position. + [[nodiscard]] constexpr auto at(size_type position) -> reference + { + if (position >= size()) + { + os::panic("Invalid index in string element access"); + } + + return m_data[position]; + } + + //! Get the element at the given position in this string. + //! + //! @param position The position from which to retrieve the element. + //! @return A reference to the character at the given position. + [[nodiscard]] constexpr auto at(size_type position) const -> const_reference + { + if (position >= size()) + { + os::panic("Invalid index in string element access"); + } + + return m_data[position]; + } + + //! Get the element at the given position in this string. + //! + //! @param position The position from which to retrieve the element. + //! @return A reference to the character at the given position. + [[nodiscard]] constexpr auto operator[](size_type position) noexcept -> reference + { + return m_data[position]; + } + + //! Get the element at the given position in this string. + //! + //! @param position The position from which to retrieve the element. + //! @return A reference to the character at the given position. + [[nodiscard]] constexpr auto operator[](size_type position) const noexcept -> const_reference + { + return m_data[position]; + } + + //! Get the first character in this string. + //! + //! @return A reference to first character. + [[nodiscard]] constexpr auto front() noexcept -> reference + { + return (*this)[0]; + } + + //! Get the first character in this string. + //! + //! @return A reference to first character. + [[nodiscard]] constexpr auto front() const noexcept -> const_reference + { + return (*this)[0]; + } + + //! Get the last character in this string. + //! + //! @return A reference to last character. + [[nodiscard]] constexpr auto back() noexcept -> reference + { + return (*this)[size() - 1]; + } + + //! Get the last character in this string. + //! + //! @return A reference to last character. + [[nodiscard]] constexpr auto back() const noexcept -> const_reference + { + return (*this)[size() - 1]; + } + + //! Get a pointer to the underlying data of this string. + //! + //! @return A pointer to the underlying data of this string. + [[nodiscard]] constexpr auto data() noexcept -> pointer + { + return m_data; + } + + //! Get a pointer to the underlying data of this string. + //! + //! @return A pointer to the underlying data of this string. + [[nodiscard]] constexpr auto data() const noexcept -> pointer + { + return m_data; + } + + //! Get a pointer to the null-terminated underlying data of this string. + //! + //! @return A pointer to the null-terminated underlying data of this string. + [[nodiscard]] constexpr auto c_str() noexcept -> pointer + { + return m_data; + } + + //! Get a pointer to the null-terminated underlying data of this string. + //! + //! @return A pointer to the null-terminated underlying data of this string. + [[nodiscard]] constexpr auto c_str() const noexcept -> pointer + { + return m_data; + } + + //! Get a non-modifiable view of this string. + operator std::basic_string_view<value_type, traits_type>() const noexcept + { + return {data(), size()}; + } + + //! Get an iterator to the beginning of this string. + [[nodiscard]] constexpr auto begin() noexcept -> iterator + { + return data(); + } + + //! Get a const iterator to the beginning of this string. + [[nodiscard]] constexpr auto begin() const noexcept -> const_iterator + { + return data(); + } + + //! Get a const iterator to the beginning of this string. + [[nodiscard]] constexpr auto cbegin() const noexcept -> const_iterator + { + return data(); + } + + //! Get an iterator to the end of this string. + [[nodiscard]] constexpr auto end() noexcept -> iterator + { + return data() + size(); + } + + //! Get a const iterator to the end of this string. + [[nodiscard]] constexpr auto end() const noexcept -> const_iterator + { + return data() + size(); + } + + //! Get a const iterator to the end of this string. + [[nodiscard]] constexpr auto cend() const noexcept -> const_iterator + { + return data() + size(); + } + + //! Get a reverse iterator to the beginning of this string. + [[nodiscard]] constexpr auto rbegin() noexcept -> reverse_iterator + { + return end(); + } + + //! Get a const reverse iterator to the beginning of this string. + [[nodiscard]] constexpr auto rbegin() const noexcept -> const_reverse_iterator + { + return end(); + } + + //! Get a const reverse iterator to the beginning of this string. + [[nodiscard]] constexpr auto crbegin() const noexcept -> const_reverse_iterator + { + return end(); + } + + //! Get a reverse iterator to the end of this string. + [[nodiscard]] constexpr auto rend() noexcept -> reverse_iterator + { + return begin(); + } + + //! Get a const reverse iterator to the end of this string. + [[nodiscard]] constexpr auto rend() const noexcept -> const_reverse_iterator + { + return begin(); + } + + //! Get a const reverse iterator to the end of this string. + [[nodiscard]] constexpr auto crend() const noexcept -> const_reverse_iterator + { + return begin(); + } + + //! Check if this string is empty. + //! + //! @return @p true iff. the string is empty, @p false otherwise. + [[nodiscard]] constexpr auto empty() const noexcept -> bool + { + return size() == 0uz; + } + + //! Get the size of this string. + //! + //! @return the number of characters in this string. + [[nodiscard]] constexpr auto size() const noexcept -> size_type + { + return m_length; + } + + //! Get the length of this string. + //! + //! @return the number of characters in this string. + [[nodiscard]] constexpr auto length() const noexcept -> size_type + { + return size(); + } + + //! Get the maximum possible size for this string. + //! + //! @return the maximum number of elements this string can hold. + [[nodiscard]] constexpr auto max_size() const noexcept -> size_type + { + return std::numeric_limits<size_type>::max() / sizeof(value_type) - 1; + } + + //! Reserve at least the given amount of memory. + //! + //! @param new_capacity The new, minimum, target capacity. + constexpr auto reserve(size_type new_capacity) -> void + { + if (new_capacity > max_size()) + { + os::panic("Tried to allocate more memory than possible"); + } + + if (new_capacity <= capacity()) + { + return; + } + + auto new_buffer = allocate_buffer(new_capacity); + traits_type::copy(new_buffer.data(), data(), length() + 1); + update_data(new_buffer); + } + + //! Shrink the buffer of this vector to fit the current content. + constexpr auto shrink_to_fit() -> void + { + if (in_sso_state()) + { + return; + } + else if (length() <= sso_length) + { + auto old_capacity = m_heap_capacity; + traits_type::copy(m_sso_buffer, m_data, m_length + 1); + std::allocator_traits<allocator_type>::deallocate(m_allocator, m_data, old_capacity); + m_data = m_sso_buffer; + } + else + { + auto new_buffer = allocate_buffer(m_length + 1); + traits_type::copy(new_buffer.data(), m_data, m_length + 1); + release_buffer(); + update_data(new_buffer); + } + } + + //! Get the currently allocated capacity of this string + //! + //! @return the number of elements that can be stored in this string without causing a reallocation. + [[nodiscard]] constexpr auto capacity() const noexcept -> size_type + { + return (in_sso_state() ? std::size(m_sso_buffer) : m_heap_capacity) - 1; + } + + //! Clear the content of this string. + constexpr auto clear() -> void + { + update_length(0); + } + + //! Insert a sequence of identical characters at the given index. + //! + //! @param index The position to insert the characters at. + //! @param count The number of characters to insert. + //! @param character The character to insert. + //! @return A reference to this string. + constexpr auto insert(size_type index, size_type count, CharacterType character) -> basic_string & + { + if (index > size()) + { + os::panic("Index out of bounds while inserting into string"); + } + + if (count == 0uz) + { + return *this; + } + + auto new_length = size() + count; + + if (capacity() < new_length) + { + auto new_buffer = allocate_buffer(new_length, true); + traits_type::copy(new_buffer.data(), m_data, index); + std::ranges::fill_n(new_buffer.data() + index, count, character); + traits_type::copy(new_buffer.data() + index + count, m_data + index, size() - index); + update_data(new_buffer); + } + else + { + traits_type::move(m_data + index + count, m_data + index, size() - index); + std::ranges::fill_n(m_data + index, count, character); + } + + update_length(new_length); + return *this; + } + + //! Insert a C-style string into this string at a given position. + //! + //! @param index The position to insert the data at. + //! @param string The string to insert. + constexpr auto insert(size_type index, CharacterType const * string) -> basic_string & + { + if (string == nullptr) + { + os::panic("Tried to insert nullptr string"); + } + + return do_insert(index, std::basic_string_view<value_type, traits_type>{string}); + } + + //! Append a character to this string. + //! + //! @param character The character to append. + constexpr auto push_back(CharacterType character) -> void + { + auto new_length = m_length + 1; + + if (capacity() < new_length) + { + auto new_buffer = allocate_buffer(new_length); + traits_type::copy(new_buffer.data(), m_data, m_length); + update_data(new_buffer); + } + + m_data[m_length] = character; + update_length(new_length); + } + + //! Remove the last character of this string. + constexpr auto pop_back() -> void + { + if (m_length > 0) + { + update_length(m_length - 1); + } + } + + //! Append a number of copies of a given character to this string. + //! + //! @param count The number of copies to append. + //! @param character The character to append. + //! @return A reference to this string. + constexpr auto append(size_type count, CharacterType character) -> basic_string & + { + if (count == 0) + { + return *this; + } + + auto new_length = m_length + count; + if (capacity() < new_length) + { + auto new_buffer = allocate_buffer(new_length); + traits_type::copy(new_buffer.data(), m_data, m_length); + update_data(new_buffer); + } + + std::ranges::fill_n(m_data + m_length, count, character); + update_length(new_length); + + return *this; + } + + //! Append a substring of a given C-style string to this string. + //! + //! @param string The string to append. + //! @param count The number of characters of that string to append. + //! @return A reference to this string. + constexpr auto append(CharacterType const * string, std::size_t count) -> basic_string & + { + if (string == nullptr) + { + os::panic("Attempted to append nullptr string"); + } + + if (count == 0) + { + return *this; + } + + auto new_length = m_length + count; + if (capacity() < new_length) + { + auto new_buffer = allocate_buffer(new_length); + traits_type::copy(new_buffer.data(), m_data, m_length); + traits_type::copy(new_buffer.data() + m_length, string, count); + update_data(new_buffer); + } + else + { + traits_type::copy(m_data + m_length, string, count); + } + + update_length(new_length); + + return *this; + } + + //! Append a C-style string to this string. + //! + //! @param string The string to append. + //! @return A reference to this string. + constexpr auto append(CharacterType const * string) -> basic_string & + { + return append(string, traits_type::length(string)); + } + + //! Append to this string by copying from a given string view like object + //! + //! @param view_like The string view like object to copy from. + //! @return A reference to this string. + template<typename StringViewLike> + requires(std::is_convertible_v<StringViewLike const &, std::basic_string_view<CharacterType, Traits>> && + !std::is_convertible_v<StringViewLike const &, CharacterType const *>) + constexpr auto append(StringViewLike const & view_like) -> basic_string & + { + auto converted = std::basic_string_view<value_type, traits_type>{view_like}; + return append(converted.data(), converted.length()); + } + + //! Append a string to this string. + //! + //! @param string The string to append. + //! @return A reference to this string. + constexpr auto append(basic_string const & string) -> basic_string & + { + return append(string.c_str(), string.length()); + } + + //! Append a string to this string + //! + //! @param string The string to append. + //! @return A reference to this string. + constexpr auto operator+=(basic_string const & string) -> basic_string & + { + return append(string); + } + + //! Append a character to this string + //! + //! @param character The character to append. + //! @return A reference to this string. + constexpr auto operator+=(value_type character) -> basic_string & + { + push_back(character); + return *this; + } + + //! Swap the contents of this string with another one. + //! + //! @param other The string to swap contents with. + constexpr auto + swap(basic_string & other) noexcept(std::allocator_traits<allocator_type>::propagate_on_container_swap::value || + std::allocator_traits<allocator_type>::is_always_equal::value) -> void + { + using std::swap; + + if (this == &other) + { + return; + } + + if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_swap::value) + { + swap(m_allocator, other.m_allocator); + } + + if (!in_sso_state() && !other.in_sso_state()) + { + swap(m_data, other.m_data); + swap(m_heap_capacity, other.m_heap_capacity); + } + else if (in_sso_state() && !other.in_sso_state()) + { + auto new_data = std::exchange(other.m_data, other.m_sso_buffer); + auto new_heap_capacity = other.m_heap_capacity; + + traits_type::copy(other.m_data, m_data, m_length + 1); + + m_data = new_data; + m_heap_capacity = new_heap_capacity; + } + else if (!in_sso_state() && other.in_sso_state()) + { + auto new_data = std::exchange(m_data, m_sso_buffer); + auto new_heap_capacity = m_heap_capacity; + + traits_type::copy(m_data, other.m_data, other.m_length + 1); + + other.m_data = new_data; + other.m_heap_capacity = new_heap_capacity; + } + else + { + auto temporary_buffer = std::array<value_type, sso_capacity>{}; + + traits_type::copy(temporary_buffer.data(), m_data, m_length + 1); + traits_type::copy(m_data, other.m_data, other.m_length + 1); + traits_type::copy(other.m_data, temporary_buffer.data(), m_length + 1); + } + + swap(m_length, other.m_length); + } + + //! Concatenate two string. + //! + //! @param lhs The left hand side string. + //! @param rhs The right hand side string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string const & lhs, basic_string const & rhs) -> basic_string + { + auto result = lhs; + result.append(rhs); + return result; + } + + //! Concatenate a string an a C-style string. + //! + //! @param lhs The right hand side string. + //! @param rhs The left hand side C-style string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string const & lhs, CharacterType const * rhs) -> basic_string + { + auto result = lhs; + result.append(rhs); + return result; + } + + //! Create a new string by appending a character to a string. + //! + //! @param lhs The string. + //! @param rhs The character to append. + //! @return A new string with the character appended to the string. + [[nodiscard]] constexpr friend auto operator+(basic_string const & lhs, CharacterType rhs) -> basic_string + { + auto result = lhs; + result.push_back(rhs); + return result; + } + + //! Contcatenate a C-style string and a string. + //! + //! @param lhs The left hand side C-style string. + //! @param rhs The right hand side string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(const_pointer lhs, basic_string const & rhs) -> basic_string + { + auto result = rhs; + result.insert(0, lhs); + return result; + } + + //! Create a new string by prepending a character to a string. + //! + //! @param lhs The character to prepend. + //! @param rhs The string + //! @return A new string with the character prepended to the string. + [[nodiscard]] constexpr friend auto operator+(CharacterType lhs, basic_string const & rhs) -> basic_string + { + auto result = rhs; + result.insert(0, lhs); + return result; + } + + //! Contcatenate two strings. + //! + //! @param lhs The left hand side string. + //! @param rhs The right hand side string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string && lhs, basic_string && rhs) -> basic_string + { + lhs.append(rhs); + return std::move(lhs); + } + + //! Contcatenate two strings. + //! + //! @param lhs The left hand side string. + //! @param rhs The right hand side string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string && lhs, basic_string const & rhs) -> basic_string + { + lhs.append(rhs); + return std::move(lhs); + } + + //! Contcatenate a string and a C-style string. + //! + //! @param lhs The left hand side string. + //! @param rhs The right hand side C-style string. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string && lhs, const_pointer rhs) -> basic_string + { + lhs.append(rhs); + return std::move(lhs); + } + + //! Append a character to a string. + //! + //! @param lhs The string to append to. + //! @param rhs The character to append. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string && lhs, value_type rhs) -> basic_string + { + lhs.push_back(rhs); + return std::move(lhs); + } + + //! Contcatenate two strings + //! + //! @param lhs The string to prepend. + //! @param rhs The string to append to. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(basic_string const & lhs, basic_string && rhs) -> basic_string + { + rhs.insert(0, lhs); + return std::move(rhs); + } + + //! Contcatenate a C-style string and a string. + //! + //! @param lhs The C-style string to prepend. + //! @param rhs The string to prepend to. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(const_pointer lhs, basic_string && rhs) -> basic_string + { + rhs.insert(0, lhs); + return std::move(rhs); + } + + //! Prepend a character to a string. + //! + //! @param lhs The character to prepend. + //! @param rhs The string to prepend to. + //! @return The concatenation of the two strings. + [[nodiscard]] constexpr friend auto operator+(value_type lhs, basic_string && rhs) -> basic_string + { + rhs.insert(0, 1, lhs); + return std::move(rhs); + } + + [[nodiscard]] constexpr friend auto operator==(basic_string const & lhs, basic_string const & rhs) noexcept -> bool + { + if (lhs.size() != rhs.size()) + { + return false; + } + + if (lhs.size() == 0uz) + { + return true; + } + + return traits_type::compare(lhs.data(), rhs.data(), lhs.size()) == 0; + } + + [[nodiscard]] constexpr friend auto operator==(basic_string const & lhs, + std::basic_string_view<value_type, traits_type> const & rhs) noexcept + -> bool + { + if (lhs.size() != rhs.size()) + { + return false; + } + + if (lhs.size() == 0uz) + { + return true; + } + + return traits_type::compare(lhs.data(), rhs.data(), rhs.size()) == 0; + } + + [[nodiscard]] constexpr friend auto operator==(std::basic_string_view<value_type, traits_type> const & lhs, + basic_string const & rhs) noexcept -> bool + { + if (lhs.size() != rhs.size()) + { + return false; + } + + if (lhs.size() == 0uz) + { + return true; + } + + return traits_type::compare(lhs.data(), rhs.data(), lhs.size()) == 0; + } + + [[nodiscard]] constexpr friend auto operator==(basic_string const & lhs, const_pointer rhs) noexcept -> bool + { + if (rhs == nullptr) + { + os::panic("Tried to compare a string with nullptr"); + } + + return lhs == std::basic_string_view<value_type, traits_type>{rhs}; + } + + [[nodiscard]] constexpr friend auto operator==(const_pointer lhs, basic_string const & rhs) noexcept -> bool + { + if (rhs == nullptr) + { + os::panic("Tried to compare a string with nullptr"); + } + + return std::basic_string_view<value_type, traits_type>{lhs} == rhs; + } + + [[nodiscard]] constexpr friend auto operator<=>(basic_string const & lhs, basic_string const & rhs) noexcept + { + return std::lexicographical_compare_three_way(std::cbegin(lhs), std::cend(lhs), std::cbegin(rhs), std::cend(rhs)); + } + + [[nodiscard]] constexpr friend auto + operator<=>(basic_string const & lhs, std::basic_string_view<value_type, traits_type> const & rhs) noexcept + { + return std::lexicographical_compare_three_way(std::cbegin(lhs), std::cend(lhs), std::cbegin(rhs), std::cend(rhs)); + } + + [[nodiscard]] constexpr friend auto operator<=>(std::basic_string_view<value_type, traits_type> const & lhs, + basic_string const & rhs) noexcept -> std::strong_ordering + { + return std::lexicographical_compare_three_way(std::cbegin(lhs), std::cend(lhs), std::cbegin(rhs), std::cend(rhs)); + } + + [[nodiscard]] constexpr friend auto operator<=>(basic_string const & lhs, const_pointer rhs) noexcept + { + if (rhs == nullptr) + { + os::panic("Tried to compare a string with nullptr"); + } + + return lhs <=> std::basic_string_view<value_type, traits_type>{rhs}; + } + + [[nodiscard]] constexpr friend auto operator<=>(const_pointer lhs, basic_string const & rhs) noexcept + { + if (rhs == nullptr) + { + os::panic("Tried to compare a string with nullptr"); + } + + return std::basic_string_view<value_type, traits_type>{lhs} <=> rhs; + } + + private: + //! The size of the SSO buffer. + constexpr auto static inline sso_capacity = 15 / sizeof(value_type) + 1; + + //! The maximum string length that fits in the SSO buffer. + constexpr auto static inline sso_length = sso_capacity - 1; + + //! Allocate a buffer for the data. + //! + //! @param count The of character to reserve space for, excluding the termininating null. + //! @param exact Allocate space for the exact number of characters requested. + //! @return A span describing the newly allocated buffer. + [[nodiscard]] constexpr auto allocate_buffer(size_type count, bool exact = false) -> std::span<value_type> + { + if (count > max_size()) + { + os::panic("Tried to allocate more memory than possible"); + } + + auto to_allocate = (exact ? count : std::min(std::max(count, 2 * capacity()), max_size())) + 1; + return {std::allocator_traits<allocator_type>::allocate(m_allocator, to_allocate), to_allocate}; + } + + //! Insert a string view into this string at a given position. + //! + //! @param index The position to insert the data at. + //! @param view The string view to insert. + constexpr auto do_insert(size_type index, std::basic_string_view<value_type, traits_type> const & view) + -> basic_string & + { + if (index > size()) + { + os::panic("Index out of bounds while inserting into string"); + } + + if (view.size() == 0uz) + { + return *this; + } + + auto new_length = size() + view.size(); + + if (capacity() < new_length) + { + auto new_buffer = allocate_buffer(new_length); + traits_type::copy(new_buffer.data(), m_data, index); + traits_type::copy(new_buffer.data() + index, view.data(), view.size()); + traits_type::copy(new_buffer.data() + index + view.size(), m_data + index, size() - index + 1); + update_data(new_buffer); + } + else + { + traits_type::move(m_data + index + view.size(), m_data + index, size() - index); + + if (is_aliased(view.data())) // NOLINT(bugprone-suspicious-stringview-data-usage) + { + auto offset = view.data() - m_data; + + if (offset >= index) + { + traits_type::copy(m_data + index, m_data + offset + view.size(), view.size()); + } + else + { + traits_type::copy(m_data + index, m_data + offset, view.size()); + } + } + else + { + traits_type::copy(m_data + index, view.data(), view.size()); + } + } + + update_length(new_length); + return *this; + } + + //! Copy elements from a range described by an input iterator pair. + //! + //! @param first An iterator pointing to the first element to copy. + //! @param last An iterator pointing beyond the last elemento copy. + template<typename InputIterator, typename Sentinel> + requires std::input_iterator<std::remove_cvref_t<InputIterator>> + constexpr auto forward_from(InputIterator && first, Sentinel last) -> void + { + auto input_size = 0uz; + + for (; first != last && input_size < capacity(); ++first, ++input_size) + { + traits_type::assign(m_data[input_size], *std::forward<InputIterator>(first)); + } + + for (; first != last; ++first, ++input_size) + { + if (input_size == capacity()) + { + auto new_buffer = allocate_buffer(input_size + 1); + traits_type::move(new_buffer.data(), m_data, input_size + 1); + update_data(new_buffer); + } + + traits_type::assign(m_data[input_size], *std::forward<InputIterator>(first)); + } + + update_length(input_size); + } + + //! Copy elements from a range described by a forward iterator pair. + //! + //! @param first An iterator pointing to the first element to copy. + //! @param last An iterator pointing beyond the last elemento copy. + template<typename ForwardIterator, typename Sentinel> + requires std::forward_iterator<std::remove_cvref_t<ForwardIterator>> + constexpr auto forward_from(ForwardIterator && first, Sentinel last) -> void + { + auto input_size = std::ranges::distance(std::forward<ForwardIterator>(first), last); + + if (input_size > capacity()) + { + auto new_buffer = allocate_buffer(input_size, true); + update_data(new_buffer); + } + + for (auto i = 0uz; first != last; ++first, ++i) + { + traits_type::assign(m_data[i], *std::forward<ForwardIterator>(first)); + } + + update_length(input_size); + } + + //! Check if this string is currently in its SSO state. + //! + //! @return @p true iff. this string is in its SSO state, @p false otherwise. + [[nodiscard]] constexpr auto in_sso_state() const noexcept -> bool + { + return m_data == m_sso_buffer; + } + + //! Check if the a given pointer aliases into the internal string buffer. + //! + //! @param pointer The pointer to check for aliasing. + //! @return @p true iff. the given pointer aliases into the internal string buffer, @p false otherwise. + [[nodiscard]] constexpr auto is_aliased(const_pointer pointer) const noexcept -> bool + { + if consteval + { + for (auto i = 0uz; i < m_length; ++i) + { + if (pointer == m_data + i) + { + return true; + } + } + return false; + } + else + { + return pointer >= m_data && pointer <= m_data + m_length; + } + } + + //! Release the current buffer of this string. + //! + //! This function can be called even if this string is currently in tis SSO state. + [[nodiscard]] constexpr auto release_buffer() + { + if (!in_sso_state()) + { + std::allocator_traits<allocator_type>::deallocate(m_allocator, m_data, m_heap_capacity); + } + } + + //! Update the data pointer + //! + //! @param new_buffer The new buffer for this string. + constexpr auto update_data(std::span<value_type> new_buffer) -> void + { + release_buffer(); + m_data = new_buffer.data(); + m_heap_capacity = new_buffer.size(); + } + + //! Update the recorded length of this string and ensure null-termination. + //! + //! @param new_length The new length of this string. + constexpr auto update_length(size_type new_length) noexcept -> void + { + m_length = new_length; + traits_type::assign(m_data[m_length], value_type{}); + } + + //! The allocator used for heap allocations. + [[no_unique_address]] allocator_type m_allocator; + + //! The pointer to the start of the string data. + //! + //! When the SSO is active, this points to the internal SSO buffer m_sso_buffer. Otherwise, this points to the + //! heap allocation backing this string. + pointer m_data; + + //! The length of this string. + size_type m_length; + + //! The SSO buffer, or the capacity of this string if SSO is not active. + union + { + value_type m_sso_buffer[sso_capacity]; // NOLINT(modernize-avoid-c-arrays) + size_type m_heap_capacity; + }; + }; + + template<typename CharacterType, typename Traits, typename Allocator> + constexpr auto swap(basic_string<CharacterType, Traits, Allocator> & lhs, + basic_string<CharacterType, Traits, Allocator> & rhs) -> void + { + lhs.swap(rhs); + } + +} // namespace kstd + +#endif diff --git a/libs/kstd/kstd/string b/libs/kstd/kstd/string index 9343b428..de254a1d 100644 --- a/libs/kstd/kstd/string +++ b/libs/kstd/kstd/string @@ -1,330 +1,20 @@ #ifndef KSTD_STRING_HPP #define KSTD_STRING_HPP +#include <kstd/bits/basic_string.hpp> // IWYU pragma: export #include <kstd/bits/format/context.hpp> #include <kstd/bits/format/formatter.hpp> -#include <kstd/bits/format/formatter/string_view.hpp> +#include <kstd/bits/format/formatter/cstring.hpp> #include <kstd/cstring> #include <kstd/os/error.hpp> #include <kstd/vector> #include <algorithm> -#include <compare> #include <concepts> -#include <cstddef> -#include <string_view> namespace kstd { - /** - * @brief A simple string implementation that owns its data and provides basic operations. - */ - struct string - { - //! The type of the characters contained in this string. - using value_type = char; - //! The type of the underlying storage used by this string. - using storage_type = kstd::vector<value_type>; - //! The type of all sizes used in and with this string. - using size_type = std::size_t; - //! The type of the difference between two iterators. - using difference_type = std::ptrdiff_t; - //! The type of references to single values in this string. - using reference = value_type &; - //! The type of references to constant single values in this string. - using const_reference = value_type const &; - //! The type of pointers to single values in this string. - using pointer = value_type *; - //! The type of pointers to constant single values in this string. - using const_pointer = value_type const *; - //! The type of iterators into this string. - using iterator = pointer; - //! The type of constant iterators into this string. - using const_iterator = const_pointer; - - /** - * @brief Constructs an empty null-terminated string. - */ - string() - : m_storage{value_type{'\0'}} - {} - - /** - * @brief Constructs a string from a string view by copying the characters into owned storage. - * @param view The string view to copy the characters from. - */ - explicit string(std::string_view view) - : string() - { - append(view); - } - - /** - * @brief Constructs a string from a null-terminated C-style string by copying the characters into owned storage. - * @param c_str The null-terminated C-style string to copy. - */ - string(char const * c_str) - : string() - { - if (c_str != nullptr) - { - append(std::string_view{c_str}); - } - } - - /** - * @brief Constructs a string containing a single character. - * @param c The character to copy. - */ - string(value_type c) - : string() - { - push_back(c); - } - - /** - * @brief Constructs a string by copying another string. - * @param other The string to copy. - */ - constexpr string(string const & other) - : m_storage{other.m_storage} - {} - - /** - * @brief Destructs the string. - */ - constexpr ~string() = default; - - /** - * @brief Assigns the value of another string to this string. - * @param other The string to assign from. - * @return A reference to this string. - */ - constexpr auto operator=(string const & other) -> string & = default; - - constexpr auto operator=(std::string_view const & other) -> string & - { - clear(); - append(other); - return *this; - } - - constexpr auto operator=(char const * other) -> string & - { - clear(); - append(std::string_view{other}); - return *this; - } - - //! Create a string view from this string. - constexpr operator std::string_view() const noexcept - { - return {data(), size()}; - } - - /** - * @brief Returns the number of characters in this string, not including the null terminator. - */ - [[nodiscard]] constexpr auto size() const noexcept -> size_type - { - return m_storage.empty() ? 0 : m_storage.size() - 1; - } - - /** - * @brief Checks if this string is empty, not including the null terminator. - */ - [[nodiscard]] constexpr auto empty() const noexcept -> bool - { - return size() == 0; - } - - /** - * @brief Clears the content of the string, resulting in an empty string. - * The string remains null-terminated after this operation. - */ - constexpr auto clear() -> void - { - m_storage.clear(); - m_storage.push_back(value_type{'\0'}); - } - - //! Get a pointer to the underlying storage of the string - [[nodiscard]] constexpr auto data() noexcept -> pointer - { - return m_storage.data(); - } - - //! Get a const pointer to the underlying storage of the string - [[nodiscard]] constexpr auto data() const noexcept -> const_pointer - { - return m_storage.data(); - } - - //! Get a const pointer to the underlying storage of the string - [[nodiscard]] constexpr auto c_str() const noexcept -> const_pointer - { - return data(); - } - - //! Get an iterator to the beginning of the string - [[nodiscard]] constexpr auto begin() noexcept -> iterator - { - return data(); - } - - //! Get an const iterator to the beginning of the string - [[nodiscard]] constexpr auto begin() const noexcept -> const_iterator - { - return data(); - } - - //! Get an const iterator to the beginning of the string - [[nodiscard]] constexpr auto cbegin() const noexcept -> const_iterator - { - return begin(); - } - - //! Get an iterator to the end of the string - [[nodiscard]] constexpr auto end() noexcept -> iterator - { - return data() + size(); - } - - //! Get an const iterator to the end of the string - [[nodiscard]] constexpr auto end() const noexcept -> const_iterator - { - return data() + size(); - } - - //! Get an const iterator to the end of the string - [[nodiscard]] constexpr auto cend() const noexcept -> const_iterator - { - return end(); - } - - //! Get a reference to the first character of the string - [[nodiscard]] constexpr auto front() -> reference - { - return m_storage.front(); - } - - //! Get a const reference to the first character of the string - [[nodiscard]] constexpr auto front() const -> const_reference - { - return m_storage.front(); - } - - //! Get a reference to the last character of the string - [[nodiscard]] constexpr auto back() -> reference - { - return m_storage[size() - 1]; - } - - //! Get a const reference to the last character of the string - [[nodiscard]] constexpr auto back() const -> const_reference - { - return m_storage[size() - 1]; - } - - /** - * @brief Appends a character to the end of the string. - * @param ch The character to append. - */ - constexpr auto push_back(value_type ch) -> void - { - m_storage.back() = ch; - m_storage.push_back(value_type{'\0'}); - } - - /** - * @brief Appends a string view to the end of the string by copying the characters into owned storage. - * @param view The string view to append. - * @return A reference to this string. - */ - constexpr auto append(std::string_view view) -> string & - { - if (!view.empty()) - { - m_storage.reserve(size() + view.size() + 1); - std::ranges::for_each(view, [this](auto const ch) { push_back(ch); }); - } - - return *this; - } - - /** - * @brief Appends another string to the end of this string by copying the characters into owned storage. - * @param other The string to append. - * @return A reference to this string. - */ - constexpr auto append(string const & other) -> string & - { - return append(static_cast<std::string_view>(other)); - } - - /** - * @brief Appends another string to the end of this string by copying the characters into owned storage. - * @param other The string to append. - * @return A reference to this string. - */ - constexpr auto operator+=(string const & other) -> string & - { - return append(other); - } - - /** - * @brief Appends a character to the end of the string. - * @param ch The character to append. - * @return A reference to this string. - */ - constexpr auto operator+=(value_type ch) -> string & - { - push_back(ch); - return *this; - } - - //! Compare this string lexicographically to another string. - //! - //! @param other The string to compare to this one. - [[nodiscard]] constexpr auto operator<=>(string const & other) const noexcept -> std::strong_ordering = default; - - [[nodiscard]] constexpr auto operator==(string const & other) const noexcept -> bool = default; - - //! Compare this string lexicographically to a C-style string. - //! - //! @param other The C-style string to compare to this one. - //! @return The result of the comparison. - [[nodiscard]] constexpr auto operator<=>(char const * other) const noexcept - { - return static_cast<std::string_view>(*this) <=> other; - } - - //! Check if this string compares equal to a C-style string. - //! - //! @param other The C-style string to compare to this one. - //! @return @p true iff. this string compares equal to @p other, @p false otherwise. - [[nodiscard]] constexpr auto operator==(char const * other) const noexcept -> bool - { - return static_cast<std::string_view>(*this) == other; - } - - private: - //! The underlying storage of the string, which owns the characters and ensures null-termination. - storage_type m_storage{}; - }; - - /** - * @brief Concatenates a strings and a character and returns the result as a new string. - * @param lhs The string to concatenate. - * @param rhs The string to concatenate. - * @return A new string that is the result of concatenating @p lhs and @p rhs. - */ - [[nodiscard]] constexpr auto inline operator+(string const & lhs, string const & rhs) -> string - { - string result{lhs}; - result += rhs; - return result; - } + using string = basic_string<char>; /** * @brief Converts an unsigned integer to a string by converting each digit to the corresponding character and @@ -356,11 +46,11 @@ namespace kstd } template<> - struct formatter<string> : formatter<std::string_view> + struct formatter<string> : formatter<char const *> { auto format(string const & str, format_context & context) const -> void { - formatter<std::string_view>::format(static_cast<std::string_view>(str), context); + formatter<char const *>::format(str.data(), context); } }; diff --git a/libs/kstd/kstd/string.test.cpp b/libs/kstd/kstd/string.test.cpp index b81cd3a6..19345e09 100644 --- a/libs/kstd/kstd/string.test.cpp +++ b/libs/kstd/kstd/string.test.cpp @@ -1,158 +1,2042 @@ #include <kstd/string> +#include <kstd/allocator> +#include <kstd/test_support/os_panic.hpp> + #include <catch2/catch_test_macros.hpp> #include <algorithm> #include <cstring> +#include <forward_list> +#include <iterator> +#include <memory> +#include <sstream> #include <string_view> +#include <type_traits> +#include <utility> + +TEST_CASE("String static interface") +{ + REQUIRE(std::is_same_v<kstd::string::traits_type, kstd::char_traits<char>>); + REQUIRE(std::is_same_v<kstd::string::value_type, char>); + REQUIRE(std::is_same_v<kstd::string::allocator_type, kstd::allocator<char>>); + REQUIRE(std::is_same_v<kstd::string::size_type, std::allocator_traits<kstd::allocator<char>>::size_type>); + REQUIRE(std::is_same_v<kstd::string::difference_type, std::allocator_traits<kstd::allocator<char>>::difference_type>); + REQUIRE(std::is_same_v<kstd::string::reference, char &>); + REQUIRE(std::is_same_v<kstd::string::const_reference, char const &>); + REQUIRE(std::is_same_v<kstd::string::pointer, std::allocator_traits<kstd::allocator<char>>::pointer>); + REQUIRE(std::is_same_v<kstd::string::const_pointer, std::allocator_traits<kstd::allocator<char>>::const_pointer>); + REQUIRE(std::is_same_v<kstd::string::iterator, char *>); + REQUIRE(std::is_same_v<kstd::string::const_iterator, char const *>); + REQUIRE(std::is_same_v<kstd::string::reverse_iterator, std::reverse_iterator<char *>>); + REQUIRE(std::is_same_v<kstd::string::const_reverse_iterator, std::reverse_iterator<char const *>>); + + REQUIRE(kstd::string::npos == kstd::string::size_type(-1)); +} SCENARIO("String initialization and construction", "[string]") { - GIVEN("Nothing") + GIVEN("An empty context") { - WHEN("constructing an empty string") + WHEN("constructing by default") { - auto str = kstd::string{}; + auto s = kstd::string{}; + + THEN("the string is empty") + { + REQUIRE(s.empty()); + } - THEN("the size is zero and therefore the string is empty") + THEN("the size is equal to zero") { - REQUIRE(str.empty()); - REQUIRE(str.size() == 0); + REQUIRE(s.size() == 0); + } + + THEN("the length is equal to zero") + { + REQUIRE(s.length() == 0); + } + + THEN("at raises a panic") + { + REQUIRE_THROWS_AS(s.at(0), kstd::tests::os_panic); + } + + THEN("data returns a pointer poiting to a null byte") + { + REQUIRE(*s.data() == '\0'); + } + + THEN("c_str returns a pointer poiting to a null byte") + { + REQUIRE(*s.c_str() == '\0'); + } + + THEN("the string is convertible to an empty string view") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.empty()); + } + } + + WHEN("constructing with 10 copies of the letter 'a'") + { + auto s = kstd::string{10, 'a'}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 10") + { + REQUIRE(s.size() == 10); + } + + THEN("the length is equal to 10") + { + REQUIRE(s.length() == 10); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns a") + { + REQUIRE(s.at(s.size() - 1) == 'a'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns a") + { + REQUIRE(s[s.size() - 1] == 'a'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns a") + { + REQUIRE(s.back() == 'a'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 10") + { + REQUIRE(std::strlen(s.c_str()) == 10); + } + + THEN("the string converts to a string view of length 10") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 10); + } + } + + WHEN("constructing with 20 copies of the letter 'a'") + { + auto s = kstd::string{20, 'a'}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns a") + { + REQUIRE(s.at(s.size() - 1) == 'a'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns a") + { + REQUIRE(s[s.size() - 1] == 'a'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns a") + { + REQUIRE(s.back() == 'a'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing with an input iterator pair of 10 characters") + { + auto source = std::istringstream{"abcdefghij"}; + auto s = kstd::string{std::istream_iterator<char>{source}, std::istream_iterator<char>{}}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 10") + { + REQUIRE(s.size() == 10); + } + + THEN("the length is equal to 10") + { + REQUIRE(s.length() == 10); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns j") + { + REQUIRE(s.at(s.size() - 1) == 'j'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns j") + { + REQUIRE(s[s.size() - 1] == 'j'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns j") + { + REQUIRE(s.back() == 'j'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 10") + { + REQUIRE(std::strlen(s.c_str()) == 10); + } + + THEN("the string converts to a string view of length 10") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 10); + } + } + + WHEN("constructing with an input iterator pair of 20 characters") + { + auto source = std::istringstream{"abcdefghijABCDEFGHIJ"}; + auto s = kstd::string{std::istream_iterator<char>{source}, std::istream_iterator<char>{}}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is greater than or equal to 20") + { + REQUIRE(s.capacity() >= 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); } + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing with a forward iterator pair of 10 characters") + { + auto source = std::forward_list{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'}; + auto s = kstd::string{source.cbegin(), source.cend()}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 10") + { + REQUIRE(s.size() == 10); + } + + THEN("the length is equal to 10") + { + REQUIRE(s.length() == 10); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns j") + { + REQUIRE(s.at(s.size() - 1) == 'j'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns j") + { + REQUIRE(s[s.size() - 1] == 'j'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns j") + { + REQUIRE(s.back() == 'j'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 10") + { + REQUIRE(std::strlen(s.c_str()) == 10); + } + + THEN("the string converts to a string view of length 10") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 10); + } + } + + WHEN("constructing with a forward iterator pair of 20 characters") + { + auto source = std::forward_list{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', + 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'}; + auto s = kstd::string{source.cbegin(), source.cend()}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing from a null pointer with zero size") + { + auto s = kstd::string{static_cast<char const *>(nullptr), 0}; + THEN("the string is empty") { - REQUIRE(str == std::string_view{}); + REQUIRE(s.empty()); + } + + THEN("the size is equal to 0") + { + REQUIRE(s.size() == 0); + } + + THEN("the length is equal to 0") + { + REQUIRE(s.length() == 0); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at raises a panic") + { + REQUIRE_THROWS_AS(s.at(0), kstd::tests::os_panic); + } + + THEN("data returns a pointer poiting to a null byte") + { + REQUIRE(*s.data() == '\0'); + } + + THEN("c_str returns a pointer poiting to a null byte") + { + REQUIRE(*s.c_str() == '\0'); + } + + THEN("the string is convertible to an empty string view") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.empty()); + } + } + + WHEN("constructing from a from a null pointer and non-zero size") + { + THEN("a panic is raised") + { + REQUIRE_THROWS_AS((kstd::string{static_cast<char const *>(nullptr), 1}), kstd::tests::os_panic); + } + } + + WHEN("constructing from a non-null pointer and zero size") + { + auto ptr = "abcd"; + auto s = kstd::string{ptr, 0}; + + THEN("the string is empty") + { + REQUIRE(s.empty()); + } + + THEN("the size is equal to 0") + { + REQUIRE(s.size() == 0); + } + + THEN("the length is equal to 0") + { + REQUIRE(s.length() == 0); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at raises a panic") + { + REQUIRE_THROWS_AS(s.at(0), kstd::tests::os_panic); + } + + THEN("data returns a pointer poiting to a null byte") + { + REQUIRE(*s.data() == '\0'); + } + + THEN("c_str returns a pointer poiting to a null byte") + { + REQUIRE(*s.c_str() == '\0'); + } + + THEN("the string is convertible to an empty string view") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.empty()); + } + } + + WHEN("constructing from a non-null pointer and a size of 4") + { + auto ptr = "abcd"; + auto s = kstd::string{ptr, 4}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 4") + { + REQUIRE(s.size() == 4); + } + + THEN("the length is equal to 4") + { + REQUIRE(s.length() == 4); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns d") + { + REQUIRE(s.at(s.size() - 1) == 'd'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns d") + { + REQUIRE(s[s.size() - 1] == 'd'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns d") + { + REQUIRE(s.back() == 'd'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 4") + { + REQUIRE(std::strlen(s.c_str()) == 4); + } + + THEN("the string converts to a string view of length 4") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 4); + } + } + + WHEN("constructing from a non-null pointer and a size of 20") + { + auto ptr = "abcdefghijABCDEFGHIJ"; + auto s = kstd::string{ptr, 20}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing from a C-style string of length 4") + { + auto ptr = "abcd"; + auto s = kstd::string{ptr}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 4") + { + REQUIRE(s.size() == 4); + } + + THEN("the length is equal to 4") + { + REQUIRE(s.length() == 4); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns d") + { + REQUIRE(s.at(s.size() - 1) == 'd'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns d") + { + REQUIRE(s[s.size() - 1] == 'd'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns d") + { + REQUIRE(s.back() == 'd'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 4") + { + REQUIRE(std::strlen(s.c_str()) == 4); + } + + THEN("the string converts to a string view of length 4") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 4); + } + } + + WHEN("constructing from a C-style string of length 20") + { + auto ptr = "abcdefghijABCDEFGHIJ"; + auto s = kstd::string{ptr}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing from a string view of length 4") + { + using namespace std::string_view_literals; + + auto view = "abcd"sv; + auto s = kstd::string{view}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 4") + { + REQUIRE(s.size() == 4); + } + + THEN("the length is equal to 4") + { + REQUIRE(s.length() == 4); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns d") + { + REQUIRE(s.at(s.size() - 1) == 'd'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns d") + { + REQUIRE(s[s.size() - 1] == 'd'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns d") + { + REQUIRE(s.back() == 'd'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 4") + { + REQUIRE(std::strlen(s.c_str()) == 4); + } + + THEN("the string converts to a string view of length 4") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 4); + } + } + + WHEN("constructing from a string view of length 20") + { + using namespace std::string_view_literals; + + auto view = "abcdefghijABCDEFGHIJ"sv; + auto s = kstd::string{view}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + + THEN("the capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("at(0) returns a") + { + REQUIRE(s.at(0) == 'a'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns a") + { + REQUIRE(s[0] == 'a'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); + } + + THEN("front returns a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an a") + { + REQUIRE(*s.data() == 'a'); + } + + THEN("c_str returns a pointer pointing to an a") + { + REQUIRE(*s.c_str() == 'a'); + } + + THEN("c_str points to the start of a c-string of length 20") + { + REQUIRE(std::strlen(s.c_str()) == 20); + } + + THEN("the string converts to a string view of length 20") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 20); + } + } + + WHEN("constructing from a substring of a string view of length 4") + { + using namespace std::string_view_literals; + + auto view = "abcd"sv; + auto s = kstd::string{view, 1, 4}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 3") + { + REQUIRE(s.size() == 3); + } + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + + THEN("the capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("at(0) returns b") + { + REQUIRE(s.at(0) == 'b'); + } + + THEN("at(size() - 1) returns d") + { + REQUIRE(s.at(s.size() - 1) == 'd'); + } + + THEN("[0] returns b") + { + REQUIRE(s[0] == 'b'); + } + + THEN("[size() - 1] returns d") + { + REQUIRE(s[s.size() - 1] == 'd'); + } + + THEN("front returns b") + { + REQUIRE(s.front() == 'b'); + } + + THEN("back returns d") + { + REQUIRE(s.back() == 'd'); + } + + THEN("data returns a pointer pointing to an b") + { + REQUIRE(*s.data() == 'b'); + } + + THEN("c_str returns a pointer pointing to an b") + { + REQUIRE(*s.c_str() == 'b'); + } + + THEN("c_str points to the start of a c-string of length 3") + { + REQUIRE(std::strlen(s.c_str()) == 3); + } + + THEN("the string converts to a string view of length 3") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 3); + } + } + + WHEN("constructing from a substring of a string view of length 20") + { + using namespace std::string_view_literals; + + auto view = "abcdefghijABCDEFGHIJ"sv; + auto s = kstd::string{view, 1, 20}; + + THEN("the string is not empty") + { + REQUIRE_FALSE(s.empty()); + } + + THEN("the size is equal to 19") + { + REQUIRE(s.size() == 19); + } + + THEN("the length is equal to 19") + { + REQUIRE(s.length() == 19); + } + + THEN("the capacity is equal to 19") + { + REQUIRE(s.capacity() == 19); + } + + THEN("at(0) returns b") + { + REQUIRE(s.at(0) == 'b'); + } + + THEN("at(size() - 1) returns J") + { + REQUIRE(s.at(s.size() - 1) == 'J'); + } + + THEN("[0] returns b") + { + REQUIRE(s[0] == 'b'); + } + + THEN("[size() - 1] returns J") + { + REQUIRE(s[s.size() - 1] == 'J'); + } + + THEN("front returns b") + { + REQUIRE(s.front() == 'b'); + } + + THEN("back returns J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("data returns a pointer pointing to an b") + { + REQUIRE(*s.data() == 'b'); + } + + THEN("c_str returns a pointer pointing to an b") + { + REQUIRE(*s.c_str() == 'b'); + } + + THEN("c_str points to the start of a c-string of length 19") + { + REQUIRE(std::strlen(s.c_str()) == 19); + } + + THEN("the string converts to a string view of length 19") + { + auto view = static_cast<std::string_view>(s); + REQUIRE(view.length() == 19); } } } - GIVEN("A string view") + GIVEN("An existing short string, of length 10") { - auto view = std::string_view{"Blub Blub"}; + auto other = kstd::string{"abcdefghij"}; - WHEN("constructing a string from string_view") + WHEN("constructing by copy") { - auto str = kstd::string{view}; + auto s = other; - THEN("the string is not empty and has the same size as the view") + THEN("the sizes are identical") { - REQUIRE_FALSE(str.empty()); - REQUIRE(str.size() == view.size()); + REQUIRE(s.size() == other.size()); } - THEN("the string contains the same characters as the view") + THEN("the capacities are idendtical") { - REQUIRE(str == view); + REQUIRE(s.capacity() == other.capacity()); + } + + THEN("the underlying strings are identical") + { + REQUIRE_FALSE(std::strcmp(s.data(), other.data())); + } + } + + WHEN("constructing by move") + { + auto s = std::move(other); + + THEN("size is equal to 10") + { + REQUIRE(s.size() == 10); + } + + THEN("capacity is equal to 15") + { + REQUIRE(s.capacity() == 15); + } + + THEN("front() return an a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back() return a j") + { + REQUIRE(s.back() == 'j'); + } + + THEN("The moved from object's size is 0") + { + REQUIRE(other.size() == 0); + } + + THEN("The moved from object's capacity is 15") + { + REQUIRE(other.capacity() == 15); + } + + THEN("c_str() on the moved from object points to a null byte") + { + REQUIRE(*other.c_str() == '\0'); } } } - GIVEN("A C-style string") + GIVEN("An existing short string, of length 20") { - auto c_str = "Blub Blub"; + auto other = kstd::string{"abcdefghijABCDEFGHIJ"}; - WHEN("constructing a string from the C-style string") + WHEN("constructing by copy") { - auto str = kstd::string{c_str}; + auto s = other; - THEN("the string is not empty and has the same size as the C-style string") + THEN("the sizes are identical") { - REQUIRE_FALSE(str.empty()); - REQUIRE(str.size() == std::strlen(c_str)); + REQUIRE(s.size() == other.size()); } - THEN("the string contains the same characters as the C-style string") + THEN("the capacities are idendtical") { - REQUIRE(str == c_str); + REQUIRE(s.capacity() == other.capacity()); + } + + THEN("the underlying strings are identical") + { + REQUIRE_FALSE(std::strcmp(s.data(), other.data())); + } + } + + WHEN("constructing by move") + { + auto s = std::move(other); + + THEN("size is equal to 20") + { + REQUIRE(s.size() == 20); + } + + THEN("capacity is equal to 20") + { + REQUIRE(s.capacity() == 20); + } + + THEN("front() return an a") + { + REQUIRE(s.front() == 'a'); + } + + THEN("back() return a J") + { + REQUIRE(s.back() == 'J'); + } + + THEN("The moved from object's size is 0") + { + REQUIRE(other.size() == 0); + } + + THEN("The moved from object's capacity is 15") + { + REQUIRE(other.capacity() == 15); + } + + THEN("c_str() on the moved from object points to a null byte") + { + REQUIRE(*other.c_str() == '\0'); } } } +} - GIVEN("A character") +SCENARIO("String assignment", "[string]") +{ + GIVEN("Two short strings") { - auto ch = 'x'; + auto s1 = kstd::string{"abcd"}; + auto s2 = kstd::string{"defghij"}; + + WHEN("copy assigning the shorter to the longer one") + { + s2 = s1; + + THEN("the new length of the longer one is equal to the length of the shorter one") + { + REQUIRE(s2.length() == s1.length()); + } + + THEN("the underlying data of the two is identical") + { + REQUIRE_FALSE(std::strcmp(s1.data(), s2.data())); + } + } - WHEN("constructing a string from the character") + WHEN("copy assigning the longer to the shorter one") { - auto str = kstd::string{ch}; + s1 = s2; - THEN("the string is not empty and has size 1") + THEN("the new length of the shorter one is equal to the length of the longer one") { - REQUIRE_FALSE(str.empty()); - REQUIRE(str.size() == 1); + REQUIRE(s1.length() == s2.length()); } - THEN("the string contains the same character as the given character") + THEN("the underlying data of the two is identical") { - REQUIRE(str == std::string_view{&ch, 1}); + REQUIRE_FALSE(std::strcmp(s2.data(), s1.data())); + } + } + + WHEN("move assigning the shorter to the longer one") + { + s2 = std::move(s1); + + THEN("the new length of the longer one is equal to the original length of the shorter one") + { + REQUIRE(s2.length() == 4); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s1.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s1.capacity() == 15); + } + + THEN("the capacity of the moved to one is 15") + { + REQUIRE(s2.capacity() == 15); + } + } + + WHEN("move assigning the longer to the shorter one") + { + s1 = std::move(s2); + + THEN("the new length of the shorter one is equal to the original length of the longer one") + { + REQUIRE(s1.length() == 7); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s2.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s2.capacity() == 15); + } + + THEN("the capacity of the moved to one is 15") + { + REQUIRE(s1.capacity() == 15); } } } - GIVEN("Another string") + GIVEN("One short and one long string") { - auto other = kstd::string{"Blub Blub"}; + auto s1 = kstd::string{"abcd"}; + auto s2 = kstd::string{"ABCDEFGHIJabcdefghij"}; + + WHEN("copy assigning the shorter to the longer one") + { + s2 = s1; + + THEN("the new length of the longer one is equal to the length of the shorter one") + { + REQUIRE(s2.length() == s1.length()); + } - WHEN("copy constructing a new string") + THEN("the new capacity of the longer one is 15") + { + REQUIRE(s2.capacity() == 15); + } + + THEN("the underlying data of the two is identical") + { + REQUIRE_FALSE(std::strcmp(s1.data(), s2.data())); + } + } + + WHEN("copy assigning the longer to the shorter one") { - auto str = kstd::string{other}; + s1 = s2; + + THEN("the new length of the shorter one is equal to the length of the longer one") + { + REQUIRE(s1.length() == s2.length()); + } - THEN("the new string contains the same characters as the original") + THEN("the new capacity of the shorter one is 20") { - REQUIRE(static_cast<std::string_view>(str) == static_cast<std::string_view>(other)); + REQUIRE(s1.capacity() == 20); + } + + THEN("the underlying data of the two is identical") + { + REQUIRE_FALSE(std::strcmp(s2.data(), s1.data())); } } - auto str = kstd::string{"Blub"}; + WHEN("move assigning the shorter to the longer one") + { + s2 = std::move(s1); - WHEN("copy assigning another string") + THEN("the new length of the longer one is equal to the original length of the shorter one") + { + REQUIRE(s2.length() == 4); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s1.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s1.capacity() == 15); + } + + THEN("the capacity of the moved to one is 15") + { + REQUIRE(s2.capacity() == 15); + } + } + + WHEN("move assigning the longer to the shorter one") { - auto other = kstd::string{"Blub Blub"}; - str = other; + s1 = std::move(s2); + + THEN("the new length of the shorter one is equal to the original length of the longer one") + { + REQUIRE(s1.length() == 20); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s2.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s2.capacity() == 15); + } - THEN("the string contains the same characters as the assigned string") + THEN("the capacity of the moved to one is 15") { - REQUIRE(static_cast<std::string_view>(str) == static_cast<std::string_view>(other)); + REQUIRE(s1.capacity() == 20); } } } - GIVEN("A string") + GIVEN("Two long strings") + { + auto s1 = kstd::string{"abcdefghijABCDEFGH"}; + auto s2 = kstd::string{"ABCDEFGHIJabcdefghij"}; + + WHEN("copy assigning the shorter to the longer one") + { + s2 = s1; + + THEN("the new length of the longer one is equal to the length of the shorter one") + { + REQUIRE(s2.length() == s1.length()); + } + + THEN("the new capacity of the longer one is still 20") + { + REQUIRE(s2.capacity() == 20); + } + + THEN("the underlying data of the two is identical") + { + REQUIRE_FALSE(std::strcmp(s1.data(), s2.data())); + } + } + + WHEN("copy assigning the longer to the shorter one") + { + s1 = s2; + + THEN("the new length of the shorter one is equal to the length of the longer one") + { + REQUIRE(s1.length() == s2.length()); + } + + THEN("the new capacity of the shorter one is 20") + { + REQUIRE(s1.capacity() == 20); + } + + THEN("the underlying data of the two is identical") + { + REQUIRE_FALSE(std::strcmp(s2.data(), s1.data())); + } + } + + WHEN("move assigning the shorter to the longer one") + { + s2 = std::move(s1); + + THEN("the new length of the longer one is equal to the original length of the shorter one") + { + REQUIRE(s2.length() == 18); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s1.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s1.capacity() == 15); + } + + THEN("the capacity of the moved to one is 15") + { + REQUIRE(s2.capacity() == 18); + } + } + + WHEN("move assigning the longer to the shorter one") + { + s1 = std::move(s2); + + THEN("the new length of the shorter one is equal to the original length of the longer one") + { + REQUIRE(s1.length() == 20); + } + + THEN("the length of the moved from one is 0") + { + REQUIRE(s2.length() == 0); + } + + THEN("the capacity of the moved from one is 15") + { + REQUIRE(s2.capacity() == 15); + } + + THEN("the capacity of the moved to one is 15") + { + REQUIRE(s1.capacity() == 20); + } + } + } + + GIVEN("An short string") { - auto str = kstd::string{"Hello"}; + auto s = kstd::string{"abcd"}; + + WHEN("assigning a new, shorter c-style string of length 3") + { + s = "def"; + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } - WHEN("copy assigning a string view") + WHEN("assigning a new, longer, c-style string of length 5") { - auto view = std::string_view{"Hello, world!"}; - str = view; + s = "defgh"; - THEN("the string contains the same characters as the assigned view") + THEN("the length is equal to 5") { - REQUIRE(str == view); + REQUIRE(s.length() == 5); + } + } + + WHEN("assigning a new, longer, c-style string of length 20") + { + s = "ABCDEFGHIJabcdefghij"; + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + } + + WHEN("assigning a single character") + { + s = 'z'; + + THEN("the length is equal to 1") + { + REQUIRE(s.length() == 1); + } + } + + WHEN("assigning an shorter initializer list of length 3") + { + s = {'d', 'e', 'f'}; + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } + + WHEN("assigning an longer initializer list of length 5") + { + s = {'d', 'e', 'f', 'g', 'h'}; + + THEN("the length is equal to 5") + { + REQUIRE(s.length() == 5); + } + } + + WHEN("assigning an longer initializer list of length 20") + { + s = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'}; + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); + } + } + + WHEN("assigning from a shorter string view of length 3") + { + using namespace std::string_view_literals; + + s = "def"sv; + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } + + WHEN("assigning from a longer string view of length 5") + { + using namespace std::string_view_literals; + + s = "defgh"sv; + + THEN("the length is equal to 5") + { + REQUIRE(s.length() == 5); + } + } + + WHEN("assigning from a longer string view of length 20") + { + using namespace std::string_view_literals; + + s = "ABCDEFGHIJabcdefghij"sv; + + THEN("the length is equal to 20") + { + REQUIRE(s.length() == 20); } } } - GIVEN("A string") + GIVEN("An long string") { - auto str = kstd::string{"Hello"}; + auto s = kstd::string{"abcdefghijABCDEFGHIJ"}; + + WHEN("assigning a new, shorter c-style string of length 3") + { + s = "def"; + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } + + WHEN("assigning a new, longer, c-style string of length 22") + { + s = "ABCDEFGHIJabcdefghijkl"; + + THEN("the length is equal to 22") + { + REQUIRE(s.length() == 22); + } + } + + WHEN("assigning a single character") + { + s = 'z'; + + THEN("the length is equal to 1") + { + REQUIRE(s.length() == 1); + } + } + + WHEN("assigning an shorter initializer list of length 3") + { + s = {'d', 'e', 'f'}; + + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } + + WHEN("assigning an longer initializer list of length 22") + { + s = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'a', + 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'}; + + THEN("the length is equal to 22") + { + REQUIRE(s.length() == 22); + } + } + + WHEN("assigning from a shorter string view of length 3") + { + using namespace std::string_view_literals; + + s = "def"sv; - WHEN("copy assigning a C-style string") + THEN("the length is equal to 3") + { + REQUIRE(s.length() == 3); + } + } + + WHEN("assigning from a longer string view of length 22") { - auto c_str = "Hello, world!"; - str = c_str; + using namespace std::string_view_literals; + + s = "ABCDEFGHIJabcdefghijkl"sv; - THEN("the string contains the same characters as the assigned C-style string") + THEN("the length is equal to 22") { - REQUIRE(str == c_str); + REQUIRE(s.length() == 22); } } } } -SCENARIO("String concatenation", "[string]") +SCENARIO("String modifiers", "[string]") { + GIVEN("A short string") + { + auto s = kstd::string{"abcd"}; + auto old_capacity = s.capacity(); + auto old_size = s.size(); + auto old_data = s.data(); + + WHEN("reserving a smaller capacity") + { + s.reserve(1); + + THEN("the capacity does not change") + { + REQUIRE(s.capacity() == old_capacity); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcd"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer stays the same") + { + REQUIRE(s.data() == old_data); + } + } + + WHEN("reserving equal capacity") + { + s.reserve(old_capacity); + + THEN("the capacity does not change") + { + REQUIRE(s.capacity() == old_capacity); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcd"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer stays the same") + { + REQUIRE(static_cast<void const *>(s.data()) == static_cast<void const *>(old_data)); + } + } + + WHEN("reserving larger capacity") + { + s.reserve(old_capacity + 1); + + THEN("the capacity increases") + { + REQUIRE(s.capacity() >= old_capacity + 1); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcd"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer changes") + { + REQUIRE(s.data() != old_data); + } + } + } + + GIVEN("A long string") + { + auto s = kstd::string{"abcdefghijABCDEFGHIJ"}; + auto old_capacity = s.capacity(); + auto old_size = s.size(); + auto old_data = s.data(); + + WHEN("reserving a smaller capacity") + { + s.reserve(1); + + THEN("the capacity does not change") + { + REQUIRE(s.capacity() == old_capacity); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcdefghijABCDEFGHIJ"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer stays the same") + { + REQUIRE(s.data() == old_data); + } + } + + WHEN("reserving equal capacity") + { + s.reserve(old_capacity); + + THEN("the capacity does not change") + { + REQUIRE(s.capacity() == old_capacity); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcdefghijABCDEFGHIJ"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer stays the same") + { + REQUIRE(static_cast<void const *>(s.data()) == static_cast<void const *>(old_data)); + } + } + + WHEN("reserving larger capacity") + { + s.reserve(old_capacity + 1); + + THEN("the capacity increases") + { + REQUIRE(s.capacity() >= old_capacity + 1); + } + + THEN("the content stays the same") + { + REQUIRE(s == "abcdefghijABCDEFGHIJ"); + } + + THEN("the size stays the same") + { + REQUIRE(s.size() == old_size); + } + + THEN("the data pointer changes") + { + REQUIRE(s.data() != old_data); + } + } + } + GIVEN("Two strings") { auto str1 = kstd::string{"Blub"}; @@ -187,21 +2071,6 @@ SCENARIO("String concatenation", "[string]") REQUIRE(str1.size() == str2.size() + 4); } } - - WHEN("using operator+ to concatenate the two strings into a new string") - { - auto str3 = str1 + str2; - - THEN("the new string contains the characters of both strings concatenated") - { - REQUIRE(str3 == "Blub Blub"); - } - - THEN("the size of the new string is the sum of the sizes of both strings") - { - REQUIRE(str3.size() == str1.size() + str2.size()); - } - } } GIVEN("A string and a string view") @@ -260,6 +2129,51 @@ SCENARIO("String concatenation", "[string]") } } } + + GIVEN("A non-empty string") + { + auto str = kstd::string{"Blub Blub"}; + + WHEN("clearing the string") + { + str.clear(); + + THEN("the string is empty and has size zero") + { + REQUIRE(str.empty()); + REQUIRE(str.size() == 0); + } + + THEN("the string contains no characters") + { + REQUIRE(str == std::string_view{}); + } + } + } +} + +SCENARIO("String concatenation", "[string]") +{ + GIVEN("Two strings") + { + auto str1 = kstd::string{"Blub"}; + auto str2 = kstd::string{" Blub"}; + + WHEN("using operator+ to concatenate the two strings into a new string") + { + auto str3 = str1 + str2; + + THEN("the new string contains the characters of both strings concatenated") + { + REQUIRE(str3 == "Blub Blub"); + } + + THEN("the size of the new string is the sum of the sizes of both strings") + { + REQUIRE(str3.size() == str1.size() + str2.size()); + } + } + } } SCENARIO("String conversion and comparison", "[string]") @@ -317,30 +2231,6 @@ SCENARIO("String conversion and comparison", "[string]") } } -SCENARIO("String clearing", "[string]") -{ - GIVEN("A non-empty string") - { - auto str = kstd::string{"Blub Blub"}; - - WHEN("clearing the string") - { - str.clear(); - - THEN("the string is empty and has size zero") - { - REQUIRE(str.empty()); - REQUIRE(str.size() == 0); - } - - THEN("the string contains no characters") - { - REQUIRE(str == std::string_view{}); - } - } - } -} - SCENARIO("String iteration", "[string]") { GIVEN("A string") |