You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by su...@apache.org on 2026/07/05 07:59:01 UTC

(groovy) 01/01: GROOVY-12133: Implement matchBalanced utility to support Regex Balanced Groups

This is an automated email from the ASF dual-hosted git repository.

asf-gitbox-commits pushed a commit to branch GROOVY-12133
in repository https://gitbox.apache.org/repos/asf/groovy.git

commit e6fd0132b6e72412a911463312c97d86ae796277
Author: Daniel Sun <su...@apache.org>
AuthorDate: Sun Jul 5 16:58:45 2026 +0900

    GROOVY-12133: Implement matchBalanced utility to support Regex Balanced Groups
---
 .../org/codehaus/groovy/runtime/RegexSupport.java  | 161 ++++++++++++++++++++-
 .../groovy/runtime/StringGroovyMethods.java        |  18 +++
 src/test/groovy/groovy/GroovyMethodsTest.groovy    | 108 ++++++++++++++
 3 files changed, 282 insertions(+), 5 deletions(-)

diff --git a/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java b/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java
index 4e58158dc1..6dd332c2f6 100644
--- a/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java
+++ b/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java
@@ -18,20 +18,171 @@
  */
 package org.codehaus.groovy.runtime;
 
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.List;
+import java.util.Objects;
 import java.util.regex.Matcher;
