Version 1.3 of ai05s/ai05-0001-1.txt

Unformatted version of ai05s/ai05-0001-1.txt version 1.3
Other versions for file ai05s/ai05-0001-1.txt

!standard A.18(0/2)          08-10-23 AI05-0001-1/02
!class Amendment 05-10-24
!status work item 06-03-15
!status received 05-10-02
!priority Medium
!difficulty Hard
!subject Bounded containers and other container issues
!summary
(See proposal.)
!problem
The Ada 2005 containers were intended to provide the needs of most common uses (often estimated as 80%). What about the other 20%?
In particular, better control over storage management is needed for real-time systems. Some users have indicated that access to a single container by multiple tasks is needed.
!proposal
Bounded forms for all of the containers are added to Ada. We also add task-safe queues, generalized sorting, and case-insensitive comparison and hashing operations.
!wording
Bounded Vector
The bounded vector differs from the unbounded vector as follows:
The package is named Ada.Containers.Bounded_Vectors.
The package has Pure categorization.
The container type is declared with a discriminant that specifies the capacity, as follows:
type Vector (Capacity : Count_Type) is tagged private;
[ARG] We agreed during the meeting on 2008/09/22 that the bounded forms would not be controlled. Do we need to say that? One consequence is this is that we cannot detect finalization of the container when it's in a tampering state, e.g.
declare V : Vector_Access := new Vector (42);
procedure Process (E : ET) is begin Free (V); end; begin V.Query_Element (1, Process'access); end;
How should be handle this case?
We also have the problem of assignment during a tampering context:
declare V1, V2 : Vector (42);
procedure Process (E : ET) is begin V2 = V1; end; begin V1.Query_Element (1, Process'access); -- (1) V2.Delete_First; -- (2) end;
Here the tampering bit gets set on V1 when we enter Query_Element (1), and it get copied to V2. In principle the deletion (2) should work, but unless we do something special it would incorrectly raise Program_Error. It think we agreed in NYC that such pathological assignments would be considered a bounded error, but we need a definitive confirmation. [END ARG]
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out Vector; Source : Vector);
function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector;
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and appends each element in Source to Target.
[ARG]: We need to decide what exception to raise if Source.Length is greater then Target.Capacity. I think Storage_Error makes the most sense, but a case could be made for Constraint_Error. Also, we need to decide whether the check precedes the clear (which would prevent side-effect if check fails).
The semantics of Copy is as follows. The function declares a bounded vector object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity argument, then appends each element of Source to Target, and finally returns the Target object.
[ARG]: Is this over-specified?
[ARG]: Should append Append, Insert, etc, say what happens if vector length equals vector capacity?
[ARG]: Is there anything we want to say about the relationship between the range of Index_Type and vector capacity? It's possible to declare a vector object with a capacity smaller than the range of the index subtype (and this makes sense for types as Positive, etc), but it's also possible to declare a vector object with a capacity larger than the range -- but we could never even add those elements, since the maximum vector length is determined by the range of the index subtype. Should we allow this? [END ARG]
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) elements from Source to Target, and finally clears Source.
[ARG]: What exception when Src.Len > Tgt.Cap?
[ARG]: For Vector'Read, do we need to specify what happens if the number of elements in the stream is larger than the capacity of the vector object? I explicitly check, the same as for Insert et al.
The semantics of Reserve_Capacity is as follows. If the specified Capacity is larger than the Container.Capacity, then it raises Storage_Error. Otherwise, the operation does nothing.
[ARG]: Is this the correct exception?
The semantics of Set_Length are as follows. If Length is greater than the Container.Capacity, then it raises Storage_Error. If Container is busy, then it raises Program_Error. Otherwise it sets the container length to the specified value.
[ARG] What exception when Len > Container.Cap? Also, do we need a check to ensure that the new length (really, the value returned by Last_Index) is within the range of the index subtype? (This also applies to To_Vector.)
Bounded Doubly-Linked List
The bounded doubly-linked list differs from the unbounded list as follows.
The package is named Ada.Containers.Bounded_Doubly_Linked_Lists.
The package has Pure categorization.
The list container type is declared with a discriminant that specifies the capacity, as follows:
type List (Capacity : Count_Type) is tagged private;
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out List; Source : List);
function Copy (Source : List; Capacity : Count_Type := 0) return List;
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and appends each element in Source to Target.
[ARG]: Perhaps we can consolidate the descriptions of Assign and Copy into a single place, so we only have to describe these operations once.
The semantics of Copy is as follows. The function declares a bounded list object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity argument, then appends each element of Source to Target, and finally returns the Target object.
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) elements from Source to Target, and finally clears Source.
[ARG]: This isn't really how it's done. Really, it copies an element from source to target, and then (assuming the assignment succeeds) unlinks it from source. This process repeats until the source list is exhausted. I don't know how much or how little needs to be specified.
[ARG]: Do we need to state this explicitly: (Swap_Links doesn't change) (Splice with one container also doesn't change) [END ARG].
The semantics of
procedure Splice
(Target : in out List;
Before : Cursor; Source : in out List);
differ from the unbounded form as follows. All elements of Source are copied (preserving their order) to Target, at the position immediately preceeding Before, and then deleted from Source. (Moving elements from Source is not possible for a bounded from, since storage for nodes is associated with the container object.)
[ARG]: We probably don't want to overspecify here, since we want to allow one element at a time to be copied to the target and then immediately deleted from source. [END ARG]
The semantics of
procedure Splice
(Target : in out List;
Before : Cursor; Source : in out List; Position : in out Cursor);
differ from the unbounded form as follows. The element of Source designated by Position is copied to Target, at the position immediately preceeding Before, and then deleted from Source. On return, cursor Position designates the newly-inserted element of Target.
[ARG]: We might not need to bring this up at all, for either version of splice. We do say in the RM that the elements are "removed from Source and moved to Target", but you could interpret that liberally for our purposes here, to mean that the elements are "removed from Source and copied to Target". [END ARG]
Bounded Hashed Map
The bounded hashed map differs from the unbounded hashed map as follows.
The package is named Ada.Containers.Bounded_Hashed_Maps.
The package has Pure categorization.
The container type is declared with a discriminant that specifies both the capacity (number of elements) and modulus (length of buckets array), as follows:
type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private;
The semantics of Reserve_Capacity is as follows. If the specified Capacity is larger than the Container.Capacity, then it raises Storage_Error. Otherwise, the operation does nothing.
[ARG] Actually, I think this has the same behavior as the unbounded form (since in principle the unbounded form could also raise an exception "if the specified capacity is larger than the container capacity". Since this API is just supposed to specify how the bounded form differs from the unbounded form, then do we need to mention Reserve_Capacity here? [END ARG]
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out Map; Source : Map);
function Copy (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map;
[ARG] Need ruling about whether the formal parameter should be "Source" or "Container".
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and inserts each key/element pair of Source into Target.
The semantics of Copy are as follows. The function declares a bounded hashed map object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity argument, and a modulus determined as follows. If the Modulus parameter is 0, then the Target's modulus is the value returned by a call of function Default_Modulus with the capacity specified as above; otherwise the Target's modulus is the value of the actual parameter. The operation then inserts each key/element pair of Source into Target, and finally returns the Target object.
[ARG] Another way to say that last sentence is:
"The operation then calls Target.Assign (Source), and finally returns the Target object."
Any preference? [END ARG]
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) the key/element pairs from Source to Target, and finally clears Source.
[ARG] The implementation advice in RM05 A.18.4 says:
83/2 Move should not copy elements, and should minimize copying of internal data structures.
Do we need some new implementation advice somewhere? [END ARG]
Immediately following operation Iterate, the following operation is declared:
function Default_Modulus (Capacity : Count_Type) return Hash_Type;
Default_Modulus returns the length of a buckets array that would be proper for hashing the given capacity (maximum number of elements). This is useful for specifying descriminant values for the declaration of a bounded hashed map object.
[ARG]: Should be define "proper"?
Bounded Ordered Map
The bounded ordered map differs from the unbounded ordered map as follows.
The package is named Ada.Containers.Bounded_Ordered_Maps.
The package has Pure categorization.
The container type is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:
type Map (Capacity : Count_Type) is tagged private;
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out Map; Source : Map);
function Copy (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map;
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and inserts each key/element pair of Source into Target.
The semantics of Copy are as follows. The function declares a bounded ordered map object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity parameter. The operation then inserts each key/element pair of Source into Target, and finally returns the Target object.
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) the key/element pairs from Source to Target, and finally clears Source.
Bounded Hashed Set
The bounded hashed set differs from the unbounded hashed set as follows.
The package is named Ada.Containers.Bounded_Hashed_Sets.
The package has Pure categorization.
The container type is declared with a discriminant that specifies both the capacity (maximum number of elements) and modulus (length of buckets array), as follows:
type Set (Capacity : Count_Type; Modulus : Hash_Type) is tagged private;
The semantics of Reserve_Capacity is as follows. If the specified Capacity is larger than the Container.Capacity, then it raises Storage_Error. Otherwise, the operation does nothing.
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out Set; Source : Set);
function Copy (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Set;
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and inserts (a copy of) each element of Source into Target.
The semantics of Copy are as follows. The function declares a bounded hashed set object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity argument, and a modulus determined as follows. If the Modulus parameter is 0, then the Target's modulus is the value returned by a call of function Default_Modulus with the capacity specified as above; otherwise the Target's modulus is the value of the actual parameter. The operation then inserts (a copy of) each element of Source into Target, and finally returns the Target object.
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) the elements from Source to Target, and finally clears Source.
Immediately following operation Iterate, the following operation is declared:
function Default_Modulus (Capacity : Count_Type) return Hash_Type;
Default_Modulus returns the length of a buckets array that would be proper for hashing the given capacity (maximum number of elements). This is useful for specifying descriminant values for the declaration of a bounded hashed set object.
Bounded Ordered Set
The bounded ordered set differs from the unbounded ordered set as follows.
The package is named Ada.Containers.Bounded_Ordered_Sets.
The package has Pure categorization.
The container type is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:
type Set (Capacity : Count_Type) is tagged private;
Immediately following the declaration of operation Clear, the following pair of operations are declared:
procedure Assign (Target : in out Set; Source : Set);
function Copy (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Set;
The semantics of Assign are as follows. If Target denotes the same object as Source, the operation does nothing. If Source length is greater than Target capacity, then the operation raises Storage_Error. Otherwise, it clears Target and inserts (a copy of) each element of Source into Target.
The semantics of Copy are as follows. The function declares a bounded ordered set object (call it the Target) whose capacity is the maximum of Source.Length and the Capacity parameter. The operation then inserts (a copy of) each element Source into Target, and finally returns the Target object.
The semantics of Move are as follows. If Target denotes the same object as Source, the operation does nothing. If Source is busy, then it raises Program_Error. If Source.Length is greater than Target.Capacity, then it raises Storage_Error. Otherwise, the operation clears Target, then copies (not moves -- which is not possible for a bounded form) the elements from Source to Target, and finally clears Source.
protected Queues
[ARG] Is parameter name "Q" OK? Should this be "Container"?
The generic library package Containers.Queues has the following declaration:
generic type Element_Type is private;
package Ada.Containers.Queues is pragma Pure;
type Queue is synchronized interface;
procedure Enqueue (Q : in out Queue; New_Item : Element_Type) is abstract; pragma Implemented (Enqueue, By_Entry);
procedure Dequeue (Q : in out Queue; Element : out Element_Type) is abstract; pragma Implemented (Dequeue, By_Entry);
function Is_Full (Q : Queue) return Boolean is abstract;
-- [ARG] What about: -- -- procedure Enqueue -- (Q : in out Queue; -- New_Item : in Element_Type; -- Existing : out Count_Type) is abstract; -- -- procedure Dequeue -- (Q : in out Queue; -- Element : out Element_Type; -- Remaining : out Count_Type) is abstract; -- -- function Length (Q : Queue) return Count_Type is abstract; -- -- [END ARG]
end Ada.Containers.Queues;
Interface Queue specifies a first-in, first-out queue.
Enqueue copies New_Item onto the back of the queue. If Is_Full is True, then Enqueue waits on the entry for storage to become available.
Dequeue removes the element at the front of the queue, and returns a copy of the element. Is Is_Empty is True, then Dequeue waits on the entry for an item to become available.
Is_Empty returns an indication of whether the queue contains items.
Is_Full returns an indication of whether the queue is able to contain more items.
The generic library package Containers.Queues.Bounded has the following declaration:
generic package Queues.Bounded is -- [ARG]: Should this be Generic_Bounded? pragma Pure; -- [ARG] OK? (Can PO be pure?)
type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private;
private
-- not specified
end Queues.Bounded;
The bounded queue specifies a queue with finite capacity. Is_Full returns True when the length (the current number of items) equals the capacity.
The generic library package Containers.Queues.Unbounded has the following declaration:
generic package Queues.Unbounded is -- [ARG]: Should this be Generic_Unbounded? pragma Preelaborate; -- [ARG] OK?
type Queue is synchronized new Queues.Queue with private;
private
-- not specified
end Queues.Unbounded;
The unbounded queue specifies a queue with no specified maximum capacity. Is_Full always returns False. Enqueue will never block (although it can fail for other reasons, e.g. storage is exhausted).
Generic_Sort
The following generic sort procedure is defined:
generic type Index_Type is (<>); with function Less (Left, Right : Index_Type) return Boolean is <>; with procedure Swap (Left, Right : Index_Type) is <>;
procedure Ada.Containers.Generic_Sort (First, Last : Index_Type'Base); pragma Pure (Ada.Containers.Generic_Sort);
Reorders the elements of an anonmyous array-like container, over the range First .. Last, such that the elements are sorted smallest first as determined by the generic formal Less function provided. Generic formal Less compares the container elements having the given indices, and generic formal Swap exchanges the values of the indicated container elements. Any exception raised during evaluation of Less or Swap is propagated.
The actual function for the generic formal function Less of Generic_Sort is expected to return the same value each time it is called with a particular pair of element values. It should define a strict ordering relationship, that is, be irreflexive, asymmetric, and transitive; it should not modify the container. If the actual for Less behaves in some other manner, the behavior of the instance of Generic_Sort is unspecified. How many times Generic_Sort calls Less or Swap is unspecified.
Case-Insensitive Operations
The library function Strings.Hash_Case_Insensitive has the following declaration:
with Ada.Containers; function Ada.Strings.Hash_Case_Insensitive (Key : String) return Containers.Hash_Type; pragma Pure (Ada.Strings.Hash_Case_Insensitive);
Returns an implementation-defined value which is a function of the value of Key, folded to lower case. If A and B are strings such that A equals B, Hash_Case_Insensitive(A) equals Hash_Case_Insensitive(B).
The library function Strings.Fixed.Hash_Case_Insensitive has the following declaration:
with Ada.Containers, Ada.Strings.Hash_Case_Insensitive; function Ada.Strings.Fixed.Hash_Case_Insensitive (Key : String) return Containers.Hash_Type renames Ada.Strings.Hash_Case_Insensitive; pragma Pure(Hash_Case_Insensitive);
The generic library function Strings.Bounded.Hash_Case_Insensitive has the following declaration:
with Ada.Containers; generic with package Bounded is new Ada.Strings.Bounded.Generic_Bounded_Length (<>); function Ada.Strings.Bounded.Hash_Case_Insensitive (Key : Bounded.Bounded_String) return Containers.Hash_Type; pragma Preelaborate(Hash_Case_Insensitive);
Strings.Bounded.Hash_Case_Insensitive is equivalent to the function call Strings.Hash_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Hash_Case_Insensitive has the following declaration:
with Ada.Containers; function Ada.Strings.Unbounded.Hash_Case_Insensitive (Key : Unbounded_String) return Containers.Hash_Type; pragma Preelaborate(Hash_Case_Insensitive);
Strings.Unbounded.Hash_Case_Insensitive is equivalent to the function call Strings.Hash_Case_Insensitive (To_String (Key));
The library function Strings.Equal_Case_Insensitive has the following declaration:
function Ada.Strings.Equal_Case_Insensitive
(Left, Right : String) return Boolean;
pragma Pure (Ada.Strings.Equal_Case_Insensitive);
Compares strings Left and Right, folded to lower case, for equality.
The library function Strings.Fixed.Equal_Case_Insensitive has the following declaration:
with Ada.Containers, Ada.Strings.Equal_Case_Insensitive; function Ada.Strings.Fixed.Equal_Case_Insensitive (Key : String) return Boolean renames Ada.Strings.Equal_Case_Insensitive; pragma Pure(Equal_Case_Insensitive);
The generic library function Strings.Bounded.Equal_Case_Insensitive has the following declaration:
with Ada.Containers; generic with package Bounded is new Ada.Strings.Bounded.Generic_Bounded_Length (<>); function Ada.Strings.Bounded.Equal_Case_Insensitive (Left, Right : Bounded.Bounded_String) return Boolean; pragma Preelaborate(Equal_Case_Insensitive);
Strings.Bounded.Equal_Case_Insensitive is equivalent to the function call Strings.Equal_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Equal_Case_Insensitive has the following declaration:
with Ada.Containers; function Ada.Strings.Unbounded.Equal_Case_Insensitive (Left, Right : Unbounded_String) return Boolean; pragma Preelaborate(Equal_Case_Insensitive);
Strings.Unbounded.Equal_Case_Insensitive is equivalent to the function call Strings.Equal_Case_Insensitive (To_String (Key));
The library function Strings.Less_Case_Insensitive has the following declaration:
function Ada.Strings.Less_Case_Insensitive
(Left, Right : String) return Boolean;
pragma Pure (Ada.Strings.Less_Case_Insensitive);
Performs a lexicographic comparison of strings Left and Right, folded to lower case.
The library function Strings.Fixed.Less_Case_Insensitive has the following declaration:
with Ada.Containers, Ada.Strings.Less_Case_Insensitive; function Ada.Strings.Fixed.Less_Case_Insensitive (Key : String) return Boolean renames Ada.Strings.Less_Case_Insensitive; pragma Pure(Less_Case_Insensitive);
The generic library function Strings.Bounded.Less_Case_Insensitive has the following declaration:
with Ada.Containers; generic with package Bounded is new Ada.Strings.Bounded.Generic_Bounded_Length (<>); function Ada.Strings.Bounded.Less_Case_Insensitive (Left, Right : Bounded.Bounded_String) return Boolean; pragma Preelaborate(Less_Case_Insensitive);
Strings.Bounded.Less_Case_Insensitive is equivalent to the function call Strings.Less_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Less_Case_Insensitive has the following declaration:
with Ada.Containers; function Ada.Strings.Unbounded.Less_Case_Insensitive (Left, Right : Unbounded_String) return Boolean; pragma Preelaborate(Equal_Case_Insensitive);
Strings.Unbounded.Less_Case_Insensitive is equivalent to the function call Strings.Less_Case_Insensitive (To_String (Key));
!discussion
The forms added were decided at the September subcommittee meeting in New York.
We need to copy some info from the notes from that meeting here to justify these choices better.
!example
!ACATS test
!appendix

From: Martin Dowie
Date: Sunday, Octoher 2, 2005  1:12 PM

I didn't realize that changes were still being proposed/allowed at this
stage until Randy sent in the "extends" email. :-)

I have a suggestion that I hope will be fairly simple and hopefully
useful...

I think that we could extend the Ada.Containers.* hierarchy to include
"Bounded_" variants of each container type by defining that each bounded
package has exactly the same specification as the unbounded version,
except that the container type has a "(Max_Length : Count_Type)" constraint.

Insert/Append routines would raise a Constraint_Error if "Length
(Container) = Max_Length" (or, a "Length_Error : exception;" could be
added to Ada.Containers).

