Version 1.21 of ai05s/ai05-0212-1.txt

Unformatted version of ai05s/ai05-0212-1.txt version 1.21
Other versions for file ai05s/ai05-0212-1.txt

!standard 7.6(4/1)          11-10-12 AI05-0212-1/14
!standard A.18.2(6/2)
!standard A.18.2(8/2)
!standard A.18.2(11/2)
!standard A.18.2(34/2)
!standard A.18.2(72/2)
!standard A.18.2(74/2)
!standard A.18.2(97/2)
!standard A.18.2(147/2)
!standard A.18.2(225/2)
!standard A.18.2(226/2)
!standard A.18.2(230/2)
!standard A.18.2(240/2)
!standard A.18.2(252/2)
!standard A.18.3(5/2)
!standard A.18.3(6/2)
!standard A.18.3(9/2)
!standard A.18.3(17/2)
!standard A.18.3(44/2)
!standard A.18.3(46/2)
!standard A.18.3(69/2)
!standard A.18.3(86/2)
!standard A.18.3(139/2)
!standard A.18.3(140/2)
!standard A.18.3(144/2)
!standard A.18.3(157/2)
!standard A.18.4(18/2)
!standard A.18.4(41/2)
!standard A.18.4(72/2)
!standard A.18.4(73/2)
!standard A.18.4(80/2)
!standard A.18.5(2/2)
!standard A.18.5(3/2)
!standard A.18.5(6/2)
!standard A.18.5(17/2)
!standard A.18.5(33/2)
!standard A.18.5(37/2)
!standard A.18.5(61/2)
!standard A.18.6(2/2)
!standard A.18.6(4/2)
!standard A.18.6(7/2)
!standard A.18.6(16/2)
!standard A.18.6(43/2)
!standard A.18.6(51/2)
!standard A.18.6(94/2)
!standard A.18.7(19/2)
!standard A.18.7(36/2)
!standard A.18.7(83/2)
!standard A.18.7(84/2)
!standard A.18.7(96/2)
!standard A.18.7(101/2)
!standard A.18.8(2/2)
!standard A.18.8(3/2)
!standard A.18.8(6/2)
!standard A.18.8(17/2)
!standard A.18.8(45/2)
!standard A.18.8(49/2)
!standard A.18.8(58/2)
!standard A.18.8(85/2)
!standard A.18.9(2/2)
!standard A.18.9(4/2)
!standard A.18.9(7/2)
!standard A.18.9(16/2)
!standard A.18.9(53/2)
!standard A.18.9(61/2)
!standard A.18.9(73/2)
!standard A.18.9(113/2)
!standard A.18.10(0)
!standard A.18.18(0)
!standard A.18.32(0)
!class Amendment 10-04-26
!status Amendment 2012 11-06-18
!status ARG Approved (by Letter Ballot) 9-0-2 11-05-16
!status work item 11-04-26
!status ARG Approved 8-0-0 11-03-17
!status work item 10-04-26
!status received 10-02-27
!priority Medium
!difficulty Medium
!subject Accessors and Iterators for Ada.Containers
!summary
(See proposal.)
!problem
We've defined a number of new features that potentially can improve the use of the containers libraries in AI05-0139-2, AI05-0142-4, AI05-0143-1, and AI05-0162-1. The containers ought to be updated to use these new features.
!proposal
Add accessors and iterators to the containers packages.
!wording
[Editor's note: The following is based on AI05-0139-2/07.]
Replace 7.6(4/1) with:
package Finalization is pragma Pure(Finalization);
[This changes this to a Pure package, and drops "Remote_Types" (which is implicit in Pure).]
Add the following with to each container package that has iterators:
with Ada.Iterator_Interfaces;
Modify the definition of the container types for each of the containers that has a cursor (with suitable substitutions for the names of types) as follows [note: Set does not have Variable_Indexing as it does not allow in-place modification of elements]:
type Vector is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector);
Move after constant No_Element:
function Has_Element (Position : Cursor) return Boolean;
Add following that:
package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
Add the following to each Ada.Containers package (other than the Queues packages, but including Indefinite_Holders) immediately after Update_Element (with suitable substitutions for the names of types):
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;
The types Constant_Reference_Type and Reference_Type need finalization.
The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
AARM Reason: It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.
Add the following to each Ada.Containers package that has a Cursor type immediately after the above (with suitable substitutions for the names of types) - exception: there is no Reference in package Sets [meta-rule: There is a Constant_Reference for each Query_Element; a Reference for each Update_Element]:
function Constant_Reference (Container : aliased in Vector; Position : in Cursor) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector; Position : in Cursor) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
The element designated by Position is not an empty element after successful completion of this operation. [This is only needed for the Vectors case. - ED]
Add the following to Ada.Containers.Vectors and its relatives:
function Constant_Reference (Container : aliased in Vector; Index : in Index_Type) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with an index value.
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector; Index : in Index_Type) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with an index value.
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
The element at position Index is not an empty element after successful completion of this operation.
Modify A.18.2(240/2):
Reading the value of an empty element by calling Element, Query_Element, Update_Element, {Constant_Reference, Reference,} Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a bounded error. The implementation may treat the element as having any normal value (see 13.9.1) of the element type, or raise Constraint_Error or Program_Error before modifying the vector.
Add the following to Ada.Containers.Hashed_Maps and the various other Map containers:
function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type;
This routine (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a key value.
Equivalent to Constant_Reference (Container, Find (Container, Key)).
function Reference (Container : aliased in out Map; Key : in Key_Type) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with an key value.
Equivalent to Reference (Container, Find (Container, Key)).
Add the following as inside of the Generic_Keys package for the various Set containers:
[Note: Reference_Type is also declared inside of package Generic_Keys.]
function Reference_Preserving_Key (Container : aliased in out Set; Position : in Cursor) return Reference_Type;
This function (combined with the Implicit_Dereference aspect) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference_Preserving_Key uses Key to save the key value K; then returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference_Preserving_Key exists and has not been finalized. When the object returned by Reference_PReserving_Key is finalized, a check is made if K determines the same equivalence class as that for the new element; if not, the element is removed from the set and Program_Error is propagated.
function Constant_Reference (Container : aliased in Set; Key : in Key_Type) return Constant_Reference_Type;
This routine (combined with the Implicit_Dereference aspect) provides a convenient way to gain read access to the individual elements of a container starting with a key value.
Equivalent to Constant_Reference (Container, Find (Container, Key)).
function Reference_Preserving_Key (Container : aliased in out Set; Key : in Key_Type) return Reference_Type;
This function (combined with the Implicit_Dereference aspect) provides a convenient way to gain read and write access to the individual elements of a container starting with an key value.
Equivalent to Reference_Preserving_Key (Container, Find (Container, Key)).
[Note: The versions for the set containers are unfortunately not primitive operations; therefore they cannot be used via the _Indexing magic nor can they be called with prefix notation. However, the reference semantics is operational, so the discriminant and .all can be omitted; and they're probably still easier to use than Update_Element. That seems like enough to justify defining them.]
Add the following to Ada.Containers.Indefinite_Holders and its relatives:
function Constant_Reference (Container : aliased in Holder) return Constant_Reference_Type;
This routine (combined with the Implicit_Dereference aspect) provides a convenient way to gain read access to the contained element of a holder container.
If Container is empty, Constraint_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the contained element. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Holder) return Reference_Type;
This function (combined with the Implicit_Dereference aspects) provides a convenient way to gain read and write access to the contained element of a holder container.
If Container is empty, Constraint_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the contained element. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
After the existing procedure Reverse_Iterate of each container that has Reverse_Iterate, add a new function:
function Iterate (Container : in Vector) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
[Note: This wording will need to be adjusted for containers that don't have Next, like Maps. The wording will be parallel to that of the existing Iterate procedure.]
After the above routine for various Vector and List containers, add a new function:
function Iterate (Container : in Vector; Start : in Cursor) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
if Start is not No_Element and does not designate an item in Container, then Program_Error is propagated. if Start is No_Element, the call is equivalent to Iterate (Container). Otherwise, Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
AARM Note: Exits are allowed from the loops created using the iterator objects. in particular, to stop the iteration at a particular cursor, just add exit when Cur = Stop; in the body of the loop (assuming the Cur is the loop parameter and Stop is the cursor that you want to stop at).
After the existing procedure Iterate of each container that does not have a procedure Reverse_Iterate (for example, Hashed_Sets), add a new function:
function Iterate (Container : in Set) return Set_Iterator_Interfaces.Forward_Iterator'Class;
Iterate returns an iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and moving the cursor as per the Next function. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
Instead of the above, the Multiway_Tree containers would have:
function Iterate (Container : in Tree) return Tree_Iterator_Interfaces.Forward_Iterator'Class;
Iterate returns an iterator object that will generate a value for the loop parameter designating each node in Container, starting with the root node and proceeding in a depth-first order. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
function Iterate_Subtree (Position : in Cursor) return Tree_Iterator_Interfaces.Forward_Iterator'Class;
Iterate_Subtree returns an iterator object that will generate a value for the loop parameter designating each element in the subtree rooted by the node designated by Position, starting with the node designated by Position and proceeding in a depth-first order. if Position equals No_Element, then Constraint_Error is propagated. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of the container in which the node designated by Position exists while the iterator object exists. The iterator object needs finalization.
function Iterate_Children (Container : in Tree; Parent : in Cursor) return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate_Children returns a reversible iterator object that will generate a value for the loop parameter designating each child node of Parent. if Parent equals No_Element, then Constraint_Error is propagated. if Parent does not designate a node in Container, then Program_Error is propagated. Otherwise, when used as a forward iterator, the nodes are designated starting with the first child node and moving the cursor as per the function Next_Sibling; when used as a reverse iterator, the nodes are designated starting with the last child node and moving the cursor as per the function Previous_Sibling. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
Add the following to the Erroneous Execution section of each (unbounded) container package:
Execution is erroneous if the vector associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
AARM Reason: Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a non-existent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)
Modify A.18.2(230/2), A.18.3(143/2), A.18.6(94/2), and A.18.9(113/2): "... as per {procedure} Iterate, ..." [Necessary as we are now adding Iterate functions, and this would then be ambiguous without the clarification.]
For each bounded container, delete AARM implementation note that says:
Package Containers.Bounded_Vectors cannot depend on package Ada.Finalization (because that package has Preelaborate categorization).
Add an AARM note after the bullet about when the container needs finalization:
Implementation Note: The type Vector cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.
Add a new clause at the end of the containers section: (Currently A.18.32)
A.18.32 Example of Container Use
The following example is an implementation of Dijkstra's shortest path algorithm in a directed graph with positive distances. The graph is represented by a map from nodes to sets of edges.
with Ada.Containers.Vectors; with Ada.Containers.Doubly_Linked_Lists; use Ada.Containers; generic type Node is range <>; package Shortest_Paths is type Distance is new Float range 0.0 .. Float'Last; type Edge is record To, From : Node; Length : Distance; end record;
package Node_Maps is new Vectors (Node, Node); -- The algorithm builds a map to indicate the node used to reach a given -- node in the shortest distance.
package Adjacency_Lists is new Doubly_Linked_Lists (Edge); use Adjacency_Lists;
package Graphs is new Vectors (Node, Adjacency_Lists.List);
package Paths is new Doubly_Linked_Lists (Node);
function Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List with Pre => G (Source) /= Adjacency_Lists.Empty_List;
end Shortest_Paths;
package body Shortest_Paths is function Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List is use Adjacency_Lists, Node_Maps, Paths, Graphs; Reached : array (Node) of Boolean := (others => False); -- The set of nodes whose shortest distance to the source is known.
Reached_From : array (Node) of Node; So_Far : array (Node) of Distance := (others => Distance'last); The_Path : Paths.List := Paths.Empty_List; Nearest_Distance : Distance; Next : Node; begin Reached (Source) := True; So_Far (Source) := 0.0;
while not Reached (Target) loop Nearest_Distance := Distance'Last;
-- Find closest node not reached yet, by iterating over all nodes. -- A more efficient algorithm uses a priority queue for this step.
Next := Source; for N in Node'First .. Node'Last loop if not Reached (N) and then So_Far (N) < Nearest_Distance then Next := N; Nearest_Distance := So_Far (N); end if; end loop;
if Next = Source then -- No next node found, graph is not connected return Paths.Empty_List;
else Reached (Next) := True; end if;
-- Update minimum distance to newly reachable nodes.
for E of G (Next) loop if not Reached (E.To) then Nearest_Distance := Distance'Min (So_Far (E.To) + So_Far (Next), So_Far (E.To));
if Nearest_Distance < So_Far (E.To) then Reached_From (E.To) := Next; So_Far (E.To) := Nearest_Distance; end if; end if; end loop; end loop;
-- Rebuild path from target to source.
declare N : Node := Target; begin while N /= Source loop N := Reached_From (N); Prepend (The_Path, N); end loop; end;
return The_Path; end; end Shortest_Paths;
Note that the effect of the Constant_Indexing aspect (on type Vector) and the Implicit_Dereference aspect (on type Reference_Type) is that
G (Next)
is a convenient short hand for
G.Constant_Reference (Next).Element.all
Similarly, the effect of the loop:
for E of G (Next) loop if not Reached (E.To) then ... end if; end loop;
is the same as:
for C in G (Next).Iterate loop declare E : Edge renames G (Next)(C).all; begin if not Reached (E.To) then ... end if; end; end loop;
which is the same as:
declare L : Adjacency_Lists.List renames G (Next); C : Adjacency_Lists.Cursor := L.First; begin while Has_Element (C) loop declare E : Edge renames L(C).all; begin if not Reached (E.To) then ... end if; end; C := L.Next (C); end loop; end;
!discussion
Note that the accessibility of the returned object from a call to Reference will prevent converting the returned access discriminant to any type that lives longer than the returned object. That means that we can assume that the discriminant value cannot be accessed after the object disappears (thus we can tie the tampering check to the lifetime of the returned object).
It is possible to use Unchecked_Deallocation to destroy the returned Reference_Type object prematurely, while continuing to use the returned access. The accessibility check on the container argument to the Reference function means that the returned access can't live longer than the container, but the use of Unchecked_Deallocation would allow tampering on the container. This could look like:
declare type AR is access MV.Reference_Type; procedure Free is new Ada.Unchecked_Deallocation (MV.Reference_Type, AR);
PAR : AR := new MV.Reference_Type'(Vect.Reference (1))
Element : access Element_Type := PAR.Element; -- OK.
begin Free (PAR); -- Tampering checking ends here!
Vect.Delete (1); -- No check here. ... Element.all ... -- Oops, gone. end;
Obviously, this is highly unlikely to happen by accident. This is more like shooting oneself in the foot by attaching a laser target to your foot and then firing a laser-seeking missile. It doesn't seem worth worrying about someone who wants to go to these lengths to avoid a tampering check - they're just as likely to use Unchecked_Conversion or .all'Unchecked_Access or something else nasty.
---
We need to be able to define the period of existence of the return object of the accessor as a time when tampering with elements is prohibited. If we didn't do this, we would be opening the door to all manner of problems (up to and including erroneousness) if an element is added or deleted to the container.
To see how this could happen, consider the following example:
Assume that Ada.Containers.Vectors has an accessor function defined as follows:
function Reference (C : aliased in out Vector; I : Index_Type) return access Element_Type;
Now consider the following program fragments:
package Data is type Node (D : Boolean := True) is record case D is when True => CT : Natural; when False => CF : Float; end case; end record; subtype True_Node is Node (D => True); subtype False_Node is Node (D => False);
package Node_Vector is new Ada.Containers.Vectors (Element_Type => Node, Index_Type => Positive);
Node_List : Node_Vector.Vector; end Data;
with Data; package Far_Away is procedure Some_Complex_Operation (...); end Far_Away;
package body Far_Away is procedure Some_Complex_Operation (...) is Some_Index : Positive; begin ... Some_Index := <lengthy-computation-resulting-in-value-of-1>; ... Data.Node_List.Delete (Some_Index); ... end Some_Complex_Operation; end Far_Away;
with Data; package Process is procedure Process_True (NT : in out Data.True_Node); end Process;
with Far_Away; package body Process is procedure Process_True (NT : in out Data.True_Node) is Component : renames NT.CT; -- OK, NT is constrained. begin ... Far_Away.Some_Complex_Operation (...); if Component > 10 then -- ** Oh-oh!! Component has moved. ... end if; end Process_True; end Process;
with Data, Process; procedure Main is begin Data.Node_List.Append (New_Item => (D => False, CF => 1.0)); -- Element 1. Data.Node_List.Append (New_Item => (D => True, CT => 4)); -- Element 2. Data.Node_List.Append (New_Item => (D => False, CF => 26.5)); -- Element 3. ... Process.Process_True (Data.Node_List.Reference (2).all); ... end Main;
In the canonical implementation for a vector, all of the data is stored in an array of some size, and when a component is deleted, the rest of them slide down. So, when the Far_Away operation (probably called through many levels of calls) deletes the first element of the vector, all of the rest of them move. That means that the second element passed to Process_True unexpectedly changes its value to that which was in the third element. But that element doesn't match the constraint and doesn't even have a CT component! So we get erroneous behavior. Note that the same thing would happen if an element was inserted at the front of the vector.
Note that in this example no one has copied the access value returned by the accessor. So a rule preventing copying does no good. You can also get a similar effect by renaming the access value itself and doing bad things while the renames exists.
Note that the erroneousness can't happen if you use Update_Element instead, because the tampering check will cause the deletion to raise Program_Error. Similarly, cursors have rules allowing implementations to detect this sliding and raise Program_Error.
This example code seems plausible; the record type is similar to many found in the author's compiler and using a library-level container is not unusual. So it seems reasonable that cases like this would happen in practice. Thus we conclude that a tampering check is needed for the accessor functions.
!examples
The new Reference function can be used to update an element directly. For example (based on a recent example from comp.lang.ada):
with Ada.Containers.Vectors; procedure Check is package Integer_Vectors is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Integer);
package Nested_Vectors is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Integer_Vectors.Vector, "=" => Integer_Vectors."=");
IV : Integer_Vectors.Vector; NV : Nested_Vectors.Vector; begin IV.Append(42); NV.Append(IV); NV.Reference(0).Element.all.Append(43); end Check;
The dereference does not need to be explicitly given in this case, and the fact that the object returned by Reference is limited and (probably) controlled is not visible in the code as the function call is used directly as a prefix. So the call can be just:
NV.Reference(0).Element.Append(43);
The "Implicit_Dereference" aspect of the returned object allows us to drop the ".Element" as well. That leave us with:
NV.Reference(0).Append(43);
Since containers have the "Variable_Indexing" aspect set to the Reference function, directly indexing the container is equivalent to a call to Reference. So we also could have written:
NV(0).Append(43);
This is essentially the same as what we could have written had the type of NV been an array type.
You could also save the entire object as long as needed:
declare My_IV : Nested_Vectors.Reference_Type := NV.Reference(0); -- Or just NV(0). begin
(since My_NV would be built-in-place).
Note that this design still works as intended even if the user renames only the discriminant access value:
declare My_IV : Integer_Vectors.Vector renames NV.Reference(0).Element.all; begin
Even in this case, the wrapping (probably controlled) object still is protecting the container, because the master of the returned object is the master of the renames: it will stick around as long as the renames does.
Moreover, splitting the access from the object usually isn't possible:
declare My_IV : access Integer_Vectors.Vector := NV.Reference(0).Element; -- Illegal! begin
This is illegal because the accessibility check fails. The (anonymous) object returned here will have the master of the expression (as a prefix, the special "directly initializing" rule does not apply to this function call), which is shorter than the master of the declaration of My_IV. Thus the accessibility check preventing shorter lifetimes will fail.
It is OK to rename the access:
declare My_IV : access Integer_Vectors.Vector renames NV.Reference(0).Element; begin
as in this case, the anonymous object will continue to exist until the renames is finalized.
This element can be passed as a parameter, as again the wrapping object will live as long as the parameter:
Operate (NV.Reference(0).Element);
or
Munge (NV.Reference(0).Element.all);
For Maps, we define indexing by the key as well as by cursors. So if we have:
type Point is record X, Y : Natural; end record; package Point_Maps is new Ada.Containers.Indefinite_Ordered_Maps (String, Point);
Locations : Point_Maps.Map;
Locations.Insert ("Tucker", (X | Y => 0)); Locations.Insert ("Randy", (X => 10, Y => 5)); Locations.Insert ("Steve", (X | Y => 20)); Locations.Insert ("John", (X => 50, Y => 100));
we can reference the elements directly via the keys (again we're using the Variable_Indexing aspect to simplify the calls):
if Locations("Randy").X > 10 then ... if Locations("Tucker").all = (X | Y => 0) then ... Locations ("Steve").X := 15; Locations ("John").all := (X | Y => 60);
The iterator functions can be used directly in a for loop:
for C in My_Vector.Iterator loop if My_Vector(C).B then My_Vector(C).Cnt := My_Vector(C).Cnt + 1; end if; end loop;
Note that the Reference and Constant_Reference functions (implicitly called above) are very helpful in writing the body of this sort of loop.
When reasonable, the keyword "reverse" is supported with the usual meaning:
for C in reverse My_Vector.Iterator loop
Containers have the "Iterator" function as their default iterator. This is always the iterator that unconditionally iterates the entire contents of the container. These iterators can be used with the "of" syntax to directly access the elements of a container. This means that the first loop above can be written:
for E of My_Vector loop if E.B then E.Cnt := E.Cnt + 1; end if; end loop;
Note however that the cursor form is more powerful. For instance, for a Map, the default iterator can only access the elements and not the keys, while the cursor form can access both. Similarly, for a tree, the element form does not allow the loop body to know where in the tree the element exists; the cursor form allows querying Depth, Parent, and many other useful functions.
!corrigendum 7.6(4/2)
Replace the paragraph:
package Ada.Finalization is pragma Preelaborate(Finalization); pragma Remote_Types(Finalization);
by:
package Ada.Finalization is pragma Pure(Finalization);
!corrigendum A.18.2(6/2)
Replace the paragraph:
generic type Index_Type is range <>; type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Vectors is pragma Preelaborate(Vectors);
by:
with Ada.Iterator_Interfaces; generic type Index_Type is range <>; type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Vectors is pragma Preelaborate(Vectors);
!corrigendum A.18.2(8/2)
Replace the paragraph:
type Vector is tagged private; pragma Preelaborable_Initialization(Vector);
by:
type Vector is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Vector);
!corrigendum A.18.2(11/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.2(34/2)
Insert after the paragraph:
procedure Update_Element (Container : in out Vector; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type));
the new paragraphs:
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;
function Constant_Reference (Container : aliased in Vector; Index : in Index_Type) return Constant_Reference_Type;
function Reference (Container : aliased in out Vector; Index : in Index_Type) return Reference_Type;
function Constant_Reference (Container : aliased in Vector; Position : in Cursor) return Constant_Reference_Type;
function Reference (Container : aliased in out Vector; Position : in Cursor) return Reference_Type;
!corrigendum A.18.2(72/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.2(74/2)
Insert after the paragraph:
procedure Reverse_Iterate (Container : in Vector; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in Vector) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in Vector; Start : in Cursor) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
!corrigendum A.18.2(97/2)
Insert after the paragraph:
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.2(147/2)
Insert after the paragraph:
The element designated by Position is not an empty element after successful completion of this operation.
the new paragraphs:
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;
The types Constant_Reference_Type and Reference_Type need finalization.
The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in Vector; Index : in Index_Type) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with an index value.
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector; Index : in Index_Type) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with an index value.
If Index is not in the range First_Index (Container) .. Last_Index (Container), then Constraint_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element at position Index. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
The element at position Index is not an empty element after successful completion of this operation.
function Constant_Reference (Container : aliased in Vector; Position : in Cursor) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Vector; Position : in Cursor) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
The element designated by Position is not an empty element after successful completion of this operation.
!corrigendum A.18.2(225/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.2(226/2)
Delete the paragraph:
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.2(230/2)
Replace the paragraph:
Iterates over the elements in Container as per Iterate, except that elements are traversed in reverse index order.
@ddy
Iterates over the elements in Container as per procedure Iterate, except that elements are traversed in reverse index order.
function Iterate (Container : in Vector) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
function Iterate (Container : in Vector; Start : in Cursor) return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
If Start is not No_Element and does not designate an item in Container, then Program_Error is propagated. If Start is No_Element, the call is equivalent to Iterate (Container). Otherwise, Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.2(240/2)
Replace the paragraph:
Reading the value of an empty element by calling Element, Query_Element, Update_Element, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a bounded error. The implementation may treat the element as having any normal value (see 13.9.1) of the element type, or raise Constraint_Error or Program_Error before modifying the vector.
by:
Reading the value of an empty element by calling Element, Query_Element, Update_Element, Constant_Reference, Reference, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a bounded error. The implementation may treat the element as having any normal value (see 13.9.1) of the element type, or raise Constraint_Error or Program_Error before modifying the vector.
!corrigendum A.18.2(252/2)
Insert after the paragraph:
The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Vectors is called with an invalid cursor parameter.
the new paragraph:
Execution is erroneous if the vector associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
!corrigendum A.18.3(5/2)
Replace the paragraph:
generic type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Doubly_Linked_Lists is pragma Preelaborate(Doubly_Linked_Lists);
by:
with Ada.Iterator_Interfaces; generic type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Doubly_Linked_Lists is pragma Preelaborate(Doubly_Linked_Lists); pragma Remote_Types(Doubly_Linked_Lists);
!corrigendum A.18.3(6/2)
Replace the paragraph:
type List is tagged private; pragma Preelaborable_Initialization(List);
by:
type List is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(List);
!corrigendum A.18.3(9/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package List_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.3(17/2)
Insert after the paragraph:
procedure Update_Element (Container : in out List; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type));
the new paragraphs:
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;
function Constant_Reference (Container : aliased in List; Position : in Cursor) return Constant_Reference_Type;
function Reference (Container : aliased in out List; Position : in Cursor) return Reference_Type;
!corrigendum A.18.3(44/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.3(46/2)
Insert after the paragraph:
procedure Reverse_Iterate (Container : in List; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in List) return List_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in List; Start : in Cursor) return List_Iterator_Interfaces.Reversible_Iterator'Class;
!corrigendum A.18.3(69/2)
Insert after the paragraph:
the new paragraph:
function Has_Element (Position : Cursor) return Boolean;
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.3(86/2)
Insert after the paragraph:
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
the new paragraphs:
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;
The types Constant_Reference_Type and Reference_Type need finalization.
The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in List; Position : in Cursor) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out List; Position : in Cursor) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
!corrigendum A.18.3(139/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.3(140/2)
Delete the paragraph:
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.3(144/2)
Replace the paragraph:
Iterates over the elements in Container as per Iterate, except that elements are traversed in reverse index order.
by:
Iterates over the elements in Container as per procedure Iterate, except that elements are traversed in reverse index order.
function Iterate (Container : in List) return List_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
function Iterate (Container : in List; Start : in Cursor) return List_Iterator_Interfaces.Reversible_Iterator'Class;
If Start is not No_Element and does not designate an item in Container, then Program_Error is propagated. If Start is No_Element, the call is equivalent to Iterate (Container). Otherwise, Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.3(157/2)
Insert after the paragraph:
The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Doubly_Linked_Lists is called with an invalid cursor parameter.
the new paragraph:
Execution is erroneous if the list associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
!corrigendum A.18.4(19/2)
Insert after the paragraph:
Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
the new paragraph:
function Has_Element (Position : Cursor) return Boolean;
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.4(41/2)
Insert after the paragraph:
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
the new paragraph:
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;
The types Constant_Reference_Type and Reference_Type need finalization.
The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in Map; Position : in Cursor) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Map; Position : in Cursor) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.
function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a key value.
Equivalent to Constant_Reference (Container, Find (Container, Key)).
function Reference (Container : aliased in out Map; Key : in Key_Type) return Reference_Type;
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a key value.
Equivalent to Reference (Container, Find (Container, Key)).
!corrigendum A.18.4(72/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.4(73/2)
Delete the paragraph:
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.4(80/2)
Insert after the paragraph:
The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps is called with an invalid cursor parameter.
the new paragraph:
Execution is erroneous if the map associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
!corrigendum A.18.5(2/2)
Replace the paragraph:
generic type Key_Type is private; type Element_Type is private; with function Hash (Key : Key_Type) return Hash_Type; with function Equivalent_Keys (Left, Right : Key_Type) return Boolean; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Hashed_Maps is pragma Preelaborate(Hashed_Maps);
by:
with Ada.Iterator_Interfaces; generic type Key_Type is private; type Element_Type is private; with function Hash (Key : Key_Type) return Hash_Type; with function Equivalent_Keys (Left, Right : Key_Type) return Boolean; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Hashed_Maps is pragma Preelaborate(Hashed_Maps); pragma Remote_Types(Hashed_Maps);
!corrigendum A.18.5(3/2)
Replace the paragraph:
type Map is tagged private; pragma Preelaborable_Initialization(Map);
by:
type Map is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Map);
!corrigendum A.18.5(6/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.5(17/2)
Insert after the paragraph:
procedure Update_Element (Container : in out Map; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));
the new paragraphs:
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;
function Constant_Reference (Container : aliased in Map; Position : in Cursor) return Constant_Reference_Type;
function Reference (Container : aliased in out Map; Position : in Cursor) return Reference_Type;
function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type;
function Reference (Container : aliased in out Map; Key : in Cursor) return Reference_Type;
!corrigendum A.18.5(33/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.5(37/2)
Insert after the paragraph:
procedure Iterate (Container : in Map; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in Map) return Map_Iterator_Interfaces.Forward_Iterator'Class;
!corrigendum A.18.5(61/2)
Insert after the paragraph:
Equivalent to Equivalent_Keys (Left, Key (Right)).
the new paragraphs:
function Iterate (Container : in Map) return Map_Iterator_Interfaces.Forward_Iterator'Class;
Iterate returns an iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and and moving the cursor according to the successor relation. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.6(2/2)
Replace the paragraph:
generic type Key_Type is private; type Element_Type is private; with function "<" (Left, Right : Key_Type) return Boolean is <>; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Ordered_Maps is pragma Preelaborate(Ordered_Maps);
by:
with Ada.Iterator_Interfaces; generic type Key_Type is private; type Element_Type is private; with function "<" (Left, Right : Key_Type) return Boolean is <>; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Ordered_Maps is pragma Preelaborate(Ordered_Maps); pragma Remote_Types(Ordered_Maps);
!corrigendum A.18.6(4/2)
Replace the paragraph:
type Map is tagged private; pragma Preelaborable_Initialization(Map);
by:
type Map is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Map);
!corrigendum A.18.6(7/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.6(16/2)
Insert after the paragraph:
procedure Update_Element (Container : in out Map; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));
the new paragraphs:
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;
function Constant_Reference (Container : aliased in Map; Position : in Cursor) return Constant_Reference_Type;
function Reference (Container : aliased in out Map; Position : in Cursor) return Reference_Type;
function Constant_Reference (Container : aliased in Map; Key : in Key_Type) return Constant_Reference_Type;
function Reference (Container : aliased in out Map; Key : in Cursor) return Reference_Type;
!corrigendum A.18.6(43/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.6(46/2)
Insert after the paragraph:
procedure Reverse_Iterate (Container : in Map; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class;
!corrigendum A.18.6(94/2)
Replace the paragraph:
Iterates over the elements in Container as per Iterate, except that elements are traversed in predecessor order, starting with the last node.
by:
Iterates over the elements in Container as per procedure Iterate, except that elements are traversed in predecessor order, starting with the last node.
function Iterate (Container : in Map) return Map_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each node in Container, starting with the first node and moving the cursor according to the successor relation when used as a forward iterator, and starting with the last node and moving the cursor according to the predecessor relation when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.7(18/2)
Insert after the paragraph:
Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
the new paragraph:
function Has_Element (Position : Cursor) return Boolean;
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.7(36/2)
Insert after the paragraph:
If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Query_Element calls Process.all with the element designated by Position as the argument. Program_Error is propagated if Process.all tampers with the elements of Container. Any exception raised by Process.all is propagated.
the new paragraphs:
type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element;
The type Constant_Reference_Type needs finalization.
The default initialization of an object of type Constant_Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in Set; Position : in Cursor) return Constant_Reference_Type;
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.
!corrigendum A.18.7(83/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.7(84/2)
Delete the paragraph:
Returns True if Position designates an element, and returns False otherwise.
!corrigendum A.18.7(96/2)
Insert after the paragraph:
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
the new paragraphs:
type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element;
The type Reference_Type needs finalization.
The default initialization of an object of type Reference_Type propagates Program_Error.
function Reference_Preserving_Key (Container : aliased in out Set; Position : in Cursor) return Reference_Type;
This function (combined with the Implicit_Dereference aspect) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.
If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference_Preserving_Key uses Key to save the key value K; then returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference_Preserving_Key exists and has not been finalized. When the object returned by Reference_PReserving_Key is finalized, a check is made if K determines the same equivalence class as that for the new element; if not, the element is removed from the set and Program_Error is propagated.
function Constant_Reference (Container : aliased in Set; Key : in Key_Type) return Constant_Reference_Type;
This function (combined with the Implicit_Dereference aspect) provides a convenient way to gain read access to the individual elements of a container starting with a key value.
Equivalent to Constant_Reference (Container, Find (Container, Key)).
function Reference_Preserving_Key (Container : aliased in out Set; Key : in Key_Type) return Reference_Type;
This function (combined with the Implicit_Dereference aspect) provides a convenient way to gain read and write access to the individual elements of a container starting with a key value.
Equivalent to Reference_Preserving_Key (Container, Find (Container, Key)).
!corrigendum A.18.7(101/2)
Insert after the paragraph:
The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Hashed_Sets or Containers.Ordered_Sets is called with an invalid cursor parameter.
the new paragraph:
Execution is erroneous if the set associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
!corrigendum A.18.8(2/2)
Replace the paragraph:
generic type Element_Type is private; with function Hash (Element : Element_Type) return Hash_Type; with function Equivalent_Elements (Left, Right : Element_Type) return Boolean; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Hashed_Sets is pragma Preelaborate(Hashed_Sets);
by:
with Ada.Iterator_Interfaces; generic type Element_Type is private; with function Hash (Element : Element_Type) return Hash_Type; with function Equivalent_Elements (Left, Right : Element_Type) return Boolean; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Hashed_Sets is pragma Preelaborate(Hashed_Sets); pragma Remote_Types(Hashed_Sets);
!corrigendum A.18.8(3/2)
Replace the paragraph:
type Set is tagged private; pragma Preelaborable_Initialization(Set);
by:
type Set is tagged private with Constant_Indexing => Constant_Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Set);
!corrigendum A.18.8(6/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package Set_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.8(17/2)
Insert after the paragraph:
procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type));
the new paragraphs:
type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element;
function Constant_Reference (Container : aliased in Set; Position : in Cursor) return Constant_Reference_Type;
!corrigendum A.18.8(45/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.8(49/2)
Insert after the paragraph:
procedure Iterate (Container : in Set; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in Set) return Set_Iterator_Interfaces.Forward_Iterator'Class;
!corrigendum A.18.8(58/2)
Insert after the paragraph:
procedure Update_Element_Preserving_Key (Container : in out Set; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));
the new paragraphs:
type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element;
function Reference_Preserving_Key (Container : aliased in out Set; Position : in Cursor) return Reference_Type;
function Constant_Reference (Container : aliased in Set; Key : in Key_Type) return Constant_Reference_Type;
function Reference_Preserving_Key (Container : aliased in out Set; Key : in Cursor) return Reference_Type;
!corrigendum A.18.8(85/2)
Insert after the paragraph:
Equivalent to Equivalent_Elements (Left, Element (Right)).
the new paragraphs:
function Iterate (Container : in Set) return Map_Iterator_Interfaces.Forward_Iterator'Class;
Iterate returns an iterator object that will generate a value for the loop parameter designating each element in Container, starting with the first element and and moving the cursor according to the successor relation. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.9(2/2)
Replace the paragraph:
generic type Element_Type is private; with function "<" (Left, Right : Element_Type) return Boolean is <>; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Ordered_Sets is pragma Preelaborate(Ordered_Sets);
by:
with Ada.Iterator_Interfaces; generic type Element_Type is private; with function "<" (Left, Right : Element_Type) return Boolean is <>; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Ordered_Sets is pragma Preelaborate(Ordered_Sets); pragma Remote_Types(Ordered_Sets);
!corrigendum A.18.9(4/2)
Replace the paragraph:
type Set is tagged private; pragma Preelaborable_Initialization(Set);
by:
type Set is tagged private with Constant_Indexing => Constant_Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; pragma Preelaborable_Initialization(Set);
!corrigendum A.18.9(7/2)
Insert after the paragraph:
No_Element : constant Cursor;
the new paragraphs:
function Has_Element (Position : Cursor) return Boolean;
package Set_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
!corrigendum A.18.9(16/2)
Insert after the paragraph:
procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type));
the new paragraphs:
type Constant_Reference_Type (Element : not null access constant Element_Type) is private with Implicit_Dereference => Element;
function Constant_Reference (Container : aliased in Set; Position : in Cursor) return Constant_Reference_Type;
!corrigendum A.18.9(53/2)
Delete the paragraph:
function Has_Element (Position : Cursor) return Boolean;
!corrigendum A.18.9(61/2)
Insert after the paragraph:
procedure Reverse_Iterate (Container : in Set; Process : not null access procedure (Position : in Cursor));
the new paragraphs:
function Iterate (Container : in Set) return Set_Iterator_Interfaces.Reversible_Iterator'Class;
!corrigendum A.18.9(73/2)
Insert after the paragraph:
procedure Update_Element_Preserving_Key (Container : in out Set; Position : in Cursor; Process : not null access procedure (Key : in Key_Type; Element : in out Element_Type));
the new paragraphs:
type Reference_Type (Element : not null access Element_Type) is private with Implicit_Dereference => Element;
function Reference_Preserving_Key (Container : aliased in out Set; Position : in Cursor) return Reference_Type;
function Constant_Reference (Container : aliased in Set; Key : in Key_Type) return Constant_Reference_Type;
function Reference_Preserving_Key (Container : aliased in out Set; Key : in Cursor) return Reference_Type;
!corrigendum A.18.9(113/2)
Replace the paragraph:
Iterates over the elements in Container as per Iterate, except that elements are traversed in predecessor order, starting with the last element.
by:
Iterates over the elements in Container as per procedure Iterate, except that elements are traversed in predecessor order, starting with the last element.
function Iterate (Container : in Set) return Map_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns a reversible iterator object that will generate a value for the loop parameter designating each element in Container, starting with the first element and moving the cursor according to the successor relation when used as a forward iterator, and starting with the last element and moving the cursor according to the predecessor relation when used as a reverse iterator. Program_Error is propagated if any operation (in particular, the sequence_of_statements of the loop_statement whose iterator_specification denotes this object) tampers with the cursors of Container while the iterator object exists. The iterator object needs finalization.
!corrigendum A.18.10(0)
Insert new clause:
Force a conflict; the real text is in the conflict file.
!corrigendum A.18.18(0)
Insert new clause:
Force a conflict; the real text is in the conflict file.
!corrigendum A.18.32(0)
Insert new clause:
The following example is an implementation of Dijkstra's shortest path algorithm in a directed graph with positive distances. The graph is represented by a map from nodes to sets of edges.
with Ada.Containers.Vectors; with Ada.Containers.Doubly_Linked_Lists; use Ada.Containers; generic type Node is range <>; package Shortest_Paths is type Distance is new Float range 0.0 .. Float'Last; type Edge is record To, From : Node; Length : Distance; end record;
package Node_Maps is new Vectors (Node, Node); -- The algorithm builds a map to indicate the node used to reach a given -- node in the shortest distance.
package Adjacency_Lists is new Doubly_Linked_Lists (Edge); use Adjacency_Lists;
package Graphs is new Vectors (Node, Adjacency_Lists.List);
package Paths is new Doubly_Linked_Lists (Node);
function Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List with Pre => G (Source) /= Adjacency_Lists.Empty_List;
end Shortest_Paths;
package body Shortest_Paths is
function Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List is use Adjacency_Lists, Node_Maps, Paths, Graphs; Reached : array (Node) of Boolean := (others => False); -- The set of nodes whose shortest distance to the source is known.
Reached_From : array (Node) of Node; So_Far : array (Node) of Distance := (others => Distance'Last); The_Path : Paths.List := Paths.Empty_List; Nearest_Distance : Distance; Next : Node; begin Reached(Source) := True; So_Far(Source) := 0.0;
while not Reached(Target) loop Nearest_Distance := Distance'Last;
-- Find closest node not reached yet, by iterating over all nodes. -- A more efficient algorithm uses a priority queue for this step.
Next := Source; for N in Node'First .. Node'Last loop if not Reached(N) and then So_Far(N) < Nearest_Distance then Next := N; Nearest_Distance := So_Far(N); end if; end loop;
if Next = Source then -- No next node found, graph is not connected return Paths.Empty_List;
else Reached(Next) := True; end if;
-- Update minimum distance to newly reachable nodes.
for E of G (Next) loop if not Reached(E.To) then Nearest_Distance := Distance'Min (So_Far(E.To) + So_Far(Next), So_Far(E.To));
if Nearest_Distance < So_Far(E.To) then Reached_From(E.To) := Next; So_Far(E.To) := Nearest_Distance; end if; end if; end loop; end loop;
-- Rebuild path from target to source.
declare N : Node := Target; begin while N /= Source loop N := Reached_From(N); Prepend (The_Path, N); end loop; end;
return The_Path; end; end Shortest_Paths;
Note that the effect of the Constant_Indexing aspect (on type Vector) and the Implicit_Dereference aspect (on type Reference_Type) is that
G (Next)
is a convenient short hand for
G.Constant_Reference (Next).Element.all
Similarly, the effect of the loop:
for E of G (Next) loop if not Reached(E.To) then ... end if; end loop;
is the same as:
for C in G (Next).Iterate loop declare E : Edge renames G (Next)(C).all; begin if not Reached(E.To) then ... end if; end; end loop;
which is the same as:
declare L : Adjacency_Lists.List renames G (Next); C : Adjacency_Lists.Cursor := L.First; begin while Has_Element (C) loop declare E : Edge renames L(C).all; begin if not Reached(E.To) then ... end if; end; C := L.Next (C); end loop; end;
!ACATS test
ACATS tests would be needed for these changes.
!appendix

From: Randy Brukardt
Sent: Never (Written January 28, 2011)

Notes on version /03 (compared to the /02 discussed at the phone meeting):

The declaration of the container type does not need an interface because we
replaced that by an aspect several versions back in AI05-0139-2. Sorry about
having completely forgotten that. That simplifies the description and eliminates
the incompatibility that we talked about.

Used the name "Vector_Iterator_Interfaces" for the magic instance, as the
suggested name "Iterator_Implementation" doesn't make much sense.

Added notes about the Set implementation of the Reference and Constant_Reference
routines for Keys.

Added a sentence about the object returned from the various iterator functions
needing finalization.

Added a note that all of the bounded containers are Preelaborated, not Pure.
(This drops A.18.19(3/3) and similar bullets.)

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

From: Randy Brukardt
Sent: Monday, February  7, 2011  7:28 PM

Steve brings up an interesting question in some private mail: should the Ada
strings packages have changes to incorporate iterators  and indexing?
Presumably, we'd make those changes in this same AI.

Here is a list of the various changes and how they might be used in strings
packages:

Aspect Implicit_Dereference
   This doesn't make sense for the strings packages; we don't want to be making
   pointers at individual characters. Requiring the individual characters to be
   aliased to support this strategy could cause some implementations to waste a
   lot of memory (on a word-addressable machine in particular).

Aspect Constant_Indexing
   This maps nicely on the existing function Element for the Bounded and
   Unbounded strings. (Fixed strings, of course, already have this as an array
   type.) So I think we should consider adding this.

Aspect Variable_Indexing
   This maps to procedure Replace_Element, but not sensibly. The current scheme
   imagines that it maps to a function returning an access to an element (using
   reference) -- but using an access type doesn't make much sense in this
   context. Rather, we'd rather pass a value to a procedure to set the element.
   That of course would require some sort of change to the currently defined
   mechanism for Variable_Indexing. I'd guess that is too complicated to define,
   so I think it probably would make more sense to just forget this capability.
   (Whether this means we should forget about providing *read* access I can't
   say.)

Iterator interfaces
   These seem like overkill here, since the indexes are integers and iterating
   an entire object S just requires
       for I in 1..Length(S) loop
   But see the next item.

Aspects Default_Iterator and Iterator_Element
   These would be useful, as they would enable the string to be iterated with
   the container syntax:
       for Ch of My_Unb_String loop

   There are a couple of issues:
     (1) First, without Variable_Indexing, Ch could only be used in a read-only
	 way. That might be pretty limiting.
     (2) We'd have to define an iterator function much like we do in the
	 containers to be used here. That adds a bit of complication (no big
	 deal, though).

   It's not clear if this is worth it.

So, the only slam-dunk is Constant_Indexing. It's not clear if that alone is
worth defining (it could be confusing that writing elements isn't supported). Or
we could consider trying to come up with an extra mapping for Variable_Indexing
that would map:
    S(N) := C;
into
    Replace_Element (S, N, C);

In which case we would want to define all of these things.

Thoughts??

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

From: Tucker Taft
Sent: Monday, February  7, 2011  8:06 PM

> Aspect Implicit_Dereference
>     This doesn't make sense for the strings packages; we don't want to
> be making pointers at individual characters. Requiring the individual
> characters to be aliased to support this strategy could cause some
> implementations to waste a lot of memory (on a word-addressable
> machine in particular).

We could generalize Implicit_Dereference a bit by having a different
equivalence, such as "Ref" by itself is equivalent to
"Ref.Discrim.all(Ref.Index)" or "Ref.Discrim.all.Field" and thereby avoid the
need to have the individual elements be aliased, so long as some enclosing
composite object is aliased.

...
> Aspect Variable_Indexing
>     This maps to procedure Replace_Element, but not sensibly. The
> current scheme imagines that it maps to a function returning an access
> to an element (using reference) -- but using an access type doesn't
> make much sense in this context. Rather, we'd rather pass a value to a
> procedure to set the element. That of course would require some sort
> of change to the currently defined mechanism for Variable_Indexing.
> I'd guess that is too complicated to define, so I think it probably
> would make more sense to just forget this capability. (Whether this
> means we should forget about providing *read* access I can't say.)

For Variable_Indexing, if we generalize Implicit_Dereference, then we can also
generalize Variable_Indexing.

...
>     There are a couple of issues:
>       (1) First, without Variable_Indexing, Ch could only be used in a
> read-only way. That might be pretty limiting.

But see above.

...
> Thoughts??

Might be worth investigating a generalization of Implicit_Dereference which
works with unaliased subcomponents of an aliased composite object.

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

From: Randy Brukardt
Sent: Monday, February  7, 2011  8:22 PM

...
> We could generalize Implicit_Dereference a bit by having a different
> equivalence, such as "Ref" by itself is equivalent to
> "Ref.Discrim.all(Ref.Index)" or "Ref.Discrim.all.Field"
> and thereby avoid the need to have the individual elements be aliased,
> so long as some enclosing composite object is aliased.

I don't see how this helps. The public view of an Unbounded_String is a
featureless partial view. Whether or not there is any enclosing composite object
that is aliased is not something that the public can know about. OTOH, the
aspects are all about the *public* view of something.

I don't think it is a good idea to expose anything about the implementation of
this type, because there probably are implementations that violate it.

For instance, you could make the scheme you suggest here work if you were
willing to require that all implementations store unbounded strings as an access
to a string. [Then an operation that returned such a pointer could be used as an
implicit dereference.] But that would break any implementations that use a
chunked implementation (which might make sense if assignments/modifications are
more common in programs than the reading operations).

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

From: Tucker Taft
Sent: Monday, February  7, 2011  10:28 PM

> I don't see how this helps. The public view of an Unbounded_String is
> a featureless partial view. Whether or not there is any enclosing
> composite object that is aliased is not something that the public can know about.
> OTOH, the aspects are all about the *public* view of something.

Hmmm...  Getting creative here.  Suppose we define a new aspect
"Private_Implicit_Dereference" which indicates that the associated type is a
reference type which when implicitly dereferenced has the specified type:

    type Element_Reference(<>) is private
      with
        Private_Implicit_Dereference => Character;

    ...
private

    type Unbounded_String is new Finalization.Controlled with record
        Chars : access String;
    end record;

    type Element_Reference(UStr : access Unbounded_String) is record
        Index : Positive := 1;
    end record
      with
        Implicit_Dereference => UStr.Chars(Index);

Then we extend the Implicit_Dereference aspect to take not just a name of an
access discriminant, but allow a more general name as exemplified by the above.

> I don't think it is a good idea to expose anything about the
> implementation of this type, because there probably are implementations that
> violate it...

Agreed.

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

From: Randy Brukardt
Sent: Monday, February  7, 2011  10:50 PM

> Hmmm...  Getting creative here.  Suppose we define a new aspect
> "Private_Implicit_Dereference" which indicates that the associated
> type is a reference type which when implicitly dereferenced has the
> specified type:
...
> Then we extend the Implicit_Dereference aspect to take not just a name
> of an access discriminant, but allow a more general name as
> exemplified by the above.

That seems like a lot of mechanism for not much gain. We *really* want to be
able to do assignments of values directly into elements of this type; I don't
see much point in even faking a by-reference mechanism. (Note that there can be
components that you can't usefully take an address of; this seems similar.)

That's why I suggested changing Variable_Indexing so that it could work by
calling the existing procedure Replace_Element. That also seems like quite a lot
of mechanism, but at least it doesn't require faking something no one wants in
the first place.

That is, allow Variable_Indexing to match a procedure with three parameters,
then convert
    S(N) := C;
to
    Replace_Element (S, N, C);

This would also require a bit more care with the definition of the two cases. In
particular, for "in out" parameter passing by-copy, you would have to use
Constant_Indexing on the way in and Variable_Indexing on the way out.

The only unusual thing is that S(N) would not be the name of an object (rather
the name of a value), so it couldn't be renamed.

=============

In any case, I don't want this corner case to screw up the nice proposal. So
let's not try too hard with this one...

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

From: Tucker Taft
Sent: Monday, February  7, 2011  11:14 PM

> That seems like a lot of mechanism for not much gain. We *really* want
> to be able to do assignments of values directly into elements of this
> type; I don't see much point in even faking a by-reference mechanism.
> (Note that there can be components that you can't usefully take an
> address of; this seems similar.)

I don't understand the above paragraph.  You say we want to be able to do
assignments directly into elements of this type, but then you don't see much
point in faking a by-reference mechanism. These seem to be contradictory
statements (at least to me).

> That's why I suggested changing Variable_Indexing so that it could
> work by calling the existing procedure Replace_Element. That also
> seems like quite a lot of mechanism, but at least it doesn't require
> faking something no one wants in the first place.

This would only work for elements of a by-copy type when passing an OUT or
IN-OUT parameter.

> That is, allow Variable_Indexing to match a procedure with three
> parameters, then convert
>      S(N) := C;
> to
>      Replace_Element (S, N, C);
>
> This would also require a bit more care with the definition of the two
> cases. In particular, for "in out" parameter passing by-copy, you
> would have to use Constant_Indexing on the way in and Variable_Indexing on the
> way out.
>
> The only unusual thing is that S(N) would not be the name of an object
> (rather the name of a value), so it couldn't be renamed.

Sounds pretty ugly, particularly since it wouldn't work at all for non-by-copy
element types.

> =============
>
> In any case, I don't want this corner case to screw up the nice
> proposal. So let's not try too hard with this one...

Agreed.  We have much bigger fish to fry...

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

From: Randy Brukardt
Sent: Monday, February  7, 2011  11:33 PM

> I don't understand the above paragraph.  You say we want to be able to
> do assignments directly into elements of this type, but then you don't
> see much point in faking a by-reference
mechanism.
> These seem to be contradictory statements (at least to me).

I don't see any reason that assignment necessarily has anything to do with a
by-reference mechanism. The obvious counter-example is by-copy parameter passing
-- you still can assign into such parameters; even if you can get a useful
address for them (and you don't have to be able to), it doesn't correspond to
any other object (and certainly not the actual).

In implementation terms, Janus/Ada has the concept of assignable components that
you can't take an address of. For instance, most bit-packed components don't
have a machine address per se (some container does, of course). Such things will
always be passed by copy, and assignments always require changing the entire
"container" (in the case of bit operations, you have to do a read, some masking,
and then a write). Setting a single bit in a packed array always falls into this
model.

I was trying to abstract this model into something that makes sense at the
language level. For such a thing, you can *only* talk about the container and
operations on it; it doesn't make sense to even think about references to
individual elements because you cannot make an assignment that way, anymore than
you can talk about setting a single bit in a word (or whatever your addressible
unit is).

Anyway, it seems obvious that this isn't going to work very easily, so it's
probably best to leave it for Ada 2020.

Which leaves the question of whether to use Constant_Indexing in Bounded_Strings
and Unbounded_Strings now, or forget it as insufficiently helpful.

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

From: Tucker Taft
Sent: Monday, February  7, 2011  11:58 PM

> I don't see any reason that assignment necessarily has anything to do
> with a by-reference mechanism. The obvious counter-example is by-copy
> parameter passing -- you still can assign into such parameters; even
> if you can get a useful address for them (and you don't have to be
> able to), it doesn't correspond to any other object (and certainly not the
> actual).

I think we are using the term "reference" in two different ways.
The idea of the "Private_Implicit_Dereference" is that a pointer-like thing can
be converted into a name of a component of a data structure. It doesn't mean it
is converted into an *address*, so it would work just fine for a packed array.
It necessarily *starts* with going through a "true" pointer, but then it might
refer to a subcomponent of some packed structure.

> In implementation terms, Janus/Ada has the concept of assignable
> components that you can't take an address of. For instance, most
> bit-packed components don't have a machine address per se (some
> container does, of course). Such things will always be passed by copy,
> and assignments always require changing the entire "container" (in the
> case of bit operations, you have to do a read, some masking, and then
> a write). Setting a single bit in a packed array always falls into this model.
>
> I was trying to abstract this model into something that makes sense at
> the language level. For such a thing, you can *only* talk about the
> container and operations on it; it doesn't make sense to even think
> about references to individual elements because you cannot make an
> assignment that way, anymore than you can talk about setting a single
> bit in a word (or whatever your addressible unit is).

Here is where you are using the term "reference" and seem to be implying that it
requires an address.  I was thinking that Ref.Discrim.all.Chars(Index) was a
"reference" to a particular component of the Chars array, but there is no
requirement that Ref.Discrim.all.Chars(Index)'Address be well defined.  Merely
that "Ref.Discrim.all.Chars(Index)" be a variable name that can be used on the
LHS of an assignment or passed as an OUT parameter.  Presumably it will be
passed by copy if necessary, in the normal way.

> Anyway, it seems obvious that this isn't going to work very easily, so
> it's probably best to leave it for Ada 2020.

Agreed.

>
> Which leaves the question of whether to use Constant_Indexing in
> Bounded_Strings and Unbounded_Strings now, or forget it as
> insufficiently helpful.

I think it could be confusing to be able to use these in some contexts but not
others.

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

From: Jean-Pierre Rosen
Sent: Tuesday, February  8, 2011  3:37 AM

> Which leaves the question of whether to use Constant_Indexing in
> Bounded_Strings and Unbounded_Strings now, or forget it as
> insufficiently helpful.

I'm hesitant (like anybody I guess), but here are some thoughts FWIW:

1) This is all syntactic sugar with no new functionality. I know "it's the sugar
   that helps the medicine go down", but I don't think we heard much complaints
   that the string packages were too complicated to be usable, or anything like
   that.

2) We have no idea how people will receive the new forms of iterators.
Will they adopt it immediately, or just stick to the old-fashioned way on the
ground that it is closer to what is actually happening? No one knows.

3) Extending the new iterator mechanism in the next revision of Ada if there is
   demand for it will be easy. Undoing a last-minute extension that missed some
   important point will not.

