www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Out of bound problem

reply bearophile <bearophileHUGS lycos.com> writes:
While testing I have found a problem in my code, I have reduced the code to the
following lines:

template IsArray(T) {
    const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                         is(typeof(T.reverse)) && is(typeof(T.dup));
}

TA[] foo(TA, TB)(TA[] a, TB b) {
    TA[] result;

    static if (IsArray!(TB)) {
        if (b.length == 0) {
            result = a;
        } else if (b.length == 1) {
            result = foo(a, b[0]);
        }
    }

    return result;
}

void main() {
    foo("test", "");
}


Its output:

bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
bug.d(21): template instance bug.foo!(char,char[0u]) error instantiating

I have found ways to solve this problem, but can someone please explain me
what's the problem?

Bye and thank you,
bearophile
Feb 16 2008
next sibling parent Denton Cockburn <diboss hotmail.com> writes:
On Sat, 16 Feb 2008 19:43:54 -0500, bearophile wrote:


 While testing I have found a problem in my code, I have reduced the code
 to the following lines:
 
 template IsArray(T) {
     const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                          is(typeof(T.reverse)) && is(typeof(T.dup));
 }
 
 TA[] foo(TA, TB)(TA[] a, TB b) {
     TA[] result;
 
     static if (IsArray!(TB)) {
         if (b.length == 0) {
             result = a;
         } else if (b.length == 1) {
             result = foo(a, b[0]);
         }
     }
 
     return result;
 }
 
 void main() {
     foo("test", "");
 }
 
 
 Its output:
 
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0] bug.d(13):
 Error: array index 0 is out of bounds b[0 .. 0] bug.d(13): Error: array
 index 0 is out of bounds b[0 .. 0] bug.d(21): template instance
 bug.foo!(char,char[0u]) error instantiating
 
 I have found ways to solve this problem, but can someone please explain
 me what's the problem?
 
 Bye and thank you,
 bearophile


I tried looking at this.  It's weird (and tripping me out).
I would love to see the explanation of what's going wrong here.
Feb 16 2008
prev sibling next sibling parent reply "Neil Vice" <psgdg swiftdsl.com.au> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:fp800a$2781$1 digitalmars.com...

 While testing I have found a problem in my code, I have reduced the code 
 to the following lines:

 template IsArray(T) {
    const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                         is(typeof(T.reverse)) && is(typeof(T.dup));
 }

 TA[] foo(TA, TB)(TA[] a, TB b) {
    TA[] result;

    static if (IsArray!(TB)) {
        if (b.length == 0) {
            result = a;
        } else if (b.length == 1) {
            result = foo(a, b[0]);
        }
    }

    return result;
 }

 void main() {
    foo("test", "");
 }


 Its output:

 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(21): template instance bug.foo!(char,char[0u]) error instantiating

 I have found ways to solve this problem, but can someone please explain me 
 what's the problem?

 Bye and thank you,
 bearophile


As far as I can tell the cause is that the expression b[0] is being 
evaluated even if the enclosing if statement hasn't been entered. For 
example if the line containing b[0] is replaced with a writef() it is never 
output to the console.

I can only assume that this is a compiler bug.
Feb 16 2008
parent Denton Cockburn <diboss hotmail.com> writes:
On Sun, 17 Feb 2008 11:37:53 +0900, Neil Vice wrote:


 "bearophile" <bearophileHUGS lycos.com> wrote in message
 news:fp800a$2781$1 digitalmars.com...

 While testing I have found a problem in my code, I have reduced the
 code to the following lines:

 template IsArray(T) {
    const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                         is(typeof(T.reverse)) && is(typeof(T.dup));
 }

 TA[] foo(TA, TB)(TA[] a, TB b) {
    TA[] result;

    static if (IsArray!(TB)) {
        if (b.length == 0) {
            result = a;
        } else if (b.length == 1) {
            result = foo(a, b[0]);
        }
    }

    return result;
 }

 void main() {
    foo("test", "");
 }


 Its output:

 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0] bug.d(13):
 Error: array index 0 is out of bounds b[0 .. 0] bug.d(13): Error: array
 index 0 is out of bounds b[0 .. 0] bug.d(21): template instance
 bug.foo!(char,char[0u]) error instantiating

 I have found ways to solve this problem, but can someone please explain
 me what's the problem?

 Bye and thank you,
 bearophile


 
 As far as I can tell the cause is that the expression b[0] is being
 evaluated even if the enclosing if statement hasn't been entered. For
 example if the line containing b[0] is replaced with a writef() it is
 never output to the console.
 
 I can only assume that this is a compiler bug.


