You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@groovy.apache.org by "paulk-asert (via GitHub)" <gi...@apache.org> on 2026/09/03 06:13:02 UTC
[PR] GROOVY-12333: findBalancedGroups: bound the cost of deeply nested input [groovy]
paulk-asert opened a new pull request, #2872:
URL: https://github.com/apache/groovy/pull/2872
A few hundred KB of nested delimiters cost tens of seconds, then died - with a StackOverflowError if the stack ran out first, otherwise by exhausting the heap. Two independent quadratics, both in the nesting.
Depth was assigned eagerly during assembly. find() builds bottom-up, so a node is attached to a new parent once per enclosing delimiter, and each attach re-walked the whole subtree beneath it to restamp depths - quadratic, and one stack frame per level. Depth is now resolved from the parent chain when first asked for and cached, along with every ancestor walked on the way, so resolving a whole tree costs O(n) and any node is O(1) once resolved. The walk is iterative, so nesting no longer consumes stack. A chain 20,000 deep goes from 3646ms to 51ms, and one 10,000 deep whose depths are never read from 853ms to 4ms.
Attaching a node whose depth was already read caches it against a parent chain that is about to change, so the attach drops the cached depths beneath it. That walk is iterative too, prunes at any node whose depth was never read, and does not run during find(), which reads no depths while assembling.
Each node also held its own copy of its matched text. Groups nest, so their spans overlap and those copies duplicate most of the document once per level: 64KB of nesting retained about 990MB. A node now keeps the source and slices on demand, which is what the start/end offsets it already carried were for, so retention is proportional to the input - the same 64KB now retains 2MB. Reading every group's text costs what it did; reading one group's text repeatedly now slices each time rather than returning a stored copy, about 2ns per call.
The package-private six-argument constructor consequently takes the source rather than the already-sliced text, and its offsets index into it. Passing text detached from its offsets is no longer meaningful, so the range check that compared them is now a bounds check against the source. find() is the only production caller and always had the source to hand; it no longer allocates a substring per group.
The source must be effectively immutable for as long as a node lives. find() already flattens its input to a String before matching, which guarantees that.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@groovy.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GROOVY-12333: findBalancedGroups: bound the cost of deeply nested input [groovy]
Posted by "testlens-app[bot] (via GitHub)" <gi...@apache.org>.
testlens-app[bot] commented on PR #2872:
URL: https://github.com/apache/groovy/pull/2872#issuecomment-5521629059
## 🚨 TestLens detected 3 failed tests 🚨
Here is what you can do:
1) Inspect the test failures carefully.
2) If you are convinced that some of the tests are flaky, you can mute them below.
3) Finally, trigger a rerun by checking the rerun checkbox.
### Test Summary
#### [Build and test / lts \(17, windows-latest, 1\)](https://github.com/apache/groovy/actions/runs/33722217093/job/100543530211?pr=2872) > :groovy-groovysh:test
| Test | Runs | Flakiness |
|---|---|--:|
| GroovyPosixCommandsTest > headAndGrepAndWcStripControlCharactersFromNames\(\) | ❌ | 20% 🔴 |
| GroovyPosixCommandsTest > lsStripsControlCharactersFromFileNames\(\) | ❌ | 20% 🔴 |
| GroovyPosixCommandsTest > lsStripsControlCharactersFromSymlinkTargets\(\) | ❌ | 20% 🔴 |
🏷️ Commit: 3bcc275a8004ac2f5dafc40dfa42de011d2be21d
▶️ Tests: 68875 executed
🟡 Checks: 8/29 completed
### Test Failures
<details><summary><strong>GroovyPosixCommandsTest > headAndGrepAndWcStripControlCharactersFromNames()</strong> (:groovy-groovysh:test in <a href="https://github.com/apache/groovy/actions/runs/33722217093/job/100543530211?pr=2872">Build and test / lts (17, windows-latest, 1)</a>)</summary>
```
java.nio.file.InvalidPathException: Illegal char <> at index 2: ok[2Ktrap.txt
at java.base/sun.nio.fs.WindowsPathParser.normalize(WindowsPathParser.java:182)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:153)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:77)
at java.base/sun.nio.fs.WindowsPath.parse(WindowsPath.java:92)
at java.base/sun.nio.fs.WindowsFileSystem.getPath(WindowsFileSystem.java:232)
at java.base/java.nio.file.Path.resolve(Path.java:515)
at java.base/jdk.internal.reflect.GeneratedMethodAccessor33.invoke(Unknown Source)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:569)
at org.codehaus.groovy.reflection.CachedMethod.invokeReflective(CachedMethod.java:505)
at org.codehaus.groovy.reflection.CachedMethod.invoke(CachedMethod.java:455)
at groovy.lang.MetaMethod.doMethodInvoke(MetaMethod.java:298)
at org.codehaus.groovy.vmplugin.v8.IndyInterface.invokeColdReflective(IndyInterface.java:650)
at org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest.headAndGrepAndWcStripControlCharactersFromNames(GroovyPosixCommandsTest.groovy:123)
```
</details>
<details><summary><strong>GroovyPosixCommandsTest > lsStripsControlCharactersFromFileNames()</strong> (:groovy-groovysh:test in <a href="https://github.com/apache/groovy/actions/runs/33722217093/job/100543530211?pr=2872">Build and test / lts (17, windows-latest, 1)</a>)</summary>
```
java.nio.file.InvalidPathException: Illegal char <> at index 2: ok[2Ktrap.txt
at java.base/sun.nio.fs.WindowsPathParser.normalize(WindowsPathParser.java:182)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:153)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:77)
at java.base/sun.nio.fs.WindowsPath.parse(WindowsPath.java:92)
at java.base/sun.nio.fs.WindowsFileSystem.getPath(WindowsFileSystem.java:232)
at java.base/java.nio.file.Path.resolve(Path.java:515)
at java.base/jdk.internal.reflect.GeneratedMethodAccessor33.invoke(Unknown Source)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:569)
at org.codehaus.groovy.reflection.CachedMethod.invokeReflective(CachedMethod.java:505)
at org.codehaus.groovy.reflection.CachedMethod.invoke(CachedMethod.java:455)
at groovy.lang.MetaMethod.doMethodInvoke(MetaMethod.java:298)
at org.codehaus.groovy.vmplugin.v8.IndyInterface.invokeColdReflective(IndyInterface.java:650)
at org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest.lsStripsControlCharactersFromFileNames(GroovyPosixCommandsTest.groovy:97)
```
</details>
<details><summary><strong>GroovyPosixCommandsTest > lsStripsControlCharactersFromSymlinkTargets()</strong> (:groovy-groovysh:test in <a href="https://github.com/apache/groovy/actions/runs/33722217093/job/100543530211?pr=2872">Build and test / lts (17, windows-latest, 1)</a>)</summary>
```
java.nio.file.InvalidPathException: Illegal char <> at index 2: ok[2Ktrap.txt
at java.base/sun.nio.fs.WindowsPathParser.normalize(WindowsPathParser.java:182)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:153)
at java.base/sun.nio.fs.WindowsPathParser.parse(WindowsPathParser.java:77)
at java.base/sun.nio.fs.WindowsPath.parse(WindowsPath.java:92)
at java.base/sun.nio.fs.WindowsFileSystem.getPath(WindowsFileSystem.java:232)
at java.base/java.nio.file.Path.resolve(Path.java:515)
at java.base/jdk.internal.reflect.GeneratedMethodAccessor33.invoke(Unknown Source)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:569)
at org.codehaus.groovy.reflection.CachedMethod.invokeReflective(CachedMethod.java:505)
at org.codehaus.groovy.reflection.CachedMethod.invoke(CachedMethod.java:455)
at groovy.lang.MetaMethod.doMethodInvoke(MetaMethod.java:298)
at org.codehaus.groovy.vmplugin.v8.IndyInterface.invokeColdReflective(IndyInterface.java:650)
at org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest.lsStripsControlCharactersFromSymlinkTargets(GroovyPosixCommandsTest.groovy:108)
```
</details>
### Rerun Controls
> [!NOTE]
> Checks are currently running using the configuration below.
Select tests to mute in this pull request:
🔲 GroovyPosixCommandsTest > headAndGrepAndWcStripControlCharactersFromNames\(\) <!-- uniqueId=[engine:junit-jupiter]/[class:org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest]/[method:headAndGrepAndWcStripControlCharactersFromNames()] -->
🔲 GroovyPosixCommandsTest > lsStripsControlCharactersFromFileNames\(\) <!-- uniqueId=[engine:junit-jupiter]/[class:org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest]/[method:lsStripsControlCharactersFromFileNames()] -->
🔲 GroovyPosixCommandsTest > lsStripsControlCharactersFromSymlinkTargets\(\) <!-- uniqueId=[engine:junit-jupiter]/[class:org.apache.groovy.groovysh.jline.GroovyPosixCommandsTest]/[method:lsStripsControlCharactersFromSymlinkTargets()] -->
Reuse successful test results:
🔲 ♻️ Only rerun the tests that failed or were muted before
Click the checkbox to trigger a rerun:
🔲 **Rerun jobs**
---
_Learn more about TestLens at [testlens.app/docs](https://testlens.app/docs/features/pr-comment/)._
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@groovy.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GROOVY-12333: findBalancedGroups: bound the cost of deeply nested input [groovy]
Posted by "paulk-asert (via GitHub)" <gi...@apache.org>.
paulk-asert merged PR #2872:
URL: https://github.com/apache/groovy/pull/2872
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@groovy.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GROOVY-12333: findBalancedGroups: bound the cost of deeply nested input [groovy]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #2872:
URL: https://github.com/apache/groovy/pull/2872#issuecomment-5521748237
## [Codecov](https://app.codecov.io/gh/apache/groovy/pull/2872?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `93.10345%` with `2 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 70.9736%. Comparing base ([`b0fb70b`](https://app.codecov.io/gh/apache/groovy/commit/b0fb70bfc9554d143743a3f5bcd1de46aefb3ac3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`3bcc275`](https://app.codecov.io/gh/apache/groovy/commit/3bcc275a8004ac2f5dafc40dfa42de011d2be21d?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 2 commits behind head on master.
| [Files with missing lines](https://app.codecov.io/gh/apache/groovy/pull/2872?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [src/main/java/groovy/util/regex/BalancedGroup.java](https://app.codecov.io/gh/apache/groovy/pull/2872?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fgroovy%2Futil%2Fregex%2FBalancedGroup.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-c3JjL21haW4vamF2YS9ncm9vdnkvdXRpbC9yZWdleC9CYWxhbmNlZEdyb3VwLmphdmE=) | 93.1034% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/groovy/pull/2872?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
[](https://app.codecov.io/gh/apache/groovy/pull/2872?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)
```diff
@@ Coverage Diff @@
## master #2872 +/- ##
==================================================
+ Coverage 70.9621% 70.9736% +0.0115%
- Complexity 37181 37196 +15
==================================================
Files 1578 1578
Lines 135189 135215 +26
Branches 25038 25046 +8
==================================================
+ Hits 95933 95967 +34
+ Misses 30569 30562 -7
+ Partials 8687 8686 -1
```
| [Files with missing lines](https://app.codecov.io/gh/apache/groovy/pull/2872?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [src/main/java/groovy/util/regex/BalancedGroup.java](https://app.codecov.io/gh/apache/groovy/pull/2872?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fgroovy%2Futil%2Fregex%2FBalancedGroup.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-c3JjL21haW4vamF2YS9ncm9vdnkvdXRpbC9yZWdleC9CYWxhbmNlZEdyb3VwLmphdmE=) | `94.9275% <93.1034%> (-0.9058%)` | :arrow_down: |
... and [13 files with indirect coverage changes](https://app.codecov.io/gh/apache/groovy/pull/2872/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)
</details>
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@groovy.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org