!standard 3.4(2/2)                                  17-04-14  AI12-0223-1/00
!class Amendment 17-04-14
!status Hold by Letter Ballot (9-1-1) - 18-05-07 
!status work item 17-04-14
!status received 17-01-11
!priority Low
!difficulty Hard
!subject The co-derivation problem
!summary

** TBD.

!problem

The containers are tagged types, with the idea that they would support
extension if needed. But it turns out that one can't really extend them
sensibly. Consider what happens if you try.

The obvious way to create an extension of a container would be something
like:

    package P is
       package My_Map_Pkg is new Ada.Containers.Ordered_Maps (Positive, My_Rec);

       type Map_Rec is new My_Map_Pkg.Map with private;

       type Map_Rec_Cursor is new My_Map_Pkg.Cursor;

       -- New and overridden operations here.

    private
       ...
    end P;

The problem is that the inherited operations are NOT the ones we want. For the
derivation making type Map_Rec, we have inherited primitive operations on
Map_Rec and on My_Map_Pkg.Cursor (that is, the new map and the old cursor).
For the derivation making type Map_Rec_Cursor, we have inherited primitive
Operations on My_Map_Pkg.Vector and on Map_Rec_Cursor (that is, the old map
and the new cursor). That is certainly not what we want, for either type.

The only workaround would be to declare all of the operations we want and then
manually call the correct original operations, very tedious and error-prone.
(Plus we still have all of those junk operations declared and visible, meaning
lots of potential errors in use could go undetected.)

This problem comes up anytime you have an ADT and an associated handle, with
operations on both. For tagged types, one can mitigate the problem if the
"handle" is a raw access type, by using an access-to-classwide type for the
handle. But that eliminates any compile-time checking, moving everything to
runtime checks (with the usual resulting problems - insufficient testing could
leave a time-bomb in the code).

Ada is all about compile-time checking, so there should be a way to do this
that preserves it.

!proposal

The following does not work in all cases, but it is presented as a starting
point for a solution:

When one has two types that are tied together, it doesn't make sense to
derive them separately. Therefore, we provide co-derivation, where multiple
types are derived at once.

The syntax would be:
    type defining_identifier {, defining_identifier} is new
       derived_type_definition {, derived_type_definition};

