www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RFC: Value range propagation for if-else

reply Lionello Lunesu <lionello lunesu.remove.com> writes:
Hi,

I got this thing working and I think it's about time I get some comments 
on it.

I've been wanting to extend Value Rang Propagation (VRE) for some time 
now. Mostly because of the fix to the troublesome "signed-unsigned 
comparisons" issue. Enabling VRE for if-else and "&&" will fix many of 
the false-positive warnings given out by the fix to bug 259 by allowing 
code like this: if (signed > 0 && signed < unsigned) { .. }

Have a look at the branch:
https://github.com/lionello/dmd/compare/if-else-range

There, I've also added a __traits(intrange, <expression>) which returns 
a tuple with the min and max for the given expression. It's used in the 
test case as follows:


     const i = foo ? -1 : 33;

     if (i)
       static assert(__traits(intrange, i) == Tuple!(-1, 33));
     else
     {
       //static assert(i == 0); TODO
       static assert(__traits(intrange, i) == Tuple!(0, 0));
     }

     if (i == 33)
     {
       //static assert(i == 33); TODO
       static assert(__traits(intrange, i) == Tuple!(33, 33));
     }
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 32));

     if (10 <= i)
       static assert(__traits(intrange, i) == Tuple!(10, 33));
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 9));


It would be nice if this can be used by CTFE as well.

Destroy?

L.
Jun 17 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Lionello Lunesu:


 I've also added a __traits(intrange, <expression>) which 
 returns a tuple with the min and max for the given expression.


I'd like a name like integral_range, and perhaps it's better for 
it to return a T[2] (fixed size array) instead of a tuple.

Such __traits(integral_range, exp) could work on core.checkedint 
values too, or it could be used by them to remove some overflow 
tests and increase their performance.



 It's used in the test case as follows:


I presume your proposal allows this code to compile:

int x = 100;
void main() {
     if (x >= 0 && x <= ubyte.max) {
         ubyte y = x;
     }
}


If your proposal is extended to contracts, you can also write:


ubyte foo(immutable int x)
in {
     assert(x >= 0 && x <= ubyte.max);
} body {
     return x;
}
void main() {}


Bye,
bearophile
Jun 18 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 I'd like a name like integral_range,


"value_range" seems better, more general.

Bye,
bearophile
Jun 18 2014
parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig rejectedsoftware.com> writes:
Am 18.06.2014 09:54, schrieb bearophile:

 I'd like a name like integral_range,


 "value_range" seems better, more general.

 Bye,
 bearophile


Or even better, "valueRange", to be consistent with the general naming 
convention.
Jun 18 2014
parent Lionello Lunesu <lionello lunesu.remove.com> writes:
On 18/06/14 16:42, Sönke Ludwig wrote:

 Or even better, "valueRange", to be consistent with the general naming
 convention.


That's what I ended up calling it.
Jun 18 2014
prev sibling parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 18/06/14 15:53, bearophile wrote:

 I've also added a __traits(intrange, <expression>) which returns a
 tuple with the min and max for the given expression.


 I'd like a name like integral_range, and perhaps it's better for it to
 return a T[2] (fixed size array) instead of a tuple.


Most other traits return tuples, so it seemed like a good fit.


 I presume your proposal allows this code to compile:

 int x = 100;
 void main() {
      if (x >= 0 && x <= ubyte.max) {
          ubyte y = x;
      }
 }


Yes, provided 'x' is immutable or const. It can be extended for mutable 
values as well, but then mutations/gotos must be tracked.


 If your proposal is extended to contracts, you can also write:


 ubyte foo(immutable int x)
 in {
      assert(x >= 0 && x <= ubyte.max);
 } body {
      return x;
 }


Yeah, I wanted to support "assert" as well, but it doesn't create a 
scope so it'll be a bit trickier to implement.

L.
Jun 18 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Lionello Lunesu:


 ubyte foo(immutable int x)
 in {
     assert(x >= 0 && x <= ubyte.max);
 } body {
     return x;
 }


 Yeah, I wanted to support "assert" as well, but it doesn't 
 create a scope so it'll be a bit trickier to implement.


If you have an assert in a pre-condition and the argument is 
const, then the body{} is the scope you look for.

