--- ai05s/ai05-0212-1.txt 2011/03/09 00:46:29 1.6 +++ ai05s/ai05-0212-1.txt 2011/03/10 03:26:30 1.7 @@ -355,8 +355,8 @@ For each bounded container, delete AARM implementation note that says: -Package Containers.Bounded_Vectors cannot depend on package Ada.Finalization (because that package has -Preelaborate categorization). +Package Containers.Bounded_Vectors cannot depend on package Ada.Finalization (because that +package has Preelaborate categorization). Add an AARM note after the bullet about when the container needs finalization: @@ -370,105 +370,120 @@ A.18.33 Example of container use -The following example using the containers to calculate the shortest paths -between each pair of nodes in a set. +The following example is an implementation of Dijkstra's shortest path algorithm in +a directed graph with positive distances. The graph is represented by a map from nodes +to sets of edges. + +with Ada.Containers.Hashed_Sets; with Ada.Containers.Vectors; +with Ada.Containers.Doubly_Linked_Lists; +use Ada.Containers; +generic + type Node is range <>; +package Shortest_Paths is + type Distance is new Float range 0.0 .. Float'Last; + type Edge is record + To, From : Node; + Length : Distance; + end record; + + package Node_Sets is new Vectors (Node, Boolean); + -- A set of nodes is a boolean vector. + + package Node_Maps is new Vectors (Node, Node); + -- The algorithm builds a map to indicate the node used to reach a given + -- node in the shortest distance. + + package Adjacency_Lists is new Doubly_Linked_Lists (Edge); + use Adjacency_Lists; + + package Graphs is new Vectors (Node, Adjacency_Lists.List); + + package Paths is new Doubly_Linked_Lists (Node); + + package Distances is new Vectors (Node, Distance); + -- The algorithm keeps a map from node to the shortest distance found so + -- far to that node. + + function Shortest_Path + (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List; +end Shortest_Paths; + +package body Shortest_Paths is + function Shortest_Path + (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List + is + use Adjacency_Lists, Node_Sets, Node_Maps, Paths, Distances, Graphs; + + Reached : Node_Sets.Vector; + -- The set of nodes whose shortest distance to the source is known. + + Reached_From : Node_Maps.Vector; + So_Far : Distances.Vector; + The_Path : Paths.List := Paths.Empty_List; + Nearest : Node; + Nearest_Distance : Distance; + Next : Node; + begin + Reserve_Capacity (So_Far, Length (G)); + Reserve_Capacity (Reached, Length (G)); + + -- Initially all nodes are unreachable. The set of nodes is given by + -- the domain of the graph G. + + for N in G.Iterate loop + So_Far (N) := Distance'Last; + Reached (N) := False; + end loop; + + Reached (Source) := True; + + while not Reached (Target) loop + Nearest_Distance := Distance'Last; + + -- Find closest node not reached yet, by iterating over all nodes. + -- A more efficient algorithm uses a priority queue for this step. + + for N in G.Iterate loop + if not Reached (N) + and then So_Far (N) < Nearest_Distance then + Next := N; + Nearest_Distance := So_Far (N); + end if; + end loop; + + Reached (Next) := True; + + -- Update minimum distance to other nodes, by iterating over the + -- adjacency list of the newly reached node. + + for E of G (Next) loop + if not Reached (E.To) then + Nearest_Distance := + Distance'Min (So_Far (E.To) + So_Far (Nearest), So_Far (E.To)); + + if Nearest_Distance < So_Far (E.To) then + Reached_From (E.To) := Next; + So_Far (E.To) := Nearest_Distance; + end if; + end if; + end loop; + end loop; + + -- Rebuild path from target to source. + + declare + N : Node := Target; + begin + while N /= Source loop + N := Reached_From (N); + Prepend (The_Path, N); + end loop; + end; + + return The_Path; + end; +end Shortest_Paths; -with Ada.Containers.Hashed_Sets; with Ada.Containers.Vectors; -with Ada.Containers.Doubly_Linked_Lists; -use Ada.Containers; -generic - type Node is range <>; -package Shortest_Paths is - type Distance is new Float range 0.0 .. Float'Last; - type Edge is record - To, From : Node; - Length : Distance; - end record; - - package Node_Sets is new Vectors (Node, Boolean); - package Node_Maps is new Vectors (Node, Node); - - package Adjacency_Lists is new Doubly_Linked_Lists (Edge); - use Adjacency_Lists; - - package Graphs is new Vectors (Node, Adjacency_Lists.List); - - package Paths is new Doubly_Linked_Lists (Node); - - package Distances is new Vectors (Node, Distance); - - function Shortest_Path - (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List; -end Shortest_Paths; - -package body Shortest_Paths is - function Shortest_Path - (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List - is - use Node_Sets, Node_Maps, Paths, Distances, Graphs; - Reached : Node_Sets.Vector; - Reached_From : Node_Maps.Vector; - So_Far : Distances.Vector; - The_Path : Paths.List := Paths.Empty_List; - Nearest : Node; - Nearest_Distance : Distance; - Next : Node; - begin - Reserve_Capacity (So_Far, Length (G)); - Reserve_Capacity (Reached, Length (G)); - - -- Initially all nodes are unreachable. - for N in G.Iterate loop - So_Far (N) := Distance'Last; - Reached (N) := False; - end loop; - - Reached (Source) := True; - - while not Reached (Target) loop - Nearest_Distance := Distance'Last; - - -- Find closest node not reached yet. - - for N in G.Iterate loop - if not Reached (N) - and then So_Far (N) < Nearest_Distance then - Next := N; - Nearest_Distance := So_Far (N); - end if; - end loop; - - Reached (Next) := True; - - -- Update minimum distance to newly reachable nodes. - - for E of G (Next) loop - if not Reached (E.To) then - Nearest_Distance := - Distance'Min (So_Far (E.To) + So_Far (Nearest), So_Far (E.To)); - - if Nearest_Distance < So_Far (E.To) then - Reached_From (E.To) := Next; - So_Far (E.To) := Nearest_Distance; - end if; - end if; - end loop; - end loop; - - -- Rebuild path from target to source. - - declare - N : Node := Target; - begin - while N /= Source loop - N := Reached_From (N); - Prepend (The_Path, N); - end loop; - end; - return The_Path; - end; -end Shortest_Paths; - Note that the effect of the Variable_Indexing aspect (on type Vector) and the Implicit_Dereference aspect (on type Reference_Type) is that @@ -1087,7 +1102,8 @@ > > This would also require a bit more care with the definition of the two > cases. In particular, for "in out" parameter passing by-copy, you -> would have to use Constant_Indexing on the way in and Variable_Indexing on the way out. +> would have to use Constant_Indexing on the way in and Variable_Indexing on the +> way out. > > The only unusual thing is that S(N) would not be the name of an object > (rather the name of a value), so it couldn't be renamed. @@ -1291,7 +1307,10 @@ From: Randy Brukardt Sent: Thursday, February 10, 2011 1:28 PM -You both (maybe intentionally) missed my point. I'll use the renames here if there are more than one or two uses of "To_Unbounded_String". This is the same conditions under which I would consider using a use clause. So this sort of thing only shows up in the "rare usage" scenario. +You both (maybe intentionally) missed my point. I'll use the renames here if +there are more than one or two uses of "To_Unbounded_String". This is the same +conditions under which I would consider using a use clause. So this sort of +thing only shows up in the "rare usage" scenario. In any case, I don't find: @@ -1330,6 +1349,150 @@ "use" clauses more often. Unfortunately, that doesn't help Ada.Strings.Unbounded much -- as previously noted, I think To_Unbounded_String is ridiculous with or without a use clause. + +**************************************************************** + +From: Randy Brukardt +Sent: Tuesday, March 8, 2011 5:21 PM + +My notes for the last meeting has: + +Randy asks about the change from Pure to Preelaborate. Tucker wonders if we +could just change Controlled to Pure (also dropping Remote_Types). No one can +think of a real problem with that. There is "state" involved, but that state is +managed solely by the implementation (not by the user), and there is no way to +depend upon it. (A Pure Finalize routine could not depend on global variables, +which might be harder to write, but tough.) + +I've been pondering this change, because I was unconvinced that there wouldn't +be a problem. I've now convinced myself that there can be no problem with this +change, and I wanted to record the reasons behind that. (And if someone knows +different, please speak up now!) + +One topic that we touched on briefly at the meeting (but didn't get recorded) is +the issue of distribution. Pure packages imply that types declared within them +can be used as remote types. That cannot cause a (new) problem in this case, as +package Finalization already has the Remote_Types categorization. So there is +nothing to worry about there. + +The main thing that concerned me is that a constant controlled object does not +need to act as a constant, as a writable version is provided to the +Initialize/Adjust/Finalize routines. The wording changes of AI05-0054-2 stress +this fact. This matters because Pure disallows library-level variables; but in +general, constant controlled objects work the same as a variable. + +For instance, we would have trouble if a constant object of a type like the +following could be declared at the library-level in a Pure package: + + type Ouch is new Ada.Finalization.Controlled with record + Self : access Ouch; + end record; + + procedure Initialize (Obj : in out Ouch) is + begin + Obj.Self := Obj'Access; + end; + +The assignment creates a variable reference to the object itself and saves it +within the object. Later routines could then use this variable reference to +modify the object -- thus creating state. This is trouble because it could +happen in some inner call, not necessarily within Initialize itself. + +Luckily, Pure packages also have to be preelaborable. A constant object declared +at the library-level of a Pure package also has to have Preelaborable +Initialization (PI). And a type with a non-null Initialize routine is defined to +not have PI. + +However, constants have to be initialized, so Initialize isn't likely to be +called anyway. But we could create the same problem with Adjust. That is, if we +could declare an object: + Owww : constant Ouch := <???>; +such that Adjust is called, we would have the same problem. + +[Aside channelling Steve: Note that the preelaboration rules might in fact make +this illegal simply because of the call to Adjust (which is clearly a +subprogram). This illustrates the rather nasty nature of the preelaboration +rules, in that they require the compiler to predict the future. (Steve has noted +this problem in the past.) Note that 10.2.1(5) says "unless its elaboration +performs any of the following actions:". But that is a dynamic semantics action +which cannot be completely predicted at compile-time. It also mixes dynamic +rules (which are typically privacy breaking) with legality rules (which are +typically not privacy breaking). I have to wonder whether: + + C : constant Integer := (if True then 1 else Some_Function(Some_Object)); + +is preelaborable. Reading the letter of the wording, it would appear that it is +preelaborable (the elaboration of C will not call Some_Function nor evaluate the +name of Some_Object). Do we really want this?? Do we want it if True is replaced +by some static expression? Should preelaborability depend on values elsewhere in +the program? Enquiring minds don't really want to know. ;-) + +Anyway, we'll skip whether this rule applies because it doesn't matter.] + +However, for this to happen, we have to write something to replace <???> which +is both allowed by preelaboration and which would force a call to Adjust. If +<???> is replaced by an aggregate, no call to Adjust is made. The only other +possibilities for a tagged type are an object or a function call, and these are +illegal by 10.2.1(8) and 10.2.1(7), respectively. + +Thus, we can't create a writable reference via Adjust. + +We probably can create such a reference via Finalize, but that is too late to be +interesting (it's hard to imagine how that could be used to create library-level +state during the normal execution of the package). + +Thus, I conclude that a constant controlled object used in a Pure package acts +as a constant through its entire life until Finalize is called. + +(There probably is a similar issue involving immutably limited types; but since +that isn't new I'm not going to analyze it, and in any case, it doesn't hide +inside of subprograms.) + +---- + +One additional issue is whether this adds any difficulties in using or +implementing the container Reference and Iterator types. + +On usability: + +Neither of these types will have PI, so these objects cannot be used at library +level in Pure or Preelaborable packages. But that is OK, as we don't want +default-initialized stand-alone objects of these types in the first place, and +initialized ones will be illegal because of the function call needed to get the +values. + +This implies that container dereferencing and indexing will not be available at +library-level in such packages. But that is OK, because any library-level +container necessarily has to be empty (can't execute the procedure calls to put +anything into it). So there ought not be any such references. + +On implementability: + +The Reference object typically will contain a pointer to the container and the +discriminant that points at the element. Initialize will raise Program_Error (we +don't want default-initialized Reference objects), and Finalize will reset the +tampering bit in the container. None of this requires any package-level objects. + +The Iterator object typically will contain a pointer to the container and a +cursor for a position within the container. The routines to call are determined +by the interface, so calls are made with dispatching calls. No package-level +objects appear to be needed. + +In summary, I don't think there is a problem with this. + +---- + +One tiny aside: the AARM note about the bounded forms says: + +Implementation Note: Package Containers.Bounded_Vectors cannot depend on package +Ada.Finalization (because that package has Preelaborate categorization). + +This note is still wrong and still needs to be removed (as noted in the AI). The +reason is different, but the effect is the same. + +The AARM note that I added after the "needs finalization" bullet still is needed +as well (to note that the Vector type cannot itself be controlled if the element +type does not have a controlled part). ****************************************************************

Questions? Ask the ACAA Technical Agent