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 4ed84504d6de3b24fcc1b5f0f5c11358f0aad944 Author: Daniel Sun <[email protected]> AuthorDate: Sun Jul 5 16:58:45 2026 +0900 GROOVY-12133: Implement findBalancedGroups utility to support Regex Balanced Groups --- src/main/java/groovy/util/regex/BalancedGroup.java | 488 ++++++++++++++++ .../groovy/runtime/StringGroovyMethods.java | 93 ++++ src/test/groovy/bugs/Groovy12133.groovy | 615 +++++++++++++++++++++ 3 files changed, 1196 insertions(+) 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..772c807061 --- /dev/null +++ b/src/main/java/groovy/util/regex/BalancedGroup.java @@ -0,0 +1,488 @@ +/* + * 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 groovy.util.regex; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Deque; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +/** + * A node in the tree of balanced groups extracted by {@link #find}, + * also exposed on {@link CharSequence} via + * {@link org.codehaus.groovy.runtime.StringGroovyMethods#findBalancedGroups(CharSequence, String, String)}. + * <p> + * Java's {@link Pattern} has no .NET-style balancing groups + * ({@code (?<name1-name2>…)}). This type is both the structured result and the + * entry point for Groovy's stack-based equivalent: each node is one successfully + * closed span, with immediately nested spans as children (richer than .NET's flat + * {@code CaptureCollection} on a single group). + * </p> + * <p> + * Offsets mirror .NET {@code Capture.Index} / {@code Length}: {@link #getStart()} + * and {@link #getEnd()} describe the range of {@link #getMatchedString()} in the + * original input (half-open {@code [start, end)}). {@link #getFullStart()} / + * {@link #getFullEnd()} always cover the complete pair including delimiters, + * even when {@link MatchOptions#includeEdges()} is {@code false} (comparable to + * knowing both the balancing capture and the open/close match positions). + * </p> + * <p> + * Parent links are set when a node is constructed as a child of another node; + * root nodes have a {@code null} parent. + * </p> + * + * @since 6.0.0 + */ +public final class BalancedGroup { + + /** + * Bounded LRU cache for compiled tokenizer patterns. Hot call sites often + * reuse the same open/close/ignore triple; recompiling those on every call + * dominates cost for short inputs. + */ + private static final int TOKENIZER_CACHE_LIMIT = 64; + + private static final Map<String, Pattern> TOKENIZER_CACHE = + new LinkedHashMap<>(TOKENIZER_CACHE_LIMIT, 0.75f, true) { + @Override + protected boolean removeEldestEntry(Map.Entry<String, Pattern> eldest) { + return size() > TOKENIZER_CACHE_LIMIT; + } + }; + + private final String matchedString; + private final int start; + private final int end; + private final int fullStart; + private final int fullEnd; + private final List<BalancedGroup> children; + private BalancedGroup parent; + + /** + * Constructs a node with the given matched text and children. + * Offsets are treated as relative to {@code matchedString} + * ({@code start = 0}, {@code end = matchedString.length()}, and the same + * for the full span). Prefer + * {@link #BalancedGroup(String, int, int, int, int, List)} when absolute + * indices in a source string are known. + * + * @param matchedString the text captured for this group (never {@code null}) + * @param children immediate nested groups, or {@code null}/empty for a leaf + * @throws NullPointerException if {@code matchedString} is {@code null}, or + * {@code children} contains {@code null} + * @throws IllegalArgumentException if any child already has a parent + */ + public BalancedGroup(String matchedString, List<BalancedGroup> children) { + this(matchedString, 0, lengthOf(matchedString), 0, lengthOf(matchedString), children); + } + + /** + * Constructs a node with matched text, absolute source offsets, and children. + * + * @param matchedString the text captured for this group (never {@code null}); + * may include or exclude boundary delimiters depending on + * {@link MatchOptions#includeEdges()} + * @param start start index of {@code matchedString} in the source (inclusive) + * @param end end index of {@code matchedString} in the source (exclusive) + * @param fullStart start index of the full pair including open delimiter + * @param fullEnd end index of the full pair including close delimiter (exclusive) + * @param children immediate nested groups, or {@code null}/empty for a leaf + * @throws NullPointerException if {@code matchedString} is {@code null}, or + * {@code children} contains {@code null} + * @throws IllegalArgumentException if ranges are invalid or a child already has a parent + */ + public BalancedGroup(String matchedString, int start, int end, int fullStart, int fullEnd, + List<BalancedGroup> children) { + this.matchedString = Objects.requireNonNull(matchedString, "matchedString"); + if (start < 0 || end < start) { + throw new IllegalArgumentException("invalid match range: [" + start + ", " + end + ")"); + } + if (fullStart < 0 || fullEnd < fullStart) { + throw new IllegalArgumentException("invalid full range: [" + fullStart + ", " + fullEnd + ")"); + } + if (end - start != matchedString.length()) { + throw new IllegalArgumentException( + "matchedString length " + matchedString.length() + " != range length " + (end - start)); + } + this.start = start; + this.end = end; + this.fullStart = fullStart; + this.fullEnd = fullEnd; + if (children == null || children.isEmpty()) { + this.children = List.of(); + } else { + this.children = List.copyOf(children); + for (BalancedGroup child : this.children) { + if (child.parent != null) { + throw new IllegalArgumentException("child BalancedGroup already has a parent"); + } + child.parent = this; + } + } + } + + private static int lengthOf(String s) { + return s == null ? 0 : s.length(); + } + + /** + * Finds balanced groups using {@link MatchOptions#defaults()}. + * + * @param text text to scan + * @param openRegex regex for an opening delimiter (must not be empty) + * @param closeRegex regex for a closing delimiter (must not be empty) + * @return unmodifiable list of outermost groups (empty if none) + * @see #find(CharSequence, String, String, MatchOptions) + * @since 6.0.0 + */ + public static List<BalancedGroup> find(CharSequence text, String openRegex, String closeRegex) { + return find(text, openRegex, closeRegex, MatchOptions.defaults()); + } + + /** + * Finds balanced (nested) groups in {@code text} and returns them as a forest of + * {@link BalancedGroup} nodes. + * <p> + * <b>Relation to .NET balancing groups:</b> .NET keeps a capture stack per + * named group, pushes with {@code (?<Open>…)}, pops with + * {@code (?<-Open>…)} or {@code (?<Between-Open>…)}, and can require a + * fully empty stack via {@code (?(Open)(?!))}. This method uses the same + * push/pop idea on an explicit stack, but returns a hierarchical tree + * (children + parent) rather than a flat {@code CaptureCollection}, and + * always extracts every completed span in one left-to-right scan. + * </p> + * <p> + * <b>Algorithm:</b> matches of a combined tokenizer + * ({@code IGNORE}? / {@code OPEN} / {@code CLOSE}) are consumed in order. + * Nesting is resolved by the stack, not by recursive regex, so balancing + * itself does not introduce ReDoS; cost is proportional to the number of + * tokenizer hits times the cost of the user-supplied patterns. Compiled + * tokenizers are cached (bounded LRU). + * </p> + * <p> + * <b>Fault tolerance</b> (differs from a strict .NET + * {@code (?(Open)(?!))} pattern): unmatched closers are ignored; unclosed + * openers are dropped at end-of-input, but groups already completed inside + * them are promoted outward ("orphan rescue"). + * </p> + * <p> + * Named capturing groups {@code OPEN}, {@code CLOSE}, and {@code IGNORE} are + * reserved for the tokenizer; do not use those names inside + * {@code openRegex}, {@code closeRegex}, or {@link MatchOptions#ignoreRegex()}. + * </p> + * + * @param text text to scan + * @param openRegex regex for an opening delimiter (must not be empty) + * @param closeRegex regex for a closing delimiter (must not be empty) + * @param options match options; {@code null} means {@link MatchOptions#defaults()} + * @return unmodifiable list of outermost groups (empty if none) + * @throws NullPointerException if {@code text}, {@code openRegex}, or {@code closeRegex} is {@code null} + * @throws IllegalArgumentException if {@code openRegex} or {@code closeRegex} is empty + * @throws java.util.regex.PatternSyntaxException if a supplied pattern is not a valid Java regex + * @since 6.0.0 + */ + public static List<BalancedGroup> find(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"); + if (openRegex.isEmpty()) { + throw new IllegalArgumentException("openRegex must not be empty"); + } + if (closeRegex.isEmpty()) { + throw new IllegalArgumentException("closeRegex must not be empty"); + } + + MatchOptions actualOptions = options != null ? options : MatchOptions.defaults(); + String ignoreRegex = actualOptions.ignoreRegex(); + boolean hasIgnoreRule = ignoreRegex != null && !ignoreRegex.isBlank(); + boolean includeEdges = actualOptions.includeEdges(); + + // Single String source: Matcher indices and substring share the same coordinate space; + // avoids repeated CharSequence.subSequence materialization for non-String inputs. + final String source = text instanceof String ? (String) text : text.toString(); + + Matcher matcher = tokenizer(openRegex, closeRegex, hasIgnoreRule ? ignoreRegex : null).matcher(source); + + // Virtual super-root so top-level groups need no empty-stack special case. + Deque<PendingGroup> stack = new ArrayDeque<>(); + stack.push(new PendingGroup(-1, -1)); + + while (matcher.find()) { + if (hasIgnoreRule && matcher.start("IGNORE") >= 0) { + continue; + } + + if (matcher.start("OPEN") >= 0) { + stack.push(new PendingGroup(matcher.start(), matcher.end())); + } else if (matcher.start("CLOSE") >= 0 && stack.size() > 1) { + PendingGroup openGroup = stack.pop(); + int openStart = openGroup.openStart; + int openEnd = openGroup.openEnd; + int closeStart = matcher.start(); + int closeEnd = matcher.end(); + + int matchStart = includeEdges ? openStart : openEnd; + int matchEnd = includeEdges ? closeEnd : closeStart; + // Pathological open/close patterns can invert the interior range. + if (matchStart > matchEnd) { + matchStart = matchEnd; + } + String matchStr = source.substring(matchStart, matchEnd); + + // Constructor wires child → parent links. + BalancedGroup completedNode = new BalancedGroup( + matchStr, matchStart, matchEnd, openStart, closeEnd, openGroup.children()); + stack.peek().addChild(completedNode); + } + } + + // Promote completed children out of any still-open (dangling) frames. + while (stack.size() > 1) { + PendingGroup dangling = stack.pop(); + stack.peek().addAllChildren(dangling); + } + + return stack.peek().snapshotChildren(); + } + + /** + * Builds or reuses the tokenizer pattern. Alternation order is significant: + * IGNORE wins over OPEN, OPEN over CLOSE (same idea as putting more specific + * alternatives first in a hand-written .NET balancing pattern). + */ + private static Pattern tokenizer(String openRegex, String closeRegex, String ignoreRegex) { + String key; + String pattern; + if (ignoreRegex != null) { + key = ignoreRegex + "\0" + openRegex + "\0" + closeRegex; + pattern = "(?<IGNORE>" + ignoreRegex + ")|(?<OPEN>" + openRegex + ")|(?<CLOSE>" + closeRegex + ")"; + } else { + key = openRegex + "\0" + closeRegex; + pattern = "(?<OPEN>" + openRegex + ")|(?<CLOSE>" + closeRegex + ")"; + } + synchronized (TOKENIZER_CACHE) { + Pattern cached = TOKENIZER_CACHE.get(key); + if (cached != null) { + return cached; + } + Pattern compiled = Pattern.compile(pattern); + TOKENIZER_CACHE.put(key, compiled); + return compiled; + } + } + + /** + * Returns the text captured for this group. + * + * @return the matched text (never {@code null}); may include or exclude boundary + * delimiters depending on {@link MatchOptions#includeEdges()} + */ + public String getMatchedString() { + return matchedString; + } + + /** + * Start index of {@link #getMatchedString()} in the original input (inclusive). + * Comparable to .NET {@code Capture.Index}. + * + * @return the start offset + */ + public int getStart() { + return start; + } + + /** + * End index of {@link #getMatchedString()} in the original input (exclusive). + * Length is {@code getEnd() - getStart()}, like .NET {@code Capture.Length}. + * + * @return the end offset + */ + public int getEnd() { + return end; + } + + /** + * Length of {@link #getMatchedString()} ({@code end - start}). + * + * @return the length + */ + public int getLength() { + return end - start; + } + + /** + * Start index of the full balanced pair, always including the opening delimiter. + * + * @return the full-span start offset + */ + public int getFullStart() { + return fullStart; + } + + /** + * End index of the full balanced pair, always including the closing delimiter (exclusive). + * + * @return the full-span end offset + */ + public int getFullEnd() { + return fullEnd; + } + + /** + * Returns the immediately nested balanced groups. + * + * @return an unmodifiable list of children; empty (never {@code null}) for a leaf + */ + public List<BalancedGroup> getChildren() { + return children; + } + + /** + * Returns the enclosing group, if any. + * + * @return the parent node, or {@code null} if this is a root + */ + public BalancedGroup getParent() { + return parent; + } + + /** + * Nesting depth of this node (0 for a root). + * + * @return the number of ancestors + */ + public int getDepth() { + int depth = 0; + for (BalancedGroup p = parent; p != null; p = p.parent) { + depth++; + } + return depth; + } + + /** + * Returns the matched text of this group. + * + * @return the same value as {@link #getMatchedString()} + */ + @Override + public String toString() { + return matchedString; + } + + /** + * Frame for an as-yet unmatched opening delimiter during the scan. + * Child lists are allocated lazily: most frames are leaves. + */ + private static final class PendingGroup { + final int openStart; + final int openEnd; + private ArrayList<BalancedGroup> completedChildren; + + PendingGroup(int openStart, int openEnd) { + this.openStart = openStart; + this.openEnd = openEnd; + } + + void addChild(BalancedGroup child) { + if (completedChildren == null) { + completedChildren = new ArrayList<>(2); + } + completedChildren.add(child); + } + + void addAllChildren(PendingGroup other) { + if (other.completedChildren == null || other.completedChildren.isEmpty()) { + return; + } + if (completedChildren == null) { + completedChildren = other.completedChildren; + other.completedChildren = null; + } else { + completedChildren.addAll(other.completedChildren); + } + } + + List<BalancedGroup> children() { + return completedChildren == null ? List.of() : completedChildren; + } + + List<BalancedGroup> snapshotChildren() { + if (completedChildren == null || completedChildren.isEmpty()) { + return List.of(); + } + return List.copyOf(completedChildren); + } + } + + /** + * Options controlling balanced-group matching. + * <p> + * Instances are immutable; use the {@code with*} methods to derive variants. + * </p> + * + * @param ignoreRegex regex for spans to skip while scanning (e.g. string literals + * or escape sequences); {@code null} or blank means ignore nothing. + * This is the practical counterpart to writing “neither open nor + * close” character classes in a hand-built .NET balancing pattern. + * @param includeEdges {@code true} to keep opening/closing delimiters in + * {@link BalancedGroup#getMatchedString()}; {@code false} to strip + * them (like .NET's balancing capture of the interval between + * the subtracted open capture and the close match) + * + * @since 6.0.0 + */ + public record MatchOptions(String ignoreRegex, boolean includeEdges) { + + /** + * Default options: nothing ignored, delimiters included. + * + * @return the default options + */ + public static MatchOptions defaults() { + return new MatchOptions(null, true); + } + + /** + * Returns a copy with the given ignore regex. + * + * @param ignoreRegex regex of content to skip, or {@code null}/blank for none + * @return a new options instance + */ + public MatchOptions withIgnoreRegex(String ignoreRegex) { + return new MatchOptions(ignoreRegex, this.includeEdges); + } + + /** + * Returns a copy with the given edge-inclusion policy. + * + * @param includeEdges whether matched text keeps opening/closing delimiters + * @return a new options instance + */ + public MatchOptions withIncludeEdges(boolean includeEdges) { + return new MatchOptions(this.ignoreRegex, includeEdges); + } + } +} diff --git a/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java b/src/main/java/org/codehaus/groovy/runtime/StringGroovyMethods.java index 2d7f8248ae..2883e12748 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,96 @@ public class StringGroovyMethods extends DefaultGroovyMethodsSupport { return self.toString().toLowerCase(Locale.ROOT).contains(searchString.toString().toLowerCase(Locale.ROOT)); } + + /** + * Finds balanced (nested) groups in this CharSequence using default options + * (no ignore pattern; opening and closing delimiters are kept in the match text). + * <p> + * This is Groovy's structured alternative to .NET regex balancing groups + * ({@code (?<Open>…)} / {@code (?<Close-Open>…)} / {@code (?(Open)(?!))}). + * Delegates to {@link BalancedGroup#find(CharSequence, String, String)}. + * Java {@link java.util.regex.Pattern} cannot express capture-stack push/pop, so + * nesting is resolved with an explicit stack and the result is a tree of + * {@link BalancedGroup} nodes (with {@link BalancedGroup#getStart()}/{@link BalancedGroup#getEnd()} + * offsets comparable to .NET {@code Capture.Index}/{@code Length}). + * </p> + * <pre class="groovyTestCase"> + * def text = 'Root: (A + (B * C) + (D(E)))' + * def roots = text.findBalancedGroups(/\(/, /\)/) + * assert roots.size() == 1 + * assert roots[0].matchedString == '(A + (B * C) + (D(E)))' + * assert roots[0].children*.matchedString == ['(B * C)', '(D(E))'] + * assert roots[0].children[1].children[0].matchedString == '(E)' + * assert text.substring(roots[0].start, roots[0].end) == roots[0].matchedString + * assert roots[0].children[0].depth == 1 + * </pre> + * <p> + * Unmatched closers are ignored; unclosed openers are dropped but completed + * groups nested inside them are still returned (more tolerant than a strict + * .NET {@code (?(Open)(?!))} whole-string match). + * </p> + * + * @param self a CharSequence + * @param openRegex regular expression for the opening delimiter (must not be empty) + * @param closeRegex regular expression for the closing delimiter (must not be empty) + * @return an unmodifiable list of outermost {@link BalancedGroup} nodes (empty if none) + * @throws NullPointerException if {@code self}, {@code openRegex}, or {@code closeRegex} is {@code null} + * @throws IllegalArgumentException if {@code openRegex} or {@code closeRegex} is empty + * @throws java.util.regex.PatternSyntaxException if a pattern is not a valid Java regex + * + * @see BalancedGroup#find(CharSequence, String, String) + * @see #findBalancedGroups(CharSequence, String, String, BalancedGroup.MatchOptions) + * @since 6.0.0 + */ + public static List<BalancedGroup> findBalancedGroups(final CharSequence self, final String openRegex, final String closeRegex) { + return BalancedGroup.find(self, openRegex, closeRegex); + } + + /** + * Finds balanced (nested) groups in this CharSequence with the given options. + * Delegates to {@link BalancedGroup#find(CharSequence, String, String, BalancedGroup.MatchOptions)}. + * <pre class="groovyTestCase"> + * import groovy.util.regex.BalancedGroup + * def opts = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + * def g = 'func(arg1, arg2)'.findBalancedGroups(/\(/, /\)/, opts)[0] + * assert g.matchedString == 'arg1, arg2' + * assert g.start == 5 && g.end == 15 + * assert g.fullStart == 4 && g.fullEnd == 16 + * + * def code = 'if (true) { String s = "}"; }' + * def ignoreStrings = BalancedGroup.MatchOptions.defaults() + * .withIgnoreRegex(/"(?:\\.|[^"\\])*"/) + * assert code.findBalancedGroups(/\{/, /\}/, ignoreStrings)[0].matchedString == '{ String s = "}"; }' + * </pre> + * <p> + * {@link BalancedGroup.MatchOptions#includeEdges()}{@code false} keeps only the + * interior text (like .NET's balancing capture of the interval between the + * open capture and the close). {@link BalancedGroup.MatchOptions#ignoreRegex()} + * skips spans such as string literals—the usual substitute for a hand-built + * “neither delimiter” class in a .NET balancing pattern. + * </p> + * <p> + * If {@code options} is {@code null}, {@link BalancedGroup.MatchOptions#defaults()} is used. + * Named groups {@code OPEN}, {@code CLOSE}, and {@code IGNORE} are reserved by the scanner. + * </p> + * + * @param self a CharSequence + * @param openRegex regular expression for the opening delimiter (must not be empty) + * @param closeRegex regular expression for the closing delimiter (must not be empty) + * @param options match options, or {@code null} for defaults + * @return an unmodifiable list of outermost {@link BalancedGroup} nodes (empty if none) + * @throws NullPointerException if {@code self}, {@code openRegex}, or {@code closeRegex} is {@code null} + * @throws IllegalArgumentException if {@code openRegex} or {@code closeRegex} is empty + * @throws java.util.regex.PatternSyntaxException if a pattern is not a valid Java regex + * + * @see BalancedGroup#find(CharSequence, String, String, BalancedGroup.MatchOptions) + * @see #findBalancedGroups(CharSequence, String, String) + * @since 6.0.0 + */ + public static List<BalancedGroup> findBalancedGroups(final CharSequence self, final String openRegex, final String closeRegex, + final BalancedGroup.MatchOptions options) { + return BalancedGroup.find(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..46d44a236e --- /dev/null +++ b/src/test/groovy/bugs/Groovy12133.groovy @@ -0,0 +1,615 @@ +/* + * 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 java.util.regex.PatternSyntaxException + +import static org.junit.jupiter.api.Assertions.assertEquals +import static org.junit.jupiter.api.Assertions.assertFalse +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 + +/** + * GROOVY-12133: findBalancedGroups — structured alternative to .NET balancing groups. + */ +final class Groovy12133 { + + @Test + void testNullArgumentsThrowNpe() { + assertThrows(NullPointerException, () -> StringGroovyMethods.findBalancedGroups(null, '\\(', '\\)')) + assertThrows(NullPointerException, () -> StringGroovyMethods.findBalancedGroups('test', null, '\\)')) + assertThrows(NullPointerException, () -> StringGroovyMethods.findBalancedGroups('test', '\\(', null)) + } + + @Test + void testEmptyOpenOrCloseRegexRejected() { + assertThrows(IllegalArgumentException, () -> 'x'.findBalancedGroups('', '\\)')) + assertThrows(IllegalArgumentException, () -> 'x'.findBalancedGroups('\\(', '')) + } + + @Test + void testNoMatchReturnsEmptyList() { + assertTrue('plain text'.findBalancedGroups('\\(', '\\)').isEmpty()) + } + + @Test + void testPerfectlyNestedBuildsTree() { + String input = 'Root: (A + (B * C) + (D(E)))' + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)') + + assertEquals(1, roots.size()) + + BalancedGroup root = roots[0] + assertEquals('(A + (B * C) + (D(E)))', root.matchedString) + assertNull(root.parent) + assertEquals(0, root.depth) + assertEquals(2, root.children.size()) + + // Offsets comparable to .NET Capture.Index / Length + assertEquals(input.indexOf('(A +'), root.start) + assertEquals(root.start + root.matchedString.length(), root.end) + assertEquals(root.matchedString.length(), root.length) + assertEquals(root.start, root.fullStart) + assertEquals(root.end, root.fullEnd) + assertEquals(root.matchedString, input.substring(root.start, root.end)) + + BalancedGroup nodeB = root.children[0] + assertEquals('(B * C)', nodeB.matchedString) + assertSame(root, nodeB.parent) + assertEquals(1, nodeB.depth) + assertEquals(input.indexOf('(B * C)'), nodeB.start) + + BalancedGroup nodeD = root.children[1] + assertEquals('(D(E))', nodeD.matchedString) + assertSame(root, nodeD.parent) + + BalancedGroup nodeE = nodeD.children[0] + assertEquals('(E)', nodeE.matchedString) + assertSame(nodeD, nodeE.parent) + assertEquals(2, nodeE.depth) + } + + @Test + void testLeafChildrenImmutable() { + BalancedGroup leaf = 'Leaf: ()'.findBalancedGroups('\\(', '\\)')[0] + + assertTrue(leaf.children.isEmpty()) + assertThrows(UnsupportedOperationException, () -> leaf.children.add(null)) + } + + @Test + void testConstructorWiresParentAndRejectsReparenting() { + BalancedGroup child = new BalancedGroup('(E)', null) + BalancedGroup parent = new BalancedGroup('(D(E))', [child]) + + assertSame(parent, child.parent) + assertEquals(1, parent.children.size()) + assertSame(child, parent.children[0]) + assertEquals(0, child.start) + assertEquals(3, child.end) + + assertThrows(IllegalArgumentException, () -> new BalancedGroup('other', [child])) + assertThrows(NullPointerException, () -> new BalancedGroup(null, null)) + assertThrows(IllegalArgumentException, () -> new BalancedGroup('ab', 0, 1, 0, 1, null)) // length mismatch + assertThrows(IllegalArgumentException, () -> new BalancedGroup('a', -1, 1, 0, 1, null)) + } + + @Test + void testDanglingOpenRescuesCompletedChildren() { + // .NET strict (?(Open)(?!)) would fail the whole match; we salvage closed spans. + List<BalancedGroup> roots = '(A (B) (C(D)'.findBalancedGroups('\\(', '\\)') + + assertEquals(2, roots.size()) + assertEquals('(B)', roots[0].matchedString) + assertEquals('(D)', roots[1].matchedString) + assertNull(roots[0].parent) + assertNull(roots[1].parent) + assertEquals(0, roots[0].depth) + } + + @Test + void testDanglingCloseIgnored() { + List<BalancedGroup> roots = 'A ) B (C) D )'.findBalancedGroups('\\(', '\\)') + + assertEquals(1, roots.size()) + assertEquals('(C)', roots[0].matchedString) + } + + @Test + void testIncludeEdgesFalseStripsDelimitersLikeNetBalancingCapture() { + // .NET (?<Content-Open>\)) captures the interval between Open and close, not the delimiters. + String input = 'func(arg1, arg2)' + def options = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)', options) + + assertEquals(1, roots.size()) + BalancedGroup g = roots[0] + assertEquals('arg1, arg2', g.matchedString) + assertEquals(5, g.start) + assertEquals(15, g.end) + assertEquals(4, g.fullStart) // '(' + assertEquals(16, g.fullEnd) // after ')' + assertEquals('(arg1, arg2)', input.substring(g.fullStart, g.fullEnd)) + assertEquals('arg1, arg2', input.substring(g.start, g.end)) + } + + @Test + void testIncludeEdgesFalseWithEmptyContent() { + def options = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + List<BalancedGroup> roots = 'Empty: ()'.findBalancedGroups('\\(', '\\)', options) + + assertEquals(1, roots.size()) + assertEquals('', roots[0].matchedString) + assertEquals(0, roots[0].length) + assertEquals(roots[0].start, roots[0].end) + assertTrue(roots[0].fullEnd > roots[0].fullStart) + } + + @Test + void testIgnoreRegexSkipsLiterals() { + String code = 'if(true) { String s = "}"; }' + def options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex('"(?:\\\\.|[^"\\\\])*"') + + List<BalancedGroup> roots = code.findBalancedGroups('\\{', '\\}', options) + + assertEquals(1, roots.size()) + assertEquals('{ String s = "}"; }', roots[0].matchedString) + } + + @Test + void testBlankIgnoreRegexTreatedAsAbsent() { + def options = BalancedGroup.MatchOptions.defaults().withIgnoreRegex(' ') + List<BalancedGroup> roots = '(Test)'.findBalancedGroups('\\(', '\\)', options) + + assertEquals('(Test)', roots[0].matchedString) + } + + @Test + void testNullOptionsUsesDefaults() { + List<BalancedGroup> roots = '(A)'.findBalancedGroups('\\(', '\\)', null) + assertEquals('(A)', roots[0].matchedString) + + List<BalancedGroup> rootsOverload = '[B]'.findBalancedGroups('\\[', '\\]') + assertEquals('[B]', rootsOverload[0].matchedString) + } + + @Test + void testNestedHtmlDivsWithAttributes() { + 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.findBalancedGroups('<div\\b[^>]*>', '</div>') + + assertEquals(2, roots.size()) + + BalancedGroup appDiv = roots[0] + assertTrue(appDiv.matchedString.startsWith('<div id="app"')) + assertEquals(2, appDiv.children.size()) + assertEquals(html.substring(appDiv.start, appDiv.end), appDiv.matchedString) + + assertEquals('<div class="header" style="color: red;">Header</div>', + appDiv.children[0].matchedString) + + BalancedGroup bodyDiv = appDiv.children[1] + assertEquals(1, bodyDiv.children.size()) + assertEquals('<div class="content">Content</div>', + bodyDiv.children[0].matchedString) + } + + @Test + void testHtmlIncludeEdgesFalse() { + String html = '<div class="wrapper">\n <p>Hello World</p>\n</div>' + def options = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + + List<BalancedGroup> roots = html.findBalancedGroups('<div\\b[^>]*>', '</div>', options) + + assertEquals(1, roots.size()) + assertEquals('\n <p>Hello World</p>\n', roots[0].matchedString) + assertTrue(roots[0].fullStart < roots[0].start) + assertTrue(roots[0].fullEnd > roots[0].end) + } + + @Test + void testIgnoreHtmlComments() { + String html = ''' + <div id="main"> + <!-- <div class="fake">not real</div> --> + <div class="real">Valid Content</div> + </div> + ''' + + def options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex('(?s)<!--.*?-->') + + List<BalancedGroup> roots = html.findBalancedGroups('<div\\b[^>]*>', '</div>', options) + + assertEquals(1, roots.size()) + + BalancedGroup mainDiv = roots[0] + assertTrue(mainDiv.matchedString.contains('Valid Content')) + assertEquals(1, mainDiv.children.size()) + assertEquals('<div class="real">Valid Content</div>', mainDiv.children[0].matchedString) + } + + @Test + void testIgnoreScriptBlocksContainingFakeTags() { + String html = ''' + <div id="react-root"> + <script type="text/javascript"> + const fakeHtml = "</div>"; + </script> + <div class="app">App Ready</div> + </div> + ''' + + def options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex('(?s)<script\\b[^>]*>.*?</script>') + + List<BalancedGroup> roots = html.findBalancedGroups('<div\\b[^>]*>', '</div>', options) + + assertEquals(1, roots.size()) + assertEquals(1, roots[0].children.size()) + assertEquals('<div class="app">App Ready</div>', roots[0].children[0].matchedString) + } + + @Test + void testIgnoreSelfClosingTags() { + String html = ''' + <div id="parent"> + <div class="placeholder" /> <div class="child">I am child</div> + </div> + ''' + + def options = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex('<div\\b[^>]*/>') + + List<BalancedGroup> roots = html.findBalancedGroups('<div\\b[^>]*>', '</div>', options) + + assertEquals(1, roots.size()) + assertEquals(1, roots[0].children.size()) + assertEquals('<div class="child">I am child</div>', roots[0].children[0].matchedString) + } + + @Test + void testMalformedOuterHtmlRescuesInner() { + String html = ''' + <div class="broken-wrapper"> + <div class="lost-tag"> <div class="target">I am safe!</div> + ''' + + List<BalancedGroup> roots = html.findBalancedGroups('<div\\b[^>]*>', '</div>') + + assertEquals(1, roots.size()) + assertEquals('<div class="target">I am safe!</div>', roots[0].matchedString) + } + + @Test + void testMultipleTopLevelGroups() { + String input = '(a)(b(c))(d)' + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)') + + assertEquals(3, roots.size()) + assertEquals('(a)', roots[0].matchedString) + assertEquals('(b(c))', roots[1].matchedString) + assertEquals('(c)', roots[1].children[0].matchedString) + assertEquals('(d)', roots[2].matchedString) + + // Successive top-level spans are ordered and non-overlapping + assertTrue(roots[0].fullEnd <= roots[1].fullStart) + assertTrue(roots[1].fullEnd <= roots[2].fullStart) + roots.each { g -> + assertEquals(input.substring(g.start, g.end), g.matchedString) + } + } + + @Test + void testReturnedListIsUnmodifiable() { + List<BalancedGroup> roots = '(a)'.findBalancedGroups('\\(', '\\)') + assertThrows(UnsupportedOperationException, () -> roots.add(null)) + } + + @Test + void testCharSequenceOtherThanString() { + CharSequence cs = new StringBuilder('pre(x(y))post') + List<BalancedGroup> roots = cs.findBalancedGroups('\\(', '\\)') + + assertEquals(1, roots.size()) + assertEquals('(x(y))', roots[0].matchedString) + assertEquals('(y)', roots[0].children[0].matchedString) + assertEquals(3, roots[0].start) + assertEquals(9, roots[0].end) + } + + @Test + void testDeepNestingDepthAndOffsets() { + String input = '((((a))))' + BalancedGroup root = input.findBalancedGroups('\\(', '\\)')[0] + + assertEquals(0, root.depth) + BalancedGroup n = root + int expectedDepth = 0 + while (!n.children.isEmpty()) { + n = n.children[0] + expectedDepth++ + assertEquals(expectedDepth, n.depth) + assertEquals(input.substring(n.start, n.end), n.matchedString) + } + assertEquals('(a)', n.matchedString) + assertEquals(3, n.depth) // ((((a)))) → four nodes, depths 0..3 + } + + @Test + void testRepeatedCallsReuseTokenizerCache() { + // Behavioural smoke test: many identical calls must stay correct (cache hit path). + 100.times { + def roots = 'x(a(b))y(c)'.findBalancedGroups('\\(', '\\)') + assertEquals(2, roots.size()) + assertEquals('(a(b))', roots[0].matchedString) + assertEquals('(b)', roots[0].children[0].matchedString) + assertEquals('(c)', roots[1].matchedString) + } + } + + @Test + void testAdjacentAndNestedMixLikeNetCaptureCollectionUseCases() { + // Classic .NET sample shape: <abc><mno<xyz>> as angle-bracket pairs + String input = '<abc><mno<xyz>>' + List<BalancedGroup> roots = input.findBalancedGroups('<', '>') + + assertEquals(2, roots.size()) + assertEquals('<abc>', roots[0].matchedString) + assertTrue(roots[0].children.isEmpty()) + assertEquals('<mno<xyz>>', roots[1].matchedString) + assertEquals(1, roots[1].children.size()) + assertEquals('<xyz>', roots[1].children[0].matchedString) + } + + + @Test + void testBalancedGroupFindDirectApiAndToString() { + List<BalancedGroup> viaStatic = BalancedGroup.find('(x)', '\\(', '\\)') + assertEquals(1, viaStatic.size()) + assertEquals('(x)', viaStatic[0].toString()) + assertEquals('(x)', viaStatic[0].matchedString) + + List<BalancedGroup> viaStaticOpts = BalancedGroup.find( + 'f(y)', '\\(', '\\)', BalancedGroup.MatchOptions.defaults().withIncludeEdges(false)) + assertEquals('y', viaStaticOpts[0].matchedString) + } + + @Test + void testBalancedGroupFindNullTextThrows() { + assertThrows(NullPointerException, () -> BalancedGroup.find(null, '\\(', '\\)')) + assertThrows(NullPointerException, () -> BalancedGroup.find(null, '\\(', '\\)', null)) + } + + @Test + void testInvalidPatternThrowsPatternSyntaxException() { + assertThrows(PatternSyntaxException, () -> '(a)'.findBalancedGroups('[', '\\)')) + assertThrows(PatternSyntaxException, () -> BalancedGroup.find('a', '\\(', '*')) + assertThrows(PatternSyntaxException, + () -> BalancedGroup.find('{}', '\\{', '\\}', + BalancedGroup.MatchOptions.defaults().withIgnoreRegex('['))) + } + + @Test + void testConstructorRejectsInvalidFullRangeAndEndBeforeStart() { + assertThrows(IllegalArgumentException, () -> new BalancedGroup('a', 3, 1, 0, 1, null)) + assertThrows(IllegalArgumentException, () -> new BalancedGroup('a', 0, 1, 3, 1, null)) + assertThrows(IllegalArgumentException, () -> new BalancedGroup('a', 0, 1, -1, 0, null)) + assertThrows(NullPointerException, () -> new BalancedGroup('a', 0, 1, 0, 1, [null])) + } + + @Test + void testConstructorAcceptsEmptyListAndAbsoluteOffsets() { + BalancedGroup leaf = new BalancedGroup('leaf', []) + assertTrue(leaf.children.isEmpty()) + assertEquals(0, leaf.start) + assertEquals(4, leaf.end) + assertEquals(0, leaf.fullStart) + assertEquals(4, leaf.fullEnd) + + BalancedGroup absolute = new BalancedGroup('xy', 10, 12, 8, 15, null) + assertEquals('xy', absolute.matchedString) + assertEquals(10, absolute.start) + assertEquals(12, absolute.end) + assertEquals(8, absolute.fullStart) + assertEquals(15, absolute.fullEnd) + assertEquals(2, absolute.length) + } + + @Test + void testMatchOptionsWithersPreserveOtherFields() { + def base = BalancedGroup.MatchOptions.defaults() + assertNull(base.ignoreRegex()) + assertTrue(base.includeEdges()) + + def noEdges = base.withIncludeEdges(false) + assertFalse(noEdges.includeEdges()) + assertNull(noEdges.ignoreRegex()) + + def withIgnore = noEdges.withIgnoreRegex('"(?:\\\\.|[^"\\\\])*"') + assertFalse(withIgnore.includeEdges()) + assertEquals('"(?:\\\\.|[^"\\\\])*"', withIgnore.ignoreRegex()) + + def edgesBack = withIgnore.withIncludeEdges(true) + assertTrue(edgesBack.includeEdges()) + assertEquals(withIgnore.ignoreRegex(), edgesBack.ignoreRegex()) + + def cleared = edgesBack.withIgnoreRegex(null) + assertNull(cleared.ignoreRegex()) + assertTrue(cleared.includeEdges()) + } + + @Test + void testOnlyDanglingOpensYieldEmptySnapshot() { + // Orphan rescue with no completed children: addAllChildren early-return path + assertTrue('(((('.findBalancedGroups('\\(', '\\)').isEmpty()) + assertTrue(BalancedGroup.find('open only (', '\\(', '\\)').isEmpty()) + } + + @Test + void testCompletedGroupThenDanglingOpen() { + List<BalancedGroup> roots = '(done)(still-open'.findBalancedGroups('\\(', '\\)') + assertEquals(1, roots.size()) + assertEquals('(done)', roots[0].matchedString) + } + + @Test + void testOrphanRescueMergesIntoParentThatAlreadyHasChildren() { + // Super-root / outer frames already holding children when a dangling frame is popped + // exercises PendingGroup.addAllChildren merge branch (addAll vs list steal). + String input = '(outer (first) (second-open (inner)' + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)') + + assertEquals(2, roots.size()) + assertEquals('(first)', roots[0].matchedString) + assertEquals('(inner)', roots[1].matchedString) + } + + @Test + void testNestedThenSiblingAfterClose() { + String input = '(a(b))(c)' + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)') + assertEquals(2, roots.size()) + assertEquals('(a(b))', roots[0].matchedString) + assertEquals('(b)', roots[0].children[0].matchedString) + assertEquals('(c)', roots[1].matchedString) + // second addChild on the same pending frame (super-root) + assertEquals(0, roots[0].depth) + assertEquals(0, roots[1].depth) + } + + @Test + void testIgnoreRegexCacheKeyDistinctFromNoIgnore() { + String text = '{ "x": 1 }' + def withIgnore = BalancedGroup.MatchOptions.defaults() + .withIgnoreRegex('"(?:\\\\.|[^"\\\\])*"') + // Without ignore, the quote-embedded content is not special; braces still balance. + assertEquals(1, text.findBalancedGroups('\\{', '\\}').size()) + assertEquals(1, text.findBalancedGroups('\\{', '\\}', withIgnore).size()) + // Hit both tokenizer cache keys (with and without IGNORE alternative) + assertEquals(1, text.findBalancedGroups('\\{', '\\}').size()) + assertEquals(1, text.findBalancedGroups('\\{', '\\}', withIgnore).size()) + } + + @Test + void testTokenizerCacheEvictionBeyondLimit() { + // TOKENIZER_CACHE_LIMIT is 64; filling unique ignore keys exercises removeEldestEntry. + def base = BalancedGroup.MatchOptions.defaults() + 70.times { int i -> + def opts = base.withIgnoreRegex("never_match_${i}_xyz") + List<BalancedGroup> roots = '(ok)'.findBalancedGroups('\\(', '\\)', opts) + assertEquals(1, roots.size()) + assertEquals('(ok)', roots[0].matchedString) + } + // Still correct after eviction churn + assertEquals('(ok)', '(ok)'.findBalancedGroups('\\(', '\\)')[0].matchedString) + } + + @Test + void testZeroWidthOpenLookaheadWithIncludeEdgesFalse() { + // Zero-width OPEN then CLOSE: interior is the span between openEnd and closeStart. + def opts = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false) + List<BalancedGroup> roots = BalancedGroup.find('ab', '(?=a)', 'b', opts) + assertEquals(1, roots.size()) + assertEquals('a', roots[0].matchedString) + assertEquals(roots[0].start, roots[0].fullStart) // open was zero-width at fullStart + assertTrue(roots[0].fullEnd > roots[0].end || roots[0].fullEnd >= roots[0].end) + } + + @Test + void testCloseWhenOpenStackIsOnlyVirtualRootIsIgnored() { + // Explicit extra closers before any open — CLOSE branch with stack.size() == 1 + assertTrue(')))'.findBalancedGroups('\\(', '\\)').isEmpty()) + assertEquals(['(x)'], ')))(x)))'.findBalancedGroups('\\(', '\\)')*.matchedString) + } + + @Test + void testGStringCharSequenceSource() { + def name = 'world' + GString g = "(hello $name)" + List<BalancedGroup> roots = g.findBalancedGroups('\\(', '\\)') + assertEquals(1, roots.size()) + assertEquals('(hello world)', roots[0].matchedString) + assertEquals(g.toString(), roots[0].matchedString) + assertEquals(0, roots[0].start) + assertEquals(g.toString().length(), roots[0].end) + } + + @Test + void testIncludeEdgesTrueExplicitOptions() { + def opts = BalancedGroup.MatchOptions.defaults().withIncludeEdges(true) + BalancedGroup g = '(z)'.findBalancedGroups('\\(', '\\)', opts)[0] + assertEquals('(z)', g.matchedString) + assertEquals(g.start, g.fullStart) + assertEquals(g.end, g.fullEnd) + } + + @Test + void testMultipleChildrenOnSameFrameViaAddChild() { + // Three completed children under one parent → repeated addChild growth + String input = '(p (a) (b) (c))' + BalancedGroup root = input.findBalancedGroups('\\(', '\\)')[0] + assertEquals(3, root.children.size()) + assertEquals(['(a)', '(b)', '(c)'], root.children*.matchedString) + root.children.each { child -> + assertSame(root, child.parent) + assertEquals(1, child.depth) + } + } + + @Test + void testDeepOrphanRescueChain() { + // Several unfinished opens each carrying a completed child + String input = '(a (b)) (c (d (e)' + List<BalancedGroup> roots = input.findBalancedGroups('\\(', '\\)') + assertEquals(2, roots.size()) + assertEquals('(a (b))', roots[0].matchedString) + assertEquals('(b)', roots[0].children[0].matchedString) + assertEquals('(e)', roots[1].matchedString) + } + + @Test + void testNullIgnoreRegexOnOptionsIsAbsent() { + def opts = BalancedGroup.MatchOptions.defaults().withIgnoreRegex(null) + assertNull(opts.ignoreRegex()) + assertEquals('(t)', '(t)'.findBalancedGroups('\\(', '\\)', opts)[0].matchedString) + } + + @Test + void testEmptyInput() { + assertTrue(''.findBalancedGroups('\\(', '\\)').isEmpty()) + assertTrue(BalancedGroup.find('', '\\(', '\\)').isEmpty()) + } +}
