CVS difference for ai05s/ai05-0139-1.txt

Differences between 1.4 and version 1.5
Log of other versions for file ai05s/ai05-0139-1.txt

--- ai05s/ai05-0139-1.txt	2009/06/02 06:22:37	1.4
+++ ai05s/ai05-0139-1.txt	2009/06/09 01:53:16	1.5
@@ -1,4 +1,4 @@
-!standard 5.5                                       09-02-13  AI05-0139-1/01
+!standard 5.5                                       09-06-08  AI05-0139-1/02
 !class Amendment 09-02-13
 !status work item 09-02-13
 !status received 09-01-19
@@ -24,7 +24,6 @@
 
 Define a magic generic unit that defines a pair of interfaces:
 
-
    generic
        type Cursor is private;
        No_Element : in Cursor;
@@ -34,7 +33,7 @@
        function First (Object : Basic_Iterator) return Cursor;
        function Next (Object : Basic_Iterator; Position : Cursor) return Cursor;
 
-       type Reversible_Iterator is new Basic_Iterator with null record;
+       type Reversible_Iterator is limited interface and Basic_Iterator;
        function Last (Object : Reversible_Iterator) return Cursor;
        function Previous (Object : Reversible_Iterator; Position : Cursor) return Cursor;
 
@@ -49,31 +48,151 @@
 
    defining_identifier in [reverse] iterator_expression
 
-The rules for this are:
-   * The iterator_expression is expected to be of an (instance of
-     Iterator_Interfaces).Basic_Iterator'Class [the parens here mean
-     that we're talking about (any) type declared in an instance of
-     Iterator_Interfaces];
-   * The type of the defining_identifier is the appropriate Cursor type
-     for the instance of Iterator_Interfaces;
-   * the keyword "reverse" can only appear if the type is of an (instance
-     of Iterator_Interfaces).Reversible_Iterator'Class;
-   * The iterator_expression is a build-in-place context;
-   * the master of the iterator_expression is the (entire) loop; the
-     iterator_expression continues to exist until the loop is completed
-     (normally or abnormally).
-
-The loop executes by calling First (or Last if the keyword "reverse" is
-present), followed by calling Next (or Previous if the keyword "reverse" is
-present) for each following iteration until the function called returns
-No_Element. The loop body is executed once for each cursor value (other than
-No_Element) obtained from the functions with the loop parameter set to that
-cursor value.
+See the wording below for the detailed rules.
 
 !wording
+
+Replace 5.5(3) by:
+   iteration_scheme := while condition
+      | for loop_parameter_specification
+      | for user_loop_parameter_specification
+
+[Author's note: We need a different kind of loop parameter syntax so that
+5.5(6) doesn't get triggered for user-defined iterators, as that would
+give it the wrong sort of type; this also reduces forward references just
+to syntax, which is generally accepted in the Standard.]
+
+Modify 5.5(9):
+For execution of a loop_statement with a for iteration_scheme {with a
+loop_parameter_specification}, the ...
+
+[Author's note: More detail to eliminate confusion between the two kinds of
+for loop.]
+
+
+5.5.1 The generic package Iterator_Interfaces
+
+The generic package Iterator_Interfaces provide a template for the definition
+of user-defined iterators.
+
+   generic
+       type Cursor is private;
+       No_Element : in Cursor;
+   package Ada.Iterator_Interfaces is
+
+       type Basic_Iterator is limited interface;
+       function First (Object : Basic_Iterator) return Cursor;
+       function Next (Object : Basic_Iterator; Position : Cursor) return Cursor;
+
+       type Reversible_Iterator is limited interface and Basic_Iterator;
+       function Last (Object : Reversible_Iterator) return Cursor;
+       function Previous (Object : Reversible_Iterator; Position : Cursor) return Cursor;
+
+   end Ada.Iterator_Interfaces;
+
+The interface Basic_Iterator defines a user-defined iterator for the forward direction;
+the interface Reversible_Iterator defines a user-defined iterator for both the forward and
+reverse direction.
+
+The function First is expected to deliver the first cursor value for the iterator iterating
+in the forward direction, or return No_Element if no cursor value is available. The function
+Next is expected to deliver the next cursor value for the iterator iterating
+in the forward direction given the previous cursor value returned from a call to First or
+Next, or return No_Element if no additional cursor values are available.
+
+The function Last is expected to deliver the last cursor value for the iterator iterating
+in the reverse direction, or return No_Element if no cursor value is available. The function
+Previous is expected to deliver the next cursor value for the iterator iterating
+in the reverse direction given the previous cursor value returned from a call to Last or
+Previous, or return No_Element if no additional cursor values are available.
+
+5.5.2 User-defined iteration
+
+[Author's note: This is a separate clause, so that we don't need a forward reference to
+the generic package.]
+
+Syntax
+
+   user_loop_parameter_specification ::= defining_identifier in [reverse] iterator_expression
+
+Name Resolution Rules
+
+The iterator_expression of a user_loop_parameter_specification is expected to be of any
+tagged type.
+   
+Legality Rules
+
+The iterator_expression shall be of a type covered by exactly one type Basic_Iterator'Class
+of an instance of Iterator_Interfaces.
+
+AARM Reason: It would be possible for a single type to inherit from multiple instances
+of Iterator_Interfaces. However, since the type of the loop parameter is determined by the
+instance of the type Basic_Iterator'Class, we can have only one such interface in order for
+the loop parameter to have an unambiguous type. 
 
