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 a71e19e2327d888865a77fa13a62a85b348afe4f Author: Daniel Sun <[email protected]> AuthorDate: Sun Jul 5 16:58:45 2026 +0900 GROOVY-12133: Implement findBalanced utility to support Regex Balanced Groups --- src/main/java/groovy/util/regex/BalancedGroup.java | 113 +++++++++ .../org/codehaus/groovy/runtime/RegexSupport.java | 165 ++++++++++++- .../groovy/runtime/StringGroovyMethods.java | 19 ++ src/test/groovy/bugs/Groovy12133.groovy | 269 +++++++++++++++++++++ 4 files changed, 561 insertions(+), 5 deletions(-) diff --git a/src/main/java/groovy/util/regex/BalancedGroup.java b/src/main/java/groovy/util/regex/BalancedGroup.java new file mode 100644 index 0000000000..bac83cdc5b --- /dev/null +++ b/src/main/java/groovy/util/regex/BalancedGroup.java @@ -0,0 +1,113 @@ +package groovy.util.regex; + +import java.util.Collections; +import java.util.List; + +/** + * Represents a node within the Abstract Syntax Tree (AST) generated by the balanced regex parser. + * Each node corresponds to a successfully paired inner or outer matched group. + * + * @since 6.0.0 + */ +public final class BalancedGroup { + private final String matchedString; + private final List<BalancedGroup> children; + private BalancedGroup parent; // Node linkage: points to the parent node, or null if it is a root node. + + /** + * Constructs a new {@code BalancedGroup} instance with the specified matched string and child nodes. + * @param matchedString the raw string content captured by this balanced group, potentially including boundary tags depending on {@link MatchOptions} + * @param children the list of child {@code BalancedGroup} nodes nested within this group. Can be null or empty for leaf nodes. + */ + public BalancedGroup(String matchedString, List<BalancedGroup> children) { + this.matchedString = matchedString; + this.children = children == null || children.isEmpty() ? Collections.emptyList() : List.copyOf(children); + } + + /** + * Retrieves the raw string content captured by this balanced group. + * + * @return the captured string, potentially stripped of its boundaries depending on {@link MatchOptions} + */ + public String getMatchedString() { + return matchedString; + } + + /** + * Retrieves the inner balanced groups deeply nested within this current group. + * + * @return an unmodifiable list of child nodes. Returns an empty list (never null) if this is a leaf node. + */ + public List<BalancedGroup> getChildren() { + return children; + } + + /** + * Retrieves the parent group that encapsulates this current group. + * + * @return the parent {@code BalancedGroup}, or {@code null} if this is an outermost (root) node. + */ + public BalancedGroup getParent() { + return parent; + } + + /** + * setter for establishing bidirectional tree links during construction. + * + * @param parent the parent {@code BalancedGroup} to be set for this node. Can be {@code null} if this is a root node. + */ + public void setParent(BalancedGroup parent) { + this.parent = parent; + } + + /** + * Returns a string representation of this balanced group, which is the matched string content. + */ + @Override + public String toString() { + return matchedString; + } + + /** + * Configuration options for the balanced regex matching process. + * Implemented as an immutable record using the Wither pattern for thread-safe configurations. + * + * @param ignoreRegex a regular expression defining patterns to be strictly ignored during + * lexical tokenization (e.g., escaped boundaries or string literals). + * @param includeEdges {@code true} to include the opening and closing boundary tags in the + * extracted results; {@code false} to strip them. + * + * @since 6.0.0 + */ + public record MatchOptions(String ignoreRegex, boolean includeEdges) { + + /** + * Returns the default matching options: no patterns are ignored, and boundary edges are included. + * + * @return the default {@code MatchOptions} + */ + public static MatchOptions defaults() { + return new MatchOptions(null, true); + } + + /** + * Creates a new {@code MatchOptions} instance with the specified ignore regex. + * + * @param ignoreRegex the regular expression of the content to ignore + * @return a new {@code MatchOptions} instance + */ + public MatchOptions withIgnoreRegex(String ignoreRegex) { + return new MatchOptions(ignoreRegex, this.includeEdges); + } + + /** + * Creates a new {@code MatchOptions} instance with the specified edge inclusion policy. + * + * @param includeEdges whether to include the boundary tags + * @return a new {@code MatchOptions} instance + */ + public MatchOptions withIncludeEdges(boolean includeEdges) { + return new MatchOptions(this.ignoreRegex, includeEdges); + } + } +} diff --git a/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java b/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java index 4e58158dc1..24882a2a87 100644 --- a/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java +++ b/src/main/java/org/codehaus/groovy/runtime/RegexSupport.java @@ -18,20 +18,175 @@ */ package org.codehaus.groovy.runtime; +import groovy.util.regex.BalancedGroup; +import groovy.util.regex.BalancedGroup.MatchOptions; + +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); } + + /** + * Finds and extracts balanced (nested) groups from the specified text using default matching options. + * <p> + * This convenience overload invokes {@link #findBalanced(CharSequence, String, String, MatchOptions)} + * using {@link MatchOptions#defaults()}, meaning no content is ignored and boundary edges are preserved. + * </p> + * + * @param self the input character sequence to parse + * @param openRegex the regular expression defining the opening boundary + * @param closeRegex the regular expression defining the closing boundary + * @return an unmodifiable list containing the outermost root nodes of the extracted AST + * @throws NullPointerException if {@code self}, {@code openRegex}, or {@code closeRegex} is {@code null} + * @see #findBalanced(CharSequence, String, String, MatchOptions) + * + * @since 6.0.0 + */ + static List<BalancedGroup> findBalanced(CharSequence self, String openRegex, String closeRegex) { + return findBalanced(self, openRegex, closeRegex, MatchOptions.defaults()); + } + + /** + * Finds and extracts balanced (nested) groups from the specified text, constructing a hierarchical + * Abstract Syntax Tree (AST) of the results. + * <p> + * <b>Algorithm Overview:</b> + * This method employs a highly optimized, single-pass $O(N)$ scanning algorithm using a virtual-root + * stack tracker. It effectively mimics C# Regex balancing groups while eliminating the risk of + * Catastrophic Backtracking (ReDoS). + * </p> + * <p> + * <b>Fault Tolerance:</b> + * The parser is highly resilient. It will gracefully discard unmatched closing tags and perform an + * "orphan rescue" to salvage valid nested structures trapped inside unclosed opening tags. + * </p> + * <p> + * <b>Important:</b> The provided {@code openRegex} and {@code closeRegex} must not define named + * capturing groups called {@code <OPEN>}, {@code <CLOSE>}, or {@code <IGNORE>}, as these are reserved + * for internal lexical tokenization. + * </p> + * + * @param self the input character sequence to parse + * @param openRegex the regular expression defining the opening boundary (e.g., {@code "\\("}) + * @param closeRegex the regular expression defining the closing boundary (e.g., {@code "\\)"}) + * @param options the configuration options for the parsing process. If {@code null}, + * {@link MatchOptions#defaults()} will be applied. + * @return an unmodifiable list containing the outermost root nodes of the extracted AST. + * Returns an empty list if no valid balanced groups are found. + * @throws NullPointerException if {@code self}, {@code openRegex}, or {@code closeRegex} is {@code null} + * + * @since 6.0.0 + */ + static List<BalancedGroup> findBalanced(CharSequence self, String openRegex, String closeRegex, MatchOptions options) { + Objects.requireNonNull(self, "self 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(); + + boolean hasIgnoreRule = actualOptions.ignoreRegex() != null && !actualOptions.ignoreRegex().isBlank(); + + StringBuilder combinedRegex = new StringBuilder(); + if (hasIgnoreRule) { + 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(self); + + // A Deque is utilized as a Pushdown Automaton stack. + // We initialize it with a 'Virtual SuperRoot' (-1, -1) to radically simplify the mounting + // of top-level root nodes and eliminate complex empty-stack checks. + Deque<PendingGroup> stack = new ArrayDeque<>(); + stack.push(new PendingGroup(-1, -1)); + + while (matcher.find()) { + // Bypass explicitly ignored patterns (e.g., literals or escape sequences) + if (hasIgnoreRule && matcher.group("IGNORE") != null) { + continue; + } + + if (matcher.group("OPEN") != null) { + // Left boundary encountered: push a new pending frame onto the stack + stack.push(new PendingGroup(matcher.start(), matcher.end())); + } else if (matcher.group("CLOSE") != null) { + // Right boundary encountered: pop and finalize if there's a valid open frame + // (stack size > 1 ensures we never pop the Virtual SuperRoot) + if (stack.size() > 1) { + PendingGroup openGroup = stack.pop(); + + int startIdx = actualOptions.includeEdges() ? openGroup.openStart : openGroup.openEnd; + int endIdx = actualOptions.includeEdges() ? matcher.end() : matcher.start(); + + // Edge case prevention: if stripping edges results in negative length, return empty string + String matchStr = startIdx <= endIdx ? self.subSequence(startIdx, endIdx).toString() : ""; + + // Instantiate the finalized AST node + BalancedGroup completedNode = new BalancedGroup(matchStr, openGroup.completedChildren); + + // Establish bidirectional tree linkage for all its children + for (BalancedGroup child : openGroup.completedChildren) { + child.setParent(completedNode); + } + + // Mount the newly completed node onto the pending children list of its immediate parent + stack.peek().completedChildren.add(completedNode); + } + } + } + + // Orphan Rescue Mechanism (Fault Tolerance): + // If the stack contains more than the SuperRoot after scanning, dangling open tags exist. + // We systematically bubble up any successfully completed child nodes trapped inside these + // invalid pending groups, salvaging valid subtrees up to the SuperRoot. + while (stack.size() > 1) { + PendingGroup dangling = stack.pop(); + stack.peek().completedChildren.addAll(dangling.completedChildren); + } + + // The SuperRoot's children collection now strictly contains all valid outermost root nodes. + return Collections.unmodifiableList(stack.peek().completedChildren); + } + + + /** + * Internal data structure used to track the state of unclosed groups during the single-pass scan. + * + * @since 6.0.0 + */ + private static final class PendingGroup { + final int openStart; + final int openEnd; + final List<BalancedGroup> completedChildren = new ArrayList<>(); + + PendingGroup(int openStart, int openEnd) { + this.openStart = openStart; + this.openEnd = openEnd; + } + } + + + 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 2d7f8248ae..58d026b010 100644 --- a/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java +++ b/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java @@ -26,6 +26,7 @@ import groovy.lang.Range; import groovy.transform.stc.ClosureParams; import groovy.transform.stc.FromString; import groovy.transform.stc.PickFirstResolver; +import groovy.util.regex.BalancedGroup; import org.apache.groovy.io.StringBuilderWriter; import org.apache.groovy.lang.annotation.Incubating; import org.codehaus.groovy.runtime.typehandling.DefaultTypeTransformation; @@ -4447,4 +4448,22 @@ public class StringGroovyMethods extends DefaultGroovyMethodsSupport { return self.toString().toLowerCase(Locale.ROOT).contains(searchString.toString().toLowerCase(Locale.ROOT)); } + + /** + * @see RegexSupport#findBalanced(CharSequence, String, String) + * + * @since 6.0.0 + */ + public static List<BalancedGroup> findBalanced(CharSequence self, String openRegex, String closeRegex) { + return RegexSupport.findBalanced(self, openRegex, closeRegex); + } + + /** + * @see RegexSupport#findBalanced(CharSequence, String, String, BalancedGroup.MatchOptions) + * + * @since 6.0.0 + */ + public static List<BalancedGroup> findBalanced(CharSequence self, String openRegex, String closeRegex, BalancedGroup.MatchOptions options) { + return RegexSupport.findBalanced(self, openRegex, closeRegex, options); + } } diff --git a/src/test/groovy/bugs/Groovy12133.groovy b/src/test/groovy/bugs/Groovy12133.groovy new file mode 100644 index 0000000000..26f6fa9367 --- /dev/null +++ b/src/test/groovy/bugs/Groovy12133.groovy @@ -0,0 +1,269 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package bugs + +import groovy.util.regex.BalancedGroup +import org.codehaus.groovy.runtime.StringGroovyMethods +import org.junit.jupiter.api.Test + +import static org.junit.jupiter.api.Assertions.assertEquals +import static org.junit.jupiter.api.Assertions.assertNull +import static org.junit.jupiter.api.Assertions.assertSame +import static org.junit.jupiter.api.Assertions.assertThrows +import static org.junit.jupiter.api.Assertions.assertTrue + +final class Groovy12133 { + @Test + void should_ThrowException_When_NullArgumentsPassed() { + assertThrows(NullPointerException.class, () -> StringGroovyMethods.findBalanced(null, "\\(", "\\)")) + assertThrows(NullPointerException.class, () -> StringGroovyMethods.findBalanced("test", null, "\\)")) + assertThrows(NullPointerException.class, () -> StringGroovyMethods.findBalanced("test", "\\(", null)) + } + + @Test + void should_ReturnEmptyList_When_NoMatchFound() { + List<BalancedGroup> results = "plain text".findBalanced("\\(", "\\)") + assertTrue(results.isEmpty()) + } + + @Test + void should_BuildCompleteTree_When_PerfectlyNested() { + String input = "Root: (A + (B * C) + (D(E)))" + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)") + + assertEquals(1, roots.size()) + + BalancedGroup root = roots.get(0) + assertEquals("(A + (B * C) + (D(E)))", root.getMatchedString()) + assertNull(root.getParent()) + assertEquals(2, root.getChildren().size()) + + BalancedGroup nodeB = root.getChildren().get(0) + assertEquals("(B * C)", nodeB.getMatchedString()) + assertSame(root, nodeB.getParent()) + + BalancedGroup nodeD = root.getChildren().get(1) + assertEquals("(D(E))", nodeD.getMatchedString()) + assertSame(root, nodeD.getParent()) + + BalancedGroup nodeE = nodeD.getChildren().get(0) + assertEquals("(E)", nodeE.getMatchedString()) + assertSame(nodeD, nodeE.getParent()) + } + + @Test + void should_ReturnImmutableEmptyListForChildren_When_NodeIsLeaf() { + String input = "Leaf: ()" + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)") + + BalancedGroup leaf = roots.get(0) + + assertTrue(leaf.getChildren().isEmpty()) + assertThrows(UnsupportedOperationException.class, () -> leaf.getChildren().add(null)) + } + + @Test + void should_RescueValidChildren_When_DanglingOpenExists() { + String input = "(A (B) (C(D)" + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)") + + assertEquals(2, roots.size()) + assertEquals("(B)", roots.get(0).getMatchedString()) + assertEquals("(D)", roots.get(1).getMatchedString()) + + assertNull(roots.get(0).getParent()) + } + + @Test + void should_IgnoreDanglingClose_When_NoOpenExists() { + String input = "A ) B (C) D )" + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)") + + assertEquals(1, roots.size()) + assertEquals("(C)", roots.get(0).getMatchedString()) + } + + @Test + void should_StripEdges_When_IncludeEdgesIsFalse() { + String input = "func(arg1, arg2)" + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)", options) + + assertEquals(1, roots.size()) + assertEquals("arg1, arg2", roots.get(0).getMatchedString()) + } + + @Test + void should_HandleEmptyStringCorrectly_When_IncludeEdgesIsFalseAndContentIsEmpty() { + String input = "Empty: ()" + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)", options) + + assertEquals(1, roots.size()) + assertEquals("", roots.get(0).getMatchedString()) + } + + @Test + void should_IgnoreConfiguredPatterns_When_IgnoreRegexIsSet() { + String code = "if(true) { String s = \"}\"; }" + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex("\"(?:\\\\.|[^\"\\\\])*\"") + + List<BalancedGroup> roots = code.findBalanced("\\{", "\\}", options) + + assertEquals(1, roots.size()) + assertEquals("{ String s = \"}\"; }", roots.get(0).getMatchedString()) + } + + @Test + void should_HandleBlankIgnoreRegex_Gracefully() { + String input = "(Test)" + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults().withIgnoreRegex(" ") + List<BalancedGroup> roots = input.findBalanced("\\(", "\\)", options) + assertEquals("(Test)", roots.get(0).getMatchedString()) + } + + @Test + void should_UseOptionsFromMethodOverload_When_OptionsNotProvided() { + List<BalancedGroup> roots = "(A)".findBalanced("\\(", "\\)", null) + assertEquals("(A)", roots.get(0).getMatchedString()) + + List<BalancedGroup> rootsOverload = "[B]".findBalanced("\\[", "\\]") + assertEquals("[B]", rootsOverload.get(0).getMatchedString()) + } + + @Test + void should_ExtractNestedHtmlDivs_When_TagsContainAttributes() { + String html = """ + <div id="app" class="container"> + <div class="header" style="color: red;">Header</div> + <div class="body"> + <div class="content">Content</div> + </div> + </div> + <div id="footer">Footer</div> + """ + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>") + + assertEquals(2, roots.size(), "Should find two top-level div roots") + + BalancedGroup appDiv = roots.get(0) + assertTrue(appDiv.getMatchedString().startsWith("<div id=\"app\"")) + assertEquals(2, appDiv.getChildren().size()) + + assertEquals("<div class=\"header\" style=\"color: red;\">Header</div>", + appDiv.getChildren().get(0).getMatchedString()) + + BalancedGroup bodyDiv = appDiv.getChildren().get(1) + assertEquals(1, bodyDiv.getChildren().size()) + assertEquals("<div class=\"content\">Content</div>", + bodyDiv.getChildren().get(0).getMatchedString()) + } + + @Test + void should_ExtractInnerHTML_When_IncludeEdgesIsFalse() { + String html = "<div class=\"wrapper\">\n <p>Hello World</p>\n</div>" + + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults() + .withIncludeEdges(false) + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>", options) + + assertEquals(1, roots.size()) + assertEquals("\n <p>Hello World</p>\n", roots.get(0).getMatchedString()) + } + + @Test + void should_IgnoreHtmlComments_When_IgnoreRegexIsConfigured() { + String html = """ + <div id="main"> + <div class="real">Valid Content</div> + </div> + """ + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>") + + assertEquals(1, roots.size(), "AST should contain exactly 1 root block") + + BalancedGroup mainDiv = roots.get(0) + assertTrue(mainDiv.getMatchedString().contains("Valid Content")) + + List<BalancedGroup> children = mainDiv.getChildren() + assertEquals(1, children.size()) + assertEquals("<div class=\"real\">Valid Content</div>", children.get(0).getMatchedString()) + } + + @Test + void should_IgnoreScriptBlocks_When_JavascriptContainsFakeTags() { + String html = """ + <div id="react-root"> + <script type="text/javascript"> + const fakeHtml = "</div>"; + </script> + <div class="app">App Ready</div> + </div> + """ + + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex("(?s)<script\\b[^>]*>.*?</script>") + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>", options) + + assertEquals(1, roots.size()) + assertEquals(1, roots.get(0).getChildren().size()) + assertEquals("<div class=\"app\">App Ready</div>", + roots.get(0).getChildren().get(0).getMatchedString()) + } + + @Test + void should_BypassSelfClosingTags_When_AddedToIgnoreRegex() { + String html = """ + <div id="parent"> + <div class="placeholder" /> <div class="child">I am child</div> + </div> + """ + + BalancedGroup.MatchOptions options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex("<div\\b[^>]*/>") + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>", options) + + assertEquals(1, roots.size()) + + List<BalancedGroup> children = roots.get(0).getChildren() + assertEquals(1, children.size()) + assertEquals("<div class=\"child\">I am child</div>", children.get(0).getMatchedString()) + } + + @Test + void should_RescueValidInnerHtml_When_OuterHtmlIsMalformed() { + String html = """ + <div class="broken-wrapper"> + <div class="lost-tag"> <div class="target">I am safe!</div> + """ + + List<BalancedGroup> roots = html.findBalanced("<div\\b[^>]*>", "</div>") + + assertEquals(1, roots.size()) + assertEquals("<div class=\"target\">I am safe!</div>", roots.get(0).getMatchedString()) + } +}
