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 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 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 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 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 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 next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 I'd like a name like integral_range,

"value_range" seems better, more general. Bye, bearophile
Jun 18 2014
prev sibling next sibling parent "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
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
next 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 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
parent 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
prev sibling next sibling parent =?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
prev sibling next sibling parent "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
prev sibling 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 next sibling parent =?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
prev sibling 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent =?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
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Destroy!

Correction: static if (this.min <= r[0] && r[1] <= this.max)
Jun 18 2014
prev sibling next 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 "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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 "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 next sibling 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 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 =?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
prev sibling next sibling parent =?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
prev sibling 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 next sibling parent "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
prev sibling 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 next sibling parent =?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
prev sibling next sibling parent "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
prev sibling next 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 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 next sibling 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 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