AI22-0034-1

!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

!subject Implementation model of dynamic accessibility checking

!summary

[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; 201x] 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.

!issue

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.

!recommendation

(See summary.)

!wording

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;2019]}.

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

paper once it is published. I hope Steve is joking with the included date. :-)>

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

 [These described the "small integer" implementation.]

!discussion

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

the implicit parameter passed to P1 to describe X's accessibility level might be

implemented by something like

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

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

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:

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

When P3 is called, the call stack is

•     P3
•     Call_Proc
•     P2
•     Call_Proc
•     P1
•     Accessibility_Test

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.

So now we take the view that the "static link" is just one example (albeit, the

most important one) of a level whose lifetime is known to be longer than that of

a given level for which we are declaring the level object. In the case of a

subprogram which has an anonymous access-to-object parameter, for example, the

level of the parameter (which is passed in) is also known to have this property.

For a class-wide parameter, the level of the underlying specific type of the

parameter is another such "known to outlive me" level. For a build-in-place

function or a function with an anonymous access result type, the level

determined at the point of call is another.  The point is that a set of such

"predecessor" levels can be determined by combining the static-link with other

levels extracted (extraction details TBD) from the parameters. The idea is that

at the time of a subprogram call, the only existing levels that the callee will

need to refer to are those that are reachable via an uplevel reference to an

enclosing scope combined with those that are somehow passed in as parameters

(this includes things like the accessibility level of the underlying specific

type of a tagged parameter, not just simple cases like anonymous

access-to-object typed parameters; note that for most implementations this

particular example probably means that the descriptor for specific tagged type

will contain the pointer value representing its accessibility level).

This suggests something like

In our example above, the two level objects declared locally to the two

invocations of Call_Proc would now capture the needed distinction by

incorporating the levels of their parameters. See the "gory details" section

below for a detailed explanation of how this is accomplished. It would also be

instructive (I imagine) to look at the examples given in the initial AI

discussion (in particular, procedures Ada05_Example and Access_Result_Test)

which illustrate cases that the small integer model cannot handle and to work

through how these cases work with the proposed model (Note: I have not actually

had time to do this yet, but that doesn't stop me from recommending this action

to others).

This raises performance questions. To decide whether level A is at least as

long-lived as level B, we need to traverse B's known predecessors, just as

before, but now this involves traversing a DAG instead of a linked list. Can

this be done cheaply enough?

One answer to that is to store the "static link" in the first element of the

Predecessors array and to optimize for the case where the Ada-95-style

representation described above would have sufficed to determine that the check

would pass. We certainly don't care about performance in the case where the

check will fail; it might be that we also don't care very much about performance

in the corner cases where this richer data structure (i.e., multiple

predecessors) is needed to get the right answer.

Is it worthwhile to try to avoid adding redundant predecessors to a

Level_Vector? Consider the case of a subprogram which takes an access parameter

when the parameter happens to be null (or a pointer to an object declared at

library level). If redundant predecessors are always filtered out, then we are

talking about traversing a tree instead of a DAG.

We still have the important optimization that no level object is declared for a

master that doesn't need one. In particular, wrappers don't declare level

objects.

The details of how we extract predecessor information from a routine's

parameters when building a level object have been glossed over here. Some

thought is needed here (e.g., are there cases where a parameter of a specific

tagged type requires extracting the accessibility level of the underlying type

of the actual and incorporating that into the predecessor set of the callee?).

Note, however, that the rest of the model is not particularly sensitive to these

details.

====

Gory details (as promised above):

When P3 is called, the call stack is

•     P3
•     Call_Proc - second call
•     P2
•     Call_Proc - first call
•     P1
•     Accessibility_Test

The only masters in this example (besides the library_level master) are

subprogram body executions, so there are at most 7 accessibility level objects

to worry about. In fact, the procedures Accessibility_Test, P1, and P3 do not

require level objects, so there are only 4.

When P1 calls Call_Proc, it has to pass in two accessibility levels for the

parameters X and Y. Because it is passing in "null" values, it passes in the

library level.

Inside this (i.e., the first) call to Call_Proc, Call_Proc builds its local

level object. Let's ignore the access-to-subprogram parameter for now and also

assume that we are not going to perform any filtering at this point to weed out

predecessors which contribute no new information. So the object declaration

might be implemented as something like

In this case, X'Accessibility_Level and Y'Accessibility_Level both yield

Library_Level, so we get three copies of the same dependency. To recap:

Call Proc then calls P2, passing in Call_Proc_Call_1.Level_Object'Access as the

accessibility level for X and passing along Library_Level as the accessibility

level for Y.

P2, upon being called, builds its local level object in much the same way that

Call_Proc did, ending up with

P2 then calls Call_Proc, passing along Call_Proc_Call_1.Level_Object'Access as

the accessibility level for X and passing in Library_Level as the level for Y.

Call_Proc, upon being called again, builds its local level object, ending up

with

Call Proc then calls P3, passing along Call_Proc_Call_1.Level_Object'Access as

the accessibility level for X and passing in

Call_Proc_Call_2.Level_Object'Access as the accessibility level for Y.

P3 now performs two accessibility checks. For the first access type conversion,

it compares the accessibility level for X (which is

Call_Proc_Call_1.Level_Object'Access) to that of the access type Ref (which is

P2.Level_Object'Access) so see if X is sufficiently long-lived. The answer is

yes, because X's level is a predecessor of Ref's, and the check passes as

desired.

For the second access type conversion, the accessibility level of Y is used in

place of X's. The accessibility level of Y is

Call_Proc_Call_2.Level_Object'Access, which is nowhere to be found in a

predecessor traversal starting from Ref's level. Thus, the check fails as

desired.

!ACATS test

No ACATS tests are needed for this specifically, although tests for many dynamic

accessibility checks should include examples like those in these above descriptions.

!ASIS

This has no effect on the normative standard, so it has no effect on ASIS, either.

!appendix

[Editor's note: Older relevant e-mail can be found in the !appendix of

AI12-0016-1.]

****************************************************************