+import java.util.regex.Pattern;
 
 /**
- * Used to store the last regex match.
+ * Provides utility methods for working with regular expressions
  */
 public class RegexSupport {
-
-    private static final ThreadLocal CURRENT_MATCHER = new ThreadLocal();
-
+    /**
+     * Returns the last regex matcher used in the current thread.
+     */
     public static Matcher getLastMatcher() {
-        return (Matcher) CURRENT_MATCHER.get();
+        return CURRENT_MATCHER.get();
     }
 
+    /**
+     * Sets the last regex matcher used in the current thread.
+     */
     public static void setLastMatcher(Matcher matcher) {
         CURRENT_MATCHER.set(matcher);
     }
+
+    /**
+     * Extracts the outermost balanced (nested) groups from the specified text using default configuration options.
+     * <p>
+     * This is a convenience overload that delegates to
+     * {@link #matchBalanced(CharSequence, String, String, MatchOptions)} using {@link MatchOptions#defaults()}.
+     * By default, no patterns are ignored, and the boundary edges (open/close tags) are included in the result.
+     * </p>
+     *
+     * @param text       the input character sequence to scan
+     * @param openRegex  the regular expression defining the opening boundary
+     * @param closeRegex the regular expression defining the closing boundary
+     * @return           an unmodifiable list containing the extracted outermost balanced groups
+     * @throws NullPointerException if {@code text}, {@code openRegex}, or {@code closeRegex} is {@code null}
+     * @see #matchBalanced(CharSequence, String, String, MatchOptions)
+     *
+     * @since 6.0.0
+     */
+    static List<String> matchBalanced(CharSequence text, String openRegex, String closeRegex) {
+        return matchBalanced(text, openRegex, closeRegex, MatchOptions.defaults());
+    }
+
+    /**
+     * Extracts the outermost balanced (nested) groups from the specified text.
+     * <p>
+     * This method provides functionality similar to the .NET (C#) Regex balancing groups
+     * (pushdown automaton), allowing for the extraction of infinitely nested structures
+     * such as matched parentheses, brackets, or HTML/XML tags.
+     * </p>
+     * <p>
+     * <b>Algorithm Details:</b> It utilizes a highly optimized, single-pass O(N)
+     * scanning algorithm with dynamic subsumption (tail-absorption). This guarantees
+     * linear time complexity and complete immunity to Catastrophic Backtracking (ReDoS).
+     * It is fully fault-tolerant and will gracefully ignore unmatched or dangling boundaries.
+     * </p>
+     * <p>
+     * <b>Important:</b> The provided {@code openRegex} and {@code closeRegex} strings
+     * must not contain named capturing groups named {@code <OPEN>}, {@code <CLOSE>},
+     * or {@code <IGNORE>}, as these are reserved for internal lexical tokenization.
+     * </p>
+     * * <pre>{@code
+     * // Example usage:
+     * String text = "Math: (A + (B * C)) and (D)";
+     * List<String> results = BalancedRegexUtils.matchBalanced(text, "\\(", "\\)", MatchOptions.defaults());
+     * // results: ["(A + (B * C))", "(D)"]
+     * }</pre>
+     *
+     * @param text       the input character sequence to scan
+     * @param openRegex  the regular expression defining the opening boundary (e.g., {@code "\\("} or {@code "<div[^>]*>"})
+     * @param closeRegex the regular expression defining the closing boundary (e.g., {@code "\\)"} or {@code "</div>"})
+     * @param options    the configuration options for the matching process (e.g., patterns to ignore, edge inclusion).
+     * If {@code null}, {@link MatchOptions#defaults()} will be used.
+     * @return           an unmodifiable list containing the extracted outermost balanced groups.
+     * Returns an empty list if no valid balanced groups are found.
+     * @throws NullPointerException if {@code text}, {@code openRegex}, or {@code closeRegex} is {@code null}
+     * @throws java.util.regex.PatternSyntaxException if the combined regex is invalid (e.g., reserved named groups are used)
+     *
+     * @since 6.0.0
+     */
+    static List<String> matchBalanced(CharSequence text, String openRegex, String closeRegex, MatchOptions options) {
+        Objects.requireNonNull(text, "text must not be null");
+        Objects.requireNonNull(openRegex, "openRegex must not be null");
+        Objects.requireNonNull(closeRegex, "closeRegex must not be null");
+        MatchOptions actualOptions = options != null ? options : MatchOptions.defaults();
+
+        StringBuilder combinedRegex = new StringBuilder();
+        if (actualOptions.ignoreRegex() != null && !actualOptions.ignoreRegex().isBlank()) {
+            combinedRegex.append("(?<IGNORE>").append(actualOptions.ignoreRegex()).append(")|");
+        }
+        combinedRegex.append("(?<OPEN>").append(openRegex).append(")|")
+            .append("(?<CLOSE>").append(closeRegex).append(")");
+
+        Matcher matcher = Pattern.compile(combinedRegex.toString()).matcher(text);
+
+        Deque<Token> openStack = new ArrayDeque<>();
+        Deque<MatchPair> mergedResults = new ArrayDeque<>();
+
+        while (matcher.find()) {
+            if (actualOptions.ignoreRegex() != null && matcher.group("IGNORE") != null) {
+                continue;
+            }
+
+            if (matcher.group("OPEN") != null) {
+                openStack.push(new Token(matcher.start(), matcher.end()));
+            } else if (matcher.group("CLOSE") != null) {
+                if (!openStack.isEmpty()) {
+                    Token openToken = openStack.pop();
+                    MatchPair newPair = new MatchPair(openToken, new Token(matcher.start(), matcher.end()));
+                    while (!mergedResults.isEmpty() && mergedResults.peekLast().open().start() > newPair.open().start()) {
+                        mergedResults.pollLast();
+                    }
+
+                    mergedResults.addLast(newPair);
+                }
+            }
+        }
+
+        List<String> results = new ArrayList<>(mergedResults.size());
+        for (MatchPair pair : mergedResults) {
+            int startIdx = actualOptions.includeEdges() ? pair.open().start() : pair.open().end();
+            int endIdx = actualOptions.includeEdges() ? pair.close().end() : pair.close().start();
+
+            if (startIdx <= endIdx) {
+                results.add(text.subSequence(startIdx, endIdx).toString());
+            }
+        }
+
+        return Collections.unmodifiableList(results);
+    }
+
+    /**
+     * Options for configuring the behavior of the balanced matching process.
+     * @param ignoreRegex  A regular expression pattern to ignore certain matches during the scanning process.
+     * @param includeEdges A boolean flag indicating whether to include the opening and closing boundaries in the final matched results.
+     * @since 6.0.0
+     */
+    public record MatchOptions(String ignoreRegex, boolean includeEdges) {
+        public static MatchOptions defaults() {
+            return new MatchOptions(null, true);
+        }
+        public MatchOptions withIgnoreRegex(String ignoreRegex) {
+            return new MatchOptions(ignoreRegex, this.includeEdges);
+        }
+        public MatchOptions withIncludeEdges(boolean includeEdges) {
+            return new MatchOptions(this.ignoreRegex, includeEdges);
+        }
+    }
+
+    /**
+     * Represents a token with a start and end index in the input text.
+     * @since 6.0.0
+     */
+    private record Token(int start, int end) {}
+
+    /**
+     * Represents a matched pair of opening and closing tokens.
+     * @since 6.0.0
+     */
+    private record MatchPair(Token open, Token close) {}
+
+    private static final ThreadLocal<Matcher> CURRENT_MATCHER = new ThreadLocal<>();
 }
diff --git a/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java b/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java
index b50f3e631e..d45b72e46c 100644
--- a/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java
+++ b/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java
@@ -4342,4 +4342,22 @@ public class StringGroovyMethods extends DefaultGroovyMethodsSupport {
 
         return self.toString().toLowerCase(Locale.ROOT).contains(searchString.toString().toLowerCase(Locale.ROOT));
     }
+
+    /**
+     * @see RegexSupport#matchBalanced(CharSequence, String, String)
+     *
+     * @since 6.0.0
+     */
+    public static List<String> matchBalanced(CharSequence text, String openRegex, String closeRegex) {
+        return RegexSupport.matchBalanced(text, openRegex, closeRegex);
+    }
+
+    /**
+     * @see RegexSupport#matchBalanced(CharSequence, String, String, RegexSupport.MatchOptions)
+     *
+     * @since 6.0.0
+     */
+    public static List<String> matchBalanced(CharSequence text, String openRegex, String closeRegex, RegexSupport.MatchOptions options) {
+        return RegexSupport.matchBalanced(text, openRegex, closeRegex, options);
+    }
 }
