1*67e74705SXin Li // RUN: %clang_cc1 -verify -std=c++11 %s
2*67e74705SXin Li // expected-no-diagnostics
3*67e74705SXin Li
4*67e74705SXin Li // A direct proof that constexpr is Turing-complete, once DR1454 is implemented.
5*67e74705SXin Li
6*67e74705SXin Li const unsigned halt = (unsigned)-1;
7*67e74705SXin Li
8*67e74705SXin Li enum Dir { L, R };
9*67e74705SXin Li struct Action {
10*67e74705SXin Li bool tape;
11*67e74705SXin Li Dir dir;
12*67e74705SXin Li unsigned next;
13*67e74705SXin Li };
14*67e74705SXin Li using State = Action[2];
15*67e74705SXin Li
16*67e74705SXin Li // An infinite tape!
17*67e74705SXin Li struct Tape {
TapeTape18*67e74705SXin Li constexpr Tape() : l(0), val(false), r(0) {}
TapeTape19*67e74705SXin Li constexpr Tape(const Tape &old, bool write) :
20*67e74705SXin Li l(old.l), val(write), r(old.r) {}
TapeTape21*67e74705SXin Li constexpr Tape(const Tape &old, Dir dir) :
22*67e74705SXin Li l(dir == L ? old.l ? old.l->l : 0 : &old),
23*67e74705SXin Li val(dir == L ? old.l ? old.l->val : false
24*67e74705SXin Li : old.r ? old.r->val : false),
25*67e74705SXin Li r(dir == R ? old.r ? old.r->r : 0 : &old) {}
26*67e74705SXin Li const Tape *l;
27*67e74705SXin Li bool val;
28*67e74705SXin Li const Tape *r;
29*67e74705SXin Li };
update(const Tape & old,bool write)30*67e74705SXin Li constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
move(const Tape & old,Dir dir)31*67e74705SXin Li constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }
32*67e74705SXin Li
33*67e74705SXin Li // Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
34*67e74705SXin Li // steps taken until halt.
run(const State * tm,const Tape & tape,unsigned state)35*67e74705SXin Li constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
36*67e74705SXin Li return state == halt ? 0 :
37*67e74705SXin Li run(tm, move(update(tape, tm[state][tape.val].tape),
38*67e74705SXin Li tm[state][tape.val].dir),
39*67e74705SXin Li tm[state][tape.val].next) + 1;
40*67e74705SXin Li }
41*67e74705SXin Li
42*67e74705SXin Li // 3-state busy beaver. S(bb3) = 21.
43*67e74705SXin Li constexpr State bb3[] = {
44*67e74705SXin Li { { true, R, 1 }, { true, R, halt } },
45*67e74705SXin Li { { true, L, 1 }, { false, R, 2 } },
46*67e74705SXin Li { { true, L, 2 }, { true, L, 0 } }
47*67e74705SXin Li };
48*67e74705SXin Li static_assert(run(bb3, Tape(), 0) == 21, "");
49*67e74705SXin Li
50*67e74705SXin Li // 4-state busy beaver. S(bb4) = 107.
51*67e74705SXin Li constexpr State bb4[] = {
52*67e74705SXin Li { { true, R, 1 }, { true, L, 1 } },
53*67e74705SXin Li { { true, L, 0 }, { false, L, 2 } },
54*67e74705SXin Li { { true, R, halt }, { true, L, 3 } },
55*67e74705SXin Li { { true, R, 3 }, { false, R, 0 } } };
56*67e74705SXin Li static_assert(run(bb4, Tape(), 0) == 107, "");
57