diff --git a/libc/src/__support/CPP/CMakeLists.txt b/libc/src/__support/CPP/CMakeLists.txt --- a/libc/src/__support/CPP/CMakeLists.txt +++ b/libc/src/__support/CPP/CMakeLists.txt @@ -55,6 +55,15 @@ libc.src.__support.common ) +add_header_library( + string + HDRS + string.h + DEPENDS + libc.src.__support.common + libc.src.string.memory_utils.memory_utils +) + add_header_library( stringstream HDRS diff --git a/libc/src/__support/CPP/string.h b/libc/src/__support/CPP/string.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/CPP/string.h @@ -0,0 +1,217 @@ +//===-- Standalone implementation std::string -------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_SRC_SUPPORT_CPP_STRING_H +#define LLVM_LIBC_SRC_SUPPORT_CPP_STRING_H + +#include "src/__support/common.h" // For LIBC_INLINE +#include "src/string/memory_utils/memcpy_implementations.h" + +#include // For size_t + +namespace __llvm_libc { +namespace cpp { + +// A very simple implementation of an equivalent of std::string. The full +// std::string API is not available. New methods are added on an as-needed +// basis. +// +// TODO: Replace the use of the global new and delete with libc internal +// new and delete as described under "Allocations in the libc runtime code" on +// http://libc.llvm.org/dev/code_style.html. Using global new and delete for +// now is OK as cpp::string is only used in the unit tests. Once unit tests +// switch to an internal logging class and not use std::cout, we can switch +// over to the internal new and delete in cpp::string. +class string { + size_t len = 0; + char *data = nullptr; + + LIBC_INLINE static constexpr size_t length(const char *str) { + for (const char *end = str;; ++end) + if (*end == '\0') + return end - str; + } + + template class riterator { + private: + T *data; + + public: + explicit riterator(T *d) : data(d) {} + riterator &operator++() { + --data; + return *this; + } + riterator operator++(int) { return riterator(data--); } + T &operator*() { return *data; } + bool operator!=(const riterator &other) const { + return data != other.data; + } + bool operator==(const riterator &other) const { + return data == other.data; + } + }; + +public: + LIBC_INLINE constexpr string() = default; + LIBC_INLINE ~string() { delete[] data; } + + LIBC_INLINE string(const string &other) : len(other.len) { + if (other.len == 0) { + data = nullptr; + return; + } + data = new char[len + 1]; + if (data == nullptr) + return; + inline_memcpy(data, other.data, len + 1); + } + + LIBC_INLINE string(string &&other) : len(other.len), data(other.data) { + other.len = 0; + other.data = nullptr; + } + + LIBC_INLINE string(const char *str) { + if (str == nullptr) + return; + len = length(str); + data = new char[len + 1]; + if (data == nullptr) + return; + inline_memcpy(data, str, len + 1); + } + + LIBC_INLINE string(const char *str, size_t s) { + if (str == nullptr) + return; + data = new char[s + 1]; + if (data == nullptr) + return; + len = s; + inline_memcpy(data, str, s); + data[len] = '\0'; + } + + LIBC_INLINE string(size_t n, char c) : len(n) { + data = new char[len + 1]; + if (data == nullptr) + return; + for (size_t i = 0; i < len; ++i) + data[i] = c; + data[len] = '\0'; + } + + LIBC_INLINE size_t size() const { return len; } + + LIBC_INLINE const char *c_str() const { return data; } + + LIBC_INLINE bool operator==(const string &other) const { + if (len != other.len) + return false; + for (size_t i = 0; i < len; ++i) { + if (data[i] != other.data[i]) + return false; + } + return true; + } + + LIBC_INLINE bool operator!=(const string &other) const { + return !(*this == other); + } + + LIBC_INLINE bool operator==(const char *str) const { + for (size_t i = 0; i <= len; ++i) { + if (data[i] != str[i]) + return false; + } + return true; + } + + LIBC_INLINE bool operator!=(const char *str) const { return !(*this == str); } + + LIBC_INLINE string &operator=(const string &other) { + if (data == other.data) + return *this; + if (data != nullptr) { + delete[] data; + len = 0; + } + if (other.data == nullptr) { + data = nullptr; + len = 0; + return *this; + } + + data = new char[len + 1]; + if (data == nullptr) + return *this; + + inline_memcpy(data, other.data, len + 1); + + return *this; + } + + LIBC_INLINE string &operator=(string &&other) { + if (data == other.data) + return *this; + if (data != nullptr) { + delete[] data; + } + data = other.data; + len = other.len; + other.len = 0; + other.data = nullptr; + return *this; + } + + using reverse_iterator = riterator; + using const_reverse_iterator = riterator; + + LIBC_INLINE reverse_iterator rbegin() { + if (data == nullptr) + return reverse_iterator(nullptr); + return reverse_iterator(data + len - 1); + } + + LIBC_INLINE reverse_iterator rend() { + if (data == nullptr) + return reverse_iterator(nullptr); + return reverse_iterator(data - 1); + } + + LIBC_INLINE const_reverse_iterator rbegin() const { + if (data == nullptr) + return const_reverse_iterator(nullptr); + return const_reverse_iterator(data + len - 1); + } + + LIBC_INLINE const_reverse_iterator rend() const { + if (data == nullptr) + return const_reverse_iterator(nullptr); + return const_reverse_iterator(data - 1); + } +}; + +LIBC_INLINE string operator+(const string &s1, const string &s2) { + size_t len = s1.size() + s2.size(); + char *data = new char[len + 1]; + if (data == nullptr) + return string(); + data[len] = '\0'; + for (size_t i = 0; i < s1.size(); ++i) + data[i] = s1.c_str()[i]; + for (size_t i = 0; i < s2.size(); ++i) + data[i + s1.size()] = s2.c_str()[i]; + return string(data); +} + +} // namespace cpp +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_SUPPORT_CPP_STRING_H diff --git a/libc/src/__support/CPP/type_traits.h b/libc/src/__support/CPP/type_traits.h --- a/libc/src/__support/CPP/type_traits.h +++ b/libc/src/__support/CPP/type_traits.h @@ -147,6 +147,21 @@ template using conditional_t = typename conditional::type; +template struct remove_reference { + using type = T; +}; + +template struct remove_reference { + using type = T; +}; + +template struct remove_reference { + using type = T; +}; + +template +using remove_reference_t = typename remove_reference::type; + } // namespace cpp } // namespace __llvm_libc diff --git a/libc/src/__support/CPP/utility.h b/libc/src/__support/CPP/utility.h --- a/libc/src/__support/CPP/utility.h +++ b/libc/src/__support/CPP/utility.h @@ -35,6 +35,10 @@ using make_integer_sequence = typename internal::make_integer_sequence::type; +template cpp::remove_reference_t &&move(T &&obj) { + return static_cast &&>(obj); +} + } // namespace __llvm_libc::cpp #endif // LLVM_LIBC_SRC_SUPPORT_CPP_UTILITY_H diff --git a/libc/test/UnitTest/LibcTest.h b/libc/test/UnitTest/LibcTest.h --- a/libc/test/UnitTest/LibcTest.h +++ b/libc/test/UnitTest/LibcTest.h @@ -14,6 +14,7 @@ #include "PlatformDefs.h" +#include "src/__support/CPP/string.h" #include "src/__support/CPP/string_view.h" #include "src/__support/CPP/type_traits.h" #include "utils/testutils/ExecuteFunction.h" @@ -24,6 +25,12 @@ class RunContext; +class TestLog { +public: + constexpr TestLog() = default; + template TestLog &operator<<(const T &); +}; + // Only the following conditions are supported. Notice that we do not have // a TRUE or FALSE condition. That is because, C library funtions do not // return boolean values, but use integral return values to indicate true or @@ -119,6 +126,14 @@ return internal::test(Ctx, Cond, LHS, RHS, LHSStr, RHSStr, File, Line); } + template , + int> = 0> + bool test(TestCondition Cond, ValType LHS, ValType RHS, const char *LHSStr, + const char *RHSStr, const char *File, unsigned long Line) { + return internal::test(Ctx, Cond, LHS, RHS, LHSStr, RHSStr, File, Line); + } + bool testStrEq(const char *LHS, const char *RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line); diff --git a/libc/test/UnitTest/LibcTest.cpp b/libc/test/UnitTest/LibcTest.cpp --- a/libc/test/UnitTest/LibcTest.cpp +++ b/libc/test/UnitTest/LibcTest.cpp @@ -8,12 +8,20 @@ #include "LibcTest.h" +#include "src/__support/CPP/string.h" #include "src/__support/CPP/string_view.h" #include "src/__support/UInt128.h" +#include "src/__support/integer_to_string.h" #include "utils/testutils/ExecuteFunction.h" #include #include -#include + +// TODO: Remove once we can remove the use of std::cout as described in issue +// #61753. +std::ostream &operator<<(std::ostream &stream, + const __llvm_libc::cpp::string &s) { + return stream << s.c_str(); +} namespace __llvm_libc { namespace testing { @@ -41,10 +49,10 @@ // be able to unittest UInt<128> on platforms where UInt128 resolves to // UInt128. template -cpp::enable_if_t && cpp::is_unsigned_v, std::string> +cpp::enable_if_t && cpp::is_unsigned_v, cpp::string> describeValueUInt(T Value) { static_assert(sizeof(T) % 8 == 0, "Unsupported size of UInt"); - std::string S(sizeof(T) * 2, '0'); + cpp::string S(sizeof(T) * 2, '0'); constexpr char HEXADECIMALS[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'}; @@ -60,26 +68,28 @@ // When the value is of integral type, just display it as normal. template -cpp::enable_if_t, std::string> +cpp::enable_if_t, cpp::string> describeValue(ValType Value) { if constexpr (sizeof(ValType) <= sizeof(uint64_t)) { - return std::to_string(Value); + char Buf[IntegerToString::dec_bufsize()]; + auto StrView = *IntegerToString::dec(Value, Buf); + return cpp::string(StrView.data(), StrView.size()); } else { return describeValueUInt(Value); } } -std::string describeValue(std::string Value) { return std::string(Value); } -std::string describeValue(cpp::string_view Value) { - return std::string(Value.data(), Value.size()); +cpp::string describeValue(cpp::string Value) { return Value; } +cpp::string describeValue(cpp::string_view Value) { + return cpp::string(Value.data(), Value.size()); } template void explainDifference(ValType LHS, ValType RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line, - std::string OpString) { + cpp::string OpString) { size_t OffsetLength = OpString.size() > 2 ? OpString.size() - 2 : 0; - std::string Offset(OffsetLength, ' '); + cpp::string Offset(OffsetLength, ' '); std::cout << File << ":" << Line << ": FAILURE\n" << Offset << "Expected: " << LHSStr << '\n' @@ -92,57 +102,80 @@ bool test(RunContext *Ctx, TestCondition Cond, ValType LHS, ValType RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line) { - auto ExplainDifference = [=](std::string OpString) { + auto ExplainDifference = [=](cpp::string OpString) { explainDifference(LHS, RHS, LHSStr, RHSStr, File, Line, OpString); }; - switch (Cond) { - case Cond_EQ: - if (LHS == RHS) - return true; - - Ctx->markFail(); - ExplainDifference("equal to"); - return false; - case Cond_NE: - if (LHS != RHS) - return true; - - Ctx->markFail(); - ExplainDifference("not equal to"); - return false; - case Cond_LT: - if (LHS < RHS) - return true; - - Ctx->markFail(); - ExplainDifference("less than"); - return false; - case Cond_LE: - if (LHS <= RHS) - return true; - - Ctx->markFail(); - ExplainDifference("less than or equal to"); - return false; - case Cond_GT: - if (LHS > RHS) - return true; - - Ctx->markFail(); - ExplainDifference("greater than"); - return false; - case Cond_GE: - if (LHS >= RHS) - return true; - - Ctx->markFail(); - ExplainDifference("greater than or equal to"); - return false; - default: - Ctx->markFail(); - std::cout << "Unexpected test condition.\n"; - return false; + if constexpr (cpp::is_same_v) { + switch (Cond) { + case Cond_EQ: + if (LHS == RHS) + return true; + + Ctx->markFail(); + ExplainDifference("equal to"); + return false; + case Cond_NE: + if (LHS != RHS) + return true; + + Ctx->markFail(); + ExplainDifference("not equal to"); + return false; + default: + Ctx->markFail(); + std::cout << "Unexpected test condition.\n"; + return false; + } + } else { + switch (Cond) { + case Cond_EQ: + if (LHS == RHS) + return true; + + Ctx->markFail(); + ExplainDifference("equal to"); + return false; + case Cond_NE: + if (LHS != RHS) + return true; + + Ctx->markFail(); + ExplainDifference("not equal to"); + return false; + case Cond_LT: + if (LHS < RHS) + return true; + + Ctx->markFail(); + ExplainDifference("less than"); + return false; + case Cond_LE: + if (LHS <= RHS) + return true; + + Ctx->markFail(); + ExplainDifference("less than or equal to"); + return false; + case Cond_GT: + if (LHS > RHS) + return true; + + Ctx->markFail(); + ExplainDifference("greater than"); + return false; + case Cond_GE: + if (LHS >= RHS) + return true; + + Ctx->markFail(); + ExplainDifference("greater than or equal to"); + return false; + default: + Ctx->markFail(); + std::cout << "Unexpected test condition.\n"; + return false; + } } } @@ -167,7 +200,7 @@ int FailCount = 0; for (Test *T = Start; T != nullptr; T = T->Next) { const char *TestName = T->getName(); - std::string StrTestName(TestName); + cpp::string StrTestName(TestName); constexpr auto GREEN = "\033[32m"; constexpr auto RED = "\033[31m"; constexpr auto RESET = "\033[0m"; @@ -298,19 +331,24 @@ __llvm_libc::cpp::string_view RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line); +template bool test<__llvm_libc::cpp::string>( + RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::string LHS, + __llvm_libc::cpp::string RHS, const char *LHSStr, const char *RHSStr, + const char *File, unsigned long Line); + } // namespace internal bool Test::testStrEq(const char *LHS, const char *RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line) { - return internal::test(Ctx, Cond_EQ, LHS ? std::string(LHS) : std::string(), - RHS ? std::string(RHS) : std::string(), LHSStr, RHSStr, + return internal::test(Ctx, Cond_EQ, LHS ? cpp::string(LHS) : cpp::string(), + RHS ? cpp::string(RHS) : cpp::string(), LHSStr, RHSStr, File, Line); } bool Test::testStrNe(const char *LHS, const char *RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line) { - return internal::test(Ctx, Cond_NE, LHS ? std::string(LHS) : std::string(), - RHS ? std::string(RHS) : std::string(), LHSStr, RHSStr, + return internal::test(Ctx, Cond_NE, LHS ? cpp::string(LHS) : cpp::string(), + RHS ? cpp::string(RHS) : cpp::string(), LHSStr, RHSStr, File, Line); } diff --git a/libc/test/src/__support/CPP/CMakeLists.txt b/libc/test/src/__support/CPP/CMakeLists.txt --- a/libc/test/src/__support/CPP/CMakeLists.txt +++ b/libc/test/src/__support/CPP/CMakeLists.txt @@ -30,6 +30,17 @@ libc.src.__support.CPP.string_view ) +add_libc_unittest( + string_test + SUITE + libc_cpp_utils_unittests + SRCS + string_test.cpp + DEPENDS + libc.src.__support.CPP.string + libc.src.__support.CPP.utility +) + add_libc_unittest( limits_test SUITE diff --git a/libc/test/src/__support/CPP/string_test.cpp b/libc/test/src/__support/CPP/string_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/CPP/string_test.cpp @@ -0,0 +1,137 @@ +//===-- Unittests for cpp::string -----------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/__support/CPP/string.h" +#include "src/__support/CPP/utility.h" +#include "test/UnitTest/Test.h" + +using __llvm_libc::cpp::string; + +// Tests for the various cpp::string constructors and assignment operators. +TEST(LlvmLibcStringTest, InitializeCheck) { + string v; + ASSERT_EQ(v.size(), size_t(0)); + ASSERT_TRUE(v.c_str() == nullptr); + + v = string(""); + ASSERT_EQ(v.size(), size_t(0)); + ASSERT_TRUE(v.c_str() != nullptr); + + v = string("abc", 0); + ASSERT_EQ(v.size(), size_t(0)); + ASSERT_TRUE(v.c_str() != nullptr); + + v = string("123456789"); + ASSERT_EQ(v.size(), size_t(9)); + + v = string("123456789", 5); + ASSERT_EQ(v.size(), size_t(5)); + ASSERT_EQ(v, string("12345")); +} + +TEST(LlvmLibcStringTest, EqualityCheck) { + string v("abc"); + ASSERT_EQ(v, string("abc")); + ASSERT_NE(v, string()); + ASSERT_NE(v, string("")); + ASSERT_NE(v, string("a")); + ASSERT_NE(v, string("123")); + ASSERT_NE(v, string("abd")); + ASSERT_NE(v, string("aaa")); + ASSERT_NE(v, string("abcde")); + + ASSERT_TRUE(v == string("abc")); + ASSERT_FALSE(v != string("abc")); + ASSERT_TRUE(v != string()); + ASSERT_FALSE(v == string()); + ASSERT_TRUE(v != string("")); + ASSERT_FALSE(v == string("")); + ASSERT_TRUE(v != string("a")); + ASSERT_FALSE(v == string("a")); + ASSERT_TRUE(v != string("123")); + ASSERT_FALSE(v == string("123")); + ASSERT_TRUE(v != string("abd")); + ASSERT_FALSE(v == string("abd")); + ASSERT_TRUE(v != string("aaa")); + ASSERT_FALSE(v == string("aaa")); + ASSERT_TRUE(v != string("abcde")); + ASSERT_FALSE(v == string("abcde")); + + ASSERT_TRUE(v == "abc"); + ASSERT_FALSE(v != "abc"); + ASSERT_TRUE(v != ""); + ASSERT_FALSE(v == ""); + ASSERT_TRUE(v != "a"); + ASSERT_FALSE(v == "a"); + ASSERT_TRUE(v != "123"); + ASSERT_FALSE(v == "123"); + ASSERT_TRUE(v != "abd"); + ASSERT_FALSE(v == "abd"); + ASSERT_TRUE(v != "aaa"); + ASSERT_FALSE(v == "aaa"); + ASSERT_TRUE(v != "abcde"); + ASSERT_FALSE(v == "abcde"); +} + +TEST(LlvmLibcStringTest, ReverseIteration) { + string s("abcdef"); + size_t i = s.size(); + ASSERT_EQ(i, static_cast(6)); + for (auto iter = s.rbegin(); iter != s.rend(); ++iter, --i) { + ASSERT_EQ(*iter, s.c_str()[i - 1]); + *iter = 'x'; + } + ASSERT_EQ(i, static_cast(0)); + ASSERT_EQ(s, string("xxxxxx")); + + string empty; + ASSERT_TRUE(empty.rbegin() == empty.rend()); + + string zero(""); + ASSERT_TRUE(empty.rbegin() == empty.rend()); +} + +TEST(LlvmLibcStringTest, ConstReverseIteration) { + const string s("abcdef"); + size_t i = s.size(); + ASSERT_EQ(i, static_cast(6)); + for (auto iter = s.rbegin(); iter != s.rend(); ++iter, --i) { + ASSERT_EQ(*iter, s.c_str()[i - 1]); + } + ASSERT_EQ(i, static_cast(0)); + + const string empty; + ASSERT_TRUE(empty.rbegin() == empty.rend()); + + const string zero(""); + ASSERT_TRUE(empty.rbegin() == empty.rend()); +} + +TEST(LlvmLibcStringTest, Concatenation) { + string s1("abc"), s2("xyz"), empty, zero(""); + + ASSERT_EQ(s1 + s2, string("abcxyz")); + ASSERT_TRUE(s1 + s2 == "abcxyz"); + + ASSERT_EQ(s1 + empty, s1); + ASSERT_EQ(s1 + zero, s1); + + ASSERT_EQ(empty + s2, s2); + ASSERT_EQ(zero + s2, s2); +} + +TEST(LlvmLibcStringTest, MoveSemantics) { + string s1("abcdef"); + string s2(__llvm_libc::cpp::move(s1)); + ASSERT_EQ(s2.size(), static_cast(6)); + ASSERT_EQ(s1.size(), static_cast(0)); + + s1 = __llvm_libc::cpp::move(s2); + ASSERT_EQ(s1.size(), static_cast(6)); + ASSERT_EQ(s2.size(), static_cast(0)); +} diff --git a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel @@ -189,6 +189,16 @@ ], ) +libc_support_library( + name = "__support_cpp_string", + hdrs = ["src/__support/CPP/string.h"], + deps = [ + ":__support_common", + ":libc_root", + ":string_memory_utils", + ], +) + libc_support_library( name = "__support_cpp_type_traits", hdrs = ["src/__support/CPP/type_traits.h"], diff --git a/utils/bazel/llvm-project-overlay/libc/test/UnitTest/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/test/UnitTest/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/libc/test/UnitTest/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/test/UnitTest/BUILD.bazel @@ -23,8 +23,10 @@ "//libc:__support_cpp_bit", "//libc:__support_cpp_bitset", "//libc:__support_cpp_span", + "//libc:__support_cpp_string", "//libc:__support_cpp_string_view", "//libc:__support_cpp_type_traits", + "//libc:__support_integer_to_string", "//libc:__support_uint128", "//libc:libc_root", "//libc/utils/testutils:libc_test_utils",