diff --git a/src/test/groovy/groovy/GroovyMethodsTest.groovy b/src/test/groovy/groovy/GroovyMethodsTest.groovy
index 609a19155f..172c41c9ed 100644
--- a/src/test/groovy/groovy/GroovyMethodsTest.groovy
+++ b/src/test/groovy/groovy/GroovyMethodsTest.groovy
@@ -18,6 +18,8 @@
  */
 package groovy
 
+import org.codehaus.groovy.runtime.RegexSupport
+import org.codehaus.groovy.runtime.StringGroovyMethods
 import org.codehaus.groovy.util.StringUtil
 import org.junit.jupiter.api.Test
 
@@ -27,6 +29,8 @@ import java.util.concurrent.LinkedBlockingQueue
 
 import static groovy.test.GroovyAssert.shouldFail
 import static org.junit.jupiter.api.Assertions.assertEquals
+import static org.junit.jupiter.api.Assertions.assertThrows
+import static org.junit.jupiter.api.Assertions.assertTrue
 import static org.junit.jupiter.api.Assumptions.assumeFalse
 
 /**
@@ -2586,6 +2590,110 @@ final class GroovyMethodsTest {
             }
         }
     }
+
+    // GROOVY-12133
+    @Test
+    void should_ThrowException_When_NullArgumentsPassed() {
+        assertThrows(NullPointerException.class, () -> StringGroovyMethods.matchBalanced(null, "\\(", "\\)"));
+        assertThrows(NullPointerException.class, () -> StringGroovyMethods.matchBalanced("test", null, "\\)"));
+        assertThrows(NullPointerException.class, () -> StringGroovyMethods.matchBalanced("test", "\\(", null));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_ReturnEmptyList_When_NoMatchFound() {
+        List<String> results = StringGroovyMethods.matchBalanced("Plain text", "\\(", "\\)");
+        assertTrue(results.isEmpty());
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_MatchSingleGroups_When_ValidStructure() {
+        String input = "(A) and (B)";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)");
+        assertEquals(2, results.size());
+        assertEquals("(A)", results.get(0));
+        assertEquals("(B)", results.get(1));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_AbsorbInnerGroups_When_PerfectlyNested() {
+        String input = "Outer: ((A)(B))";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)");
+        assertEquals(1, results.size());
+        assertEquals("((A)(B))", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_HandleLeftDanglingBracket_When_UnmatchedOpenExists() {
+        String input = "(A(B)";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)");
+        assertEquals(1, results.size());
+        assertEquals("(B)", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_HandleRightDanglingBracket_When_UnmatchedCloseExists() {
+        String input = "A)B(C)D)";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)");
+        assertEquals(1, results.size());
+        assertEquals("(C)", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_HandleComplexChaoticNesting() {
+        String input = "(a (b (c) ) d (e (f) g";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)");
+        assertEquals(2, results.size());
+        assertEquals("(b (c) )", results.get(0));
+        assertEquals("(f)", results.get(1));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_StripEdges_When_IncludeEdgesIsFalse() {
+        String input = "func(arg1, arg2)";
+        RegexSupport.MatchOptions options = RegexSupport.MatchOptions.defaults().withIncludeEdges(false);
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)", options);
+        assertEquals(1, results.size());
+        assertEquals("arg1, arg2", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_HandleEmptyInnerContent_When_IncludeEdgesIsFalse() {
+        String input = "Empty: ()";
+        RegexSupport.MatchOptions options = RegexSupport.MatchOptions.defaults().withIncludeEdges(false);
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\(", "\\)", options);
+        assertEquals(1, results.size());
+        assertEquals("", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_IgnoreConfiguredPatterns_When_IgnoreRegexIsSet() {
+        String code = "if (true) { print(\"}\"); }";
+        // 忽略双引号内的字符串
+        RegexSupport.MatchOptions options = RegexSupport.MatchOptions.defaults()
+            .withIgnoreRegex("\"(?:\\\\.|[^\"\\\\])*\"");
+
+        List<String> results = StringGroovyMethods.matchBalanced(code, "\\{", "\\}", options);
+        assertEquals(1, results.size());
+        assertEquals("{ print(\"}\"); }", results.get(0));
+    }
+
+    // GROOVY-12133
+    @Test
+    void should_UseOptionsFromMethodOverload_When_OptionsNotProvided() {
+        String input = "[val]";
+        List<String> results = StringGroovyMethods.matchBalanced(input, "\\[", "\\]");
+        assertEquals(1, results.size());
+        assertEquals("[val]", results.get(0));
+    }
 }
 
 //---------------------------------------------------------------------------