-** TBD **
+If the reserved word *reverse* is present, the iterator_expression shall be of a type
+covered by type Reversible_Iterator'Class of an instance of Iterator_Interfaces.
 
+Static Semantics
+
+A user_loop_parameter_specification declares a loop parameter, which is an object whose
+subtype is that of the actual type given for the instance of Iterator_Interfaces that
+contains the Basic_Iterator interface from which the type of the iterator_expression
+is descended.
+
+[Author's note: Wording is as similar as possible to 5.5(6).]
+
+Dynamic Semantics
+
+For the execution of a loop_statement with a for iteration_scheme with a
+user_loop_parameter_specification, the iterator_expression is first evaluated; the
+result is treated as an implicit by-reference formal parameter *I* of the
+loop_statement. 
+
+[Author's note: I don't like this wording much, but it has the correct semantics.
+The intent is that this evaluation work just like the evaluation of a by-reference
+parameter - see below.]
+
+AARM Ramification: If the iterator_expression is a function call, a temporary
+object will be created here. A statement is a master (see 7.6.1), so the master of
+this temporary object (if any) is the loop statement. That means that the temporary
+object is finalized when the loop is left (including by transfers of control), and
+designers of user-defined iterators can depend on this behavior.
+
+The sequence_of_statements of statements is executed once for each value returned
+from the primitive operations of the type of the iterator_expression (or until the
+loop is left as the consequence of a transfer of control). Prior to each such iteration,
+a value is assigned to the loop parameter as follows:
+   * For the first iteration of a loop that does not include the reserved word *reverse*,
+     the loop parameter is initialized from the result of a call of *I*.First;
+   * For following iterations of a loop that does not include the reserved word *reverse*,
+     the loop parameter is initialized from the result of a call of *I*.Next passed the
+     current value of the loop parameter;
+   * For the first iteration of a loop that includes the reserved word *reverse*,
+     the loop parameter is initialized from the result of a call of *I*.Last;
+   * For following iterations of a loop that includes the reserved word *reverse*,
+     the loop parameter is initialized from the result of a call of *I*.Previous passed the
+     current value of the loop parameter.
+If any of these function calls return the value No_Element (as specified in the appropriate
+instance of Iterator_Interfaces), the loop is completed and left without executing the
+sequence_of_statements. The loop_statement propagates any exception propagated by these
+function calls.
+
+
+[Author's note: I did not provide any special case if the inherited operations are not
+implemented as suggested in 5.5.1. That means that an implementation must actually
+call the routines as described (in case they do something weird); only as-if optimizations
+are allowed. Since the functions can only return a cursor (including No_Element) or
+raise an exception, there is no need to have a special case for misbehaving functions.]
+
+
+Add after 7.5(2.7/2):
+
+* the iterator_expression of a user_loop_parameter_specification of a loop_statement (see 5.5.2);
+
+
+** Containers updates TBD ** (see !examples)
+
 !discussion
 
 This is based on the earlier proposal and discussion recorded in AC-0112.TXT.
@@ -107,36 +226,58 @@
 That will detect errors earlier; it generally is better to detect errors at
 compile-time if possible.
 
-Issues:
 
-This proposal requires some solution to the instantiation for private types
-problem (see the many alternatives for AI05-0074) in order to be useful in the
-Ada.Containers packages. As this is a "magic" generic (really to provide a
-signature), we could relax the rules for it (only), but that is pretty
-distasteful.
+It might appear that this proposal would require some solution to the
+instantiation for private types problem, but as the examples below show, this
+is not true.
+
+
+Note that the actual iterator type can be either limited or non-limited. The
+value of a limited iterator object is that an iterator implementation can
+assume (presuming that it only exports functions and not types) that the
+iterator object is created and destroyed with the loop. This allows safe
+cleanup operations when the loop is exited (as in the examples below).
+If that capability is not needed, an iterator implementation allow reuse of
+iterator objects (especially if no temporary storage is needed).
+
+Note that if temporary storage or loop exit actions are needed, the iterator
+object *must be* separate from the container object that it is iterating
+on. Otherwise nested loops on the same container would not work.
+   for I in My_Container.Iterator loop
+      for J in My_Container.Iterator loop
+          ...
+      end loop;
+   end loop;
+The I and J loops need separate temporary storage, which must be provided by
+the iterator object (the loop can only provide the loop parameter cursor object).
+
+
+Issues:
 
 This proposal requires some solution to the modify-in-place problem for the
-containers packages (see earlier proposals). Without that, modifying an element
-in an iterator would require writing an extra subprogram, meaning the new syntax
-would not have gained anything.
-
-The rule about an iterator_expression being a build-in-place context is intended
-to allow iterators to get control on premature loop exit. If we didn't have
-that, it would not be possible to prevent reuse of iterator objects and thus
-the finalization of the objects would not necessarily occur when the loop
-is exited. This is somewhat of a hack - there is no intrinsic reason why an
-iterator object should not be allowed to be reused. Note, however, that reusable
-iterator types can be defined: they just have to be non-limited (and presumably
-not controlled). So perhaps we can justify this limitation in the service of
-additional control.
+containers packages (see the family of AI05-0142 proposals). Without that,
+modifying an element in an iterator would require writing an extra subprogram,
+meaning the new syntax would not have gained anything.
 
 The use of a controlled type for an iterator in this proposal would require
 bounded containers to be preelaborable units, rather than pure units. We add a
 prohibition on the actual container from being controlled, so that finalization
 adverse users could still use the bounded containers (but obviously not the
-iterators).
+iterators). This seems OK, given that the current accessor proposal (AI05-0142-4)
+has similar requirements.
 
