Test.DejaFu.Common

Common types and functions used throughout DejaFu. This module is NOT considered to form part of the public interface of this library.

Identifiers

data ThreadId

Every live thread has a unique identitifer.

Constructors

ThreadId (Maybe String) Int

Instances

Eq ThreadId

Methods

(==) :: ThreadId -> ThreadId -> Bool

(/=) :: ThreadId -> ThreadId -> Bool

Ord ThreadId

Methods

compare :: ThreadId -> ThreadId -> Ordering

(<) :: ThreadId -> ThreadId -> Bool

(<=) :: ThreadId -> ThreadId -> Bool

(>) :: ThreadId -> ThreadId -> Bool

(>=) :: ThreadId -> ThreadId -> Bool

max :: ThreadId -> ThreadId -> ThreadId

min :: ThreadId -> ThreadId -> ThreadId

Show ThreadId

Methods

showsPrec :: Int -> ThreadId -> ShowS

show :: ThreadId -> String

showList :: [ThreadId] -> ShowS

NFData ThreadId

Methods

rnf :: ThreadId -> ()

data CRefId

Every CRef has a unique identifier.

Constructors

CRefId (Maybe String) Int

Instances

Eq CRefId

Methods

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

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

Ord CRefId

Methods

compare :: CRefId -> CRefId -> Ordering

(<) :: CRefId -> CRefId -> Bool

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

(>) :: CRefId -> CRefId -> Bool

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

max :: CRefId -> CRefId -> CRefId

min :: CRefId -> CRefId -> CRefId

Show CRefId

Methods

showsPrec :: Int -> CRefId -> ShowS

show :: CRefId -> String

showList :: [CRefId] -> ShowS

NFData CRefId

Methods

rnf :: CRefId -> ()

data MVarId

Every MVar has a unique identifier.

Constructors

MVarId (Maybe String) Int

Instances

Eq MVarId

Methods

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

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

Ord MVarId

Methods

compare :: MVarId -> MVarId -> Ordering

(<) :: MVarId -> MVarId -> Bool

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

(>) :: MVarId -> MVarId -> Bool

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

max :: MVarId -> MVarId -> MVarId

min :: MVarId -> MVarId -> MVarId

Show MVarId

Methods

showsPrec :: Int -> MVarId -> ShowS

show :: MVarId -> String

showList :: [MVarId] -> ShowS

NFData MVarId

Methods

rnf :: MVarId -> ()

data TVarId

Every TVar has a unique identifier.

Constructors

TVarId (Maybe String) Int

Instances

Eq TVarId

Methods

(==) :: TVarId -> TVarId -> Bool

(/=) :: TVarId -> TVarId -> Bool

Ord TVarId

Methods

compare :: TVarId -> TVarId -> Ordering

(<) :: TVarId -> TVarId -> Bool

(<=) :: TVarId -> TVarId -> Bool

(>) :: TVarId -> TVarId -> Bool

(>=) :: TVarId -> TVarId -> Bool

max :: TVarId -> TVarId -> TVarId

min :: TVarId -> TVarId -> TVarId

Show TVarId

Methods

showsPrec :: Int -> TVarId -> ShowS

show :: TVarId -> String

showList :: [TVarId] -> ShowS

NFData TVarId

Methods

rnf :: TVarId -> ()

initialThread :: ThreadId

The ID of the initial thread.

Identifier source

data IdSource

The number of ID parameters was getting a bit unwieldy, so this hides them all away.

Constructors

Id

Fields

• _nextCRId :: Int
• _nextMVId :: Int
• _nextTVId :: Int
• _nextTId :: Int
• _usedCRNames :: [String]
• _usedMVNames :: [String]
• _usedTVNames :: [String]
• _usedTNames :: [String]

Instances

Eq IdSource

Methods

(==) :: IdSource -> IdSource -> Bool

(/=) :: IdSource -> IdSource -> Bool

Ord IdSource

Methods

compare :: IdSource -> IdSource -> Ordering

(<) :: IdSource -> IdSource -> Bool

(<=) :: IdSource -> IdSource -> Bool

(>) :: IdSource -> IdSource -> Bool

(>=) :: IdSource -> IdSource -> Bool

max :: IdSource -> IdSource -> IdSource

min :: IdSource -> IdSource -> IdSource

Show IdSource

Methods

showsPrec :: Int -> IdSource -> ShowS

show :: IdSource -> String

showList :: [IdSource] -> ShowS

NFData IdSource

