AI22-0034-2
!standard 3.10.2(22) 25-03-24 AI12-0034-2/05
!class ramification 25-03-24
!status WG9 Approved 23-10-12
!status ARG Approved 8-0-0 23-06-11
!status work item 22-01-26
!status received 22-01-02
!priority Medium
!difficulty Hard
!subject Implementation model of dynamic accessibility checking
[Editor's note: This model is intended to be applicable to the existing language versions of Ada 2005, Ada 2012, and Ada 2022. As such, it cannot add significant cases of erroneous execution or substantial incompatibility, and should not invalidate basic guarantees of those Ada versions. We could be more aggressive with an Amendment AI that applies to future Ada versions. However, we still need to solve this problem for those older language versions.]
The implementation model of dynamic accessibility checking given in the AARM is inadequate. This AI proposes a model that can support the full language using level objects, but it is a bit too complex for the AARM, thus the associated notes are deleted.
The AARM provides a suggested implementation model for dynamic accessibility checking in the Implementation Note beginning with AARM 3.10.2(22.u). However, this model alone is not enough to correctly implement Ada 2005, and Ada 2012 makes this even less true.
Is the intent that the "small integer" model of dynamic accessibility is no longer enough? (Yes.) If so, the AARM notes are misleading and should be replaced.
(See summary.)
Modify AARM 3.10.2(22.w/2):
The “obvious” implementation of the run-time checks would be inefficient, and would involve distributed overhead; [therefore, an efficient method is given below] {an implementation approach with minimal distributed overhead is described in AI22-0034-2}.
Delete AARM 3.10.2(22.x-22.ff).
[These paragraphs described the "small integer" implementation.]
Problems with the "small integer" model for representing accessibility levels and performing run-time accessibility checking have been identified (see mail message of July 28, 2011, filed in AI12-0016-1). This is a description of a more general "level object" approach which addresses these problems with modest cost that has minimal distributed overhead in cases where there are no dynamic accessibility checks. This is only intended to demonstrate that at least one viable implementation model exists and to make this available to language implementors as an option.
The level-object model is not intended to introduce any language changes, but rather to offer one way of meeting the requirements that are already implicit in the language definition. It may be that language changes in this area are needed. "Master-based" accessibility checking (see the accept_statement example and the discussion of incomparable accessibility levels in AI05-0024) rather than level-based checking may be needed to address scenarios involving incomparable accessibility levels (i.e., unequal levels, neither of which is "deeper" than the other). For example, the check associated with an access type conversion is defined by RM 4.6(48/3):
For an access-to-object type, a check is made that the accessibility level of the operand type is not deeper than that of the target type, ....
If it is somehow possible that the two accessibility levels mentioned above might be incomparable then we would want the run-time check to fail in this case; with the current wording, the check would pass. Such RM wording changes are outside the scope of this discussion, except that it is intended that the implementation model described herein would be compatible with such changes.
We describe the level-object approach in the "software present tense", as a fait accompli.
The accessibility level of a master is represented at run-time by a pointer to a level object whose lifetime is that of the master (and could be a "master record" or equivalent if that is already being allocated). For example, if the master is an execution of a subprogram body, then the level object would be declared (implicitly, by the compiler) within the subprogram.
For the following example
procedure P1 (X : access Integer) is ...
;
procedure P2 is
Local : aliased Integer;
begin
P1 (Local'Access);
the implicit parameter passed to P1 to describe X's accessibility level might be implemented by something like
procedure P2 is
P2_Level : aliased constant Level_Object := ... ;
Local : aliased Integer;
begin
P1 (..., P2_Level'Unchecked_Access);
Note that existing Ada implementations already pass some sort of accessibility level indicator with access parameters, typically a small integer representing a static nesting level. We are suggesting that implicitly-passed indicator now will be a pointer to a level object instead.
So what does this type Level_Object look like?
Given two accessibility levels A and B, the fundamental operation that must be supported by a dynamic accessibility check is answering the question "might the master associated with accessibility level A finish before the master associated with level B?". This can be answered by determining whether A and B are associated with the same master, or the master associated with A includes the master associated with B. Effectively there is a tree of masters (where each task starts its own branch), and we are interested in whether A's master is at the same point as B's master in this tree, or somewhere further toward the root than B's.
If we presume we are representing a master's accessibility level by a pointer to an object declared within the master, then we can simplify things by using "null" to represent the environment-level master (that is, "library level"). This means that when doing an accessibility check, there are two easy cases. If the pointers are equal, then we know the two accessibility levels are the same, and there is no danger of a dangling reference. The other easy special case is when one of the pointers is null, and the other is not. In that case we know the one with the null pointer will outlive the one with the non-null pointer.
If we have determined we need to do a dynamic accessibility check, but neither special case applies, then we can do the following: if we presume each level object has a pointer to the immediately enclosing level object (in the dynamic call chain or task creation chain), then to answer the question of whether we know accessibility level A lives at least as long as level B, we can walk up B's pointer until we reach null or A's pointer. If we reach a null, A might go away before B. If we reach A's pointer, then we know A outlives B.
We can optimize this approach by storing more information in the level object. For example, we could store a task id and a level number in the level object, and then we would walk the chain only when the task ids don't match, and otherwise rely on the within-task (dynamic) level numbers.
Not every scope needs a level object. Only if there might be some sort of dynamic accessibility check involving objects at a given accessibility level do we need a level object. In general, if there are aliased objects declared in a scope, and such an aliased object might be passed as an access parameter, we will need a level object. Similarly, if there is an access type declared in a local scope, and it participates in a dynamic accessibility check (due to, say, some conversion from an access parameter), we will need a level object. Minimizing the number of level objects is important to minimizing the distributed overhead of dynamic accessibility checking.
In the scopes where a level object is needed, we will need to initialize the object. At a minimum we presume each level object will need a pointer to the level object of the innermost dynamically enclosing scope where a level object was declared. This means that we should keep in thread-local storage a pointer to the "current" level object for a given Ada task, and upon creating a new level object we should initialize the new level object's "encloser" pointer to point to the (dynamically) enclosing level object, and then update this thread-local pointer to point to the new level object. On exit from a scope with a level object, we will need to restore the thread-local pointer.
If there is additional information in a level object, we will need to initialize that as well, generally by copying information or incrementing a counter taken from the dynamically enclosing level object.
In addition to the accessibility checks associated with access types, there are checks associated with returning or allocating class-wide objects (or objects with class-wide access discriminants), when there is the possibility that the tag of (some part of) the value might not live as long as the caller of the function, or the access type of the allocator. There is only a possibility of failure if the class-wide type has type extensions more nested than the root of the class-wide type.
For type extensions at the same level as all of their ancestors, we can use "null" as the value for their accessibility's level-object pointer, because they are effectively at the "top level" for this hierarchy of types. But for type extensions more nested than one of their ancestors, we will want their tag to give access to a level object, so a level object will need to be allocated in any scope where such nested extensions are declared.
If we know a type hierarchy has no nested type extensions (perhaps because the root of the type hierarchy is declared locally and there are no more-nested extensions), then no tag accessibility checks are needed for that type. However, in a generic body with a formal tagged type, an assume-the-worst rule would typically be needed, even if all types in the actual's type hierarchy would have effectively a "null" as their tag's level-object pointer. If generic bodies are macro expanded, then presumably there would be no significant run-time overhead for this assume-the-worst approach.
The net effect is that tag accessibility checks requires level objects only in scopes where a nested extension is declared, and a level-object pointer will need to be added to the type descriptor pointed to by the tag, but this pointer can be null for all tagged types that are not nested extensions.
Unlike accessibility checks for access types (which can avoid dynamic accessibility checks by avoiding certain constructs, for instance see the restriction proposed in AI22-0076-1), tag accessibility checks almost always have to be performed at runtime. The rules of Ada say that the actual tag of an object becomes visible when the object is converted to a class-wide type. This means that it is possible for the tag of a nested extension to appear in contexts when the nominal subtype of an object is a specific type that is not a nested extension (for instance, in an inherited subprogram). Thus the checks need to be made at runtime (and always performed, in some contexts), because only then is the actual tag known. Given that nested extensions can be created after the compilation of units containing ancestor types and their operations, it is only possible to determine that no checks are needed at link time (essentially, the dynamic checks are required for the operations of a type hierarchy unless there are no nested extensions anywhere in the program for that hierarchy). As such, implementations will need a properly operating dynamic tag accessibility check mechanism unless a restriction preventing the declaration of nested extensions exists in the program.
No ACATS tests are needed for this specifically, although tests for many dynamic
accessibility checks should include examples like those implied by the above descriptions.
[Editor's note: Older relevant e-mail can be found in the !appendix of AI12-0016-1 and in this note recording minutes of a discussion between Steve, Bob, Gary, Ed (Schonberg), Hristian, and Tuck that took place at AdaCore in October of 2014, related to an AdaCore internal "ticket" numbered N812-042.]
****************************************************************