Version 1.1 of ai05s/ai05-0212-1.txt

!standard A.18.2(9/2) 10-04-26 AI05-0212-1/01
!class Amendment 10-04-26
!status work item 10-04-26
!status received 10-02-27
!priority Medium
!difficulty Medium
!subject Accessors and Iterators for Ada.Containers

We've defined a number of new features that potentially can improve the use of the containers libraries in AI05-0139-2, AI05-0142-4, AI05-0143-1, and AI05-0162-1. The containers ought to be updated to use these new features.

Add accessors and iterators to the containers packages.

[Editor's note: The following does not yet use most of the AI05-0139-2 features. Version /04 only contains a rough proposal, and alomst nothing for the form of the accessors magic.]

Add the following to each Ada.Containers package immediately after Update_Element (with suitable substitutions for the names of types).

type Constant_Reference_Type (Element : not null access constant Element_Type) is limited new Ada.Reference.References with private;

type Reference_Type (Element : not null access Element_Type) is limited new Ada.Reference.References with private;

Constant_Reference_Type and Reference_Type need finalization.

The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.

AARM Reason: It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.

If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.

[Editor's note: We want to say something about the accessor capability here, not sure what exactly.]

If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.

The element designated by Position is not an empty element after successful completion of this operation. [This is only needed for the Vectors case. - ED]

Add the following to Ada.Containers.Vectors and its relatives.

If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.

If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.

The element designated by Position is not an empty element after successful completion of this operation.

Add the following to the Erroneous Execution section of each container package:

Execution is erroneous if the vector associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.

AARM Reason: Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a non-existent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)

Note that the accessibility of the returned object from a call to Reference will prevent converting the returned access discriminant to any type that lives longer than the returned object. That means that we can assume that the discriminant value cannot be accessed after the object disappears (thus we can tie the tampering check to the lifetime of the returned object).

It is possible to use Unchecked_Deallocation to destroy the returned Reference_Type object prematurely, while continuing to use the returned access. The accessibility check on the container argument to the Reference function means that the returned access can't live longer than the container, but the use of Unchecked_Deallocation would allow tampering on the container. This could look like:

declare type AR is access MV.Reference_Type; procedure Free is new Ada.Unchecked_Deallocation (MV.Reference_Type, AR);

Obviously, this is highly unlikely to happen by accident. This is more like shooting oneself in the foot by attaching a laser target to your foot and then firing a laser-seeking missile. It doesn't seem worth worrying about someone who wants to go to these lengths to avoid a tampering check - they're just as likely to use Unchecked_Conversion or .all'Unchecked_Access or something else nasty.

We need to be able to define the period of existence of the return object of the accessor as a time when tampering with elements is prohibited. If we didn't do this, we would be opening the door to all manner of problems (up to and including erroneousness) if an element is added or deleted to the container.

To see how this could happen, consider the following example:

Assume that Ada.Containers.Vectors has an accessor function defined as follows:

Now consider the following program fragments:

package Data is type Node (D : Boolean := True) is record case D is when True => CT : Natural; when False => CF : Float; end case; end record; subtype True_Node is Node (D => True); subtype False_Node is Node (D => False);

package body Far_Away is procedure Some_Complex_Operation (...) is Some_Index : Positive; begin ... Some_Index := <lengthy-computation-resulting-in-value-of-1>; ... Data.Node_List.Delete (Some_Index); ... end Some_Complex_Operation; end Far_Away;

with Far_Away; package body Process is procedure Process_True (NT : in out Data.True_Node) is Component : renames NT.CT; -- OK, NT is constrained. begin ... Far_Away.Some_Complex_Operation (...); if Component > 10 then -- ** Oh-oh!! Component has moved. ... end if; end Process_True; end Process;

with Data, Process; procedure Main is begin Data.Node_List.Append (New_Item => (D => False, CF => 1.0)); -- Element 1. Data.Node_List.Append (New_Item => (D => True, CT => 4)); -- Element 2. Data.Node_List.Append (New_Item => (D => False, CF => 26.5)); -- Element 3. ... Process.Process_True (Data.Node_List.Reference (2).all); ... end Main;

In the canonical implementation for a vector, all of the data is stored in an array of some size, and when a component is deleted, the rest of them slide down. So, when the Far_Away operation (probably called through many levels of calls) deletes the first element of the vector, all of the rest of them move. That means that the second element passed to Process_True unexpectedly changes its value to that which was in the third element. But that element doesn't match the constraint and doesn't even have a CT component! So we get erroneous behavior. Note that the same thing would happen if an element was inserted at the front of the vector.

Note that in this example no one has copied the access value returned by the accessor. So a rule preventing copying does no good. You can also get a similar effect by renaming the access value itself and doing bad things while the renames exists.

Note that the erroneousness can't happen if you use Update_Element instead, because the tampering check will cause the deletion to raise Program_Error. Similarly, cursors have rules allowing implementations to detect this sliding and raise Program_Error.

This example code seems plausible; the record type is similar to many found in the author's compiler and using a library-level container is not unusual. So it seems reasonable that cases like this would happen in practice. Thus we conclude that a tampering check is needed for the accessor functions.

The new Reference function could be used (based on a recent example from comp.lang.ada):

with Ada.Containers.Vectors; procedure Check is package Integer_Vectors is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Integer);

package Nested_Vectors is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Integer_Vectors.Vector, "=" => Integer_Vectors."=");

IV : Integer_Vectors.Vector; NV : Nested_Vectors.Vector; begin IV.Append(42); NV.Append(IV); NV.Reference(0).Element.Append(43); end Check;

The dereference does not need to be explicitly given in this case, and the fact that the object returned by Reference is limited and (probably) controlled is not visible in the code as the function call is used directly as a prefix.

You could also save the entire object as long as needed:

(since My_NV would be built-in-place).

Note that this design still works as intended even if the user renames only the discriminant access value:

Even in this case, the wrapping (probably controlled) object still is protecting the container, because the master of the returned object is the master of the renames: it will stick around as long as the renames does.

Moreover, splitting the access from the object usually isn't possible:

This is illegal because the accessibility check fails. The (anonymous) object returned here will have the master of the expression (as a prefix, the special "directly initializing" rule does not apply to this function call), which is shorter than the master of the declaration of My_IV. Thus the accessibility check preventing shorter lifetimes will fail.