CVS difference for 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