You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@poi.apache.org by fa...@apache.org on 2026/10/18 10:15:25 UTC
(poi) branch trunk updated: Formula evaluation: avoid regex backtracking in wildcard criteria, number parsing and IMAGINARY/IMREAL (#1441)
This is an automated email from the ASF dual-hosted git repository.
pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git
The following commit(s) were added to refs/heads/trunk by this push:
new e9e51e10a6 Formula evaluation: avoid regex backtracking in wildcard criteria, number parsing and IMAGINARY/IMREAL (#1441)
e9e51e10a6 is described below
commit e9e51e10a6daba723b293d2a775308d18565f0b3
Author: PJ Fanning <pj...@users.noreply.github.com>
AuthorDate: Sun Oct 18 11:15:18 2026 +0100
Formula evaluation: avoid regex backtracking in wildcard criteria, number parsing and IMAGINARY/IMREAL (#1441)
Formula evaluation: avoid exponential/polynomial regex backtracking in wildcard criteria, number parsing and complex numbers
- COUNTIF/SUMIF/AVERAGEIF/*IFS, D* functions and MATCH/VLOOKUP/HLOOKUP/XLOOKUP
matched wildcard criteria with a regex built from '*' -> '.*', which
backtracks exponentially in the number of '*'. Use a new package-private
WildcardMatcher (NFA simulation, O(text * criteria)) with the same
semantics: code points, ASCII-only case folding, '?' and '*' not
matching line terminators, same '~' escapes. getWildCardPattern is kept.
- OperandResolver.parseDouble: make the number regex possessive; it accepts
the same text.
- IMAGINARY/IMREAL: replace COMPLEX_NUMBER_PATTERN matching with a parser
that tries the same splits in the same order as the regex, so the groups
are identical. The public pattern constants are kept.
Co-authored-by: Claude Opus 5.5 <no...@anthropic.com>
---
.../poi/ss/formula/eval/OperandResolver.java | 15 +-
.../apache/poi/ss/formula/functions/Countif.java | 14 +-
.../poi/ss/formula/functions/DStarRunner.java | 7 +-
.../apache/poi/ss/formula/functions/ImReal.java | 12 +-
.../apache/poi/ss/formula/functions/Imaginary.java | 107 +++++++++++++-
.../poi/ss/formula/functions/LookupUtils.java | 13 +-
.../poi/ss/formula/functions/WildcardMatcher.java | 159 +++++++++++++++++++++
.../poi/ss/formula/eval/TestOperandResolver.java | 14 ++
.../poi/ss/formula/functions/TestCountFuncs.java | 30 ++++
.../poi/ss/formula/functions/TestDCount.java | 19 +++
.../poi/ss/formula/functions/TestImaginary.java | 69 +++++++++
.../apache/poi/ss/formula/functions/TestMatch.java | 17 +++
12 files changed, 436 insertions(+), 40 deletions(-)
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/eval/OperandResolver.java b/poi/src/main/java/org/apache/poi/ss/formula/eval/OperandResolver.java
index cc4c6be022..03cf97caa2 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/eval/OperandResolver.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/eval/OperandResolver.java
@@ -34,14 +34,17 @@ public final class OperandResolver {
// Based on regular expression defined in JavaDoc at {@link java.lang.Double#valueOf}
// modified to remove support for NaN, Infinity, Hexadecimal support and floating type suffixes
- private static final String Digits = "(\\p{Digit}+)";
- private static final String Exp = "[eE][+-]?"+Digits;
+ // The quantifiers are possessive: "digits, optional '.', optional digits" could otherwise split a run
+ // of digits in many ways, and text that is not a number made matches() take polynomial time.
+ // Each part can only end where the next one starts, so this accepts the same text.
+ private static final String Digits = "\\p{Digit}++";
+ private static final String Exp = "([eE][+-]?"+Digits+")?+";
private static final String fpRegex =
- ("[\\x00-\\x20]*" +
+ ("[\\x00-\\x20]*+" +
"[+-]?(" +
- "("+Digits+"(\\.)?("+Digits+"?)("+Exp+")?)|"+
- "(\\."+Digits+"("+Exp+")?))"+
- "[\\x00-\\x20]*");
+ "("+Digits+"(\\.\\p{Digit}*+)?+"+Exp+")|"+
+ "(\\."+Digits+Exp+"))"+
+ "[\\x00-\\x20]*+");
private static final Pattern fpPattern = Pattern.compile(fpRegex);
private OperandResolver() {
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/Countif.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/Countif.java
index 7ee32478cc..0baad8453d 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/Countif.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/Countif.java
@@ -288,23 +288,23 @@ public final class Countif extends Fixed2ArgFunction implements ArrayFunction {
public static final class StringMatcher extends MatcherBase {
private final String _value;
- private final Pattern _pattern;
+ private final WildcardMatcher _wildCardMatcher;
public StringMatcher(String value, CmpOp operator) {
super(operator);
_value = value;
- _pattern = switch (operator.getCode()) {
- case CmpOp.NONE, CmpOp.EQ, CmpOp.NE -> getWildCardPattern(value);
+ _wildCardMatcher = switch (operator.getCode()) {
+ case CmpOp.NONE, CmpOp.EQ, CmpOp.NE -> WildcardMatcher.compile(value);
// pattern matching is never used for < > <= =>
default -> null;
};
}
@Override
protected String getValueText() {
- if (_pattern == null) {
+ if (_wildCardMatcher == null) {
return _value;
}
- return _pattern.pattern();
+ return getWildCardPattern(_value).pattern();
}
@Override
@@ -340,8 +340,8 @@ public final class Countif extends Fixed2ArgFunction implements ArrayFunction {
default -> false;
};
}
- if (_pattern != null) {
- return evaluate(_pattern.matcher(testedValue).matches());
+ if (_wildCardMatcher != null) {
+ return evaluate(_wildCardMatcher.matches(testedValue));
}
// String criteria in COUNTIF are case insensitive:
// for example, the string "apples" and the string "APPLES" will match the same cells.
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/DStarRunner.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/DStarRunner.java
index 0285c763d5..e9ab844c20 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/DStarRunner.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/DStarRunner.java
@@ -18,7 +18,6 @@
package org.apache.poi.ss.formula.functions;
import java.util.function.Supplier;
-import java.util.regex.Pattern;
import org.apache.poi.ss.formula.eval.AreaEval;
import org.apache.poi.ss.formula.eval.BlankEval;
@@ -351,11 +350,11 @@ public final class DStarRunner implements Function3Arg {
String valueString = value instanceof BlankEval ? "" : OperandResolver.coerceValueToString(value);
final String lowerValue = valueString.toLowerCase(LocaleUtil.getUserLocale());
final String lowerCondition = conditionString.toLowerCase(LocaleUtil.getUserLocale());
- final Pattern pattern = Countif.StringMatcher.getWildCardPattern(lowerCondition);
- if (pattern == null) {
+ final WildcardMatcher wildCardMatcher = WildcardMatcher.compile(lowerCondition);
+ if (wildCardMatcher == null) {
return lowerValue.startsWith(lowerCondition);
} else {
- return pattern.matcher(lowerValue).matches();
+ return wildCardMatcher.matches(lowerValue);
}
}
}
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/ImReal.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/ImReal.java
index 024fb119db..26b59fd40b 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/ImReal.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/ImReal.java
@@ -17,8 +17,6 @@
package org.apache.poi.ss.formula.functions;
-import java.util.regex.Matcher;
-
import org.apache.poi.ss.formula.OperationEvaluationContext;
import org.apache.poi.ss.formula.eval.ErrorEval;
import org.apache.poi.ss.formula.eval.EvaluationException;
@@ -55,18 +53,18 @@ public class ImReal extends Fixed1ArgFunction implements FreeRefFunction {
}
String iNumber = OperandResolver.coerceValueToString(veText1);
- Matcher m = Imaginary.COMPLEX_NUMBER_PATTERN.matcher(iNumber);
- if (!m.matches()) {
+ String[] groups = Imaginary.parseComplexNumber(iNumber);
+ if (groups == null) {
return ErrorEval.NUM_ERROR;
}
- String realGroup = m.group(2);
+ String realGroup = groups[2];
if (realGroup.isEmpty()) {
return new StringEval("0");
}
- String realSign = m.group(Imaginary.GROUP1_REAL_SIGN);
- String groupRealNumber = m.group(Imaginary.GROUP2_IMAGINARY_INTEGER_OR_DOUBLE);
+ String realSign = groups[Imaginary.GROUP1_REAL_SIGN];
+ String groupRealNumber = groups[Imaginary.GROUP2_IMAGINARY_INTEGER_OR_DOUBLE];
String sign = "+".equals(realSign) ? "" : realSign;
String real = groupRealNumber.isEmpty() ? "1" : groupRealNumber;
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/Imaginary.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/Imaginary.java
index f478c95d5b..51bfc9859f 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/Imaginary.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/Imaginary.java
@@ -20,7 +20,6 @@ package org.apache.poi.ss.formula.functions;
import org.apache.poi.ss.formula.OperationEvaluationContext;
import org.apache.poi.ss.formula.eval.*;
-import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
@@ -66,12 +65,11 @@ public class Imaginary extends Fixed1ArgFunction implements FreeRefFunction {
}
String iNumber = OperandResolver.coerceValueToString(veText1);
- Matcher m = COMPLEX_NUMBER_PATTERN.matcher(iNumber);
- boolean result = m.matches();
+ String[] groups = parseComplexNumber(iNumber);
String imaginary = "";
- if (result) {
- String imaginaryGroup = m.group(5);
+ if (groups != null) {
+ String imaginaryGroup = groups[5];
boolean hasImaginaryPart = imaginaryGroup.equals("i") || imaginaryGroup.equals("j");
if (imaginaryGroup.isEmpty()) {
@@ -80,12 +78,12 @@ public class Imaginary extends Fixed1ArgFunction implements FreeRefFunction {
if (hasImaginaryPart) {
String sign = "";
- String imaginarySign = m.group(GROUP3_IMAGINARY_SIGN);
+ String imaginarySign = groups[GROUP3_IMAGINARY_SIGN];
if (imaginarySign.length() != 0 && !(imaginarySign.equals("+"))) {
sign = imaginarySign;
}
- String groupImaginaryNumber = m.group(GROUP4_IMAGINARY_INTEGER_OR_DOUBLE);
+ String groupImaginaryNumber = groups[GROUP4_IMAGINARY_INTEGER_OR_DOUBLE];
if (groupImaginaryNumber.length() != 0) {
imaginary = sign + groupImaginaryNumber;
} else {
@@ -99,6 +97,101 @@ public class Imaginary extends Fixed1ArgFunction implements FreeRefFunction {
return new StringEval(imaginary);
}
+ /**
+ * Gives the same result as matching {@link #COMPLEX_NUMBER_PATTERN}, without the regular expression:
+ * its groups can split a run of digits in many ways, so matching text that is not a complex number
+ * took polynomial time. This tries the same splits in the same order as the regular expression
+ * backtracking does, but checks each one in constant time.
+ *
+ * @return the groups that {@link java.util.regex.Matcher#group(int)} would return, indexed by group number
+ * (index 0 is the whole text), or {@code null} if the text does not match the pattern
+ */
+ static String[] parseComplexNumber(String text) {
+ int n = text.length();
+ // digitsEnd[i] is the end of the run of digits that starts at i
+ int[] digitsEnd = new int[n + 1];
+ digitsEnd[n] = n;
+ for (int i = n - 1; i >= 0; i--) {
+ digitsEnd[i] = isDigit(text.charAt(i)) ? digitsEnd[i + 1] : i;
+ }
+ // group 1: [+-]? tries the sign first
+ boolean hasRealSign = n > 0 && isSign(text.charAt(0));
+ for (int realStart = hasRealSign ? 1 : 0; realStart >= 0; realStart--) {
+ // group 2: [0-9]+\.[0-9]+ with fewer and fewer digits after the '.', then [0-9]* with fewer and fewer digits
+ int pointEnd = decimalPointEnd(text, realStart, digitsEnd);
+ if (pointEnd >= 0) {
+ for (int realEnd = digitsEnd[pointEnd]; realEnd > pointEnd; realEnd--) {
+ String[] groups = parseImaginaryPart(text, realStart, realEnd, digitsEnd);
+ if (groups != null) {
+ return groups;
+ }
+ }
+ }
+ for (int realEnd = digitsEnd[realStart]; realEnd >= realStart; realEnd--) {
+ String[] groups = parseImaginaryPart(text, realStart, realEnd, digitsEnd);
+ if (groups != null) {
+ return groups;
+ }
+ }
+ }
+ return null;
+ }
+
+ /** groups 3 to 5, for groups 1 and 2 ending at {@code realStart} and {@code realEnd} */
+ private static String[] parseImaginaryPart(String text, int realStart, int realEnd, int[] digitsEnd) {
+ int n = text.length();
+ // group 3: [+-]? tries the sign first
+ boolean hasImaginarySign = realEnd < n && isSign(text.charAt(realEnd));
+ for (int imaginaryStart = hasImaginarySign ? realEnd + 1 : realEnd; imaginaryStart >= realEnd; imaginaryStart--) {
+ // group 4 is followed by [ij]? and the end of the text, and neither starts with a digit,
+ // so of all the ways group 4 can match, only the longest one of each alternative can succeed
+ int imaginaryEnd = -1;
+ int pointEnd = decimalPointEnd(text, imaginaryStart, digitsEnd);
+ if (pointEnd >= 0 && isImaginaryUnitAndEnd(text, digitsEnd[pointEnd])) {
+ imaginaryEnd = digitsEnd[pointEnd];
+ } else if (isImaginaryUnitAndEnd(text, digitsEnd[imaginaryStart])) {
+ imaginaryEnd = digitsEnd[imaginaryStart];
+ }
+ if (imaginaryEnd >= 0) {
+ return new String[] {
+ text,
+ text.substring(0, realStart),
+ text.substring(realStart, realEnd),
+ text.substring(realEnd, imaginaryStart),
+ text.substring(imaginaryStart, imaginaryEnd),
+ text.substring(imaginaryEnd)
+ };
+ }
+ }
+ return null;
+ }
+
+ /**
+ * @return the index after the '.' if {@code [0-9]+\.[0-9]} matches at {@code start}, otherwise -1
+ */
+ private static int decimalPointEnd(String text, int start, int[] digitsEnd) {
+ int pointIndex = digitsEnd[start];
+ if (pointIndex > start && pointIndex + 1 < text.length() && text.charAt(pointIndex) == '.'
+ && isDigit(text.charAt(pointIndex + 1))) {
+ return pointIndex + 1;
+ }
+ return -1;
+ }
+
+ /** whether {@code ([ij]?)} followed by the end of the text matches at {@code index} */
+ private static boolean isImaginaryUnitAndEnd(String text, int index) {
+ int n = text.length();
+ return index == n || (index == n - 1 && (text.charAt(index) == 'i' || text.charAt(index) == 'j'));
+ }
+
+ private static boolean isDigit(char ch) {
+ return ch >= '0' && ch <= '9';
+ }
+
+ private static boolean isSign(char ch) {
+ return ch == '+' || ch == '-';
+ }
+
@Override
public ValueEval evaluate(ValueEval[] args, OperationEvaluationContext ec) {
if (args.length != 1) {
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
index bc8a7860da..fbe58a827c 100644
--- a/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/LookupUtils.java
@@ -23,8 +23,6 @@ import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
import org.apache.poi.ss.formula.TwoDEval;
import org.apache.poi.ss.formula.eval.BlankEval;
@@ -390,14 +388,14 @@ public final class LookupUtils {
private static class StringLookupComparer extends LookupValueComparerBase {
protected final String _value;
- protected final Pattern _wildCardPattern;
+ protected final WildcardMatcher _wildCardMatcher;
protected final boolean _matchExact;
protected final boolean _isMatchFunction;
protected StringLookupComparer(StringEval se, boolean matchExact, boolean isMatchFunction) {
super(se);
_value = se.getStringValue();
- _wildCardPattern = Countif.StringMatcher.getWildCardPattern(_value);
+ _wildCardMatcher = WildcardMatcher.compile(_value);
_matchExact = matchExact;
_isMatchFunction = isMatchFunction;
}
@@ -410,11 +408,8 @@ public final class LookupUtils {
@Override
protected CompareResult compareSameType(ValueEval other) {
String stringValue = convertToString(other);
- if (_wildCardPattern != null && (_isMatchFunction || !_matchExact)) {
- Matcher matcher = _wildCardPattern.matcher(stringValue);
- boolean matches = matcher.matches();
-
- return CompareResult.valueOf(matches);
+ if (_wildCardMatcher != null && (_isMatchFunction || !_matchExact)) {
+ return CompareResult.valueOf(_wildCardMatcher.matches(stringValue));
}
return CompareResult.valueOf(_value.compareToIgnoreCase(stringValue));
diff --git a/poi/src/main/java/org/apache/poi/ss/formula/functions/WildcardMatcher.java b/poi/src/main/java/org/apache/poi/ss/formula/functions/WildcardMatcher.java
new file mode 100644
index 0000000000..9245f82cbe
--- /dev/null
+++ b/poi/src/main/java/org/apache/poi/ss/formula/functions/WildcardMatcher.java
@@ -0,0 +1,159 @@
+/* ====================================================================
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+==================================================================== */
+
+package org.apache.poi.ss.formula.functions;
+
+import java.util.Arrays;
+
+/**
+ * Matches text against an Excel wildcard criteria ({@code ?}, {@code *} and the {@code ~} escape).
+ * <p>
+ * This gives the same result as matching against {@link Countif.StringMatcher#getWildCardPattern(String)},
+ * but in O(text length * criteria length) time. The regular expression backtracks, so criteria with
+ * several {@code *} could take exponential time.
+ * <p>
+ * Like that regular expression, it works on code points, folds only ASCII letters when comparing, and
+ * {@code ?} and {@code *} do not match line terminators.
+ */
+final class WildcardMatcher {
+ /** token for {@code ?}: exactly one character */
+ private static final int ANY_CHAR = -1;
+ /** token for {@code *}: zero or more characters */
+ private static final int ANY_CHARS = -2;
+
+ /** literal code points (ASCII folded to lower case), {@link #ANY_CHAR} or {@link #ANY_CHARS} */
+ private final int[] _tokens;
+
+ private WildcardMatcher(int[] tokens) {
+ _tokens = tokens;
+ }
+
+ /**
+ * Parses Excel wildcard criteria.
+ * @return {@code null} if the specified value contains no special wildcard characters
+ * (the same cases where {@link Countif.StringMatcher#getWildCardPattern(String)} returns {@code null}).
+ */
+ static WildcardMatcher compile(String value) {
+ int len = value.length();
+ int[] tokens = new int[len];
+ int count = 0;
+ boolean hasWildCard = false;
+ for (int i = 0; i < len; i++) {
+ char ch = value.charAt(i);
+ switch (ch) {
+ case '?':
+ hasWildCard = true;
+ tokens[count++] = ANY_CHAR;
+ continue;
+ case '*':
+ hasWildCard = true;
+ tokens[count++] = ANY_CHARS;
+ continue;
+ case '~':
+ if (i + 1 < len) {
+ char next = value.charAt(i + 1);
+ if (next == '?' || next == '*' || next == '~') {
+ // '~' escapes the wildcards and itself
+ hasWildCard = true;
+ tokens[count++] = next;
+ i++;
+ continue;
+ }
+ }
+ // else just plain '~'
+ tokens[count++] = ch;
+ continue;
+ }
+ int cp = ch;
+ if (Character.isHighSurrogate(ch) && i + 1 < len && Character.isLowSurrogate(value.charAt(i + 1))) {
+ cp = Character.toCodePoint(ch, value.charAt(i + 1));
+ i++;
+ }
+ tokens[count++] = toLowerAscii(cp);
+ }
+ if (!hasWildCard) {
+ return null;
+ }
+ int[] trimmed = new int[count];
+ System.arraycopy(tokens, 0, trimmed, 0, count);
+ return new WildcardMatcher(trimmed);
+ }
+
+ /**
+ * @return {@code true} if the whole of {@code text} matches the criteria
+ */
+ boolean matches(String text) {
+ final int[] tokens = _tokens;
+ final int n = tokens.length;
+ // states[j] is set when the first j tokens match the text read so far
+ boolean[] states = new boolean[n + 1];
+ boolean[] nextStates = new boolean[n + 1];
+ states[0] = true;
+ skipAnyChars(states);
+ int len = text.length();
+ for (int i = 0; i < len; ) {
+ int cp = text.codePointAt(i);
+ i += Character.charCount(cp);
+ int lowerCp = toLowerAscii(cp);
+ boolean lineTerminator = isLineTerminator(cp);
+ boolean any = false;
+ for (int j = 0; j < n; j++) {
+ if (!states[j]) {
+ continue;
+ }
+ int token = tokens[j];
+ if (token == ANY_CHARS) {
+ if (!lineTerminator) {
+ nextStates[j] = true;
+ any = true;
+ }
+ } else if (token == ANY_CHAR ? !lineTerminator : token == lowerCp) {
+ nextStates[j + 1] = true;
+ any = true;
+ }
+ }
+ if (!any) {
+ return false;
+ }
+ skipAnyChars(nextStates);
+ boolean[] tmp = states;
+ states = nextStates;
+ nextStates = tmp;
+ Arrays.fill(nextStates, false);
+ }
+ return states[n];
+ }
+
+ /** a {@code *} can match nothing, so a state before one implies the state after it */
+ private void skipAnyChars(boolean[] states) {
+ for (int j = 0; j < _tokens.length; j++) {
+ if (states[j] && _tokens[j] == ANY_CHARS) {
+ states[j + 1] = true;
+ }
+ }
+ }
+
+ /** the characters that {@code .} in a regular expression does not match */
+ private static boolean isLineTerminator(int cp) {
+ return cp == '\n' || cp == '\r' || cp == '\u0085' || cp == '\u2028' || cp == '\u2029';
+ }
+
+ /** case folding as done by {@link java.util.regex.Pattern#CASE_INSENSITIVE} without UNICODE_CASE */
+ private static int toLowerAscii(int cp) {
+ return (cp >= 'A' && cp <= 'Z') ? cp + ('a' - 'A') : cp;
+ }
+}
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/eval/TestOperandResolver.java b/poi/src/test/java/org/apache/poi/ss/formula/eval/TestOperandResolver.java
index db03115cb3..ed0321d531 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/eval/TestOperandResolver.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/eval/TestOperandResolver.java
@@ -21,8 +21,10 @@ import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.fail;
+import java.time.Duration;
import java.util.LinkedHashMap;
import java.util.Map;
@@ -141,6 +143,18 @@ final class TestOperandResolver {
assertEquals(Double.MAX_VALUE, OperandResolver.parseDouble("1.7976931348623157E308"), 0);
}
+ @Test
+ void testParseDoubleLongNonNumericText() {
+ // the number regular expression used to backtrack over the ways to split the digits,
+ // which took minutes for this text
+ String digits = "1".repeat(20000);
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ assertNull(OperandResolver.parseDouble(digits + "x"));
+ assertNull(OperandResolver.parseDouble(digits + "." + digits + "e"));
+ assertEquals(1.25, OperandResolver.parseDouble(" 1.25" + "0".repeat(20000) + " "), 0);
+ });
+ }
+
@Test
void testCoerceDoubleToInt() throws EvaluationException {
assertEquals(2, OperandResolver.coerceDoubleToInt(2.9));
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestCountFuncs.java b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestCountFuncs.java
index 48e3726983..7f8ebeefcc 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestCountFuncs.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestCountFuncs.java
@@ -21,9 +21,11 @@ import static org.apache.poi.ss.util.Utils.assertDouble;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.io.IOException;
+import java.time.Duration;
import org.apache.poi.hssf.HSSFTestDataSamples;
import org.apache.poi.hssf.usermodel.HSSFCell;
@@ -606,6 +608,34 @@ final class TestCountFuncs {
confirmPredicate(false, mp, "a~~*");
}
+ @Test
+ void testWildCardsWithSeveralAsterisks() {
+ I_MatchPredicate mp = createCriteriaPredicate(new StringEval("*a*b*c"));
+ confirmPredicate(true, mp, "abc");
+ confirmPredicate(true, mp, "xAxBxC");
+ confirmPredicate(false, mp, "xAxBxCx");
+ confirmPredicate(true, mp, "cbaabc");
+ confirmPredicate(false, mp, "cba");
+
+ mp = createCriteriaPredicate(new StringEval("a*?b"));
+ confirmPredicate(false, mp, "ab");
+ confirmPredicate(true, mp, "axb");
+ confirmPredicate(true, mp, "abbb");
+ }
+
+ @Test
+ void testWildCardsDoNotTakeExponentialTime() {
+ // the criteria used to be matched with a backtracking regular expression,
+ // which took minutes for this text: each '*' multiplied the work by the text length
+ String text = "a".repeat(2000) + "b";
+ I_MatchPredicate noMatch = createCriteriaPredicate(new StringEval("*a*a*c"));
+ I_MatchPredicate match = createCriteriaPredicate(new StringEval("*A*a*B"));
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ confirmPredicate(false, noMatch, text);
+ confirmPredicate(true, match, text);
+ });
+ }
+
@Test
void testWildCardsWithRegexMetaCharactersInWorkbook() throws IOException {
// the reporter's steps for bug 69878
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestDCount.java b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestDCount.java
index ea4d79e5fe..0b8e9601cf 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestDCount.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestDCount.java
@@ -24,9 +24,11 @@ import org.apache.poi.hssf.usermodel.HSSFWorkbook;
import org.junit.jupiter.api.Test;
import java.io.IOException;
+import java.time.Duration;
import static org.apache.poi.ss.util.Utils.addRow;
import static org.apache.poi.ss.util.Utils.assertDouble;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
/**
* Testcase for function DCOUNT()
@@ -51,6 +53,23 @@ public class TestDCount {
}
}
+ @Test
+ void testWildCardsDoNotTakeExponentialTime() throws IOException {
+ // text criteria used to be matched with a backtracking regular expression,
+ // which took minutes for this text
+ try (HSSFWorkbook wb = new HSSFWorkbook()) {
+ HSSFSheet sheet = wb.createSheet();
+ addRow(sheet, 0, "Name", "Value", null, "Name", "Name");
+ addRow(sheet, 1, "a".repeat(2000) + "b", 1, null, "*a*a*c", "*a*a*b");
+ HSSFFormulaEvaluator fe = new HSSFFormulaEvaluator(wb);
+ HSSFCell cell = sheet.getRow(0).createCell(100);
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ assertDouble(fe, cell, "DCOUNT(A1:B2, \"Value\", D1:D2)", 0);
+ assertDouble(fe, cell, "DCOUNT(A1:B2, \"Value\", E1:E2)", 1);
+ });
+ }
+ }
+
private HSSFWorkbook initWorkbook1() {
HSSFWorkbook wb = new HSSFWorkbook();
HSSFSheet sheet = wb.createSheet();
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestImaginary.java b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestImaginary.java
new file mode 100644
index 0000000000..333038a3d4
--- /dev/null
+++ b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestImaginary.java
@@ -0,0 +1,69 @@
+/* ====================================================================
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+==================================================================== */
+
+package org.apache.poi.ss.formula.functions;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+
+import java.time.Duration;
+
+import org.apache.poi.ss.formula.eval.ErrorEval;
+import org.apache.poi.ss.formula.eval.StringEval;
+import org.apache.poi.ss.formula.eval.ValueEval;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Tests for IMAGINARY() and IMREAL()
+ */
+final class TestImaginary {
+
+ private static ValueEval imaginary(String text) {
+ return new Imaginary().evaluate(-1, -1, new StringEval(text));
+ }
+
+ private static ValueEval imReal(String text) {
+ return new ImReal().evaluate(-1, -1, new StringEval(text));
+ }
+
+ @Test
+ void testParts() {
+ assertEquals("4", ((StringEval) imaginary("3+4i")).getStringValue());
+ assertEquals("3", ((StringEval) imReal("3+4i")).getStringValue());
+ assertEquals("-4.5", ((StringEval) imaginary("-3.25-4.5j")).getStringValue());
+ assertEquals("-3.25", ((StringEval) imReal("-3.25-4.5j")).getStringValue());
+ assertEquals("1", ((StringEval) imaginary("i")).getStringValue());
+ assertEquals("0", ((StringEval) imaginary("12")).getStringValue());
+ assertEquals("12", ((StringEval) imReal("12")).getStringValue());
+ // the real part can end inside a run of digits: "1.1" and "1.1i"
+ assertEquals("1.1", ((StringEval) imaginary("1.11.1i")).getStringValue());
+ assertEquals("1.1", ((StringEval) imReal("1.11.1i")).getStringValue());
+ assertEquals(ErrorEval.NUM_ERROR, imaginary("1x"));
+ assertEquals(ErrorEval.NUM_ERROR, imReal("1+2k"));
+ }
+
+ @Test
+ void testLongNonComplexText() {
+ // the complex number regular expression used to backtrack over the ways to split the digits,
+ // which took minutes for this text
+ String text = "1".repeat(20000) + "x";
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ assertEquals(ErrorEval.NUM_ERROR, imaginary(text));
+ assertEquals(ErrorEval.NUM_ERROR, imReal(text));
+ });
+ }
+}
diff --git a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestMatch.java b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestMatch.java
index c627947b0d..5dc8afad39 100644
--- a/poi/src/test/java/org/apache/poi/ss/formula/functions/TestMatch.java
+++ b/poi/src/test/java/org/apache/poi/ss/formula/functions/TestMatch.java
@@ -19,9 +19,12 @@ package org.apache.poi.ss.formula.functions;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertInstanceOf;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.fail;
+import java.time.Duration;
+
import org.apache.poi.ss.formula.eval.AreaEval;
import org.apache.poi.ss.formula.eval.BoolEval;
import org.apache.poi.ss.formula.eval.ErrorEval;
@@ -236,6 +239,20 @@ final class TestMatch {
}
+ @Test
+ void testWildCardsDoNotTakeExponentialTime() {
+ // the lookup value used to be matched with a backtracking regular expression,
+ // which took minutes for this text
+ AreaEval ae = EvalFactory.createAreaEval("A1:A2", new ValueEval[] {
+ new StringEval("x"),
+ new StringEval("a".repeat(2000) + "b"),
+ });
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ assertEquals(ErrorEval.NA, invokeMatch(new StringEval("*a*a*c"), ae, MATCH_EXACT));
+ confirmInt(2, invokeMatch(new StringEval("*a*a*b"), ae, MATCH_EXACT));
+ });
+ }
+
/**
* Ensures that the match_type argument can be an {@code AreaEval}.<br>
* Bugzilla 44421
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@poi.apache.org
For additional commands, e-mail: commits-help@poi.apache.org