[
https://issues.apache.org/jira/browse/GROOVY-12133?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Daniel Sun updated GROOVY-12133:
--------------------------------
Description:
h2. Summary
Add a GDK utility to extract nested balanced groups from text (parentheses,
braces, HTML-like tags, etc.), providing a structured alternative to .NET regex
balancing groups for the Java/Groovy regex stack.
h2. Motivation
{{java.util.regex.Pattern}} has no equivalent of .NET balancing groups
({{(?<name1-name2>…)}}). Nested constructs are therefore awkward to handle with
pure Java regex and often lead to fragile or backtracking-heavy patterns.
Groovy users need a first-class, safe way to recover hierarchical balanced
spans with clear source offsets.
h2. Solution
Introduce {{groovy.util.regex.BalancedGroup}} and a GDK method
{{CharSequence.findBalancedGroups(...)}}, backed by a single-pass tokenizer +
stack (not recursive regex). Nesting is resolved by an explicit stack, so
balancing itself does not introduce ReDoS; cost scales with tokenizer matches
and the user-supplied open/close/ignore patterns.
h3. API
* {{BalancedGroup.find(text, openRegex, closeRegex[, options])}} — core entry
point
* {{CharSequence.findBalancedGroups(openRegex, closeRegex[, options])}} — GDK
sugar (delegates to the above)
* {{BalancedGroup.MatchOptions}} — immutable options ({{ignoreRegex}},
{{includeEdges}}) with wither methods
* Result tree: {{matchedString}}, {{start}}/{{end}}/{{length}},
{{fullStart}}/{{fullEnd}}, {{children}}, {{parent}}, {{depth}}
h3. Behaviour notes
* *Open/close* are user regexes for delimiters (must be non-empty).
* *{{includeEdges}}*: when {{false}}, {{matchedString}} is the interior only
(interval between open and close), while {{fullStart}}/{{fullEnd}} still cover
the full pair including delimiters.
* *{{ignoreRegex}}*: spans to skip while scanning (e.g. string literals,
comments, self-closing tags).
* Unmatched closers are ignored. Unclosed openers are dropped at end-of-input;
completed groups nested inside them are promoted (“orphan rescue”).
* Named groups {{OPEN}}, {{CLOSE}}, and {{IGNORE}} are reserved by the internal
tokenizer.
* Compiled tokenizers are cached (bounded LRU) for repeated open/close/ignore
triples.
h2. Examples
{code:groovy}
def roots = 'Root: (A + (B * C) + (D(E)))'.findBalancedGroups(/\(/, /\)/)
assert roots.size() == 1
assert roots[0].matchedString == '(A + (B * C) + (D(E)))'
assert roots[0].children*.matchedString == ['(B * C)', '(D(E))']
def opts = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false)
assert 'func(arg1, arg2)'.findBalancedGroups(/\(/, /\)/, opts)[0].matchedString
== 'arg1, arg2'
def code = 'if (true) { String s = "}"; }'
def ignoreStrings = BalancedGroup.MatchOptions.defaults()
.withIgnoreRegex(/"(?:\\.|[^"\\])*"/)
assert code.findBalancedGroups(/\{/, /\}/, ignoreStrings)[0].matchedString ==
'{ String s = "}"; }'
{code}
was:
*Context*
Java's native regex engine lacks C#-style balanced group support (pushdown
automaton). This makes parsing infinitely nested structures (e.g., nested
parentheses, HTML tags, or code blocks) notoriously difficult, often leading to
ReDoS (Regular Expression Denial of Service) vulnerabilities if solved purely
via regex.
*Proposed Solution*
Introduce a highly optimized {{findBalancedGroups}} method. It should use a
single-pass, stack-based scanner with dynamic subsumption (tail-absorption) to
mimic C# balanced group behavior while guaranteeing O(N) performance.
*Acceptance Criteria*
* *Core Extraction:* Correctly extracts the balanced groups from deeply nested
strings (e.g., {{(A + (B * C))}} extracts the entire block).
* *Fault Tolerance:* Gracefully handles malformed/dangling boundaries
(unmatched open or close tags) without polluting the stack or crashing.
* *Ignore Options:* Supports an {{ignoreRegex}} configuration to safely bypass
escaped boundaries or string literals (e.g., ignoring {{"{}"}} inside quotes).
* *Edge Stripping:* Supports an {{includeEdges}} configuration to optionally
strip the outer boundary tags from the result.
* *Performance:* Must guarantee strict O(N) time complexity. No backtracking,
recursion, or expensive sorting operations are allowed.
> Implement findBalancedGroups utility to support Regex Balanced Groups
> ---------------------------------------------------------------------
>
> Key: GROOVY-12133
> URL: https://issues.apache.org/jira/browse/GROOVY-12133
> Project: Groovy
> Issue Type: Improvement
> Reporter: Daniel Sun
> Priority: Major
> Fix For: 6.0.0-beta-1
>
>
> h2. Summary
> Add a GDK utility to extract nested balanced groups from text (parentheses,
> braces, HTML-like tags, etc.), providing a structured alternative to .NET
> regex balancing groups for the Java/Groovy regex stack.
> h2. Motivation
> {{java.util.regex.Pattern}} has no equivalent of .NET balancing groups
> ({{(?<name1-name2>…)}}). Nested constructs are therefore awkward to handle
> with pure Java regex and often lead to fragile or backtracking-heavy
> patterns. Groovy users need a first-class, safe way to recover hierarchical
> balanced spans with clear source offsets.
> h2. Solution
> Introduce {{groovy.util.regex.BalancedGroup}} and a GDK method
> {{CharSequence.findBalancedGroups(...)}}, backed by a single-pass tokenizer +
> stack (not recursive regex). Nesting is resolved by an explicit stack, so
> balancing itself does not introduce ReDoS; cost scales with tokenizer matches
> and the user-supplied open/close/ignore patterns.
> h3. API
> * {{BalancedGroup.find(text, openRegex, closeRegex[, options])}} — core entry
> point
> * {{CharSequence.findBalancedGroups(openRegex, closeRegex[, options])}} — GDK
> sugar (delegates to the above)
> * {{BalancedGroup.MatchOptions}} — immutable options ({{ignoreRegex}},
> {{includeEdges}}) with wither methods
> * Result tree: {{matchedString}}, {{start}}/{{end}}/{{length}},
> {{fullStart}}/{{fullEnd}}, {{children}}, {{parent}}, {{depth}}
> h3. Behaviour notes
> * *Open/close* are user regexes for delimiters (must be non-empty).
> * *{{includeEdges}}*: when {{false}}, {{matchedString}} is the interior only
> (interval between open and close), while {{fullStart}}/{{fullEnd}} still
> cover the full pair including delimiters.
> * *{{ignoreRegex}}*: spans to skip while scanning (e.g. string literals,
> comments, self-closing tags).
> * Unmatched closers are ignored. Unclosed openers are dropped at
> end-of-input; completed groups nested inside them are promoted (“orphan
> rescue”).
> * Named groups {{OPEN}}, {{CLOSE}}, and {{IGNORE}} are reserved by the
> internal tokenizer.
> * Compiled tokenizers are cached (bounded LRU) for repeated open/close/ignore
> triples.
> h2. Examples
> {code:groovy}
> def roots = 'Root: (A + (B * C) + (D(E)))'.findBalancedGroups(/\(/, /\)/)
> assert roots.size() == 1
> assert roots[0].matchedString == '(A + (B * C) + (D(E)))'
> assert roots[0].children*.matchedString == ['(B * C)', '(D(E))']
> def opts = BalancedGroup.MatchOptions.defaults().withIncludeEdges(false)
> assert 'func(arg1, arg2)'.findBalancedGroups(/\(/, /\)/,
> opts)[0].matchedString == 'arg1, arg2'
> def code = 'if (true) { String s = "}"; }'
> def ignoreStrings = BalancedGroup.MatchOptions.defaults()
> .withIgnoreRegex(/"(?:\\.|[^"\\])*"/)
> assert code.findBalancedGroups(/\{/, /\}/, ignoreStrings)[0].matchedString ==
> '{ String s = "}"; }'
> {code}
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
