Version 1.1 of acs/ac-00270.txt

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

!standard A.18          15-06-17 AC95-00270/00
!class confirmation 15-06-17
!status received no action 15-06-17
!status received 15-05-23
!subject Bounded indefinite containers
!summary
!appendix

From: Martin Dowie
Sent: Friday, May 23, 2015   4:35 AM

Why are there no Bounded Indefinite containers?

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

From: Pascal Obry
Sent: Sunday, May 24, 2015  2:03 AM

Maybe because the bounded containers are designed to not use memory allocation.
In the indefinite case it would be required. So both requirement are in
contradiction.

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

From: John Barnes
Sent: Sunday, May 24, 2015  2:14 AM

The last paragraph of Section 8.2 of the rationale says

Finally, note that there are no bounded containers for indefinite types.
This is becuase the size of an object of an indefinitet type (such as
String) is gnerally not known and so indefinite types need some dynamic storage
management. However, the whole point of introducing bounded containers was to
avoid such management.

See also page 700 of Programming in Ada 2012.

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

From: Tucker Taft
Sent: Sunday, May 24, 2015  7:43 AM

> Why are there no Bounded Indefinite containers?

Indefinite containers, by their nature, require access types and heap
allocation.  One could "cheat" in various ways to try to avoid the use of access
types, but it wouldn't be pretty.  One could create a version of a "Holder"
container specially designed to avoid heap allocation, and then use that as an
element of a bounded container, but that again would require a fair amount of
ugly low-level storage management trickery.

Another alternative is to create your own storage pool or access type with an
associated Storage_Size-specified pool, and then manage containers of access
values into that pool.

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

From: Martin Dowie
Sent: Sunday, May 24, 2015  12:11 AM

Yes, and your final suggestion is what I'm doing but that just makes *my* code
ugly (and very likely wrong!!).when the ugly bit could be done in a standard
package. There is loads of ugly stuff in the standard packages already :-)

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

From: Randy Brukardt
Sent: Sunday, May 24, 2015  5:53 PM

But this still is nonsense. The bounded containers are not intended to use any
storage allocation. That certainly includes any pools. One could imagine a
container designed to use a user-defined pool, but that would have nothing
whatsoever to do with the bounded containers. Moreover, such pools would have to
be general (that is, allow any pattern of allocations and deallocations), and
that would be incompatible with any sort of safety-critical pool (which have to
avoid any sort of fragmentation, and thus have to limit the sizes of
allocations/deallocations to a very small known set).

So, there is no known usage scenario where a general unbounded container could
be combined with a safety-critical pool. Additionally, there is no possible
value to a bound in such a scenario (it would just be a nuisance, it wouldn't
allow any simplifications to the container). So there is no sensible use for a
bounded, indefinite container (and little sensible use for an unbounded
container with a user-specified pool) -- that's why we don't have such
containers.

Finally, you can write such code yourself (it appears that you are doing that),
but I would guess that that code is also nonsense. You're just working hard to
put allocations into a form that you've convinced yourself have some special
properties -- but they don't really have any such properties. The same reasons
that you aren't willing to use usual dynamic allocation apply to whatever it is
that you're doing, simply because the sizes of indefinite objects vary (and vary
depending upon the compiler and even compiler version).

One that isn't allowed to use the general "new" has to completely avoid
indefinite objects that aren't allocated on the stack (and even that isn't
enough on all compilers - Janus/Ada will do heap allocation for parts of some
indefinite objects). If you're going to use them beyond that, then you have to
be willing to do heap allocation, so the normal indefinite containers are fine.
Else you can't get there from here. :-)

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

From: Bob Duff
Sent: Wednesday, May 27, 2015  12:10 PM

>...So there is no
> sensible use for a bounded, indefinite container (and little sensible
>use  for an unbounded container with a user-specified pool) -- that's
>why we  don't have such containers.

AdaCore provides two bounded containers that allow indefinite
Element_Type:

Ada.Containers.Bounded_Holders allows you to create (for example) an array of
class-wide, without using pointers or heap allocation.

Ada.Containers.Formal_Indefinite_Vectors is a bounded vector allowing indefinite
Element_Type -- again, without pointers or heap allocation.

I'm not sure if these are what Martin Dowie wants; he can take a look at the
sources if he's interested.

> The same reasons that you aren't willing to use usual dynamic
> allocation apply to whatever it is that you're doing, simply because
> the sizes of indefinite objects vary...

