| /* |
| * 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.lucene.util.automaton; |
| |
| |
| 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 org.apache.lucene.util.BytesRef; |
| import org.apache.lucene.util.BytesRefBuilder; |
| import org.apache.lucene.util.IntsRef; |
| import org.apache.lucene.util.IntsRefBuilder; |
| import org.apache.lucene.util.LuceneTestCase; |
| import org.apache.lucene.util.TestUtil; |
| import org.apache.lucene.util.UnicodeUtil; |
| import org.apache.lucene.util.automaton.AutomatonTestUtil.RandomAcceptedStrings; |
| import org.apache.lucene.util.fst.Util; |
| |
| import static org.apache.lucene.util.automaton.Operations.DEFAULT_DETERMINIZE_WORK_LIMIT; |
| |
| public class TestAutomaton extends LuceneTestCase { |
| |
| public void testBasic() throws Exception { |
| Automaton a = new Automaton(); |
| int start = a.createState(); |
| int x = a.createState(); |
| int y = a.createState(); |
| int end = a.createState(); |
| a.setAccept(end, true); |
| |
| a.addTransition(start, x, 'a', 'a'); |
| a.addTransition(start, end, 'd', 'd'); |
| a.addTransition(x, y, 'b', 'b'); |
| a.addTransition(y, end, 'c', 'c'); |
| a.finishState(); |
| } |
| |
| public void testReduceBasic() throws Exception { |
| Automaton a = new Automaton(); |
| int start = a.createState(); |
| int end = a.createState(); |
| a.setAccept(end, true); |
| // Should collapse to a-b: |
| a.addTransition(start, end, 'a', 'a'); |
| a.addTransition(start, end, 'b', 'b'); |
| a.addTransition(start, end, 'm', 'm'); |
| // Should collapse to x-y: |
| a.addTransition(start, end, 'x', 'x'); |
| a.addTransition(start, end, 'y', 'y'); |
| |
| a.finishState(); |
| assertEquals(3, a.getNumTransitions(start)); |
| Transition scratch = new Transition(); |
| a.initTransition(start, scratch); |
| a.getNextTransition(scratch); |
| assertEquals('a', scratch.min); |
| assertEquals('b', scratch.max); |
| a.getNextTransition(scratch); |
| assertEquals('m', scratch.min); |
| assertEquals('m', scratch.max); |
| a.getNextTransition(scratch); |
| assertEquals('x', scratch.min); |
| assertEquals('y', scratch.max); |
| } |
| |
| public void testSameLanguage() throws Exception { |
| Automaton a1 = Automata.makeString("foobar"); |
| Automaton a2 = Operations.removeDeadStates(Operations.concatenate( |
| Automata.makeString("foo"), |
| Automata.makeString("bar"))); |
| assertTrue(Operations.sameLanguage(a1, a2)); |
| } |
| |
| public void testCommonPrefixString() throws Exception { |
| Automaton a = Operations.concatenate( |
| Automata.makeString("foobar"), |
| Automata.makeAnyString()); |
| assertEquals("foobar", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixEmpty() throws Exception { |
| assertEquals("", Operations.getCommonPrefix(Automata.makeEmpty())); |
| } |
| |
| public void testCommonPrefixEmptyString() throws Exception { |
| assertEquals("", Operations.getCommonPrefix(Automata.makeEmptyString())); |
| } |
| |
| public void testCommonPrefixAny() throws Exception { |
| assertEquals("", Operations.getCommonPrefix(Automata.makeAnyString())); |
| } |
| |
| public void testCommonPrefixRange() throws Exception { |
| assertEquals("", Operations.getCommonPrefix(Automata.makeCharRange('a', 'b'))); |
| } |
| |
| public void testAlternatives() throws Exception { |
| Automaton a = Automata.makeChar('a'); |
| Automaton c = Automata.makeChar('c'); |
| assertEquals("", Operations.getCommonPrefix(Operations.union(a, c))); |
| } |
| |
| public void testCommonPrefixLeadingWildcard() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeAnyChar(), Automata.makeString("boo")); |
| assertEquals("", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixTrailingWildcard() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeString("boo"), Automata.makeAnyChar()); |
| assertEquals("boo", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixLeadingKleenStar() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeAnyString(), Automata.makeString("boo")); |
| assertEquals("", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixTrailingKleenStar() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeString("boo"), Automata.makeAnyString()); |
| assertEquals("boo", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixDeadStates() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeAnyString(), Automata.makeString("boo")); |
| // reverse it twice, to create some dead states |
| // TODO: is it possible to fix reverse() to not create dead states?! |
| Automaton withDeadStates = Operations.reverse(Operations.reverse(a)); |
| IllegalArgumentException expected = |
| expectThrows( |
| IllegalArgumentException.class, |
| () -> { |
| Operations.getCommonPrefix(withDeadStates); |
| }); |
| assertEquals("input automaton has dead states", expected.getMessage()); |
| } |
| |
| public void testCommonPrefixRemoveDeadStates() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeAnyString(), Automata.makeString("boo")); |
| // reverse it twice, to create some dead states |
| // TODO: is it possible to fix reverse() to not create dead states?! |
| Automaton withDeadStates = Operations.reverse(Operations.reverse(a)); |
| // now remove the deadstates |
| Automaton withoutDeadStates = Operations.removeDeadStates(withDeadStates); |
| assertEquals("", Operations.getCommonPrefix(withoutDeadStates)); |
| } |
| |
| public void testCommonPrefixOptional() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int fini = a.createState(); |
| a.setAccept(init, true); |
| a.setAccept(fini, true); |
| a.addTransition(init, fini, 'm'); |
| a.addTransition(fini, fini, 'm'); |
| a.finishState(); |
| assertEquals("", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixNFA() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int medial = a.createState(); |
| int fini = a.createState(); |
| a.setAccept(fini, true); |
| a.addTransition(init, medial, 'm'); |
| a.addTransition(init, fini, 'm'); |
| a.addTransition(medial, fini, 'o'); |
| a.finishState(); |
| assertEquals("m", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixNFAInfinite() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int medial = a.createState(); |
| int fini = a.createState(); |
| a.setAccept(fini, true); |
| a.addTransition(init, medial, 'm'); |
| a.addTransition(init, fini, 'm'); |
| a.addTransition(medial, fini, 'm'); |
| a.addTransition(fini, fini, 'm'); |
| a.finishState(); |
| assertEquals("m", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testCommonPrefixUnicode() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeString("boo😂😂😂"), Automata.makeAnyChar()); |
| assertEquals("boo😂😂😂", Operations.getCommonPrefix(a)); |
| } |
| |
| public void testConcatenate1() throws Exception { |
| Automaton a = Operations.concatenate( |
| Automata.makeString("m"), |
| Automata.makeAnyString()); |
| assertTrue(Operations.run(a, "m")); |
| assertTrue(Operations.run(a, "me")); |
| assertTrue(Operations.run(a, "me too")); |
| } |
| |
| public void testConcatenate2() throws Exception { |
| Automaton a = Operations.concatenate(Arrays.asList( |
| Automata.makeString("m"), |
| Automata.makeAnyString(), |
| Automata.makeString("n"), |
| Automata.makeAnyString())); |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "mn")); |
| assertTrue(Operations.run(a, "mone")); |
| assertFalse(Operations.run(a, "m")); |
| assertFalse(Operations.isFinite(a)); |
| } |
| |
| public void testUnion1() throws Exception { |
| Automaton a = Operations.union(Arrays.asList( |
| Automata.makeString("foobar"), |
| Automata.makeString("barbaz"))); |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "foobar")); |
| assertTrue(Operations.run(a, "barbaz")); |
| |
| assertMatches(a, "foobar", "barbaz"); |
| } |
| |
| public void testUnion2() throws Exception { |
| Automaton a = Operations.union(Arrays.asList( |
| Automata.makeString("foobar"), |
| Automata.makeString(""), |
| Automata.makeString("barbaz"))); |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "foobar")); |
| assertTrue(Operations.run(a, "barbaz")); |
| assertTrue(Operations.run(a, "")); |
| |
| assertMatches(a, "", "foobar", "barbaz"); |
| } |
| |
| public void testMinimizeSimple() throws Exception { |
| Automaton a = Automata.makeString("foobar"); |
| Automaton aMin = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| |
| assertTrue(Operations.sameLanguage(a, aMin)); |
| } |
| |
| public void testMinimize2() throws Exception { |
| Automaton a = Operations.union(Arrays.asList(Automata.makeString("foobar"), |
| Automata.makeString("boobar"))); |
| Automaton aMin = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.sameLanguage(Operations.determinize( |
| Operations.removeDeadStates(a), DEFAULT_DETERMINIZE_WORK_LIMIT), aMin)); |
| } |
| |
| public void testReverse() throws Exception { |
| Automaton a = Automata.makeString("foobar"); |
| Automaton ra = Operations.reverse(a); |
| Automaton a2 = Operations.determinize(Operations.reverse(ra), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| |
| assertTrue(Operations.sameLanguage(a, a2)); |
| } |
| |
| public void testOptional() throws Exception { |
| Automaton a = Automata.makeString("foobar"); |
| Automaton a2 = Operations.optional(a); |
| a2 = Operations.determinize(a2, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| |
| assertTrue(Operations.run(a, "foobar")); |
| assertFalse(Operations.run(a, "")); |
| assertTrue(Operations.run(a2, "foobar")); |
| assertTrue(Operations.run(a2, "")); |
| } |
| |
| public void testRepeatAny() throws Exception { |
| Automaton a = Automata.makeString("zee"); |
| Automaton a2 = Operations.determinize(Operations.repeat(a), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a2, "")); |
| assertTrue(Operations.run(a2, "zee")); |
| assertTrue(Operations.run(a2, "zeezee")); |
| assertTrue(Operations.run(a2, "zeezeezee")); |
| } |
| |
| public void testRepeatMin() throws Exception { |
| Automaton a = Automata.makeString("zee"); |
| Automaton a2 = Operations.determinize(Operations.repeat(a, 2), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertFalse(Operations.run(a2, "")); |
| assertFalse(Operations.run(a2, "zee")); |
| assertTrue(Operations.run(a2, "zeezee")); |
| assertTrue(Operations.run(a2, "zeezeezee")); |
| } |
| |
| public void testRepeatMinMax1() throws Exception { |
| Automaton a = Automata.makeString("zee"); |
| Automaton a2 = Operations.determinize(Operations.repeat(a, 0, 2), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a2, "")); |
| assertTrue(Operations.run(a2, "zee")); |
| assertTrue(Operations.run(a2, "zeezee")); |
| assertFalse(Operations.run(a2, "zeezeezee")); |
| } |
| |
| public void testRepeatMinMax2() throws Exception { |
| Automaton a = Automata.makeString("zee"); |
| Automaton a2 = Operations.determinize(Operations.repeat(a, 2, 4), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertFalse(Operations.run(a2, "")); |
| assertFalse(Operations.run(a2, "zee")); |
| assertTrue(Operations.run(a2, "zeezee")); |
| assertTrue(Operations.run(a2, "zeezeezee")); |
| assertTrue(Operations.run(a2, "zeezeezeezee")); |
| assertFalse(Operations.run(a2, "zeezeezeezeezee")); |
| } |
| |
| public void testComplement() throws Exception { |
| Automaton a = Automata.makeString("zee"); |
| Automaton a2 = Operations.determinize(Operations.complement(a, |
| DEFAULT_DETERMINIZE_WORK_LIMIT), DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a2, "")); |
| assertFalse(Operations.run(a2, "zee")); |
| assertTrue(Operations.run(a2, "zeezee")); |
| assertTrue(Operations.run(a2, "zeezeezee")); |
| } |
| |
| public void testInterval() throws Exception { |
| Automaton a = Operations.determinize(Automata.makeDecimalInterval(17, 100, 3), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertFalse(Operations.run(a, "")); |
| assertTrue(Operations.run(a, "017")); |
| assertTrue(Operations.run(a, "100")); |
| assertTrue(Operations.run(a, "073")); |
| } |
| |
| public void testCommonSuffix() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int fini = a.createState(); |
| a.setAccept(init, true); |
| a.setAccept(fini, true); |
| a.addTransition(init, fini, 'm'); |
| a.addTransition(fini, fini, 'm'); |
| a.finishState(); |
| assertEquals(0, Operations.getCommonSuffixBytesRef(a).length); |
| } |
| |
| public void testCommonSuffixEmpty() throws Exception { |
| assertEquals(new BytesRef(), Operations.getCommonSuffixBytesRef(Automata.makeEmpty())); |
| } |
| |
| public void testCommonSuffixEmptyString() throws Exception { |
| assertEquals(new BytesRef(), Operations.getCommonSuffixBytesRef(Automata.makeEmptyString())); |
| } |
| |
| public void testCommonSuffixTrailingWildcard() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeString("boo"), Automata.makeAnyChar()); |
| assertEquals(new BytesRef(), Operations.getCommonSuffixBytesRef(a)); |
| } |
| |
| public void testCommonSuffixLeadingKleenStar() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeAnyString(), Automata.makeString("boo")); |
| assertEquals(new BytesRef("boo"), Operations.getCommonSuffixBytesRef(a)); |
| } |
| |
| public void testCommonSuffixTrailingKleenStar() throws Exception { |
| Automaton a = Operations.concatenate(Automata.makeString("boo"), Automata.makeAnyString()); |
| assertEquals(new BytesRef(), Operations.getCommonSuffixBytesRef(a)); |
| } |
| |
| public void testCommonSuffixUnicode() throws Exception { |
| Automaton a = |
| Operations.concatenate(Automata.makeAnyString(), Automata.makeString("boo😂😂😂")); |
| Automaton binary = new UTF32ToUTF8().convert(a); |
| assertEquals(new BytesRef("boo😂😂😂"), Operations.getCommonSuffixBytesRef(binary)); |
| } |
| |
| public void testReverseRandom1() throws Exception { |
| int ITERS = atLeast(100); |
| for(int i=0;i<ITERS;i++) { |
| Automaton a = AutomatonTestUtil.randomAutomaton(random()); |
| Automaton ra = Operations.reverse(a); |
| Automaton rra = Operations.reverse(ra); |
| assertTrue(Operations.sameLanguage( |
| Operations.determinize(Operations.removeDeadStates(a), Integer.MAX_VALUE), |
| Operations.determinize(Operations.removeDeadStates(rra), Integer.MAX_VALUE))); |
| } |
| } |
| |
| public void testReverseRandom2() throws Exception { |
| int ITERS = atLeast(100); |
| for(int iter=0;iter<ITERS;iter++) { |
| //System.out.println("TEST: iter=" + iter); |
| Automaton a = AutomatonTestUtil.randomAutomaton(random()); |
| if (random().nextBoolean()) { |
| a = Operations.removeDeadStates(a); |
| } |
| Automaton ra = Operations.reverse(a); |
| Automaton rda = Operations.determinize(ra, Integer.MAX_VALUE); |
| |
| if (Operations.isEmpty(a)) { |
| assertTrue(Operations.isEmpty(rda)); |
| continue; |
| } |
| |
| RandomAcceptedStrings ras = new RandomAcceptedStrings(a); |
| |
| for(int iter2=0;iter2<20;iter2++) { |
| // Find string accepted by original automaton |
| int[] s = ras.getRandomAcceptedString(random()); |
| |
| // Reverse it |
| for(int j=0;j<s.length/2;j++) { |
| int x = s[j]; |
| s[j] = s[s.length-j-1]; |
| s[s.length-j-1] = x; |
| } |
| //System.out.println("TEST: iter2=" + iter2 + " s=" + Arrays.toString(s)); |
| |
| // Make sure reversed automaton accepts it |
| assertTrue(Operations.run(rda, new IntsRef(s, 0, s.length))); |
| } |
| } |
| } |
| |
| public void testAnyStringEmptyString() throws Exception { |
| Automaton a = Operations.determinize(Automata.makeAnyString(), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "")); |
| } |
| |
| public void testBasicIsEmpty() throws Exception { |
| Automaton a = new Automaton(); |
| a.createState(); |
| assertTrue(Operations.isEmpty(a)); |
| } |
| |
| public void testRemoveDeadTransitionsEmpty() throws Exception { |
| Automaton a = Automata.makeEmpty(); |
| Automaton a2 = Operations.removeDeadStates(a); |
| assertTrue(Operations.isEmpty(a2)); |
| } |
| |
| public void testInvalidAddTransition() throws Exception { |
| Automaton a = new Automaton(); |
| int s1 = a.createState(); |
| int s2 = a.createState(); |
| a.addTransition(s1, s2, 'a'); |
| a.addTransition(s2, s2, 'a'); |
| expectThrows(IllegalStateException.class, () -> { |
| a.addTransition(s1, s2, 'b'); |
| }); |
| } |
| |
| public void testBuilderRandom() throws Exception { |
| int ITERS = atLeast(100); |
| for(int iter=0;iter<ITERS;iter++) { |
| Automaton a = AutomatonTestUtil.randomAutomaton(random()); |
| |
| // Just get all transitions, shuffle, and build a new automaton with the same transitions: |
| List<Transition> allTrans = new ArrayList<>(); |
| int numStates = a.getNumStates(); |
| for(int s=0;s<numStates;s++) { |
| int count = a.getNumTransitions(s); |
| for(int i=0;i<count;i++) { |
| Transition t = new Transition(); |
| a.getTransition(s, i, t); |
| allTrans.add(t); |
| } |
| } |
| |
| Automaton.Builder builder = new Automaton.Builder(); |
| for(int i=0;i<numStates;i++) { |
| int s = builder.createState(); |
| builder.setAccept(s, a.isAccept(s)); |
| } |
| |
| Collections.shuffle(allTrans, random()); |
| for(Transition t : allTrans) { |
| builder.addTransition(t.source, t.dest, t.min, t.max); |
| } |
| |
| assertTrue(Operations.sameLanguage( |
| Operations.determinize(Operations.removeDeadStates(a), Integer.MAX_VALUE), |
| Operations.determinize(Operations.removeDeadStates(builder.finish()), |
| Integer.MAX_VALUE))); |
| } |
| } |
| |
| public void testIsTotal() throws Exception { |
| assertFalse(Operations.isTotal(new Automaton())); |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int fini = a.createState(); |
| a.setAccept(fini, true); |
| a.addTransition(init, fini, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); |
| a.finishState(); |
| assertFalse(Operations.isTotal(a)); |
| a.addTransition(fini, fini, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); |
| a.finishState(); |
| assertFalse(Operations.isTotal(a)); |
| a.setAccept(init, true); |
| assertTrue(Operations.isTotal(MinimizationOperations.minimize(a, |
| DEFAULT_DETERMINIZE_WORK_LIMIT))); |
| } |
| |
| public void testMinimizeEmpty() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int fini = a.createState(); |
| a.addTransition(init, fini, 'a'); |
| a.finishState(); |
| a = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertEquals(0, a.getNumStates()); |
| } |
| |
| public void testMinus() throws Exception { |
| Automaton a1 = Automata.makeString("foobar"); |
| Automaton a2 = Automata.makeString("boobar"); |
| Automaton a3 = Automata.makeString("beebar"); |
| Automaton a = Operations.union(Arrays.asList(a1, a2, a3)); |
| if (random().nextBoolean()) { |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } else if (random().nextBoolean()) { |
| a = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } |
| assertMatches(a, "foobar", "beebar", "boobar"); |
| |
| Automaton a4 = Operations.determinize(Operations.minus(a, a2, |
| DEFAULT_DETERMINIZE_WORK_LIMIT), DEFAULT_DETERMINIZE_WORK_LIMIT); |
| |
| assertTrue(Operations.run(a4, "foobar")); |
| assertFalse(Operations.run(a4, "boobar")); |
| assertTrue(Operations.run(a4, "beebar")); |
| assertMatches(a4, "foobar", "beebar"); |
| |
| a4 = Operations.determinize(Operations.minus(a4, a1, |
| DEFAULT_DETERMINIZE_WORK_LIMIT), DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertFalse(Operations.run(a4, "foobar")); |
| assertFalse(Operations.run(a4, "boobar")); |
| assertTrue(Operations.run(a4, "beebar")); |
| assertMatches(a4, "beebar"); |
| |
| a4 = Operations.determinize(Operations.minus(a4, a3, |
| DEFAULT_DETERMINIZE_WORK_LIMIT), DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertFalse(Operations.run(a4, "foobar")); |
| assertFalse(Operations.run(a4, "boobar")); |
| assertFalse(Operations.run(a4, "beebar")); |
| assertMatches(a4); |
| } |
| |
| public void testOneInterval() throws Exception { |
| Automaton a = Automata.makeDecimalInterval(999, 1032, 0); |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "0999")); |
| assertTrue(Operations.run(a, "00999")); |
| assertTrue(Operations.run(a, "000999")); |
| } |
| |
| public void testAnotherInterval() throws Exception { |
| Automaton a = Automata.makeDecimalInterval(1, 2, 0); |
| a = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| assertTrue(Operations.run(a, "01")); |
| } |
| |
| public void testIntervalRandom() throws Exception { |
| int ITERS = atLeast(100); |
| for(int iter=0;iter<ITERS;iter++) { |
| int min = TestUtil.nextInt(random(), 0, 100000); |
| int max = TestUtil.nextInt(random(), min, min+100000); |
| int digits; |
| if (random().nextBoolean()) { |
| digits = 0; |
| } else { |
| String s = Integer.toString(max); |
| digits = TestUtil.nextInt(random(), s.length(), 2*s.length()); |
| } |
| StringBuilder b = new StringBuilder(); |
| for(int i=0;i<digits;i++) { |
| b.append('0'); |
| } |
| String prefix = b.toString(); |
| |
| Automaton a = Operations.determinize(Automata.makeDecimalInterval(min, max, digits), |
| DEFAULT_DETERMINIZE_WORK_LIMIT); |
| if (random().nextBoolean()) { |
| a = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } |
| String mins = Integer.toString(min); |
| String maxs = Integer.toString(max); |
| if (digits > 0) { |
| mins = prefix.substring(mins.length()) + mins; |
| maxs = prefix.substring(maxs.length()) + maxs; |
| } |
| assertTrue(Operations.run(a, mins)); |
| assertTrue(Operations.run(a, maxs)); |
| |
| for(int iter2=0;iter2<100;iter2++) { |
| int x = random().nextInt(2*max); |
| boolean expected = x >= min && x <= max; |
| String sx = Integer.toString(x); |
| if (sx.length() < digits) { |
| // Left-fill with 0s |
| sx = b.substring(sx.length()) + sx; |
| } else if (digits == 0) { |
| // Left-fill with random number of 0s: |
| int numZeros = random().nextInt(10); |
| StringBuilder sb = new StringBuilder(); |
| for(int i=0;i<numZeros;i++) { |
| sb.append('0'); |
| } |
| sb.append(sx); |
| sx = sb.toString(); |
| } |
| assertEquals(expected, Operations.run(a, sx)); |
| } |
| } |
| } |
| |
| private void assertMatches(Automaton a, String... strings) { |
| Set<IntsRef> expected = new HashSet<>(); |
| for(String s : strings) { |
| IntsRefBuilder ints = new IntsRefBuilder(); |
| expected.add(Util.toUTF32(s, ints)); |
| } |
| |
| assertEquals(expected, TestOperations.getFiniteStrings( |
| Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT))); |
| } |
| |
| public void testConcatenatePreservesDet() throws Exception { |
| Automaton a1 = Automata.makeString("foobar"); |
| assertTrue(a1.isDeterministic()); |
| Automaton a2 = Automata.makeString("baz"); |
| assertTrue(a2.isDeterministic()); |
| assertTrue((Operations.concatenate(Arrays.asList(a1, a2)).isDeterministic())); |
| } |
| |
| public void testRemoveDeadStates() throws Exception { |
| Automaton a = Operations.concatenate(Arrays.asList(Automata.makeString("x"), |
| Automata.makeString("y"))); |
| assertEquals(4, a.getNumStates()); |
| a = Operations.removeDeadStates(a); |
| assertEquals(3, a.getNumStates()); |
| } |
| |
| public void testRemoveDeadStatesEmpty1() throws Exception { |
| Automaton a = new Automaton(); |
| a.finishState(); |
| assertTrue(Operations.isEmpty(a)); |
| assertTrue(Operations.isEmpty(Operations.removeDeadStates(a))); |
| } |
| |
| public void testRemoveDeadStatesEmpty2() throws Exception { |
| Automaton a = new Automaton(); |
| a.finishState(); |
| assertTrue(Operations.isEmpty(a)); |
| assertTrue(Operations.isEmpty(Operations.removeDeadStates(a))); |
| } |
| |
| public void testRemoveDeadStatesEmpty3() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int fini = a.createState(); |
| a.addTransition(init, fini, 'a'); |
| Automaton a2 = Operations.removeDeadStates(a); |
| assertEquals(0, a2.getNumStates()); |
| } |
| |
| public void testConcatEmpty() throws Exception { |
| // If you concat empty automaton to anything the result should still be empty: |
| Automaton a = Operations.concatenate(Automata.makeEmpty(), |
| Automata.makeString("foo")); |
| assertEquals(new HashSet<IntsRef>(), TestOperations.getFiniteStrings(a)); |
| |
| a = Operations.concatenate(Automata.makeString("foo"), |
| Automata.makeEmpty()); |
| assertEquals(new HashSet<IntsRef>(), TestOperations.getFiniteStrings(a)); |
| } |
| |
| public void testSeemsNonEmptyButIsNot1() throws Exception { |
| Automaton a = new Automaton(); |
| // Init state has a transition but doesn't lead to accept |
| int init = a.createState(); |
| int s = a.createState(); |
| a.addTransition(init, s, 'a'); |
| a.finishState(); |
| assertTrue(Operations.isEmpty(a)); |
| } |
| |
| public void testSeemsNonEmptyButIsNot2() throws Exception { |
| Automaton a = new Automaton(); |
| int init = a.createState(); |
| int s = a.createState(); |
| a.addTransition(init, s, 'a'); |
| // An orphan'd accept state |
| s = a.createState(); |
| a.setAccept(s, true); |
| a.finishState(); |
| assertTrue(Operations.isEmpty(a)); |
| } |
| |
| public void testSameLanguage1() throws Exception { |
| Automaton a = Automata.makeEmptyString(); |
| Automaton a2 = Automata.makeEmptyString(); |
| int state = a2.createState(); |
| a2.addTransition(0, state, 'a'); |
| a2.finishState(); |
| assertTrue(Operations.sameLanguage(Operations.removeDeadStates(a), |
| Operations.removeDeadStates(a2))); |
| } |
| |
| private Automaton randomNoOp(Automaton a) { |
| switch (random().nextInt(7)) { |
| case 0: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: determinize"); |
| } |
| return Operations.determinize(a, Integer.MAX_VALUE); |
| case 1: |
| if (a.getNumStates() < 100) { |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: minimize"); |
| } |
| return MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } else { |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: skip op=minimize: too many states (" + a.getNumStates() + ")"); |
| } |
| return a; |
| } |
| case 2: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: removeDeadStates"); |
| } |
| return Operations.removeDeadStates(a); |
| case 3: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: reverse reverse"); |
| } |
| a = Operations.reverse(a); |
| a = randomNoOp(a); |
| return Operations.reverse(a); |
| case 4: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: concat empty string"); |
| } |
| return Operations.concatenate(a, Automata.makeEmptyString()); |
| case 5: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: union empty automaton"); |
| } |
| return Operations.union(a, Automata.makeEmpty()); |
| case 6: |
| if (VERBOSE) { |
| System.out.println(" randomNoOp: do nothing!"); |
| } |
| return a; |
| } |
| assert false; |
| return null; |
| } |
| |
| private Automaton unionTerms(Collection<BytesRef> terms) { |
| Automaton a; |
| if (random().nextBoolean()) { |
| if (VERBOSE) { |
| System.out.println("TEST: unionTerms: use union"); |
| } |
| List<Automaton> as = new ArrayList<>(); |
| for(BytesRef term : terms) { |
| as.add(Automata.makeString(term.utf8ToString())); |
| } |
| a = Operations.union(as); |
| } else { |
| if (VERBOSE) { |
| System.out.println("TEST: unionTerms: use makeStringUnion"); |
| } |
| List<BytesRef> termsList = new ArrayList<>(terms); |
| Collections.sort(termsList); |
| a = Automata.makeStringUnion(termsList); |
| } |
| |
| return randomNoOp(a); |
| } |
| |
| private String getRandomString() { |
| //return TestUtil.randomSimpleString(random()); |
| return TestUtil.randomRealisticUnicodeString(random()); |
| } |
| |
| public void testRandomFinite() throws Exception { |
| |
| int numTerms = atLeast(10); |
| int iters = atLeast(100); |
| |
| if (VERBOSE) { |
| System.out.println("TEST: numTerms=" + numTerms + " iters=" + iters); |
| } |
| |
| Set<BytesRef> terms = new HashSet<>(); |
| while (terms.size() < numTerms) { |
| terms.add(new BytesRef(getRandomString())); |
| } |
| |
| Automaton a = unionTerms(terms); |
| assertSame(terms, a); |
| |
| for(int iter=0;iter<iters;iter++) { |
| if (VERBOSE) { |
| System.out.println("TEST: iter=" + iter + " numTerms=" + terms.size() + " a.numStates=" + a.getNumStates()); |
| /* |
| System.out.println(" terms:"); |
| for(BytesRef term : terms) { |
| System.out.println(" " + term); |
| } |
| */ |
| } |
| switch(random().nextInt(15)) { |
| |
| case 0: |
| // concatenate prefix |
| { |
| if (VERBOSE) { |
| System.out.println(" op=concat prefix"); |
| } |
| Set<BytesRef> newTerms = new HashSet<>(); |
| BytesRef prefix = new BytesRef(getRandomString()); |
| BytesRefBuilder newTerm = new BytesRefBuilder(); |
| for(BytesRef term : terms) { |
| newTerm.copyBytes(prefix); |
| newTerm.append(term); |
| newTerms.add(newTerm.toBytesRef()); |
| } |
| terms = newTerms; |
| boolean wasDeterministic1 = a.isDeterministic(); |
| a = Operations.concatenate(Automata.makeString(prefix.utf8ToString()), a); |
| assertEquals(wasDeterministic1, a.isDeterministic()); |
| } |
| break; |
| |
| case 1: |
| // concatenate suffix |
| { |
| BytesRef suffix = new BytesRef(getRandomString()); |
| if (VERBOSE) { |
| System.out.println(" op=concat suffix " + suffix); |
| } |
| Set<BytesRef> newTerms = new HashSet<>(); |
| BytesRefBuilder newTerm = new BytesRefBuilder(); |
| for(BytesRef term : terms) { |
| newTerm.copyBytes(term); |
| newTerm.append(suffix); |
| newTerms.add(newTerm.toBytesRef()); |
| } |
| terms = newTerms; |
| a = Operations.concatenate(a, Automata.makeString(suffix.utf8ToString())); |
| } |
| break; |
| |
| case 2: |
| // determinize |
| if (VERBOSE) { |
| System.out.println(" op=determinize"); |
| } |
| a = Operations.determinize(a, Integer.MAX_VALUE); |
| assertTrue(a.isDeterministic()); |
| break; |
| |
| case 3: |
| if (a.getNumStates() < 100) { |
| if (VERBOSE) { |
| System.out.println(" op=minimize"); |
| } |
| // minimize |
| a = MinimizationOperations.minimize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } else if (VERBOSE) { |
| System.out.println(" skip op=minimize: too many states (" + a.getNumStates() + ")"); |
| } |
| break; |
| |
| case 4: |
| // union |
| { |
| if (VERBOSE) { |
| System.out.println(" op=union"); |
| } |
| Set<BytesRef> newTerms = new HashSet<>(); |
| int numNewTerms = random().nextInt(5); |
| while (newTerms.size() < numNewTerms) { |
| newTerms.add(new BytesRef(getRandomString())); |
| } |
| terms.addAll(newTerms); |
| Automaton newA = unionTerms(newTerms); |
| a = Operations.union(a, newA); |
| } |
| break; |
| |
| case 5: |
| // optional |
| { |
| if (VERBOSE) { |
| System.out.println(" op=optional"); |
| } |
| // NOTE: This can add a dead state: |
| a = Operations.optional(a); |
| terms.add(new BytesRef()); |
| } |
| break; |
| |
| case 6: |
| // minus finite |
| { |
| if (VERBOSE) { |
| System.out.println(" op=minus finite"); |
| } |
| if (terms.size() > 0) { |
| RandomAcceptedStrings rasl = new RandomAcceptedStrings(Operations.removeDeadStates(a)); |
| Set<BytesRef> toRemove = new HashSet<>(); |
| int numToRemove = TestUtil.nextInt(random(), 1, (terms.size()+1)/2); |
| while (toRemove.size() < numToRemove) { |
| int[] ints = rasl.getRandomAcceptedString(random()); |
| BytesRef term = new BytesRef(UnicodeUtil.newString(ints, 0, ints.length)); |
| if (toRemove.contains(term) == false) { |
| toRemove.add(term); |
| } |
| } |
| for(BytesRef term : toRemove) { |
| boolean removed = terms.remove(term); |
| assertTrue(removed); |
| } |
| Automaton a2 = unionTerms(toRemove); |
| a = Operations.minus(a, a2, Integer.MAX_VALUE); |
| } |
| } |
| break; |
| |
| case 7: |
| { |
| // minus infinite |
| List<Automaton> as = new ArrayList<>(); |
| int count = TestUtil.nextInt(random(), 1, 5); |
| Set<Integer> prefixes = new HashSet<>(); |
| while(prefixes.size() < count) { |
| // prefix is a leading ascii byte; we remove <prefix>* from a |
| int prefix = random().nextInt(128); |
| prefixes.add(prefix); |
| } |
| |
| if (VERBOSE) { |
| System.out.println(" op=minus infinite prefixes=" + prefixes); |
| } |
| |
| for(int prefix : prefixes) { |
| // prefix is a leading ascii byte; we remove <prefix>* from a |
| Automaton a2 = new Automaton(); |
| int init = a2.createState(); |
| int state = a2.createState(); |
| a2.addTransition(init, state, prefix); |
| a2.setAccept(state, true); |
| a2.addTransition(state, state, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); |
| a2.finishState(); |
| as.add(a2); |
| Iterator<BytesRef> it = terms.iterator(); |
| while (it.hasNext()) { |
| BytesRef term = it.next(); |
| if (term.length > 0 && (term.bytes[term.offset] & 0xFF) == prefix) { |
| it.remove(); |
| } |
| } |
| } |
| Automaton a2 = randomNoOp(Operations.union(as)); |
| a = Operations.minus(a, a2, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } |
| break; |
| |
| case 8: |
| { |
| int count = TestUtil.nextInt(random(), 10, 20); |
| if (VERBOSE) { |
| System.out.println(" op=intersect infinite count=" + count); |
| } |
| // intersect infinite |
| List<Automaton> as = new ArrayList<>(); |
| |
| Set<Integer> prefixes = new HashSet<>(); |
| while(prefixes.size() < count) { |
| int prefix = random().nextInt(128); |
| prefixes.add(prefix); |
| } |
| if (VERBOSE) { |
| System.out.println(" prefixes=" + prefixes); |
| } |
| |
| for(int prefix : prefixes) { |
| // prefix is a leading ascii byte; we retain <prefix>* in a |
| Automaton a2 = new Automaton(); |
| int init = a2.createState(); |
| int state = a2.createState(); |
| a2.addTransition(init, state, prefix); |
| a2.setAccept(state, true); |
| a2.addTransition(state, state, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); |
| a2.finishState(); |
| as.add(a2); |
| prefixes.add(prefix); |
| } |
| |
| Automaton a2 = Operations.union(as); |
| if (random().nextBoolean()) { |
| a2 = Operations.determinize(a2, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } else if (random().nextBoolean()) { |
| a2 = MinimizationOperations.minimize(a2, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| } |
| a = Operations.intersection(a, a2); |
| |
| Iterator<BytesRef> it = terms.iterator(); |
| while (it.hasNext()) { |
| BytesRef term = it.next(); |
| if (term.length == 0 || prefixes.contains(term.bytes[term.offset]&0xff) == false) { |
| if (VERBOSE) { |
| System.out.println(" drop term=" + term); |
| } |
| it.remove(); |
| } else { |
| if (VERBOSE) { |
| System.out.println(" keep term=" + term); |
| } |
| } |
| } |
| } |
| break; |
| |
| case 9: |
| // reverse |
| { |
| if (VERBOSE) { |
| System.out.println(" op=reverse"); |
| } |
| a = Operations.reverse(a); |
| Set<BytesRef> newTerms = new HashSet<>(); |
| for(BytesRef term : terms) { |
| newTerms.add(new BytesRef(new StringBuilder(term.utf8ToString()).reverse().toString())); |
| } |
| terms = newTerms; |
| } |
| break; |
| |
| case 10: |
| if (VERBOSE) { |
| System.out.println(" op=randomNoOp"); |
| } |
| a = randomNoOp(a); |
| break; |
| |
| case 11: |
| // interval |
| { |
| int min = random().nextInt(1000); |
| int max = min + random().nextInt(50); |
| // digits must be non-zero else we make cycle |
| int digits = Integer.toString(max).length(); |
| if (VERBOSE) { |
| System.out.println(" op=union interval min=" + min + " max=" + max + " digits=" + digits); |
| } |
| a = Operations.union(a, Automata.makeDecimalInterval(min, max, digits)); |
| StringBuilder b = new StringBuilder(); |
| for(int i=0;i<digits;i++) { |
| b.append('0'); |
| } |
| String prefix = b.toString(); |
| for(int i=min;i<=max;i++) { |
| String s = Integer.toString(i); |
| if (s.length() < digits) { |
| // Left-fill with 0s |
| s = prefix.substring(s.length()) + s; |
| } |
| terms.add(new BytesRef(s)); |
| } |
| } |
| break; |
| |
| case 12: |
| if (VERBOSE) { |
| System.out.println(" op=remove the empty string"); |
| } |
| a = Operations.minus(a, Automata.makeEmptyString(), DEFAULT_DETERMINIZE_WORK_LIMIT); |
| terms.remove(new BytesRef()); |
| break; |
| |
| case 13: |
| if (VERBOSE) { |
| System.out.println(" op=add the empty string"); |
| } |
| a = Operations.union(a, Automata.makeEmptyString()); |
| terms.add(new BytesRef()); |
| break; |
| |
| case 14: |
| // Safety in case we are really unlucky w/ the dice: |
| if (terms.size() <= numTerms * 3) { |
| if (VERBOSE) { |
| System.out.println(" op=concat finite automaton"); |
| } |
| int count = random().nextBoolean() ? 2 : 3; |
| Set<BytesRef> addTerms = new HashSet<>(); |
| while (addTerms.size() < count) { |
| addTerms.add(new BytesRef(getRandomString())); |
| } |
| if (VERBOSE) { |
| for(BytesRef term : addTerms) { |
| System.out.println(" term=" + term); |
| } |
| } |
| Automaton a2 = unionTerms(addTerms); |
| Set<BytesRef> newTerms = new HashSet<>(); |
| if (random().nextBoolean()) { |
| // suffix |
| if (VERBOSE) { |
| System.out.println(" do suffix"); |
| } |
| a = Operations.concatenate(a, randomNoOp(a2)); |
| BytesRefBuilder newTerm = new BytesRefBuilder(); |
| for(BytesRef term : terms) { |
| for(BytesRef suffix : addTerms) { |
| newTerm.copyBytes(term); |
| newTerm.append(suffix); |
| newTerms.add(newTerm.toBytesRef()); |
| } |
| } |
| } else { |
| // prefix |
| if (VERBOSE) { |
| System.out.println(" do prefix"); |
| } |
| a = Operations.concatenate(randomNoOp(a2), a); |
| BytesRefBuilder newTerm = new BytesRefBuilder(); |
| for(BytesRef term : terms) { |
| for(BytesRef prefix : addTerms) { |
| newTerm.copyBytes(prefix); |
| newTerm.append(term); |
| newTerms.add(newTerm.toBytesRef()); |
| } |
| } |
| } |
| |
| terms = newTerms; |
| } |
| break; |
| default: |
| throw new AssertionError(); |
| } |
| |
| assertSame(terms, a); |
| assertEquals(AutomatonTestUtil.isDeterministicSlow(a), a.isDeterministic()); |
| |
| if (random().nextInt(10) == 7) { |
| a = verifyTopoSort(a); |
| } |
| } |
| |
| assertSame(terms, a); |
| } |
| |
| /** Runs topo sort, verifies transitions then only "go forwards", and |
| * builds and returns new automaton with those remapped toposorted states. */ |
| private Automaton verifyTopoSort(Automaton a) { |
| int[] sorted = Operations.topoSortStates(a); |
| // This can be < if we removed dead states: |
| assertTrue(sorted.length <= a.getNumStates()); |
| Automaton a2 = new Automaton(); |
| int[] stateMap = new int[a.getNumStates()]; |
| Arrays.fill(stateMap, -1); |
| Transition transition = new Transition(); |
| for(int state : sorted) { |
| int newState = a2.createState(); |
| a2.setAccept(newState, a.isAccept(state)); |
| |
| // Each state should only appear once in the sort: |
| assertEquals(-1, stateMap[state]); |
| stateMap[state] = newState; |
| } |
| |
| // 2nd pass: add new transitions |
| for(int state : sorted) { |
| int count = a.initTransition(state, transition); |
| for(int i=0;i<count;i++) { |
| a.getNextTransition(transition); |
| assert stateMap[transition.dest] > stateMap[state]; |
| a2.addTransition(stateMap[state], stateMap[transition.dest], transition.min, transition.max); |
| } |
| } |
| |
| a2.finishState(); |
| return a2; |
| } |
| |
| private void assertSame(Collection<BytesRef> terms, Automaton a) { |
| |
| try { |
| assertTrue(Operations.isFinite(a)); |
| assertFalse(Operations.isTotal(a)); |
| |
| Automaton detA = Operations.determinize(a, DEFAULT_DETERMINIZE_WORK_LIMIT); |
| |
| // Make sure all terms are accepted: |
| IntsRefBuilder scratch = new IntsRefBuilder(); |
| for(BytesRef term : terms) { |
| Util.toIntsRef(term, scratch); |
| assertTrue("failed to accept term=" + term.utf8ToString(), Operations.run(detA, term.utf8ToString())); |
| } |
| |
| // Use getFiniteStrings: |
| Set<IntsRef> expected = new HashSet<>(); |
| for(BytesRef term : terms) { |
| IntsRefBuilder intsRef = new IntsRefBuilder(); |
| Util.toUTF32(term.utf8ToString(), intsRef); |
| expected.add(intsRef.toIntsRef()); |
| } |
| Set<IntsRef> actual = TestOperations.getFiniteStrings(a); |
| |
| if (expected.equals(actual) == false) { |
| System.out.println("FAILED:"); |
| for(IntsRef term : expected) { |
| if (actual.contains(term) == false) { |
| System.out.println(" term=" + term + " should be accepted but isn't"); |
| } |
| } |
| for(IntsRef term : actual) { |
| if (expected.contains(term) == false) { |
| System.out.println(" term=" + term + " is accepted but should not be"); |
| } |
| } |
| throw new AssertionError("mismatch"); |
| } |
| |
| // Use sameLanguage: |
| Automaton a2 = Operations.removeDeadStates(Operations.determinize(unionTerms(terms), |
| Integer.MAX_VALUE)); |
| assertTrue(Operations.sameLanguage(a2, Operations.removeDeadStates(Operations.determinize(a, |
| Integer.MAX_VALUE)))); |
| |
| // Do same check, in UTF8 space |
| Automaton utf8 = randomNoOp(new UTF32ToUTF8().convert(a)); |
| |
| Set<IntsRef> expected2 = new HashSet<>(); |
| for(BytesRef term : terms) { |
| IntsRefBuilder intsRef = new IntsRefBuilder(); |
| Util.toIntsRef(term, intsRef); |
| expected2.add(intsRef.toIntsRef()); |
| } |
| assertEquals(expected2, TestOperations.getFiniteStrings(utf8)); |
| } catch (AssertionError ae) { |
| System.out.println("TEST: FAILED: not same"); |
| System.out.println(" terms (count=" + terms.size() + "):"); |
| for(BytesRef term : terms) { |
| System.out.println(" " + term); |
| } |
| System.out.println(" automaton:"); |
| System.out.println(a.toDot()); |
| //a.writeDot("fail"); |
| throw ae; |
| } |
| } |
| |
| private boolean accepts(Automaton a, BytesRef b) { |
| IntsRefBuilder intsBuilder = new IntsRefBuilder(); |
| Util.toIntsRef(b, intsBuilder); |
| return Operations.run(a, intsBuilder.toIntsRef()); |
| } |
| |
| private Automaton makeBinaryInterval(BytesRef minTerm, boolean minInclusive, |
| BytesRef maxTerm, boolean maxInclusive) { |
| |
| if (VERBOSE) { |
| System.out.println("TEST: minTerm=" + minTerm + " minInclusive=" + minInclusive + " maxTerm=" + maxTerm + " maxInclusive=" + maxInclusive); |
| } |
| |
| Automaton a = Automata.makeBinaryInterval(minTerm, minInclusive, |
| maxTerm, maxInclusive); |
| |
| Automaton minA = MinimizationOperations.minimize(a, Integer.MAX_VALUE); |
| if (minA.getNumStates() != a.getNumStates()) { |
| assertTrue(minA.getNumStates() < a.getNumStates()); |
| System.out.println("Original was not minimal:"); |
| System.out.println("Original:\n" + a.toDot()); |
| System.out.println("Minimized:\n" + minA.toDot()); |
| System.out.println("minTerm=" + minTerm + " minInclusive=" + minInclusive); |
| System.out.println("maxTerm=" + maxTerm + " maxInclusive=" + maxInclusive); |
| fail("automaton was not minimal"); |
| } |
| |
| if (VERBOSE) { |
| System.out.println(a.toDot()); |
| } |
| |
| return a; |
| } |
| |
| public void testMakeBinaryIntervalFiniteCasesBasic() throws Exception { |
| // 0 (incl) - 00 (incl) |
| byte[] zeros = new byte[3]; |
| Automaton a = makeBinaryInterval(new BytesRef(zeros, 0, 1), true, new BytesRef(zeros, 0, 2), true); |
| assertTrue(Operations.isFinite(a)); |
| assertFalse(accepts(a, new BytesRef())); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 1))); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 2))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 3))); |
| |
| // '' (incl) - 00 (incl) |
| a = makeBinaryInterval(new BytesRef(), true, new BytesRef(zeros, 0, 2), true); |
| assertTrue(Operations.isFinite(a)); |
| assertTrue(accepts(a, new BytesRef())); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 1))); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 2))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 3))); |
| |
| // '' (excl) - 00 (incl) |
| a = makeBinaryInterval(new BytesRef(), false, new BytesRef(zeros, 0, 2), true); |
| assertTrue(Operations.isFinite(a)); |
| assertFalse(accepts(a, new BytesRef())); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 1))); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 2))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 3))); |
| |
| // 0 (excl) - 00 (incl) |
| a = makeBinaryInterval(new BytesRef(zeros, 0, 1), false, new BytesRef(zeros, 0, 2), true); |
| assertTrue(Operations.isFinite(a)); |
| assertFalse(accepts(a, new BytesRef())); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 1))); |
| assertTrue(accepts(a, new BytesRef(zeros, 0, 2))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 3))); |
| |
| // 0 (excl) - 00 (excl) |
| a = makeBinaryInterval(new BytesRef(zeros, 0, 1), false, new BytesRef(zeros, 0, 2), false); |
| assertTrue(Operations.isFinite(a)); |
| assertFalse(accepts(a, new BytesRef())); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 1))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 2))); |
| assertFalse(accepts(a, new BytesRef(zeros, 0, 3))); |
| } |
| |
| public void testMakeBinaryIntervalFiniteCasesRandom() throws Exception { |
| int iters = atLeast(100); |
| for(int iter=0;iter<iters;iter++) { |
| BytesRef prefix = new BytesRef(TestUtil.randomRealisticUnicodeString(random())); |
| |
| BytesRefBuilder b = new BytesRefBuilder(); |
| b.append(prefix); |
| int numZeros = random().nextInt(10); |
| for(int i=0;i<numZeros;i++) { |
| b.append((byte) 0); |
| } |
| BytesRef minTerm = b.get(); |
| |
| b = new BytesRefBuilder(); |
| b.append(minTerm); |
| numZeros = random().nextInt(10); |
| for(int i=0;i<numZeros;i++) { |
| b.append((byte) 0); |
| } |
| BytesRef maxTerm = b.get(); |
| |
| boolean minInclusive = random().nextBoolean(); |
| boolean maxInclusive = random().nextBoolean(); |
| Automaton a = makeBinaryInterval(minTerm, minInclusive, |
| maxTerm, maxInclusive); |
| assertTrue(Operations.isFinite(a)); |
| int expectedCount = maxTerm.length - minTerm.length + 1; |
| if (minInclusive == false) { |
| expectedCount--; |
| } |
| if (maxInclusive == false) { |
| expectedCount--; |
| } |
| |
| if (expectedCount <= 0) { |
| assertTrue(Operations.isEmpty(a)); |
| continue; |
| } else { |
| // Enumerate all finite strings and verify the count matches what we expect: |
| assertEquals(expectedCount, TestOperations.getFiniteStrings(a, expectedCount).size()); |
| } |
| |
| b = new BytesRefBuilder(); |
| b.append(minTerm); |
| if (minInclusive == false) { |
| assertFalse(accepts(a, b.get())); |
| b.append((byte) 0); |
| } |
| while (b.length() < maxTerm.length) { |
| b.append((byte) 0); |
| |
| boolean expected; |
| if (b.length() == maxTerm.length) { |
| expected = maxInclusive; |
| } else { |
| expected = true; |
| } |
| assertEquals(expected, accepts(a, b.get())); |
| } |
| } |
| } |
| |
| public void testMakeBinaryIntervalRandom() throws Exception { |
| int iters = atLeast(100); |
| for(int iter=0;iter<iters;iter++) { |
| BytesRef minTerm = TestUtil.randomBinaryTerm(random()); |
| boolean minInclusive = random().nextBoolean(); |
| BytesRef maxTerm = TestUtil.randomBinaryTerm(random()); |
| boolean maxInclusive = random().nextBoolean(); |
| |
| Automaton a = makeBinaryInterval(minTerm, minInclusive, maxTerm, maxInclusive); |
| |
| for(int iter2=0;iter2<500;iter2++) { |
| BytesRef term = TestUtil.randomBinaryTerm(random()); |
| int minCmp = minTerm.compareTo(term); |
| int maxCmp = maxTerm.compareTo(term); |
| |
| boolean expected; |
| if (minCmp > 0 || maxCmp < 0) { |
| expected = false; |
| } else if (minCmp == 0 && maxCmp == 0) { |
| expected = minInclusive && maxInclusive; |
| } else if (minCmp == 0) { |
| expected = minInclusive; |
| } else if (maxCmp == 0) { |
| expected = maxInclusive; |
| } else { |
| expected = true; |
| } |
| |
| if (VERBOSE) { |
| System.out.println(" check term=" + term + " expected=" + expected); |
| } |
| IntsRefBuilder intsBuilder = new IntsRefBuilder(); |
| Util.toIntsRef(term, intsBuilder); |
| assertEquals(expected, Operations.run(a, intsBuilder.toIntsRef())); |
| } |
| } |
| } |
| |
| private static IntsRef intsRef(String s) { |
| IntsRefBuilder intsBuilder = new IntsRefBuilder(); |
| Util.toIntsRef(new BytesRef(s), intsBuilder); |
| return intsBuilder.toIntsRef(); |
| } |
| |
| public void testMakeBinaryIntervalBasic() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef("bar"), true, new BytesRef("foo"), true); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertTrue(Operations.run(a, intsRef("foo"))); |
| assertTrue(Operations.run(a, intsRef("beep"))); |
| assertFalse(Operations.run(a, intsRef("baq"))); |
| assertTrue(Operations.run(a, intsRef("bara"))); |
| } |
| |
| public void testMakeBinaryIntervalLowerBoundEmptyString() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef(""), true, new BytesRef("bar"), true); |
| assertTrue(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertFalse(Operations.run(a, intsRef("bara"))); |
| assertFalse(Operations.run(a, intsRef("baz"))); |
| |
| |
| a = Automata.makeBinaryInterval(new BytesRef(""), false, new BytesRef("bar"), true); |
| assertFalse(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertFalse(Operations.run(a, intsRef("bara"))); |
| assertFalse(Operations.run(a, intsRef("baz"))); |
| } |
| |
| public void testMakeBinaryIntervalEqual() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef("bar"), true, new BytesRef("bar"), true); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertTrue(Operations.isFinite(a)); |
| assertEquals(1, TestOperations.getFiniteStrings(a).size()); |
| } |
| |
| public void testMakeBinaryIntervalCommonPrefix() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef("bar"), true, new BytesRef("barfoo"), true); |
| assertFalse(Operations.run(a, intsRef("bam"))); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertTrue(Operations.run(a, intsRef("bara"))); |
| assertTrue(Operations.run(a, intsRef("barf"))); |
| assertTrue(Operations.run(a, intsRef("barfo"))); |
| assertTrue(Operations.run(a, intsRef("barfoo"))); |
| assertTrue(Operations.run(a, intsRef("barfonz"))); |
| assertFalse(Operations.run(a, intsRef("barfop"))); |
| assertFalse(Operations.run(a, intsRef("barfoop"))); |
| } |
| |
| public void testMakeBinaryExceptEmpty() throws Exception { |
| Automaton a = Automata.makeNonEmptyBinary(); |
| assertFalse(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef(TestUtil.randomRealisticUnicodeString(random(), 1, 10)))); |
| } |
| |
| public void testMakeBinaryIntervalOpenMax() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef("bar"), true, null, true); |
| assertFalse(Operations.run(a, intsRef("bam"))); |
| assertTrue(Operations.run(a, intsRef("bar"))); |
| assertTrue(Operations.run(a, intsRef("bara"))); |
| assertTrue(Operations.run(a, intsRef("barf"))); |
| assertTrue(Operations.run(a, intsRef("barfo"))); |
| assertTrue(Operations.run(a, intsRef("barfoo"))); |
| assertTrue(Operations.run(a, intsRef("barfonz"))); |
| assertTrue(Operations.run(a, intsRef("barfop"))); |
| assertTrue(Operations.run(a, intsRef("barfoop"))); |
| assertTrue(Operations.run(a, intsRef("zzz"))); |
| } |
| |
| public void testMakeBinaryIntervalOpenMaxZeroLengthMin() throws Exception { |
| // when including min, automaton should accept "a" |
| Automaton a = Automata.makeBinaryInterval(new BytesRef(""), true, null, true); |
| assertTrue(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("aaaaaa"))); |
| // excluding min should still accept "a" |
| a = Automata.makeBinaryInterval(new BytesRef(""), false, null, true); |
| assertFalse(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("aaaaaa"))); |
| } |
| |
| public void testMakeBinaryIntervalOpenMin() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(null, true, new BytesRef("foo"), true); |
| assertFalse(Operations.run(a, intsRef("foz"))); |
| assertFalse(Operations.run(a, intsRef("zzz"))); |
| assertTrue(Operations.run(a, intsRef("foo"))); |
| assertTrue(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("aaa"))); |
| assertTrue(Operations.run(a, intsRef("bz"))); |
| } |
| |
| public void testMakeBinaryIntervalOpenBoth() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(null, true, null, true); |
| assertTrue(Operations.run(a, intsRef("foz"))); |
| assertTrue(Operations.run(a, intsRef("zzz"))); |
| assertTrue(Operations.run(a, intsRef("foo"))); |
| assertTrue(Operations.run(a, intsRef(""))); |
| assertTrue(Operations.run(a, intsRef("a"))); |
| assertTrue(Operations.run(a, intsRef("aaa"))); |
| assertTrue(Operations.run(a, intsRef("bz"))); |
| } |
| |
| public void testAcceptAllEmptyStringMin() throws Exception { |
| Automaton a = Automata.makeBinaryInterval(new BytesRef(), true, null, true); |
| assertTrue(Operations.sameLanguage(Automata.makeAnyBinary(), a)); |
| } |
| |
| private static IntsRef toIntsRef(String s) { |
| IntsRefBuilder b = new IntsRefBuilder(); |
| for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) { |
| cp = s.codePointAt(i); |
| b.append(cp); |
| } |
| |
| return b.get(); |
| } |
| |
| public void testGetSingleton() { |
| int iters = atLeast(10000); |
| for(int iter=0;iter<iters;iter++) { |
| String s = TestUtil.randomRealisticUnicodeString(random()); |
| Automaton a = Automata.makeString(s); |
| assertEquals(toIntsRef(s), Operations.getSingleton(a)); |
| } |
| } |
| |
| public void testGetSingletonEmptyString() { |
| Automaton a = new Automaton(); |
| int s = a.createState(); |
| a.setAccept(s, true); |
| a.finishState(); |
| assertEquals(new IntsRef(), Operations.getSingleton(a)); |
| } |
| |
| public void testGetSingletonNothing() { |
| Automaton a = new Automaton(); |
| a.createState(); |
| a.finishState(); |
| assertNull(Operations.getSingleton(a)); |
| } |
| |
| public void testGetSingletonTwo() { |
| Automaton a = new Automaton(); |
| int s = a.createState(); |
| int x = a.createState(); |
| a.setAccept(x, true); |
| a.addTransition(s, x, 55); |
| int y = a.createState(); |
| a.setAccept(y, true); |
| a.addTransition(s, y, 58); |
| a.finishState(); |
| assertNull(Operations.getSingleton(a)); |
| } |
| |
| // LUCENE-9981 |
| public void testDeterminizeTooMuchEffort() { |
| // make sure determinize properly aborts, relatively quickly, for this regexp: |
| expectThrows( |
| TooComplexToDeterminizeException.class, |
| () -> { |
| Automaton a = new RegExp("(.*a){2000}").toAutomaton(); |
| Operations.determinize(a, Operations.DEFAULT_DETERMINIZE_WORK_LIMIT); |
| }); |
| // ... and for its reversed form too: |
| expectThrows( |
| TooComplexToDeterminizeException.class, |
| () -> { |
| Automaton a = new RegExp("(.*a){2000}").toAutomaton(); |
| a = Operations.reverse(a); |
| Operations.determinize(a, Operations.DEFAULT_DETERMINIZE_WORK_LIMIT); |
| }); |
| } |
| } |
