dejafu

A library for unit-testing concurrent programs.

https://github.com/barrucadu/dejafu

Version on this page:1.0.0.1
LTS Haskell 22.17:2.4.0.5
Stackage Nightly 2024-04-14:2.4.0.5
Latest on Hackage:2.4.0.5

See all snapshots dejafu appears in

MIT licensed by Michael Walker
Maintained by [email protected]
This version can be pinned in stack with:dejafu-1.0.0.1@sha256:cc07bdcece726fb581fc4abf0275e1b535a79823dbb548b87694e6c2e29592f5,2868

Module documentation for 1.0.0.1

Used by 2 packages in nightly-2018-02-11(full list with versions):
hunit-dejafu, tasty-dejafu

dejafu

[Déjà Fu is] A martial art in which the user’s limbs move in time as well as space, […] It is best described as “the feeling that you have been kicked in the head this way before”

– Terry Pratchett, Thief of Time

Déjà Fu is a unit-testing library for concurrent Haskell programs. Tests are deterministic and expressive, making it easy and convenient to test your threaded code. Available on GitHub, Hackage, and Stackage.

Installation

Install from Hackage globally:

$ cabal install dejafu

Or add it to your cabal file:

build-depends: ...
             , dejafu

Or to your package.yaml:

dependencies:
  ...
  - dejafu

Quick start guide

Déjà Fu supports unit testing, and comes with a helper function called autocheck to look for some common issues. Let’s see it in action:

import Control.Concurrent.Classy

myFunction :: MonadConc m => m String
myFunction = do
  var <- newEmptyMVar
  fork (putMVar var "hello")
  fork (putMVar var "world")
  readMVar var

That MonadConc is a typeclass abstraction over concurrency, but we’ll get onto that shortly. First, the result of testing:

> autocheck myFunction
[pass] Never Deadlocks
[pass] No Exceptions
[fail] Consistent Result
        "hello" S0----S1--S0--

        "world" S0----S2--S0--
False

There are no deadlocks or uncaught exceptions, which is good; but the program is (as you probably spotted) nondeterministic!

Along with each result, Déjà Fu gives us a representative execution trace in an abbreviated form. Sn means that thread n started executing, and Pn means that thread n pre-empted the previously running thread.

Why Déjà Fu?

Testing concurrent programs is difficult, because in general they are nondeterministic. This leads to people using work-arounds like running their testsuite many thousands of times; or running their testsuite while putting their machine under heavy load.

These approaches are inadequate for a few reasons:

  • How many runs is enough? When you are just hopping to spot a bug by coincidence, how do you know to stop?
  • How do you know if you’ve fixed a bug you saw previously? Because the scheduler is a black box, you don’t know if the previously buggy schedule has been re-run.
  • You won’t get that much scheduling variety! Operating systems and language runtimes like to run threads for long periods of time, which reduces the variety you get (and so drives up the number of runs you need).

Déjà Fu addresses these points by offering complete testing. You can run a test case and be guaranteed to find all results with some bounds. These bounds can be configured, or even disabled! The underlying approach used is smarter than merely trying all possible executions, and will in general explore the state-space quickly.

If your test case is just too big for complete testing, there is also a random scheduling mode, which is necessarily incomplete. However, Déjà Fu will tend to produce much more schedule variety than just running your test case in IO the same number of times, and so bugs will tend to crop up sooner. Furthermore, as you get execution traces out, you can be certain that a bug has been fixed by simply following the trace by eye.

Contributing

Bug reports, pull requests, and comments are very welcome!

