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
15using namespace llvm;
16using testing::ContainerEq;
17using 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
31TEST(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
42TEST(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
60TEST(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
76TEST(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
100TEST(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
131TEST(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

source code of llvm/unittests/TableGen/AutomataTest.cpp