pjfanning opened a new pull request, #1440:
URL: https://github.com/apache/poi/pull/1440
## Repro
Each of these takes seconds with a crafted format string from styles.xml /
an HSSF FORMAT record, or an embedded object name (times for 20k-char inputs
below):
- `DataFormatter`, colours: `"a"` x 10k + `"[RED]"` x 2k. Every colour was
removed by `indexOf` + `substring`, then the search started again from the
beginning.
- `DataFormatter`, `localePatternGroup` `\[\$[^-\]]*(?:-[0-9A-Za-z]+)?]`:
`"[$"` x 10k with no `]` or `-`. Each `[$` scans to the end of the string and
fails.
- `DataFormatter.InternalDecimalFormatWithScale`, `endsWithCommas` `(,+)$`:
a long run of commas that is not at the end, e.g. `0"x,,,,...,y"`. find() is
tried from every comma in the run.
- `DateUtil.date_ptrn3b`: `y` + `/` x n + `x`. `/`, `m`, `M` and space are
in both the first class and the `0* ?[ampAMP/]*` tail, so `+` gives them back
one at a time.
- `EmbeddedData.setFilename`, `[^/\\]*[/\\]` replaceAll: a long name with no
separator. Each start position scans to the end.
## Fix
- Colours: one pass that appends to a StringBuilder. A colour has no
brackets inside it, so a colour can only end at a `]` and start at the last `[`
before it. On a `]`, the text from that `[` is checked with
`colorPattern.matches()` and removed if it is a colour. That also handles
colours made by an earlier removal, e.g. `[Re[Red]d]`, as the old loop did.
- Locale: a scanner gives the same matches as the regex. From `[$` it scans
to the first `-` or `]`. `]` is a match. `-` needs one or more ASCII
letters/digits and then `]`. If that fails, the search resumes after the `-`,
because any `[$` before it stops at the same `-` and fails the same way. The
replacement text is unchanged.
- `endsWithCommas` becomes `(?<!,)(,++)$`. A match can only start at the
first comma of a run, and a shorter run never reaches `$`.
- `normalizeSectionGrouping` counted the scaling commas by repeatedly
calling `substring` (also quadratic). It now counts them with an index.
- `date_ptrn3b`: the first class is possessive (`++`). If the old regex
matched by giving chars back, those chars are `m`/`M`/`/` and maybe a space.
The rest of the string after the longest first-class prefix starts with a char
outside that class, so it can only be `[ampAMP/]*`. The possessive form
therefore matches with an empty `0* ?` and the tail.
- `EmbeddedData`: `substring(max(lastIndexOf('/'), lastIndexOf('\\')) +
1).trim()`.
## Equivalence check
I compared the old code against the new code on every string up to a length
bound and looked for identical outputs:
| What | Alphabet | Max length | Strings |
|---|---|---|---|
| colour removal (output) | `[ ] R e D x` | 9 | 12,093,235 |
| colour removal (output) | tokens `[ ] RED Re d COLOR color ␠ \t 1 5 6 x` |
6 tokens | 5,229,043 |
| locale replacement (output of the whole loop) | `[ $ - ] a Z 1 . \ _` | 7
| 11,111,111 |
| endsWithCommas (replaceAll result, find() group and start) | `, 0 x \n \r
\u0085
` | 8 | 6,725,601 |
| date_ptrn3b matches() | `y / ␠ 0 a m M P x \n` | 7 | 11,111,111 |
| EmbeddedData file name | `/ \ a ␠ \n \t` | 9 | 12,093,235 |
I also compared 2M random strings of length < 30 for colours and for
locales. Every output was identical.
## Timings (20k-char adversarial input, old vs new)
| Case | Old | New |
|---|---|---|
| colours | 20,028 ms | 2 ms |
| locale | 21,837 ms | 0 ms |
| endsWithCommas | 91,688 ms (replaceAll + find) | 4 ms |
| date_ptrn3b | 17,237 ms | 11 ms |
| EmbeddedData | 18,716 ms | 0 ms |
## Tests
New tests use 50k-char inputs with
`assertTimeoutPreemptively(Duration.ofSeconds(10), ...)`. All six time out on
trunk and pass with this change:
TestDataFormatter `testManyColours`, `testLocaleWithoutEnd`,
`testManyCommasNotAtEnd`, `testLongDateLikeFormat`; TestDateUtil
`isADateFormatWithLongRun`; TestEmbeddedExtractor `filenameWithoutPath`.
I ran these test classes, with no failures:
- poi: TestDataFormatter (70, 2 skipped), TestDateUtil (29),
TestHSSFDataFormatter (5), TestCellFormat (50), TestCellFormatCondition (1),
TestCellFormatResult (1)
- poi-ooxml: TestDataFormatterAgainstExcel (569), TestXSSFDataFormat (12),
TestCellFormatPart (9), TestEmbeddedExtractor (4), TestEmbedOLEPackage (3)
🤖 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]