So, I'm inclined to saying: "nice idea; take a note of it for the next
revision".

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

From: Edmond Schonberg
Sent: Tuesday, February  8, 2011  2:42 PM

I think that iteration over unbounded strings is adequately supported currently,
and there is no need to extend the new iterator machinery to cover them. We know
the lower bound is 1, we have the function Length, the function Element and the
procedure Replace_Element. No one has complained that there is no direct
indexing syntax for them, and they have not been treated as containers so far.
I agree with Jean-Pierre that this can wait to see whether there is a perceived
need (none so far).

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

From: Randy Brukardt
Sent: Thursday, February 10, 2011  2:12 AM

...
> 1) This is all syntactic sugar with no new functionality. I know "it's
> the sugar that helps the medicine go down", but I don't think we heard
> much complaints that the string packages were too complicated to be
> usable, or anything like that.

Well, I HAVE heard that. But what we can do easily won't help any of the real
problems with these packages enough to make it worth the effort. We would need
to tackle the string literal problem in order to do that, but we're definitely
not going to do that this time.
  (Which only leaves users with the
         function "+" (S : String) return Unbounded_String renames Ada.Strings.Unbounded.To_Unbounded_String;
   "solution", it's considered too ugly to put into the standard package. Why
   NO solution is preferable escapes me. If I don't do the above, my programs
   look something like:

    Header := new Line_Rec'(Number => 1,
                            Value => Ada.Strings.Unbounded.To_Unbounded_String ("============"),
                            Next => null);

