packages feed

haskoin-store-1.16.0: test/Haskoin/Store/Database/MergeSpec.hs

-- | The merge operators of the database against what they are meant to
-- do, said in Haskell.
--
-- The operators are C functions that RocksDB calls on its own threads
-- ("Haskoin.Store.Database.Merge"). They are tested twice. First by
-- calling them directly, as RocksDB would, with random values and merge
-- records: the result must be the bytes of the Haskell fold of the same,
-- records combined beforehand must do what they did one by one, and input
-- that is not of the format must be refused. Then through a database:
-- merge records, puts and deletes written in any order, in memtables and
-- in table files, must read as the same fold, before and after a
-- compaction.
module Haskoin.Store.Database.MergeSpec (spec) where

import Control.Monad (forM_)
import Data.ByteString (ByteString)
import Data.ByteString qualified as B
import Data.Default (def)
import Data.IntMap.Strict (IntMap)
import Data.IntMap.Strict qualified as IntMap
import Data.Map.Strict qualified as Map
import Data.Maybe (fromMaybe)
import Data.Serialize (encode)
import Data.Word (Word32, Word64)
import Database.RocksDB
  ( FullMerge,
    MergeOperator (..),
    PartialMerge,
    columnFamilies,
    compactRange,
    deleteCF,
    flush,
    mergeCF,
    putCF,
  )
import Database.RocksDB.Query (retrieveCF)
import Foreign.C.String (CString)
import Foreign.C.Types (CInt (..), CSize (..), CUChar (..))
import Foreign.Marshal.Alloc (alloca, free)
import Foreign.Marshal.Array (withArray)
import Foreign.Marshal.Utils (withMany)
import Foreign.Ptr (FunPtr, Ptr, nullPtr)
import Foreign.Storable (peek)
import Haskoin
  ( Address,
    TxHash (..),
    btcRegTest,
    eitherToMaybe,
    scriptToAddressBS,
    sha256,
  )
import Haskoin.Store.Data (Spender (..))
import Haskoin.Store.Database.Merge (balanceOperator, spenderOperator)
import Haskoin.Store.Database.Query qualified as Q
import Haskoin.Store.Database.Reader (DatabaseReader (..), balanceCF, spenderCF)
import Haskoin.Store.Database.Types
  ( BalKey (..),
    BalVal (..),
    SpenderKey (..),
    SpenderVal (..),
    addBalVal,
    valToBalance,
  )
import Haskoin.Store.Histories (openLayered)
import Haskoin.Store.Integration.Temp (withSystemTempDirectory)
import Test.Hspec
import Test.Hspec.QuickCheck (modifyMaxSuccess, prop)
import Test.QuickCheck
  ( Gen,
    arbitrary,
    choose,
    elements,
    forAll,
    frequency,
    ioProperty,
    listOf,
    listOf1,
    oneof,
    vectorOf,
  )

