clang/test/SemaCXX/constexpr-turing-cxx2a.cpp

   1 // RUN: %clang_cc1 -verify -std=c++2a %s
   2 // expected-no-diagnostics
   3
   4 const unsigned halt = (unsigned)-1;
   5
   6 enum Dir { L, R };
   7 struct Action {
   8   bool tape;
   9   Dir dir;
  10   unsigned next;
  11 };
  12 using State = Action[2];
  13
  14 // An infinite tape!
  15 struct Tape {
  16   constexpr Tape() = default;
  17   constexpr ~Tape() {
  18     if (l) { l->r = nullptr; delete l; }
  19     if (r) { r->l = nullptr; delete r; }
  20   }
  21   constexpr Tape *left() {
  22     if (!l) { l = new Tape; l->r = this; }
  23     return l;
  24   }
  25   constexpr Tape *right() {
  26     if (!r) { r = new Tape; r->l = this; }
  27     return r;
  28   }
  29   Tape *l = nullptr;
  30   bool val = false;
  31   Tape *r = nullptr;
  32 };
  33
  34 // Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
  35 // steps taken until halt.
  36 constexpr unsigned run(const State *tm) {
  37   Tape *tape = new Tape;
  38   unsigned state = 0;
  39   unsigned steps = 0;
  40
  41   for (state = 0; state != halt; ++steps) {
  42     auto [val, dir, next_state] = tm[state][tape->val];
  43     tape->val = val;
  44     tape = (dir == L ? tape->left() : tape->right());
  45     state = next_state;
  46   }
  47
  48   delete tape;
  49   return steps;
  50 }
  51
  52 // 3-state busy beaver. S(bb3) = 21.
  53 constexpr State bb3[] = {
  54   { { true, R, 1 }, { true, R, halt } },
  55   { { true, L, 1 }, { false, R, 2 } },
  56   { { true, L, 2 }, { true, L, 0 } }
  57 };
  58 static_assert(run(bb3) == 21, "");
  59
  60 // 4-state busy beaver. S(bb4) = 107.
  61 constexpr State bb4[] = {
  62   { { true, R, 1 }, { true, L, 1 } },
  63   { { true, L, 0 }, { false, L, 2 } },
  64   { { true, R, halt }, { true, L, 3 } },
  65   { { true, R, 3 }, { false, R, 0 } } };
  66 static_assert(run(bb4) == 107, "");