which is not great for readability...)

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

From: Jean-Pierre Rosen
Sent: Thursday, February 10, 2011  3:15 AM

Are you saying that the ban on use clauses hampers readability? I can't agree
any more ;-). And I have also no problem with the renaming as "+", which was
intended by JDI. YMMV ...

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

From: Robert Dewar
Sent: Thursday, February 10, 2011  5:22 AM

Well to me Ada.Strings.Unbounded.To_Unbounded is plain horrible compared to just
To_Unbounded. This package is designed to be used without use clauses. People
who ban use clauses shoot themselves in the foot in a case like this, no
sympathy :-)

BTW, I really think it is a pity that we did not add a unary operator intended
for conversion, the use of unary "+" is a bit bogus (always fascinating to me
how operators bring anti-use folks to their senses, almost no one wants to write
Algebra."+"(A, B) :-) :-))

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

From: Randy Brukardt
Sent: Thursday, February 10, 2011  1:28 PM

You both (maybe intentionally) missed my point. I'll use the renames here if
there are more than one or two uses of "To_Unbounded_String". This is the same
conditions under which I would consider using a use clause. So this sort of
thing only shows up in the "rare usage" scenario.

In any case, I don't find:

      Header := new Line_Rec'(Number =>  1,
                              Value => To_Unbounded_String ("============"),
                              Next =>  null);

to be any improvement. It is still way too long and wordy (for something that is
logically an identity function).

Also note that it is not unusual to have both Ada.Strings.Fixed and
Ada.Strings.Unbounded in the same code; you can't "use" both or you'll never
figure out resolution errors. (I've been there!)

> BTW, I really think it is a pity that we did not add a unary operator
> intended for conversion, the use of unary "+" is a bit bogus (always
> fascinating to me how operators bring anti-use folks to their senses,
> almost no one wants to write Algebra."+"(A, B) :-) :-))

Sorry, I sometimes write exactly that, for two reasons:
   (1) If there is only one operator, it takes longer to find a nearby
       declarative part and figure out the name of the appropriate type than it
       does to just write this in prefix notation.
   (2) If there are resolution problems, this is good way to tell the compiler
       exactly what you mean. Trial-and-error is often the only way to fix these
       things, because the typical compiler error messages aren't much help for
       fixing non-resolving expressions involving operations (there are just too
       many of them; the typical program that I debug has more than 50 "="
       defined and the compiler simply can't guess effectively as to the
       intended meaning).

It also should be noted that I have much less objection to use clauses when they
are applied to overloadable entities. It's the non-overloadable entities that
cause all of the trouble, requiring you to put *in* as much dot notation
elsewhere as you take out locally. "use all type" will definitely let me use
"use" clauses more often. Unfortunately, that doesn't help Ada.Strings.Unbounded
much -- as previously noted, I think To_Unbounded_String is ridiculous with or
without a use clause.

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

From: Randy Brukardt
Sent: Tuesday, March  8, 2011  5:21 PM

My notes for the last meeting has:

Randy asks about the change from Pure to Preelaborate. Tucker wonders if we
could just change Controlled to Pure (also dropping Remote_Types). No one can
think of a real problem with that. There is "state" involved, but that state is
managed solely by the implementation (not by the user), and there is no way to
depend upon it. (A Pure Finalize routine could not depend on global variables,
which might be harder to write, but tough.)

I've been pondering this change, because I was unconvinced that there wouldn't
be a problem. I've now convinced myself that there can be no problem with this
change, and I wanted to record the reasons behind that. (And if someone knows
different, please speak up now!)

One topic that we touched on briefly at the meeting (but didn't get recorded) is
the issue of distribution. Pure packages imply that types declared within them
can be used as remote types. That cannot cause a (new) problem in this case, as
package Finalization already has the Remote_Types categorization. So there is
nothing to worry about there.

The main thing that concerned me is that a constant controlled object does not
need to act as a constant, as a writable version is provided to the
Initialize/Adjust/Finalize routines. The wording changes of AI05-0054-2 stress
this fact. This matters because Pure disallows library-level variables; but in
general, constant controlled objects work the same as a variable.

For instance, we would have trouble if a constant object of a type like the
following could be declared at the library-level in a Pure package:

     type Ouch is new Ada.Finalization.Controlled with record
         Self : access Ouch;
     end record;

     procedure Initialize (Obj : in out Ouch) is
     begin
         Obj.Self := Obj'Access;
     end;

The assignment creates a variable reference to the object itself and saves it
within the object. Later routines could then use this variable reference to
modify the object -- thus creating state. This is trouble because it could
happen in some inner call, not necessarily within Initialize itself.

Luckily, Pure packages also have to be preelaborable. A constant object declared
at the library-level of a Pure package also has to have Preelaborable
Initialization (PI). And a type with a non-null Initialize routine is defined to
not have PI.

However, constants have to be initialized, so Initialize isn't likely to be
called anyway. But we could create the same problem with Adjust. That is, if we
could declare an object:
      Owww : constant Ouch := <???>;
such that Adjust is called, we would have the same problem.

[Aside channelling Steve: Note that the preelaboration rules might in fact make
this illegal simply because of the call to Adjust (which is clearly a
subprogram). This illustrates the rather nasty nature of the preelaboration
rules, in that they require the compiler to predict the future. (Steve has noted
this problem in the past.) Note that 10.2.1(5) says "unless its elaboration
performs any of the following actions:". But that is a dynamic semantics action
which cannot be completely predicted at compile-time. It also mixes dynamic
rules (which are typically privacy breaking) with legality rules (which are
typically not privacy breaking). I have to wonder whether:

         C : constant Integer := (if True then 1 else Some_Function(Some_Object));

is preelaborable. Reading the letter of the wording, it would appear that it is
preelaborable (the elaboration of C will not call Some_Function nor evaluate the
name of Some_Object). Do we really want this?? Do we want it if True is replaced
by some static expression? Should preelaborability depend on values elsewhere in
the program? Enquiring minds don't really want to know. ;-)

Anyway, we'll skip whether this rule applies because it doesn't matter.]

However, for this to happen, we have to write something to replace <???> which
is both allowed by preelaboration and which would force a call to Adjust. If
<???> is replaced by an aggregate, no call to Adjust is made. The only other
possibilities for a tagged type are an object or a function call, and these are
illegal by 10.2.1(8) and 10.2.1(7), respectively.

Thus, we can't create a writable reference via Adjust.

We probably can create such a reference via Finalize, but that is too late to be
interesting (it's hard to imagine how that could be used to create library-level
state during the normal execution of the package).

Thus, I conclude that a constant controlled object used in a Pure package acts
as a constant through its entire life until Finalize is called.

(There probably is a similar issue involving immutably limited types; but since
that isn't new I'm not going to analyze it, and in any case, it doesn't hide
inside of subprograms.)

----

One additional issue is whether this adds any difficulties in using or
implementing the container Reference and Iterator types.

On usability:

Neither of these types will have PI, so these objects cannot be used at library
level in Pure or Preelaborable packages. But that is OK, as we don't want
default-initialized stand-alone objects of these types in the first place, and
initialized ones will be illegal because of the function call needed to get the
values.

This implies that container dereferencing and indexing will not be available at
library-level in such packages. But that is OK, because any library-level
container necessarily has to be empty (can't execute the procedure calls to put
anything into it). So there ought not be any such references.

On implementability:

The Reference object typically will contain a pointer to the container and the
discriminant that points at the element. Initialize will raise Program_Error (we
don't want default-initialized Reference objects), and Finalize will reset the
tampering bit in the container. None of this requires any package-level objects.

The Iterator object typically will contain a pointer to the container and a
cursor for a position within the container. The routines to call are determined
by the interface, so calls are made with dispatching calls. No package-level
objects appear to be needed.

In summary, I don't think there is a problem with this.

----

One tiny aside: the AARM note about the bounded forms says:

Implementation Note: Package Containers.Bounded_Vectors cannot depend on package
Ada.Finalization (because that package has Preelaborate categorization).

This note is still wrong and still needs to be removed (as noted in the AI). The
reason is different, but the effect is the same.

The AARM note that I added after the "needs finalization" bullet still is needed
as well (to note that the Vector type cannot itself be controlled if the element
type does not have a controlled part).

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

From: Ed Schonberg
Sent: Tuesday, March 15, 2011  2:00 PM

Here is a revised version of Dijkstra's shortest path algorithm.  It is simpler
than the previous version, (it even uses anonymous array types where
appropriate) and only makes use once of the new iterator form. It compiles
properly with the partial implementation of iterators in GNAT, and the code
incorporates the suggestions made at last meeting, including the precondition
that the source node is connected to the given graph.  a proper postcondition
seems out of reach: describing the set of possible paths would be longer than
the algorithm itself!

[Editor's note: This is version /07 of the AI.]

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

From: Tucker Taft
Sent: Tuesday, March 15, 2011  2:45 PM

The line below could be simplified to "for N in Node loop"
for what it's worth.  Actually seems a little clearer to me to leave off the
'First/'Last, since you use simply "Node" as the index subtype when declaring
the arrays.

>          for N in Node'First .. Node'Last loop

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

From: Robert Dewar
Sent: Tuesday, March 15, 2011  2:53 PM

> Here is a revised version of Dijkstra's shortest path algorithm.  It
> is simpler than the previous version, (it even uses anonymous array
> types where appropriate) and only makes use once of the new iterator
> form. It compiles properly with the partial implementation of
> iterators in GNAT, and the code incorporates the suggestions made at
> last meeting, including the precondition that the source node is
> connected to the given graph.  a proper postcondition seems out of
> reach: describing the set of possible paths would be longer than the
> algorithm itself!

Where are power sets when you need them? :-) :-)

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

From: Ed Schonberg
Sent: Tuesday, March 15, 2011  2:59 PM

Of course, this was left-over from an earlier version. Will update

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

From: Randy Brukardt
Sent: Wednesday, March 16, 2011  9:07 PM

I've made this change to the AI.

I also noticed that

         for E of G. Element (Next) loop

could be written

         for E of G (Next) loop

to take advantage of the Constant_Indexing facility. (I realize you probably
removed that in order to compile it with GNAT today.) That seems important to
tie into the descriptive text that I preserved from my older example. So I made
this change as well.

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

From: Edmond Schonberg
Sent: Wednesday, March 16, 2011  9:15 PM

That's right, I wanted to make sure that I had a version that compiled. I'm
happy to have the more Ada2012 version of course.

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

From: Edmond Schonberg
Sent: Thursday, April 14, 2011  4:27 PM

The AI states:


Add after constant No_Element:

package Vector_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursors,
   No_Element);

The name of the type is Cursor, of course.  But the type at that point is
private, and the instantiation is illegal.

Same for other containers.

(I'm not suggesting we go back to multiple visible parts !)

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

From: Randy Brukardt
Sent: Thursday, April 14, 2011  4:39 PM

We'll just have to put the nested cursor package back in. (I missed the
instantiation issue when I wrote the latest version of AI, obviously.) You can
look at an older version of the AI to see what that would look like.

That's slightly incompatible (it would change what is inherited for derived
cursors), but we previously discussed that and did not think that was a problem
-- deriving cursors causes all kinds of oddities.

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

From: Edmond Schonberg
Sent: Thursday, April 14, 2011  5:05 PM

I guess that works, some rearranging needed.

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

From: Edmond Schonberg
Sent: Thursday, April 14, 2011  5:11 PM

In fact lots of it, because the code in the body of each container depends
heavily on the full view of Cursor. That means that the visible  part of the
Cursors package may have to include some additional accessor functions.  Grumble
....

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

From: Randy Brukardt
Sent: Thursday, April 14, 2011  5:33 PM

Humm, that's trouble. I don't think we want implementations exporting unsafe
accessors (the container access is only safe if a Reference function is used,
and that's an unnecessary overhead hit). And in any case, we don't want to be
exporting "magic" functions that the user isn't supposed to use (or worse, must
not use or are implementation-defined).

But no solution comes immediately to mind. I'll think about this some, this is a
common problem and it ought not be impossible.

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

From: Randy Brukardt
Sent: Thursday, April 14, 2011  9:27 PM

Having thought about this for a while, there does not appear to be an easy and
safe solution. But there are at least three solutions available (one is not
easy, and two that are not safe).

A quick overview of the problem: AI05-0212-1 changes the specification of the
containers packages to look like:

with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
   with function "=" (Left, Right : Element_Type)
      return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists is
   pragma Preelaborate(Doubly_Linked_Lists);
   pragma Remote_Types(Doubly_Linked_Lists);

   type List is tagged private
      with
         Constant_Indexing => Constant_Reference,
         Variable_Indexing => Reference,
         Default_Iterator  => Iterate,
         Iterator_Element  => Element_Type;
   pragma Preelaborable_Initialization(List);

   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);

   Empty_List : constant List;

   No_Element : constant Cursor;

   package List_Iterator_Interfaces is new
      Ada.Iterator_Interfaces (Cursor, No_Element); --(1)

   ...

Ed notes that the instantiation (1) is illegal because Cursor is not completely
defined.

My initial suggestion was to reintroduce the nested package so that the Cursor
type is completely defined:

with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
   with function "=" (Left, Right : Element_Type)
      return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists is
   pragma Preelaborate(Doubly_Linked_Lists);
   pragma Remote_Types(Doubly_Linked_Lists);

   type List is tagged private
      with
         Constant_Indexing => Constant_Reference,
         Variable_Indexing => Reference,
         Default_Iterator  => Iterate,
         Iterator_Element  => Element_Type;
   pragma Preelaborable_Initialization(List);

   package Cursors is
      type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);

      No_Element : constant Cursor;
   private
      ... -- not specified by the language
   end Cursors;
   subtype Cursor is Cursors.Cursor;
   No_Element : Cursor renames Cursors.No_Element;

   Empty_List : constant List;

   package List_Iterator_Interfaces is new
      Ada.Iterator_Interfaces (Cursor, No_Element); --(1)

The instantiation is now legal. However, Ed has pointed out that with this
organization, the body of the List package has no access to the implementation
of a Cursor. Given that package Cursors have no operations, it should be obvious
why this is bad. :-)

Ed suggested solving this problem by adding accessor(s) into the Cursors
package. There are number of ways to do so, but they all suffer from similar
problems.

The easiest way to do this is is just to allow the implementation to put
whatever it wants into the specification of Cursors:

   package Cursors is
      type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);

      No_Element : constant Cursor;
      ... -- not specified by the language
   private
      ... -- not specified by the language
   end Cursors;

This permission would then be used to put something into the specification for
the body to use:

     type Cursor_Impl is record
        Container : access List;
        Node : access Node;
     end record;
     function Get_Cursor_Implementation (C : in Cursor) return Cursor_Impl;
     procedure Set_Cursor_Implementation (C : in out Cursor; Impl : Cursor_Impl);

But there is a number of obvious problems with this scheme. The main one is that
it exposes the entire Cursor definition for the world to use (and use!). Note
that we need to somehow define a Node here, which exposes even more of the
container implementation. And this is all implementation-dependent stuff. Yuck.

It also totally invalidates all of the good work we've done to make these things
safer: it exposes the pointers directly with no tampering checks, no dangling
pointer checks, or anything else.

We could mitigate some of these issues by defining "safer" accessors, or even by
having the language define some such accessors. That would sort-of work for the
container access, but the node access (which shouldn't be exposed at all) is
still a problem. Additionally, if the language defines these accessors, then
implementations couldn't add features to their cursors (such as dangling node
detection).

So, while this solution will work, I would consider it a last resort.

=================================

There is a related solution which will work. We can simply define the language
as above, and let the implementers deal with it. That can be done by using
Unchecked_Conversion or some other unchecked programming in the body to access
the contents of the cursor. One possible way to do that would be to put the
following in the body:

    type Cursor_Impl is record
       Container : access List;
       Node : access Node;
    end record;
    function Get_Cursor_Implementation is new Ada.Unchecked_Conversion(Cursor, Cursor_Impl);
    function Set_Cursor_Implementation is new Ada.Unchecked_Conversion(Cursor_Impl, Cursor);

This is annoying, as every cursor usage would need to be wrapped in a call to
Get_Cursor_Implementation. (Well, I'd probably use a much shorter name!) But at
least it doesn't expose the entire implementation to the universe to use and
abuse.

The problem with this solution is that it is a maintenance hazard; the Cursor
and Cursor_Impl types have to change in lockstep. This can be mitigated a bit
with a size check in the package body elaboration:
    pragma Assert (Cursor'Size = Cursor_Impl'Size);

This solution is easy, but note that the nested Cursor package is (mildly)
incompatible (the primitive operations of Cursor change when this package is
introduced). And the need to keep the two types in synch is a safety issue.

================================

There is a much better solution, but we need a new language feature to use it.
Specifically, we would have to resurrect AI05-0213-1, incomplete formal types.
(Note that this AI was in the Ada 2012 scope approved by WG 9, so adding this
feature back in cannot cause any WG 9-level complaints.)

We dropped this feature since it was only useful for generic signature packages,
mainly those doing nothing other than defining an interface. In this case, we
have a language-defined magic package that does nothing other that defining an
interface. Humm. :-)

So it should be obvious that Iterator_Interfaces could take a pair of incomplete
formal types; if that was done, the instantiation would be legal in the original
structure and sweetness and light would ensue.

Note that this is very similar to what we did with generic dispatching
constructor -- we defined a new language feature specifically so we could write
a magic language defined generic unit.

The problems with this idea are obvious: a new language feature is pretty heavy.
Moreover, I don't know if this feature is Baird-approved (although Steve was the
original author of AI05-0213-1, so he must have thought about it some, and he
didn't tell us that the whole thing was impossible then).

Still, this seems to be the best approach, and as a side-benefit, Tucker can
write more of his signature packages. :-)

===============================

I've thought about a number of other approaches. Most of them are just weird,
but I thought I'd list them in case it triggers a better idea in someone else.

The obvious first idea is to put the Iterator_Interfaces instance into a
package. But that only would help if the package was a child package (otherwise,
it would have to be visible in the specification, and Cursor would still not be
complete). But putting the Iterators into a child package would mean that it
would not be possible to define a Default_Iterator. Personally, I wouldn't mind
losing that feature, but I know others felt strongly that we needed that. But
even if we could agree on dropping that, putting the iterators into a separate
package just seems wrong - we *want* people to use these forms, not hide them
somewhere.

Of course, dropping the iterators completely would also work. Not going there.

Another idea that clearly would work would be Tucker's "Public" part (sorry, I
hate the idea of "End Private", "End" does not belong in the middle of a
construct), but it is really too late to work out the details.

This is a pretty general problem. Another thing that we could do is define an
aspect of a nested package that makes the private part visible in the body (and
private part??) of the parent package. (If the private part was included, we
could use this as a solution for the Queue problem as well.) But this sort of
visibility tinkering seems messy at best, and again it is pretty late to try to
define such a thing.

We could just say that the magic package Iterator_Interfaces also has magic
matching rules. But we decided to avoid that in Ada 2005, and I don't know
what's different today. Especially as we already have worked out the needed
wording for a language feature to have this effect.

Lastly, we could try to figure out how to make the iterator interface into some
sort of aspect. The problem with that is the needed operations of an iterator
type -- an interface bundles those for free, while we would have to define them
manually for an aspect. Probably we would need 5 aspects, which sounds like a
pain at best.

