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 __GLASGOW_HASKELL__
  37 import GHC.IOBase       ( IO(..) )
  38 import GHC.Base         ( Int(..), StableName#, makeStableName#
  39                         , eqStableName#, stableNameToInt# )
  40
  41 -----------------------------------------------------------------------------
  42 -- Stable Names
  43
  44 {-|
  45   An abstract name for an object, that supports equality and hashing.
  46
  47   Stable names have the following property:
  48
  49   * If @sn1 :: StableName@ and @sn2 :: StableName@ and @sn1 == sn2@
  50    then @sn1@ and @sn2@ were created by calls to @makeStableName@ on
  51    the same object.
  52
  53   The reverse is not necessarily true: if two stable names are not
  54   equal, then the objects they name may still be equal.
  55
  56   Stable Names are similar to Stable Pointers ('Foreign.StablePtr'),
  57   but differ in the following ways:
  58
  59   * There is no @freeStableName@ operation, unlike 'Foreign.StablePtr's.
  60     Stable names are reclaimed by the runtime system when they are no
  61     longer needed.
  62
  63   * There is no @deRefStableName@ operation.  You can\'t get back from
  64     a stable name to the original Haskell object.  The reason for
  65     this is that the existence of a stable name for an object does not
  66     guarantee the existence of the object itself; it can still be garbage
  67     collected.
  68 -}
  69
  70 data StableName a = StableName (StableName# a)
  71
  72
  73 -- | Makes a 'StableName' for an arbitrary object.  The object passed as
  74 -- the first argument is not evaluated by 'makeStableName'.
  75 makeStableName  :: a -> IO (StableName a)
  76 #if defined(__PARALLEL_HASKELL__)
  77 makeStableName a =
  78   error "makeStableName not implemented in parallel Haskell"
  79 #else
  80 makeStableName a = IO $ \ s ->
  81     case makeStableName# a s of (# s', sn #) -> (# s', StableName sn #)
  82 #endif
  83
  84 -- | Convert a 'StableName' to an 'Int'.  The 'Int' returned is not
  85 -- necessarily unique; several 'StableName's may map to the same 'Int'
  86 -- (in practice however, the chances of this are small, so the result
  87 -- of 'hashStableName' makes a good hash key).
  88 hashStableName :: StableName a -> Int
  89 #if defined(__PARALLEL_HASKELL__)
  90 hashStableName (StableName sn) =
  91   error "hashStableName not implemented in parallel Haskell"
  92 #else
  93 hashStableName (StableName sn) = I# (stableNameToInt# sn)
  94 #endif
  95
  96 instance Eq (StableName a) where
  97 #if defined(__PARALLEL_HASKELL__)
  98     (StableName sn1) == (StableName sn2) =
  99       error "eqStableName not implemented in parallel Haskell"
 100 #else
 101     (StableName sn1) == (StableName sn2) =
 102        case eqStableName# sn1 sn2 of
 103          0# -> False
 104          _  -> True
 105 #endif
 106
 107 #endif /* __GLASGOW_HASKELL__ */
 108
 109 #include "Dynamic.h"
 110 INSTANCE_TYPEABLE1(StableName,stableNameTc,"StableName")