spec :: Spec
spec = describe "the merge operators of the database" $ do
  describe "the formats that they read and write" $ do
    it "are those of the values: forty bytes for a balance, a count and forty bytes for each spender" $ do
      encode (BalVal 1 2 3 4 0x0102030405060708)
        `shouldBe` B.pack (concat [[0, 0, 0, 0, 0, 0, 0, n] | n <- [1 .. 4]] <> [1 .. 8])
      let spender = Spender (TxHash (sha256 ("spender" :: ByteString))) 0x0a0b0c0d
          two = SpenderVal (IntMap.fromList [(0x01020304, spender), (2, spender)])
      encode two
        `shouldBe` B.concat
          [ B.pack [2],
            B.pack [0, 0, 0, 2],
            encode (sha256 ("spender" :: ByteString)),
            B.pack [0x0a, 0x0b, 0x0c, 0x0d],
            B.pack [1, 2, 3, 4],
            encode (sha256 ("spender" :: ByteString)),
            B.pack [0x0a, 0x0b, 0x0c, 0x0d]
          ]
      B.length (encode two) `shouldBe` 1 + 2 * 40

  describe "of balances" $ do
    prop "adds the differences to the balance, each number modulo 2^64, from zero if there is none" $
      forAll ((,) <$> oneof [pure Nothing, Just <$> genBalVal] <*> listOf genBalVal) $ \(existing, records) ->
        ioProperty $
          fullOf balanceOperator (encode <$> existing) (map encode records)
            `shouldReturn` Just (encode (foldl addBalVal (fromMaybe def existing) records))
    prop "makes one record of several, which does what they did" $
      forAll ((,) <$> oneof [pure Nothing, Just <$> genBalVal] <*> listOf1 (listOf1 genBalVal)) $
        \(existing, parts) -> ioProperty $ do
          combined <- mapM (partialOf balanceOperator . map encode) parts
          map (fmap B.length) combined `shouldBe` map (const (Just 40)) parts
          combined `shouldBe` map (Just . encode . foldl1 addBalVal) parts
          one <- fullOf balanceOperator (encode <$> existing) (map encode (concat parts))
          fullOf balanceOperator (encode <$> existing) [r | Just r <- combined] `shouldReturn` one
    it "takes a number down by its two's complement" $ do
      let had = BalVal {confirmed = 5000, unconfirmed = 0, utxo = 2, txs = 7, received = 9000}
          spent = (def :: BalVal) {confirmed = negate 3000, utxo = negate 1, txs = 1}
      fullOf balanceOperator (Just (encode had)) [encode spent]
        `shouldReturn` Just (encode BalVal {confirmed = 2000, unconfirmed = 0, utxo = 1, txs = 8, received = 9000})
    it "refuses what is not forty bytes" $ do
      let good = encode (def :: BalVal)
      fullOf balanceOperator (Just good) [good] `shouldReturn` Just good
      fullOf balanceOperator (Just (B.init good)) [good] `shouldReturn` Nothing
      fullOf balanceOperator (Just good) [good, good <> "\0"] `shouldReturn` Nothing
      fullOf balanceOperator Nothing [""] `shouldReturn` Nothing
      fullOf balanceOperator (Just "") [good] `shouldReturn` Nothing
      partialOf balanceOperator [good, B.take 8 good] `shouldReturn` Nothing

  describe "of groups of spenders" $ do
    prop "joins the records with the group, the newest winning for an output, in the order of the outputs" $
      forAll ((,) <$> oneof [pure Nothing, Just <$> genGroup] <*> listOf genGroup) $ \(existing, records) ->
        ioProperty $
          fullOf spenderOperator (group <$> existing) (map group records)
            `shouldReturn` Just (group (joined (fromMaybe IntMap.empty existing) records))
    prop "makes one record of several, which does what they did" $
      forAll ((,) <$> oneof [pure Nothing, Just <$> genGroup] <*> listOf1 (listOf1 genGroup)) $
        \(existing, parts) -> ioProperty $ do
          combined <- mapM (partialOf spenderOperator . map group) parts
          combined `shouldBe` map (Just . group . joined IntMap.empty) parts
          one <- fullOf spenderOperator (group <$> existing) (map group (concat parts))
          fullOf spenderOperator (group <$> existing) [r | Just r <- combined] `shouldReturn` one
    it "refuses a group whose length is not that of its count" $ do
      let good = group (IntMap.fromList [(1, spenderOf 1), (2, spenderOf 2)])
      fullOf spenderOperator (Just good) [good] `shouldReturn` Just good
      fullOf spenderOperator (Just (B.init good)) [good] `shouldReturn` Nothing
      fullOf spenderOperator (Just good) [good <> "\0"] `shouldReturn` Nothing
      fullOf spenderOperator Nothing [""] `shouldReturn` Nothing
      fullOf spenderOperator Nothing [B.pack [3] <> B.drop 1 good] `shouldReturn` Nothing
      partialOf spenderOperator [good, B.take 41 good] `shouldReturn` Nothing
    it "takes a group with no entries for what it is" $
      fullOf spenderOperator (Just "\0") ["\0"] `shouldReturn` Just "\0"

  describe "in a database" $
    modifyMaxSuccess (const 25) $ do
      prop "give the balances that the same writes give when each is read and written whole" $
        forAll (listOf (genStep genBalVal)) $ \steps -> ioProperty . withDB $ \db -> do
          let cf = balanceCF db.db
              wanted = model addBalVal def steps
              agree = forM_ [0 .. keys - 1] $ \k -> do
                let a = address (fromIntegral k)
                Q.getBalance db a `shouldReturn` (valToBalance a <$> Map.lookup k wanted)
                retrieveCF db.db cf (BalKey a) `shouldReturn` Map.lookup k wanted
          forM_ steps $ \case
            Whole k v -> putCF db.db cf (encode (BalKey (address (fromIntegral k)))) (encode v)
            Gone k -> deleteCF db.db cf (encode (BalKey (address (fromIntegral k))))
            Change k v -> mergeCF db.db cf (encode (BalKey (address (fromIntegral k)))) (encode v)
            ToFile -> flush db.db (Just cf)
          agree
          flush db.db (Just cf)
          agree
          compactRange db.db (Just cf) Nothing Nothing
          agree
      prop "give the groups of spenders that the same writes give when each is read and written whole" $
        forAll (listOf (genStep genGroup)) $ \steps -> ioProperty . withDB $ \db -> do
          let cf = spenderCF db.db
              wanted = model (flip IntMap.union) IntMap.empty steps
              -- the groups of one transaction, sixteen outputs apart, and
              -- one of another
              key k = if k == 0 then SpenderKey (made 0) 7 else SpenderKey (made 1) (fromIntegral k)
              agree = do
                forM_ [0 .. keys - 1] $ \k ->
                  retrieveCF db.db cf (key k) `shouldReturn` (SpenderVal <$> Map.lookup k wanted)
                -- and as the queries read them, with a scan of the
                -- transaction
                Q.getChainSpenders db (made 0) `shouldReturn` fromMaybe IntMap.empty (Map.lookup 0 wanted)
                Q.getChainSpenders db (made 1)
                  `shouldReturn` IntMap.unions [m | (k, m) <- Map.toList wanted, k /= 0]
          forM_ steps $ \case
            Whole k v -> putCF db.db cf (encode (key k)) (group v)
            Gone k -> deleteCF db.db cf (encode (key k))
            Change k v -> mergeCF db.db cf (encode (key k)) (group v)
            ToFile -> flush db.db (Just cf)
          agree
          flush db.db (Just cf)
          agree
          compactRange db.db (Just cf) Nothing Nothing
          agree
      it "has the two operators on their column families, and the one that keeps older stores out" $
        withDB $
          \db -> length (columnFamilies db.db) `shouldBe` 11

