{-# OPTIONS_HADDOCK not-home #-}

module Database.LSMTree.Internal.Entry (
    Entry (..)
  , hasBlob
  , onValue
  , onBlobRef
  , NumEntries (..)
  , unNumEntries
    -- * Value resolution/merging
  , combine
  , combineUnion
  , combineMaybe
  ) where

import           Control.DeepSeq (NFData (..))
import           Data.Bifoldable (Bifoldable (..))
import           Data.Bifunctor (Bifunctor (..))

data Entry v b
    = Insert !v
    | InsertWithBlob !v !b
    | Mupdate !v
    | Delete
  deriving stock (Entry v b -> Entry v b -> Bool
(Entry v b -> Entry v b -> Bool)
-> (Entry v b -> Entry v b -> Bool) -> Eq (Entry v b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v b. (Eq b, Eq v) => Entry v b -> Entry v b -> Bool
$c== :: forall v b. (Eq b, Eq v) => Entry v b -> Entry v b -> Bool
== :: Entry v b -> Entry v b -> Bool
$c/= :: forall v b. (Eq b, Eq v) => Entry v b -> Entry v b -> Bool
/= :: Entry v b -> Entry v b -> Bool
Eq, Int -> Entry v b -> ShowS
[Entry v b] -> ShowS
Entry v b -> String
(Int -> Entry v b -> ShowS)
-> (Entry v b -> String)
-> ([Entry v b] -> ShowS)
-> Show (Entry v b)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v b. (Show b, Show v) => Int -> Entry v b -> ShowS
forall v b. (Show b, Show v) => [Entry v b] -> ShowS
forall v b. (Show b, Show v) => Entry v b -> String
$cshowsPrec :: forall v b. (Show b, Show v) => Int -> Entry v b -> ShowS
showsPrec :: Int -> Entry v b -> ShowS
$cshow :: forall v b. (Show b, Show v) => Entry v b -> String
show :: Entry v b -> String
$cshowList :: forall v b. (Show b, Show v) => [Entry v b] -> ShowS
showList :: [Entry v b] -> ShowS
Show, (forall a b. (a -> b) -> Entry v a -> Entry v b)
-> (forall a b. a -> Entry v b -> Entry v a) -> Functor (Entry v)
forall a b. a -> Entry v b -> Entry v a
forall a b. (a -> b) -> Entry v a -> Entry v b
forall v a b. a -> Entry v b -> Entry v a
forall v a b. (a -> b) -> Entry v a -> Entry v b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall v a b. (a -> b) -> Entry v a -> Entry v b
fmap :: forall a b. (a -> b) -> Entry v a -> Entry v b
$c<$ :: forall v a b. a -> Entry v b -> Entry v a
<$ :: forall a b. a -> Entry v b -> Entry v a
Functor, (forall m. Monoid m => Entry v m -> m)
-> (forall m a. Monoid m => (a -> m) -> Entry v a -> m)
-> (forall m a. Monoid m => (a -> m) -> Entry v a -> m)
-> (forall a b. (a -> b -> b) -> b -> Entry v a -> b)
-> (forall a b. (a -> b -> b) -> b -> Entry v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Entry v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Entry v a -> b)
-> (forall a. (a -> a -> a) -> Entry v a -> a)
-> (forall a. (a -> a -> a) -> Entry v a -> a)
-> (forall a. Entry v a -> [a])
-> (forall a. Entry v a -> Bool)
-> (forall a. Entry v a -> Int)
-> (forall a. Eq a => a -> Entry v a -> Bool)
-> (forall a. Ord a => Entry v a -> a)
-> (forall a. Ord a => Entry v a -> a)
-> (forall a. Num a => Entry v a -> a)
-> (forall a. Num a => Entry v a -> a)
-> Foldable (Entry v)
forall a. Eq a => a -> Entry v a -> Bool
forall a. Num a => Entry v a -> a
forall a. Ord a => Entry v a -> a
forall m. Monoid m => Entry v m -> m
forall a. Entry v a -> Bool
forall a. Entry v a -> Int
forall a. Entry v a -> [a]
forall a. (a -> a -> a) -> Entry v a -> a
forall v a. Eq a => a -> Entry v a -> Bool
forall v a. Num a => Entry v a -> a
forall v a. Ord a => Entry v a -> a
forall m a. Monoid m => (a -> m) -> Entry v a -> m
forall v m. Monoid m => Entry v m -> m
forall v a. Entry v a -> Bool
forall v a. Entry v a -> Int
forall v a. Entry v a -> [a]
forall b a. (b -> a -> b) -> b -> Entry v a -> b
forall a b. (a -> b -> b) -> b -> Entry v a -> b
forall v a. (a -> a -> a) -> Entry v a -> a
forall v m a. Monoid m => (a -> m) -> Entry v a -> m
forall v b a. (b -> a -> b) -> b -> Entry v a -> b
forall v a b. (a -> b -> b) -> b -> Entry v a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall v m. Monoid m => Entry v m -> m
fold :: forall m. Monoid m => Entry v m -> m
$cfoldMap :: forall v m a. Monoid m => (a -> m) -> Entry v a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Entry v a -> m
$cfoldMap' :: forall v m a. Monoid m => (a -> m) -> Entry v a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Entry v a -> m
$cfoldr :: forall v a b. (a -> b -> b) -> b -> Entry v a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Entry v a -> b
$cfoldr' :: forall v a b. (a -> b -> b) -> b -> Entry v a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Entry v a -> b
$cfoldl :: forall v b a. (b -> a -> b) -> b -> Entry v a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Entry v a -> b
$cfoldl' :: forall v b a. (b -> a -> b) -> b -> Entry v a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Entry v a -> b
$cfoldr1 :: forall v a. (a -> a -> a) -> Entry v a -> a
foldr1 :: forall a. (a -> a -> a) -> Entry v a -> a
$cfoldl1 :: forall v a. (a -> a -> a) -> Entry v a -> a
foldl1 :: forall a. (a -> a -> a) -> Entry v a -> a
$ctoList :: forall v a. Entry v a -> [a]
toList :: forall a. Entry v a -> [a]
$cnull :: forall v a. Entry v a -> Bool
null :: forall a. Entry v a -> Bool
$clength :: forall v a. Entry v a -> Int
length :: forall a. Entry v a -> Int
$celem :: forall v a. Eq a => a -> Entry v a -> Bool
elem :: forall a. Eq a => a -> Entry v a -> Bool
$cmaximum :: forall v a. Ord a => Entry v a -> a
maximum :: forall a. Ord a => Entry v a -> a
$cminimum :: forall v a. Ord a => Entry v a -> a
minimum :: forall a. Ord a => Entry v a -> a
$csum :: forall v a. Num a => Entry v a -> a
sum :: forall a. Num a => Entry v a -> a
$cproduct :: forall v a. Num a => Entry v a -> a
product :: forall a. Num a => Entry v a -> a
Foldable, Functor (Entry v)
Foldable (Entry v)
(Functor (Entry v), Foldable (Entry v)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> Entry v a -> f (Entry v b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Entry v (f a) -> f (Entry v a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Entry v a -> m (Entry v b))
-> (forall (m :: * -> *) a.
    Monad m =>
    Entry v (m a) -> m (Entry v a))
-> Traversable (Entry v)
forall v. Functor (Entry v)
forall v. Foldable (Entry v)
forall v (m :: * -> *) a. Monad m => Entry v (m a) -> m (Entry v a)
forall v (f :: * -> *) a.
Applicative f =>
Entry v (f a) -> f (Entry v a)
forall v (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Entry v a -> m (Entry v b)
forall v (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Entry v a -> f (Entry v b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Entry v (m a) -> m (Entry v a)
forall (f :: * -> *) a.
Applicative f =>
Entry v (f a) -> f (Entry v a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Entry v a -> m (Entry v b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Entry v a -> f (Entry v b)
$ctraverse :: forall v (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Entry v a -> f (Entry v b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Entry v a -> f (Entry v b)
$csequenceA :: forall v (f :: * -> *) a.
Applicative f =>
Entry v (f a) -> f (Entry v a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
Entry v (f a) -> f (Entry v a)
$cmapM :: forall v (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Entry v a -> m (Entry v b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Entry v a -> m (Entry v b)
$csequence :: forall v (m :: * -> *) a. Monad m => Entry v (m a) -> m (Entry v a)
sequence :: forall (m :: * -> *) a. Monad m => Entry v (m a) -> m (Entry v a)
Traversable)

hasBlob :: Entry v b -> Bool
hasBlob :: forall v a. Entry v a -> Bool
hasBlob Insert{}         = Bool
False
hasBlob InsertWithBlob{} = Bool
True
hasBlob Mupdate{}        = Bool
False
hasBlob Delete{}         = Bool
False

instance (NFData v, NFData b) => NFData (Entry v b) where
    rnf :: Entry v b -> ()
rnf (Insert v
v)            = v -> ()
forall a. NFData a => a -> ()
rnf v
v
    rnf (InsertWithBlob v
v b
br) = v -> ()
forall a. NFData a => a -> ()
rnf v
v () -> () -> ()
forall a b. a -> b -> b
`seq` b -> ()
forall a. NFData a => a -> ()
rnf b
br
    rnf (Mupdate v
v)           = v -> ()
forall a. NFData a => a -> ()
rnf v
v
    rnf Entry v b
Delete                = ()

onValue :: v' -> (v -> v') -> Entry v b -> v'
onValue :: forall v' v b. v' -> (v -> v') -> Entry v b -> v'
onValue v'
def v -> v'
f = \case
    Insert v
v           -> v -> v'
f v
v
    InsertWithBlob v
v b
_ -> v -> v'
f v
v
    Mupdate v
v          -> v -> v'
f v
v
    Entry v b
Delete             -> v'
def

onBlobRef :: b' -> (b -> b') -> Entry v b -> b'
onBlobRef :: forall b' b v. b' -> (b -> b') -> Entry v b -> b'
onBlobRef b'
def b -> b'
g = \case
    Insert{}            -> b'
def
    InsertWithBlob v
_ b
br -> b -> b'
g b
br
    Mupdate{}           -> b'
def
    Entry v b
Delete              -> b'
def

instance Bifunctor Entry where
  first :: forall a b c. (a -> b) -> Entry a c -> Entry b c
first a -> b
f = \case
      Insert a
v            -> b -> Entry b c
forall v b. v -> Entry v b
Insert (a -> b
f a
v)
      InsertWithBlob a
v c
br -> b -> c -> Entry b c
forall v b. v -> b -> Entry v b
InsertWithBlob (a -> b
f a
v) c
br
      Mupdate a
v           -> b -> Entry b c
forall v b. v -> Entry v b
Mupdate (a -> b
f a
v)
      Entry a c
Delete              -> Entry b c
forall v b. Entry v b
Delete

  second :: forall b c a. (b -> c) -> Entry a b -> Entry a c
second b -> c
g = \case
      Insert a
v            -> a -> Entry a c
forall v b. v -> Entry v b
Insert a
v
      InsertWithBlob a
v b
br -> a -> c -> Entry a c
forall v b. v -> b -> Entry v b
InsertWithBlob a
v (b -> c
g b
br)
      Mupdate a
v           -> a -> Entry a c
forall v b. v -> Entry v b
Mupdate a
v
      Entry a b
Delete              -> Entry a c
forall v b. Entry v b
Delete

instance Bifoldable Entry where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Entry a b -> m
bifoldMap a -> m
f b -> m
g = \case
      Insert a
v            -> a -> m
f a
v
      InsertWithBlob a
v b
br -> a -> m
f a
v m -> m -> m
forall a. Semigroup a => a -> a -> a
<> b -> m
g b
br
      Mupdate a
v           -> a -> m
f a
v
      Entry a b
Delete              -> m
forall a. Monoid a => a
mempty

-- | A count of entries, for example the number of entries in a run.
--
-- This number is limited by the machine's word size. On 32-bit systems, the
-- maximum number we can represent is @2^31@ which is roughly 2 billion. This
-- should be a sufficiently large limit that we never reach it in practice. By
-- extension for 64-bit and higher-bit systems this limit is also sufficiently
-- large.
newtype NumEntries = NumEntries Int
  deriving stock (NumEntries -> NumEntries -> Bool
(NumEntries -> NumEntries -> Bool)
-> (NumEntries -> NumEntries -> Bool) -> Eq NumEntries
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: NumEntries -> NumEntries -> Bool
== :: NumEntries -> NumEntries -> Bool
$c/= :: NumEntries -> NumEntries -> Bool
/= :: NumEntries -> NumEntries -> Bool
Eq, Eq NumEntries
Eq NumEntries =>
(NumEntries -> NumEntries -> Ordering)
-> (NumEntries -> NumEntries -> Bool)
-> (NumEntries -> NumEntries -> Bool)
-> (NumEntries -> NumEntries -> Bool)
-> (NumEntries -> NumEntries -> Bool)
-> (NumEntries -> NumEntries -> NumEntries)
-> (NumEntries -> NumEntries -> NumEntries)
-> Ord NumEntries
NumEntries -> NumEntries -> Bool
NumEntries -> NumEntries -> Ordering
NumEntries -> NumEntries -> NumEntries
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: NumEntries -> NumEntries -> Ordering
compare :: NumEntries -> NumEntries -> Ordering
$c< :: NumEntries -> NumEntries -> Bool
< :: NumEntries -> NumEntries -> Bool
$c<= :: NumEntries -> NumEntries -> Bool
<= :: NumEntries -> NumEntries -> Bool
$c> :: NumEntries -> NumEntries -> Bool
> :: NumEntries -> NumEntries -> Bool
$c>= :: NumEntries -> NumEntries -> Bool
>= :: NumEntries -> NumEntries -> Bool
$cmax :: NumEntries -> NumEntries -> NumEntries
max :: NumEntries -> NumEntries -> NumEntries
$cmin :: NumEntries -> NumEntries -> NumEntries
min :: NumEntries -> NumEntries -> NumEntries
Ord, Int -> NumEntries -> ShowS
[NumEntries] -> ShowS
NumEntries -> String
(Int -> NumEntries -> ShowS)
-> (NumEntries -> String)
-> ([NumEntries] -> ShowS)
-> Show NumEntries
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> NumEntries -> ShowS
showsPrec :: Int -> NumEntries -> ShowS
$cshow :: NumEntries -> String
show :: NumEntries -> String
$cshowList :: [NumEntries] -> ShowS
showList :: [NumEntries] -> ShowS
Show)
  deriving newtype NumEntries -> ()
(NumEntries -> ()) -> NFData NumEntries
forall a. (a -> ()) -> NFData a
$crnf :: NumEntries -> ()
rnf :: NumEntries -> ()
NFData

instance Semigroup NumEntries where
  NumEntries Int
a <> :: NumEntries -> NumEntries -> NumEntries
<> NumEntries Int
b = Int -> NumEntries
NumEntries (Int
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
b)

instance Monoid NumEntries where
  mempty :: NumEntries
mempty = Int -> NumEntries
NumEntries Int
0

unNumEntries :: NumEntries -> Int
unNumEntries :: NumEntries -> Int
unNumEntries (NumEntries Int
x) = Int
x

{-------------------------------------------------------------------------------
  Value resolution/merging
-------------------------------------------------------------------------------}

-- | Given a value-merge function, combine entries. Only take a blob from the
-- left entry.
--
-- Note: 'Entry' is a semigroup with 'combine' if the @(v -> v -> v)@ argument
-- is associative.
combine :: (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
combine :: forall v b. (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
combine v -> v -> v
_ e :: Entry v b
e@Entry v b
Delete            Entry v b
_                    = Entry v b
e
combine v -> v -> v
_ e :: Entry v b
e@Insert {}         Entry v b
_                    = Entry v b
e
combine v -> v -> v
_ e :: Entry v b
e@InsertWithBlob {} Entry v b
_                    = Entry v b
e
combine v -> v -> v
_   (Mupdate v
u)       Entry v b
Delete               = v -> Entry v b
forall v b. v -> Entry v b
Insert v
u
combine v -> v -> v
f   (Mupdate v
u)       (Insert v
v)           = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
combine v -> v -> v
f   (Mupdate v
u)       (InsertWithBlob v
v b
_) = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
combine v -> v -> v
f   (Mupdate v
u)       (Mupdate v
v)          = v -> Entry v b
forall v b. v -> Entry v b
Mupdate (v -> v -> v
f v
u v
v)

-- | Combine two entries of runs that have been 'union'ed together. If any one
-- has a value, the result should have a value (represented by 'Insert'). If
-- both have a value, these values get combined monoidally. Only take a blob
-- from the left entry.
--
-- Note: 'Entry' is a semigroup with 'combineUnion' if the @(v -> v -> v)@
-- argument is associative.
combineUnion :: (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
combineUnion :: forall v b. (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
combineUnion v -> v -> v
f = Entry v b -> Entry v b -> Entry v b
go
  where
    go :: Entry v b -> Entry v b -> Entry v b
go Entry v b
Delete               (Mupdate v
v)          = v -> Entry v b
forall v b. v -> Entry v b
Insert v
v
    go Entry v b
Delete               Entry v b
e                    = Entry v b
e
    go (Mupdate v
u)          Entry v b
Delete               = v -> Entry v b
forall v b. v -> Entry v b
Insert v
u
    go Entry v b
e                    Entry v b
Delete               = Entry v b
e
    go (Insert v
u)           (Insert v
v)           = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
    go (Insert v
u)           (InsertWithBlob v
v b
_) = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
    go (Insert v
u)           (Mupdate v
v)          = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
    go (InsertWithBlob v
u b
b) (Insert v
v)           = v -> b -> Entry v b
forall v b. v -> b -> Entry v b
InsertWithBlob (v -> v -> v
f v
u v
v) b
b
    go (InsertWithBlob v
u b
b) (InsertWithBlob v
v b
_) = v -> b -> Entry v b
forall v b. v -> b -> Entry v b
InsertWithBlob (v -> v -> v
f v
u v
v) b
b
    go (InsertWithBlob v
u b
b) (Mupdate v
v)          = v -> b -> Entry v b
forall v b. v -> b -> Entry v b
InsertWithBlob (v -> v -> v
f v
u v
v) b
b
    go (Mupdate v
u)          (Insert v
v)           = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
    go (Mupdate v
u)          (InsertWithBlob v
v b
_) = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)
    go (Mupdate v
u)          (Mupdate v
v)          = v -> Entry v b
forall v b. v -> Entry v b
Insert (v -> v -> v
f v
u v
v)

combineMaybe :: (v -> v -> v) -> Maybe (Entry v b) -> Maybe (Entry v b) -> Maybe (Entry v b)
combineMaybe :: forall v b.
(v -> v -> v)
-> Maybe (Entry v b) -> Maybe (Entry v b) -> Maybe (Entry v b)
combineMaybe v -> v -> v
_ Maybe (Entry v b)
e1 Maybe (Entry v b)
Nothing          = Maybe (Entry v b)
e1
combineMaybe v -> v -> v
_ Maybe (Entry v b)
Nothing Maybe (Entry v b)
e2          = Maybe (Entry v b)
e2
combineMaybe v -> v -> v
f (Just Entry v b
e1) (Just Entry v b
e2) = Entry v b -> Maybe (Entry v b)
forall a. a -> Maybe a
Just (Entry v b -> Maybe (Entry v b)) -> Entry v b -> Maybe (Entry v b)
forall a b. (a -> b) -> a -> b
$! (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
forall v b. (v -> v -> v) -> Entry v b -> Entry v b -> Entry v b
combine v -> v -> v
f Entry v b
e1 Entry v b
e2