-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Abstract, parameterized interface to mutable Deques.
--   
--   An abstract interface to highly-parameterizable queues/deques.
--   
--   Background: There exists a feature space for queues that extends
--   between:
--   
--   
--   
- simple, single-ended, non-concurrent, bounded queues
--   
- double-ended, threadsafe, growable queues
--   
--   
--   ... with important points inbetween (such as the queues used for
--   work-stealing).
--   
--   This package includes an interface for Deques that allows the
--   programmer to use a single API for all of the above, while using the
--   type-system to select an efficient implementation given the
--   requirements (using type families).
--   
--   This package also includes a simple reference implementation based on
--   IORef and Data.Sequence.
@package abstract-deque
@version 0.3

-- | An abstract, parameterizable interface for queues.
--   
--   This interface includes a non-associated type family for Deques plus
--   separate type classes encapsulating the Deque operations. That is, we
--   separate type selection (type family) from function overloading
--   (vanilla type classes).
--   
--   This design strives to hide the extra phantom-type parameters from the
--   Class constraints and therefore from the type signatures of client
--   code.
module Data.Concurrent.Deque.Class

-- | A family of Deques implementations. A concrete Deque implementation is
--   selected based on the (phantom) type parameters, which encode several
--   choices.
--   
--   For example, a work stealing deque is threadsafe only on one end and
--   supports push/pop on one end (and pop-only) on the other:
--   
--   
--   > (Deque NT T  D S Grow elt)
--   
--   
--   Note, however, that the above example is overconstraining in many
--   situations. It demands an implementation which is NOT threadsafe on
--   one end and does NOT support push on one end, whereas both these
--   features would not hurt, if present.
--   
--   Thus when accepting a queue as input to a function you probably never
--   want to overconstrain by demanding a less-featureful option.
--   
--   For example, rather than (Deque NT D T S Grow elt) You would
--   probably want: (Deque nt D T s Grow elt)
type family Deque lThreaded rThreaded lDbl rDbl bnd safe elt

-- | Haskell IO threads (Control.Concurrent) may concurrently access
--   this end of the queue. Note that this attribute is set separately for
--   the left and right ends.
data Threadsafe

-- | Only one thread at a time may access this end of the queue.
data Nonthreadsafe

-- | This end of the queue provides push-only (left) or pop-only (right)
--   functionality. Thus a SingleEnd / SingleEnd combination
--   is what is commonly referred to as a single ended queue,
--   whereas DoubleEnd / DoubleEnd is a double ended
--   queue. Heterogeneous combinations are sometimes colloquially
--   referred to as "1.5 ended queues".
data SingleEnd

-- | This end of the queue supports both push and pop.
data DoubleEnd

-- | The queue has bounded capacity.
data Bound

-- | The queue can grow as elements are added.
data Grow

-- | The queue will not duplicate elements.
data Safe

-- | Pop operations may possibly duplicate elements. Hopefully with low
--   probability!
data Dup
type S = SingleEnd
type D = DoubleEnd
type NT = Nonthreadsafe
type T = Threadsafe

-- | A traditional single-threaded, single-ended queue.
type Queue a = Deque Nonthreadsafe Nonthreadsafe SingleEnd SingleEnd Grow Safe a

-- | A concurrent queue.
type ConcQueue a = Deque Threadsafe Threadsafe SingleEnd SingleEnd Grow Safe a

-- | A concurrent deque.
type ConcDeque a = Deque Threadsafe Threadsafe DoubleEnd DoubleEnd Grow Safe a

-- | Work-stealing deques (1.5 ended). Typically the worker pushes and pops
--   its own queue (left) whereas thieves only pop (right).
type WSDeque a = Deque Nonthreadsafe Threadsafe DoubleEnd SingleEnd Grow Safe a

-- | Class encompassing the basic queue operations that hold for all
--   single, 1.5, and double ended modes. We arbitrarily call the ends
--   "left" and "right" and choose the natural operations to be pushing on
--   the left and popping on the right.
class DequeClass (d :: Type -> Type)

-- | Create a new deque. Most appropriate for unbounded deques. If bounded,
--   the size is unspecified.
newQ :: DequeClass d => IO (d elt)

-- | Is the queue currently empty? Beware that this can be a highly
--   transient state.
nullQ :: DequeClass d => d elt -> IO Bool

-- | Natural push: push onto the left end of the deque.
pushL :: DequeClass d => d elt -> elt -> IO ()

-- | Natural pop: pop from the right end of the deque.
tryPopR :: DequeClass d => d elt -> IO (Maybe elt)

-- | Runtime indication of thread saftey for pushL (and
--   popL). (Argument unused.)
leftThreadSafe :: DequeClass d => d elt -> Bool