+It would be nice for an iterator implementation to be able to prevent the
+creation of iterator objects not associated with a loop. For instance, given
+the implementation of the example below:
+    My_Iter : Some_Instance.Basic_Iterator'Class := My_List.Iterator;
+would have the effect setting tampering on My_List and keeping it set until
+until the object is destroyed (potentially a long time in the future). But this
+is not the natural thing to do -- it requires a lot more typing than the intended
+usage -- and no major definitional problems are encountered in this case. We
+would need a lot more mechanism to prevent the creation of objects outside of
+the loop context, so we do not try to prevent this misuse.
 
+
 Alternatives considered:
 
 One option considered was including the name of the cursor type somewhere in the
@@ -183,18 +324,61 @@
 This feature could easily be used in the existing Ada.Containers packages. We
 give a suggested implementation for Ada.Containers.Doubly_Linked_Lists; the
 other containers could be similar.
+
+The start of the visible part of Ada.Containers.Doubly_Linked_Lists would be
+modified as follows:
 
-Somewhere in the visible part of Ada.Containers.Doubly_Linked_Lists we would add
-an instantiation of Iterator_Interfaces:
+   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);
+
+      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;
+
+      package Iterators is new
+          Ada.Iterator_Interfaces (Cursors, No_Element);
+
+      type List is new Iterators with private;
+      pragma Preelaborable_Initialization(List);
+
+      Empty_List : constant List;
+
+      ...
+
+Note that the changes here are the addition of the nested package Cursors,
+the addition of the instantiation, and the subtype and renames to eliminate the
+effect of the nested package. The majority of the package is unchanged.
 
