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));
+ }
}
//---------------------------------------------------------------------------