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
TEST(Automata,SimpleAutomatonAcceptsFromInitialState)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
TEST(Automata,SimpleAutomatonAcceptsSequences)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
TEST(Automata,TupleAutomatonAccepts)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
TEST(Automata,NfaAutomatonAccepts)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
TEST(Automata,BinPackerAutomatonAccepts)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
TEST(Automata,BinPackerAutomatonExplains)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