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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |