Optimizing and Constraint Checks

Optimizing and Constraint Checks

[Ed Bruce]

I am currently attempting to implement a safe, portable
Unchecked_Conversion of an enumerated type to integer and from an integer
type back to the enumeration. The following code shows the current
solution, the question raised by one engineer is can we guarantee the the
return statement in the To_Enum function is portable. That is may a
compiler optimize away the ENUM'Pos and ENUM'Val and effectively eliminate
the constraint check.

with Unchecked_Conversion;

generic
  type ENUM is (<>);
package Convert is
  Illegal_Value : exception;

  function To_Integer( Value : in ENUM )    return INTEGER;
  function To_Enum   ( Value : in INTEGER ) return ENUM;
end Convert;

package Convert is
  function To_Integer is new Unchecked_Conversion(
    Source => ENUM,
    Target => INTEGER );

  function Convert_Enum is new Unchecked_Conversion(
    Source => INTEGER,
    Target => ENUM );

  function To_Enum( Value : in INTEGER ) return ENUM is
  begin
    return ENUM'Val( ENUM'Pos( Convert_Enum( Value )))
  exception
    when Constraint_Error =>
      raise Illegal_Value;
    when Others =>
     raise;
  end To_Enum;
end Convert;
Ed Bruce
edward@igate1.hac.com

Re: Optimizing and Constraint Checks

[Theodore Dennison]

Ed Bruce <edward@igate1.hac.com> writes:

> I am currently attempting to implement a safe, portable
> Unchecked_Conversion of an enumerated type to integer and from an integer
> type back to the enumeration. The following code shows the current
> solution, the question raised by one engineer is can we guarantee the the
> return statement in the To_Enum function is portable. That is may a
> compiler optimize away the ENUM'Pos and ENUM'Val and effectively eliminate
> the constraint check.


Your engineer has a vaild concern. One of the problems with Ada 83 is that 
there is no PORTABLE way to force a constraint check. In practice, you have
to find what your compiler won't optimize away, and code to that. 
Unfortunately, the next version of the same compiler could work differently.

In practice this isn't as big a problem as it looks on paper. I have only 
encountered one compiler (for an embedded system) which optimized away too
many checks. The benefits that this kind of type checking can give you 
vastly outweigh the problems it causes. Just make sure you test it!

Hopefully, this problem was fixed with Ada 95.

T.E.D.

Re: Optimizing and Constraint Checks

[Garlington KE]

Ed Bruce (edward@igate1.hac.com) wrote:
: I am currently attempting to implement a safe, portable
: Unchecked_Conversion of an enumerated type to integer and from an integer
: type back to the enumeration. The following code shows the current
: solution, the question raised by one engineer is can we guarantee the the
: return statement in the To_Enum function is portable. That is may a
: compiler optimize away the ENUM'Pos and ENUM'Val and effectively eliminate
: the constraint check.

I think your first portability problem is whether the ENUM will fit into an
INTEGER. My compiler manual says: "Objects of enumeration types are allocated
one word when no representation specification is given. If a specification
is given that uses values in the range of LONG_INTEGER (but outside the
range of INTEGER), objects will be allocated in double words.

Second, I could definitely see a compiler optimizing away 'Val('Pos). 'Valid
would be a better attribute here.

Third, if an enum spec is used, I'm not sure what happens if there are holes
in the underlying number sequence. The LRM says that CONSTRANT_ERROR is
raised if X'Val is not in the _range_ T'POS(T'BASE'FIRST) ..
T'POS(T'BASE'LAST). If it's in range, but not a valid representation, I
suspect different compilers might behave differently.

--------------------------------------------------------------------
Ken Garlington                  GarlingtonKE@lfwc.lockheed.com
F-22 Computer Resources         Lockheed Fort Worth Co.

If LFWC or the F-22 program has any opinions, they aren't telling me.

Re: Optimizing and Constraint Checks

[Robert Dewar]

Bruce, your code is probably wrong in many implementations, since it
involves unchecked conversion from enumeration type to type Integer,
and the types may well have different lengths. You should be sure to
do an unchecked conversion to an integer type of the same length.

Incidentally, GNAT implements an attribute 'Enum_Rep which gives the
underlying representation of an enumeration type in a more direct
manner than unchecked conversion.

Finally, for conversion of an integer to enumeration by unchecked
conversion, the attribute 'Valid should be used to ensure (in Ada 95)
that the result is a valid value of the type.

One more point: have a look at the routine Enumchek in the ACVC suite
which does related things, and is sure to work on all implementations :-)
Actually the code is not so long, I will just quote it here:

-- THIS GENERIC PROCEDURE IS INTENDED FOR USE IN CONJUNCTION WITH THE ACVC
-- CHAPTER 13 C TESTS. IT IS INSTANTIATED WITH TWO TYPES. THE FIRST IS AN
-- ENUMERATION TYPE FOR WHICH AN ENUMERATION CLAUSE HAS BEEN GIVEN, AND THE
-- SECOND IS AN INTEGER TYPE WHOSE 'SIZE IS THE SAME AS THE 'SIZE OF THIS
-- ENUMERATION TYPE.

-- THE PROCEDURE ENUM_CHECK IS THEN CALLED WITH THREE ARGUMENTS. THE FIRST IS
-- AN ENUMERATION LITERAL FROM THE ENUMERATION TYPE, THE SECOND IS AN INTEGER
-- LITERAL WHICH IS THE VALUE OF THE EXPECTED REPRESENTATION (TAKEN FROM THE
-- ENUMERATION REPRESENTATION CLAUSE), AND THE THIRD IS A STRING DESCRIBING OR
-- NAMING THE TYPE (USED IN A CALL TO FAILED IF THE REPRESENTATION CHECK FAILS).

-- THE CHECK IS TO CONVERT THE ENUMERATION VALUE TO A BOOLEAN ARRAY WITH A
-- LENGTH CORRESONDING TO THE 'SIZE OF THE ENUMERATION TYPE. AN INTEGER TYPE
-- IS THEN CREATED WITH THIS SAME 'SIZE, AND THE REQUIRED REPRESENTATION VALUE
-- IS CONVERTED FROM THIS TYPE TO A BOOLEAN ARRAY WITH THE SAME LENGTH. THE
-- TWO BOOLEAN ARRAYS ARE THEN COMPARED AND SHOULD BE EQUAL. THE CONVERSIONS
-- ARE PERFORMED USING APPROPRIATE INSTANTIATIONS OF UNCHECKED_CONVERSION.

-- AUTHOR: ROBERT B. K. DEWAR, UNCOPYRIGHTED, PUBLIC DOMAIN USE AUTHORIZED

GENERIC

   TYPE ENUM_TYPE IS PRIVATE;
   TYPE INT_TYPE IS RANGE <>;

PROCEDURE ENUM_CHECK (TEST_VALUE : ENUM_TYPE;
		      REP_VALUE  : INT_TYPE;
		      TYPE_ID	 : STRING);


WITH UNCHECKED_CONVERSION;
WITH REPORT; USE REPORT;

PROCEDURE ENUM_CHECK (TEST_VALUE : ENUM_TYPE;
		      REP_VALUE  : INT_TYPE;
		      TYPE_ID	 : STRING) IS

   TYPE BIT_ARRAY_TYPE IS ARRAY (1 .. ENUM_TYPE'SIZE) OF BOOLEAN;
   PRAGMA PACK (BIT_ARRAY_TYPE);

   FUNCTION TO_BITS IS NEW UNCHECKED_CONVERSION (ENUM_TYPE, BIT_ARRAY_TYPE);
   FUNCTION TO_BITS IS NEW UNCHECKED_CONVERSION (INT_TYPE, BIT_ARRAY_TYPE);

   BIT_ARRAY_1 : BIT_ARRAY_TYPE;
   BIT_ARRAY_2 : BIT_ARRAY_TYPE;

   INT_VALUE : INT_TYPE := INT_TYPE (REP_VALUE);

BEGIN

   -- VERIFY CORRECT CALL (THIS IS A SANITY CHECK ON THE TEST ITSELF)

   IF ENUM_TYPE'SIZE /= INT_TYPE'SIZE THEN
      FAILED ("ERROR IN ENUM_CHECK CALL: SIZES DO NOT MATCH");
   END IF;

   BIT_ARRAY_1 := TO_BITS (TEST_VALUE);
   BIT_ARRAY_2 := TO_BITS (INT_VALUE);

   IF BIT_ARRAY_1 /= BIT_ARRAY_2 THEN
      FAILED ("CHECK ON REPRESENTATION OF TYPE " & TYPE_ID & " FAILED.");
   END IF;

END ENUM_CHECK;

Re: Optimizing and Constraint Checks

[David Wheeler]

Theodore Dennison (dennison@escmail.orl.mmc.com) wrote:
: Ed Bruce <edward@igate1.hac.com> writes:

: > I am currently attempting to implement a safe, portable
: > Unchecked_Conversion of an enumerated type to integer and from an integer
: > type back to the enumeration.

: Your engineer has a vaild concern. One of the problems with Ada 83 is that 
: there is no PORTABLE way to force a constraint check. In practice, you have
: to find what your compiler won't optimize away, and code to that. 
: Unfortunately, the next version of the same compiler could work differently.

: Hopefully, this problem was fixed with Ada 95.


See the new 'Valid attribute.


--- David A. Wheeler
Net address: wheeler@ida.org

Re: Optimizing and Constraint Checks

[Robert Dewar]

Ken said

"Third, if an enum spec is used, I'm not sure what happens if there are holes
in the underlying number sequence. The LRM says that CONSTRANT_ERROR is
raised if X'Val is not in the _range_ T'POS(T'BASE'FIRST) ..
T'POS(T'BASE'LAST). If it's in range, but not a valid representation, I
suspect different compilers might behave differently."

Wait a moment! In the absence of an numeration rep clause, this whole
discussion is irrelevant. If you don't have a rep clause, you just use
Pos and Val to go backwards andd forwards and the whole apparatus of
the generic is junk!

Re: Optimizing and Constraint Checks

[Garlington KE]

Robert Dewar (dewar@cs.nyu.edu) wrote:
: Wait a moment! In the absence of an numeration rep clause, this whole
: discussion is irrelevant. If you don't have a rep clause, you just use
: Pos and Val to go backwards andd forwards and the whole apparatus of
: the generic is junk!

Yes, I'm assuming it's supposed to support both cases (with and without a
rep clause).

There is one other obscure possibility that can hang this code as well,
even in the absense of a rep spec. A strange compiler could align enum
values in a storage unit differently than for integers. I've never seen
this in practice for enums, although it happens a lot for packed arrays
of BOOLEAN. If the compiler doesn't shift the value on an UNCHECKED_
CONVERSION (which, according to an AI, it's supposed to, although some
don't), then your results are trashed.

--
--------------------------------------------------------------------
Ken Garlington                  GarlingtonKE@lfwc.lockheed.com
F-22 Computer Resources         Lockheed Fort Worth Co.

If LFWC or the F-22 program has any opinions, they aren't telling me.

Re: Optimizing and Constraint Checks

[Ed Bruce]

In article <3kuhpo$ban@theopolis.orl.mmc.com>, Theodore Dennison
<dennison@escmail.orl.mmc.com> wrote:


> Your engineer has a vaild concern. One of the problems with Ada 83 is that 
> there is no PORTABLE way to force a constraint check. In practice, you have
> to find what your compiler won't optimize away, and code to that. 
> Unfortunately, the next version of the same compiler could work differently.
> 

I have suggested that we use 'IMAGE and 'VALUE with enumeration types that
are stored in the database. First I believe this to be more portable and
likely to guarantee constraint checking will be performed in all validated
compilers. Second it is more likely to catch illegal values in the
database when we change enumeration_literals and fail to update the
database correctly(maintenace issue).

Your last sentence is the crux of the problem. Change vs. stability.
Today's solution is tomorrow's problem.

-- 
Ed Bruce
edward@igate1.hac.com

Re: Optimizing and Constraint Checks

[Ed Bruce]

In article <3l3l2v$ria@gnat.cs.nyu.edu>, dewar@cs.nyu.edu (Robert Dewar) wrote:

> 
> Wait a moment! In the absence of an numeration rep clause, this whole
> discussion is irrelevant. If you don't have a rep clause, you just use
> Pos and Val to go backwards andd forwards and the whole apparatus of
> the generic is junk!

I realize now I should have provided more background and also debugged my
code before posting. I rushed this one out.

The underlining problem is how to represent enumeration types in an
external database(that is one not implemented directly in Ada). The
current solution is to use 'POS and 'VAL. The problem is our code is in a
very dynamic state and our enumerated types have and will continue to
change. Since 'POS and 'VAL for any given enumeration_literal for an
enumeration_type_definition may change as enumeration_literal's are added
or deleted from the enumeration_type_definition our database maintainer
has to modify the database to reflect these changes manually.

Which leads to an increased risk of making a mistake that won't be caught
easily if at all. That is if the an enumerated_value'POS is currently 5 in
the database and should be changed to 4 (a literal was deleted), but is
changed to 3. Well enumeration_type'VAL(3) is this case is legal but
invalid.

So I have suggested to the principal engineers on our project that we use
enumeration representation clauses and unchecked type conversion. This way
we are not dependant on the ordering of the enumeration_literal's. The
problem is ARM 13.10.2(3): "...it is the programmer's responsibility to
ensure that these conversions maintain the properties that are guaranteed
by the language for objects of the target type." My question was, is there
a portable way to do this and the answer I am getting is no for Ada, and
yes/maybe for Ada-95. 

Haing received these answers I have also proposed we look at using 'IMAGE
and 'VALUE instead and as expected I am receiving grumblings about sizing
and performance issues. Luckily all I have to do is propose solutions and
trade offs. The higher ups must balance cost, performance, and
maintainability and decide which solution is best.

-- 
Ed Bruce
edward@igate1.hac.com

Re: Optimizing and Constraint Checks

[Garlington KE]

Ed Bruce (edward@igate1.hac.com) wrote:
: The underlining problem is how to represent enumeration types in an
: external database(that is one not implemented directly in Ada).

Without thinking about it very hard, my first impulse is to use a cross-
reference table of the Ada enumeration type values and the values used
in the database, and then bury this table in an appropriate encapsulation.
This way, you should be able to represent the enumeration values as strings,
or numbers, or whatever in the database. If the enumeration type changes,
and you code the aggregate for the cross-reference table properly, you
should be able to control changes fairly well.

I'm not exactly sure what you want done if an enueration value is replaced;
for example, if the third value changes from BLUE to YELLOW. You may want
to encode a version number somewhere in the database and in the encapsulation,
and have it check on elaboration (or some appropriate point).

This should work in Ada-anything.

--------------------------------------------------------------------
Ken Garlington                  GarlingtonKE@lfwc.lockheed.com
F-22 Computer Resources         Lockheed Fort Worth Co.

If LFWC or the F-22 program has any opinions, they aren't telling me.

Re: Optimizing and Constraint Checks

[Mike Meier]

Ed Bruce (edward@igate1.hac.com) wrote:

: Which leads to an increased risk of making a mistake that won't be caught
: easily if at all. That is if the an enumerated_value'POS is currently 5 in
: the database and should be changed to 4 (a literal was deleted), but is
: changed to 3. Well enumeration_type'VAL(3) is this case is legal but
: invalid.

: So I have suggested to the principal engineers on our project that we use
: enumeration representation clauses and unchecked type conversion.

We faced the same problems on our rather large (1M SLOC) project with lots
of enumerated types in the DB.  It turns out that even rep clauses
and unchecked type conversions have potential for maintainability and
portability problems.  Our solution was to require the definition and use
of a set of mapping functions (for which we provided a generic) for every
enumerated type to be stored in the DB.  This may seem like overkill, but
it saved significant effort overall the (so far) 5-year life of the
project.  Additional benefits were that the values used in the DB could
be used in many other contexts, and that the values could be defined in
the body rather than the spec (which reduced recompilation when a value
had to be changed).

Re: Optimizing and Constraint Checks

[Robert Dewar]

Obviously if you want to write enumeration values out to a database and
read them into a completely different enumeration type where the only
guarantee is that the names correspond, then there is no choice but
to use 'Image and 'Value.

Grumbling about efficiency is irrelevant, if you have stated the problem
in such a way that it is tautalogically obvious that 'Image and 'Value is
the only possible approach, then you can't discuss whether this is an
acceptable solution!