dejafu-0.9.0.0: Systematic testing for Haskell concurrency.

Copyright(c) 2016 Michael Walker
LicenseMIT
MaintainerMichael Walker <mike@barrucadu.co.uk>
Stabilityexperimental
PortabilityFlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses, RankNTypes, TypeFamilies, TypeSynonymInstances
Safe HaskellNone
LanguageHaskell2010

Test.DejaFu.Conc

Contents

Description

Deterministic traced execution of concurrent computations.

This works by executing the computation on a single thread, calling out to the supplied scheduler after each step to determine which thread runs next.

Synopsis

The ConcT monad transformer

data ConcT r n a Source #

Since: 0.6.0.0

Instances

MonadIO ConcIO Source # 

Methods

liftIO :: IO a -> ConcIO a #

MonadBase IO ConcIO Source # 

Methods

liftBase :: IO α -> ConcIO α #

MonadTrans (ConcT r) Source # 

Methods

lift :: Monad m => m a -> ConcT r m a #

MonadRef (CRef r) (ConcT r n) Source # 

Methods

newRef :: a -> ConcT r n (CRef r a) #

readRef :: CRef r a -> ConcT r n a #

writeRef :: CRef r a -> a -> ConcT r n () #

modifyRef :: CRef r a -> (a -> a) -> ConcT r n () #

modifyRef' :: CRef r a -> (a -> a) -> ConcT r n () #

MonadAtomicRef (CRef r) (ConcT r n) Source # 

Methods

atomicModifyRef :: CRef r a -> (a -> (a, b)) -> ConcT r n b #

atomicModifyRef' :: CRef r a -> (a -> (a, b)) -> ConcT r n b #

Monad (ConcT r n) Source # 

Methods

(>>=) :: ConcT r n a -> (a -> ConcT r n b) -> ConcT r n b #

(>>) :: ConcT r n a -> ConcT r n b -> ConcT r n b #

return :: a -> ConcT r n a #

fail :: String -> ConcT r n a #

Functor (ConcT r n) Source # 

Methods

fmap :: (a -> b) -> ConcT r n a -> ConcT r n b #

(<$) :: a -> ConcT r n b -> ConcT r n a #

Applicative (ConcT r n) Source # 

Methods

pure :: a -> ConcT r n a #

(<*>) :: ConcT r n (a -> b) -> ConcT r n a -> ConcT r n b #

(*>) :: ConcT r n a -> ConcT r n b -> ConcT r n b #

(<*) :: ConcT r n a -> ConcT r n b -> ConcT r n a #

Monad n => MonadConc (ConcT r n) Source # 

Associated Types

type STM (ConcT r n :: * -> *) :: * -> * #

type MVar (ConcT r n :: * -> *) :: * -> * #

type CRef (ConcT r n :: * -> *) :: * -> * #

type Ticket (ConcT r n :: * -> *) :: * -> * #

type ThreadId (ConcT r n :: * -> *) :: * #

Methods

fork :: ConcT r n () -> ConcT r n (ThreadId (ConcT r n)) #

forkWithUnmask :: ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n ()) -> ConcT r n (ThreadId (ConcT r n)) #

forkWithUnmaskN :: String -> ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n ()) -> ConcT r n (ThreadId (ConcT r n)) #

forkOn :: Int -> ConcT r n () -> ConcT r n (ThreadId (ConcT r n)) #

forkOnWithUnmask :: Int -> ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n ()) -> ConcT r n (ThreadId (ConcT r n)) #

forkOnWithUnmaskN :: String -> Int -> ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n ()) -> ConcT r n (ThreadId (ConcT r n)) #

getNumCapabilities :: ConcT r n Int #

setNumCapabilities :: Int -> ConcT r n () #

myThreadId :: ConcT r n (ThreadId (ConcT r n)) #

yield :: ConcT r n () #

threadDelay :: Int -> ConcT r n () #

newEmptyMVar :: ConcT r n (MVar (ConcT r n) a) #

newEmptyMVarN :: String -> ConcT r n (MVar (ConcT r n) a) #

putMVar :: MVar (ConcT r n) a -> a -> ConcT r n () #

tryPutMVar :: MVar (ConcT r n) a -> a -> ConcT r n Bool #

readMVar :: MVar (ConcT r n) a -> ConcT r n a #

tryReadMVar :: MVar (ConcT r n) a -> ConcT r n (Maybe a) #

takeMVar :: MVar (ConcT r n) a -> ConcT r n a #

