!standard A.18(0/2) 09-02-16 AI05-0001-1/04 !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 Package Containers The library package Containers has the following additional declaration: Capacity_Error : exception; Bounded Vector The language-defined generic package Containers.Bounded_Vectors provides a private type Vector and a set of operations. It provides the same operations as the package Containers.Vectors (see A.18.2), with the difference that internal storage is allocated statically. [ARG] Is that last sentence OK? [END ARG] Static Semantics The declaration of the generic library package Containers.Bounded_Vectors has the same contents as Containers.Vectors except: The package has Pure categorization. The container type is declared with a discriminant that specifies the capacity: type Vector (Capacity : Count_Type) is tagged private; Add the following declarations after A.18.2(34/2): procedure Assign (Target : in out Vector; Source : Vector); function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector; Add the following after A.18.2(147/2): procedure Assign (Target : in out Vector; Source : Vector); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, Reserve_Capacity is called with the Source length as the capacity. Each element of Source is then assigned to the matching element of Target. function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector; Returns a vector whose elements match the active elements of Source. If Capacity is 0, then the vector capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the vector capacity is at least the specified value. Otherwise, the operation raises Capacity_Error. [ARG] OK to say above "...who elements match the active elements of Source"? [END ARG] [ARG] FOR BOUNDED FORM: DECLARE A CAPACITY_SUBTYPE FOR BOUNDED VECTOR FOR UNBOUNDED CASE TOO USE SUBTYPE IN COPY, RES_CAP, etc TODO: I don't know how to declare this subtype It's supposed to be subtype Capacity_Subtype is Count_Type range 0 .. ; The intent was to prevent a vector object from having a capacity greater than the number of values in the index subtype, e.g. type IT is range 0 .. 5; type ET is ...; package P is new Bounded_Vectors (IT, ET); V : P.Vector (10); -- only V[0] .. V[5] are accessible Would this work? subtype Capacity_Subtype is Count_Type range 0 .. Count_Type'Max (0, Index_Type'Pos (Index_Type'Last) - Index_Type'Pos (Index_Type'First) + 1); The problem here is the instantiation: package P is new Bounded_Vectors (Natural, ET); Subtype Natural has more values in the type than Count_Type'Last. Another option is to raise Constraint_Error (or whatever) at the point of declaration of the object -- but that won't work either, since the bounded forms aren't controlled. If there were a way to return the count of the number of values in the type, then the user could pass that as the capacity, and we could leave the declaration of the descriminant as-is: V : P.Vector (IT'Value_Count); -- IT'Value_Count = 6 In a review of a draft of this document, Randy B. said: The trick here, of course, is to ensure that you're evaluating as Universal_Integer. But I suppose that isn't perfect, since the expressions don't have to be static, and you could always use a type with more values than the largest integer type supported by the compiler. OTOH, you don't want to support more than Count_Type'Last elements, so giving an index with more is dubious. OT3H, not allowing Natural seems annoying. Anyway, if you write the expressions as boolean conditionals, they're be evaluated as univeral integers. One idea is something like: subtype Capacity_Subtype is Count_Type range 0 .. Count_Type'Max (0, Boolean'Pos(Index_Type'Pos (Index_Type'Last) - Index_Type'Pos (Index_Type'First) + 1 > Count_Type'Pos(Count_Type'Last))*Count_Type'Last + Boolean'Pos(Index_Type'Pos (Index_Type'Last) - Index_Type'Pos (Index_Type'First) + 1 <= Count_Type'Pos(Count_Type'Last)*(Index_Type'Pos (Index_Type'Last) - Index_Type'Pos (Index_Type'First) + 1)); Gosh that's awful. (And it still will raise an exception if Index_Type is a 64-bit type on GNAT.) I guess we better leave this one for the full group. [END ARG] [ARG] procedure Move (Target : in out Vector; Source : in out Vector); My notes say: RE-WRITE UNBOUNDED FORM TO INCLUDE A CALL TO RES_CAP, which means we could reuse the wording for unbounded form, therefore we don't need to say anything special here. Here's what the RM says now: "If Target denotes the same object as Source, then Move has no effect. Otherwise, Move first calls Clear (Target); then, each element from Source is removed from Source and inserted into Target in the original order. The length of Source is 0 after a successful call to Move." We change add a call to Reserve_Capacity to that description, subject to the following constraints: (1) In the bounded form, if the source length is greater than target capacity, we could prefer to raise Capacity_Error immediately (instead of clearning target as a side effect). (2) In the unbounded form, we prefer to clear first, and then reserve capacity. If you do in the other way around then the existing items are copied (in the reserve) and then immediately deleted (in the clear). Perhaps we only have to require the final effect (no items, and such-and-such capacity), but merely describe it in terms of a reserve followed by a clear. With that in mind, here's the revised description: "If Target denotes the same object as Source, then Move has no effect. Otherwise, Move first calls Target.Reserve_Capacity (Source.Length) and then Target.Clear; then, each element from Source is removed from Source and inserted into Target in the original order. The length of Source is 0 after a successful call to Move." If the original description of the Move operation is modified as above for the unbounded form, then there's probably nothing else we need to say for the bounded form (since Reserve_Capacity does what we want here). [END ARG] Implementation Advice A.18.2(261/2) is deleted. [ARG] RLB: In the bounded form only? Or in unbounded and bounded forms? Alternatively, we would have to put as Implementation Advice in the bounded form: "The Implementation Advice for procedure Move is deleted." That's pretty weird. [END ARG] procedure Reserve_Capacity (Container : in out Vector; Capacity : Capacity_Subtype); If the specified Capacity is larger than the Container.Capacity, then Reserve_Capacity raises Capacity_Error. Otherwise, the operation has no effect. [ARG] The bounded form has a distinct description for Reserve_Capacity, because it can raise Capacity_Error. Where does this description go? [RLB: Under the description of Reserve_Capacity in the bounded forms, of course. Where else would it go?] More generally, no operations for the unbounded forms raise Capacity_Error. Do we need to specify this distinct behavior of the bounded forms? [END ARG] Bounded Doubly-Linked List The language-defined generic package Containers.Bounded_Doubly_Linked_Lists provides a private type List and a set of operations. It provides the same operations as the package Containers.Doubly_Linked_Lists (see A.18.3), with the difference that internal storage is allocated statically. Static Semantics The declaration of the generic library package Containers.Bounded_Doubly_Linked_Lists has the same contents as Containers.Doubly_Linked_Lists except: 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; Add the following declarations after A.18.3(17/2): procedure Assign (Target : in out List; Source : List); function Copy (Source : List; Capacity : Count_Type := 0) return List; Add the following after A.18.3(86/2): procedure Assign (Target : in out List; Source : List); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, then the operation raises Capacity_Error, and Target is not modified. Otherwise, it clears Target, and then each element of Source is assigned to the matching element of Target. function Copy (Source : List; Capacity : Count_Type := 0) return List; Returns a list whose match the elements of Source. If Capacity is 0, then the list capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the list capacity is at least the specified value. Otherwise, the operation raises Capacity_Error. [ARG] An issue with Assign here is that there's no Reserve_Capacity operation for lists, so we can't use the trick as we did for vectors to write a description that works for both the unbounded and bounded forms. Do we write distinct descriptions of Assign for the unbounded vs. bounded cases? In general, operations that can raise Capacity_Error include: Append, Insert, Assign, Copy, Move, Prepend, List'Read, Splice [END ARG] procedure Move (Target : in out List; Source : in out List); Equivalent to Target.Assign (Source) followed by Source.Clear. [ARG] Will this description suffice for both the unbounded and bounded forms? [END ARG] Implementation Advice A.18.3(162/2) is deleted. [ARG] RLB: See notes under bounded vector. [END ARG] procedure Splice (Target : in out List; Before : Cursor; Source : in out List); If the sum of the Target length and Source length is greater than the Target capacity, then Splice raises Capacity_Error. Otherwise the elements from Source are moved to Target, immediately preceding position Before. [ARG] We say "... are moved to ..." implying a call to Move. Do we need to say that explicitly? [END ARG] procedure Splice (Target : in out List; Before : Cursor; Source : in out List; Position : in out Cursor); If the Target length equals the Target capacity, then Splice raises Capacity_Error. Otherwise the element of Source designated by Position is moved to Target, immediately preceeding position Before. Maps Implementation Advice A.18.4(83/2) is deleted. Bounded Hashed Map The language-defined generic package Containers.Bounded_Hashed_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Hashed_Maps (see A.18.5), with the difference that internal storage is allocated statically. Static Semantics The declaration of the generic library package Containers.Bounded_Hashed_Maps has the same contents as Containers.Hashed_Maps except: The package has Pure categorization. The container type is declared with a discriminant that specifies both the capacity (number of elements) and modulous (number of distinct hash values) of the hash table as follows: type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; procedure Reserve_Capacity (Container : in out Map; Capacity : Count_Type); If the specified Capacity is larger than the Container.Capacity, then it raises Capacity_Error. Otherwise, the operation has no effect. Add the following declarations after A.18.5(17/2): procedure Assign (Target : in out Map; Source : Map); function Copy (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map; Add the following after A.18.5(53/2): procedure Assign (Target : in out Map; Source : Map); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, Reserve_Capacity is called with the Source length as the capacity. Otherwise, it clears Target and inserts each key/element pair of Source into Target. [ARG] This is written very similar (i.e. in terms of Reserve_Capacity) to the description of Assign for the vector (with the intent that it work for both unbounded and bounded forms). Whatever we decide for vector should probably apply here as well. Note also we say "If Source length is greater than Target capacity, then Reserve_Capacity is called...". Do we need to bother with the if-clause? Reserve_Capacity is allowed to return more than requested, so the post-condition would be satified no matter what. [END ARG] function Copy (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map; Returns a map with key/element pairs copied from Source, and having a capacity and modulus determined as follows. If Capacity is 0, then the map capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the map capacity is least the specified value; otherwise, the operation raises Capacity_Error. If the Modulus argument is 0, then the map modulus is the value returned by a call to Default_Modulus with the map capacity as its argument; otherwise the map modulus is the value of the Modulus argument. [ARG] We say "... pairs copied from Source ..." above: is this too tautological? [END ARG] [ARG] I have put the description of Assign and Copy here instead of in A.18.4 only because here I have two slightly different descriptions for hashed vs. ordered forms. [END ARG] procedure Move (Target : in out Map; Source : in out Map); Equivalent to Target.Assign (Source) followed by Source.Clear. [ARG] Here we describe Move in terms of Assign (which is in turn described in terms of Reserve_Capacity). Should we describe Move directly in terms of Reserve_Capacity, instead of in terms of Assign? [END ARG] [ARG] Make this an implementation note? KNUTH SAYS YOU SHOULD GOLDEN RATIO FOR LOAD FACTOR SEE JOHN'S BOOK FOR SPECIFIC REF [END ARG] function Default_Modulus (Capacity : Count_Type) return Hash_Type; Default_Modulus returns an implementation-defined value for the length of the buckets array (number of distinct hash values) for hashing the given capacity (maximum number of elements). [ARG] Use of "implementation-defined" is OK here? [END ARG] Bounded Ordered Map The language-defined generic package Containers.Bounded_Ordered_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Ordered_Maps (see A.18.6), with the difference that internal storage is allocated statically. Static Semantics The declaration of the generic library package Containers.Bounded_Ordered_Maps has the same contents as Containers.Ordered_Maps except: 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; Add the following declarations after A.18.6(16/2): procedure Assign (Target : in out Map; Source : Map); function Copy (Source : Map; Capacity : Count_Type := 0) return Map; Add the following after A.18.6(58/2): procedure Assign (Target : in out Map; Source : Map); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, then the operation raises Capacity_Error. Otherwise, it clears Target and inserts each key/element pair of Source into Target. [ARG] This is similar to the case of lists (no Reserve_Capacity). [END ARG] function Copy (Source : Map; Capacity : Count_Type := 0) return Map; Returns a map with key/element pairs copied from Source, and having a capacity determined as follows. If Capacity is 0, then the map capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the map capacity is at least the specified value; otherwise, the operation raises Capacity_Error. [ARG] Here's a list of operations that raise Capacity_Error: Assign, Copy, Include, Insert, Move, Map'Read, Reserve_Capacity We just need to decide how to handle these, since there are differences between the unbounded and bounded forms. [END ARG] procedure Move (Target : in out Map; Source : in out Map); Equivalent to Target.Assign (Source) followed by Source.Clear. Sets Implementation Advice A.18.7(104/2) is deleted. Bounded Hashed Set The language-defined generic package Containers.Bounded_Hashed_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Hashed_Sets (see A.18.8), with the difference that internal storage is allocated statically. Static Semantics The declaration of the generic library package Containers.Bounded_Hashed_Sets has the same contents as Containers.Hashed_Sets except: The package has Pure categorization. The container type is declared with a discriminant that specifies both the capacity (number of elements) and modulous (number of distinct hash values) of the hash table as follows: type Set (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; procedure Reserve_Capacity (Container : in out Map; Capacity : Count_Type); If the specified Capacity is larger than the Container.Capacity, then it raises Capacity_Error. Otherwise, the operation has no effect. Add the following declarations after A.18.8(17/2): procedure Assign (Target : in out Set; Source : Set); function Copy (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Set; Add the following after A.18.8(75/2): procedure Assign (Target : in out Set; Source : Set); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, Reserve_Capacity is called with the Source length as the capacity. Otherwise, it clears Target and inserts each element of Source into Target. function Copy (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Set; Returns a set with elements copied from Source, and having a capacity and modulus determined as follows. If Capacity is 0, then the set capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the set capacity is at least the specified value; otherwise, the operation raises Capacity_Error. If the Modulus argument is 0, then the set modulus is the value returned by a call to Default_Modulus with the set capacity as its argument; otherwise the set modulus is the value of the Modulus argument. procedure Move (Target : in out Set; Source : in out Set); Equivalent to Target.Assign (Source) followed by Source.Clear. function Default_Modulus (Capacity : Count_Type) return Hash_Type; Default_Modulus returns an implementation-defined value for the length of the buckets array (number of distinct hash values) for hashing the given capacity (maximum number of elements). [ARG] Use of "implementation-defined" is OK here? [END ARG] Bounded Ordered Set The language-defined generic package Containers.Bounded_Ordered_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Ordered_Sets (see A.18.9), with the difference that internal storage is allocated statically. Static Semantics The declaration of the generic library package Containers.Bounded_Ordered_Sets has the same contents as Containers.Ordered_Sets except: 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; Add the following declarations after A.18.9(16/2): procedure Assign (Target : in out Set; Source : Set); function Copy (Source : Set; Capacity : Count_Type := 0) return Set; Add the following after A.18.9(81/2): procedure Assign (Target : in out Set; Source : Set); If Target denotes the same object as Source, the operation has no effect. If Source length is greater than Target capacity, then the operation raises Capacity_Error. Otherwise, it clears Target and inserts each element of Source into Target. function Copy (Source : Set; Capacity : Count_Type := 0) return Set; Returns a set with elements copied from Source, and having a capacity determined as follows. If Capacity is 0, then the set capacity is the length of Source; if Capacity is equal to or greater than Source.Length, the set capacity is at least the specified value; otherwise, the operation raises Capacity_Error. procedure Move (Target : in out Set; Source : in out Set); Equivalent to Target.Assign (Source) followed by Source.Clear. Source is cleared. Protected Queues [ARG] Should we have priority queues too? (Steve B. suggested something like fibbonacci heaps as implementation data structure.) [END ARG] The language-defined generic package Containers.Queues provides interface type Queue, and a set of operations for that type. generic type Element_Type is private; package Ada.Containers.Queues is pragma Pure; type Queue is synchronized interface; procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; pragma Implemented (Enqueue, By_Entry); procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; pragma Implemented (Dequeue, By_Entry); function Is_Empty (Container : Queue) return Boolean is abstract; function Is_Full (Container : Queue) return Boolean is abstract; end Ada.Containers.Queues; Interface Queue specifies a first-in, first-out queue. procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; Copies New_Item onto the tail of the queue. If Is_Full is True, then Enqueue waits on the entry for storage to become available. procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; Removes the element at the head 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. function Is_Empty (Container : Queue) return Boolean is abstract; Returns an indication of whether the queue contains items. function Is_Full (Container : Queue) return Boolean is abstract; Returns an indication of whether the queue is able to contain more items. Bounded Queues The language-defined generic package Containers.Bounded_Queues provides type Queue, which implements the interface type Containers.Queues.Queue. with Ada.Containers.Queues; generic with package Queues is new Ada.Containers.Queues (<>); package Ada.Containers.Bounded_Queues is pragma Pure; type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private; private -- not specified by the language end Ada.Containers.Bounded_Queues; The bounded queue specifies a queue with finite capacity. Is_Full returns True when the length (the current number of items) equals the capacity. Unbounded Queues The language-defined generic package Containers.Unbounded_Queues provides type Queue, which implements the interface type Containers.Queues.Queue. with Ada.Containers.Queues; generic with package Queues is new Ada.Containers.Queues (<>); package Ada.Containers.Unbounded_Queues is pragma Preelaborate; type Queue is synchronized new Queues.Queue with private; private -- not specified by the language end Ada.Containers.Unbounded_Queues; 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 generic library procedure Containers.Generic_Sort has the following declaration: 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 indexable 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 elements having the given indices, and generic formal Swap exchanges the values of the indicated 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 weak ordering relationship (see A.18); it should not modify the elements. If the actual for Less behaves in some other manner, the behavior of Generic_Sort is unspecified. How many times the Generic_Sorts 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. **************************************************************** From: Randy Brukardt Sent: Thursday, September 25, 2008 5:55 PM Following is my notes on the two days of containers meetings. Matt has his own set of notes that probably differ from mine. I made a quick pass thorough these notes to eliminate/clarify nonsense, but otherwise they are as I took them. A quick summary is that we agreed on the form and semantics of the bounded containers (as little as change is possible, but no pointers and no controlled types are expected to be used in the implementation of them so that that can be used in safety-critical environments). We looked at a design for shared (task-safe) queue abstractions, but concluded that there wasn't enough need for generalized task-safe containers. (Especially as there are as many meanings of "task-safe" as there are programmers.) We rejected storage-optimized variants of the containers, as they are insufficiently different from the basic containers. We also studied issues involved with defining containers for limited element types. This probably would need some language support, or intensive headstands by an implementer. We looked at some options for that language support. Randy Brukardt. ---------------- Containers Meeting - September 22-23, 2008 Present: Randy Brukardt, Bob Duff, Tucker Taft, Ed Schonberg, Matt Heaney. Who is the customer? "The programmer of the future". Why would someone not be able to use the existing containers? Restricted environments (no dynamic allocation, no finalization). Synchronization issues. Programs can add synchronization, so that is a secondary issue. Another dimension is limitedness. Limited, No dynamic allocation No finalization Synchronization New container types: achieve parity with C++ (multimaps, multisets). Surely No dynamic allocation is the most important issue. There is a meta-rule that the containers can be written in Ada. Tucker suggests that setting an address with the tampering bits could be use add detection of copying of these bits. Tucker is trying to order these kinds of containers. No dynamic allocation No controlled types Turning to protected (task-safe) containers. Bob wonders if there is any real value to wrapping these containers? But the shared queue is commonly wanted. Perhaps we should just invent a shared queue abstraction and provide that. Tucker wonders if a generic that protected a set of operations and provided a protected operation would work. The idea is the underlying storage would be provided by the formal, so that alternative storage mechanism could be used. We talk about limited containers. That brings up issues about control of finalization. The current containers do not have that. For instance, how can we use a constructor function in a limited bounded form. C++ has placement new for this. Tucker thinks that you could play games with storage pools to do that. We talk about bounded hash table. Matt wonders how you set the hash table size here, because it can't be calculated after the fact. Tucker suggests two discriminants (or formal parameter). Bob suggests that one could use a constructor function to calculate the discriminants (which could be private). Type Hash_Objects (Hash_Size, Element_Size : Integer) is record H : Hash_Table (1..Hash_Size); E : Element_Table (1..Element_Size); End record; Should these be discriminants? Per-object boundedness seems valuable. The discriminants would be visible, and you would need a subtype in order to be compose these (container of container). Thus, the bounded forms, will not be based on storage pools, just based on discriminants, specified on the object. Matt suggests another model where the memory is allocated in the package body. That seems too much like a heap implementation. Per-object makes much more sense. If we had done it on the instantiation, we would have the choice of for one object or for all objects. But we don't want to do that. We don't think assignment is too likely, so we believe that mismatching discriminants is not an issue. --- Synchronized operations: multiple vs. single readers? Is a queue good enough, or should we make all of the containers protected? Tucker is against that, as there are many other things that you are likely to need to do. We have an aside about transactional memory. Tucker would like to try separating storage and protection aspects for a synchronized queue. --- We go through Matt's list of issues. We discuss what happens with uninitialized elements. We have covered that for vectors; they're called empty elements, and accessing them is a bounded error. We should just follow this model; and not worry about last wishes. Bounded forms are non-limited; we'll look at limited forms later and separately. Ordered multisets: should we have them? Tucker asks this is a "bag"? Essentially, yes. It contains objects, possibly duplicated. What new operations are there? There are additional iterators for iterating over an equivalence set. Bob wonders if this makes more sense for multi-maps. Tucker wonders if Generic_Keys could be used for that; it offers a second equivalence class. Ed doesn't seem to understand what this is used for. Matt says that you end up having to have a second-level indirection to use the existing containers this way. A.18.8(87/2) shows that it is not intended for Generic_Keys to establish some other equivalence class. So Tucker's idea won't work. The difference between a set and a map is that the key exists in the data in the set, while it is separate in map. So lets look at a multimap. (That's a one-to-many mapping). Even better, let's have lunch. ---- Matt explains his uses for this Multimap/Multiset package. It still doesn't sound that fundamental. Tucker now suggests breaking the key into multiple pieces (the primary key and a disambiguating key). Then using Floor and Ceiling to iterate over the subrange. The uniqueness key would not necessarily participate in the ordering relation (nor is it very interesting). So it is obvious that we can use some extra memory to get the effect with the existing packages. The question is it worth it to have this container? Is it a lot of extra work (definitionally) compared to the existing containers? Matt prefers a multiset, others think a multimap is more important. We agree that this is lower priority than bounded, queues, and even limited is more important (Tucker notes that limited adds a new capability, multiset is just a bit easier). Moving on to "case-insensitive string hash and less operations". GNAT has those. How do this work? Just apply To_Upper or To_Lower. But which is used matters for ">". Bob notes that Unix programmers would use To_Lower, and everyone else would use To_Upper. Matt says that he uses To_Lower. Tucker wonders if implementations would optimize this, that's the main reason to do it. Robert Dewar joins us and suggests that we simply try to do whatever C does for in similar functions (StrCaseCpy). But that doesn't seem to be standard. We originally dropped these because we thought that using a string map was better than having extra functions for all four kinds of strings. Robert says that going to lower is better, because there are lower case characters that have no upper characters. That gives you weird results. These are common enough that we should have them. Most uses would not care about the corner cases, and we should not let good enough to be killed off by best. No promises that Hash(Lower(Key)) = Insens_Hash(Key). Robert disagrees. Matt offers the question of storage optimized form. (He specifically mentions singly linked lists). Tucker says that they are just in the way most of the time. It's not that much of a savings in normal usage. Robert talks about a pointer that is always the xor of the forward/backward list. This scheme allows implementing a doubly linked list with only a single pointer. We think it might be possible to implement the existing package that way. Which means that potentially there is no savings at all from a singly linked list package. We don't think that storage optimized forms are that important. These would only be necessary on the bleeding edge, and there is no problem switching the implementation on their own. Do C++ have competing STLs based on performance characteristics? Moving to "more sort algorithms". Matt uses Heap Sort because it is stable and predictable. Bob wonders if we should have other sorts of sorting. He mentions a radix sort. That is not worthwhile. But this has little to do with generic that Matt proposed, that seems to be worthwhile. But it does not have much to do with anonymous arrays, so drop that part from the name. (That is, it is just "Generic_Sorting"). Recursive data structures: Tucker again thinks its harder to figure out how to instantiate or use these packages than to write them yourself. No one disagrees. Should we be considering lock-free algorithms? That really belongs to a multicore group; we don't have the expertise for that. We really ought to have a multicore research group. If we are doing an Amendment, hopefully the ARG will set up one of those. We turn to discussion of "smart pointers". Function F return T_Access is X : Auto_Ptr := Init(new T); Begin ... Return To_Access(X); End F; The idea is that it is a generic wrapper that adds this functionality. Tucker thinks that this belongs to the storage management realm, and this is really outside of the scope of this group. He's interested in it, but agrees with Randy's (old) opinion that this is probably the wrong level of abstraction. The ARG is already looking at this (lightly). We talk about lifetime of pointers. Randy talks about his problems in Claw with pointers that you want to have a defined lifetime and no more (that is, no copying). Tucker brings up another dimension: persistence. Passive partitions have this feature, but that was not the original idea of them. Anyway, pointers into the persistent area need lifetime information so we can find out when an object has become unreferenced by the program. Robert suggests using reference counts for this, but that doesn't work if you want to swap out a whole page: you'd have to find all of the reference counts that point in. Matt mentions iterator syntax "for each obj in collection". Bob mentions "Sather iterators"; Ed tries to find more about that on the web. It's in the ACM portal. In any case, this is an area of interest for future work. Randy notes he floated a proposal in 2005 (AC-0112). --- We look at a bounded vector specification. Should we still have the Capacity and Reserve_Capacity? The function Capacity should be available for consistency. Reserve_Capacity should be gone, it makes no sense. But there is some sense to it; just ignored if smaller or same, raises Storage_Error if bigger. That's the same semantics as the Unbounded case, with less restrictions. Tucker asks what is the capacity of the vector objects that are returned from functions. Since these are constants, the smallest possible is fine. That would be annoying if it is later assigned. Tucker suggests something, but it doesn't work. Also, there is no need to constrain the discriminants subtype. Matt has Assign, which allows assigning objects with different capacity. That makes sense, some exception will be raised if the source doesn't fit in the target. Do nothing if Source = Target. He also has Copy, which changes the capacity of a object on the fly. What about Move? It is a destruction Copy; implement by copying Source to Target then zeroing Source. Buglet: Move should say something about the Capacity of Source afterwards. It could be zero. Bob suggests that we say that Reserve_Capacity (Source, 0) is called (that allows rounding up). This should have another AI (it needs to be done for all of the containers). Bob thinks he doesn't want Storage_Error raised here, as this is not running out of all memory. That is a big difference here, especially since the user can understand when they have run out. He thinks that it is very similar to a range 1..10, and talking about 11. He would want to raise Constraint_Error. Tucker suggests that this is similar to Storage_Size on an access type. That raises Storage_Error even though memory is not exhausted. Tucker also suggests defining Capacity_Error. Merge is looked at, but it is decided that there is no problem. Moving to Bounded_Doubly_Linked_Lists. The list has to be implemented with indices, as pointers don't work in assignment. That has to be bitwise copy (remember, no controlled types are desired). Matt shows us a poor man's initialization and finalization scheme, we decided we don't want it. Splice makes sense, but it probably requires some changes. Merge also makes sense and should be included. Maps. Matt wants the hash table to be a prime number. If you allow specifying it, that no longer works. It should be OK for this to be true. Function Init (Capacity : Count_Type; Hash_Table_Length : Hash_Type := 0) return Map; The problem is that these things are not very static looking (and probably not static at all; it would be on the secondary stack at best). So Type Map (Capacity : Count_Type; Hash_Table_Length : Hash_Type); Function Default_Hash_Table_Length (Capacity : Count_Type) return Hash_Type; No restrictions on hash table length, because we are using a bucket implementation. Do not need a function Hash_Table_Length, using that would lock them into the bounded form (and they can read the discriminant anyway. Tucker suggests "Modulus" to "Hash_Type_Length". The current rules don't say how the hash value is mapped to the hash table, so this seems like overspecification. Others think it is good enough. The function then is Default_Modulus. Put the function at the bottom. Assign and Copy are in all of the packages. Copy works like Reserve_Capacity; the hash table also gets shrunk, calling Default_Modulus to figure out the appropriate hash table size. Copy gets an extra parameter Modulus, use Default_Modulus if it is zero. Ordered_Maps. Looks pretty similar. Should we add Assign and Copy to the original containers? We should plan to do it "next time", whenever that is. To_Set would decide its capacity, it does not get a new parameters. Hashed_Maps. Add Default_Modulus, etc. Otherwise works like the Hashed_Maps. Robert leaves us. ---- We talk a bit about indefinite, bounded forms, where the elements come a storage pool and the rest of the "control" stuff is bounded and allocated statically. Randy had previously suggested that, because the unbounded forms allocate all kinds of control junk, and that would complicate a storage pool that is tailored to a particular element type. But the idea seems pretty complex, though, and the users that want this probably wouldn't like the complexity. ---- End of day 1. Day 2. On to the queue abstraction. ---- Generic Type Element_Type is private; Package Ada.Containers.Queues is Type Queue (Capacity : Count_Type) is ... Procedure Enqueue (Q : in out Queue; New_Item : in Element); Pragma Implemented (Enqueue, By_Entry); Procedure Dequeue (Q : in out Queue; Item : out Element); Pragma Implemented (Dequeue, By_Entry); Function Is_Empty (Q : Queue) return Boolean; Function Is_Full (Q : Queue); Function Count (Q : Queue) return Count_Type is abstract; End Ada.Containers.Queues; Dequeuing from an empty queue generally waits; Enqueuing to a full (bounded) queue, then you wait. (You could also raise an exception in both cases.) Generic Type Element_Type is private; Package Ada.Containers.Queues is Type Queue is synchronized interface; Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type) is abstract; Procedure Dequeue (Q : in out Queue; Item : out Element_Type) is abstract; Function Is_Empty (Q : Queue) return Boolean is abstract; Function Is_Full (Q : Queue) is abstract; End Ada.Containers.Queues; Generic Package Ada.Containers.Queues.Unbounded Is Type Queue is synchronized new Queues.Queue with private; Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type); Procedure Dequeue (Q : in out Queue; Item : out Element_Type); Function Is_Empty (Q : Queue) return Boolean; Function Is_Full (Q : Queue); Private Protected type Queue is Procedure Enqueue (Item : Element_Type); -- Entry for bounded cases. Entry Dequeue (Item : out Element_Type); Function Is_Entry return Boolean; Private L : List; End Queue; Function Is_Full (Q : Queue); End Ada.Containers.Queues.Unbounded; Bob doesn't want this interface, because it is different than the current design of the containers. We could have done that for all of them. Tucker says he wanted something like that, but he didn't get it. We could add child signature packages, even to the original (especially for Sets and Maps to extract the commonality). But here we have an interface. Bob thinks we should use a signature here. Matt says that there is penalty here for the use of the interface; two instantiations. The solution would to be write a wrapper generic, that should cut it to one instance for simple uses. Generic Package Ada.Containers.Queues.Bounded Is Type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private; Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type); Procedure Dequeue (Q : in out Queue; Item : out Element_Type); Function Is_Empty (Q : Queue) return Boolean; Function Is_Full (Q : Queue); Private Protected type Queue (Capacity : Count) is Procedure Enqueue (Item : Element_Type); -- Entry for bounded cases. Entry Dequeue (Item : out Element_Type); Function Is_Entry return Boolean; Function Is_Full return Boolean; Private A : Element_Array_Type(1..Capacity); Front, Back : Natural; End Queue; End Ada.Containers.Queues.Bounded; Bob asks about a signature package; he says it has less overhead than an interface. But we decide it is not necessary because the overhead could be avoided by declaring a generic with a formal derived type: Generic Type T is new Inst.Queues.Queue with private; Package Bob worries that copying large objects could be expensive. He thinks about callback to initialize. Tucker worries that the callback would be in a protected action, that would greatly limit what could be done. Matt notes that the point here is to pass an object to the container. The interface package should be Pure, the unbounded packages should be Preelaborate, the types should NOT have preelaborable initialization. The bounded packages (including yesterdays) should have Pure. (We don't want any pointers in the implementation). Lock-free queues. Bob says when we get that figured out we should next talk about bug-free queues. We should be able to implement this interface with a lock-free algorithm (presuming the use implementation-defined constructs for the implementation of the package). That (for now at least) would be in an implementation-defined subpackage. ---- Limited Containers An old Bob Duff design for Ada 95: Lookup_Ptr (Map, Key) return Element_Ptr; Lookup_CPtr (Map, Key) return Element_CPtr --(access-constant) Lookup_Optional_Ptr (Map, Key) return Element_Ptr; Insert_Ptr (Map, Key) return Element_Ptr; Lookup_and_Insert_Ptr (Map, Key) return Element_Ptr; These are all functions, they use a Rosen trick/access parameter to handle updates to the Map. The idea is rename the returned value: O : Element renames Lookup_Ptr (Map, Key).all; --- We turn to Matt's proposal: Generic Type Element_Type is limited private; Package Limited_Hash_Tables is Type Map is tagged limited private; Function Insert (M : not null access Map; K : Key) return not null access Element_Type; Procedure Insert (M : in out Map; K : Key; New_Item : not null access function return Element_Type); -- The function is for initialization. Is vector useful for limited elems? Assume Element_Type is such that Bitwise copy isn't meaningful (e.g. it has internal ptrs) so make it limited. How do you make a stack of these things? When you pop the stack, you want the effect of Unchecked_Deallocation on the object; and the effect of new on pushing the stack. Tucker suggests that the container itself is a storage pool with additional operations Type Stack is new Root_Storage_Pool with record Data : array (...) of Element_Type; Top : Int := 0; End record; Tucker thinks you would need to export a package with a single object of this type. Inst (Element_Type => Scope_Descriptor); Obj : Inst.Stack; Type Scope_Ptr is access Scope_Descriptor; For Scope_Ptr'Storage_Pool use Obj; Then new would add an object to the top of the stack, and Unchecked_Deallocation would pop the item from the stack. Matt wonders: Type Pool_Type (EA : access Storage_Element_Array) is new Root_Storage_Pool ... Type Stack is record EA : Storage_Element_Array (1.. 10*Element_Type'Max_Storage_Size_in_elements); Procedure Push (S : Stack) is Pool : Pool_Type (S.EA); Type Acc is access Element_Type; For Acc'Storage_Pool use Pool; Begin But this doesn't work because the object will be finalized when the access type goes away. Tucker is trying to figure out a fix for that. We decide to look at his subpool proposal in detail. Storage Pool <-->access type 1, access type 2. (subpool) <--> object. The idea is to allow a bunch of subpools which have a (potentially) shorter lifetime than the whole pool. For instance, a hash table defined globally, with a local object. Procedure... Subpool <-- HT (access Subpool) HT1 : HT (new Subpool); or HT (Subpool1'access); Note that you can't use that now, only in a local access type. So we add Storage_Pool to new (per-object): Procedure Insert (H : HT; E : Element_Type) is New HT1.SP Node'(...E...); This works, but is horribly unsafe. So we add some checks. Goal: Ptr must not outlive designated object. Tucker wants to do the checking at the subpool level, not the individual object. So the goal becomes Subpool or stack frame (P) containing Ptr must not outlive subpool containing designated object (D). Rule: Check when storing ptr into object resident in subpool (T for target) that T does not outlive D. Temp := new (HT1.SP) Node'(); Heap_Obj.X := temp; Access value must be able to determine what subpool that contains the designated object. This is an additional requirement on subpools (need a way to get from the address to the pool, implementer must make that work) Heap_obj is in T, Temp is in D. Assert (Does_Not_Outlive(T, D)); Tucker is proposing May_Reference (A, B). This creates a partial ordering on the lifetime of the subpools. This creates a dependence (a counted reference) from subpool A to subpool B. The finalization of a subpool involves checking that the reference count of a pool is zero (but he also wants to detect cycles, all finalizing at once). A subpool handle is a counted reference (it accesses the subpool); no direct access to subpools. The subpool is finalized when its counts gets to zero (modulo cycles). A subpool handle is intended to be used for checks for stack frames. (For instance, you can't return one of these pointers.) Also need to check on return that caller has handle on D. May_Reference and Does_Not_Outlive are provided by the implementation, so that they can be optimized out in many cases. The data would part of the private part of subpools. Tucker hopes that this totally eliminates the possibility of dangling references; the subpool sticks around until the (inter-pool) pointers go away. The purpose is to allow cleaning up sets of data where the type is globally defined. Each subpool is master, both for tasks and finalization. Whatever task finds the last subpool is unreferenced is the one that would do the cleanup. Weak references (subpool+object pointer): can get either null or a strong reference to a subpool handle. There also needs to be way to destroy the strong references when they are not needed. Weak references need to be managed by the storage pool. A strong reference would a controlled object to decrement the reference count. Anonymous access parameter issues. How does that work; perhaps you would want to have master rather than a level for that check. But we had previously said that we wanted to preserve the model. Tucker suggests that we could give them a very deep level (as with anonymous access-to-subprogram), so that they could be passed but not converted to anything else. One could use Unchecked_Deallocation for finalizing, even though it isn't really Unchecked nor would it Deallocate. We'd only be using the finalization side-effect. ---- We turn to looking at control of initialization and finalization. X : LT := F(...); For X'Address use Constant_Value; For X'Master use Master_Obj; -- Object is user defined, master object. In this case, initialization happens at the point of X, but it is initialized into memory previously allocated. The new thing is to be able to specify the master of X (so it doesn't finalize too early). For a bounded hash table: Procedure Insert (HT : in out Hash_Type; Key : in Key_Type) is X : Element_Type := F(...); For X'Address use HT.Element_Array(I); For X'Master use HT.Master; -- Or existing HT'Master Element_Type'Finalize_All (HT.Element_Array(I)); This is unsafe, because we don't know if the original location is already initialized. In any case, we have to suppress the initialization on the original object (else it would be initialized twice). Pragma Suppress_Default_Initialize (HT.Element_Array); Element_Type'Initialize_All (HT.Element_Array(I), HT'Master, F(...)); (The last parameter is optional.) Do we need to pass master to T'Finalize_All? Probably not, Unchecked_Deallocation does not need it. Bob doesn't want the overhead of using a linked list for the finalization of an array of items. That's necessary with this model, because you can't know how the code is going to call T'Initialize_All. He would like the master to be user-defined. Do they get extra space for dope? That's hard to do, because we don't know a size. Element_Type'Initialize_All (HT.Element_Array(I), [F(...)]); Function T'Initialize_All (P : access ET; Initial_Value : ET); -- We use access ET because we want to worry about by-copy types; P should be by-reference. -- Also could use for pointer math. But you could Unchecked_Convert to access ET, then pass UC.all. You would have to apply Suppress_Default_Init before using T'Initialize_All, else the code is erroneous. Bob suggests pragma Suppress_Default_Init be applied to types. And then the Initialize_All and Finalize_All could be called for that type (otherwise, we wouldn't allow it). Tucker notes that you define a derivation of Element_Type to make Bob's idea work. It is erroneous to access an uninitialized object (that is, before the call to Initialize_All. Tucker notes that you could even add a bit to detect this problem. Indeed, one could imagine a type with pragma SDI as an Unchecked_Union of a bag-o-bits and Element_Type. Then actually an assignment would do the right thing (but of course that doesn't work for build-in-place). And if you stored the discriminant, you could actually check for double initialization and finalization. The model is that T'Initialize_All is an assignment to a record where we're changing the discriminants from bag-o-bits to Element_Type, T'Finalize_All goes in the reverse. Logically: Type ET (Initted : Boolean := False) is record Case Initted is When False => Bag_o_Bits : Storage_Element_Array (1 .. Right_Size); When True => Object : Element_Type; End case; End record; Goal, if T'Finalize_All is a no-op (because there is no controlled components), then there should be nothing put on any lists. Finalize_All for Obj w. components that suppress_default_init. If Unchecked_Deallocation needs to remove these, it depends on whether it is on a the list. Randy says it works the same as now, if it is on a list. Lots more brainstorming goes on, but I gave up making notes for a while. There is some discussion about only doing this for types that do not have controlled/task/protected components. Bob thinks that the initialized bit ought to exist (with the possibility of suppressing it), and then the routines should check the bit. Matt suggests possibly using a magical generic for this purpose. He is trying to make a way to get to C++ placement new. Package P is new Magic(Element_Type); Type EAT is array () of P.T; HT Arr : EAT; Ptr := new (HT.Arr(I) Element_Type'(...); Ptr := New_Object (HT.Arr(I)); Delete_Object (HT.Arr(I)); Tucker has to leave to make his train, so the meeting ends at 4:15 p.m. **************************************************************** From: Tucker Taft Sent: Thursday, September 25, 2008 7:16 PM Thanks, Randy, for taking notes. You mention these below in passing, but I believe we (tentatively, of course) agreed on having case-insensitive string hash and comparison, using To_Lower as the "folding" before comparison (by the way, I finally found a definitive statement that that is what the C-based standard requires). I think we also tentatively agreed to provide a Generic_Sort routine that takes Swap and comparison formal subprograms, without actually taking the array itself as a parameter. Thanks again for the notes. **************************************************************** From: Matthew Heaney Sent: Monday, September 29, 2008 5:55 PM Minutes for containers meeting at AdaCore on 22-3 Sep 2008 Sep 22-3 2008 (Mon, Tue) Q: What is our goal for this meeting? A: Greater demand for restricted ("bounded") forms, rather than matching what's in the C++ STL. (There has been actual demand for bounded forms, so that should have priority.) In bounded forms, there is the issue of initialization and finalization of elements. The objects don't actually get created and destroyed, so if an element is deleted from a container, and then re-inserted, what value should the newly-inserted object have? One solution is to use vector semantics. [Similar to a bounded form, a vector has storage for elements that doesn't get deallocated (at least immediately). For that container, there are a few insertion forms. The first form accepts a new value as a parameter, so that's the value that a newly-inserted element has. The second form omits a new value, and in that case a local variable having a default value is assigned to the newly-inserted element, so in that case the element has the default value of the type. In the third case, there's a distinct Insert_Space operation that simply opens up that slot in the internal array, the intent of which is for the caller to make a separate call to Replace_Element to properly assign a value to the newly-inserted element. --MJH] Can you use a storage pool hack to initialize and finalized storage that is statically allocated? No, because when the scope of the (local) access type ends, it will finalize the storage associated with that access type. [on Tue we discussed ways the language could be modified to support such a feature. --MJH] AI05-107 deallocation issues? AI05-0069-1 ?? "standards track technical report" - for this committee. MJH has the task of actually writing the TR. Next ARG meeting: Oct 30-1 (Thu, Fri), Nov 1-2 (Sat, Sun). WG9 meeting on Thu afternoon. [I will be attending the meeting on Sat-Sun. --MJH] Incorporate AI-69 into TR? AI05-0001-1 (describes need for bounded forms?) TR: will eventually become a standard. Synchronized forms - no clear meaning of what a "protected form" even is. Randy said that there was a discussion about this issue on CLA. Lock for a single container vs. lock shared among several containers. Composibility issues. e.g. set of sets. Locking mechanism: semaphore (Seize, Release) vs. monitor Canada: our main customer? What not let user wrap container in a PO himself? Dimensions of our problem space: limited-ness controlled-ness dynamic allocation synchronized new containers other non-container features space-optimized forms persistance Issue with tampering bits: there is a pathological condition in which assignment of the container is made in a tampering context. The problem is that the tampering bits are set, and these get copied to the object on the LHS of the assignment. Without controlled-ness, there's no way to reset these bits. However, the goal is to not require that the bounded forms be implemented as a private derviation from controlled. [Do we require that controlled-ness cannot be used? --MJH] So we could decide that this is a bounded error. The implementation might be able to detect this state and raise an exception. Or it could detect this state and automatically reset the bits. (There's a trick you can use: with an access component that is set to point to the current instance of the type. If you notice that the access value doesn't match the current instance, then assignment has occured and you can reset the bits. Alternatively you could set the access value when you enter the tampering context.) thread-safety vs. performance: if we can't do it better than a user can do himself, then why do it? operations are not potentially blocking [does this refer to synchronized forms???] Since we can't decide what a protected container is, we can punt and just supply a (bounded) queue, which is useful all by itself as a stand-alone abstraction. One possibility is to write a generic queue that imports the underlying structure (e.g. a bounded vector, or unblunded list) as a generic formal type. But then do we supply pre-defined instantiations? [See notes for Tue, where we tenatively decided on what the spec should look like. --MJH] Other abstractions for synchronization: barriers. Not enough complexity here to standardize? (Limited) containers with limited elements: how to finalize elements in a bounded form? What does "new T" mean? Does this count as dynamic allocation, even if (say) the access type is associated with a storage pool that is itself bounded? [I think the answer is yes, because (in GNAT at least) the compiler handles a restrictions pragma by noting where the allocators are used. So in order to satisfy the requirement for "no dynamic allocation" we must use a bounded form (the type is implemented with an array component) instead of importing some storage pool as a generic formal object.] Bounded hash table: issue of how to declare number of elements vs. size of backbone. Backbone size: specified via discriminant vs. generic formal parameter. Secondary stack discrim vs. generic formal instantiation provides defaults (but tagged types cannot have defaults for discrim) MJH argues that it would be nice if the user didn't have to specify backbone size (since he might specify a value that doesn't scatter hash values very well). However the consensus is that we should allow user to control both number of elements and backbone size. Bounded forms: do not use a storage pool. Use per-object storage rather than a "pool" shared among instances. Per-object storage is specified via discriminant (rather than generic formal parameter). Note that assignement of bounded forms will cause CE if discrims don't match. Corrigendum doesn't do much for users; amendment is more useful. Tuck's storage pool for persistence AI. John Barnes/American customers: US decision for proper amendment? What is role of ARG: to make amendment or corrigendum? Protected forms: multiple readers? Or only provide queues? Which operations are waiting? Linda language: has "tuple spaces" Thread-safe vs. atomicity: atomicity is more useful. Ed S. mentioned conference at NYU(?) about hardware-level abort/rety synchronized queue Vector has "empty" elements: created as a result of Insert_Space. It's a bounded error to read from them, so you can't assign them a value via Update_Element (e.g. in indefinite form you don't even have an element), so you must use Replace_Element. Trick for (re)initializing a statically-allocated element: use pragma Import to fake placement new. How to grant last wishes: insert nothing (default init), insert item, insert space. Can potentially raise exception if touch "empty" element. non-limited bounded forms: are not controlled multiset - same as bag Tucker wants MJH to supply an example that demonstrates how a problem is more easily solved using a multiset instead of a existing forms (e.g. map of sets). To guarantee uniqueness of key you could make a two-part key, with one part just a number that simply gets incremented (to satisfy uniqueness requirements). Multiset: how to you designant elements in a subrange. [Using an additional passive iterator that accepts a key. You might also be able to use floor/ceiling to perform active iteration (but maybe not, since they're semantics don't match C++ lower_bound/upper bounded).] Having (limited) container of limited elements is more important that a multiset. Case-insensitive string hash, string equality, string less: defined in terms of To_Upper or To_Lower (answer influences outcome of test)? In GNAT we use To_Lower. _stricmp, _wcsicmp in Microsoft C also uses lowercase compare; gives example of JOHNSON vs. JOHN_HENRY. Whatever we do should be the same as what C does (using 8-bit chars)??? We had originally gotten rid them at the Phoenix meeting. Specify map function to specify folding? But this is more than we really need. We have tenatively decided that they're a good idea: use same names as in GNAT: Ada.Strings.Equal_Case_Insensitive Ada.Strings.Hash_Case_Insensitive Ada.Strings.Less_Case_Insensitive and to fold to lower case. We don't promise that case-insensitive hash returns same result as case-sensitive hash will all lower-case letters (because implementation could use knowledge to make an optimal hash function). It would be possible to make a space-optimized doubly-linked list by xor'ing prev and next, but in order to navigate you need to refer to a pair of nodes. Cursors: for vector cursor can be "ambiguous" (see RM p.243) vs. "invalid" cursor. Radix sort? (But heap sort is probably good enough. "Heap" came from Knuth, but this is same as Floyd's "tree" sort.) Should be have a sort algorithm for an "anonymous" (my term) array? Yes, here's what the spec should look like: 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); --??? gnat-specific? "lock-free container": multi-core extensions for Ada; to be discussed at ARG meeting in Portland. lock-free algorithms transactions multi-core auto_ptr abstraction for Ada. Outside charter of this group, but it's part of "storage management issues" to be disussed by ARG (in Portland?). Persistance: via passive partition or other? pointer-swizzling language extensions for iteration: e.g. vbscript Set objCollection = ... For Each objItem in objCollection 'manipulate objItem Next Sather - nice iteration syntax CLU Randy's proposal: see Ada-Comment on 12 April 2005 (AC-112) super-null arrays Spec of bounded forms: one of our goals is to minimize changes to spec of unbounded form, so we keep some functions that don't necessarily make sense for bounded forms. The bounded non-hashed forms are declared this way (pass capacity as discrim): type Map (Capacity : Count_Type) is tagged private; The bounded hashed forms are declared this way (pass both capacity and hash table length): type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; Capacity function - keep this to support non-prefix function calls; if prefix form is used, language has preference for discriminant so we're OK. Keep Reserve_Capacity, since we can follow same semantics as for unbounded form. One issue (to be resolved) is what exception to propagate if user specifies capacity parameter larger than capacity of bounded container. My examples in the jean repository raise Storage_Error, but there was some debate about whether some other exception (e.g. Constraint_Error) would be better. Bounded vector: defined in terms of unbounded vector. RM language for Move operation of unbounded forms: must state that capacity of source container is allowed to change. Should be described in terms of calling Reserve_Capacity with 0 capacity as value. Don't worry about tamper bits in bounded form (when assigning in tampering context), since it's a bounded error. The vector, list, and ordered containers have the following pair of operations: procedure Assign (Target : in out Vector; Source : Vector); The semantics of Assign are as follows: if Target denotes same object as Source, then do nothing. function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector; The semantics of Copy are as follows: if capacity is larger than source container's length, than use that value as the capacity of LHS. Otherwise, use length of source as capacity. Hashed forms look like this: function Copy (Container : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map; As with other bounded forms, Capacity=0 means use container.length as capacity of target. Modulos=0 means use default_modulous(container.length). There's also a function (declared at end of spec): function Default_Modulus (Capacity : Count_Type) return Hash_Type; This returns a "good" value for the backbone length for a given capacity. Shared pool idea: either generic formal object (of type Storage_Pool'Class) or nodes in package body; see adalib list on 2006/12/10 & 12. Bounded forms have Pure categorization. Brad Moore - has API with heavy use of synchronized interfaces Tue Sep 23 2008 Blocking queue - the minimum we provide for a "protected container." bounded vs. unbounded signatures vs. interface dequeue from empty enqueue to full We discussed various ways of implementing a queue. We finally settled on using an abstract queue interface, with a pair of concrete children, reasoning that the interface could be used to implement class-wide message passing algorithms (see Andy Welling et al): generic type Element_Type is private; package Ada.Containers.Queues is pragma Pure; type Queue is synchronized interface; --??? param names OK? procedure Enqueue (Q : in out Queue; New_Item : Element_Type) is abstract; pragma Implemented (Enqueue, By_Entry); -- ??? -- see RM 9.5 procedure Deque (Q : in out Queue; Element : out Element_Type) is abstract; pragma Implemented (Dequeue, By_Entry); -- ??? function Is_Empty (Q : Queue) return Boolean is abstract; function Is_Full (Q : Queue) return Boolean is abstract; function Length (Q : Queue) return Count_Type is abstract; --??? do we need this? Does this over-specify the interface? -- ??? other ops end Ada.Containers.Queues; generic package Queues.Bounded is --??? should this be Generic_Bounded? pragma Pure; -- ??? type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private; private protected type Queue (Capacity : Count_Type) is ...; end Queues.Bounded; generic package Queues.Unbounded is --??? should this be Generic_Unbounded? pragma Preelaborate; -- ??? type Queue is synchronized new Queues.Queue with private; private protected type Queue is ...; end Queues.Unbounded; We disussed limited containers. Bob D. and Tucker T. have an limited hash table that looks something like: generic type Element_Type is limited private; type Key_Type is private; package Limited_Hash_Tables -- per Bob Duff and Tucker type Map is tagged limited private; -- Ada95 version: function Insert (M : Map; Key : Key_Type) return Elem_Ptr; -- Ada05 version: function Insert (M : not null access Map; Key : KT) return not null access ET; -- another idea to initialize element procedure Insert (M : in out Map; K : KT; New_Item : not null access function Init return ET); Lookup_Ptr (Map; Key) return Elem_Ptr; Lookup_CPtr (Map; Key) return Elem_Const_Ptr; Lookup_Optimal_Ptr (Map; Key) return Elem_Ptr Insert_PTr return Elem_Ptr; Insert_Or_Lookup_Ptr (Map; Key) return Elem_Ptr; -- vector - not so useful for limited elems? -- ET: bitwise copy isn't meaningful (e.g. it has internal ptrs) -- so make it limited -- how to handle the case when item is inserted in container -- deleted from container private type Map is ...; end Limited_Hash_Tables; Discussion of limited containers led to a discussion about initialization and finalization of limited elements. This led to a discussion abount memory management and initialize/finalization issues. We have identified two distinct issues. Tucker often creates long-lived data structures, that get populated but then the same elements remain for the life of the container. He argues that allocation and deallocation of nodes is at the wrong granularity, and he would like everything in the container to be finalized and then deallocated together. The other issue (identified by Bob and Matt) is initialization and finalization of the "inactive" elements in a container. This mostly applies to bounded forms (it also applies to an unbounded vector with more capacity than length). In a bounded form, the storage for elements isn't used immediately -- it's only used when an element is inserted into the container (made "active"). The issue is that if the element type has default initialization, or it's controlled, then when the container object is declared, there is a penalty because all of the (inactive) elements must be initialized. It would be nice if there were a way to defer initialization of the element until it is actually inserted. We spent the remainder of the day brainstorming changes to the language to address these issues. What follows is a rough sketch of what we discussed. Here are a couple of examples of binding a hash table to a pool: type HT (Pool : not null access Subpool_Type) is ...; H : HT(new Subpool_Type); H2 : HT(Subpool_Object'Access); The memory management infrastructure would have to be able to distinguish between the case of allocating a new pool object (is this an example of "coextension"?) and binding to an existing pool object. You can get something like placement new by supplying the pool as an argument: procedure Insert (H : in out HT; K : KT) is X : ... := new (H.Pool.all) Node_Type; -- no new access type here begin Checks: ptr must not outlive designate object (RM 3.10.2). Subpool containing ptr must not outlive subpool containing designated object (D) (really, subpool or stack frame). Check when storing ptr into subpool (really, obj in subpool). temp := new (H.Subpool.all) Node_T D heapobj.X := temp access value -> subpool that contains its designate object operation: Does_Not_Outlive (T, D) heapobj.X := temp; T T must not outlive D procedure May_Reference (A, B) create dependence between subpools; establishes partial order Finalization of a subpool ensures no references (must detect cycles) subpool handle -> subpool counted reference to subpool another check on return that caller has handle on D procedure May_Ref (A, B) weak ref = subpool + object_ptr return null or counted ref (strong ptr) with strong ref, object doesn't go away cache has weak ref - can ask about object result is either null (meaning obj has gone away) or strong ref subpool is master -> finalization of object??? AI-111 Tucker per-object storage pools masters vs. levels accessibility checks conversion from anon access type to named type? static subpools (on stackframe) special case of more general mechanism subpool handle - limited can be passed as arg to new each ht (or stack) is an instance of subpool [The rest of this stuff is the init/final idea. --MJH] X : LT := F; for X'Addr use XYZ; but master of X is local for X'Master ...; suppress default init T'Init_All T'Finalize_All stack of fixed length Finalize_All - to finalize elem ET'Init_All (H.Array(i), H.Master, F(X, Y)'Access); ET'Final_All(H.Array(i)); -- to remove from list pragma Supproess_Default_Init creates extra space for links always applies to a type gives you ET'Init_All and ET'Final_All wrapper of ET - provides extra bit; to indicate whether init'd. discriminated record: discrim says whether init'd or not data is payload pragma Supress_Discrim_Check - to remove per-elem overhead model is that ET'Init is assignment to a discrim rec and changes value of discrim HT "contains" a master calls Finalize "gets finalized at same time" bounded form is sort of like a light-weight controlled object the HT is controlled because it has controlled elements what happens to a composite type with a component for which pragma Suppress_Default_Init is specified? limited bounded case, yes, but useful for non-limited types too useful to prevent vector array from init all junk (inactive) elements e.g. vector instantiated with access type, don't want to null all elements tucker's discrim type: another option to allow just discrim to change I had an idea to abstract-away some of support for light-weight controlled-ness. Just as we have a pkg like this: generic type Object(<>) is limited private; package System.Address_To_Access_Conversions is pragma Preelaborate(Address_To_Access_Conversions); type Object_Pointer is access all Object; function To_Pointer(Value : Address) return Object_Pointer; function To_Address(Value : Object_Pointer) return Address; pragma Convention(Intrinsic, To_Pointer); pragma Convention(Intrinsic, To_Address); end System.Address_To_Access_Conversions; We could have a pkg something like: generic type Object is limited private; package System.Initialization is type Object_Storage is private; -- has size and alignment of type Object -- need separate versions for limited Obj vs. non-limited Obj? type Object_Pointer is access all Object; for Object_Pointer'Storage_Size use 0; -- to default-init object function New_Object (Storage : not null access Object_Storage) return Object_Pointer; -- to copy-assign the object function New_Object (Storage : not null access Object_Storage; Value : Element_Type) return Object_Pointer; procedure Delete_Object (Storage : in out Object_Storage); private type Object_Storage is ...; end System.Initialization; So now you could implement a bounded stack something like: with System.Initialization; generic type ET is private; package Generic_Stacks is type Stack (Capacity : Count_Type) is tagged private; procedure Push (S : in out Stack; E : ET); ... private type Element_Array is array (Count_Type range <>) of aliased Object_Storage; type Stack (Capacity : Count_Type) is tagged record Elements : Element_Array (1 .. Capacity); Top : Count_Type := 0; end record; end; package Generic_Stacks is procedure Push (S : in out Stack; E : ET) is I : constant Count_Type := S.Top + 1; -- this is the part where you might have to pass S'Master, etc. P : Object_Pointer := New_Object (S.Elements (I)'Access); begin P.all := E; S.Top := I; end; ... end Generic_Stacks; **************************************************************** From: Matthew Heaney Sent: Wednesday, October 22, 2008 12:10 AM Grein, Christoph (Fa. ESG) wrote: ... > Is there some place where I can help? (If I find some spare time, of > course.) Yes, of course. The best place is to post to the adalib list. Otherwise, I can give you developer status in jean repository, which would allow you to edit (and check-in) sources directly. > 1.---------------------------------------------------------------------- > [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] > > I think if someone asks for this, he gets what he asked for. A note in > the AARM (or, if this is only a secondary standard to the RM, in > something similar) could be added. OK, that makes sense. I don't think we made any explicit statement in the RM to handle this case for the unbounded forms, so maybe we don't need to worry about it. > 2.---------------------------------------------------------------------- > Why is there a Reserve_Capacity? It's completely useless. Actually, I think that it has semantics identical to the unbounded form. (But I have to think about it. Maybe I over-specified, in which case no discussion would even be necessary.) > Is it just for > compatibility with Ada.Containers.Vectors? Yes. > There are already operations > which are not in Ada.Containers.Vectors, so this breaks compatibility, > so why shouldn't there be some missing? I suspect that the operations we add to the bounded form will eventually migrate into the unbounded forms as well. (I think the only two operations are Assign and Copy. I forget -- were there others?) > 3.---------------------------------------------------------------------- > My lightweight opinion wrt. Constraint_ vs. Storage_Error: > I think all bounded containers should raise the same exception in such > cases. > For vectors: Arrays raise CE; vectors are kind of arrays, so they also > should raise CE. Bounded strings raise CE. OK, that's a data point from a HI user. Reviewing my code I see that I raise both SE and CE, inconsistently. Thanks for the tip. **************************************************************** From: Randy Brukardt Sent: Thursday, October 23, 2008 9:55 PM A quick glance at this did not turn up any wording for Reserve_Capacity for bounded vectors and lists. I think you need to say somewhere that the capacity of the container cannot be changed, and an attempt to set it larger than specified will always fail with Storage_Error (if that what we decided??). Surely that needs to be mentioned (it's the whole point of bounded). I see you do mention it for Maps, but then say it is the same as Unbounded. But that's not quite true; Unbounded is supposed to try to expand the capacity (assuming it is expanding) and raise an exception only if that is not possible. Bounded is not supposed to try, just raise an exception for any attempted expansion (and do nothing for a shrinkage). That is a difference in intent. Surely we want to explain that somewhere, else these containers will not be obviously different. Also note that if Reserve_Capacity is properly documented, changing Insert, etc. isn't needed, because they all call Reserve_Capacity when they need to expand (and that will raise an exception). And I do think you need to mention (but perhaps only in an AARM implementation note) that the bounded forms are not expected to be controlled types. If there is any semantic ramifications of that, we need to change the wording as needed. I didn't read further than that (I have lots of ASIS work still to do). **************************************************************** From: Matthew Heaney Sent: Friday, October 24, 2008 5:51 AM > A quick glance at this did not turn up any wording for > Reserve_Capacity for bounded vectors and lists. For Vector it's on line #105: "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." There is none for lists, since the unbounded form doesn't have that. Bounded hashed map is on line #227: "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." For the bounded hashed set it's on line #358: 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. > I think you need to say somewhere that the capacity of the container > cannot be changed, and an attempt to set it larger than specified will > always fail with Storage_Error (if that what we decided??). Surely > that needs to be mentioned (it's the whole point of bounded). Is this requirement satisfied by descriptions above? > I see you do mention it for Maps, but then say it is the same as > Unbounded. But that part was non-normative. It was in the form of a question to be answered by the ARG during our meeting: "[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]" > But that's not quite true; Unbounded is supposed to try to expand > the capacity (assuming it is expanding) and raise an exception only if that > is not possible. Bounded is not supposed to try, just raise an exception for > any attempted expansion (and do nothing for a shrinkage). That is a > difference in intent. Surely we want to explain that somewhere, else these > containers will not be obviously different. OK, that's fine by me. I was trying to minimize the amount of normative text, but if you think it's more clear to be explicit about behavior for bounded forms then we can leave it in. > Also note that if Reserve_Capacity is properly documented, changing Insert, > etc. isn't needed, because they all call Reserve_Capacity when they need to > expand (and that will raise an exception). Good point. I'll have to review all the spots where Reserve_Capacity is called indirectly, as a side-effect of insertion, etc. > And I do think you need to mention (but perhaps only in an AARM > implementation note) that the bounded forms are not expected to be > controlled types. If there is any semantic ramifications of that, we need to > change the wording as needed. Right, I asked that question on line #14: "[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, ..." **************************************************************** From: Randy Brukardt Sent: Monday, November 10, 2008 9:11 PM I'm working on the minutes of the Portland meeting, and I have: "These containers cannot be controlled, because Ada.Finalization is Preelaborated and these packages are Pure. There probably should be an AARM implementation note to that effect." But when looking at this, I remembered that the container types are defined to "need finalization" (that is, are potentially controlled). We surely don't want the bounded forms to have this property, so we need explicit wording to say that the type Vector in Bounded_Vectors does not "need finalization". (That is, to repeal that part of A.18.2(84/2), as we're planning to inherit everything except a specific list of changes from the unbounded forms.) Similar wording is needed for all of the other bounded form container types. Otherwise, Adam will make us fix it in future. ;-) I preliminarily put a mention of this into the minutes, but since we didn't talk about it explicitly in Portland, I wanted to mention it here as well. **************************************************************** From: Tucker Taft Sent: Monday, November 10, 2008 9:22 PM Good catch. Yes, we clearly don't want the bounded container types to "need finalization." ****************************************************************