The only 'tricky' bit is what to with:

1) procedure Set_Length
Either check and raise exception or limit to Max_Length even if "Length
 > Container.Max_Length"?

2) each function "&" =>
   a) if Left or Right is the only container then simply check for space;
   b) if Left and Right are elements then return a Max_Length => 2
container;
   c) if Left and Right are containers then append as much of Right to a
new container with Max_Length of Left.Max_Length.

Alternatively for "&" they could return a new container of
Left.Max_Length + Right.Max_Length but that seems against the nature of
bounded things and not so much in keeping with bounded strings. I'm not
too fussed about what the 'actual' rules are/would be, I'm just pointing
out that these are the only things that would need any discussion.

Anyway, I hope I've shown that it would be /simple/ to double the size
of the Ada.Container.* hierarchy with very little effort (and by effort,
I mean 'text'! :-), in much the same way as "Wide_" packages are added
to the RM.

I have a sample "Ada.Containers.Bounded_Vectors" if anyone would like to
see such a beast.

p.s. My $0.02 would choose "check&raise" for what to do with
Set_Length/"&" subprograms, by the way ;-)

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

From: Bob Duff
Date: Sunday, October 2, 2005  8:33 PM

> I didn't realize that changes were still being proposed/allowed at this
> stage until Randy sent in the "extends" email. :-)

