You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gs...@apache.org on 2023/06/02 17:52:15 UTC
[lucene] branch branch_9x updated: Add "direct to binary" option for DaciukMihovAutomatonBuilder and use it in TermInSetQuery#visit (#12320)
This is an automated email from the ASF dual-hosted git repository.
gsmiller pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_9x by this push:
new 349b458e889 Add "direct to binary" option for DaciukMihovAutomatonBuilder and use it in TermInSetQuery#visit (#12320)
349b458e889 is described below
commit 349b458e88957d4bbfd2322a2789cbb13df575d4
Author: Greg Miller <gs...@gmail.com>
AuthorDate: Fri Jun 2 09:34:52 2023 -0700
Add "direct to binary" option for DaciukMihovAutomatonBuilder and use it in TermInSetQuery#visit (#12320)
---
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/search/TermInSetQuery.java | 18 +-
.../java/org/apache/lucene/util/UnicodeUtil.java | 83 ++++++---
.../org/apache/lucene/util/automaton/Automata.java | 46 ++++-
.../automaton/DaciukMihovAutomatonBuilder.java | 193 ++++++++++++---------
.../org/apache/lucene/util/TestUnicodeUtil.java | 22 +++
.../automaton/TestDaciukMihovAutomatonBuilder.java | 167 +++++++++++++++++-
7 files changed, 406 insertions(+), 126 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 1c69846f150..b61ede95d8e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -49,6 +49,9 @@ Improvements
* GITHUB#12290: Make memory fence in ByteBufferGuard explicit using `VarHandle.fullFence()`
+* GITHUB#12320: Add "direct to binary" option for DaciukMihovAutomatonBuilder and use it in TermInSetQuery#visit.
+ (Greg Miller)
+
Optimizations
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/TermInSetQuery.java b/lucene/core/src/java/org/apache/lucene/search/TermInSetQuery.java
index 2e0a297c746..ed268751bba 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TermInSetQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TermInSetQuery.java
@@ -17,11 +17,10 @@
package org.apache.lucene.search;
import java.io.IOException;
-import java.util.ArrayList;
+import java.io.UncheckedIOException;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
-import java.util.List;
import java.util.SortedSet;
import org.apache.lucene.index.FilteredTermsEnum;
import org.apache.lucene.index.PrefixCodedTerms;
@@ -38,7 +37,6 @@ import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.automaton.Automata;
import org.apache.lucene.util.automaton.Automaton;
import org.apache.lucene.util.automaton.ByteRunAutomaton;
-import org.apache.lucene.util.automaton.CompiledAutomaton;
import org.apache.lucene.util.automaton.Operations;
/**
@@ -150,13 +148,17 @@ public class TermInSetQuery extends MultiTermQuery implements Accountable {
}
}
+ // TODO: This is pretty heavy-weight. If we have TermInSetQuery directly extend AutomatonQuery
+ // we won't have to do this (see GH#12176).
private ByteRunAutomaton asByteRunAutomaton() {
- TermIterator iterator = termData.iterator();
- List<Automaton> automata = new ArrayList<>();
- for (BytesRef term = iterator.next(); term != null; term = iterator.next()) {
- automata.add(Automata.makeBinary(term));
+ try {
+ Automaton a = Automata.makeBinaryStringUnion(termData.iterator());
+ return new ByteRunAutomaton(a, true, Operations.DEFAULT_DETERMINIZE_WORK_LIMIT);
+ } catch (IOException e) {
+ // Shouldn't happen since termData.iterator() provides an interator implementation that
+ // never throws:
+ throw new UncheckedIOException(e);
}
- return new CompiledAutomaton(Operations.union(automata)).runAutomaton;
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/util/UnicodeUtil.java b/lucene/core/src/java/org/apache/lucene/util/UnicodeUtil.java
index a9e9d815eb4..9cbd4910271 100644
--- a/lucene/core/src/java/org/apache/lucene/util/UnicodeUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/UnicodeUtil.java
@@ -477,40 +477,67 @@ public final class UnicodeUtil {
int utf8Upto = utf8.offset;
final byte[] bytes = utf8.bytes;
final int utf8Limit = utf8.offset + utf8.length;
+ UTF8CodePoint reuse = null;
while (utf8Upto < utf8Limit) {
- final int numBytes = utf8CodeLength[bytes[utf8Upto] & 0xFF];
- int v = 0;
- switch (numBytes) {
- case 1:
- ints[utf32Count++] = bytes[utf8Upto++];
- continue;
- case 2:
- // 5 useful bits
- v = bytes[utf8Upto++] & 31;
- break;
- case 3:
- // 4 useful bits
- v = bytes[utf8Upto++] & 15;
- break;
- case 4:
- // 3 useful bits
- v = bytes[utf8Upto++] & 7;
- break;
- default:
- throw new IllegalArgumentException("invalid utf8");
- }
-
- // TODO: this may read past utf8's limit.
- final int limit = utf8Upto + numBytes - 1;
- while (utf8Upto < limit) {
- v = v << 6 | bytes[utf8Upto++] & 63;
- }
- ints[utf32Count++] = v;
+ reuse = codePointAt(bytes, utf8Upto, reuse);
+ ints[utf32Count++] = reuse.codePoint;
+ utf8Upto += reuse.numBytes;
}
return utf32Count;
}
+ /**
+ * Computes the codepoint and codepoint length (in bytes) of the specified {@code offset} in the
+ * provided {@code utf8} byte array, assuming UTF8 encoding. As with other related methods in this
+ * class, this assumes valid UTF8 input and <strong>does not perform</strong> full UTF8
+ * validation. Passing invalid UTF8 or a position that is not a valid header byte position may
+ * result in undefined behavior. This makes no attempt to synchronize or validate.
+ */
+ public static UTF8CodePoint codePointAt(byte[] utf8, int pos, UTF8CodePoint reuse) {
+ if (reuse == null) {
+ reuse = new UTF8CodePoint();
+ }
+
+ int leadByte = utf8[pos] & 0xFF;
+ int numBytes = utf8CodeLength[leadByte];
+ reuse.numBytes = numBytes;
+ int v;
+ switch (numBytes) {
+ case 1:
+ reuse.codePoint = leadByte;
+ return reuse;
+ case 2:
+ v = leadByte & 31; // 5 useful bits
+ break;
+ case 3:
+ v = leadByte & 15; // 4 useful bits
+ break;
+ case 4:
+ v = leadByte & 7; // 3 useful bits
+ break;
+ default:
+ throw new IllegalArgumentException(
+ "Invalid UTF8 header byte: 0x" + Integer.toHexString(leadByte));
+ }
+
+ // TODO: this may read past utf8's limit.
+ final int limit = pos + numBytes;
+ pos++;
+ while (pos < limit) {
+ v = v << 6 | utf8[pos++] & 63;
+ }
+ reuse.codePoint = v;
+
+ return reuse;
+ }
+
+ /** Holds a codepoint along with the number of bytes required to represent it in UTF8 */
+ public static final class UTF8CodePoint {
+ public int codePoint;
+ public int numBytes;
+ }
+
/** Shift value for lead surrogate to form a supplementary character. */
private static final int LEAD_SURROGATE_SHIFT_ = 10;
/** Mask to retrieve the significant value from a trail surrogate. */
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java b/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java
index def98684d07..c829429d3c9 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java
@@ -29,9 +29,11 @@
package org.apache.lucene.util.automaton;
+import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefIterator;
import org.apache.lucene.util.StringHelper;
/**
@@ -578,7 +580,49 @@ public final class Automata {
if (utf8Strings.isEmpty()) {
return makeEmpty();
} else {
- return DaciukMihovAutomatonBuilder.build(utf8Strings);
+ return DaciukMihovAutomatonBuilder.build(utf8Strings, false);
}
}
+
+ /**
+ * Returns a new (deterministic and minimal) automaton that accepts the union of the given
+ * collection of {@link BytesRef}s representing UTF-8 encoded strings. The resulting automaton
+ * will be built in a binary representation.
+ *
+ * @param utf8Strings The input strings, UTF-8 encoded. The collection must be in sorted order.
+ * @return An {@link Automaton} accepting all input strings. The resulting automaton is binary
+ * based (UTF-8 encoded byte transition labels).
+ */
+ public static Automaton makeBinaryStringUnion(Collection<BytesRef> utf8Strings) {
+ if (utf8Strings.isEmpty()) {
+ return makeEmpty();
+ } else {
+ return DaciukMihovAutomatonBuilder.build(utf8Strings, true);
+ }
+ }
+
+ /**
+ * Returns a new (deterministic and minimal) automaton that accepts the union of the given
+ * iterator of {@link BytesRef}s representing UTF-8 encoded strings.
+ *
+ * @param utf8Strings The input strings, UTF-8 encoded. The iterator must be in sorted order.
+ * @return An {@link Automaton} accepting all input strings. The resulting automaton is codepoint
+ * based (full unicode codepoints on transitions).
+ */
+ public static Automaton makeStringUnion(BytesRefIterator utf8Strings) throws IOException {
+ return DaciukMihovAutomatonBuilder.build(utf8Strings, false);
+ }
+
+ /**
+ * Returns a new (deterministic and minimal) automaton that accepts the union of the given
+ * iterator of {@link BytesRef}s representing UTF-8 encoded strings. The resulting automaton will
+ * be built in a binary representation.
+ *
+ * @param utf8Strings The input strings, UTF-8 encoded. The iterator must be in sorted order.
+ * @return An {@link Automaton} accepting all input strings. The resulting automaton is binary
+ * based (UTF-8 encoded byte transition labels).
+ */
+ public static Automaton makeBinaryStringUnion(BytesRefIterator utf8Strings) throws IOException {
+ return DaciukMihovAutomatonBuilder.build(utf8Strings, true);
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java b/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java
index a0ff7d3f13a..7048d4538d1 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java
@@ -16,15 +16,16 @@
*/
package org.apache.lucene.util.automaton;
+import java.io.IOException;
import java.util.Arrays;
import java.util.Collection;
-import java.util.Comparator;
import java.util.HashMap;
import java.util.IdentityHashMap;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.CharsRef;
-import org.apache.lucene.util.CharsRefBuilder;
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.BytesRefIterator;
+import org.apache.lucene.util.UnicodeUtil;
/**
* Builds a minimal, deterministic {@link Automaton} that accepts a set of strings. The algorithm
@@ -32,6 +33,9 @@ import org.apache.lucene.util.CharsRefBuilder;
*
* @see #build(Collection)
* @see Automata#makeStringUnion(Collection)
+ * @see Automata#makeBinaryStringUnion(Collection)
+ * @see Automata#makeStringUnion(BytesRefIterator)
+ * @see Automata#makeBinaryStringUnion(BytesRefIterator)
* @deprecated Visibility of this class will be reduced in a future release. Users can access this
* functionality directly through {@link Automata#makeStringUnion(Collection)}
*/
@@ -186,64 +190,16 @@ public final class DaciukMihovAutomatonBuilder {
/** Root automaton state. */
private final State root = new State();
- /** Previous sequence added to the automaton in {@link #add(CharsRef)}. */
- private CharsRefBuilder previous;
+ /** Used for input order checking (only through assertions right now) */
+ private BytesRefBuilder previous;
- /** A comparator used for enforcing sorted UTF8 order, used in assertions only. */
- @SuppressWarnings("deprecation")
- private static final Comparator<CharsRef> comparator = CharsRef.getUTF16SortedAsUTF8Comparator();
-
- /**
- * Add another character sequence to this automaton. The sequence must be lexicographically larger
- * or equal compared to any previous sequences added to this automaton (the input must be sorted).
- */
- private void add(CharsRef current) {
- if (current.length > Automata.MAX_STRING_UNION_TERM_LENGTH) {
- throw new IllegalArgumentException(
- "This builder doesn't allow terms that are larger than 1,000 characters, got " + current);
- }
- assert stateRegistry != null : "Automaton already built.";
- assert previous == null || comparator.compare(previous.get(), current) <= 0
- : "Input must be in sorted UTF-8 order: " + previous + " >= " + current;
- assert setPrevious(current);
-
- // Descend in the automaton (find matching prefix).
- int pos = 0, max = current.length();
- State state = root;
- for (; ; ) {
- assert pos <= max;
- if (pos == max) {
- break;
- }
-
- int codePoint = Character.codePointAt(current, pos);
- State next = state.lastChild(codePoint);
- if (next == null) {
- break;
- }
-
- state = next;
- pos += Character.charCount(codePoint);
+ /** Copy <code>current</code> into an internal buffer. */
+ private boolean setPrevious(BytesRef current) {
+ if (previous == null) {
+ previous = new BytesRefBuilder();
}
-
- if (state.hasChildren()) replaceOrRegister(state);
-
- addSuffix(state, current, pos);
- }
-
- /**
- * Finalize the automaton and return the root state. No more strings can be added to the builder
- * after this call.
- *
- * @return Root automaton state.
- */
- private State complete() {
- if (this.stateRegistry == null) throw new IllegalStateException();
-
- if (root.hasChildren()) replaceOrRegister(root);
-
- stateRegistry = null;
- return root;
+ previous.copyBytes(current);
+ return true;
}
/** Internal recursive traversal for conversion. */
@@ -268,6 +224,22 @@ public final class DaciukMihovAutomatonBuilder {
return converted;
}
+ /**
+ * Called after adding all terms. Performs final minimization and converts to a standard {@link
+ * Automaton} instance.
+ */
+ private Automaton completeAndConvert() {
+ // Final minimization:
+ if (this.stateRegistry == null) throw new IllegalStateException();
+ if (root.hasChildren()) replaceOrRegister(root);
+ stateRegistry = null;
+
+ // Convert:
+ Automaton.Builder a = new Automaton.Builder();
+ convert(a, root, new IdentityHashMap<>());
+ return a.finish();
+ }
+
/**
* Build a minimal, deterministic automaton from a sorted list of {@link BytesRef} representing
* strings in UTF-8. These strings must be binary-sorted.
@@ -276,27 +248,92 @@ public final class DaciukMihovAutomatonBuilder {
*/
@Deprecated
public static Automaton build(Collection<BytesRef> input) {
+ return build(input, false);
+ }
+
+ /**
+ * Build a minimal, deterministic automaton from a sorted list of {@link BytesRef} representing
+ * strings in UTF-8. These strings must be binary-sorted.
+ */
+ static Automaton build(Collection<BytesRef> input, boolean asBinary) {
final DaciukMihovAutomatonBuilder builder = new DaciukMihovAutomatonBuilder();
- CharsRefBuilder current = new CharsRefBuilder();
for (BytesRef b : input) {
- current.copyUTF8Bytes(b);
- builder.add(current.get());
+ builder.add(b, asBinary);
}
- Automaton.Builder a = new Automaton.Builder();
- convert(a, builder.complete(), new IdentityHashMap<>());
+ return builder.completeAndConvert();
+ }
- return a.finish();
+ /**
+ * Build a minimal, deterministic automaton from a sorted list of {@link BytesRef} representing
+ * strings in UTF-8. These strings must be binary-sorted. Creates an {@link Automaton} with either
+ * UTF-8 codepoints as transition labels or binary (compiled) transition labels based on {@code
+ * asBinary}.
+ */
+ static Automaton build(BytesRefIterator input, boolean asBinary) throws IOException {
+ final DaciukMihovAutomatonBuilder builder = new DaciukMihovAutomatonBuilder();
+
+ for (BytesRef b = input.next(); b != null; b = input.next()) {
+ builder.add(b, asBinary);
+ }
+
+ return builder.completeAndConvert();
}
- /** Copy <code>current</code> into an internal buffer. */
- private boolean setPrevious(CharsRef current) {
- if (previous == null) {
- previous = new CharsRefBuilder();
+ private void add(BytesRef current, boolean asBinary) {
+ if (current.length > Automata.MAX_STRING_UNION_TERM_LENGTH) {
+ throw new IllegalArgumentException(
+ "This builder doesn't allow terms that are larger than "
+ + Automata.MAX_STRING_UNION_TERM_LENGTH
+ + " characters, got "
+ + current);
}
- previous.copyChars(current);
- return true;
+ assert stateRegistry != null : "Automaton already built.";
+ assert previous == null || previous.get().compareTo(current) <= 0
+ : "Input must be in sorted UTF-8 order: " + previous.get() + " >= " + current;
+ assert setPrevious(current);
+
+ // Reusable codepoint information if we're building a non-binary based automaton
+ UnicodeUtil.UTF8CodePoint codePoint = null;
+
+ // Descend in the automaton (find matching prefix).
+ byte[] bytes = current.bytes;
+ int pos = current.offset, max = current.offset + current.length;
+ State next, state = root;
+ if (asBinary) {
+ while (pos < max && (next = state.lastChild(bytes[pos] & 0xff)) != null) {
+ state = next;
+ pos++;
+ }
+ } else {
+ while (pos < max) {
+ codePoint = UnicodeUtil.codePointAt(bytes, pos, codePoint);
+ next = state.lastChild(codePoint.codePoint);
+ if (next == null) {
+ break;
+ }
+ state = next;
+ pos += codePoint.numBytes;
+ }
+ }
+
+ if (state.hasChildren()) replaceOrRegister(state);
+
+ // Add suffix
+ if (asBinary) {
+ while (pos < max) {
+ state = state.newState(bytes[pos] & 0xff);
+ pos++;
+ }
+ } else {
+ while (pos < max) {
+ codePoint = UnicodeUtil.codePointAt(bytes, pos, codePoint);
+ state = state.newState(codePoint.codePoint);
+ pos += codePoint.numBytes;
+ }
+ }
+ state.is_final = true;
}
/**
@@ -315,18 +352,4 @@ public final class DaciukMihovAutomatonBuilder {
stateRegistry.put(child, child);
}
}
-
- /**
- * Add a suffix of <code>current</code> starting at <code>fromIndex</code> (inclusive) to state
- * <code>state</code>.
- */
- private void addSuffix(State state, CharSequence current, int fromIndex) {
- final int len = current.length();
- while (fromIndex < len) {
- int cp = Character.codePointAt(current, fromIndex);
- state = state.newState(cp);
- fromIndex += Character.charCount(cp);
- }
- state.is_final = true;
- }
}
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestUnicodeUtil.java b/lucene/core/src/test/org/apache/lucene/util/TestUnicodeUtil.java
index 8e0348b706c..2f309e945b7 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestUnicodeUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestUnicodeUtil.java
@@ -166,6 +166,28 @@ public class TestUnicodeUtil extends LuceneTestCase {
}
}
+ public void testUTF8CodePointAt() {
+ int num = atLeast(50000);
+ UnicodeUtil.UTF8CodePoint reuse = null;
+ for (int i = 0; i < num; i++) {
+ final String s = TestUtil.randomUnicodeString(random());
+ final byte[] utf8 = new byte[UnicodeUtil.maxUTF8Length(s.length())];
+ final int utf8Len = UnicodeUtil.UTF16toUTF8(s, 0, s.length(), utf8);
+
+ int[] expected = s.codePoints().toArray();
+ int pos = 0;
+ int expectedUpto = 0;
+ while (pos < utf8Len) {
+ reuse = UnicodeUtil.codePointAt(utf8, pos, reuse);
+ assertEquals(expected[expectedUpto], reuse.codePoint);
+ expectedUpto++;
+ pos += reuse.numBytes;
+ }
+ assertEquals(utf8Len, pos);
+ assertEquals(expected.length, expectedUpto);
+ }
+ }
+
public void testNewString() {
final int[] codePoints = {
Character.toCodePoint(Character.MIN_HIGH_SURROGATE, Character.MAX_LOW_SURROGATE),
diff --git a/lucene/core/src/test/org/apache/lucene/util/automaton/TestDaciukMihovAutomatonBuilder.java b/lucene/core/src/test/org/apache/lucene/util/automaton/TestDaciukMihovAutomatonBuilder.java
index 4b31eda98c6..d72e08f18e9 100644
--- a/lucene/core/src/test/org/apache/lucene/util/automaton/TestDaciukMihovAutomatonBuilder.java
+++ b/lucene/core/src/test/org/apache/lucene/util/automaton/TestDaciukMihovAutomatonBuilder.java
@@ -16,26 +16,185 @@
*/
package org.apache.lucene.util.automaton;
+import com.carrotsearch.randomizedtesting.RandomizedTest;
+import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
+import java.io.IOException;
+import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.tests.util.TestUtil;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.BytesRefIterator;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.fst.Util;
public class TestDaciukMihovAutomatonBuilder extends LuceneTestCase {
- public void testLargeTerms() {
+ public void testBasic() throws Exception {
+ List<BytesRef> terms = basicTerms();
+ Collections.sort(terms);
+
+ Automaton a = build(terms, false);
+ checkAutomaton(terms, a, false);
+ checkMinimized(a);
+ }
+
+ public void testBasicBinary() throws Exception {
+ List<BytesRef> terms = basicTerms();
+ Collections.sort(terms);
+
+ Automaton a = build(terms, true);
+ checkAutomaton(terms, a, true);
+ checkMinimized(a);
+ }
+
+ public void testRandomMinimized() throws Exception {
+ int iters = RandomizedTest.isNightly() ? 20 : 5;
+ for (int i = 0; i < iters; i++) {
+ boolean buildBinary = random().nextBoolean();
+ int size = RandomNumbers.randomIntBetween(random(), 2, 50);
+ Set<BytesRef> terms = new HashSet<>();
+ List<Automaton> automatonList = new ArrayList<>(size);
+ for (int j = 0; j < size; j++) {
+ if (buildBinary) {
+ BytesRef t = TestUtil.randomBinaryTerm(random(), 8);
+ terms.add(t);
+ automatonList.add(Automata.makeBinary(t));
+ } else {
+ String s = TestUtil.randomRealisticUnicodeString(random(), 8);
+ terms.add(newBytesRef(s));
+ automatonList.add(Automata.makeString(s));
+ }
+ }
+ List<BytesRef> sortedTerms = terms.stream().sorted().collect(Collectors.toList());
+
+ Automaton expected =
+ MinimizationOperations.minimize(
+ Operations.union(automatonList), Operations.DEFAULT_DETERMINIZE_WORK_LIMIT);
+ Automaton actual = build(sortedTerms, buildBinary);
+ assertSameAutomaton(expected, actual);
+ }
+ }
+
+ public void testRandomUnicodeOnly() throws Exception {
+ testRandom(false);
+ }
+
+ public void testRandomBinary() throws Exception {
+ testRandom(true);
+ }
+
+ public void testLargeTerms() throws Exception {
byte[] b10k = new byte[10_000];
Arrays.fill(b10k, (byte) 'a');
IllegalArgumentException e =
expectThrows(
IllegalArgumentException.class,
- () -> DaciukMihovAutomatonBuilder.build(Collections.singleton(new BytesRef(b10k))));
+ () -> build(Collections.singleton(new BytesRef(b10k)), false));
assertTrue(
e.getMessage()
- .startsWith("This builder doesn't allow terms that are larger than 1,000 characters"));
+ .startsWith(
+ "This builder doesn't allow terms that are larger than "
+ + Automata.MAX_STRING_UNION_TERM_LENGTH
+ + " characters"));
byte[] b1k = ArrayUtil.copyOfSubArray(b10k, 0, 1000);
- DaciukMihovAutomatonBuilder.build(Collections.singleton(new BytesRef(b1k))); // no exception
+ build(Collections.singleton(new BytesRef(b1k)), false); // no exception
+ }
+
+ private void testRandom(boolean allowBinary) throws Exception {
+ int iters = RandomizedTest.isNightly() ? 50 : 10;
+ for (int i = 0; i < iters; i++) {
+ int size = RandomNumbers.randomIntBetween(random(), 500, 2_000);
+ Set<BytesRef> terms = new HashSet<>(size);
+ for (int j = 0; j < size; j++) {
+ if (allowBinary && random().nextInt(10) < 2) {
+ // Sometimes random bytes term that isn't necessarily valid unicode
+ terms.add(newBytesRef(TestUtil.randomBinaryTerm(random())));
+ } else {
+ terms.add(newBytesRef(TestUtil.randomRealisticUnicodeString(random())));
+ }
+ }
+
+ List<BytesRef> sorted = terms.stream().sorted().collect(Collectors.toList());
+ Automaton a = build(sorted, allowBinary);
+ checkAutomaton(sorted, a, allowBinary);
+ }
+ }
+
+ private void checkAutomaton(List<BytesRef> expected, Automaton a, boolean isBinary) {
+ CompiledAutomaton c =
+ new CompiledAutomaton(a, true, false, Operations.DEFAULT_DETERMINIZE_WORK_LIMIT, isBinary);
+ ByteRunAutomaton runAutomaton = c.runAutomaton;
+
+ // Make sure every expected term is accepted
+ for (BytesRef t : expected) {
+ String readable = isBinary ? t.toString() : t.utf8ToString();
+ assertTrue(
+ readable + " should be found but wasn't", runAutomaton.run(t.bytes, t.offset, t.length));
+ }
+
+ // Make sure every term produced by the automaton is expected
+ BytesRefBuilder scratch = new BytesRefBuilder();
+ FiniteStringsIterator it = new FiniteStringsIterator(c.automaton);
+ for (IntsRef r = it.next(); r != null; r = it.next()) {
+ BytesRef t = Util.toBytesRef(r, scratch);
+ assertTrue(expected.contains(t));
+ }
+ }
+
+ private void checkMinimized(Automaton a) {
+ Automaton minimized =
+ MinimizationOperations.minimize(a, Operations.DEFAULT_DETERMINIZE_WORK_LIMIT);
+ assertSameAutomaton(minimized, a);
+ }
+
+ private static void assertSameAutomaton(Automaton a, Automaton b) {
+ assertEquals(a.getNumStates(), b.getNumStates());
+ assertEquals(a.getNumTransitions(), b.getNumTransitions());
+ assertTrue(Operations.sameLanguage(a, b));
+ }
+
+ private List<BytesRef> basicTerms() {
+ List<BytesRef> terms = new ArrayList<>();
+ terms.add(newBytesRef("dog"));
+ terms.add(newBytesRef("day"));
+ terms.add(newBytesRef("dad"));
+ terms.add(newBytesRef("cats"));
+ terms.add(newBytesRef("cat"));
+ return terms;
+ }
+
+ private Automaton build(Collection<BytesRef> terms, boolean asBinary) throws IOException {
+ if (random().nextBoolean()) {
+ return DaciukMihovAutomatonBuilder.build(terms, asBinary);
+ } else {
+ return DaciukMihovAutomatonBuilder.build(new TermIterator(terms), asBinary);
+ }
+ }
+
+ private static final class TermIterator implements BytesRefIterator {
+ private final Iterator<BytesRef> it;
+
+ TermIterator(Collection<BytesRef> terms) {
+ this.it = terms.iterator();
+ }
+
+ @Override
+ public BytesRef next() throws IOException {
+ if (it.hasNext() == false) {
+ return null;
+ }
+ return it.next();
+ }
}
}