Bye,
bearophile
Jun 18 2014
parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 18/06/14 16:28, bearophile wrote:

 Lionello Lunesu:


 ubyte foo(immutable int x)
 in {
     assert(x >= 0 && x <= ubyte.max);
 } body {
     return x;
 }


 Yeah, I wanted to support "assert" as well, but it doesn't create a
 scope so it'll be a bit trickier to implement.


 If you have an assert in a pre-condition and the argument is const, then
 the body{} is the scope you look for.

 Bye,
 bearophile


That's a good point! I checked the DMD code and it seems doable. I can 
reuse the "ConditionVisitor" that I wrote for if-else.

Will play with it.
Jun 18 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Lionello Lunesu:


 Will play with it.


And later you look at other things, like post-conditions:


int foo()
out(result) {
     assert(result >= 0 && result <= ubyte.max);
} body {
     return 10;
}
void main() {
     ubyte x = foo();
}


And slowly D Contract Programming starts to become a grown-up 
language feature.

Bye,
bearophile
Jun 18 2014
next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 18 June 2014 at 17:00:36 UTC, bearophile wrote:

 Lionello Lunesu:


 Will play with it.


 And later you look at other things, like post-conditions:


 int foo()
 out(result) {
     assert(result >= 0 && result <= ubyte.max);
 } body {
     return 10;
 }
 void main() {
     ubyte x = foo();
 }


 And slowly D Contract Programming starts to become a grown-up 
 language feature.

 Bye,
 bearophile


This could be a bad thing. It makes it pretty enticing to use 
contracts as input verification instead of logic verification.
Jun 18 2014
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Jun 18, 2014 at 07:54:02PM +0000, Meta via Digitalmars-d wrote:

 On Wednesday, 18 June 2014 at 17:00:36 UTC, bearophile wrote:

Lionello Lunesu:


Will play with it.


And later you look at other things, like post-conditions:


int foo()
out(result) {
    assert(result >= 0 && result <= ubyte.max);
} body {
    return 10;
}
void main() {
    ubyte x = foo();
}


And slowly D Contract Programming starts to become a grown-up
language feature.

Bye,
bearophile


 
 This could be a bad thing. It makes it pretty enticing to use
 contracts as input verification instead of logic verification.


Until you compile with -release, and then suddenly invalid input crashes
your program. :-P (Then you'll go and fire the guy who wrote it.)


T

-- 
"The whole problem with the world is that fools and fanatics are always
so certain of themselves, but wiser people so full of doubts." --
Bertrand Russell.
"How come he didn't put 'I think' at the end of it?" -- Anonymous
Jun 18 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 18 June 2014 at 20:00:20 UTC, H. S. Teoh via 
Digitalmars-d wrote:

 Until you compile with -release, and then suddenly invalid 
 input crashes
 your program. :-P (Then you'll go and fire the guy who wrote 
 it.)


 T


My point exactly. If contracts allow things like what Bearophile 
wants to work, then people might use them to do input/output 
validation instead of validating basic assumptions, like they're 
supposed to do. Then we have problems like you described. Maybe 
it's a good idea to keep contracts as-is and not allow them to 
change a function's semantics like this, since they are removed 
in release.
Jun 18 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Meta:


 My point exactly. If contracts allow things like what 
 Bearophile wants to work, then people might use them to do 
 input/output validation instead of validating basic 
 assumptions, like they're supposed to do. Then we have problems 
 like you described. Maybe it's a good idea to keep contracts 
 as-is and not allow them to change a function's semantics like 
 this, since they are removed in release.


This is an interesting topic.

D contracts are a potentially important language feature that is 
currently underused, perhaps because it's currently a little more 
than a nicer place to locate asserts (and it still lacks the 
pre-state ("old") feature).

Function contracts don't change the program semantics, they 
define part if it at a higher level than the function body itself.

When your function has a post-condition that specifies the 
function to return a value between 0 and 9 inclusive, your 
function is defined to return such range, that's its semantics. 
If the function returns something outside that range, then your 
function has a bug. Relying on the function semantics to allow 
casts is one basic usefulness of contracts, but this is just a 
starting point (if take a look at the Whiley language you see 
what I mean: whiley.org ).

If you compile your code with -release you are assuming your code 
doesn't have bugs, and your contracts are always satisfied.

Perhaps D programmers need to stop compiling with -release. 
Perhaps even the name of this compiler switch should be changed 
to something more descriptive of its unsafety and meaning.

The presence of -release compiler switch can't hold back the use 
of contract programming for all it's worth. Currently D is not 
taking its contract programming seriously :-)

