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{ArrayRef(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{ArrayRef(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{ArrayRef(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{ArrayRef(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{ 103 ArrayRef(BinPackerAutomatonTransitions)}; 104 105 // Expect that we can pack two double-bins in 0-4, then no more in 0-4. 106 A.reset(); 107 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 108 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 109 EXPECT_FALSE(A.add(BRK_0_to_4)); 110 111 // Expect that we can pack two double-bins in 0-4, two more in 0-6 then no 112 // more. 113 A.reset(); 114 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 115 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 116 EXPECT_TRUE(A.add(BRK_0_to_6)); 117 EXPECT_TRUE(A.add(BRK_0_to_6)); 118 EXPECT_FALSE(A.add(BRK_0_to_6)); 119 120 // Expect that we can pack BRK_0_to_6 five times to occupy five bins, then 121 // cannot allocate any double-bins. 122 A.reset(); 123 for (unsigned I = 0; I < 5; ++I) 124 EXPECT_TRUE(A.add(BRK_0_to_6)); 125 EXPECT_FALSE(A.add(BRK_0_to_6_dbl)); 126 } 127 128 // The state we defined in TableGen uses the least significant 6 bits to represent a bin state. 129 #define BINS(a, b, c, d, e, f) \ 130 ((a << 5) | (b << 4) | (c << 3) | (d << 2) | (e << 1) | (f << 0)) 131 132 TEST(Automata, BinPackerAutomatonExplains) { 133 Automaton<BinPackerAutomatonAction> A{ 134 ArrayRef(BinPackerAutomatonTransitions), 135 ArrayRef(BinPackerAutomatonTransitionInfo)}; 136 // Pack two double-bins in 0-4, then a single bin in 0-6. 137 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 138 EXPECT_TRUE(A.add(BRK_0_to_4_dbl)); 139 EXPECT_TRUE(A.add(BRK_0_to_6)); 140 EXPECT_THAT( 141 A.getNfaPaths(), 142 UnorderedElementsAre( 143 // Allocate {0,1} first, then 6. 144 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1), 145 BINS(1, 0, 1, 1, 1, 1)}), 146 // Allocate {0,1} first, then 5. 147 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1), 148 BINS(0, 1, 1, 1, 1, 1)}), 149 // Allocate {2,3} first, then 6. 150 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1), 151 BINS(1, 0, 1, 1, 1, 1)}), 152 // Allocate {2,3} first, then 5. 153 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1), 154 BINS(0, 1, 1, 1, 1, 1)}))); 155 } 156