Version 1.5 of ais/ai-00344.txt

Unformatted version of ais/ai-00344.txt version 1.5
Other versions for file ais/ai-00344.txt

!standard 3.09.01 (03)          04-06-05 AI95-00344/02
!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, on streaming, 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 (by prohibiting extension in generic bodies of descendants of formal types).
Add accessibility checks on class-wide allocators, return statements, and T'Class'Input/Output.
Require that the type "Tag" include sufficient information to distinguish all descendants of a given ancestor type.
!wording
Modify 3.9(4) as follows:
... For a tagged type that is local to a generic package body {all of whose ancestors are also local to the same generic body}, the language does not specify whether repeated instantiations of the generic body result in distinct tags. However, to ensure that all descendants of a given type have distinct tgs, if any ancestor is declared outside the generic body, the tag identifies the particular instance of the body. Similarly, for a type declared at an accessibility level deeper than one of its ancestor types (if any), the tag identifies the particular execution of the enclosing master that elaborated the tagged type declaration.
AARM NOTE: In most cases, a tag need only identify a particular tagged
type declaration, and can therefore be a simple link-time-known address. However, for tag checks (see 3.9.2(16)) it is essential that each descendant of a given type have a unique tag. Hence, for types declared in shared generic bodies where an ancestor comes from outside the generic, or for types declared at a deeper level than an ancestor, the tag needs to be augmented with some kind of "static link," "global display," or "instance descriptor" pointer. This implies that type Tag may need to be two words, the second of which is normally null, but in these identified special cases needs to include a static link or equivalent. Within an object of one of these types with a two-word tag, the two parts of the tag would typically be separated, one part as the first word of the object, the second placed in the first extension part that corresponds to a type declared more nested than its parent or declared in a shared generic body when the parent is declared outside.
Add after 3.9(7):
function Descendant_Tag(External : String; Ancestor : Tag) return Tag;
function Is_Descendant_At_Same_Level(Descendant, Ancestor : Tag) return Boolean;
Modify 3.9(12):
The function Internal_Tag returns [the] {a} tag that corresponds ...
Add after 3.9(12):
The function Descendant_Tag returns the (internal) tag for the type that corresponds to the given external tag and is both a descendant of the type identified by the Ancestor tag and has the same accessibility level as the identified ancestor. Tag_Error is raised if External is not the external tag for such a type.
The function Is_Descendant_At_Same_Level returns True if Descendant tag identifies a type that is both a descendant of the type identified by Ancestor and at the same accessibility level. If not, it returns False.
AARM NOTE: Descendant_Tag is used by T'Class'Input to identify the type
identified by an external tag. Because there can be multiple elaborations of a given type declaration, Internal_Tag does not have enough information to choose a unique such type. Descendant_Tag does not return the tag for types declared at deeper accessibility levels than the ancestor because again, there could be ambiguity in the presence of recursion or multiple tasks. Is_Descendant_At_Same_Level is used by T'Class'Output to determine whether the item being written is at the same accessibility level as T. It may be used to determine prior to using T'Class'Output whether Tag_Error will be raised.
Delete the last two sentences of 3.9.1(3).
Replace 3.9.1(4) with:
Within the body of a generic unit, or the body of any of its descendant library units, a tagged type shall not be declared as a descendant of a formal type of the generic unit.
Add after 4.8(5):
If the designated type of the type of the allocator is class-wide, the accessibility level of the type determined by the subtype_indication or qualified_expression shall not be statically deeper than that of the type of the allocator.
Add at the end of 4.8(7):
... If the designated type of the type of the allocator is class-wide, then a check is made that the accessibility level of the type identified by the tag of the value of the qualified_expression is not deeper than that of the type of the allocator. Constraint_Error is raised if this check fails.
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.
Add to end of 13.13.2(31):
... Tag_Error is raised if the tag of Item identifies a type declared at an accessibility level deeper than that of S.
Modify 13.13.2(34):
First reads the external tag from Stream and determines the corresponding internal tag (by calling [Tags.Internal_Tag(String'Input(Stream))] {Tags.Descendant_Tag(String'Input(Stream), S'Tag) which might raise Tag_Error} -- see 3.9) ...
!example
!discussion
With the proposal to add a number of generic packages to provide standard container abstractions, there has been growing concern about the rule precluding extending a type at a deeper accessibliity level. Because user-defined controlled types, user-defined storage pools, and user-defined streams are all implemented using type extension, this rule can interfere with natural use of generic data structures in nested scopes.
It turns out that nested type extensions can be supported safely by shifting the accessibility checks to certain operations, rather than being enforced at the type declaration. In particular, by performing accessibility checks on class-wide allocators, class-wide function return, and class-wide stream I/O, the danger of objects outliving their type declaration can be eliminated.
For allocators, we disallow creating an object in a collection whose access type outlives the type identified by the object's tag. Similarly, for function return, we disallow returning a classwide object from a function if tag identifies a type declared at a deeper level than the function. For similar reasons, we preclude T'Class'Input returning an object whose tag identifies a type that is declared at a deeper level than T. For symmetry, and to prevent writing something which cannot later be meaningfully read, we preclude T'Class'Output writing out an item whose tag identifies a type of a deeper level than T.
To implement tag checks needed to ensure that all dynamically tagged controlling operands come from the same tagged type, we place additional requirements on the uniqueness of run-time tags. We considered defining a separate type called "extended tag." However, this would add user complexity, and would make existing user tests for tag equality using the preexisting tag type no longer sufficient to ensure that the tag check would succeed.
To implement the accessibility checks required for T'Class'Input and T'Class'Output, we provide two additional functions in Ada.Tags, Descendant_Tag and Is_Descendant_At_Same_Level. Although it is not strictly necessary to standardize these functions, it is useful for the programmer to be able to use these functions to implement their own checks, prior to, or as an alternative to, the predefined streaming attributes.
We considered requiring that an external tag be sufficient to uniquely identify an internal tag. However, given that we only allow T'Class'Input and T'Class'Output for types at the same accessibility level as T, the only (implicit) requirement is that it be unique for descendants of a given type at the same accessibility level as the ancestor. Hence, there is no need to distinguish between different elaborations of a type declared in a recursive routine. However, we do (implicitly) require that for a type declared in a shared generic body whose parent is from outside the generic, the external tag should be sufficient to identify the particular instance, for instances at the same accessibility level as the parent type.
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 instance descriptor in which the static link or global display can be found.
The type Ada.Tags.Tag would be two words, made up of the pointer to the dispatch table, as now, plus a second word that would be null for the "normal" case, but would hold the static link, global display, or instance descriptor for nested type extensions.
To avoid distributed overhead, we would suggest that the tag check required when there are multiple controlling operands only check the "first word" of the now two-word tag at the call site. Then an additional check on the second word needs to be performed after the dispatch only if you arrive in an operation which actually makes use of such a static link to make sure the static links or displays are the same. If they don't agree, then an exception should be raised just as though there had been a tag mismatch.
This seems like a relatively low overhead, since operations with multiple controlling operands are relatively rare, and the overhead would only be incurred when reaching such an operation on a nested type, meaning it is not a distributed overhead.
Note that some implementations may create "wrappers" for dispatching operations of nested extensions to fetch the static link/display pointer and then call the "real" body with the static link/display in the "normal" register or per-task display used for that. This wrapper would be the natural place to perform this additional check.
!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.

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

From: Tucker Taft
Sent: Thursday, April 1, 2004  11:19 AM

Randy, Steve Baird, and I have been having a bit
of a side-bar discussion on paragraph 3.9.1(4) and
how it relates to AI-344 on allowing extending
in nested scopes.  The most recent version of AI-344
did not touch 3.9.1(4) which disallows extending
in a generic body a type defined outside it,
since we would be allowing extension in all
kinds of other contexts.

After a few back-and-forths with Randy, we
came up with the following wording for 3.9.1(4)
which seems to be satisfactory, and
avoids contract model issues associated with extending
types with unknown number of functions that require
overriding (due to a controlling result).  It also
allows slot numbers to be assigned for any new
operations, since the parent is not a formal type.

    Within the body of a generic unit, or the body of
    any of its descendant library units, a tagged type
    shall not be declared as a descendant
    of a formal type of the generic unit.

This is carefully worded to handle child units, as well
as interfaces (hopefully).

The net effect is that you *can* extend a type
declared outside the generic body, so long as it
is not a descendant of a formal.  The anticipated
implementation model is still that the new type
would have a component that pointed to a block
of information which would contain static link/
display/instance descriptor/whatever.  Wrappers
for the dispatching operations would load this
information into appropriate registers, etc.,
and then call/jump to the user-defined primitive
subprograms.  These are essentially the same
thing as "trampolines" which are used by GNU C
and friends to support nested functions.

I have attached below the mail sent by Steve Baird,
Randy, and myself, for the record.

If there are no major objections, I will include
this change in the next version of AI-344.

----------

 From Steve, 3/29/04, 6:54 PM:

I strongly want to be able to instantiate the various container generics
anywhere (e.g. inside of a subprogram which is inside of a generic body),
even if they are implemented using controlled types.

This runs afoul of 3.9.1(4) .

If you've already addressed this problem, then this message can be
ignored.

Given AI-344's runtime checks, the only remaining need for 3.9.1(4) stems,
as I understand it,  from the case described in AARM 3.9.1(4.a-j).

This case can only arise if the parent  type is abstract.

Could 3.9.1(4) be relaxed so that it only applies to abstract types?

I'm not claiming this is elegant, but it would allow an important case.

----------

 From Tuck to Randy and then his reply (3/31/04):

 >> Hi Randy,
 >>     There seems to be some interest in pushing forward AI-344, nested type
 >> extensions.  Paragraph 3.9.1(4) disallowing extending in generic
 >> bodies has been an issue.  It seems somewhat arbitrary, if we allow
 >> extending pretty much anywhere else.  I was thinking that the following
 >> might solve the problem:
 >>
 >> Replace 3.9.1(4) with:
 >>
 >>     A type extension shall not be declared in a generic body if the parent
 >>     type is a formal type of the generic.
 >>
 >> Would this be implementable in your compiler?  Notice that I allow the
 >> parent to be descended from a formal type, but not a direct use of the
 >> parent type.  That avoids the danger that the parent type is class-wide.
 >>
 >> Presumably with AI-251, this would become:
 >>
 >>     A type extension shall not be declared in a generic body if the parent
 >>     type or one of the ancestor interface types is a formal type of the
 >>     generic.
 >>
 >> Can you think about this a bit and let me know?


I thought about this some last week while I was working on the minutes.

One comment is that I never saw any actual reaction to keeping 3.9.1(4). The
only person who seemed to care was you. So I'd suggest not giving this rule
an importance out of proportion to reality. (After all, most types can be
hoisted to the spec.)

First of all, it will be very hard to implement any part of AI-344 in our
compiler. We implicitly add generic descriptor parameters for all
subprograms (declarations and calls) if they are declared in a generic.
Doing this causes the other parameters to be renumbered automatically. The
implementation you've suggested for AI-344 requires this not to be true for
wrappers for tagged types. That will require major restructuring in the
compiler - either the wrappers would have to be created by a totally
separate set of code (meaning the duplication of the 1500 lines of call
generation code - sounds very bad) or the automatic, under the covers
operation of generics would have to be gotten rid of. Neither is likely to
be practical; I'd expect that a likely implementation of AI-344 would
completely disallow it in generics.

In any case, I don't want to stand in the way of progress here (unless it is
clearly going too far, like the generic instantiation junk). So most of the
discussion is more hypothetical than what actually can be implemented. It's
about what could be implemented with heroic efforts to provide a usable
solution, as opposed to what's clearly impossible or outrageous.

Besides implementation problems, that rule is needed to avoid contract model
issues. I hadn't thought about class-wide; the AARM mainly discusses it in
terms of must-be-overridden functions. The example is something like:

      generic
          type Foo is tagged private;
      package Gen is
          ...
      end Gen;

      package body Gen is
          type New_Foo is new Foo with private;
             -- ??
      end Gen;

      type Bar is tagged ...;
      function A_Bar return Bar;

      package New_Gen is new Gen(Bar); --??

Since A_Bar is a primitive function returning an object of Bar, it must be
overridden. But how would New_Foo know to do that? It's clear that the type
cannot depend on a formal.

There is also a practical contract violation here. We have a meta-rule that
tags always can be created statically. We certainly adhere to that rule by
generating the tags for types declared in a generic at instantiation time.
There is no way to do that for a type that depends on a formal that declared
in the body. (And note that here, this is true even if there is an
intermediate type declared in the specification, because that cannot tell us
all of the overriding needed.)

      generic
          type Foo is tagged private;
      package Gen is
          type Foolike is new Foo with null record;
      end Gen;

      package body Gen is
          type New_Foo is new Foolike with private;
          procedure Some_Operation (A : New_Foo); --??
      end Gen;

      type Bar is tagged ...;
      function Some_Operation (A : Bar);

      package New_Gen is new Gen(Bar);

Some_Operation for New_Foo is overriding and must be replaced in the tag for
New_Foo. But how is an implementation supposed to figure that out? It cannot
know whether Foo has a primitive operation Some_Operation.

This could be "solved" by declaring Some_Operation to be not overriding. But
that would violate the principle that a generic works the same as a
non-generic. (We certainly aren't going to declare this as non-overriding
outside of a generic, that would be a gratuitous incompatibility.) Moreover,
there isn't any way I can think of to create this tag at runtime (short of
including the entire Ada symboltable and code in the program, which isn't
remotely practical). Because you'd have to pass the name and parameter and
result profile with every slot in order to figure out any if there is any
overriding. (Usually we assign slot numbers to these, but in this case
that's not possible.)

This gets even more interesting when there is a package spec in the body:

    package body Gen is
       package Nested is
          type New_Foo is new Foolike with private;
          procedure Some_Operation (A : New_Foo); --??
       end Nested;
    end Gen;

Here, Some_Operation is clearly a primitive of New_Foo. How do we assign a
slot number? It might override something that comes from the formal, or it
might not.

So I'm certain that any relaxation of the rule would have to disallow
anything that depended on a formal in any way. (Direct dependence is not
enough.)

I haven't been able to decide if derivations from unrelated types (such as
"Controlled") are a problem or not. Clearly, you could use the same
techniques that you use for non-generic types. The problem (if there is one)
would occur if you need any local data space for the wrappers. This I don't
really know.

At the meeting, we discussed the fact that the wrappers probably would need
a runtime data structure (linked through the dynamic stack, perhaps, or
perhaps on the finalization chain) to find the appropriate display or static
link. Presuming that implementers sign up for that overhead (which is an
open question to me, it seems significant, but at least not distributed),
then that mechanism would provide a mechanism for finding any data needed.
So on that basis, it seems like it *might* be possible to implement. (Of
course, generating the wrappers would be a big problem because of the
generic parameter issue mentioned previously. But the question is that is
would be possible.)

So I'd probably not oppose strenuously a rule like:

      A type extension shall not be declared in a generic body if the parent
      type is descended from a formal type of a generic.

(Note that we have to worry about nested and child cases here, too. It
doesn't matter whose formal it is, we don't want to be dependent on it. But
we don't want this to apply to types declared in instances, so I'm not sure
if the above wording is right. Perhaps we need to say something about "the
generic or its ancestors".)

P.S. I presume that we'll attach this discussion to the AI? I don't want to
have to write this note again!!!

-------------------
 From Tuck to Randy and then his reply again (3/31/04):

...

 >> Since we disallow use throughout the generic body, I think this handles
 >> nested generics and subunits (since they are "plugged" into their stub
 >> prior to legality checks).  Children seem like a problem as you say,
 >> since their bodies are not considered nested within the ancestor.
 >> The "ancestor" of a generic is not always well defined, so
 >> perhaps the following:
 >>
 >>    Within the body of a generic unit, or the body of any of its descendant
 >>    library units, a tagged type shall not be declared as a descendant
 >>    of a formal type of the generic unit.
 >>
 >> This hopefully covers interface types as well.


I think this works.

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

From: Randy Brukardt
Sent: Friday, April 2, 2004  9:24 PM

Unfortunately, I've thought of another case where there is trouble creating
a tag in the body without knowing the actual types involved. Consider the
following:

    type Base is tagged ...
    procedure Proc (Obj : in out Base; Arg : in Integer); -- (1)

    subtype Short_String is String (1..10);

    generic
        type Frob is private;
    package Gen2 is
        ...
    end Gen2;

    package body Gen2 is
        type Der is new Base with ...;
        procedure Proc (Obj : in out Der; Arg : in Frob); --(2)
        ...
    end Gen2;

    package Short is new Gen2 (Short_String);
    package Int is new Gen2 (Integer);

In Short (1) and (2) have different profiles, and thus overload each other.
Therefore (2) gets a new slot (which can be calculated at compile-time,
given the above rule).

In Int, however, (2) overrides (1). That means (2) is supposed to get the
slot of (1).

In simple cases like this one, it probably would be possible to figure out
the slots by some sort of run-time tag modification. If there were multiple
such parameters, though, it could get pretty messy.

There also is a practical problem in our implementation. The parameter
passing implementation of Arg in (1) would be copy-in; while for Arg in (2)
it would be by-reference with the copy made for by-copy types at the call
site. Thus, if the wrapper for (2) was just stuck into the slot for (1), it
would have the wrong parameter passing code. Not good.

I'd suggest some sort of rule to fix this problem, but I can't think of
anything off-hand that doesn't throw the baby out with the bathwater. The
easy rule (the tagged type cannot have any primitives which depend on
generic formals) would prevent pretty much everything useful. And for types
like Controlled, it doesn't matter anyway, since the base type doesn't have
any operations that could cause problems.

But a rule that only eliminated problem cases would have to talk about the
intersection of possible profiles of all of the primitives, which seems
awful to describe and implement. Something like "Within the body...., a type
extension is illegal if a primitive operation of the type has one or more
operands which depend on a formal type of a generic, and the primitive could
override another primitive of the type in any possible instantiation of the
generic." (along with the previous restriction, of course).

I think this would still allow containers and Controlled in the bodies of
generics (presuming the containers were derived directly from Controlled),
but would avoid the problem cases.

Alternatively, we could simply say that such "overrides" don't override in a
generic body; but of course, that would mean that making a unit generic
could change its semantics. I don't like that much (and I'd think that
template implementations would like it less).

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

From: Robert I. Eachus
Sent: Friday, April 2, 2004  10:08 PM

I guess I see the problem, but I don't see it.  The problem occurs only
if there is a call inside the generic:

Proc(Some_Der, N); -- where N is of type Integer.

In the first instance Short, this call goes to the (derived) Proc
declared inside Gen2.  Your assumption in the Int case is that this call
should go to the  explicitly declared Proc.  But I don't see how it
can.  The only visible Proc inside the generic with an Integer parameter
is the implicitly declared one.

If Der and Proc were declared in the generic package spec, then there
could be external calls where the overriding must be recognized.  But
that happens only if the overriding is in the spec, which is not the
case in question here.

Now if Der was declared in the spec, and there was an explicit Proc in
the body, that could cause a problem. However, I think a rule that said
that such an overriding was not visible outside the (generic) unit would
follow the principle of least surprise.  I think this is the weird case
Randy is worried about.  However, I think that it may be one where a
more general fix is needed.  Notice that a "normal" overriding in the
body of a generic is fine.  It is a visible overriding inside the
generic as well as externally.  The compiler knows that it is an
overriding and can deal with it accordingly.  In this "accidental"
overriding case, only if the author of both the generic body and of the
instantiation is the same  (Ada language lawyer) programmer, would an
overriding visible (only) outside the generic be anything other than
surprising.

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

From: Randy Brukardt
Sent: Friday, April 2, 2004  11:27 PM

No, the problem also occurs when there is a dispatching call on Base'Class.
Which Proc gets calls for an object of Der? That call doesn't have to be
inside of the generic; any class-wide call will exhibit the difference in
behavior.

Note that the use of overridding indicators would show the problem, as
neither "overriding" nor "not overriding" would be legal on Proc
(assume-the-worst in a generic body). But they wouldn't help...

In any case, I'm mostly concerned about the implementation effects on an
implementation that tries to share bodies. If there is "conditional"
overriding in the body, sharing is going to be very hard or impossible. And
since none of this is visible in the spec (we're only discussing 3.9.1(4),
which only applies to types completely declared in the body), there can be
no body-agnostic sharing in such a case.

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

From: Tucker Taft
Sent: Saturday, April 3, 2004  7:41 AM

> Unfortunately, I've thought of another case where there is trouble creating
> a tag in the body without knowing the actual types involved. ...

I think we would want to treat this analogously to the
situation where a type has a private primitive.  It's slot
is not reused on a type extension even if a primitive with an equivalent
profile is declared outside the scope of the private
primitive.  Instead, the new primitive gets a new slot.

In this case, I would say that in a generic body, if a parameter's
types might be different in some instances, then the primitive
gets a new slot in all instances.  I can't imagine any
value to having overriding vs. overloading depend on the
actuals, since no code outside the instance is going to be
able to name this type.  Yes it could see such an object
at run-time via 'Class, but I don't think that argues
for making the overriding vs. overloading instance-specific.

In the example you give below, the declaration of
"Proc" (2) in the generic body would not override the
inherited primitive "Proc" (1), and in fact wouldn't even
be a primitive.  If Der were declared in a nested
package spec, then the new Proc (2) would be a new primitive
of Der and get a new slot, even if Frob turned out to be
Integer.

> ... Consider the
> following:
>
>     type Base is tagged ...
>     procedure Proc (Obj : in out Base; Arg : in Integer); -- (1)
>
>     subtype Short_String is String (1..10);
>
>     generic
>         type Frob is private;
>     package Gen2 is
>         ...
>     end Gen2;
>
>     package body Gen2 is
>         type Der is new Base with ...;
>         procedure Proc (Obj : in out Der; Arg : in Frob); --(2)
>         ...
>     end Gen2;
>
>     package Short is new Gen2 (Short_String);
>     package Int is new Gen2 (Integer);
>
> In Short (1) and (2) have different profiles, and thus overload each other.
> Therefore (2) gets a new slot (which can be calculated at compile-time,
> given the above rule).
>
> In Int, however, (2) overrides (1). That means (2) is supposed to get the
> slot of (1).

Naaah.  Overriding should be something that is decided before
instantiation for generic bodies.

> In simple cases like this one, it probably would be possible to figure out
> the slots by some sort of run-time tag modification. If there were multiple
> such parameters, though, it could get pretty messy.

Blech.  I can't imagine any value to allowing overriding vs.
overloading to depend on the actual when in a generic body.

> ...
> Alternatively, we could simply say that such "overrides" don't override in a
> generic body; but of course, that would mean that making a unit generic
> could change its semantics.

You aren't just making the unit generic (i.e. wrapping the
word "generic" around it).  You are also taking one of the
types and making it a formal type.  To me that implies you
want the behavior to be "generic" across changes in such
a type.  You don't want it to suddenly have a differnt
behavior if the type happens to match some parameter type
of some primitive of some tagged type that happens to be
used inside the body.  In fact, if you did that, you would
create an interesting capability to do a run-time test for
(untagged) type identity, which is *not* something we have
ever provided in a generic, and I don't think we want to
start now!