Bye,
bearophile
Jun 18 2014
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 06/18/2014 09:54 PM, Meta wrote:

 ...

 This could be a bad thing. It makes it pretty enticing to use contracts
 as input verification instead of logic verification.


The following is doable as well with a standard range analysis:

byte foo(immutable int x){
     if(x<byte.min || x>byte.max)
         throw new InvalidArgumentException("...");
     return x; // ok
}
Jun 19 2014
parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 19/06/14 15:59, Timon Gehr wrote:

 On 06/18/2014 09:54 PM, Meta wrote:

 ...

 This could be a bad thing. It makes it pretty enticing to use contracts
 as input verification instead of logic verification.


 The following is doable as well with a standard range analysis:

 byte foo(immutable int x){
      if(x<byte.min || x>byte.max)
          throw new InvalidArgumentException("...");
      return x; // ok
 }


That will only work now if you use an "else".
Jun 19 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 That will only work now if you use an "else".


So you mean something like

      if(x<byte.min || x>byte.max)
          throw new InvalidArgumentException("...
      else {}

?

That seems like a strange restriction. Why is that?
Jun 22 2014
parent Lionello Lunesu <lionello lunesu.remove.com> writes:
On 23/06/14 04:51, "Nordlöw" wrote:

 That will only work now if you use an "else".


 So you mean something like

       if(x<byte.min || x>byte.max)
           throw new InvalidArgumentException("...
       else {}

 ?

 That seems like a strange restriction. Why is that?


I meant, else return x;

Because it's easy to see what the value of x is within the if and else 
body. It's not trivial to find out that the if body never exits (because 
of the throw) and therefor the code after the if is in essence the else 
body.

L.
Jun 26 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 18 June 2014 at 17:00:36 UTC, bearophile wrote:

 And slowly D Contract Programming starts to become a grown-up 
 language feature.


Interesting!
Jun 18 2014
prev sibling next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 There, I've also added a __traits(intrange, <expression>) which


Very cool. With your new trait I can simplify and, in turn, 
reduce compilation time for usages of

https://github.com/nordlow/justd/blob/master/bound.d

I'm looking forward to the merge :)
Jun 18 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Very cool. With your new trait I can simplify and, in turn, 
 reduce compilation time for usages of


Actually, if I'm not mistaken, with this trait, we can inhibit 
range value range checking in run-time when and get all the 
benefits Ada range types currently delivers.

Yet another sales point for D!
Jun 18 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 Actually, if I'm not mistaken, with this trait, we can inhibit 
 range value range checking in run-time when and get all the 
 benefits Ada range types currently delivers.


I'd like to see and discuss how this could happen.

Bye,
bearophile
Jun 18 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 I'd like to see and discuss how this could happen.


Certainly! I'm available later on this evening at, say, 20.00 CET.

/Per
Jun 18 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 18 June 2014 at 13:00:51 UTC, bearophile wrote:


 I'd like to see and discuss how this could happen.


Note that my discussion so far is about inhibiting run-time 
checknig of the value range of

struct Bound(T,
              B = T, // bounds type
              B lower = B.min,
              B upper = B.max,
              bool optional = false,
              bool exceptional = true)

defined at

https://github.com/nordlow/justd/blob/master/bound.d

where T is an integer type, that is an Ada-style integer range 
type.

It would of course be cool if DMD could support this for floating 
points aswell.

D range indexing/slicing should probably be builtin to the 
compiler.
Jun 18 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 18 June 2014 at 13:12:19 UTC, Nordlöw wrote:


 D range indexing/slicing should probably be builtin to the 
 compiler.


Correction: I mean *inhibiting range checking for array slices* 
should be built into the compiler.
Jun 18 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 Note that my discussion so far is about inhibiting run-time 
 checknig of the value range of

 struct Bound(T,
              B = T, // bounds type
              B lower = B.min,
              B upper = B.max,
              bool optional = false,
              bool exceptional = true)


OK. But how?

Bye,
bearophile
Jun 18 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 18 June 2014 at 13:31:01 UTC, bearophile wrote:


 OK. But how?


The simplest example is probably the constructor for Bound 
defined something like

this(T value)
{
     enum r = __traits(valueRange, value);
     static if (this.min <= r[0] &&
                this.max <= r[1])
     {
         // were within inclusive range
     }
     else
     {
         // need range check here!
     }
     _value = value;
}

assuming that

- `this.min` and `this.max` are statically defined values (which 
they are in bound.d) and that
- value range information is propagated to the constructor 
argument `value`

Other functions such as arithmetic operators should be analogous.

Destroy!
Jun 18 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Destroy!


Correction:

static if (this.min <= r[0] &&
                        r[1] <= this.max)
Jun 18 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 static if (this.min <= r[0] &&
                        r[1] <= this.max)


BTW: I believe valueRange also enables specialization of constant 
arguments inside existing functions without having to move them 
to template arguments of specialized functions. Showcase:

auto pow(T)(T arg, uint n)
{
     enum vr = __traits(valueRange, arg);
     static if (vr.min == vr.max) // if arg is constant
         static      if (vr.min == 0)
             return 1;
         else static if (vr.min == 1)
             return arg;
         else static if (vr.min == 2)
             return arg*arg;
         else static if (vr.min == 3)
             return arg*arg*arg;
         // etc...
     // generic case
}

I guess a __trait, named something like has[Fixed|Constant]Value, 
would be useful here.

I bet there are more possibilities with these traits we haven't 
thought of yet.
Jun 22 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Correction:

It should of course be

auto pow(T)(T arg, uint n)
{
     enum vr = __traits(valueRange, n);
     ....
}
Jun 22 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 auto pow(T)(T arg, uint n)
 {
     enum vr = __traits(valueRange, arg);
     static if (vr.min == vr.max) // if arg is constant


I think that unfortunately this currently can't work, you can't 
tell the range of the input value like that. I have explained why 
in one of my posts in this thread. Please try to explain me why 
I'm wrong.

Bye,
bearophile
Jun 22 2014
next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 22 June 2014 at 21:10:31 UTC, bearophile wrote:

 Nordlöw:


 auto pow(T)(T arg, uint n)
 {
    enum vr = __traits(valueRange, arg);
    static if (vr.min == vr.max) // if arg is constant


 I think that unfortunately this currently can't work, you can't 
 tell the range of the input value like that. I have explained 
 why in one of my posts in this thread. Please try to explain me 
 why I'm wrong.


Don't know what you're referring to, but I guess you mean that - 
because of separate compilation - the code generated for `pow` 
needs to be generic? This is not really a problem, because the 
compiler can generate _additional_ specialized functions for it. 
But then, a normal `if` would also do, because dead code 
elimination can remove the unused parts in these specializations.
Jun 23 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 I think that unfortunately this currently can't work, you can't 
 tell the range of the input value like that. I have explained 
 why in one of my posts in this thread. Please try to explain me 
 why I'm wrong.


I'm currently merely talking about possibilities in this case, so 
I cannot currently prove you wronge ;) To me it seem like an 
unneccessary limitation that valueRanges aren't propagated to 
function call arguments provided that the function source is 
known at compile time. And it doesn't sound to me like enabling 
this in DMD would be such a great task either.
Jun 23 2014
parent reply "Daniel Murphy" <yebbliesnospam gmail.com> writes:
""Nordlöw""  wrote in message news:jctlkqtiztnbnctldtdg forum.dlang.org...


 I'm currently merely talking about possibilities in this case, so I cannot 
 currently prove you wronge ;) To me it seem like an unneccessary 
 limitation that valueRanges aren't propagated to function call arguments 
 provided that the function source is known at compile time. And it doesn't 
 sound to me like enabling this in DMD would be such a great task either.


What happens when a function is called from different places with values 
with different ranges?  What about when it's called from another compilation 
unit?  Generally the argument ranges can only be known when the function is 
inlined, and by then it's much too late to expose them via __traits.
Jun 23 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Daniel Murphy:


 What happens when a function is called from different places 
 with values with different ranges?  What about when it's called 
 from another compilation unit?


One solution is to ignore such cases, so that feature gives 
useful results only when the source is compiled in the same 
compilation unit.

An alternative solution is to handle the functions that use those 
features like templates, and keep the source available across 
different compilation units. This is perhaps acceptable because I 
think that kind of features is going to be used mostly for 
library code and not for most user functions.

Bye,
bearophile
Jun 23 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 23 June 2014 at 13:13:38 UTC, bearophile wrote:

 One solution is to ignore such cases, so that feature gives 
 useful results only when the source is compiled in the same 
 compilation unit.

 An alternative solution is to handle the functions that use 
 those features like templates, and keep the source available 
 across different compilation units. This is perhaps acceptable 
 because I think that kind of features is going to be used 
 mostly for library code and not for most user functions.


That is certainly a good idea.
Jun 23 2014
prev sibling parent reply Shammah Chancellor <anonymous coward.com> writes:
On 2014-06-23 13:13:37 +0000, bearophile said:


 Daniel Murphy:
 

 What happens when a function is called from different places with 
 values with different ranges?  What about when it's called from another 
 compilation unit?


 
 One solution is to ignore such cases, so that feature gives useful 
 results only when the source is compiled in the same compilation unit.
 
 An alternative solution is to handle the functions that use those 
 features like templates, and keep the source available across different 
 compilation units. This is perhaps acceptable because I think that kind 
 of features is going to be used mostly for library code and not for 
 most user functions.
 
 Bye,
 bearophile


Wouldn't that cause compiler errors that only happen depending on what 
order you compile things?

-Shammah
Jun 24 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Shammah Chancellor:


 Wouldn't that cause compiler errors that only happen depending 
 on what order you compile things?


If you refer to the first "solution", then the answer is yes. The 
ability to catch bugs at compile-time is not fully deterministic, 
it's a help for the programmer, but it's not always possible. 
This is why when you use a enum precondition you also have to add 
a regular pre-condition too.

If you refer to the second "solution" then I think the answer is 
no, because your problems doesn't currently happen with templates.

Bye,
bearophile
Jun 24 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 23 June 2014 at 12:51:58 UTC, Daniel Murphy wrote:

 What happens when a function is called from different places 
 with values with different ranges?  What about when it's called 
 from another compilation unit?  Generally the argument ranges 
 can only be known when the function is inlined, and by then 
 it's much too late to expose them via __traits.


Ok. That indeed makes things more complicated than I first 
thought :|
Jun 23 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:


 The simplest example is probably the constructor for Bound 
 defined something like


Very good, with this you have framed the discussion well :-)



 - value range information is propagated to the constructor 
 argument `value`


