155 lines · cpp
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-exception6//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_DECL21#define GET_BinRequirementKindEnum_DECL22#include "AutomataTables.inc"23 24// And bring in the automata from Automata.td.25#define GET_SimpleAutomaton_DECL26#define GET_TupleAutomaton_DECL27#define GET_NfaAutomaton_DECL28#define GET_BinPackerAutomaton_DECL29#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 no111 // 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, then120 // 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