-- | Runtime indication of thread saftey for tryPopR (and
--   pushR). (Argument unused.)
rightThreadSafe :: DequeClass d => d elt -> Bool
class DequeClass d => PopL (d :: Type -> Type)

-- | PopL is not the native operation for the left end, so it requires that
--   the left end be a DoubleEnd, but places no other requirements
--   on the input queue.
tryPopL :: PopL d => d elt -> IO (Maybe elt)
class DequeClass d => PushR (d :: Type -> Type)

-- | Pushing is not the native operation for the right end, so it requires
--   that end be a DoubleEnd.
pushR :: PushR d => d elt -> elt -> IO ()
class DequeClass d => BoundedL (d :: Type -> Type)

-- | Create a new, bounded deque with a specified capacity.
newBoundedQ :: BoundedL d => Int -> IO (d elt)

-- | For a bounded deque, pushing may fail if the deque is full.
tryPushL :: BoundedL d => d elt -> elt -> IO Bool
class PushR d => BoundedR (d :: Type -> Type)

-- | For a bounded deque, pushing may fail if the deque is full.
tryPushR :: BoundedR d => d elt -> elt -> IO Bool

-- | This module provides a wrapper around a deque that can enforce
--   additional invariants at runtime for debugging purposes.
module Data.Concurrent.Deque.Debugger

-- | Warning, this enforces the excessively STRONG invariant that if any
--   end of the deque is non-threadsafe then it may ever only be touched by
--   one thread during its entire lifetime.
--   
--   This extreme form of monagamy is easier to verify, because we don't
--   have enough information to know if two operations on different threads
--   are racing with one another or are properly synchronized.
--   
--   The wrapper data structure has two IORefs to track the last thread
--   that touched the left and right end of the deque, respectively.
data DebugDeque (d :: Type -> Type) elt
DebugDeque :: (IORef (Maybe ThreadId), IORef (Maybe ThreadId)) -> d elt -> DebugDeque (d :: Type -> Type) elt
instance Data.Concurrent.Deque.Class.DequeClass d => Data.Concurrent.Deque.Class.DequeClass (Data.Concurrent.Deque.Debugger.DebugDeque d)
instance Data.Concurrent.Deque.Class.PopL d => Data.Concurrent.Deque.Class.PopL (Data.Concurrent.Deque.Debugger.DebugDeque d)

-- | A strawman implementation of concurrent Dequeues. This implementation
--   is so simple that it also makes a good reference implementation for
--   debugging.
--   
--   The queue representation is simply an IORef containing a
--   Data.Sequence.
--   
--   Also see Data.Concurrent.Deque.Reference.DequeInstance. By
--   convention a module of this name is also provided.
module Data.Concurrent.Deque.Reference

-- | Stores a size bound (if any) as well as a mutable Seq.
data SimpleDeque elt
DQ :: {-# UNPACK #-} !Int -> !IORef (Seq elt) -> SimpleDeque elt
newQ :: IO (SimpleDeque elt)
nullQ :: SimpleDeque elt -> IO Bool
newBoundedQ :: Int -> IO (SimpleDeque elt)
pushL :: SimpleDeque t -> t -> IO ()
pushR :: SimpleDeque t -> t -> IO ()
tryPopR :: SimpleDeque a -> IO (Maybe a)
tryPopL :: SimpleDeque a -> IO (Maybe a)
tryPushL :: SimpleDeque a -> a -> IO Bool
tryPushR :: SimpleDeque a -> a -> IO Bool
_is_using_CAS :: Bool
instance Data.Concurrent.Deque.Class.BoundedL Data.Concurrent.Deque.Reference.SimpleDeque
instance Data.Concurrent.Deque.Class.BoundedR Data.Concurrent.Deque.Reference.SimpleDeque
instance Data.Concurrent.Deque.Class.DequeClass Data.Concurrent.Deque.Reference.SimpleDeque
instance Data.Concurrent.Deque.Class.PopL Data.Concurrent.Deque.Reference.SimpleDeque
instance Data.Concurrent.Deque.Class.PushR Data.Concurrent.Deque.Reference.SimpleDeque

-- | By convention, every provider of the
--   Data.Concurrent.Deque.Class interface optionally provides a
--   module that provides the relevant instances of the Deque type
--   class, covering the [maximum] portion of the configuration space that
--   the implementation is able to handle.
--   
--   This is kept in a separate package because importing instances is
--   unconditional and the user may well want to assemble their own
--   combination of Deque instances to cover the configuration
--   space.
module Data.Concurrent.Deque.Reference.DequeInstance
