CVS difference for ais/ai-30302.txt

Differences between 1.10 and version 1.11
Log of other versions for file ais/ai-30302.txt

--- ais/ai-30302.txt	2004/10/05 22:49:25	1.10
+++ ais/ai-30302.txt	2004/11/02 01:50:35	1.11
@@ -21117,6 +21117,13 @@
 
 ****************************************************************
 
+From: Pascal Leroy
+Sent: Wednesday, October 6, 2004 1:55 AM
+
+I agree that Reserve_Capacity is better than Ensure_Capacity.
+
+****************************************************************
+
 From: Matthew Heaney
 Sent: Monday, October 4, 2004  7:03 PM
 
@@ -21303,6 +21310,122 @@
 
 ****************************************************************
 
+From: Pascal Leroy
+Sent: Wednesday, October 6, 2004  1:55 AM
+
+This was not the "main motivation", although this was certainly one aspect
+discussed when this decision was made in Palma.  The motivation was that
+tagged types are more flexible in many respects (in particular, guess
+what, you can extend them) and since the implementation has to be a
+controlled type anyway, we might as well expose the tagged-ness to the
+user.
+
+With the addition of interfaces, I would actually expect that mixins
+involving containers and user-defined interfaces would be quite common in
+programs making heavy use of the OOP paradigm.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 6, 2004  12:25 PM
+
+The reasoning was that since these are tagged anyway (because the type 
+must privately derive from Controlled), then we might as well make them 
+publicly tagged.
+
+This has benefits besides allowing type extension, for example, tagged 
+type subprogram parameters are implicitly aliased, and you can use 
+distinguished-receiver syntax.
+
+However, there is a cost, and that is when a derivation occurs, you must 
+override all the primitive functions that return the type.
+
+This is a pain, when you simply want the convenience of implementing 
+some other type as a private derivation from vector (say):
+
+package P is
+    type T is private;
+    ...
+private
+    type T is new Vector_Types.Vector with null record;
+    --must override To_Vector, etc
+end P;
+
+The locution above is a common Ada idiom (in fact, it's how all the 
+containers are implemented).
+
+In this case, however, the convenience of deriving from Vector is 
+outweighed by having to override 6 vector functions, none of which are 
+needed to implement T.  It is in this sense that making the vector type 
+tagged isn't free.
+
+I support the decision to make the containers tagged (for the two 
+benefits I list above), but my concern is the cost of derivation.  But 
+maybe container derivation isn't common enough to worry about.
+
+You can eliminate this cost by making functions that return the type 
+non-primitive, but that of course has its own costs.  If you're doing 
+any kind of polymorphic programming, you wouldn't be able to dispatch on 
+the tag of the function result.  But then again, polymorphic programming 
+of containers seems a little bizarre, so maybe it isn't common enough to 
+worry about.
+
+
+> With the addition of interfaces, I would actually expect that mixins
+> involving containers and user-defined interfaces would be quite common in
+> programs making heavy use of the OOP paradigm.
+
+I am skeptical.  In the vast majority of cases, the type of the 
+container is known statically.  I can't imagine why anyone would ever 
+need a polymorphic class of, say, integer vectors.  Any mixing of 
+containers can be done entirely using static mechanisms (cursors and 
+iterators).
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, October 6, 2004  12:40 PM
+
+> I support the decision to make the containers tagged (for the two
+> benefits I list above), but my concern is the cost of derivation.  But
+> maybe container derivation isn't common enough to worry about.
+
+Well, if the containers weren't tagged, then there wouldn't be any (useful)
+derivation. So this is only saying that it isn't quite as easy to derive as
+we might like. The choice really seems to be between not allowing derivation
+at all or having it be more painful that we'd like.
+
+But moving various operators into a child package (which would require a
+separate instantiation) or a nested package seems weird. That's especially
+true for sets; do we really want "Union" to be non-primitive? (And then
+again you couldn't use the prefix notation for calls.)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 6, 2004  1:02 PM
+
+> Well, if the containers weren't tagged, then there wouldn't be any (useful)
+> derivation. 
+
+I gave an example of what I consider to be a very useful derivation:
+
+package P is
+    type T is private;
+    ...
+private
+    type T is new Vector_Types.Vector;  --no extension if not tagged
+end P;
+
+
+I bring this up because I actually attempted to declare a type as above, 
+but ended up abandoning that approach when I was forced to override the 
+primitive functions.
+
+But it's no big deal, since I was able to solve the problem another way.
+
+****************************************************************
+
 From: Nick Roberts
 Sent: Tuesday, October 5, 2004  11:58 AM
 
@@ -21367,133 +21490,2612 @@
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Nick Roberts
+Sent: Wednesday, October 6, 2004  5:50 AM
 
-****************************************************************
+Robert A Duff wrote:
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+>>Would it make sense now to allow conversion towards an extension type?
+> 
+> Sounds dangerous, to me.
+> ...
+> Besides, downward conversions are view conversions, and are allowed only
+> for class-wide operands, and there's a tag check.  Making TT(X)
+> equivalent to an extension aggregate doesn't fit in well with that.
+
+I actually agree, on reflection.
+
+> I wouldn't say it's awkward -- it's necessary, to make sure the
+> extension components are not forgotten.  I suppose it might make sense
+> to rescind that rule when the extension is "with null record".  I think
+> we considered that during the Ada 9X design, but decided it wasn't
+> worthwhile to have such a special case.
+
+I think maybe it would be worthwhile, on the grounds that it isn't, in 
+fact, such a special case. Perhaps the ARG should consider this again?
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Tucker Taft
+Sent: Wednesday, October 6, 2004  10:16 AM
 
-****************************************************************
+> I think maybe it would be worthwhile, on the grounds that it isn't, in 
+> fact, such a special case. Perhaps the ARG should consider this again?
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Even for a null extension, there might be additional operations
+which are not present in the dispatch table of the type of
+the object.  This really doesn't work.  What you want is
+an extension aggregate.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Randy Brukardt
+Sent: Wednesday, October 6, 2004 12:58 PM
 
-****************************************************************
+I've posted the updated AI-302-3 (Containers) to the web site. Find it
+through
+   http://www.ada-auth.org/ais.html
+(the file name is AI-20302.TXT) [This is version /07 of the AI - ED]
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+There is a list of changes beyond those discussed in Madison at the end of
+the !appendix section (the very end of the AI file).
+
+Comments are welcome, but keep in mind that we're planning to approve the AI
+at the meeting next month (else it may not make the Amendment). So major
+overhauls aren't practical. We're just looking to improve the details at
+this point.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Jeff Carter
+Sent: Wednesday, October 6, 2004  1:49 PM
 
-****************************************************************
+I have a minor complaint about the ordering of operations in the package 
+specifications. When using a container, I generally want to know how to 
+create one, how to put things in it, how to access things that are in 
+it, and how to delete things from it. The next most common thing is to 
+make it empty. Therefore, I think these operations should come first in 
+the specs. Right now they tend to be scattered around, separated by less 
+common operations. For example, looking at vectors, is "&" really more 
+common than Insert, Update, Replace (these 2 seem to be the same, so I 
+don't know why the names differ), and Delete?
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+One also needs to be able to determine locations within containers 
+(cursors and indices for vectors) in order to do these common 
+operations, so operations that provide locations should also be among 
+the first in the spec.
+
+The container library proposed seems to be significantly different from 
+the STL, not to mention much smaller. The references to the STL in the 
+AI do not seem to add anything, and should probably be eliminated.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Tucker Taft
+Sent: Thursday, October 7, 2004  5:59 AM
 
-****************************************************************
+I hate to weigh in on this now, but...
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+It is a fairly common paradigm to instantiate a package
+and then use derivation to bring the type into the
+current scope.  E.g:
+
+    package T_Vecs is new Vectors(T);
+    type T_Vec is new T_Vecs.Vector;
+
+Making the type tagged and giving it various operations
+that are functions returning the type does defeat this
+approach (since "with null record;" wouldn't work without
+having to override all of the functions).
+
+There seem to be a few alternatives to deal with this:
+
+   a) live with it as is
+   b) define "type NT is new T with null record;" to
+      provide default implementations of such functions
+      by implicitly providing an extension aggregate at the
+      point of call, e.g.: "Union(X,Y)" for NT is equiv to
+        "NT'(Union(T(X),T(Y)) with null record)"
+   c) make types untagged, and support object.op syntax
+      on untagged record and private types.
+
+I kind of like option (b) as we don't want to force the
+use of untagged types to enable this paradigm.
+
+[ASIDE: This issue also reminds me of the problem we never fixed:
+
+     type T is private;
+     function "+"(X, Y: T) return T;
+   private
+     type T is new Integer;
+     function "+"(X, Y: T) return T renames <>;  -- inventing here
+
+It is pretty often that you want a private type to expose
+some but not all of the operations of the full type.
+Some kind of renaming would be great.  Right now,
+you have to write wrappers for each such operation,
+which is a bit of a pain.  End of ASIDE.]
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Nick Roberts
+Sent: Thursday, October 7, 2004  8:57 AM
 
-****************************************************************
+This does all seem to be suggesting the introduction of a new form of 
+declaration, the 'default completion'.
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+   default_completion ::=
+     subprogram_specification [IS subprogram_default] ;
 
