From 43d2820e2f5a45c39604feaed7a23f05e7889b5d Mon Sep 17 00:00:00 2001
From: Richard Smith <richard-llvm@metafoo.co.uk>
Date: Tue, 1 Oct 2019 00:47:41 +0000
Subject: [PATCH] [c++20] Add a C++20 version of the existing turing machine
 test.

Unlike the C++11 version, this one uese mutable state and dynamic
allocation instead of a carefully balanced and ever-accumulating pile of
temporaries.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@373281 91177308-0d34-0410-b5e6-96231b3b80d8
---
 test/SemaCXX/constexpr-turing-cxx2a.cpp | 66 +++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
 create mode 100644 test/SemaCXX/constexpr-turing-cxx2a.cpp

diff --git a/test/SemaCXX/constexpr-turing-cxx2a.cpp b/test/SemaCXX/constexpr-turing-cxx2a.cpp
new file mode 100644
index 0000000000..0941cf408f
--- /dev/null
+++ b/test/SemaCXX/constexpr-turing-cxx2a.cpp
@@ -0,0 +1,66 @@
+// RUN: %clang_cc1 -verify -std=c++2a %s
+// expected-no-diagnostics
+
+const unsigned halt = (unsigned)-1;
+
+enum Dir { L, R };
+struct Action {
+  bool tape;
+  Dir dir;
+  unsigned next;
+};
+using State = Action[2];
+
+// An infinite tape!
+struct Tape {
+  constexpr Tape() = default;
+  constexpr ~Tape() {
+    if (l) { l->r = nullptr; delete l; }
+    if (r) { r->l = nullptr; delete r; }
+  }
+  constexpr Tape *left() {
+    if (!l) { l = new Tape; l->r = this; }
+    return l;
+  }
+  constexpr Tape *right() {
+    if (!r) { r = new Tape; r->l = this; }
+    return r;
+  }
+  Tape *l = nullptr;
+  bool val = false;
+  Tape *r = nullptr;
+};
+
+// Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
+// steps taken until halt.
+constexpr unsigned run(const State *tm) {
+  Tape *tape = new Tape;
+  unsigned state = 0;
+  unsigned steps = 0;
+
+  for (state = 0; state != halt; ++steps) {
+    auto [val, dir, next_state] = tm[state][tape->val];
+    tape->val = val;
+    tape = (dir == L ? tape->left() : tape->right());
+    state = next_state;
+  }
+
+  delete tape;
+  return steps;
+}
+
+// 3-state busy beaver. S(bb3) = 21.
+constexpr State bb3[] = {
+  { { true, R, 1 }, { true, R, halt } },
+  { { true, L, 1 }, { false, R, 2 } },
+  { { true, L, 2 }, { true, L, 0 } }
+};
+static_assert(run(bb3) == 21, "");
+
+// 4-state busy beaver. S(bb4) = 107.
+constexpr State bb4[] = {
+  { { true, R, 1 }, { true, L, 1 } },
+  { { true, L, 0 }, { false, L, 2 } },
+  { { true, R, halt }, { true, L, 3 } },
+  { { true, R, 3 }, { false, R, 0 } } };
+static_assert(run(bb4) == 107, "");
-- 
2.50.1