[
https://issues.apache.org/jira/browse/GROOVY-12133?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Daniel Sun updated GROOVY-12133:
--------------------------------
Description:
*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.
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 {{findBalanced}} 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
>
>
> *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.
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