-****************************************************************
+obviously similar to a formal subprogram declaration. This declaration 
+would be allowed anywhere a subprogram body is allowed, and would form the 
+completion of a subprogram, declared in the visible part of a package, 
+which is a primitive operation of a private type T. The type declaration in 
+the private part of the package must be a type derivation declaration; let 
+the type from which it is derived be called P.
+
+The subprogram's body would be formed from the body of the corresponding 
+operation of P, with every parameter of type P converted to T, and each 
+other occurrance of P replaced by T. The conversion would be a view 
+conversion for non-tagged types, and a conversion of the form Tuck 
+suggested for a tagged type which added no extra components.
+
+Default completions would be disallowed for a tagged type which did add 
+components.
+
+The idea is that we could derive from a container thus:
+
+    package Foo is
+       package T_Vecs is new Ada.Containers.Vectors(T);
+       type T_Vec is private;
+       function Length (Container : T_Vec) return Count_Type;
+       function Is_Empty (Container : T_Vec) return Boolean;
+       procedure Clear (Container : in out T_Vec);
+       procedure Append (Container : in out T_Vec;
+                         New_Item  : in     T_Vec);
+       ... -- other vector operations we want to expose
+    private
+       type T_Vec is new T_Vecs.Vector with null record;
+       ...
+    end;
+
+    package body Foo is
+       ...
+       function Length (Container : T_Vec) return Count_Type is <>;
+       function Is_Empty (Container : T_Vec) return Boolean is <>;
+       procedure Clear (Container : in out T_Vec) is <>;
+       procedure Append (Container : in out T_Vec;
+                         New_Item  : in     T_Vec) is <>;
+       ...
+    end Foo;
+
+We still have to explicitly declare the operations we wish to inherit, and 
+their completions (in the package body), but at least the form of the 
+completions is succinct and clear (making it explicit that the operations 
+are direct copies).
+
+We could also have:
+
+    package Bar is
+       type T is private;
+       function "+"(X, Y: T) return T;
+       ...
+    private
+       type T is new Integer;
+       ...
+    end;
+
+    package body Bar is
+       function "+"(X, Y: T) return T is <>;
+       ...
+    end Bar;
+
+****************************************************************
+
+From: Dan Eilers
+Sent: Thursday, October 7, 2004  4:35 PM
+
+> [ASIDE: This issue also reminds me of the problem we never fixed:
+>
+>      type T is private;
+>      function "+"(X, Y: T) return T;
+>    private
+>      type T is new Integer;
+>      function "+"(X, Y: T) return T renames <>;  -- inventing here
+>
+> It is pretty often that you want a private type to expose
+> some but not all of the operations of the full type.
+> Some kind of renaming would be great.  Right now,
+> you have to write wrappers for each such operation,
+> which is a bit of a pain.  End of ASIDE.]
+
+I am in favor of fixing this problem, having seen real customer
+code that did this.  Note that there is a hazard in trying to write
+the wrapper workaround, in that it is easy to accidentally infinitely
+recurse.
+
+****************************************************************
+
+From: Dan Eilers
+Sent: Thursday, October 7, 2004  4:57 PM
+
+> Making the type tagged and giving it various operations
+> that are functions returning the type does defeat this
+> approach (since "with null record;" wouldn't work without
+> having to override all of the functions).
+>
+> There seem to be a few alternatives to deal with this:
+...
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Another alternative might be to allow type renaming:
+      package T_Vecs is new Vectors(T);
+      type T_Vec renames T_Vecs.Vector;
+
+with the semantics that you want.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Martin Krischik
+Sent: Friday, October 8, 2004  4:01 AM
 
-****************************************************************
+I allwas though that typerenaming where not added because subtypes do the 
+same.
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+subtype  T_Vec is T_Vecs.Vector;
 
-****************************************************************
+Mind you: In my fist Ada month I did actually try to rename types I wonder why 
+it was not possible. Then the textbook told me that "subtype" is the thing to 
+do.
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+> with the semantics that you want.
+
+Saying the subtypes and typerenaming are supposed to be sematicly the same I 
+wonder if typerenaming should not be allowed as a syntax option since it 
+would be often closed to want the programmer wants to express.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Tucker Taft
+Sent: Friday, October 8, 2004  10:24 PM
 
-****************************************************************
+Type renaming creates a realm of thorny issues, relating
+for example, to where primitives are (re)declared.
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+I don't believe this is a time to open up discussion of
+a completely new syntactic feature.
 
+On the other hand, I think we do need to be sensitive
+to whether there are some minor "tweaks" of the various
+proposals that will make them work better together.
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Christoph Grein
+Sent: Thursday, October 7, 2004  6:24 AM
+
+>    b) define "type NT is new T with null record;" to
+>       provide default implementations of such functions
+>       by implicitly providing an extension aggregate at the
+>       point of call, e.g.: "Union(X,Y)" for NT is equiv to
+>         "NT'(Union(T(X),T(Y)) with null record)"
+
+I like this proposal.
+
+> [ASIDE: This issue also reminds me of the problem we never fixed:
+> 
+>      type T is private;
+>      function "+"(X, Y: T) return T;
+>    private
+>      type T is new Integer;
+>      function "+"(X, Y: T) return T renames <>;  -- inventing here
+> 
+> It is pretty often that you want a private type to expose
+> some but not all of the operations of the full type.
+> Some kind of renaming would be great.  Right now,
+> you have to write wrappers for each such operation,
+> which is a bit of a pain.  End of ASIDE.]
+
+And I have often grumbled about this, too, and like Tuck's invention, which
+is fully upward compatible.
+But I fear it's too late for Ada0Y.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Nick Roberts
+Sent: Thursday, October 7, 2004  10:55 AM
+
+I wrote:
 
+>   default_completion ::=
+>     subprogram_specification [IS subprogram_default] ;
+
+Obviously I should have written:
+
+    default_completion ::=
+      subprogram_specification IS subprogram_default ;
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Sent: Monday, October 25, 2004 11:36 AM
+
+
+
+Tucker Taft wrote:
+> 
+> It is a fairly common paradigm to instantiate a package
+> and then use derivation to bring the type into the
+> current scope.  E.g:
+> 
+>    package T_Vecs is new Vectors(T);
+>    type T_Vec is new T_Vecs.Vector;
+> 
+> Making the type tagged and giving it various operations
+> that are functions returning the type does defeat this
+> approach (since "with null record;" wouldn't work without
+> having to override all of the functions).
+
+I have been corresponding with someone who is teaching a class in data 
+structures.  He was trying to use the vector container to implement a stack:
+
+generic
+    type ET is private;
+    with function "=" (L, R : ET) is <>;
+packcage Stacks is
+    type Stack is private;
+    procedure Push (Container : in out Stack;
+                    New_Item  : in ET);
+    procedure Pop (Container : in out Stack);
+private
+
+    package ET_Vectors is
+      new Ada.Containers.Vectors (Positive, ET, "=");
+
+    type Stack is
+      new ET_Vectors.Vector with null record;
+    --won't compile as is
+
+end Stacks;
 
