packages feed

reflex-0.10.0.0: src/Data/WeakBag.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ScopedTypeVariables #-}

-- | This module defines the 'WeakBag' type, which represents a mutable
-- collection of items that does not cause the items to be retained in memory.
-- This is useful for situations where a value needs to be inspected or modified
-- if it is still alive, but can be ignored if it is dead.
module Data.WeakBag
  ( WeakBag
  , WeakBagTicket
  , empty
  , insert
  , isEmpty
  , traverse
  , traverse_
  , traverseWeakIntMap_
  , remove
  ) where

import Control.Exception
import Control.Monad.IO.Class
import Data.Functor (void)
import Data.IORef
import Data.IntMap.Internal (IntMap (Nil, Tip))
import qualified Data.IntMap.Internal as IntMap.Internal
import qualified Data.IntMap.Strict as IntMap
import Prelude hiding (traverse)
#if MIN_VERSION_base(4,13,0)
import GHC.IORef (atomicModifyIORef'_)
#endif
import System.Mem.Weak

-- | A 'WeakBag' holds a set of values of type @/a/@, but does not retain them -
-- that is, they can still be garbage-collected.  As long as the @/a/@ values remain
-- alive, the 'WeakBag' will continue to refer to them.
data WeakBag a = WeakBag
  { _weakBag_nextId :: {-# UNPACK #-} !(IORef Int) -- TODO: what if this wraps around?
  , _weakBag_children :: {-# UNPACK #-} !(IORef (IntMap (Weak a)))
  -- ^ The items referenced by the WeakBag
  }

-- | When inserting an item into a 'WeakBag', a 'WeakBagTicket' is returned.  If
-- the caller retains the ticket, the item is guranteed to stay in memory (and
-- thus in the 'WeakBag').  The ticket can also be used to remove the item from
-- the 'WeakBag' prematurely (i.e. while it is still alive), using 'remove'.
data WeakBagTicket = forall a. WeakBagTicket
  { _weakBagTicket_weakItem :: {-# UNPACK #-} !(Weak a)
  , _weakBagTicket_item :: {-# NOUNPACK #-} !a
  }

-- | Insert an item into a 'WeakBag'. The removal of the item, by garbage
-- collection or by 'remove', deletes it from the bag.
{-# INLINE insert #-}
insert :: a -> WeakBag a -> IO WeakBagTicket
insert a (WeakBag nextId children) =
  {-# SCC "insert" #-}
  do
    a' <- evaluate a
    myId <- atomicModifyIORef' nextId $ \n -> (succ n, n)
    wa <- mkWeakPtr a' $ Just $ void $ atomicModifyIORef'_ children $ IntMap.delete myId
    void $ atomicModifyIORef'_ children $ IntMap.insert myId wa
    return $
      WeakBagTicket
        { _weakBagTicket_weakItem = wa
        , _weakBagTicket_item = a'
        }

#if !MIN_VERSION_base(4,13,0)
-- | 'GHC.IORef.atomicModifyIORef'_', which base < 4.13 does not have.
atomicModifyIORef'_ :: IORef a -> (a -> a) -> IO (a, a)
atomicModifyIORef'_ ref f = atomicModifyIORef' ref $ \old -> let !new = f old in (new, (old, new))
#endif

-- | Create an empty 'WeakBag'.
{-# INLINE empty #-}
empty :: IO (WeakBag a)
empty =
  {-# SCC "empty" #-}
  do
    nextId <- newIORef 1
    children <- newIORef IntMap.empty
    let bag =
          WeakBag
            { _weakBag_nextId = nextId
            , _weakBag_children = children
            }
    return bag

-- | Whether the bag has no entry. The entry of an item that the garbage
-- collector removed is deleted by the finalizer of the item's weak pointer, so
-- the bag can be non-empty for a while after its last live item is gone.
{-# INLINE isEmpty #-}
isEmpty :: WeakBag a -> IO Bool
isEmpty (WeakBag _ children) = {-# SCC "isEmpty" #-} IntMap.null <$> readIORef children

{-# INLINE traverse_ #-}

-- | Visit every node in the given list.  If new nodes are appended during the
-- traversal, they will not be visited.  Every live node that was in the list
-- when the traversal began will be visited exactly once; however, no guarantee
-- is made about the order of the traversal.
traverse_ :: forall a m. MonadIO m => WeakBag a -> (a -> m ()) -> m ()
traverse_ (WeakBag _ children) f =
  {-# SCC "traverse" #-}
  do
    cs <- liftIO $ readIORef children
    traverseWeakIntMap_ cs f

{-# INLINE traverseWeakIntMap_ #-}
traverseWeakIntMap_ :: forall a m. MonadIO m => IntMap (Weak a) -> (a -> m ()) -> m ()
traverseWeakIntMap_ items f = go items
  where
    -- This is a very hot function in Reflex and directly recursing over the
    -- internal data structure is a noticable improvement over using forM_:
    go :: IntMap (Weak a) -> m ()
    go (IntMapBin l r) = go l >> go r
    go (Tip _ c) = mapM_ f =<< liftIO (deRefWeak c)
    go Nil = pure ()

pattern IntMapBin :: IntMap a -> IntMap a -> IntMap a
#if MIN_VERSION_containers(0,8,0)
pattern IntMapBin l r <- IntMap.Internal.Bin _ l r
#else
pattern IntMapBin l r <- IntMap.Internal.Bin _ _ l r
#endif

{-# COMPLETE IntMapBin, Tip, Nil #-}

{-# DEPRECATED traverse "Use 'traverse_' instead" #-}
traverse :: MonadIO m => WeakBag a -> (a -> m ()) -> m ()
traverse = traverse_

-- | Remove an item from the 'WeakBag'; does nothing if invoked multiple times
-- on the same 'WeakBagTicket'.
{-# INLINE remove #-}
remove :: WeakBagTicket -> IO ()
remove (WeakBagTicket w _) = {-# SCC "remove" #-} finalize w

-- TODO: Should 'remove' also drop the reference to the item?

-- TODO: can/should we provide a null WeakBagTicket?