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