+He was confused about the compiler error messages, stating that he had 
+to override the function To_Vector, etc.  (He knows Ada83, but he's 
+still learning Ada95.)
+
+I bring this up as a real-life example of the fact that private 
+derivation is a very natural Ada idiom, since to him that was the most 
+obvious solution.
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Ehud Lamm
+Sent: Monday, October 25, 2004  11:56 AM
+
+When I first started doing this sort of thing in Ada I was confused myself,
+as I am pretty sure my studetns will be. 
+Alas, I don't see a good solution. The child package approach seems to be as
+confusing, if not more.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Dan Eilers
+Sent: Monday, October 25, 2004  12:21 PM
+
+Isn't "type renaming" exactly the solution you're looking for?
+It seems you don't really want to make Stack a new type derived from
+ET_Vectors.Vector, instead you want to say that Stack is implemented by,
+or in other words, renames ET_Vectors.Vector.
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Sent: Saturday, October 9, 2004 12:47 AM
+
+I just had a quick(?) question about dope vectors for arrays.  Suppose I
+have this declaration:
+
+declare
+   type String_Access is access all String;
+   S : aliased String (1 .. 10);
+   X : String_Access := S'Access; --not legal Ada95 
+begin
+
+The declaration of X is illegal, since S doesn't have a dope vector.  I can
+do this:
+
+declare
+   type String_Access is access all String;
+   S : aliased String := String'(1 .. 10 => ' ');
+   X : String_Access := S'Access; --OK 
+begin
+
+Was this behavior liberalized in Ada 2005?  Is there a way for the
+programmer to say: "give me a dope vector for this array object", so that
+the former declaration would be legal?
+
+What about a record component:
+
+   type RT (N : Natural) is record
+      S : aliased String (1 .. N);
+   end record;
+
+   R : RT;
+   X : String_Access := R.S'Acccess;
+
+I was thinking about the functions-that-return-anonymous-access-types, to
+handle this case:
+
+   type T is limited private;
+   function S (O : access T) return access String;
+private
+   type T is limited record
+     S : aliased String (1 .. 10);  --or maybe this is a discriminant
+   end record;
+
+   function S (O : access T) return access String is 
+   begin   
+      return O.S'Access;
+   end;
+...
+
+declare
+   O : aliased T;
+   SS : String renames S (O'Access).all;
+begin
+
 
+Just curious...
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Tucker Taft
+Sent: Saturday, October 9, 2004  11:19 AM
+
+> Was this behavior liberalized in Ada 2005?
+
+No.
+
+> ...  Is there a way for the
+> programmer to say: "give me a dope vector for this array object", so that
+> the former declaration would be legal?
+
+No.
+
+> 
+> What about a record component:
+> 
+>    type RT (N : Natural) is record
+>       S : aliased String (1 .. N);
+>    end record;
+> 
+>    R : RT;
+>    X : String_Access := R.S'Acccess;
+
+No.  You can't get there from here.
+
+> ...
+> Just curious...
 
+Good question, but we didn't make fixing this a priority.
+There is no obvious fix other than to say that all
+aliased arrays must have dope vectors pre-allocated in
+a way that would allow an access-to-unconstrained pointer
+to point at them.  That probably would have been the
+right answer in Ada 95, in retrospect, but changing it
+now could break some working code in bizarre ways,
+as it would require a change in representation for
+existing data types.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Sent: Thursday, October 21, 2004 11:28 PM
+
+!standard A.17                    04-10-04  AI95-00302-03/07
+!subject Container library
+
+My review of the post-Madison AI-302 draft follows.
+
+As usual, each comment is bracketed with "MJH:" and "ENDMJH." pairs, and
+immediately follows the text to which it refers.
+
+I haven't copied the entire AI draft here.  Rather, I give just enough
+context to determine the relevant section.
+
+I can summarize most of my comments as:
+
+(1) If we decide to keep the new cursor-based replace operation for
+    sets, then it should be named "Replace_Element", not "Replace".
+
+(2) We need to get rid of the key-based replace operation for sets, the
+    operation named "Replace" in the nested package Generic_Keys.
+
+(3) The set operation named "Checked_Update_Element" declared in the
+    nested package Generic_Keys should be named just "Update_Element".
+
+(4) We need to get rid of the requirement that an implementation detect
+    container modification while passive iteration is in progress.  This
+    requirement is unnecessary since we already have a meta-rule that
+    says container behavior is unspecified if a container object is
+    simultaneously read from and written to.  This rule of course
+    applies even if it's the same task doing the reading and writing.
+
+(5) This API needs to state unambigously that a container implementation
+    must support multiple tasks simultaneously reading from a container
+    object.  In particular it is perfectly legal for multiple tasks to
+    simulaneously perform passive iteration over a container.
+
+(6) This API needs(?) to state that there are no container operations
+    that are "potentially blocking."
+    
+
+A.17 Containers
+
+...
+
+Note that the language already includes several requirements that are
+important to the use of containers. First, library packages must be
+reentrant - multiple tasks can use the packages as long as they operate on
+separate containers. Thus, it is only necessary for a user to protect a
+container if a single container needs to be used by multiple tasks.
+
+
+MJH:
+
+We need to be clear here about multithreading issues, since that last
+sentence is wrong.
+
+The only problem case is when there are multiple writers, or a single
+writer and one or more readers.  (The reader and writer can also be the
+same task.)
+
+It is definitely *not* an error for multiple readers to access the same
+container all simultaneously.
+
+In particular, it is perfectly acceptable (in fact, the API is designed
+to facilitate this) for multiple tasks to be iterating over a same
+container object, using either cursors or the passive iterator.
+
+We already have a rule that says container behavior is not defined when
+a container is simultaneously written to and read from.  The rule
+applies whether it is one task or more than one task.
+
+ENDMJH.
+
+
+Second, the language requires that language-defined types stream "properly".
+That means that the stream attributes can be used to implement persistence
+of containers when necessary, and containers can be passed between
+partitions of a program.
+
+...
+
+A.17.2 The Package Containers.Vectors
+
+...
+package Ada.Containers.Vectors is
+
+...
+   function To_Vector (Length : Count_Type) return Vector;
+
+   function To_Vector
+     (New_Item : Element_Type;
+      Length   : Count_Type) return Vector;
+
+   function "&" (Left, Right : Vector) return Vector;
+
+   function "&" (Left  : Vector;
+                 Right : Element_Type) return Vector;
+
+   function "&" (Left  : Element_Type;
+                 Right : Vector) return Vector;
+
+   function "&" (Left, Right  : Element_Type) return Vector;
+
+
+MJH:
+
+We have already discussed the fact making these functions primitive
+means that they must be overridden during a derivation, since the
+function return type is Vector.  (There is a similar issue for sets.)
+
+This is kind of a pain, since it's very common to implement the full
+view of a private type as a null extension of some other (tagged) type,
+or to derive from a type in order to bring its primitive operations into
+local scope.
+
+We can either live with this feature, arrange to make these operations
+non-primitive, or modify the language such that, say, a null extension
+inherits a default implementation of these functions.
+
+ENDMJH.
+
+...
+
+   procedure Delete (Container : in out Vector;
+                     Index     : in     Extended_Index;
+                     Count     : in     Count_Type := 1);
+
+MJH:
+
+See my comments below about the subtype and semantics of parameter Index
+for the index-based Delete operation.
+
+ENDMJH.
+
+...
+
+
+   generic
+      with function "<" (Left, Right : Element_Type)
+         return Boolean is <>;
+   procedure Generic_Sort (Container : in Vector);
+
+
+MJH:
+
+Another operation that might be useful is a binary search over a sorted
+vector:
+
+   generic
+      with function "<" (Left, Right : Element_Type)
+         return Boolean is <>;
+
+   function Generic_Binary_Search (Container : Vector;
+                                   Item      : Element_Type)
+      return Extended_Index;
+
+
+(It's just an idea...)      
+
+ENDMJH.   
+
+...
+
+procedure Delete (Container : in out Vector;
+                  Index     : in     Extended_Index;
+                  Count     : in     Count_Type := 1);
+
+If Count is 0, the operation has no effect. If Index does not specify a
+value in the range First_Index (Container) .. Last_Index (Container), then
+Constraint_Error is propagated. Otherwise Delete slides the active
+elements (if any) starting Index plus Count down to Index. Any
+exceptions raised during element assignment are propagated.
+
+
+MJH:
+
+The semantics wrt the Index parameter are arguably inconsistent with the
+semantics of the cursor-based delete.  Any index value outside of the
+range IT'First .. C.Last is technically the same as "not Has_Element",
+so you could make an argument that it should be treated the same as the
+cursor-based delete (meaning that it should be a no-op).
+
+ENDMJH.
+
+...
+
+procedure Swap (I, J      : in Cursor);
+
+If either I or J is No_Element, then Constraint_Error is propagated. If I
+and J
+designate elements in different containers, then Program_Error is
+propagated.
+Otherwise Swap exchanges the values of the elements designated by I and J.
+
+MJH:
+
+The ARG needs to confirm whether the second sentence is really correct.
+The semantics of Swap are equivalent to:
+
+  procedure Swap (I, J : Cursor) is
+     EI : constant ET := Element (I);
+  begin
+     Replace_Element (I, By => Element (J));
+     Replace_Element (J, By => EI);
+  end;
+
+There's nothing here that would preclude I and J from designating
+elements in different containers, so it's not clear why this an error.
+
+ENDMJH.
+     
+...
+
+procedure Iterate
+   (Container : in Vector;
+    Process : not null access procedure (Position : in Cursor));
+
+Invokes Process.all with a cursor that designates each element in Container,
+in
+index order. Any exception raised by Process is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called. There is no check needed if an attempt is made to insert or
+delete
+nothing (that is, Count = 0 or Length(Item) = 0).
+
+The check is easy to implement: each container needs a counter. The counter
+is incremented when Iterate is called, and decremented when Iterate
+completes.
+If the counter is nonzero when an operation that inserts or deletes is
+called,
+Finalize is called, or one of the other operations in the list occurs,
+Program_Error is raised.
+
+Swap and Generic_Sort are not included here, as they only copy elements.
+End AARM Notes.
+
+
+MJH:
+
+Au contraire: the counter-based check described above isn't adequate for
+detecting container modification during passive iteration, since it
+won't work in the presence of multiple reader tasks.
+
+We already have a rule that says container behavior is undefined if a
+container is simultaneously read from and written to.  This rule applies
+even if it's the same task doing the simultaneous reading and writing.
+
+Hence the requirement above is entirely superfluous, and therefore it
+should be removed.
+
+A cursor does not need to confer any safety benefits beyond what an
+access type provides.  (This is especially true for a vector, which
+implements a cursor as a wrapper around an index.)
+
+ENDMJH.
+
+...
+
+A.17.3 The Package Containers.Doubly_Linked_Lists
+
+...
+
+procedure Swap (I, J  : in Cursor);
+
+If either I or J is No_Element, then Constraint_Error is propagated. If I
+and J
+designate elements in different containers, then Program_Error is
+propagated.
+Otherwise Swap exchanges the values of the elements designated by I and J.
+
+AARM Notes:
+After a call to Swap, I designates the element value previously
+designated by J, and J designates the element value previously
+designated by I. The cursors do not become ambiguous from this operation.
+
+AARM Notes: To Be Honest: The implementation is not required to actually
+copy the elements if it can do the swap some other way. But it is allowed
+to copy the elements if needed.
+
+MJH:
+
+The ARG needs to confirm the behavior when I and J designate elements in
+different containers.  See my comment above for vectors.
+
+ENDMJH.
+
+...
+
+procedure Iterate
+   (Container : in List;
+    Process : not null access procedure (Position : in Cursor));
+
+Invokes Process.all with a cursor that designates each node in Container.
+Any
+exceptions raised during Process are propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all calls a routine that reorders the elements of Container
+   (Swap_Links, Splice, Generic_Sort, or Generic_Merge); or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called. There is no check needed if an attempt is made to insert or
+delete
+nothing (that is, Count = 0).
+
+See Iterate for vectors for a suggested implementation of the check.
+
+Swap is not included here, as it only copies elements.
+End AARM Notes.
+
+
+MJH:
+
+This requirement is redundant, since we already have a meta-rule that
+says container behavior isn't specified if the container object is
+simultaneously read from and written to.  This rule applies even if it's
+the same task doing the reading and writing (as would be the case when a
+container is modified during passive iteration).
+
+Note that the suggested implementation of the check doesn't work when
+there are multiple reader tasks.  A container must support simultaneous
+reading by multiple tasks.
+
+At the end of the day, it doesn't really matter whether the container is
+modified during iteration, as long as next node can be reached safely,
+and the iteration eventually terminates.  This is especially true for a
+list.  If a user decides to sort the list during iteration, and then
+iterate delivers items in some different order, then what's the problem?
+(It's certainly not a problem in the reference implementation.)
+
+The problem case is deleting nodes during iteration.  If the user
+deletes the current node, then the iterator might not be able to find
+the next node (since the next node pointer was stored on the node
+deleted).  You can handle that by keeping a few nodes in cache, so that
+a node retains its value after it has been deleted.  (You could do this
+using a special storage pool too, of course.)
+
+Here's an example I presented to Randy to illustrate some of these
+issues.  Suppose the list contains items that are equivalent in some
+way, and all the equivalent items are grouped together in sequence,
+something like:
+
+  a a b b b c d d d d e e
+
+Now we want to write a filter program, that removes all but the first
+member of each like sequence:
+
+  a b c d e
+
+You could implement such a filter this way:
+
+  procedure Filter (L : in out List) is
+
+     procedure Process (C : Cursor) is
+        D : Cursor;
+     begin
+
+        loop
+           D := Next (C);
+
+           if Has_Element (D)
+             and then Element (D) = Element (C)
+           then
+              Delete (L, D);  --NOTE: DELETION
+           else
+              return;
+           end if;
+
+        end loop;
+
+     end Process;
+
+  begin
+     Iterate (L, Process'Access);
+  end Filter;    
+
+
+Even though this algorithm deletes nodes during passive iteration, it
+works if Iterate is implemented this way:
+  
+   procedure Iterate
+     (Container : in List;
+      Process   : not null access procedure (Position : in Cursor)) is
+
+      Node : Node_Access := Container.First;
+
+   begin
+
+      while Node /= null loop
+         Process (Cursor'(Container'Unchecked_Access, Node));
+         Node := Node.Next;
+      end loop;
+
+   end Iterate;
+
+
+It's perfectly safe here, since it only deletes nodes that follow the
+current node.  The real issue is portability, since it won't work if
+Iterate is implemented this way:
+      
+   procedure Iterate
+     (Container : in List;
+      Process   : not null access procedure (Position : in Cursor)) is
+
+      Node : Node_Access := Container.First;
+
+   begin
+
+      while Node /= null loop
+         declare
+            Next : constant Node_Access := Node.Next;
+         begin
+            Process (Cursor'(Container'Unchecked_Access, Node));
+         end;
+         
+         Node := Next;
+      end loop;
+
+   end Iterate;
+
+The filter algorithm above would be erroneous in this case, since the
+node designated by the Next pointer has been deleted.
+
+Now I'm not saying that this API should support container modification
+during passive iteration, since the filter algorithm above could be
+implemented just as easily using the active iterator.  But there is a
+big difference between saying that we don't support it, and making a
+requirement that the implementation must detect modification during
+Iterate and raise an exception.
+
+The moral of the story is that the only thing this API should say about
+modification during iteration is that this API doesn't say what happens
+when modification during iteration occurs.
+           
+ENDMJH.
+
+...
+
+A.17.4 The Package Containers.Hashed_Maps
+
+...
+
+generic
+...
+package Ada.Containers.Hashed_Maps is
+...
+
+   function "=" (Left, Right : Map) return Boolean;
+
+MJH:
+
+We have been in discussion about adding another operation, called
+Equivalent, for sets and maps.  I'm not sure what such an operation
+would mean for a map, but I just wanted to write down somewhere that
+it's up for discussion in Atlanta.
+
+ENDMJH.
+
+...
+   procedure Replace_Element (Position : in Cursor;
+                              By       : in Element_Type);
+...
+   procedure Replace (Container : in out Map;
+                      Key       : in     Key_Type;
+                      New_Item  : in     Element_Type);
+
+MJH:
+
+The introduction of a new set operation has alerted me to the fact that
+we have two operations similarly named.  (See the set spec for more
+comments.)
+
+So far we have named the cursor-based replace operation
+"Replace_Element" and its element parameter "By" (this came from
+Ada.Strings.*), and named the key-based replace operation "Replace" and
+its element parameter "New_Item".
+
+The ARG should confirm whether this difference in naming of the
+cursor-based vs. key-based replace operations is intended.
+
+ENDMJH.
+                      
+...
+
+procedure Iterate
+   (Container : in Map;
+    Process : not null access procedure (Position : in Cursor));
+
+Iterate calls Process.all with a cursor that designates each node
+in the Container. Any exception raised by Process is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all calls Reserve_Capacity; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called.
+
+See Iterate for vectors for a suggested implementation of the check.
+
+We have to include Reserve_Capacity here, as rehashing probably will change
+the order that elements are stored in the map.
+End AARM Notes.
+
+MJH:
+
+We already have a rule that says behavior is unspecified when the
+container is simultaneously read from and written to.  That includes the
+case of a single task that is both the reader and writer (as is the case
+with Iterate).
+
+Note that for a hashed container (as for a list) the only real problem
+case is when the current node is deleted, since it contains the pointer
+to the next node.  (Note that if the deleted node retains its value
+after has been deallocated or put in cache, then deleting the current
+node isn't really a problem, since you would then be able to reach the
+next node.)
+
+It doesn't really matter if Move or Reserve_Capacity is called either,
+since the worst thing that happens is you run off the end of the buckets
+array, in which case Constraint_Error is propagated.  A simple assertion
+to check that the buckets index hasn't changed is all you would need to
+detect calls to Reserve_Capacity, and a simple assertion check is all
+you would need to detect whether the buckets array (pointer) has
+changed as a result of Move or Reserve_Capacity.
+
+ENDMJH.
+
+...
+
+A.17.5 The Package Containers.Ordered_Sets
+
+...
+
+generic
+...
+package Ada.Containers.Ordered_Sets is
+
+...
+
+   function "=" (Left, Right : Set) return Boolean;
+
+MJH:
+
+As I mentioned above, we have been in discussion about adding an
+operation called Equivalent, that is similar to "=" except that it
+compares each element for equivalence (using "<") instead of element
+"=".
+
+The ARG should also decide whether to bring back the lexicographical
+comparison operators for sets ("<", ">", etc), since Equivalent is
+defined as "not (L < R) and not (R < L)".
+
+ENDMJH.
+   
+...
+
+   procedure Replace (Container : in out Set;
+                      New_Item  : in     Element_Type);
+...
+
+   procedure Replace (Container : in Set;
+                      Position  : in Cursor;
+                      By        : in Element_Type);
+
+MJH:
+
+This new cursor-based replace operation for sets is named in a manner
+inconsistent with the rest of this API.  It should be named
+Replace_Element.  (Note that the element parameter is named By, not
+New_Item.  The parameter name By is always used as the element parameter
+of the cursor-based operation named Replace_Element.)
+
+ENDMJH.
+
+...
+
+   generic
+...   
+   package Generic_Keys is
+
+...
+       procedure Replace (Container : in out Set;
+                          Key       : in     Key_Type;
+                          New_Item  : in     Element_Type);
+
+MJH:
+
+This operation needs to be removed from this API.
+
+First of all, there's no guarantee that parameter Key matches the
+key-part of parameter New_Item.  This is a set and so the ultimate
+arbiter of position within the set is the key-part of the element
+itself.  In that case, you might was well just say:
+
+   Replace (Container => S, New_Item => E);
+
+A key-based replace doesn't buy you anything, since the New_Item
+parameter already has a key.
+
+But let's suppose someone really wants to use a key-based replace
+operation.  That means there are two possibilities: either the Key
+matches the key-part of New_Item, or it doesn't.
+
+If it matches the key-part of New_Item (and Randy has stated this is the
+normal case), then passing the key as a separate parameter is entirely
+redundant.
+
+If the key doesn't match, then you must search for the node that matches
+Key, remove it from the set, assign the value of New_Item to the element
+on that node, and then reinsert that node.  But of course that
+reinsertion might fail (since the key-part of New_Item) might already be
+in the set), and if so raise P_E.
+
+If you really want to change the key-part of an element, then you can do
+that using the existing key-based Find and cursor-based Replace_Element
+operations:
+
+   Replace_Element (S, Keys.Find (S, K), By => E);
+
+However, even that's kind of dubious.  That only thing Replace_Element
+really saves is that the node doesn't have to be deallocated and then
+reallocated.  You might as well just say:
+
+   Delete (S, K);
+   Insert (S, E);
+
+The bottom line is that Generic_Keys.Replace must be removed from this
+API.  It provides no new functionality, and only adds unnecessary
+clutter.
+
+ENDMJH.
+
+...
+       procedure Checked_Update_Element
+          (Container : in out Set;
+           Position  : in     Cursor;
+           Process   : not null access
+             procedure (Element : in out Element_Type));
+
+MJH:
+
+This operation should be named just "Update_Element", not
+"Checked_Update_Element".
+
+There's no need to say that an operation is "checked," since that's
+implied.  All operations are checked in some way or another.
+
+It also doesn't need to be named "Checked...", since unlike the
+Update_Element for other containers, this set operation has an extra
+parameter for the container.  Checking is implied by the extra
+parameter.
+
+Yet another clue that this Update_Element for sets is special is that it
+is declared in a special place, inside Generic_Keys.
+
+So saying that that this operation is "checked" doesn't tell you
+anything that you don't already know.  It just adds unnecessary
+syntactic overhead.
+
+Another issue is that it's inconsistent with Replace_Element.  That
+operation carries an extra container parameter too, yet it's not named
+Checked_Replace_Element (or Checked_Replace).  If it's obvious that
+Replace_Element is checked, then it should also be obvious that
+Update_Element is checked.
+
+Please change the name of this operation to "Update_Element".
+
+ENDMJH.
+
+
+   end Generic_Keys;
+
+private
+
+   ... -- not specified by the language
+
+end Ada.Containers.Ordered_Sets;
+
+...
+
+procedure Iterate
+   (Container : in Set;
+    Process : not null access procedure (Position : in Cursor));
+
+Invokes Process.all with a cursor that designates each element in Container.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called.
+
+See Iterate for vectors for a suggested implementation of the check.
+End AARM Notes.
+
+
+MJH:
+
+See my previous comments.  There should be no requirement for a check to
+determine whether a set has been modified during passive iteration.
+
+As usual, if checks are desired then they should be enabled by an
+assertion.  The ordered set is interesting because (at least in the
+reference implementation) it uses both looping and recursion to
+implement passive iteration:
+
+   procedure Generic_Iteration (Tree : in Tree_Type) is
+
+      procedure Iterate (P : Node_Access) is
+
+         X : Node_Access := P;
+
+      begin
+
+         while X /= Null_Node loop
+
+            Iterate (Left (X));
+
+            Process (X);
+
+            X := Right (X);
+
+         end loop;
+
+      end Iterate;
+
+   begin
+
+      Iterate (Tree.Root);
+
+   end Generic_Iteration;
+
+
+Again, it really doesn't matter much if the tree is modified, since
+eventually the iteration terminates when it reaches the bottom of the
+tree.
+
+However, if tree modification is a concern then you can insert some
+assertion checks (as many as the vendor feels is necessary):
+
+      procedure Iterate (P : Node_Access) is
+
+         X : Node_Access := P;
+
+      begin
+
+         while X /= Null_Node loop
+
+            pragma Assert (Is_Valid (Tree, X));
+
+            Iterate (Left (X));
+
+            pragma Assert (Is_Valid (Tree, X));
+
+            Process (X);
+
+            pragma Assert (Is_Valid (Tree, X));
+
+            X := Right (X);
+
+         end loop;
+
+      end Iterate;
+
+
+The Is_Valid function would be defined something like this:
+
+function Is_Valid 
+  (Tree : Tree_Type;
+   Node : Node_Access)  return Boolean is
+begin
+
+   if Tree.Length = 0 then
+      return False;
+   end if;
+   
+   if Tree.Root = Null_Node then
+      return False;
+   end if;
+
+   if Tree.First = Null_Node then
+      return False;
+   end if;
+
+   if Tree.Last = Null_Node then
+      return False;
+   end if;
+   
+   if Parent (Tree.Root) /= Null_Node then
+      return False;
+   end if;
+   
+   if Tree.Length > 1 then
+      null;
+
+   elsif Tree.First /= Tree.Last then
+      return False;
+
+   elsif Tree.First /= Tree.Root then
+      return False;
+
+   end if;   
+                                   
+   if Left (Node) = Null_Node then
+      null;
+
+   elsif Parent (Left (Node)) /= Node then
+      return False;
+
+   end if;
+
+   if Right (Node) = Null_Node then
+      null;
+
+   elsif Parent (Right (Node)) /= Node then
+      return False;
+
+   end if;
+
+   if Parent (Node) = Null_Node then
+      if Tree.Root /= Node then
+         return False;
+      end if;
+
+   elsif Left (Parent (Node)) = Node then
+      if Right (Parent (Node)) = Node then
+         return False;
+      end if;
+      
+   elsif Right (Parent (Node)) /= Node then
+      return False;
+
+   end if;
+
+   return True;
+
+end Is_Valid;
+
+
+You get the idea.  You can use this same technique for all the
+containers, to check the validity of the cursor passed to any
+cursor-based operation.
+
+
+ENDMJH.
+
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, October  3, 2004  xx:xx PM
+
+Here is a listing of the AI-302 updates that I made beyond those
+discussed at the meeting. These mostly have come up in more recent
+e-mail discussions.
+
+3) Replace and Exclude operations matching the ones in the Ordered_Sets were
+   added to the Generic_Keys generic, as it is odd that Delete was in there
+and
+   not the others.
+
+MJH:
+
+See my previous comments that the key-based Replace operation should not
+be part of this API.
+
+ENDMJH.
+
+
+   (The intent is that this package closely match Hashed_Maps
+   [and Ordered_Maps, if it ever is defined] - as many operations on keys in
+   Hashed_Maps should be represented here as possible.)
+
+MJH:
+
+The intent of Sets.Generic_Keys is *not* to make a set look like a map
+(we have maps for that), but rather to allow key-based manipulation of a
+set.
+
+It is always the case that the identity of the container as a *set* is
+preserved, even when using the operations in Generic_Keys.  The nested
+package is there to allow users to take advantage of composite element
+types which have a distinctive key component.
+
+ENDMJH.
+
+
+   Insert and Include were
+   omitted, as there could be no guarentee that the Key passed in matches
+the
+   one in the Element passed in. (We could check, of course, but that seems
+   like going too far; moreover, it's hard to imagine how these could be
+used.)
+
+MJH:
+
+But that's true of Replace as well.
+
+ENDMJH.
+
+   
+   Replace simply doesn't worry about it; it is defined in terms of Replace
+   (see below), replacing the element referred to by the Key. Thus it works
+   similarly to Checked_Update_Element.
+
+MJH:
+
+See my previous analysis.  There is no reason to have a key-based
+replace operation, since the addition of a cursor-based replace
+operation obviates its need.
+
+ENDMJH.
+
+
+   Replace (Container, Cursor, New_Item) also has been added to the Set
+itself,
+   as there is not a Replace_Element for a set. This tries to replace in
+place,
+   but will do an insert/delete if necessary.
+
+MJH:
+
+This operation should be named "Replace_Element", not "Replace".
+
+ENDMJH.   
+
+
+5) The index forms of Element, Replace_Element, Query_Element, and
+   Update_Element took Index_Type'Base for some reason, but passing No_Index
+   raises Constraint_Error. So I changed these to Index_Type, so that the
+   specification doesn't allow No_Index to be passed.
+
+MJH:
+
+I originally used IT'Base because the implementation must check that the
+index parameter satisfies the constraint that Index <= Last_Index (V),
+so passing in a constrained subtype didn't really buy you anything.
+
+ENDMJH.
+   
+
+6) Added an erroneous case for abuse of the Process procedure of
+Query_Element
+   and Update_Element. This usually looks like:
+
+  Execution also is erroneous if the called Process procedure of a call to
+  Query_Element or Update_Element executes an operation that causes the
+  Position cursor of Query_Element or Update_Element to become invalid.
+
+For lists, maps, and sets, the only problem occurs if the element is deleted
+directly, or if the container is finalized (via Unchecked_Deallocation).
+Insertions and other Deletions don't matter, as the nodes are logically
+separate.
+
+For vectors, the rule also includes ambiguous cursors. An insert or delete
+to
+the left of the cursor will move the elements; if the element is passed by
+reference, that will clobber the element being operated on with unknown
+effects. We don't want to require that optimization is off in Process
+subprograms! The vector version also requires wording to cover the index
+version of the routines.
+
+I'd like to suggest that we consider adding a check that the element being
+processed is not deleted by the Process procedure. This check requires only
+a
+bit per node (or a short list of elements in process), and covers all of the
+new dangerous cases for most of the containers.
+
+MJH:
+
+See my previous analysis.  This suggested implementation won't work in
+the presence of multiple reader taaks, which a container must support.
+
+We already have a rule that says simultaneous reading from and writing
+to a container has undefined behavior.  This rule applies whether it is
+one task or multiple tasks doing the simultaneous reading and writing.
+
+Hence there should be no requirement to perform any such checks.
+
+ENDMJH.
+
+
+(Bad use of
+Unchecked_Deallocation is hardly new to the containers, and Move will not
+actually cause problems in practice, as the nodes are not changed, just the
+container that they belong to.) Deleting yourself requires contortions (the
+Process routine does not have a cursor to use for this operation), and,
+since
+it damages the element parameter, the effects could be widespread. The check
+also would prevent calling Update_Element on the same element again, which
+would have different results depending on the parameter passing mode (and
+which
+makes the check cheaper). The overhead of the check would only apply to the
+various Deletes and Update_Element; no other routines would need to check.
+The
+text would be:
+
+   If the Process procedure deletes the element designated by Cursor, or
+calls
+   Update_Element on Cursor, Program_Error is raised.
+
+   AARM Note: This check has to be done in the code for Delete and
+Update_Element,
+   of course.
+
+Making vector Update_Element safe would also require checking for any
+operations that would make the cursor ambigious. (That's a bounded error in
+other cases.)
+
+MJH:
+
+See my previous comments.  The checks described above are not
+implementable.
+
+ENDMJH.
+
+
+
+8) Delete for cursors does nothing if the cursor is No_Element for Lists,
+Maps,
+   and Sets. (Matt says this was intended to model the effect of
+   Unchecked_Deallocation.) Delete for cursors in Vectors, on the other
+hand,
+   raised Constraint_Error in this case. I changed the wording for Delete
+for
+   cursors in Vectors to be consistent with the other three.
+
+MJH:
+
+The reasons are historical.  The index-based form of delete came first,
+and then (as now), specifying an index value outside of the active range
+of elements raised Contraint_Error.  (The model is that a vector is
+roughly the same as an array that can expand or contract.)
+
+When we added the cursor-based operations in Phoenix, I probably defined
+the semantics of the cursor-based delete operation for vector to match
+the semantics of the index-based delete operation, rather than matching
+the semantics of the cursor-based delete for other containers.
+
+Note that I have a comment above (in the vectors section) requesting the
+ARG to confirm the semantics of the index-based delete.  (That operation
+raises C_E if the index is outside of the active range of elements.)
+
+ENDMJH.
+
+
+10) Added an AARM note to the effect that when we say "unspecified" in this
+clause (A.17), we don't mean "erroneous". If we meant "erroneous", we said
+that. And included some ramifications of that (checking must not be
+suppressed;
+don't create dangling pointers by assuming behavior of generic formals).
+
+MJH:
+
+Maybe we should say that modifying a container during passive iteration,
+or during Update_Element, etc, has "unspecified" behavior?  I am not in
+favor of requiring any sort of check (especially since the suggested
+implementation won't work if there are multiple reader tasks).
+
+ENDMJH.
+
+
+15) Wording was added to Iterate for each container to say that
+Program_Error
+is raised if the Process routine calls an operation that will modify or
+reorder
+the container. Each container needs slightly different wording for various
+reasons (nodes can be reordered in Lists; rehashing in a Map would change
+the
+order).
+
+MJH:
+
+This requirement should be removed.  There is no way to make such a
+check that works when there are multiple reader tasks.
+
+This requirement is redundant anway, since we already have a meta-rule
+that says behavior is unspecified if a container is simultaneously read
+from and written to.  This rule applies irrespective of the number of
+tasks (including the case of the same task).
+
+ENDMJH.
+
+
+This decision grew out of a discussion between Matt and me as to what
+exactly
+the passive iterator should allow.
+
+We both agreed that trying to implement a passive iterator that could stand
+insertions and deletions of elements was hard.
+
+MJH:
+
+It varies by container.  My comments above highlight some of the
+differences among the containers.  The problem case for a list, for
+example, is deleting the current node; other than that, pretty much
+anything goes.
+
+At best, container modification during passive iteration is
+non-portable.  This API should not require that container modification
+during passive iteration be allowed, but it should not require that
+modification during passive iteration be prevented, either.
+
+In particular, there should be no requirement to perform any check
+during passive iteration to detect modification.
+
+ENDMJH.
+
+Morevoer, if the user needs to
+do that, they can use an active iterator (that is, a loop with explicit
+cursors) to do so. So, we agreed that inserting or deleting elements from
+within a passive iterator was bad, and there is no need or intent support
+it.
+
+MJH:
+
+Whether or not it's "bad" depends on the implementation.  If you delete
+the current node during passive iteration over a list, for example, then
+very likely the implementation will read some deallocated memory to get
+the pointer to the next node.  That would clearly be bad, unless the
+implementation stores deleted nodes in a cache, or arranges for
+deallocated memory to retain its state (say, by using a special storage
+pool), in which case there would be no problem.
+
+On the other hand, if nodes other than the current node are deleted,
+then there isn't any problem.  (But again, it depends on the
+implementation.)
+
+So no, this API should not require implementations to support container
+modification during passive iteration, but that's a far different thing
+from requiring that an implementation prevent such modification.
+
+There is a meta-rule that says the container must support manipulation
+by multiple reader tasks.  There is no way (that I know of, at least) to
+check that a container isn't modified during passive iteration in a way
+that doesn't violate this meta-rule.  That's why there should be no
+requirement for such a check, since it's impossible to implement.
+
+ENDMJH.
+
+
+The main undecided issue is what to do if the user does indeed make a
+mistake
+and insert or delete an element from the container during a passive
+iterator.
+There seem to be 4 possibilities:
+
+1) Specified results (it works in some specified way);
+
+MJH:
+
+For the vector and list, you could probably do that without too much
+implementation burden.  (Well, I take that back.  Randy and Pascal are
+implementing their vectors using a two-tier structure and a skip list,
+respectively, so I can't say what burden would entail.)
+
+In any event, it's probably not worth the bother of specifying allowed
+modifications during passive iteration, since the user can just manually
+use a cursor and an explicit loop.
+
+ENDMJH.
+
+
+2) Unspecified results (it works, but what it does isn't specified);
+
+MJH:
+
+I'm not sure we can even guarantee that "it works," since this might
+overly constrain an implementor (by requiring that he cache nodes, for
+example).
+
+ENDMJH.
+
+
+3) Erroneous (anything goes);
+
+MJH:
+
+If a node gets deallocated, and you refer to that node in order to
+navigate to some other node, then you have a dangling reference, so I
+assume that falls under the heading of "erroneous."
+
+ENDMJH.
+
+
+4) Check for bad cases and raise an exception.
+
+MJH:
+
+This won't work if there are multiple reader taaks.
+
+ENDMJH.
+
+
+(1) is clearly too burdensome on the implementation, and besides, we don't
+    want it.
+(2) would insure that the program wouldn't crash, but otherwise the results
+    wouldn't be portable.
+(3) would allow anything, implementers could ignore the possibility.
+(4) would be the most portable, but there are concerns about overhead.
+
+MJH:
+
+It's not even clear to me how (4) could even be implemented, since
+there's no way to perform a check that works in the presence of multiple
+reader tasks.
+
+ENDMJH.
+
+
+I originally wrote (2) using the wording: "Which cursors are presented to
+Process is unspecified if..." But that seems to be a burden on
+implementations
+for little benefit.
+
+I object to (3), because users *will* make this mistake, and likely
+implementations of the iterators would have very bad effects. If the node
+that
+the iterator was holding onto was deleted, it probably would be
+Unchecked_Deallocated, the memory might be reused, and when the pointers are
+walked, just about anything could happen.
+
+MJH:
+
+Not necessarily.  You yourself have already stated you plan on using a
+node cache, which means nodes would retain their state.  You could
+arrange to put a newly-deleted node at the end of the queue, such that
+it retains its state for as long as possible.  You could even use a
+generic formal constant (or some other mechanism) to control how large
+the cache is.
+
+Note that I have already implemented some of the validity checking
+described in an earlier comment, and I was able to successfully detect a
+dangling reference without doing anything special.  The validity
+checking would be even more robust were I to use GNAT's special
+Debug_Pool storage pool.
+
+ENDMJH.
+
+
+(4) seemed to have too much overhead, but once we stopped trying to support
+any
+insertion or deletion into the container, the cost became quite reasonable.
+All
+the implementation of the check would need is a counter (8 bits probably is
+enough) in each container. When an Iterate starts, the counter is
+incremented;
+when it completes, the counter is decremented. Each of the operations on the
+list of problem operations check that the counter is zero, raising
+Program_Error if the counter is nonzero.
+
+MJH:
+
+This won't work in the presence of multiple reader tasks, which a
+container must support.
+
+This API shouldn't be tied to a particular implementation technique
+anyway.
+
+ENDMJH.
+
+
+(We don't have to worry about tasking issues, as the container object is
+inside
+of the Iterate call the entire time. If some other task makes a call during
+that time, we have bad use of shared variables, and we don't care what
+happens.
+In fact, what will happen is that Program_Error would be raised, which is
+probably a good thing.)
+
+MJH:
+
+We certainly do have to worry about tasking issues!  It is certainly
+*not* an error if multiple tasks all call Iterate simultaneously.
+
+ENDMJH.
+
+
+That has very little overhead, because virtually all of the operations in
+question allocate or deallocate memory, and thus are expensive anyway, an
+additional compare and branch will have no visible impact on performance.
+(Sorting and Merging are also expensive; Swap_Links and Splice are the only
+exceptions.) Operations that don't modify the container don't need to make
+any
+check.
+
+MJH:
+
+This technique doesn't work if there are multiple reader tasks.
+
+ENDMJH.
+
+
+This has the advantage of making passive iterators completely safe against
+problems caused by what container operations are invoked in Process. (Yes,
+calling Unchecked_Deallocation on the container could still cause problems,
+but
+that is covered by other rules of the language -- and even it would raise
+Program_Error.) It also means that uses of passive iterators are safely
+portable (whereas active iterators could have problems if a dangling cursor
+was
+used) -- which gives them a clear advantage.
+
+MJH:
+
+Well, if we're going to invoke "other rules of the language," then we
+should just invoke the rule that says simultaneously reading from and
+writing to a container is undefined, irrespective of whether this is one
+task or multiple tasks.
+
+ENDMJH.
+
+
+This check is another one that could be dropped in an "unchecked" container.
+
+MJH:
+
+This check doesn't belong in this API.  At a minimum the implementation
+of the check described above doesn't work when there are multiple reader
+tasks.
+
+ENDMJH.
+
+
+Thus, I've worded this check into all of the passive iterators.
+
+The wording enumerates the reasons that a check is needed:
+"if Process attempts to insert or delete elements into Container; or"
+
+"modifies Container" would be too broad, as it could include replacing the
+value of an element.
+
+MJH:
+
+I tend to think of the container and its elements as separate entities.
+I often use the term "change the cardinality of the container" to
+emphasize the modification of the container itself.
+
+ENDMJH.
+
+
+We need also to talk about finalization and about calling Move, as the
+current
+wording only talks about cursors being passed to operations, not something
+that
+happens *during* an operation. Moreover, once we decide to have a check,
+including that check in the body of Finalize and Move is not difficult.
+
+MJH:
+
+I am against mandating any such check.
+
+ENDMJH.
+
+
+****************************************************************
+
+
+MJH:
+
+The following comments apply to Pascal's new set API:
+
+  AI-20302-07-addendum-set-crlf.txt
+
+ENDMJH.  
+
+  
+
+A.17.6 Sets
+
+The language-defined packages Containers.Hashed_Sets and
+Containers.Ordered_Sets 
+provide private types Set and Cursor, and a set of operations for each type.
+A 
+hashed set container allow an arbitrary type to be stored in a set. An
+ordered 
+set container orders its element per a specified relation.
+
+MJH:
+
+Well, technically both kinds of set (indeed, all kinds of containers)
+allow an "arbitrary type" to be stored, not just the hashed set.
+
+ENDMJH.
+
+
+This section describes the declarations that are common to both kinds of
+sets. 
+See A.17.7 for a description of the semantics specific to
+Containers.Hashed_Sets 
+and A.17.8 for a description of the semantics specific to 
+Containers.Ordered_Sets.
+
+The type Set is used to represent sets. The type Set needs finalization (see
+
+7.6).
+
+A set contains elements. Set cursors designate elements. There exists an 
+equivalence relation on elements, whose definition is different for hashed
+sets 
+and ordered sets. A set never contains two or more equivalent elements. The 
+*length* of a set is the number of elements it contains. 
+
+Each nonempty set has two particular elements called the *first element* and
+the 
+*last element* (which may be the same). Each element except for the last
+element 
+has a *successor element*. If there are no other intervening operations, 
+starting with the first element and repeatedly going to the successor
+element 
+will visit each element in the map exactly once until the last element is 
+reached. The exact definition of these terms is different for hashed sets
+and 
+ordered sets.
+
+MJH:
+
+But do realize that only the ordered set has a Last_Element selector and
+a Delete_Last modifier.  I'm not sure any discussion of last element is
+even relevant, since the successor of last is well-defined (the cursor
+has the value No_Element).
+
+ENDMJH.
+
+
+Empty_Set represents the empty Set object. It has a length of 0. If an
+object
+of type Set is not otherwise initialized, it is initialized to the same
+value as Empty_Set.
+
+No_Element represents a cursor that designates no element. If an object of
+type
+Cursor is not otherwise initialized, it is initialized to the same
+value as No_Element.
+
+function "=" (Left, Right : Set) return Boolean;
+
+If Left and Right denote the same set object, then the function returns
+True. If 
+Left and Right have different lengths, then the function returns False. 
+Otherwise, for each element E in Left, the function returns False if an
+element 
+equivalent to E is not present in Right. If the function has not returned a 
+result after checking all of the elements, it return True. Any exception
+raised 
+during evaluation of element equivalence is propagated.
+
+MJH:
+
+As I have already mentioned, equality for sets is (er, should be)
+defined in terms of element equality, not equivalence.  This is true for
+all containers, so sets shouldn't be any different.
+
+ENDMJH.
+
+...
+
+procedure Replace (Container : in out Set;
+                   New_Item  : in     Element_Type);
+
+If Length (Container) equals 0, then Contraint_Error is propagated.
+Otherwise, 
+Replace checks if an element equivalent to New_Item is already in the set.
+If a 
+match is found, that element is replaced with New_Item; otherwise, 
+Constraint_Error is propagated.
+
+MJH:
+
+I'm not sure why that first sentence is necessary, since the last
+sentence includes the case of Length(C) = 0.
+
+ENDMJH.
+
+...
+
+procedure Iterate
+   (Container : in Set;
+    Process : not null access procedure (Position : in Cursor));
+
+Iterate calls Process.all with a cursor that designates each element in 
+Container, starting with the first node and moving the cursor according to
+the 
+successor relation. Any exception raised by Process.all is propagated. 
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called.
+
+See Iterate for vectors for a suggested implementation of the check.
+End AARM Notes.
+
+
+MJH:
+
+I don't know how you expect to implement such a requirement.
+
+No, it's not good enough to modify the state of the container to
+indicate that iteration is in progress, since the container must work in
+the presence of multiple reader tasks.  (Mixing readers and writers is
+of course a no-no.)
+
+Get rid of the requirement for a check, and say that modifying the
+container (that is, changing its cardinality) during iteration is
+erroneous (or unspecified, or whatever).
+
+We already have a meta-rule that says behavior isn't specified if the
+container is simultaneously queried and modified.  This rule applies
+even if the reader and writer are the same task (as would be the case of
+deleting an element from the container while iteration is in progress).
+
+The best way to handle this "problem" is to use assertion checks (or
+perhaps some kind of preprocessor) that can be controlled by the user.
+The assertions can use knowledge of the representation of the internal
+storage node and the characteristics of the storage pool.  For example,
+here's a set of assertions that detect an attempt to delete a node that
+has already been deleted:
+
+      pragma Assert (Tree.Length > 0);
+      pragma Assert (Tree.Root /= Null_Node);
+      pragma Assert (Tree.First /= Null_Node);
+      pragma Assert (Tree.Last /= Null_Node);
+      pragma Assert (Parent (Tree.Root) = Null_Node);
+      pragma Assert ((Tree.Length > 1)
+                        or else (Tree.First = Tree.Last
+                                   and then Tree.First = Tree.Root));
+      pragma Assert ((Left (Node) = Null_Node)
+                        or else (Parent (Left (Node)) = Node));
+      pragma Assert ((Right (Node) = Null_Node)
+                        or else (Parent (Right (Node)) = Node));
+      pragma Assert (((Parent (Node) = Null_Node) and then (Tree.Root =
+Node))
+                        or else ((Parent (Node) /= Null_Node) and then
+                                  ((Left (Parent (Node)) = Node)
+                                     or else (Right (Parent (Node)) =
+Node))));
+
+
+See Delete_Node_Sans_Free in a-crbtgo.adb.  Similar checks immediately
+following the call to Process by Iterate should be adequate to detect
+most problems.
+
+ENDMJH.
+
+...
+
+procedure Replace (Container : in out Set;
+                   Key       : in     Key_Type;
+                   New_Item  : in     Element_Type);
+
+Equivalent to Replace (Container, Find (Container, Key), New_Item).
+
+MJH:
+
+This is a useless operation, and it should be removed from this API.
+
+I'll include my analysis in my review of the post-Madison final draft.
+[MJH -- See my earlier comments.]
+
+Note also that the the cursor-based Replace operation by which this
+key-based replace is implemented hasn't been mentioned anywhere above.
+
+ENDMJH.
+
+...
+
+A.17.7 The Package Containers.Hashed_Sets
+
+Static Semantics
+
+The package Containers.Hashed_Sets has the following declaration:
+
+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;
+
+MJH:
+
+We have already discussed the fact that you need to pass elem_t "=" too,
+in order to implement set container "=".
+
+We have also discussed the fact that I think the equivalence function
+should be named Equivalent_Keys, not Equivalent_Elements.
+
+ENDMJH.
+
+...
+
+   function Equivalent_Elements (Left, Right : Cursor)
+     return Boolean;
+
+   function Equivalent_Elements (Left  : Cursor;
+                                 Right : Element_Type)
+    return Boolean;
+
+   function Equivalent_Elements (Left  : Element_Type;
+                                 Right : Cursor)
+    return Boolean;
+
+MJH:
+
+See my comment above.  These should all be named Equivalent_Keys.
+
+The model is that an element is either a composite type with a key-part
+component; or, the element doesn't have a key-part, meaning that the
+element is all-key.  But in either case there is a key, even if the
+"key" is the element itself.
+
+(Another argument is that a set is basically the same as a map -- the
+only difference is where the key lives.  You should be able to switch
+between a set and a map without too much pain, and having the set use
+the name Equivalent_Element while the map uses Equivalent_Keys is a
+gratuitous difference.)
+
+ENDMJH.
+
+...
+
+   generic
+
+      type Key_Type (<>) is limited private;
+
+      with function Key (Element : in Element_Type) return Key_Type;
+
+      with function Hash (Key : Key_Type) return Hash_Type;
+
+      with function Equivalent (Left : Key_Type; Right : Element_Type)
+                                return Boolean;
+
+MJH:
+
+Now you have changed this too!  It should be named Equivalent_Keys.  The
+whole point of this nested package is to allow key-based set
+manipulation for (composite) element types that have a key-part.
+
+ENDMJH.
+
+
+   package Generic_Keys is
+
+...
+      procedure Replace (Container : in out Set;
+                         Key       : in     Key_Type;
+                         New_Item  : in     Element_Type);
+
+MJH:
+
+See my comments above.  This operation should be removed from this API.
+
+ENDMJH.
+
+...
+
+      function Equivalent_Keys (Left  : Cursor;
+                                Right : Key_Type)
+        return Boolean;
+
+      function Equivalent_Keys (Left  : Key_Type;
+                                Right : Cursor)
+        return Boolean;
+
+MJH:
+
+Here's all the proof you need that the formal operation should be named
+Equivalent_Keys, too.
+
+ENDMJH.
+
+
+   end Generic_Keys;
+
+private
+
+   ... -- not specified by the language
+
+end Ada.Containers.Hashed_Sets;
+
+...
+
+procedure Iterate
+   (Container : in Set;
+    Process : not null access procedure (Position : in Cursor));
+
+In addition to the semantics described in A.17.6, Program_Error is
+propagated if 
+Process.all calls Reserve_Capacity.
+
+MJH:
+
+See my earlier comments, about the fact that this requirement is
+unnecessary, and unimplementable.
+
+We already have a meta-rule that says the container cannot be read-from
+and written-to simultaneously.  The rule applies whether this is one
+task or more than one task.
+
+In this particular case, you can detect whether a node has been moved
+(as a result of rehashing) like this:
+
+  for I in Container.Buckets'Length loop
+     ...
+     Process (Cursor'(Container'UC, Node));
+     pragma Assert (Hash (Node.Element) mod Bucket'Len = I);
+     ...
+  end loop;  
+
+ENDMJH.
+
+...
+
+function Equivalent_Keys (Left  : Cursor;
+                          Right : Key_Type) return Boolean;
+
+Equivalent to Equivalent_Keys (Key (Left), Right).
+
+function Equivalent_Keys (Left  : Key_Type;
+                          Right : Cursor) return Boolean;
+
+Equivalent to Equivalent_Keys (Left, Key (Right)).
+
+
+MJH:
+
+This is inconsistent with the name for the generic formal function.
+
+ENDMJH.
+
+...
+
+A.17.8 The Package Containers.Ordered_Sets
+
+Static Semantics
+
+The package Containers.Ordered_Sets has the following declaration:
+
+generic
+
+...
+
+package Ada.Containers.Ordered_Sets is
+
+...
+
+   generic
+
+...
+
+   package Generic_Keys is
+
+...
+
+       procedure Replace (Container : in out Set;
+                          Key       : in     Key_Type;
+                          New_Item  : in     Element_Type);
+
+MJH:
+
+I have already stated this Replace operation should be removed from this
+API.
+
+ENDMJH.
+
+...
+
+   end Generic_Keys;
+
+private
+
+   ... -- not specified by the language
+
+end Ada.Containers.Ordered_Sets;
+
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, October 27, 2004  10:58 PM
+
+I'm going to only answer a few of these points, because my opinions are
+already noted in the AI and the attached e-mail.
+
+But several of the things Matt says are completely new and for the most
+part, wrong, and they need to be addressed.
+
+I'm going to answer this in several smaller messages so that we can make
+reasonable threads.
+
+...
+> A.17 Containers
+>
+> ...
+>
+> Note that the language already includes several requirements that are
+> important to the use of containers. First, library packages must be
+> reentrant - multiple tasks can use the packages as long as they operate on
+> separate containers. Thus, it is only necessary for a user to protect a
+> container if a single container needs to be used by multiple tasks.
+>
+>
+> MJH:
+>
+> We need to be clear here about multithreading issues, since that last
+> sentence is wrong.
+
+No, the last sentence exactly matches the language of A(3). And this
+paragraph has been here forever, as has A(3).
+
+> The only problem case is when there are multiple writers, or a single
+> writer and one or more readers.  (The reader and writer can also be the
+> same task.)
+>
+> It is definitely *not* an error for multiple readers to access the same
+> container all simultaneously.
+
+Yes it is, because it violates A(3).
+
+> In particular, it is perfectly acceptable (in fact, the API is designed
+> to facilitate this) for multiple tasks to be iterating over a same
+> container object, using either cursors or the passive iterator.
+
+Maybe, but it violates A(3).
+
+I would be very opposed to trying to repeal A(3) for these packages. There's
+a number of reasons for that:
+
+  1) It would be different than all other Ada-defined packages. That would
+add to user confusion.
+  2) It would prevent implementations from doing any sort of modifications
+on reading. For instance, the common technique of making most recently
+referenced elements to be more accessible in a hash table couldn't be used.
+Nor could caches or reference counts. We had similar restrictions in some
+operations in Claw, and it proved to be very constraining.
+  3) It would require a lot of wording to implement. We'd have to define
+precisely which operations are reading and which are writing; that would be
+complex to do.
+  4) It would make it far more likely for users to try to access containers
+from multiple tasks and would lead to errors. For instance, your proposed
+semantics wouldn't allow one task to write a container and another to read
+it, but it's likely that users would try to do so.
+
+The current rule is quite simple: if you want to use multiple tasks on a
+single container (or any other entity of a predefined type), wrap it in a
+protected object. Any other rule is going to be far more complex, both to
+use and to understand.
+
+We've always expected that a secondary standard would consider task-safe
+"protected" containers. But the locking needed for that is quite expensive,
+and it certainly shouldn't be mandated.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, October 27, 2004 11:58 PM
+
+Another response to Matt's review:
+
+> procedure Iterate
+>    (Container : in List;
+>     Process : not null access procedure (Position : in Cursor));
+>
+> Invokes Process.all with a cursor that designates each node in Container.
+> Any
+> exceptions raised during Process are propagated.
+> Program_Error is propagated if:
+>  * Process.all attempts to insert or delete elements from Container; or
+>  * Process.all calls a routine that reorders the elements of Container
+>    (Swap_Links, Splice, Generic_Sort, or Generic_Merge); or
+>  * Process.all finalizes Container; or
+>  * Process.all calls Move with Container as a parameter.
+>
+> AARM Note:
+> This check takes place when the operations that insert or delete elements,
+> etc.
+> are called. There is no check needed if an attempt is made to insert or
+> delete
+> nothing (that is, Count = 0).
+>
+> See Iterate for vectors for a suggested implementation of the check.
+>
+> Swap is not included here, as it only copies elements.
+> End AARM Notes.
+>
+>
+> MJH:
+>
+> This requirement is redundant, since we already have a meta-rule that
+> says container behavior isn't specified if the container object is
+> simultaneously read from and written to. This rule applies even if it's
+> the same task doing the reading and writing (as would be the case when a
+> container is modified during passive iteration).
+
+There is no such rule that I know of. A(3) of course covers it for multiple
+tasks, but for a single task, the only rules are the ones I just added to
+Query_Element, Update_Element, and Iterate.
+
+Moreover, such a rule would require careful definition of exactly which
+operations are reading and which are writing. (You can't assume that that is
+"obvious" in the Standard!) There certainly is nothing that complex in the
+current AI. (BTW, please refer to AIs by the version numbers when writing
+public messages, so that future readers can easily find out what is meant --
+"post-Madison" won't mean anything to anyone in six months.)
+
+> Note that the suggested implementation of the check doesn't work when
+> there are multiple reader tasks.  A container must support simultaneous
+> reading by multiple tasks.
+
+A(3) only requires that multiple tasks work for disjoint objects. I'm very
+opposed to going further (see my other note).
+
+Since virtually everything that Matt has to say is based on the two above
+fallicies, I'll just reiterate the important points:
+
+The Ada philosophy is that unspecified (resp. erroneous execution and
+bounded error) behavior is bad. Even if there was a "meta-rule" (whatever
+that is), it would be a bad thing. We only allow less than completely
+specified behavior when it is too expensive to check.
+
+If we do allow less than completely specified behavior, we try to specify it
+as tightly as possible. (That is a bounded error if we can.) We don't rely
+on "meta-rules" that say anything goes; that's for the C and C++ folks.
+
+In this case, we want to define what the passive iterator does in all cases.
+That helps code be portable and safe. The only real advantage of the passive
+iterator is that it is safe -- you'll only get valid cursors from it, and
+you'll get each one exactly once, and so on.
+
+If we don't protect against deletion of elements, there is no chance for the
+iterator to be implemented safely (certainly not if you use one node per
+element, as is likely for most of the containers, like lists and maps).
+Indeed, it would be hard for it to be implemented without being erroneous in
+some case, as Matt gives examples to describe. I find "erroneous" to be
+completely unacceptable for the passive iterator. It should *never* give the
+Process routine a dangling pointer or run over random memory. If it can do
+that, we shouldn't have it at all, because it them offers nothing at all
+over the active case (it's harder to use, and *less* safe?).
+
+I tried to define this as a bounded error, with it being unspecified what
+cursors are returned, but Matt convinced me that that was too hard to
+implement, and that Insert and Delete in a passive iterator is a mistake
+anyway. Fine; then simply checking that these don't happen is the better
+option.
+
+In any case, we should err on the side of safe and predictable. The
+containers have far too much "unspecified" behavior for my taste already.
+(I'd prefer checks on Query_Element and Update_Element, but these would have
+some space overhead on every element, which might be too much - which is why
+I didn't write them in.)
+
+Matt seems to have little interest in portable, predicable behavior. I don't
+understand that, unless he thinks everyone is going to use his
+implementations anyway (so it doesn't matter what the standard says). I can
+say with certainty that that will not be the case; the standard has to
+provide the predictability.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, October 28, 2004 12:03 AM
+
+Another response to Matt:
+
+> ...
+>    procedure Replace_Element (Position : in Cursor;
+>                               By       : in Element_Type);
+> ...
+>    procedure Replace (Container : in out Map;
+>                       Key       : in     Key_Type;
+>                       New_Item  : in     Element_Type);
+>
+> MJH:
+>
+> The introduction of a new set operation has alerted me to the fact that
+> we have two operations similarly named.  (See the set spec for more
+> comments.)
+>
+> So far we have named the cursor-based replace operation
+> "Replace_Element" and its element parameter "By" (this came from
+> Ada.Strings.*), and named the key-based replace operation "Replace" and
+> its element parameter "New_Item".
+>
+> The ARG should confirm whether this difference in naming of the
+> cursor-based vs. key-based replace operations is intended.
+
+Yes, it's intentional. Replace_Element only replaces the element (duh!) but
+Replace replaces both the element and the key. If you called it
+Replace_Element, it shouldn't replace the key, which would violate the
+semantics that we agreed on in Madison.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, October 28, 2004 12:27 AM
+
+> ...
+>
+>    procedure Replace (Container : in out Set;
+>                       New_Item  : in     Element_Type);
+> ...
+>
+>    procedure Replace (Container : in Set;
+>                       Position  : in Cursor;
+>                       By        : in Element_Type);
+>
+> MJH:
+>
+> This new cursor-based replace operation for sets is named in a manner
+> inconsistent with the rest of this API.  It should be named
+> Replace_Element.  (Note that the element parameter is named By, not
+> New_Item.  The parameter name By is always used as the element parameter
+> of the cursor-based operation named Replace_Element.)
+>
+> ENDMJH.
+
+I think I agree with that; I was trying to draw a parallel with the Maps,
+but that only applies to the Generic_Keys package, not the root container.
+
+> ...
+>
+>    generic
+> ...
+>    package Generic_Keys is
+>
+> ...
+>        procedure Replace (Container : in out Set;
+>                           Key       : in     Key_Type;
+>                           New_Item  : in     Element_Type);
+>
+> MJH:
+>
+> This operation needs to be removed from this API.
+...
+(followed by a lot of irrelevant discussion)
+> The bottom line is that Generic_Keys.Replace must be removed from this
+> API.  It provides no new functionality, and only adds unnecessary
+> clutter.
+
+For someone who is always proposing unnecessary operations, this is quite a
+stretch! I don't understand why you feel so strongly about this operation.
+
+Certainly, this isn't the most useful routine, except in one case: when a
+project decides to move from a Map to a Set representation.
+
+One of the most important criteria for the containers, I think, is that it
+be (relatively) easy to move between related containers as needs change.
+Certainly changing from an ordered to a hashed map should be simple. But I
+think this also applies to changing the location of the key. One of the most
+valuable uses of containers is in prototypes, and one of the most obvious
+properties of a prototype is that it is likely to change.
+
+It's not unreasonable that a project would find the need to include the key
+in the element at some point during development. Such a change shouldn't
+require wholesale rewriting of the application; and that is especially true
+for those of us who are use-adverse and will not use a use-clause. (If a
+library requires the use of use-clauses, it doesn't belong in the standard.
+Period.)
+
+Therefore, it should be the case that as many operations as possible from
+the Map be available in the Set, and in particular in the Generic_Keys
+(since that is the direct counterpart of the Map). Forcing half the
+operations to be rewritten or moved is simply not acceptable.
+
+Thus, the Replace operation is declared here simply because a similar
+operation is declared in the Maps. I would have preferred to declare an
+Insert and Include as well, but these require goofy checks that the key is
+compatible with the element. Note that I would not expect any of these
+operations to be used in new (hand-written) code; they'd only be used when a
+Map is converted into a Set. So the fact that their semantics is a little
+weird is irrelevant -- they're simply an aid for changing between
+containers.
+
+Matt seems to expect that rewriting a large percentage of the calls when
+making such a change is acceptable. I don't think that is true, unless you
+think that moving a key from a separate entity to a component is going to be
+rare (I certainly don't believe that).
+
+Anyway, I want Generic_Keys to be as similar as possible to Maps (and
+indeed, our style guide will recommend avoiding operations that are not
+common, like Update_Element - even if it is renamed, it won't have the same
+parameter list or semantics). That means that there will be a few operations
+with odd semantics. So be it.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent