llvm/unittests/TableGen/AutomataTest.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-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
  32 TEST(Automata, SimpleAutomatonAcceptsFromInitialState) {
  33   Automaton<SymKind> A{ArrayRef(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
  43 TEST(Automata, SimpleAutomatonAcceptsSequences) {
  44   Automaton<SymKind> A{ArrayRef(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
  61 TEST(Automata, TupleAutomatonAccepts) {
  62   Automaton<TupleAutomatonAction> A{ArrayRef(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
  77 TEST(Automata, NfaAutomatonAccepts) {
  78   Automaton<SymKind> A{ArrayRef(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
 101 TEST(Automata, BinPackerAutomatonAccepts) {
 102   Automaton<BinPackerAutomatonAction> A{
 103       ArrayRef(BinPackerAutomatonTransitions)};
 104
 105   // Expect that we can pack two double-bins in 0-4, then no more in 0-4.
 106   A.reset();
 107   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 108   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 109   EXPECT_FALSE(A.add(BRK_0_to_4));
 110
 111   // Expect that we can pack two double-bins in 0-4, two more in 0-6 then no
 112   // more.
 113   A.reset();
 114   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 115   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 116   EXPECT_TRUE(A.add(BRK_0_to_6));
 117   EXPECT_TRUE(A.add(BRK_0_to_6));
 118   EXPECT_FALSE(A.add(BRK_0_to_6));
 119
 120   // Expect that we can pack BRK_0_to_6 five times to occupy five bins, then
 121   // cannot allocate any double-bins.
 122   A.reset();
 123   for (unsigned I = 0; I < 5; ++I)
 124     EXPECT_TRUE(A.add(BRK_0_to_6));
 125   EXPECT_FALSE(A.add(BRK_0_to_6_dbl));
 126 }
 127
 128 // The state we defined in TableGen uses the least significant 6 bits to represent a bin state.
 129 #define BINS(a, b, c, d, e, f)                                                 \
 130   ((a << 5) | (b << 4) | (c << 3) | (d << 2) | (e << 1) | (f << 0))
 131
 132 TEST(Automata, BinPackerAutomatonExplains) {
 133   Automaton<BinPackerAutomatonAction> A{
 134       ArrayRef(BinPackerAutomatonTransitions),
 135       ArrayRef(BinPackerAutomatonTransitionInfo)};
 136   // Pack two double-bins in 0-4, then a single bin in 0-6.
 137   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 138   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 139   EXPECT_TRUE(A.add(BRK_0_to_6));
 140   EXPECT_THAT(
 141       A.getNfaPaths(),
 142       UnorderedElementsAre(
 143           // Allocate {0,1} first, then 6.
 144           ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
 145                               BINS(1, 0, 1, 1, 1, 1)}),
 146           // Allocate {0,1} first, then 5.
 147           ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
 148                               BINS(0, 1, 1, 1, 1, 1)}),
 149           // Allocate {2,3} first, then 6.
 150           ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
 151                               BINS(1, 0, 1, 1, 1, 1)}),
 152           // Allocate {2,3} first, then 5.
 153           ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
 154                               BINS(0, 1, 1, 1, 1, 1)})));
 155 }