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, "");
67