> ... I don't like that much (and I'd think that
> template implementations would like it less).

Having a template implementation doesn't change
my view.  Overriding vs. overloading within the body
should be decided when you compile the generic, not
at the time of the instance.

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

From: Randy Brukardt
Sent: Saturday, April 3, 2004  4:46 PM

Tucker said, replying to me:

> > ...
> > Alternatively, we could simply say that such "overrides" don't override in a
> > generic body; but of course, that would mean that making a unit generic
> > could change its semantics.
>
> You aren't just making the unit generic (i.e. wrapping the
> word "generic" around it).  You are also taking one of the
> types and making it a formal type.  To me that implies you
> want the behavior to be "generic" across changes in such
> a type.  You don't want it to suddenly have a differnt
> behavior if the type happens to match some parameter type
> of some primitive of some tagged type that happens to be
> used inside the body.  In fact, if you did that, you would
> create an interesting capability to do a run-time test for
> (untagged) type identity, which is *not* something we have
> ever provided in a generic, and I don't think we want to
> start now!

OK, that seems like a good argument.

> > ... I don't like that much (and I'd think that
> > template implementations would like it less).
>
> Having a template implementation doesn't change
> my view.  Overriding vs. overloading within the body
> should be decided when you compile the generic, not
> at the time of the instance.

