!standard  3.09.01    (03)                             04-02-29  AI95-00344/01
!class amendment 03-08-07
!status work item 04-02-29
!status received 03-04-21
!priority Medium
!difficulty Hard
!subject Allow nested type extensions

!summary

Type extensions are allowed in scopes more nested than their
parent type. Checks are performed on function return and
on allocators to ensure that objects of such a type extension
do not "escape" to a less nested environment.

!problem

The restriction against nested type extensions makes it harder
to instantiate certain generics in a local scope, if those generics
internally use extension from some kind of standard library-level type,
such as a storage pool, or a controlled type, or a stream. Such
restrictions can "snowball," meaning that many generics in a system may
only permit library-level instantiations.

!proposal

Repeal the accessibility check in 3.9.1(3). Replace it by something that still
allows generic sharing (probably prohibiting extension in generic bodies).

Add accessibility checks on class-wide allocators and return statements.

!wording

Delete the last two sentences of 3.9.1(3).

Add after 4.8(5):

    If the designated type of the type of the allocator is tagged, the
    accessibility level of the designated type shall not be statically deeper
    than that of the type of the allocator.

Add after 6.5(20):

    If the result type is class-wide, a check is made that the accessibility
    level of the type identified by the tag of the result is not deeper than
    that of the master that elaborated the function body.  If this check fails,
    Program_Error is raised.

!example

!discussion

[Editor's note: 3.9.1(4) is retained (which prevents extension in generic
bodies), because the contract model issues discussed in the AARM remain.
You can get similar issues from parameters which depend on formal types.
See the e-mail below.]

IMPLEMENTATION ISSUES

When a type is extended in a more nested scope, the dispatching operations
may need access to data declared in this nested scope. This will generally
require a static link or global display. However, the caller of such
a dispatching operation is generally "unaware" that they are calling
such a nested dispatching operation. This means that the dispatching
operation must deal with the static link or global display internally,
using information that the caller passes in.

The simplest approach seems to be as follows:

When defining the record layout for a nested type extension, an
additional implicit component is allocated to contain the static link,
or a pointer to a saved global display, or in the case of a shared
generic, a pointer to an instantiation descriptor in which the
static link or global display can be found.


!corrigendum 03.09.01(03)

!ACATS test

!appendix

From: Tucker Taft
Sent: Monday, April 21, 2003  3:44 PM

The current rule that disallows extending a type
at a more nested scope than the parent type has always
been a bit troublesome.  I believe that during the
Ada 9X process we felt quite strongly that this was
the only safe rule.  However, as I have thought
about this rule more recently, it seems to be possible
to avoid problems by simply performing accessibility
checks at allocators and function returns.

The danger from nested extensions is that a global variable
will end up with a tag of a nested type extension.  But this
can only happen in two ways:

   1) A function with a classwide result type returns an object of a
      type extension declared within it.

   2) An allocator for an access-to-classwide type declared at an outer
      level is evaluated for a more nested type extension.

Both of these situations seem eminently checkable.  (1) is very similar
to the current accessibility check on return-by-reference objects.
(2) is similar to a check that is required when the designated
type for an allocator has an access discriminant initialized by
local_obj'access.

Is there some other problem that I have forgotten?

Should we consider an amendment to allow nested extensions?
It would seem to eliminate a number of other annoying problems
where certain generics cannot be instantiated at a nested level.

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

From: Randy Brukardt
Sent: Monday, April 21, 2003  4:15 PM

> Should we consider an amendment to allow nested extensions?

No.

> It would seem to eliminate a number of other annoying problems
> where certain generics cannot be instantiated at a nested level.

No, this is the same as saying that we're eliminating all useful generic
sharing. (I define "useful" generic sharing as that done without looking
into the body. If you can look into the body, there is no need or reason for
language rules to be involved, the sharing 'contract' now is essentially the
entire program.)

It is critical that access-to-subprogram types (which include tags) never,
ever 'leak' out of the generic body (because such subprograms have a
'different' profile than the 'apparent' profile used for checking language
rules). The accessibility rules happen to have that effect; but clearly they
were not designed for that. If the accessibility rules are weakened or
removed, you simply have to add them back in some other way. Or, simply drop
generic sharing and the contract model. (I see no reason to keep any of the
generic-sharing rules if any of them are eliminated.)

