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.Typeable
  35
  36 #ifdef __HUGS__
  37 import Hugs.Stable
  38 #endif
  39
  40 #ifdef __GLASGOW_HASKELL__
  41 import GHC.IO           ( 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.  Note in particular
  59   that `mkStableName` may return a different `StableName` after an
  60   object is evaluated.
  61
  62   Stable Names are similar to Stable Pointers ("Foreign.StablePtr"),
  63   but differ in the following ways:
  64
  65   * There is no @freeStableName@ operation, unlike "Foreign.StablePtr"s.
  66     Stable names are reclaimed by the runtime system when they are no
  67     longer needed.
  68
  69   * There is no @deRefStableName@ operation.  You can\'t get back from
  70     a stable name to the original Haskell object.  The reason for
  71     this is that the existence of a stable name for an object does not
  72     guarantee the existence of the object itself; it can still be garbage
  73     collected.
  74 -}
  75
  76 data StableName a = StableName (StableName# a)
  77
  78
  79 -- | Makes a 'StableName' for an arbitrary object.  The object passed as
  80 -- the first argument is not evaluated by 'makeStableName'.
  81 makeStableName  :: a -> IO (StableName a)
  82 #if defined(__PARALLEL_HASKELL__)
  83 makeStableName a =
  84   error "makeStableName not implemented in parallel Haskell"
  85 #else
  86 makeStableName a = IO $ \ s ->
  87     case makeStableName# a s of (# s', sn #) -> (# s', StableName sn #)
  88 #endif
  89
  90 -- | Convert a 'StableName' to an 'Int'.  The 'Int' returned is not
  91 -- necessarily unique; several 'StableName's may map to the same 'Int'
  92 -- (in practice however, the chances of this are small, so the result
  93 -- of 'hashStableName' makes a good hash key).
  94 hashStableName :: StableName a -> Int
  95 #if defined(__PARALLEL_HASKELL__)
  96 hashStableName (StableName sn) =
  97   error "hashStableName not implemented in parallel Haskell"
  98 #else
  99 hashStableName (StableName sn) = I# (stableNameToInt# sn)
 100 #endif
 101
 102 instance Eq (StableName a) where
 103 #if defined(__PARALLEL_HASKELL__)
 104     (StableName sn1) == (StableName sn2) =
 105       error "eqStableName not implemented in parallel Haskell"
 106 #else
 107     (StableName sn1) == (StableName sn2) =
 108        case eqStableName# sn1 sn2 of
 109          0# -> False
 110          _  -> True
 111 #endif
 112
 113 #endif /* __GLASGOW_HASKELL__ */
 114
 115 #include "Typeable.h"
 116 INSTANCE_TYPEABLE1(StableName,stableNameTc,"StableName")