Of course, this means further futzing with the overriding rules. That
doesn't seem too pleasant, either. But the goal (being able to use
controlled types and containers in generic bodies) seems worthwhile.

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

From: Tucker Taft
Sent: Sunday, April 4, 2004  1:26 PM

I'm not sure that's true (though you may have something specific
in mind).  The rules I can find generally say that everything
relating to overloading and overriding is decided when you
compile the generic body.  Visible part of instances are
different, but the body seems pretty uniformly to rely on
overloading/overriding decisions made when the generic body
is compiled.  E.g. 8.3(13), 8.3(26/1), 12.3(14), 12.3(18).

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

From: Pascal Leroy
Sent: Monday, April 5, 2004  6:36 AM

But this is not new futzing.  As Tuck pointed out, declarations in the
body should work like declarations in the private part, and you probably
do quite a bit of futzing already to implement 12.3(18).  So you have a
firm foundation on which to build even more futzing.

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

From: Randy Brukardt
Sent: Tuesday, April 6, 2004  4:22 PM

No, I was thinking about in the Standard, not in our compiler. But you and
Tucker have pointed out 12.3(18), so the Standard is already correct on this
point. No futzing needed. Some implementers might need to futz if they don't
follow 12.3(18) properly, but that's not a problem for this group to worry
about.

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

From: Robert I. Eachus
Sent: Monday, April 5, 2004  1:46 AM

>No, the problem also occurs when there is a dispatching call on Base'Class.
>Which Proc gets calls for an object of Der? That call doesn't have to be
>inside of the generic; any class-wide call will exhibit the difference in
>behavior.

My head is starting to hurt.  Right now, Der is declared nested in a
generic package body.  You are proposing to assign it to a "global"
object of type Base'Class, so that it can be operated on outside the
generic.  But there is no way to do that directly, you have to have an
access type declared access (all) Base'Class.  Now you can use an
allocator for this access type inside the generic, and assign its value
to an object of the access type.  See RM 3.10.2(14&15).

So it seems to me that it would be much easier to do any required magic
as a part of that allocator.  An allocator for a class-wide type seems
pretty magic to me anyway.  In fact, in exactly the case we are
discussing, the magic rules in  3.10.2(20) and 3.9.1(3) seem to combine
to allow, for example, type extension in a generic body, the generic
body can be instantiated inside some procedure, and assignment of a
value created by allocator to an access object in the procedure body
would be legal.  In that case, there could be for example a generic
formal subprogram, that gets inherited in the generic, and must be
dispatched to.

