packages feed

reflex-0.10.0.0: src/Reflex/Spider/Height.hs

{-# LANGUAGE CPP #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}

module Reflex.Spider.Height
  ( Height
  , pattern ZeroHeight
  , pattern InvalidHeight
  , invalidHeightBeingTraversed
  , isUnmarkedInvalidHeight
  , pattern ValidHeight
  , zeroHeight
  , invalidHeight
  , maxHeight
  , raiseHeight
  , coincidenceHeight
  , compareHeight
  , heightSlotPassed
  , HeightBag
  , heightBagEmpty
  , heightBagHeight
  , heightBagParentCount
  , heightBagAddParent
  , heightBagRemoveParent
  , heightBagInvalidateParent
  , heightBagRecalculateParent
  , heightBagSuccHeight
  , HeightQueue
  , heightQueueEmpty
  , heightQueueInsert
  , heightQueueNext
  ) where

import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
#if !MIN_VERSION_base(4,20,0)
import Data.List (foldl')
#endif

--------------------------------------------------------------------------------
-- Height data
--------------------------------------------------------------------------------

debugCycles :: Bool
#ifdef DEBUG_CYCLES
debugCycles = True
#else
debugCycles = False
#endif

newtype Height = Height Int
  deriving (Show)

{-# INLINE unsafeHeightAsInt #-}
unsafeHeightAsInt :: Height -> Int
unsafeHeightAsInt (Height h) = h

pattern ZeroHeight :: Height
pattern ZeroHeight = Height 0

pattern InvalidHeight :: Height
pattern InvalidHeight <- (isInvalidHeight -> True)
  where
    InvalidHeight = Height (-1000)

{-# INLINE isInvalidHeight #-}
isInvalidHeight :: Height -> Bool
isInvalidHeight (Height h) = h == (-1000) || debugCycles && h == (-1001)

isUnmarkedInvalidHeight :: Height -> Bool
isUnmarkedInvalidHeight (Height h) = h == (-1000)

pattern ValidHeight :: Height
pattern ValidHeight <- Height ((>= 0) -> True)

pattern UnsafeValidHeight :: Int -> Height
pattern UnsafeValidHeight n <- Height (\x -> if x >= 0 then Just x else Nothing -> Just n)

{-# INLINE zeroHeight #-}
zeroHeight :: Height
zeroHeight = Height 0

{-# INLINE invalidHeight #-}
invalidHeight :: Height
invalidHeight = Height (-1000)

{-# INLINE maxHeight #-}
maxHeight :: Height
maxHeight = Height maxBound

-- | An invalid height that is currently being traversed, e.g. by walkInvalidHeightParents
{-# INLINE invalidHeightBeingTraversed #-}
invalidHeightBeingTraversed :: Height
invalidHeightBeingTraversed = Height (-1001)

{-# COMPLETE InvalidHeight, ValidHeight #-}
{-# COMPLETE InvalidHeight, UnsafeValidHeight #-}

{-# INLINE coincidenceHeight #-}
coincidenceHeight :: Height -> Height -> Height
coincidenceHeight (UnsafeValidHeight outer) (UnsafeValidHeight inner) = Height (max outer inner)
coincidenceHeight InvalidHeight ValidHeight = invalidHeight
coincidenceHeight ValidHeight InvalidHeight = invalidHeight
coincidenceHeight InvalidHeight InvalidHeight = invalidHeight

{-# INLINE raiseHeight #-}
raiseHeight :: Height -> Height -> Maybe Height
raiseHeight (UnsafeValidHeight from) (UnsafeValidHeight to)
  | to > from = Just (Height to)
  | otherwise = Nothing
raiseHeight from to =
  error $ "raiseHeight was passed special height: " <> show from <> " " <> show to

-- | Safe compare, throw an error if either is special.
{-# INLINE compareHeight #-}
compareHeight :: Height -> Height -> Ordering
compareHeight (UnsafeValidHeight a) (UnsafeValidHeight b) = compare a b
compareHeight a b = error $ "compareHeight: special height(s): " <> show a <> " " <> show b

-- Used in merges
{-# INLINE heightSlotPassed #-}
heightSlotPassed :: Height -> Height -> Bool
heightSlotPassed (UnsafeValidHeight current) (UnsafeValidHeight mine) = current >= mine
heightSlotPassed ValidHeight InvalidHeight = True
heightSlotPassed InvalidHeight _ = error "heightSlotPassed: current height is special"

--------------------------------------------------------------------------------
-- Heightbag
--------------------------------------------------------------------------------

-- | Valid merge parents' heights and the number of parents with invalid
-- heights.
data HeightBag = HeightBag
  { _heightBag_invalidParents :: {-# UNPACK #-} !Int
  , _heightBag_contents :: !(IntMap Word) -- Number of parents in each height bucket
  }
  deriving (Eq, Ord, Read, Show)

{-# INLINE heightBagEmpty #-}
heightBagEmpty :: HeightBag
heightBagEmpty = heightBagVerify $ HeightBag 0 IntMap.empty

{-# INLINE heightBagHeight #-}
heightBagHeight :: HeightBag -> Height
heightBagHeight b@(HeightBag invalidParents _) = case compare invalidParents 0 of
  EQ -> heightBagSuccHeight b
  GT -> invalidHeight
  LT -> error $ "heightBagHeight: more heights than parents: " <> show b

{-# INLINE heightBagParentCount #-}
heightBagParentCount :: HeightBag -> Int
heightBagParentCount (HeightBag invalidParents c) = invalidParents + fromIntegral (sum (IntMap.elems c))

{-# INLINE heightBagAddParent #-}
heightBagAddParent :: Height -> HeightBag -> HeightBag
heightBagAddParent h (HeightBag invalidParents c) = heightBagVerify $ case h of
  ValidHeight -> HeightBag invalidParents (insertHeight h c)
  InvalidHeight -> HeightBag (succ invalidParents) c

{-# INLINE heightBagRemoveParent #-}
heightBagRemoveParent :: Height -> HeightBag -> HeightBag
heightBagRemoveParent h b@(HeightBag invalidParents c) = heightBagVerify $ case h of
  ValidHeight -> HeightBag invalidParents (deleteHeight h b)
  InvalidHeight -> HeightBag (pred invalidParents) c

{-# INLINE heightBagInvalidateParent #-}
heightBagInvalidateParent :: Height -> HeightBag -> HeightBag
heightBagInvalidateParent h b@(HeightBag invalidParents _) =
  heightBagVerify $
    HeightBag (succ invalidParents) (deleteHeight h b)

{-# INLINE heightBagRecalculateParent #-}
heightBagRecalculateParent :: Height -> HeightBag -> HeightBag
heightBagRecalculateParent h (HeightBag invalidParents c) =
  heightBagVerify $
    HeightBag (pred invalidParents) (insertHeight h c)

{-# INLINE insertHeight #-}
insertHeight :: Height -> IntMap Word -> IntMap Word
insertHeight (Height h) = IntMap.insertWith (+) h 1

{-# INLINE deleteHeight #-}
deleteHeight :: Height -> HeightBag -> IntMap Word
deleteHeight (Height h) b@(HeightBag _ c) = IntMap.alter decrement h c
  where
    decrement Nothing = error $ "deleteHeight: Height " <> show h <> " not present in bag " <> show b
    decrement (Just 1) = Nothing
    decrement (Just old) = Just $ pred old

{-# INLINE heightBagVerify #-}
heightBagVerify :: HeightBag -> HeightBag
#ifdef DEBUG
heightBagVerify b@(HeightBag invalidParents c) = if
  | invalidParents < 0
    -> error $ "heightBagVerify: more heights than parents: " <> show b
  | unsafeHeightAsInt invalidHeight `IntMap.member` c
    -> error $ "heightBagVerify: contains invalid height: " <> show b
  | otherwise -> b
#else
heightBagVerify = id
#endif

heightBagSuccHeight :: HeightBag -> Height
heightBagSuccHeight (HeightBag _ c) = case IntMap.lookupMax c of
  Just (h, _) -> Height (succ h)
  Nothing -> zeroHeight

--------------------------------------------------------------------------------
-- HeightQueue
--------------------------------------------------------------------------------

newtype HeightQueue a = HeightQueue (IntMap [a])
  deriving (Eq, Ord, Read, Show)

{-# INLINE heightQueueEmpty #-}
heightQueueEmpty :: HeightQueue a
heightQueueEmpty = HeightQueue IntMap.empty

{-# INLINE heightQueueInsert #-}
heightQueueInsert :: Height -> a -> HeightQueue a -> HeightQueue a
heightQueueInsert height a (HeightQueue q) =
  heightQueueVerifyKey height
    $ HeightQueue
    $ IntMap.insertWith (++) (unsafeHeightAsInt height) [a] q

{-# INLINE heightQueueNext #-}
heightQueueNext :: HeightQueue a -> Maybe (Height, [a], HeightQueue a)
heightQueueNext (HeightQueue q) = case IntMap.minViewWithKey q of
  Just ((h, as), q') -> Just (Height h, as, HeightQueue q')
  Nothing -> Nothing

{-# INLINE heightQueueVerifyKey #-}
heightQueueVerifyKey :: Height -> HeightQueue a -> HeightQueue a
#ifdef DEBUG
heightQueueVerifyKey height q = case height of
  ValidHeight -> q
  _ -> error $ "heightQueueInsert: refusing special height " <> show height
#else
heightQueueVerifyKey _ q = q
#endif