--- ai05s/ai05-0001-1.txt 2006/03/23 03:30:57 1.2 +++ ai05s/ai05-0001-1.txt 2008/10/25 04:53:13 1.3 @@ -1,4 +1,4 @@ -!standard A.18(0/2) 06-03-15 AI05-0001-1/01 +!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 @@ -21,16 +21,737 @@ !proposal -Bounded forms of containers have been proposed. The ability to provide storage -pools has been proposed. +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. -Protected forms also have been proposed. +!wording -Which forms we need is very unclear at this time. +Bounded Vector -!wording +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

Questions? Ask the ACAA Technical Agent