So I guess to me it seems silly to distribute overhead to any case other
than allocators in package bodies for class-wide access types which
allocate an object of a tagged type declared in the generic package
body.   Furthermore since the painful cases require that the allocator
be in the sequence of statements for such a generic package, why not
just outlaw it and be done.  (If you have an object of the class-wide
access type in the package body, with an initial value, that object can
only be seen within the package body.  It is assignments in the sequence
of statements at the end of the generic package body that can cause
problems, and it seems to me to be simple enough to treat that scope as
statically deeper than the rest of the generic package.  I have created
packages with a sequence of statements at the end, I have even done it
with generic packages.  But assignments outside the generic--of an
object of a type created in the generic BODY?  Come on...

>Note that the use of overridding indicators would show the problem, as
>neither "overriding" nor "not overriding" would be legal on Proc
>(assume-the-worst in a generic body). But they wouldn't help...
>
>In any case, I'm mostly concerned about the implementation effects on an
>implementation that tries to share bodies. If there is "conditional"
>overriding in the body, sharing is going to be very hard or impossible. And
>since none of this is visible in the spec (we're only discussing 3.9.1(4),
>which only applies to types completely declared in the body), there can be
>no body-agnostic sharing in such a case.
>
I don't know what the "best" way to deal with this is.  But I think
Tucker and I are leaning the same way--allow the useful functionality
even if we have to keep some restrictions.  Allowing derived types in
generic package bodies while not allowing assignment of access values to
objects of the derived type outside the generic seems like a very
livable restriction.

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

From: Randy Brukardt
Sent: Monday, April 5, 2004  1:45 PM

> My head is starting to hurt.  Right now, Der is declared nested in a
> generic package body.  You are proposing to assign it to a "global"
> object of type Base'Class, so that it can be operated on outside the
> generic.

Not at all. First of all, 'Der' isn't neccessarily nested; it's in the body,
but could be at library level depending on the instantiation. But in any
case, 'leaking' the object out isn't necessary.

All you need to do is call a class-wide routine on the base class with a
parameter of type Der. If that routine then does a dispatching call on Proc,
you can tell whether it's been overridden or not.

In any case, Tucker's argument seems strong enough to avoid the issue in the
first place, by simply saying that such things are not overriding. *That* we
can implement without trouble in a shared implementation.

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

From: Stephen W. Baird
Sent: Friday, April 30, 2004  3:50 PM

AI-344 requires dynamic tag allocation in some cases. This will be something
new for some (most?) implementations. This is implementable, but this
consequence of the AI has not been discussed by the ARG.

Consider this example:

  procedure Outer is
    type Float_Vector is array (Positive range <>) of Float;
    type Integer_Vector is array (Positive range <>) of Integer;
    Test_Failed : exception;

    type Root is tagged null record;
    type Ref is access all Root'Class;
    P1, P2 : Ref;

    procedure Inner (N : Natural := 3) is
	type Extension is new Root with -- legal by AI-344
	    record
                F1 : Integer_Vector (1 .. N) := (others => 0);
                F2 : Float_Vector (N .. 10) := (others => 0.0);
	    end record;
        Local : aliased Extension;
    begin
        if P1 = null then
            P1 := Local'Unchecked_Access;
            Inner (N + 1);
        elsif P2 = null then
            P2 := Local'Unchecked_Access;
            Inner (N + 1);
        elsif P1.all = P2.all then
            raise Test_Failed;
        end if;
    end Inner;
  begin
    Inner;
  end Outer;

It seems clear that the "P1.all = P2.all" test would be problematic if
P1.all'Tag = P2.all'Tag. Those two objects must have distinct tags, and
AI-344 probably should state this explicitly.

This is not a problem with Unchecked_Access. It would be possible, albeit
somewhat more complicated, to construct an instance of the problem which
does not use Unchecked_Access (e.g. using tasks).

I believe that the Ada95 designers originally intended that multiple
elaborations of a tagged type declaration (e.g. one declared inside of a
subprogram) might share the same statically allocated tag value, or they might
have distinct dynamically allocated tags; either implementation should work.

This is no longer true in the face of AI-344 (although it remains true for
types whose legality does not depend on AI-344).

A Tag value may outlive its corresponding tagged type. Implementations must
be careful to avoid both dangling references and storage leaks in this case.
Typically this means that creating a dynamically allocated Tag value cannot
involve any kind of dynamic storage allocation. This issue already exists
in Ada95, but only for implementations which choose to allocate Tag values
dynamically. AI-344 forces everyone into that category, at least in some cases.

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

From: Gary Dismukes
Sent: Friday, April 30, 2004  6:53 PM

Steve Baird wrote:
> AI-344 requires dynamic tag allocation in some cases. This will be something
> new for some (most?) implementations. This is implementable, but this
> consequence of the AI has not been discussed by the ARG.

Yuck, I think that the prospect of requiring dynamic tag allocation
would be enough to kill this AI.

> It seems clear that the "P1.all = P2.all" test would be problematic if
> P1.all'Tag = P2.all'Tag. Those two objects must have distinct tags, and
> AI-344 probably should state this explicitly.

This seems pretty pathological.  You do have a devious mind Steve!
I would almost rather define such usage as erroneous rather than bite
the bullet of implementing dynamic tags just to handle such pathologies.

> This is not a problem with Unchecked_Access. It would be possible, albeit
> somewhat more complicated, to construct an instance of the problem which
> does not use Unchecked_Access (e.g. using tasks).

OK, but I can't help but wonder how much of a pathology these other
possible cases are.  Since I'm not sure what your other examples
are perhaps you'll have to show the details.  Somehow I suspect
they're pretty ugly.

> A Tag value may outlive its corresponding tagged type. Implementations must
> be careful to avoid both dangling references and storage leaks in this case.
> Typically this means that creating a dynamically allocated Tag value cannot
> involve any kind of dynamic storage allocation. This issue already exists
> in Ada95, but only for implementations which choose to allocate Tag values
> dynamically. AI-344 forces everyone into that category, at least in some cases.

If that's a necessary implication of the AI, then my guess is that will be
a significant nail in its coffin.  Which side are you on anyway Steve? ;-)

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

From: Robert Dewar
Sent: Friday, April 30, 2004  7:01 PM

> Yuck, I think that the prospect of requiring dynamic tag allocation
> would be enough to kill this AI.

I agree!

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

From: Tucker Taft
Sent: Friday, April 30, 2004  10:32 PM

The canonical implementation model for nested
type extensions is that each object carries a
static link, or a pointer to a display.  That implies
to me that for operations with multiple controlling
parameters, an additional check needs to be performed
*after* the dispatch if you arrive in an operation which
actually makes use of such a static link to make sure the static links
or displays are the same.  If they don't agree, then an
exception should be raised just as though there had
been a tag mismatch.

This seems like a relatively low overhead, since operations
with multiple controlling operands are relatively rare,
and the overhead would only be incurred when reaching
such an operation on a nested type, meaning it is
not a distributed overhead.

Note that some implementations
may create "wrappers" for dispatching operations of
nested extensions to fetch the static link/display
pointer and then call the "real" body with the static
link/display in the "normal" register or per-task
display used for that.  This wrapper would be the
natural place to perform this additional check.

Hence, I see no need for a "dynamic" tag, nor
any need for distributed overhead.  It does mean,
however, that comparing tags may not be a foolproof
way of knowing whether the tag-check will fail
when calling an operation with multiple controlling
operands.  We might want to add some way of doing
such a check, which might be by having another
attribute which would return some kind of "'Extended_Tag"
which would be a concatenation of the tag and
the static link/display-ptr if present.  This would
probably require an additional implicit dispatching
operation, analogous to the one needed to implement
'Size on a class-wide object.  I don't think we want
to change 'Tag itself to have this additional overhead,
though it probably wouldn't be that big of a deal
either way.

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

From: Stephen W. Baird
Sent: Friday, April 30, 2004  11:28 PM

dismukes@gnat.com (Gary Dismukes) wrote on 04/30/2004 04:52:33 PM:
> Which side are you on anyway Steve?

I strongly feel that it must be ok to instantiate AI-302's various
container generics anywhere, e.g. inside of a subprogram body which is
inside of a generic body.

I also believe that the implementations of these container generics will
need to extend Ada.Finalization.[Limited_]Controlled.

As the language stands today, these requirements cannot both be satisfied.

Because of this, I support AI-344 (including loosening up 3.9.1(4)).

The Ada.Generic_Finalization proposal that I described a while back (after
the Vienna meeting, I think) could also be used to solve this problem,
although it pertains only to controlled types, not tagged types in
general.

If AI-344 is shot down, perhaps this proposal should be revisited (feel
free to interpret this as a reason to support AI-344).

P.S. Note that "dynamic tag allocation" might not be as difficult to implement
as it sounds. Consider implementing the type Ada.Tags.Tag as a two-field record
- a pointer to a statically allocated data structure (e.g. a dispatch table)
and a uniquifying integer value that could be initialized by calling some name
allocator (there are cheaper ways). Ada.Tags.External_Tag's name for a type
might be pretty much what it is today, except with the image of this extra
integer tacked on the end. Ada.Tags.Internal_Tag could strip an integer off the
end of its argument to get the unique_id of its result and then use the same
statically-initialized mapping that is used today to get the dispatch table
address. A runtime check of the validity of this result might or might not be
required. Some details remain (you might want to special case types whose
legality does not depend on AI-344, setting the unique_id field to a null value
and omitting it from the External_Tag string), but the point is that this need
not involve anything as complicated as dynamic storage allocation.

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

From: Robert Dewar
Sent: Monday, May  3, 2004  6:07 AM

This sounds like a major incompatible earthquake at the implementation
and actual usage level. It would change the format of all tagged types
if I understand you correctly, and I would regard that as out of the
question. Am I missing something?

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

From: Tucker Taft
Sent: Monday, May  3, 2004   8:19 AM

> P.S. Note that "dynamic tag allocation" might not be as difficult to
> implement as it sounds. Consider implementing
> the type Ada.Tags.Tag as a two-field record ...

This is similar to what I ws proposing.  Since the canonical
implementation model requires that a static link/display pointer
be added as part of extending a type in a more nested scope,
the pair made up of the tag and the static link/display pointer
could provide this "dynamic" tag.  As I suggested,
the dynamic part of the tag need not be checked until
you get to a nested overriding of a dispatching operation
with more than one controlling operand.

It is a question whether 'Tag should be changed to return
this dynamic part, or whether a separate 'Extended_Tag
or equivalent should be provided to get both.  In any
case, there probably needs to be an implicit dispatching
operation, analogous to that supporting 'Size, which
returns the 'Extended_Tag pair [tag, static-link].

This pair is similar to what some implementations use
to represent an access-to-subprogram value when the access
type is declared in a nested scope.

I agree with Robert that we don't want a solution that
changes the representation of existing tagged types.
I believe the approach I suggested imposes minimal
overhead on existing tagged types, because it only
requires one additional implicit dispatching op which
returns [tag, null] by default.  It could be made
even simpler by having it be a procedure which
updates the second half of such a two-word "extended"
tag.  Then it could be a "null" procedure by default.

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

From: Robert Dewar
Sent: Monday, May  3, 2004  8:34 AM

Sounds reasonable to me

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

From: Stephen W. Baird
Sent: Monday, May  3, 2004  12:16 PM

> I agree with Robert that we don't want a solution that
> changes the representation of existing tagged types.

I agree.
Modifying 3.9.2(16) makes a lot more sense than changing the
implementation of Ada.Tags.Tag.

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

From: Tucker Taft
Sent: Monday, May  3, 2004  12:55 PM

Hence, the wording for 3.9.2(16) should be augmented to say:

   If there is more than one dynamically tagged controlling operand,
   a check is made that they all have the same tag{, and that they
   all are associated with the same type elaboration}.

An implementation note would indicate a possible implementation
approach for this which incurs no distributed (time) overhead.

We might also add to 3.9 a declaration of an Extended_Tag type in
Ada.Tags, and an Extended_Tag attribute of subtypes and
class-wide objects that uniquely identifies a particular elaboration
of a tagged type among types that exist concurrently.

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

From: Tucker Taft
Sent: Monday, May  3, 2004  12:28 PM

[Editor's Note: This note seems to be about a private discussion; none of
the previous messages are available here. The topic seems important enough to
include here.]

Stephen W Baird wrote:

> You make a good point about not changing the streamed format of existing
> types. I agree that this is important.
>
>>I suppose we could require types with ancestors at
>>an outer level to add something distinguishing them, so
>>long as all types with no such ancestors can continue
>>to use the same streamed representation as they do today.
>
> I think we need something like this. Regardless of how frequently it comes
> up, streaming rules need to be well defined.

Well, we should look at AI-279 before getting too concerned
about this case.  We say it is erroneous to use T'Class'Input
if the tag is for a type that hasn't been frozen or doesn't
exist.  I don't see it to be necessary to provide much stronger
protections against the case where there are multiple types
the tag represents.

>>I just hate to devote too much implementor effort to this issue.
>
> I agree, although I feel that this AI (or some mechanism to allow
> AI-302's generics to be instantiated most anywhere) is very important.
> If we have to introduce some complexity, that does not mean we should kill
> the AI.

True, but we shouldn't introduce significant complexity just to support
a pathological case.  I would claim it borders on pathological to
have simultaneously instances of the "same" type from different
dynamic scopes, and then try to stream them.

One possibility would be to require that nested type extensions
dynamically enter their tag into the tag "table" used by Internal_Tag,
and restore any entry previously there on the way back out.  But that
would require that each task have its own tag table.

A simpler approach might be to say that T'Class'Output and T'Class'Input
only work for extensions declared at the same level as T.  They
would raise Constraint_Error otherwise.  That would be upward compatible
and safe, though admittedly somewhat less flexible.  Then all we would
need to know is the static nesting level associated with a given tag,
which might want to be an operation in Ada.Tags defined on type Tag
(though perhaps it should be a "private" operation).

In any case, it seems this issue should be considered in the context
of AI-279, and we shouldn't go overboard if we concluded erroneousness
was acceptable in certain cases already.

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

From: Jean-Pierre Rosen
Sent: Tuesday, May  4, 2004  3:03 PM

Not being writing a compiler, I can't comment on the dynamic tags and all that
stuff. But I'm puzzled by the ratio complication/usefulness of the feature.

After all, AFAIK, no other OO language allows defining classes nested in
a subprogram.

The only case where this would be useful seems to be to declare nested
controlled types. If others agree on this, then let's just solve this
problem.

A possible solution would be to declare:
   for T'Finalization use ...;
etc.
(of course, Ada.Finalization.Controlled would be declared this way, so
it would be a compatible change).

I remember Tuck saying that this solution was considered for Ada 95; I
don't remember exactly why it was discarded, but I think not for reasons
that could not be revisited.

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

From: Tucker Taft
Sent: Wednesday, May  5, 2004  2:53 AM

> After all, AFAIK, no other OO language allows defining classes nested in
> a subprogram.

That's actually not true.  Java allows nested classes,
and they can be defined essentialy anywhere, including
inside a method (aka subprogram).  The syntax is a bit weird,
since the class extension occurs as a side effect of writing
a constructor followed by an open brace ("{").  It is actually
used fairly heavily, as a way to create a short-lived call-back.

I don't know about C#, but Java and C# are matching each other
feature for feature, so I suspect if C# doesn't have it now,
it will soon. ;-)

> The only case where this would be useful seems to be to declare nested
> controlled types. If others agree on this, then let's just solve this
> problem.

That isn't the only problem.  There are three built-in abstractions
that use type extension -- controlled types, storage pools,
and streams.  All of these are the kind of thing you might
want to extend in a generic, especially one that is providing
a "container" abstraction.  As soon as you do that, you are
stuck with a generic that cannot be instantiated at a nested
level.

And users who have designed their own tagged types are
essentially precluded from extending them inside generics,
unless they want the generic to be a library-level only
generic.

>
> A possible solution would be to declare:
>    for T'Finalization use ...;
> etc.
> (of course, Ada.Finalization.Controlled would be declared this way, so
> it would be a compatible change).
>
> I remember Tuck saying that this solution was considered for Ada 95; I
> don't remember exactly why it was discarded, but I think not for reasons
> that could not be revisited.

Finalization is a massive can of worms.  I suspect most implementors
would rather implement nested type extensions than redo finalization
in a significantly different manner.  And my sense is that many
of the challenges associated with nested type extension might
come up when supporting nested finalization.  But the programmer
wouldn't get as much benefit from the implementor's effort.

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

From: Stephen W. Baird
Sent: Friday, May  7, 2004  5:21 PM

> Hence, the wording for 3.9.2(16) should be augmented to say:
>
>    If there is more than one dynamically tagged controlling operand,
>    a check is made that they all have the same tag{, and that they
>    all are associated with the same type elaboration}.
>

Are similar changes needed in order to catch bad type conversions?

4.6(42) states:
   If the operand is class-wide, a check is made that the tag of the
operand identifies a (specific) type that is covered by or descended from
the target type.

Consider the type conversion in the example below.
If the implementation allocates tags statically, then Param'Tag will equal
Extension'Tag and this check will (incorrectly)  pass.

I think that  5.2(10)  is ok as it stands.
Once the conversion problem is fixed, the subtype conversion of 5.2(11)
will perform the needed check.

Membership tests may need work.

4.5.2(30) states:
   ... and, if the the type of the simple_expression is class-wide, the
value has a tag that identifies a type covered by the tested type.

Consider the membership test in the example below.
If the implementation allocates tags statically, then Param'Tag will equal
Extension'Tag and the membership test will (incorrectly) yield True.

--------

procedure Outer is
  Test_Failed : exception;

  type Root is tagged null record;

  N : Natural := 0;

  procedure Inner (Param : in out Root'Class) is
    type Extension is new Root with
      record
        F : String (1 .. N) := (others => '?');
      end record;

    Local : Extension;
  begin
    if N = 0 then
      N := 100;
      Inner (Local);

    elsif Param in Extension'Class then
      raise Test_Failed;

    else
      begin
        declare
          Converted : Extension renames Extension (Param);
        begin
          raise Test_Failed;
        end;
      exception
        when Constraint_Error =>
          null;
      end;
    end if;
  end Inner;

begin
  declare
    Root_Var : Root;
  begin
    Inner (Root_Var);
  end;
end Outer;

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

From: Tucker Taft
Sent: Friday, May  7, 2004  6:02 PM

If we introduce the notion of an "extended tag" then we
can probably change these all to say "an (extended) tag that
identifies a type...", or in the case of 3.9.2(16) which
prompted this, "... they all have the same (extended) tag."

I'm not sure whether parenthesization helps or hurts...

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

From: Stephen W. Baird
Sent: Monday, May 10, 2004  1:45 PM

I'd like to revisit the idea of solving the problems we've been discussing
by changing the implementation of Ada.Tags.Tag to include a disambiguating
component.

I completely agree that we don't want to change the size or layout of
existing tagged types.

For types which are legal without  AI-344, this disambiguating component
would always have some distinguished null value.

Thus, the value would not have to be stored and the existing size/layout
could be preserved.

The statically allocated data structure that a Tag value currently
references (typically a dispatch table and a few other odds and ends)
could include an  "I have a shorter lifetime than my ultimate ancestor"
flag.

Pseudo-code for evaluation of R'Tag could be something like:
     if R.Static_Tag.all.Is_An_Ai344_Type then
        return Ada.Tags.Tag'(Static_Tag => R.Static_Tag, Disambiguator =>
R.Disambiguator);
    else
        return Ada.Tags.Tag'(Static_Tag => R.Static_Tag, Disambiguator =>
Nil_Value);
    end if;

The Disambiguator field might always reside at a fixed offset, or one of
the "odds and ends" mentioned above might be the offset of this field.

Types resulting from two elaborations of one tagged type declaration would
be *required*  to  have distinct tags only if
    1) The type declaration in question is a nested extension or a
descendant thereof (i.e. it would be illegal without AI-344)
and
    2) The two types are descendants of the same elaboration of the
declaration of their ultimate ancestor.
and
    3) The lifetimes of the two types (dynamically) overlap.

If you call a procedure which declares an AI-344  type and it then calls
itself, those two elaborations of the tagged type declaration must yield
distinct tags.
On the other hand, if you call the procedure, it returns, and then  you
call it again, those two elaborations might (or might not) yield equal
tags.
This would allow using static links and the like as disambiguating values.

The interaction between this and the last sentence of 3.9(4) would need to
be worked out.