Any other thoughts???

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

From: Tucker Taft
Sent: Friday, April 15, 2011  11:15 PM

Another possibility:
type Cursor is record
   -- not specified by the language
end record;

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

From: Bob Duff
Sent: Friday, April 15, 2011  9:46 AM

> Having thought about this for a while, there does not appear to be an
> easy and safe solution. But there are at least three solutions
> available (one is not easy, and two that are not safe).

IMHO, we're in this situation because ARG is too wimpy to fix the problem
properly.  It's a serious problem that people have been complaining about for
years.  As I recall, the objection to simply allowing private types as actuals
in instantiations is that the either elaboration order rules are "weird", or we
tolerate some incompatibility.  A completely bogus argument, given that
elaboration of generic bodies normally does nothing at all, and even when it
does, the exact place it happens is unimportant.  It's language lawyering run
amok.

A language that can't even be used to implement its own predefined library is an
embarrassment, and we're too timid to fix it!

Grump.

> We dropped this feature since it was only useful for generic signature
> packages, mainly those doing nothing other than defining an interface.

In other words, it's yet another half measure, to be regretted at our leisure.

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

From: Bob Duff
Sent: Friday, April 15, 2011  9:51 PM

> There is a related solution which will work. We can simply define the
> language as above, and let the implementers deal with it.

This solution is trivial to implement.  Simply declare stuff in the visible part
using illegal syntax, such as:

    function _Accessor_Function (...) ...;

or even:

    type Cursor is record
        _Hidden_Component : ...;

And compile it in a special mode that allows leading underscores.

The problem with this solution is that the container implementations are no
longer written in Ada.  That's very bad, because people should be able to write
their own containers -- in Ada, of course.

> Any other thoughts???

Did I forget to mention:

Grump.

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

From: Edmond Schonberg
Sent: Friday, April 15, 2011  10:02 AM

> .......
> There is a much better solution, but we need a new language feature to
> use it. Specifically, we would have to resurrect AI05-0213-1,
> incomplete formal types. (Note that this AI was in the Ada 2012 scope
> approved by WG 9, so adding this feature back in cannot cause any WG
> 9-level complaints.)
>
> We dropped this feature since it was only useful for generic signature
> packages, mainly those doing nothing other than defining an interface.
> In this case, we have a language-defined magic package that does
> nothing other that defining an interface. Humm. :-)

I agree that something in this direction might be the cleanest.  The most minute
change might be to add a sentence to 13.14 (5)

...  The occurrence of a generic_instantiation causes freezing, unless the
generic package contains only abstract types and operations...

More formally we might want to introduce the notion of a signature package and
shorten that phrase accordingly.

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

From: Robert Dewar
Sent: Friday, April 15, 2011  12:10 PM

> IMHO, we're in this situation because ARG is too wimpy to fix the
> problem properly.  It's a serious problem that people have been
> complaining about for years.  As I recall, the objection to simply
> allowing private types as actuals in instantiations is that the either
> elaboration order rules are "weird", or we tolerate some
> incompatibility.

I must admit that it was very late, only a few years ago, that I learned that
private types cannot be allowed as actuals in instantiations (it was when Tuck
listed this as one of his major wish items for Ada 2012, at the Manchester Ada
UK meeting).

I continue to find this limitation distressing and surprising!

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

From: Robert Dewar
Sent: Friday, April 15, 2011  12:11 PM

...
> The problem with this solution is that the container implementations
> are no longer written in Ada.  That's very bad, because people should
> be able to write their own containers -- in Ada, of course.

Note that in GNAT, we already depart from writing the standard library in Ada,
instead it is written to be compiled with -gnatg that makes a few subtle but
important changes to Ada semantics (e.g. categorization errors are warnings
rather than errors, so that in certain circumstances they can be suppressed).

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

From: Bob Duff
Sent: Friday, April 15, 2011  1:20 PM

> Note that in GNAT, we already depart from writing the standard library
> in Ada, instead it is written to be compiled with -gnatg that makes a
> few subtle but important changes to Ada semantics

Sure, I have no problem with that.  I just want to be able to write things like
Ada.Containers.Vectors in pure Ada. I don't insist that Ada.Containers.Vectors
itself be written in pure Ada.

> (e.g. categorization errors are warnings rather than errors, so that
> in certain circumstances they can be suppressed).

That's sort of a special case, because if Bob_Duff_Containers.Super_Vectors gets
an error because I have Pure or Preelaborate or whatever, I can simply erase the
pragma.  Can't do that with language-defined ones.

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

From: Edmond Schonberg
Sent: Friday, April 15, 2011  2:12 PM

...
> A language that can't even be used to implement its own predefined
> library is an embarrassment, and we're too timid to fix it!

Changing freezing rules to allow for private types as actuals is very
problematic at this point.  Implementors know that freezing rules are delicate,
and a wholesale change here was ruled out during previous discussions.

However, allowing private types as actuals for instances of signature packages
is much less problematic, and would be generally useful.  we just have to define
precisely what is allowed in such packages.  The simplest rule would be to say:
abstract types and operations, and no formal objects.

Ada.Iterator_Interfaces qualifies, once we remove No_Element, which must be
there from some previous version of the AI, but which is not used at all in the
package.  Additionally, the package should be marked Pure so it can be
instantiated anywhere.  With these changes there is a clear path to implementing
AI05-0139-2, and AI05-0212.

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

From: Bob Duff
Sent: Friday, April 15, 2011  3:44 PM

> Changing freezing rules to allow for private types as actuals is very
> problematic at this point.  Implementors know that freezing rules are
> delicate, and a wholesale change here was ruled out during previous
> discussions.

There were a dozen solutions suggested, and they all had drawbacks, and were all
therefore rejected.  That's what I'm objecting to: we should have said, it's
important to solve this problem, and we're going to choose the least
objectionable solution.

My favorite was: The instance spec does freezing in the usual way, as if it were
written out at the point of instantiation. The body is elaborated at the first
freezing point of any of the actuals.  I don't see any big implementation
earthquake with this.  It was rejected because nobody understands the freezing
rules, and people might subtly depend on the exact place of body elaboration.
Yeah, that's a drawback, but it's hardly a show-stopper.  My instance bodies
don't do anything interesting during elaboration, and you're going to tell me I
can't have this feature because they might?!

It's just ludicrous that:

    type T is private;
    type A is array (...) of T;

is legal, but if I want to change A into a Vector:

    type T is private;
    package T_Vectors is new Vectors (T);
    subtype A is T_Vectors.Vector; -- or maybe a derived type

it's illegal, so I have to totally restructure my program.

Grumble.

> However, allowing private types as actuals for instances of signature
> packages is much less problematic, and would be generally useful.  we
> just have to define precisely what is allowed in such packages.  The
> simplest rule would be to say: abstract types and operations, and no formal
> objects.

>
> Ada.Iterator_Interfaces qualifies, once we remove No_Element, which
> must be there from some previous version of the AI, but which is not
> used at all in the package.  Additionally, the package should be
> marked Pure so it can be instantiated anywhere.  With these changes
> there is a clear path to implementing AI05-0139-2, and AI05-0212.

True, but I still say it's half measure.  Still a change to the freezing rules,
and not significantly simpler than going the whole way.

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

From: Edmond Schonberg
Sent: Friday, April 15, 2011  4:11 PM

> My favorite was: The instance spec does freezing in the usual way, as
> if it were written out at the point of instantiation.

Sorry, that doesn't work if the generic  spec has object declarations. You might
say that this is an implementation artifact (take care of the objects  in the
instance spec on another pass), but that's precisely the kind of artifact that
is at this point hard to change.

> The body is elaborated at the first freezing point of any of the
> actuals.  I don't see any big implementation earthquake with this.

Hope springs eternal!  Among other things, implementations of inlining may
depend on elaborating the body at once, so that's one of the many "artifacts"
that gets affected by this change.

> It was rejected because nobody understands the freezing rules, and
> people might subtly depend on the exact place of body elaboration.
> Yeah, that's a drawback, but it's hardly a show-stopper.  My instance
> bodies don't do anything interesting during elaboration, and you're
> going to tell me I can't have this feature because they might?!
>
> It's just ludicrous that:
>
>    type T is private;
>    type A is array (...) of T;
>
> is legal, but if I want to change A into a Vector:
>
>    type T is private;
>    package T_Vectors is new Vectors (T);
>    subtype A is T_Vectors.Vector; -- or maybe a derived type
>
> it's illegal, so I have to totally restructure my program.

Yeah, would be nice if this were legal. But Vectors is far from a signature
package so this is not going to be easy.

> Grumble.
>
>> However, allowing private types as actuals for instances of signature
>> packages is much less problematic, and would be generally useful.  we
>> just have to define precisely what is allowed in such packages.  The
>> simplest rule would be to say: abstract types and operations, and no formal objects.
>>
>> Ada.Iterator_Interfaces qualifies, once we remove No_Element, which
>> must be there from some previous version of the AI, but which is not
>> used at all in the package.  Additionally, the package should be
>> marked Pure so it can be instantiated anywhere.  With these changes
>> there is a clear path to implementing AI05-0139-2, and AI05-0212.
>
> True, but I still say it's half measure.  Still a change to the
> freezing rules, and not significantly simpler than going the whole way.

Actually it is a trivial change, given that I tried it and it works.  The full
solution is something else.

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

From: Bob Duff
Sent: Friday, April 15, 2011  5:14 PM

> > My favorite was: The instance spec does freezing in the usual way,
> > as if it were written out at the point of instantiation.
>
> Sorry, that doesn't work if the generic spec has object declarations.
> You might say that this is an implementation artifact (take care of
> the objects in the instance spec on another pass), but that's
> precisely the kind of artifact that is at this point hard to change.

I don't understand that.  If you say "package P is ... end P;"
and P contains an object decl, it freezes some stuff.
I'm saying an instance containing an object decl would do the same thing.  Yes,
it requires a pass over the instance spec, but that's not "another" pass -- we
already have to make a pass over instance specs.  What am I missing?

Randy wants to share generic bodies, but surely he doesn't share specs!?

> > of the actuals.  I don't see any big implementation earthquake with
> > this.
>
> Hope springs eternal!  Among other things, implementations of inlining
> may depend on elaborating the body at once, so that's one of the many "artifacts"
> that gets affected by this change.

Inlining has nothing to do with elaboration.

> Yeah, would be nice if this were legal. But Vectors is far from a
> signature package so this is not going to be easy.

I have yet to hear any reason it's not easy.  I could be wrong, of course, and
when it comes to software, pessimists are more often right than optimists.  ;-)

> > True, but I still say it's half measure.  Still a change to the
> > freezing rules, and not significantly simpler than going the whole way.
>
> Actually it is a trivial change, given that I tried it and it works.

OK, that's pretty convincing (that it's trivial).

>...The
> full solution is something else.

OK, I suppose I have to "put up or shut up" -- i.e. implement the rule I'm
suggesting.  Would that convince you?  I must admit, messing around with
freezing in GNAT gives me the willies.  ;-) Whenever there's a freezing-related
bug, I go cry on the shoulders of Ed or Hristian or somebody.

I've got a bad cold today (I hope I didn't infect our customer during the
on-site visit yesterday! Or Ed (the other Ed)!), which is perhaps making me
grouchier than usual (doubly so, given that my so-called "vacation" week starts
tomorrow), but I really don't think "bad cold" is driving my desire for "package
My_Vectors is new Vectors(My_Private_Type);".

My brother installed wireless in my parents' place, so maybe I'll be in touch.

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

From: Edmond Schonberg
Sent: Friday, April 15, 2011  5:28 PM

> I don't understand that.  If you say "package P is ... end P;"
> and P contains an object decl, it freezes some stuff.
> I'm saying an instance containing an object decl would do the same
> thing.  Yes, it requires a pass over the instance spec, but that's not
> "another" pass -- we already have to make a pass over instance specs.
> What am I missing?

We are speaking of implementation strategies, so of course everything is
malleable in principle. Just rewrite the front-end of the compiler!  If the
generic has an object declaration of the generic type, and the actual is private
without a completion, freezing at the point of the instance just gives you an
error, so that's useless. Therefore the minimal rule is that the generic package
cannot contain object declarations that depend on a formal type.

...
>> Hope springs eternal!  Among other things, implementations of
>> inlining may depend on elaborating the body at once, so that's one of the many "artifacts"
>> that gets affected by this change.
>
> Inlining has nothing to do with elaboration.

No, but everything with code generation, and I've spent many sleepless nights to
make sure that it is possible to inline from an instance into the code that
follows. Again, an additional pass would no doubt help.

...
>> ...The
>> full solution is something else.
>
> OK, I suppose I have to "put up or shut up" -- i.e. implement the rule
> I'm suggesting.  Would that convince you?

In a microsecond!  Be my guest.

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  6:28 PM

...
> Randy wants to share generic bodies, but surely he doesn't share
> specs!?

Yes, we share both the spec and the body, with a few execeptions for the spec
(things like derived tagged types, and those are modeled as implicit formal
parameters). It probably would be possible to change that, but it would be a
massive change.

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

From: Robert Dewar
Sent: Friday, April 15, 2011  6:33 PM

As I have said before, I think it is fine to share generics where possible, but
I don't think the ability to do universal sharing should be a language design
criterion, and sharing specs universally in particular makes no sense to me.

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  7:26 PM

...
> IMHO, we're in this situation because ARG is too wimpy to fix the
> problem properly.  It's a serious problem that people have been
> complaining about for years.  As I recall, the objection to simply
> allowing private types as actuals in instantiations is that the either
> elaboration order rules are "weird", or we tolerate some
> incompatibility.  A completely bogus argument, given that elaboration
> of generic bodies normally does nothing at all, and even when it does,
> the exact place it happens is unimportant.  It's language lawyering
> run amok.

This is utter BS, and you ought to know that.

A generic body is the only way to get a procedure call into the elaboration of a
package specification. While this usage isn't particularly common, since there
is no alternative it is very important that the capability be preserved. (Note
that Pascal said that he was aware of several of their customers having used
this capability; and I believe I've used it at least once.)

Blithly ignoring compatibility and maintenance concerns seems to me that
*someone* is running amok, and it isn't the "language laywers" (which has
nothing to do with this debate).

...
> > We dropped this feature since it was only useful for generic
> > signature packages, mainly those doing nothing other than defining an interface.
>
> In other words, it's yet another half measure, to be regretted at our
> leisure.

Why would we regret it?? I think that there ought to be a generic contract for
virtually every kind of entity that you can declare. There surely is no way to
handle incomplete types currently, so that seems like a hole, irrespective of
any other issues.

Moreover, that solution has already been worked out and is part of the "scope"
of Ada 2012 (so using it is not a problem). Any solution involving direct
inclusion of private types in generic instances is not in that scope, does not
have appropriate wording available, and thus is too late to include in Ada 2012.

I don't much care whether we decide to use the AI05-0213-1 solution, or whether
we make vendors use Unchecked_Conversion, but I don't think that there are any
other viable options (I haven't heard of any, anyway).

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  7:30 PM

> > There is a related solution which will work. We can simply define the
> > language as above, and let the implementers deal with it.
>
> This solution is trivial to implement.  Simply declare stuff in the
> visible part using illegal syntax, such as:
>
>     function _Accessor_Function (...) ...;

Why would you implement this with "non-Ada" when an all-Ada solution is
available (Unchecked_Conversion) that doesn't require modifying the
specification? The use of visible accessor functions helps nothing over using a
hidden call to U_C -- the syntax mess is the same, and if anything, the U_C
would generate better code [probably they'd be the same, but if there was any
code, it would be for the accessor function and not the U_C].

I agree this is possible, but so is making the type visible or allowing random
impl-defined stuff. Why would we want to do either??

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  7:33 PM

...
> Ada.Iterator_Interfaces qualifies, once we remove No_Element, which
> must be there from some previous version of the AI, but which is not
> used at all in the package.  Additionally, the package should be
> marked Pure so it can be instantiated anywhere.  With these changes
> there is a clear path to implementing AI05-0139-2, and AI05-0212.

Huh??? No_Element is an important part of the signature. *Nothing* in a
signature package is necessarily used in that package! Recall that the code
generated for an iterator is:

   declare
      _Iter : Iterator_Type := Iterate(Container);
      Cursor : Cursor_Type := First(_Iter);
   begin
      while Cursor /= No_Element loop
         Container(Cursor) := Container(Cursor) + 1;
           -- This presumes an appropriate _Indexing aspect
           -- is defined.

         Cursor := Next(_iter, Cursor);
      end loop;
   end;

That "/= No_Element" is going to be tough if No_Element isn't part of the
signature!!

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  7:54 PM

> There were a dozen solutions suggested, and they all had drawbacks,
> and were all therefore rejected.  That's what I'm objecting to:
> we should have said, it's important to solve this problem, and we're
> going to choose the least objectionable solution.

That's not what happened. What happened is that we looked at a bunch of
solutions, and tried to pick the least objectionable. But we couldn't get close
- pretty much everyone had at least one of the proposed solutions that they
could not tolerate. And there also was the problem that the least objectionable
solutions also tended to leave major parts of the problem unsolved.

> My favorite was: The instance spec does freezing in the usual way, as
> if it were written out at the point of instantiation.
> The body is elaborated at the first freezing point of any of the
> actuals.

Huh? I hope you mean "the first point where all of the actuals are frozen",
because trying to elaborate the body when only part of the actuals are frozen
makes no sense whatsoever.

> I don't see any big implementation earthquake with this.

It's completely impossible in the existing Janus/Ada implementation, which
shares everything. We don't have a representation of structures larger than
expressions and simple declarations, so it is unlikely that everything that
occurs in a specification could be handled with those existing structures. There
probably is a 95% solution to expanding specifications, but it would likely lead
to a never-ending parade of bugs because of the missing 5%. (Generic bodies
already suffer from this sort of thing, it would be irresponsible to double it.)

Moreover, we evaluate and create the data structures for the actual parameters
at the point of the instance. That clearly cannot be done until all of the
actual parameters are frozen. But delaying that until the point that the body is
elaborated doesn't work, because you are trying to elaborate the specification
piece-meal, and the actuals that are used have to be evaluated early.

The net effect is that the actuals have to be evaluated in several places,
except *that* doesn't work because you might get different answers from multiple
evaluations of the actuals. Whatever rules you intend would have to be *very*
clearly spelled out in the standard -- and they would require a total redo of
the generic instance processing in Janus/Ada.

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  7:58 PM

...
> > Yeah, would be nice if this were legal. But Vectors is far from a
> > signature package so this is not going to be easy.
>
> I have yet to hear any reason it's not easy.  I could be wrong, of
> course, and when it comes to software, pessimists are more often right
> than optimists.  ;-)

Pretty much any description of this feature has lots of discussion of
implementation headaches (from me, from Ed, from Pascal, and probably from
others as well). If you have never read any of that accumulated evidence, you're
statement is understandable, but clearly comes from ignorance.

And that doesn't take into account the dangers to compatibility and
maintainability.

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  8:06 PM

...
> As I have said before, I think it is fine to share generics where
> possible, but I don't think the ability to do universal sharing should
> be a language design criterion, and sharing specs universally in
> particular makes no sense to me.

That's surely a possibility, but when it comes to delicate parts of an Ada
implementation (like generics), the rule tends to be "whatever you think ought
to be easy in an implementation isn't" :-)

In any case, I needed to explain that Bob is mistaken in how he thinks Janus/Ada
works (since he was wrong).

There are lots of problems with Bob's approach (not having to do with generic
sharing), starting with the runtime inconsistency that's implied, and the
possible maintenance problems. I would much prefer that such generics (and their
formals) be marked syntactically somehow, so that inconsistency only happens to
people who ask for it.

And of course there is the whole issue that this is way, way too late; there is
no way to vet such a feature by the end of next week (which is the deadline for
ARG modifications to Ada 2012).

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

From: Robert Dewar
Sent: Friday, April 15, 2011  9:07 PM

> The net effect is that the actuals have to be evaluated in several
> places, except *that* doesn't work because you might get different
> answers from multiple evaluations of the actuals. Whatever rules you
> intend would have to be *very* clearly spelled out in the standard --
> and they would require a total redo of the generic instance processing in Janus/Ada.

I think that total redo is in the long run inevitable if you really intend to
keep up with the swim of things.

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

From: Robert Dewar
Sent: Friday, April 15, 2011  9:13 PM

BTW, to put this comment in perspective, we have a number of times in GNAT had
to redo completely a significant chunk of the implementation. Yes, it's a big
pain, but one that is sometimes unavoidable.

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

From: Randy Brukardt
Sent: Friday, April 15, 2011  10:50 PM

> ...
> > Randy wants to share generic bodies, but surely he doesn't share
> > specs!?
>
> Yes, we share both the spec and the body, with a few execeptions for
> the spec (things like derived tagged types, and those are modeled as
> implicit formal parameters). It probably would be possible to change
> that, but it would be a massive change.

Let me expand on this a bit, lest I appear crazy (well, more crazy :-).

Generic body sharing requires that the data layout of every shared instance is
the same; otherwise, the body could not read the objects declared in the
specification (an obvious bug). For instance, if specification object A is
stored at location offset 12 in instance I1, then it has to be stored at
location offset 12 in every instance that is shared.

Since the data layout is the same, the code generated to do the elaboration is
also the same for the vast majority of entities in a generic specification.
(That was evem more true for Ada 83, when most of the these design decisions
were made.) Thus, there didn't seem to be much advantage to *not* sharing the
code. Moreover, our philosophy was always to share as much code as possible,
because it is a lot easier to remove sharing after the fact (that is, do
inlining) than to add sharing after the fact (turning common sequences of code
into subprograms - we did this successfully for the 8080/Z80 compiler, but it
did not usefully work on the X86).

For Ada 95, we added some limited non-shared items to the specification; they're
generated at the point of the instance after the formal parameters. That was
done mostly to support derived tagged types (tags are generated per-instance); I
don't recall if we ever used it for anything else). I could imagine using this
mechanism more generally, but since it wasn't intended to be able to elaborate
everything it probably would turn into a real mess.

And it wouldn't help by itself since it follows evaluating the actuals -- that
in itself isn't possible in a no-freezing scheme. I have no idea how that could
be changed -- but part of the problem there is that no one has ever explained
any rules for evaluation of actuals (if they don't have to be frozen) that make
any sense.

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

From: Edmond Schonberg
Sent: Saturday, April 16, 2011  9:03 AM

> That "/= No_Element" is going to be tough if No_Element isn't part of
> the signature!!

That code is in the context of the instantiation, where Cursor is both the
actual in the instance and the local type, and No_Element is a constant of that
type. I don't see the problem.

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

From: Edmond Schonberg
Sent: Saturday, April 16, 2011  9:24 AM

Which of course only makes sense if instances are not shared. sorry for the slip
....

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

From: Edmond Schonberg
Sent: Saturday, April 16, 2011  7:17 PM

I conclude from this discussion that the unchecked conversion approach is the
only viable one.  With proper choice of names it does not clutter the package
bodies too much, and it does not require last-minute features that we are not
sure how to implement. AI05-0212 has to be revised to include the Cursors
package again.

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

From: Randy Brukardt
Sent: Saturday, April 16, 2011  7:23 PM

> > That code is in the context of the instantiation, where Cursor is
> > both the actual in the instance and the local type, and No_Element
> > is a constant of that type. I don't see the problem.
>
> Which of course only makes sense if instances are not shared.
> sorry for the slip ....

It doesn't even make sense then. There is no requirement that the constant have
the name No_Element, just that some constant with that role exists.

For instance, we could create an iterator for a singly linked list thus:

   type My_Rec;
   type My_Ptr is access My_Rec;
   type My_Rec is record
       Next : My_Ptr;
       ...
   end record;

   package My_Iterator_Instance is new Ada.Iterator_Interfaces (My_Ptr, null);

In this case, My_Ptr has the role of "Cursor", and null has the role of
"No_Element".

Then, if we defined the following iterator type (note: I'm skipping the specs
here, this needs to be wrapped in a package to be compilable):

   type My_Iterator is new My_Iterator_Instance.Forward_Iterator with record
       Start : My_Ptr;
   end record;

   function Create_Iterator (Start : My_Iterator) return My_Iterator is
   begin
       return (My_Iterator_Instance.Forward_Iterator with Start => Start);
   end Create_Iterator;

   function First (Object : My_Iterator) return My_Ptr is
   begin
      return Object.Start;
   end First;

   function Next (Object : My_Iterator; Position : My_Ptr) return My_Ptr is
   begin
      if Position = null then return null;
      else return My_Ptr.Next;
      end if;
   end Next;

With this type in hand, we can write a loop for a list of My_Rec pointed at by
Head:

   for Ptr in Create_Iterator(Head) loop
      ...
   end loop;

This is the long way to write such an iterator, of course, but the point is that
you can do it, and nothing names No_Element is anywhere to be seen.

It strikes me that this object formal is a flaw in the idea of using the
AI05-0213-1 capability as-is, since an object cannot have an incomplete type. We
could fix that by making an explicit exception for this case [that is,
explicitly allow a formal object to be of a formal incomplete type] -- this
works as any legal instance would necessarily have an object that must not use
an incomplete type, but I admit it is not very appealing.

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

From: Randy Brukardt
Sent: Saturday, April 16, 2011  7:29 PM

> I conclude from this discussion that the unchecked conversion approach
> is the only viable one.  With proper choice of names it does not
> clutter the package bodies too much, and it does not require
> last-minute features that we are not sure how to implement.
> AI05-0212 has to be revised to include the Cursors package again.

That's pretty much the conclusion I came to as well (note the message that I
wrote while you wrote this one). It's a bit ugly, but not too bad if you know
about it from the start. [I knew there was a good reason that I haven't
implemented the containers packages yet... :-)]

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

