Add StringRef {take, drop} x {_while, _until}

[zturner]

Summary

This adds support for some common functional style operations
that allow you to take or drop characters until a certain
condition is met.

Example:

assert(StringRef("ABCD2908XYZ".take_while([](char c) { return ::is_hexdigit(c); }) == "XYZ");

[zturner]

Cleaned up the test. The lambda was unnecessary.

[davide]

lgtm, I like llvm becoming more haskell'y.

[davide]

include/llvm/ADT/StringRef.h

499–500 ↗

(On Diff #72210)

Oh, and maybe if you can add a comment at the beginning of each function (e.g. as consume_front() already does) it would be good.

[majnemer]

include/llvm/ADT/StringRef.h

499–511 ↗

(On Diff #72210)

Can you use function_ref instead?

[sanjoy]

Have you considered adding StringRef(iterator, iterator) constructor, and replacing the explicit loops with std::find_if and std::find_if_not.

[zturner]

Added find_if and made the drop and take functions use that.

[zturner]

Last patch was wrong. Let's try this.

[sanjoy]

lgtm modulo minor comments

include/llvm/ADT/StringRef.h

280 ↗

(On Diff #72374)

Docs?

283 ↗

(On Diff #72374)

Do you know if clang generates a zero-abstraction-overhead loop for this code? If it doesn't, it is an LLVM bug. :)

292 ↗

(On Diff #72374)

No LLVM_ATTRIBUTE_UNUSED_RESULT here?

293 ↗

(On Diff #72374)

Docs?

517 ↗

(On Diff #72374)

Docs?

Applies to all of the new functions you added.

unittests/ADT/StringRefTest.cpp

918 ↗

(On Diff #72374)

I'd use a separate variable for this:

StringRef EmptyStr = "";

Same comment for TakeWhileUntil.

llvm/trunk/include/llvm/ADT/StringRef.h

 //===--- StringRef.h - Constant String Reference Wrapper --------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STRINGREF_H
 #define LLVM_ADT_STRINGREF_H
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include <algorithm>
 #include <cassert>
 #include <cstring>
 #include <limits>
 #include <string>
 #include <utility>
size_t find(char C, size_t From = 0) const {
       if (FindBegin < Length) { // Avoid calling memchr with nullptr.
         // Just forward to memchr, which is faster than a hand-rolled loop.
         if (const void *P = ::memchr(Data + FindBegin, C, Length - FindBegin))
           return static_cast<const char *>(P) - Data;
       }
       return npos;
     }
 
+    /// Search for the first character satisfying the predicate \p F
+    ///
+    /// \returns The index of the first character satisfying \p F starting from
+    /// \p From, or npos if not found.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    size_t find_if(function_ref<bool(char)> F, size_t From = 0) const {
+      StringRef S = drop_front(From);
+      while (!S.empty()) {
+        if (F(S.front()))
+          return size() - S.size();
+        S = S.drop_front();
+      }
+      return npos;
+    }
+
+    /// Search for the first character not satisfying the predicate \p F
+    ///
+    /// \returns The index of the first character not satisfying \p F starting
+    /// from \p From, or npos if not found.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    size_t find_if_not(function_ref<bool(char)> F, size_t From = 0) const {
+      return find_if([F](char c) { return !F(c); }, From);
+    }
+
     /// Search for the first string \p Str in the string.
     ///
     /// \returns The index of the first occurrence of \p Str, or npos if not
     /// found.
     size_t find(StringRef Str, size_t From = 0) const;
 
     /// Search for the last character \p C in the string.
     ///
public:
     /// Complexity: O(size() + Chars.size())
     size_t find_last_not_of(StringRef Chars, size_t From = npos) const;
 
     /// Return true if the given string is a substring of *this, and false
     /// otherwise.
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool contains(StringRef Other) const { return find(Other) != npos; }
 
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool contains(char C) const { return find_first_of(C) != npos; }
+
     /// @}
     /// @name Helpful Algorithms
     /// @{
 
     /// Return the number of occurrences of \p C in the string.
     size_t count(char C) const {
       size_t Count = 0;
       for (size_t i = 0, e = Length; i != e; ++i)
public:
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     LLVM_ATTRIBUTE_UNUSED_RESULT
     StringRef 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.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    StringRef take_while(function_ref<bool(char)> F) const {
+      return substr(0, find_if_not(F));
+    }
+
+    /// Return the longest prefix of 'this' such that no character in
+    /// the prefix satisfies the given predicate.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    StringRef take_until(function_ref<bool(char)> F) const {
+      return substr(0, find_if(F));
+    }
+
     /// Return a StringRef equal to 'this' but with the first \p N elements
     /// dropped.
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     LLVM_ATTRIBUTE_UNUSED_RESULT
     StringRef drop_front(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return substr(N);
     }
 
     /// Return a StringRef equal to 'this' but with the last \p N elements
     /// dropped.
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     LLVM_ATTRIBUTE_UNUSED_RESULT
     StringRef drop_back(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return substr(0, size()-N);
     }
 
+    /// Return a StringRef equal to 'this', but with all characters satisfying
+    /// the given predicate dropped from the beginning of the string.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    StringRef drop_while(function_ref<bool(char)> F) const {
+      return substr(find_if_not(F));
+    }
+
+    /// Return a StringRef equal to 'this', but with all characters not
+    /// satisfying the given predicate dropped from the beginning of the string.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    LLVM_ATTRIBUTE_UNUSED_RESULT
+    StringRef drop_until(function_ref<bool(char)> F) const {
+      return substr(find_if(F));
+    }
+
     /// Returns true if this StringRef has the given prefix and removes that
     /// prefix.
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     LLVM_ATTRIBUTE_UNUSED_RESULT
     bool consume_front(StringRef Prefix) {
       if (!startswith(Prefix))
         return false;
 

llvm/trunk/unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, Take) {
 
   Taken = Test.take_front(0);
   EXPECT_TRUE(Taken.empty());
 
   Taken = Test.take_back(0);
   EXPECT_TRUE(Taken.empty());
 }
 
+TEST(StringRefTest, FindIf) {
+  StringRef Punct("Test.String");
+  StringRef NoPunct("ABCDEFG");
+  StringRef Empty;
+
+  auto IsPunct = [](char c) { return ::ispunct(c); };
+  auto IsAlpha = [](char c) { return ::isalpha(c); };
+  EXPECT_EQ(4, Punct.find_if(IsPunct));
+  EXPECT_EQ(StringRef::npos, NoPunct.find_if(IsPunct));
+  EXPECT_EQ(StringRef::npos, Empty.find_if(IsPunct));
+
+  EXPECT_EQ(4, Punct.find_if_not(IsAlpha));
+  EXPECT_EQ(StringRef::npos, NoPunct.find_if_not(IsAlpha));
+  EXPECT_EQ(StringRef::npos, Empty.find_if_not(IsAlpha));
+}
+
+TEST(StringRefTest, TakeWhileUntil) {
+  StringRef Test("String With 1 Number");
+
+  StringRef Taken = Test.take_while([](char c) { return ::isdigit(c); });
+  EXPECT_EQ("", Taken);
+
+  Taken = Test.take_until([](char c) { return ::isdigit(c); });
+  EXPECT_EQ("String With ", Taken);
+
+  Taken = Test.take_while([](char c) { return true; });
+  EXPECT_EQ(Test, Taken);
+
+  Taken = Test.take_until([](char c) { return true; });
+  EXPECT_EQ("", Taken);
+
+  Test = "";
+  Taken = Test.take_while([](char c) { return true; });
+  EXPECT_EQ("", Taken);
+}
+
+TEST(StringRefTest, DropWhileUntil) {
+  StringRef Test("String With 1 Number");
+
+  StringRef Taken = Test.drop_while([](char c) { return ::isdigit(c); });
+  EXPECT_EQ(Test, Taken);
+
+  Taken = Test.drop_until([](char c) { return ::isdigit(c); });
+  EXPECT_EQ("1 Number", Taken);
+
+  Taken = Test.drop_while([](char c) { return true; });
+  EXPECT_EQ("", Taken);
+
+  Taken = Test.drop_until([](char c) { return true; });
+  EXPECT_EQ(Test, Taken);
+
+  StringRef EmptyString = "";
+  Taken = EmptyString.drop_while([](char c) { return true; });
+  EXPECT_EQ("", Taken);
+}
+
 } // end anonymous namespace