Methods

rnf :: IdSource -> ()

nextCRId :: String -> IdSource -> (IdSource, CRefId)

Get the next free CRefId.

nextMVId :: String -> IdSource -> (IdSource, MVarId)

Get the next free MVarId.

nextTVId :: String -> IdSource -> (IdSource, TVarId)

Get the next free TVarId.

nextTId :: String -> IdSource -> (IdSource, ThreadId)

Get the next free ThreadId.

initialIdSource :: IdSource

The initial ID source.

Actions

Thread actions

data ThreadAction

All the actions that a thread can perform.

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.

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.

Instances

Eq ThreadAction

Methods

(==) :: ThreadAction -> ThreadAction -> Bool

(/=) :: ThreadAction -> ThreadAction -> Bool

Show ThreadAction

Methods

showsPrec :: Int -> ThreadAction -> ShowS

show :: ThreadAction -> String

showList :: [ThreadAction] -> ShowS

NFData ThreadAction

Methods

rnf :: ThreadAction -> ()

isBlock :: ThreadAction -> Bool

Check if a ThreadAction immediately blocks.

tvarsOf :: ThreadAction -> Set TVarId

Get the TVars affected by a ThreadAction.

Lookahead

data Lookahead

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

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.

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.

Instances

Eq Lookahead

Methods

(==) :: Lookahead -> Lookahead -> Bool

(/=) :: Lookahead -> Lookahead -> Bool

Show Lookahead

Methods

showsPrec :: Int -> Lookahead -> ShowS

show :: Lookahead -> String

showList :: [Lookahead] -> ShowS

NFData Lookahead

Methods

rnf :: Lookahead -> ()

rewind :: ThreadAction -> Maybe Lookahead

Convert a ThreadAction into a Lookahead: "rewind" what has happened. Killed has no Lookahead counterpart.

willRelease :: Lookahead -> Bool

Check if an operation could enable another thread.

Simplified actions

data ActionType

A simplified view of the possible actions a thread can perform.

Constructors

UnsynchronisedRead CRefId

A readCRef or a readForCAS.

UnsynchronisedWrite CRefId

A writeCRef.

UnsynchronisedOther

Some other action which doesn't require cross-thread communication.

PartiallySynchronisedCommit CRefId

A commit.

PartiallySynchronisedWrite CRefId

A casCRef

PartiallySynchronisedModify CRefId

A modifyCRefCAS

SynchronisedModify CRefId

An atomicModifyCRef.

SynchronisedRead MVarId

A readMVar or takeMVar (or try/blocked variants).

SynchronisedWrite MVarId

A putMVar (or try/blocked variant).

SynchronisedOther

Some other action which does require cross-thread communication.

Instances

Eq ActionType

Methods

(==) :: ActionType -> ActionType -> Bool

(/=) :: ActionType -> ActionType -> Bool

Show ActionType

Methods

showsPrec :: Int -> ActionType -> ShowS

show :: ActionType -> String

showList :: [ActionType] -> ShowS

NFData ActionType

Methods

rnf :: ActionType -> ()

isBarrier :: ActionType -> Bool

Check if an action imposes a write barrier.

isCommit :: ActionType -> CRefId -> Bool

Check if an action commits a given CRef.

synchronises :: ActionType -> CRefId -> Bool

Check if an action synchronises a given CRef.

crefOf :: ActionType -> Maybe CRefId

Get the CRef affected.

mvarOf :: ActionType -> Maybe MVarId

Get the MVar affected.

simplifyAction :: ThreadAction -> ActionType

Throw away information from a ThreadAction and give a simplified view of what is happening.

This is used in the SCT code to help determine interesting alternative scheduling decisions.

simplifyLookahead :: Lookahead -> ActionType

Variant of simplifyAction that takes a Lookahead.

STM actions

type TTrace = [TAction]

A trace of an STM transaction is just a list of actions that occurred, as there are no scheduling decisions to make.

data TAction

All the actions that an STM transaction can perform.

Constructors

TNew

Create a new TVar

TRead TVarId

Read from a TVar.

TWrite TVarId

Write to a TVar.

TRetry

Abort and discard effects.

TOrElse TTrace (Maybe TTrace)

Execute a transaction until it succeeds (STMStop) or aborts (STMRetry) and, if it aborts, execute the other transaction.

TThrow

Throw an exception, abort, and discard effects.

TCatch TTrace (Maybe TTrace)