I think Randy's suggestion was for Ada 201X, not Ada 2005.  ;-)

> I have a suggestion that I hope will be fairly simple and hopefully
> useful...
>
> I think that we could extend the Ada.Containers.* hierarchy to include
> "Bounded_" variants of each container type by defining that each bounded
> package has exactly the same specification as the unbounded version,
> except that the container type has a "(Max_Length : Count_Type)" constraint.

Hmm... If I say:

    X: Bounded_Whatever(Max_Length => 80);
    ...
    X := Y & Z;

where Length(Y) + Length(Z) <= 80, I would like it to work.
I don't know how to do that in Ada.

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

From: Jeffrey Carter
Date: Sunday, October 2, 2005  10:04 PM

> I think that we could extend the Ada.Containers.* hierarchy to include
> "Bounded_" variants of each container type by defining that each bounded
> package has exactly the same specification as the unbounded version,
> except that the container type has a "(Max_Length : Count_Type)"
> constraint.

This doesn't work very well, because user-defined assignment doesn't handle
this kind of thing. That's why bounded strings have the limit as a generic
formal constant, not a discriminant on Bounded_String.

Somehow, I doubt anything is being considered for Ada 0X anymore. Randy said
his suggestion was for Ada 1X.

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

From: Matthew Heaney
Date: Monday, October 3, 2005  9:05 AM