This change would break code that makes use of Ada.Tags.Tag'Size for
things like

       type T is tagged record F1, F2 : Integer; end record;
       pragma Assert (T'Size = 2* Integer'Size + Ada.Tags.Tag'Size);

; would this be acceptable?

I'm still not sure that changing Ada.Tags.Tag is a good idea, but I don't
think it is as bad as we thought at first.

If we did go with this approach, would the current wording of  4.6(42) and
4.5.2(30) be ok? Is it already clear, for example,
that two elaborations of one tagged type declaration do not cover each
other and are not descendants of each other?
The current wording of 3.9.2(16) would certainly be ok.

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

From: Tucker Taft
Sent: Monday, May 10, 2004  1:53 PM

I suggested we leave Ada.Tags.Tag as is, and add a new
type and attribute, Extended_Tag.  Can you comment on that
alternative?  You include the mail I sent, but don't make
any mention of it in your note.  I believe it could solve the same problem
with less disruption.

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

From: Stephen W. Baird
Sent: Monday, May 10, 2004  3:35 PM

I agree that the Extended_Tag approach would work.

I think it would be better if we did not have to make the distinction
between tags and extended tags user-visible.
It hairs up the language specification, it introduces complexity for users
(users now have to figure
out which kind of tag they want in various contexts), and it just feels
like a grafted-on solution which forces
users to be more aware of the implementation than is necessary.

Why do users want/need to be aware of this distinction?

I think that if the language were being designed from scratch, it is very
unlikely that we would end up with two kinds of tags (do you agree?).
The language is not being designed from scratch and if compatibility
considerations dictate a language design which looks like it was developed
in two stages, then so be it.
If, however, we have a more seamless alternative, then we ought to at
least consider it.

If the costs associated with changing Ada.Tags.Tag still seem too high, I
would support Extended_Tags.

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

From: Robert A. Duff
Sent: Monday, May 10, 2004  4:52 PM

I tend to agree with Steve Baird, here.  That is, make Ada.Tags.Tag work
as if AI-344 had been there all along.  Steve outlines an implementation
approach that would not disturb existing tagged-type layout.  One would
have to go to some trouble to find an incompatible case -- or am I
missing something?

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

From: Randy Brukardt
Sent: Monday, May 10, 2004  5:26 PM

> I suggested we leave Ada.Tags.Tag as is, and add a new
> type and attribute, Extended_Tag.  Can you comment on that
> alternative?  You include the mail I sent, but don't make
> any mention of it in your note.  I believe it could solve the same problem
> with less disruption.

I agree with Steve that adding a second kind of tag is ugly. I'm surprised
that you'd even suggest such a thing, given the usual emphesis that you put
on avoiding grafted-on solutions.

In any case, what ever is done here should be integrated with AI-279. It
would be silly to expend a lot of effort on these cases here, and not use
that effort to eliminate erroneousness from AI-279. (I think that is pretty
much required if we're going to allow nested derived tagged types. Regular
nested tagged types are so rare and useless that we don't need to care
whether they stream properly; but derived types are much more likely to be
streamed. Moreover, the type is much less likely to exist if they are
streamed, so the erroneousness is much more likely to occur.)

If we required dynamic tag allocation and a dynamic, stack-based lookup
scheme for nested tagged types, AI-279 can be defined without any
erroneousness -- if the type doesn't "exist", Internal_Tag raises Tag_Error.
Period. But of course this has compatibility issues -- but only with nested
tagged types. Are these defined and streamed often enough to be worth
worrying about?

Steve's approach (of having an offset of a static link/display component in
the tag, set to null for library level types) seems clean enough.

If changing Tag'Size is not acceptable, I'd recommend defining
Ada.Tags.Tag_Type, and putting the existing routines of Ada.Tags in the
obsolecent features section, with the use of them erroneous for a prefix/tag
value that does not denote a library-level tagged type.

[If we're going to do that sort of major surgury, could we please figure out
a way to make constructors a-la T'Class'Input usable by users???]

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

From: Randy Brukardt
Sent: Monday, May 10, 2004  5:30 PM

> I tend to agree with Steve Baird, here.  That is, make Ada.Tags.Tag work
> as if AI-344 had been there all along.  Steve outlines an implementation
> approach that would not disturb existing tagged-type layout.  One would
> have to go to some trouble to find an incompatible case -- or am I
> missing something?

Objects of nested tagged types would stream differently. (One could avoid
that by making streaming of currently legal nested tagged types erroneous,
but that seems silly -- and also grafted-on.)

I also don't understand the model of "=" for tags here; it's not something
that would compose properly -- so it could cost a lot of work in many
compilers.

I'm not sure whether 'Size for a tag would have to change or not. The offset
scheme would seem to avoid that, but would put a lot of pain into "=".

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

From: Tucker Taft
Sent: Monday, May 10, 2004  5:37 PM

> I think it would be better if we did not have to make the distinction
> between tags and extended tags user-visible.

Ok.  I understand this point of view.  My problem with your earlier
response was that I couldn't tell whether you had understood the
extended-tag idea.  The key issue is whether there is any value
in maintaining the notion of a "static" tag in addition to the
more "dynamic" extended tag.  Clearly when it comes to I/O, it is
going to be challenging to figure out how to represent the
extended tag persistently.  Also, we have the notion of Expanded_Name,
which based on the current wording, clearly doesn't distinguish
particular levels.  Finally, the likelihood that there are multiple
elaborations of the *same* tagged type declaration in existence due to
recursion is quite small.  I hate to make all tag manipulations
have to pay an overhead for this.

I have been trying to come up with a solution that imposes no
distributed (time) overhead on programs that make no use of
nested extensions.  Perhaps it is not worth trying to preserve
the space or time performance of 'Tag, given how rarely it is used.

I think it would be nice at least to preserve the time performance
of the tag check on binary dispatching operations, and hence would
encourage implementors *not* to call an extended 'Tag attribute
to perform the check.  Doing a check on the "static" tag part
at the call-site, and then only comparing the "dynamic" part
if you reach a nested extension still seems like a good idea.


> It hairs up the language specification, it introduces complexity for users
> (users now have to figure
> out which kind of tag they want in various contexts), and it just feels
> like a grafted-on solution which forces
> users to be more aware of the implementation than is necessary.
>
> Why do users want/need to be aware of this distinction?

Good question.  I suppose in the presence of streaming of
class-wide types, they may need to face the issue of distinguishing
the "static" part versus the "dynamic" part of the tag.

I discussed limiting T'Class'Input and T'Class'Output to types that
are at the same accessibility level as T.  Any comment on that?
I think it will simplify the implementation significantly, and eliminate
various possible erroneous situations.  And it may be related
to this issue, one way or another ... ;-)

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

From: Robert I. Eachus
Sent: Monday, May 10, 2004  4:34 PM

> If we introduce the notion of an "extended tag" then we
> can probably change these all to say "an (extended) tag that
> identifies a type...", or in the case of 3.9.2(16) which
> prompted this, "... they all have the same (extended) tag."

I'm not sure that I am following the whole discussion correctly.  If, as
I understand it the problem is two dynamic instances of the same unit
constaining a tagged type declaration are the issue, then we are trying
to deal with a issue of broken implementations, not a language issue.