[Note: "and" probably would have been better syntax, but since interfaces use
that, we're stuck with ','.]

For a co-derivation, the primitives inherited are those that are primitive
on either type, and that both types appearing in the profile are replaced as
described in 3.4. The bodies of the new routines are the original routines
called with parameters of both types converted as needed.

For the example given in the problem, that would give:

    type Map_Rec, Map_Rec_Cursor is new
       My_Map_Pkg.Map with private, My_Map_Pkg.Cursor;

This is known not to work in various cases.

The most important is that it doesn't make sense for dispatching. If one of
the types is tagged (both cannot be tagged, as that would imply a type
primitive for two tagged types, which is not allowed in Ada), then one would
get inherited dispatching routines.

For instance, with the above declaration, we'd inherit delete, which is
defined as:

   procedure Delete (Container : in out Map;
                     Position  : in out Cursor);

which would be inherited as:

   procedure Delete (Container : in out Map_Rec;
                     Position  : in out Map_Rec_Cursor);

However, a dispatching call on My_Map_Pkg.Map'Class would call:

   procedure Delete (Container : in out Map_Rec;
                     Position  : in out My_Map_Pkg.Cursor);

which doesn't exist.

One could imagine limiting this feature to untagged types, but that doesn't
seem to be very helpful. One could also imagine somehow banning dispatching
from the root type to make this work, but that also seems to be a weird (and
potentially incompatible in the case of existing code like the containers)
restriction.

Steve Baird notes that there might be issues with generic formal derived types
causing emergence of routines that aren't declared. Probably generic matching
could fix that. He also noted similar issues with deriving from abstract root
types with abstract routines.

!wording

** TBD.

!discussion

An industrial Ada user reported the following:

We have a "design pattern" here of handles being class-wide, when a specific
type would be much better. Procedure X has an object of a specific type, it's
upward converted to a class-wide type for passing as a parameter to procedure
Y. Y downward converts it back to the specific type - indeed can only handle
that specific type. A hole has been created where there is the potential to
call Y with an actual of the wrong specific type, which would fail the Tag
Check and crash with a Constraint Error.

This is an example of how existing OOP practice forces users away from static
strong typing into dynamic type checks. Better would be a "post-OOP" practice
that uses strong static typing everywhere. (All we have to do is figure it
out. ;-)

!example

(See Problem and Proposal.)

!ASIS

The new capabilities will need ASIS support.

!ACATS test

ACATS B-Test and C-Tests will be needed to check that the new capabilities
are supported.

!appendix

From: Randy Brukardt
Sent: Wednesday, January 11, 2017  6:48 PM

I mentioned this problem in an aside to Tucker, but it probably deserves a
first-class examination.

The containers are tagged types, with the idea that they would support
extension if needed. But it turns out that one can't really extend them
sensibly. Consider what happens if you try.

The obvious way to create an extension of a container would be something
like:

    package P is
       package My_Map_Pkg is new Ada.Containers.Ordered_Maps (Positive, My_Rec);

       type Map_Rec is new My_Map_Pkg.Map with private;

       type Map_Rec_Cursor is new My_Map_Pkg.Cursor;

       -- New and overridden operations here.

    private
       ...
    end P;

The problem is that the inherited operations are NOT the ones we want. For the
derivation making type Map_Rec, we have inherited primitive operations on
Map_Rec and on My_Map_Pkg.Cursor (that is, the new map and the old cursor).
For the derivation making type Map_Rec_Cursor, we have inherited primitive
Operations on My_Map_Pkg.Vector and on Map_Rec_Cursor (that is, the old map
and the new cursor). That is certainly not what we want, for either type.

The only workaround would be to declare all of the operations we want and then
manually call the correct original operations, very tedious and error-prone.
(Plus we still have all of those junk operations declared and visible, meaning
lots of potential errors in use could go undetected.)

[Aside: I had a version of this problem in early Claw versions, when a "type
Handle is new Dword;" caused all kinds of routines that were accidentally
primitive on Dword to get derived. Which I found out when trying to debug some
unrelated problem; looking at a compiler symboltable dump I realized that
there were many unintended routines in it. I ended up moving Dword into a
subpackage to prevent any uses of it from being primitive.]

This problem comes up anytime you have an ADT and an associated handle, with
operations on both. That seems pretty common to me, especially as the "handle"
might just be an explicit access type that points at the original type.

[Yes, this exhibit N in the long list of reasons that we should have had all
of the container operations having a container parameter. If that had been the
case, we'd just be losing a bit of type checking by using the first derivation
alone, annoying but not necessarily catastrophic. It seems too late to fix
that problem, though. Unless we want to add overloaded versions of Next and
First and the like (we already have Reference and the like, and for Vectors,
we have all of the index versions) -- but that's not a general solution, it
would only help the containers.]

---

I once tried to work out a proposal for "co-derivation", with the intent of
handling this problem. It has issues with dispatching, sadly. I'll present the
idea here in the hopes that someone can think of something better.

The basic idea is that the two types above have to be derived at the same
time. It doesn't make sense to derive them separately because they're joined
at the hip. So I proposed a co-derivation, that would look something like:

    type Map_Rec, Map_Rec_Cursor is new
       My_Map_Pkg.Map with private, My_Map_Pkg.Cursor;

[Note: "and" probably would have been better syntax, but since interfaces use
that, we're stuck with ','.]

The basic idea is that the primitives inherited are those that are primitive
on either type, and that both types appearing in the profile are replaced as
described in 3.4. The bodies of the new routines are the original routines
called with parameters of both types converted as needed.

This works fine for untagged types, as far as I can tell (but Steve may be
able to disprove that optimistic assumption :-).

However, for tagged types, it's unclear how to deal with dispatching (since
one of the types necessarily has to be untagged, and we don't have any
"co-dispatching" anyway). Arguably, you don't want dispatching in this case
(the handle would almost always be the wrong type), but that seems
unfortunate on basic principles. (And you do want tagged types, so that you
can use the containers and especially prefix notation.)

Anyway, an idea to consider. Something seems to be needed to handle this sort
of problem in the general case, because it is frequent and the existing
solutions are lengthy and error-prone.

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

From: Jean-Pierre Rosen
Sent: Tuesday, May 22, 2018  9:16 AM

Taking up this AI from where it was left...

The killing problem noted by Randy is (from the AI):
-------------------------
For the example given in the problem, that would give:

    type Map_Rec, Map_Rec_Cursor is new
       My_Map_Pkg.Map with private, My_Map_Pkg.Cursor;

This is known not to work in various cases.

The most important is that it doesn't make sense for dispatching. If one of
the types is tagged (both cannot be tagged, as that would imply a type 
primitive for two tagged types, which is not allowed in Ada), then one would
get inherited dispatching routines.

For instance, with the above declaration, we'd inherit delete, which is 
defined as:

   procedure Delete (Container : in out Map;
                     Position  : in out Cursor);

which would be inherited as:

   procedure Delete (Container : in out Map_Rec;
                     Position  : in out Map_Rec_Cursor);

However, a dispatching call on My_Map_Pkg.Map'Class would call:

   procedure Delete (Container : in out Map_Rec;
                     Position  : in out My_Map_Pkg.Cursor);

which doesn't exist.
-----------------------------------------------
Is it really a problem? Important points to keep in mind:
1) Coderivation does not imply multi-dispatch, since at most one type is 
tagged.
2) Derived non-tagged types are equivalent (assuming no change in 
representation), and calls to primitive operations are always statically 
bound.