tryTakeMVar :: MVar (ConcT r n) a -> ConcT r n (Maybe a) #

newCRef :: a -> ConcT r n (CRef (ConcT r n) a) #

newCRefN :: String -> a -> ConcT r n (CRef (ConcT r n) a) #

readCRef :: CRef (ConcT r n) a -> ConcT r n a #

atomicModifyCRef :: CRef (ConcT r n) a -> (a -> (a, b)) -> ConcT r n b #

writeCRef :: CRef (ConcT r n) a -> a -> ConcT r n () #

atomicWriteCRef :: CRef (ConcT r n) a -> a -> ConcT r n () #

readForCAS :: CRef (ConcT r n) a -> ConcT r n (Ticket (ConcT r n) a) #

peekTicket' :: proxy (ConcT r n) -> Ticket (ConcT r n) a -> a #

casCRef :: CRef (ConcT r n) a -> Ticket (ConcT r n) a -> a -> ConcT r n (Bool, Ticket (ConcT r n) a) #

modifyCRefCAS :: CRef (ConcT r n) a -> (a -> (a, b)) -> ConcT r n b #

modifyCRefCAS_ :: CRef (ConcT r n) a -> (a -> a) -> ConcT r n () #

atomically :: STM (ConcT r n) a -> ConcT r n a #

readTVarConc :: TVar (STM (ConcT r n)) a -> ConcT r n a #

throwTo :: Exception e => ThreadId (ConcT r n) -> e -> ConcT r n () #

MonadThrow (ConcT r n) Source # 

Methods

throwM :: Exception e => e -> ConcT r n a #

MonadCatch (ConcT r n) Source # 

Methods

catch :: Exception e => ConcT r n a -> (e -> ConcT r n a) -> ConcT r n a #

MonadMask (ConcT r n) Source # 

Methods

mask :: ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n b) -> ConcT r n b #

uninterruptibleMask :: ((forall a. ConcT r n a -> ConcT r n a) -> ConcT r n b) -> ConcT r n b #

type ThreadId (ConcT r n) Source # 
type ThreadId (ConcT r n) = ThreadId
type Ticket (ConcT r n) Source # 
type Ticket (ConcT r n) = Ticket
type CRef (ConcT r n) Source # 
type CRef (ConcT r n) = CRef r
type MVar (ConcT r n) Source # 
type MVar (ConcT r n) = MVar r
type STM (ConcT r n) Source # 
type STM (ConcT r n) = STMLike n r

type ConcST t = ConcT (STRef t) (ST t) Source #

A MonadConc implementation using ST, this should be preferred if you do not need liftIO.

Since: 0.4.0.0

type ConcIO = ConcT IORef IO Source #

A MonadConc implementation using IO.

Since: 0.4.0.0

Executing computations

data Failure Source #

An indication of how a concurrent computation failed.

The Eq, Ord, and NFData instances compare/evaluate the exception with show in the UncaughtException case.

Since: 0.9.0.0

Constructors

InternalError

Will be raised if the scheduler does something bad. This should never arise unless you write your own, faulty, scheduler! If it does, please file a bug report.

Abort

The scheduler chose to abort execution. This will be produced if, for example, all possible decisions exceed the specified bounds (there have been too many pre-emptions, the computation has executed for too long, or there have been too many yields).

Deadlock

The computation became blocked indefinitely on MVars.

STMDeadlock

The computation became blocked indefinitely on TVars.

UncaughtException SomeException

An uncaught exception bubbled to the top of the computation.

IllegalSubconcurrency

Calls to subconcurrency were nested, or attempted when multiple threads existed.

data MemType Source #

The memory model to use for non-synchronised CRef operations.

Since: 0.4.0.0

Constructors

SequentialConsistency

The most intuitive model: a program behaves as a simple interleaving of the actions in different threads. When a CRef is written to, that write is immediately visible to all threads.

TotalStoreOrder

Each thread has a write buffer. A thread sees its writes immediately, but other threads will only see writes when they are committed, which may happen later. Writes are committed in the same order that they are created.

PartialStoreOrder

Each CRef has a write buffer. A thread sees its writes immediately, but other threads will only see writes when they are committed, which may happen later. Writes to different CRefs are not necessarily committed in the same order that they are created.

runConcurrent :: MonadRef r n => Scheduler s -> MemType -> s -> ConcT r n a -> n (Either Failure a, s, Trace) Source #

Run a concurrent computation with a given Scheduler and initial state, returning a failure reason on error. Also returned is the final state of the scheduler, and an execution trace.

