LibRegex: Add a basic optimization pass

This currently tries to convert forking loops to atomic groups, and
unify the left side of alternations.

1 files changed, 19 insertions, 0 deletions

diff --git a/Tests/LibRegex/Regex.cpp b/Tests/LibRegex/Regex.cpp
index 5203a277a0..4aeffb8da8 100644
--- a/Tests/LibRegex/Regex.cpp
+++ b/Tests/LibRegex/Regex.cpp
@@ -8,6 +8,7 @@
 #include <LibTest/TestCase.h> // import first, to prevent warning of VERIFY* redefinition
 
 #include <AK/StringBuilder.h>
+#include <AK/Tuple.h>
 #include <LibRegex/Regex.h>
 #include <LibRegex/RegexDebug.h>
 #include <stdio.h>
@@ -887,3 +888,21 @@ BENCHMARK_CASE(fork_performance)
     auto result = re.match(g_lots_of_a_s);
     EXPECT_EQ(result.success, true);
 }
+
+TEST_CASE(optimizer_atomic_groups)
+{
+    Array tests {
+        // Fork -> ForkReplace
+        Tuple { "a*b"sv, "aaaaa"sv, false },
+        Tuple { "a+b"sv, "aaaaa"sv, false },
+        // Alternative fuse
+        Tuple { "(abcfoo|abcbar|abcbaz).*x"sv, "abcbarx"sv, true },
+        Tuple { "(a|a)"sv, "a"sv, true },
+    };
+
+    for (auto& test : tests) {
+        Regex<ECMA262> re(test.get<0>());
+        auto result = re.match(test.get<1>());
+        EXPECT_EQ(result.success, test.get<2>());
+    }
+}