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(makeArrayRef(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(makeArrayRef(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(makeArrayRef(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(makeArrayRef(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(makeArrayRef(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(makeArrayRef(BinPackerAutomatonTransitions),
 133                                         makeArrayRef(BinPackerAutomatonTransitionInfo));
 134   // Pack two double-bins in 0-4, then a single bin in 0-6.
 135   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 136   EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
 137   EXPECT_TRUE(A.add(BRK_0_to_6));
 138   EXPECT_THAT(
 139       A.getNfaPaths(),
 140       UnorderedElementsAre(
 141           // Allocate {0,1} first, then 6.
 142           ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
 143                               BINS(1, 0, 1, 1, 1, 1)}),
 144           // Allocate {0,1} first, then 5.
 145           ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
 146                               BINS(0, 1, 1, 1, 1, 1)}),
 147           // Allocate {2,3} first, then 6.
 148           ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
 149                               BINS(1, 0, 1, 1, 1, 1)}),
 150           // Allocate {2,3} first, then 5.
 151           ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
 152                               BINS(0, 1, 1, 1, 1, 1)})));
 153 }