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

Differences between 1.13 and version 1.14
Log of other versions for file ai05s/ai05-0111-1.txt

--- ai05s/ai05-0111-1.txt	2010/02/25 05:01:42	1.13
+++ ai05s/ai05-0111-1.txt	2010/05/20 02:45:15	1.14
@@ -1,4 +1,4 @@
-!standard  4.8(2)                                   10-02-23    AI05-0111-1/08
+!standard  4.8(2)                                   10-05-17    AI05-0111-1/09
 !standard  4.8(3/2)
 !standard  4.8(10.1/3)
 !standard 13.11(16/3)
@@ -220,7 +220,7 @@
          -- This is a reference-counted handle on an underlying
          -- subpool descriptor (see Subpools.Implementation)
 
-       function Create_Subpool(Manager : access Root_Subpool_Manager;
+       function Create_Subpool(Manager : [access]{aliased in out} Root_Subpool_Manager;
          Storage_Size : Storage_Elements.Storage_Count :=
            Storage_Elements.Storage_Count'Last) return Subpool_Handle is abstract;
            -- Create subpool within given subpool manager.  Storage_Size
@@ -248,7 +248,7 @@
          --       track of the subpool from which an object was allocated.
 
        procedure Allow_Reference(From : Subpool_Handle; To : Subpool_Handle)
-         with Pre => Manager(From) = Manager(To);
+         with Pre => Manager(From) = Manager(To), Post => Is_Reachable(From, To);
            -- Allow pointers in "From" subpool to safely designate objects
            -- in "To" subpool, by ensuring that the "To" subpool is not
            -- reclaimed prior to reclaiming the "From" subpool.
@@ -283,8 +283,6 @@
          -- Indicates whether the given subpool is the initial subpool for
          -- its subpool manager.
 
-   end System.Subpools;
-
   private
     ... -- not specified by the language
 
@@ -324,9 +322,11 @@
 finalized* (see below), its finalization proceeds by completing any
 tasks dependent on the subpool's master that are waiting at an open
 terminate alternative, waiting for their termination, and then
-finalizing all of the objects allocated from the subpool.  After a
-subpool has been finalized, any storage allocated for objects in the
-subpool can be reclaimed.
+finalizing any of the objects allocated from the subpool that still
+exist.  After a subpool has been finalized, any storage allocated for
+objects in the subpool can be reclaimed.
+
+The type Subpool_Handle needs finalization.
 
 13.11.5 Subpool Reclamation
 
@@ -334,19 +334,19 @@
 
    with Ada.References;
    generic
-       type Desig(<>) is limited private;
-       type Acc is access Desig;
+       type Object(<>) is limited private;
+       type Name is access Object;
    package System.Subpools.References is
        -- This generic package provides strong and weak references
        -- to objects in subpools, which can safely be assigned and
        -- reassigned without requiring any reachability checks.
 
-       pragma Assert(Acc'Storage_Pool in Root_Subpool_Manager'Class);
+       pragma Assert(Name'Storage_Pool in Root_Subpool_Manager'Class);
          -- This package is only defined for access types whose storage
          -- pool is of a type descended from Root_Subpool_Manager.
 
-       function Enclosing_Subpool(Object : not null Desig) return Subpool_Handle;
-         -- Return subpool from which object designated by Object was
+       function Enclosing_Subpool(Obj : not null Name) return Subpool_Handle;
+         -- Return subpool from which object designated by Obj was
          -- allocated.
          -- NOTE: This calls the Enclosing_Subpool function in System.Subpools.
 
@@ -356,7 +356,7 @@
          -- the associated subpool from being reclaimed.
        Null_Strong_Reference : constant Strong_Reference;
 
-       function New_Strong_Reference(Object : Desig) return Strong_Reference;
+       function New_Strong_Reference(Object : Name) return Strong_Reference;
            -- Create a strong reference to the given object which
            -- will prevent premature reclamation of its enclosing subpool.
 
@@ -364,7 +364,7 @@
        function Is_Null(Ref : Strong_Reference) return Boolean;
          -- Return True if pointer within Strong_Reference is null.
 
-       type Object_Ref(Object : not null access Desig) is
+       type Object_Ref(Obj : not null access Object) is
          new Ada.References.Reference with limited private;
            -- This uses the "magic" interface to provide
            -- implicit dereference of the result.
@@ -377,32 +377,19 @@
          -- Return a reference to the object identified by the
          -- Strong_Reference.
 
-       type Weak_Reference is private;
-         -- A weak reference to an object allocated from a subpool.  The
-         -- reference is "weak" in that the associated subpool might be reclaimed
-         -- if the storage is needed.  This is determined by converting
-         -- the weak reference to a strong reference, and then
-         -- checking whether it is null.
-       function New_Weak_Reference(Object : Desig) return Weak_Reference;
-           -- Create a weak reference to an object allocated
-           -- from a subpool.
-
-       function To_Strong_Reference(Ref : Weak_Reference) return Strong_Reference;
-         -- To use a weak reference, it must first be converted
-         -- into a strong reference.
-
    end System.Subpools.References;
 
+
 Subpools are automatically finalized and reclaimed when it is safe to do so.
-Subpool handles (see 13.11.4), as well as the *strong references* and *weak
-references* defined in the above generic package, are used to prevent premature
-reclamation, based on a *reachability* relationship. If an object of type
-Subpool_Handle is part of an object elaborated within a (construct) master, the
-subpool identified by the handle is *reachable from* that master. A subpool is
-*reachable from* a master for a subpool if it is reachable from the associated
-subpool, as a result of calls on Allow_Reference. A subpool is *reachable from*
-a strong or weak reference if the subpool is reachable from the subpool
-associated with the reference. A subpool is *reachable from* itself.
+Subpool handles (see 13.11.4), as well as the *strong references* (defined
+above) are used to prevent premature reclamation, based on a *reachability*
+relationship. If an object of type Subpool_Handle is part of an object
+elaborated within a (construct) master, the subpool identified by the handle is
+*reachable from* that master. A subpool is *reachable from* a master for a
+subpool if it is reachable from the associated subpool, as a result of calls on
+Allow_Reference. A subpool is *reachable from* a strong reference if the subpool
+is reachable from the subpool associated with the reference. A subpool is
+*reachable from* itself.
 
 [Redundant: The *master of an object* is the innermost (construct)
 master that included the elaboration of the object, for an object that
@@ -414,13 +401,11 @@
 If a subpool is not reachable from any construct master, any strong
 references, nor any master for a subpool with one or more nonterminable
 tasks that depend on it, the given subpool is *ready to be finalized.*
-If a subpool is ready to be finalized, and is not reachable from any
-weak reference, it is immediately finalized. If a subpool is reachable
-from one or more weak references, but is otherwise ready to be finalized
-at the point when Allocate is called on the subpool manager or one of
-its subpools, the allocation procedure may finalize the weakly
-referenced subpool so as to reclaim storage prior to the new allocation.
+In the absence of *weak references* (see 13.11.8), once a subpool is
+ready to be finalized, it is immediately finalized.
 
+The type Strong_Reference needs finalization.
+
 13.11.6 Subpool Reachability Checks
 
 In an assignment operation, if the target is a variable of an access type whose
@@ -446,28 +431,31 @@
 a check is made that the type of the operand is a named access type
 that has the same storage pool.  Program_Error is raised if this check fails.
 
+The master is preserved when converting to an access parameter.
+[Editor: *** More details needed on conversion to an anon access type.]
+
 
-13.11.7 Subpool Implementation
+13.11.7 Subpool Descriptors
 
 The following language-defined package exists:
 
-   package System.Subpools.Implementation is
-       -- This package is used by implementations of subpool managers.
+   package System.Subpools.Descriptors is
+       -- This package is used to support the implementation of a subpool manager.
 
-       -- The sequence of events is that a call on Create_Subpool goes
-       -- to the subpool manager, it allocates a subpool descriptor,
+       -- A call on Create_Subpool goes to the subpool manager,
+       -- which allocates a subpool descriptor, and
        -- then calls New_Subpool_Handle to create a handle.
 
-       -- When a subpool is ready to be reclaimed, the underlying implementation
+       -- When a subpool is ready to be reclaimed, the Ada implementation
        -- waits for any tasks, finalizes the objects in the subpool, then
        -- calls Reclaim_Subpool_Storage.  Finally, it calls Deallocate
-       -- with the address of the subpool descriptor
+       -- with the address of the subpool descriptor.
 
        type Root_Subpool_Descriptor(
           Manager : not null access Root_Subpool_Manager'Class) is
              abstract tagged limited private;
          -- This type is used to represent a storage pool within a subpool manager.
-         -- The implementation uses this to represent the dynamic master.  It holds
+         -- The Ada implementation uses this to represent the master for the subpool.  It holds
          -- the reference count of handles, as well as the count of weak references.
          -- The subpool manager also uses some extension of this type to keep
          -- track of the actual storage associated with the subpool so it
@@ -475,7 +463,7 @@
 
        procedure Reclaim_Subpool_Storage(Subpool : access Root_Subpool_Descriptor)
          is abstract;
-           -- This is called by the implementation when the subpool is no longer
+           -- This is called by the Ada implementation when the subpool is no longer
            -- reachable from any non-terminable task, and the weak reference
            -- count is zero, or the Process procedure returns with Reclaim True.
 
@@ -483,6 +471,60 @@
          Subpool : access Root_Subpool_Descriptor'Class) return Subpool_Handle;
            -- Create a subpool handle given a descriptor of the subpool
 
+       procedure Iterate_Connected_Subpools(Subpool : access Root_Subpool_Descriptor'Class;
+         Process : access procedure (Connected_Subpool : access Root_Subpool_Descriptor'Class));
+           -- This iterates through the subpools that are strongly connected to the
+           -- given subpool, meaning that when Subpool is reclaimed, so will be
+           -- all of the connected subpools.  This can be used to determine
+           -- the total amount of storage that will be reclaimed if it is decided
+           -- to reclaim one of the subpools in the strongly-connected set.
+
+   end System.Subpools.Descriptors;
+
+Subpools are represented internally by objects of a type descended from
+Root_Subpool_Descriptor, which are allocated from the *initial* subpool
+of the subpool manager. The abstract operations on Root_Subpool_Manager
+and Root_Subpool_Descriptor are not provided by the Ada implementation. All
+other operations within System.Subpools, System.Subpools.References, and
+System.Subpools.Descriptors, are provided by the Ada implementation, for
+use in implementing overridings of the abstract operations.
+
+13.11.8 Weak References
+
+The following language-defined generic child package exists:
+
+    generic
+    package System.Subpools.References.Weak is
+
+       type Weak_Reference is private;
+         -- A weak reference to an object allocated from a subpool.  The
+         -- reference is "weak" in that the associated subpool might be reclaimed
+         -- if the storage is needed.  This is determined by converting
+         -- the weak reference to a strong reference, and then
+         -- checking whether it is null.
+
+       function New_Weak_Reference(Object : Name) return Weak_Reference;
+           -- Create a weak reference to an object allocated
+           -- from a subpool.
+
+       function To_Strong_Reference(Ref : Weak_Reference) return Strong_Reference;
+         -- To use a weak reference, it has to first be converted
+         -- into a strong reference.
+
+    end System.Subpools.References.Weak;
+
+A *weak reference* is a managed reference to an object allocated from a subpool.
+To use a weak reference it has to be converted into a strong reference.  Upon
+conversion, the strong reference will be null if the enclosing subpool was reclaimed
+prior to the conversion; otherwise it will designate the object designated by
+the access value passed to New_Weak_Reference.
+
+The type Weak_Reference needs finalization.
+
+The following language-defined package exists:
+
+    package System.Subpools.Descriptors.Weak is
+
        procedure Iterate_Reclaimable_Subpools(Manager : Root_Subpool_Manager'Class;
          Process : access procedure (Subpool : access Root_Subpool_Descriptor'Class;
          Weak_Reference_Count : Positive; Reclaim : out Boolean; Quit : out Boolean));
@@ -492,35 +534,25 @@
            -- The Weak_Reference_Count indicates how many weak references identify this
            -- subpool or some subpool strongly connected to it.  If upon return Reclaim is
            -- True, then the given subpool and all of its strongly connected
-           -- subpools will be reclaimed.  If Quit is True then the iteration
+           -- subpools will be finalized and reclaimed.  If Quit is True then the iteration
            -- will stop.
 
-       procedure Iterate_Connected_Subpools(Subpool : access Root_Subpool_Descriptor'Class;
-         Process : access procedure (Connected_Subpool : access Root_Subpool_Descriptor'Class));
-           -- This iterates through the subpools that are strongly connected to the
-           -- given subpool, meaning that when Subpool is reclaimed, so will be
-           -- all of the connected subpools.  This can be used to determine
-           -- the total amount of storage that will be reclaimed if it is decided
-           -- to reclaim one of the subpools in the strongly-connected set.
+    end System.Subpools.Implementation.Weak;
 
-   end System.Subpools.Implementation;
 
-Subpools are represented internally by objects of a type
-descended from Root_Subpool_Descriptor, which are allocated
-from the *initial* subpool of the subpool manager. The abstract
-operations on Root_Subpool_Manager and Root_Subpool_Descriptor
-are not provided by the implementation. All other operations
-within System.Subpools, System.Subpools.References, and
-System.Subpools.Implementation, are provided by the
-implementation, for use in implementing overridings of the
-abstract operations.
+If a subpool is reachable from one or more weak references, but is
+otherwise ready to be finalized (see 13.11.5 above), then at the point
+when Allocate or Allocate_From_Subpool is called on the subpool manager,
+the allocation procedure may specify that the subpool be finalized and
+reclaimed by returning from the Process procedure of
+Iterate_Reclaimable_Subpools with Reclaim having value True.
 
 
 !discussion
 
 There is a delicate "dance" here between code provided by the Ada
 implementation and code provided by the implementor of the subpool
-manager type. The compiler implementation is responsible for worrying
+manager type. The Ada implementation is responsible for worrying
 about reference counting, task dependence, finalization chains,
 reachability checks, weak references. Essentially everything having to
 do with avoiding dangling references. The implementor of the subpool
@@ -712,6 +744,8 @@
 
 !example
 
+{Show a real example.}
+
 As an example of the use of subpools, imagine a long-running web server
 for a retail establishment, which builds up in-memory representations of
 historical customer information, current product information, and each
@@ -5340,5 +5374,222 @@
 Anyway, we both ought to be doing our important homework for the meeting, and
 discussing this isn't helping. Talk to you Friday (weather and airlines
 permitting).
+
+****************************************************************
+
+From: Bob Duff
+Sent: Monday, May 17, 2010  2:55 PM
+
+Here's my last bit of homework, in preparation for the phone meeting this
+Thurday, May 20, at 3:00 PM EST.
+
+This is from the Minutes of Meeting #40:
+
+> Action item to everyone to look at this and see how (or if) they might
+> use it.
+
+OK, I've studied this stuff some more.
+
+If it existed, I would certainly use it sometimes.
+I'd use it whenever large numbers of objects can be grouped into those with
+similar lifetimes.  E.g. a giant hash table, where all the nodes go away when
+the hash table does.
+
+In fact, I've built the same sort of stuff myself, except without language
+support, it necessarily had some drawbacks:
+
+(1) Unsafe (possible dangling pointers), because there was no
+    check that when you copy an access value, the right subpool
+    is "reachable".
+
+(2) Unreadable, because there was no syntax for specifying the
+    subpool on the "new".  Instead, I had a global "current subpool"
+    variable, which had to be set up beforehand.  (Actually, a
+    stack of them, with limited-controlled types managing the
+    setup and teardown -- quite complicated.)
+
+(3) Task-unsafe, because of that global variable.
+
+(4) No support for allocating controlled objects or tasks
+    within a subpool (if you try, the runtime system gets
+    deeply confused).
+
+(5) It was technically wrong (relied on implementation-specific
+    behavior not guaranteed by the language).
+
+I would be pretty happy with a solution that solved just (2) and (3), which
+seems pretty easy (see the title of this AI!).  In the past, this suggestion has
+been shot down, saying "we can't have a new way of creating erroneous behavior"
+(i.e. (1) above).  I have never understood that argument.  If a new feature is
+unsafe, you have to look at what it replaces.  Unsafe subpools would replace
+some uses of Unchecked_Dealloc.  Unsafe subpools are unsafe, but they're still
+safer than Unchecked_Dealloc -- by far, in my experience.  So unsafe subpools
+would make Ada programs safer, on the whole.
+
+Support for unsafe subpools exists in C and C++, which is our competition if
+you're looking at the embedded world.  If a C++ programmer says "Ada can't do
+X", we can usually answer, "Oh, yes it can, you just have to do it in a more
+disciplined, safer way."  That's fine. But in this case, our current answer is,
+"Right, you can't do that in Ada, and we're not going to let you, because it's
+unsafe." That's not an acceptable answer to someone who needs to do X.
+
+Given the widespread use of unsafe subpools (AKA user-defined malloc, placement
+new, etc) in C and C++, I find the question posed in the minutes "see... if...
+they might use it" to be rather puzzling.
+
+Safe subpools, as proposed by this AI, prevent (1), which is very cool.
+On the other hand, there's a fair amount of implementation complexity for that.
+
+I can't get too excited about (4).  From a practical point of view, I'd be happy
+if allocating such "fancy" things raised an exception.  That's ugly of course --
+but that's a more theoretical point of view.  There's a huge implementation
+complexity in solving (4).
+
+I believe that a modern, efficient implementation of garbage collection would do
+far more to promote the use of Ada than this AI.  The !example, of a
+"long-running web server" seems appropriate for GC -- no hard real-time
+constraints, not safety critical, etc.  On the other hand, the implementation
+cost of this AI is far less than that of a really good GC.
+
+Summary: I have mixed feelings.  :-(
+
+****************************************************************
+
+From: Bob Duff
+Sent: Monday, May 17, 2010  3:11 PM
+
+> Action item to everyone to look at this and see how (or if) they might
+> use it.
+
+Anecdote: Last weekend, I was helping my son Bill who is writing an Ada program
+to do some text processing, involving reading (arbitrarily long) lines of text
+from input files, and grinding upon them in various ways.  This required fairly
+complicated data structures containing Strings and other stuff.
+
+Subpools (safe or unsafe) containing Strings would have come in very handy.
+We ended up using Unbounded_Strings, which works, but it's awfully heavy
+syntactically.  You end up either converting back and forth between String and
+Unbounded_String all over, or using calls to Element, Replace_Element, and the
+like instead of normal array indexing and the like.  A loop such as:
+
+    loop
+        create subpool;
+        process one file, doing "new String..." a lot;
+        destroy subpool;
+    end loop;
+
+would have made the code rather more readable, I think.
+And it's not too hard to make sure the subpool is destroyed at the right time to
+avoid dangling pointers.
+
+GC would have been another good solution.
+
+I suspect any of the three (safe subpools, unsafe subpools, or GC) would have
+been more efficient than all that string copying we ended up doing.   (E.g. what
+do you do when you want to rename a slice of an Unbounded_String?!)
+
+****************************************************************
+
+From: Bob Duff
+Sent: Monday, May 17, 2010  3:18 PM
+
+> Anecdote: Last weekend, I was helping my son Bill who is writing
+
+For a good time, google "the plural of anecdote is data".  ;-)
+
+Anybody else going to do this homework?...
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, May 17, 2010  8:37 PM
+
+> We ended up using Unbounded_Strings, which works, but it's awfully
+> heavy syntactically.  You end up either converting back and forth
+> between String and Unbounded_String all over, or using calls to
+> Element, Replace_Element, and the like instead of normal array
+> indexing and the like.  A loop such as:
+
+That's a problem with unbounded strings that doesn't seem to have much to do
+with subpools. Unbounded_Strings shouldn't be so clunky, period. Unfortunately,
+fixing that would take a fairly massive redesign, and would be incompatible in
+some corner cases.
+
+Tucker's indexing syntax might help with this as well. (We ought to consider
+defining it for bounded and unbounded strings.)
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, May 17, 2010  8:48 PM
+
+> Given the widespread use of unsafe subpools (AKA user-defined malloc,
+> placement new, etc) in C and C++, I find the question posed in the
+> minutes "see... if... they might use it" to be rather puzzling.
+
+I totally agree with this logic. I don't actually see the point of "safe
+subpools"; they're a lot of work to fix something that isn't (seriously) broken.
+
+> Safe subpools, as proposed by this AI, prevent (1), which is very
+> cool.
+> On the other hand, there's a fair amount of implementation complexity
+> for that.
+>
+> I can't get too excited about (4).  From a practical point of view,
+> I'd be happy if allocating such "fancy" things raised an exception.
+> That's ugly of course -- but that's a more theoretical point of view.
+> There's a huge implementation complexity in solving (4).
+
+Here I disagree with you, on both points. If we had simple unsafe subpools, it
+makes perfect sense for the allocated objects to be associated with the subpool,
+and thus go away when the subpool does. That's simple to implement in that it
+works the same way as it does for declared access types, just associated with a
+different object. The only problem that might come up is if the implementation
+cannot handle a dynamically determined object for the "master" of an allocated
+object. That shouldn't be the case for a chain-based implementation (only the
+root of the chain needs to be identified, and that can be treated as a normal
+object [an address]). An implementation that does things statically might have
+more trouble, but I can't figure out how a static implementation would even work
+for allocated objects - it seems like there would have to be a list somewhere.
+
+> I believe that a modern, efficient implementation of garbage
+> collection would do far more to promote the use of Ada than this AI.
+> The !example, of a "long-running web server" seems appropriate for GC
+> -- no hard real-time constraints, not safety critical, etc.  On the
+> other hand, the implementation cost of this AI is far less than that
+> of a really good GC.
+>
+> Summary: I have mixed feelings.  :-(
+
+Mine aren't mixed. Tucker's current proposal is too much. Solving (2), (3), and
+(4) is relatively easy and might be worthwhile, but I see no reason to go beyond
+that. And I'd rather do nothing than make a large implementation burden for a
+relatively rare use. (Remember that we've made it quite a bit easier to create a
+container that can handle all of this stuff at a higher level; that doesn't
+solve every problem but it solves a whole lot of them.)
+
+I had seriously considered writing an alternative AI that did just (2), (3), and
+(4), but I decided to go on vacation instead. Now I don't have time... ;-)
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Tuesday, May 18, 2010  9:07 PM
+
+One thing worth noting in the update
+to AI05-0111, is that there are no
+compile-time checks required to support
+the "reachability" requirements.
+My guess is that this simplifies
+the implementation significantly,
+since it can be offloaded almost
+entirely to the run-time system,
+which is almost always easier
+to update and debug than the compiler.
+
+Also, the reachability checks are
+now described in just a handful of
+paragraphs, in 13.11.6, and are
+hopefully easier to understand than before.
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent