pjfanning opened a new pull request, #137:
URL: https://github.com/apache/poi-xmlbeans/pull/137
## Quadratic closure matching (main fix)
`RegularExpression.ClosureContext` records each offset a `*`/`+` closure
visits so it can stop repeats that match nothing. The offsets were kept in a
list that `contains()` scanned linearly on every iteration, so matching any
closure was O(nĀ²) in the input length. This affects runtime `xs:pattern`
validation (e.g. `\c+` on a long value) as well as the identity-constraint
XPath check at schema compile time.
The list is now an open-addressing int hash set with O(1) lookups. Memory
grows with the number of offsets seen, as it did with the list, so sparse
offsets stay cheap; a `BitSet` would be sized by the largest offset. `reset()`
drops a table grown by a long match so a cached `Context` doesn't keep it.
| input | before | after |
|---|---|---|
| XPath regex, 50k-char name | 3.2 s | ~75ā540 ms (noisy, heavily loaded
machine) |
| `\c+`, 8k chars | ~100 ms (4x per doubling) | ~10ā35 ms |
| `\c+`, 1M chars | ~20 min (extrapolated) | < 1 s |
## Smaller changes
- `RegularExpression.match`: use `ArrayDeque` for the op stack instead of
the synchronized `java.util.Stack`.
- `RangeToken.match`: characters above U+00FF were checked with a linear
scan of the class ranges (hundreds of them for `\c`, `\i`, `\p{L}`). They now
use a binary search of a merged copy of those ranges, built once alongside the
existing Latin-1 bitmap. The copy is merged because uncompacted ranges can
overlap. No serialized fields changed: the new field is `private transient`.
- Replaced simple regex calls with plain string code:
`String.matches("^\\w+$")` in `StscState`/`StscImporter` (which compiled a new
regex on every call), plus `replaceAll` in `CodeGenUtil` and `MavenPlugin`.
## Tests
- `testLongClosureIsLinear`: `\c+` against 1M chars, with a 30 s timeout.
- `testCharClassAboveLatin1`: compares a positive and a negated class
against `java.util.regex` for every code point.
- Ran the `misc.*`, `scomp.*`, `xmlobject.*`, `compile.scomp.*` and
`validator.*` tests locally: 779 tests, all pass. `CompilationTests.partials`
failed once on a missing generated file while the machine was overloaded, then
passed when run alone.
š¤ Generated with [Claude Code](https://claude.com/claude-code)
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
