[project @ 2002-05-27 15:43:44 by simonmar]
authorsimonmar <unknown>
Mon, 27 May 2002 15:43:44 +0000 (15:43 +0000)
committersimonmar <unknown>
Mon, 27 May 2002 15:43:44 +0000 (15:43 +0000)
Documentation for System.Mem.Weak

libraries/base/GHC/Weak.lhs
libraries/base/System/Mem/Weak.hs

index 9b85f54..3ce0467 100644 (file)
@@ -20,21 +20,71 @@ import GHC.Base
 import Data.Maybe
 import GHC.IOBase      ( IO(..), unIO )
 
+{-|
+A weak pointer object with a key and a value.  The value has type @v@.
+
+A weak pointer expresses a relationship between two objects, the
+/key/ and the /value/:  if the key is considered to be alive by the
+garbage collector, then the value is also alive.  A reference from
+the value to the key does /not/ keep the key alive.
+
+A weak pointer may also have a finalizer of type @IO ()@; if it does,
+then the finalizer will be run once, and once only, at a time after
+the key has become unreachable by the program (\"dead\").  The storage
+manager attempts to run the finalizer(s) for an object soon after the
+object dies, but promptness is not guaranteed.  
+
+References from the finalizer to the key are treated in the same way
+as references from the value to the key: they do not keep the key
+alive.  A finalizer may therefore ressurrect the key, perhaps by
+storing it in the same data structure.
+
+The finalizer, and the relationship between the key and the value,
+exist regardless of whether the program keeps a reference to the
+'Weak' object or not.
+
+There may be multiple weak pointers with the same key.  In this
+case, the finalizers for each of these weak pointers will all be
+run in some arbitrary order, or perhaps concurrently, when the key
+dies.  If the programmer specifies a finalizer that assumes it has
+the only reference to an object (for example, a file that it wishes
+to close), then the programmer must ensure that there is only one
+such finalizer.
+
+If there are no other threads to run, the runtime system will check
+for runnable finalizers before declaring the system to be deadlocked.
+-}
 data Weak v = Weak (Weak# v)
 
-mkWeak  :: k                           -- key
-       -> v                            -- value
-       -> Maybe (IO ())                -- finalizer
-       -> IO (Weak v)                  -- weak pointer
+-- | Establishes a weak pointer to @k@, with value @v@ and a finalizer.
+--
+-- This is the most general interface for building a weak pointer.
+--
+mkWeak  :: k                           -- ^ key
+       -> v                            -- ^ value
+       -> Maybe (IO ())                -- ^ finalizer
+       -> IO (Weak v)                  -- ^ returns: a weak pointer object
 
 mkWeak key val (Just finalizer) = IO $ \s ->
    case mkWeak# key val finalizer s of { (# s1, w #) -> (# s1, Weak w #) }
 mkWeak key val Nothing = IO $ \s ->
    case mkWeak# key val (unsafeCoerce# 0#) s of { (# s1, w #) -> (# s1, Weak w #) }
 
+{-|
+  A specialised version of 'mkWeak', where the key and the value are the
+  same object:
+
+  > mkWeakPtr key finalizer = mkWeak key key finalizer
+-}
 mkWeakPtr :: k -> Maybe (IO ()) -> IO (Weak k)
 mkWeakPtr key finalizer = mkWeak key key finalizer
 
+{-|
+  A specialised version of 'mkWeakPtr', where the 'Weak' object
+  returned is simply thrown away (however the finalizer will be
+  remembered by the garbage collector, and will still be run
+  when the key becomes unreachable).
+-}
 addFinalizer :: key -> IO () -> IO ()
 addFinalizer key finalizer = do
    mkWeakPtr key (Just finalizer)      -- throw it away
index 62495fc..85907b0 100644 (file)
@@ -8,22 +8,63 @@
 -- Stability   :  experimental
 -- Portability :  non-portable
 --
--- Weak references, weak pairs, weak pointers, and finalizers.
+-- In general terms, a weak pointer is a reference to an object that is
+-- not followed by the garbage collector - that is, the existence of a
+-- weak pointer to an object has no effect on the lifetime of that
+-- object.  A weak pointer can be de-referenced to find out
+-- whether the object it refers to is still alive or not, and if so
+-- to return the object itself.
+-- 
+-- Weak pointers are particularly useful for caches and memo tables.
+-- To build a memo table, you build a data structure 
+-- mapping from the function argument (the key) to its result (the
+-- value).  When you apply the function to a new argument you first
+-- check whether the key\/value pair is already in the memo table.
+-- The key point is that the memo table itself should not keep the
+-- key and value alive.  So the table should contain a weak pointer
+-- to the key, not an ordinary pointer.  The pointer to the value must
+-- not be weak, because the only reference to the value might indeed be
+-- from the memo table.   
+-- 
+-- So it looks as if the memo table will keep all its values
+-- alive for ever.  One way to solve this is to purge the table
+-- occasionally, by deleting entries whose keys have died.
+-- 
+-- The weak pointers in this library
+-- support another approach, called /finalization/.
+-- When the key referred to by a weak pointer dies, the storage manager
+-- arranges to run a programmer-specified finalizer.  In the case of memo
+-- tables, for example, the finalizer could remove the key\/value pair
+-- from the memo table.  
+-- 
+-- Another difficulty with the memo table is that the value of a
+-- key\/value pair might itself contain a pointer to the key.
+-- So the memo table keeps the value alive, which keeps the key alive,
+-- even though there may be no other references to the key so both should
+-- die.  The weak pointers in this library provide a slight 
+-- generalisation of the basic weak-pointer idea, in which each
+-- weak pointer actually contains both a key and a value.
 --
 -----------------------------------------------------------------------------
 
 module System.Mem.Weak (
+       -- * The @Weak@ type
        Weak,                   -- abstract
-       -- instance Eq (Weak v)  
 
+       -- * The general interface
        mkWeak,                 -- :: k -> v -> Maybe (IO ()) -> IO (Weak v)
        deRefWeak,              -- :: Weak v -> IO (Maybe v)
        finalize,               -- :: Weak v -> IO ()
-       -- replaceFinaliser     -- :: Weak v -> IO () -> IO ()
 
+       -- * Specialised versions
        mkWeakPtr,              -- :: k -> Maybe (IO ()) -> IO (Weak k)
+       addFinalizer,           -- :: key -> IO () -> IO ()
        mkWeakPair,             -- :: k -> v -> Maybe (IO ()) -> IO (Weak (k,v))
-       addFinalizer            -- :: key -> IO () -> IO ()
+       -- replaceFinaliser     -- :: Weak v -> IO () -> IO ()
+
+       -- * A precise semantics
+       
+       -- $precise
    ) where
 
 import Prelude
@@ -38,6 +79,14 @@ import GHC.Weak
 #include "Dynamic.h"
 INSTANCE_TYPEABLE1(Weak,weakTc,"Weak")
 
+{-|
+Dereferences a weak pointer.  If the key is still alive, then
+@'Just' v@ is returned (where @v@ is the /value/ in the weak pointer), otherwise
+'Nothing' is returned.
+
+The return value of 'deRefWeak' depends on when the garbage collector
+runs, hence it is in the 'IO' monad.
+-}
 deRefWeak :: Weak v -> IO (Maybe v)
 deRefWeak (Weak w) = IO $ \s ->
    case deRefWeak# w s of
@@ -45,9 +94,18 @@ deRefWeak (Weak w) = IO $ \s ->
                                0# -> (# s1, Nothing #)
                                _  -> (# s1, Just p #)
 
+-- | A specialised version of 'mkWeak' where the value is actually a pair
+-- of the key and value passed to 'mkWeakPair':
+--
+-- > mkWeakPair key val finalizer = mkWeak key (key,val) finalizer
+--
+-- The advantage of this is that the key can be retrieved by 'deRefWeak'
+-- in addition to the value.
 mkWeakPair :: k -> v -> Maybe (IO ()) -> IO (Weak (k,v))
 mkWeakPair key val finalizer = mkWeak key (key,val) finalizer
 
+-- | Causes a the finalizer associated with a weak pointer to be run
+-- immediately.
 finalize :: Weak v -> IO ()
 finalize (Weak w) = IO $ \s ->
    case finalizeWeak# w s of 
@@ -55,3 +113,35 @@ finalize (Weak w) = IO $ \s ->
        (# s1, _,  f #) -> f s1
 #endif
 
+
+{- $precise
+
+The above informal specification is fine for simple situations, but
+matters can get complicated.  In particular, it needs to be clear
+exactly when a key dies, so that any weak pointers that refer to it
+can be finalized.  Suppose, for example, the value of one weak pointer
+refers to the key of another...does that keep the key alive?
+
+The behaviour is simply this:
+
+ *  If a weak pointer (object) refers to an /unreachable/
+    key, it may be finalized.
+
+ *  Finalization means (a) arrange that subsequent calls
+    to 'deRefWeak' return 'Nothing'; and (b) run the finalizer.
+
+This behaviour depends on what it means for a key to be reachable.
+Informally, something is reachable if it can be reached by following
+ordinary pointers from the root set, but not following weak pointers.
+We define reachability more precisely as follows A heap object is
+reachable if:
+
+ * It is a member of the /root set/.
+
+ * It is directly pointed to by a reachable object, other than
+   a weak pointer object.
+
+ * It is a weak pointer object whose key is reachable.
+
+ * It is the value or finalizer of an object whose key is reachable.
+-}