head	1.1;
branch	1.1.1;
access;
symbols
	netbsd-11-0-RC4:1.1.1.2
	netbsd-11-0-RC3:1.1.1.2
	netbsd-11-0-RC2:1.1.1.2
	netbsd-11-0-RC1:1.1.1.2
	perseant-exfatfs-base-20250801:1.1.1.2
	netbsd-11:1.1.1.2.0.10
	netbsd-11-base:1.1.1.2
	netbsd-10-1-RELEASE:1.1.1.2
	perseant-exfatfs-base-20240630:1.1.1.2
	perseant-exfatfs:1.1.1.2.0.8
	perseant-exfatfs-base:1.1.1.2
	netbsd-8-3-RELEASE:1.1.1.1
	netbsd-9-4-RELEASE:1.1.1.1
	netbsd-10-0-RELEASE:1.1.1.2
	netbsd-10-0-RC6:1.1.1.2
	netbsd-10-0-RC5:1.1.1.2
	netbsd-10-0-RC4:1.1.1.2
	netbsd-10-0-RC3:1.1.1.2
	netbsd-10-0-RC2:1.1.1.2
	netbsd-10-0-RC1:1.1.1.2
	netbsd-10:1.1.1.2.0.6
	netbsd-10-base:1.1.1.2
	netbsd-9-3-RELEASE:1.1.1.1
	cjep_sun2x:1.1.1.2.0.4
	cjep_sun2x-base:1.1.1.2
	cjep_staticlib_x-base1:1.1.1.2
	netbsd-9-2-RELEASE:1.1.1.1
	cjep_staticlib_x:1.1.1.2.0.2
	cjep_staticlib_x-base:1.1.1.2
	netbsd-9-1-RELEASE:1.1.1.1
	phil-wifi-20200421:1.1.1.2
	phil-wifi-20200411:1.1.1.2
	phil-wifi-20200406:1.1.1.2
	netbsd-8-2-RELEASE:1.1.1.1
	netbsd-9-0-RELEASE:1.1.1.1
	netbsd-9-0-RC2:1.1.1.1
	netbsd-9-0-RC1:1.1.1.1
	netbsd-9:1.1.1.1.0.32
	netbsd-9-base:1.1.1.1
	phil-wifi-20190609:1.1.1.1
	netbsd-8-1-RELEASE:1.1.1.1
	netbsd-8-1-RC1:1.1.1.1
	pgoyette-compat-merge-20190127:1.1.1.1
	pgoyette-compat-20190127:1.1.1.1
	pgoyette-compat-20190118:1.1.1.1
	pgoyette-compat-1226:1.1.1.1
	pgoyette-compat-1126:1.1.1.1
	pgoyette-compat-1020:1.1.1.1
	pgoyette-compat-0930:1.1.1.1
	pgoyette-compat-0906:1.1.1.1
	netbsd-7-2-RELEASE:1.1.1.1
	pgoyette-compat-0728:1.1.1.1
	clang-337282:1.1.1.1
	netbsd-8-0-RELEASE:1.1.1.1
	phil-wifi:1.1.1.1.0.30
	phil-wifi-base:1.1.1.1
	pgoyette-compat-0625:1.1.1.1
	netbsd-8-0-RC2:1.1.1.1
	pgoyette-compat-0521:1.1.1.1
	pgoyette-compat-0502:1.1.1.1
	pgoyette-compat-0422:1.1.1.1
	netbsd-8-0-RC1:1.1.1.1
	pgoyette-compat-0415:1.1.1.1
	pgoyette-compat-0407:1.1.1.1
	pgoyette-compat-0330:1.1.1.1
	pgoyette-compat-0322:1.1.1.1
	pgoyette-compat-0315:1.1.1.1
	netbsd-7-1-2-RELEASE:1.1.1.1
	pgoyette-compat:1.1.1.1.0.28
	pgoyette-compat-base:1.1.1.1
	netbsd-7-1-1-RELEASE:1.1.1.1
	clang-319952:1.1.1.1
	matt-nb8-mediatek:1.1.1.1.0.26
	matt-nb8-mediatek-base:1.1.1.1
	clang-309604:1.1.1.1
	perseant-stdc-iso10646:1.1.1.1.0.24
	perseant-stdc-iso10646-base:1.1.1.1
	netbsd-8:1.1.1.1.0.22
	netbsd-8-base:1.1.1.1
	prg-localcount2-base3:1.1.1.1
	prg-localcount2-base2:1.1.1.1
	prg-localcount2-base1:1.1.1.1
	prg-localcount2:1.1.1.1.0.20
	prg-localcount2-base:1.1.1.1
	pgoyette-localcount-20170426:1.1.1.1
	bouyer-socketcan-base1:1.1.1.1
	pgoyette-localcount-20170320:1.1.1.1
	netbsd-7-1:1.1.1.1.0.18
	netbsd-7-1-RELEASE:1.1.1.1
	netbsd-7-1-RC2:1.1.1.1
	clang-294123:1.1.1.1
	netbsd-7-nhusb-base-20170116:1.1.1.1
	bouyer-socketcan:1.1.1.1.0.16
	bouyer-socketcan-base:1.1.1.1
	clang-291444:1.1.1.1
	pgoyette-localcount-20170107:1.1.1.1
	netbsd-7-1-RC1:1.1.1.1
	pgoyette-localcount-20161104:1.1.1.1
	netbsd-7-0-2-RELEASE:1.1.1.1
	localcount-20160914:1.1.1.1
	netbsd-7-nhusb:1.1.1.1.0.14
	netbsd-7-nhusb-base:1.1.1.1
	clang-280599:1.1.1.1
	pgoyette-localcount-20160806:1.1.1.1
	pgoyette-localcount-20160726:1.1.1.1
	pgoyette-localcount:1.1.1.1.0.12
	pgoyette-localcount-base:1.1.1.1
	netbsd-7-0-1-RELEASE:1.1.1.1
	clang-261930:1.1.1.1
	netbsd-7-0:1.1.1.1.0.10
	netbsd-7-0-RELEASE:1.1.1.1
	netbsd-7-0-RC3:1.1.1.1
	netbsd-7-0-RC2:1.1.1.1
	netbsd-7-0-RC1:1.1.1.1
	clang-237755:1.1.1.1
	clang-232565:1.1.1.1
	clang-227398:1.1.1.1
	tls-maxphys-base:1.1.1.1
	tls-maxphys:1.1.1.1.0.8
	netbsd-7:1.1.1.1.0.6
	netbsd-7-base:1.1.1.1
	clang-215315:1.1.1.1
	clang-209886:1.1.1.1
	yamt-pagecache:1.1.1.1.0.4
	yamt-pagecache-base9:1.1.1.1
	tls-earlyentropy:1.1.1.1.0.2
	tls-earlyentropy-base:1.1.1.1
	riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.1
	riastradh-drm2-base3:1.1.1.1
	clang-202566:1.1.1.1
	clang-201163:1.1.1.1
	clang-199312:1.1.1.1
	clang-198450:1.1.1.1
	clang-196603:1.1.1.1
	clang-195771:1.1.1.1
	LLVM:1.1.1;