Warning: Blocking on the action of another thread in liftIO cannot be detected! So if you perform some potentially blocking action in a liftIO the entire collection of threads may deadlock! You should therefore keep IO blocks small, and only perform blocking operations with the supplied primitives, insofar as possible.

Note: In order to prevent computation from hanging, the runtime will assume that a deadlock situation has arisen if the scheduler attempts to (a) schedule a blocked thread, or (b) schedule a nonexistent thread. In either of those cases, the computation will be halted.

Since: 0.8.0.0

subconcurrency :: ConcT r n a -> ConcT r n (Either Failure a) Source #

Run a concurrent computation and return its result.

This can only be called in the main thread, when no other threads exist. Calls to subconcurrency cannot be nested. Violating either of these conditions will result in the computation failing with IllegalSubconcurrency.

Since: 0.6.0.0

Execution traces

type Trace = [(Decision, [(ThreadId, Lookahead)], ThreadAction)] Source #

One of the outputs of the runner is a Trace, which is a log of decisions made, all the runnable threads and what they would do, and the action a thread took in its step.

Since: 0.8.0.0

data Decision Source #

Scheduling decisions are based on the state of the running program, and so we can capture some of that state in recording what specific decision we made.

Since: 0.5.0.0

Constructors

Start ThreadId

Start a new thread, because the last was blocked (or it's the start of computation).

Continue

Continue running the last thread for another step.

SwitchTo ThreadId

Pre-empt the running thread, and switch to another.

Instances

data ThreadId Source #

Every live thread has a unique identitifer.

The Eq and Ord instances only consider the int, not the name.

Since: 0.4.0.0

Constructors

ThreadId (Maybe String) !Int 

Instances

Eq ThreadId Source #

Previously this was a derived instance.

Since: 0.7.2.0

Ord ThreadId Source # 
Show ThreadId Source # 
NFData ThreadId Source #

Since: 0.5.1.0

Methods

rnf :: ThreadId -> () #

data ThreadAction Source #

All the actions that a thread can perform.

Since: 0.9.0.0

Constructors

Fork ThreadId

Start a new thread.

MyThreadId

Get the ThreadId of the current thread.

GetNumCapabilities Int

Get the number of Haskell threads that can run simultaneously.

SetNumCapabilities Int

Set the number of Haskell threads that can run simultaneously.

Yield

Yield the current thread.

ThreadDelay Int

Yield/delay the current thread.

NewMVar MVarId

Create a new MVar.

PutMVar MVarId [ThreadId]

Put into a MVar, possibly waking up some threads.

BlockedPutMVar MVarId

Get blocked on a put.

TryPutMVar MVarId Bool [ThreadId]

Try to put into a MVar, possibly waking up some threads.

ReadMVar MVarId

Read from a MVar.

TryReadMVar MVarId Bool

Try to read from a MVar.

BlockedReadMVar MVarId

Get blocked on a read.

TakeMVar MVarId [ThreadId]

Take from a MVar, possibly waking up some threads.

BlockedTakeMVar MVarId

Get blocked on a take.

TryTakeMVar MVarId Bool [ThreadId]

Try to take from a MVar, possibly waking up some threads.

NewCRef CRefId

Create a new CRef.

ReadCRef CRefId

Read from a CRef.

ReadCRefCas CRefId

Read from a CRef for a future compare-and-swap.

ModCRef CRefId

Modify a CRef.

ModCRefCas CRefId

Modify a CRef using a compare-and-swap.

WriteCRef CRefId

Write to a CRef without synchronising.

CasCRef CRefId Bool

Attempt to to a CRef using a compare-and-swap, synchronising it.

CommitCRef ThreadId CRefId

Commit the last write to the given CRef by the given thread, so that all threads can see the updated value.

STM TTrace [ThreadId]

An STM transaction was executed, possibly waking up some threads.

BlockedSTM TTrace

Got blocked in an STM transaction.

Catching

Register a new exception handler

PopCatching

Pop the innermost exception handler from the stack.

Throw

Throw an exception.

ThrowTo ThreadId

Throw an exception to a thread.

BlockedThrowTo ThreadId

Get blocked on a throwTo.

Killed

Killed by an uncaught exception.

SetMasking Bool MaskingState

Set the masking state. If True, this is being used to set the masking state to the original state in the argument passed to a masked function.

ResetMasking Bool MaskingState

Return to an earlier masking state. If True, this is being used to return to the state of the masked block in the argument passed to a masked function.

LiftIO

Lift an IO action. Note that this can only happen with ConcIO.

Return

A return or pure action was executed.

Stop

Cease execution and terminate.

Subconcurrency

Start executing an action with subconcurrency.

StopSubconcurrency

Stop executing an action with subconcurrency.

data Lookahead Source #

A one-step look-ahead at what a thread will do next.

Since: 0.9.0.0

Constructors

WillFork

Will start a new thread.

WillMyThreadId

Will get the ThreadId.

WillGetNumCapabilities

Will get the number of Haskell threads that can run simultaneously.

WillSetNumCapabilities Int

Will set the number of Haskell threads that can run simultaneously.

WillYield

Will yield the current thread.

WillThreadDelay Int

Will yield/delay the current thread.

WillNewMVar

Will create a new MVar.

WillPutMVar MVarId

Will put into a MVar, possibly waking up some threads.

WillTryPutMVar MVarId

Will try to put into a MVar, possibly waking up some threads.

WillReadMVar MVarId

Will read from a MVar.

WillTryReadMVar MVarId

Will try to read from a MVar.

WillTakeMVar MVarId

Will take from a MVar, possibly waking up some threads.

WillTryTakeMVar MVarId

Will try to take from a MVar, possibly waking up some threads.

WillNewCRef

Will create a new CRef.

WillReadCRef CRefId

Will read from a CRef.

WillReadCRefCas CRefId

Will read from a CRef for a future compare-and-swap.

WillModCRef CRefId

Will modify a CRef.

WillModCRefCas CRefId

Will modify a CRef using a compare-and-swap.

WillWriteCRef CRefId

Will write to a CRef without synchronising.

WillCasCRef CRefId

Will attempt to to a CRef using a compare-and-swap, synchronising it.

WillCommitCRef ThreadId CRefId

Will commit the last write by the given thread to the CRef.

WillSTM

Will execute an STM transaction, possibly waking up some threads.

WillCatching

Will register a new exception handler

WillPopCatching

Will pop the innermost exception handler from the stack.

WillThrow

Will throw an exception.

WillThrowTo ThreadId

Will throw an exception to a thread.

WillSetMasking Bool MaskingState

Will set the masking state. If True, this is being used to set the masking state to the original state in the argument passed to a masked function.

WillResetMasking Bool MaskingState

Will return to an earlier masking state. If True, this is being used to return to the state of the masked block in the argument passed to a masked function.

WillLiftIO

Will lift an IO action. Note that this can only happen with ConcIO.

WillReturn

Will execute a return or pure action.

WillStop

Will cease execution and terminate.

WillSubconcurrency

Will execute an action with subconcurrency.

WillStopSubconcurrency

Will stop executing an extion with subconcurrency.

data MVarId Source #

Every MVar has a unique identifier.

The Eq and Ord instances only consider the int, not the name.

Since: 0.4.0.0

Instances

Eq MVarId Source #

Previously this was a derived instance.

Since: 0.7.2.0

Methods

(==) :: MVarId -> MVarId -> Bool #

(/=) :: MVarId -> MVarId -> Bool #

Ord MVarId Source # 
Show MVarId Source # 
NFData MVarId Source #

Since: 0.5.1.0

Methods

rnf :: MVarId -> () #

data CRefId Source #

Every CRef has a unique identifier.

The Eq and Ord instances only consider the int, not the name.

Since: 0.4.0.0

Instances

Eq CRefId Source #

Previously this was a derived instance.

Since: 0.7.2.0

Methods

(==) :: CRefId -> CRefId -> Bool #

(/=) :: CRefId -> CRefId -> Bool #

Ord CRefId Source # 
Show CRefId Source # 
NFData CRefId Source #

Since: 0.5.1.0

Methods

rnf :: CRefId -> () #

data MaskingState :: * #

Describes the behaviour of a thread when an asynchronous exception is received.

Constructors

Unmasked

asynchronous exceptions are unmasked (the normal state)

MaskedInterruptible

the state during mask: asynchronous exceptions are masked, but blocking operations may still be interrupted

MaskedUninterruptible

the state during uninterruptibleMask: asynchronous exceptions are masked, and blocking operations may not be interrupted

showTrace :: Trace -> String Source #

Pretty-print a trace, including a key of the thread IDs (not including thread 0). Each line of the key is indented by two spaces.

Since: 0.5.0.0

showFail :: Failure -> String Source #

Pretty-print a failure

Since: 0.4.0.0

Scheduling