System/Mem/StableName.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  System.Mem.StableName
   4 -- Copyright   :  (c) The University of Glasgow 2001
   5 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   6 --
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  experimental
   9 -- Portability :  non-portable
  10 --
  11 -- Stable names are a way of performing fast (O(1)), not-quite-exact
  12 -- comparison between objects.
  13 --
  14 -- Stable names solve the following problem: suppose you want to build
  15 -- a hash table with Haskell objects as keys, but you want to use
  16 -- pointer equality for comparison; maybe because the keys are large
  17 -- and hashing would be slow, or perhaps because the keys are infinite
  18 -- in size.  We can\'t build a hash table using the address of the
  19 -- object as the key, because objects get moved around by the garbage
  20 -- collector, meaning a re-hash would be necessary after every garbage
  21 -- collection.
  22 --
  23 -------------------------------------------------------------------------------
  24
  25 module System.Mem.StableName (
  26   -- * Stable Names
  27   StableName,
  28   makeStableName,
  29   hashStableName,
  30   ) where
  31
  32 import Prelude
  33
  34 import Data.Dynamic
  35
  36 #ifdef __HUGS__
  37 import Hugs.Stable
  38 #endif
  39
  40 #ifdef __GLASGOW_HASKELL__
  41 import GHC.IOBase       ( IO(..) )
  42 import GHC.Base         ( Int(..), StableName#, makeStableName#
  43                         , eqStableName#, stableNameToInt# )
  44
  45 -----------------------------------------------------------------------------
  46 -- Stable Names
  47
  48 {-|
  49   An abstract name for an object, that supports equality and hashing.
  50
  51   Stable names have the following property:
  52
  53   * If @sn1 :: StableName@ and @sn2 :: StableName@ and @sn1 == sn2@
  54    then @sn1@ and @sn2@ were created by calls to @makeStableName@ on
  55    the same object.
  56
  57   The reverse is not necessarily true: if two stable names are not
  58   equal, then the objects they name may still be equal.
  59
  60   Stable Names are similar to Stable Pointers ('Foreign.StablePtr'),
  61   but differ in the following ways:
  62
  63   * There is no @freeStableName@ operation, unlike 'Foreign.StablePtr's.
  64     Stable names are reclaimed by the runtime system when they are no
  65     longer needed.
  66
  67   * There is no @deRefStableName@ operation.  You can\'t get back from
  68     a stable name to the original Haskell object.  The reason for
  69     this is that the existence of a stable name for an object does not
  70     guarantee the existence of the object itself; it can still be garbage
  71     collected.
  72 -}
  73
  74 data StableName a = StableName (StableName# a)
  75
  76
  77 -- | Makes a 'StableName' for an arbitrary object.  The object passed as
  78 -- the first argument is not evaluated by 'makeStableName'.
  79 makeStableName  :: a -> IO (StableName a)
  80 #if defined(__PARALLEL_HASKELL__)
  81 makeStableName a =
  82   error "makeStableName not implemented in parallel Haskell"
  83 #else
  84 makeStableName a = IO $ \ s ->
  85     case makeStableName# a s of (# s', sn #) -> (# s', StableName sn #)
  86 #endif
  87
  88 -- | Convert a 'StableName' to an 'Int'.  The 'Int' returned is not
  89 -- necessarily unique; several 'StableName's may map to the same 'Int'
  90 -- (in practice however, the chances of this are small, so the result
  91 -- of 'hashStableName' makes a good hash key).
  92 hashStableName :: StableName a -> Int
  93 #if defined(__PARALLEL_HASKELL__)
  94 hashStableName (StableName sn) =
  95   error "hashStableName not implemented in parallel Haskell"
  96 #else
  97 hashStableName (StableName sn) = I# (stableNameToInt# sn)
  98 #endif
  99
 100 instance Eq (StableName a) where
 101 #if defined(__PARALLEL_HASKELL__)
 102     (StableName sn1) == (StableName sn2) =
 103       error "eqStableName not implemented in parallel Haskell"
 104 #else
 105     (StableName sn1) == (StableName sn2) =
 106        case eqStableName# sn1 sn2 of
 107          0# -> False
 108          _  -> True
 109 #endif
 110
 111 #endif /* __GLASGOW_HASKELL__ */
 112
 113 #include "Typeable.h"
 114 INSTANCE_TYPEABLE1(StableName,stableNameTc,"StableName")