!standard A.18.2(97.1/3) 18-12-06 AI12-0111-1/09 !class Amendment 16-06-06 !status work item 14-05-15 !status received 14-02-08 !priority Medium !difficulty Hard !qualifier Omission !subject Stable Containers to reduce tampering checks !summary Add a nested package Stable within each Container package, which provides a *stabilized view* of an underlying regular (unstable) container. Such stable containers have no operations that change their shape, and the stabilization "lock" on the underlying regular container need only be set once when the view is created, and released when the view goes away. Simplify "tampering with elements" to be equivalent to "tampering with cursors" for containers of elements of a definite type. For containers of an indefinite type, the original definition remains. Add an aspect Iterator_View to be used by "of" form iterators to determine the view of the container used. Add this to all containers to use the stable view of the container. !problem The performance of the standard containers is way less efficient than the C++ containers. The primary cause of this is tampering checks, and specifically, the cost of setting up and tearing down the tampering state. In a loop, this overhead can be considerable. The standard should be improved to reduce this overhead. !proposal We propose to eliminate the requirement for per-reference tampering checks by providing a mechanism to "stabilize" a container against tampering. This can be used by the iterator expansion and elsewhere. When a container is stabilized, we could provide a different mechanism for indexing which would fail, or not be available, if the iterator were not stabilized. We propose the notion of a Stable_XXX handle to the container as a whole, which would be a separate type with cheaper indexing operations. This can also be a way to get read-only references which could be passed to multiple tasks. That is you could safely pass a read-only stable reference to multiple tasks. We propose to define a nested package "Stable" within each of the various Container packages, removing operations that tamper with cursors. Below we provide a Stable subpackage for Vectors. The stable vector is of a limited type, and has a non-null access discriminant called "Base," with no default, which refers to an underlying unstable vector which is automatically stabilized as long as the stable vector exists (hence the stabilized vector needs to be controlled so that when it goes away, it automatically releases the stabilization "lock" on the underlying vector). Two essential properties of stable containers are that they have no tampering checks, and can be iterated by multiple tasks in parallel. We also define an aspect Iterator_View which defines the container view to use for an "of" form iterator (formally, a "container element iterator"). We use this to have all such iterators for the language-defined containers to use the stable view of the container (meaning that there are not tampering checks on the individual calls to Reference). Note that we propose to reclassify Merge as tampering with cursors, and to define "tampering with elements" to be the same as tampering with cursors for all containers other than those with indefinite elements. !wording [Note: The below text will appear under an existing heading of: The following type-related operational aspects may be specified for an indexable container type T:] Add after 5.5.1(9/3): Iterator_View This aspect is specified by a name that denotes a type T2 with the following properties: * T2 is declared in the same compilation unit as T; * T2 is an indexable container type; * T2 has a single discriminant which is an access discriminant designating T; and * The default iterator subtypes for T and T2 statically match. Add to the end of 5.5.2(12/3): If the container type has Iterator_View specified, an object of the Iterator_View type is created with the discriminant referencing the denoted iterable container object. This is the *iterated container object* for this loop. Otherwise, the denoted iterable container object is the *iterated container object* for this loop. AARM Reason: If Iterator_View is specified, we add an extra object and use that object. This allows these iterators to use the stable view (defined in each of the language-defined containers) to do the iteration. That eliminates the need to set and clear the tampering with elements indication each time Reference is called; that eliminates substantial overhead as finalization is typically used to implement this. In 5.5.2(13/3), replace each use of "iterable container object" with "iterated container object". [Author's note: Not showing this wording here, as it is heavily modified by the parallel iterator proposal, AI12-0266-1.] Add after A.18(2/5): Some operations of the language-defined child units of Ada.Containers have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. An action on a container that might add or remove an element is considered to /tamper with cursors/, and these are prohibited during all such operations. An action on a container that might replace an element with one of a different size is considered to /tamper with elements/, and these are prohibited during certain of such operations. The details of the specific actions that are considered to tamper with cursors or elements are defined for each child unit of Ada.Containers. Several of the language-defined child units of Ada.Containers include a nested package named Stable, which provides a view of a container that prohibits any operations that would tamper with elements. By using a Stable view for manipulating a container, the number of tampering checks performed while performing the operations can be reduced. The details of the Stable subpackage are defined separately for each child unit of Ada.Containers that includes such a nested package. Replace A.18.2(8/3) with: type Vector is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type, Iterator_View => Stable.Vector; pragma Preelaborable_Initialization(Vector); (make a similar change for each container type, in A.18.3(6/3), A.18.5(3/3), A.18.6(4/3), A.18.8(3/3), A.18.9(4/3), A.18.10(8/3). Delete A.18.2(90/2) (introduction to tampering -- now in A.18) (also delete similar paragraphs elsewhere: A.18.3(61/2), A.18.4(7/2), A.18.7(7/2), A.18.10(80/3)) Modify A.18.2(92/2) (and similar paragraphs elsewhere): * it inserts or deletes elements of V, that is, it calls the Insert, Insert_Space, Clear, Delete, or Set_Length procedures{,or Merge procedure of an instance of Generic_Sorting,} with V as a parameter; or Replace A.18.2(95/2-97/2) (also do the same with similar paragraphs elsewhere: A.18.3(67/2-69/2), A.18.4(13/2-15/2), A.18.7(13/2-14/2), A.18.10(87/3-89/3)) with: A subprogram is said to tamper with elements of a vector object V if it tampers with cursors of V. AARM Reason: A definite element cannot change size, so there are no other operations that tamper with elements. That's not true for the indefinite containers, which is why we leave this separate definition. Insert after A.18.2(79/2): [Author's note: Below, we have left in the original paragraph numbers from the Vector container because we thought they might be useful, and mostly because we are too lazy to remove them.] ... -- enclosing package Ada.Containers.Vectors package Stable is 8/3 type Vector (Base : not null access Vectors.Vector) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector); 9/2 type Cursor is private; pragma Preelaborable_Initialization(Cursor); 10/2 Empty_Vector : constant Vector; 11/2 No_Element : constant Cursor; 11.1/3 function Has_Element (Position : Cursor) return Boolean; 11.2/3 package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); 12/2 function "=" (Left, Right : Vector) return Boolean; 13/2 function To_Vector (Length : Count_Type) return Vector; 14/2 function To_Vector (New_Item : Element_Type; Length : Count_Type) return Vector; 15/2 function "&" (Left, Right : Vector) return Vector; 16/2 function "&" (Left : Vector; Right : Element_Type) return Vector; 17/2 function "&" (Left : Element_Type; Right : Vector) return Vector; 18/2 function "&" (Left, Right : Element_Type) return Vector; 19/2 function Capacity (Container : Vector) return Count_Type; 21/2 function Length (Container : Vector) return Count_Type; 23/2 function Is_Empty (Container : Vector) return Boolean; 25/2 function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor; 26/2 function To_Index (Position : Cursor) return Extended_Index; 27/2 function Element (Container : Vector; Index : Index_Type) return Element_Type; 28/2 function Element (Position : Cursor) return Element_Type; 29/2 procedure Replace_Element (Container : in out Vector; Index : in Index_Type; New_Item : in Element_Type); 30/2 procedure Replace_Element (Container : in out Vector; Position : in Cursor; New_item : in Element_Type); 31/2 procedure Query_Element (Container : in Vector; Index : in Index_Type; Process : not null access procedure (Element : in Element_Type)); 32/2 procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type)); 33/2 procedure Update_Element (Container : in out Vector; Index : in Index_Type; Process : not null access procedure (Element : in out Element_Type)); 34/2 procedure Update_Element (Container : in out Vector; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type)); 34.1/3 type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; 34.2/3 type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; 34.3/3 function Constant_Reference (Container : aliased in Vector; Index : in Index_Type) return Constant_Reference_Type; 34.4/3 function Reference (Container : aliased in out Vector; Index : in Index_Type) return Reference_Type; 34.5/3 function Constant_Reference (Container : aliased in Vector; Position : in Cursor) return Constant_Reference_Type; 34.6/3 function Reference (Container : aliased in out Vector; Position : in Cursor) return Reference_Type; 34.7/3 procedure Assign (Target : in out Vectors.Vector; Source : in Vector); 34.8/3 function Copy (Source : Vector) return Vector; function Copy (Source : Vectors.Vector) return Vector; 54/2 procedure Reverse_Elements (Container : in out Vector); 55/2 procedure Swap (Container : in out Vector; I, J : in Index_Type); 56/2 procedure Swap (Container : in out Vector; I, J : in Cursor); 57/2 function First_Index (Container : Vector) return Index_Type; 58/2 function First (Container : Vector) return Cursor; 59/2 function First_Element (Container : Vector) return Element_Type; 60/2 function Last_Index (Container : Vector) return Extended_Index; 61/2 function Last (Container : Vector) return Cursor; 62/2 function Last_Element (Container : Vector) return Element_Type; 63/2 function Next (Position : Cursor) return Cursor; 64/2 procedure Next (Position : in out Cursor); 65/2 function Previous (Position : Cursor) return Cursor; 66/2 procedure Previous (Position : in out Cursor); 67/2 function Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'First) return Extended_Index; 68/2 function Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 69/2 function Reverse_Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'Last) return Extended_Index; 70/2 function Reverse_Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 71/2 function Contains (Container : Vector; Item : Element_Type) return Boolean; 73/2 procedure Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor)); 74/2 procedure Reverse_Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor)); 74.1/3 function Iterate (Container : in Vector) return Vector_Iterator_Interfaces.Reversible_Iterator'Class; 74.2/3 function Iterate (Container : in Vector; Start : in Cursor) return Vector_Iterator_Interfaces.Reversible_Iterator'Class; 75/2 generic with function "<" (Left, Right : Element_Type) return Boolean is <>; package Generic_Sorting is 76/2 function Is_Sorted (Container : Vector) return Boolean; 77/2 procedure Sort (Container : in out Vector); 79/2 end Generic_Sorting; 80/2 private 81/2 ... -- not specified by the language 82/2 end Stable; Insert the following at the end of A.18.2: The nested package Vectors.Stable provides a type Stable.Vector that represents a /stable/ vector, which is one that cannot grow and shrink. Such a vector can be created by calling the To_Vector or Copy functions, or by establishing a /stabilized view/ of a regular Vector. The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors. If a stable vector is declared with the Base discriminant designating a pre-existing regular vector, the stable vector represents a stabilized view of the underlying regular vector, and any operation on the stable vector is reflected on the underlying regular vector. While a stabilized view exists, any operation that tampers with elements performed on the underlying vector is prohibited. The finalization of a stable vector that provides such a view removes this restriction on the underlying regular vector Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable vector is declared without specifying Base, the object must be initialized. The initializing expression of the stable vector, Redundant[typically a call on To_Vector or Copy], determines the Length of the vector. By default the Length is zero. The Length of a stable vector never changes after initialization. Add in the Indefinite_Vectors section, after A.18.11(9/4): * The operations Replace_Element, Reverse_Elements, and Swap, and the nested generic unit Generic_Sorting are omitted from the nested package Stable. * A subprogram is said to /tamper with elements/ of an indefinite vector object V if: - it tampers with cursors of V; or - it replaces one or more elements of V, that is, it calls the Replace_Element, Reverse_Elements, or Swap procedures, or the Sort procedures of an instance of Generic_Sorting, with V as a parameter. AARM Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. -------- Insert after A.18.3(51/2): [Author's note: Below, we have left in the original paragraph numbers from the Vector container because we thought they might be useful, and mostly because we are too lazy to remove them.] ... -- enclosing package Ada.Containers.Doubly_Linked_Lists package Stable is 8/3 type List (Base : not null access Doubly_Linked_Lists.List) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(List); 9/2 type Cursor is private; pragma Preelaborable_Initialization(Cursor); 10/2 Empty_List : constant List; 11/2 No_Element : constant Cursor; 11.1/3 function Has_Element (Position : Cursor) return Boolean; 11.2/3 package List_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); 12/2 function "=" (Left, Right : List) return Boolean; 21/2 function Length (Container : List) return Count_Type; 23/2 function Is_Empty (Container : List) return Boolean; 28/2 function Element (Position : Cursor) return Element_Type; 30/2 procedure Replace_Element (Container : in out List; Position : in Cursor; New_item : in Element_Type); 32/2 procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type)); 34/2 procedure Update_Element (Container : in out List; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type)); 34.1/3 type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; 34.2/3 type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; 34.5/3 function Constant_Reference (Container : aliased in List; Position : in Cursor) return Constant_Reference_Type; 34.6/3 function Reference (Container : aliased in out List; Position : in Cursor) return Reference_Type; 34.7/3 procedure Assign (Target : in out Doubly_Linked_Lists.List; Source : in List); 34.8/3 function Copy (Source : List) return List; function Copy (Source : Doubly_Linked_Lists.List) return List; 54/2 procedure Reverse_Elements (Container : in out List); 56/2 procedure Swap (Container : in out List; I, J : in Cursor); 58/2 function First (Container : List) return Cursor; 59/2 function First_Element (Container : List) return Element_Type; 61/2 function Last (Container : List) return Cursor; 62/2 function Last_Element (Container : List) return Element_Type; 63/2 function Next (Position : Cursor) return Cursor; 64/2 procedure Next (Position : in out Cursor); 65/2 function Previous (Position : Cursor) return Cursor; 66/2 procedure Previous (Position : in out Cursor); 68/2 function Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 70/2 function Reverse_Find (Container : List; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 71/2 function Contains (Container : List; Item : Element_Type) return Boolean; 73/2 procedure Iterate (Container : in List; Process : not null access procedure (Position : in Cursor)); 74/2 procedure Reverse_Iterate (Container : in List; Process : not null access procedure (Position : in Cursor)); 74.1/3 function Iterate (Container : in List) return List_Iterator_Interfaces.Reversible_Iterator'Class; 74.2/3 function Iterate (Container : in List; Start : in Cursor) return List_Iterator_Interfaces.Reversible_Iterator'Class; 75/2 generic with function "<" (Left, Right : Element_Type) return Boolean is <>; package Generic_Sorting is 76/2 function Is_Sorted (Container : List) return Boolean; 77/2 procedure Sort (Container : in out List); 79/2 end Generic_Sorting; 80/2 private 81/2 ... -- not specified by the language 82/2 end Stable; private ... -- not specified by the language end Ada.Containers.Doubly_Linked_Lists; Delete A.18.3(67/2-69/2). Modify A.18.3(69.1/4) as follows: When tampering with cursors is prohibited for a particular list object L, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the cursors of L, leaving L unmodified. [Similarly, when tampering with elements is prohibited for a particular list object L, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the elements of L (or tamper with the cursors of L), leaving L unmodified.] These checks are made before any other defined behavior of the body of the language-defined subprogram. Insert new section at the end of A.18.3: The nested package Doubly_Linked_Lists.Stable provides a type Stable.List that represents a /stable/ list, which is one that cannot grow and shrink. Such a list can be created by calling the To_Vector or Copy functions, or by establishing a /stabilized view/ of a regular Vector. The operations of this package are equivalent to those for regular Doubly_Linked_Lists, except that no tampering checks are performed on stable lists. If a stable list is declared with the Base discriminant designating a pre-existing regular list, the stable list represents a stabilized view of the underlying regular list, and any operation on the stable list is reflected on the underlying regular list. While a stabilized view exists, any operation that tampers with elements performed on the underlying list is prohibited. The finalization of a stable list that provides such a view removes this restriction on the underlying regular list Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable list is declared without specifying Base, the object must be initialized. The initializing expression of the stable list, Redundant[typically a call on To_Vector or Copy], determines the Length of the list. By default the Length is zero. The Length of a stable list never changes after initialization. ----- In the section on Indefinite_Doubly_Linked_Lists, A.18.12, add after para 8/4: * The operations Replace_Element and Swap are omitted from the nested package Stable. * A subprogram is said to tamper with elements of an indefinite list object L if: - it tampers with cursors of L; or - it replaces one or more elements of L, that is, it calls the Replace_Element or Swap procedures with L as a parameter. AARM Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. --- In section A.18.4 on Maps, modify A.18.4(13/2) as follows: * A subprogram is said to tamper with elements of a map object M if {the formal Element_Type is indefinite (see A.18.13 and A.18.14), and}: Insert at end of A.18.4: The nested package Stable provides a type Stable.Map that represents a /stable/ map, which is one that cannot grow and shrink. Such a map can be created by calling the Copy functions, or by establishing a /stabilized view/ of a regular Map. The operations of this package are equivalent to those for regular Hashed_Maps, except that no tampering checks are performed on stable maps. If a stable map is declared with the Base discriminant designating a pre-existing regular map, the stable map represents a stabilized view of the underlying regular map, and any operation on the stable map is reflected on the underlying regular map. While a stabilized view exists, any operation that tampers with elements performed on the underlying map is prohibited. The finalization of a stable map that provides such a view removes this restriction on the underlying regular map Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable map is declared without specifying Base, the object must be initialized. The initializing expression of the stable map, Redundant[typically a call on Copy], determines the Length of the map. By default the Length is zero. The Length of a stable map never changes after initialization. Insert after A.18.5(38/2): [Author's note: Below, we have left in the original paragraph numbers from the Hashed_Maps container because we thought they might be useful, and mostly because we are too lazy to remove them.] package Stable is 3/3 type Map (Base : not null access Hashed_Maps.Map) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; 4/2 type Cursor is private; pragma Preelaborable_Initialization(Cursor); 5/2 Empty_Map : constant Map; 6/2 No_Element : constant Cursor; 6.1/3 function Has_Element (Position : Cursor) return Boolean; 6.2/3 package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); 7/2 function "=" (Left, Right : Map) return Boolean; 8/2 function Capacity (Container : Map) return Count_Type; 9/2 procedure Reserve_Capacity (Container : in out Map; Capacity : in Count_Type); 10/2 function Length (Container : Map) return Count_Type; 11/2 function Is_Empty (Container : Map) return Boolean; 12/2 procedure Clear (Container : in out Map); 13/2 function Key (Position : Cursor) return Key_Type; 14/2 function Element (Position : Cursor) return Element_Type; 15/2 procedure Replace_Element (Container : in out Map; Position : in Cursor; New_Item : in Element_Type); 16/2 procedure Query_Element (Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in Element_Type)); 17/2 procedure Update_Element (Container : in out Map; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type)); 17.1/3 type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; 17.2/3 type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; 17.3/3 function Constant_Reference (Container : aliased in Map; Position : in Cursor) return Constant_Reference_Type; 17.4/3 function Reference (Container : aliased in out Map; Position : in Cursor) return Reference_Type; 17.5/3 function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type; 17.6/3 function Reference (Container : aliased in out Map; Key : in Key_Type) return Reference_Type; 17.7/3 procedure Assign (Target : in out Hashed_Map.Map; Source : in Map); 17.8/3 function Copy (Source : Map; Capacity : Count_Type := 0) return Map; procedure Replace (Container : in out Map; Key : in Key_Type; New_Item : in Element_Type); 27/2 function First (Container : Map) return Cursor; 28/2 function Next (Position : Cursor) return Cursor; 29/2 procedure Next (Position : in out Cursor); 30/2 function Find (Container : Map; Key : Key_Type) return Cursor; 31/2 function Element (Container : Map; Key : Key_Type) return Element_Type; 32/2 function Contains (Container : Map; Key : Key_Type) return Boolean; 34/2 function Equivalent_Keys (Left, Right : Cursor) return Boolean; 35/2 function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean; 36/2 function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean; 37/2 procedure Iterate (Container : in Map; Process : not null access procedure (Position : in Cursor)); 37.1/3 function Iterate (Container : in Map) return Map_Iterator_Interfaces.Forward_Iterator'Class; 38/2 private 39/2 ... -- not specified by the language 40/2 end Stable; ---- Insert after A.18.6(51.2/3): [Author's note: Below, we have left in the original paragraph numbers from the Ordered_Maps container because we thought they might be useful, and mostly because we are too lazy to remove them.] package Stable is function Equivalent_Keys (Left, Right : Key_Type) return Boolean; 4/3 type Map (Base : not null access Ordered_Maps.Map) is is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; 5/2 type Cursor is private; pragma Preelaborable_Initialization(Cursor); 6/2 Empty_Map : constant Map; 7/2 No_Element : constant Cursor; 7.1/3 function Has_Element (Position : Cursor) return Boolean; 7.2/3 package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); 8/2 function "=" (Left, Right : Map) return Boolean; 9/2 function Length (Container : Map) return Count_Type; 10/2 function Is_Empty (Container : Map) return Boolean; 12/2 function Key (Position : Cursor) return Key_Type; 13/2 function Element (Position : Cursor) return Element_Type; 14/2 procedure Replace_Element (Container : in out Map; Position : in Cursor; New_Item : in Element_Type); 15/2 procedure Query_Element (Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in Element_Type)); 16/2 procedure Update_Element (Container : in out Map; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type)); 16.1/3 type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; 16.2/3 type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; 16.3/3 function Constant_Reference (Container : aliased in Map; Position : in Cursor) return Constant_Reference_Type; 16.4/3 function Reference (Container : aliased in out Map; Position : in Cursor) return Reference_Type; 16.5/3 function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type; 16.6/3 function Reference (Container : aliased in out Map; Key : in Key_Type) return Reference_Type; 16.7/3 procedure Assign (Target : in out Ordered_Map.Map; Source : in Map); 16.8/3 function Copy (Source : Map) return Map; 22/2 procedure Replace (Container : in out Map; Key : in Key_Type; New_Item : in Element_Type); 28/2 function First (Container : Map) return Cursor; 29/2 function First_Element (Container : Map) return Element_Type; 30/2 function First_Key (Container : Map) return Key_Type; 31/2 function Last (Container : Map) return Cursor; 32/2 function Last_Element (Container : Map) return Element_Type; 33/2 function Last_Key (Container : Map) return Key_Type; 34/2 function Next (Position : Cursor) return Cursor; 35/2 procedure Next (Position : in out Cursor); 36/2 function Previous (Position : Cursor) return Cursor; 37/2 procedure Previous (Position : in out Cursor); 38/2 function Find (Container : Map; Key : Key_Type) return Cursor; 39/2 function Element (Container : Map; Key : Key_Type) return Element_Type; 40/2 function Floor (Container : Map; Key : Key_Type) return Cursor; 41/2 function Ceiling (Container : Map; Key : Key_Type) return Cursor; 42/2 function Contains (Container : Map; Key : Key_Type) return Boolean; 44/2 function "<" (Left, Right : Cursor) return Boolean; 45/2 function ">" (Left, Right : Cursor) return Boolean; 46/2 function "<" (Left : Cursor; Right : Key_Type) return Boolean; 47/2 function ">" (Left : Cursor; Right : Key_Type) return Boolean; 48/2 function "<" (Left : Key_Type; Right : Cursor) return Boolean; 49/2 function ">" (Left : Key_Type; Right : Cursor) return Boolean; 50/2 procedure Iterate (Container : in Map; Process : not null access procedure (Position : in Cursor)); 51/2 procedure Reverse_Iterate (Container : in Map; Process : not null access procedure (Position : in Cursor)); 51.1/3 function Iterate (Container : in Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class; 51.2/3 function Iterate (Container : in Map; Start : in Cursor) return Map_Iterator_Interfaces.Reversible_Iterator'Class; 52/2 private 53/2 ... -- not specified by the language 54/2 end Stable; 55/2 In the section on Indefinite_Hashed_Maps, A.18.13, add after para 9/4: * The operations Replace and Replace_Element are omitted from the nested package Stable. * A subprogram is said to tamper with elements of a map object M if: - it tampers with cursors of M; or - it replaces one or more elements of M, that is, it calls the Replace or Replace_Element procedures with M as a parameter. AARM Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. In the section on Indefinite_Ordered_Maps, A.18.14, add after para 9/4: * The operations Replace and Replace_Element are omitted from the nested package Stable. * A subprogram is said to tamper with elements of a map object M if: - it tampers with cursors of M; or - it replaces one or more elements of M, that is, it calls the Replace or Replace_Element procedures with M as a parameter. AARM Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. ---- Insert at end of A.18.7: The nested package Stable provides a type Stable.Set that represents a /stable/ set, which is one that cannot grow and shrink. Such a set can be created by calling the Copy functions, or by establishing a /stabilized view/ of a regular Set. The operations of this package are equivalent to those for regular maps, except that no tampering checks are performed on stable sets. If a stable set is declared with the Base discriminant designating a pre-existing regular set, the stable set represents a stabilized view of the underlying regular set, and any operation on the stable set is reflected on the underlying regular set. While a stabilized view exists, any operation that tampers with elements performed on the underlying set is prohibited. The finalization of a stable set that provides such a view removes this restriction on the underlying regular set Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable set is declared without specifying Base, the object must be initialized. The initializing expression of the stable set, Redundant[typically a call on Copy], determines the Length of the set. By default the Length is zero. The Length of a stable set never changes after initialization. Insert code for Hashed_Sets.Stable after A.18.8(59/2): ... analogous to Hashed_Maps.Stable, but list of omitted operations is instead: Procedures Reserve_Capacity, Clear, Replace_Element, Move, Insert, Include, Replace, Exclude, Delete, Union, Intersection, Difference, and Symmetric_Difference are omitted, as is the nested generic package Generic_Keys. Insert code for Ordered_Sets.Stable after A.18.9(74/2): ... analogous to Ordered_Maps.Stable, but list of omitted operations is instead: Procedures Reserve_Capacity, Clear, Replace_Element, Move, Insert, Include, Replace, Exclude, Delete, Delete_First, Delete_Last, Union, Intersection, Difference, and Symmetric_Difference are omitted, as is the nested generic package Generic_Keys. [Author's note: For a Set, there is no additional operations that tamper with elements. We should move AARM A.18.7(14.a-b/2) into A.18.15 and A.18.16 to explain why there is no "tampering with elements" definition in those packages.] Insert code for Multiway_Trees.Stable after A.18.10(70/3): ... analogous to Vectors.Stable, but list of omitted operations is instead: Procedures Clear, Move, Insert_Child, Append_Child, Prepend_Child, Delete_Leaf, Delete_Subtree, Delerte_Children, Copy_Subtree, Splice_Subtree, and Splice_Children are omitted. Insert at end of A.18.10: The nested package Stable provides a type Stable.Tree that represents a /stable/ tree, which is one that cannot grow and shrink. Such a tree can be created by calling the Copy functions, or by establishing a /stabilized view/ of a regular Tree. The operations of this package are equivalent to those for regular maps, except that no tampering checks are performed on stable trees. If a stable tree is declared with the Base discriminant designating a pre-existing regular tree, the stable tree represents a stabilized view of the underlying regular tree, and any operation on the stable tree is reflected on the underlying regular tree. While a stabilized view exists, any operation that tampers with elements performed on the underlying tree is prohibited. The finalization of a stable tree that provides such a view removes this restriction on the underlying regular tree Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable tree is declared without specifying Base, the object must be initialized. The initializing expression of the stable tree, Redundant[typically a call on Copy], determines the Length of the tree. By default the Length is zero. The Length of a stable tree never changes after initialization. Add after A.18.17(8/4): [Indefinite_Multiway_Trees] A subprogram is said to tamper with elements of a tree object T if: * it tampers with cursors of T; or * it replaces one or more elements of T, that is, it calls the Replace_Element or Swap procedures with T as a parameter. * The operations Replace_Element and Swap are omitted from the Stable subpackage. !discussion As mentioned in the proposal, the intent is that a stable container can be manipulated more efficiently, and safely walked concurrently by multiple tasks, because tampering bits need not be updated as part of each operation. Tampering was primarily intended to prevent erroneous/unspecified behavior. As part of this AI we have also simplified the rules for tampering, by eliminating the tampering with elements checks when elements are of a definite subtype. More specifically, tampering with cursors was intended to prevent loops from going off the rails because an element was deleted (which might cause an iterator to run into non-existent memory) or inserted (which might cause an iterator to go into an infinite loop). Tampering with elements was intended to prevent an element that is actively being used from disappearing or being replaced (which might change the "shape" of the element). We are proposing to restrict this concern to cases where the formal element type is indefinite, since for definite types, normal assignment can be used to replace objects, and access types will work safely across assignment to their designated objects. We make a stable container type a limited type because normal assignment would almost certainly fail due to a mismatch of the access discriminant. We considered using child (generic) packages rather than nested packages, but the complexity of using child generic packages, requiring a separate "with" clause and an appropriate parameterless instantiation, made that a less attractive option. !ASIS No ASIS effect. !ACATS test ** TBD. !appendix [This thread diverged from the one in AI12-0110-1; there was some cross-pollination.] From: Robert Dewar Sent: Monday, February 10, 2014 7:23 AM BTW, while on the subject of tampering checks, we are becoming more worried that the design of the containers in Ada is fundamentally flawed. It is a serious embarrassment, one noted by several of our customers, that the performance of the Ada containers is way less efficient than the C++ containers, and we fear that a lot of this inefficiency is mandated by the Ada design. In the case of bounded containers, we have a set of "formal" containers that are much simpler and much more efficient. I don't know if in practice we will end up replacing the official containers entirely, perhaps so. *************************************************************** From: Brad Moore Sent: Monday, February 10, 2014 9:45 AM It strikes me that Tampering should be a check that can be suppressed with pragma Suppress. Maybe it was an oversight that it isnt already a suppressable check? Once programmers are satisfied that their code does not tamper with the containers, they might want to choose to suppress the tampering checks, to obtain better performance. I'd much rather see that than "replace the official containers entirely". *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 9:51 AM > It strikes me that Tampering should be a check that can be suppressed > with pragma Suppress. > Maybe it was an oversight that it isnt already a suppressable check? Well the notion of suppressible checks, which can be turned on and off at will, does not work well with run-time units where the checks are deeply embedded into the run-time code and its design. > Once programmers are satisfied that their code does not tamper with > the containers, they might want to choose to suppress the tampering > checks, to obtain better performance. > > I'd much rather see that than "replace the official containers > entirely". Well yes, but it won't help at all I am afraid. *************************************************************** From: Jean-Pierre Rosen Sent: Monday, February 10, 2014 10:21 AM > It strikes me that Tampering should be a check that can be suppressed > with pragma Suppress. > Maybe it was an oversight that it isnt already a suppressable check? > > Once programmers are satisfied that their code does not tamper with > the containers, they might want to choose to suppress the tampering > checks, to obtain better performance. > > I'd much rather see that than "replace the official containers > entirely". I agree with you, but how could you do that if the containers are written in Ada, like regular packages? Suppress can remove only compiler generated checks. Tampering checks could be suppressed only if fully implemented as pre/post conditions, but I doubt this is doable (disclaimer: I never actually looked into the implementation of containers, please correct me if I'm wrong) *************************************************************** From: Brad Moore Sent: Monday, February 10, 2014 10:20 AM > Well the notion of suppressible checks, which can be turned on and off > at will, does not work well with run-time units where the checks are > deeply embedded into the run-time code and its design. I see, but I would have thought that something could be done however. Maybe if the suppression is globally specified as a configuration pragma, the tampering could be removed by the compiler as dead code, similar to when a constant boolean expression is encountered in GNAT? i.e. Do_Tampering_Checks : constant Boolean := False; if Do_Tampering_Checks then ... -- Tampering check code end if; *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 10:33 AM > I see, but I would have thought that something could be done however. > Maybe if the suppression is globally specified as a configuration > pragma, the tampering could be removed by the compiler as dead code, > similar to when a constant boolean expression is encountered in GNAT? How can that help, the run-time does not get recompiled in response to setting a configuration pragma! *************************************************************** From: Brad Moore Sent: Monday, February 10, 2014 10:59 AM Could it be used as a switch to select a different container library to link with, then? *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 11:01 AM > Could it be used as a switch to select a different container library to link > with, then? Conceivably a configuration pragma could be used in this way, but it is more attractive to just fix the existing containers IMO. This is damaging the language, and what I would be inclined to do is to make a new set of efficient containers, and retain the old ones just to pass ACATS tests but not expect many other people to use them. I don't see why we should have a default that is unusable. *************************************************************** From: Brad Moore Sent: Monday, February 10, 2014 11:14 AM I would say that not everyone cares about performance, when using containers. Having safety as the default seems like the right choice to me for Ada. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 11:20 AM > I would say that not everyone cares about performance, when using > containers. Having safety as the default seems like the right choice to > me for Ada. Ada is supposed to be about getting safety WITHOUT paying a huge performance hit. We are finding a lot of users who are very disappointed to find out that the containers are a) SO much worse than C++ b) as a consequence pretty much useless We found that ourselves internally, so some of our attempts to use the standard containers have just been abandoned in favor of spinning our own, and that is what will happen with customers. Believe me "we know that the containers in Ada are five times slower than those in C++, but they are so much safer" won't fly. Besides we have no real basis for saying that they are safer, we don't know in practice that all this checking will actually be helpful, we are just guessing that this is the case without real data. We don't expect critical applications to use the containers at all. Far too much difficult stuff. Instead they will typically use our formal bounded containers which are very usable, but much simplified AND much safer, because they are much more friendly to certification and formal proof. One thing that would have helped is to design all the safety stuff so that it was in the form of preconditions and postconditions, which could be easily suppressed. *************************************************************** From: Brad Moore Sent: Monday, February 10, 2014 11:38 AM >> I would say that not everyone cares about performance, when using >> containers.Having safety as the default seems like the right choice >> to me for Ada. > >Ada is supposed to be about getting safety WITHOUT paying a huge >performance hit. We are finding a lot of users who are very >disappointed to find out that the containers are > >a) SO much worse than C++ I could see performance as being the default, but I can also imagine that there are projects that would want to have a way to turn on the extra checking, when performance is not an issue, and the possibility of tampering hasn't been completely ruled out. *************************************************************** From: Gary Dismukes Sent: Monday, February 10, 2014 1:18 PM > > I see, but I would have thought that something could be done however. > > Maybe if the suppression is globally specified as a configuration > > pragma, the tampering could be removed by the compiler as dead code, > > similar to when a constant boolean expression is encountered in GNAT? > > How can that help, the run-time does not get recompiled in response to > setting a configuration pragma! In fact it does effectively get recompiled, since these are generics getting expanded in the user's code. So in principle a configuration pragma could be used to control this, though would still be a little tricky to control tampering checks this way. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 1:26 PM Surely we don't make a copy of the ENTIRE body of the generic, sounds horrible not to be sharing code as much as possible, certainly the interface does not demand such behavior. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 2:10 PM > BTW, while on the subject of tampering checks, we are becoming more > worried that the design of the containers in Ada is fundamentally > flawed. It is a serious embarrassment, one noted by several of our > customers, that the performance of the Ada containers is way less > efficient than the C++ containers, and we fear that a lot of this > inefficiency is mandated by the Ada design. I can believe this, but I find it hard to believe that tampering (alone) is the cause of this inefficiency. The tampering *check* should be a simple comparison against an integer value, which shouldn't add significant overhead compared to the "real" operation in most cases. I'd expect dangling cursor checks (if you make them) to be much more expensive (and a drag on performance). But those are optional. It would be nice if someone could quantify the difference between the Ada and C++ libraries and pinpoint the exact issues. My guess is that you'd still see similar problems even with the tampering check eliminated. (I'd do this myself, but I don't know C++ well enough to make an accurate comparison.) > One thing that would have helped is to design all the safety stuff so > that it was in the form of preconditions and postconditions, which > could be easily suppressed. I've suggested that before (including on Friday). It's still possible, of course, it would be compatible to do so (we couldn't use predicates, but preconditions would work). (But it would be a lot of work for the Standard, and some for implementers.) Of course, we couldn't have done this for Ada 2005, as we didn't have preconditions then. In particular, if we added the routine Is_Tampering_with_Cursors (Container : in Vector) return Boolean, then the bounded vector Insert could be: procedure Insert (Container : in out Vector; Before : in Extended_Index; New_Item : in Vector) with Pre => (if Container.Is_Tampering_with_Cursors then raise Program_Error with "Tampering check") and then (if Before not in Container.First_Index .. Container.Last_Index + 1 then raise Constraint_Error) and then (if Container.Length = Container.Capacity then raise Capacity_Error), Post => (Container.Is_Tampering_with_Cursors'Old = Container.Is_Tampering_with_Cursors) and Container.Length'Old + 1 = Container.Length); The postcondition is intended to show provers that a call of Insert doesn't change the tampering state. Having these as preconditions and postconditions would allow easy suppression of the checks (and also would allow the compiler to combine and/or eliminate them, so it wouldn't be as necessary to suppress them). This seems to me to be the best way to fix the performance problem caused by the checking. But that presumes that we're sure that the performance problem is caused solely by the checking. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 2:15 PM > This seems to me to be the best way to fix the performance problem > caused by the checking. But that presumes that we're sure that the > performance problem is caused solely by the checking. The main issue for performance is in loops, and I believe Ed has some insight into the issues there, Ed? *************************************************************** From: Ed Schonberg Sent: Monday, February 10, 2014 2:58 PM >> BTW, while on the subject of tampering checks, we are becoming more >> worried that the design of the containers in Ada is fundamentally >> flawed. It is a serious embarrassment, one noted by several of our >> customers, that the performance of the Ada containers is way less >> efficient than the C++ containers, and we fear that a lot of this >> inefficiency is mandated by the Ada design. > > I can believe this, but I find it hard to believe that tampering > (alone) is the cause of this inefficiency. The tampering *check* > should be a simple comparison against an integer value, which > shouldn't add significant overhead compared to the "real" operation in most > cases. the cost is not the comparison, but the setting and reseting of the tampering counter. Its management requires that references be somehow controlled, so in an loop you are forced to create. initialize, and finalize an object with a controlled component. This makes simple loops (add the elements of a vector, say) more than an order of magnitude slower that the naive array code. The finalization machinery cannot be inlined, so there is no hope for the code generator to optimize any of it. There are possible front-end optimizations for some simple loops, and we will experiment with them in coming weeks, but in general the controlled overhead is the killer. If there are better suggestions on how to manage tampering bits in the presence of arbitrary references that may be floating around, I’d be delighted to hear it. *************************************************************** From: Ed Schonberg Sent: Monday, February 10, 2014 3:00 PM > Surely we don't make a copy of the ENTIRE body of the generic, sounds > horrible not to be sharing code as much as possible, certainly the > interface does not demand such behavior. Surely you jest. There is very little that can be shared between different kinds of containers. *************************************************************** From: Gary Dismukes Sent: Monday, February 10, 2014 3:09 PM And what is shared is either unrelated to tampering checks or is itself generic. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 3:06 PM Perhaps the idea of a completely separate set of containers, which completely remove the tampering checks, and a configuration pragma saying whether tampering checks are required to choose which set of containers are needed. Then probably for GNAT, we would default to the efficient set, and have a compiler switch for strictly conforming behavior. The configuration pragma could be pragma Container_Tampering_Checks (On | Off); with a requirement that this be set consistently for all units withing containers. Or perhaps, since these are all generic, it would work to instantiate two separate versions depending on the setting of Tampering_Check??? *************************************************************** From: Tucker Taft Sent: Monday, February 10, 2014 3:09 PM >> Surely we don't make a copy of the ENTIRE body of the generic, sounds >> horrible not to be sharing code as much as possible, certainly the >> interface does not demand such behavior. > > Surely you jest. There is very little that can be shared between different > kinds of containers. I think Robert meant that you might be able to share code between different instantiations of the same generic, by carving out some of the code into a non-generic package. I think we already do that for the unbounded containers. It might be harder to do that with the bounded containers. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 3:11 PM > Surely you jest. There is very little that can be shared between different > kinds of containers. I do not jest, I am talking about sharing code between multiple instantiations of the same container, as we do for Text_IO or Bounded_String. We minimize the amount of generic code in such packages, so that e.g. multiple instantiations of Bounded_Strings for different lengths share 95% of the code between them (they are actually uses of a Superbounded package that keeps the max length around). Similarly, 95% of the work of the generic subpackages in Text_IO is done by non-generic helper routines. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 3:22 PM > the cost is not the comparison, but the setting and reseting of the > tampering counter. Its management requires that references be somehow > controlled, so in an loop you are forced to create. initialize, and > finalize an object with a controlled component. This makes simple > loops (add the elements of a vector, say) more than an order of > magnitude slower that the naive array code. The finalization > machinery cannot be inlined, so there is no hope for the code > generator to optimize any of it. There are possible front-end > optimizations for some simple loops, and we will experiment with them > in coming weeks, but in general the controlled overhead is the killer. > If there are better suggestions on how to manage tampering bits in the > presence of arbitrary references that may be floating around, I'd be > delighted to hear it. Thanks, I was starting to think about that since Robert's message pointed me the right way. It's especially annoying because there isn't any sensible way to suppress such overhead (it's not with the check per-se). I would have expected worse problems with Reference/Constant_Reference, but perhaps they're not used as much in critical situations. Anyway, I think it is possible to optimize the overhead away in simple cases. I know I hoped that the containers would get used enough to make such optimizations worthwhile. But I don't see a general way to do that (it would be specific to the containers), and I admit I'm not sure the substantial efforts required would help enough. Specifically, if the compiler "knows" that it is dealing with a controlled object used solely for a tampering check, then it can determine if there are any possible occurrences of a tampering check within the scope of that object. (That necessarily would have to be pretty conservative, probably would assume that any call to a non-container routine contains tampering.) If there are no tampering checks in that scope, then the controlled object itself (setup and removal) can be completely removed from the program, which of course would completely eliminate the overhead. (This probably would require in-lining of the setup and finalization of the object.) I would expect that the majority of Reference/Constant_Reference calls would meet these requirements and could have the overhead removed. It would be rarer for loops, but then again loops that have lots of contained calls will be less sensitive to the loop overhead (it would be a much smaller part of the whole). This isn't ideal because it requires knowledge about the containers themselves. Perhaps if the tampering check was a precondition, it would require a bit less magic, but you'd also want to know about routines that could not possibly have a tampering check (other container routines that are pure reads, in particular). [Because blocking the optimization by *any* call would leave few loops that could be optimized.] I can imagine defining a set of [implementation-defined] aspects for the purpose, but of course that increases the work needed. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 3:28 PM > Specifically, if the compiler "knows" that it is dealing with a > controlled object used solely for a tampering check, then it can > determine if there are any possible occurrences of a tampering check > within the scope of that object. (That necessarily would have to be > pretty conservative, probably would assume that any call to a > non-container routine contains tampering.) If there are no tampering > checks in that scope, then the controlled object itself (setup and > removal) can be completely removed from the program, which of course > would completely eliminate the overhead. (This probably would require > in-lining of the setup and finalization of the object.) I don't see this kind of highly specialized flow analysis as being even vaguely practical, at least in our environment. It would require a complete extra complicated pass in the compiler, and I can't see that happening. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 3:36 PM ... > Specifically, if the compiler "knows" that it is dealing with a > controlled object used solely for a tampering check, then it can > determine if there are any possible occurrences of a tampering check > within the scope of that object. (That necessarily would have to be > pretty conservative, probably would assume that any call to a > non-container routine contains tampering.) If there are no tampering > checks in that scope, then the controlled object itself (setup and > removal) can be completely removed from the program, which of course > would completely eliminate the overhead. (This probably would require > in-lining of the setup and finalization of the object.) Another way to do this would be to have unsafe versions of the routines somewhere (which don't create the controlled object) and switch to them anytime that the scope of the object doesn't contain any possible tampering operations. More generally, since the controlled object exists solely for the tampering check, it isn't needed at all if it is known that there isn't any possible tampering in the actual loop body (or scope of Reference/Constant_Reference). For simple cases, this is determinable by the compiler, and then some method has to be used to ensure that no useless controlled object is created and managed. *************************************************************** From: Robert Dewar Sent: Monday, February 10, 2014 3:45 PM > More generally, since the controlled object exists solely for the > tampering check, it isn't needed at all if it is known that there > isn't any possible tampering in the actual loop body (or scope of > Reference/Constant_Reference). For simple cases, this is determinable > by the compiler, and then some method has to be used to ensure that no > useless controlled object is created and managed. It's really uncomfortable to have the front end of the compiler have to know this much about containers. I think I prefer the approach where you just indicate at instantiation time whether or not you want tampering checks. Note that another advantage of having the tampering checks be stated as preconditions and the status stated as pre/post conditions is that you have a chance of verifying formally that no tampering is possible. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 3:55 PM > I don't see this kind of highly specialized flow analysis as being > even vaguely practical, at least in our environment. It would require > a complete extra complicated pass in the compiler, and I can't see > that happening. Yeah, it's probably too hard to do for loops. I have to wonder, though, if something like it would be worth it for Reference/Constant_Reference, which probably are a lot of the overhead in many cases. Most of the time, their lifetime is very short (within a single expression), and there probably is an expression pass that such an optimization could be added to. For instance, in Sum := 0; for C in Container.Iterator loop -- (1) Sum := Sum + Container(C).Component; -- (2) end loop; Let's assume that there are 100 elements in Container. In that case, the tampering loop setup at (1) is executed once; the tampering setup for Constant_Reference (implicit in 2) happens 100 times. Moreover, that second, very local object gets finalized as soon as the assignment statement is completed (it might even be sooner than that). So that is very localized, it's clear that there is no tampering check (because there is no call of any kind) in the scope of that tampering check. And it's clear that removing (2) would save 100 times the overhead that removing (1) would. Of course, I haven't tried this in practice, so I don't know how hard it would really be. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 4:00 PM ... > Note that another advantage of having the tampering checks be stated > as preconditions and the status stated as pre/post conditions is that > you have a chance of verifying formally that no tampering is possible. I agree with this in any case, that's one reason I've been interested in doing this for quite a while. But I don't think it would help much for the purpose of eliminating the setup cost (other than a SPARK-like environment), because real code has just too many external subprogram calls to be able to tell. Instrumenting them all with no tampering pre/postconditions is likely to be prohibitive. *************************************************************** From: Ed Schonberg Sent: Monday, February 10, 2014 4:08 PM > And it's clear that removing (2) would save 100 times the overhead > that removing (1) would. > > Of course, I haven't tried this in practice, so I don't know how hard > it would really be. this is the kind of transformation i have been experimenting with. There are cases where the expansion of the generalized indexing following by an explicit dereference could be replaced with a call to Element directly, which does not involve the creation of a reference, and therefore generates no controlled calls. The question is to determine precisely when the body of the loop makes this transformation safe. *************************************************************** From: Randy Brukardt Sent: Monday, February 10, 2014 4:24 PM Ah, great minds think alike! :-) Unless the generalized indexing is used in a renames or as an actual parameter, I would expect that the determination whether tampering could occur would be purely local to the subexpression in question. So that seems practical. I probably would look into the idea of having a "unsafe" Reference/Constant_Reference routine somehow hidden in the container, to use in place of the standard call. The problem with Element is that it logically copies the element, while Reference/Constant_Reference is a pointer to it. So there are other considerations with replacing with Element that don't come up if an unsafe version (without the controlled object) of Reference/Constant_Reference is available. (It's also possible that copying a large element is more expensive than the tampering setup. That can't happen for a no-tampering Reference/Constant_Reference.) I suppose it makes sense to use an Element replacement as a proof-of-concept, as no funny business in the containers is needed. If it looks promising, then try a container modification to go further. *************************************************************** From: Randy Brukardt Sent: Friday, February 14, 2014 12:55 PM At the risk of restarting a thread which has died down, I have some additional thoughts on this issue today. I was thinking a bit about this while getting ready for work, and I was wondering if the bounded containers are actually different than the other containers in terms of needing some tampering checks. This thought inspired me to go back and look at the original problems that inspired the checks. This note (essentially an LSN) explains what I found out. ---- Executive summary: The tampering with elements checks associated with Reference/Constant_Reference for bounded containers are probably not worth their overhead, as most of the problems that they're intended to prevent aren't possible if the implementation advice is followed. The checks do prevent some problems, however. The tampering with elements checks associated with Reference/Constant_Reference could be eliminated with little loss of safety if some additional constraints are placed on the implementation of the containers. For a bounded container, these constraints are already part of the implementation advice, so the effect would be minimal (additional advice would reduce risk even further). For an unbounded container, these constraints could be lived with, but would make some likely implementation approaches impossible, especially for vectors. For indefinite containers, the constraints would be impossible. The tampering with elements checks associated with the Query_Element/Update_Element callbacks could be eliminated with the same constraints as mentioned above. There would be a small additional loss of safety for Update_Element, mainly for elements that could be passed by-copy. The tampering with cursors checks associated with iterators (both the callback form and the for loop form) can't be eliminated without a significant loss of safety. Eliminating tampering checks from some kinds of containers and some operations (but not other containers and operations) would reduce consistency between the containers, but that could only be a problem when moving from a container without such checks to one that has them, and even then a problem seems unlikely. ---- Let's start with some background. The tampering checks were originated to ensure that call-back iterators (and now for loops) did not have to be constructed defensively. Specifically, inserting or deleting an element near the current one in an iterator can cause trouble, as the iterator may have already saved a cursor (pointer) to the "next" value. If that next value was to change by some operation, the iterator could malfunction (possibly missing an element, or visiting an element twice, or worst of all, visiting some memory that *used* to be an element but has since been returned to the system). The cost of these check was thought to be acceptable, because the setup only happens once per loop, and the checks are cheap (an integer compare, typically). Moreover, the setup is cheap for the call-back iterators, as the body of the iterator can clear the tampering flag when it completes its actions. Later, we ran into some similar issues with Query_Element/Update_Element, and we decided to use the already defined tampering mechanism to handle them. Specifically, if the element that Query_Element/Update_Element is currently working on is deleted or replaced, then if the parameter was passed by reference, it may no longer reference allocated memory (for container implementations that allocate elements individually, especially likely for the indefinite containers). For Update_Element, there is also the potential for data loss -- if the element is passed by copy, any modifications made to it via operations calls from Update_Element (rather than to the parameter) will be lost when Update_Element returns and copies back the parameter to the element. The tampering checks for elements weren't restricted to the element being operated on specifically, for two reasons. First, tracking the element in question would make the checks significantly more expensive, especially as several nested operations could be used to operate on a number of elements at once. Secondly, some reference container designs (especially for vectors) move elements around when new ones are inserted or deleted. That means that element might change if something is inserted in front of it, with all of the same issues happening. In order to give implementers maximum flexibility for implementations, we simply banned any insertions or deletions, which also has the effect of making the check relatively simple. For Ada 2012, we have new operations that also use these checks. The iterators and the associated for loop syntax has exactly the same need for tampering checks as the Ada 2005 call-back iterators. The only difference is that clearing the tampering state is harder as there is no easy place to put that code. The usual solution is to use a controlled object, but of course that increases the overhead of the setup and removal of the tampering state. Again, this isn't too significant in most uses, as it occurs only once per loop, and the other overhead of setting up iteration can also be fairly significant. Ada 2012 also adds Reference/Constant_Reference. The design of these functions uses accessibility checks on the container (via it being an explicitly aliased parameter) and on the result to ensure that the returned access value cannot outlive the container. This eliminates the majority of dangling pointer issues. However, we still have the same problem as with Query_Element/Update_Element, in that a replacement or deletion of the element could leave the pointer accessing nothing. That might appear to be hard to do (given the generally short life of the result), but parameter passing and renames both can extend that lifetime arbitrarily. There is an example of this causing erroneous execution in AI05-0212-1. Thus, we determined that a tampering check is needed here, too. It's implementable using a controlled object that is finalized at the end of the lifetime of the access value. When the object is finalized, the tampering state is cleared. The problem, of course, is that this setup and tear-down of the tampering state is rather expensive, as it involves creating and destroying a controlled object. In addition, this is likely to be very frequent in Ada code, especially that using the new indexing syntax. Finally, a lot of these cases cannot have any tampering operations occur during their very short lifetime, so the check is just arbitrary overhead. In a typical loop, there will be one or more indexed accesses per iteration. So while the for loop will have one tampering setup/teardown per execution of the entire loop statement, similar overhead will be incurred per iteration by Reference/Constant_Reference. Thus the Reference/Constant_Reference overhead is likely to be several orders of magnitude more important than the loop overhead. If we change anything, this is the most important thing to change. --- We wanted the containers to be as similar as possible. Thus, we used the same tampering checks on all of the containers. However, the *need* for the tampering checks is not the same for each kind of container. In particular, the indefinite containers have to, by definition, allocate each element separately (as the size and shape of the element is not known until it is inserted). These containers also will have to delete and then reinsert an element that is replaced (at least in general), as again the size and shape could change. In these cases, the element memory will most likely be returned to the storage pool (often the standard storage pool) and reused (maybe by something completely unrelated). Later references to that memory will cause havoc. OTOH, the bounded containers will never return memory to a storage pool; the maximum size is fixed throughout the life of the container. Thus an element will continue to exist during the entire life of the container, and a reference to it will continue to point somewhere so long as the container itself hasn't been destroyed. As you might guess, the situation with the unbounded containers is somewhere in between. Some containers implementations might move an element when a container is expanded to allow more elements. For instance, the typical vector implementation expands its capacity by allocating a new, larger data area, copying all of the existing elements to the new data area, and then freeing the old data area. (Vectors don't have to work this way, a point we'll come back to later.) In such an implementation, an element insertion has a non-zero risk of making any existing references dangling. (This is an important reason for the tampering check covering any insertions or deletions, not just of the element itself.) Another interesting difference is between Update_Element and Reference. The data loss situation that can occur for elements passed by copy in Update_Element can't occur for Reference, because all access to the element is via the reference -- essentially by-reference. This means that for Reference and Constant_Reference, the only concern is about elements being inserted/deleted/replaced. --- There are two levels of the concern about elements being inserted/deleted/replaced for functions Reference and Constant_Reference. The primary concern is any case where the memory of the element could be deallocated and potentially reused, not just for another element of the same type, but possibly in some unrelated data structure. This is the classic erroneous execution problem, and it is well-known to be a major cause of security bugs and other pestilence. Solutions that eliminate these problems are highly desired, and we're certainly willing to pay some overhead to eliminate this. The secondary concern are cases where the element is deleted and the memory is reused for another element. (A closely related concern, which only happens for vectors, is cases where the insertion or deletion of an element causes the referenced element to move such that the reference no longer points at the same element.) In these cases, the reference still points at a valid element, but it's the *wrong* element. Such cases certainly can cause problems (say by writing components of the wrong element), but they can't cause erroneous execution by themselves. Moreover, these cases are essentially the same as mistakes that can happen with a fixed array of elements. If there is a way to cause erroneous execution from such a case, it's also possible to create the same erroneous execution from similar misuse of array elements (such examples usually involve renaming or parameter passing, both of which can be done with array elements just like container elements). As such, we don't want to have any extra cost in trapping these errors, but if we can detect them for free, that would be good. --- If you've still awake at this point, you're probably wondering where I'm going with all this. The key here is that bounded containers are not supposed to allocate or deallocate elements on the fly. They're supposed to be all allocated when the container is created. (There is implementation advice to this effect for each bounded container.) Thus the primary concern about functions Reference and Constant_Reference is impossible for a bounded container: the returned reference can only become dangling if the entire container is destroyed while the reference exists. (This can only happen if the container is explicitly deallocated with Unchecked_Deallocation or the similar subpool facilities while the reference exists. Tampering checks do not provide any help for this extreme circumstance.) To reiterate, for a bounded container (only), dereferencing the result of Reference cannot cause erroneous execution unless the container is itself deallocated. Otherwise, it will always continue to point to the memory of an element (it just might not be the right element). Moreover, for containers other than vectors, implementations can further reduce trouble this by waiting to reallocate elements as long as possible. That is, when inserting new elements, a previously used element should be used only if no other elements are available, and then the least recently used element should be reused. That makes it much more likely that any dangling references point at deleted elements (to which modifications are not going to cause any problems by themselves) as opposed to pointing at some other in-use element (to which modifications are likely to cause problems). Note that one can get erroneous execution in such cases by changing discriminants of known-to-be-constrained objects (such as formal parameters). But this is possible without involving any containers -- there is nothing new with this. --- As such, the tampering check on Reference and especially Constant_Reference for bounded containers is not doing a lot of good. For containers with individual nodes (all but vectors), we can give implementation advice to use least-recently used allocation of nodes. For an implementation that follows such advice, the reuse of nodes while a reference exists is unlikely (it can happen of course if the container is near capacity), so the danger of modifying the wrong element is minimal. The danger mainly comes from data loss, where code continues to update an element that has been deleted. It's probably not worth the overhead for such cases. That's especially true for Constant_Reference (where no updating is allowed anyway). The case with the bounded vector is not as clear-cut. Deleting or inserting an element usually causes the others to "slide" over, invalidating all cursors and references. These now all point at the wrong element. Thus, while a reference will still access data, it will always be the wrong data. There is an argument that this is not significant, as the same thing can happen with a fixed array. That argument however seems to mainly be that fixed arrays are buggy, so bounded vectors should also be buggy. :-) As such, it is not only reasonable to suppress the tampering check for Reference and Constant_Reference for bounded containers, but for most containers, it may be sensible to eliminate it altogether. That would make bounded containers slightly less safe than the unbounded form, but they also would be considerably faster. --- If we were to make some or all of the bounded containers different by eliminating their tampering check for Reference/Constant_Reference, there would clearly be an interoperability concern. Moving from a working bounded container to an unbounded one could cause some failures from tampering. (Going in the other direction would not cause any problems, of course.) It's hard to say how significant this is; most Reference/Constant_Reference calls are very-shortlived and couldn't tamper in any way. But there probably would be some longer-lived ones (via renaming or parameter passing) that could cause issues. --- Could we go further? Yes, but there are downsides. First, consider Update_Element. It has the additional data loss issue of by-copy elements. Moreover, it's tampering state setup is cheaper than Reference as no controlled object is needed. So a bit less safety in exchange for much less overhead gain (and in a lesser-used routine) is probably not worth a change. Query_Element is essentially the same as Constant_Reference, so it could be eliminated, but again there this isn't used much and the overhead is much less than Constant_Reference. We also could remove the tampering checks in the same way for the Unbounded forms if we were willing to require that implementations refrain from deallocating (as opposed to saving and reusing) elements when they are deleted/inserted/replaced. The problem with this is that it would prevent the contiguous implementation of vectors; an implementation would have to be chunked so that a capacity expansion did not move any existing elements to new memory. That's probably a too much of an imposition. --- On the other side of the tampering check, we could make the tampering checks (along with some of the other checks for containers) an explicit precondition on the containers routines. This is compatible as renaming/'Access does not require matching preconditions. This would allow dropping some of the English text in the RM, as a pleasant side-effect. (A lot of that text is really messy as it is trying to write something better described in pseudo-code in English.) That might not help the performance problem too much, at least not directly, but it would allow a compiler to remove redundant tampering checks (once a routine has made the check, it doesn't need to be repeated on future calls unless something that might change the tampering state intervenes), and it also would allow a compiler to know when no tampering failure is possible (which could be used to eliminate tampering overhead, particularly for Reference and Constant_Reference). --- Concluding. When I started writing this, I was pretty sure that the tampering check on Reference/Constant_Reference for bounded containers had no purpose at all. I now realize that I was wrong about that, as it does prevent reading or modifying the wrong element after a tampering operation. However, it is unlikely that such reading or modifying would cause erroneous execution (more specifically, the reading or writing of memory that does not currently belong to the container); it could only do so for discriminated records that already have such problems in many other non-container cases. Moreover, with care, most containers could ensure that such reading or modifying is only of an unused element, which is even less likely to cause problems. (Not for the bounded vector, unfortunately.) The main negative here is making the bounded containers more different (and somewhat less safe) than the other kinds of containers. I'm not sure how important we think having all of the containers be as similar as possible is. I do think we need to talk about this in a meeting setting, and perhaps I need to write up some examples of the cases that would slip through without a tampering check for bounded containers. So we probably need to make an AI for further consideration. *************************************************************** From: Geert Bosch Sent: Friday, February 14, 2014 1:22 PM (Let me preface this with noting that I read Randy's excellent write up from this morning, but this is not a direct reply.) > the cost is not the comparison, but the setting and reseting of the > tampering counter. Its management requires that references be somehow > controlled, so in an loop you are forced to create. initialize, and finalize > an object with a controlled component. This makes simple loops (add the > elements of a vector, say) more than an order of magnitude slower that the > naive array code. It seems clear to me that anything involving controlled types for the cursor is going to be unusable. In particular, it is a really bad idea to require that creating a reference to a container must modify that container. Argument 1: Multiple tasks must be able to concurrently read the same thing =========================================================================== I shouldn't have to know whether some type is implemented with a container or otherwise to be able to concurrently read objects of that type from multiple tasks. As it is currently in GNAT, referencing a container requires updating a reference count in the container and the update is not protected and will cause erroneous execution if done concurrently from multiple tasks. Argument 2: References are fleeting, but have an unclear life time ================================================================== As references often are very local and live only for a single use (as in indexing), they should not require updating the container, which typically is a far more global data structure. Writing global data does not only require more care (see above, consider locking), especially on multiprocessors writing to non-local memory can be far slower. Along the jest of Randy's mail, we don't really need tampering checks all that much. What do we care about? What are our requirements? I see one big one. Requirement: Avoid erroneous execution ====================================== We don't want a program that attempts to update a container while holding references to it cause erroneous execution when using the reference after the update. Current situation for GNAT ========================== As shown above, today tampering checks not only slow things down, they CAUSE erroneous execution in multitasking programs concurrently reading a container, as concurrent references cause concurrent writes. Cause of the problem ==================== The problem is that we require the tampering checks on the operations modifying the container. This in turn requires updates to *know* about references, resulting in all issues above. Proposed solution ================= Instead of requiring the update to fail the tampering check, allow subsequent use of the now-stale references to fail the tampering check. A conceptual implementation would be as follows: - any operations that would currently require a tampering check will instead increase the version number (modification counter) of the container - any reference (such as a cursor) contains the version number of the container at the time the reference was created - any dereference checks the container for its version number, and raises Program_Error if it detects tampering Benefits ======== 1. References only need to read the container, so are fast. 2. Concurrent reads of containers are safe, even when iterating 3. It is OK to hold a reference and then perform an update while still holding the reference, as long as the reference is not used subsequently. 4. This approach could be easily extended to allow efficient concurrent updates, or detect concurrent usage, with only locking overhead for writes. My hope is that we can slightly rework the concept of tampering checks, so that we can get containers to be efficient. *************************************************************** From: Randy Brukardt Sent: Friday, February 14, 2014 2:43 PM ... > It seems clear to me that anything involving controlled types for the > cursor is going to be unusable. In particular, it is a really bad idea > to require that creating a reference to a container must modify that > container. You're confusing cursors and references here. There are no (mandated) tampering checks for cursors. Your counter solution for cursors is a good one for detecting cursor problems. My container implementations uses a similar solution for that, although mine uses per-element rather than per-container ids. (That solution was designed in 2006 or 2007; this is not a new idea.) A reference, however, is an access discriminant. It's lifetime is strictly known to be that of the enclosing object, and the (usually static) accessibility checks required ensure that it cannot be used after that lifetime without heroic efforts. We also (usually statically) ensure that the container lives as long as the reference. The tampering check is used to ensure that the *element* lives as long as the reference. [Note that tampering is only in effect during the (usually short) lifetime of the reference; it's not related in any way to the cursor.] Without that, you can get erroneous execution from a dangling pointer -- and that's one of the worst kinds of erroneousness as it means potentially writing someone else's memory. It's not worthwhile to detect that after the fact, because once some other data structure is corrupt, it will stay that way. It's too late to recover. Your proposal: > - any dereference checks the container for its version number, and raises > Program_Error if it detects tampering makes no sense for references, because they are just a normal access-to-object dereference. Thus the element modification takes place through a raw pointer. There is no opportunity to communicate that modification back to the container. I suppose that one could *assume-the-worst* that all references are modifications, but that does not help because you find out too late: once you've overwritten random memory, the program is unrecoverable. You'd usually know that the program is corrupt (unless of course the corruption was such that it made the counters look OK), but all you can do then is terminate the program. One would not want to use such a container in a rocket controller! > As shown above, today tampering checks not only slow things down, they CAUSE erroneous execution > in multitasking programs concurrently reading a container, as concurrent references cause > concurrent writes. Right, but no one is required to use a reference to read an element. Calling function Element involves no tampering check, the "problem" is that it requires a copy of the element. Ergo, if you want concurrent reads, just use Element rather than Constant_Reference. Of course, Ada does not guarantee concurrent reads in any case in the standard library. Of course, we could add such a guarantee (presumably for a very limited set of container operations). I suspect that it wouldn't be too hard to make a read guarantee work for the bounded containers, but for the much more general indefinite containers (the big advance, IMHO), I suspect that it would be problematical. One reason being that we have to have tampering checks to prevent erroneous execution of references there (as any replacement of an element causes reallocation), whereas their value for bounded containers is much more doubtful. (As described in detail in my previous message.) I'm somewhat dubious of the value of supporting concurrent reads (only), you're always going to need some sort of locking to handle the modifications, and it isn't going to add any additional overhead to use that for reads as well. (My spam filter has this problem, blacklists and whitelists and other data are rarely modified compared to the runtime of the filter, but one still has to get a lock before reading from them in order to ensure that the data isn't in the process of being updated.) What is the use case that you are considering?? *************************************************************** From: Tucker Taft Sent: Friday, February 14, 2014 3:37 PM I have had trouble following all of the ins and outs of this thread. But I definitely agree with this idea, though Randy implies it may be solving a different problem. The container library Bob implemented many years ago for our static analysis tool (CodePeer) uses a very similar approach, where you have a "modification count" or equivalent, and checks are performed that this modification count doesn't change, to detect the equivalent of tampering. I also wonder whether references might be short-lived enough that we could do something at compile-time to improve performance. In partial answer to something Randy mentioned, I think it would be reasonable to bump a "modification count" whenever you return a reference that supports update, even before any actual modification takes place. We use that approach for a software virtual-memory mechanism, also in our static analysis tool. *************************************************************** From: Bob Duff Sent: Friday, February 14, 2014 4:21 PM > I have had trouble following all of the ins and outs of this thread. I have not read all of it. I think the way to make containers fast is for someone (AdaCore?) to hack on them, and do measurements and profiling. Perhaps then language change suggestions might be in order. > But I definitely agree with this idea, though Randy implies it may be > solving a different problem. The container library Bob implemented > many years ago for our static analysis tool (CodePeer) uses a very > similar approach, where you have a "modification count" or equivalent, > and checks are performed that this modification count doesn't change, > to detect the equivalent of tampering. That's not how I remember it. As I recall, for something like Vectors, there were two types, one growable (call it G), and one fixed length (call it F). You create a G object, and append things onto it. You then call Freeze, which takes a G, and returns an F containing the same sequence of items. You now process the F. Freeze is implemented so it didn't have to copy the data. Once you call Freeze, the G object is destroyed, and any attempt to touch it raises an exception. It is often used like this: function Build_F_Obj(...) return F is G_Obj: G; -- [*] begin ...build G_Obj... return Freeze (G_Obj); end Build_F_Obj; so there's little opportunity for tripping over that exception, because G_Obj vanishes right after the Freeze. And once you call Freeze, you've got an F, whose length cannot change. So there's no need for tampering checks on F. This supports programs where the first phase builds up the data structure, and then the second phase processes it without modifying it (or, at least, without changing its size/shape). Pretty common. [*] As I recall, G is limited, and F is nonlimited. So at [*], we default init to empty. Today, I would use a build-in-place function Empty, and avoid use of defaults. That was many years ago, so I might be misremembering, and someone might have changed it in the meantime. *************************************************************** From: Randy Brukardt Sent: Friday, February 14, 2014 4:28 PM > I have had trouble following all of the ins and outs of this thread. That doesn't surprise me, there's a lot of misinformation out there. And I'm not good at explaining things concisely -- I hope that you manage to do that. :-) > But I definitely agree with this idea, though Randy implies it may be > solving a different problem. Yes, it's solving a different problem. Read the "problem" part of my message for an explanation of the problems that tampering is intended to solve. Geert's solution is really about detecting "invalid" cursors, which the containers have never required. We didn't require that because solutions like Geert's don't provide 100% detection, which is necessary in order to meet a requirement, or they have a lot of false positives. The hope was that implementations would implement a cheaper 95% solution, but one also has to be careful not to introduce too many false positives. Tampering of elements is mainly about preventing erroneous execution by reading or writing a no longer existing element -- either one that was passed as a parameter to the call-back of Query_Element or Update_Element, or one that we have a reference to from Reference/Constant_Reference. I've always considered these more dangerous than the cursor cases, because a container implementation can decide just how much erroneousness from invalid cursors it was willing to tolerate (which is of course a trade-off with performance). There is no possibility of detecting such problems in the reference or call-back cases, at least without a large amount of complication (because no false positives would be tolerated, just as false positives are not tolerated in the detection of ). The tampering check gives us well-defined bounds on what false positives are tolerated. It does make sense to allow an implementation to "suppress" the tampering check somehow, if it in fact would prefer maximum performance, erroneousness be damned. That would be consistent with the handling of the cursor cases, where an implementation can allow erroneousness for maximum performance if desired. (My understanding is that there is a debug implementation of the containers for GNAT that detects invalid cursors and a performance implementation that does not. It makes sense to treat tampering with elements the same way, because the problem is fairly similar.) *************************************************************** From: Geert Bosch Sent: Friday, February 14, 2014 11:56 PM > ... >> It seems clear to me that anything involving controlled types for the >> cursor is going to be unusable. In particular, it is a really bad >> idea to require that creating a reference to a container must modify >> that container. > > You're confusing cursors and references here. There are no (mandated) > tampering checks for cursors. I'm referring to this (A.18.2(97.1/3)): > When tampering with cursors is prohibited for a particular vector > object V, Program_Error is propagated by a call of any > language-defined subprogram that is defined to tamper with the cursors > of V, leaving V unmodified. Isn't this a mandated tampering check for cursors? > Your counter solution for cursors is a good one for detecting cursor > problems. My container implementations uses a similar solution for > that, although mine uses per-element rather than per-container ids. > (That solution was designed in 2006 or 2007; this is not a new idea.) The purpose is not to invent new ideas, but to fix the horrible inefficiencies (and lack of safety) that we have today. Today, a cursor has to be controlled as the container has to know about it in order to raise exceptions on operations that are defined to tamper with cursors. Containers having to know about references to them, whether cursors or otherwise, is the root of all evil. > A reference, however, is an access discriminant. It's lifetime is > strictly known to be that of the enclosing object, and the (usually > static) accessibility checks required ensure that it cannot be used > after that lifetime without heroic efforts. We also (usually > statically) ensure that the container lives as long as the reference. Right, that is helpful. Unfortunately cursors don't have that property, but there are ways to solve that with an extra level of indirection. > The tampering check is used to ensure that the *element* lives as long > as the reference. [Note that tampering is only in effect during the > (usually > short) lifetime of the reference; it's not related in any way to the > cursor.] Without that, you can get erroneous execution from a dangling > pointer -- and that's one of the worst kinds of erroneousness as it > means potentially writing someone else's memory. It's not worthwhile > to detect that after the fact, because once some other data structure > is corrupt, it will stay that way. It's too late to recover. For simplicity, I only recognize a single kind of erroneousness, and it always is the worst kind, and it always is too late to recover. Fortunately, access types are abstract in Ada. We can invent whatever implementation we want for them, including ones that look like: type Version_Number_Access is access Version_Number; type Element_Access is record Address : System.Address; Reference_Version : Version_Number; Current_Version : Version_Number_Access; end record; The compiler can implement the dereference of this fat pointer as: function Dereference (Ptr : Element_Access) return Element is begin if Ptr.Current_Version.all /= Ptr.Reference_Version then raise Program_Error with "failed tampering check"; end if; declare Item : Element; for Item'Address use Ptr.Address; begin return Element; -- return-by-reference end; end Dereference; > Your proposal: >> - any dereference checks the container for its version number, and >> raises Program_Error >> if it detects tampering > > makes no sense for references, because they are just a normal > access-to-object dereference. Thus the element modification takes > place through a raw pointer. There is no opportunity to communicate > that modification back to the container. AFAIK, we don't have to. Tampering with elements means replacing elements, not modifying them. > I suppose that one could > *assume-the-worst* that all references are modifications, but that > does not help because you find out too late: once you've overwritten > random memory, the program is unrecoverable. You'd usually know that > the program is corrupt (unless of course the corruption was such that > it made the counters look OK), but all you can do then is terminate > the program. One would not want to use such a container in a rocket controller! No, the point is that containers just manage elements. So containers care about tampering with cursors (adding/removing elements) or tampering with elements (replacing elements with different elements), not so much with modifying the elements managed by the container. The Cursor, Constant_Reference_Type and Reference_Type types in the end are all just references. Informally, cursors can become invalid because adding/removing elements might involve reorganization or reallocation of the datastructure causing any pointers to elements to become invalid. References can become invalid because the referenced element is no longer in the container and could be freed. >> As shown above, today tampering checks not only slow things down, they >> CAUSE erroneous execution >> in multitasking programs concurrently reading a container, as >> concurrent references cause concurrent writes. > > Right, but no one is required to use a reference to read an element. > Calling function Element involves no tampering check, the "problem" is > that it requires a copy of the element. Ergo, if you want concurrent > reads, just use Element rather than Constant_Reference. I don't see how this should make a difference. As long as we're only reading it shouldn't matter what kind of references or indexing we use. Remember, vectors should be able to be substitutes for arrays. We can concurrently read from multiple references to the same array element. The same should be true for vectors. > Of course, Ada does not guarantee concurrent reads in any case in the > standard library. Of course, we could add such a guarantee (presumably > for a very limited set of container operations). Repeating the "of course" twice doesn't really make it a stronger argument. If we'd violate the principle that concurrent reads are OK, that makes containers not a viable substitute for arrays. Vectors should have the same semantics as arrays. > I suspect that it wouldn't be too > hard to make a read guarantee work for the bounded containers, but for > the much more general indefinite containers (the big advance, IMHO), I > suspect that it would be problematical. It shouldn't be, or the implementation is flawed. In essence, if reading from a data-structure involves writing that data-structure, we're lost. > One reason being that we have to have > tampering checks to prevent erroneous execution of references there > (as any replacement of an element causes reallocation), whereas their > value for bounded containers is much more doubtful. (As described in > detail in my previous message.) Again, access types are not just memory addresses. We could implement access types as pairs of (integer index, version number), where the index points into an array of pointers and version numbers. That way we could detect dereferencing of access types whose target has disappeared or changed. > I'm somewhat dubious of the value of supporting concurrent reads > (only), you're always going to need some sort of locking to handle the > modifications, and it isn't going to add any additional overhead to > use that for reads as well. This is completely wrong. If we're not protecting against concurrent access, as is the case of regular data types such as arrays, no locking is needed for concurrent reads. They just work. A program wishing to update a container needs to ensure there are no concurrent readers, just as for any other variable. Updating the container concurrently with reading it is erroneous, just as for any other variable. With the version numbering scheme, it is easy to detect this. Reading never needs locking. > (My spam filter has this problem, blacklists and whitelists and other > data are rarely modified compared to the runtime of the filter, but > one still has to get a lock before reading from them in order to > ensure that the data isn't in the process of being updated.) What is > the use case that you are considering?? The general method is: read the version number, copy the data, read the version number again. If the number didn't change the data is good. Otherwise, repeat. This scheme ensures consistent data, as well as lock-free behavior: the system will always make progress, even though an individual task might starve. *************************************************************** From: Randy Brukardt Sent: Saturday, February 15, 2014 12:57 AM > > ... > >> It seems clear to me that anything involving controlled types for > >> the cursor is going to be unusable. In particular, it is a really > >> bad idea to require that creating a reference to a container must > >> modify that container. > > > > You're confusing cursors and references here. There are no > > (mandated) tampering checks for cursors. > > I'm referring to this (A.18.2(97.1/3)): > > When tampering with cursors is prohibited for a particular vector > > object V, Program_Error is propagated by a call of any > > language-defined subprogram that is defined to tamper with the > > cursors of V, leaving V unmodified. > Isn't this a mandated tampering check for cursors? No. This is a mandated tampering check (used in for loops and iterators) that no operations occur on the containers that would damage cursors. There is no mandated check on cursors themselves, and it's certainly not required that they are controlled. (They could be if the implementation wants that.) > > Your counter solution for cursors is a good one for detecting cursor > > problems. My container implementations uses a similar solution for > > that, although mine uses per-element rather than per-container ids. > > (That solution was designed in 2006 or 2007; this is not a > new idea.) > The purpose is not to invent new ideas, but to fix the horrible > inefficiencies (and lack of safety) that we have today. Today, a > cursor has to be controlled as the container has to know about it in > order to raise exceptions on operations that are defined to tamper > with cursors. This is definitely not true. There is little relationship between a cursor and a reference: a *reference* has to be controlled, a cursor does not. I think you need to read the container model much more closely before discussing it, because you have so much confused it takes an amazing amount of time to refute it. > Containers having to know about references to them, whether cursors or > otherwise, is the root of all evil. Then we have nothing that we could ever agree on vis-a-vis safety of containers. > > A reference, however, is an access discriminant. It's lifetime is > > strictly known to be that of the enclosing object, and the (usually > > static) accessibility checks required ensure that it cannot be used > > after that lifetime without heroic efforts. We also (usually > > statically) ensure that the container lives as long as the > > reference. > > Right, that is helpful. Unfortunately cursors don't have that > property, but there are ways to solve that with an extra level of > indirection. Cursors have nothing (directly) to do with tampering. "Tampering with cursors" is just a name. ... > Fortunately, access types are abstract in Ada. We can invent whatever > implementation we want for them, including ones that look like: > > type Version_Number_Access is access Version_Number; > type Element_Access is record > Address : System.Address; > Reference_Version : Version_Number; > Current_Version : Version_Number_Access; > end record; > > The compiler can implement the dereference of this fat pointer as: > > function Dereference (Ptr : Element_Access) return Element is > begin > if Ptr.Current_Version.all /= Ptr.Reference_Version then > raise Program_Error with "failed tampering check"; > end if; > > declare > Item : Element; > for Item'Address use Ptr.Address; > begin > return Element; -- return-by-reference > end; > end Dereference; Since Ada allows anonymous access types to be converted to other access types, you are saying that you want *all* general access types in Ada to have this representation. The odds of that happening are nil (it wouldn't be compatible with C, it would have huge overhead for people that never use the cursors, etc.). Besides, you're directly trying the same false starts we had when we tried to solve the user-defined dereference problem. We ended up with the access discriminant solution because it had the best overall properties. I doubt much has changed about that. Besides, this doesn't actually work. If the pointer is dereferenced and then passed as a reference parameter, and then tampering happens within the called subprogram, your check would pass, but use of the reference parameter is still erroneous. The existing tampering check catches that case (indeed, that case is the primary reason for this specific tampering check). > > Your proposal: > >> - any dereference checks the container for its version number, and > >> raises Program_Error > >> if it detects tampering > > > > makes no sense for references, because they are just a normal > > access-to-object dereference. Thus the element modification takes > > place through a raw pointer. There is no opportunity to communicate > > that modification back to the container. > > AFAIK, we don't have to. Tampering with elements means replacing > elements, not modifying them. Correct. In which case I have no idea what your proposal is intended to detect, because it won't detect any tampering at all. > The Cursor, Constant_Reference_Type and Reference_Type types in the > end are all just references. Informally, cursors can become invalid > because adding/removing elements might involve reorganization or > reallocation of the datastructure causing any pointers to elements to > become invalid. > References can become invalid because the referenced element is no > longer in the container and could be freed. Right. But these are handled very differently, because the consequences are very different. With a cursor, you always have to use some other operation for it to have any effect. That other operation can make any checks needed. With a reference, since you have a bare pointer, we can't make the checks that way, and we have to have tampering. > >> As shown above, today tampering checks not only slow things down, > >> they CAUSE erroneous execution in multitasking programs > >> concurrently reading a container, as concurrent references cause > >> concurrent writes. > > > > Right, but no one is required to use a reference to read an element. > > Calling function Element involves no tampering check, the "problem" > > is that it requires a copy of the element. Ergo, if you want > > concurrent reads, just use Element rather than Constant_Reference. > > I don't see how this should make a difference. It makes a difference because when an element is copied, it no longer matters what happens to the original element afterwards. It's the same reason that one uses temporaries rather than calculating values in place. > As long as > we're only reading it shouldn't matter what kind of references or > indexing we use. Remember, vectors should be able to be substitutes > for arrays. We can concurrently read from multiple references to the > same array element. The same should be true for vectors. If we had ragged arrays (like the indefinite containers), you'd have all of the same problems. Only a bounded container is anything like an array, and I could see making an exception for those. But really, you are asking for more than Ada guarantees about anything. Unless you have atomic or protected objects, having multiple tasks access (or call!) anything is always risky. That's a flaw in Ada, but it is pervasive. One hopes that the parallel subgroup will come up with some proposals that will help that. You can get away with multiple access to an array so long as the components are disjoint. But that works simply because there is no control structure associated with it; if there is, as in the case of the containers, access becomes much more problematical. > > Of course, Ada does not guarantee concurrent reads in any case in > > the standard library. Of course, we could add such a guarantee > > (presumably for a very limited set of container operations). > Repeating the "of course" twice doesn't really make it a stronger > argument. > If we'd violate the principle that concurrent reads are OK, that makes > containers not a viable substitute for arrays. > Vectors should have the same semantics as arrays. Only protected (and atomic) objects are truly safe when used from tasks. So in this way, they *are* the same as arrays. :-) More seriously, if you're willing to restrict your view to what can be accomplished with arrays (as in the bounded vectors), then I can see your point. But a vector (in general) has many capabilities that an array does not, especially in allowing elements of different sizes and shapes. And those compatibilities require complex implementations that would be hard to make task safe AND memory safe. > > I suspect that it wouldn't be too > > hard to make a read guarantee work for the bounded containers, but > > for the much more general indefinite containers (the big advance, > > IMHO), I suspect that it would be problematical. > > It shouldn't be, or the implementation is flawed. In essence, if > reading from a data-structure involves writing that data-structure, > we're lost. No, you're lost. The whole advantage of the containers to me is that they manage memory and eliminate almost all erroneous execution from dangling pointers. (Iterators also have a termination guarantee.) To eliminate those guarantees in order to have a dubious read-only tasking guarantee is going in the wrong direction. There would be value to a fully task-safe container implementation, but it would necessarily be quite expensive. > > One reason being that we have to have tampering checks to prevent > > erroneous execution of references there (as any replacement of an > > element causes reallocation), whereas their value for bounded > > containers is much more doubtful. (As described in detail in my > > previous message.) > Again, access types are not just memory addresses. We could implement > access types as pairs of (integer index, version number), where the > index points into an array of pointers and version numbers. That way > we could detect dereferencing of access types whose target has > disappeared or changed. That's never going to happen. It's been proposed before but the overhead would be crippling. Indeed, one of the main reasons cursors are private types is so that they can have an implementation like the one you're talking about. But it doesn't work for references (both because the check is too soon, and because you can't change the representation of an Ada general access type, since they're all interconvertable modulo accessibility checks). > > I'm somewhat dubious of the value of supporting concurrent reads > > (only), you're always going to need some sort of locking to handle > > the modifications, and it isn't going to add any additional overhead > > to use that for reads as well. > This is completely wrong. If we're not protecting against concurrent > access, as is the case of regular data types such as arrays, no > locking is needed for concurrent reads. They just work. A program > wishing to update a container needs to ensure there are no concurrent > readers, just as for any other variable. Exactly. And the only way I know (that doesn't pervert the program structure) to prevent concurrent readers is to have them test an "updating" lock before they do any reading, and free it afterwards. You could have the updater call an entry in the readers to tell them to pause, but that really puts irrelevant stuff into the readers (and has at least has as much overhead as a lock). It makes much more sense to have the entire data structure protected by an appropriate locking system. The only time your suggestion would make sense is in the case of a data structure that is *never* modified after initialization. But those structures are much rarer in practice than initially seems to be the case. (Almost every structure that I've ever designed that way had to be changed at some future point to allow modifications.) > Updating the container concurrently with reading it is erroneous, just > as for any other variable. With the version numbering scheme, it is > easy to detect this. Reading never needs locking. > > > > (My spam filter has this problem, blacklists and whitelists and other > > data are rarely modified compared to the runtime of the filter, but > > one still has to get a lock before reading from them in order to > > ensure that the data isn't in the process of being > > updated.) What is the use case that you are considering?? > The general method is: read the version number, copy the > data, read the version number again. If the number didn't > change the data is good. Otherwise, repeat. > This scheme ensures consistent data, as well as lock-free > behavior: the system will always make progress, even though > an individual task might starve. Such a system is likely to miss deadlines. Hard to say if that is acceptable or not. For my spam filter, that would require a version number on every individual item (since reads have a very small granularity), or copying all of the data. Neither seems like a good option. Remember that the containers, like an array, are designed to allow using of elements in place. You *never* have to copy an element. I don't see how this scheme would work when updating parts of elements in place (which is the normal case). Anyway, please explain a scheme that actually detects the bugs that tampering prevents, and then it will make much more sense to talk about this. It's frustrating when someone is solving different problems than the ones the checks actually prevent. *************************************************************** From: Randy Brukardt Sent: Saturday, February 15, 2014 8:19 PM The problem with quickly answering messages on the way out of the office is that you don't organize your thoughts very well. Thus I want to clarify a point that's somewhat off-topic here, hopefully so we don't discuss it more (certainly not in this thread). I said: > Unless you have atomic or protected objects, having multiple tasks > access (or call!) anything is always risky. That's a flaw in Ada, but > it is pervasive. By this, I mean that multiple task access to raw Ada data structures like an array is risky. It's risky because safe access always requires some sort of protocol, be it "no access after initialization", or "check version number and retry if changed", or "lock before use", or whatever. Just accessing an array from multiple tasks without any sort of protocol is likely going to cause a latent bug of some sort. And that is a very hard bug to find, as it is likely to occur rarely, and also it is an error of omission (which are usually the hardest ones to find). The Ada language provides very little help for this, in that it doesn't have many ways to prevent access that avoids the protocol. The best thing one can do is to completely encapsulate the data structure (array in this example) in a package, but once that's done, the "arrayness" has disappeared -- we just have another ADT, essentially another container. Essentially, if you want a multi-tasking guarantee in Ada, you need to write a package that provides it. The standard containers are no different in this regard. Whether Ada should have some purpose-built multi-tasking safe containers is another question, but they clearly would need a different design (or abandonment of safety). *************************************************************** From: Randy Brukardt Sent: Saturday, February 15, 2014 9:06 PM ... > Besides, this doesn't actually work. If the pointer is dereferenced > and then passed as a reference parameter, and then tampering happens > within the called subprogram, your check would pass, but use of the > reference parameter is still erroneous. The existing tampering check > catches that case (indeed, that case is the primary reason for this > specific tampering check). In case someone actually wants to see some of the examples that the reference tampering check is intended to prevent, and to have them ready for the eventual AI, I've created some examples: package Pkg is type Item is record C : Character := 'R'; ... end record; package Item_Vector is new Ada.Containers.Vectors (Element_Type => Item, Index_Type => Positive); Item_List : Item_Vector.Vector; procedure Process_Item (Obj : in out Item); end Pkg; package body Pkg is procedure Process_Item (Obj : in out Item) is begin ... -- Split Item: Item_List.Append (Item'(C => Character'Pred(Obj.C), ...)); -- [1] Obj.C := Character'Succ(Obj.C); -- [2] ... end Process_Item; end Pkg; with Pkg; procedure Main is begin Pkg.Item_List.Append (Item'(C => 'M', ...)); Pkg.Item_List.Append (Item'(C => 'T', ...)); Pkg.Process_Item (Pkg.Item_List(2).all); -- [3] end Main; The call at [3] uses the Variable_Indexing aspect and expands into Pkg.Process_Item (Pkg.Item_List.Reference(2).Element.all); In this case, tampering with elements is prohibited until the call Process_Item returns. This means that the call at [1] fails a tampering check. This is important; if the Append call required an expansion of the vector, and the vectors' implementation uses a reallocation strategy (this was Matt's original reference implementation of unbounded vectors), then the element Item_List(2) will be copied to the new (larger) vector data area, and the original one will be freed. If the parameter Obj is passed by reference (as it must be if Item is a by-reference type, for example if it is tagged), then the parameter object no longer exists at the location referenced by the parameter, and the modification at [2] will occur into memory no longer owned by the container. This is classic use of a dangling pointer. The parameter Obj being passed by copy does not help. In that case, the modification at [2] will be OK, but the copy-back after the call will be to non-existent memory. Moreover, the problem occurs in the by-copy case even if the object is never touched after the tampering call. Note that at the point of the dereference, there is no problem. The problem happens later, AFTER the dereference, but while the reference object exists. Also note that this is a new problem to the containers; it does not happen with arrays. That's because arrays have no way to create or delete or replace elements. The set of elements is fixed for the entire life of an array object. We don't want the implicit use of Unchecked_Deallocation inside of the containers to leak out and cause new erroneous cases. Even when the parameters in question have mode "in", a version of the problem still exists, since no modification of the container is necessary to cause problems. While reading non-existent memory is less dangerous than writing it (as it can't corrupt the program directly), it still can cause the program to fault (for instance, if the deallocated memory was returned to the target OS/kernel and it was unmapped from the process's address space). So the read at [2] has a risk of causing a program fault and thus it has to be formally erroneous in this case. A similar problem can happen if the reference is passed as an access parameter: package Pkg2 is type Item is record C : Character := 'R'; ... end record; package Item_Vector is new Ada.Containers.Vectors (Element_Type => Item, Index_Type => Positive); Item_List : Item_Vector.Vector; procedure Process_Item (Obj : access Item); end Pkg2; package body Pkg is procedure Process_Item (Obj : access Item) is begin ... -- Split Item: Item_List.Append (Item'(C => Character'Pred(Obj.all.C), ...)); -- [4] Obj.all.C := Character'Succ(Obj.all.C); -- [5] ... end Process_Item; end Pkg; with Pkg; procedure Main is begin Pkg.Item_List.Append (Item'(C => 'M', ...)); Pkg.Item_List.Append (Item'(C => 'T', ...)); Pkg.Process_Item (Pkg.Item_List(2)); -- [6] end Main; In this case, the parameter acts as if it is passed by-reference, so the by-copy issues can't happen, but the remaining issues still are possible. Note that the reference (an anonymous access discriminant) is implicitly converted to the anonymous access parameter. The accessibility rules are still in place; an attempt to assign the access parameter to a long-lived access type should raise Program_Error. In this example, the dereference occurs after the tampering, but it's possible to use a renaming to move that before the tampering: My_Obj : Item renames Obj.all; In any case, passing objects as parameters is fundamental to Ada; having them be unsafe is not acceptable. As I've previously noted, these particular examples can't cause erroneous execution this way for the bounded containers (as the underlying memory is never allocated or freed on the fly, only when the container is created or destroyed), so it might make sense to eliminate the tampering check there. But there is another way for tampering with a container to cause erroneous execution. Specifically, AI05-0212-1 gives an example of how vector sliding can cause erroneous execution for a reference. (It's rather long so I won't repeat it here.) In this case, the erroneous execution is caused by changing the discriminants of a constrained object. Argubly, we could tolerate this erroneousness, since we do so for other kinds of calls (see 3.7.2(4)). We never decided if that was OK as we prevented it with no extra cost with the same check that prevents the first problem. Hope this sheds some light on the purpose of the tampering checks for Reference/Constant_Reference. *************************************************************** From: Bob Duff Sent: Sunday, February 16, 2014 8:35 AM > Even when the parameters in question have mode "in", a version of the > problem still exists, since no modification of the container is > necessary to cause problems. While reading non-existent memory is less > dangerous than writing it (as it can't corrupt the program directly), > it still can cause the program to fault (for instance, if the > deallocated memory was returned to the target OS/kernel and it was > unmapped from the process's address space). So the read at [2] has a > risk of causing a program fault and thus it has to be formally erroneous in > this case. Well, you don't need unlikely events like "unmapped from address space" to see bad behavior. If X is a dangling pointer, then: Y := X.all.Next; Y.all := ...; will overwrite arbitrary memory locations. So yes, the fact that X is an in-mode parameter doesn't help. > Hope this sheds some light on the purpose of the tampering checks for > Reference/Constant_Reference. Yes, thank you. I think I sort-of knew all that, but it was helpful to have it clearly laid out. *************************************************************** From: Bob Duff Sent: Wednesday, June 4, 2014 2:16 PM [From an administrative thread:] >...AI 111 is on performance (rather than strictly real-time), of >Containers, but I get the impression that Randy isn’t too keen on >relaxing the safety checks, and I think it’s too early to discuss >until there’s at least one implementation of the Containers that >passes the ACATS tests (get it functionally correct then think about >tuning it). Good point. But even then it will be premature to discuss in ARG. The way to attack that problem is to hack on (some implementation of) containers, profile them, and experiment with possible language changes, possible compiler changes, etc. Making language changes first, in the hopes that they might make containers efficient, won't work -- too much guesswork. The moral of the story is that the folks who say standards committees should be standardizing existing practice, rather than inventing, are right. *************************************************************** From: Robert Dewar Sent: Wednesday, June 4, 2014 2:23 PM > Good point. But even then it will be premature to discuss in ARG. > The way to attack that problem is to hack on (some implementation of) > containers, profile them, and experiment with possible language > changes, possible compiler changes, etc. Making language changes > first, in the hopes that they might make containers efficient, won't > work -- too much guesswork. I agree. Let GNAT figure out how to make containers usable, we have an enormous incentive to do that, many of our customers are seriously worried by the horrible performance compared to C++ and we have to do something about it. > The moral of the story is that the folks who say standards committees > should be standardizing existing practice, rather than inventing, are > right. Especially at this stage. *************************************************************** From: Brad Moore Sent: Thursday, October 16, 2014 9:32 AM The discussion section of this AI shows an example of tampering with elements that the tampering checks detect, basically involving obtaining a reference to an element of a vector, and then using that reference to call a procedure which appends an item to container, which could cause the array to be increased in size, leaving the original reference pointing to garbage. I'm wondering if it would be possible to catch this sort of error at compile time rather than at run time. This is the approach taken by the Rust programming language, for a similar example. See http://doc.rust-lang.org/nightly/intro.html fn main() { let mut v = vec![]; v.push("Hello"); let x = &v[0]; v.push("world"); println!("{}", x); } This fails to compile because the second push call it attempting to "borrow" a mutable reference to vector v, while an immutable "borrow" exists (the declaration of x) Maybe Ada could have a compiler mode where it does this sort of checking, or maybe the Global aspects proposal of AI12-0079 could help here. If we had a way to rely on these sorts of errors being caught at compile time, then maybe the need for expensive run-time checks could be eliminated. *************************************************************** From: Robert Dewar Sent: Saturday, October 18, 2014 8:25 AM > The discussion section of this AI shows an example of tampering with > elements that the tampering checks detect, basically involving > obtaining a reference to an element of a vector, and then using that > reference to call a procedure which appends an item to container, > which could cause the array to be increased in size, leaving the > original reference pointing to garbage. > > I'm wondering if it would be possible to catch this sort of error at > compile time rather than at run time. VERY messy to have the compiler have to know this much about container packages, so best would be if some pragmas could be devised that makes the relevant check more general. *************************************************************** From: Randy Brukardt Sent: Tuesday, May 26, 2015 3:55 PM > The discussion section of this AI shows an example of tampering with > elements that the tampering checks detect, basically involving > obtaining a reference to an element of a vector, and then using that > reference to call a procedure which appends an item to container, > which could cause the array to be increased in size, leaving the > original reference pointing to garbage. > > I'm wondering if it would be possible to catch this sort of error at > compile time rather than at run time. I keep thinking about this, and wanted to write something up so I can stop thinking about it and do something actually on my work list. The answer to Brad's question is yes, and in fact the main thing we need is the proposal for the Global aspect. But the result would be wildly incompatible (because of course no existing subprogram has a global aspect). Specifically, tampering with elements effectively is the same as saying that the container cannot be written (other than by the reference itself, of course). So, when tampering with elements is prohibited, any attempt to write the container other than by the reference could be an error. (We'd probably want to somehow define an aspect to mean this, so the rules aren't completely aribtrary.) That's easy for direct uses (as when the result of Reference is renamed), but it's messier when calls are involved (the most important such case being when the result of Reference is passed as a parameter). Here the (proposed) Global aspect is a huge help: the rule could be that the call is illegal if the subprogram's Global aspect allows writing of the container. Since the vast majority of calls would not even know about the container in question, most calls would work fine. The problem here being that the default meaning if there is no Global aspect is "writes all", which clearly would have to be illegal. We could mitigate that somewhat by making the error suppressible (assuming that idea gets implemented), but it still would be too incompatible (in my view, anyway) to use it unconditionally on the existing containers. Thus, the idea would be best used on new containers (specifically the task-safe ones designed for use in parallel loops and the like). Tucker had noted that the "of" form of iterator is a combination of an iterator and a reference, so the same compile-time tampering check would be OK there as well (the reference needs the strong check in any case, and it's stronger than the check for the iterator). However, it would be way too fierce for tampering with cursors situations for regular iterators (it would prevent modifying the element in an iterator, which of course would be nonsense). So it would seem that would need to remain a run-time check. That's probably OK, the number of iterators in a program is far less than the number of calls to Reference. *************************************************************** From: Tucker Taft Sent: Saturday, June 4, 2016 9:59 PM Here is a new version of AI-111 [Version /03 - Ed] that proposes defining a child package "Stable" for each container package, in which a "stable" container type is defined. A stable container object has an access discriminant which can designate an underlying regular container, to provide a "stabilized view" of that container. While the stabilized view exists, no tampering of the underlying container is permitted. A stable container type includes essentially all of the operations of the "regular" container type that do not change the "shape" of the container. This AI also proposes to eliminate the notion of "tampering with elements" for all but containers with elements having an indefinite type. *************************************************************** From: Tucker Taft Sent: Sunday, June 5, 2016 9:41 AM After more thought, it seems we might consider making the Stable.Vector type limited, and require the Base discriminant to be non-null. It is going to be build-in-place anyway, and ":=" won't be reliable so the Assign procedure will be needed in most cases, so there really isn't much benefit in making it non-limited and having the special case for Base=>null. If we do this, then stable vectors created by functions like Copy or To_Vector will become the perfect candidates for use of co-extensions. ;-) For what it is worth, the "&" operators are other ways to create values of the Stable.Vector type, which wasn't mentioned in the write-up. *************************************************************** From: Randy Brukardt Sent: Tuesday, June 7, 2016 5:31 PM > Here is a new version of AI-111 that proposes defining a child package > "Stable" for each container package, in which a "stable" container > type is defined. A stable container object has an access discriminant > which can designate an underlying regular container, to provide a > "stabilized view" > of that container. While the stabilized view exists, no tampering of > the underlying container is permitted. A stable container type > includes essentially all of the operations of the "regular" container > type that do not change the "shape" > of the container. For the record, I changed this AI into the form of an Amendment, since adding dozens of Stable subpackages and removing a check seems way beyond a Binding Interpretation. > This AI also proposes to eliminate the notion of "tampering with > elements" for all but containers with elements having an indefinite > type. The way you did this is as follows: Delete 18.2(95/2-97/2) (and similar paragraphs except for Indefinite_*) talking about tampering with elements. The problem with this is that the Indefinite_* containers never talk about tampering with elements at all (the word "tampering" does not appear in A.18.11 for Indefinite_Vectors, for instance). You have to *move* the existing wording to the indefinite clauses, you can't just delete it in the regular containers. [I also assume that you are replacing "tampering with elements" with "tampering with cursors" in the places where it currently says "tampering with elements", lest reallocation on growth not be allowed as an implementation strategy (that's the "canonical" implementation of a vector). If you're doing that, you need to say so somewhere.] Overall, I can't figure out how to get from your suggested change to your intended result. *************************************************************** From: Tucker Taft Sent: Tuesday, June 7, 2016 9:54 PM > ... Overall, I can't figure out how to get from your suggested change > to your intended result. Actually, you seemed to have figured out my intent. Hopefully it will also be clear to the rest of the ARG. We can fix up the wording after the meeting, if there is support for the approach. *************************************************************** From: Erhard Ploedereder Sent: Sunday, June 12, 2016 8:53 AM In response to questions raised... It was the reading from Containers that was exceptionally slow. Writing was reasonably competitive with other languages. Hashed sets were called out as culprits (this may well be an "e.g." rather than pointing out the only sinner); the difference to other languages was 4x to 8x execution time. Other containers used were Vectors, Doubly_linked_lists and Hash maps. (Orthogonally: Use of indefinite containers in contrast to the "normal" ones added a factor of ~2.) *************************************************************** From: Randy Brukardt Sent: Monday, July 11, 2016 9:17 PM Could you find out *which* operations that were used to read from Containers? I'd expect the performance of Element, Query_Element, and Constant_Reference (the three main ways to read) to be very different (with Query_Element being the fastest and Element being the slowest for most element types). (Of course, regular indexed notation expands into calls on Constant_Reference.) After all, Element essentially makes a copy of an element, whereas the other two use a direct reference into the element. *************************************************************** From: Jeff Cousins Sent: Tuesday, August 16, 2016 6:21 AM Erhard - do you know specifically which reads were slow? Presumably you've already done the legwork of taking the measurements, but which did you measure? *************************************************************** From: Erhard Ploedereder Sent: Wednesday, August 17, 2016 7:18 AM A while ago, I cleaned the experiment from my disk, as changes to the containers made the results obsolete anyway. As such, I have to see whether I can retrieve this from backup somehow and I have not got around to doing the archeology. It was not my experiment, but one of my assistants, so mmy memory alone does not serve. *************************************************************** From: Jeff Cousins Sent: Wednesday, August 17, 2016 8:01 AM Ok, thanks Erhard. *************************************************************** From: Erhard Ploedereder Sent: Saturday, August 20, 2016 7:31 PM I did ask my assistant to look at the problem again. First, I barked up the wrong tree in my cited message. Apologies. The slowness comes from inserting entities into hashed sets after reading them from external files. So it is the writing to hashed sets that is slow. Simply invert the quoted statements below wrt reading/writing. The time for reading/writing these files inclusive of storing/retrieving the entities from containers was measured. These measurements were compared among multiple languages using their respective container packages. Hence my inverted statement about reading/writing. Times for reading the files were really bad for Ada in comparison to the others. Culprit was/is the writing to the container. The slow writing to hashed sets is done by Ada.Containers.Hashed_Sets procedure Include (Container : in out Set; New_Item : Element_Type); The comparably much faster reading is done by cursor over the hash set while writing the retrieved entities to a file. These possible causes were suspected (but not verified as the true causes): - unnecessary additional allocations - seemingly irrelevant computations (maybe tampering checks?) - generality to deal with Element_Type of size not known at compile time - exception handling preventing inlining of calls *************************************************************** From: Jeff Cousins Sent: Sunday, August 21, 2016 1:49 AM Thanks for looking that up Erhard. Good to get the info. *************************************************************** From: Tucker Taft Sent: Sunday, August 21, 2016 12:19 PM For what it is worth, AdaCore has re-implemented most of the containers, and has added the ability to suppress either just tampering checks, or all checks, on container operations. Might be worth trying with the latest GNAT container implementations. *************************************************************** From: Tucker Taft Sent: Sunday, October 2, 2016 9:10 PM Here is an update on the stable containers AI. [This is version /04 - Editor.] I don't believe Raphael had time to prototype this. Major changes -- made this into a subpackage, and made the Base discriminant "not null" with no default. Began describing the semantics of the operations of the package, perhaps most importantly, To_Vector and Copy. Also added a version of Copy that takes an unstable vector as its parameter. Eliminated the Capacity parameter to Copy, as that doesn't make much sense for a stable vector. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 3:21 PM I was in holidays for two weeks - I'll try not to take vacations just before an ARG meeting in the future ;) - but I'm well on my way prototyping stable vectors, I hope to have some results for the ARG ! I do have some questions though: type Vector (Base : not null access Vectors.Vector) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; Why do you need the Base to be an access discriminant ? The rationale may be obvious, it is not mentioned in the AI, but to my mind it mostly causes problems in the implementation. How do you plan to define Empty_Vector, knowing that Base can't be null, and that you cannot use Vectors.Empty_Vector because it will appear later ? *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 3:35 PM > Why do you need the Base to be an access discriminant ? The rationale > may be obvious, it is not mentioned in the AI, but to my mind it > mostly causes problems in the implementation. Without an access discriminant, I can't imagine how the user will specify which unstable vector the stable vector will control. > ... How do you plan to define Empty_Vector, knowing that Base can't be null, > and that you cannot use Vectors.Empty_Vector because it will appear later ? Good point. We probably have to make Empty_Vector into a parameterless function, now that this is a nested package. E.g.: function Empty_Vector return Vector is begin return Result : Vector(Base => new Vectors.Vector'(Empty_Vector)); end Empty_Vector; The result would be "built in place" at the point of call. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 3:56 PM > Without an access discriminant, I can't imagine how the user will specify > which unstable vector the stable vector will control. Via a constructor function ? That would be a better option I think, make the type completely private, and have one/several constructor functions if you need to enable the user to construct them directly. Also what do you mean by user ? To my mind a stable container can only be constructed via functions on the container itself, something like: function Stable_View (Self : Vector) return Stable.Vector; >>... How do you plan to define Empty_Vector, knowing that Base can't be null, >>and that you cannot use Vectors.Empty_Vector because it will appear later ? >Good point. We probably have to make Empty_Vector into a parameterless >function, now that this is a nested package. E.g.: > > function Empty_Vector return Vector is > begin > return Result : Vector(Base => new Vectors.Vector'(Empty_Vector)); > end Empty_Vector; > >The result would be "built in place" at the point of call. I think this is a bit kludgey, I'd like to be sure that the access discriminant is needed first. *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 4:18 PM > Via a constructor function ? That would be a better option I think, > make the type completely private, and have one/several constructor > functions if you need to enable the user to construct them directly. Not quite sure how that would work from an accessibility point of view. Remember that we are taking an existing object, and creating a wrapper around it. Using an access discriminant the only requirement is that the existing object be aliased, and since Vector is a tagged type, when passed as a parameter it is always aliased. > Also what do you mean by user ? To my mind a stable container can only > be constructed via functions on the container itself, something like: > > function Stable_View (Self : Vector) return Stable.Vector; That is not the model proposed by this AI. Instead, you write: X : aliased My_Vectors.Vector; ... declare Stable_X : My_Vectors.Stable.Vector(Base => X'Access); ... >>> ... How do you plan to define Empty_Vector, knowing that Base can't >>> be null, and that you cannot use Vectors.Empty_Vector because it will appear later ? >> >> Good point. We probably have to make Empty_Vector into a >> parameterless function, now that this is a nested package. E.g.: >> >> function Empty_Vector return Vector is >> begin >> return Result : Vector(Base => new Vectors.Vector'(Empty_Vector)); >> end Empty_Vector; >> >> The result would be "built in place" at the point of call. > > I think this is a bit kludgey, I'd like to be sure that the access > discriminant is needed first. This situation is in some sense exactly what access discriminants were designed for. It seems odd not to use them since they are the most natural solution for this sort of wrapper. *************************************************************** From: Bob Duff Sent: Monday, October 3, 2016 4:24 PM > Good point. We probably have to make Empty_Vector into a > parameterless function, now that this is a nested package. E.g.: > > function Empty_Vector return Vector is Functions are better anyway, because they can be overloaded. It's annoying when the compiler complains, "Which Empty_Vector did you mean?" "The one of the right type, of course, YA BIG DUMMY!!" ;-) *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 4:29 PM Ok, thank you for the precisions, that makes sense. I'll go for the Empty_Vector function then. *************************************************************** From: Edmond Schonberg Sent: Monday, October 3, 2016 5:05 PM > Ok, thank you for the precisions, that makes sense. I'll go for the > Empty_Vector function then. Not the precisions again :-)! *************************************************************** From: Randy Brukardt Sent: Monday, October 3, 2016 4:42 PM ... > Functions are better anyway, because they can be overloaded. > It's annoying when the compiler complains, "Which Empty_Vector did you > mean?" "The one of the right type, of course, YA BIG DUMMY!!" ;-) There'd be no major problem in allowing constants to be overloaded (the profile is obvious, just like it is for enumeration literals). (Having variables overloaded would be a bit weird, but not a difficult problem either.) It's unfortunate that Ichbiah didn't take the model to that obvious point, because most of the issues with maintenance problems come from non-overloadable entities. I researched this once in the past (I think in the context of the "integrated package" proposal) and concluded that it wouldn't cause real issues (mostly, it would make illegal programs legal, which hardly could be a problem). But there is a lot of FUD when it comes to visibility, and I fully understand. Plus it would be fairly complex in terms of language wording, so I don't suppose there would be enough support to try again. (Similarly, there is no problem with allowing untagged types in the private part of a protected object [no other unit has visibility, so the usual problems of where operators become visible in the visible view are moot]. Another thing that there is no will to change. I'd rather fix these annoyances, which would make Ada better for everyone, rather than spend time on limited-use features. YMMV.) *************************************************************** From: Randy Brukardt Sent: Monday, October 3, 2016 5:41 PM > Here is an update on the stable containers AI. In the third paragraph of A.18.2.1, there is a Redundant section which ends (but does not start) with a paren. I put a starting paren at the start of the Redundant text (that's what was in the previous version). Perhaps you meant to delete both parens instead? (A closing paren with no opening paren does not work.) *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 8:50 PM Oops. I meant to remove both parens. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 6:06 PM > Good point. We probably have to make Empty_Vector into a > parameterless function, now that this is a nested package. E.g.: > > function Empty_Vector return Vector is > begin > return Result : Vector(Base => new Vectors.Vector'(Empty_Vector)); > end Empty_Vector; > > The result would be "built in place" at the point of call. I don't understand though, are you thinking about actually allocating a new empty vector copy every time the users calls Stable.Empty_Vector? *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 8:58 PM Yes, although this is a "co-extension" so that its lifetime lasts only as long as the enclosing object -- it isn't necessarily on the heap -- it is allocated where the enclosing object is allocated. Note that for a limited type, you are obliged to create a new object every time you call a function. You are not allowed to return a reference to or copy of an existing object of a limited type. I suppose we could create a single underlying unstable empty vector and have all of the copies of Stable.Empty_Vector point at it, but it doesn't seem like a big deal, and I worry about multi-tasking issues associated with multiple wrappers all simultaneously setting the "no-tampering" flag on this shared unstable empty vector. In any case, I don't see many uses of Empty_Vector for a stable vector type. I could see using "Is_Empty" to see if a stable vector is empty, but since stable vectors aren't allowed to change in length, you would normally call "To_Vector(Length => whatever)" to create a stable vector of the desired length. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 9:10 PM Is this implemented by GNAT though, or by any other Ada compiler ? That would need to be checked in my opinion, because however uncommon checking a stable vector against the empty vector would be, it could still happen in a time critical loop where I certainly would not expect an allocation to happen, with all associated cons (System call, context switch, unbounded time operation). If it is, I only have a theoretical objection against such a solution (the code is too complicated for what it does). If it is not, I also have a practical one :) The reason we're in this situation in the first place is that performance was not originally taken into consideration in the design of the containers. Let's not do the same mistake again. *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 9:35 PM >> Yes, although this is a "co-extension" so that its lifetime lasts >> only as long as the enclosing object -- it isn't necessarily on the >> heap -- it is allocated where the enclosing object is allocated. > > Is this implemented by GNAT though, or by any other Ada compiler ? > That would need to be checked in my opinion, This might justify GNAT fixing this, if they don't do it correctly now. But see below -- simpler is to delete Empty_Vector from the package. > ... because however uncommon checking a stable vector against the > empty vector would be, it could still happen in a time critical loop > where I certainly would not expect an allocation to happen, with all > associated cons (System call, context switch, unbounded time operation). If that is a real concern, I would suggest we omit "Empty_Vector" completely from the package. The right way to check if a vector is empty is using "Is_Empty" and if you want to create a stable empty vector for some bizarre reason, in the absence of an Empty_Vector operation, you could do it using To_Vector() or Copy(). > If it is, I only have a theoretical objection against such a solution > (the code is too complicated for what it does). If it is not, I also > have a practical one :) > > The reason we're in this situation in the first place is that > performance was not originally taken into consideration in the design of the > containers. That is a little unfair, I would say. There was an implementation of containers from day one of the design, and performance was a significant concern. It may be that we just didn't understand the usage patterns, or the overall impact of tampering checks. And as Randy likes to remind us, it is the implementation of references as controlled objects rather than tampering checks per se that can be the source of a lot of the overhead. These kind of references didn't exist when containers were first designed. > ... Let's not do the same > mistake again. Agreed. But on the other hand, let's not worry too much about performance implications of misusing the operations. In any case, if we remove Empty_Vector from the package, I think we simplify the interface and eliminate a way that a naive user might waste a lot of energy creating an empty vector just to use it to compare against some other vector. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 10:01 PM > If that is a real concern, I would suggest we omit "Empty_Vector" > completely from the package. The right way to check if a vector is > empty is using "Is_Empty" and if you want to create a stable empty > vector for some bizarre reason, in the absence of an Empty_Vector > operation, you could do it using > To_Vector() or Copy(). I think this is the best option indeed ! > That is a little unfair, I would say. There was an implementation of > containers from day one of the design, and performance was a > significant concern. It may be that we just didn't understand the > usage patterns, or the overall impact of tampering checks. And as > Randy likes to remind us, it is the implementation of references as > controlled objects rather than tampering checks per se that can be the > source of a lot of the overhead. These kind of references didn't exist when > containers were first designed. Yes, I'm sorry, my statement was overly broad, and I clearly don't know all the history. >> ... Let's not do the same >> mistake again. > > Agreed. But on the other hand, let's not worry too much about > performance implications of misusing the operations. In any case, if > we remove Empty_Vector from the package, I think we simplify the > interface and eliminate a way that a naive user might waste a lot of > energy creating an empty vector just to use it to compare against some other > vector. Agreed ! *************************************************************** From: Randy Brukardt Sent: Monday, October 3, 2016 10:04 PM > >> Yes, although this is a "co-extension" so that its lifetime lasts > >> only as long as the enclosing object -- it isn't necessarily on the > >> heap -- it is allocated where the enclosing object is allocated. "coextension" (no hyphen). And yes, Raphael, it is a first-class part of the Ada language. It's either a great thing (Tucker), or the spawn of the devil (many of us). You can chose which group you belong to. ;-) Steve Baird got his reputation by interjecting in discussions about almost anything -- "what about a coextension"? Sadly, most of these turned out to be real issues. (I hate coextensions with a passion...) ... > If that is a real concern, I would suggest we omit "Empty_Vector" > completely from the package. That seems to be the correct solution. What possible purpose is there for avoiding the tampering checks on a known empty container? You can't do anything with such a container other than query its length (since you can't insert anything). The usual use for Empty_Vector and the like is an initial value for a container that will get added to, but that will never happen for a "stable" container. OTOH, I can't imagine why we would care how an operation that would never be used is implemented. Heck, it could permanently leak memory and send pinups to Ada mailing lists and no one other than a possible ACATS test would ever care. So this has to be one of the silliest tempest-in-a-teapots ARG discussions I've heard in a while. *************************************************************** From: Raphael Amiard Sent: Monday, October 3, 2016 10:28 PM > OTOH, I can't imagine why we would care how an operation that would > never be used is implemented. Heck, it could permanently leak memory > and send pinups to Ada mailing lists As the guy in charge of prototyping, challenge accepted ! > and no one other than a possible ACATS test would ever care. So this > has to be one of the silliest tempest-in-a-teapots ARG discussions > I've heard in a while. Well, I'll take pride in that if in nothing else :) On a more serious note, Stable vectors could be a generic container parameter to another generic package - I don't know, binary search for example - and that package could expect a constant object representing the empty container. Or even worse, and probably much more realistic, somebody could just be adapting code working on vectors that has special cases for empty containers. We're, after all, designing the API to be very similar, so that migration is easy, so that kind of mechanic migration is not out of the question. Anyway, I think it was pretty productive - we found the best solution, and one we apparently all agree on :) *************************************************************** From: Tucker Taft Sent: Monday, October 3, 2016 10:28 PM Agreed. Ignore the grump behind the curtain... ;-) He'll be all sweetness and light by the time we get to Pittsburgh. *************************************************************** From: Raphael Amiard Sent: Tuesday, October 4, 2016 8:59 AM > That is not the model proposed by this AI. Instead, you write: > > X : aliased My_Vectors.Vector; > > ... > > declare > Stable_X : My_Vectors.Stable.Vector(Base => X'Access); > ... I've made good progress with the implementation, to the point where I'm writing use cases, and looking back on it, this seems like a verbose way to declare a stable vector, since it's an operation you might want to do for every loop. What about having a shortcut primitive in Vector: for El of X.Stable loop end loop; ? *************************************************************** From: Tucker Taft Sent: Tuesday, October 4, 2016 10:05 AM > for El of X.Stable loop > end loop; Our expectation was that stable containers will be used automatically for these sorts of loops as part of the standard expansion of this "syntactic sugar," subject perhaps to adding an additional aspect specification (e.g. type Vector ... with Stable_Type => Stable.Vector). To some degree, the idea of stable containers arises from the need to make loops that iterate over containers more efficient. *************************************************************** From: Raphael Amiard Sent: Tuesday, October 4, 2016 10:08 AM Ok, that makes sense, and is even better since it doesn't require any intervention from the user. *************************************************************** From: Raphael Amiard Sent: Tuesday, October 4, 2016 10:46 AM > Here is an update on the stable containers AI. I don’t believe Raphael had time to prototype this. So, I’m more or less done prototyping this, will clean up the code and send it here when I’m done. The prototyped version provides the expected performance results. Running this program: with Vectors; with Ada.Text_IO; use Ada.Text_IO; with Ada.Calendar; use Ada.Calendar; procedure Main is package V is new Vectors (Natural, Integer); use V; Vec : aliased Vector := Empty_Vector & 1 & 2 & 3 & 4; T : Time; Sum : Long_Long_Integer; begin Put_Line ("Inserting elements into Vector .."); for I in 1 .. 1_000_0000 loop Vec.Append (I); end loop; Put_Line ("Iterating on regular vector .."); T := Clock; Sum := 0; for El of Vec loop El := El + 1; Sum := Sum + Long_Long_Integer (El); end loop; Put_Line ("SUM : " & Sum'Image); Put_Line ("Time = " & Duration'Image (Clock - T)); Put_Line ("Iterating on stable vector .."); T := Clock; Sum := 0; declare S : Stable.Vector (Vec'Access); begin for El of S loop El := El + 1; Sum := Sum + Long_Long_Integer (El); end loop; end; Put_Line ("SUM : " & Sum'Image); Put_Line ("Time = " & Duration'Image (Clock - T)); end Main; Has the following output: Inserting elements into Vector .. Iterating on regular vector .. SUM : 50000015000014 Time = 0.796831000 Iterating on stable vector .. SUM : 50000025000018 Time = 0.045607000 Several things: I spoke with Hristian, the guy in charge of implementing co-extensions in GNAT. He told me that the implementation was not complete and could still leak memory. It is my understanding that every operation that creates a vector in the Stable package is supposed to rely on the co-extension mechanism for finalization of the underlying Vector. Since this is not completely working in GNAT, probably not working at all in other compilers (Randy your input would be welcome here), I’m wary of basing memory management of a feature fix on co-extensions. For future reference, Hristian is also positive that co-extensions as currently implemented in GNAT do not allocate the sub-object graph in place, instead making new calls. GNAT already has an ad-hoc expansion mechanism devised by Bob Duff that does more or less the same thing as stable for for .. of loops. I had to disable it in my package to see the performance difference. *************************************************************** From: Tucker Taft Sent: Tuesday, October 4, 2016 11:23 AM > Here is an update on the stable containers AI. I don’t believe Raphael > had time to prototype this. > > So, I’m more or less done prototyping this, will clean up the code and > send it here when I’m done. Great! > The prototyped version provides the expected performance results. > Running this program: > > ... > > Has the following output: > > |Inserting elements into Vector .. Iterating on regular vector .. SUM > |: 50000015000014 Time > = 0.796831000 Iterating on stable vector .. SUM : 50000025000018 Time > = 0.045607000 | Nice! But should I be worried that they result in different SUM values??? > > Several things: > > 1. > > I spoke with Hristian, the guy in charge of implementing > co-extensions in GNAT. He told me that the implementation was not > complete and could still leak memory. It is my understanding that every > operation that creates a vector in the Stable package is supposed to > rely on the co-extension mechanism for finalization of the underlying > Vector. Since this is not completely working in GNAT, probably not > working at all in other compilers (Randy your input would be welcome > here), I’m wary of basing memory management of a feature fix on > co-extensions. Since Stable containers will need to be controlled anyway (to turn off the no-tampering flag), we can resort to explicit allocate and free for the underlying vector, if we don't trust co-extensions. The trick is to know whether the underlying vector should be deallocated as part of the finalization of the stable vector. So you will need to add a flag to the stable vector which indicates this. E.g. add a component: Boolean : Deallocate_Vector_On_Finalization := False; It needs to default to False so a Stable.Vector without an explicit initialization will know not to deallocate the vector it refers to. > 2. > > For future reference, Hristian is also positive that co-extensions as > currently implemented in GNAT do not allocate the sub-object graph in > place, instead making new calls. That doesn't surprise me. > 3. > > GNAT already has an ad-hoc expansion mechanism devised by Bob Duff > that does more or less the same thing as stable for for .. of loops. > I had to disable it in my package to see the performance difference. Right. That was the attempt to accomplish something similar without any language support. *************************************************************** From: Raphael Amiard Sent: Tuesday, October 4, 2016 11:26 AM > Salut Raphael. > Why does the summation differ in the two cases? Because I'm doing something idiotic, eg. incrementing every value of the vector by 1, both times over. Since it's the same underlying vector, the second summation is not the same. I added that to check which Reference_Type was used, will remove it now ! *************************************************************** From: Raphael Amiard Sent: Tuesday, October 4, 2016 11:27 AM ... > So you will need to add a > flag to the stable vector which indicates this. E.g. add a component: > > Boolean : Deallocate_Vector_On_Finalization := False; > > It needs to default to False so a Stable.Vector without an explicit > initialization will know not to deallocate the vector it refers to. Already implemented it like that, and realized at the end it should be handled by co-extensions :) *************************************************************** From: Randy Brukardt Sent: Tuesday, October 4, 2016 2:12 PM I'm confused. Why would you ever need to deallocate the underlying vector? I thought "stable" was just a wrapper around an *existing* vector. I wouldn't want "stable" to be creating/destroying regular vectors; that would seem to clobber any performance improvement. *************************************************************** From: Tucker Taft Sent: Tuesday, October 4, 2016 2:30 PM It is the functions that create stable vectors out of whole cloth, namely "To_Vector" and "Copy" (and for a little while also Empty_Vector). These are useful if you want a vector that is stable for its entire life: package Vecs is new Ada.Containers.Vector(Whatever); ... X : Vecs.Stable.Vector := Vecs.Stable.To_Vector(Length => 42); So Raphael was talking about functions that create (unstable) vectors as a side effect of creating a new stable vector. In the original proposal, we were using a "null" access discriminant for these, but that slows down all uses of every stable vector by first having to check whether the discriminant is null. This does impose a tiny bit of distributed overhead during finalization of a stable vector, to check this boolean flag, but that is almost certainly much less than the distributed overhead of checking for a null Base all over the place. *************************************************************** From: Raphael Amiard Sent: Wednesday, October 5, 2016 1:42 PM Here is my homework for this AI. [Find this in the grab bag: http://www.ada-auth.org/ai-files/grab_bag/stable-vectors.tgz] Conclusion from my point of view is that stable containers are pretty simple and understandable, and actually fix the problem they're designed for, so kudos ! Seems to me like we still need to do the AI about using stable containers by default for for .. of iterations, for the work to be complete. *************************************************************** From: Tucker Taft Sent: Wednesday, October 5, 2016 2:54 PM Thanks Raphaël for putting this together so quickly. Probably will want to define a new aspect rather than somehow treating a nested package called Stable as something magical. *************************************************************** From: Tucker Taft Sent: Monday, June 12, 2017 4:46 PM Update given below. [This is version /05 of the AI - Editor.] I repeated the full spec for Doubly_Linked_Lists.Stable, but then simplified later additions by describing the differences, rather than duplicating the spec. That might be the right way to do Vectors.Stable and Doubly_Linked_Lists.Stable as well. I tried two different ways to deal with tampering with elements. Probably we should pick one or the other. *************************************************************** From: Randy Brukardt Sent: Monday, June 12, 2017 7:16 PM > ... I tried two different ways to > deal with tampering with elements. Probably we should pick one or the > other. I only saw one, which clause used a different method than Vectors? Secondly, while you have a nice definition of tampering with elements and prohibiting tampering with elements in the Indefinite_Vector, I didn't see any text that defines what operations prohibit tampering with elements (since you changed the original definitions to "tampering with cursors"). Humm, actually, I can't find where you changed the original definitions. But you have to do that, as "tampering with elements" is no longer defined in A.18.2, so you can't use it in A.18.2. Otherwise, a quick check looks OK. *************************************************************** From: Tucker Taft Sent: Tuesday, June 13, 2017 3:46 AM ... > I only saw one, which clause used a different method than Vectors? For Maps, I left the definition of tampering with elements in the same place, but said it only applied if the Element_Type was indefinite. > Secondly, while you have a nice definition of tampering with elements > and prohibiting tampering with elements in the Indefinite_Vector, I > didn't see any text that defines what operations prohibit tampering > with elements (since you changed the original definitions to "tampering with cursors"). > Humm, actually, I can't find where you changed the original > definitions. But you have to do that, as "tampering with elements" is > no longer defined in A.18.2, so you can't use it in A.18.2. I left the wording about what disallows tampering with elements in A.18.2, presuming a forward reference. But I think the approach in Maps is probably better. *************************************************************** From: Randy Brukardt Sent: Tuesday, June 13, 2017 1:15 PM ... > > I only saw one, which clause used a different method than Vectors? > > For Maps, I left the definition of tampering with elements in the same > place, but said it only applied if the Element_Type was indefinite. I see. That would work, if you added some wording somewhere to say that if tampering with elements doesn't apply, then tampering with cursors does. The way you have it worded, one could interpret it as saying that there is no tampering check at all unless the element is indefinite. That's not what we agreed to. > > Secondly, while you have a nice definition of tampering with > > elements and prohibiting tampering with elements in the > > Indefinite_Vector, I didn't see any text that defines what > > operations prohibit tampering with elements (since you changed the > > original definitions to "tampering with cursors"). > > Humm, actually, I can't find where you changed the original > > definitions. But you have to do that, as "tampering with elements" > > is no longer defined in A.18.2, so you can't use it in A.18.2. > > I left the wording about what disallows tampering with elements in > A.18.2, presuming a forward reference. But I think the approach in > Maps is probably better. That doesn't make sense, IMHO. You have a use of a completely undefined term. And the problem I noted above still exists here as well: you need to say that something that is tampering with elements becomes tampering with cursors. I expected you to do neither of these things, rather doing what you did for A.18.2 (in deleting and adding text), then followed by changing the existing wording to "prohibits tampering with cursors" wherever it currently says "tampering with elements", and then in A.18.11 add something on the line of: * For Query_Element, Update_Element, ... , tampering with elements is prohibited whenever A.18.2 says that tampering with cursors is prohibited." That's the most work, but it's also crystal-clear what's going on, and it doesn't require defining terms in clauses where they aren't used (as in the Maps version), or any forward references. *************************************************************** From: Tucker Taft Sent: Wednesday, October 11, 2017 2:18 PM Here is an update on AI12-0111 -- adding a Stable sub package to most containers, and removing tampering with elements from "definite"-element-type containers. [This is version /06 of this AI - Editor.] *************************************************************** From: Randy Brukardt Sent: Wednesday, October 11, 2017 10:12 PM Comment: I don't think the Stable subpackage semantics can go at the end of A.18.2 (or any other clause), since that (depending on how literally you take "end") is a notes or Implementation Advice subsection. Perhaps you want it at the end of the "Static Semantics" subsection, or perhaps you want another "Static Semantics" header. (I'd go for the former.) This applies to all of the top-level items. Minor glitch: in A.18.12, the new paragraph dropping Replace_Element and Swap is not in the form of a bullet, which is the format of that subclause. I fixed this. Question: Why do we drop Replace_Element for Indefinite lists and Trees, but not Indefinite vectors, maps, or sets?? Glitch: The change to A.18.17 (Indefinite Trees) appears twice, at around line 620 and 1050. (Maybe you started to do the above for Maps and Sets and never finished it???) I deleted the extra copy. Comment: I think you need a sentence in the "regular" containers that says that tampering with elements is equivalent to tampering with cursors. You can sort of derive that from other rules, but it's a leap. Many of the operations of the regular containers prohibit tampering with elements, but there is no explicit definition of what that means there (only in the indefinite containers). Alternatively, you could have some sort of equivalence rule in the introduction "For containers with elements that aren't indefinite, tampering with elements is the same as tampering with cursors." *************************************************************** From: Randy Brukardt Sent: Thursday, October 18, 2018 11:53 PM Posting this [this is version /07 of the AI - Editor.] here as much so I can remember what is changed when we discuss this next week as any other reason. So attached is a new version of this AI. (1) Added an aspect Iterator_View to specify the view of a container to use for an "of" iterator (formally, a "container element iterator"). We specify this on each language-defined container to require the use of the stable view in such an iterator. This reduces the number of times that "tampering with cursors" is set and cleared from N to 1. We used an aspect since compiler authors would need to use some similar mechanism to tie the iterator to the stable view in any case, and it might be useful for users to use a similar mechanism in their own containers. For instance, a task-safe container might use an analog of a stable view to provide a view that is locked against writing while the iterator is executing. (2) Redid the text to leave all of the uses and definitions of "tampering with elements". What was changed was for all of the normal containers to change the definition of "tampering with elements" to be exactly the same as "tampering with cursors". (All of the indefinite containers already had the previous definition of "tampering with elements" - but see the next item.) (3) The text defining "tampering with elements" for the indefinite maps (two containers) was missing completely. Also added an AARM note to the indefinite sets (two containers) to explain why there is no such definition in them. (So future readers won't think that we made a mistake!) (4) For Maps and Sets, moved the definition of the Stable package to the shared part (it's the same for both kinds). (5) The definition of stabilized views had sentences in two different paragraphs saying that tampering is prohibited. Once is enough, I eliminated the extra one. (They even both started with "While a stabilized view exists...") (6) I modified the wording "except that no tampering checks are performed{ on stable <>}" so that there is a tampering check on the (non-stable) target of the stable Assign operation (also see the next item). We wouldn't want the tampering check to be skipped for some container just because the assignment source was a stable view. (7) Tucker had an item to "define Assign". The version of Assign in Stable that has a non-stable target is exactly as Assign is defined for the underlying container, so no special definition is needed. Tucker also had a version of assign whose target is a stable view. This operation is problematical, so I saved myself a bunch of work and deleted it everywhere. Specifically: (A) Changing the entire contents of a "stable" view seems pretty unstable. :-) This doesn't feel like a stable operation, which mostly would be reading and possibly simple modifications of a small part of an element. (B) Certainly, changing a stable view can't be allowed in an indefinite container, as the individual elements might change size. Excluding it is annoying as it is overloaded so just giving the name is not enough. (C) Assign is a tampering with cursors operation, and those are generally the operations excluded from Stable in the first place. (D) It is only allowed when the lengths match already. That would generally require creating an object with the right length -- but if one is going to do that, one could have used Copy to create the object and Assign is not needed. (E) Worst case if it is omitted, one can assign into a normal vector and then immediately create a stable view of it. That doesn't seem difficult for most code. (F) To avoid problems with (C), this Assign needs a special definition. It has to copy elements without doing any memory allocation/deallocation, reordering of elements, or any other operations that could cause trouble. Such a definition sounds reasonably complicated and could require a special implementation compared to other similar operations. (G) Tucker only defined this operation for Vectors and Lists, and omitted assign from the other kinds of containers. That's presumably because of issues with the structure associated. But the version with a normal container would work for all; so I added that to all of the Stable subpackages. All-in-all, this operation doesn't seem worth the trouble (especially as it only makes sense for two containers). If it turns out in practice to be an issue, we can define it in the Corrigendum that is almost certainly coming in 2023. --- (10) One thought that I did not pursue would be to define "tampering with elements" for bounded containers to be associated with *no* operations. Since the bounded containers do not (if the implementation advice is followed) ever allocate or deallocate memory when an object inserted or deleted, the problem that requires us to keep "tampering with cursors" for all unbounded container operations does not exist for bounded operations. (If we didn't check "tampering with cursors" for an unbounded definite container, a "tampering with cursors" scenario would have to be erronous for operations like Reference, which is a worse situation than would occur when writing the code explicitly.) For a bounded container, the worst thing that could happen would be that some mutable discriminant would change value, which is a situation that can happen for regular subprogram calls (and is declared erroneous). There'd be no new problem. We could do that fairly simply by adding something like the following to each bounded container: * A subprogram is never said to tamper with elements of a bounded vector object V. AARM Reason: The memory for a bounded container is not allocated or deallocated during normal operations. Therefore, an Update_Element routine (for example) can never be holding deallocated memory even if a tampering with cursors operation is called on the container. A discriminant might change, but that is already possible for any parameter of a mutable record type, and that case is covered by an erroneous execution rule in 3.7.2. We'd also have to add a rule for stabilized views to the same bounded containers: * While a stabilized view exists, any operation that tampers with cursors performed on the underlying tree is prohibited. since the primary goal is to make stable views safe for all operations without checks, and tampering checks are still needed for bounded containers to prevent iteration from going off into the weeds. I didn't do this as we haven't discussed it previously (it's possible that this was Tucker's original intent, but I don't know for sure), and it was a bunch more work (I've have to look up the paragraph numbers in each clause). I'm already way behind... *************************************************************** From: Randy Brukardt Sent: Thursday, December 6, 2018 11:53 PM We made no decision on AI12-0111-1 in Lexington as several people thought the specifications were too large for the value. I need to find out whether this AI is in or out so I can deal with inserting it (or not), and dealing with the conflicts with AI12-0112-1 (container contracts), all of which are likely to be very time-consuming. The sooner I have less I've spent 90 minutes crafting three alternative ways to present the stable packages in the RM. Option 1 is essentially the presentation as it currently is given in the draft AI. Option 2 is a primarily English definition. Option 3 is the same as option 2, reversing the polarity of the English (listing omitted subprograms rather than included ones). I note that option 3 is probably better that either option 1 or 2 for future maintenance, as it only requires modifying the stable text if a new routine that tampers with cursors/elements is added to the basic packages. Option 1 requires modifying the specification if a new routine that doesn't tamper is added (much more likely), while option 2 requires modifying the English in that case. There would be an additional possibility of simply identifying the routines by function ("those that don't tamper with elements"), but that would vary from the style of the rest of the containers packages (which always identify the subprograms by name), and I'd insist on the AARM note with the list anyway, so I don't think that would really help any. Regardless of the option selected, I'd like to get a feel from the group on note (2) at the bottom of each of these alternatives, which is whether the cursor-only versions of routines ought to be included (or not) in the stable packages. These have nasty contracts (which is why the container-cursor versions are defined in AI12-0112-1), and I rather think of them as obsolete (they can't be used in a parallel loop while checking is on, for instance). As such, leaving them out of the stable packages seems like we wouldn't be losing anything except perhaps a tiny bit of consistency. (It definitely simplifies the wording; I didn't try to figure out the wording to include them.) To be discussed at the meeting. =================== Option 1 attachment =================== The option currently in the RM for Ada.Containers.Vectors: Insert after A.18.2(79/2): [Author's note: Below, we have left in the original paragraph numbers from the Vector container because we thought they might be useful, and mostly because we are too lazy to remove them.] ... -- enclosing package Ada.Containers.Vectors package Stable is 8/3 type Vector (Base : not null access Vectors.Vector) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector); 9/2 type Cursor is private; pragma Preelaborable_Initialization(Cursor); 10/2 Empty_Vector : constant Vector; 11/2 No_Element : constant Cursor; 11.1/3 function Has_Element (Position : Cursor) return Boolean; 11.2/3 package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); 12/2 function "=" (Left, Right : Vector) return Boolean; 13/2 function To_Vector (Length : Count_Type) return Vector; 14/2 function To_Vector (New_Item : Element_Type; Length : Count_Type) return Vector; 15/2 function "&" (Left, Right : Vector) return Vector; 16/2 function "&" (Left : Vector; Right : Element_Type) return Vector; 17/2 function "&" (Left : Element_Type; Right : Vector) return Vector; 18/2 function "&" (Left, Right : Element_Type) return Vector; 19/2 function Capacity (Container : Vector) return Count_Type; 21/2 function Length (Container : Vector) return Count_Type; 23/2 function Is_Empty (Container : Vector) return Boolean; 25/2 function To_Cursor (Container : Vector; Index : Extended_Index) return Cursor; 26/2 function To_Index (Position : Cursor) return Extended_Index; 27/2 function Element (Container : Vector; Index : Index_Type) return Element_Type; 28/2 function Element (Position : Cursor) return Element_Type; 29/2 procedure Replace_Element (Container : in out Vector; Index : in Index_Type; New_Item : in Element_Type); 30/2 procedure Replace_Element (Container : in out Vector; Position : in Cursor; New_item : in Element_Type); 31/2 procedure Query_Element (Container : in Vector; Index : in Index_Type; Process : not null access procedure (Element : in Element_Type)); 32/2 procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type)); 33/2 procedure Update_Element (Container : in out Vector; Index : in Index_Type; Process : not null access procedure (Element : in out Element_Type)); 34/2 procedure Update_Element (Container : in out Vector; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type)); 34.1/3 type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; 34.2/3 type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; 34.3/3 function Constant_Reference (Container : aliased in Vector; Index : in Index_Type) return Constant_Reference_Type; 34.4/3 function Reference (Container : aliased in out Vector; Index : in Index_Type) return Reference_Type; 34.5/3 function Constant_Reference (Container : aliased in Vector; Position : in Cursor) return Constant_Reference_Type; 34.6/3 function Reference (Container : aliased in out Vector; Position : in Cursor) return Reference_Type; 34.7/3 procedure Assign (Target : in out Vectors.Vector; Source : in Vector); 34.8/3 function Copy (Source : Vector) return Vector; function Copy (Source : Vectors.Vector) return Vector; 54/2 procedure Reverse_Elements (Container : in out Vector); 55/2 procedure Swap (Container : in out Vector; I, J : in Index_Type); 56/2 procedure Swap (Container : in out Vector; I, J : in Cursor); 57/2 function First_Index (Container : Vector) return Index_Type; 58/2 function First (Container : Vector) return Cursor; 59/2 function First_Element (Container : Vector) return Element_Type; 60/2 function Last_Index (Container : Vector) return Extended_Index; 61/2 function Last (Container : Vector) return Cursor; 62/2 function Last_Element (Container : Vector) return Element_Type; 63/2 function Next (Position : Cursor) return Cursor; 64/2 procedure Next (Position : in out Cursor); 65/2 function Previous (Position : Cursor) return Cursor; 66/2 procedure Previous (Position : in out Cursor); 67/2 function Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'First) return Extended_Index; 68/2 function Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 69/2 function Reverse_Find_Index (Container : Vector; Item : Element_Type; Index : Index_Type := Index_Type'Last) return Extended_Index; 70/2 function Reverse_Find (Container : Vector; Item : Element_Type; Position : Cursor := No_Element) return Cursor; 71/2 function Contains (Container : Vector; Item : Element_Type) return Boolean; 73/2 procedure Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor)); 74/2 procedure Reverse_Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor)); 74.1/3 function Iterate (Container : in Vector) return Vector_Iterator_Interfaces.Reversible_Iterator'Class; 74.2/3 function Iterate (Container : in Vector; Start : in Cursor) return Vector_Iterator_Interfaces.Reversible_Iterator'Class; 75/2 generic with function "<" (Left, Right : Element_Type) return Boolean is <>; package Generic_Sorting is 76/2 function Is_Sorted (Container : Vector) return Boolean; 77/2 procedure Sort (Container : in out Vector); 79/2 end Generic_Sorting; 80/2 private 81/2 ... -- not specified by the language 82/2 end Stable; Insert the following at the end of A.18.2: The nested package Vectors.Stable provides a type Stable.Vector that represents a /stable/ vector, which is one that cannot grow and shrink. Such a vector can be created by calling the To_Vector or Copy functions, or by establishing a /stabilized view/ of a regular Vector. The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors. If a stable vector is declared with the Base discriminant designating a pre-existing regular vector, the stable vector represents a stabilized view of the underlying regular vector, and any operation on the stable vector is reflected on the underlying regular vector. While a stabilized view exists, any operation that tampers with elements performed on the underlying vector is prohibited. The finalization of a stable vector that provides such a view removes this restriction on the underlying regular vector Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable vector is declared without specifying Base, the object must be initialized. The initializing expression of the stable vector, Redundant[typically a call on To_Vector or Copy], determines the Length of the vector. By default the Length is zero. The Length of a stable vector never changes after initialization. ----- end of option. (1) If AI12-0112-1 is adopted, * the text ", except that no tampering checks are performed on stable Vectors" will be deleted. * All of the routines in this package will need contracts added; the package itself might also need a contract. * The additional routines defined for type Vector in the base package will need to be added to the stable package. * The preconditions of the routines defined in the stable package would be modified from the version in the main package by omitting the following subexpressions: (if Tampering_With_Elements_Prohibited (Container) then raise Program_Error) and (if Tampering_With_Cursors_Prohibited (Container) then raise Program_Error) I'd intend to do that in AI12-0112-1, not here. (2) We ought to consider omitting the cursor-only operations from the stable packages. Assuming that AI12-0112-1 is approved, they would be available in both (Vector, Cursor) and (Cursor) forms. The Cursor forms necessarily have to access global vectors as the container is not a parameter; this makes the contract unusable for parallel constructs. (They also can't be used in prefix notation.) As such, it's probably best to consider these as obsolete. we could drop all of the following: function To_Index (Position : Cursor) return Extended_Index; function Element (Position : Cursor) return Element_Type; function Next (Position : Cursor) return Cursor; procedure Next (Position : in out Cursor); function Previous (Position : Cursor) return Cursor; procedure Previous (Position : in out Cursor); ========================= Option 2 attachment ========================= This option uses English to describe the routines that take and return Vectors in the stable subpackage. We include the type declarations and the unique subprograms with normal specifications. Note that there is no similar, partially specified package in the Standard, so there is no model to follow. Insert after A.18.2(79/2): ... -- enclosing package Ada.Containers.Vectors package Stable is type Vector (Base : not null access Vectors.Vector) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector); type Cursor is private; pragma Preelaborable_Initialization(Cursor); Empty_Vector : constant Vector; No_Element : constant Cursor; function Has_Element (Position : Cursor) return Boolean; package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); procedure Assign (Target : in out Vectors.Vector; Source : in Vector); function Copy (Source : Vectors.Vector) return Vector; type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; -- Additional subprograms as described in the text are declared -- here. 80/2 private 81/2 ... -- not specified by the language 82/2 end Stable; Insert the following at the end of A.18.2: The nested package Vectors.Stable provides a type Stable.Vector that represents a /stable/ vector, which is one that cannot grow and shrink. Such a vector can be created by calling the To_Vector or Copy functions, or by establishing a /stabilized view/ of a regular Vector. The following subprograms of package Containers.Vectors that have a parameter or result of type Vector are included in the nested package Stable with the same specification: "=", To_Vector, "&", Capacity, Length, Is_Empty, To_Cursor, To_Index, Element, Replace_Element, Query_Element, Update_Element, Constant_Reference, Reference, Copy, Reverse_Elements. Swap, First_Index, First, First_Element, Last_Index, Last, Last_Element, Next, Previous, Find_Index, Find, Reverse_Find_Index, Reverse_Find, Contains, Iterate, and Reverse_Iterate. Generic package Generic_Sorting is also included with the same specification. AARM Ramification: The names Vector and Cursor mean the types declared in the nested package in these subprogram specifications. AARM Reason: The included routines are those that do not tamper with elements. The model is that it is impossible to tamper with elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view. The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors. If a stable vector is declared with the Base discriminant designating a pre-existing regular vector, the stable vector represents a stabilized view of the underlying regular vector, and any operation on the stable vector is reflected on the underlying regular vector. While a stabilized view exists, any operation that tampers with elements performed on the underlying vector is prohibited. The finalization of a stable vector that provides such a view removes this restriction on the underlying regular vector Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable vector is declared without specifying Base, the object must be initialized. The initializing expression of the stable vector, Redundant[typically a call on To_Vector or Copy], determines the Length of the vector. By default the Length is zero. The Length of a stable vector never changes after initialization. ----- end of option. (1) If AI12-0112-1 is adopted: * All of the routines in this package will need contracts added; the package itself might also need a contract. * The additional routines defined for type Vector in the base package will need to be added to the stable package. * The text "The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors." would be replaced by (assuming AI12-0112-1 is adopted): The operations of this package are equivalent to those for regular Vectors, except that the following subexpressions are omitted from the preconditions: (if Tampering_With_Elements_Prohibited (Container) then raise Program_Error) and (if Tampering_With_Cursors_Prohibited (Container) then raise Program_Error) I'd intend to do that in AI12-0112-1, not here. (2) I've omitted the cursor-only operations from the stable forms. Assuming that AI12-0112-1 is approved, they would be available in both (Vector, Cursor) and (Cursor) forms. The Cursor forms necessarily have to access global vectors as the container is not a parameter; this makes the contract unusable for parallel constructs. As such, it's probably best to consider these as obsolete. If we want them anyway, we'd need to add the following to the Stable package, or add some additional English wording to get them: function To_Index (Position : Cursor) return Extended_Index; function Element (Position : Cursor) return Element_Type; function Next (Position : Cursor) return Cursor; procedure Next (Position : in out Cursor); function Previous (Position : Cursor) return Cursor; procedure Previous (Position : in out Cursor); (3) Assign should be omitted from the stable package of all forms whether or not it is considered tampering with elements. (But I think all forms do tamper with elements.) ========================= Option 3 attachment ========================= This option uses English to describe the routines that take and return Vectors in the stable subpackage. We include the type declarations and the unique subprograms with normal specifications. Note that there is no similar, partially specified package in the Standard, so there is no model to follow. This version describes the routines that are *not* included in the package. Insert after A.18.2(79/2): ... -- enclosing package Ada.Containers.Vectors package Stable is type Vector (Base : not null access Vectors.Vector) is tagged limited private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector); type Cursor is private; pragma Preelaborable_Initialization(Cursor); Empty_Vector : constant Vector; No_Element : constant Cursor; function Has_Element (Position : Cursor) return Boolean; package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); procedure Assign (Target : in out Vectors.Vector; Source : in Vector); function Copy (Source : Vectors.Vector) return Vector; type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element; type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element; -- Additional subprograms as described in the text are declared -- here. 80/2 private 81/2 ... -- not specified by the language 82/2 end Stable; Insert the following at the end of A.18.2: The nested package Vectors.Stable provides a type Stable.Vector that represents a /stable/ vector, which is one that cannot grow and shrink. Such a vector can be created by calling the To_Vector or Copy functions, or by establishing a /stabilized view/ of a regular Vector. The subprograms of package Containers.Vectors that have a parameter or result of type Vector are included in the nested package Stable with the same specification, except for the following: Assign, Move, Insert, Insert_Space, Clear, Delete, and Set_Length Generic package Generic_Sorting is also included with the same specification. AARM Ramification: The names Vector and Cursor mean the types declared in the nested package in these subprogram specifications. AARM Reason: The omitted routines are those that tamper with elements. The model is that it is impossible to tamper with elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view. The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors. If a stable vector is declared with the Base discriminant designating a pre-existing regular vector, the stable vector represents a stabilized view of the underlying regular vector, and any operation on the stable vector is reflected on the underlying regular vector. While a stabilized view exists, any operation that tampers with elements performed on the underlying vector is prohibited. The finalization of a stable vector that provides such a view removes this restriction on the underlying regular vector Redundant[(though some other restriction might exist due to other concurrent iterations or stabilized views)]. If a stable vector is declared without specifying Base, the object must be initialized. The initializing expression of the stable vector, Redundant[typically a call on To_Vector or Copy], determines the Length of the vector. By default the Length is zero. The Length of a stable vector never changes after initialization. ----- end of option. (1) If AI12-0112-1 is adopted: * All of the routines in this package will need contracts added; the package itself might also need a contract. * The additional routines defined for type Vector in the base package will need to be added to the stable package. * The text "The operations of this package are equivalent to those for regular Vectors, except that no tampering checks are performed on stable Vectors." would be replaced by (assuming AI12-0112-1 is adopted): The operations of this package are equivalent to those for regular Vectors, except that the following subexpressions are omitted from the preconditions: (if Tampering_With_Elements_Prohibited (Container) then raise Program_Error) and (if Tampering_With_Cursors_Prohibited (Container) then raise Program_Error) I'd intend to do that in AI12-0112-1, not here. (2) I've omitted the cursor-only operations from the stable forms. Assuming that AI12-0112-1 is approved, they would be available in both (Vector, Cursor) and (Cursor) forms. The Cursor forms necessarily have to access global vectors as the container is not a parameter; this makes the contract unusable for parallel constructs. As such, it's probably best to consider these as obsolete. If we want them anyway, we'd need to add the following to the Stable package, or add some additional English wording to get them: function To_Index (Position : Cursor) return Extended_Index; function Element (Position : Cursor) return Element_Type; function Next (Position : Cursor) return Cursor; procedure Next (Position : in out Cursor); function Previous (Position : Cursor) return Cursor; procedure Previous (Position : in out Cursor); (3) Assign should be omitted from the stable package of all forms whether or not it is considered tampering with elements. (But I think all forms do tamper with elements.) ***************************************************************