Why no constraint error?

Why no constraint error?

[Samuel Mize]

Greetings, all,

The following question has come up on chat@gnat.com, but it's really
a general Ada question and I'm throwing it out to comp.lang.ada.

It's probably been asked and answered before, but I can't find a
good explanation on DejaNews.

The question is, why doesn't this code raise an exception when run
under GNAT?

    pragma Normalize_Scalars;
    with Ada.Text_Io;
    procedure Test_Subrange_Checks is
        type T_Source  is new Integer range 7 .. 10;
        type T_Target is new Integer range 7 .. 10; -- identical ranges

        Source: T_Source; -- initialized out of range by Normalize_Scalars
        Target: T_Target := 10;
    begin
        Target := T_Target (Source);  -- no range check occurs!!!!!!!!!!
        Ada.Text_Io.Put_Line (T_Target'Image (Target));
    end Test_Subrange_Checks;


Per 13.9.1(9-11), evaluating the uninitialized variable quite properly
returns an invalid value.  However, in the assignment, this value
"is converted to the subtype of the target" per 5.2(11).  In type
conversion, "[a]fter conversion of the value to the target type, if
the target subtype is constrained, a check is performed that the value
satisfies this constraint" per 4.6(51).

11.6(5) provides permission to skip language-defined checks if this
would not "have some effect on the external interactions of the
program."  Since program output is an external file, this is an
external effect per 1.1.3(8-9).

If your reply is the following, please consider it already sent:

* Trust me, GNAT is right.

* Informally, it makes sense to omit this check, since the ranges
  of the types statically match.

I'm looking for an ARM reference that makes it legal to omit the
check named in 4.6(51) in this case.  I want to understand the
specific language rule, so I can tell when it will or won't apply.

I'd appreciate email, but will also check this group for replies.

Thanks very much for your time and attention.

Samuel Mize

-- 
Samuel Mize -- smize@imagin.net -- Team Ada
(personal net account)

Re: Why no constraint error?

[Samuel Mize]

In article <5gs20s$2g11@prime.imagin.net>,
Samuel Mize <smize@imagin.net> wrote:
>The question is, why doesn't this code raise an exception when run
>under GNAT?
>
>    pragma Normalize_Scalars;
>    with Ada.Text_Io;
>    procedure Test_Subrange_Checks is
>        type T_Source  is new Integer range 7 .. 10;
>        type T_Target is new Integer range 7 .. 10; -- identical ranges
>
>        Source: T_Source; -- initialized out of range by Normalize_Scalars
>        Target: T_Target := 10;
>    begin
>        Target := T_Target (Source);  -- no range check occurs!!!!!!!!!!
>        Ada.Text_Io.Put_Line (T_Target'Image (Target));
>    end Test_Subrange_Checks;


It turns out GNAT is right.  (No big surprise.)

I think I've found it.  13.9.1(9) defines invalid representations;
it also states "The rules of the language outside this subclause
assume that all objects have valid representations."

So, the compiler can omit the range checks by assuming that
the data is valid.

Note that, in a similar case, an array reference can point to
any arbitrary memory location (uninitialized scalar used as
an array index).

While I understand this from an efficiency point of view, I'd
like it to be different.  Whine, whine.  One project I'm on is
auto-converting a huge base of occam code to Ada, and a number
of uninitialized integers are biting us in the tail.
(don't start, we DON'T HAVE occam on our target machine)

However, I now see how this optimization is allowed by the
formal rules, so I'll live with it.

One useful compiler option, it seems to me, would tell the
compiler to NOT omit such checks in such cases -- to do
explicitly all range checks.  I'd love to be able to test
some of this auto-generated garbage under such an option.

Samuel Mize

-- 
Samuel Mize -- smize@imagin.net -- Team Ada
(personal net account)

Re: Why no constraint error?

[Robert A Duff]

In article <5gs81q$114r@prime.imagin.net>,
Samuel Mize <smize@imagin.net> wrote:
>In article <5gs20s$2g11@prime.imagin.net>,
>Samuel Mize <smize@imagin.net> wrote:
>>The question is, why doesn't this code raise an exception when run
>>under GNAT?
>>
>>    pragma Normalize_Scalars;
>>    with Ada.Text_Io;
>>    procedure Test_Subrange_Checks is
>>        type T_Source  is new Integer range 7 .. 10;
>>        type T_Target is new Integer range 7 .. 10; -- identical ranges
>>
>>        Source: T_Source; -- initialized out of range by Normalize_Scalars
>>        Target: T_Target := 10;
>>    begin
>>        Target := T_Target (Source);  -- no range check occurs!!!!!!!!!!
>>        Ada.Text_Io.Put_Line (T_Target'Image (Target));
>>    end Test_Subrange_Checks;
>
>
>It turns out GNAT is right.  (No big surprise.)

No, I believe GNAT is wrong.

>I think I've found it.  13.9.1(9) defines invalid representations;
>it also states "The rules of the language outside this subclause
>assume that all objects have valid representations."
>
>So, the compiler can omit the range checks by assuming that
>the data is valid.

No, that's not what I meant when I wrote 13.9.1(9).  That is, the
compiler cannot assume data is valid.  The *rules* in the rest of the RM
assume valid data, but that assumption is wrong, and 13.9.1 tries to
fill in the resulting logical holes.

In your example, Source should be initialized to some invalid value of
type T_Source, such as 11.  13.9.1(10) applies, and 11 is greater than
10 (despite the fact that 11 is invalid), and so should fail the range
check.  I believe there is no permission to omit that check.

Unfortunately, 13.9.1(11) is a loophole you could drive a truck through.
The assumption is that compilers will be reasonable.  There's some AARM
discussion on this point.  But this para is irrelevant to your example.

I'm not entirely sure if the above analysis is correct.  Tucker, if
you're listening, can you comment?

>Note that, in a similar case, an array reference can point to
>any arbitrary memory location (uninitialized scalar used as
>an array index).

It was definitely a goal of Ada 9X that an uninitialized variable cannot
cause arbitrary memory locations to be overwritten (e.g. when you say
"A(I) := ..." and I is uninitialized.  This is true whether or not you
say Normalize_Scalars.  (In Ada 83, such a case is erroneous, and so
could trash memory or anything else bad.)

>While I understand this from an efficiency point of view, I'd
>like it to be different.  Whine, whine.  One project I'm on is
>auto-converting a huge base of occam code to Ada, and a number
>of uninitialized integers are biting us in the tail.
>(don't start, we DON'T HAVE occam on our target machine)
>
>However, I now see how this optimization is allowed by the
>formal rules, so I'll live with it.
>
>One useful compiler option, it seems to me, would tell the
>compiler to NOT omit such checks in such cases -- to do
>explicitly all range checks.  I'd love to be able to test
>some of this auto-generated garbage under such an option.

I'd like to have an option to check all uninit vars.

- Bob

Re: Why no constraint error?

[Tucker Taft]

Robert A Duff (bobduff@world.std.com) wrote:

: In article <5gs81q$114r@prime.imagin.net>,
: Samuel Mize <smize@imagin.net> wrote:
: >In article <5gs20s$2g11@prime.imagin.net>,
: >Samuel Mize <smize@imagin.net> wrote:
: >>The question is, why doesn't this code raise an exception when run
: >>under GNAT?
: >>
: >>    pragma Normalize_Scalars;
: >>    with Ada.Text_Io;
: >>    procedure Test_Subrange_Checks is
: >>        type T_Source  is new Integer range 7 .. 10;
: >>        type T_Target is new Integer range 7 .. 10; -- identical ranges
: >>
: >>        Source: T_Source; -- initialized out of range by Normalize_Scalars
: >>        Target: T_Target := 10;
: >>    begin
: >>        Target := T_Target (Source);  -- no range check occurs!!!!!!!!!!
: >>        Ada.Text_Io.Put_Line (T_Target'Image (Target));
: >>    end Test_Subrange_Checks;
: >
: >
: >It turns out GNAT is right.  (No big surprise.)

: No, I believe GNAT is wrong.

Well Bob, I believe GNAT is technically right in this one, though
I think it may be pessimizing the code overall if it follows
the approach implied by the above (see below for more discussion).

One thing to keep in mind is that "out of the box" GNAT suppresses
certain run-time checks (not my favorite feature of GNAT, I might say ;-).  
I trust this was compiled with all checks *on*...

: >I think I've found it.  13.9.1(9) defines invalid representations;
: >it also states "The rules of the language outside this subclause
: >assume that all objects have valid representations."
: >
: >So, the compiler can omit the range checks by assuming that
: >the data is valid.

: No, that's not what I meant when I wrote 13.9.1(9).  That is, the
: compiler cannot assume data is valid.  The *rules* in the rest of the RM
: assume valid data, but that assumption is wrong, and 13.9.1 tries to
: fill in the resulting logical holes.

: In your example, Source should be initialized to some invalid value of
: type T_Source, such as 11.  13.9.1(10) applies, and 11 is greater than
: 10 (despite the fact that 11 is invalid), and so should fail the range
: check.  I believe there is no permission to omit that check.

I believe there is permission to do this, though I think it is unwise 
to do so (see below).

: Unfortunately, 13.9.1(11) is a loophole you could drive a truck through.
: The assumption is that compilers will be reasonable.  There's some AARM
: discussion on this point.  But this para is irrelevant to your example.

: I'm not entirely sure if the above analysis is correct.  Tucker, if
: you're listening, can you comment?

: >Note that, in a similar case, an array reference can point to
: >any arbitrary memory location (uninitialized scalar used as
: >an array index).

: It was definitely a goal of Ada 9X that an uninitialized variable cannot
: cause arbitrary memory locations to be overwritten (e.g. when you say
: "A(I) := ..." and I is uninitialized.  This is true whether or not you
: say Normalize_Scalars.  (In Ada 83, such a case is erroneous, and so
: could trash memory or anything else bad.)

: >While I understand this from an efficiency point of view, I'd
: >like it to be different.  Whine, whine.  One project I'm on is
: >auto-converting a huge base of occam code to Ada, and a number
: >of uninitialized integers are biting us in the tail.
: >(don't start, we DON'T HAVE occam on our target machine)
: >
: >However, I now see how this optimization is allowed by the
: >formal rules, so I'll live with it.
: >
: >One useful compiler option, it seems to me, would tell the
: >compiler to NOT omit such checks in such cases -- to do
: >explicitly all range checks.  I'd love to be able to test
: >some of this auto-generated garbage under such an option.

: I'd like to have an option to check all uninit vars.

Here is my explanation of the issue:  For checks whose failure
might result in real "damage", the compiler must be very careful
about what it assumes.  In particular, it must not assume that
variables are initialized unless it can prove they are.  This means
that for certain checks, the compiler should not "believe" in the
declared range of the variable.  

In this particular case, the propagation of an uninitialized 
value from one variable to another is relatively benign, since 
no memory is being trashed by this propagation.  The real question 
is what happens when "Target" is used as an index into an array.
Does GNAT remember that Target might become deinitialized by the
assignment, and hence do the check when Target is used as an index?
Or does GNAT see that Target is initialized to a valid value, and
presume that it never becomes deinitialized.

In our AdaMagic front end, objects are identified by the compiler
as either "reliable" or "unreliable."  For reliable objects, we
presume they are within their declared subtype, and we make sure that
that presumption is not violated.  In particular, we presume that
explicitly initialized scalar variables are reliable, and we
believe in their declared subtype, and we make sure we don't
allow them to become deinitialized.  Scalar variables that are not
explicitly initialized are considered "unreliable," and we don't
believe their declared subtype unless we can prove through other
means that they are within it.  So in the above test case, we
would certainly do the check, because we are assigning from an
unreliable variable to a reliable one.  An alternative approach
is to mark "Target" as unreliable after such an assignment, and
factor that into future decisions.  That requires some amount
of data flow analysis in the front end, which is something which
is more often deferred until an optimization phase.

Also, marking Target as unreliable might be pessimizing the code,
if there are a number of uses of Target which will require more
checks due to its unreliability.  A global optimizer can look around
and decide where to put checks.  Our front end adopts some simple
rules (as exemplified above) that allows it to run essentially one pass.

I'm curious what approach GNAT adopts, and whether the above
would in fact reveal a bug if Target were used as an array index...

: - Bob

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Why no constraint error?

[Robert A Duff]

In article <E7G5q1.J8q.0.-s@inmet.camb.inmet.com>,
Tucker Taft <stt@houdini.camb.inmet.com> wrote:
>Well Bob, I believe GNAT is technically right in this one, ...

Can you quote chapter and verse, to show where my analysis was wrong?
(Legalistically, I mean -- ignoring issues of what's
desirable/efficient/etc.)

- Bob

Re: Why no constraint error?

[Tucker Taft]

Robert A Duff (bobduff@world.std.com) wrote:

: In article <E7G5q1.J8q.0.-s@inmet.camb.inmet.com>,
: Tucker Taft <stt@houdini.camb.inmet.com> wrote:
: >Well Bob, I believe GNAT is technically right in this one, ...

: Can you quote chapter and verse, to show where my analysis was wrong?
: (Legalistically, I mean -- ignoring issues of what's
: desirable/efficient/etc.)

I guess I agree with you, that presuming 13.9.1(10) applies, then
"deinitializing" an initialized scalar variable is a no-no.

You would have to invoke 13.9.1(11) and claim that the uninitialized
representation was so weird that it didn't correspond to a value of
the type, and hence you could legitimately propagate it on assignment
(so long as the optimizer didn't forget that the LHS is now potentially
deinitialized as well).

I think the simpler choice is to prevent initialized scalars from
becoming deinitialized, and that seems to be what 13.9.1(10) is requiring.

A subtler question is whether an assignment from an uninitialized
scalar to another uninitialized scalar can be allowed to leave the
LHS still having an invalid representation.  13.9.1(10) seems to
say "no," any assignment must leave the LHS with a valid representation
(unless the RHS is an unchecked conversion or call on an imported 
function, per 13.9.1(12)).

: - Bob

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Why no constraint error?

[Samuel A. Mize]

Tucker Taft wrote:
> Well Bob, I believe GNAT is technically right in this one, though
> I think it may be pessimizing the code overall if it follows
> the approach implied by the above (see below for more discussion).

Sorry -- "pessimizing?"  Could you supply a definition for the
less experienced?  Do you mean "making less efficient through
excessive pessimism?"  Thanks.


> One thing to keep in mind is that "out of the box" GNAT suppresses
> certain run-time checks (not my favorite feature of GNAT, I might say ;-).
> I trust this was compiled with all checks *on*...

It was.


> In this particular case, the propagation of an uninitialized
> value from one variable to another is relatively benign, since
> no memory is being trashed by this propagation.  The real question
> is what happens when "Target" is used as an index into an array.
> Does GNAT remember that Target might become deinitialized by the
> assignment, and hence do the check when Target is used as an index?

No.


> Or does GNAT see that Target is initialized to a valid value, and
> presume that it never becomes deinitialized.

No.  I tested the array case with a straight uninitialized
variable, and it indexed to it.  (I used Normalize_Scalars
to get a predictable value, but I don't *think* this would
impact the presence/absence of this range check.)


> In our AdaMagic front end, objects are identified by the compiler
> as either "reliable" or "unreliable."  ...

This sounds slick.  I'll look at your web site.


> I'm curious what approach GNAT adopts, and whether the above
> would in fact reveal a bug if Target were used as an array index...

No, it doesn't.


> 
> -Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
> Intermetrics, Inc.  Burlington, MA  USA


Sam Mize
(same Sam Mize, different account -- opinions are my own)
-- 
Samuel Mize           (817) 619-8622               "Team Ada"
Hughes Training Inc.  PO Box 6171 m/s 400, Arlington TX 76005

Re: Why no constraint error?

[Robert Dewar]

Sam Mize said

<<No.  I tested the array case with a straight uninitialized
variable, and it indexed to it.  (I used Normalize_Scalars
to get a predictable value, but I don't *think* this would
impact the presence/absence of this range check.)>>

"it indexed to it"

but certainly did not assign to it!!!!

Re: Why no constraint error?

[Robert A Duff]

In article <33369ACC.41C6@magellan.bgm.link.com>,
Samuel A. Mize <smize@magellan.bgm.link.com> wrote:
>Tucker Taft wrote:
>Sorry -- "pessimizing?"  Could you supply a definition for the
>less experienced?  Do you mean "making less efficient through
>excessive pessimism?"  Thanks.

"To pessimize" is the opposite of "to optimize".  If the compiler goes
out of its way to do something that makes typical programs run slower
(than they otherwise would, whatever that might mean), then that's a
"pessimization".

>> Does GNAT remember that Target might become deinitialized by the
>> assignment, and hence do the check when Target is used as an index?
>
>No.

>> Or does GNAT see that Target is initialized to a valid value, and
>> presume that it never becomes deinitialized.
>
>No.  I tested the array case with a straight uninitialized
>variable, and it indexed to it.  (I used Normalize_Scalars
>to get a predictable value, but I don't *think* this would
>impact the presence/absence of this range check.)

>> I'm curious what approach GNAT adopts, and whether the above
>> would in fact reveal a bug if Target were used as an array index...
>
>No, it doesn't.

I don't understand the above three "No" answers -- they seem mutually
contradictory.  If "A(I) := ..." can overwrite memory that is not part
of the array A, when I is an uninitialized variable, then that's a
compiler bug.  Are you saying that GNAT does, or does not, have this
bug?  (Note that it wasn't a compiler bug in Ada 83 -- in Ada 83, it was
erroneous, whereas in Ada 95, it is a bounded error.)

- Bob

Re: Why no constraint error?

[Robert Dewar]

<<I don't understand the above three "No" answers -- they seem mutually
contradictory.  If "A(I) := ..." can overwrite memory that is not part
of the array A, when I is an uninitialized variable, then that's a
compiler bug.  Are you saying that GNAT does, or does not, have this
bug?  (Note that it wasn't a compiler bug in Ada 83 -- in Ada 83, it was
erroneous, whereas in Ada 95, it is a bounded error.)>>

I cannot answer for what Sam Mize is trying to say, since his post was
indeed confusing, but the fact is that GNAT does NOT overwrite memory
on an array assignment of this type ....

Re: Why no constraint error?

[Robert Dewar]

<<Unfortunately, 13.9.1(11) is a loophole you could drive a truck through.
The assumption is that compilers will be reasonable.  There's some AARM
discussion on this point.  But this para is irrelevant to your example.>>

I was always amazed that Bob could seriously suggest that all assignment
statements must do range checks. In some cases, especially with arrays
where you can never prove that elements are uninitialized in practice,
you can slow things down by a large factor with this decision.

Furthermore, in practice putting these range checks in has almost no
effect (that's an empirical observation from experimentation). So what
is being suggested here makes no sense to me, and seems completely
*unreasonable*.

For GNAT, part of "will be reasonable" is "will be reasonably efficient",
so I agree with your assumption, and so does GNAT!

Re: Why no constraint error?

[Robert A Duff]

In article <dewar.859021939@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>I was always amazed that Bob could seriously suggest that all assignment
>statements must do range checks. In some cases, especially with arrays
>where you can never prove that elements are uninitialized in practice,
                                               initialized, you mean?
>you can slow things down by a large factor with this decision.

Not sure what you mean, but I'm certainly not suggesting that array
assignment must check each component.  It's perfectly legitimate to copy
an array containing uninitialized scalar values -- it would be wrong
(and slow) to range check them.

- Bob