About CTFE and pointers

[bearophile]

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