Version 1.1 of acs/ac-00283.txt

Unformatted version of acs/ac-00283.txt version 1.1
Other versions for file acs/ac-00283.txt

!standard 3.10.1(10/3)          16-08-18 AC95-00283/00
!class Amendment 16-08-18
!status received no action 16-08-18
!status received 16-07-30
!subject Enhancements to standard containers
!summary
!appendix

!topic Expand the usefulness of incomplete types, esp. WRT generics.
!reference Ada 202x RM 3.10.1; Ada Rationale 4.3
!from Edward Fish 16-07-30
!keywords incomplete types generics
!discussion

In response to a posting on comp.lang.ada regarding the possibility/feasibility
of making a container-type for incomplete and indefinite types to facilitate the
ease of creation of recursively-defined types, Randy Brukardt said:

You could, of course, create a container using a formal incomplete type (which
does match incomplete types). The issue(*) is that you'd need to pass in a
constructor function and a destructor procedure (since you can't allocate an
object of an incomplete type). That would look something like:

    generic
         type Index_Type is range <>;
         type Element_Type;
         with function "=" (Left, Right : Element_Type)  return Boolean is <>;
         with function Copy_Constructor (Obj : Element_Type) return access Element_Type;
         with procedure Destructor (Value : access Element_Type);
    package Incomplete_Vectors is
      ....

Then the operations that add elements to the container would use
Copy_Constructor to allocate a copy, and the clean-up code would use Destructor.
(It might be better to use a named access for this purpose, the problem with
that is that you'd have to declare it visible before the instance, while that
type is really an implementation artifact best kept private to this usage.)

(*) It's *almost* possible to create a container of pre-existing objects using a
formal incomplete type. The problem is that you're not allowed to take 'Access
of a parameter of such a type (that violates 3.10.1(10/3) - even though there's
no real problem with that particular operation). I've suggested "fixing" this
issue in the Ada Standard, but that hasn't gotten any traction as most see it as
a curiosity rather than the realistic technique. If you'd like to see this work,
send something to Ada-Comment!

[End Randy Brukardt quote - Editor.]

The LRM 3.10.1 (10/3) says:

A prefix that denotes an object shall not be of an incomplete view. An actual
parameter in a call shall not be of an untagged incomplete view. The result
object of a function call shall not be of an incomplete view. A prefix shall not
denote a subprogram having a formal parameter of an untagged incomplete view,
nor a return type that is an incomplete view.

However, the Ada Rationale in 4.3 says the following about parameters:

However, the overall rule remained that an incomplete type could only be
completed by a full type declaration and, moreover, a parameter could not
(generally) be of an incomplete type. This latter restriction encouraged the use
of access parameters.
[...]
This is changed in Ada 2012 so that an incomplete type can be completed by any
type (other than another incomplete type). Note especially that an incomplete
type can be completed by a private extension as well as by a private type.

The other major problem in Ada 2005 was that with mutually dependent types in
different packages we could not use incomplete types as parameters because it
was not known whether they were by-copy or by-reference. Of course, if they were
tagged then we did know they were by reference but that was a severe
restriction.

The need to know whether parameters are by reference or by copy was really a red
herring. The model used for parameter passing in versions of Ada up to and
including Ada 2005 was basically that at the point of the declaration of a
subprogram we need to have all the information required to call the subprogram.
Thus we needed to know how to pass parameters and so whether they were by
reference or by copy. But this is quite unnecessary; we don't need to know the
mechanisms involved until a point where the subprogram is actually called or the
body itself is encountered since it is only at those points that the parameter
mechanism is really required. It is only at those points that the compiler has
to grind out the code for the call or for the body.

[End Rationale quote - Editor.]

Like the above with the case of parameters, the case of generics and
incomplete-types is similar, we could have an internally defined/used
access-type, invisible and invalid to the public users of the package but still
usable:

generic
   type Element_Type (<>);
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Incomplete_Indefinite_Holders with Preelaborate, Remote_Types, Spark_Mode => On is

   type Holder is tagged private;
private

   type Element_Access is access all Element_Type;
   Type Holder is record
      Counter : System.Atomic_Counters.Atomic_Counter;
      Element : Element_Access;
   end Holder
   with --...
end Incomplete_Indefinite_Holders;
and

   function "=" (Left, Right : Holder) return Boolean is
   begin
      if Left.Reference = Right.Reference then
         --  Covers both null and not null but the same shared object cases
         return True;
      elsif Left.Reference /= null and Right.Reference /= null then
          -- The following errors, even though we are assured to have the
          -- proper equality-function from the formal parameters, namely
          -- the "=" function; this operation is illegal by 3.10.1 (10/3).
          return Left.Reference.Element.all = Right.Reference.Element.all;
      else
         return False;
      end if;
   end "=";

