[Support] Fix behavior of StringRef::count with overlapping occurrences, add tests

[Bensge]

Summary

Fix the behavior of StringRef::count(StringRef) to not count overlapping occurrences, as is stated in the documentation.
Fixes bug https://bugs.llvm.org/show_bug.cgi?id=44072

I added Krzysztof Parzyszek to review this change because a use of this function in HexagonInstrInfo::getInlineAsmLength might depend on the overlapping-behavior. I don't have enough domain knowledge to tell if this change could break anything there.

All other uses of this method in LLVM (besides the unit tests) only use single-character search strings. In those cases, search occurrences can not overlap anyway.

[Bensge]

Ping.

[Bensge]

Ping.

[jdoerfert]

LGTM.

[Bensge]

Thank you for reviewing this change. You may commit it as I don't have commit access.

[aganea]

Hi! This patch broke the polly tests (the bot seems down). I wrote a fix here: 92b68c1937cd065a2fc44d18c1099de7da19b356 - it was trivial enough, but please let me know if you don't agree with the fix.

llvm/lib/Support/StringRef.cpp

 
 /// count - Return the number of non-overlapped occurrences of \arg Str in
 /// the string.
 size_t StringRef::count(StringRef Str) const {
   size_t Count = 0;
   size_t N = Str.size();
   if (N > Length)
     return 0;
-  for (size_t i = 0, e = Length - N + 1; i != e; ++i)
-    if (substr(i, N).equals(Str))
+  for (size_t i = 0, e = Length - N + 1; i < e;) {
+    if (substr(i, N).equals(Str)) {
       ++Count;
+      i += N;
+    }
+    else
+      ++i;
+  }
   return Count;
 }
 
 static unsigned GetAutoSenseRadix(StringRef &Str) {
   if (Str.empty())
     return 10;
 
   if (Str.startswith("0x") || Str.startswith("0X")) {

llvm/unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, Count) {
   StringRef Str("hello");
   EXPECT_EQ(2U, Str.count('l'));
   EXPECT_EQ(1U, Str.count('o'));
   EXPECT_EQ(0U, Str.count('z'));
   EXPECT_EQ(0U, Str.count("helloworld"));
   EXPECT_EQ(1U, Str.count("hello"));
   EXPECT_EQ(1U, Str.count("ello"));
   EXPECT_EQ(0U, Str.count("zz"));
+
+  StringRef OverlappingAbba("abbabba");
+  EXPECT_EQ(1U, OverlappingAbba.count("abba"));
+  StringRef NonOverlappingAbba("abbaabba");
+  EXPECT_EQ(2U, NonOverlappingAbba.count("abba"));
+  StringRef ComplexAbba("abbabbaxyzabbaxyz");
+  EXPECT_EQ(2U, ComplexAbba.count("abba"));
 }
 
 TEST(StringRefTest, EditDistance) {
   StringRef Hello("hello");
   EXPECT_EQ(2U, Hello.edit_distance("hill"));
 
   StringRef Industry("industry");
   EXPECT_EQ(6U, Industry.edit_distance("interest"));