> I think that we could extend the Ada.Containers.* hierarchy to include
> "Bounded_" variants of each container type by defining that each bounded
> package has exactly the same specification as the unbounded version,
> except that the container type has a "(Max_Length : Count_Type)"
> constraint.

The container type would have to be limited, because of assignment behavior.

What you refer to as Max_Length above is really just capacity.

> 1) procedure Set_Length
> Either check and raise exception or limit to Max_Length even
 > if "Length > Container.Max_Length"?

Just raise CE.

> 2) each function "&" =>
>   a) if Left or Right is the only container then simply check for space;
>   b) if Left and Right are elements then return a Max_Length => 2
> container;
>   c) if Left and Right are containers then append as much of Right to a
> new container with Max_Length of Left.Max_Length.

No.  Operator "&" is gone, because the type has to be limited.

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

From: Martin Dowie
Date: Monday, October 3, 2005  10:17 AM

I could live with either "Max_Length" or "Capacity".

Why would "&" have to go? They are present in "Bounded_String"-s...

Can you give me an example of the problems with assignment behaviour?
Because just now I'm sitting in front of something that seems to work
fine with everything I try and throw at it.

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

From: Matthew Heaney
Date: Monday, October 3, 2005  10:30 AM

> Why would "&" have to go? They are present in "Bounded_String"-s...

Because there's nothing you can to do with the result, if the type is
limited.

Actually, I should take that back.  Operator "&" could become a
constructor-type function (aka "initializer"), since you would only be
able to use it during the declaration of the bounded contained object
(because the type is limited).

> Can you give me an example of the problems with assignment behaviour?
> Because just now I'm sitting in front of something that seems to work
> fine with everything I try and throw at it.

Assuming the type were non-limited:

declare
    C1 : CT (42);
    C2 : CT (1963);
begin
    C2 := C1;  -- raises CE
end;

(But maybe there were some changes in semantics for Ada 2005, such that
the assignment no longer raises CE.)

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

From: Matthew Heaney
Date: Monday, October 3, 2005  11:29 AM

> Hmm... If I say:
>
>     X: Bounded_Whatever(Max_Length => 80);
>     ...
>     X := Y & Z;
>
> where Length(Y) + Length(Z) <= 80, I would like it to work.
> I don't know how to do that in Ada.

Hmmm... Why not?  If the discriminant of the result of Y & Z is the same
as X, then the assignment will succeed.  And the sum of the lengths can
be calculated in the implementation of "&".

Another issue wrt assignment of bounded forms is the (in)efficiency,
since there will be a bitwise copy of both the active and inactive
("free store") elements.

Martin: the Charles library has bounded list forms (having a clever
implementation of the free store, IMHO).  You can play around with those
if you want to get some more data...

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

From: Martin Dowie
Date: Monday, October 3, 2005  11:50 AM

Thanks Matt - I'll take a look - is there an easy 'zipped' version of
the head, or do I need to download each file individually? (I've never
really used CVS)

And while I can't do:
declare
   C1 : CT (42);
   C2 : CT (1963);
begin
   C2 := C1;  -- raises CE
end;

I can do:
declare
   C1 : CT (42);
   C2 : CT (1963);
begin
   C2 := C2 & C1;  -- works fine
end;

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

From: Bob Duff
Date: Monday, October 3, 2005  12:26 PM

> Hmmm... Why not?  If the discriminant of the result of Y & Z is the same
> as X, then the assignment will succeed.  And the sum of the lengths can
> be calculated in the implementation of "&".

I was thinking of this:

    type Bounded_Sequence(Max_Length: Natural) is
        record
            Elements: Element_Array(1..Max_Length);
            Length: Natural := 0;
        end record;

    X: Bounded_Sequence(Max_Length => 80);
    Y: Bounded_Sequence(Max_Length => 40);
    ...

Now, if Y.Length = 20, I would like to be able to say "X := Y",
since the length of Y is shorter than the Max_Length of X.
But that doesn't work.

Same issue for "X := Y & Z" -- the "&" operation can calculate the right
length for the result, but it can't calculate the right Max_Length.

As you pointed out in another message, this is why Bounded_Strings is
generic on the max length.  That means all objects of a given type will
have the same max length, thus trivially ensuring that, as you said
above, the max length "of the result of Y & Z is the same as X".

> Another issue wrt assignment of bounded forms is the (in)efficiency,
> since there will be a bitwise copy of both the active and inactive
> ("free store") elements.

Good point.  Of course that doesn't matter if the thing is limited,
and if it's limited, the issues about assignment and "&" go away.
In Ada 2005, limited is one good way to go.

In any case, it's not _trivial_ to add these bounded versions,
nor to decide on their exact semantics.  So I think it's unlikely that
they will be included in Ada 2005.  Go for 2015!

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

From: Martin Dowie
Date: Monday, October 3, 2005  11:26 PM

>I think Randy's suggestion was for Ada 201X, not Ada 2005.  ;-)
>
>
Apologies for being a bit early with my Ada1Z proposal then! :-)


>Hmm... If I say:
>
>    X: Bounded_Whatever(Max_Length => 80);
>    ...
>    X := Y & Z;
>
>where Length(Y) + Length(Z) <= 80, I would like it to work.
>I don't know how to do that in Ada.
>
Ok, I'm confused by this one as my implementation seems to do the right
thing for this!...

Anyway, I guess all this can wait for the ISO IWA.

-- bounded_integer_vectors.ads
with Ada.Containers.Bounded_Vectors;

package Bounded_Integer_Vectors is
   new Ada.Containers.Bounded_Vectors (Natural, Integer);

-- test_biv.adb
with Ada.Containers; use Ada.Containers;
with Ada.Exceptions; use Ada.Exceptions;
with Ada.Text_IO;    use Ada.Text_IO;

with Bounded_Integer_Vectors; use Bounded_Integer_Vectors;

procedure Test_BIV is
   subtype Vector_3 is Vector (3);
   V1, V2, V3 : Vector_3;
