On 24/02/12 15:18, Alex Rønne Petersen wrote:
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@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.


Yes, that's exactly what it does. That's how it's able to implement pointers safely.

That's a nice story, Thanks, bearophile.

Reply via email to