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/STLExtras.h"
10 #include "llvm/Support/Debug.h"
11 #include "llvm/Support/Automaton.h"
12 #include "gmock/gmock.h"
13 #include "gtest/gtest.h"
14
15 using namespace llvm;
16 using testing::ContainerEq;
17 using testing::UnorderedElementsAre;
18
19 // Bring in the enums created by SearchableTables.td.
20 #define GET_SymKind_DECL
21 #define GET_BinRequirementKindEnum_DECL
22 #include "AutomataTables.inc"
23
24 // And bring in the automata from Automata.td.
25 #define GET_SimpleAutomaton_DECL
26 #define GET_TupleAutomaton_DECL
27 #define GET_NfaAutomaton_DECL
28 #define GET_BinPackerAutomaton_DECL
29 #include "AutomataAutomata.inc"
30
TEST(Automata,SimpleAutomatonAcceptsFromInitialState)31 TEST(Automata, SimpleAutomatonAcceptsFromInitialState) {
32 Automaton<SymKind> A{ArrayRef(SimpleAutomatonTransitions)};
33 EXPECT_TRUE(A.add(SK_a));
34 A.reset();
35 EXPECT_TRUE(A.add(SK_b));
36 A.reset();
37 EXPECT_TRUE(A.add(SK_c));
38 A.reset();
39 EXPECT_FALSE(A.add(SK_d));
40 }
41
TEST(Automata,SimpleAutomatonAcceptsSequences)42 TEST(Automata, SimpleAutomatonAcceptsSequences) {
43 Automaton<SymKind> A{ArrayRef(SimpleAutomatonTransitions)};
44 // Test sequence <a b>
45 A.reset();
46 EXPECT_TRUE(A.add(SK_a));
47 EXPECT_TRUE(A.add(SK_b));
48
49 // Test sequence <a c> is rejected (c cannot get bit 0b10);
50 A.reset();
51 EXPECT_TRUE(A.add(SK_a));
52 EXPECT_FALSE(A.add(SK_c));
53
54 // Symmetric test: sequence <c a> is rejected.
55 A.reset();
56 EXPECT_TRUE(A.add(SK_c));
57 EXPECT_FALSE(A.add(SK_a));
58 }
59
TEST(Automata,TupleAutomatonAccepts)60 TEST(Automata, TupleAutomatonAccepts) {
61 Automaton<TupleAutomatonAction> A{ArrayRef(TupleAutomatonTransitions)};
62 A.reset();
63 EXPECT_TRUE(
64 A.add(TupleAutomatonAction{SK_a, SK_b, "yeet"}));
65 A.reset();
66 EXPECT_FALSE(
67 A.add(TupleAutomatonAction{SK_a, SK_a, "yeet"}));
68 A.reset();
69 EXPECT_FALSE(
70 A.add(TupleAutomatonAction{SK_a, SK_b, "feet"}));
71 A.reset();
72 EXPECT_TRUE(
73 A.add(TupleAutomatonAction{SK_b, SK_b, "foo"}));
74 }
75
TEST(Automata,NfaAutomatonAccepts)76 TEST(Automata, NfaAutomatonAccepts) {
77 Automaton<SymKind> A{ArrayRef(NfaAutomatonTransitions)};
78
79 // Test sequences <a a>, <a b>, <b a>, <b b>. All should be accepted.
80 A.reset();
81 EXPECT_TRUE(A.add(SK_a));
82 EXPECT_TRUE(A.add(SK_a));
83 A.reset();
84 EXPECT_TRUE(A.add(SK_a));
85 EXPECT_TRUE(A.add(SK_b));
86 A.reset();
87 EXPECT_TRUE(A.add(SK_b));
88 EXPECT_TRUE(A.add(SK_a));
89 A.reset();
90 EXPECT_TRUE(A.add(SK_b));
91 EXPECT_TRUE(A.add(SK_b));
92
93 // Expect that <b b b> is not accepted.
94 A.reset();
95 EXPECT_TRUE(A.add(SK_b));
96 EXPECT_TRUE(A.add(SK_b));
97 EXPECT_FALSE(A.add(SK_b));
98 }
99
TEST(Automata,BinPackerAutomatonAccepts)100 TEST(Automata, BinPackerAutomatonAccepts) {
101 Automaton<BinPackerAutomatonAction> A{
102 ArrayRef(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
TEST(Automata,BinPackerAutomatonExplains)131 TEST(Automata, BinPackerAutomatonExplains) {
132 Automaton<BinPackerAutomatonAction> A{
133 ArrayRef(BinPackerAutomatonTransitions),
134 ArrayRef(BinPackerAutomatonTransitionInfo)};
135 // Pack two double-bins in 0-4, then a single bin in 0-6.
136 EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
137 EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
138 EXPECT_TRUE(A.add(BRK_0_to_6));
139 EXPECT_THAT(
140 A.getNfaPaths(),
141 UnorderedElementsAre(
142 // Allocate {0,1} first, then 6.
143 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
144 BINS(1, 0, 1, 1, 1, 1)}),
145 // Allocate {0,1} first, then 5.
146 ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
147 BINS(0, 1, 1, 1, 1, 1)}),
148 // Allocate {2,3} first, then 6.
149 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
150 BINS(1, 0, 1, 1, 1, 1)}),
151 // Allocate {2,3} first, then 5.
152 ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
153 BINS(0, 1, 1, 1, 1, 1)})));
154 }
155