Harden fixST
[ghc.git] / libraries / base / Control / Monad / ST / Imp.hs
1 {-# LANGUAGE NoImplicitPrelude #-}
2 {-# LANGUAGE Unsafe #-}
3 {-# OPTIONS_HADDOCK hide #-}
4
5 -----------------------------------------------------------------------------
6 -- |
7 -- Module : Control.Monad.ST.Imp
8 -- Copyright : (c) The University of Glasgow 2001
9 -- License : BSD-style (see the file libraries/base/LICENSE)
10 --
11 -- Maintainer : libraries@haskell.org
12 -- Stability : experimental
13 -- Portability : non-portable (requires universal quantification for runST)
14 --
15 -- This library provides support for /strict/ state threads, as
16 -- described in the PLDI \'94 paper by John Launchbury and Simon Peyton
17 -- Jones /Lazy Functional State Threads/.
18 --
19 -----------------------------------------------------------------------------
20
21 module Control.Monad.ST.Imp (
22 -- * The 'ST' Monad
23 ST, -- abstract, instance of Functor, Monad, Typeable.
24 runST,
25 fixST,
26
27 -- * Converting 'ST' to 'IO'
28 RealWorld, -- abstract
29 stToIO,
30
31 -- * Unsafe operations
32 unsafeInterleaveST,
33 unsafeDupableInterleaveST,
34 unsafeIOToST,
35 unsafeSTToIO
36 ) where
37
38 import GHC.ST ( ST, runST, unsafeInterleaveST
39 , unsafeDupableInterleaveST )
40 import GHC.Base ( RealWorld, ($), return )
41 import GHC.IO ( stToIO, unsafeIOToST, unsafeSTToIO
42 , unsafeDupableInterleaveIO )
43 import GHC.MVar ( readMVar, putMVar, newEmptyMVar )
44 import Control.Exception.Base
45 ( catch, throwIO, NonTermination (..)
46 , BlockedIndefinitelyOnMVar (..) )
47
48 -- | Allow the result of a state transformer computation to be used (lazily)
49 -- inside the computation.
50 --
51 -- Note that if @f@ is strict, @'fixST' f = _|_@.
52 fixST :: (a -> ST s a) -> ST s a
53 -- See Note [fixST]
54 fixST k = unsafeIOToST $ do
55 m <- newEmptyMVar
56 ans <- unsafeDupableInterleaveIO
57 (readMVar m `catch` \BlockedIndefinitelyOnMVar ->
58 throwIO NonTermination)
59 result <- unsafeSTToIO (k ans)
60 putMVar m result
61 return result
62
63 {- Note [fixST]
64 ~~~~~~~~~~~~
65
66 For many years, we implemented fixST much like a pure fixpoint,
67 using liftST:
68
69 fixST :: (a -> ST s a) -> ST s a
70 fixST k = ST $ \ s ->
71 let ans = liftST (k r) s
72 STret _ r = ans
73 in
74 case ans of STret s' x -> (# s', x #)
75
76 We knew that lazy blackholing could cause the computation to be re-run if the
77 result was demanded strictly, but we thought that would be okay in the case of
78 ST. However, that is not the case (see Trac #15349). Notably, the first time
79 the computation is executed, it may mutate variables that cause it to behave
80 *differently* the second time it's run. That may allow it to terminate when it
81 should not. More frighteningly, Arseniy Alekseyev produced a somewhat contrived
82 example ( https://mail.haskell.org/pipermail/libraries/2018-July/028889.html )
83 demonstrating that it can break reasonable assumptions in "trustworthy" code,
84 causing a memory safety violation. So now we implement fixST much like we do
85 fixIO. See also the implementation notes for fixIO. Simon Marlow wondered
86 whether we could get away with an IORef instead of an MVar. I believe we
87 cannot. The function passed to fixST may spark a parallel computation that
88 demands the final result. Such a computation should block until the final
89 result is available.
90 -}