-   package List_Iterators is Ada.Iterator_Interfaces (Cursor, No_Element);
+After the existing procedure Reverse_Iterate, we would add a new function:
 
-And a function Iterate:
    function Iterate (Container : in List) return List_Iterators.Reversible_Iterator'Class;
+
+This would be described as
 
-In the private part of Ada.Containers.Doubly_Linked_Lists, we'd define a
-controlled type:
+      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 user_loop_parameter_statement, and starting
+      with the last node and moving the cursor as per the Previous function otherwise.
+      Program_Error is propagated if any operation (in particular, the sequence_of_statements
+      of the loop_statement whose iterator_expression denotes this object) tampers with
+      the cursors of Container while the returned object exists.
 
+This could be implemented by defining a controlled type in the private part of
+Ada.Containers.Doubly_Linked_Lists:
+
    type Our_List_Iterator is new Ada.Controlled.Limited_Controlled and
                                    List_Iterators.Reversible_Iterator with record
          Our_List : access List;
@@ -205,7 +389,7 @@
    function Previous (Object : Our_List_Iterator; Position : Cursor) return Cursor;
    procedure Finalize (Object : in out Our_List_Iterator);
 
-The implementation would be something like:
+The implementation of these operations would be something like:
    function Iterate (Container : in List) return List_Iterators.Reversible_Iterator'Class is
    begin
       return Iter:Our_List_Iterator do
@@ -228,6 +412,7 @@
    end Next;
 
    -- Similar implementations for Last and Previous.
+
    procedure Finalize (Object : in out Our_List_Iterator) is
    begin
        -- Clear the tampering context for Object.Our_List.
@@ -235,12 +420,17 @@
 
 Note that we didn't add these interfaces to the actual container types. That was
 because we wanted these iterators to be a tampering context (thus ensuring that
-they terminate and do not lead to erroneous execution). This is important from
-an analysis perspective: proving that a loop terminates is equivalent to proving
-that it is equivalent to a for loop. For this reason, we don't want for loops
-that don't terminate (at least logically; if the container is very large, the
-loop might not terminate for a long time).
+they terminate and do not lead to erroneous execution). Users would be very
+surprised if a "safe" construct like a for loop caused erroneous execution
+(which will happen if the node designated by the loop parameter is deleted).
+
+The function Iterate would normally be used directly in a loop:
+
+   for C in My_List.Iterate loop
+      ... Element (C) ...
+   end loop;
 
+
 We could also define a partial list iterator:
 
    function Partial_Iterate (Container : in List;
@@ -258,6 +448,34 @@
    for C in Partial_Iterate (My_List, Start, Finish) loop
       ... Element (C) ...
    end loop;
+
+Some reviewers have said that they would prefer the iterator to work
+directly on the container object. This would only eliminate a single
+selected name, which does not seem worth the problems that would be
+introduced. The example above means that an iterator is written:
+
+   for C in My_List.Iterate loop
+
+Only the truly lazy would find a significant difference from:
+
+   for C in My_List loop
+
+Moreover, we are planning (as of this writing) to use a similar
+mechanism to provide safe accessors. That mechanism also requires
+writing an extra selector; it would seem bizarre to work hard to eliminate
+that here, but still handle use it for accessors.
+
+Finally, a direct syntax would not allow nested loops (as different
+termination code is needed for each loop) unless significant additional
+magic is defined. Essentially, something like function Iterate would
+have to be defined internally to the interface to provide the needed
+temporary space/termination object. This would require far more
+mechanism than the current proposal.
+
+About the only thing going for the direct syntax is that it would be a
+bit easier to understand. However, usage of the current proposal is so
+easy that once a programmer sees an example, they will immediately
+understand how it works. Understanding the details would rarely be needed.
 
 
 !ACATS test

Questions? Ask the ACAA Technical Agent