diff --git a/libc/src/__support/CPP/StringView.h b/libc/src/__support/CPP/StringView.h --- a/libc/src/__support/CPP/StringView.h +++ b/libc/src/__support/CPP/StringView.h @@ -24,7 +24,20 @@ const char *Data; size_t Len; + static size_t min(size_t A, size_t B) { return A <= B ? A : B; } + + static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) { + for (size_t I = 0; I < Length; ++I) + if (int Diff = (int)Lhs[I] - (int)Rhs[I]) + return Diff; + return 0; + } + public: + // special value equal to the maximum value representable by the type + // size_type. + static constexpr size_t npos = -1; + StringView() : Data(nullptr), Len(0) {} // Assumes Str is a null-terminated string. The length of the string does @@ -41,18 +54,67 @@ explicit StringView(const char *Str, size_t N) : Data(N ? Str : nullptr), Len(Str == nullptr ? 0 : N) {} + // Ctor for raw literal. + template + StringView(const char (&Str)[N]) : StringView(Str, N - 1) {} + const char *data() const { return Data; } - size_t size() { return Len; } + // Returns the size of the StringView. + size_t size() const { return Len; } + + // Returns whether the StringView is empty. + bool empty() const { return Len == 0; } + + // Returns an iterator to the first character of the view. + const char *begin() const { return Data; } + // Returns an iterator to the character following the last character of the + // view. + const char *end() const { return Data + Len; } + + // Returns a const reference to the character at specified location pos. + // No bounds checking is performed: the behavior is undefined if pos >= + // size(). const char &operator[](size_t Index) const { return Data[Index]; } + /// compare - Compare two strings; the result is -1, 0, or 1 if this string + /// is lexicographically less than, equal to, or greater than the \p Other. + int compare(StringView Other) const { + // Check the prefix for a mismatch. + if (int Res = compareMemory(Data, Other.Data, min(Len, Other.Len))) + return Res < 0 ? -1 : 1; + // Otherwise the prefixes match, so we only need to check the lengths. + if (Len == Other.Len) + return 0; + return Len < Other.Len ? -1 : 1; + } + + // An equivalent method is not available in std::string_view. + bool equals(StringView Other) const { + return (Len == Other.Len && + compareMemory(Data, Other.Data, Other.Len) == 0); + } + + inline bool operator==(StringView Other) const { return equals(Other); } + inline bool operator!=(StringView Other) const { return !(*this == Other); } + inline bool operator<(StringView Other) const { return compare(Other) == -1; } + inline bool operator<=(StringView Other) const { return compare(Other) != 1; } + inline bool operator>(StringView Other) const { return compare(Other) == 1; } + inline bool operator>=(StringView Other) const { + return compare(Other) != -1; + } + + // Moves the start of the view forward by n characters. + // The behavior is undefined if n > size(). StringView remove_prefix(size_t N) const { if (N >= Len) return StringView(); return StringView(Data + N, Len - N); } + // Moves the end of the view back by n characters. + // The behavior is undefined if n > size(). StringView remove_suffix(size_t N) const { if (N >= Len) return StringView(); @@ -61,45 +123,134 @@ // An equivalent method is not available in std::string_view. StringView trim(char C) const { - if (Len == 0) - return StringView(); + StringView Copy = *this; + while (!Copy.empty() && Copy.front() == C) + Copy = Copy.drop_front(); + while (!Copy.empty() && Copy.back() == C) + Copy = Copy.drop_back(); + return Copy; + } - const char *NewStart = Data; - size_t PrefixLen = 0; - for (; PrefixLen < Len; ++NewStart, ++PrefixLen) { - if (*NewStart != C) - break; - } + // Check if this string starts with the given Prefix. + bool starts_with(StringView Prefix) const { + return Len >= Prefix.Len && + compareMemory(Data, Prefix.Data, Prefix.Len) == 0; + } + + // Check if this string ends with the given Suffix. + bool ends_with(StringView Suffix) const { + return Len >= Suffix.Len && + compareMemory(end() - Suffix.Len, Suffix.Data, Suffix.Len) == 0; + } + + // Return a reference to the substring from [Start, Start + N). + // + // Start The index of the starting character in the substring; if the index is + // npos or greater than the length of the string then the empty substring will + // be returned. + // + // N The number of characters to included in the substring. If N exceeds the + // number of characters remaining in the string, the string suffix (starting + // with Start) will be returned. + StringView substr(size_t Start, size_t N = npos) const { + Start = min(Start, Len); + return StringView(Data + Start, min(N, Len - Start)); + } - size_t SuffixLen = 0; - const char *NewEnd = Data + Len - 1; - for (; SuffixLen < Len; --NewEnd, ++SuffixLen) { - if (*NewEnd != C) - break; + // Search for the first character satisfying the predicate Function + // + // Returns The index of the first character satisfying Function starting from + // From, or npos if not found. + template size_t find_if(F Function, size_t From = 0) const { + StringView S = drop_front(From); + while (!S.empty()) { + if (Function(S.front())) + return size() - S.size(); + S = S.drop_front(); } + return npos; + } - return remove_prefix(PrefixLen).remove_suffix(SuffixLen); + // Search for the first character not satisfying the predicate Function + // Returns The index of the first character not satisfying Function starting + // from From, or npos if not found. + template size_t find_if_not(F Function, size_t From = 0) const { + return find_if([Function](char c) { return !Function(c); }, From); } - // Check if this string starts with the given \p Prefix. - bool starts_with(StringView Prefix) const { - if (Len < Prefix.Len) + // front - Get the first character in the string. + char front() const { return Data[0]; } + + // back - Get the last character in the string. + char back() const { return Data[Len - 1]; } + + // Return a StringView equal to 'this' but with the first N elements + // dropped. + StringView drop_front(size_t N = 1) const { return substr(N); } + + // Return a StringView equal to 'this' but with the last N elements + // dropped. + StringView drop_back(size_t N = 1) const { return substr(0, size() - N); } + + // Return a StringView equal to 'this' but with only the first N + // elements remaining. If N is greater than the length of the + // string, the entire string is returned. + StringView take_front(size_t N = 1) const { + if (N >= size()) + return *this; + return drop_back(size() - N); + } + + // Return a StringView equal to 'this' but with only the last N + // elements remaining. If N is greater than the length of the + // string, the entire string is returned. + StringView take_back(size_t N = 1) const { + if (N >= size()) + return *this; + return drop_front(size() - N); + } + + // Return the longest prefix of 'this' such that every character + // in the prefix satisfies the given predicate. + template StringView take_while(F Function) const { + return substr(0, find_if_not(Function)); + } + + // Return the longest prefix of 'this' such that no character in + // the prefix satisfies the given predicate. + template StringView take_until(F Function) const { + return substr(0, find_if(Function)); + } + + // Return a StringView equal to 'this', but with all characters satisfying + // the given predicate dropped from the beginning of the string. + template StringView drop_while(F Function) const { + return substr(find_if_not(Function)); + } + + // Return a StringView equal to 'this', but with all characters not + // satisfying the given predicate dropped from the beginning of the string. + template StringView drop_until(F Function) const { + return substr(find_if(Function)); + } + + // Returns true if this StringView has the given prefix and removes that + // prefix. + bool consume_front(StringView Prefix) { + if (!starts_with(Prefix)) return false; - for (size_t I = 0; I < Prefix.Len; ++I) { - if (Data[I] != Prefix.Data[I]) - return false; - } + + *this = drop_front(Prefix.size()); return true; } - // An equivalent method is not available in std::string_view. - bool equals(StringView Other) const { - if (Len != Other.Len) + // Returns true if this StringView has the given suffix and removes that + // suffix. + bool consume_back(StringView Suffix) { + if (!ends_with(Suffix)) return false; - for (size_t I = 0; I < Len; ++I) { - if (Data[I] != Other.Data[I]) - return false; - } + + *this = drop_back(Suffix.size()); return true; } }; diff --git a/libc/test/src/__support/CPP/stringview_test.cpp b/libc/test/src/__support/CPP/stringview_test.cpp --- a/libc/test/src/__support/CPP/stringview_test.cpp +++ b/libc/test/src/__support/CPP/stringview_test.cpp @@ -9,65 +9,67 @@ #include "src/__support/CPP/StringView.h" #include "utils/UnitTest/Test.h" +using __llvm_libc::cpp::StringView; + TEST(LlvmLibcStringViewTest, InitializeCheck) { - __llvm_libc::cpp::StringView v; + StringView v; ASSERT_EQ(v.size(), size_t(0)); ASSERT_TRUE(v.data() == nullptr); - v = __llvm_libc::cpp::StringView(""); + v = StringView(""); ASSERT_EQ(v.size(), size_t(0)); ASSERT_TRUE(v.data() == nullptr); - v = __llvm_libc::cpp::StringView(nullptr); + v = StringView(nullptr); ASSERT_EQ(v.size(), size_t(0)); ASSERT_TRUE(v.data() == nullptr); - v = __llvm_libc::cpp::StringView(nullptr, 10); + v = StringView(nullptr, 10); ASSERT_EQ(v.size(), size_t(0)); ASSERT_TRUE(v.data() == nullptr); - v = __llvm_libc::cpp::StringView("abc", 0); + v = StringView("abc", 0); ASSERT_EQ(v.size(), size_t(0)); ASSERT_TRUE(v.data() == nullptr); - v = __llvm_libc::cpp::StringView("123456789"); + v = StringView("123456789"); ASSERT_EQ(v.size(), size_t(9)); } TEST(LlvmLibcStringViewTest, Equals) { - __llvm_libc::cpp::StringView v("abc"); - ASSERT_TRUE(v.equals(__llvm_libc::cpp::StringView("abc"))); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView())); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView(""))); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView("123"))); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView("abd"))); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView("aaa"))); - ASSERT_FALSE(v.equals(__llvm_libc::cpp::StringView("abcde"))); + StringView v("abc"); + ASSERT_TRUE(v.equals(StringView("abc"))); + ASSERT_FALSE(v.equals(StringView())); + ASSERT_FALSE(v.equals(StringView(""))); + ASSERT_FALSE(v.equals(StringView("123"))); + ASSERT_FALSE(v.equals(StringView("abd"))); + ASSERT_FALSE(v.equals(StringView("aaa"))); + ASSERT_FALSE(v.equals(StringView("abcde"))); } TEST(LlvmLibcStringViewTest, startsWith) { - __llvm_libc::cpp::StringView v("abc"); - ASSERT_TRUE(v.starts_with(__llvm_libc::cpp::StringView("a"))); - ASSERT_TRUE(v.starts_with(__llvm_libc::cpp::StringView("ab"))); - ASSERT_TRUE(v.starts_with(__llvm_libc::cpp::StringView("abc"))); - ASSERT_TRUE(v.starts_with(__llvm_libc::cpp::StringView())); - ASSERT_TRUE(v.starts_with(__llvm_libc::cpp::StringView(""))); - ASSERT_FALSE(v.starts_with(__llvm_libc::cpp::StringView("123"))); - ASSERT_FALSE(v.starts_with(__llvm_libc::cpp::StringView("abd"))); - ASSERT_FALSE(v.starts_with(__llvm_libc::cpp::StringView("aaa"))); - ASSERT_FALSE(v.starts_with(__llvm_libc::cpp::StringView("abcde"))); + StringView v("abc"); + ASSERT_TRUE(v.starts_with(StringView("a"))); + ASSERT_TRUE(v.starts_with(StringView("ab"))); + ASSERT_TRUE(v.starts_with(StringView("abc"))); + ASSERT_TRUE(v.starts_with(StringView())); + ASSERT_TRUE(v.starts_with(StringView(""))); + ASSERT_FALSE(v.starts_with(StringView("123"))); + ASSERT_FALSE(v.starts_with(StringView("abd"))); + ASSERT_FALSE(v.starts_with(StringView("aaa"))); + ASSERT_FALSE(v.starts_with(StringView("abcde"))); } TEST(LlvmLibcStringViewTest, RemovePrefix) { - __llvm_libc::cpp::StringView v("123456789"); + StringView v("123456789"); auto p = v.remove_prefix(0); ASSERT_EQ(p.size(), size_t(9)); - ASSERT_TRUE(p.equals(__llvm_libc::cpp::StringView("123456789"))); + ASSERT_TRUE(p.equals(StringView("123456789"))); p = v.remove_prefix(4); ASSERT_EQ(p.size(), size_t(5)); - ASSERT_TRUE(p.equals(__llvm_libc::cpp::StringView("56789"))); + ASSERT_TRUE(p.equals(StringView("56789"))); p = v.remove_prefix(9); ASSERT_EQ(p.size(), size_t(0)); @@ -79,15 +81,15 @@ } TEST(LlvmLibcStringViewTest, RemoveSuffix) { - __llvm_libc::cpp::StringView v("123456789"); + StringView v("123456789"); auto p = v.remove_suffix(0); ASSERT_EQ(p.size(), size_t(9)); - ASSERT_TRUE(p.equals(__llvm_libc::cpp::StringView("123456789"))); + ASSERT_TRUE(p.equals(StringView("123456789"))); p = v.remove_suffix(4); ASSERT_EQ(p.size(), size_t(5)); - ASSERT_TRUE(p.equals(__llvm_libc::cpp::StringView("12345"))); + ASSERT_TRUE(p.equals(StringView("12345"))); p = v.remove_suffix(9); ASSERT_EQ(p.size(), size_t(0)); @@ -99,42 +101,78 @@ } TEST(LlvmLibcStringViewTest, TrimSingleChar) { - __llvm_libc::cpp::StringView v(" 123456789 "); + StringView v(" 123456789 "); auto t = v.trim(' '); ASSERT_EQ(t.size(), size_t(9)); - ASSERT_TRUE(t.equals(__llvm_libc::cpp::StringView("123456789"))); + ASSERT_TRUE(t.equals(StringView("123456789"))); - v = __llvm_libc::cpp::StringView("====12345=="); + v = StringView("====12345=="); t = v.trim(' '); ASSERT_EQ(v.size(), size_t(11)); - ASSERT_TRUE(t.equals(__llvm_libc::cpp::StringView("====12345=="))); + ASSERT_TRUE(t.equals(StringView("====12345=="))); t = v.trim('='); ASSERT_EQ(t.size(), size_t(5)); - ASSERT_TRUE(t.equals(__llvm_libc::cpp::StringView("12345"))); + ASSERT_TRUE(t.equals(StringView("12345"))); - v = __llvm_libc::cpp::StringView("12345==="); + v = StringView("12345==="); t = v.trim('='); ASSERT_EQ(t.size(), size_t(5)); - ASSERT_TRUE(t.equals(__llvm_libc::cpp::StringView("12345"))); + ASSERT_TRUE(t.equals(StringView("12345"))); - v = __llvm_libc::cpp::StringView("===========12345"); + v = StringView("===========12345"); t = v.trim('='); ASSERT_EQ(t.size(), size_t(5)); - ASSERT_TRUE(t.equals(__llvm_libc::cpp::StringView("12345"))); + ASSERT_TRUE(t.equals(StringView("12345"))); - v = __llvm_libc::cpp::StringView("============"); + v = StringView("============"); t = v.trim('='); ASSERT_EQ(t.size(), size_t(0)); ASSERT_TRUE(t.data() == nullptr); - v = __llvm_libc::cpp::StringView(); + v = StringView(); t = v.trim(' '); ASSERT_EQ(t.size(), size_t(0)); ASSERT_TRUE(t.data() == nullptr); - v = __llvm_libc::cpp::StringView(""); + v = StringView(""); t = v.trim(' '); ASSERT_EQ(t.size(), size_t(0)); ASSERT_TRUE(t.data() == nullptr); } + +TEST(LlvmLibcStringViewTest, Observer) { + StringView ABC("abc"); + ASSERT_EQ(ABC.size(), size_t(3)); + ASSERT_FALSE(ABC.empty()); + ASSERT_EQ(ABC.front(), 'a'); + ASSERT_EQ(ABC.back(), 'c'); +} + +bool isDigit(char c) { return c >= '0' && c <= '9'; } + +TEST(LlvmLibcStringViewTest, Transform) { + ASSERT_TRUE(StringView("123abc").drop_back(3).equals("123")); + ASSERT_TRUE(StringView("123abc").drop_front(3).equals("abc")); + ASSERT_TRUE(StringView("123abc").take_back(3).equals("abc")); + ASSERT_TRUE(StringView("123abc").take_front(3).equals("123")); + + ASSERT_TRUE(StringView("123abc").take_while(&isDigit).equals("123")); + ASSERT_TRUE(StringView("abc123").take_until(&isDigit).equals("abc")); + ASSERT_TRUE(StringView("123abc").drop_while(&isDigit).equals("abc")); + ASSERT_TRUE(StringView("abc123").drop_until(&isDigit).equals("123")); +} + +TEST(LlvmLibcStringViewTest, ConsumeFront) { + StringView Tmp("abc"); + ASSERT_FALSE(Tmp.consume_front("###")); + ASSERT_TRUE(Tmp.consume_front("ab")); + ASSERT_TRUE(Tmp.equals("c")); +} + +TEST(LlvmLibcStringViewTest, ConsumeBack) { + StringView Tmp("abc"); + ASSERT_FALSE(Tmp.consume_back("###")); + ASSERT_TRUE(Tmp.consume_back("bc")); + ASSERT_TRUE(Tmp.equals("a")); +}