AK: Move the wildcard-matching implementation to StringUtils

Provide wrappers in the String and StringView classes, and add some tests.

9 files changed, 140 insertions, 61 deletions

diff --git a/AK/String.cpp b/AK/String.cpp
index 131ba9e70f..c0bfd9bfea 100644
--- a/AK/String.cpp
+++ b/AK/String.cpp
@@ -331,59 +331,7 @@ String String::repeated(char ch, size_t count)
 
 bool String::matches(const StringView& mask, CaseSensitivity case_sensitivity) const
 {
-    if (case_sensitivity == CaseSensitivity::CaseInsensitive) {
-        String this_lower = this->to_lowercase();
-        String mask_lower = String(mask).to_lowercase();
-        return this_lower.match_helper(mask_lower);
-    }
-
-    return match_helper(mask);
-}
-
-bool String::match_helper(const StringView& mask) const
-{
-    if (is_null())
-        return false;
-
-    const char* string_ptr = characters();
-    const char* mask_ptr = mask.characters_without_null_termination();
-    const char* mask_end = mask_ptr + mask.length();
-
-    // Match string against mask directly unless we hit a *
-    while ((*string_ptr) && (mask_ptr < mask_end) && (*mask_ptr != '*')) {
-        if ((*mask_ptr != *string_ptr) && (*mask_ptr != '?'))
-            return false;
-        mask_ptr++;
-        string_ptr++;
-    }
-
-    const char* cp = nullptr;
-    const char* mp = nullptr;
-
-    while (*string_ptr) {
-        if ((mask_ptr < mask_end) && (*mask_ptr == '*')) {
-            // If we have only a * left, there is no way to not match.
-            if (++mask_ptr == mask_end)
-                return true;
-            mp = mask_ptr;
-            cp = string_ptr + 1;
-        } else if ((mask_ptr < mask_end) && ((*mask_ptr == *string_ptr) || (*mask_ptr == '?'))) {
-            mask_ptr++;
-            string_ptr++;
-        } else if ((cp != nullptr) && (mp != nullptr)) {
-            mask_ptr = mp;
-            string_ptr = cp++;
-        } else {
-            break;
-        }
-    }
-
-    // Handle any trailing mask
-    while ((mask_ptr < mask_end) && (*mask_ptr == '*'))
-        mask_ptr++;
-
-    // If we 'ate' all of the mask and the string then we match.
-    return (mask_ptr == mask_end) && !*string_ptr;
+    return StringUtils::matches(*this, mask, case_sensitivity);
 }
 
 bool String::contains(const String& needle) const
diff --git a/AK/String.h b/AK/String.h
index c1c381f00f..9716eabf73 100644
--- a/AK/String.h
+++ b/AK/String.h
@@ -29,6 +29,7 @@
 #include <AK/Forward.h>
 #include <AK/RefPtr.h>
 #include <AK/StringImpl.h>
+#include <AK/StringUtils.h>
 #include <AK/StringView.h>
 #include <AK/Traits.h>
 
@@ -108,13 +109,8 @@ public:
     {
     }
 
-    enum class CaseSensitivity {
-        CaseInsensitive,
-        CaseSensitive,
-    };
-
     static String repeated(char, size_t count);
-    bool matches(const StringView& pattern, CaseSensitivity = CaseSensitivity::CaseInsensitive) const;
+    bool matches(const StringView& mask, CaseSensitivity = CaseSensitivity::CaseInsensitive) const;
 
     // FIXME: These should be shared between String and StringView somehow!
     int to_int(bool& ok) const;
@@ -244,7 +240,6 @@ public:
     }
 
 private:
-    bool match_helper(const StringView& mask) const;
     RefPtr<StringImpl> m_impl;
 };
 