The problem is, I think this is currently false (even if you call 
your constructor with just a number literal). I'd like this 
feature in D, but I don't know how much work it needs to be 
implemented.

D language is designed to allow you to create data structures in 
library code able to act a lot like built-in features (so there's 
a refined operator overloading, opCall, static opCall, and even 
more unusual things like opDispatch), but there are built-in 
features that can't yet be reproduced in library code, observe:


void main() {
     int[5] arr;
     auto x = arr[7];
}


dmd 2.066alpha gives a compile error:

test.d(3,14): Error: array index 7 is out of bounds arr[0 .. 5]


In D there is opIndex to overload the [ ], but its arguments are 
run-time values, so I think currently they have no way to give a 
compile-time error if you use an index that is known statically 
to be outside the bounds. So currently you can't reproduce that 
behavour with library code. Propagating the value range 
information to the constructor, plus the new __trait(valueRange, 
exp), allow to solve this problem. And indeed this allows to 
implement nice ranged values like in Ada, and to do what the 
Static_Predicate of Ada does.


Another common example of what you currently can't do with 
library code:

void main() {
     import std.bigint;
     BigInt[] arr = [10, 20];

     import std.numeric;
     alias I10 = Bound!(int, 0, 10);
     I10[] arr = [8, 6, 20];
}