I started to write up a long LSN/web page on the topic of generic sharing,
because I seem to need to re-explain it every couple of months. Other things
intervened, but it appears that I still need to do so...

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

From: Tucker Taft
Sent: Monday, April 21, 2003  5:15 PM

Would it help if you still had to put type extensions
in the spec as opposed to the body (if they are at the
same accessibility level as the spec, that is)?  I thought that
was the thing which simplified generic sharing.  Allowing
extensions inside a subprogram body seems like a different
sort of thing, and I presumed would not break sharing.

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

From: Randy Brukardt
Sent: Monday, April 21, 2003  5:37 PM

The only way that it wouldn't break sharing is if there never, ever was a
way to call them from outside of the body (including from calls outside of
the body). That clearly includes dispatching calls, but is not limited to
that. I don't see what such a type (or object) would be useful for.

Indeed, I can't see what your proposed extension is useful for. Your
proposed limitations seem to prevent the type from being used for
dispatching. That presumably includes implicit dispatching (that is,
finalization and storage pools), since that is likely to be implemented with
real dispatching (they certainly are in Janus/Ada). If it's not prohibited
from use in dispatching, I don't see how you expect it to work - you'd have
to include a static link or display in the tag - indeed in ALL tags. (The
'current' one wouldn't work, you could make external calls to the same level
and have the wrong link/display values. That's not a problem for local
variables because they're not accessible, but certainly it would be possible
with a dispatching call where the lack of visibility doesn't matter). That's
clearly a lot of overhead (because you'd have to 'switch' the display or
static link on every dispatching call); there had better be a pretty solid
purpose behind the extension.

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

From: Tucker Taft
Sent: Monday, April 21, 2003  6:45 PM

Yes, the static link/display is the issue, I suppose.
It would seem you could implement this by putting
the link/display information in any object of a nested type
extension.  We do something analagous for dealing
with nested protected types, I believe, because we
pass a pointer to the protected object in the same
register we normally use for passing the static
link.  If the protected type is itself nested, the
"real" static link is retrieved from the protected object.

Given that nesting is usually shallow, even a display
would only occupy a few words in the tagged object.

Does that sound feasible?

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

From: Randy Brukardt
Sent: Monday, April 21, 2003  5:37 PM

Well, that would work, but its completely non-responsive to my question. In
Janus/Ada, all objects have a static size. Anything dynamically sized is
allocated from a storage pool and stored in a fixed size descriptor (which
is often just a pointer). Thus, there is only the options of including
enough space for everything (8 levels in Janus/Ada) in all objects or
allocating the space off of one of the storage pools (with the associated
runtime overhead).

But this is equivalent to putting it into the tag, just a lot more expensive
in space overhead (unless there is only one object). So I don't see any
difference. Moreover, it does nothing to address the distributed runtime
overhead: every dispatching call has to extract the tag or display from
somewhere (doesn't matter where), and arrange to use it on the call. That's
not too expensive for a static link, but it is very expensive for a display
(because you have to save the old one somewhere, then copy in the new one,
then reverse the process on return). And there is no hope to optimize it out
(unless you're into link-time code generation), because any program can have
a nested type added in the future. The absolute best you can do is check at
runtime whether you have to do it, but even then, there is a gob of code
needed to provide the rarely-to-be-used support (and the extra test and
jump). That's the definition of distributed overhead.

> Does that sound feasible?

Feasible, but not practical as noted above.

Do you have any realistic example of what this would be good for? I still
see no value to it, and you haven't explained how you would use it. You have
to explain what is so important to take on the sort of distributed overhead
that you are discussing here. I'm not going to waste any more time
discussing implementation until I understand what it would be used for.
Otherwise, I'm just answering the same old questions; I have no opportunity
to suggest an alternative that might not be such a problem.

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

From: Tucker Taft
Sent: Monday, April 21, 2003  8:38 PM

I'm not sure I understand why this would introduce a dynamic size.  If
inside a subprogram body I extend a type declared outside
the subprogram, I know I am creating a nested extension,
and only objects of that type need a static link/display,
and I "know" exactly how deeply nested I am.
(I wouldn't want to put them in the type descriptor pointed
to by the tag because we allocate and initialize that
statically.)

When dispatching operations of this type are called, they are treated
as though they were declared at the same level as the root type
as far as the caller is concerned.  If they need access to data
at levels more nested than that, they have to go indirect via
the static link/display stored in the tagged object.

I don't think this implies distributed overhead, since only
dispatching operations for nested extensions would have to
use the "funny" static link/display entries.

> ...
>
> Do you have any realistic example of what this would be good for? I still
> see no value to it, and you haven't explained how you would use it. You have
> to explain what is so important to take on the sort of distributed overhead
> that you are discussing here. I'm not going to waste any more time
> discussing implementation until I understand what it would be used for.

I agree that if it implies all of the distributed overhead you
suggest, then it would not be a good idea.  In fact, if it involved
any distributed overhead at all it would be a bad idea.  But
it seems like the overhead could be kept within the place
where a nested extension appears.  Disallowing such
things in generic bodies would seem a reasonably limitation,
since type extensions are not permitted in generic bodies
now anyway.

But I presume the benefits are obvious.  Right now, if
you define a root type like "Finalization.Controlled" or
something else, and then create useful code that deals
with the root-type'Class, this is only usable with types
declared at the same nesting level as the root type.

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

From: Randy Brukardt
Sent: Monday, April 21, 2003  9:31 PM

> I'm not sure I understand why this would introduce a dynamic size.  If
> inside a subprogram body I extend a type declared outside
> the subprogram, I know I am creating a nested extension,
> and only objects of that type need a static link/display,
> and I "know" exactly how deeply nested I am.
> (I wouldn't want to put them in the type descriptor pointed
> to by the tag because we allocate and initialize that
> statically.)

OK, but how do you know whether objects of that type have such a thing, and
where it is?? This can't happen by magic: a dispatching call needs exactly
the same layout of components that it is going to deal with in all cases.

> When dispatching operations of this type are called, they are treated
> as though they were declared at the same level as the root type
> as far as the caller is concerned.  If they need access to data
> at levels more nested than that, they have to go indirect via
> the static link/display stored in the tagged object.

You want a wrapper around the wrapper? Yikes - I can't figure out how this
works as it is. That is going to be one messy wrapper, because it has to
have a stack frame of its own (to save the current display in); which means
the parameters will have to be copied.

> I don't think this implies distributed overhead, since only
> dispatching operations for nested extensions would have to
> use the "funny" static link/display entries.

No, I suppose you're right (presuming that such wrappers can be built - I
think there might be problems if the root type is nested. What is the level
of the wrapper in that case? I suppose one can just forget such a case,
'cause it's useless.)

> ...
> Disallowing such
> things in generic bodies would seem a reasonably limitation,
> since type extensions are not permitted in generic bodies now anyway.

But that's a fallacy. The only reason type extensions are prohibited in
generic bodies is because of the assume-the-worst accessibility check.
You're proposing to eliminate the accessibility check; then there is no
longer any legitimate reason for prohibiting type extensions in a generic
body. We'd have to add a specific rule for that - and it would have no real
justification - it would essentially be there only because of me. People
would picket my office if they found out. :-)

> But I presume the benefits are obvious.  Right now, if
> you define a root type like "Finalization.Controlled" or
> something else, and then create useful code that deals
> with the root-type'Class, this is only usable with types
> declared at the same nesting level as the root type.

Maybe to you, but I don't see the "benefits" of declaring a nested type. The
only times I've wanted to do it is in Q&D test programs where declaring a
separate package is a pain. But that 'pain' is a benefit in real, large
systems - it prevents the main subprogram from containing stuff that really
doesn't belong there. Moreover, if you declare a nested type, it can't
(usefully) be inherited from -- which means you're losing some of the
benefits of O-O. So, you almost always want a package for your type
extensions.

If the goal is to get subprogram-level finalization, I'd rather see that
done in a first-class manner (which would be both easier to write and more
obvious that it is unusually expensive). That requires some syntax. But I
see no benefit at all to extending anything other than
Finalization.Limited_Controlled in a subprogram, and that being the case,
I'd rather leave well enough alone and only deal with the case that is
interesting.

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

From: Pascal Leroy
Sent: Wednesday, April 23, 2003  5:07 AM

I don't think you have yet provided a compelling justification for this
change.  Other than the specific case of Controlled (which we might want
to address separately) I don't see that nested OO hierarchies are
particularly useful or frequent in practice.  I would not be opposed to
reopening AC-00050, but this is going to irritate Randy.

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

From: Tucker Taft
Sent: Thursday, April 24, 2003  10:15 AM

> ... But I
> see no benefit at all to extending anything other than
> Finalization.Limited_Controlled in a subprogram,...

I'm surprised others haven't run into this before.
One of the biggest "privacy" breakages is that
a generic can't be instantiated inside a subprogram
if it happens to implement any of its private types
using type extension of some type declared outside
the generic.

This is particularly annoying for "container"-type
generics, where one would really like to be able to instantiate
and declare a local hash table, for example, but can't do it if
it happens to declare a local storage pool type.

It is often possible with some amount of pain to
move the instantiation, while keeping the local
hash table object (presuming the instantiation declares
a type rather than havings its own internal table object).
But this gets nastier if you are yourself writing
a generic, and the element type is a formal type.

Ultimately you end up with a whole bunch of generics
that can only be instantiated at library level.

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

From: Randy Brukardt
Sent: Monday, March 1, 2004   9:12 PM

Tucker wrote in the AI: [Editor's note: Version /01.]

> When defining the record layout for a nested type extension, an
> additional implicit component is allocated to contain the static link,
> or a pointer to a saved global display, or in the case of a shared
> generic, a pointer to an instantiation descriptor in which the
> static link or global display can be found.

Of course, this doesn't work in the generic body for all of the reasons that
previously been discussed.

The accessibility check in generic bodies prevents all kinds of things that
can't be implemented -- and the problems arise from issues that have nothing
to do with accessibility. Every subprogram that can be dispatched to or
accessed via an access-to-subprogram needs a thunk: both to add the hidden
generic parameter (which we've talked about at length), and also to convert
the parameter passing between the implementation for the formal and the
implementation for the actual.

If you were to put the instantiation descriptor into tagged objects that are
extended in generic units, you could declare a wrapper that added that to
the call for dispatching calls. And the tagged object is always passed by
reference, so that's OK. But other parameters might have different passing,
and you couldn't reconcile that in a wrapper (you don't know the actual
types involved).

Which brings up an interesting question: is a operation (potentially)
primitive if it depends on a formal type? We never had to answer this in Ada
95 for bodies; we said that it is true in specs. Consider something like:

    type Root is tagged ...
    procedure Oper (Obj : in out Root; Arg : in Natural);

    generic
       type Priv is private;
    package Gen is
       ...
    end Gen;

    package body Gen is
       type New_Type is new Root with ...;
       procedure Oper (Obj : in out New_Type; Arg : in Priv); --??
       ...
    end Gen;

    package Inst is new Gen (Natural);

Now, does Inst.Oper override the inherited one? If this occurred in the
spec, it would. But if you do this in the body (which is currently illegal),
then sharing without body knowledge is impossible, because you need to know
the actual type(s) in order to determine the contents of the tag. (One also
has to wonder about the contract model implications here.)

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

From: Tucker Taft
Sent: Monday, March 1, 2004   9:42 PM

> Of course, this doesn't work in the generic body for all of the reasons that
> previously been discussed.

Sorry, I really don't understand your model enough
to suggest something intelligent.  In any case,
I was presuming that the restriction 3.9.1(4) would remain:

   A type extension shall not be declared in a generic body
   if the parent type is declared outside that body.

Perhaps that restriction makes no sense if we are allowing
type extension in arbitrary non-generic bodies, but I
presumed it was still important for shared generics
for some reason.

...
>     package body Gen is
>        type New_Type is new Root with ...;
>        procedure Oper (Obj : in out New_Type; Arg : in Priv); --??

This would violate 3.9.1(4) I believe.

>        ...
>     end Gen;

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

From: Ramdy Brukardt
Sent: Monday, March 1, 2004   9:58 PM

>    A type extension shall not be declared in a generic body
>    if the parent type is declared outside that body.

Sigh. I didn't remember this rule; I've always thought that the accessibilty
check itself preventing body tagged types.

Anyway, the AARM primarily discusses accessibility reasons for this rule.
Those obviously would be gone. But it also discusses problems with abstract
subprograms causing contract problems. Those would still remain, so we'd
still have a reason for the rule (although we'd need to rewrite the
explanation in order for it to make sense). I think you could construct an
example where whether the program was legal or not depended on the actual
type used for another parameter similar to the example I showed in my last
message. So it looks like there are real contract problems with that, so
there isn't a problem.

But I do think a brief discussion of why 3.9.1(4) remains (and that it
exists!) would be valuable in the AI. Otherwise, people might be expecting
more out of this than they'll actually get.

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