This is an automated email from the ASF dual-hosted git repository. rzo1 pushed a commit to branch fix/degrees-lat-lon-pattern in repository https://gitbox.apache.org/repos/asf/opennlp.git
commit fecf890687c47e5aafe149f174a4452fe99de567 Author: Richard Zowalla <[email protected]> AuthorDate: Mon Nov 2 10:50:33 2026 +0100 Bound whitespace backtracking in the DEGREES_MIN_SEC_LAT_LON pattern The whitespace quantifiers of the DEGREES_MIN_SEC_LAT_LON pattern are now possessive, so a long run of whitespace after a digit is scanned once instead of being re-partitioned between adjacent quantifiers. The pattern finds the same spans as before, which new tests check against the previous pattern on coordinate strings and a seeded random corpus. The timing tests for the built-in patterns now also cover long whitespace runs matched on the raw text. --- .../tools/namefind/RegexNameFinderFactory.java | 14 +- .../tools/namefind/RegexNameFinderFactoryTest.java | 155 ++++++++++++++++++++- 2 files changed, 162 insertions(+), 7 deletions(-) diff --git a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/namefind/RegexNameFinderFactory.java b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/namefind/RegexNameFinderFactory.java index 3f8e798ec..a3d676873 100644 --- a/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/namefind/RegexNameFinderFactory.java +++ b/opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/namefind/RegexNameFinderFactory.java @@ -185,9 +185,17 @@ public class RegexNameFinderFactory { @SuppressForbidden("default patterns of the regex name finder") public Map<String, Pattern[]> getRegexMap() { Pattern[] p = new Pattern[1]; - p[0] = Pattern.compile("([-|\\+]?\\d{1,3}[d|D|\\u00B0|\\s](\\s*\\d{1,2}['|\\u2019|\\s])" + - "?(\\s*\\d{1,2}[\\\"|\\u201d])?\\s*[N|n|S|s]?)(\\s*|,|,\\s*)([-|\\+]?\\d{1,3}[d|D|\\u00B0|" + - "\\s](\\s*\\d{1,2}['|\\u2019|\\s])?(\\s*\\d{1,2}[\\\"|\\u201d])?\\s*[E|e|W|w]?)", + // Every whitespace run is consumed possessively (\s*+), so a long run of whitespace + // is scanned once instead of being re-partitioned between adjacent \s* quantifiers, + // and matching stays linear in the input length. This finds exactly the same spans + // as the greedy form: giving whitespace back never helps, because each \s*+ is + // followed by a digit, by the optional tail of the pattern, or by an optional + // hemisphere letter and a separator whose own \s*+ would re-consume the given-back + // whitespace and reach a state that was already tried. + p[0] = Pattern.compile("([-|\\+]?\\d{1,3}[d|D|\\u00B0|\\s](\\s*+\\d{1,2}['|\\u2019|\\s])" + + "?(\\s*+\\d{1,2}[\\\"|\\u201d])?\\s*+[N|n|S|s]?)(\\s*+|,|,\\s*+)([-|\\+]?\\d{1,3}" + + "[d|D|\\u00B0|\\s](\\s*+\\d{1,2}['|\\u2019|\\s])?(\\s*+\\d{1,2}[\\\"|\\u201d])?" + + "\\s*+[E|e|W|w]?)", Pattern.CASE_INSENSITIVE); Map<String, Pattern[]> regexMap = new HashMap<>(); regexMap.put(getType(), p); diff --git a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/namefind/RegexNameFinderFactoryTest.java b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/namefind/RegexNameFinderFactoryTest.java index 9bc72dbb2..c4be25348 100644 --- a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/namefind/RegexNameFinderFactoryTest.java +++ b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/namefind/RegexNameFinderFactoryTest.java @@ -18,14 +18,19 @@ package opennlp.tools.namefind; import java.time.Duration; +import java.util.ArrayList; import java.util.Arrays; import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.regex.Pattern; import java.util.stream.Stream; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.BeforeEach; import org.junit.jupiter.api.Named; import org.junit.jupiter.api.Test; +import org.junit.jupiter.api.function.Executable; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; @@ -121,11 +126,153 @@ public class RegexNameFinderFactoryTest { @MethodSource("reDoSAttacks") void testBuiltinPatternsAreNotVulnerableToReDoS(String attack) { String[] tokens = WhitespaceTokenizer.INSTANCE.tokenize(attack); - // Warmup: JIT-compile the pattern engine before the timed run. - regexNameFinder.find(tokens); + assertCompletesQuickly(() -> regexNameFinder.find(tokens)); + assertCompletesQuickly(() -> regexNameFinder.find(attack)); + } + + /** + * Long whitespace runs after a digit, the shape of a degrees/minutes/seconds + * coordinate whose remainder never arrives. Matched on the raw text (the + * whitespace-tokenized form collapses the runs), every built-in pattern must + * finish in time linear in the run length. + */ + private static Stream<Arguments> whitespaceRunInputs() { + final int n = 32_000; + final String spaces = " ".repeat(n); + final List<Named<String>> inputs = List.of( + Named.of("digitThenSpaces", "1" + spaces), + Named.of("degreeMarkThenSpaces", "1d" + spaces), + Named.of("degreeSignThenSpaces", "1°" + spaces), + Named.of("digitSpacesDigitSpaces", "1" + spaces + "1" + spaces), + Named.of("minutesThenSpaces", "1 22'" + spaces), + Named.of("hemisphereThenSpaces", "1 N" + spaces), + Named.of("commaThenSpaces", "1 ," + spaces), + Named.of("digitThenTabs", "1" + "\t".repeat(n)), + Named.of("digitThenMixedWhitespace", "1" + " \t\n\r".repeat(n / 4)), + Named.of("mgrsWithSpaces", "11S" + spaces + "KU" + spaces + "1" + spaces)); + final List<Arguments> cases = new ArrayList<>(); + for (RegexNameFinderFactory.DEFAULT_REGEX_NAME_FINDER def + : RegexNameFinderFactory.DEFAULT_REGEX_NAME_FINDER.values()) { + for (Named<String> input : inputs) { + cases.add(Arguments.of(def, input)); + } + } + return cases.stream(); + } + + @ParameterizedTest(name = "{0} {1}") + @MethodSource("whitespaceRunInputs") + void testBuiltinPatternsMatchWhitespaceRunsInLinearTime( + RegexNameFinderFactory.DEFAULT_REGEX_NAME_FINDER def, String input) { + RegexNameFinder finder = RegexNameFinderFactory.getDefaultRegexNameFinders(def); + String[] tokens = WhitespaceTokenizer.INSTANCE.tokenize(input); + assertCompletesQuickly(() -> finder.find(input)); + assertCompletesQuickly(() -> finder.find(tokens)); + } + + /** + * Runs {@code find} once as a warmup outside the timed section, so the budget + * measures the match itself rather than JVM cold start on throttled machines, + * then asserts that a second run finishes within the budget. + */ + private static void assertCompletesQuickly(Executable find) { + Assertions.assertDoesNotThrow(find); + Assertions.assertTimeoutPreemptively(Duration.ofSeconds(2), find); + } + + /** + * The {@code DEGREES_MIN_SEC_LAT_LON} pattern with greedy whitespace quantifiers, + * kept verbatim as the reference the built-in pattern must agree with. + */ + private static final Pattern REFERENCE_DEGREES_MIN_SEC_LAT_LON = Pattern.compile( + "([-|\\+]?\\d{1,3}[d|D|\\u00B0|\\s](\\s*\\d{1,2}['|\\u2019|\\s])" + + "?(\\s*\\d{1,2}[\\\"|\\u201d])?\\s*[N|n|S|s]?)(\\s*|,|,\\s*)([-|\\+]?\\d{1,3}[d|D|\\u00B0|" + + "\\s](\\s*\\d{1,2}['|\\u2019|\\s])?(\\s*\\d{1,2}[\\\"|\\u201d])?\\s*[E|e|W|w]?)", + Pattern.CASE_INSENSITIVE); + + /** + * Asserts that the built-in pattern finds the same spans as the reference pattern. + * + * @return The number of spans found. + */ + private static int assertSameDegreesSpans(String input) { + final String type = + RegexNameFinderFactory.DEFAULT_REGEX_NAME_FINDER.DEGREES_MIN_SEC_LAT_LON.getType(); + RegexNameFinder reference = new RegexNameFinder( + Map.of(type, new Pattern[] {REFERENCE_DEGREES_MIN_SEC_LAT_LON})); + RegexNameFinder actual = RegexNameFinderFactory.getDefaultRegexNameFinders( + RegexNameFinderFactory.DEFAULT_REGEX_NAME_FINDER.DEGREES_MIN_SEC_LAT_LON); + Span[] expected = reference.find(input); + Assertions.assertArrayEquals(expected, actual.find(input), + () -> "spans differ for input: \"" + input + "\""); + return expected.length; + } - Assertions.assertTimeoutPreemptively(Duration.ofSeconds(2), - () -> regexNameFinder.find(tokens)); + private static Stream<String> realisticCoordinates() { + return Stream.of( + "40°26'46\"N 79°58'56\"W", + "40° 26' 46\" N, 79° 58' 56\" W", + "40°26’46”N 79°58’56”W", + "40 26 46 N, 79 58 56 W", + "40 26 46 N 79 58 56 W", + "40 26 46 N", + "79 58 56 W", + "-12.5", + "-12.5, 130.8", + "+45.1234, -123.12", + "45.1234N 123.12W", + "45N 123W", + "45 30 N 50 30 W", + "40d 26' 46\" N, 79d 58' 56\" W", + "40D 26' 46\" S, 79D 58' 56\" E", + "40d26'46\"n,79d58'56\"e", + "40d\t26'\t46\"\tN,\t79d\t58'\t56\"\tW", + "40d 26' 46\" N , 79d 58' 56\" W", + "40d 26' 46\" N,\n79d 58' 56\" W", + "40 26 46\nN\n79 58 56\nW", + "40°, -79°", + "40° N , \t 79° W", + "lat 40 lon 79", + "at 12 34 56 S and 123 45 6 E today", + "between 1 2 and 3 4, then 5d 6' 7\" N 8d 9' 10\" W.", + "1, 2, 3, 4, 5", + "1234 5678", + "|40|26|N|79|58|W", + "1" + " ".repeat(200), + "1d" + " ".repeat(100) + "2" + " ".repeat(100) + "N"); + } + + @ParameterizedTest + @MethodSource("realisticCoordinates") + void testDegreesPatternMatchesReferenceOnCoordinates(String input) { + assertSameDegreesSpans(input); + } + + @Test + void testDegreesPatternMatchesReferenceOnFuzzCorpus() { + final char[] alphabet = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ' ', ' ', ' ', + '\t', '\n', 'd', 'D', '°', '\'', '’', '"', '”', 'N', 'n', 'S', 's', + 'E', 'e', 'W', 'w', ',', '-', '+', '|', 'x'}; + // Coordinate-shaped fragments, so a good share of the corpus reaches deep into the pattern. + final String[] fragments = {"4", "40", "179", "-12", "+5", "40d", "179°", "40 ", "26'", + "26’", "46\"", "46”", " ", " ", "\t", "\n", "d", "N", "s", "E", "w", ",", ", ", + "x", "|"}; + final Random random = new Random(20261102L); + int spans = 0; + for (int i = 0; i < 6000; i++) { + final int length = 1 + random.nextInt(40); + final StringBuilder sb = new StringBuilder(length); + while (sb.length() < length) { + if (i % 2 == 0) { + sb.append(alphabet[random.nextInt(alphabet.length)]); + } else { + sb.append(fragments[random.nextInt(fragments.length)]); + } + } + spans += assertSameDegreesSpans(sb.toString()); + } + // Guards against a corpus that rarely matches and so compares little. + Assertions.assertTrue(spans > 1000, "fuzz corpus produced only " + spans + " spans"); } /**