From: Robert Dewar
Sent: Saturday, April 16, 2011  7:53 PM

> I conclude from this discussion that the unchecked conversion approach
> is the only viable one.

What in the RM guarantees that this UC approach works as intended?

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

From: Randy Brukardt
Sent: Saturday, April 16, 2011  11:17 PM

Does it matter? The UC will only appear in the body of the packages, and
presumably the implementer won't do anything that doesn't work on their own
compiler.

Beyond that, I don't think the RM could guarantee any approach here, because
this type is going to include access values, and pretty much no sorts of
unchecked programming or streaming is guaranteed for those.

Since this UC would be between two types with identical declarations, it is hard
to imagine why an implementation would break such a UC (you'd expect all kinds
of trouble with Sequential_IO and Direct_IO if an implementation did that).

This surely is not ideal, but the alternatives are worse:
 * Make the type visible, instantly defeating all of the safety measures
   built-into the containers;
 * Require compiler magic to implement containers (this is always an
   alternative, but it shouldn't be required);
 * Delay the standard long enough to work out some better solution;
 * Remove all of the iterator stuff from the standard (if we can't use it in the
   containers, it obviously is seriously flawed).

This is (to take Bob's phrase), the "least objectionable choice".

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

From: Robert Dewar
Sent: Sunday, April 17, 2011  7:07 AM

> Since this UC would be between two types with identical declarations,
> it is hard to imagine why an implementation would break such a UC
> (you'd expect all kinds of trouble with Sequential_IO and Direct_IO if
> an implementation did that).

I think it would be worth a rule in the RM that UC always works between types
with identical declarations.

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

From: Robert Dewar
Sent: Sunday, April 17, 2011  7:15 AM

rule here = implementation advice

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

From: Edmond Schonberg
Sent: Sunday, April 17, 2011  11:15 AM

It appears that we follow that advice.  I introduced a type in the body of
Ada.Vectors that has the identical representation as the (private) type Cursor,
and after a sprinkling of unchecked conversions from one to the other the
package works as expected, and so do the implicit dereference and variable
indexing aspects.

In a sense, the implicit conversion is part of the magic that makes these
iterators work. As with any good magic, it's just not visible to the user. And
it's cheap magic because UC is after all an old language feature.

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

From: Jean-Pierre Rosen
Sent: Sunday, April 17, 2011  4:36 PM

> I think it would be worth a rule in the RM that UC always works
> between types with identical declarations.

Always? Even if one is in the scope of a pragma optimize (time), and the other
one in the scope of a pragma optimize (space) ?

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

From: Robert Dewar
Sent: Sunday, April 17, 2011  8:58 PM

You could consider these non-identical declarations, but at the same time I
*VERY* much doubt there are any compilers which would make this kind of
distinction.Imagine for instance writing a sequential_IO file with a program
that says optimize(time) and not being able to read the result back into a
program that says optimize(space). While conforming, I think this would be
horrible behavior.

Also this is just implementation advice, not a requirement

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

From: Randy Brukardt
Sent: Monday, April 18, 2011  4:59 PM

> You could consider these non-identical declarations, but at the same
> time I *VERY* much doubt there are any compilers which would make this
> kind of distinction.Imagine for instance writing a sequential_IO file
> with a program that says optimize(time) and not being able to read the
> result back into a program that says optimize(space). While
> conforming, I think this would be horrible behavior.

Well, clearly there is a question of what "identical" means here. Obviously,
declarations aren't identical if one is packed and the other is not. But where
do we draw the line? If one is compiled with one compiler version and the other
is compiled with a different compiler version (surely possible when talking
about IO, if not for UC), I don't see how you could expect them to be the same.

Cases involving compiler switches or configuration pragmas (like Optimize) are
murkier, but the same seems to hold here.

For the record, Janus/Ada has an optimization setting that changes the handling
of alignments (so it could cause changing of the layout of records). So there is
a mode in Janus/Ada that would indeed make such a distinction. Having said that,
it strikes me that this switch violates our rules for "good taste in
optimization switches" (essentially, that setting such switches don't materially
change the behavior of the program -- but breaking Sequential_IO and Direct_IO
surely would not qualify). So I've added a work item to move this to some
non-optimization switch in future versions of Janus/Ada. Even so, there
definitely will continue to be at least one compiler switch in Janus/Ada that
changes data layout, and such a switch would violate the proposed Implementation
Advice.

> Also this is just implementation advice, not a requirement

Right, and so long as vendors look at IA that way and not as some sort of veiled
requirement, it would make sense (presuming a decent definition of "identical"
can be made).

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

From: Robert Dewar
Sent: Monday, April 18, 2011  8:28 PM

> Right, and so long as vendors look at IA that way and not as some sort
> of veiled requirement, it would make sense (presuming a decent
> definition of "identical" can be made).

Well I do think of IA as a "veiled" requirement, but if you choose not to follow
it, you have to document why of course. In any case, compiler switches are
allowed to do anything they like, you only have to have a specific set of
switches where your compiler conforms, so I dont consider that your switch would
introduce a non-conformance with the IA.

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

From: Matthey Heaney
Sent: Tuesday, April 19, 2011  2:36 PM

> The problem with this solution is that the container implementations
> are no longer written in Ada.  That's very bad, because people should
> be able to write their own containers -- in Ada, of course.

As far as GNAT is concerned, it's probably more accurate to say that the
container library in GNAT is implemented using GNAT, not strictly Ada, since
those units make frequent use of 'Unrestricted_Access. (Though I suppose you
could use 'Address, but then the counter-argument would be that you're leaving
the language completely.)

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:46 AM

> ...
> > IMHO, we're in this situation because ARG is too wimpy to fix the
> > problem properly.  It's a serious problem that people have been
> > complaining about for years.  As I recall, the objection to simply
> > allowing private types as actuals in instantiations is that the
> > either elaboration order rules are "weird", or we tolerate some
> > incompatibility.  A completely bogus argument, given that
> > elaboration of generic bodies normally does nothing at all, and even
> > when it does, the exact place it happens is unimportant.  It's
> > language lawyering run amok.
>
> This is utter BS, and you ought to know that.

I disagree.  What's BS is naysayers insisting that the problems are intolerable
and/or coming up with half-baked solutions that don't really solve the problem.
We should have taken the attitude: "We need to solve this problem, so let's find
a way."

Perhaps it's too late for that, now.  In which case we should drop iterators.

> A generic body is the only way to get a procedure call into the
> elaboration of a package specification.

No, it's not.

>...While this usage isn't particularly common,  since there is no
>alternative it is very important that the capability be  preserved.
>(Note that Pascal said that he was aware of several of their  customers
>having used this capability; and I believe I've used it at least
> once.)
>
> Blithly ignoring compatibility and maintenance concerns seems to me
> that
> *someone* is running amok, and it isn't the "language laywers" (which
> has nothing to do with this debate).

Certain instantiations are currently illegal.  Making them legal cannot possibly
introduce compatibility problems.  (Implementation problems, I can believe!)

I think the maintenance concerns are bogus.  (Yeah, maybe Pascal has some
examples of people using generics in a way that depends subtly on elaboration
rules.  So those can continue to work.)

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

From: Edmond Schonberg
Sent: Wednesday, April 20, 2011  8:20 AM

>> I conclude from this discussion that the unchecked conversion
>> approach is the only viable one.  With proper choice of names it does
>> not clutter the package bodies too much, and it does not require
>> last-minute features that we are not sure how to implement.
>> AI05-0212 has to be revised to include the Cursors package again.
>
> That's pretty much the conclusion I came to as well (note the message
> that I wrote while you wrote this one). It's a bit ugly, but not too
> bad if you know about it from the start. [I knew there was a good
> reason that I haven't implemented the containers packages yet... :-)]

Unfortunately, making a nested package Cursors in order to have a complete type
for the instantiation of Iterator_Interfaces has other problems. To preserve the
existing container interface requires reexporting Cursor and No_Element, which
forces the declaration of a non-static object in each package. it becomes
impossible to preserve the Preelaborate and Remote_Type properties of
containers.

We may have to re-examine relaxed rules for instantiations of signature
packages, which means some twists to freezing rules.  I see no other way of
getting accessors and iterators in a way that is not totally incompatible with
current containers.

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

From: Randy Brukardt
Sent: Wednesday, April 20, 2011  1:36 PM

...
> Unfortunately, making a nested package Cursors in order to have a
> complete type for the instantiation of Iterator_Interfaces has other
> problems. To preserve the existing container interface requires
> reexporting Cursor and No_Element, which forces the declaration of a
> non-static object in each package. it becomes impossible to preserve
> the Preelaborate and Remote_Type properties of containers.

I don't see a *real* problem (but I can believe that there is a problem with the
preelaboration rules). See below.

> We may have to re-examine relaxed rules for instantiations of
> signature packages, which means some twists to freezing rules.  I see
> no other way of getting accessors and iterators in a way that is not
> totally incompatible with current containers.

This seems like the long way to go to fix a problem with preelaboration.
(Aside: I still think a solution based on formal incomplete types would be much
easier to create and implement. But I'd rather avoid both.)

Specifically, we have the following construct:

    package Cursors is
        type Cursor is private;
        pragma Preelaborable_Initialization (Cursor);
        No_Element : constant Cursor;
    private
        -- ... Not defined by the language
        -- But probably looks something like:
        type Cursor is record
           Container : access Vector;
           Node : access Integer; -- Anything the right size.
        end record;
        No_Element : constant Cursor := (Container => null, Node => null);
    end Cursors;

    subtype Cursor is Cursors.Cursor;
    No_Element : constant Cursor := Cursors.No_Element;

The problem here is that Cursors.No_Element is not a static constant. But there
is no real problem with this constant; it is easy to make preelaborable and I
would be somewhat surprised if a compiler didn't do that.

But of course it is not *formally* preelaborable. I think the problem here is
that "static constant" is pretty limiting, as that eliminates any composite
types, even when the declaration is "obviously" OK. Probably what we need here
is a counterpart to Preelaborable_Initialization for constants, defined
something like:

    The name of an object has PI if:
        * it is a static expression;
        * it denotes a constant initialized by an aggregate whose components are
	  all:
              * the name of an object with PI and whose type is not controlled
		[Note: so no Adjust calls are involved]; or
              * <>, and the type of the component has PI.

    Pragma PI may apply to a deferred constant. If pragma PI applies to a
    deferred constant, the full constant declaration shall have PI.

And then we would change 10.2.1(8) to say that "...unless the name denotes an
object that has PI, or ...".

One could imagine tightening the definition even more if there are problems with
the above (perhaps as far as to require all of the components to be elementary),
but something on this line would fix the problem and as a side-effect make
Preelaborated items a bit more capable.

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

From: Edmond Schonberg
Sent: Wednesday, April 20, 2011  4:19 PM

...
>subtype Cursor is Cursors.Cursor;
>   No_Element : constant Cursor := Cursors.No_Element;

You have to re-export equality as well (the canonical approach would be to
derive Cursors.Cursor, but a renaming also works).

...
>One could imagine tightening the definition even more if there are problems
>with the above (perhaps as far as to require all of the components to be
>elementary), but something on this line would fix the problem and as a
>side-effect make Preelaborated items a bit more capable.

Looks plausible.  What do others think?  Is it worth pursuing signature packages
instead?  This is certainly a much smaller change to the language.  using
signature packages instead means that the bodies of containers need not get
cluttered with unchecked conversions, but of course it means some tweaking of
freezing rules.

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

From: Steve Baird
Sent: Wednesday, April 20, 2011  4:53 PM

As we discussed on the phone, I will try to demonstrate that we may be able to
address the problem by means of what some have argued is a contradiction in
terms, a minor change to the freezing rules.

I really don't like the Unchecked_Conversion approach, but I don't see a better
solution without some new language support.

The new feature should also be useful in its own right for other things (i.e.,
traditional signature generics).

I hope to send out a proposal sometime soon.

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

From: Randy Brukardt
Sent: Wednesday, April 20, 2011  5:30 PM

> As we discussed on the phone, I will try to demonstrate that we may be
> able to address the problem by means of what some have argued is a
> contradiction in terms, a minor change to the freezing rules.

I still firmly believe that any such change to generics needs some sort of
syntactic introduction, either in the generic or in the instance, to signal to
both the compiler and the reader that the "old" freezing and elaboration rules
do not apply.

Otherwise, it would be way too easy to introduce dangerous behavior changes (and
access-before-elaboration exceptions) from supposedly harmless maintenance (and,
depending on the rules, even in existing "unlucky" instances).

> I really don't like the Unchecked_Conversion approach, but I don't see
> a better solution without some new language support.
>
> The new feature should also be useful in its own right for other
> things (i.e., traditional signature generics).

Right. Either proposal that I am suggesting (either PI for constants or
incomplete formals) expand the capabilities of preelaboration and generics.
Neither is a one-time hack.

> I hope to send out a proposal sometime soon.

Soon is too late unless it includes complete wording and can be vetted by Friday
(Letter Ballot for all remaining Ada 2012 proposals starts Friday). Which I
think is impossible...

I was planning to send out a e-mail straw poll this afternoon as to which
solution to peruse (we can't work on all of them at once, that's for sure). I
wanted to write up a concrete proposal for each of the options before doing
that.

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

From: Steve Baird
Sent: Thursday, April 21, 2011  6:00 PM

> A quick overview of the problem: AI05-0212-1 changes the specification of
 > the containers packages to look like:
 >
 > with Ada.Iterator_Interfaces;
 > generic
 >    ...
 > package Ada.Containers.Doubly_Linked_Lists is
 >    ...
 >
 >    type Cursor is private;
 >    ...
 >    No_Element : constant Cursor;
 >
 >    package List_Iterator_Interfaces is new
 >       Ada.Iterator_Interfaces (Cursor, No_Element); --(1)
 >
 >    ...
 >
 > Ed notes that the instantiation (1) is illegal because Cursor is not
 > completely defined.

This is a proposal (with fairly complete wording) for solving this problem.
Randy and Ed have provided useful feedback in putting this together, but don't
assume that this reflects their views. I'm not claiming that the ideas here are
original - I'm just trying to package things up in a way that perhaps we can go
forward with.

====

This proposal has three parts (but two are very easy):

   1) Introduce the notion of "signature generics" (all names are,
      of course, open for discussion). A generic package may be
      marked as a "signature generic" by specifying an aspect,
      or via a pragma.

      A signature generic must meet certain restrictions:
        a) It must be generic package.
        b) Its visible part may contain only declarations of
           interface types and abstract primitive subprograms
           thereof.
        c) Its private part must be empty.
        d) It cannot have a body.

     An instance of a signature generic does not cause freezing in the
     same way as an instance of a "normal" generic. There is no freezing
     associated with such an instance other than the freezing associated
     with any expressions which are evaluated as part of the evaluation
     of the actual parameters of the instantiation.

     The point of all this is to allow passing in a not-yet-completed
     private type as an actual corresponding to a formal private type.

[Note: restriction to interface types, as opposed to abstract types, allows us
to avoid having to worry about interactions between freezing and any static
expressions which might occur in a component declaration; we don't want any
expressions (and specifically static expressions) in a signature package's spec
other than default expressions (which have different freezing rules).]

[Note: We could allow signature generics to declare non-abstract primitive
subprograms of interface types (i.e., null procedures). We could also allow them
to declare nested (bodiless, non-generic) packages. These relaxations are
arguably reasonable, but it is easier to start out with rules that are too
strict and relax them later].

    2) Ada.Iterator_Interfaces is modified in two ways:
         a) It is marked as being a signature generic (it sounds like
            the pragma is the preferred mechanism for a generic package,
            but the mechanism used is a minor detail in any case).

         b) The No_Element formal parameter is replaced with an
            Has_Element predicate:

              with function Has_Element
                (Position : Cursor) return Boolean;

            In the wording for the dynamic semantics of generalized loop
            iteration, replace all occurrences of
              "is equal to No_Element"
            with equivalent wording expressed in terms of calls to
            Has_Element.

            This is needed so that the formal Cursor type can be
            a not-yet-completed private type; this would be impossible
            if a value type Cursor had to be passed in.

     3) The instances of Ada.Iterator_Interfaces in the various
        container specs are each updated to pass in their existing
        Has_Element function instead of a No_Element parameter.
        Declarations are reordered to make this work (either move the
        instance down or move the declaration of Has_Element up).

====

!wording (for change #1 of 3)

New section (12.9 - ?)

Signature Generics

A signature generic is a restricted form of generic package which may be
instantiated with a private type before it is completely defined (see 3.11.1).

Syntax
   The form of a pragma Signature, which is a program unit pragma
   (see  10.1.5), is as follows:

     pragma Signature;

Static Semantics

   For any generic package, the following language-defined aspect
   is defined:
    Signature
      The type of aspect Signature is Boolean. A generic package is
      said to be a *signature generic* if and only if the aspect
      Signature is True for the generic package.

   A pragma Signature specifies that the aspect Signature is True for a
   generic package. The pragma shall appear immediately within the
   visible part of a generic package, but not within
   a generic_formal_part.

[Do we want to allow an optional identifier, as with pragma Pure?
For now, no. We can relax this later]

Legality Rules

    The first list of basic_declarative_items for a signature generic
    (informally speaking, the visible part) shall include at most:
       - a pragma Signature
       - declarations of interface types and their primitive subprograms

    The second list of basic_declarative_items of a signature
    generic (informally speaking, the private part) shall be empty.

    A signature generic shall not have a body.


AARM note:
    The freezing rules for an instance of a signature generic are
    different than for an instance of a non-signature generic
    (see 13.14). These differences allow a signature generic to
    be instantiated with a type which has not been completed. For
    an example, see the instance of Ada.Iterator_Interfaces (which
    is a signature generic) in the specification of
    Ada.Containers.Doubly_Linked_Lists.

----

Replace 13.14(5)

   - The occurrence of a generic_instantiation causes freezing; also,
     if a parameter of the instantiation is defaulted, the
     default_expression or default_name for that parameter
     causes freezing.

with

   - The occurrence of a generic_instantiation causes freezing unless the
     instantiated generic is a signature generic; also,
     if a parameter of such an instantiation is defaulted, the
     default_expression or default_name for that parameter causes
     freezing.

   - Any expressions occurring anywhere within the generic_actual_part of
     an instantiation of a signature generic cause freezing; also, if a
     parameter of such an instantiation is defaulted, the
     default_expression or any expressions occurring within
     the default_name cause freezing.

     AARM note: in particular, actual type parameters for
     an instantiation of a signature generic do not cause freezing.
     This allows passing a type which has not been completed as
     a parameter without violating the freezing rules.

[Note: we are replacing one bulleted-list item with two (and an AARM note).]

[Note: the expression-freezing stuff also handles corner case stuff like passing
Array_Of_Tasks(Function_Call).Some_Entry or Some_Acc_To_Subp_Func.all as an
actual subprogram parameter]

====

!wording (for change #2 of 3)

In the spec for Ada.Iterator_Interfaces, replace

   generic
     type Cursor is private;
     No_Element : in Cursor;
   package Ada.Iterator_Interfaces is

with

   generic
     type Cursor is private;
     with function Has_Element (Position : Cursor) return Boolean is <>;
   package Ada.Iterator_Interfaces is
     pragma Signature;

[Note: seeing this example, would Signature_Generic be a better pregma/aspect
name than Signature ?]

In the dynamic semantics wording, replace
    "If the initial value is equal to No_Element"
   with
    "If Has_Element returns False for the initial value"

Replace
    "This repeats until the loop parameter is equal to No_Element"
   with
    "This repeats until Has_Element returns False for the loop parameter"

The above 2 replacements are each performed twice.

[Note: When we are done, there should be no occurrences of "No_Element"
in the wording describing this generic.]

====

!wording (for change #3 of 3)

In the !wording given in AI05-0212, replace

   package Vector_Iterator_Interfaces is new
    Ada.Iterator_Interfaces (Cursors, No_Element);

with

   function Has_Element (Position : Cursor) return Boolean;

   package Vector_Iterator_Interfaces is new
     Ada.Iterator_Interfaces (Cursor, Has_Element);

Also delete the existing declaration of Has_Element (we are just moving the
declaration of Has_Element without changes to an earlier point).

Note that this wording is prefaced in AI05-0212 with "Add the following with to
each container package:"; the same idea applies here - we do this for each
container package.

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:46 AM

> I still firmly believe that any such change to generics needs some
> sort of syntactic introduction, either in the generic or in the
> instance, to signal to both the compiler and the reader that the "old"
> freezing and elaboration rules do not apply.

And I firmly believe the opposite.  Adding such syntax would just be a nuisance,
and no Ada programmer is going to understand the subtle meaning of such syntax
anyway.

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

From: Tucker Taft
Sent: Friday, April 22, 2011  12:36 PM

> I still firmly believe that any such change to generics needs some
> sort of syntactic introduction, either in the generic or in the
> instance, to signal to both the compiler and the reader that the "old"
> freezing and elaboration rules do not apply.

And I firmly believe the opposite.  Adding such syntax would just be a nuisance,
and no Ada programmer is going to understand the subtle meaning of such syntax
anyway.

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

From: Steve Baird
Sent: Friday, April 22, 2011  1:08 PM

> It would sure help to have some examples. ;-)

I'll try to come up with something.

>
> Why are we calling it a "signature generic" if it contains
> declarations of interfaces?
> Perhaps "pragma Antifreeze"? ;-)
>

As I said in my original message,
   "all names are,of course, open for discussion".

I called them signature generics because I thought Randy wouldn't like me
calling them Frobisher generics (pending agreement on a better name).

Ed thought that the term "signature" is used in ML in some vaguely similar way;
I don't know.

> Or perhaps any generic without a body follows different freezing rules
> (essentially freeze the expansion), and "pragma No_Body" is a way to
> make it clear that there is no body.
>

With pragma No_Body, I think we would not need the new Signature aspect. We
could just say that the freezing rules are different for any generic which
happens to meet some list of restrictions, which would include the presence of a
No_Body pragma.

It is not obvious that this would be desirable.

Randy's position is that if we want a signature generic, we shuld somehow
explicitly say so in order to avoid cases where an innocent-looking change to a
generic breaks an instantiation elsewhere.

> I would also prefer if the presence of the "pragma"
> was not changing the semantics, but merely used as a way to verify
> that the package satisfied the requirements for a "non-freezing"
> generic.

It changes only the freezing rules for an instance, which is the whole point of
the proposal. We are taking an instance which would otherwise violate the
freezing rules and inventing a mechanism to make it legal.

> Wouldn't we know by the time
> we get to "freezing" whether or not there is a body, and whether the
> spec satisfies the requirements for being non-freezing?

What about the case where the body-or-not decision occurs in a different
compilation unit?

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  2:23 PM

...
> > Or perhaps any generic without a body follows different freezing
> > rules (essentially freeze the expansion), and "pragma No_Body" is a
> > way to make it clear that there is no body.
>
> With pragma No_Body, I think we would not need the new Signature
> aspect. We could just say that the freezing rules are different for
> any generic which happens to meet some list of restrictions, which
> would include the presence of a No_Body pragma.

This is the wrong interpretation. The critical point for Steve's model
(IMHO) is that there is no signficant *elaboration* in this generic unit.
Once that is the case, freezing is relatively unimportant, since one of its
primary purposes is to avoid access-before-elaboration problems.

Leaving out the body is just part of the restrictions needed to make that
happen. There can't be any variables, constants initialized with non-static
expressions, etc.

> It is not obvious that this would be desirable.
>
> Randy's position is that if we want a signature generic, we shuld
> somehow explicitly say so in order to avoid cases where an
> innocent-looking change to a generic breaks an instantiation
> elsewhere.

Right. Maintenance is the second reason for having an up-front marker. If
someone adds a variable to a generic specification that is being used as a
signature, it is far better that they get an immediate error rather than errors
far away in a project (and quite possibly in other people's code). This is
especially a problem with "canned" libraries like Claw (or the language-defined
Ada library). We probably have some generics that don't have bodies, but if that
automatically allows people to use them as signatures, that effectively means
that we can never add a body or make other similar changes (because the
compatibility cost would be too high). That's bad.

Implementation issues also come up. I want to know at the head of the package
whether or not any elaboration code, generic sharing, and the like are going to
apply to this generic unit. For us at least, a signature package would be
compiled very differently than a normal one (it would be much more of a
template), and having to wait to see the entire package is just too late for
that.

> > I would also prefer if the presence of the "pragma"
> > was not changing the semantics, but merely used as a way to verify
> > that the package satisfied the requirements for a "non-freezing"
> > generic.
>
> It changes only the freezing rules for an instance, which is the whole
> point of the proposal.
> We are taking an instance which would otherwise violate the freezing
> rules and inventing a mechanism to make it legal.

Right. And it adds some legality rules to the package (but so far as I can tell,
no semantic changes).

> > Wouldn't we know by the time
> > we get to "freezing" whether or not there is a body, and whether the
> > spec satisfies the requirements for being non-freezing?
>
> What about the case where the body-or-not decision occurs in a
> different compilation unit?

This is way too late, as noted above.

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

From: Jean-Pierre Rosen
Sent: Friday, April 22, 2011  3:52 PM

> With pragma No_Body, I think we would not need the new Signature
> aspect. We could just say that the freezing rules are different for
> any generic which happens to meet some list of restrictions, which
> would include the presence of a No_Body pragma.
>
> It is not obvious that this would be desirable.

I'm in favour of an aspect, by analogy with categorization pragmas (we could
even say it is a categorization pragma): it has some extra properties, provided
some restrictions are met.

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

From: Tucker Taft
Sent: Friday, April 22, 2011  4:06 PM

> With pragma No_Body, I think we would not need the new Signature
> aspect. We could just say that the freezing rules are different for
> any generic which happens to meet some list of restrictions, which
> would include the presence of a No_Body pragma.

Right.

>
> It is not obvious that this would be desirable.
>
> Randy's position is that if we want a signature generic, we shuld
> somehow explicitly say so in order to avoid cases where an
> innocent-looking change to a generic breaks an instantiation
> elsewhere.

I understand that, but my hope was that the pragma would not cause the change in
semantics, but merely indicate that we are expecting the "non-freezing"
semantics, and if there is something preventing that, warn us now rather than
when we do an instantiation that relies on non-freezing.

>> I would also prefer if the presence of the "pragma"
>> was not changing the semantics, but merely used as a way to verify
>> that the package satisfied the requirements for a "non-freezing"
>> generic.
>
> It changes only the freezing rules for an instance, which is the whole
> point of the proposal.
> We are taking an instance which would otherwise violate the freezing
> rules and inventing a mechanism to make it legal.

I understand that.  I was just trying to avoid having the pragma *change* the
semantics, but instead validate that the change is taking place due to other
considerations.

>> Wouldn't we know by the time
>> we get to "freezing" whether or not there is a body, and whether the
>> spec satisfies the requirements for being non-freezing?
>
> What about the case where the body-or-not decision occurs in a
> different compilation unit?

I guess I presumed that when you got to the part of the compiler that enforced
freezing rules, you would also be at the place where the presence or absence of
a body is known (even if it is in a different compilation unit). Of course with
shared generics, that may not work.

Somehow I find the combination of pragma No_Body and an optional "confirming"
pragma Non_Freezing preferable to a pragma that changes the freezing semantics.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  4:26 PM

...
> Somehow I find the combination of pragma No_Body and an optional
> "confirming" pragma Non_Freezing preferable to a pragma that changes
> the freezing semantics.

Would you feel better if it is an aspect? Seriously, I think of this as an
aspect with an optional pragma, not the other way around.

In any case, this is not just about freezing, or even mostly about freezing.
It's also about "no elaboration"; the body is only part of that.

Jean-Pierre wrote:

> I'm in favour of an aspect, by analogy with categorization pragmas (we
> could even say it is a categorization pragma):
> it has some extra properties, provided some restrictions are met.

