Version 1.1 of ai12s/ai12-0240-2.txt

!standard 3.10.3(0) 18-06-14 AI12-0240-2/01
!class Amendment 18-06-14
!status work item 18-06-14
!status received 18-06-14
!priority Low
!difficulty Hard
!subject Access ownership for Abstract Data Types

A new kind of access type, the owing access type, is defined, which allows a more limited form of Global aspect for subprograms in which it is used.

Assuming that we have static tasking checks (AI12-0267-1), it is important that the Global aspects of abstract data types (ADTs) have as little conflicts as possible. In particular, the Global aspects of the containers need to have a very minimum use of global objects; otherwise, they could not be used in parallel blocks and loops when the static checks are on.

Many ADTs (including the normal unbounded containers and the indefinite containers) internally use access types and allocated data. This is necessary to provide memory efficiency and unbounded behavior -- statically sized structures necessarily have a defined bound and have to use the memory needed for the largest possible object.

Moreover, well-defined ADTs hide the implementation from the clients. Thus, the types of allocated objects are unknown to clients.

In normal use, allocated objects for a pool-specific type are considered to belong to the pool that they are allocated from; this typically is a shared global object. General access objects can be part of an associated pool or indeed any object in the entire program that has the correct type. In an ADT where the allocated type is not visible to the client, the only choice often is "in out all".

However, such objects are typically allocated so they belong to a single ADT object. If we could communicate this ownership to the compiler, the objects could be considered to belong to a particular object (typically a parameter to a subprogram, not subject to Global checks) rather than the storage pool that they were allocated from.

Add "owned access types" to the language. We define the rules for such access types so that an owned access value can belong to at most one object at a time. (As a side-effect, if the value belongs to no object, it can be automatically reclaimed.)

We allow "unsafe" owned access types, which are unmanaged copies of owned access types. They provide no ownership effects of their own; indeed it is considered erroreous to dereference such an access value if not directly in the scope of the appropriate owner.

Detailed outline of the proposal.

3.10.3 Owned Access Types

[Author's notes: This is pseudo-wording: some of it is in the style of Ada wording, and some is not.

We have this in the core, as it will be needed to support Global contracts and language defined containers so that they can pass the core checks for data races in parallel statements - see AI12-0267-1.]

There is a new kind of access type, the owning access type.

The Owning access type is declared by the following aspect:

The subtype_marks specified by the Primary_Owners define the *primary owner types*; the other subtype_marks (if any) define *secondary owner types*. These are collectively called owner types. These subtype_marks shall be first subtypes.

AARM Discussion: The primary owner types are typically a public ADT, and the secondary owner are (private) nodes of the data structure. For instance, consider a list container: there is a header structure which is used as the container itself, and individual nodes that make up the chain of elements.

AARM Reason: This allows multiple node types, as would be needed to implement an indefinite list or map container. We allow multiple Primary_Owners so that multiple types can share node types if needed.

An owning access type shall be:

* the primary owner type and any secondary owner types shall have their (full) declaration in the same declaration list as the owned access type;

[Author's note: These restrictions imply that these types are either private or completely hidden; they're only usable within the subsystem. It's not clear whether the private restriction actually helps, because of the possibility of child units that can see all of the declarations. Similarly, requiring the types in the same declaration list may not be necessary; in any case, it's easier to relax restrictions than to have too few. And these restrictions correspond to the typical organization of an ADT.]

No type shall be derived from an owing access type, or any owner type. An owing access type shall only match a formal access type which is itself an owning access type.

