Re: How to define an array of a variant record type?

[Nick Roberts <nick.roberts@acm.org>]

Harald Schmidt wrote:

> I would like to define an array, which its element type is a variant record
> and the Value_Type is only known at runtime.
> 
>    type Name_Value_Type is (String_Type,
>                             Integer_Type,
>                             Float_Type);
> 
>    type Name_Value(Value_Type : Name_Value_Type) is
>       record
>          The_Name : Unbounded_String;
>          case Value_Type is
>             when String_Type =>
>                String_Value : Unbounded_String;
>             when Integer_Type =>
>                Integer_Value : Integer;
>             when Float_Type =>
>                The_Value : Float;
>          end case;
>       end record;
> 
>    type Name_Value_Sequence is array(Natural range <>) of Name_Value;
> 
> The compiler says "unconstrained element type in array declaration",
> ...right!
> 
> I know Ada is a strong typed language, but sometimes information is only at
> runtime available. Does anyone know some workaround, or a regulare design
> pattern for this problem?

So, to summarise the various answers to this question, you could use 
indirection or default discriminants.

An example of using indirection:

    type Name_Value_Ptr is access Name_Value;

    type Name_Value_Sequence is array (Natural range <>) of Name_Value_Ptr;

Here Name_Value_Ptr is a pool-specific access type. You can create values 
of the designated type (Name_Value) by allocating them (generally in an 
area of memory called the 'heap'). For example:

    function "+" (Right: String)
       return Unbounded_String renames To_Unbounded_String;

    X: Name_Value_Sequence(0..9);
    ...
    X(5) := new Name_Value'( Integer_Type, +"Fred", 23 );

The amount of memory space used up by the allocated value will be the space 
required for the actual components selected by the discriminant (in this 
case Integer_Value) plus the mandatory components (in this case The_Name) 
plus (usually) the discriminants themselves (in this case Value_Type) plus 
whatever administrative information is required (associated with the 
management of the heap). Usually the administrative information is small 
(sometimes it is zero). We should also count the size of the access value 
in the array. Usually an access value is also small.

Another example of using indirection:

    type Name_Value_Ptr is access all Name_Value;

    type Name_Value_Sequence is array (Natural range <>) of Name_Value_Ptr;

Here Name_Value_Ptr is a general access type (note the 'all' in the 
declaration). You can create values of the designated type (Name_Value) by 
allocating them as before. However, you can also refer to aliased objects 
anywhere in memory. For example:

    function "+" (Right: String)
       return Unbounded_String renames To_Unbounded_String;

    X: Name_Value_Sequence(0..9);
    ...
    Y: aliased Name_Value := ( Integer_Type, +"Fred", 23 );
    ...
    X(5) := Y'Access;

The memory used by this technique is the same, except that if we do not 
allocate objects in the heap, we avoid the space used up by the 
administrative information (however much that is). A general access type 
may be bigger than a pool-specific one (but I think they are usually the 
same size, in fact).

Finally, an example of using default discriminants:

    type Name_Value (Value_Type : Name_Value_Type := String_Type) is
       record
          ...

    type Name_Value_Sequence is array (Natural range <>) of Name_Value;
    ...
    X: Name_Value_Sequence(0..9);
    ...
    X(5) := ( Integer_Type, +"Fred", 23 );

The memory space used up by each component of the array will be the space 
required for the maximum of the union of the size of every component which 
could be selected by the discriminant (in this case the greatest of the 
sizes of String_Value, Integer_Value, and The_Value) plus the mandatory 
components (in this case The_Name) plus (usually) the discriminants 
themselves (in this case Value_Type).

Therefore, if your discriminated record has some variants that are much 
bigger than others, this option could be very wasteful of memory space. On 
the other hand, if the variants are all of similar size (or memory space is 
not a major worry), this option could be the best, since it involves no 
indirection, no allocation, and no administrative information.

There are many other possible ways of resolving the problem.

One idea is to have separate arrays, one for each variation. This approach 
allows you to make each array of an appropriate length. For example, if you 
know that most of your values will be Float_Type, you could make that array 
big, and the other two small. The disadvantage of this approach is that you 
have to solve the problem of other data referring to array components: now 
there are many arrays, the right array has to be selected in addition to an 
index into the array. One advantage is that you do not have to store the 
discriminants, as such; in some cases this could save a lot of memory.

A possible alternative to using an array is to use a structure with 
pointers (usually access values) to form a linked list, a tree, or 
whichever structure suits the data and the way it needs to be accessed.

Typically, most of the hard work can be taken out of this approach by 
taking advantage of one of the various 'container' types provided by 
libraries such as Charles:

    http://home.earthlink.net/~matthewjheaney/charles/

Some containers are able to contain indefinite types (such as a record with 
discriminants without default values), and can provide various convenient 
ways of accessing the data too.

A radical solution is to bypass the typing system. You have an array of 
small memory buffers, or you just have one big memory buffer (just like the 
heap), and store things in there in an encoding that suits the data. This 
approach can be a lot of work (especially to debug), and it may require a 
trade-off between memory use and speed of access, but it can be a very 
efficient option. In a few cases, it may be the only practical option.

Finally, it should be mentioned that an alternative to using a single 
discriminant to simply select one of a set of variants is to use a 
hierarchy of tagged types. For example:

    type Root_Name_Value_Pair is abstract tagged
       record
          The_Name : Unbounded_String;
       end record;

    type Name_String_Pair is new Root_Name_Value_Pair with
       record
          String_Value : Unbounded_String;
       end record;

    type Name_Integer_Pair is new Root_Name_Value_Pair with
       record
          Integer_Value : Integer;
       end record;

    type Name_Float_Pair is new Root_Name_Value_Pair with
       record
          The_Value : Float;
       end record;

    type Name_Value_Access is access Root_Name_Value_Pair'Class;

    type Name_Value_Sequence is
       array (Positive range <>) of Name_Value_Access;

With tagged types, it is usually necessary to use indirection (access 
types) to cope with the fact that polymorphism almost inevitably involves 
indefinite types.

The alleged advantages of this approach vary from the subtle and arguable 
("it is clearer") to the sure but possibly more complex: each different 
type within the hierarchy can have its own 'overriding' body of a 
subprogram; the hierarchy can be extended (in separate library units) 
without disturbing the existing source text. A call can dynamically select 
the correct body of an overridden subprogram, based on the tag of a 
parameter; this is a very neat technique, but it isn't always necessarily 
the better choice.

Note that in the above example I've used Positive for the 'confinement' 
subtype of the array. It is my habit to do this for arrays used in this 
typical 'sequence' role, just like Ada's standard String type. People used 
to C arrays might prefer Natural. It can be significant if positional array 
aggregates are used, since the lower bound will determined by the 
confinement subtype (1 for Positive or 0 for Natural).

Some food for thought, hopefully!

-- 
Nick Roberts