begin
   Put_Line ("Length =>" & Count_Type'Image (V1.Length));
   V1.Append (1);
   Put_Line ("Length =>" & Count_Type'Image (V1.Length));
   V1.Append (3);
   Put_Line ("Length =>" & Count_Type'Image (V1.Length));
   V1.Append (6);
   Put_Line ("Length =>" & Count_Type'Image (V1.Length));
   begin
      V1.Append (10);
   exception
      when Error : others =>
         Put_Line ("!!! " & Exception_Message (Error));
   end;
   Put_Line ("Length =>" & Count_Type'Image (V1.Length));
   Put_Line ("Length =>" & Count_Type'Image (V3.Length));
   V3 := V1 & V2;
   Put_Line ("Length =>" & Count_Type'Image (V3.Length));
end Test_BIV;

-- result.txt
C:\Ada\Bounded_Containers\gps\obj\test_biv.exe
Length => 0
Length => 1
Length => 2
Length => 3
!!! Insert error, already full.
Length => 3
Length => 0
Length => 3

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

From: Bob Duff
Date: Tuesday, October 4, 2005  12:01 PM

> Ok, I'm confused by this one as my implementation seems to do the right
> thing for this!...

>    subtype Vector_3 is Vector (3);
>    V1, V2, V3 : Vector_3;

Try it like this:

    V1, V2: Vector_3;
    V3: Vector(6);

6 is plenty big enough to store 3 characters, but the assignment
will raise Constraint_Error.

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

From: Martin Dowie
Date: Tuesday, October 4, 2005  12:32 PM

Well, that depends on what I make "&" mean! :-)

   declare
      C1, C2 : Bounded_Integer_Vectors.Vector (3);
      C3     : Bounded_Integer_Vectors.Vector (6);
   begin
      C1.Append (1);
      C1.Append (3);
      C1.Append (7);
      C2.Append (11);
      C2.Append (13);
      C2.Append (17);
      C3 := C1 & C2;
      Put_Line ("+++ No exception raised");
      Put_Line ("Length =>" & Count_Type'Image (C3.Length));
   exception
      when Error : others =>
         Put_Line ("!!! " & Exception_Message (Error));
   end;

-- results.txt
+++ No exception raised
Length => 6

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

From: Jeffrey Carter
Date: Tuesday, October 4, 2005  1:00 PM

>   Well, that depends on what I make "&" mean! :-)

Sure, but the point is that there's no way to make

A := B & C;

work for any A, B, & C such that

Length (B) + Length (C) <= A.Max_Length.

Indeed, if you can make it work for your example and for

A : Vector ( 7);
B : Vector (10);
C : Vector (23);

Length (B) = 3
Length (C) = 3

I'll be impressed.

I suspect this discussion should be moved from Ada-Comment.

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

From: Bibb Latting
Sent: Thursday, February 9, 2006  1:31 PM

!topic Control over storage pool underlying Ada.Containers packages
!reference Ada 2005 RMA.18(all)
!from Bibb Latting 05-02-09
!keywords Containers, Storage Pools
!discussion
 
The capability to use a derivation of root_storage_pool with a container
is desired to provide flexibility in the management of the storage
underlying the container.  This capability provides the opportunity for
the user to optimize memory allocation for a given application, work-around
fragmentation in the hardware mapping of memory, provide non-core memory
allocation of the container, or to comply with safety/security issues.
 
Please feel free to change the above discussion as desired.
 
****************************************************************

From: Tucker Taft
Sent: Thursday, February 9, 2006  1:58 PM

The general consensus on this suggestion was that it
is good, but would involve significant analysis to
get it right at this point.  A recommendation was to
leave it out of the standard, but encourage implementations
to support the capability.  In general the Containers
packages were designed to be a starting point, not
the final story.  Ordered_ and Hashed_ might easily be
augmented with numerous other capabilities, including
"Bounded_...", "Protected_...", "Pooled_...", etc.
So long as all the packages have nearly identical
contents, it isn't too bad to have implementation-specific
code at the point of the instantiation.  The large
bulk of the user's code will depend only on the package
contents, not its instantiation parameters, and reasonable
portability can be preserved.

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

From: Randy Brukardt
Sent: Thursday, February 9, 2006  3:22 PM

The deadline for informal comments on Ada 2005 was last Friday. At this
point, only editorial comments will be accepted. There may be an opportunity
for formal comments at some point later in the future (although the primary
effect of such comments would be to endanger the future of the Amendment and
potentially of Ada itself).

So, at the point we're primarily talking about future work (beyond Ada
2005).

In any case, there are a number of reasons that user-defined storage pools
are inappropriate for the unbounded containers that Ada 2005 has:

1) There is no good way to name the default storage pool. Thus, there is no
good way to specify the default case of using the default storage pool. We
definitely do not want to make instantiating these containers harder.

Note that we tried early in the Ada 2005 process (see AI-300) to find a way
to make the default pool available. However, it ran into opposition from
some ARG members, who noted that some implementations used multiple default
storage pools, tailored to the characteristics of the type. That model
doesn't make it easy to name the default pool. The issue died because no
solution that worked for such a model could be found.

2) Although it's counter-intuitive, allowing user-defined storage pools
makes the containers less safe. The containers are almost certainly going to
be implemented as controlled types. If the storage pool has some method
other than Deallocate for freeing memory (before the pool itself ceases to
exist) -- and many user-defined pools do -- that could free memory belonging
to container objects and subparts. When those objects are later finalized,
the world will end, as the finalization information could very well have
been destroyed. (For instance, Janus/Ada chains together controlled objects;
if the memory is prematurely freed, those chains can be destroyed, and
almost anything could happen, none of it good.)

This problem cannot happen with the standard storage pool.

One could try to mitigate this problem by trying to define when it would be
safe to do premature deallocation, but such wording would also have the
effect of banning useful implementation techniques (such as caching of
nodes).

We'd also have to add wording to take into account this possibility. That
would make the containers *appear* less safe than they currently are, by
adding additional cases of erroneous behavior. Some reviewers were extremely
concerned about erroneous behavior of the containers, and we spent a lot of
effort eliminating as much such behavior as possible.

Aside: We'd also need wording to allow any operation to call Allocate, and
to require the propagation of any exceptions it generates. We don't need
special wording for the standard storage pool, because all it can do is
propagate Storage_Error, and *any* operation in Ada is *always* allowed to
do that. So no extra wording is needed.

3) The unbounded forms can (and often have to) allocate pretty much any size
or shape of memory as part of pretty much any operation. For instance, a
vector container (depending on it's implementation) could allocate
individual elements, small "chunks" of elements, or the entire data array of
elements at one time. Putting limits on that would be inappropriate for the
unbounded containers - we want to encourage innovative implementations.
Thus, any pool used with the unbounded containers would need to allow
arbitrary-sized allocations.

The effect of (2) and (3) is that many useful storage pools couldn't be used
in the context of the unbounded containers. A pool that is used to manage
memory would be inappropriate; it could only manage memory when no container
instantiation exists, and at that point no memory is allocated anyway. A
pool that does not allow any size allocation also cannot be used. For
instance, a pool that only allows specific sizes of allocations to eliminate
fragmentation could not be used in the context of the unbounded containers.

That doesn't leave many useful pools that could be used with the unbounded
containers. A pool that simply records the memory use could be used, and an
alternative heap could be used, but that's about it. That didn't seem like
enough to be worth the additional complication.

OTOH, it makes perfect sense for other forms of container to provide this
sort of functionality. The intent (as Tucker pointed out) is that the
containers in Ada 2005 provide a starting point for Ada containers, not be
the end point. We certainly hope that additional forms of containers are
developed for future use. (Hopefully, that would contain a solution to (1),
as well.)

One of the things that we'll be doing in future months is considering where
we need future work. Certainly, there has been a lot of interest in other
containers and other forms of containers (such as Bounded), so that will be
considered. And, as these are separate packages, there is no need to wait
another 10 years to standardize them. Moreover, these packages are
relatively easy for implementers to provide, so I would expect that most
implementers will do so. But we'll need energetic people (like Matt Heaney
was for the current set of containers) to participate and draft all of the
tedious wording needed. (A thick skin, to survive the constant nit-picking
at their hard work, also is a prerequisite.)

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

From: Robert A. Duff
Sent: Thursday, February 9, 2006  4:54 PM

>...The containers are almost certainly going to
> be implemented as controlled types. If the storage pool has some method
> other than Deallocate for freeing memory (before the pool itself ceases to
> exist) -- and many user-defined pools do -- that could free memory belonging
> to container objects and subparts.

The container type has finalization.  The heap-allocated memory blocks do not
(unless the actual element type passed in does).  So it would be OK
to use a user-def pool, so long as the element type does not have
controlled parts.

Anyway, I agree with what Tuck and Randy said: allowing user-def pools is a
good idea, but for the future (after Ada 2005).

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

From: Randy Brukardt
Sent: Thursday, February 9, 2006  5:10 PM

Huh? If the heap-allocated blocks are linked together (certainly will be
true in the list container, probably in most of the others too), when the
finalization routine walks the blocks whose memory has been reused to free
them, the results won't be pretty.

We certainly don't want to be mandating implementations that don't include
any links (that would be a major change for the unbounded containers, and
would make it very hard to implement the intended semantics). So I don't see
how one could expect such a pool to work at any time than when no container
objects exist. And even that prevents node caching.

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

From: Robert A. Duff
Sent: Thursday, February 9, 2006  5:53 PM

Yes, you're right.  I was confused.

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

From: Bibb Latting

...
> 1) There is no good way to name the default storage pool. Thus, there is
> no good way to specify the default case of using the default storage pool.

It seems to me that the use of multiple default pools implies an
"overloading" of a "root" default storage pool.  How does this
implementation support a user-defined storage pool?  Are all collections
assigned to the pool allocated from the same user-pool or are there
implementation restrictions that require the user to support an "overloaded"
set of user-pools?

From this perspective, an implementation would be free to do what it
currently does with the default pool, while the use of a user-defined pool
would operate in the same manner and with the same restrictions as the
current implementation.  The implementation always has the option of
exposing the specialized allocation mechanism in some way for their
customer's use.

> 2) Although it's counter-intuitive, allowing user-defined storage pools
> makes the containers less safe.