locks; strict;
comment	@// @;


1.1
date	2013.11.28.14.14.56;	author joerg;	state Exp;
branches
	1.1.1.1;
next	;
commitid	ow8OybrawrB1f3fx;

1.1.1.1
date	2013.11.28.14.14.56;	author joerg;	state Exp;
branches
	1.1.1.1.4.1
	1.1.1.1.8.1
	1.1.1.1.30.1;
next	1.1.1.2;
commitid	ow8OybrawrB1f3fx;

1.1.1.2
date	2019.11.13.22.22.54;	author joerg;	state dead;
branches;
next	;
commitid	QD8YATxuNG34YJKB;

1.1.1.1.4.1
date	2013.11.28.14.14.56;	author yamt;	state dead;
branches;
next	1.1.1.1.4.2;
commitid	WSrDtL5nYAUyiyBx;

1.1.1.1.4.2
date	2014.05.22.16.19.40;	author yamt;	state Exp;
branches;
next	;
commitid	WSrDtL5nYAUyiyBx;

1.1.1.1.8.1
date	2013.11.28.14.14.56;	author tls;	state dead;
branches;
next	1.1.1.1.8.2;
commitid	jTnpym9Qu0o4R1Nx;

1.1.1.1.8.2
date	2014.08.19.23.49.17;	author tls;	state Exp;
branches;
next	;
commitid	jTnpym9Qu0o4R1Nx;