Exactly. This is an aspect like a categorization pragma.

Just like the categorization pragmas, it really isn't necessary (the compiler
*could* figure out the right thing). But it is good to *declare* your
intentions, both for now, and for the future.

Bob seems to discount the "for the future" part, but I don't understand why.
When you are building reusable code that is being used by others, it is critical
to declare as much as possible of your intentions formally.

In this case, it is important to declare whether you intend to allow use of a
generic as a signature. That's because doing so puts a constraint on possible
future changes to the generic package. With that constraint visible, it is
obvious whether a proposed change is compatible or not. Otherwise, you are much
more likely to make a change and only find out from beta testers or (worse)
customers that the change is incompatible. (And given that the work-around
requires restructuring of the code, this isn't an compatiblity change I would
want to force on customers without a lot of consideration.)

This has happened to us of number of times related to various projects at RRS,
and it is not something that I want to introduce more ways to do in Ada. The
fewer implicit contracts that we can have, the better.

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

From: Bob Duff
Sent: Friday, April 22, 2011  4:54 PM

> Bob seems to discount the "for the future" part, but I don't understand why.

I just don't think it's that big of a deal, given that there are already many
ways to make incompatible changes to existing packages.  Yeah, if that package
is used by unknown clients, you have to be careful.

You might decide that "type Enum is (Red, Green);" needs a new enumeral
"Yellow".  If you control all the clients, you might decide to go ahead, and fix
all the clients that have "case" on that type.  If your customers control the
clients, you might shy away from that change. We don't need "pragma
Has_Exactly_Two_Enumerals(Enum);" to help with that decision.

Adding anything to a package spec might cause use-clause conflicts.

Pretty much anything visible to clients can cause incompatibilities if you
change it.

> When you are building reusable code that is being used by others, it
> is critical to declare as much as possible of your intentions formally.

I just don't think we need a zillion pragmas/aspects to declare every such
thing.  I fear programmers will just be confused by such "features".

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  5:21 PM

...
> You might decide that "type Enum is (Red, Green);" needs a new
> enumeral "Yellow".  If you control all the clients, you might decide
> to go ahead, and fix all the clients that have "case" on that type.
> If your customers control the clients, you might shy away from that
> change.
> We don't need "pragma Has_Exactly_Two_Enumerals(Enum);" to help with
> that decision.

No, because the enumeration says exactly that. But it might be valuable to have
an aspect (nobody uses pragmas anymore ;-) that declared that a particular
enumeration is intended to extended. Such an aspect cause a warning that case
statements without "others" are not recommended. If combined with some way to
specify "new enumerations" in a case statement, it could even be an error.

Currently, you can only put a comment there, which users tend to ignore. :-)

> Adding anything to a package spec might cause use-clause conflicts.
>
> Pretty much anything visible to clients can cause incompatibilities if
> you change it.

True enough. But adding names or parameters, or changing types or subtypes are
things that everyone reasonably experienced knows cause incompatibilities. No
one expects that adding a declaration with a non-conflicting name would be
incompatible other than to the terminally unlucky. This case is much worse than
that.

> > When you are building reusable code that is being used by others, it
> > is critical to declare as much as possible of your intentions formally.
>
> I just don't think we need a zillion pragmas/aspects to declare every
> such thing.

I don't want a zillion, but a half zillion would seem about right. :-) Global
in/global out and exception contracts are more instances of declaring exactly
what you want and having them checked as well. The fact that the compiler
enforces these extra contracts is an important part of the functionality, and
the same is true for the signature. (And note that all of these are mostly about
optimization, at least from the perspective of a compiler, they don't do a lot
for the programmer directly.)

> I fear programmers will just be confused by such "features".

It's possible, but I view these as power tools to mostly be used by experts.
(That's true of all generic construction.) OTOH, users of these tools don't need
to think about it much (the compiler will complain if they get it wrong), and
the difference is obvious and up-front.

My mantra: If in doubt, have an explicit declaration.

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

From: Tucker Taft
Sent: Friday, April 22, 2011  4:27 PM

> Somehow I find the combination of pragma No_Body and an optional
> "confirming" pragma Non_Freezing preferable to a pragma that changes
> the freezing semantics.

Another thing about this approach is that pragma No_Body would be unnecessary
for generics that are library units, since for a library unit generic, pragma
"No_Body" is implicit if it doesn't need a body.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011   5:05 PM

> > Somehow I find the combination of pragma No_Body and an optional
> > "confirming" pragma Non_Freezing preferable to a pragma that changes
> > the freezing semantics.
>
> Another thing about this approach is that pragma No_Body would be
> unnecessary for generics that are library units, since for a library
> unit generic, pragma "No_Body" is implicit if it doesn't need a body.

That's exactly what I don't want: implicit behavior that can change drastically wth tiny changes in maintenance -- it is a real headache for reusable code.

In any case, I don't think what you are talking about really works. As
previously noted, there are two important properties being guaranteed here.
These properties have the effect of making our previous concerns with such
proposals moot.
(1) No elaboration code (at all). A body would be OK if it did not have any
    elaboration code (but it wouldn't pass the next one).
(2) Nothing can be done with formal type parameters that require them to be
    frozen. That does seem to prevent having a body (since bodies freeze
    everything), although it is arguable whether formal parameters follow normal
    freezing in that way.

The restrictions that Steve proposed have this effect (although they definitely
go further than necessary). Note that neither of the above reasons say anything
whatsoever about the formal parameters, which is why there are no restrictions
on them. But simply disallowing a body does not guarantee either of these
properties.

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

From: Tucker Taft
Sent: Friday, April 22, 2011  5:31 PM

I don't understand the "no elaboration" stuff.

All we really want is for freezing to happen on the *expansion* of the spec, and
for there to be no body.  This is as opposed to arbitrarily freezing all of the
actual types, even though they aren't necessarily used in the generic spec in
any way that requires freezing.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  5:56 PM

NO!!!

What we want is for the specification of the generic to do no freezing at all of
formal types (when expanded or originally). Otherwise, we reignite all of the
debates about piece-meal freezing. (This is late minute, it has to be simple --
Steve's proposal is, what you are describing above is not.)

Similarly, for this to work sanely, there can't be any code associated with the
generic unit. That surely includes objects of formal types, but I think it
includes other sorts of things as well. (Ed had indicated some similar issue
privately, but I don't know the details. It's why no objects are allowed in
Steve's proposal.)

It's possible that I focused on elaboration more because the code generation
issues are much more important to me, and the truly critical point is that there
is no uses of a generic formal that causes freezing (this necessarily eliminates
the bulk of possible elaboration code). I don't know for sure about that; the
elimination of any code at all seems like a large bonus to me because it frees
our compiler from any considerations about sharing. That's pretty much the only
way that could happen (supporting two methods of generic units would be
untenable, it's barely possible to support one).

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

From: Steve Baird
Sent: Friday, April 22, 2011   6:05 PM

> All we really want is for freezing to happen on the *expansion* of the
> spec, and for there to be no body.  This is as opposed to arbitrarily
> freezing all of the actual types, even though they aren't necessarily
> used in the generic spec in any way that requires freezing.

This sounds like the "fine-granularity freezing" model that has been discussed
previously.

The rough idea is that the freezing associated with an expanded spec is the same
what would have resulted if the expansion had been performed at the source level
(with appropriate subtypes and renames to express the actual/formal bindings).

This is an elegant approach, but the last time we discussed this it was agreed
that requiring this would be too much of an earthquake for compiler
implementers.

One advantage of the signature generic proposal is that the restrictions imposed
on a signature generic make it much easier to implement the freezing associated
with an instance thereof. In the case of a generic which happens to meet the
restrictions associated with being a signature generic, I believe the freezing
rules given in the signature generic proposal (which are intended to be easy to
implement) are equivalent to what you would get from fine-grained freezing.

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

From: Steve Baird
Sent: Friday, April 22, 2011   5:24 PM

> Another thing about this approach is that pragma No_Body would be
> unnecessary for generics that are library units, since for a library
> unit generic, pragma "No_Body" is implicit if it doesn't need a body.

Yes, if you really wanted to go whole-hog, you could define "known to be
bodiless", which could know about

   1) The No_Body pragma/aspect
   2) The rules for library unit bodies
      (e.g., a generic declared within a library unit package spec where
       the enclosing package cannot have a body certainly can't have
       a body itself)
   3) All the cases where the body, if present, must be in the
      same compilation unit as the spec (don't forget to deal
      with subunits here).

I suppose we could throw this in if we get a lot of complaints that the current
proposal is insufficiently complicated.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   7:29 PM

Introduction to upcoming straw poll

Given that our self-imposed deadline for finishing work on the standard has
passed, I would like to get a sense as to which of the possible solutions we
ought to use. In order to get an answer to that, I am calling a straw poll on
this question.

What I will do over the next couple of hours is send each of the four proposed
practical solutions to the list, written up in the same form for each, followed
by a ballot. Your job will be to read each of the proposed solutions and then
vote on which solutions you would prefer that the standard uses.

Thanks in advance for your time.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   7:39 PM

Solution #1: Rejiggering

For our first solution to this problem, we will not consider any additional language features.

1) Ada.Iterator_Interfaces is modified by replacing the No_Element formal parameter is replaced with an Has_Element predicate:

     with function Has_Element
        (Position : Cursor) return Boolean;

     In the wording for the dynamic semantics of generalized loop
     iteration, replace all occurrences of
       "is equal to No_Element"
      with equivalent wording expressed in terms of calls to Has_Element.

2) The declaration of the cursor type in each container is replaced by:

   package Cursors is
      type Cursor is private;
      No_Element : constant Cursor;
   private
      -- .. Not specified by the language.
   end Cursors;
   subtype Cursor is Cursors.Cursor;
   function "=" (Left, Right : Cursor) renames Cursors."=";
   No_Element : constant Cursor := Cursors.Cursor;

3) The instances of Ada.Iterator_Interfaces in the various
   container specs are each updated to pass in their existing
   Has_Element function instead of a No_Element parameter.
   The declaration of Has_Element is moved to the just in front
   of the generic instance.

=======================================

Pros:
  (1) No new language features needed.
Cons:
  (1) Using a cursor in the body of a containers package will require
      Unchecked_Conversion.
  (2) This is (slightly) incompatible, as operations on type Cursor that are
      primitive in Ada 2005 are not primitive in Ada 2012. This is unlikely to
      matter (derivation of type Cursor causes nasty effects if done with an
      extension of the container type).
  (3) By switching to a function, it is slightly harder to write an iterator and
      probably slightly less efficient (depending on automatic inlining of
      "Has_Element". For instance, to create an iterator on an access type, one
      would need to create a function that always compares against null (an
      expression function would do nicely).

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:42 AM

> For our first solution to this problem, we will not consider any
> additional language features.

>    package Cursors is
>       type Cursor is private;
>       No_Element : constant Cursor;
>    private
>       -- .. Not specified by the language.
>    end Cursors;
>    subtype Cursor is Cursors.Cursor;
>    function "=" (Left, Right : Cursor) renames Cursors."=";
>    No_Element : constant Cursor := Cursors.Cursor;

I assume that's supposed to be ":= Cursors.No_Element".

>   (3) By switching to a function, it is slightly harder to write an
> iterator and probably slightly less efficient (depending on automatic
> inlining of "Has_Element". For instance, to create an iterator on an
> access type, one would need to create a function that always compares
> against null (an expression function would do nicely).

I don't think we should worry about efficiency at that level.
If it's inefficient because of poor support for inlining, then implementations
should improve their inlining support, or else just live with it.  (I think GNAT
is in that boat!) There's nothing *fundamentally* inefficient, here.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   7:47 PM

Solution #2: Preelab_Init for objects

For our second solution to this problem, we will consider adopting
Preelaborable_Initialization to apply to objects as well as types.

1) pragma Preelaborable_Initialization (PI) is extended to deferred constants;
   objects also can have PI.

    The name of an object has PI if:
        * it is a static expression;
        * it denotes a constant initialized by an aggregate whose components are
	  all:
              * the name of an object with PI and whose type is not controlled
		[Note: so no Adjust calls are involved]; or
              * <>, and the type of the component has PI.

    Pragma PI may apply to a deferred constant. If pragma PI applies to a
    deferred constant, the full constant declaration shall have PI.

Change 10.2.1(8) to say that "...unless the name denotes an object that has PI,
or ...".

2) The declaration of the cursor type in each container is replaced by:

   package Cursors is
      type Cursor is private;
      No_Element : constant Cursor;
      pragma Preelaborable_Initialization (No_Element);
   private
      -- .. Not specified by the language.
   end Cursors;
   subtype Cursor is Cursors.Cursor;
   function "=" (Left, Right : Cursor) renames Cursors."=";
   No_Element : constant Cursor := Cursors.Cursor;

=======================================

Pros:
  (1) Not necessary to change the definition of iterators; constants like "null"
      can be used directly.
  (2) Adds capabilities to preelaborated packages (more constants can be used).
Cons:
  (1) Using a cursor in the body of a containers package will require
      Unchecked_Conversion.
  (2) This is (slightly) incompatible, as operations on type Cursor that are
      primitive in Ada 2005 are not primitive in Ada 2012. This is unlikely to
      matter (derivation of type Cursor causes nasty effects if done with an
      extension of the container type).

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:43 AM

> 1) pragma Preelaborable_Initialization (PI) is extended to deferred
> constants; objects also can have PI.
>
>     The name of an object has PI if:
>         * it is a static expression;
>         * it denotes a constant initialized by an aggregate whose
>           components are all:
>               * the name of an object with PI and whose type is not
>                 controlled [Note: so no Adjust calls are involved]; or
>               * <>, and the type of the component has PI.

I don't see any mention of allowing "null" here.

But:

>   (1) Not necessary to change the definition of iterators; constants
> like "null" can be used directly.

Apparently it's intended to allow null.

What about 'Access of a statically declared (lib level) object?

================

Same problem as Solution #1:

   No_Element : constant Cursor := Cursors.Cursor;

I think ":= Cursors.No_Element" was meant.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   8:05 PM

Solution #3: Incomplete formal types

For our third solution to this problem, we will reintroduce incomplete formal
types.

1) We adopt the solution as written up in AI05-0213-1 to add incomplete formal
   types.

   This looks, as you might expect, like a stand-alone incomplete type
   declaration. It has the semantics of an incomplete type within the generic
   unit (thus, no objects or components, OK in subprogram profiles).

   The actual for such a formal can be any type, and in particular the actual is
   not frozen at the point of the instance. (This allows the actual to be an
   incomplete type or a private type.)

   There is a detailed proposal in AI05-0213-1 which I will not repeat here.

2) Ada.Iterator_Interfaces is modified by:
    A) Changing type Cursor to be an incomplete formal type:

      type Cursor;

    B) Replacing the No_Element formal parameter is replaced with an Has_Element
       predicate:

      with function Has_Element
         (Position : Cursor) return Boolean;

      In the wording for the dynamic semantics of generalized loop
      iteration, replace all occurrences of
        "is equal to No_Element"
      with equivalent wording expressed in terms of calls to Has_Element.

[Note: The latter is necessary as a formal object cannot be of an incomplete
type, but a parameter can be of an incomplete type.]

3) The instances of Ada.Iterator_Interfaces in the various
   container specs are each updated to pass in their existing
   Has_Element function instead of a No_Element parameter.
   The declaration of Has_Element is moved to the just in front
   of the generic instance.

=======================================

Pros:
   (1) Restructuring of the containers packages is minimal, and there is no
       incompatibility.
   (2) The new formal will be useful for signature generics and probably in
       other ways as well. Ada provides formals for many useful categories of
       types; it is surprising that a completely universal type is not
       available.
   (3) No possibly unnatural restrictions on the contents of the generic (beyond
       the existing limitations on incomplete types).
   (4) AI05-0213-1 was included in the scope of Ada 2012, so there can be no
       argument that this is a legitimate inclusion in the Standard. (Unlike
       Solutions #2 and #4.)

Cons:
   (1) A new formal type? Really?? :-) Language complexity is increased.
   (2) Getting the freezing rules for an instance exactly right is tricky (I
       don't think the wording in AI05-0213-1 is quite right.)
   (3) By switching to a function, it is slightly harder to write an iterator
       and probably slightly less efficient (depending on automatic inlining of
       "Has_Element". For instance, to create an iterator on an access type, one
       would need to create a function that always compares against null (an
       expression function would do nicely).

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:45 AM

>    (4) AI05-0213-1 was included in the scope of Ada 2012, so there can
> be no argument that this is a legitimate inclusion in the Standard.
> (Unlike Solutions #2 and #4.)

I find it hard to take this sort of argument seriously.  I mean, if iterators
are in scope, then anything it takes to make iterators work well is in scope.
And if that's too much work, then we should drop iterators.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  5:23 PM

Tucker has convinced me that I was confused about the freezing rules. The ones
in the draft AI (AI05-0213-1) are just fine, so far as I can tell.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   8:18 PM

For our fourth solution to this problem, we will introduce declared signature
generics.

1) Introduce the notion of "signature generics". A generic package may be marked
   as a "signature generic" by specifying an aspect, or via a pragma.

 A signature generic must meet certain restrictions:
    a) It must be generic package.
    b) Its visible part may contain only declarations of
       interface types and abstract primitive subprograms
       thereof.
    c) Its private part must be empty.
    d) It cannot have a body.

An instance of a signature generic does not cause freezing in the same way as an
instance of a "normal" generic. There is no freezing associated with such an
instance other than the freezing associated eith any expressions which are
evaluated as part of the evaluation of the actual parameters of the
instantiation.

Steve's e-mail provided wording for this proposal, along with justifications for
these rules. I won't repeat them here.

2) Ada.Iterator_Interfaces is modified by:
    A) Adding aspect "Signature" to its specification.
    B) The No_Element formal parameter is replaced with an Has_Element
       predicate:

      with function Has_Element
         (Position : Cursor) return Boolean;

      In the wording for the dynamic semantics of generalized loop
      iteration, replace all occurrences of
        "is equal to No_Element"
      with equivalent wording expressed in terms of calls to Has_Element.

[Note: The latter is necessary as passing a formal object to a signature generic
freezes the object, and that would not work for the containers where the object
is a deferred constant.]

3) The instances of Ada.Iterator_Interfaces in the various
   container specs are each updated to pass in their existing
   Has_Element function instead of a No_Element parameter.
   The declaration of Has_Element is moved to the just in front
   of the generic instance.

=======================================

Pros:
   (1) Restructuring of the containers packages is minimal, and there is no
       incompatibility.
   (2) The kind of generic specification will be useful for signature generics.

Cons:
   (1) The restrictions on the contents are rather arbitrary, and probably will
       be annoying in some uses.
   (2) Language complexity and implementation complexity is increased. (But
       probably not a lot; such a generic cannot have any elaboration code, and
       thus never has any presence in the generated code -- it is purely a
       symboltable template that even code sharing implementations can handle.)
   (3) By switching to a function, it is slightly harder to write an iterator
       and probably slightly less efficient (depending on automatic inlining of
       "Has_Element". For instance, to create an iterator on an access type, one
       would need to create a function that always compares against null (an
       expression function would do nicely).

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   8:25 PM

Here is the straw poll ballot.

Please rank the following solutions (as outlined in previous e-mail messages on
this list) from 1 (preferred) to 4 (least preferred):

________  Solution #1 - Rejiggering with no language changes


________  Solution #2 - Preelaborable_Initialization for objects


________  Solution #3 - Formal incomplete types


________  Solution #4 - Declared signature generic packages


________  Solution #5 - Write-in

________________________________________________

Please vote by Monday evening Wisconsin time (-5 UTC).

P.S. Yes, I realize this is somewhat overkill for this particular problem;
however, I need to know the form of the solution soon so that I can make the
extensive changes to the containers packages in the draft standard. And our next
meeting is at the end of June, way too late. So this ballot is the next best
choice, especially to find out what the "lurkers" think.

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

From: Randy Brukardt
Sent: Thursday, April 21, 2011   8:45 PM

Here is my ballot and some commentary:

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least
> preferred):
>
>
> ___3____  Solution #1 - Rejiggering with no language changes
>
>
> ___4____  Solution #2 - Preelaborable_Initialization for objects
>
>
> ___1____  Solution #3 - Formal incomplete types
>
>
> ___2____  Solution #4 - Declared signature generic packages
>
>
> ________  Solution #5 - Write-in
__________________________________________


I prefer the formal incomplete solution because it seems like it will be more
generally useful than the others, and in particular it will not look as strange
in future versions of Ada if a more general solution to this problem is adopted.
(At worst, it would be a little-used formal type, like formal arrays and in out
objects.) In addition, it doesn't require (minor) compatibility issues with the
containers packages, and doesn't require using Unchecked_Conversion in the
bodies.

I do worry a bit about the freezing rules for instances; the rule proposed in
AI05-0213-1 isn't quite right (the instance would freeze everything, making it
irrelevant as to whether the actual type parameter is frozen or not). The rule
needs to be more judious about what is frozen (most likely, only the actuals of
a generic instantiation that includes a formal incomplete parameter should be
frozen). Otherwise, I don't see an issue here, the generic unit freezes as it
currently does (no changes are needed), and the elaboration also is unchanged.

Steve's signature generics is a close second. It has less possibility of trouble
with freezing rules, but the restrictions are such that it wouldn't be useful
for a lot beyond this particular package. The implementation appears about the
same (not a major problem) for both, as is the effect on the containers
packages. It would be possible to relax these restrictions in a future Ada
version, so this might be more useful in the future. OTOH, if a more general
feature is added in the future, this will look as logical as a third eye, and
about as useful. (At least as an aspect, it could be buried in Annex J with
minimal impact.)

Solutions #1 and #2 have the ugly restructuring, with its compatibility problem
and the ugly use of Unchecked_Conversion in the body. That ugliness is permanent
once introduced, so I want to avoid that if possible. I'll live with #1 if
nothing else will fly; #2 doesn't seem to have enough to recommend it to bother
with that option. (Steve's idea of changing the formal object to a formal
function eliminated most of the need for it.)

The write-in blank was provided so that Bob could feel better about ranting
about fixing the problem "right". It's way too late for such a solution, and as
we determined a couple of years ago, child or nested packages are actually
pretty adequate for solving this problem in many real examples. The main problem
with using nested packages also occurs for instances in their own right, and we
effectively decided that the fixes were as bad as the disease there (i.e.
integrated packages).

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

From: Edmond Schonberg
Sent: Thursday, April 21, 2011   9:46 PM

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least preferred):
>
>
> ___4_____  Solution #1 - Rejiggering with no language changes
>
>
> ---------3----  Solution #2 - Preelaborable_Initialization for objects
>
>
> ____2____  Solution #3 - Formal incomplete types
>
>
> ____1____  Solution #4 - Declared signature generic packages
>
>
> ________  Solution #5 - Write-in

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

From: Tucker Taft
Sent: Thursday, April 21, 2011  10:05 PM

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least preferred):
>
>
> ____4____  Solution #1 - Rejiggering with no language changes
>
>
> _____1___  Solution #2 - Preelaborable_Initialization for objects
>
>
> _____2___  Solution #3 - Formal incomplete types
>
>
> ____3____  Solution #4 - Declared signature generic packages
>
>
> ________  Solution #5 - Write-in

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