This problem exists for any controlled type allocated within a user-defined
pool; the coupling between user-defined pools and controlled types is really
what needs to be addressed.  It would seem that the use of a user-defined
pool with any controlled type would be unsafe.

> 3) The unbounded forms can (and often have to) allocate pretty much any
size
> or shape of memory as part of pretty much any operation. For instance, a
> vector container (depending on it's implementation) could allocate
> individual elements, small "chunks" of elements, or the entire data array
of
> elements at one time. Putting limits on that would be inappropriate for
> the
> unbounded containers - we want to encourage innovative implementations.
> Thus, any pool used with the unbounded containers would need to allow
> arbitrary-sized allocations.

Agreed, although the user-defined pool may be attempting to correct
underlying memory issues rather than addressing performance.  Of course this
could be overcome by customizing the implementation of the root pool, if an
interface has been provided by the implementation.

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

From: Randy Brukardt

...
> > 1) There is no good way to name the default storage pool. Thus, there is
> > no good way to specify the default case of using the default
> storage pool.
>
> It seems to me that the use of multiple default pools implies an
> "overloading" of a "root" default storage pool.  How does this
> implementation support a user-defined storage pool?  Are all collections
> assigned to the pool allocated from the same user-pool or are there
> implementation restrictions that require the user to support an
> "overloaded" set of user-pools?

I believe that the implementation uses nested default pools to better handle
memory management. Anyway, I don't understand their implementation very
well, so I can't comment too intelligently.

> From this perspective, an implementation would be free to do what it
> currently does with the default pool, while the use of a user-defined pool
> would operate in the same manner and with the same restrictions as the
> current implementation.  The implementation always has the option of
> exposing the specialized allocation mechanism in some way for their
> customer's use.

Well, the problem is how to represent that default pool in a generic
specification. Surely, the "root" containers have to work with the default
pool; we certainly don't want to require every user to define their own
storage pool! For instance, if we had a container that looked like:

    generic
        type Element_Type is private;
        Pool : in out Root_Storage_Pool'Class;
    package Pool_Unbounded_List is

That would work fine for a user-defined pool, but what would the
instantiation be for the default pool? There is no name for such a thing.
You could use the awful kludge:

    type Junk_Ptr is access all Integer;
    package My_List is new Pool_Unbounded_List (Integer, Junk_Ptr'Storage_Pool);

but the default pool here might not support the allocation of the larger
blocks needed by the list.

> > 2) Although it's counter-intuitive, allowing user-defined storage pools
> > makes the containers less safe.
>
> This problem exists for any controlled type allocated within a user-defined
> pool; the coupling between user-defined pools and controlled types is really
> what needs to be addressed.  It would seem that the use of a user-defined
> pool with any controlled type would be unsafe.

Correct, but the problem is worse with the containers, because the whole
point of the containers is to hide the storage allocation behavior. Thus,
there is no clear point where it is safe to do deallocations via the pool,
and it is less obvious that such deallocations are dangerous.

In any case, this whole area needs work (garbage collection appears to not
be allowed if any controlled objects are in the memory), so it seems that
this will be cleaned up. But not this go-round. (We've only discussed this
problem at dinner; it's never been on the agenda.)

> > 3) The unbounded forms can (and often have to) allocate pretty much any size
> > or shape of memory as part of pretty much any operation. For instance, a
> > vector container (depending on it's implementation) could allocate
> > individual elements, small "chunks" of elements, or the entire data array of
> > elements at one time. Putting limits on that would be inappropriate for the
> > unbounded containers - we want to encourage innovative implementations.
> > Thus, any pool used with the unbounded containers would need to allow
> > arbitrary-sized allocations.
>
> Agreed, although the user-defined pool may be attempting to correct
> underlying memory issues rather than addressing performance.  Of course this
> could be overcome by customizing the implementation of the root pool, if an
> interface has been provided by the implementation.

I agree that there are *some* uses of such pools; there just aren't that
many. The common use of such pools (tracking down storage leaks) shouldn't
be necessary with the predefined containers -- vendors will fix such
problems quickly if they ever existed. In any case, users shouldn't need to
debug the containers implementations.

I have a pool that bypasses all of the heap stuff to directly allocate
memory using the Windows memory allocation functions. It was designed to
allocate arrays that could be expanded in place rather than having to copy
them as more memory is needed. Such a pool would be useful for vectors in
some cases: but it isn't general enough to use for the arbitrary-sized
allocations of the containers library. I don't know how many pools are that
general (unless they fall back to the default pool somehow).

Anyway, it's not that allowing user-defined pools is bad idea, but rather
that such use would work better either with a container tailored for that
use and/or with bounded forms. I think we'll get there, but not immediately.

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

From: Bibb Latting

...
>    generic
>        type Element_Type is private;
>        Pool : in out Root_Storage_Pool'Class;
>    package Pool_Unbounded_List is
>
> That would work fine for a user-defined pool, but what would the
> instantiation be for the default pool? There is no name for such a thing.
> You could use the awful kludge:
>
>    type Junk_Ptr is access all Integer;
>    package My_List is new Pool_Unbounded_List (Integer, Junk_Ptr'Storage_Pool);
>

Indeed, we can cajole the address of the default pool out of the system by
using a variety of kludges.  I'm compelled to confess that I've used several
myself.  In AI-300, there are two aspects of the problem that seem
interesting: 1) a way to name a default pool (not necessarily the root pool;
note the special implementation), and 2) a syntax change to support some
sort of auto-switching in a generic.  I don't think the second is worth the
complexity introduced; the first represents a philosophical problem for the
language.  It seems that supporting some level of visibility for the root
pool would be worthwhile.  However, this exposes the root pool to easier
manipulation (corruption) by a programmer.