My model has always been that elaboration of a tagged type declaration
results in assignment of a _unique_ tag.  The easiest way to do this is
to have a protected counter.  Another method is to have the tag be a
pointer to the dispatch table for the type.  This works fine, since tag
values can be reused after the scope containing the declaration has been
left, at the same point as the memory would be reclaimed.  However, all
that is implementation issues, as is how multiple tasks or partitions
assign unique tags.  (I have always assumed that the identity of the
partition elaborating the type declaration is part of the tag, if
partitions don't have unique memory addresses.)

If an implementation wants to use static values associated with the
source code for most tags, that is an implementation detail--as long as
they deal with the recursive case correctly.  The method of dealing with
the recursive case in such a misguided implementation is not our
responsibility.

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

From: Robert Dewar
Sent: Monday, May 10, 2004  8:19 PM

> I completely agree that we don't want to change the size or layout of
> existing tagged types.

I also don't want to change the size of tags, this is just asking for
nasty incompatibilities. I think absolute upwards compatibility for
correct programs is essential. I don't mind exceptions being removed
in favor of sensible behavior, or illegal code being made legal in
some sensible way, but existing legal code that executes successfully
should not have to be molested to be compatible with the new standard.
No language bell/whistle is worth that.

So for example, I think it is fine to remove abstract operations
to that previously ambiguous expressions are now legal. But if a
program that is legal and executes correctly must be modified to
run under the new Ada even if no new feature is used, that to me
is unacceptable (it likelyh would mean that we would be reluctant
to implement the feature).

So I think you definitely need two tag types here.

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

From: Robert Dewar
Sent: Monday, May 10, 2004  8:20 PM

> I suggested we leave Ada.Tags.Tag as is, and add a new
> type and attribute, Extended_Tag.  Can you comment on that
> alternative?  You include the mail I sent, but don't make
> any mention of it in your note.  I believe it could solve the same problem
> with less disruption.

Yes, I like this approach.

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

From: Randy Brukardt
Sent: Friday, May 14, 2004  11:17 PM

Tucker wrote on Monday:

> I have been trying to come up with a solution that imposes no
> distributed (time) overhead on programs that make no use of
> nested extensions.  Perhaps it is not worth trying to preserve
> the space or time performance of 'Tag, given how rarely it is used.
>
> I think it would be nice at least to preserve the time performance
> of the tag check on binary dispatching operations, and hence would
> encourage implementors *not* to call an extended 'Tag attribute
> to perform the check.  Doing a check on the "static" tag part
> at the call-site, and then only comparing the "dynamic" part
> if you reach a nested extension still seems like a good idea.

Re-reading this mail as I've been filing it, I realized what I was imagining
as Steve's solution isn't quite the same. And since it meets almost all of
the requirements that people have set out, I thought I better describe it
more carefully.

In particular, the solution I'm proposing (A) does not change the size of a
tag; (B) allows tags to be statically allocated; (C) does not change the
layout of library-level tagged types; and (D) has minimal overhead for
library-level tagged types. (I refuse to consider non-derived nested tagged
types separately. They are vanishingly rare - why complicate things? But
they could be treated separately if you wanted to.)

I'm going to describe an implementation approach; I haven't tried to figure
out precisely what this means in RM terms (my hope is that it means
absolutely nothing, in that no RM wording needs to change).

The basic idea is that every tag includes a slot which contains the offset
of the dynamic link/display component of a tagged object. For library-level
types, this component offset would be zero (or some other value that cannot
be a legal component offset - zero usually works because the tag itself
lives there).

The only thing that needs to change in that case is "=" for tag checks. It
would be implemented like:

    function Check (A, B : <any tagged object>) return Boolean is
    begin
        if A(Tag_Offset) /= B(Tag_Offset) then -- Compare the tag values.
            return False;
        elsif A(Tag_Offset)(Link_Component) = 0 then
            return True;
        else
            return A(A(Tag_Offset)(Link_Component)) =
                   B(B(Tag_Offset)(Link_Component));
               -- Comparing the static links or display.
        end if;
    end Check;

We'd define External_Tag would need some indication of the nesting depth
(the number of such tags on the current call stack; this would be omitted
for the first one, which would cover virtually all real cases); Internal_Tag
would need to be able to look in the call stack for the correct item.
Tucker's alternative of banning T'Class'Output for types deeper than their
root would help, but you have the problem of recursive types for *any*
nested tagged types.

That is:

    A_Stream : ....;

    procedure Beauty (N : Natural := 3) is
	  type Nested is tagged record -- Legal in Ada 95.
                F1 : Integer_Vector (1 .. N) := (others => 0);
                F2 : Float_Vector (N .. 10) := (others => 0.0);
	    end record;
        Local : Nested;
    begin
        if N = 1 then
            T'Class'Output (A_Stream, Local)
            Beauty (2);
        elsif N = 2 then
            Reset (A_Stream);
            Local := T'Class'Input (A_Stream);
               -- Ouch. Different bounds for components, same external name!
        end if;
    end Beauty;

    Beauty (1);

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

From: Robert Dewar
Sent: Saturday, May 15, 2004  4:11 AM

>I have been trying to come up with a solution that imposes no
>distributed (time) overhead on programs that make no use of
>nested extensions.  Perhaps it is not worth trying to preserve
>the space or time performance of 'Tag, given how rarely it is used.

I agree that 'Tag is rarely used and that a minor hit in performance
is probably OK here.

>I think it would be nice at least to preserve the time performance
>of the tag check on binary dispatching operations

This seems to me to be in price-of-admission category. If this
cannot be achieved, the whole feature should be junked.

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

From: Stephen W. Baird
Sent: Thursday, June 3, 2004 12:46 PM

Tuck said:
> I discussed limiting T'Class'Input and T'Class'Output to types that
> are at the same accessibility level as T.  Any comment on that?

I have not been able to come up with a better alternative.

If we wanted to, I believe we could allow streaming of types whose
accessibility level lies in the range between that of T and that of the call
site. This could be done by storing an accessibility level (or something very
much like it) in the statically allocated data structure associated with a
tagged type declaration. The caller would then be able to produce a "full" tag.
Having the dynamic semantics of a streaming operation depend on the location of
the caller seems like a very bad idea. I only mention this approach in hopes
that someone else might find a way to fix it.

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

From: Randy Brukardt
Sent: Thursday, June 3, 2004  6:07 PM

The trouble with this solution is that T'Class'Input is defined in terms of
Ada.Tags.Internal_Tag. But Ada.Tags.Internal_Tag does not have any access to
the type T, so it cannot enforce any restrictions.

That means that T'Class'Input also cannot enforce any restrictions - it doesn't
have any way to get the information it would need to do so. That seems to
suggest that both T'Class'Input and Ada.Tags.Internal_Tag would have to be
erroneous in this case. And that is simply not acceptable, given that the
program does not have any real control over what it streams in. It must be
possible to write streaming operations which detect all bad data -- without
erroneous execution. And it is not acceptable to say that class-wide streaming
cannot be used in such cases, as the language gives us no other "factory"
operations that can create an object from a tag (or surregate).

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

From: Steven W. Baird
Sent: Friday, June 4, 2004  12:40 PM

T'Class'Input could be defined to perform the check that you want.

The statically allocated data structure that a Tag value currently
references (typically a dispatch table and a few other odds and ends)
could include an accessibility level (or something analogous - perhaps
just a count of many AI344-ish derivations occur on the path from the root
type to the given type).

Implementing the check would then be straightforward.

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

From: Tucker Taft
Sent: Sunday, June 6, 2004  11:49 AM

Here is an update to AI-344 on nested type extensions.
It attempts to address the issues relating to T'Class'Input
and T'Class'Output and the representation of the type Tag.
I concluded that type Tag will probably become two words
in most implementations (though a level of indirection
could probably be used to keep it to one word if desired).

I decided that the primary language requirement is that
the type Tag must be sufficient to distinguish between
all descendants of a given ancestor type.  If two types
have no common ancestor, then they could have the
same tag.  Hence, for existing situations where a type
is declared in a recursive or reentrant routine, it is
OK if all elaborations of the type declaration have
the same tag.  However, if such a type is an extension
of some type declared at a shallower nesting level, then
all elaborations must be distinguished, because objects
of two distinct elaborations might be passed to a single
dispatching operation, and the tag check must be able
to notice the mismatch.

A related issue has to do with how unique are the external
tags.  My conclusion is that they only need to distinguish
between descendants that are at the same level as their
shared ancestor, presuming we limit T'Class'Input to reading
objects at the same level as T.  This limitation is actually
consistent with our rule that a function may not return
a class-wide object with a tag identifying a type from a
deeper level than the function.  Hence, there is no need
for an external tag to include some indication of the
particular elaboration of a type declaration.  However,
some kind of instance identifier may be needed in the
presence of shared generic bodies (see the !discussion).

Randy indicated a concern about different elaborations
of a type having different component constraints.  However,
I don't see that as any worse as different executions
of a program having different component constraints.
You can always get an exception if T'Class'Input is given
bad data, whether it was produced by T'Class'Output
or by some random bit generator.  The important thing is
that we don't dispatch off to some out-of-scope type's
'Read routine.

Comments welcome, now or at the meeting.

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

From: Robert A. Duff
Sent: Sunday, June 6, 2004  1:53 PM

> Here is an update to AI-344 on nested type extensions.

I like this proposal.

> Modify 3.9(4) as follows:
>
>     ... For a tagged type that is local to a generic package body {all of
>     whose ancestors are also local to the same generic body}, the
>     language does not specify whether repeated instantiations of the generic
>     body result in distinct tags.  However, to ensure that all descendants
>     of a given type have distinct tgs, if any ancestor is declared outside the

"tgs" --> "tags"

>     generic body, the tag identifies the particular instance of the body.
>     Similarly, for a type declared at an accessibility level deeper than one
>     of its ancestor types (if any), the tag identifies the particular execution
>     of the enclosing master that elaborated the tagged type declaration.

The above seems rather chatty, and rather implementation oriented.  Why
not just say what you want, namely, that each type in a hierarchy rooted
at a given ultimate ancestor has a unique tag?  The stuff about generics
and accessibility levels can be moved into the AARM.

In other words, the model implied by the first sentence of para (4) is
(now) wrong -- we're not identifying type_decls, we're identifying types
within a hierarchy.

I think para (4.b) needs rewording as well.

>   AARM NOTE: In most cases, a tag need only identify a particular tagged
>     type declaration, and can therefore be a simple link-time-known
>     address. However, for tag checks (see 3.9.2(16)) it is essential
>     that each descendant of a given type have a unique tag.

There!  That last sentence seems more like what the RM should say,
rather than hiding this simple idea in the AARM.

>...  Hence, for
>     types declared in shared generic bodies where an ancestor comes from
>     outside the generic, or for types declared at a deeper level than an
>     ancestor, the tag needs to be augmented with some kind of "static
>     link," "global display," or "instance descriptor" pointer. This
>     implies that type Tag may need to be two words, the second of which
>     is normally null, but in these identified special cases needs to
>     include a static link or equivalent.  Within an object of one of
>     these types with a two-word tag, the two parts of the tag would
>     typically be separated, one part as the first word of the object,
>     the second placed in the first extension part that corresponds to a
>     type declared more nested than its parent or declared in a shared
>     generic body when the parent is declared outside.

>     The function Descendant_Tag returns the (internal) tag for the type
>     that corresponds to the given external tag and is both a descendant of the
>     type identified by the Ancestor tag and has the same accessibility level as
>     the identified ancestor.  Tag_Error is raised if External is not the
>     external tag for such a type.
>
>     The function Is_Descendant_At_Same_Level returns True if Descendant tag
>     identifies a type that is both a descendant of the type identified
>     by Ancestor and at the same accessibility level.  If not, it returns False.

Is the above really what you mean?  Is it implementable?  It seems like
if the two tags passed to Is_Descendant_At_Same_Level are from different
type hierarchies (or at least, different type hierarchies in generic
bodies and the like), then the implementation can't tell whether to
return True or False.  The same question applies to the Tag_Error on
Descendant_Tag.

> !discussion
>
> With the proposal to add a number of generic packages to provide
> standard container abstractions, there has been growing concern about the rule
> precluding extending a type at a deeper accessibliity level.  Because

"accessibliity" --> "accessibility"

> user-defined controlled types, user-defined storage pools, and
> user-defined streams are all implemented using type extension, this rule
> can interfere with natural use of generic data structures in nested
> scopes.
>
> It turns out that nested type extensions can be supported safely by
> shifting the accessibility checks to certain operations, rather than
> being enforced at the type declaration.  In particular, by performing
> accessibility checks on class-wide allocators, class-wide function
> return, and class-wide stream I/O, the danger of objects outliving their
> type declaration can be eliminated.
>
> For allocators, we disallow creating an object in a collection whose
> access type outlives the type identified by the object's tag.
> Similarly, for function return, we disallow returning a classwide object
> from a function if tag identifies a type declared at a deeper level than

"if tag" --> "if the tag"

> the function. For similar reasons, we preclude T'Class'Input returning
> an object whose tag identifies a type that is declared at a deeper level
> than T. For symmetry, and to prevent writing something which cannot

"which" --> "that"

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

From: Tucker Taft
Sent: Sunday, June 6, 2004  2:41 PM

> I like this proposal.

Glad to hear it.

>>Modify 3.9(4) as follows:
...
> The above seems rather chatty, and rather implementation oriented.  Why
> not just say what you want, namely, that each type in a hierarchy rooted
> at a given ultimate ancestor has a unique tag?  The stuff about generics
> and accessibility levels can be moved into the AARM.

I agree this should be rewritten.  I tried to make incremental
fixes to the existing wording, but I think a fresh start would
be better.

> In other words, the model implied by the first sentence of para (4) is
> (now) wrong -- we're not identifying type_decls, we're identifying types
> within a hierarchy.
>
> I think para (4.b) needs rewording as well.

I wrote this without having the AARM in front of me, so
I can easily believe you are right.

>>  AARM NOTE: In most cases, a tag need only identify a particular tagged
>>    type declaration, and can therefore be a simple link-time-known
>>    address. However, for tag checks (see 3.9.2(16)) it is essential
>>    that each descendant of a given type have a unique tag.
>
> There!  That last sentence seems more like what the RM should say,
> rather than hiding this simple idea in the AARM.

I would welcome some suggested rewording of para (4) from
any volunteer!

> ...
>>    The function Descendant_Tag returns the (internal) tag for the type
>>    that corresponds to the given external tag and is both a descendant of the
>>    type identified by the Ancestor tag and has the same accessibility level as
>>    the identified ancestor.  Tag_Error is raised if External is not the
>>    external tag for such a type.
>>
>>    The function Is_Descendant_At_Same_Level returns True if Descendant tag
>>    identifies a type that is both a descendant of the type identified
>>    by Ancestor and at the same accessibility level.  If not, it returns False.
>
> Is the above really what you mean?  Is it implementable?  It seems like
> if the two tags passed to Is_Descendant_At_Same_Level are from different
> type hierarchies (or at least, different type hierarchies in generic
> bodies and the like), then the implementation can't tell whether to
> return True or False.

I suppose it could be changed to require a True if the tags identify *some*
pair of types that have the desired relationship.  It would only return
False if the tags cannot be construed to identify such a pair.  In particular,
if Descendant = Ancestor, then I would expect it to return True, even
if the tag identifies a type declaration from a nested scope or a generic
body.

> ...The same question applies to the Tag_Error on Descendant_Tag.

Again, it would raise Tag_Error only if there is no type with the
given external tag and an ancestor with the given tag.

I see Is_Descendant_At_Same_Level as being very easy to implement,
presuming every tagged type descriptor has an array of ancestor tags
(which is the canonical data structure used to implement class-wide
membership) plus an indication of its static nesting level.
Descendant_Tag probably implies that the tag table used to
implement Internal_Tag needs to be updated both on elaboration and
finalization of a tagged type.

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

From: Robert A. Duff
Sent: Sunday, June 6, 2004  8:12 PM

> I would welcome some suggested rewording of para (4) from
> any volunteer!

Well, I suppose I should volunteer.  But please answer these questions
first:

The first sentence of 3.9(4) says, "The tag of a specific tagged type
identifies the full_type_declaration of the type."  Ignoring the
generic-related issues for the moment, it says a tag identifies a
full_type_decl.  Not a *type*.  3.9(4.b) then says, "The language does
not specify whether repeated elaborations of the same
full_type_declaration correspond to distinct tags."

First, I don't see how the AARM note follows from the RM text.  The RM
seems to be saying that if a full_type_decl is elaborated twice, you get
*one* tag.  It doesn't say you *might* get either one or two, which is
what the AARM says.  What was the actual intent?

It would seem cleaner to say a tag identifies a *type*.
Para (4.b) goes on to explain why we didn't do that:
for ease of (efficient) implementation, we wanted to allow
statically-allocated type descriptors, and the tag is then naturally
the address of that descriptor.

The AI breaks that property, and explains how we need two words in some
cases.  In particular, for nested type extensions and type extensions in
shared generic bodies, we need to attach some extra information.
My question is: why not attach the extra information for *all* nested
types (even root ones), and *all* types declared in shared generics?
If we do that, it seems like the model (and therefore the wording)
is very simple: tags can "identify" types -- tags and types are
one-for-one.

The implementation burden seems identical to what the AI is already
trying to propose -- namely, that in some nested cases and
generic-sharing cases, the implementation has to conjure up an extra
piece of info.

Still no distributed overhead, in the sense that if you don't nest (and
don't use shared generics), you don't pay anything.  The vast majority
of tagged types are not nested.

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

From: Robert I. Eachus
Sent: Sunday, June 6, 2004  8:27 PM

Robert A Duff wrote:

>>  AARM NOTE: In most cases, a tag need only identify a particular tagged
>>    type declaration, and can therefore be a simple link-time-known
>>    address. However, for tag checks (see 3.9.2(16)) it is essential
>>    that each descendant of a given type have a unique tag.
>
>There!  That last sentence seems more like what the RM should say,
>rather than hiding this simple idea in the AARM.
>
Now I understand where Tucker is coming from in his vison of a proper
implementation.  I like the fact that this version of the proposal does
not require two part Tags, because the implementation I envision does not.

I think that the only way this issue can come up is if you have two
nested types which are derived from different instances of the same
derived type declaration.  If in that case, which is not now legal, the
dispatch table normally pointed to by the tag is created either on some
heap visible at the point of the parent type declaration, or in a stack
or stacks similarly visible, then the different instances will have
different tags.  Yes, some tags will be in code space and others on the
heap or stack.  As such this is not a problem.  (Even if the stack is
marked as non-executable, it should be okay to have pointers into code
segments stored there.)

The two word vs. one word Tag is an issue, but it will occur anyway in
64-bit environments, as a side-effect of the addressing model.  For
example, in the AMD64 (Intel EM64T) ISA, you can have DLLs that use
32-bit addressing which are called from a 64-bit addressing
environment.  Obviously an Ada compiler that supports such calls must
use a mechanism that insures that two Tags created in the 32-bit
environment as a child of a 64-bit type are not identical, even if
created inside two different 32-bit address maps.  The solution of
course is to make the Tag for a 32-bit DLL 64-bits, and you can use
Tucker's approach of a two-part Tag, or allocate the dispatch tables in
global memory mapped into all 32-bit address spaces.  This could be, but
need not be, a special heap visible to all threads (tasks) and
libraries.  It could even be the case that all libraries map the
addesses to the same 32-bit address, whether they use 32-bit or 64-bit
addressing.  (This will work until you have a program that requires more
than 4 Gigabytes for the globally-visible code segments and these
dispatch tables.)

Incidently, in the implementation I envision, it is possible that two
types derived from the same parent will have the same tag values, if the
second type is created after the scope of the first has been left.
Absent calls to Unchecked_Conversion, this is fine.  Since the two types
will not co-exist in time, all objects of the first type must no longer
be live when the second type is created.  In other words, if the tags
are the same, the types have to be non-overlapping in time, so there is
no way to test tags of the two different derived types for equality.

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

From: Tucker Taft
Sent: Monday, June 7, 2004  11:13 AM

> First, I don't see how the AARM note follows from the RM text.  The RM
> seems to be saying that if a full_type_decl is elaborated twice, you get
> *one* tag.  It doesn't say you *might* get either one or two, which is
> what the AARM says.  What was the actual intent?

We wanted to allow either approach, where you allocate tags statically,
or on each elaboration.

> It would seem cleaner to say a tag identifies a *type*.
> Para (4.b) goes on to explain why we didn't do that:
> for ease of (efficient) implementation, we wanted to allow
> statically-allocated type descriptors, and the tag is then naturally
> the address of that descriptor.
>
> The AI breaks that property, and explains how we need two words in some
> cases.  In particular, for nested type extensions and type extensions in
> shared generic bodies, we need to attach some extra information.
> My question is: why not attach the extra information for *all* nested
> types (even root ones), and *all* types declared in shared generics?
> If we do that, it seems like the model (and therefore the wording)
> is very simple: tags can "identify" types -- tags and types are
> one-for-one.
>
> The implementation burden seems identical to what the AI is already
> trying to propose -- namely, that in some nested cases and
> generic-sharing cases, the implementation has to conjure up an extra
> piece of info.
>
> Still no distributed overhead, in the sense that if you don't nest (and
> don't use shared generics), you don't pay anything.  The vast majority
> of tagged types are not nested.

One goal was to require *no* change in implementation approach for
existing tagged types, and there are certainly existing nested tagged types,
and there are probably existing shared generic implementations that
share tags between bodies.  I agree they are rare, so it seems quite possible
that some implementors may decide to use the same approach for all
non-library-level types, but I don't think we should *require* that.

So I would prefer wording that continued to allow either implementation approach,
including for nested types or types declared in generic bodies, presuming
their ancestors obey the Ada 95 restrictions.  My suggestion would be to
say that the tag identifies the type declaration, and is also sufficient to
distinguish all descendants of the same ancestor that exist concurrently.
The rule allowing sharing in generic bodies would remain, though perhaps
it would be relegated to an implementation permission section, to get it out
of the main part of the text.

An AARM note could explain some of the implementation implications
of these rules.

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

From: Randy Brukardt
Sent: Monday, June 7, 2004  8:55 PM

> > The AI breaks that property, and explains how we need two words in some
> > cases.  In particular, for nested type extensions and type extensions in
> > shared generic bodies, we need to attach some extra information.
> > My question is: why not attach the extra information for *all* nested
> > types (even root ones), and *all* types declared in shared generics?
> > If we do that, it seems like the model (and therefore the wording)
> > is very simple: tags can "identify" types -- tags and types are
> > one-for-one.

Tagged types derived in the spec of a shared generic are really like formal
types of the generic (otherwise, it wouldn't be possible to implement the
overridding rules). So attaching the extra information to all tagged types
in shared generics is equivalent to adding it to *all* types.

The important property is that the representation of existing, non-nested,
tagged types doesn't change. (We can't break streaming of common types.) But
nested tagged types are rare, and streaming of them should be close to
non-existent. Similarly, our experience has been that tag checks are rare in
real O-O code -- so I wouldn't care much if they became slightly more
expensive.

Thus, I'd probably use the two-word tags everywhere for tag operations. The
second part would be accessed via an offset component in the static part of
the tag itself (set to 0 for library level items). The second part would be
allocated in tagged objects only if they are nested (or could be, for
generic body types).

Tucker said:

> One goal was to require *no* change in implementation approach for
> existing tagged types, and there are certainly existing nested tagged types,
> and there are probably existing shared generic implementations that
> share tags between bodies.  I agree they are rare, so it seems quite possible
> that some implementors may decide to use the same approach for all
> non-library-level types, but I don't think we should *require* that.

That's fair, but if it requires standing on one's head, and no one is going
to use the permission anyway (we certainly won't), why bother cluttering up
the standard with it??

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


Questions? Ask the ACAA Technical Agent