pjfanning opened a new pull request, #1441:
URL: https://github.com/apache/poi/pull/1441
Three regular expressions in formula evaluation backtrack badly on text that
almost matches. Each is evaluated once per cell or per evaluation, so a single
formula can hang for minutes.
## Repro (before)
| Input | Old time |
|---|---|
| COUNTIF-style criteria `*a*a*c` vs text `"a"x2000 + "b"` | 146 s (2.0 s at
500, 15.5 s at 1000) |
| `OperandResolver.parseDouble("1"x20000 + "x")` | 204 s (16 s at 5000) |
| `IMAGINARY` / `IMREAL` of `"1"x20000 + "x"` | 92 s (11 s at 5000) |
## Cause
1. `Countif.StringMatcher.getWildCardPattern` turns `*` into `.*`. Every
extra `*` multiplies the work by the text length. It is used by
COUNTIF/SUMIF/AVERAGEIF and the *IFS functions, by the D* functions
(DStarRunner) and by MATCH/VLOOKUP/HLOOKUP/XLOOKUP/XMATCH (LookupUtils).
2. `OperandResolver.fpPattern` has `(\d+)(\.)?((\d+)?)`. Without a `.`, a
run of digits can be split between the two groups in many ways.
3. `Imaginary.COMPLEX_NUMBER_PATTERN` (also used by ImReal) has the same
kind of ambiguity: `([0-9]+\.[0-9]+|[0-9]*)([+-]?)([0-9]+\.[0-9]+|[0-9]*)`.
## Fix
The goal is to change nothing about what POI returns, even for garbage input.
1. A new package-private `WildcardMatcher` simulates the wildcard as an NFA:
O(text length x criteria length), no backtracking. It copies the regex's
semantics exactly. It works on code points (a surrogate pair is one `?`). Case
folding is ASCII-only, as with `CASE_INSENSITIVE` without `UNICODE_CASE`. `?`
and `*` do not match `\n`, `\r`, `\u0085`, `\u2028` or `\u2029`, as with `.`
without `DOTALL`. The `~` escapes are handled the same way, and it returns
`null` in the same cases (no wildcard). Countif, DStarRunner and LookupUtils
now use it. The public `getWildCardPattern` is unchanged and still used for
`StringMatcher.toString()`.
2. The number regex now uses possessive quantifiers. Each part can only end
where the next one starts, so the set of accepted strings does not change. Only
`matches()` is used, never the groups.
3. `Imaginary.parseComplexNumber` (package-private) replaces the regex in
IMAGINARY and IMREAL. It returns all 6 groups. It tries the same splits in the
same order as the regex's backtracking, and checks each in constant time using
a precomputed digit-run table. This keeps quirks such as `1.11.1i` matching as
real `1.1` plus imaginary `1.1i`. The public pattern and group constants are
kept.
No public API is added or changed.
## Equivalence checks (old vs new, exhaustive)
- Wildcards: compared `getWildCardPattern(p).matcher(t).matches()` with
`WildcardMatcher.compile(p).matches(t)`, including whether both return null.
742M (criteria, text) pairs, 0 mismatches:
- criteria from `aA*?~.` up to length 5 x text from `aAb\n.*` up to length
6: 460M pairs
- criteria from `a * ? ~ <high surrogate> <low surrogate>` up to length 5
x text from `a <high> <low> \r \u0085 \u2028 *` up to length 5: 161M pairs.
This covers surrogate pairs and lone surrogates.
- criteria from `bZ*?~\[é` up to length 4 x text from `bzZ \u2029 ?~\É` up
to length 5: 121M pairs
- Number regex: compared old and new `matches()` on 133M strings, 0
mismatches. The alphabets were `1.eE+- x\u0001` up to length 8, `1.e+- ` up to
length 10, and `1.e\u0663\t-` up to length 9.
- Complex numbers: compared old `matches()` plus groups 0-5 with the new
parser on 179M strings, 0 mismatches. The alphabets were `1.+-ijx` up to length
9, `10.+-ij x` up to length 8, `1.-i` up to length 12, and `12.+i` up to length
11.
## Timings (new)
| Input | Old | New |
|---|---|---|
| `*a*a*c` vs `a`x2000+`b` | 146 s | 3 ms |
| `*a*a*a*a*c` vs `a`x32767+`b` | (not run) | 169 ms |
| parseDouble `1`x20000+`x` | 204 s | 6 ms |
| IMAGINARY `1`x20000+`x` | 92 s | 22 ms |
## Tests
New tests use `assertTimeoutPreemptively(10 s)` and also assert the result:
- `TestCountFuncs.testWildCardsDoNotTakeExponentialTime`
- `TestMatch.testWildCardsDoNotTakeExponentialTime`
- `TestDCount.testWildCardsDoNotTakeExponentialTime`
- `TestOperandResolver.testParseDoubleLongNonNumericText`
- `TestImaginary.testLongNonComplexText` (new class)
All five time out on trunk and pass with this change.
`TestCountFuncs.testWildCardsWithSeveralAsterisks` and
`TestImaginary.testParts` pass both before and after.
Targeted runs, all passing:
- TestCountFuncs, TestMatch, TestDCount, TestDCountA, TestDGet,
TestDAverage, TestDProduct, TestDStdev, TestDVar
- TestDStarFunctionsFromSpreadsheet, TestDGetFunctionsFromSpreadsheet
- TestSumif, TestSumifs, TestAverageIf, TestAverageifs, TestMaxifs,
TestMinifs, atp.TestIfs
- TestLookupFunctionsFromSpreadsheet, TestMatchFunctionsFromSpreadsheet,
atp.TestXLookupFunction, atp.TestXMatchFunction
- TestOperandResolver, TestValue
- TestImaginary, TestImaginaryFunctionsFromSpreadsheet,
TestImRealFunctionsFromSpreadsheet, TestComplex
🤖 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]
