Add StringRef::find_lower and contains_lower

[zturner]

Summary

These are replacements for the standard C api strcasestr().

I chose to implement this by allocating two copies on the heap and then using existing code. But I could also implement this using an M*N loop if you think that's preferable. Neither way is ideal, but there isn't exactly a fast way to implement this.

[chandlerc]

Why not implement find_lower the same way find is implemented? It doesn't seem too hard? Just define a local version of memcmp that does ascii_tolower on each character before comparing and doing the same thing prior to inserting into the skip table or looking up a skip distance in it?

Could try to share the code if you really want with a templated helper that calls a passed-in callable on each character, but doesn't really seem worth it to me.

[zturner]

Actually I don't see why we shouldn't just use startswith_lower. It basically does exactly what you're saying. Updated the code to use this approach. While I'm in here, I think we might as well add rfind_lower to maintain API symmetry, so I went ahead and did that too.

include/llvm/ADT/StringRef.h

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 \p C in the string, ignoring case.
+    ///
+    /// \returns The index of the first occurrence of \p C, or npos if not
+    /// found.
+    size_t find_lower(char C, size_t From = 0) const;
+
     /// 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);
public:
     }
 
     /// 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 first string \p Str in the string, ignoring case.
+    ///
+    /// \returns The index of the first occurrence of \p Str, or npos if not
+    /// found.
+    size_t find_lower(StringRef Str, size_t From = 0) const;
+
     /// Search for the last character \p C in the string.
     ///
     /// \returns The index of the last occurrence of \p C, or npos if not
     /// found.
     size_t rfind(char C, size_t From = npos) const {
       From = std::min(From, Length);
       size_t i = From;
       while (i != 0) {
         --i;
         if (Data[i] == C)
           return i;
       }
       return npos;
     }
 
+    /// Search for the last character \p C in the string, ignoring case.
+    ///
+    /// \returns The index of the last occurrence of \p C, or npos if not
+    /// found.
+    size_t rfind_lower(char C, size_t From = npos) const;
+
     /// Search for the last string \p Str in the string.
     ///
     /// \returns The index of the last occurrence of \p Str, or npos if not
     /// found.
     size_t rfind(StringRef Str) const;
 
+    /// Search for the last string \p Str in the string, ignoring case.
+    ///
+    /// \returns The index of the last occurrence of \p Str, or npos if not
+    /// found.
+    size_t rfind_lower(StringRef Str) const;
+
     /// Find the first character in the string that is \p C, or npos if not
     /// found. Same as find.
     size_t find_first_of(char C, size_t From = 0) const {
       return find(C, From);
     }
 
     /// Find the first character in the string that is in \p Chars, or npos if
     /// not found.
public:
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool contains(StringRef Other) const { return find(Other) != npos; }
 
     /// Return true if the given character is contained in *this, and false
     /// otherwise.
     LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool contains(char C) const { return find_first_of(C) != npos; }
 
+    /// Return true if the given string is a substring of *this, and false
+    /// otherwise.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool contains_lower(StringRef Other) const {
+      return find_lower(Other) != npos;
+    }
+
+    /// Return true if the given character is contained in *this, and false
+    /// otherwise.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool contains_lower(char C) const { return find_lower(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)

lib/Support/StringRef.cpp

 }
 
 /// Check if this string ends with the given \p Suffix, ignoring case.
 bool StringRef::endswith_lower(StringRef Suffix) const {
   return Length >= Suffix.Length &&
       ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0;
 }
 
+size_t StringRef::find_lower(char C, size_t From) const {
+  char L = ascii_tolower(C);
+  return find_if([L](char D) { return ascii_tolower(D) == L; }, From);
+}
+
 /// compare_numeric - Compare strings, handle embedded numbers.
 int StringRef::compare_numeric(StringRef RHS) const {
   for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) {
     // Check for sequences of digits.
     if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) {
       // The longer sequence of numbers is considered larger.
       // This doesn't really handle prefixed zeros well.
       size_t J;
do {
 
     // Otherwise skip the appropriate number of bytes.
     Start += BadCharSkip[(uint8_t)Start[N-1]];
   } while (Start < Stop);
 
   return npos;
 }
 
+size_t StringRef::find_lower(StringRef Str, size_t From) const {
+  StringRef This = substr(From);
+  while (This.size() >= Str.size()) {
+    if (This.startswith_lower(Str))
+      return From;
+    This = This.drop_front();
+    ++From;
+  }
+  return npos;
+}
+
+size_t StringRef::rfind_lower(char C, size_t From) const {
+  From = std::min(From, Length);
+  size_t i = From;
+  while (i != 0) {
+    --i;
+    if (ascii_tolower(Data[i]) == ascii_tolower(C))
+      return i;
+  }
+  return npos;
+}
+
 /// rfind - Search for the last string \arg Str in the string.
 ///
 /// \return - The index of the last occurrence of \arg Str, or npos if not
 /// found.
 size_t StringRef::rfind(StringRef Str) const {
   size_t N = Str.size();
   if (N > Length)
     return npos;
   for (size_t i = Length - N + 1, e = 0; i != e;) {
     --i;
     if (substr(i, N).equals(Str))
       return i;
   }
   return npos;
 }
 
+size_t StringRef::rfind_lower(StringRef Str) const {
+  size_t N = Str.size();
+  if (N > Length)
+    return npos;
+  for (size_t i = Length - N + 1, e = 0; i != e;) {
+    --i;
+    if (substr(i, N).equals_lower(Str))
+      return i;
+  }
+  return npos;
+}
+
 /// find_first_of - Find the first character in the string that is in \arg
 /// Chars, or npos if not found.
 ///
 /// Note: O(size() + Chars.size())
 StringRef::size_type StringRef::find_first_of(StringRef Chars,
                                               size_t From) const {
   std::bitset<1 << CHAR_BIT> CharBits;
   for (size_type i = 0; i != Chars.size(); ++i)

unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, ConsumeBack) {
   EXPECT_EQ("hel", Str);
   EXPECT_TRUE(Str.consume_back("hel"));
   EXPECT_EQ("", Str);
   EXPECT_FALSE(Str.consume_back("h"));
   EXPECT_TRUE(Str.consume_back(""));
 }
 
 TEST(StringRefTest, Find) {
-  StringRef Str("hello");
-  EXPECT_EQ(2U, Str.find('l'));
-  EXPECT_EQ(StringRef::npos, Str.find('z'));
-  EXPECT_EQ(StringRef::npos, Str.find("helloworld"));
-  EXPECT_EQ(0U, Str.find("hello"));
-  EXPECT_EQ(1U, Str.find("ello"));
-  EXPECT_EQ(StringRef::npos, Str.find("zz"));
-  EXPECT_EQ(2U, Str.find("ll", 2));
-  EXPECT_EQ(StringRef::npos, Str.find("ll", 3));
-  EXPECT_EQ(0U, Str.find(""));
-  StringRef LongStr("hellx xello hell ello world foo bar hello");
-  EXPECT_EQ(36U, LongStr.find("hello"));
-  EXPECT_EQ(28U, LongStr.find("foo"));
-  EXPECT_EQ(12U, LongStr.find("hell", 2));
-  EXPECT_EQ(0U, LongStr.find(""));
+  StringRef Str("helloHELLO");
+  StringRef LongStr("hellx xello hell ello world foo bar hello HELLO");
+
+  struct {
+    StringRef Str;
+    char C;
+    std::size_t From;
+    std::size_t Pos;
+    std::size_t LowerPos;
+  } CharExpectations[] = {
+      {Str, 'h', 0U, 0U, 0U},
+      {Str, 'e', 0U, 1U, 1U},
+      {Str, 'l', 0U, 2U, 2U},
+      {Str, 'l', 3U, 3U, 3U},
+      {Str, 'o', 0U, 4U, 4U},
+      {Str, 'L', 0U, 7U, 2U},
+      {Str, 'z', 0U, StringRef::npos, StringRef::npos},
+  };
+
+  struct {
+    StringRef Str;
+    llvm::StringRef S;
+    std::size_t From;
+    std::size_t Pos;
+    std::size_t LowerPos;
+  } StrExpectations[] = {
+      {Str, "helloword", 0, StringRef::npos, StringRef::npos},
+      {Str, "hello", 0, 0U, 0U},
+      {Str, "ello", 0, 1U, 1U},
+      {Str, "zz", 0, StringRef::npos, StringRef::npos},
+      {Str, "ll", 2U, 2U, 2U},
+      {Str, "ll", 3U, StringRef::npos, 7U},
+      {Str, "LL", 2U, 7U, 2U},
+      {Str, "LL", 3U, 7U, 7U},
+      {Str, "", 0U, 0U, 0U},
+      {LongStr, "hello", 0U, 36U, 36U},
+      {LongStr, "foo", 0U, 28U, 28U},
+      {LongStr, "hell", 2U, 12U, 12U},
+      {LongStr, "HELL", 2U, 42U, 12U},
+      {LongStr, "", 0U, 0U, 0U}};
+
+  for (auto &E : CharExpectations) {
+    EXPECT_EQ(E.Pos, E.Str.find(E.C, E.From));
+    EXPECT_EQ(E.LowerPos, E.Str.find_lower(E.C, E.From));
+    EXPECT_EQ(E.LowerPos, E.Str.find_lower(toupper(E.C), E.From));
+  }
+
+  for (auto &E : StrExpectations) {
+    EXPECT_EQ(E.Pos, E.Str.find(E.S, E.From));
+    EXPECT_EQ(E.LowerPos, E.Str.find_lower(E.S, E.From));
+    EXPECT_EQ(E.LowerPos, E.Str.find_lower(E.S.upper(), E.From));
+  }
 
   EXPECT_EQ(3U, Str.rfind('l'));
   EXPECT_EQ(StringRef::npos, Str.rfind('z'));
   EXPECT_EQ(StringRef::npos, Str.rfind("helloworld"));
   EXPECT_EQ(0U, Str.rfind("hello"));
   EXPECT_EQ(1U, Str.rfind("ello"));
   EXPECT_EQ(StringRef::npos, Str.rfind("zz"));
 
+  EXPECT_EQ(8U, Str.rfind_lower('l'));
+  EXPECT_EQ(8U, Str.rfind_lower('L'));
+  EXPECT_EQ(StringRef::npos, Str.rfind_lower('z'));
+  EXPECT_EQ(StringRef::npos, Str.rfind_lower("HELLOWORLD"));
+  EXPECT_EQ(5U, Str.rfind("HELLO"));
+  EXPECT_EQ(6U, Str.rfind("ELLO"));
+  EXPECT_EQ(StringRef::npos, Str.rfind("ZZ"));
+
   EXPECT_EQ(2U, Str.find_first_of('l'));
   EXPECT_EQ(1U, Str.find_first_of("el"));
   EXPECT_EQ(StringRef::npos, Str.find_first_of("xyz"));
 
+  Str = "hello";
   EXPECT_EQ(1U, Str.find_first_not_of('h'));
   EXPECT_EQ(4U, Str.find_first_not_of("hel"));
   EXPECT_EQ(StringRef::npos, Str.find_first_not_of("hello"));
 
   EXPECT_EQ(3U, Str.find_last_not_of('o'));
   EXPECT_EQ(1U, Str.find_last_not_of("lo"));
   EXPECT_EQ(StringRef::npos, Str.find_last_not_of("helo"));
 }