diff --git a/AK/StringUtils.cpp b/AK/StringUtils.cpp
new file mode 100644
index 0000000000..fe37f49e0b
--- /dev/null
+++ b/AK/StringUtils.cpp
@@ -0,0 +1,64 @@
+#include <AK/String.h>
+#include <AK/StringUtils.h>
+#include <AK/StringView.h>
+
+namespace AK {
+
+namespace StringUtils {
+
+    bool matches(const StringView& str, const StringView& mask, CaseSensitivity case_sensitivity)
+    {
+        if (str.is_null() || mask.is_null())
+            return str.is_null() && mask.is_null();
+
+        if (case_sensitivity == CaseSensitivity::CaseInsensitive) {
+            const String str_lower = String(str).to_lowercase();
+            const String mask_lower = String(mask).to_lowercase();
+            return matches(str_lower, mask_lower, CaseSensitivity::CaseSensitive);
+        }
+
+        const char* string_ptr = str.characters_without_null_termination();
+        const char* string_end = string_ptr + str.length();
+        const char* mask_ptr = mask.characters_without_null_termination();
+        const char* mask_end = mask_ptr + mask.length();
+
+        // Match string against mask directly unless we hit a *
+        while ((string_ptr < string_end) && (mask_ptr < mask_end) && (*mask_ptr != '*')) {
+            if ((*mask_ptr != *string_ptr) && (*mask_ptr != '?'))
+                return false;
+            mask_ptr++;
+            string_ptr++;
+        }
+
+        const char* cp = nullptr;
+        const char* mp = nullptr;
+
+        while (string_ptr < string_end) {
+            if ((mask_ptr < mask_end) && (*mask_ptr == '*')) {
+                // If we have only a * left, there is no way to not match.
+                if (++mask_ptr == mask_end)
+                    return true;
+                mp = mask_ptr;
+                cp = string_ptr + 1;
+            } else if ((mask_ptr < mask_end) && ((*mask_ptr == *string_ptr) || (*mask_ptr == '?'))) {
+                mask_ptr++;
+                string_ptr++;
+            } else if ((cp != nullptr) && (mp != nullptr)) {
+                mask_ptr = mp;
+                string_ptr = cp++;
+            } else {
+                break;
+            }
+        }
+
+        // Handle any trailing mask
+        while ((mask_ptr < mask_end) && (*mask_ptr == '*'))
+            mask_ptr++;
+
+        // If we 'ate' all of the mask and the string then we match.
+        return (mask_ptr == mask_end) && string_ptr == string_end;
+    }
+
+}
+
+}
diff --git a/AK/StringUtils.h b/AK/StringUtils.h
new file mode 100644
index 0000000000..a21fc23de2
--- /dev/null
+++ b/AK/StringUtils.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <AK/Forward.h>
+
+namespace AK {
+
+enum class CaseSensitivity {
+    CaseInsensitive,
+    CaseSensitive,
+};
+
+namespace StringUtils {
+
+    bool matches(const StringView& str, const StringView& mask, CaseSensitivity = CaseSensitivity::CaseInsensitive);
+
+}
+
+}
+
+using AK::CaseSensitivity;
diff --git a/AK/StringView.cpp b/AK/StringView.cpp
index 0dcd8e5b54..c94c8dea33 100644
--- a/AK/StringView.cpp
+++ b/AK/StringView.cpp
@@ -143,6 +143,11 @@ bool StringView::ends_with(const StringView& str) const
     return !memcmp(characters_without_null_termination() + length() - str.length(), str.characters_without_null_termination(), str.length());
 }
 