-------------------------------------------------------------------------------
-- Calling the operators as RocksDB does
-------------------------------------------------------------------------------

foreign import ccall "dynamic" callFull :: FunPtr FullMerge -> FullMerge

foreign import ccall "dynamic" callPartial :: FunPtr PartialMerge -> PartialMerge

-- | The full merge of an operator: the value that a key has, if any, and
-- its merge records, oldest first. 'Nothing' if the function says that it
-- failed, which it must say as RocksDB's C API reads it: with no bytes.
fullOf :: MergeOperator -> Maybe ByteString -> [ByteString] -> IO (Maybe ByteString)
fullOf op existing records = case op of
  MergeFunctions {fullMerge = function} ->
    operands records $ \pointers lengths count success size -> do
      let call (value, n) =
            callFull function nullPtr nullPtr 0 value (fromIntegral n) pointers lengths count success size
      maybe (call (nullPtr, 0 :: Int)) (`B.useAsCStringLen` call) existing
  UInt64Add -> fail "not an operator of the store"

-- | The partial merge of an operator: merge records, oldest first.
partialOf :: MergeOperator -> [ByteString] -> IO (Maybe ByteString)
partialOf op records = case op of
  MergeFunctions {partialMerge = function} ->
    operands records $ \pointers lengths count success size ->
      callPartial function nullPtr nullPtr 0 pointers lengths count success size
  UInt64Add -> fail "not an operator of the store"