1.1.1.1.30.1
date	2020.04.13.07.50.22;	author martin;	state dead;
branches;
next	;
commitid	X01YhRUPVUDaec4C;


desc
@@


1.1
log
@Initial revision
@
text
@// RUN: %clang_cc1 -verify -std=c++11 %s
// expected-no-diagnostics

// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.

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() : l(0), val(false), r(0) {}
  constexpr Tape(const Tape &old, bool write) :
    l(old.l), val(write), r(old.r) {}
  constexpr Tape(const Tape &old, Dir dir) :
    l(dir == L ? old.l ? old.l->l : 0 : &old),
    val(dir == L ? old.l ? old.l->val : false
                 : old.r ? old.r->val : false),
    r(dir == R ? old.r ? old.r->r : 0 : &old) {}
  const Tape *l;
  bool val;
  const Tape *r;
};
constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }

// Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
// steps taken until halt.
constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
  return state == halt ? 0 :
         run(tm, move(update(tape, tm[state][tape.val].tape),
                      tm[state][tape.val].dir),
             tm[state][tape.val].next) + 1;
}

// 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, Tape(), 0) == 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, Tape(), 0) == 107, "");
@


1.1.1.1
log
@Import Clang 3.4rc1 r195771.
@
text
@@


1.1.1.1.30.1
log
@Mostly merge changes from HEAD upto 20200411
@
text
@@


1.1.1.2
log
@Mark old LLVM instance as dead.
@
text
@@


1.1.1.1.8.1
log
@file constexpr-turing.cpp was added on branch tls-maxphys on 2014-08-19 23:49:17 +0000
@
text
@d1 56
@


1.1.1.1.8.2
log
@Rebase to HEAD as of a few days ago.
@
text
@a0 56
// RUN: %clang_cc1 -verify -std=c++11 %s
// expected-no-diagnostics

// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.

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() : l(0), val(false), r(0) {}
  constexpr Tape(const Tape &old, bool write) :
    l(old.l), val(write), r(old.r) {}
  constexpr Tape(const Tape &old, Dir dir) :
    l(dir == L ? old.l ? old.l->l : 0 : &old),
    val(dir == L ? old.l ? old.l->val : false
                 : old.r ? old.r->val : false),
    r(dir == R ? old.r ? old.r->r : 0 : &old) {}
  const Tape *l;
  bool val;
  const Tape *r;
};
constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }

// Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
// steps taken until halt.
constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
  return state == halt ? 0 :
         run(tm, move(update(tape, tm[state][tape.val].tape),
                      tm[state][tape.val].dir),
             tm[state][tape.val].next) + 1;
}

// 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, Tape(), 0) == 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, Tape(), 0) == 107, "");
@


1.1.1.1.4.1
log
@file constexpr-turing.cpp was added on branch yamt-pagecache on 2014-05-22 16:19:40 +0000
@
text
@d1 56
@


1.1.1.1.4.2
log
@sync with head.

for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.

this commit was splitted into small chunks to avoid
a limitation of cvs.  ("Protocol error: too many arguments")
@
text
@a0 56
// RUN: %clang_cc1 -verify -std=c++11 %s
// expected-no-diagnostics

// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.

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() : l(0), val(false), r(0) {}
  constexpr Tape(const Tape &old, bool write) :
    l(old.l), val(write), r(old.r) {}
  constexpr Tape(const Tape &old, Dir dir) :
    l(dir == L ? old.l ? old.l->l : 0 : &old),
    val(dir == L ? old.l ? old.l->val : false
                 : old.r ? old.r->val : false),
    r(dir == R ? old.r ? old.r->r : 0 : &old) {}
  const Tape *l;
  bool val;
  const Tape *r;
};
constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }

// Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
// steps taken until halt.
constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
  return state == halt ? 0 :
         run(tm, move(update(tape, tm[state][tape.val].tape),
                      tm[state][tape.val].dir),
             tm[state][tape.val].next) + 1;
}

// 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, Tape(), 0) == 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, Tape(), 0) == 107, "");
@