+bool StringView::matches(const StringView& mask, CaseSensitivity case_sensitivity) const
+{
+    return StringUtils::matches(*this, mask, case_sensitivity);
+}
+
 StringView StringView::substring_view(size_t start, size_t length) const
 {
     ASSERT(start + length <= m_length);
diff --git a/AK/StringView.h b/AK/StringView.h
index 8ccbefcad5..7835498cad 100644
--- a/AK/StringView.h
+++ b/AK/StringView.h
@@ -28,6 +28,7 @@
 
 #include <AK/Forward.h>
 #include <AK/StdLibExtras.h>
+#include <AK/StringUtils.h>
 
 namespace AK {
 
@@ -65,6 +66,7 @@ public:
     bool ends_with(const StringView&) const;
     bool starts_with(char) const;
     bool ends_with(char) const;
+    bool matches(const StringView& mask, CaseSensitivity = CaseSensitivity::CaseInsensitive) const;
 
     StringView substring_view(size_t start, size_t length) const;
     Vector<StringView> split_view(char, bool keep_empty = false) const;
diff --git a/AK/TestSuite.h b/AK/TestSuite.h
index 67317df3c8..ec68f780de 100644
--- a/AK/TestSuite.h
+++ b/AK/TestSuite.h
@@ -182,7 +182,7 @@ NonnullRefPtrVector<TestCase> TestSuite::find_cases(const String& search, bool f
 {
     NonnullRefPtrVector<TestCase> matches;
     for (const auto& t : m_cases) {
-        if (!search.is_empty() && !t.name().matches(search, String::CaseSensitivity::CaseInsensitive)) {
+        if (!search.is_empty() && !t.name().matches(search, CaseSensitivity::CaseInsensitive)) {
             continue;
         }
 
diff --git a/AK/Tests/Makefile b/AK/Tests/Makefile
index abede6c7ba..783d92c0dd 100644
--- a/AK/Tests/Makefile
+++ b/AK/Tests/Makefile
@@ -3,6 +3,7 @@ SHARED_TEST_SOURCES = \
 	../StringImpl.cpp \
 	../StringBuilder.cpp \
 	../StringView.cpp \
+	../StringUtils.cpp \
 	../LogStream.cpp \
 	../JsonValue.cpp \
 	../JsonParser.cpp \
diff --git a/AK/Tests/TestStringUtils.cpp b/AK/Tests/TestStringUtils.cpp
new file mode 100644
index 0000000000..5162f48f74
--- /dev/null
+++ b/AK/Tests/TestStringUtils.cpp
@@ -0,0 +1,44 @@
+#include <AK/StringUtils.h>
+#include <AK/TestSuite.h>
+
+TEST_CASE(matches_null)
+{
+    EXPECT(AK::StringUtils::matches(StringView(), StringView()));
+
+    EXPECT(!AK::StringUtils::matches(StringView(), ""));
+    EXPECT(!AK::StringUtils::matches(StringView(), "*"));
+    EXPECT(!AK::StringUtils::matches(StringView(), "?"));
+    EXPECT(!AK::StringUtils::matches(StringView(), "a"));
+
+    EXPECT(!AK::StringUtils::matches("", StringView()));
+    EXPECT(!AK::StringUtils::matches("a", StringView()));
+}
+
+TEST_CASE(matches_empty)
+{
+    EXPECT(AK::StringUtils::matches("", ""));
+
+    EXPECT(AK::StringUtils::matches("", "*"));
+    EXPECT(!AK::StringUtils::matches("", "?"));
+    EXPECT(!AK::StringUtils::matches("", "a"));
+
+    EXPECT(!AK::StringUtils::matches("a", ""));
+}
+
+TEST_CASE(matches_case_sensitive)
+{
+    EXPECT(AK::StringUtils::matches("a", "a", CaseSensitivity::CaseSensitive));
+    EXPECT(!AK::StringUtils::matches("a", "A", CaseSensitivity::CaseSensitive));
+    EXPECT(!AK::StringUtils::matches("A", "a", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(matches_case_insensitive)
+{
+    EXPECT(!AK::StringUtils::matches("aa", "a"));
+    EXPECT(AK::StringUtils::matches("aa", "*"));
+    EXPECT(!AK::StringUtils::matches("cb", "?a"));
+    EXPECT(AK::StringUtils::matches("adceb", "a*b"));
+    EXPECT(!AK::StringUtils::matches("acdcb", "a*c?b"));
+}
+
+TEST_MAIN(StringUtils)