About CTFE and pointers

[Alex Rønne Petersen]

On 24-02-2012 15:08, bearophile wrote:
> I have seen this C++11 program:
> http://kaizer.se/wiki/log/post/C++_constexpr/
>
> I have translated it to this D code:
>
>
> bool notEnd(const char *s, const int n) {
>      return s&&  s[n];
> }
> bool strPrefix(const char *s, const char *t, const int ns, const int nt) {
>      return (s == t) ||
>             !t[nt] ||
>             (s[ns] == t[nt]&&  (strPrefix(s, t, ns+1, nt+1)));
> }
> bool contains(const char *s, const char *needle, const int n=0) {
>      // Works only with C-style 0-terminated strings
>      return notEnd(s, n)&&
>             (strPrefix(s, needle, n, 0) || contains(s, needle, n+1));
> }
> enum int x = contains("froogler", "oogle");
> void main() {
> //    assert(contains("froogler", "oogle"));
> }
>
>
> If I run the version of the code with the run-time, it generates no errors.
>
> If I run the version with enum with the latest dmd it gives:
>
> test.d(6): Error: string index 5 is out of bounds [0 .. 5]
> test.d(7):        called from here: strPrefix(s,t,ns + 1,nt + 1)
> test.d(4):        5 recursive calls to function strPrefix
> test.d(12):        called from here: strPrefix(s,needle,n,0)
> test.d(12):        called from here: contains(s,needle,n + 1)
> test.d(12):        called from here: contains(s,needle,n + 1)
> test.d(14):        called from here: contains("froogler","oogle",0)
>
>
> At first sight it looks like a CTFE bug, but studying the code a little it seems there is a off-by-one bug in the code (http://en.wikipedia.org/wiki/Off-by-one_error ). A quick translation to D arrays confirms it:
>
>
> bool notEnd(in char[] s, in int n) {
>      return s&&  s[n];
> }
> bool strPrefix(in char[] s, in char[] t, in int ns, in int nt) {
>      return (s == t) ||
>             !t[nt] ||
>             (s[ns] == t[nt]&&  (strPrefix(s, t, ns+1, nt+1)));
> }
> bool contains(in char[] s, in char[] needle, in int n=0) {
>      // Works only with C-style 0-terminated strings
>      return notEnd(s, n)&&
>             (strPrefix(s, needle, n, 0) || contains(s, needle, n+1));
> }
> //enum int x = contains("froogler", "oogle");
> void main() {
>      assert(contains("froogler", "oogle"));
> }
>
>
> It gives at run-time:
>
> core.exception.RangeError at test(6): Range violation
> ----------------
> ....\test.d(6): bool test.strPrefix(const(char[]), const(char[]), const(int), const(int))
> ....
> ----------------
>
>
> So it seems that Don, when he has implemented the last parts of the CTFE interpreter, has done something curious, because in some cases it seems able to find out of bounds even when you use just raw pointers :-)
>
> Bye,
> bearophile

It's not at all unlikely that the CTFE interpreter represents blocks of 
memory as a pointer+length pair internally.

-- 
- Alex