Execute a transaction until it succeeds (STMStop) or aborts (STMThrow). If the exception is of the appropriate type, it is handled and execution continues; otherwise aborts, propagating the exception upwards.

TStop

Terminate successfully and commit effects.

Instances

Eq TAction

Methods

(==) :: TAction -> TAction -> Bool

(/=) :: TAction -> TAction -> Bool

Show TAction

Methods

showsPrec :: Int -> TAction -> ShowS

show :: TAction -> String

showList :: [TAction] -> ShowS

NFData TAction

Methods

rnf :: TAction -> ()

Traces

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

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.

data Decision

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.

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

Eq Decision

Methods

(==) :: Decision -> Decision -> Bool

(/=) :: Decision -> Decision -> Bool

Show Decision

Methods

showsPrec :: Int -> Decision -> ShowS

show :: Decision -> String

showList :: [Decision] -> ShowS

NFData Decision

Methods

rnf :: Decision -> ()

showTrace :: Trace -> String

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.

preEmpCount :: [(Decision, ThreadAction)] -> (Decision, Lookahead) -> Int

Count the number of pre-emptions in a schedule prefix.

Commit threads complicate this a bit. Conceptually, commits are happening truly in parallel, nondeterministically. The commit thread implementation is just there to unify the two sources of nondeterminism: commit timing and thread scheduling.

SO, we don't count a switch TO a commit thread as a preemption. HOWEVER, the switch FROM a commit thread counts as a preemption if it is not to the thread that the commit interrupted.

Failures

data Failure

An indication of how a concurrent computation failed.

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

An uncaught exception bubbled to the top of the computation.

IllegalSubconcurrency

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

Instances

Bounded Failure

Methods

minBound :: Failure

maxBound :: Failure

Enum Failure

Methods

succ :: Failure -> Failure

pred :: Failure -> Failure

toEnum :: Int -> Failure

fromEnum :: Failure -> Int

enumFrom :: Failure -> [Failure]

enumFromThen :: Failure -> Failure -> [Failure]

enumFromTo :: Failure -> Failure -> [Failure]

enumFromThenTo :: Failure -> Failure -> Failure -> [Failure]

Eq Failure

Methods

(==) :: Failure -> Failure -> Bool

(/=) :: Failure -> Failure -> Bool

Ord Failure

Methods

compare :: Failure -> Failure -> Ordering

(<) :: Failure -> Failure -> Bool

(<=) :: Failure -> Failure -> Bool

(>) :: Failure -> Failure -> Bool

(>=) :: Failure -> Failure -> Bool

max :: Failure -> Failure -> Failure

min :: Failure -> Failure -> Failure

Read Failure

Methods

readsPrec :: Int -> ReadS Failure

readList :: ReadS [Failure]

readPrec :: ReadPrec Failure

readListPrec :: ReadPrec [Failure]

Show Failure

Methods

showsPrec :: Int -> Failure -> ShowS

show :: Failure -> String

showList :: [Failure] -> ShowS

NFData Failure

Methods

rnf :: Failure -> ()

showFail :: Failure -> String

Pretty-print a failure

Memory models

data MemType

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

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.

Instances

Bounded MemType

Methods

minBound :: MemType

maxBound :: MemType

Enum MemType

Methods

succ :: MemType -> MemType

pred :: MemType -> MemType

toEnum :: Int -> MemType

fromEnum :: MemType -> Int

enumFrom :: MemType -> [MemType]

enumFromThen :: MemType -> MemType -> [MemType]

enumFromTo :: MemType -> MemType -> [MemType]

enumFromThenTo :: MemType -> MemType -> MemType -> [MemType]

Eq MemType

Methods

(==) :: MemType -> MemType -> Bool

(/=) :: MemType -> MemType -> Bool

Ord MemType

Methods

compare :: MemType -> MemType -> Ordering

(<) :: MemType -> MemType -> Bool

(<=) :: MemType -> MemType -> Bool

(>) :: MemType -> MemType -> Bool

(>=) :: MemType -> MemType -> Bool

max :: MemType -> MemType -> MemType

min :: MemType -> MemType -> MemType

Read MemType

Methods

readsPrec :: Int -> ReadS MemType

readList :: ReadS [MemType]

readPrec :: ReadPrec MemType

readListPrec :: ReadPrec [MemType]

Show MemType

Methods

showsPrec :: Int -> MemType -> ShowS

show :: MemType -> String

showList :: [MemType] -> ShowS

NFData MemType

Methods

rnf :: MemType -> ()