I think there are language features in place (Ravenscar is built on the features)
that provide the basis for a mechanism to control what language features are
allowed for a given application.  So, in terms of a default storage pool, I guess
my starting position advocates the presentation of a method to obtain a reference
to a default pool.  What each implementation does with the default reference is
up to the implementation; any derivations would work the same way as user-pools
currently do for an implementation.

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

From: Randy Brukardt
Sent: Tuesday, March 14, 2006  4:30 PM

I'm posting this question here because I don't want to post someone's
contact information on comp.lang.ada (that's a certain way to increase the
amount of spam you get), and it's at least tangentially related to the
Amendment. Please cc Dr. Barry if you respond, since I don't believe that he
is joined here.


---------

From: Dr Alwyn Barry

Hi,

Could you forward this question to the appropriate person?

I have been using Ada 2005 to rewrite some Python code.  In translating
the List processing using the new Doubly_Linked_Lists container class
I constantly have to use:

C : Cursor := First(L);
...
while Has_Element(C) loop
   ... do something using Element(C) or Update_Element(..)
   Next(C);
end loop;

Given the inherent insecurity with First()...Next(), is there a better
iterator, such as the 'natural' extension of the For Loop construct
to iterators ... eg:

for C in L loop
   ... do something using Element (C) or Update_Element(..)
end loop;

Also, the GNAT version binds a cursor to the created list, which
means that when the Move() procedure is called, cursors on the moved
list cannot be used!  Since move is a _genuine_ move, this is very
limiting.  It is impossible to overcome this limitation because the
Node_Type is hidden and so there is no other way to reference into
a list.

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

From: Randy Brukardt
Sent: Wednesday, March 15, 2006  10:42 PM

(I'd hoped someone else would answer this, but since no one has, I'll take a
stab at it...)

A.M. Barry writes:

> I have been using Ada 2005 to rewrite some Python code.  In translating
> the List processing using the new Doubly_Linked_Lists container class
> I constantly have to use:
>
> C : Cursor := First(L);
> ...
> while Has_Element(C) loop
>    ... do something using Element(C) or Update_Element(..)
>    Next(C);
> end loop;
>
> Given the inherent insecurity with First()...Next(), is there a better
> iterator, such as the 'natural' extension of the For Loop construct
> to iterators ... eg:
>
> for C in L loop
>    ... do something using Element (C) or Update_Element(..)
> end loop;

We talked about this "natural" extension a little bit, and it's pretty clear
that it's not obvious what is natural. See the e-mail in AC-112:
http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AC-00112.TXT (warning, this
link is going to change in the next couple of days to:
http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ACs/AC-00112.TXT - the site is
being reorganized to make room for Ada 2005 AIs and ASIS AIs.)

However, there are the Iterate and Reverse_Iterate procedures in the
containers packages. Is there a reason that you can't use them?? They're not
quite as convinient as the loop syntax given above, but they're just as
safe.

> Also, the GNAT version binds a cursor to the created list, which
> means that when the Move() procedure is called, cursors on the moved
> list cannot be used!  Since move is a _genuine_ move, this is very
> limiting.  It is impossible to overcome this limitation because the
> Node_Type is hidden and so there is no other way to reference into
> a list.

Cursors include the container; that's a fundamental property of them in this
model. That's because you can do operations on them without giving the
container. Also, cursors are not pointers per se, although they may be
implemented that way. We wanted to allow alternative implementations that
don't necessarily use explicit pointers.

In any case, Move destroys all of the cursors; the language defines them as
"invalid", and any future use is erroneous. (If the error was detected, you
are lucky.) In this sense, Move is very similar to destroying the container
itself (say, by calling Unchecked_Deallocation on it).

But Move isn't intended for cases where you need to preserve cursors. The
four parameter Splice is designed for that, as it returns the new cursor for
where the element(s) are inserted. If you want to preserve the original
container, just use ":=".

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

From: Matthew Heaney
Sent: Thursday, March 16, 2006  7:56 AM