From: Jean-Pierre Rosen
Sent: Friday, April 22, 2011  6:06 AM

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least preferred):
>
> _____2___  Solution #1 - Rejiggering with no language changes
>
> _____4___  Solution #2 - Preelaborable_Initialization for objects
>
>
> _____1___  Solution #3 - Formal incomplete types
>
>
> _____3__  Solution #4 - Declared signature generic packages
>

#3 looks like the cleanest solution, and the only one where the new feature
seems to have usefulness that extends beyond the immediate need. I'm a bit
worried that those who understand freezing rules say that there may be "some
issues" with them...

#1 is the less disruptive to the language, but I'm quite worried that the only
way to implement the containers in full Ada is by cheating with U_C (we're
really violating the privacy principles here).

#4 looks too much like an ad-hoc solution. I doubt (but I may be wrong) that
there will be much uses for the functionality beyond containers.

#2 I already have a hard time understanding PI... And I doubt that any normal
and sane person (i.e. not belonging to the ARG) whose gerenics are rejected for
a similar reason will be able to discover that PI of objects can save the day.

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

From: Brad Moore
Sent: Friday, April 22, 2011  10:17 AM

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least preferred):
>
>
> _____4___  Solution #1 - Rejiggering with no language changes
>
>
> _____3___  Solution #2 - Preelaborable_Initialization for objects
>
>
> ____1____  Solution #3 - Formal incomplete types
>
>
> ____2____  Solution #4 - Declared signature generic packages
>
>
> _See Below_  Solution #5 - Write-in
> ________________________________________________
>

#1 and #2, I feel the language has a hole if iterable containers cannot be
written without having to do the unchecked conversion trick in the body of the
container.

#3 Seems more useful than #4, and easier to understand, from a user perspective.
(Though I suspect more difficult to implement than #4?)

I am concerned about the difficulty in writing iterators that #1, #3, and #4
share. What I'd really like to see is the best of both worlds.  #2 plus #3.
Could that work?

Specifically, could a formal object be of an incomplete type if the object had
preelaborable initialization?

The #3 proposal would look the same except that instead of modifying
Ada.Iterator_Interfaces to change No_Element to Has_Element, a pragma
Preelaborable_Initialization would be added to the No_Element formal object. The
pragma would also need to be applied to all No_Element object declarations in
the containers.

If it was workable, then wouldn't the pros and cons of that combination be;

Pros:
   (1) Not necessary to change the definition of iterators; constants like
       "null" can be used directly.
   (2) Adds capabilities to preelaborated packages (more constants can be used).
   (3) Restructuring of the containers packages is minimal, and there is no
       incompatibility.
   (4) The new formal will be useful for signature generics and probably in
       other ways as well. Ada provides formals for many useful categories of
       types; it is surprising that a completely universal type is not
       available.
   (5) No possibly unnatural restrictions on the contents of the generic (beyond
       the existing limitations on incomplete types).

Cons:
   (1) A new formal type? Really??:-)  Language complexity is increased.
   (2) Getting the freezing rules for an instance exactly right is tricky (Randy
       doesn't think the wording in AI05-0213-1 is quite right.)

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

From: Steve Baird
Sent: Friday, April 22, 2011  11:29 AM

Please rank the following solutions (as outlined in previous e-mail messages on this list) from 1 (preferred) to 4 (least preferred):


___3____  Solution #1 - Rejiggering with no language changes


___4____  Solution #2 - Preelaborable_Initialization for objects


__ 2 ___  Solution #3 - Formal incomplete types


__ 1 __  Solution #4 - Declared signature generic packages


To me, the key point is avoiding the need for Unchecked_Conversion.

Thus, either of solutions 3 or 4 seem substantially better than either of
solutions 2 or 1.

My preferences for 4 over 3 or for 1 over 2 are much weaker.

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:45 AM

> > Please rank the following solutions (as outlined in previous e-mail
> > messages on this list) from 1 (preferred) to 4 (least
> > preferred):
> >
> >
> > ___3____  Solution #1 - Rejiggering with no language changes
> >
> >
> > ___4____  Solution #2 - Preelaborable_Initialization for objects
> >
> >
> > ___1____  Solution #3 - Formal incomplete types
> >
> >
> > ___2____  Solution #4 - Declared signature generic packages

I asked a few questions about these solutions, but before hearing the answers, I
think my ranking is identical to Randy's above.

I think requiring Unchecked_Conversion is equivalent to requiring compiler magic
-- it's really not a solution

However:

> > ________  Solution #5 - Write-in

> The write-in blank was provided so that Bob could feel better about
> ranting about fixing the problem "right".

Thanks.  ;-)

I do prefer the following over the above:

    - Fix it "right", even if that requires delaying the Standard.
      I have never understood the 2012 hurry.

or:

    - Realize that we don't have a good solution in time,
      and drop iterators.  There's always 2020.

>...It's way too late for such a solution, and  as we determined a
>couple of years ago, child or nested packages are  actually pretty
>adequate for solving this problem in many real examples. The  main
>problem with using nested packages also occurs for instances in their
>own right, and we effectively decided that the fixes were as bad as the
>disease there (i.e. integrated packages).

If we had "pretty adequate" solution(s), we wouldn't be having this discussion!

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

From: John Barnes
Sent: Friday, April 22, 2011  12:05 PM

Being very hot today and having just bashed my lip, bruised my jaw and  cut my chin when splitting a log, I thought I would retire and read some gentle email. And Lo and Behold an exciting ballot.

And transferable votes no less.

> Here is the straw poll ballot.
>
> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least preferred):
>
>
> _____3___  Solution #1 - Rejiggering with no language changes
>
>
> _____1___  Solution #2 - Preelaborable_Initialization for objects
>
>
> ______2__  Solution #3 - Formal incomplete types
>
>
> ____4____  Solution #4 - Declared signature generic packages

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

From: Tucker Taft
Sent: Friday, April 22, 2011  12:39 PM

Formal incomplete types seems to be
everyone's second choice.  Always a
bridesmaid... ;-)

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

From: John Barnes
Sent: Friday, April 22, 2011  1:24 PM

Au contraire, it was the first choice of Jean_Pierre, Brad and Bob.

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

From: John Barnes
Sent: Friday, April 22, 2011  1:26 PM

And Randy's frst choice. Could be a winner.

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

From: Robert Dewar
Sent: Friday, April 22, 2011  1:51 PM

Roberts vote
>
> ___3_____  Solution #1 - Rejiggering with no language changes
>
>
> ___4_____  Solution #2 - Preelaborable_Initialization for objects
>
>
> ___1_____  Solution #3 - Formal incomplete types
>
>
> ___2_____  Solution #4 - Declared signature generic packages

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  2:24 PM

I think formal incomplete types is ahead by a nose at the moment.

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

From: Erhard Ploedereder
Sent: Monday, April 25, 2011  8:19 AM

Please rank the following solutions (as outlined in previous e-mail messages on this list) from 1 (preferred) to 4 (least preferred):


___3____  Solution #1 - Rejiggering with no language changes


___4____  Solution #2 - Preelaborable_Initialization for objects


__ 1 ___  Solution #3 - Formal incomplete types


__ 2 __  Solution #4 - Declared signature generic packages


________  Solution #5 - Write-in


#1 and #2 look like a local hack and still have the U_C problem.

#4 is "too much concept" to solve a seemingly simple issue. If it could be argued that the feature is really useful in general (and hence be included almost for its own sake), I might switch preferences between #3 and #4.


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

From: Gary Dismukes
Sent: Monday, April 25, 2011  5:41 PM

> ____3___  Solution #1 - Rejiggering with no language changes
>
>
> ____4___  Solution #2 - Preelaborable_Initialization for objects
>
>
> ____1___  Solution #3 - Formal incomplete types
>
>
> ____2___  Solution #4 - Declared signature generic packages
>
>
> ________  Solution #5 - Write-in
> ________________________________________________
>

I'd really like to avoid the need for unchecked conversions.

Although I definitely find myself leaning toward #3, which seems like it would
potentially be more generally useful than just solving this problem, I wonder if
I'm not appreciating more general benefits of #4 (which I haven't managed to
fully digest in my quick reading of messages), and also wonder whether there
could be hidden complexities of #3, though on the surface (and based on mail
messages) it sounds like it's safe and straightforward enough (in terms of not
having semantic, usability, or implementation gotchas).

> Please vote by Monday evening Wisconsin time (-5 UTC).

Not sure what counts as the start of evening in Wisconsin, but hopefully my vote
will get counted. :-)

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  4:23 PM

Here are the results of the straw poll ballot:

> Please rank the following solutions (as outlined in previous e-mail
> messages on this list) from 1 (preferred) to 4 (least
> preferred):

_3_4_4_2_4_3_3_3_3_3_3_  Solution #1 - Rejiggering with no language changes

Average: 3.18. Median: 3.

_4_3_1_4_3_4_4_1_4_4_4_  Solution #2 - Preelaborable_Initialization for objects

Average: 3.27. Median: 4.

_1_2_2_1_1_2_1_2_1_1_1_  Solution #3 - Formal incomplete types

Average: 1.36. Median: 1.

_2_1_3_3_2_1_2_4_2_2_2_  Solution #4 - Declared signature generic packages

Average: 2.18. Median: 2.

Eleven votes talied. The results seem pretty clear. I'll write these up using
solution #3.

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

From: Bob Duff
Sent: Friday, April 22, 2011  11:45 AM

> This proposal has three parts (but two are very easy):
>
>    1) Introduce the notion of "signature generics" (all names are,
>       of course, open for discussion).

The word "generic" is an adjective.  Informally, we use "generic"
as a noun, but I think the RM always says "generic package"
or "generic unit" or whatever.

Therefore, I think these things should be call "signatures".
As in, "A *signature* is a generic package ...[with certain properties, or with
a certain pragma, or ...]".

Or, if you like extra verbiage, it could be "A *generic signature
package* (also known as a *signature*) is ..."  And then use "signature" where
it's clear, and "generic signature package" where the shorthand is unclear.

>...A generic package may be
>       marked as a "signature generic" by specifying an aspect,
>       or via a pragma.

Why does it have to be marked?  That is, why not say it's a signature if it
obeys the restrictions?

I understand that the freezing rules change a little, but can you should an
example of a currently-legal program whose run-time semantics would change?

>       A signature generic must meet certain restrictions:
>         a) It must be generic package.
>         b) Its visible part may contain only declarations of
>            interface types and abstract primitive subprograms
>            thereof.
>         c) Its private part must be empty.
>         d) It cannot have a body.

Don't you need some restrictions on the formals?
I thought this whole discussion was about the fact that No_Element doesn't work
-- did you intend to forbid generic formal objects?  I guess I'm confused...

>    generic
>      type Cursor is private;
>      with function Has_Element (Position : Cursor) return Boolean is <>;
>    package Ada.Iterator_Interfaces is
>      pragma Signature;
>
> [Note: seeing this example, would Signature_Generic be a better
> pregma/aspect name than Signature ?]

No.  See above.

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

From: Steve Baird
Sent: Friday, April 22, 2011  12:09 AM

> Or, if you like extra verbiage, it could be "A *generic signature
> package* (also known as a *signature*) is ..."  And then use
> "signature" where it's clear, and "generic signature package"
> where the shorthand is unclear.

Sounds good to me.

> Why does it have to be marked?  That is, why not say it's a signature
> if it obeys the restrictions?
>

A generic signature package cannot have a body.
I think this implies that it has to be marked.
Recall that cases exist where you can't tell whether a generic package will have
a body when the spec is seen.

> I understand that the freezing rules change a little, but can you
> should an example of a currently-legal program whose run-time
> semantics would change?
>
>>       A signature generic must meet certain restrictions:
>>         a) It must be generic package.
>>         b) Its visible part may contain only declarations of
>>            interface types and abstract primitive subprograms
>>            thereof.
>>         c) Its private part must be empty.
>>         d) It cannot have a body.
>
> Don't you need some restrictions on the formals?
> I thought this whole discussion was about the fact that No_Element
> doesn't work -- did you intend to forbid generic formal objects?  I
> guess I'm confused...

No restrictions on formals/actuals. One of the major advantages of this proposal
is that it allows "traditional" signature generics: that is, a generic package
with an arbitrary formal part, a completely empty spec (and private part), and
no body.

Another generic (which may or may not be a signature generic) can then take a
formal instance of the signature generic.

Thus, this proposal is a two-fer: we solve the problem with iterators and we get
functionality which is useful in its own right.

To make this work, we freeze expressions occurring in actual parameters. This
freezing has no effect in the case where the actual parameter is a type or a
(statically named) subprogram because no expressions are present.

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

From: Dan Eilers
Sent: Friday, April 22, 2011  12:33 PM

> A generic signature package cannot have a body.
> I think this implies that it has to be marked.
> Recall that cases exist where you can't tell whether a generic package
> will have a body when the spec is seen.

Yes, but this ambiguity is evil, and has caused compilers to generate bad code
(see http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=243811). There would not
be any great harm in requiring generic packages that have a body they don't need
to be marked with pragma elaborate_body.

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

From: Steve Baird
Sent: Friday, April 22, 2011  1:18 PM

I agree that it would be nice if it were known from a generic package's spec
whether it was going to have a body and your solution sounds reasonable, but I
don't think anything like this is going to make it into Ada 2012.

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

From: Robert Dewar
Sent: Friday, April 22, 2011  1:48 PM

> Yes, but this ambiguity is evil, and has caused compilers to generate
> bad code (see http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=243811).
> There would not be any great harm in requiring generic packages that
> have a body they don't need to be marked with pragma elaborate_body.

yes, there would! It would be a HUGE incompatibility. I know software folks
often think that if you can fix an incompatibility with a simple edit, then you
don't have to worry about, such folks do not live in the real world!

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

From: Steve Baird
Sent: Friday, April 22, 2011  1:54 PM

Dan Eilers wrote:
> There would not be any great harm in requiring generic packages that
> have a body they don't need to be marked with pragma elaborate_body.

Robert Dewar wrote:
>  It would be a HUGE incompatibility.

I agree with Robert.
The problem being solved would not justify the incompatibility.

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

From: Dan Eilers
Sent: Friday, April 22, 2011  2:04 PM

> yes, there would! It would be a HUGE incompatibility.  ...

Do you have any data to back this up?
Since Gnat and possibly other compilers have gone many years without
implementing this correctly, it is hard to believe that it is common. And it is
the best kind of incompatibility, one that is detected by the compiler, causing
the program to be rejected, with a one-line fix.

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

From: Robert Dewar
Sent: Friday, April 22, 2011  2:13 PM

> Do you have any data to back this up?
> Since Gnat and possibly other compilers have gone many years without
> implementing this correctly,

Not sure what you mean by "implementing this correctly", we are not aware of any
bugs in this area?

> it is hard to believe that it is common.
> And it is the best kind of incompatibility, one that is detected by
> the compiler, causing the program to be rejected, with a one-line fix.

these fixes can be prohibitive in large systems of legacy code (similar to the
significant impact of new reserved words -- which is why SOME should not have
been reserved).

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

From: Dan Eilers
Sent: Friday, April 22, 2011   2:15 PM

> The problem being solved would not justify the incompatibility.

If you like, I think you can avoid the incompatibility by simply rejecting an
unneeded body for generics that have been instantiatied with incomplete private
actual parameters.

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

From: Dan Eilers
Sent: Friday, April 22, 2011   2:19 PM

> Not sure what you mean by "implementing this correctly", we are not
> aware of any bugs in this area?

see http://gcc.gnu.org/PR15593

> these fixes can be prohibitive in large systems of legacy code
> (similar to the significant impact of new reserved words -- which is
> why SOME should not have been reserved).

legacy code does not use this feature because legacy compilers did not correctly
implement it.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011   2:29 PM

> legacy code does not use this feature because legacy compilers did not
> correctly implement it.

This was an Ada 83 "feature" that Ada 95 partially changed. I suspect that most
if not all of the Ada 83-derived compilers (like Janus/Ada) have the mechanisms
needed to implement this correctly (it was required by the ACVC for Ada 83).
(I'd need to try an example to be sure - we did remove some of those mechanisms,
but I don't think this was one.)

As such, I expect that there is plenty of legacy code using the feature -- not
all "legacy" code is written for GNAT!!

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

From: Dan Eilers
Sent: Friday, April 22, 2011   2:45 PM

> This was an Ada 83 "feature" that Ada 95 partially changed. I suspect
> that most if not all of the Ada 83-derived compilers (like Janus/Ada)
> have the mechanisms needed to implement this correctly (it was
> required by the ACVC for Ada 83). (I'd need to try an example to be
> sure - we did remove some of those mechanisms, but I don't think this
> was one.)
>
> As such, I expect that there is plenty of legacy code using the
> feature -- not all "legacy" code is written for GNAT!!

I do not believe there was an Ada 83 ACVC test for this.
Ada 83 did not require instantiations before the body was available, so many Ada
83 implementations would have rejected this.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011   2:58 PM

Perhaps, although there were a number of such ".DEP" tests in the test suite.

In any event, Janus/Ada always allowed such instantiations, and I'm pretty sure
we implemented the "feature" as required (we have "optional" entry points in our
linker for this purpose).

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

From: Robert Dewar
Sent: Friday, April 22, 2011  2:31 PM

> If you like, I think you can avoid the incompatibility by simply
> rejecting an unneeded body for generics that have been instantiatied
> with incomplete private actual parameters.

Now that sounds just fine to me ...

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

From: Robert Dewar
Sent: Friday, April 22, 2011  2:33 PM

>> Not sure what you mean by "implementing this correctly", we are not
>> aware of any bugs in this area?
>
> see http://gcc.gnu.org/PR15593

This seems to have been fixed a long time ago, am I reading things incorrectly?

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

From: Dan Eilers
Sent: Friday, April 22, 2011   2:45 PM

> > see http://gcc.gnu.org/PR15593
>
> This seems to have been fixed a long time ago, am I reading things
> incorrectly?

It appears to have existed in Gnat for at least a decade, and even longer for
projects that don't update their compiler frequently, so quite unlikely to be a
commonly used feature.

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

From: Robert Dewar
Sent: Friday, April 22, 2011  2:55 PM

Fair enough, you may be right that this is rare. But in any case you suggested a
solution that does NOT have an incompatibility, which seems preferable, no?

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

From: Dan Eilers
Sent: Friday, April 22, 2011  3:02 PM

I could live with it either way.  The incompatibility does not bother me at all since it is so rare and so easily detected and fixed.
There seem to be three possible variations, all of which I can live with:
  1) reject any unneeded generic body;
  2) reject any unneeded generic body after any instantiation;
  3) reject any unneeded generic body after an instantiation with
        incomplete private actual parameters.

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

From: Dan Eilers
Sent: Friday, April 22, 2011  6:39 PM

> Solution #5 - Write-in

Instead of trying to rejigger the rules for elaboration of generics, maybe there
is a solution that avoids generics.

As I understand it, the reason that package Ada.Iterator_Interfaces is generic,
is so it can be parameterized by type Cursor. Currently, each container package
independently declares it's own Cursor type.  If instead, each Cursor type was
derived from a common Cursor type declared in Ada.Containers, and if the
Ada.Iterator_Interfaces package was made a child or subpackage of
Ada.Containers, so that it had visibility to the common Cursor type, then maybe
there would be no need for generics.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  7:01 PM

We considered something like that way back in the dark ages. But there are two
problems:

(1) The contents of a cursor is different for each container. Many of them point
    at nodes, but the vector in particular includes an array index instead.
(2) We want users to be able to write their own iterators for their own
    containers (and things that are only vaguely like a container). This would
    pretty much restrict iterators to the existing containers.

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

From: Dan Eilers
Sent: Friday, April 22, 2011  7:12 PM

> (1) The contents of a cursor is different for each container. Many of
> them point at nodes, but the vector in particular includes an array
> index instead.

Doesn't type extension solve this problem?  Or do you bump into problems of
multiple dispatch?

> (2) We want users to be able to write their own iterators for their
> own containers (and things that are only vaguely like a container).
> This would pretty much restrict iterators to the existing containers.

This problem would be solved by putting the parent Cursor type in a child
package of Ada.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  7:26 PM

> > (1) The contents of a cursor is different for each container. Many
> > of them point at nodes, but the vector in particular includes an
> > array index instead.
>
> Doesn't type extension solve this problem?  Or do you bump into
> problems of multiple dispatch?

Cursor isn't tagged, both for overhead reasons, and because an operation cannot
be primitive for two tagged types. I'm sure that could be fixed, but it seems
like a slippery slope. (That's why it's better to fix, in some sense, the
underlying problem than to keep crafting workarounds.)

> > (2) We want users to be able to write their own iterators for their
> > own containers (and things that are only vaguely like a container).
> > This would pretty much restrict iterators to the existing containers.
>
> This problem would be solved by putting the parent Cursor type in a
> child package of Ada.

Maybe, but now you've required the form of an iteratable cursor (rather than it
being anything that the programmer can imagine). Not a show-stopping problem,
but seems to argue in favor of other solutions without such restrictions.

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

From: Dan Eilers
Sent: Friday, April 22, 2011  7:47 PM

> (That's why it's better to fix, in some sense, the underlying problem
> than to keep crafting workarounds.)

Of course, that depends on what you see as the underlying problem.
It seems like a pretty fundamental problem that the only explicit commonality
between all the container packages is type Hash_Type and type Count_Type, when
there is all sorts of commonality just under the surface that begs to be made
explicit.

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

From: Randy Brukardt
Sent: Friday, April 22, 2011  8:03 PM

We've always viewed that commonality as the provence of signature generics
and/or interfaces. The main reason the containers don't have those is this
signature generic instantiation problem, and the extra layer of instantiations
needed for an organization like the ones used by the queues (as the interfaces
have to be parameterized by the element_type).

Maybe there is some other way to look at it, but it always seems to come back to
the need to parameterize on the element_type, and that is in direct conflict
with the desire for these to be easy to use and understandable if you are not a
multiple inheritance guru.

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

From: Tucker Taft
Sent: Monday, April 25, 2011  8:31 AM

> #4 is "too much concept" to solve a seemingly simple issue. If it
> could be argued that the feature is really useful in general (and
> hence be included almost for its own sake), I might switch preferences
> between #3 and #4.

I am attracted to #4 as well, but only if it is generalized to any bodyless
generic.  Essentially bodyless generics would do freezing on their expansion,
and not automatically freeze their actuals.

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

From: Steve Baird
Sent: Monday, April 25, 2011  11:09 AM

I agree that this is an appealing idea. Ed has argued that this would be too
much of an earthquake for compiler implementers. Ed is vacationing today and
tomorrow.

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

From: Tucker Taft
Sent: Monday, April 25, 2011  11:32 AM

Another way to think of this is that freezing always happens this way for the
spec of an instance, and it is the body of an instance that freezes all of the
actuals.

Ed's view on this idea of "incremental" freezing has blown warm and cold.  He
has occasionally said it was no big deal, and on other occasions said it is an
earthquake (e.g. see Oct. 21, 2008 comment by Ed in AI05-0074-3).  Perhaps the
real question is what is the earthquake's rating on the Richter scale? ;-)

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  1:58 PM

Well, first of all, I have absolutely no idea what rules you are actually
proposing. The way it is described seems like a massive incompatibility, in that
many things currently frozen would be unfrozen, requiring code generation delays
in order to deal with them. I can't believe that is what you have in mind, so
please explain whatever you are thinking of at least the level of detail in the
straw poll.

Second, any new, unvetted proposal is simply too late at this point. We need to
adopt a solution that we can trust without much additional work, as the final
letter ballot for Ada 2012 is going out tonight. There is no possibility of
having a solution vetted in that time!

One could ask, what's the rush? The "rush" is that every month of delay requires
the ARA or someone to find another $5000 to fund another month of my time. There
is no such money budgeted or available so far as I can tell, meaning if the
standard isn't done by July, it is unlikely to be finished this year.

Finally, I wanted to make some sort of intelligent comment on the implementation
effort (at least from my perspective), but I realized that I simply don't
understand what you are proposing. How specifically is the freezing for
instantiations changed, and in what cases? (Nearly every generic unit can have a
body; we handle that by having all packages having an usually empty body that is
used if no real body is provided; that also handles task activation, if
necessariy, since that is normally done by the body. So there is no such thing
as a "bodiless generic".)

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  2:11 PM

I should add that I prefer the formal incomplete proposal at this point because
it is simple to understand (both for users and implementors) and fully worked
out, and it doesn't prevent a more general solution in the future. If we rush
into a solution based on partial freezing now, and get it wrong, we're stuck
with it forever -- and we'll never be able to fix it.

