Author: rsmith
Date: Mon Sep 30 17:47:41 2019
New Revision: 373281
URL: http://llvm.org/viewvc/llvm-project?rev=373281&view=rev
Log:
[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.
Added:
cfe/trunk/test/SemaCXX/constexpr-turing-cxx2a.cpp
Added: cfe/trunk/test/SemaCXX/constexpr-turing-cxx2a.cpp
URL:
http://llvm.org/viewvc/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing-cxx2a.cpp?rev=373281&view=auto
==============================================================================
--- cfe/trunk/test/SemaCXX/constexpr-turing-cxx2a.cpp (added)
+++ cfe/trunk/test/SemaCXX/constexpr-turing-cxx2a.cpp Mon Sep 30 17:47:41 2019
@@ -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, "");
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
