www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Correctness bug in TDPL

reply Timon Gehr <timon.gehr gmx.ch> writes:
On p368 the CheckedInt struct does not check for overflow in the unary minus
operator.
May 13 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in the unary minus
 operator.


Unary minus never overflows. That being said, there is the oddity that 
-x is x when x == int.min. Even in that case there is no loss of 
information.

Andrei
May 13 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
 On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in the unary minus
 operator.


 Unary minus never overflows. That being said, there is the oddity that
 -x is x when x == int.min. Even in that case there is no loss of
 information.

 Andrei


This behavior is caused by _overflow_ when the error condition that is checked
in
++ is overflow:

auto x=CheckedInt(int.min);
x=-x; //passes

x=~x;
x++;//throws

Also, the statement that there is no loss of information is just wrong:

scanf("%d %d %d",&n_,&m_);
auto n=CheckedInt!int(n_),m=CheckedInt!int(m_);
enforce(n>0 && m<0, "provide meaningful input!");
foreach(i;0..n) m=-m;
writeln(n," is"~(m<0?"odd":"even")); //disaster strikes!


Timon
May 13 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/13/11 1:01 PM, Timon Gehr wrote:

 On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in the unary minus
 operator.


 Unary minus never overflows. That being said, there is the oddity that
 -x is x when x == int.min. Even in that case there is no loss of
 information.

 Andrei


 This behavior is caused by _overflow_ when the error condition that is checked
in
 ++ is overflow:

 auto x=CheckedInt(int.min);
 x=-x; //passes

 x=~x;
 x++;//throws


Not sure I understand the point here. I do agree that this may be 
confusing and also that it's reasonable to check against int.min in 
unary minus.


 Also, the statement that there is no loss of information is just wrong:

 scanf("%d %d %d",&n_,&m_);
 auto n=CheckedInt!int(n_),m=CheckedInt!int(m_);
 enforce(n>0&&  m<0, "provide meaningful input!");
 foreach(i;0..n) m=-m;
 writeln(n," is"~(m<0?"odd":"even")); //disaster strikes!


Depends on how one defines "information". I meant it simply as state 
available to the program.


Andrei
May 13 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Andrei Alexandrescu wrote:

On 5/13/11 1:01 PM, Timon Gehr wrote:

 On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in the unary minus
 operator.


 Unary minus never overflows. That being said, there is the oddity that
 -x is x when x == int.min. Even in that case there is no loss of
 information.

 Andrei


 This behavior is caused by _overflow_ when the error condition that is checked
in
 ++ is overflow:

 auto x=CheckedInt(int.min);
 x=-x; //passes

 x=~x;
 x++;//throws


 Not sure I understand the point here. I do agree that this may be
 confusing and also that it's reasonable to check against int.min in
 unary minus.


In two's complement, -x is the same as ~x+1. The implementation in TDPL says one
is correct and the other is wrong on int.min.

My understanding is that something that claims to be a CheckedInt has exactly
two
options on every operation:

1. Behave like a pure whole number, without any strange corner cases.
2. Throw an exception.

struct CheckedInt in TDPL does not guarantee that.
This means it basically gives no reasonable guarantee. You may disagree on this
but in my eyes it is a serious bug.


 Also, the statement that there is no loss of information is just wrong:

 scanf("%d %d %d",&n_,&m_);
 auto n=CheckedInt!int(n_),m=CheckedInt!int(m_);
 enforce(n>0&&  m<0, "provide meaningful input!");
 foreach(i;0..n) m=-m;
 writeln(n," is"~(m<0?"odd":"even")); //disaster strikes!


 Depends on how one defines "information". I meant it simply as state
 available to the program.


Okay. But I think this is not really applicable to CheckedInt. By this
definition
the fact that int.max+1==int.min is just another oddity (when inspected nearer
it
is even just the same oddity), not overflow that loses information. TDPL checks
for that though.


 Andrei


But it is of course up to you if you consider this a worthy addition to some
future version of TDPL.

Timon


OT: I got one of those without an author on it. =) How many are there of those?
BTW, it is one of the best reads I've had!
May 13 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/13/11 5:29 PM, Timon Gehr wrote:

 Andrei Alexandrescu wrote:

 On 5/13/11 1:01 PM, Timon Gehr wrote:

 On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in the unary minus
 operator.


 Unary minus never overflows. That being said, there is the oddity that
 -x is x when x == int.min. Even in that case there is no loss of
 information.

 Andrei


 This behavior is caused by _overflow_ when the error condition that is checked
in
 ++ is overflow:

 auto x=CheckedInt(int.min);
 x=-x; //passes

 x=~x;
 x++;//throws


 Not sure I understand the point here. I do agree that this may be
 confusing and also that it's reasonable to check against int.min in
 unary minus.


 In two's complement, -x is the same as ~x+1. The implementation in TDPL says
one
 is correct and the other is wrong on int.min.


Now I understand. Thanks for clarifying. I updated the errata with 
credit and with a reference to this discussion:

http://erdani.com/tdpl/errata


 My understanding is that something that claims to be a CheckedInt has exactly
two
 options on every operation:

 1. Behave like a pure whole number, without any strange corner cases.
 2. Throw an exception.

 struct CheckedInt in TDPL does not guarantee that.
 This means it basically gives no reasonable guarantee. You may disagree on this
 but in my eyes it is a serious bug.


 Also, the statement that there is no loss of information is just wrong:

 scanf("%d %d %d",&n_,&m_);
 auto n=CheckedInt!int(n_),m=CheckedInt!int(m_);
 enforce(n>0&&   m<0, "provide meaningful input!");
 foreach(i;0..n) m=-m;
 writeln(n," is"~(m<0?"odd":"even")); //disaster strikes!


 Depends on how one defines "information". I meant it simply as state
 available to the program.


 Okay. But I think this is not really applicable to CheckedInt. By this
definition
 the fact that int.max+1==int.min is just another oddity (when inspected nearer
it
 is even just the same oddity), not overflow that loses information. TDPL checks
 for that though.


 Andrei


 But it is of course up to you if you consider this a worthy addition to some
 future version of TDPL.


It definitely is. I appreciate you followed through and explained the 
matter to me.


 Timon


 OT: I got one of those without an author on it. =) How many are there of those?
 BTW, it is one of the best reads I've had!


Thanks very much! There were like 1830 copies without an author's name 
on the cover, they are now getting hard to find.


Andrei
May 13 2011
prev sibling parent "BULLSHIT-GENERATOR" <BULLSHIT DELIVERY.COM> writes:
On Friday, 13 May 2011 at 13:36:13 UTC, Andrei Alexandrescu wrote:

 On 5/13/11 3:25 AM, Timon Gehr wrote:

 On p368 the CheckedInt struct does not check for overflow in 
 the unary minus
 operator.


 Unary minus never overflows. That being said, there is the 
 oddity that -x is x when x == int.min. Even in that case there 
 is no loss of information.

 Andrei


BULLSHIT
Feb 10 2013