Feel free to contact me on GitHub, through IRC (#haskell on freenode), or email ([email protected]).

Changes

Release Notes

All notable changes to this project will be documented in this file.

This project is versioned according to the Package Versioning Policy, the de facto standard Haskell versioning scheme.

1.0.0.1

Miscellaneous

  • The upper bound on concurrency was bumped to <1.5.

1.0.0.0

Test.DejaFu

  • All testing functions now require a MonadConc, MonadRef, and MonadIO constraint:

    It is no longer possible to test things in ST.

  • All testing functions now take the action to test as the last parameter.

  • The autocheckIO, dejafuIO, dejafusIO, autocheckWayIO, dejafuWayIO, dejafusWayIO, dejafuDiscardIO, runTestM, and runTestWayM functions are now gone.

  • The Predicate type has been replaced with a more general ProPredicate type which is a profunctor and (b) can discard results not needed to determine if the predicate passes. (#124)

    All testing functions have been generalised to take a ProPredicate instead. The Predicate a type remains as an alias for ProPredicate a a. Passing tests have their resident memory usage significantly decreased.

  • The Result type no longer includes a number of cases checked, as this is not meaningful with predicates including discard functions.

  • New alwaysNothing and somewhereNothing functions, like alwaysTrue and somewhereTrue, to lift functions to ProPredicates.

  • The alwaysTrue2 function is gone, as its behaviour was unintuitive and easy to get wrong, and has been replaced with new alwaysSameOn and alwaysSameBy predicates, which generalise alwaysSame.

  • The alwaysSame, alwaysSameOn, and alwaysSameBy predicates now gives the simplest execution trace leading to each distinct result.

Test.DejaFu.Common

  • This module has been split up into new Test.DejaFu.Internal, Types, and Utils modules. (#155)

  • New ForkOS and IsCurrentThreadBound thread actions. (#126)

  • New WillForkOS and WillIsCurrentThreadBound lookaheads. (#126)

  • The TTrace type synonym for [TAction] has been removed.

  • The preEmpCount function has been removed.

  • New functions strengthenDiscard and weakenDiscard to combine discard functions.

  • The Discard type is now defined here and re-exported from Test.DejaFu.SCT.

  • The ThreadId, CRefId, MVarId, and TVarId types are now newtypes over a common Id type. (#137)

Test.DejaFu.Conc

  • The ConcST type alias is gone.

  • The MonadBase IO ConcIO instance is gone.

  • The MonadIO ConcIO instance is replaces with a more general MonadIO n => MonadIO (ConcT r n) instance.

  • The runConcurrent function now has a MonadConc constraint.

  • If bound threads are supported, the main thread when testing is bound. (#126)

  • Each entry in an execution trace is now in the form (decision, alternatives, action). The chosen thread is no longer in the list of alternatives, which makes raw traces easier to read. (#121)

  • Due to changes in Test.DejaFu.Schedule, no longer re-exports Decision, NonEmpty, tidOf, or decisionOf.

Test.DejaFu.Refinement

  • A blocking interference function is no longer reported as a deadlocking execution.

Test.DejaFu.Schedule

  • No longer re-exports Decision or NonEmpty.

  • The tidOf and decisionOf functions have moved to Test.DejaFu.Utils.

Test.DejaFu.SCT

  • All testing functions now require a MonadConc constraint:

    It is no longer possible to test things in ST.

Test.DejaFu.STM

  • This is now an internal module. (#155)

Performance

  • Significant resident memory reduction for most passing tests.
  • Improved dependency detection for MVar actions, leading to fewer executions.

Miscellaneous

  • The minimum supported version of concurrency is now 1.3.0.0.

0.9.1.2

Miscellaneous

  • The upper bound on leancheck was bumped to <0.8.

0.9.1.1

Miscellaneous

  • Fix an issue where nested masks nested inside unmasks would sometimes not be pre-empted in systematic testing.

0.9.1.0

Test.DejaFu.Common

  • Fix some incorrect “@since” haddock comments.
  • Pretty-printed traces now display a pre-emption following a yield with a little “p”.

Test.DejaFu.Conc

  • Add a missing MonadFail instance.

Test.DejaFu.STM

  • Add a missing MonadFail instance.

0.9.0.3

Miscellaneous

  • Impose a dependency between commits and memory barriers, to make barriers sound (#138).

0.9.0.2

Miscellaneous

  • Small improvement to dependency detection of STM transactions.
  • A fair bound of 0 will now prevent all yields.

0.9.0.1

Miscellaneous

  • Fixed an issue where tests with exception handlers would sometimes skip over nested handlers or try to take the tail of an empty list (#139 and #141).

0.9.0.0

Test.DejaFu.Common

  • New isInternalError, isAbort, isDeadlock, isUncaughtException, and isIllegalSubconcurrency functions for matching failure types. Also exported from Test.DejaFu.

  • The UncaughtException Failure constructor now includes the exception.

    The Read, Enum, and Bounded instances are gone. The Eq, Ord, and NFData instances use the show of the exception. Pretty-printed failures include the exception text.

  • New ThreadDelay and WillThreadDelay constructors in ThreadAction and Lookahead. Uses of threadDelay are no longer reported as a use of yield.

0.8.0.0

Test.DejaFu.Common

  • Execution traces now only include a single item of lookahead (#120).
  • STM traces now include IDs of created TVars (#80).

Test.DejaFu.Schedule

  • Schedulers no longer take the execution trace so far (#106).
  • The Scheduler type is now a newtype (#122).

0.7.3.0

Test.DejaFu.Common

  • A new function threadNames, to get all named threads from a trace.

Miscellaneous

  • Escaping a mask by raising an exception now correctly restores the masking state (#118).
  • Named threads which are only started by a pre-emption now show up in the trace (#101).

0.7.2.0

Test.DejaFu.STM

  • The STM n r monad now has Alternative and MonadPlus instances, using orElse for the binary operation and retry for the unit.

Miscellaneous

  • The Eq instance for ThreadId, CRefId, MVarId, and TVarId now only compares the numbers, not the names.

    This makes it consistent with the Ord instances, and is also a small performance gain.

  • Now compatible with concurrency-1.2.0.0.

0.7.1.3

Miscellaneous

  • Aborted STM transactions are now rolled back correctly (issue #111).
  • Slightly improved run-time of systematic testing.

0.7.1.2

Miscellaneous

  • Errors thrown with Control.Monad.fail no longer terminate testing, and are now correctly treated as asynchronous exceptions.

0.7.1.1

Miscellaneous

  • Significantly reduced memory usage in systematic testing when discarding traces.

    Previously this was O(max trace length * number of executions)

    Now it’s O(max trace length + total size of traces kept)

0.7.1.0

Test.DejaFu

  • Exposed the new SCT discard functions through dejafuDiscard and dejafuDiscardIO.

    There are no dejafusDiscard and dejafusDiscardIO functions because this would probably be confusing, as the traces are shared.

  • The Discard type and defaultDiscard function are also exposed.

Test.DejaFu.Defaults

  • Added a new defaultDiscarder function, which discards nothing.

Test.DejaFu.SCT

  • Added new SCT functions to selectively discard results or traces, which can be a significant memory saving if you know what sorts of results you are interested in:
    • New type: Discard.
    • New functions: runSCTDiscard, resultsSetDiscard, sctBoundDiscard, sctUniformRandomDiscard, and sctWeightedRandomDiscard.
    • resultsSet and resultsSet' now discard traces as they are produced, rather than all at the end, greatly improving performance when traces are large.

0.7.0.2

Test.DejaFu.Refinement

  • Removed unnecessary typeclass constraints from check, check', checkFor, and counterExamples.

Miscellaneous

0.7.0.1

Test.DejaFu.Refinement

  • check, check', and checkFor are now faster if there are multiple counterexamples.
  • The above and counterExamples are now faster even if there is only a single counterexample in some cases.

0.7.0.0

Test.DejaFu

  • The new Test.DejaFu.Defaults and Test.DejaFu.Refinement modules are re-exported.
  • The new smart constructors from Test.DejaFu.SCT are exported.

Test.DejaFu.Defaults

  • The default* values are now defined in the new Test.DejaFu.Defaults module. There is no breaking API change as they are re-exported from Test.DejaFu.

Test.DejaFu.Refinement

  • A new module for checking observational properties of the side-effects of stateful, concurrent functions.

    This is related to my work on CoCo, allowing dejafu to test what CoCo discovers.

Test.DejaFu.SCT

  • The Way type is now abstract and exposes smart constructor functions:
    • systematically, corresponding to the old Systematically.
    • randomly, corresponding to the old Randomly,
    • uniformly, a new uniform random (as opposed to weighted random) scheduler.
    • swarmy, corresponding to the old Randomly and specifying how many executions to use the same weights for.
  • A new sctUniformRandom function to do uniform (non-weighted) scheduling.
  • The sctRandom function is now called sctWeightedRandom and can now re-use the same weights for multiple executions.
  • The sctPreBound, sctFairBound, and sctLengthBound functions have been removed.

Fixed

  • An issue where subconcurrency would re-use MVar IDs, leading to false reports of deadlock on occasion (issue #81).

0.6.0.0

Test.DejaFu.Conc

  • The Conc n r a type is now ConcT r n a, and has been given a MonadTrans instance. Uses of lift appear in the execution trace in the same way as liftBase and liftIO.
    • The ConcIO and ConcST aliases have been updated, so this should be an invisible change to most users.

Test.DejaFu.SCT

  • Way is now a GADT, no longer taking a type parameter. This greatly improves type inference when the Systematically constructor is used.
    • The NFData instance for Way is now gone. The alternative was requiring that any RandomGen used also implement NFData, which is very restrictive

Miscellaneous

  • There is now a changelog.
  • Test.DejaFu.Common is now considered to form part of the public API of the library.
  • Every definition and instance now has a Haddock “@since” annotation.

0.5.1.3

Miscellaneous

  • The version range on the concurrency package has been changed to 1.1.*.

0.5.1.2

This version was misnumbered! It should have caused a minor version bump!

Test.DejaFu.Conc

  • New MonadRef and MonadAtomicRef instances for the Conc type using CRef.

Fixed

  • A long-standing bug where if the main thread is killed with a throwTo, the throwing neither appears in the trace nor correctly terminates the execution.

Miscellaneous

  • The maximum supported version of the concurrency package has been changed to 1.1.1.*.

0.5.1.1

Fixed

  • The correct scheduler state is now passed to the scheduler immediately after the termination of a subconcurrency action.
  • SCT of subconcurrency no longer loops infinitely.

0.5.1.0

Test.DejaFu

  • A new NFData instance for Result.

Test.DejaFu.Common

  • New instances:
    • NFData for ThreadId, CRefId, MVarId, TVarId, IdSource, ThreadAction, Lookahead, ActionType, TAction, Decision, Failure, and MemType.
    • Eq, Ord, and Show instances for IdSource.

Test.DejaFu.SCT

  • New NFData instances for Way, Bounds, PreemptionBound, FairBound, and LengthBound.
  • New strict variants of runSCT and resultsSet: runSCT' and resultsSet'.

Test.DejaFu.STM

  • A new NFData instance for Result.

0.5.0.2

This version was misnumbered! It should have caused a major version bump!

Test.DejaFu.Common

  • A new StopSubconcurrency constructor of ThreadAction.

Changed

  • A StopConcurrency action appears in the execution trace immediately after the end of a subconcurrency action (much like the PopCatching and ResetMasking actions which appear after a catch and mask).
  • A subconcurrency action now inherits the number of capabilities from the outer computation, rather than being reset to 2 as before.

Miscellaneous

  • Test.DejaFu.SCT now compiles with MonoLocalBinds enabled (implied by GADTs and TypeFamilies), which may be relevant to hackers.

0.5.0.1

  • Date 2017-02-21
  • Git tag dejafu-0.5.0.1
  • This version was never pushed to hackage, whoops!

Fixed

  • readMVar is once again considered a “release action” for the purposes of fair-bounding.

0.5.0.0

Test.DejaFu

  • All the functions which did take a Bounds now take a Way instead and support random scheduling as well.

Test.DejaFu.Common

  • New Eq instances for ThreadAction and Lookahead.
  • A TryReadMVar constructor for ThreadAction and a corresponding WillTryReadMVar constructor for Lookahead.

Test.DejaFu.Conc

  • A new testing-only subconcurrency function, to run a concurrent action and do something with its result in the same concurrent context, even if it fails.

Test.DejaFu.SCT

  • An sctRandom function to run a fixed number of randomly-scheduled executions of a program.
  • The Way type, to abstract over how to run a concurrent program, used by new functions runSCT and resultsSet.

Fixed

  • Some previously-missed CRef action dependencies are no longer missed.

Miscellaneous

  • The supported version of the concurrency package was bumped to 1.1.0.0, introducing tryReadMVar.
  • A bunch of things were called “Var” or “Ref”, these are now consistently “MVar” and “CRef”.
  • Significant performance improvements in both time and space.
  • The dpor package has been merged back into this, as it turned out not to be very generally useful. There is no direct replacement, but I have no intent to update it, so the dpor package is now deprecated.

0.4.0.0

Test.DejaFu

  • The autocheck' function now takes the schedule bounds as a parameter.
  • New runTestM and runTestM' functions, monad-polymorphic variants of the now-removed runTestIO and runTestIO' functions.

Test.DejaFu.Conc

  • The Conc type no longer has the STM type as a parameter.
  • A new runConcurrent function, a monad-polymorphic version of the now-removed runConcST and runConcIO functions.

Test.DejaFu.SCT

  • The ST-specific functions are now monad-polymorphic.
  • The IO function variants have been removed.

Test.DejaFu.STM

  • A new runTransaction function, a monad-polymorphic version of the now-removed runTransactionST and runTransactionIO functions.

Changed

  • The termination of the main thread in execution traces now appears as a single Stop, rather than the sequence Lift, Stop.
  • Execution traces printed by the helpful functions in Test.DejaFu now include a key of thread names.

Miscellaneous

  • Remodularisation:
    • The Control.* modules have all been split out into a separate “concurrency” package.
    • Many definitions from other modules have been moved to the new Test.DejaFu.Common module.
    • The Test.DejaFu.Deterministic module has been renamed to Test.DejaFu.Conc

0.3.2.1

Fixed

  • The implementation of the STM orElse for STMLike incorrectly handled some state non-associatively, leading to false deadlocks being reported in some cases.

0.3.2.0

Builds with both dpor-0.1 and dpor-0.2, however some improvements require dpor-0.2.

Fixed

  • (faster with dpor-0.2) Executions missed due to daemon threads with uninteresting first actions are no longer missed.

Changed

  • (requires dpor-0.2) Significantly improved dependency inference of exceptions, greatly improving performance of testcases using exceptions.
  • Significantly improved dependency inference of STM transactions, greatly improving performance of testcases using STM.

0.3.1.1

Miscellaneous

  • Now supports GHC 8.

0.3.1.0

Fixed

  • Context switches around relaxed memory commit actions could cause the number of pre-emptions in an execution to be miscounted, leading to the pre-emption bounding being too lenient.

0.3.0.0

The minimum supported version of GHC is now 7.10.

I didn’t write proper release notes, and this is so far back I don’t really care to dig through the logs.

0.2.0.0

I didn’t write proper release notes, and this is so far back I don’t really care to dig through the logs.

0.1.0.0

Initial release. Go read the API docs.