[libc][utils] Add more methods to StringView

[gchatelet]

• remove duplicated method with similar name

[gchatelet]

• Use StringRef implementation for equals

[courbet]

libc/src/__support/CPP/StringView.h

22

@sivachandra Do we really want to keep duplicating the whole libc++ in there ? I can see why we can't use gtest to test the libc, but we should be able to use gtest to test individual internal components. Then we would not need to reimplement the world.

internal unit tests would test __llvm_libc::CodeUnderTest using the system libc and gtest
libc API tests would use the extern C CodeUnderTest build with -ffrestanding and using llvm-libc and LibCTest

Does that make sense ? At least for code that doe snot rely on errno and such weird things.

[jeffbailey]

This would be really nice to have for things like the TZ environment variable string parsing that Raman are working on.

[gchatelet]

This comment has been deleted.

[sivachandra]

libc/src/__support/CPP/StringView.h

22

@sivachandra Do we really want to keep duplicating the whole libc++ in there ?

Just pointing out, a large part of that duplicated code is used in the actual libc runtime code. So, while it might seem like unnecessarily duplicated especially when it seems like it is being used only for testing, it is not going to waste.

I can see why we can't use gtest to test the libc, but we should be able to use gtest to test individual internal components. Then we would not need to reimplement the world.

internal unit tests would test __llvm_libc::CodeUnderTest using the system libc and gtest
libc API tests would use the extern C CodeUnderTest build with -ffrestanding and using llvm-libc and LibCTest

We almost never test the C symbols in our unittests. All of our unittests test members in the __llvm_libc namespace. So, if we go with your suggestion, then we can stick with gtest almost always. But, we have moved away from using gtest because we build and run our unittests in two different modes:

1. The default mode in which we use public headers from the system libc. Of course, only those functions which do not depend on the definitions in the header files can be tested in this manner. For example, most of the functions in string.h and math.h. The unittests for those functions can very well use gtest, include the C++ standard library etc and it should all just work fine.
2. The full build mode in which we test the libc against its own public headers. This mode prevents us from including the C++ standard library headers, gtest headers or any other third party library headers as they can themselves potentially include the libc headers.

Does that make sense ? At least for code that doe snot rely on errno and such weird things.

Beyond errno, not so weird things like macro definitions and type definitions can also cause problems in the full build mode.

[jeffbailey]

A few minor comments within. Thanks for doing this.

libc/src/__support/CPP/StringView.h

22

I wonder if the conversation about gtest could be forked off to a different thread, as I'd really like this patch in for the TZ parsing stuff and it seem a bit orthogonal to the cpp::StringView improvements.

27

Is it with factoring this out into a separate header and making a template? It seems likely that min/max will get used in a few places.

134–158

operator== was added in c++17

141

Why not starts_with like in the standard?

161

Why not ends_with like in the standard?

[courbet]

libc/src/__support/CPP/StringView.h

22

I'm not opposed to this particular patch to be clear, please proceed :)

22

Just pointing out, a large part of that duplicated code is used in the actual libc runtime code.

For code were that's the case, then that's fine. But I've seen Guillaume suffer from not being able to use gtest (and he implemented this patch for tests if I'm not mistaken).

We almost never test the C symbols in our unittests. All of our unittests test members in the __llvm_libc namespace. So, if we go with your suggestion, then we can stick with gtest almost always.

I think this is great.

The full build mode in which we test the libc against its own public headers. This mode prevents us from including the C++ standard library headers, gtest headers or any other third party library headers as they can themselves potentially include the libc headers.

My suggestion would be to have some tests not be run in full build mode, and therefore let these use gtest and all c++ features directly. For example, the tests for the memcpy SizedOp really focus on testing the c++ logic there. I think it't fine to assume that the underlying libc is working, and therefore to use whatever is installed on the system.

[gchatelet]

libc/src/__support/CPP/StringView.h

22

Since everybody agrees, let's proceed with this patch.

As @courbet said I've created this patch because I couldn't use iostream nor string in algorithm_test.cpp and it was failing in full build mode.
The solution was to disable this particular test in full build mode.

@sivachandra AFAIU full build is really here to make sure that we can build llvmlibc.a while using llvm libc's header and library. To me it serves as an integration test. It would make sense to run functional tests in full build more (i.e. making sure that the C function behaves like they should) but I don't think running unittests brings anything.

Let's discuss this in a separate patch.

[gchatelet]

• Address comments

[jeffbailey]

Thank you!

libc/src/__support/CPP/StringView.h

 namespace __llvm_libc {
 namespace cpp {
 
 // This is very simple alternate of the std::string_view class. There is no
 // bounds check performed in any of the methods. The callers are expected to
 // do the checks before invoking the methods.
 //
 // This class will be extended as needed in future.
 class StringView {
 private:
   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
   // not include the terminating null character.
   explicit StringView(const char *Str) : Data(Str), Len(0) {
     if (Str == nullptr)
       return;
     for (const char *D = Data; *D != '\0'; ++D, ++Len)
       ;
     if (Len == 0)
       Data = nullptr;
   }
 
   explicit StringView(const char *Str, size_t N)
       : Data(N ? Str : nullptr), Len(Str == nullptr ? 0 : N) {}
 
+  // Ctor for raw literal.
+  template <size_t N>
+  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();
     return StringView(Data, Len - N);
   }
 
   // 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;
 
-    size_t SuffixLen = 0;
-    const char *NewEnd = Data + Len - 1;
-    for (; SuffixLen < Len; --NewEnd, ++SuffixLen) {
-      if (*NewEnd != C)
-        break;
-    }
+  // 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 remove_prefix(PrefixLen).remove_suffix(SuffixLen);
+  // 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));
   }
 
-  // Check if this string starts with the given \p Prefix.
-  bool starts_with(StringView Prefix) const {
-    if (Len < Prefix.Len)
-      return false;
-    for (size_t I = 0; I < Prefix.Len; ++I) {
-      if (Data[I] != Prefix.Data[I])
-        return false;
+  // 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 <typename F> 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 true;
+    return npos;
   }
 
-  // An equivalent method is not available in std::string_view.
-  bool equals(StringView Other) const {
-    if (Len != Other.Len)
-      return false;
-    for (size_t I = 0; I < Len; ++I) {
-      if (Data[I] != Other.Data[I])
-        return false;
-    }
+  // 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 <typename F> size_t find_if_not(F Function, size_t From = 0) const {
+    return find_if([Function](char c) { return !Function(c); }, From);
+  }
+
+  // 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 <typename F> 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 <typename F> 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 <typename F> 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 <typename F> 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))
+
+    *this = drop_front(Prefix.size());
+    return true;
+
+  // Returns true if this StringView has the given suffix and removes that
+  // suffix.
+  bool consume_back(StringView Suffix) {
+    if (!ends_with(Suffix))
+      return false;
+
+    *this = drop_back(Suffix.size());
     return true;
   }
 };
 
 } // namespace cpp
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_STRINGVIEW_H

libc/test/src/__support/CPP/stringview_test.cpp

 //===-- Unittests for StringView ------------------------------------------===//
 //
 // 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/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));
   ASSERT_TRUE(p.data() == nullptr);
 
   p = v.remove_prefix(10);
   ASSERT_EQ(p.size(), size_t(0));
   ASSERT_TRUE(p.data() == nullptr);
 }
 
 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));
   ASSERT_TRUE(p.data() == nullptr);
 
   p = v.remove_suffix(10);
   ASSERT_EQ(p.size(), size_t(0));
   ASSERT_TRUE(p.data() == nullptr);
 }
 
 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"));
+}