Some do.  But this one:

   type Constant_Reference_Type
     (Element : not null access constant Element_Type) is
      record
         Control : Reference_Control_Type :=
           raise Program_Error with "uninitialized reference";
         --  The RM says, "The default initialization of an object of
         --  type Constant_Reference_Type or Reference_Type propagates
         --  Program_Error."
      end record;

does not -- all objects of this type are of the same
(compile-time-known) size.

>... (and vary depending upon the compiler and  even compiler version).

I don't see how that's relevant -- the sizes of objects of definite types can
vary across implementations, too, but that has nothing to do with memory
allocation on a particular implementation.

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

From: Randy Brukardt
Sent: Wednesday, May 27, 2015  12:36 PM

> AdaCore provides two bounded containers that allow indefinite
> Element_Type:
>
> Ada.Containers.Bounded_Holders allows you to create (for
> example) an array of class-wide, without using pointers or heap
> allocation.
>
> Ada.Containers.Formal_Indefinite_Vectors is a bounded vector allowing
> indefinite Element_Type -- again, without pointers or heap allocation.
>
> I'm not sure if these are what Martin Dowie wants; he can take a look
> at the sources if he's interested.

These still seem like nonsense to me. There's no possible way to have an array
of class-wide (for example) without pointers or heap allocation. At best, you
could emulate a heap within the container -- that might meet the letter of
avoiding heap allocation but could not avoid the spirit (the internal thing
would work the same way), and certainly you'd have to have a level of
indirection -- which surely sounds like a pointer to me. If one only allowed
setting of such elements once (no change after initialization), you could sort
of do it (although you'd certainly still need some form of pointers), but that
would be extremely limiting and nothing like the general containers (which allow
arbitrary additions and removals of elements).

I don't see much point in containers that lie about their implementation so that
they can be used where a direct feature cannot.

> > The same reasons that you aren't willing to use usual dynamic
> > allocation apply to whatever it is that you're doing, simply because
> > the sizes of indefinite objects vary...
>
> Some do.  But this one:
>
>    type Constant_Reference_Type
>      (Element : not null access constant Element_Type) is
>       record
>          Control : Reference_Control_Type :=
>            raise Program_Error with "uninitialized reference";
>          --  The RM says, "The default initialization of an object of
>          --  type Constant_Reference_Type or Reference_Type propagates
>          --  Program_Error."
>       end record;
>
> does not -- all objects of this type are of the same
> (compile-time-known) size.

Sure. But I don't know of any way to write a generic specification that can only
be instantiated with indefinite types whose size doesn't vary. Besides, we've
been talking about class-wide types, and there cannot be one of those whose size
might not vary (since someone could add a later extension, and that does not
force recompilation of the class-wide types).

> >... (and vary depending upon the compiler and  even compiler version).
>
> I don't see how that's relevant -- the sizes of objects of definite
> types can vary across implementations, too, but that has nothing to do
> with memory allocation on a particular implementation.

Portability. If you write something that works on a particular compiler version
and optimization settings, there is no reason to assume it will work on a
different compiler or a newer version of the same compiler or even the same
compiler with different settings. It makes little sense to write code that is
that fragile, and certainly the Standard shouldn't define features that are that
fragile.

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

From: Bob Duff
Sent: Wednesday, May 27, 2015  1:18 PM

> > AdaCore provides two bounded containers that allow indefinite
> > Element_Type:
> >
> > Ada.Containers.Bounded_Holders allows you to create (for
> > example) an array of class-wide, without using pointers or heap
> > allocation.

I shouldn't say "without pointers".  There is a pointer used in the
implementation.   "Without heap allocation" is correct.

> > Ada.Containers.Formal_Indefinite_Vectors is a bounded vector
> > allowing indefinite Element_Type -- again, without pointers or heap
> > allocation.

That one takes a generic formal "Bounded : Boolean := True;".
If Bounded is True, then there's it's bounded, and there is no heap allocation.

> > I'm not sure if these are what Martin Dowie wants; he can take a
> > look at the sources if he's interested.
>
> These still seem like nonsense to me. There's no possible way to have
> an array of class-wide (for example) without pointers or heap
> allocation. At best, you could emulate a heap within the container --
> that might meet the letter of avoiding heap allocation but could not
> avoid the spirit (the internal thing would work the same way), and
> certainly you'd have to have a level of indirection -- which surely
> sounds like a pointer to me. If one only allowed setting of such
> elements once (no change after initialization), you could sort of do
> it (although you'd certainly still need some form of pointers), but
> that would be extremely limiting and nothing like the general containers
> (which allow arbitrary additions and removals of elements).

Sorry, but most of the above paragraph is incorrect.  Please look at the source
code before making further comments.

> I don't see much point in containers that lie about their
> implementation so that they can be used where a direct feature cannot.

There's no "lie" -- these two containers do not use heap allocation (if Bounded
is True for the second one), and do not use anything like the "spirit" of heap
allocation.

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

From: Randy Brukardt
Sent: Wednesday, May 27, 2015  1:52 PM

> Sorry, but most of the above paragraph is incorrect.  Please look at
> the source code before making further comments.

I don't see any point in trying to figure out from source code what is going on.
I'd be very likely to be wrong anyway, and I'm not very familiar with the
internals of your implementation.

Rather, I'd like an explanation of how a container could possible get blocks of
memory of varying sizes, and support some form of deallocation, without working
like a heap. That's the very definition of a heap - anything that supports those
operations is essentially a heap (even if it is not called that).

And I don't see any possible way to avoid those operations (the size of the
memory needed is not known for a class-wide type; avoiding deallocation would be
extremely limiting in that modifications would cause a massive memory leak).

