!standard 3.10.2(22)                                      22-01-26        AI12-0034-1/01

!class binding interpretation 22-01-26

!status work item 22-01-26

!status received 22-01-02

!priority Medium

!difficulty Hard

!qualifier Clarification

!subject Implementation model of dynamic accessibility checking


[Editor's note: The contents of this AI is that of the last version of the Ada 2012 AI. It needs to be revised in some way, yet to be determined. Note that this is the Binding Interpretation for dynamic accessibility -- it applies 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. It is proven by [Baird, Brukardt; 202x] that dynamic accessibility checking as defined by the Standard is implementable without excessive overhead. That model is too complex for the AARM, thus the associated notes are deleted.


The AARM provides a suggested implementation model for dynamic accessibility checking in the Implmentation 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 should be updated to provide a realistic model.


(See summary.)


Modify 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]

{fortunately, more efficient methods are described in [Baird,Brukardt;202x]}.

<Editor's note: The citation in the square brackets will change to reflect the actual

paper once it is published.>

Delete 3.10.2(22.x-22.ff).

 [These described the "small integer" implementation.]


Problems with the the "small integer" model for representing accessibility levels and performing run-time accessibility checking have been identified (see mail message of July 28, 2011, previously filed in this AI - [Now AI12-0016-1 - Editor.]). This is a description of a more general implementation approach which addresses these problems without introducing unacceptable costs in space, time, or complexity. 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.

It 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) may require wording changes 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

   "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 proposal in the "software present tense", as a fait accompli.

The accessibility level of a master is represented at run-time by a pointer to an object whose lifetime is that of the master. For example, if the master is an execution of a subprogram body, then the 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;
       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;
       P1 (..., P2_Level'Unchecked_Access);


So what does this type Level_Object look like?

Given two accessibility levels A and B, the fundamental operation that must be supported is answering the question "might an entity whose accessibility level is A outlive one whose level is B?". Fortunately, it is not necessary to support this query for an arbitrary pair of accessibility levels; an implementation can take advantage of knowledge about the domain of this query. A query at some point in the execution of a program can only involve levels that are directly

visible or somehow indirectly reachable at that point.

To illustrate this point, let's first consider an implementation which would suffice to implement Ada 95 (but not, as it turns out, Ada 2005 or Ada 2012). Note that the small integer model also suffices for implementing Ada 95, so this initial implementation is really only useful as an expository stepping stone towards a more expressive implementation which does support Ada 2005 and Ada 2012.

The Ada-95-only implementation:

    For each master whose level needs to be represented at run-time

    (e.g., because a reference to a local variable is passed as an

    actual parameter where the corresponding formal is of an anonymous

    access type, as in procedure P2 in the example above), a local

    aliased constant of type Level_Object_95 is declared. The type is

    declared as

       type Level_Object_95;
      type Level_95 is access constant Level_Object_95;
      type Level_Object_95 is
          Static_Link : Level_95;
        end record;


A single constant of type Level_Object_95 is declared at library level:

    Library_Level_Object_95 : aliased constant Level_Object_95
     := (Static_Link => null);
   Library_Level_95 : constant Level_95
     := Library_Level_Object_95'Access;


All other objects of type Level_Object_95 are aliased constants declared in more nested scopes and containing pointers to the level object for the corresponding elaboration of the nearest (statically) enclosing scope which has a level object. This corresponds roughly to the "static link" mechanism traditionally used for implementing up-level references. To determine whether level A is deeper than level B, one traverses links starting at A until either B or null is encountered (the former indicating A is deeper than B, the latter indicating otherwise; a level is, by definition, not deeper than itself so the A = B case must also be handled correctly).

The following example (which involves an anonymous access-to-subprogram type, not an Ada 95 feature) demonstrates that this approach, at least as described so far, doesn't handle some Ada 2012 constructs:

   procedure Accessibility_Test is
    procedure Call_Proc
      (Proc : not null access procedure (X, Y : access Integer);
       X, Y : access Integer) is
        Local : aliased Integer;
        if X = null then
           Proc.all (Local'Access, Y);
           Proc.all (X, Local'Access);
        end if;

    procedure P1 is
        procedure P2 (X, Y : access Integer) is
            type Ref is access all Integer;
            for Ref'Storage_Size use 0;
            Ptr : Ref;

            procedure P3 (X, Y : access Integer) is
                Ptr := Ref (X); -- OK (1)
                    Ptr := Ref (Y); -- raises Program_Error (2)
                    when Program_Error =>
                pragma Assert (Ptr /= Y);
           Call_Proc (P3'Access, X, null);
       Call_Proc (P2'Access, null, null);


Let's look at how this model breaks down in the case of this example.

When P3 is called, the call stack is

The two accessibility levels passed into P3 correspond to the two calls to Call_Proc. One of these two levels is longer lived than the level of the call to P2 (which is also the level of Ref, the target type of the access type conversions) and one of them is shorter-lived, but this essential distinction is lost. The first access type conversion should succeed and the second should

fail, but there is insufficient information to make this distinction.