(In theory the compiler should also catch at compile time that 
bug, because 20 is outside the valid bounds of I10.)


The "enum precondition" I've suggested elsewhere is a 
generalization of that feature (but it's not a strict subset 
because it only works with literals, so it's good to have both 
features), because it manages not just ranges of a single value, 
but also other literals, like an array:


void foo(int[] arr)
enum in {
     assert(arr.all!(x => x < 10));
} in {
     assert(arr.all!(x => x < 10));
} body {
     // ...
}
void main() {
     foo([10, 20]); // gives compile-time error.
}


This is possible only if the source code of foo is available in 
the compilation unit. In presence of separated compilation the 
enum precondition is ignored. So the enum preconditon can't 
replace regular pre-conditions, they are useful to catch 
statically only a subset of bugs. The same happens with the idea 
of propagating range information to the constructors. One way to 
avoid or mitigate this problem is to leave available the source 
code of functions with an enum pre-conditions, just like with 
templates. Perhaps this is not a big problem because enum 
preconditions and constructor value range propagation are meant 
to be used mostly in library code, like in Bound integers, etc.

Bye,
bearophile
Jun 18 2014
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Jun 18, 2014 at 10:08:06PM +0000, bearophile via Digitalmars-d wrote:
[...]

 D language is designed to allow you to create data structures in
 library code able to act a lot like built-in features (so there's a
 refined operator overloading, opCall, static opCall, and even more
 unusual things like opDispatch),