> > I don't see much point in containers that lie about their
> > implementation so that they can be used where a direct feature
> > cannot.
>
> There's no "lie" -- these two containers do not use heap allocation
> (if Bounded is True for the second one), and do not use anything like
> the "spirit" of heap allocation.

Again, please explain. It's logically impossible, with the possible exception of
link-time compilation (which GNAT surely is not an example of). And that's
irrelevant anyway, since we're surely not going to require link-time compilation
for Ada.

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

From: Bob Duff
Sent: Wednesday, May 27, 2015  2:45 PM

> I don't see any point in trying to figure out from source code what is
> going on. I'd be very likely to be wrong anyway, and I'm not very
> familiar with the internals of your implementation.

Sigh.  It's a pretty small amount of code.  I'm sure you could understand it in
less time than it takes you send several emails saying that it's impossible.
;-)

One point is that you need a max size.  Lots of tagged type hierarchies have a
max size.  I can think of several ways the compiler could know that max size.
The one we chose is the simplest: the programmer specifies it, and there are
run-time checks in case it's specified incorrectly.  The downside, of course, is
that you have to fit within a bounded size -- but that's the nature of
"bounded".

There are several other "tricks", if you want to call them that; I refer you to
the code.

> Rather, I'd like an explanation of how a container could possible get
> blocks of memory of varying sizes,

No blocks of varying sizes.

>... and support some form of deallocation, ...

No deallocation.  (Well, local variables are deallocated when leaving a
procedure, but I know that's not what you meant.)

>...without
> working like a heap.

No heap, or anything heap-like.

>...That's the very definition of a heap - anything that  supports those
>operations is essentially a heap (even if it is not called  that).

I'd say a "heap" is something where allocation and deallocation are not
(necessarily) done in LIFO order.

> And I don't see any possible way to avoid those operations (the size
> of the memory needed is not known for a class-wide type; avoiding
> deallocation would be extremely limiting in that modifications would
> cause a massive memory leak).

No memory leaks.

If you still don't believe me, I repeat: Please look at the source code before
making further comments.

> > > I don't see much point in containers that lie about their
> > > implementation so that they can be used where a direct feature
> > > cannot.
> >
> > There's no "lie" -- these two containers do not use heap allocation
> > (if Bounded is True for the second one), and do not use anything
> > like the "spirit" of heap allocation.
>
> Again, please explain. It's logically impossible, with the possible
> exception of link-time compilation (which GNAT surely is not an example of).
> And that's irrelevant anyway, since we're surely not going to require
> link-time compilation for Ada.

I'm not talking about any link-time work (although GNAT is capable of doing
link-time optimization and code gen).  It could be done at run time (but it's
not currently in GNAT).

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

From: Randy Brukardt
Sent: Wednesday, May 27, 2015  4:55 PM

> > I don't see any point in trying to figure out from source code what
> > is going on. I'd be very likely to be wrong anyway, and I'm not very
> > familiar with the internals of your implementation.
>
> Sigh.  It's a pretty small amount of code.  I'm sure you could
> understand it in less time than it takes you send several emails
> saying that it's impossible.  ;-)

Maybe. But I can write a dozen such e-mails before I would figure out where to
look for the source code that you are telling me to read. :-)

> One point is that you need a max size.  Lots of tagged type
> hierarchies have a max size.