[Author's note: The owner type part is mainly to keep my head from exploding trying to figure out the owner relationships in such cases. Most likely, it will need to be removed at some point.

The restriction on the owning access type is to eliminate complications caused by having multiple access types in these rules. There's no value to such types (they also have to be owning types with the same pool, and with the same restrictions).]

An object designated by by an owning access type is a *designated owned object* (or *owned object* for short).

Access objects of an owned access type can be of of various kinds:

* Owner objects are the primary access to the designated owned objects; they also control the lifetime of those objects;

* Reference objects are copies that also designated the owned objects; they have no effect on the lifetime of the owned object and have no protection against becoming dangling.

[Author's note: AI12-0240-1 has two additional kinds of access objects, the borrower and the observer; it may make sense to add them here to allow additional kinds of checked access usages. A borrower is similar to a compile-time tampering check, an observer is a short-term use of an object -- in both cases, the object can't disappear while they exist. We don't need these to implement containers. We have some pieces of their definitions below.]

The kind of an access object is defined with an aspect when the access object is declared (this includes components, stand-alone objects, parameters, etc.).

For an access object that is of an owing access type, or for a subtype of an owning access type, the following aspects are defined:

[Author's note: The short-hands are defined to keep object and component declarations from getting too wordy. Similarly, we allow defining subtypes so that common uses (mainly references) don't have to be repeated everywhere. My personal preference would be that Borrowers and Owners in particular are always explicitly declared on the object -- there should be very few of these. There might be more References and Observers.]

If the Owning_Kind for an object is Owner, the object shall be a component of the primary owner type or a secondary owner type, or be a stand-alone object.

For a parameter or generic formal of a owning access type, the actual object shall have the same kind.

[Other rules for Borrower and Observer go here.]

[Author's note: There are no other restrictions on Reference objects than the ones on all objects of owing access types. OTOH, there's no safety, either: they have even more possible cases of erroneous execution than regular access types.]

An owner access object is always the only owner of the owned object; it is never the case that more than one owner designates a single owned object.

For an assignment whose target is (directly) an owned access object, the source expression shall be only an allocator, another owned access variable (not a constant), or the literal null.

AARM Ramification: Other kinds of access objects for a owing access types cannot be assigned into an owned access object.

Assigning a new value to an owned access object first deallocates the existing designated object (if any). If the new value comes from some other owned access object, that object is set to null.

A deallocator shall be only passed an owned access object.

Inside of a subprogram with one or more parameters of the primary owner type, the accessibility of an owned access value (including when stored in a reference access object) is that of the parameter (as adjusted for "aliased" parameters). Otherwise, the accessibility level is infinite.

AARM Reason: This allows converting one of these access values to an anonymous access type when inside such a subprogram; otherwise, all conversions to other types are banned. This allows creating the anonymous access discriminant of a generalized reference.

AARM Ramification: Except as allowed above, an owning access type cannot be converted to any other access type. This is regardless of the kind of the access object involved.

If an owner type is controlled, after the call to Adjust a check is made that the owned access component is different in the target object than in the original source object. Program_Error is raised if this check fails.

AARM Reason: We want all copies of owner objects to be deep copies (or illegal, if the type is limited). This check is a simple way to ensure that Adjust does a deep copy.

The finalization of an owner access object deallocates the designated owned object, if any.

AARM Ramification: This can only happen for stand-alone (local) objects and as part of Unchecked_Deallocation of an owner type.

An owned access value V might belong to an object X if:

* the designated type of the type of V is a secondary owner type of a type D which has an primary owner type which is the type of X;

AARM Reason: This allows multiple secondary owner types, as might be needed to represent different parts of a data structure.

An owned access value V belongs to an object X if:

In a subprogram with one or more parameters P of the primary owner type, execution is erroneous if a reference access object is dereferenced that does not belong to one of the parameters P.

[Author's note: This rule is annoying, but there is no static way to check it. Luckily, for the containers, such uses of a cursor are already erroneous (the cursor is "invalid"). Moreover, the preconditions for the containers checks this property on cursors, so it will always be detected so long as the owner of a node is not changed (Move/Splice is not used).]

Notwithstanding what is said elsewhere, a dereference of an owned access value V (regardless of the kind of object it comes from) is considered covered by the Global contract needed to cover any object X that V might belong to.

AARM Reason: This allows a more restrictive contract than that which normally could be used -- in particular, this rule means that the storage pool of the owning access type is not considered.

AARM Discussion: If X is a parameter, then "Global => null" (that is, anything) is considered to cover the dereference; if X is some global object, then the contract needed to cover X is sufficient to cover the dereference.

No wording yet. See the detailed outline above.

This proposal shares several features with the "access value ownership and parameter aliasing" proposal. The aims of this proposal are much more limited than that proposal, since we are only trying to make it possible to build task-safe ADTs using allocated objects. In particular, we are not trying to prevent dangling references or allow general use of owned access values. Some of those capabilities could be added to this proposal, but at the cost of substantial additional complication.

Note in particular that the design of the Ada.Containers packages require the possible creation of dangling pointers (inside of cursors). If we tried to eliminate all dangling cursors, we would have to put usage restrictions on cursors which would be highly incompatible with existing usages of the containers.

The Ada.Containers always include an access to the container in each cursor, so it is possible to check that the cursor belongs to the "current" container. Indeed, this check is mandated by all container operations, so erroneous dereference of an unsafe owned access value is essentially impossible unless the owner is changed to a different container object (only a few operations allow that). This latter case is already erroneous by the container rules. Thus, the new possibility of erroneous execution does not change the possibilities of erroneous execution for containers.

One goal of this proposal that is explicitly different than the AI12-0240-1 proposal is that we make an effort here to never have these rules have any consequence to the client of a package. In particular, the semantics of types that contain owned objects is identical to similar declarations that don't include owned objects. We never allow ownership semantics to "leak" out of the package, nor do we require declaration of ownership outside of the ADT.

To allow container operations to use "Global => in out null" (assuming an element type that is "Global => in out null"), we need at a minimum for allocated nodes:

Nodes need to be owned by a particular container, the one being operated on.

Nodes need to be able to moved from one container to another. In particular Vector.Move and List.Splice are operations that explicitly change the owner of nodes. Implicitly, we also want to be able to reuse nodes, which can be accomplished by having a global "free" list container, and then using Splice inside of Delete to move the deleted nodes to "free", Insert also using Splice to get nodes from "free". I don't think that eliminating Move and Splice would be a good idea (that would be at a minimum performance incompatible).

We need to be able to convert owned access values (or something contained in them) into an access discriminant to implement Reference/Constant_Reference.

We need to be able to have unchecked references in Cursor values; they have to be able to become dangling without causing some error (the error is using such a cursor).

For a linked list container, we might have declarations like the following in the private part:

type Node is limited record Elem : Element_Type; Prev : Node_Ptr with Reference; Next : Node_Ptr with Owner; end record;

(Note: List is the visible private type.)

The Prev component is NOT an owner object; it is used only for list traversal and does not have any effect on the lifetime of the objects.

If the implementation wanted to have a free list of nodes, it could declare the following (probably in a protected object; the protected type would have to be listed as a primary owner type):

Then assigning a Node_Ptr to this object would have the effect of changing the owner to the global protected object (dereferencing such a pointer would require Global to include this protected object).