opDispatch is extremely powerful; I think we've only barely begun to tap
into what it can do. Like my recent safe-dereference template function.
;-)



 but there are built-in features that can't yet be reproduced in
 library code, observe:
 
 void main() {
     int[5] arr;
     auto x = arr[7];
 }
 
 
 dmd 2.066alpha gives a compile error:
 
 test.d(3,14): Error: array index 7 is out of bounds arr[0 .. 5]
 
 
 In D there is opIndex to overload the [ ], but its arguments are
 run-time values, so I think currently they have no way to give a
 compile-time error if you use an index that is known statically to be
 outside the bounds. So currently you can't reproduce that behavour
 with library code. Propagating the value range information to the
 constructor, plus the new __trait(valueRange, exp), allow to solve
 this problem. And indeed this allows to implement nice ranged values
 like in Ada, and to do what the Static_Predicate of Ada does.


It seems like ultimately, we want to have some kind of uniformity
between built-in compiler intrinsics and user-defined types, such as
allowing user-defined types to access internal compiler knowledge like
value range and many other things.

One very useful thing to have would be a way to tell if a particular
symbol has a compile-time known value. You could then do things like
custom constant-folding on user-defined types by automatically
simplifying expressions at compile-time.

Hmm. Maybe this is already possible to some extent?

	template hasCompileTimeValue(alias Sym) {
		alias hasCompileTimeValue = __traits(compiles, (){
			enum val = Sym;
		});
	}
	int x = 10, y;

	// Will this work? (I don't know)
	assert(hasCompileTimeValue!x);
	assert(!hasCompileTimeValue!y);



 Another common example of what you currently can't do with library
 code:
 
 void main() {
     import std.bigint;
     BigInt[] arr = [10, 20];
 
     import std.numeric;
     alias I10 = Bound!(int, 0, 10);
     I10[] arr = [8, 6, 20];
 }
 
 
 (In theory the compiler should also catch at compile time that bug,
 because 20 is outside the valid bounds of I10.)


[...]

This is a different instance of the same problem as above, isn't it?
If Bound has access to compiler knowledge about value ranges, then it
would be able to statically reject out-of-range values.


T

-- 
"I'm not childish; I'm just in touch with the child within!" - RL
Jun 18 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:


 This is a different instance of the same problem as above, 
 isn't it?
 If Bound has access to compiler knowledge about value ranges, 
 then it
 would be able to statically reject out-of-range values.


Yes, with the latest patch by Kenji it's thankfully an instance 
of the same problem above, because every literal in the array 
gets used to instantiate a Bound!().

Bye,
bearophile
Jun 19 2014
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 void main() {
     import std.bigint;
     BigInt[] arr = [10, 20];

     import std.numeric;
     alias I10 = Bound!(int, 0, 10);
     I10[] arr = [8, 6, 20];
 }