Well, every indefinite type has a max size. The problem, of course, is that the
compiler can't know it without some sort of link-time calculation.

> I can think of several ways the
> compiler could know that max size.  The one we chose is the
> simplest: the programmer specifies it, and there are run-time checks
> in case it's specified incorrectly.  The downside, of course, is that
> you have to fit within a bounded size -- but that's the nature of
> "bounded".

Ah, you're making the user calculate the uncalculable. I'd consider that a
compiler-specific hack, not something suitable for general use. (After all,
there is no requirement that an object of an indefinite type even be
contiguous.) It also adds coupling that shouldn't exist, because now the size
has to be adjusted whenever new types are added. Of course, the only way to
remove that coupling is to force it to be calculated at bind-time, and Ada
doesn't make such a requirement. Perhaps a particular implementation could, but
that's not useful for the Ada Standard.

The provision of such a size makes the container tailored to a specific type (or
hierarchy in this case). I've always said *that* is possible, but that's not
very valuable or interesting. (It also would waste a massive amount of space in
the hierarchies I've been associated with, but I suppose there must exist some
hierarchies were all of the types are roughly the same size.)

...
> >...That's the very definition of a heap - anything that supports those
> >operations is essentially a heap (even if it is not called  that).
>
> I'd say a "heap" is something where allocation and deallocation are not
> (necessarily) done in LIFO order.

Right. That goes without saying (there's no restrictions on the order that
allocate and deallocate operations are called). That's the case in this
situation (baring some sort of make-the-user-provide-a-max-size).

> > And I don't see any possible way to avoid those operations (the size
> > of the memory needed is not known for a class-wide type; avoiding
> > deallocation would be extremely limiting in that modifications would
> > cause a massive memory leak).
>
> No memory leaks.

Unless you count wasting 80% of the memory using a max-size strategy. ;-) [OK,
that's not fair.]

> If you still don't believe me, I repeat: Please look at the source
> code before making further comments.

Still don't know where I would look to find it.

...
> > Again, please explain. It's logically impossible, with the possible
> > exception of link-time compilation (which GNAT surely is not an
> > example of).
> > And that's irrelevant anyway, since we're surely not going to
> > require link-time compilation for Ada.
>
> I'm not talking about any link-time work (although GNAT is capable of
> doing link-time optimization and code gen).  It could be done at run
> time (but it's not currently in GNAT).

But if you did it at run-time, you'd have to allocate the block of memory
dynamically. That's going to be a heap, unless you have some way to find out
what pool to allocate in and then have a "stack pool" to allocate from. (The
Janus/Ada compiler has these things but of course they're not materialized at
the Ada level.) [I don't see any sensible way to do it at run-time, either, as
the container is not going to have a way to find out all of the types in a
hierarchy; Ada only provides operations toward the root of a hierarchy.]

In order to truly be free of an allocation, the maximum size has to be
determined before execution (presumably at bind or link-time).

Anyway, I'll admit that I forgot about the possibility of using the maximum size
when I originally responded. (I historically don't like maximum size solutions
to anything, because of my background in very small systems and the associated
memory waste. But it's clear that on modern systems that one can afford to waste
memory for other goals, so it's not as bad as it once was.) But I will contend
that in the absence of requiring the compiler to calculate such things
pre-execution, it's not really a practical solution (any such code will be
completely non-portable, even to newer versions of the same compiler).

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

From: Emmanuel Briot
Sent: Thursday, May 28, 2015  2:33 AM

> The provision of such a size makes the container tailored to a
> specific type (or hierarchy in this case). I've always said *that* is
> possible, but that's not very valuable or interesting. (It also would
> waste a massive amount of space in the hierarchies I've been
> associated with, but I suppose there must exist some hierarchies were
> all of the types are roughly the same size.)

Of course the instance of the container is tailored to a specific hierarchy,
since the actual parameter is known at instantiation time.

In general, applications that want to forbid dynamic memory allocations also
have a very controlled usage of tagged types, and it often happens that all the
possible children of the Element_Type are actually defined in the same package,
so using a 'Max to get the maximum size is a trivial operation. Remember that we
are speaking of very specific applications here, not general usage of Ada.

>> If you still don't believe me, I repeat: Please look at the source
>> code before making further comments.
>
> Still don't know where I would look to find it.

Ada.Containers.Formal_Indefinite_Vectors is the GNAT runtime, as well as
Ada.Containers.Bounded_Holders. The files are a-cfinve.ads and a-coboho.ads

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

