LibRegex: Correct the alternative matching order when one is empty

Previously we were compiling `/a|/` into what effectively would be
`/|a`, which is clearly incorrect.

2 files changed, 22 insertions, 7 deletions

diff --git a/Tests/LibRegex/Regex.cpp b/Tests/LibRegex/Regex.cpp
index 7dbf8c6d3d..6b8f5f559c 100644
--- a/Tests/LibRegex/Regex.cpp
+++ b/Tests/LibRegex/Regex.cpp
@@ -958,6 +958,21 @@ TEST_CASE(optimizer_char_class_lut)
         EXPECT_EQ(re.match("1635488940000"sv).success, false);
 }
 
+TEST_CASE(optimizer_alternation)
+{
+    Array tests {
+        // Pattern, Subject, Expected length
+        Tuple { "a|"sv, "a"sv, 1u },
+    };
+
+    for (auto& test : tests) {
+        Regex<ECMA262> re(test.get<0>());
+        auto result = re.match(test.get<1>());
+        EXPECT(result.success);
+        EXPECT_EQ(result.matches.first().view.length(), test.get<2>());
+    }
+}
+
 TEST_CASE(posix_basic_dollar_is_end_anchor)
 {
     // Ensure that a dollar sign at the end only matches the end of the line.
diff --git a/Userland/Libraries/LibRegex/RegexOptimizer.cpp b/Userland/Libraries/LibRegex/RegexOptimizer.cpp
index 969f37143c..f0d2912965 100644
--- a/Userland/Libraries/LibRegex/RegexOptimizer.cpp
+++ b/Userland/Libraries/LibRegex/RegexOptimizer.cpp
@@ -450,17 +450,17 @@ void Optimizer::append_alternation(ByteCode& target, ByteCode&& left, ByteCode&&
         if (left_is_empty && right_is_empty)
             return;
 
-        // ForkJump right (+ left.size() + 2 + right.size())
-        // (left)
-        // Jump end (+ right.size())
+        // ForkJump left (+ 2 + right.size())
         // (right)
+        // Jump end (+ left.size())
+        // (left)
         // LABEL end
         target.append(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
-        target.append(left.size() + 2 + right.size());
-        target.extend(move(left));
-        target.append(static_cast<ByteCodeValueType>(OpCodeId::Jump));
-        target.append(right.size());
+        target.append(2 + right.size());
         target.extend(move(right));
+        target.append(static_cast<ByteCodeValueType>(OpCodeId::Jump));
+        target.append(left.size());
+        target.extend(move(left));
         return;
     }