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

Differences between 1.6 and version 1.7
Log of other versions for file ai05s/ai05-0212-1.txt

--- 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