AI22-0100-2
!standard 3.6.1(8) 24-08-03 AI22-0100-2/04
!standard 4.2(10/5)
!standard 4.2(11/5)
!standard 4.3.3(26)
!standard 4.3.3(26.2/5)
!standard 4.5.3(8)
!status Amendment 1-2022 24-05-02
!status WG9 Approved 24-10-10
!status ARG Approved 14-0-0 24-05-02
!class binding interpretation 24-04-05
!status work item 24-04-05
!status received 24-04-05
!submitter Stephen Baird
!priority Low
!difficulty Medium
!qualifier Omission
!subject Upper bound calculation
When calculating the upper bound of some array object from the lower bound and a given length, the position number of the lower bound is added to the length minus one, and the result value is that with the calculated position number. If there is no such value, Constraint_Error is raised.
This calculation is used for calculating the upper bounds of a null_array_aggregate, a positional_array_aggregate with no others choice, a named_array_aggregate made up solely of iterators, and the result of a concatenation operator.
There is a check defined for a null string literal that the bounds make sense (see 4.2(11/5)). This is needed when the lower bound is Index_Subtype'Base'First. It would seem that a similar check is needed for a null_array_aggregate, but none is defined. Additionally, the upper bound of a null string literal is defined explicitly. The duplication of the rules is uncomfortable.
This introduces a more general problem. There is no rule anywhere that explains what happens when the upper bound of a positional_array_aggregate is not representable in the index type. A related problem is that the upper bound might not make sense for a modular type, which has wrapping semantics. Should we add rules? (Yes.)
This is a more general issue than just positional_array_aggregates. A similar calculation is used for various other aggregates. Additionally, the result of a concatenation operator also uses a similar calculation.
Thus, we define the method of such a calculation, and then refer to it from each of the uses.
Add after 3.6.1(8):
When the upper bound is calculated from the lower bound and another value representing the
length of an array, the following steps are performed:
[Editor's Notes: The last step here is essentially the same wording as is used for the S'Val attribute. I used a numbered list as the text had become lengthy and hard to follow. I used numbers rather than bullets since this is a series of steps (not a list of alternatives).
An alternative to "calculated" here is to use "determined". "Determined" is the existing wording, we just need to define specifically how that works. So we would have to make fewer wording changes if we did that (but we still need the new cross-references to this definition). I didn't use "determined" since it didn't seem to me like a term that would be defined, although there are already a couple of phrases starting with "determined" that are defined terms. End Editor’s notes.]
AARM Reason: We use position numbers as they are calculated as universal_integers, and thus have a theoretical unlimited range. For a static lower bound and length, the calculation should be exact. Using position numbers avoids problems that would be caused by using the index type for these calculations (no addition operation for enumeration types, and wrapping addition for modular types).
AARM Implementation Note: 4.4 allows using type root_integer to evaluate universal_integer expressions that have to be evaluated at runtime. So long as overflow is detected, that is sufficient for almost all standard discrete types (overflow corresponding to cases where the value is not representable as a value of the index type). (But be careful, the subtract of 1 has to be done to the length, not the lower bound, lest an incorrect overflow happen if the lower bound is the first value of the base type.) For the largest modular type (that with a modulus of System.Max_Binary_Modulus), however, some of the position numbers are not representable as root_integer. For that type, it is preferable to use unsigned arithmetic that detects overflow when runtime evaluation is required. (On typical machines, that means testing the carry flag rather than the overflow flag after arithmetic operations.)
[Editor's notes: I didn't mention non-standard integer types that are allowed for array indexing, as they are, well, non-standard. As such, anything could be allowed (or not allowed). That makes saying anything interesting difficult.
Also, I didn't try to specify whether such unsigned arithmetic is required, or whether the rules of 4.4 are enough. 4.4 certainly allows doing better if the implementation wants to do so. Cases where the lower bound and length are not static and Root_Integer cannot be used are quite unusual (mostly contrived), and thus it didn't seem worth it to mandate that they work. See !discussion for more on this point. End Editor’s notes.]
Modify 4.2(10/5):
The evaluation of a string_literal that is a primary and has an expected type that is a string type, yields an array value containing the value of each character of the sequence of characters of the string_literal, as defined in 2.6. The bounds of this array value are determined according to the rules for positional_array_aggregates {without an others choice} (see 4.3.3)[, except that for a null string literal, the upper bound is the predecessor of the lower bound]. In other cases, the effect of evaluating a string_literal is determined by the String_Literal aspect that applies (see 4.2.1).
[Editor's note: I added "without an others choice" to the above, since the rules for positional_array_aggregates with an others choice are very different. We need to be clear which we mean.]
{AARM Ramification: Determining the bounds of a string_literal includes the checks on the computed bounds themselves (such as checking that the determined range is compatible with the appropriate index subtype).}
Modify 4.2(11/5):
For the evaluation of a string_literal of a string type T, a check is made that the value of each character of the string_literal belongs to the component subtype of T. [For the evaluation of a null string literal of a string type, a check is made that its lower bound is greater than the lower bound of the base range of the index type.] The exception Constraint_Error is raised if {this check}[either of these checks] fails.
Modify 4.3.3(26):
{AARM Ramification: Calculating the upper bound includes raising Constraint_Error if the value computed is not a value of the index type.}
Modify 4.3.3(26.2/5):
[Editor's note: Since AI22-0006-1 requires the total number of values for both sets of iterations to be the same, it isn't necessary to specify which set is used to calculate the bounds. It's better to leave the choice up to the implementation (it's likely that the bounds are set when the memory for the temporary is allocated), thus I deleted the word "second".]
Modify 4.5.3(8):
The upper bound is {calculated (see 3.6.1) from}[determined by] the lower bound and the length. A check is made that the upper bound of the result of the concatenation belongs to the range of the index subtype, unless the result is a null array. Constraint_Error is raised if this check fails.
[Editor’s note: The first sentence above is marked as Redundant in the current RM; that marking should be removed as it is the only definition of how the upper bound is calculated. I’d argue that it never was Redundant, but it certainly isn’t now.]
{AARM Ramification: Calculating the upper bound includes raising Constraint_Error if the value computed is not a value of the index type.}
For cases already handled by the wording and/or tested by the ACATS, no semantic change is intended. This proposal is intended to clarify the handling of corner cases, and define some missing ones.
Until the introduction of the null_array_aggregate in Ada 2022, it was not possible for an array aggregate to have no elements unless the bounds were determined elsewhere (either from an applicable index constraint for an aggregate containing only an others choice, or from explicit bounds in a named_array_aggregate). Thus the case of the upper bound not being representable because the lower bound is the smallest possible value could only occur for a string literal, and the rules for dealing with that case were placed there.
With the introduction of the null_array_aggregate, it makes more sense to put all of the rules with null_array_aggregates and associate null string literals with those rules.
But we can do better still. With the position number formulation, we now have enhanced the definition of the positional_array_aggregate without others choice case so that it works for any length (including zero). (In particular, any case where the calculated position number does not represent a value of the index type is now well-defined.) That wasn’t the case before Ada 2022, so we needed a special case for null string literals. But we no longer need such a case.
We still need a special rule for null_array_aggregates, as those can represent a multidimensional array. But for any single dimension, it just refers to the positional_array_aggregate without others choice case. It is best to cut out the middleman here.
The ACVC tested (for Ada 83) cases of aggregates with unrepresentable upper bounds extensively, as part of the checks associated with what is now paragraph 28 (the range compatibility check). This can easily be justified for integer types, as the underlying range of integers is considered infinite, and implementations are expected to detect when those are not representable (after all, that's what an overflow check is, and that is how the overflow check is defined).
It's harder to justify this for enumeration types. One can imagine that this check is actually on the position numbers associated with the enumeration, and then one can apply the explanation associated with integers. But that is a stretch, enumeration types are primarily defined by their literals and the operations provided.
The problem here is that we do not describe how the upper bound is determined other than by handwaving. It is better to explicitly describe how that is done.
By using position numbers rather than trying to calculate the bounds using the index type, we avoid a number of problems.
First, there is no addition operation for enumeration types. We could use iteration on the 'Succ attribute as a replacement (indeed, we tried that in an alternative of this AI - AI22-0100-1), but that is rather unusual. At least 'Succ detects the case of not having a value. We also have to use 'Pred for the null_array_aggregate case, meaning we need additional wording.
Second, addition for modular types wraps around rather than overflows. This means that the upper bound does not go out of range, but rather the bounds and length are inconsistent. That needs to be detected somehow.
To see this problem, consider the following declarations:
type Small is mod 8;
type Small_Array is (Small range <>) of Integer;
Null_Array : Small_Array := [];
Big_Array : Small_Array := [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
For the null_array_aggregate initializing Null_Array, the determined lower bound is 0. If we add zero (the length) minus one to the lower bound of 0, we get 7 (since the type wraps around). This gives bounds of 0 .. 7, which represents a length of 8. Of course, the length of a null_array_aggregate is 0, so we have a mismatch and that cannot be allowed.
Similarly, for the positional_array_aggregate initializing Big_Array, the determined lower bound is also 0. If we add ten (the length) minus one to the lower bound, we get an upper bound of 1. That of course represents a range of 0 .. 1, with a represented length of 2; since the aggregate has ten elements, we again have a mismatch and that still cannot be allowed.
Note that in both of these cases, the resulting bounds are compatible with the index subtype. So that check does not (always) help us in this situation; we need a specific check.
Using position numbers avoids these problems as they use the operations of universal_integer. That is a type that is unlimited and thus never wraps around. For static calculation, the results are calculated exactly
However, there is a problem if the lower bound is not known statically. When a universal integer value is evaluated at runtime, root_integer math and rules are used. This means that not all of the position numbers associated with modular types are required to be representable (root_integer is signed, while the largest modular type is unsigned); Constraint_Error could be raised for correct aggregates.
To see how this could happen, consider:
type Largest_Modular is mod System.Max_Binary_Modulus;
function Dyn (A : Largest_Modular) return (A); -- Force to non-static.
subtype Big_Range is Largest_Modular range
Dyn(Largest_Modular'Last-2) .. Dyn(Largest_Modular'Last-1);
type Mod_Array is (Big_Range range <>) of Integer;
OK_Array : Mod_Array := [1, 2];
Bad_Array : Mod_Array := [1, 2, 3];
The position numbers of Big_Range are most likely outside of the range of Root_Integer. The combination of 4.4(10.1/5) and 4.4(11) says that such evaluation can raise Constraint_Error. Thus, if we use position numbers to determine the bounds of array aggregates, any positional aggregate of type Mod_Array could raise Constraint_Error. That includes OK_Array in this example.
Such cases are unusual enough that we don't attempt to ensure that they will work, but we do have an Implementation Note suggesting that this problem can be avoided by using an unsigned representation for the position number calculation (so long as operations on that representation check for overflow). 4.4(11) always allows getting the correct answer rather than raising Constraint_Error, and that can be done in this case using unsigned representations.
Concatenation operations also have to calculate the upper bound from a length, and thus also have the same possible problems. (Imagine concatenating two arrays for type Small_Array above to get something longer than 8 elements, similarly for an enumeration type.) We've included updating the rules for the calculation of the upper bound of a concatenation in this AI.
(See Discussion.)
@dinsa
The elaboration of an @fa{index_constraint} consists of the evaluation of the @fa{discrete_range}(s), in an arbitrary order. The evaluation of a @fa{discrete_range} consists of the elaboration of the @fa{subtype_indication} or the evaluation of the @fa{range}.
@dinss
When the @i{upper bound is calculated} from the lower bound and another value representing the length of an array, the following steps are performed:
@xhang{@xterms{1.}determine the position number of the lower bound, giving position number @i{L};}
@xhang{@xterms{2.}add one less than the length value to @i{L}, giving the position number @i{U}; then}
@xhang{@xterms{3.}the value of the index type whose position number is @i{U} is the value of the upper bound; if there is no value of the index type whose position number is @i{U}, Constraint_Error is raised.}
@drepl
The evaluation of a @fa{string_literal} that is a @fa{primary} and has an expected type that is a string type, yields an array value containing the value of each character of the sequence of characters of the @fa{string_literal}, as defined in @ref{2.6}. The bounds of this array value are determined according to the rules for @fa{positional_array_aggregate}s (see @ref{4.3.3}), except that for a null string literal, the upper bound is the predecessor of the lower bound. In other cases, the effect of evaluating a @fa{string_literal} is determined by the String_Literal aspect that applies (see @ref{4.2.1}).
@dby
The evaluation of a @fa{string_literal} that is a @fa{primary} and has an expected type that is a string type, yields an array value containing the value of each character of the sequence of characters of the @fa{string_literal}, as defined in @ref{2.6}. The bounds of this array value are determined according to the rules for @fa{positional_array_aggregate}s without an @b{others} choice (see @ref{4.3.3}). In other cases, the effect of evaluating a @fa{string_literal} is determined by the String_Literal aspect that applies (see @ref{4.2.1}).
@drepl
For the evaluation of a @fa{string_literal} of a string type @i{T}, a check is made that the value of each character of the @fa{string_literal} belongs to the component subtype of @i{T}. For the evaluation of a null string literal of a string type, a check is made that its lower bound is greater than the lower bound of the base range of the index type. The exception Constraint_Error is raised if either of these checks fails.
@dby
For the evaluation of a @fa{string_literal} of a string type @i{T}, a check is made that the value of each character of the @fa{string_literal} belongs to the component subtype of @i{T}. The exception Constraint_Error is raised if this check fails.
@drepl
@xbullet{For a @fa{positional_array_aggregate} (or equivalent @fa{string_literal}) without an @b{others} choice, the lower bound is that of the corresponding index range in the applicable index constraint, if defined, or that of the corresponding index subtype, if not; in either case, the upper bound is determined from the lower bound and the number of @fa{expression}s (or the length of the @fa{string_literal});}
@dby
@xbullet{For a @fa{positional_array_aggregate} (or equivalent @fa{string_literal}) without an @b{others} choice, the lower bound is that of the corresponding index range in the applicable index constraint, if defined, or that of the corresponding index subtype, if not; in either case, the upper bound is calculated (see @ref{3.6.1}) from the lower bound and the number of @fa{expression}s (or the length of the @fa{string_literal});}
@drepl
@xbullet{For a @fa{named_array_aggregate} containing only @fa{iterated_component_association}s with an @fa{iterator_specification}, the lower bound is determined as for a @fa{positional_array_aggregate} without an @b{others} choice, and the upper bound is determined from the lower bound and the total number of values produced by the second set of iterations;}
@dby
@xbullet{For a @fa{named_array_aggregate} containing only @fa{iterated_component_association}s with an @fa{iterator_specification}, the lower bound is determined as for a @fa{positional_array_aggregate} without an @b{others} choice, and the upper bound is calculated (see @ref{3.6.1}) from the lower bound and the total number of values produced by the set of iterations;}
@drepl
The upper bound is determined by the lower bound and the length. A check is made that the upper bound of the result of the concatenation belongs to the range of the index subtype, unless the result is a null array. Constraint_Error is raised if this check fails.
@dby
The upper bound is calculated (see @ref{3.6.1}) from the lower bound and the length. A check is made that the upper bound of the result of the concatenation belongs to the range of the index subtype, unless the result is a null array. Constraint_Error is raised if this check fails.
For positional_array_aggregates without an others choice, ACATS C-Tests exist that check an unrepresentable upper bound for integer and enumeration index types (from the ACVC in the mid-1980's; existing compilers clearly get that right). Modular type examples of those tests should be constructed.
For string_literals, one could construct C-Tests like those for positional_array_aggregates, but declaring string types with enumeration or modular index types is very unusual. So only cases involving string types with signed integer bounds are candidates for new tests.
For null_array_aggregates, C-Tests are needed to test the cases (including the modular cases) tested for positional_array_aggregates without an others choice.
For named_array_aggregates solely consisting of iterators, C-Tests are needed to test some of the cases of unrepresentable upper bounds. These are lower priority than the other cases, since the relatively unusual declarations are unlikely to be combined with an iterator in an aggregate (which is also unlikely).
For concatenation operators, C-Tests are needed to test all of the cases of unrepresentable upper bounds.
This AI arose from a private question submitted to the Editor by Steve Baird.