About CTFE and pointers

Don Clugston dac at nospam.com
Fri Feb 24 07:20:25 PST 2012


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 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.
>

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

That's a nice story, Thanks, bearophile.



More information about the Digitalmars-d-learn mailing list