Another operation that should be legal and is prohibited by 10/3, though I don't
know the applicability, is application of the 'address and 'access attributes
after dereference (eg Left.Reference.Element.all'Address) even if
incomplete-types are generally inaccessible because those attributes must be
known by the compiler at compile-time (the later being an access to the
aliased-object the original access referenced.).


Note 1 -- If the profile of Unchecked_Deallocation is altered to the following,
then it will work with even access types to incomplete types, which
addresses/eliminates Randy's need for a destructor to be passed in via
formal-parameters:

generic
    type Object (<>);
    type Name is access Object;
procedure Unchecked_Deallocation (X : in out Name)
  with Preelaborate, Import, Convention => Intrinsic;

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

From: Randy Brukardt
Sent: Monday, August 1, 2016  5:07 PM

...
> Like the above with the case of parameters, the case of generics and
> incomplete-types is similar, we could have an internally defined/used
> access-type, invisible and invalid to the public users of the package
> but still usable:
>
>		generic
>		   type Element_Type (<>);
>		   with function "=" (Left, Right : Element_Type) return Boolean is <>;
>		package Incomplete_Indefinite_Holders with Preelaborate, Remote_Types, Spark_Mode => On is
>
>		   type Holder is tagged private;
>		private
>
>		   type Element_Access is access all Element_Type;
>		   Type Holder is record
>		      Counter : System.Atomic_Counters.Atomic_Counter;
>		      Element : Element_Access;
>		   end Holder
>		   with --...
>		end Incomplete_Indefinite_Holders;

Not like that, unfortunately. As I pointed out in the message that you quoted,
you can write this, but you can't create any elements as allocation is not
supported for access-to-incomplete types. Much like abstract types, the major
thing you can't do with an incomplete type is create an object, in any way.

So you have to pass some sort of copy constructor in (and a matching destructor)
if you are going to use this form. (Also note that you will not be able to copy
the objects even into an existing object, as incomplete types are limited.)

The case I was talking about was a container of *existing* objects. That is, the
objects live elsewhere; the container just organizes them. (For instance,
imagine making a map of tasks, where the key belongs to the container and the
tasks are created somewhere else.)

You can do that with an explicit access type (that is, making a container of
access values), but of course that introduces an access type into the interface.

> Another operation that should be legal and is prohibited by 10/3,
> though I don't know the applicability, is application of the 'address
> and 'access attributes after dereference (eg
> Left.Reference.Element.all'Address) even if incomplete-types are
> generally inaccessible because those attributes must be known by the
> compiler at compile-time (the later being an access to the aliased-object the original access referenced.).

The reason these sorts of things are prohibited is to prevent any sort of query
about the object itself. The only time a dereference can be allowed is when the
entire object is involved, and no information about the object is needed (for
instance, tagged incomplete type parameter passing). That necessarily requires a
number of special cases. The one I was interested in was getting an access to an
existing object (that is, a parameter).

There's no real need for .all'access, since you can do the same thing with a
type conversion (and without the problematic prefix). And 'address should be
restricted to very-low level code, so it should never appear in a container.

> Note 1 -- If the profile of Unchecked_Deallocation is altered to the
> following, then it will work with even access types to incomplete
> types, which addresses/eliminates Randy's need for a destructor to be
> passed in via formal-parameters:

>		generic
>		    type Object (<>);
>		    type Name is access Object;
>		procedure Unchecked_Deallocation (X : in out Name)
>		  with Preelaborate, Import, Convention => Intrinsic;

(1) This is irrelevant, as one still has to pass in some sort of constructor. If
    that's the case, you have to also pass in the matching destructor, since
    there is no reason to assume that the constructor even uses the heap. (It
    could just pass aliased elements of an array, for instance.) It's always
    wrong to pass in only one of a matching pair of operations.

(2) This would make zero-space-overhead pool designs impossible. Such a pool
    uses the size of the object in Deallocate to determine how much memory to
    return to the pool (as opposed to using some sort of object header). On
    smaller targets, this sort of thing can be critical.

(3) It wouldn't work with the existing storage pool definition for
    Deallocate:

procedure Deallocate(
      Pool : in out Root_Storage_Pool;
      Storage_Address : in Address;
      Size_In_Storage_Elements : in Storage_Elements.Storage_Count;
      Alignment : in Storage_Elements.Storage_Count) is abstract;

The size and alignment of a formal incomplete type is not necessarily known.
(Remember that a formal incomplete type can match a regular incomplete type, and
an incomplete type can be declared in a package spec with the completion
declared in a body. In such a case, even the compiler doesn't know how the real
object is defined outside of the package body.) As such, this definition would
have to be changed and then all existing storage pools would also have to be
changed. A totally unacceptable incompatibility (especially in light of (2)).

Ergo, this idea is a non-starter.

---

In any case, I was hoping to get some problem statements: that is, *real*
examples where the existing containers can't do the job. If those don't exist,
then it's hard to justify the work to extend the applicability of the containers
further. (I'd like to see containers of incomplete types, but I need usage cases
in order to make a case for that to the rest of the ARG. "It would be nice"
doesn't carry much weight!!)

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


Questions? Ask the ACAA Technical Agent