Bug: It's not possible to have a safe recursive data type in Ada

[raph-amiard]

Problem

It's not possible to have a type that has a collection of refcounted pointers to itself as a component:

type Rec;

package Rec_Ref is new Refcounted (Rec);

package Rec_Ref_Vectors is new Ada.Containers.Vectors (Positive, Ref_Ref.Ref);

type Rec is record
   A, B : Integer;
   Children : Rec_Ref_Vectors.Vector;
end record;

Possible solution

We should investigate if it's possible to write a refcounted pointer type that works with an incomplete type. First investigations on GNATCOLL.Refcounted were inconclusive. If it's not possible, we should investigate what we can do at a language level to improve the situation.

[jere-software]

It's possible if you aren't tied to the GNATCOLL package, but somewhat messy. You need to supply the access type and the unchecked deallocation operation as part of the package instantiation. It definitely can use some sprucing up in Ada. I think better language support would still help.

https://github.com/jeremiahbreeden/bullfrog/blob/master/src/bullfrog-access_types-smart_access.ads

Here's a quick test package that shows hot to use it in a self referencial instantiation: https://github.com/jeremiahbreeden/bullfrog/blob/master/src/tests/bullfrog-tests-smart_access_node.ads

This should be usable in a collection? Or did I miss the issue?

For reference, using the smart_access package would change the example to something like:

type Rec;
type Rec_Access is access Rec;

-- Implement this with Ada.Unchecked_Deallocation later on
-- when Rec is fully declared.
procedure Unchecked_Deallocation(Self : in out Rec_Access);

package Rec_Ref is new Bullfrog.Access_Types.Smart_Access
   (Element_Type   => Rec, 
    Element_Access => Rec_Access, 
    Finalize       => Unchecked_Deallocation);

package Rec_Ref_Vectors is new Ada.Containers.Vectors (Positive, Ref_Ref.Shared_Access);

type Rec is record
   A, B : Integer;
   Children : Rec_Ref_Vectors.Vector;
end record;

[briot]

It's possible, but somewhat messy. You need to supply the access type and the unchecked deallocation operation as part of the package instantiation. It definitely can use some sprucing up in Ada.

In the context of GNATCOLL.Refcount, I indeed never quite managed to make it work with an incomplete type, though I got pretty close by the use of several mechanisms:

• Removing constraints on Element_Type (limited or not, definite or indefinite, …)

One thing that GNATCOLL.Refcount.Shared_Pointers does nicely is that the Element_Type does not have to derive from a specific parent type that would contain the counter (so we are one step closer to allowing incomplete types).

Another thing it does is that via the use of a special storage pool, we do not need to store the Element_Type (or an access to it) in a record that would also contain the refcount. Instead, when we allocate memory for Element_Access, we allocate extra space for the counter (and for any decorator generated by the compiler like bounds, tag,…). Storing the Element_Type is a record that would contain the counter would of course mean not allowing limited types for Element_Type. So if using a record, we would have to store an Element_Access and a Counter_Access, requiring two allocations.

• Because we need this special storage pool, though, the Element_Access has to be declared in the generic package itself, not provided by the user.

• One reason why incomplete types are not possible in gnatcoll is because I wanted Element_Type to possibly be indefinite. That would mean passing an allocator function as formal parameter, but then again it doesn’t necessarily play well with the special storage pool.

• The other reason that I can remember where incomplete types are an obstacle depends on the API chosen for the smart pointers. If you want something like:

  procedure Set (Ref : in out Smart_Pointer’Class; Data : Element_Type);

  then of course you need to be able to copy, and disallow limited types. Not compatible with incomplete types.

  Just having procedure Allocate (Ref : in out Smart_Pointer’Class); removes that need, but then users need a second step to initialize the newly allocated smart pointer. So we give up on user convenience for the incomplete types...

One idea I had what to have several specialized generic packages for smart pointers, one for definite types, one for indefinite,… It would be nice if they could have the same name, and the compiler somehow automatically choses the most appropriate one (to be defined…) This might make it easier to write some of the packages (for instance: in some cases, use the record-with-two-access representation, sometimes use the specialized-storage-pool, depending on the constraints. And the user doesn’t have to understand exactly which package to use when.

Another approach, of course, would be to allow instantiating generic packages when a type hasn’t been frozen yet, likely with some lighter restrictions. This seems the most powerful approach, and perhaps in line with existing discussions reviewing how freezing works in Ada.

Emmanuel

[raph-amiard]

Thanks @briot, @jeremiahbreeden for your input, that does kind of confirm my intuition :) (Hi Manu! nice to hear from you ^ ^ was kind of expecting your input on this)

I'll play with it and think about what language improvements would be the best to improve the statu quo wrt. expressivity.