Behaviour exists in DMD 2.010 and GDC 0.25(1.021)
Feb 16 2008
prev sibling next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
bearophile wrote:

 While testing I have found a problem in my code, I have reduced the code to
the following lines:
 
 template IsArray(T) {
     const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                          is(typeof(T.reverse)) && is(typeof(T.dup));
 }


...
Y'know, there's a template for this in std.traits and tango.core.Traits.


 TA[] foo(TA, TB)(TA[] a, TB b) {
     TA[] result;
 
     static if (IsArray!(TB)) {
         if (b.length == 0) {
             result = a;
         } else if (b.length == 1) {
             result = foo(a, b[0]);
         }
     }
 
     return result;
 }
 
 void main() {
     foo("test", "");
 }
 
 
 Its output:
 
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(13): Error: array index 0 is out of bounds b[0 .. 0]
 bug.d(21): template instance bug.foo!(char,char[0u]) error instantiating


Ouch! Constant expansion for the lose!

What's going on is, this is being evaluated at compile time, when you've 
got a runtime check for length. So it's expanded like this:

if ("".length == 0) {
    // blah
} else if ("".length == 1) {
    result = foo(blah, ""[0]);
}

Then the compiler sees: Array literal! Constant index! Must expand!
Obviously, it can't do that. So it gives an error.

So, you can use a static if, but that'll fail for a dynamic array. Or 
you can pass in ""[] rather than "". Or you can check if it's a static 
array, do a 'static if (array.length)' in that case, and in the case of 
a dynamic array, use a non-static if.

But yeah, it's a bug.


 I have found ways to solve this problem, but can someone please explain me
what's the problem?
 
 Bye and thank you,
 bearophile
Feb 16 2008
next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
Christopher Wright <dhasenan gmail.com> wrote:

 if ("".length == 0) {
     // blah
 } else if ("".length == 1) {
     result = foo(blah, ""[0]);
 }
 
 Then the compiler sees: Array literal! Constant index! Must expand!
 Obviously, it can't do that. So it gives an error.
 
 [...]
 But yeah, it's a bug.


But how the compiler should handle this ?  In trivial case above, the 
code with error is unreachable.  But as a generic solution, it probably 
should expand into something like:

if (condition) {
    // blah
} else if (other condition) {
    blah;  // stays here for possible side effects
    // ""[0] is replaced with this at compile time
    throw new ArrayBoundsException();
    // the rest of the block is unreachable, throw away
}

-- 
SnakE
Feb 16 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Thanks to everybody, in my code I did solve the problem like this:
result = foo(a, b.dup[0]);

But I was curious to know what you think about this situation. Now I know it's
probably a compiler bug.


Christopher Wright:

 Y'know, there's a template for this in std.traits and tango.core.Traits.


I don't use Tango (yet). I use always the std lib when possible, I know there's
no point in duplicating the std lib. I don't remember the bugs or the problems,
but I have found std.traits not enough for similar array purposes, and I have
found a bug in the traits of Tango to do that array purposes, so I have created
IsArray and IsDynamicArray, you can find them in my d libs:

