From 9f6b13e5cce96066d7262d224c971d93c2724795 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Tue, 24 Dec 2019 17:25:37 -0600 Subject: [PATCH] [Support] Fix behavior of StringRef::count with overlapping occurrences, add tests 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. Patch by Benno (@Bensge) Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D70585 --- llvm/lib/Support/StringRef.cpp | 9 +++++++-- llvm/unittests/ADT/StringRefTest.cpp | 7 +++++++ 2 files changed, 14 insertions(+), 2 deletions(-) diff --git a/llvm/lib/Support/StringRef.cpp b/llvm/lib/Support/StringRef.cpp index 4bafc4e..d7fa99d 100644 --- a/llvm/lib/Support/StringRef.cpp +++ b/llvm/lib/Support/StringRef.cpp @@ -374,9 +374,14 @@ size_t StringRef::count(StringRef Str) const { 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; } diff --git a/llvm/unittests/ADT/StringRefTest.cpp b/llvm/unittests/ADT/StringRefTest.cpp index 2e5159d..cbb2a30 100644 --- a/llvm/unittests/ADT/StringRefTest.cpp +++ b/llvm/unittests/ADT/StringRefTest.cpp @@ -509,6 +509,13 @@ TEST(StringRefTest, Count) { 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) { -- 2.7.4