In the meantime Kenji delivers, those BigInt array literals are 
possible with this patch:
https://github.com/D-Programming-Language/dmd/pull/3680

Bye,
bearophile
Jun 19 2014
prev sibling parent Lionello Lunesu <lionello lunesu.remove.com> writes:
On 18/06/14 20:46, "Nordlöw" wrote:

 Very cool. With your new trait I can simplify and, in turn, reduce
 compilation time for usages of


 Actually, if I'm not mistaken, with this trait, we can inhibit range
 value range checking in run-time when and get all the benefits Ada range
 types currently delivers.

 Yet another sales point for D!


I submitted a pull request with the trait, without the if-else stuff! 
This should be faster to make it in.

https://github.com/D-Programming-Language/dmd/pull/3679

L.
Jun 18 2014
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu wrote:

 I got this thing working and I think it's about time I get some 
 comments on it.


This is really cool. Good job!

One thing we need to be careful with is how this is specified.
Because of all the compile time introspection (e.g. __traits
compiles and now __traits intrange), this VRP needs to be
precisely specified otherwise you end up with incompatible
differences between different compiler front ends. I don't want
to see code compiling in one compiler, but not another like we do
in C++ (and if we do, I'd like it to be minimized).

If this goes in, the mechanisms by which is works need to be
added to the spec.
Jun 18 2014
parent "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Wednesday, 18 June 2014 at 14:10:11 UTC, Peter Alexander wrote:

 On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu 
 wrote:

 I got this thing working and I think it's about time I get 
 some comments on it.


 This is really cool. Good job!

 One thing we need to be careful with is how this is specified.
 Because of all the compile time introspection (e.g. __traits
 compiles and now __traits intrange), this VRP needs to be
 precisely specified otherwise you end up with incompatible
 differences between different compiler front ends. I don't want
 to see code compiling in one compiler, but not another like we 
 do
 in C++ (and if we do, I'd like it to be minimized).

 If this goes in, the mechanisms by which is works need to be
 added to the spec.


I agree with what is stated here.

And will repeat that this sounds awesome.
Jun 18 2014
prev sibling next sibling parent reply "Don" <x nospam.com> writes:
On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu wrote:

 Hi,



 https://github.com/lionello/dmd/compare/if-else-range

 There, I've also added a __traits(intrange, <expression>) which 
 returns a tuple with the min and max for the given expression.



 Destroy?


The compiler uses value range propagation in this {min, max} 
form, but I think that's an implementation detail. It's well 
suited for arithmetic operations, but less suitable for logical 
operations. For example, this code can't overflow, but {min, max} 
range propagation thinks it can.

ubyte foo ( uint a) {
   return (a & 0x8081) & 0x0FFF;
}

For these types of expressions, {known_one_bits, known_zero_bits} 
works better.
Now, you can track both types of range propagation 
simultaneously, and I think we probably should improve our 
implementation in that way. It would improve the accuracy in many 
cases.

Question: If we had implemented that already, would you still 
want the interface you're proposing here?
Jun 20 2014
parent Lionello Lunesu <lionello lunesu.remove.com> writes:
On 20/06/14 15:53, Don wrote:

 On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu wrote:

 Hi,



 https://github.com/lionello/dmd/compare/if-else-range

 There, I've also added a __traits(intrange, <expression>) which
 returns a tuple with the min and max for the given expression.



 Destroy?


 The compiler uses value range propagation in this {min, max} form, but I
 think that's an implementation detail. It's well suited for arithmetic
 operations, but less suitable for logical operations. For example, this
 code can't overflow, but {min, max} range propagation thinks it can.

 ubyte foo ( uint a) {
    return (a & 0x8081) & 0x0FFF;
 }

 For these types of expressions, {known_one_bits, known_zero_bits} works
 better.
 Now, you can track both types of range propagation simultaneously, and I
 think we probably should improve our implementation in that way. It
 would improve the accuracy in many cases.

 Question: If we had implemented that already, would you still want the
 interface you're proposing here?


You could have different __traits in that case:
__traits(valueRange,...) // for min/max
__traits(bitRange,...) // mask

You example seems rather artificial though. IRL you'd get a compiler 
warning/error and could fix it by changing the code to "& 0xFF". I 
personally have not yet had the need for these bit-masks.

L.
Jun 20 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Lionello Lunesu:


 Have a look at the branch:
 https://github.com/lionello/dmd/compare/if-else-range


The need for this D improvement is sufficiently common, a just 
appeared question:
http://forum.dlang.org/thread/jwfvuaohvlvwzjlmztsj forum.dlang.org

Lionello needs some cheering & support to create the patch that 
implements the value range propagation for if-else. Exposing the 
range and implementing value range propagation for if-else are 
sufficiently distinct needs.

Bye,
bearophile
Jun 22 2014
prev sibling next sibling parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
Latest [1] now also supports CTFE:

     const i = foo ? -1 : 33;

     if (i)
       static assert(__traits(intrange, i) == Tuple!(-1, 33));
     else
     {
       static assert(i == 0); // Works now!
       static assert(__traits(intrange, i) == Tuple!(0, 0));
     }

     if (i == 33)
     {
       static assert(i == 33); // Works now!
       static assert(__traits(intrange, i) == Tuple!(33, 33));
     }
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 32));