template IsArray(T) {
    const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                         is(typeof(T.reverse)) && is(typeof(T.dup));
}
template IsDynamicArray(T) {
    const bool IsDynamicArray = is( typeof(T.init[0])[] == T );
}
template IsStaticArray(T) {
    const bool IsStaticArray = IsArray!(T) && (!IsDynamicArray!(T));
}

That IsArray may look a bit like "duck typing at compile time", but that's the
only thing that works that I have found.
I use similar tools all the time, so I need to have them quite sharp :-)

Bye,
bearophile
Feb 17 2008
parent reply Christopher Wright <dhasenan gmail.com> writes:
bearophile wrote:

 Thanks to everybody, in my code I did solve the problem like this:
 result = foo(a, b.dup[0]);
 
 But I was curious to know what you think about this situation. Now I know it's
probably a compiler bug.
 
 
 Christopher Wright:

 Y'know, there's a template for this in std.traits and tango.core.Traits.


 
 I don't use Tango (yet). I use always the std lib when possible, I know
there's no point in duplicating the std lib. I don't remember the bugs or the
problems, but I have found std.traits not enough for similar array purposes,
and I have found a bug in the traits of Tango to do that array purposes, so I
have created IsArray and IsDynamicArray, you can find them in my d libs:


std.traits.isArray/isStaticArray/isDynamic doesn't work? I don't recall 
seeing such a bug report.


 template IsArray(T) {
     const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                          is(typeof(T.reverse)) && is(typeof(T.dup));
 }
 template IsDynamicArray(T) {
     const bool IsDynamicArray = is( typeof(T.init[0])[] == T );
 }
 template IsStaticArray(T) {
     const bool IsStaticArray = IsArray!(T) && (!IsDynamicArray!(T));
 }


const bool IsStaticArray(T) {
    const bool IsStaticArray = is(typeof(T[0])) && 
is(typeof(T[0])[T.sizeof/T[0].sizeof] == T);
}

Then, since IsStaticArray doesn't depend on IsArray, you can change 
IsArray to return true iff IsStaticArray or IsDynamicArray.


 That IsArray may look a bit like "duck typing at compile time", but that's the
only thing that works that I have found.
 I use similar tools all the time, so I need to have them quite sharp :-)
 
 Bye,
 bearophile
Feb 17 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Christopher Wright:

 Then, since IsStaticArray doesn't depend on IsArray, you can change 
 IsArray to return true iff IsStaticArray or IsDynamicArray.


You are right, thank you. I'm learning D still.

Bye,
bearophile
Feb 17 2008
parent reply Christopher Wright <dhasenan gmail.com> writes:
bearophile wrote:

 Christopher Wright:

 Then, since IsStaticArray doesn't depend on IsArray, you can change 
 IsArray to return true iff IsStaticArray or IsDynamicArray.


 
 You are right, thank you. I'm learning D still.


Not many people using D spend a lot of time spelunking in the bowels of 
templates, especially now that CTFE is available. The basics are quite 
handy, but a lot of it is rather arcane, since the type system allows 
for quite a bit of freedom.


 Bye,
 bearophile
Feb 17 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Christopher Wright wrote:

 bearophile wrote:

 Christopher Wright:

 Then, since IsStaticArray doesn't depend on IsArray, you can change 
 IsArray to return true iff IsStaticArray or IsDynamicArray.


 You are right, thank you. I'm learning D still.


 
 Not many people using D spend a lot of time spelunking in the bowels of 
 templates, especially now that CTFE is available. The basics are quite 
 handy, but a lot of it is rather arcane, since the type system allows 
 for quite a bit of freedom.


...and since the syntax for 'is' expressions make about as much sense as 
George W.

