You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2025/03/21 18:28:48 UTC
(lucene) branch main updated: RegExp: add CASE_INSENSITIVE_RANGE support (#14381)
This is an automated email from the ASF dual-hosted git repository.
rmuir pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new fefa4e7076f RegExp: add CASE_INSENSITIVE_RANGE support (#14381)
fefa4e7076f is described below
commit fefa4e7076fb33eed33fa1af88b5559c007fbaae
Author: Robert Muir <rm...@apache.org>
AuthorDate: Fri Mar 21 14:28:43 2025 -0400
RegExp: add CASE_INSENSITIVE_RANGE support (#14381)
Add optional flag to support case-insensitive ranges. A minimal DFA is
always created. This works with Unicode but may have a performance cost.
Each codepoint in the range must be iterated, and any alternatives added
to a set. This can be large if the range spans much of Unicode.
CPU and memory costs are contained within a single function enabled by
the optional flag. For example when matching a caseless /[a-z]/, 54
codepoints will be accumulated into an int[], which is then compressed to
4 ranges before adding to the parse tree.
Closes #14378
---
lucene/CHANGES.txt | 3 ++
.../org/apache/lucene/util/automaton/RegExp.java | 57 ++++++++++++++++++++--
.../lucene/util/automaton/TestRegExpParsing.java | 22 +++++++--
3 files changed, 76 insertions(+), 6 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 7b4e2836167..d8170266060 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -137,6 +137,9 @@ Improvements
* GITHUB#14192: Added support for RegExp to handle case insensitive matching
across the full set of Unicode characters. (John Wagster)
+* GITHUB#14381: Add RegExp.CASE_INSENSITIVE_RANGE flag to support case-insensitive
+ matches of character class ranges such as /[a-z]/ (Robert Muir)
+
* GITHUB#14239: Hunspell's option to tolerate affix rule count mismatches was
improved to tolerate more instances of this problem. (Robert Muir)
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java b/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java
index b10ed8ec30c..c5e80fa8c0c 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java
@@ -479,6 +479,14 @@ public class RegExp {
*/
public static final int CASE_INSENSITIVE = 0x0200;
+ /**
+ * Similar to {@link #CASE_INSENSITIVE} but for character class ranges.
+ *
+ * <p>This flag allows ranges such as {@code [a-z]} to match {@code A}, but may result in
+ * performance costs during parsing.
+ */
+ public static final int CASE_INSENSITIVE_RANGE = 0x0400;
+
// ----- Deprecated flags ( > 0xffff ) ------
/**
@@ -769,6 +777,45 @@ public class RegExp {
return list.stream().mapToInt(Integer::intValue).toArray();
}
+ /**
+ * Expands range to include case-insensitive matches.
+ *
+ * <p>This is expensive: case-insensitive range involves iterating over the range space, adding
+ * alternatives. Jump on the grenade here, contain CPU and memory explosion just to this method
+ * activated by optional flag.
+ */
+ private void expandCaseInsensitiveRange(
+ int start, int end, List<Integer> rangeStarts, List<Integer> rangeEnds) {
+ if (start > end)
+ throw new IllegalArgumentException(
+ "invalid range: from (" + start + ") cannot be > to (" + end + ")");
+
+ // contain the explosion of transitions by using a throwaway state
+ Automaton scratch = new Automaton();
+ int state = scratch.createState();
+
+ // iterate over range, adding codepoint and any alternatives as transitions
+ for (int i = start; i <= end; i++) {
+ CaseFolding.expand(
+ i,
+ (int ch) -> {
+ scratch.addTransition(state, state, ch);
+ });
+ }
+
+ // compress transitions
+ scratch.finishState();
+
+ // add compressed ranges to list
+ Transition transition = new Transition();
+ int numTransitions = scratch.initTransition(state, transition);
+ for (int i = 0; i < numTransitions; i++) {
+ scratch.getNextTransition(transition);
+ rangeStarts.add(transition.min);
+ rangeEnds.add(transition.max);
+ }
+ }
+
private Automaton toCaseInsensitiveString() {
List<Automaton> list = new ArrayList<>();
@@ -1314,9 +1361,13 @@ public class RegExp {
int c = parseCharExp();
if (match('-')) {
- // range from c-d
- starts.add(c);
- ends.add(parseCharExp());
+ if (check(CASE_INSENSITIVE_RANGE)) {
+ expandCaseInsensitiveRange(c, parseCharExp(), starts, ends);
+ } else {
+ // simple range from c-d
+ starts.add(c);
+ ends.add(parseCharExp());
+ }
} else if (check(ASCII_CASE_INSENSITIVE | CASE_INSENSITIVE)) {
// single case-insensitive character
for (int form : toCaseInsensitiveChar(c)) {
diff --git a/lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java b/lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java
index f0f050e8b60..79c154170af 100644
--- a/lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java
+++ b/lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java
@@ -87,14 +87,30 @@ public class TestRegExpParsing extends LuceneTestCase {
AutomatonTestUtil.assertMinimalDFA(re.toAutomaton());
}
- // ranges aren't treated as case-insensitive, but maybe ok with charclass
- // instead of adding range, expand it: iterate each codepoint, adding its alternatives
- public void testCaseInsensitiveClassRange() {
+ // ranges aren't treated as case-insensitive, unless special flag is provided
+ public void testCaseInsensitiveClassRangeDisabled() {
RegExp re = new RegExp("[c-d]", RegExp.NONE, RegExp.ASCII_CASE_INSENSITIVE);
assertEquals("REGEXP_CHAR_RANGE from=c to=d\n", re.toStringTree());
AutomatonTestUtil.assertMinimalDFA(re.toAutomaton());
}
+ // case insensitive range
+ public void testCaseInsensitiveClassRange() {
+ RegExp re = new RegExp("[c-d]", RegExp.NONE, RegExp.CASE_INSENSITIVE_RANGE);
+ assertEquals(
+ "REGEXP_CHAR_CLASS starts=[U+0043 U+0063] ends=[U+0044 U+0064]\n", re.toStringTree());
+ AutomatonTestUtil.assertMinimalDFA(re.toAutomaton());
+ }
+
+ // common enough that we need to ensure this one is efficient
+ public void testCaseInsensitiveClassRangeCompression() {
+ RegExp re = new RegExp("[a-z]", RegExp.NONE, RegExp.CASE_INSENSITIVE_RANGE);
+ assertEquals(
+ "REGEXP_CHAR_CLASS starts=[U+0041 U+0061 U+017F U+212A] ends=[U+005A U+007A U+017F U+212A]\n",
+ re.toStringTree());
+ AutomatonTestUtil.assertMinimalDFA(re.toAutomaton());
+ }
+
public void testCaseInsensitiveCharUpper() {
RegExp re = new RegExp("C", RegExp.NONE, RegExp.ASCII_CASE_INSENSITIVE);
assertEquals("\\C", re.toString());