So it seems harmles for the co-derived subprogram to use the same slot in 
the dispatch table as the original one, i.e. a dispatching call on some 
Container will call the Delete on Map_Rec_Cursor if the dispatching call
is on Map_Rec, and the Delete on Cursor if the dispatching call is on Map.

Where could such a dispatching call happen? Presumably within a procedure 
like:

Do_Something (Container : in out Map'Class;
              Position  : in out Cursor);

Now, the user has declared:
My_Cont : Map_Rec;
My_Curs : Map_Rec_Cursor;

He can call:
Do_Something (My_Cont, Cursor (My_Curs));

(Annoying conversion, see later)

Inside Do_Something, there is a call:
Delete (Container, Position);  -- Dispatching

In this case, the dispatching table will point to the co-derived subprogram 
=> it works as expected.

1) Extra point 1:
This assumes that there is no change of representation for the derived type - 
i.e. changes of representation would not be allowed for types that are part of
a coderivation. Or alternatively, co-derivation would not be allowed if a non 
tagged type has a change of representation. This seems a small price to pay 
for the feature.

2) Extra point 2:
The extra conversion in the call:
 Do_Something (My_Cont, Cursor (My_Curs)); is annoying. It could be avoided by 
allowing T'Class on non-tagged types ONLY IN FORMAL PARAMETERS  (trying to 
quickly jump into my asbestos suit), with the obvious meaning: compatible with
any type derived from it, perhaps also under the condition that there is no 
change of representation.

Thoughts?

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

From: Randy Brukardt
Sent: Thrusday, June 7, 2018  7:31 PM

...
> Where could such a dispatching call happen? Presumably within a 
> procedure like:
> 
> Do_Something (Container : in out Map'Class;
>               Position  : in out Cursor);
> 
> Now, the user has declared:
> My_Cont : Map_Rec;
> My_Curs : Map_Rec_Cursor;
> 
> He can call:
> Do_Something (My_Cont, Cursor (My_Curs));

True, but he's totally lost static type checking. The routine can no longer 
know whether it is getting the right type.

Nothing prevents calling Do_Something with mixed types, such as:

My_Other_Cont : Map_Rec;
My_Other_Curs : Cursor;

Do_Something (My_Other_Cont, Cursor (My_Other_Curs));

...and now you'll dispatch to the primitive routine Delete with the wrong kind
of cursor.

That is, it will work in the "correct" case, but it also will allow many 
incorrect calls.

If you're going to lose most of the type checking, you might as well not 
bother with the co-derivation.

...
> 1) Extra point 1:
> This assumes that there is no change of representation for the derived 
> type - i.e. changes of representation would not be allowed for types 
> that are part of a coderivation. Or alternatively, co-derivation would 
> not be allowed if a non tagged type has a change of representation. 
> This seems a small price to pay for the feature.

The tagged type is not the problem, and it should be allowed to have a change
of representation. Untagged types with primitive routines never allow change
of representation (except via a language bug) - see 13.1(10). So this doesn't
seem to be a problem unless we decide to remove the nasty (and incompletely
enforced) 13.1(10).

> 2) Extra point 2:
> The extra conversion in the call:
>  Do_Something (My_Cont, Cursor (My_Curs)); is annoying. It could be 
> avoided by allowing T'Class on non-tagged types ONLY IN FORMAL 
> PARAMETERS  (trying to quickly jump into my asbestos suit), with the 
> obvious meaning: compatible with any type derived from it, perhaps 
> also under the condition that there is no change of representation.

That would work, but you'd still have the typing problem noted above.

The way to fix the typing problem would be to require that both types be 
tagged (not currently allowed). We'd only allow co-derivation for such types,
so their tags would always be related. That would avoid the problems of 
multiple dispatch. (I don't think the tags could be the same, because 
predefined single type stuff like streaming and assignment has to be different
for each type. But the routines with multiple controlling parameters would 
have to be present in both tags, and designate the same subprogram.)

We already have a check for any subprogram that has multiple controlling 
parameters that the tags match. We could replace that by a rule that the tags
have to have the same relationship (come from the same co-derivation). In that
case, dispatching would always go to the routine with the correct parameter.

A dispatching routine would thus have to have dynamically tagged values (or
statically tagged) for both parameters. And 'Class is automatically available.
So Do_Something could be declared:

Do_Something (Container : in out Map'Class;
              Position  : in out Cursor'Class);

I think this would solve the typing problem, but I don't know if it works for
the generic derived type issues that Steve (who else?) raised privately with 
me. And I don't know if it would interfere with any other language mechanisms.
Someone more motivated than me needs to figure that out.

P.S. It also would be an issue with the existing containers. Not sure if 
making Cursors tagged would be compatible enough; it would make regular 
derivations of them (and containerss) illegal. I think the result would be 
much better (if the code was rewritten to use coderivation), but the code 
breakage might be too much to stomach.

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