> (I'd hoped someone else would answer this, but since no one 
> has, I'll take a stab at it...)

I sent him some email privately.
 
> In any case, Move destroys all of the cursors; the language 
> defines them as "invalid", and any future use is erroneous. 
> (If the error was detected, you are lucky.)

In the GNAT case (that's the compiler he's using), the cursor is implemented
as a record with a pointer to list object and another pointer to the node
containing the item.  When he attempted to use the old cursor with the new
list object, he probabably got Program_Error, since the first thing
cursor-based operations do is compare the list pointer to the address of the
list parameter.

> In this sense, 
> Move is very similar to destroying the container itself (say, 
> by calling Unchecked_Deallocation on it).

Well, it's not quite as extreme as that, since the nodes haven't been
deallocated; they've just been moved onto another list.  His algorithm would
work fine if the cursor didn't have a list pointer too.

There is often a tradeoff between flexibility and safety, and Move is an
example where some flexibility was lost as a result of adding the checks.

> But Move isn't intended for cases where you need to preserve 
> cursors. The four parameter Splice is designed for that, as 
> it returns the new cursor for where the element(s) are 
> inserted. If you want to preserve the original container, 
> just use ":=".

You could use Splice (in fact that's what I told him), but it can get a
little hairy since you must somehow keep track of all the extant cursors.
As you're iterating over the old list, splicing nodes on the new list, you
have to compare the cursor with old cursors, and then call splice with the
old cursor.

I also told him to just write a generic child procedure to rebind the cursor
from the old list to the new, and he seemed to like that idea better.
There's probably a more elegant way to solve his problem without extending
container behavior, but I didn't really understand the small fragments of
code he sent me.

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

From: Nick Roberts
Sent: Saturday, March 18, 2006  5:20 PM

> Given the inherent insecurity with First()...Next(), is there a better
> iterator, such as the 'natural' extension of the For Loop construct
> to iterators ... eg:
> 
> for C in L loop
>    ... do something using Element (C) or Update_Element(..)
> end loop;

For what it is worth, I would point out that Ada is really a somewhat 
lower level language than Python. I find iterating awkward in Ada (and 
in many other languages, to a lesser or greater degree), but I often 
find that, in Ada, an alternative such as:

    declare
       procedure Mogrify (C : in Widget_Lists.Cursor) is
       begin
          ...
       end;
    begin
       Widget_Lists.Iterate (My_Widgets, Mogrify'Access);
    end;

alleviates the dangers of missing something vital out.

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

From: Pascal Leroy
Sent: Monday, March 20, 2006  8:00 AM

> in Ada, an alternative such as:
> 
>     declare
>        procedure Mogrify (C : in Widget_Lists.Cursor) is
>        begin
>           ...
>        end;
>     begin
>        Widget_Lists.Iterate (My_Widgets, Mogrify'Access);
>     end;
> 
> alleviates the dangers of missing something vital out.

I fail to see what dangers it alleviates.  I for one would much prefer to
write something like:

	for each C in My_Widgets loop
	   ...
	end loop;

Remember, Ada is about readability, too.

However, last time this was discussed it appeared that grafting such a
capability on the language was not easy.

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

From: Randy Brukardt
Sent: Monday, March 20, 2006  8:28 PM

I'm reposting this private mail (with permission) on this topic for the
record.

----
From: Alwyn Barry

Hi,

Thanks for your response.

I did, in the end, use iterators.  However I am using a list
(which is backed-up on each cycle of the algorithm to a
back-up list), and three different index lists onto the list
(which are also backed up).  This means, in the worst case,
up to five iterator functions, each of one line, for five
lines of algorithm.  Its ok, but hardly readable.  For cases
where there are large tasks to do, Iterate is great.  For
single statements it is overkill.  What is particularly
frustrating is that though iterate() is provided [effectively
apply()], there is a lack of reduce() and map() functions
which would remove the need for the iterator functions to
access other variables outside the function in order to do
their task.  These functions can easily be provided, but
could have been included.

Anyway, that was one issue which I could work around, although
frustrated that Ada is not adopting features which other
languages have included exactly so that the "dropped next()"
errors do not occur.  In regard to the other problem...

Splice() could be used, but there is no cursor update
with it.  As Matthew Heaney points out in his reply, trying
to update the cursors too gets nasty (the cursor is invalid
once the item has moved, yet the new list does not contain
the item so you cannot update the cursor before the splice).
This can be programmed around, but thats not helpful either.

Anyway, I've got around it by the old trick of having two
records, one the 'current' and one the 'backup' list and
indexes, and simply switching pointers.  I used to do this
in C, which I guess says something about the elegance or
otherwise of the solution.  It does save copying, but where
speed is not really an issue it is a pity there is not a
better way.  Mind you, I do like the safety constraints of
the current implementation! ... it just needs a means of
switching the cursors if the list is moved, or a further
internal level of indirection so that the cursor to list
pointer remains, but the actual list type is a level removed.

Alwyn

---

From: Randy Brukardt

The general answer is that you can't provide the solution to every possible
need, and keep things efficient. Every solution has trade-offs, and with
containers, *everybody* has a better idea. Undoubtedly there is something
better that could have been done [if I had designed them, they would have
worked quite differently!], but the real value here is that they're
standard. There never was any intent that this version would be the final
word in containers for Ada.

The syntax for iterators *is* clunky. We never seriously considered doing
anything about that; I suspect that the greater use of containers will make
that more important as we go forward. But the "next" style is needed for
maximum flexibility; the only way to avoid it is to give up that flexibility
in some way. So, you need both (no matter how nice the syntax of iterators).

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

From: Nick Roberts
Sent: Tuesday, March 21, 2006  8:52 PM

Alwyn Barry wrote [forwarded by Randy Brukardt]:

> ...  What is particularly frustrating is that though iterate() is 
> provided [effectively apply()], there is a lack of reduce() and map()
> functions which would remove the need for the iterator functions to 
> access other variables outside the function in order to do their 
> task.  These functions can easily be provided, but could have been 
> included. ...

These functions (reduce and map) could not be so easily provided in Ada
as they are in Python (which has dynamic typing and comprehensions,
which Ada essentially does not). I think both functions would have to be
generic, the 'reduce' function taking the result type as its generic
parameter, and the 'map' function taking another list or vector package
as its generic parameter. In other words, they would be not be the
elegant one-liners that they are in Python.

> ... Anyway, I've got around it by the old trick of having two 
> records, one the 'current' and one the 'backup' list and indexes, and
> simply switching pointers.  I used to do this in C, which I guess 
> says something about the elegance or otherwise of the solution.  It 
> does save copying, but where speed is not really an issue it is a 
> pity there is not a better way.  ...

This is the kind of solution that I would have adopted. I'm sure that it
is generally safer using access values in Ada than using pointers in C,
so I'm not sure it need be considered a particularly inelegant solution
(perhaps not in C either).

Randy Brukardt replied:

> The general answer is that you can't provide the solution to every 
> possible need, and keep things efficient. ... [if I had designed 
> them, they would have worked quite differently!], but the real value
> here is that they're standard. There never was any intent that this
> version would be the final word in containers for Ada. ...

If I had designed the containers, they would have worked quite
differently as well! But I think Matthew Heaney (the principal designer)
and the ARG have done a good job, in the end, of producing a design that
combines efficiency, safety, and intelligibility, especially as they
didn't have a great deal of time to refine it.

I am currently using Matt's reference implementation of the new
containers, grafted into GNAT 3.15p (which is Ada 95), in various 'real
life' programs I am writing, so I'm getting to know them quite well, and
they are very handy!

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

From: Matthew Heaney
Sent: Tuesday, March 21, 2006  9:17 AM

> For cases
> where there are large tasks to do, Iterate is great.  For
> single statements it is overkill.  

The library works by providing primitives that you can use to synthesize 
higher-level abstractions.  Any "single statement" can be written as a 
generic and instantiated as necessary.

 > What is particularly
> frustrating is that though iterate() is provided [effectively
> apply()], there is a lack of reduce() and map() functions
> which would remove the need for the iterator functions to
> access other variables outside the function in order to do
> their task.  

Well this is just silly.  Of *course* local functions "access variables 
outside the function" since otherwise there'd be little point in making 
them local.  Ada has *always* worked this way; the container library 
simply conforms to already-established language idioms.

> These functions can easily be provided, but
> could have been included.

Yes of course, and that is by design.  Obviously we didn't include 
everything.  If you want a map function, then it's trivial to write it 
once and then keep reusing it.  Here's one for arrays (which of course 
could be generalized):

generic
    type Result_Type is private;
    type Array_Type is array (Count_Type range <>) of Result_Type;
    type Container_Type (<>) is limited private;
    type Cursor_Type (<>) is limited private;
    with procedure Process
      (Posn : Cursor_Type;
       Result : out Result_Type);
    with function Length (C : Container_Type) return Count_Type;
    with procedure Iterate
      (C : Container_Type;
       Process : not null access procedure (C : Cursor);
function Generic_Map (C : Container_Type) return Array_Type;

function Generic_Map (C : Container_Type) return Array_Type is
    A : Array_Type (1 .. Length (C));
    I : Count_Type := 0;

    procedure Process (Posn : Cursor_Type) is
    begin
       I := I + 1;
       Process (Posn, A (I));
    end;
begin
    Iterate (C, Process'Access);
    return A (1 .. I);
end;

This algorithm works for any container type, including arrays.

> Anyway, that was one issue which I could work around, although
> frustrated that Ada is not adopting features which other
> languages have included exactly so that the "dropped next()"
> errors do not occur.  In regard to the other problem...

What "other languages" are we speaking about?  Ada is a low-level 
systems programming language.  It is not a scripting language.  In 
particular it is neither Perl nor Python.

Ada's closest analog is C++.  Anything you can do in the STL you can do 
in the Ada container library.

We didn't even attempt to include a generic algorithms library too, 
since we were trying to keep the scope of the revision small.  The 
simplest thing for you to do it write the generic algorithms you need 
and reuse them as necessary.

> Splice() could be used, but there is no cursor update
> with it.  

Of course there is cursor update with it.  I don't know what you're 
talking about here.  The Position parameter of the 4-parameter Splice is 
passed using inout mode, the purpose of which is to rebind the cursor 
from the old (source) list to the new (target) list.

> As Matthew Heaney points out in his reply, trying
> to update the cursors too gets nasty (the cursor is invalid
> once the item has moved, yet the new list does not contain
> the item so you cannot update the cursor before the splice).

So you update the cursor *during* the call to Splice, by specifying the 
cursor you want to rebind as the Position parameter.

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


Questions? Ask the ACAA Technical Agent