1 //===- unittest/TableGen/AutomataTest.cpp - DFA tests ---------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/ADT/ArrayRef.h" 10 #include "llvm/ADT/STLExtras.h" 11 #include "llvm/Support/Debug.h" 12 #include "llvm/Support/Automaton.h" 13 #include "gmock/gmock.h" 14 #include "gtest/gtest.h" 15 16 using namespace llvm; 17 using testing::ContainerEq; 18 using testing::UnorderedElementsAre; 19 20 // Bring in the enums created by SearchableTables.td. 21 #define GET_SymKind_DECL 22 #define GET_BinRequirementKindEnum_DECL 23 #include "AutomataTables.inc" 24 25 // And bring in the automata from Automata.td. 26 #define GET_SimpleAutomaton_DECL 27 #define GET_TupleAutomaton_DECL 28 #define GET_NfaAutomaton_DECL 29 #define GET_BinPackerAutomaton_DECL 30 #include "AutomataAutomata.inc" 31 32 TEST(Automata, SimpleAutomatonAcceptsFromInitialState) { 33 Automaton<SymKind> A(makeArrayRef(SimpleAutomatonTransitions)); 34 EXPECT_TRUE(A.add(SK_a)); 35 A.reset(); 36 EXPECT_TRUE(A.add(SK_b)); 37 A.reset(); 38 EXPECT_TRUE(A.add(SK_c)); 39 A.reset(); 40 EXPECT_FALSE(A.add(SK_d)); 41 } 42 43 TEST(Automata, SimpleAutomatonAcceptsSequences) { 44 Automaton<SymKind> A(makeArrayRef(SimpleAutomatonTransitions)); 45 // Test sequence <a b> 46 A.reset(); 47 EXPECT_TRUE(A.add(SK_a)); 48 EXPECT_TRUE(A.add(SK_b)); 49 50 // Test sequence <a c> is rejected (c cannot get bit 0b10); 51 A.reset(); 52 EXPECT_TRUE(A.add(SK_a)); 53 EXPECT_FALSE(A.add(SK_c)); 54 55 // Symmetric test: sequence <c a> is rejected. 56 A.reset(); 57 EXPECT_TRUE(A.add(SK_c)); 58 EXPECT_FALSE(A.add(SK_a)); 59 } 60 61 TEST(Automata, TupleAutomatonAccepts) { 62 Automaton<TupleAutomatonAction> A(makeArrayRef(TupleAutomatonTransitions)); 63 A.reset(); 64 EXPECT_TRUE( 65 A.add(TupleAutomatonAction{SK_a, SK_b, "yeet"})); 66 A.reset(); 67 EXPECT_FALSE( 68 A.add(TupleAutomatonAction{SK_a, SK_a, "yeet"})); 69 A.reset(); 70 EXPECT_FALSE( 71 A.add(TupleAutomatonAction{SK_a, SK_b, "feet"})); 72 A.reset(); 73 EXPECT_TRUE( 74 A.add(TupleAutomatonAction{SK_b, SK_b, "foo"})); 75 } 76 77 TEST(Automata, NfaAutomatonAccepts) { 78 Automaton<SymKind> A(makeArrayRef(NfaAutomatonTransitions)); 79 80 // Test sequences <a a>, <a b>, <b a>, <b b>. All should be accepted. 81 A.reset(); 82 EXPECT_TRUE(A.add(SK_a)); 83 EXPECT_TRUE(A.add(SK_a)); 84 A.reset(); 85 EXPECT_TRUE(A.add(SK_a)); 86 EXPECT_TRUE(A.add(SK_b)); 87 A.reset(); 88 EXPECT_TRUE(A.add(SK_b)); 89 EXPECT_TRUE(A.add(SK_a)); 90 A.reset(); 91 EXPECT_TRUE(A.add(SK_b)); 92 EXPECT_TRUE(A.add(SK_b)); 93 94 // Expect that <b b b> is not accepted. 95 A.reset(); 96 EXPECT_TRUE(A.add(SK_b)); 97 EXPECT_TRUE(A.add(SK_b)); 98 EXPECT_FALSE(A.add(SK_b)); 99 } 100 101 TEST(Automata, BinPackerAutomatonAccepts) { 102 Automaton<BinPackerAutomatonAction> A(makeArrayRef(BinPackerAutomatonTransitions)); 103 104 // Expect that we can pack two double-bins in 0-4, then no more in 0-4. 105 A.reset(); 106 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 107 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 108 EXPECT_FALSE(A.add(BRK_0_to_4)); 109 110 // Expect that we can pack two double-bins in 0-4, two more in 0-6 then no 111 // more. 112 A.reset(); 113 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 114 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 115 EXPECT_TRUE(A.add(BRK_0_to_6)); 116 EXPECT_TRUE(A.add(BRK_0_to_6)); 117 EXPECT_FALSE(A.add(BRK_0_to_6)); 118 119 // Expect that we can pack BRK_0_to_6 five times to occupy five bins, then 120 // cannot allocate any double-bins. 121 A.reset(); 122 for (unsigned I = 0; I < 5; ++I) 123 EXPECT_TRUE(A.add(BRK_0_to_6)); 124 EXPECT_FALSE(A.add(BRK_0_to_6_dbl)); 125 } 126 127 // The state we defined in TableGen uses the least significant 6 bits to represent a bin state. 128 #define BINS(a, b, c, d, e, f) \ 129 ((a << 5) | (b << 4) | (c << 3) | (d << 2) | (e << 1) | (f << 0)) 130 131 TEST(Automata, BinPackerAutomatonExplains) { 132 Automaton<BinPackerAutomatonAction> A(makeArrayRef(BinPackerAutomatonTransitions), 133 makeArrayRef(BinPackerAutomatonTransitionInfo)); 134 // Pack two double-bins in 0-4, then a single bin in 0-6. 135 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 136 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 137 EXPECT_TRUE(A.add(BRK_0_to_6)); 138 EXPECT_THAT( 139 A.getNfaPaths(), 140 UnorderedElementsAre( 141 // Allocate {0,1} first, then 6. 142 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1), 143 BINS(1, 0, 1, 1, 1, 1)}), 144 // Allocate {0,1} first, then 5. 145 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1), 146 BINS(0, 1, 1, 1, 1, 1)}), 147 // Allocate {2,3} first, then 6. 148 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1), 149 BINS(1, 0, 1, 1, 1, 1)}), 150 // Allocate {2,3} first, then 5. 151 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1), 152 BINS(0, 1, 1, 1, 1, 1)}))); 153 } 154