-- | Hand merge records to a function as RocksDB's C API does, and read
-- what it returns: memory from malloc, a length, and whether it worked.
operands ::
  [ByteString] ->
  (Ptr CString -> Ptr CSize -> CInt -> Ptr CUChar -> Ptr CSize -> IO CString) ->
  IO (Maybe ByteString)
operands records call =
  withMany B.useAsCStringLen records $ \rows ->
    withArray (map fst rows) $ \pointers ->
      withArray (map (fromIntegral . snd) rows :: [CSize]) $ \lengths ->
        alloca $ \success ->
          alloca $ \size -> do
            bytes <- call pointers lengths (fromIntegral (length rows)) success size
            ok <- peek success
            n <- peek size
            if ok == 0
              then do
                -- RocksDB copies this many bytes before it looks at the flag
                (bytes, n) `shouldBe` (nullPtr, 0)
                return Nothing
              else do
                result <- B.packCStringLen (bytes, fromIntegral n)
                free bytes
                return (Just result)

-------------------------------------------------------------------------------
-- What they are meant to do
-------------------------------------------------------------------------------

-- | A group with these records joined to it, oldest first: a newer entry
-- takes the place of an older one for the same output.
joined :: IntMap Spender -> [IntMap Spender] -> IntMap Spender
joined = foldl (flip IntMap.union)

-- | The bytes of a group of spenders.
group :: IntMap Spender -> ByteString
group = encode . SpenderVal

-- | A write to one of a few keys: a whole value, a delete, a merge record,
-- or a flush of the memtable to a table file.
data Step v
  = Whole Int v
  | Gone Int
  | Change Int v
  | ToFile
  deriving (Show)

-- | The keys that the steps write to.
keys :: Int
keys = 4

genStep :: Gen v -> Gen (Step v)
genStep value =
  frequency
    [ (2, Whole <$> key <*> value),
      (1, Gone <$> key),
      (6, Change <$> key <*> value),
      (2, pure ToFile)
    ]
  where
    key = choose (0, keys - 1)

-- | What each key holds after the steps, given how a merge record changes
-- a value and the value that a key without one counts from.
model :: (v -> v -> v) -> v -> [Step v] -> Map.Map Int v
model merge zero = foldl step Map.empty
  where
    step m (Whole k v) = Map.insert k v m
    step m (Gone k) = Map.delete k m
    step m (Change k v) = Map.insert k (merge (Map.findWithDefault zero k m) v) m
    step m ToFile = m

-- | Numbers of any size, so that sums wrap around, and small ones.
genBalVal :: Gen BalVal
genBalVal = BalVal <$> number <*> number <*> number <*> number <*> number
  where
    number = oneof [arbitrary, fromIntegral <$> choose (0, 3 :: Int), negate . fromIntegral <$> choose (1, 3 :: Int)]

-- | A few spenders, of outputs that other groups often have too.
genGroup :: Gen (IntMap Spender)
genGroup = do
  n <- choose (0, 5)
  IntMap.fromList <$> vectorOf n ((,) <$> output <*> (spenderOf <$> arbitrary))
  where
    -- most in the sixteen outputs of a group, and some whose number takes
    -- all four bytes
    output = frequency [(8, choose (0, 15)), (1, elements [255, 256, 65536, 16777216, 2000000000])]

spenderOf :: Word32 -> Spender
spenderOf n = Spender (TxHash (sha256 (encode n))) (n `mod` 7)

made :: Word64 -> TxHash
made n = TxHash (sha256 (encode n))

address :: Word32 -> Address
address i =
  fromMaybe (error "no address") . eitherToMaybe . scriptToAddressBS btcRegTest $
    "\x76\xa9\x14" <> B.take 20 (encode (sha256 (encode i))) <> "\x88\xac"

withDB :: (DatabaseReader -> IO a) -> IO a
withDB action = withSystemTempDirectory "haskoin-store-merge-" $ \dir -> openLayered btcRegTest dir action