--bb
Feb 17 2008
parent reply Christopher Wright <dhasenan gmail.com> writes:
Bill Baxter wrote:

 Christopher Wright wrote:

 bearophile wrote:

 Christopher Wright:

 Then, since IsStaticArray doesn't depend on IsArray, you can change 
 IsArray to return true iff IsStaticArray or IsDynamicArray.


 You are right, thank you. I'm learning D still.


 Not many people using D spend a lot of time spelunking in the bowels 
 of templates, especially now that CTFE is available. The basics are 
 quite handy, but a lot of it is rather arcane, since the type system 
 allows for quite a bit of freedom.


 
 ....and since the syntax for 'is' expressions make about as much sense 
 as George W.
 
 --bb


Now, now. No cross, no crown, no green sword. If you want to start a 
flamewar, just talk about const :P

Though it does make sense, in a vague, twisted way. You just expect to 
be able to do some things that don't yet work.
Feb 17 2008
parent reply Christopher Wright <dhasenan gmail.com> writes:
Christopher Wright wrote:

 Now, now. No cross, no crown, no green sword. If you want to start a 
 flamewar, just talk about const :P


Green sword? I meant green star. It's the symbol for Esperanto.
Feb 18 2008
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Christopher Wright wrote:

 Christopher Wright wrote:

 Now, now. No cross, no crown, no green sword. If you want to start a 
 flamewar, just talk about const :P


 
 Green sword? I meant green star. It's the symbol for Esperanto.
 


I googled the phrase and came up with bupkis.
Still am clueless as to what you meant even with the correction. :-)

--bb
Feb 18 2008
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
Bill Baxter escribió:

 Christopher Wright wrote:

 Christopher Wright wrote:

 Now, now. No cross, no crown, no green sword. If you want to start a 
 flamewar, just talk about const :P


 Green sword? I meant green star. It's the symbol for Esperanto.


 
 I googled the phrase and came up with bupkis.


I found this: http://archives.conlang.info/pho/zheinfi/wurqanwhian.html :)


 Still am clueless as to what you meant even with the correction. :-)


I think everytime someone mentions Esperanto, all kind of discussions 
arise... maybe it's that what he meant?


 
 --bb
Feb 18 2008
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Ary Borenszweig wrote:

 Bill Baxter escribió:

 Christopher Wright wrote:

 Christopher Wright wrote:

 Now, now. No cross, no crown, no green sword. If you want to start a 
 flamewar, just talk about const :P


 Green sword? I meant green star. It's the symbol for Esperanto.


 I googled the phrase and came up with bupkis.


 
 I found this: http://archives.conlang.info/pho/zheinfi/wurqanwhian.html :)


That doesn't explain it either, just uses the phrase.


 Still am clueless as to what you meant even with the correction. :-)


 
 I think everytime someone mentions Esperanto, all kind of discussions 
 arise... maybe it's that what he meant?


Sounds like maybe it means "if you can't say something nice, don't say 
anything at all".

--bb
Feb 18 2008
prev sibling parent Christopher Wright <dhasenan gmail.com> writes:
Bill Baxter wrote:

 Christopher Wright wrote:

 Christopher Wright wrote:

 Now, now. No cross, no crown, no green sword. If you want to start a 
 flamewar, just talk about const :P


 Green sword? I meant green star. It's the symbol for Esperanto.


 
 I googled the phrase and came up with bupkis.
 Still am clueless as to what you meant even with the correction. :-)
 
 --bb


Green star: symbol for Esperanto. Shorthand way of saying 'don't flame'.
Feb 18 2008
prev sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:

 TA[] foo(TA, TB)(TA[] a, TB b) {
     TA[] result;
 
     static if (IsArray!(TB)) {
         if (b.length == 0) {
             result = a;
         } else if (b.length == 1) {
             result = foo(a, b[0]);
         }
     }
 
     return result;
 }


It seems to replace the line
result = foo(a, b[0]);
with
result = foo("test", ""[0]);
and then complain that the constant expression ""[0] is wrong.  It's 
about distinguishing between static and dynamic arrays which I don't 
know how to do.

In your case, adding static if(b.sizeof) should do the trick: only empty 
static arrays have zero size.

-- 
SnakE
Feb 16 2008