{-# OPTIONS_HADDOCK not-home #-}

-- |
--  Provides support for working with fence pointer indexes of different types
--  and their accumulators.
--
--  Keys used with an index are subject to the key size constraints of the
--  concrete type of the index. These constraints are stated in the descriptions
--  of the modules "Database.LSMTree.Internal.Index.Compact" and
--  "Database.LSMTree.Internal.Index.Ordinary", respectively.
--
--  Part of the functionality that this module provides is the construction of
--  serialised indexes in a mostly incremental fashion. The incremental part of
--  serialisation is provided through index accumulators, while the
--  non-incremental bits are provided through the index operations 'headerLBS'
--  and 'finalLBS'. To completely serialise an index interleaved with its
--  construction, proceed as follows:
--
--   1. Use 'headerLBS' to generate the header of the serialised index.
--
--   2. Incrementally construct the index using the operations of 'IndexAcc',
--      and assemble the body of the serialised index from the generated chunks.
--
--   3. Use 'finalLBS' to generate the footer of the serialised index.
--
module Database.LSMTree.Internal.Index
(
    -- * Index types
    IndexType (Compact, Ordinary),
    indexToIndexType,

    -- * Indexes
    Index (CompactIndex, OrdinaryIndex),
    search,
    sizeInPages,
    headerLBS,
    finalLBS,
    fromSBS,

    -- * Index accumulators
    IndexAcc (CompactIndexAcc, OrdinaryIndexAcc),
    newWithDefaults,
    appendSingle,
    appendMulti,
    unsafeEnd
)
where

import           Control.Arrow (second)
import           Control.DeepSeq (NFData (rnf))
import           Control.Monad.ST.Strict (ST)
import           Data.ByteString.Lazy (LazyByteString)
import           Data.ByteString.Short (ShortByteString)
import           Data.Word (Word32)
import           Database.LSMTree.Internal.Chunk (Chunk)
import           Database.LSMTree.Internal.Entry (NumEntries)
import           Database.LSMTree.Internal.Index.Compact (IndexCompact)
import qualified Database.LSMTree.Internal.Index.Compact as Compact (finalLBS,
                     fromSBS, headerLBS, search, sizeInPages)
import           Database.LSMTree.Internal.Index.CompactAcc (IndexCompactAcc)
import qualified Database.LSMTree.Internal.Index.CompactAcc as Compact
                     (appendMulti, appendSingle, newWithDefaults, unsafeEnd)
import           Database.LSMTree.Internal.Index.Ordinary (IndexOrdinary)
import qualified Database.LSMTree.Internal.Index.Ordinary as Ordinary (finalLBS,
                     fromSBS, headerLBS, search, sizeInPages)
import           Database.LSMTree.Internal.Index.OrdinaryAcc (IndexOrdinaryAcc)
import qualified Database.LSMTree.Internal.Index.OrdinaryAcc as Ordinary
                     (appendMulti, appendSingle, newWithDefaults, unsafeEnd)
import           Database.LSMTree.Internal.Page (NumPages, PageSpan)
import           Database.LSMTree.Internal.Serialise (SerialisedKey)

-- * Index types

-- | The type of supported index types.
data IndexType = Compact | Ordinary
    deriving stock (IndexType -> IndexType -> Bool
(IndexType -> IndexType -> Bool)
-> (IndexType -> IndexType -> Bool) -> Eq IndexType
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: IndexType -> IndexType -> Bool
== :: IndexType -> IndexType -> Bool
$c/= :: IndexType -> IndexType -> Bool
/= :: IndexType -> IndexType -> Bool
Eq, Int -> IndexType -> ShowS
[IndexType] -> ShowS
IndexType -> String
(Int -> IndexType -> ShowS)
-> (IndexType -> String)
-> ([IndexType] -> ShowS)
-> Show IndexType
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> IndexType -> ShowS
showsPrec :: Int -> IndexType -> ShowS
$cshow :: IndexType -> String
show :: IndexType -> String
$cshowList :: [IndexType] -> ShowS
showList :: [IndexType] -> ShowS
Show)

instance NFData IndexType where
    rnf :: IndexType -> ()
rnf IndexType
Compact  = ()
    rnf IndexType
Ordinary = ()

-- * Indexes

-- | The type of supported indexes.
data Index
    = CompactIndex  !IndexCompact
    | OrdinaryIndex !IndexOrdinary
    deriving stock (Index -> Index -> Bool
(Index -> Index -> Bool) -> (Index -> Index -> Bool) -> Eq Index
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Index -> Index -> Bool
== :: Index -> Index -> Bool
$c/= :: Index -> Index -> Bool
/= :: Index -> Index -> Bool
Eq, Int -> Index -> ShowS
[Index] -> ShowS
Index -> String
(Int -> Index -> ShowS)
-> (Index -> String) -> ([Index] -> ShowS) -> Show Index
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Index -> ShowS
showsPrec :: Int -> Index -> ShowS
$cshow :: Index -> String
show :: Index -> String
$cshowList :: [Index] -> ShowS
showList :: [Index] -> ShowS
Show)

instance NFData Index where
    rnf :: Index -> ()
rnf (CompactIndex  IndexCompact
index) = IndexCompact -> ()
forall a. NFData a => a -> ()
rnf IndexCompact
index
    rnf (OrdinaryIndex IndexOrdinary
index) = IndexOrdinary -> ()
forall a. NFData a => a -> ()
rnf IndexOrdinary
index

indexToIndexType :: Index -> IndexType
indexToIndexType :: Index -> IndexType
indexToIndexType CompactIndex{}  = IndexType
Compact
indexToIndexType OrdinaryIndex{} = IndexType
Ordinary

{-|
    Searches for a page span that contains a key–value pair with the given key.
    If there is indeed such a pair, the result is the corresponding page span;
    if there is no such pair, the result is an arbitrary but valid page span.
-}
search :: SerialisedKey -> Index -> PageSpan
search :: SerialisedKey -> Index -> PageSpan
search SerialisedKey
key (CompactIndex  IndexCompact
index) = SerialisedKey -> IndexCompact -> PageSpan
Compact.search  SerialisedKey
key IndexCompact
index
search SerialisedKey
key (OrdinaryIndex IndexOrdinary
index) = SerialisedKey -> IndexOrdinary -> PageSpan
Ordinary.search SerialisedKey
key IndexOrdinary
index

-- | Yields the number of pages covered by an index.
sizeInPages :: Index -> NumPages
sizeInPages :: Index -> NumPages
sizeInPages (CompactIndex  IndexCompact
index) = IndexCompact -> NumPages
Compact.sizeInPages  IndexCompact
index
sizeInPages (OrdinaryIndex IndexOrdinary
index) = IndexOrdinary -> NumPages
Ordinary.sizeInPages IndexOrdinary
index

{-|
    Yields the header of the serialised form of an index.

    See [the module documentation]("Database.LSMTree.Internal.Index") for how to
    generate a complete serialised index.
-}
headerLBS :: IndexType -> LazyByteString
headerLBS :: IndexType -> LazyByteString
headerLBS IndexType
Compact  = LazyByteString
Compact.headerLBS
headerLBS IndexType
Ordinary = LazyByteString
Ordinary.headerLBS

{-|
    Yields the footer of the serialised form of an index.

    See [the module documentation]("Database.LSMTree.Internal.Index") for how to
    generate a complete serialised index.
-}
finalLBS :: NumEntries -> Index -> LazyByteString
finalLBS :: NumEntries -> Index -> LazyByteString
finalLBS NumEntries
entryCount (CompactIndex  IndexCompact
index) = NumEntries -> IndexCompact -> LazyByteString
Compact.finalLBS  NumEntries
entryCount IndexCompact
index
finalLBS NumEntries
entryCount (OrdinaryIndex IndexOrdinary
index) = NumEntries -> IndexOrdinary -> LazyByteString
Ordinary.finalLBS NumEntries
entryCount IndexOrdinary
index

{-|
    Reads an index along with the number of entries of the respective run from a
    byte string.

    The byte string must contain the serialised index exactly, with no leading
    or trailing space. Furthermore, its contents must be stored 64-bit-aligned.

    The contents of the byte string may be directly used as the backing memory
    for the constructed index. Currently, this is done for compact indexes.

    For deserialising numbers, the endianness of the host system is used. If
    serialisation has been done with a different endianness, this mismatch is
    detected by looking at the type–version indicator.
-}
fromSBS :: IndexType -> ShortByteString -> Either String (NumEntries, Index)
fromSBS :: IndexType -> ShortByteString -> Either String (NumEntries, Index)
fromSBS IndexType
Compact ShortByteString
input  = (IndexCompact -> Index)
-> (NumEntries, IndexCompact) -> (NumEntries, Index)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IndexCompact -> Index
CompactIndex  ((NumEntries, IndexCompact) -> (NumEntries, Index))
-> Either String (NumEntries, IndexCompact)
-> Either String (NumEntries, Index)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ShortByteString -> Either String (NumEntries, IndexCompact)
Compact.fromSBS  ShortByteString
input
fromSBS IndexType
Ordinary ShortByteString
input = (IndexOrdinary -> Index)
-> (NumEntries, IndexOrdinary) -> (NumEntries, Index)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IndexOrdinary -> Index
OrdinaryIndex ((NumEntries, IndexOrdinary) -> (NumEntries, Index))
-> Either String (NumEntries, IndexOrdinary)
-> Either String (NumEntries, Index)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ShortByteString -> Either String (NumEntries, IndexOrdinary)
Ordinary.fromSBS ShortByteString
input

-- * Index accumulators

{-|
    The type of supported index accumulators, where an index accumulator denotes
    an index under incremental construction.

    Incremental index construction is only guaranteed to work correctly when the
    supplied key ranges do not overlap and are given in ascending order.
-}
data IndexAcc s = CompactIndexAcc  !(IndexCompactAcc  s)
                | OrdinaryIndexAcc !(IndexOrdinaryAcc s)

-- | Create a new index accumulator, using a default configuration.
newWithDefaults :: IndexType -> ST s (IndexAcc s)
newWithDefaults :: forall s. IndexType -> ST s (IndexAcc s)
newWithDefaults IndexType
Compact  = IndexCompactAcc s -> IndexAcc s
forall s. IndexCompactAcc s -> IndexAcc s
CompactIndexAcc  (IndexCompactAcc s -> IndexAcc s)
-> ST s (IndexCompactAcc s) -> ST s (IndexAcc s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ST s (IndexCompactAcc s)
forall s. ST s (IndexCompactAcc s)
Compact.newWithDefaults
newWithDefaults IndexType
Ordinary = IndexOrdinaryAcc s -> IndexAcc s
forall s. IndexOrdinaryAcc s -> IndexAcc s
OrdinaryIndexAcc (IndexOrdinaryAcc s -> IndexAcc s)
-> ST s (IndexOrdinaryAcc s) -> ST s (IndexAcc s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ST s (IndexOrdinaryAcc s)
forall s. ST s (IndexOrdinaryAcc s)
Ordinary.newWithDefaults

{-|
    Adds information about a single page that fully comprises one or more
    key–value pairs to an index and outputs newly available chunks.

    See the documentation of the 'IndexAcc' type for constraints to adhere to.
-}
appendSingle :: (SerialisedKey, SerialisedKey)
             -> IndexAcc s
             -> ST s (Maybe Chunk)
appendSingle :: forall s.
(SerialisedKey, SerialisedKey) -> IndexAcc s -> ST s (Maybe Chunk)
appendSingle (SerialisedKey, SerialisedKey)
pageInfo (CompactIndexAcc  IndexCompactAcc s
indexAcc) = (SerialisedKey, SerialisedKey)
-> IndexCompactAcc s -> ST s (Maybe Chunk)
forall s.
(SerialisedKey, SerialisedKey)
-> IndexCompactAcc s -> ST s (Maybe Chunk)
Compact.appendSingle
                                                        (SerialisedKey, SerialisedKey)
pageInfo
                                                        IndexCompactAcc s
indexAcc
appendSingle (SerialisedKey, SerialisedKey)
pageInfo (OrdinaryIndexAcc IndexOrdinaryAcc s
indexAcc) = (SerialisedKey, SerialisedKey)
-> IndexOrdinaryAcc s -> ST s (Maybe Chunk)
forall s.
(SerialisedKey, SerialisedKey)
-> IndexOrdinaryAcc s -> ST s (Maybe Chunk)
Ordinary.appendSingle
                                                        (SerialisedKey, SerialisedKey)
pageInfo
                                                        IndexOrdinaryAcc s
indexAcc

{-|
    Adds information about multiple pages that together comprise a single
    key–value pair to an index and outputs newly available chunks.

    The provided 'Word32' value denotes the number of /overflow/ pages, so that
    the number of pages that comprise the key–value pair is the successor of
    that number.

    See the documentation of the 'IndexAcc' type for constraints to adhere to.
-}
appendMulti :: (SerialisedKey, Word32) -> IndexAcc s -> ST s [Chunk]
appendMulti :: forall s. (SerialisedKey, Word32) -> IndexAcc s -> ST s [Chunk]
appendMulti (SerialisedKey, Word32)
pagesInfo (CompactIndexAcc  IndexCompactAcc s
indexAcc) = (SerialisedKey, Word32) -> IndexCompactAcc s -> ST s [Chunk]
forall s.
(SerialisedKey, Word32) -> IndexCompactAcc s -> ST s [Chunk]
Compact.appendMulti
                                                        (SerialisedKey, Word32)
pagesInfo
                                                        IndexCompactAcc s
indexAcc
appendMulti (SerialisedKey, Word32)
pagesInfo (OrdinaryIndexAcc IndexOrdinaryAcc s
indexAcc) = (SerialisedKey, Word32) -> IndexOrdinaryAcc s -> ST s [Chunk]
forall s.
(SerialisedKey, Word32) -> IndexOrdinaryAcc s -> ST s [Chunk]
Ordinary.appendMulti
                                                        (SerialisedKey, Word32)
pagesInfo
                                                        IndexOrdinaryAcc s
indexAcc

{-|
    Returns the constructed index, along with a final chunk in case the
    serialised key list has not been fully output yet, thereby invalidating the
    index under construction. Executing @unsafeEnd index@ is only safe when
    @index@ is not used afterwards.
-}
unsafeEnd :: IndexAcc s -> ST s (Maybe Chunk, Index)
unsafeEnd :: forall s. IndexAcc s -> ST s (Maybe Chunk, Index)
unsafeEnd (CompactIndexAcc  IndexCompactAcc s
indexAcc) = (IndexCompact -> Index)
-> (Maybe Chunk, IndexCompact) -> (Maybe Chunk, Index)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IndexCompact -> Index
CompactIndex         ((Maybe Chunk, IndexCompact) -> (Maybe Chunk, Index))
-> ST s (Maybe Chunk, IndexCompact) -> ST s (Maybe Chunk, Index)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
                                        IndexCompactAcc s -> ST s (Maybe Chunk, IndexCompact)
forall s. IndexCompactAcc s -> ST s (Maybe Chunk, IndexCompact)
Compact.unsafeEnd  IndexCompactAcc s
indexAcc
unsafeEnd (OrdinaryIndexAcc IndexOrdinaryAcc s
indexAcc) = (IndexOrdinary -> Index)
-> (Maybe Chunk, IndexOrdinary) -> (Maybe Chunk, Index)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IndexOrdinary -> Index
OrdinaryIndex        ((Maybe Chunk, IndexOrdinary) -> (Maybe Chunk, Index))
-> ST s (Maybe Chunk, IndexOrdinary) -> ST s (Maybe Chunk, Index)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
                                        IndexOrdinaryAcc s -> ST s (Maybe Chunk, IndexOrdinary)
forall s. IndexOrdinaryAcc s -> ST s (Maybe Chunk, IndexOrdinary)
Ordinary.unsafeEnd IndexOrdinaryAcc s
indexAcc