From: Martin Dowie
Sent: Saturday, June 6, 2015  5:19 AM

Thanks to all for the responses - much appreciated.

FYI, this isn't a `safety' related set of code but it is embedded, so I would
prefer to be able to bound all sizes at 'code time'. My way of thinking about
this is that I have 2 'size axes' - one the number of objects to be held in each
container instance, the other the max size of all possible objects of that type.
While the root (interface) type clearly does't have a max size at the point I
define the container instance, I would have loved ot have been able to bound the
number of items in that container type, e.g. I may have 1 instance of a very
large vector and many smaller but both containing items in that hierarchy. In
other words bound one axis. The other axis would eventually be bound by the max
size of each nodes in the type hierarchy and the number of container instances.

I was thinking it might look something like this (in some 'new' Ada):

type I is interface;
...
package Large is new Ada.Containers.Bounded_Indefinite_Vectors (1000, I'Class);
package Small is new Ada.Containers.Bounded_Indefinite_Vectors (4, I'Class);
..
LV : Large.Vector;
SV1 : Small.Vector;
SV2 : Small.Vector;

I'd prefer this as I may not have memory for N * Large.Vector. I think this is
very readable and clean - at least from the users perspective. Who knows what
nastiness may have had to appear inside
Ada.Containers.Bounded_Indefinite_Vectors!!

Anyway, for now, I shall just have to use a bounded vector or access types and
be very careful with my storage pools.

John: thanks for the rationale - I'm going to have a hack around and try and
make them accessible from the GPS help menu.

Finally, the GNAT indefinite containers didn't work for me as the are limited
and I'd have to have made my interfaces limited and that just brings in a world
of pain for me.

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

From: Randy Brukardt
Sent: Monday, June 8, 2015  3:53 PM

> Thanks to all for the responses - much appreciated.
>
> FYI, this isn't a 'safety' related set of code but it is
> embedded, so I would prefer to be able to bound all sizes at
> 'code time'. My way of thinking about this is that I have 2
> 'size axes' - one the number of objects to be held in each
> container instance, the other the max size of all possible
> objects of that type. While the root (interface) type clearly
> does't have a max size at the point I define the container
> instance, I would have loved ot have been able to bound the
> number of items in that container type, e.g. I may have 1
> instance of a very large vector and many smaller but both
> containing items in that hierarchy. In other words bound one
> axis. The other axis would eventually be bound by the max
> size of each nodes in the type hierarchy and the number of
> container instances.

You can already do this (assuming you don't mind some heap allocation) by
using dynamic predicates on the unbounded indefinite containers. The dynamic
predicate would bound the number of elements in each object; the other
dimension is a virtual bound anyway, you're just trying to guarentee that
you have enough memory available (right?).

> I was thinking it might look something like this (in some 'new' Ada):
>
> type I is interface;
> ...
> package Large is new
> Ada.Containers.Bounded_Indefinite_Vectors (1000, I'Class);

BTW, you forgot the index subtype for the vector here.

> package Small is new
> Ada.Containers.Bounded_Indefinite_Vectors (4, I'Class); ...
> LV : Large.Vector;
> SV1 : Small.Vector;
> SV2 : Small.Vector;

That would look like:

type I is interface;
...

package IVector is new  Ada.Containers Indefinite_Vectors (I'Class,
Index_Subtype);

subtype Large_Vector is Ivector.Vector with
   Dynamic_Predicate => Large_Vector.Length in 0 .. 1000;
subtype Small_Vector is Ivector.Vector with
   Dynamic_Predicate => Small_Vector.Length in 0 .. 4;
LV : Large_Vector;
SV1 : Small_Vector;
SV2 : Small_Vector;

The predicate will get checked on every subtype conversion and on return
from any subprogram that passes it as an in out parameter. In this case,
that should prevent any problems (the predicate isn't checked if individual
components are updated, but that can't happen here). There's an ACATS test
like this based on a previous thread here, so this is highly likely to work
correctly.

There's not much point in declaring a separate container type for this,
because the above does the job as well. The point of a separate container is
to change the way that it internally manages the memory (the bounded
containers do static memory management), but that requires putting
restrictions on the element type and/or severe new restrictions on the
compiler implementation, plus some sort of link-time code generation (at
least value calculation), which to me seems over the top of the standard
(Ada is used by more than just people with heavy coding restrictions; at
least I hope that we want that to be true).

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

Questions? Ask the ACAA Technical Agent