Moreover, even if we add such a general solution in a future version of Ada,
formal incomplete types will continue to be useful in cases where someone wants
to ensure that a package can be used as a signature -- because adding anything
that would cause trouble will automatically be detected (and not be breaking
some client's instantiations!). So I don't see any harm in adding that feature
now to solve the immediate problem cleanly.

Tucker in particular seems to dislike formal incomplete types a lot (even I
think they originally were his idea); I don't understand why he is trying so
hard to avoid using that solution.

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

From: Tucker Taft
Sent: Monday, April 25, 2011  2:52 PM

> Well, first of all, I have absolutely no idea what rules you are
> actually proposing. The way it is described seems like a massive
> incompatibility, in that many things currently frozen would be
> unfrozen, requiring code generation delays in order to deal with them.
> I can't believe that is what you have in mind, so please explain
> whatever you are thinking of at least the level of detail in the straw poll.

What I was suggesting is that generic specs are expanded, and then freezing
happens on the expansion in the "normal" way, rather than a preemptive freezing
of the actuals. You are correct that freezing would be deferred for some items
to a later point, but it is rare that things break because freezing is delayed.
I'm not sure what you mean by "code generation delays."  We are only delaying it
until a bit later in the same compilation unit.  The end of the compilation unit
will freeze everything in any case.

> Second, any new, unvetted proposal is simply too late at this point.
> We need to adopt a solution that we can trust without much additional
> work, as the final letter ballot for Ada 2012 is going out tonight.
> There is no possibility of having a solution vetted in that time!

Agreed.

> One could ask, what's the rush? The "rush" is that every month of
> delay requires the ARA or someone to find another $5000 to fund
> another month of my time. There is no such money budgeted or available
> so far as I can tell, meaning if the standard isn't done by July, it
> is unlikely to be finished this year.

I hear you.

> Finally, I wanted to make some sort of intelligent comment on the
> implementation effort (at least from my perspective), but I realized
> that I simply don't understand what you are proposing. How
> specifically is the freezing for instantiations changed, and in what
> cases? (Nearly every generic unit can have a body; we handle that by
> having all packages having an usually empty body that is used if no
> real body is provided; that also handles task activation, if
> necessariy, since that is normally done by the body. So there is no
> such thing as a "bodiless generic".)

Any library unit generic that does not need a body is not allowed to have one,
so if the generic is a separate library unit, then bodiless <==> doesn't need a
body.  For others, I presumed we would provide some kind of pragma/aspect to
declare that there is no body, sort of the flip side of "Elaborate_Body."

For generics with bodies, there would presumably be no visible effect of the
change.  With generics without bodies, the freezing would happen on the
(conceptual) expansion of the generic spec, so the net effect is that some
actuals might not be frozen, depending on how they are used in the generic spec.

But I agree with you that this is probably too much too late.  My response was
to express support for the view that the "signature" proposal was too focused on
a special case, and a more general bodiless generic would be preferable from a
language-design point of view.  But I should have made it clear that I was
dubious we could actually pull this off in the time we have left.

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

From: Tucker Taft
Sent: Monday, April 25, 2011  2:56 PM

I agree that the formal incomplete type thing seems pretty straightforward.  I
suspect it will end up being mostly used for bodiless generics, since the formal
types are incomplete in the body as well, meaning that it will be illegal for
the types to be used as parameters to non-abstract subprogram declarations,
since the corresponding body would be illegal. So the two proposals have
something in common -- good for generic specs, not so good for bodies.

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

From: Steve Baird
Sent: Monday, April 25, 2011  3:10 PM

> But I agree with you that this is probably too much too late.  My
> response was to express support for the view that the "signature"
> proposal was too focused on a special case, and a more general
> bodiless generic would be preferable from a language-design point of
> view.  But I should have made it clear that I was dubious we could
> actually pull this off in the time we have left.

Incidentally, I agree with Tuck that his approach is cleaner.

The restrictions imposed in the signature generic proposal which Tuck mentioned
relaxing were motivated by a desire to avoid requiring implementations to
implement the "fine-granularity" freezing model for expanded instance specs. If
that were not an issue, then it would certainly be better to jettison those
restrictions as Tuck suggested.

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  3:20 PM

> I agree that the formal incomplete type thing seems pretty
> straightforward.  I suspect it will end up being mostly used for
> bodiless generics, since the formal types are incomplete in the body
> as well, meaning that it will be illegal for the types to be used as
> parameters to non-abstract subprogram declarations, since the
> corresponding body would be illegal.
> So the two proposals have something in common -- good for generic
> specs, not so good for bodies.

I don't think this is quite right; there is no requirement for the type to be
complete in a body per-se, the requirement is on calls (with the tagged
incomplete exceptions that we had in Ada 2005). So I think there will be some
uses in bodies, especially of access-to-incomplete. But it obviously would be
hard to do much that way, so I agree that the uses will be pretty similar.

Once the ballot closes tonight (Gary hasn't voted yet, so I'm waiting until he
does or the time runs out to declare a winner), I suspect I'll be going forward
with the formal incomplete solution. There for course will be a letter ballot on
all of the unfinished or substantially changed stuff, so there will be more
opportunities for discussion.

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  3:27 PM

...
> What I was suggesting is that generic specs are expanded, and then
> freezing happens on the expansion in the "normal"
> way, rather than a preemptive freezing of the actuals.
> You are correct that freezing would be deferred for some items to a
> later point, but it is rare that things break because freezing is
> delayed.  I'm not sure what you mean by "code generation delays."  We
> are only delaying it until a bit later in the same compilation unit.
> The end of the compilation unit will freeze everything in any case.

I don't think that quite works, because some formals need to freeze the
corresponding actuals. In particular, formal objects need to freeze their
expressions and types. I haven't though carefully about formal subprograms or
packages in this regard, but clearly that would need to be done.

...
> > Finally, I wanted to make some sort of intelligent comment on the
> > implementation effort (at least from my perspective), but I realized
> > that I simply don't understand what you are proposing. How
> > specifically is the freezing for instantiations changed, and in what
> > cases? (Nearly every generic unit can have a body; we handle that by
> > having all packages having an usually empty body that is used if no
> > real body is provided; that also handles task activation, if
> > necessariy, since that is normally done by the body. So there is no
> > such thing as a "bodiless generic".)
>
> Any library unit generic that does not need a body is not allowed to
> have one, so if the generic is a separate library unit, then bodiless
> <==> doesn't need a body.  For others, I presumed we would provide
> some kind of pragma/aspect to declare that there is no body, sort of
> the flip side of "Elaborate_Body."

There is no such thing as a package without a body. All packages have a body (it
might be implicit); it's the place where task activation happens. See 7.2(5):
"For any package_declaration without an explicit completion, there is an
implicit package_body containing a single null_statement."

So the wording would be tricky, although your intent seems clear enough.

> For generics with bodies, there would presumably be no visible effect
> of the change.

We hope, not certain!

> With generics without bodies,
> the freezing would happen on the (conceptual) expansion of the generic
> spec, so the net effect is that some actuals might not be frozen,
> depending on how they are used in the generic spec.

OK.

> But I agree with you that this is probably too much too late.
>  My response was to express support for the view that the
> "signature" proposal was too focused on a special case, and a
> more general bodiless generic would be preferable from a
> language-design point of view.  But I should have made it
> clear that I was dubious we could actually pull this off in
> the time we have left.

Fair enough.

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

From: Tucker Taft
Sent: Monday, April 25, 2011  3:30 PM

> I don't think this is quite right; there is no requirement for the
> type to be complete in a body per-se, the requirement is on calls
> (with the tagged incomplete exceptions that we had in Ada 2005).

Good point, it is OK to have a tagged incomplete type as a parameter of a
subprogram body.  Untagged incomplete aren't allowed on a body, nor are tagged
incomplete types allowed as return types. Of course access-to-incomplete
parameters and access-to-incomplete results are allowed, but that is pretty
limiting.

> ... So I think there will be
> some uses in bodies, especially of access-to-incomplete. But it
> obviously would be hard to do much that way, so I agree that the uses
> will be pretty similar.

Agreed.

> Once the ballot closes tonight (Gary hasn't voted yet, so I'm waiting
> until he does or the time runs out to declare a winner), I suspect
> I'll be going forward with the formal incomplete solution. There for
> course will be a letter ballot on all of the unfinished or
> substantially changed stuff, so there will be more opportunities for
> discussion.

OK!

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

From: Dan Eilers
Sent: Monday, April 25, 2011  3:57 PM

...
> Moreover, even if we add such a general solution in a future version
> of Ada, formal incomplete types will continue to be useful in cases
> where someone wants to ensure that a package can be used as a
> signature -- because adding anything that would cause trouble will
> automatically be detected (and not be breaking some client's
> instantiations!). So I don't see any harm in adding that feature now to solve the immediate problem cleanly.

I'm not sure I agree that the formal incomplete proposal won't be regretted
later if/when a more general solution is found.  My understanding is that there
are still cases where a solution to AI-74 ("end private") would be useful, and
if/when that happens, most if not all of the work done to implement AI-212 would
be wasted, including the work users will expend trying to identify and mark all
their generic formal private types that should allow incomplete actuals.

The signature package proposal can be seen as eliminating a language flaw
(useless ambiguity regarding the existence of bodies), which would be welcome
even if AI-74 is solved, rather than adding new language machinery for a new
kind of formal generic parameter, whould would be effectively obsoleted by a
solution to AI-74.

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  4:19 PM

...
> I'm not sure I agree that the formal incomplete proposal won't be
> regretted later if/when a more general solution is found.  My
> understanding is that there are still cases where a solution to AI-74
> ("end private") would be useful, and if/when that happens, most if not
> all of the work done to implement AI-212 would be wasted, including
> the work users will expend trying to identify and mark all their
> generic formal private types that should allow incomplete actuals.

I strongly disagree. You appear to be saying that the effort to declare your
intended use of a formal type is "wasted". That does not seem to be a very
Ada-like perspective to me.

As I noted previously, the proposal that Tucker is suggesting applies to all
generics, and the freezing depends only on the contents. I view this as
dangerous for maintenance, as a clueless maintainer (me, perhaps :-) could add
something to specification that means it is no longer able to be instantiated
with a private type. This would be a minor problem within your own projects
(you'll find out soon), but it could be a disaster in a widely-used library
(language-defined, implementation-defined, 3rd-party-defined (like Claw), or
company-defined). In that case, it is not unusual that only a few problematic
uses exist, in rarely worked on systems, but the cost to restructure to avoid
the problem is huge.

The use of a proper declaration (a formal incomplete is one way to do that) to
mark that a formal is intended to be used with unfrozen types will remain
valuable no matter what other solutions end up being provided.

(Note that a solution that does not allow generic bodies is not going to help
use the containers in such cases, so it also remains an incomplete solution. I
very much doubt that a complete solution to this problem is possible.)

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

From: Dan Eilers
Sent: Monday, April 25, 2011  4:41 PM

> (Note that a solution that does not allow generic bodies is not going
> to help use the containers in such cases, so it also remains an
> incomplete solution. I very much doubt that a complete solution to
> this problem is
> possible.)

Is the incomplete-private proposal better than the signature-generic proposal in that it would allow container packages (with bodies) to be instantiated with incomplete private types?  If so, that would be a nice advantage, but I thought the proposal was a
imed primarily at the iterators package.


> As I noted previously, the proposal that Tucker is suggesting applies
> to all generics, and the freezing depends only on the contents. I view
> this as dangerous for maintenance, as a clueless maintainer (me,
> perhaps :-)

I think this depends on the details of the signature-package proposal.
I agree that if the freezing depends on the contents of the generic spec, then there might be somewhat of a maintenance hazard.  But if the generic spec is marked as freezable, then the hazard goes away, with less wasted effort than marking each formal pri
vate type.

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

From: Randy Brukardt
Sent: Monday, April 25, 2011  4:42 PM

For some reason this recent Dilbert reminded me of the aftermath of some ARG
meetings. Enjoy!

http://dilbert.com/strips/2011-04-23/

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

From: Tucker Taft
Sent: Monday, May  2, 2011  9:44 PM

[The appropriate part of a longer message - Editor]

AI05-0212-1/10  Accessors and Iterators for Ada.Containers
    [The only change is to use Has_Element rather than No_Element in the iterator instances.]
    Approve ___X___ Disapprove ______ Abstain _______
   Comments:
     This aspect_specification does not match the recommended formatting:
      type Reference_Type (Element : not null access Element_Type) is private
        with
           Implicit_Dereference => Element
     It should be simply:
      type Reference_Type (Element : not null access Element_Type) is private
        with Implicit_Dereference => Element
     It also means one less line in the RM for each such declaration.

     It is a bit unclear whether the following paragraph (and similar ones) are
     intended to be in the RM, or if it is a "meta" comment in the AI:
       This function (combined with the Constant_Indexing and Implicit_Dereference
       aspects) provides a convenient way to get read access to the individual
       elements of a container starting with a cursor.
     If it is to be in the RM, then "get read access" would be better expressed
     as "gain read access" I believe.  Also, it is tedious to see this same
     paragraph over and over.  Can't we just have a single user NOTE somewhere
     explaining the purpose of these operations?

     Can we simplify this repeated wording: "Iterate returns an object that can
     be used in a loop_statement to loop with a loop parameter designating each
     node in Container"?  How about just saying "Iterate returns a container
     element iterator for Container" or something like that?

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

From: Randy Brukardt
Sent: Monday, May  2, 2011  10:32 PM

[The appropriate part of a longer message - Editor]

> AI05-0212-1/10  Accessors and Iterators for Ada.Containers
>     [The only change is to use Has_Element rather than No_Element in
> the iterator instances.]
>     Approve ___X___ Disapprove ______ Abstain _______
>    Comments:
...
>      It is a bit unclear whether the following paragraph (and similar ones) are
>      intended to be in the RM, or if it is a "meta" comment in the AI:
>        This function (combined with the Constant_Indexing and Implicit_Dereference
>        aspects) provides a convenient way to get read access to the individual
>        elements of a container starting with a cursor.
>      If it is to be in the RM, then "get read access" would be better expressed
>      as "gain read access" I believe.  Also, it is tedious to see this same
>      paragraph over and over.  Can't we just have a single user NOTE somewhere
>      explaining the purpose of these operations?

The intent is that the container definitions are expected to be mostly referred
to in a reference fashion. Thus we have generally put each note (AARM and User)
in each clause (since we don't expect people to read the Vectors in order to
understand the Lists).

And it was intended to put this text in the RM, because otherwise the purpose of
these functions is very mysterious. And remember that there are only two of
these per container; the repetition is much more obvious in this AI where they
are all lumped together.

It might make sense to try to combine the note for both routines (so it doesn't
have to be repeated on the second one), but an obvious way to do that doesn't
jump out at me (since the indexing aspects differ for the two routines).

>      Can we simplify this repeated wording: "Iterate returns an object that can
>      be used in a loop_statement to loop with a loop parameter designating each
>      node in Container"?  How about just saying "Iterate returns a container element
>      iterator for Container" or something like that?

This wording was designed to be as close as possible to the existing Iterator,
thus we get the part about "designating each node in Container". The rest of it
is just to make that part make sense. I definitely don't want to say *less*
about that here, especially as this is the only text that specifies what cursors
are returned, and in what order. That had better be specified somewhere! If you
have a better suggestion that includes that text (which I don't want to have to
reorganize or reword, because that is very likely to be full of errors), I'd be
glad to hear it.

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

From: Tucker Taft
Sent: Tuesday, May  3, 2011  7:44 AM

[The appropriate part of a longer message - Editor]

>>       Can we simplify this repeated wording: "Iterate returns an object that can
>>       be used in a loop_statement to loop with a loop parameter designating each
>>       node in Container"?  How about just saying "Iterate returns a container element
>>       iterator for Container" or something like that?
>
> This wording was designed to be as close as possible to the existing
> Iterator, thus we get the part about "designating each node in Container".
> The rest of it is just to make that part make sense. I definitely
> don't want to say *less* about that here, especially as this is the
> only text that specifies what cursors are returned, and in what order.
> That had better be specified somewhere! If you have a better
> suggestion that includes that text (which I don't want to have to
> reorganize or reword, because that is very likely to be full of errors), I'd be glad
> to hear it.

I was suggesting using the term "container element iterator" which is defined in
the Iterator AI.  I see no reason to repeat the definition of an container
element iterator, though of course a "see 5.5.1" might be helpful.

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

From: Randy Brukardt
Sent: Tuesday, May  3, 2011  5:33 PM

[The appropriate part of a longer message - Editor]

> >> ... AI05-0212-1/10  Accessors and Iterators for Ada.Containers
...
> >>       Can we simplify this repeated wording: "Iterate returns an object
> >>       that can be used in a loop_statement to loop with a loop parameter
> >>       designating each node in Container"?  How about just saying "Iterate
> >>       returns a container element
> >>       iterator for Container" or something like that?
> >
> > This wording was designed to be as close as possible to the existing
> > Iterator, thus we get the part about "designating each node in Container".
> > The rest of it is just to make that part make sense. I definitely
> > don't want to say *less* about that here, especially as this is the
> > only text that specifies what cursors are returned, and in what order.
> > That had better be specified somewhere! If you have a better
> > suggestion that includes that text (which I don't want to have to
> > reorganize or reword, because that is very likely to be full of
> > errors), I'd be glad to hear it.
>
> I was suggesting using the term "container element iterator"
> which is defined in the Iterator AI.  I see no reason to repeat the
> definition of an container element iterator, though of course a "see
> 5.5.1" might be helpful.

Well, we have to define which elements are returned and in what order. 5.5.1 and
5.5.2 provides no guidance there (and it can't, since these are general
concepts). Remember that the actual type of the iterator is not defined here and
thus the routines used to implement it aren't known either. (There is nothing
requiring that the iterator Next does the same thing as the container Next, and
that's rather important.)

A second point is that this is a function returning an "iterator object". That
object can be used in the first form of iterator (I'm reading the definitions in
5.5.1 and 5.5.2.) Some of these functions are also used to provide the object
for the default "container element iterator" (for the third form), but that is a
secondary purpose. (And not all of them provide "container element iterator"s at
all.)

Remember that the first form allows one to iterate through the cursors of a
container, the third form allows one to iterate through the elements of a
container. You can get elements given a cursor, but you can't get cursors given
elements, so the first form is more general. And this text is talking about the
first form (if you are using the third form, you would not call this function
explicitly).

So I think your suggestion is just plain wrong. I can imagine simplifying this
text somehow, but it doesn't have anything to do with a "container element
iterator".

The text currently is:

Iterate returns an object that can be used in a loop_statement to loop with a
loop parameter designating each node in Container, starting with the first node
and moving the cursor as per the Next function if the reserved word *reverse* is
not used in the iterator_specification, and starting with the last node and
moving the cursor as per the Previous function otherwise.

We could try to eliminate some small parts of this using more terminology from
139-2, but we need most of it. In particular, we could say that the function
returns an "iterator object (see 5.5.1)", when used in a "generalized iterator
(see 5.5.2)", and describe the semantics for "forward iterators" and "reverse
iterators". That would look something like:

Iterate returns an iterator object (see 5.5.1) that can be used in a generalized
iterator (see 5.5.2) causing the loop parameter to designate each node in
Container, starting with the first node and moving the cursor as per the Next
function if used as a forward iterator, and starting with the last node and
moving the cursor as per the Previous function if used as a reverse iterator.

I'm not sure this is a huge improvement, as we still have to mention the
loop_statement in the tampering check text which follows this. But it does use
the defined terminology. (I didn't use that originally because I thought you
were going to get rid of a lot of it, as much of it never seems to be used.
Maybe you're just trying to justify that work. ;-)

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

From: Tucker Taft
Sent: Tuesday, May  3, 2011  6:59 PM

> Iterate returns an iterator object (see 5.5.1) that can be used in a
> generalized iterator (see 5.5.2) causing the loop parameter to
> designate each node in Container, starting with the first node and
> moving the cursor as per the Next function if used as a forward
> iterator, and starting with the last node and moving the cursor as per
> the Previous function if used as a reverse iterator.

I don't think we need to say "that can be used in a generalized iterator causing
the loop parameter" since that is all implicit in the definition of iterator
object.  How about something like this:

    Iterate returns a reversible iterator object (see 5.5.1) representing the
    sequence of all nodes of the Container, with First, Next, Last, and Previous
    corresponding to the same-named operations of this package.

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

From: Randy Brukardt
Sent: Wednesday, May  4, 2011  2:47 PM

That would work for the most of the basic iterators (modulo dealing with the
iterators that aren't reversible), but it wouldn't work for the new ones that
include a starting position. We don't have any existing functions that would
return that would return that start position, so talking about First and Last
would be very confusing. It also wouldn't work for the full tree ones, which
just say "depth-first order"; there are no existing functions that will directly
produce that order (you need a combination and a stack of some sort [or
recursion, which can't be used in the Iterator object for obvious reasons]).

I was trying to write wording that would change the existing iterator text as
little as possible, rather than discarding it completely and starting over (with
the certain set of bugs that will be introduced). Maybe that wasn't a worthy
goal, but I don't see how to fit all of the iterators into the form you are
proposing. (The AI has six different templates for Iterator text, I need to be
able to change them all.)

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

From: Tucker Taft
Sent: Wednesday, May  4, 2011  3:01 PM

It just feels that we should be able to say what an iterator represents without
a whole paragraph, especially if they are going to be used regularly.  An
iterator represents a sequence of elements.  If "reverse" is present, then the
sequence is processed from last to first, otherwise it is processed from first
to last, but it is still just a single sequence. I would like us to be able to
describe that sequence (e.g. is a depth-first walk of the nodes) and not say a
whole lot more.  We shouldn't have to mention First, Next, Last, and Previous at
all ideally.  We should just define the sequence, and have everything else be
common semantics, which we define in just one place.

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

From: Randy Brukardt
Sent: Thursday, May  5, 2011  2:07 PM

> It just feels that we should be able to say what an iterator
> represents without a whole paragraph, especially if they are going to
> be used regularly.  An iterator represents a sequence of elements.  If
> "reverse"
> is present, then the sequence is processed from last to first,
> otherwise it is processed from first to last, but it is still just a
> single sequence.

You are overspecifying what an iterator itself does. All it says is that a
series of cursors will be presented in some order with some starting cursor.
That order is defined by the specific iterator type, and all I'm trying to do is
ensure that that order is well-defined.

In particular, there is absolutely no requirement that an iterator "processes
from first to last". It does whatever it is defined to do, limited only by the
cleverness of the implementers! There is no concept of "first to last" for a
depth first order, and it would be fine to have an iterator that processed in a
random order.

> I would like us to be able to describe that sequence (e.g. is a
> depth-first walk of the nodes) and not say a whole lot more.

That's fine and that's what I'm proposing.

> We shouldn't have to mention First, Next, Last, and Previous at all
> ideally.

And we wouldn't for the trees, because the order is defined somewhere else.
Your problem here is that you are looking at the wording for the Vector and the
List, which is the most complex of all, and thinking that is the way they all
will look.

Neither Vectors nor Lists have much defined about ordering; pretty much
everything is written in terms of using Next to find the next element.

Clearly, we could rewrite all of this text to talk about starting at the first
node and proceeding by successors -- but is that really helping anything?? And
if we change this, we also have to change the existing iterator description (it
needs to be consistent - it should be crystal clear that you can convert one to
the other).

This seems to me to be an exercise in churn; nothing will be shorter or more
understandable, it will just be different.

> We should just define the sequence,
> and have everything else be common semantics, which we define in just
> one place.

Well, that doesn't make any sense, because the sequence itself would have to
defined individually for each container, that hardly is "one place". And if we
did define the sequence separately from the iterators, that is only going to
save about one sentence total in the RM. Is that really worth it??

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

From: Randy Brukardt
Sent: Thursday, July 28, 2011  1:43 AM

I was explaining how empty elements work to Christoph Grein and noticed that the
bounded error for the reading of empty elements was not updated to include the
creation of a reference to an empty element.

Since Reference is just a better version of Update_Element, and
Constant_Reference is just a better version of Query_Element, we ought to be
using the same rules for both (and Update_Element and Query_Element are in this
bounded error).

This seems absolutely necessary, as in the indefinite container case, the
element has no tag/bounds/discriminants. How one could create a reference to
something with no bounds or tag or discriminants escapes me. And assigning
something into a reference to such an object and magically have an object with
the right bounds/tag/discriminants appear doesn't seem any more possible.

It's annoying that something like:

   Cont(1) := 10;

is a bounded error if the element (1) is an empty element, but that is already
true for the Ada 2005 containers (using Update_Element) and it doesn't seem
possible to avoid it without putting major constraints on the implementation (or
making the indefinite version much more different).

Of course, it is easy to avoid creating an empty element (don't use
Insert_Space), so this is not a major hardship.

So, Reference and Constant_Reference should be added to the list of routines in
A.18.2(240/2).

P.S. Reading an empty element is a bounded error so that it isn't required to
have an "Is_Empty" bit with every element of a definite type. That seemed like
overkill, especially for small elements like characters. If no exception is
raised, the element must have a normal (but possibly invalid) value.

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

From: Randy Brukardt
Sent: Thursday, October 13, 2011  12:20 AM

Brad had in his review:

> 14) A.18.2(230.2/3, 230.4/3) "will generate a loop parameter"
> How can Iterate "generate" a loop parameter.
> A loop parameter is a declaration. To generate one, it requires
> someone to type the declaration in a text editor. I think "generate"
> is the wrong choice of word.

[He then goes on to repeat this comment a dozen more times, just in case I
missed it the first time. :-)]

This is really talking about the different values that the loop parameter will
take on; the iterator "generates" those values. That's still the best word I can
think of to describe what's going on.

I do agree that "loop parameter" by itself is confusing, it really talking about
the values that the parameter will have.

So let's start with the original wording:

Iterate returns a reversible iterator object that will generate a loop parameter
designating each node in Container, ...

[the "..." here describes the order the values are provided, and it is different
for each iterator function; I want to concentrate on the common part so I don't
just move the bump around.]

The easiest fix is just to insert "value":

Iterate returns a reversible iterator object that will generate a loop parameter
{value} designating each node in Container, ...

or reordering:

Iterate returns a reversible iterator object that will generate a {value of the}
loop parameter designating each node in Container, ...

This is still a bit dicey, in that when the default iterator is used in the "of"
form, the loop parameter is the element, not the cursor designating, but given
the equivalence of the forms it should be OK.

So, is this enough or is there some other change that would fix this problem??

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

From: Tucker Taft
Sent: Thursday, October 13, 2011  12:31 AM

I agree with "... will generate a value of the loop parameter"
or perhaps "... will generate a value for the loop parameter ..."

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

From: Brad Moore
Sent: Thursday, October 13, 2011  8:05 AM

I am also happy with either of these though I think "for" is marginally better
than "of".

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

Questions? Ask the ACAA Technical Agent