Next up: support for immutable/const members and "if (i) static assert(i)"

L.

[1] https://github.com/lionello/dmd/tree/if-else-range
Jun 30 2014
parent "Tove" <Tove fransson.se> writes:
On Monday, 30 June 2014 at 07:47:22 UTC, Lionello Lunesu wrote:

 Latest [1] now also supports CTFE:

     const i = foo ? -1 : 33;

     if (i)
       static assert(__traits(intrange, i) == Tuple!(-1, 33));
     else
     {
       static assert(i == 0); // Works now!
       static assert(__traits(intrange, i) == Tuple!(0, 0));
     }

     if (i == 33)
     {
       static assert(i == 33); // Works now!
       static assert(__traits(intrange, i) == Tuple!(33, 33));
     }
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 32));


 Next up: support for immutable/const members and "if (i) static 
 assert(i)"

 L.

 [1] https://github.com/lionello/dmd/tree/if-else-range


Fantastic work, although I would prefer Bearophile's  
'value_range', is there any reason why the same trait could not 
be used for float, etc? (I don't need it for float, just as an 
example).

I guess an interval_set would be too complicated, slowing down 
the compiler? i.e. multiple ranges, or multiple values, just 
thinking out loud... Anyway what you did already is kick ass! :)
Jun 30 2014
prev sibling parent Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 18 June 2014 16:40, Lionello Lunesu via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 Hi,

 I got this thing working and I think it's about time I get some comments on
 it.

 I've been wanting to extend Value Rang Propagation (VRE) for some time now.
 Mostly because of the fix to the troublesome "signed-unsigned comparisons"
 issue. Enabling VRE for if-else and "&&" will fix many of the false-positive
 warnings given out by the fix to bug 259 by allowing code like this: if
 (signed > 0 && signed < unsigned) { .. }

 Have a look at the branch:
 https://github.com/lionello/dmd/compare/if-else-range

 There, I've also added a __traits(intrange, <expression>) which returns a
 tuple with the min and max for the given expression. It's used in the test
 case as follows:


     const i = foo ? -1 : 33;

     if (i)
       static assert(__traits(intrange, i) == Tuple!(-1, 33));
     else
     {
       //static assert(i == 0); TODO
       static assert(__traits(intrange, i) == Tuple!(0, 0));
     }

     if (i == 33)
     {
       //static assert(i == 33); TODO
       static assert(__traits(intrange, i) == Tuple!(33, 33));
     }
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 32));

     if (10 <= i)
       static assert(__traits(intrange, i) == Tuple!(10, 33));
     else
       static assert(__traits(intrange, i) == Tuple!(-1, 9));


 It would be nice if this can be used by CTFE as well.

 Destroy?


I'm looking forward to this so hard!
The one time I've attempted to hack on DMD, it was to investigate the
idea of doing this.

As others said, I think a key use case is for contracts/preconditions.
Also eliminating annoying warnings when down-casting.

I suspect there are many great optimisation opportunities available
too when this is pervasive. switch() may gain a lot of great
information to work with! :)
Jun 30 2014