packages feed

rocksdb-haskell-jprupp-2.8.0: test/Spec.hs

{-# LANGUAGE ForeignFunctionInterface #-}
{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections #-}

-- |
-- Tests of "Database.RocksDB" against a real RocksDB, in temporary
-- directories.
--
-- There are two kinds of test here, because the bindings can go wrong in two
-- ways:
--
-- * Examples, which pin down one behaviour each: what a function returns, when
--   it throws, what a setting changes in the files RocksDB writes. Several
--   exist because a binding was once wrong without anything failing, so they
--   check an effect that can be observed rather than that a call returns.
--
-- * Properties, which run random sequences of writes against the database and
--   against a 'Map', and require that the two agree however they are read.
--   They find what nobody thought to write an example for: empty keys and
--   values, bytes that C would take for the end of a string, a delete of a key
--   that was never there, the order of iteration.
--
-- Every test opens its own database, so tests do not depend on each other or
-- on the order they run in.
module Main (main) where

import Control.Concurrent
import Control.Concurrent.Async
import Control.Exception (bracket, evaluate, try)
import Control.Monad
import Data.Bits (shiftR)
import Data.ByteString (ByteString)
import Data.ByteString qualified as BS
import Data.ByteString.Char8 qualified as C
import Data.ByteString.Internal qualified as BI
import Data.Default (def)
import Data.List (isInfixOf, isPrefixOf, isSuffixOf)
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Maybe
import Data.Word (Word64, Word8)
import Database.RocksDB
import Foreign.Marshal.Utils (copyBytes)
import Foreign.Ptr (FunPtr, Ptr, castPtr, plusPtr)
import GHC.Clock (getMonotonicTime)
import System.Directory (listDirectory)
import System.FilePath ((</>))
import System.IO (IOMode (ReadWriteMode), SeekMode (AbsoluteSeek), hSeek, withBinaryFile)
import System.IO.Error (ioeGetErrorString)
import System.IO.Temp
import Test.Hspec
import Test.Hspec.QuickCheck (modifyMaxSuccess, prop)
import Test.QuickCheck hiding (Property)
import Test.QuickCheck qualified as QC
import Text.Printf

main :: IO ()
main = hspec $ do
  around (withTunedDB ["one", "two", "tree"]) tunedSpec
  around withPlainDB plainSpec
  around withPlainDB chunkSpec
  chunkErrorSpec
  packedSpec
  mergeSpec
  boundSpec
  openingSpec
  tuningSpec
  modifyMaxSuccess (const 50) modelSpec

-------------------------------------------------------------------------------
-- Databases to test against
-------------------------------------------------------------------------------

-- | A configuration with a Bloom filter and a prefix extractor, as a program
-- tuned for point lookups would have. The older tests run against it.
tuned :: Config
tuned =
  def
    { createIfMissing = True,
      errorIfExists = True,
      bloomFilter = True,
      prefixLength = Just 3
    }

-- | The defaults, creating the database. Tests that iterate over the whole
-- database use it, since a prefix extractor changes what a seek promises.
plain :: Config
plain = def {createIfMissing = True}

-- | Run a test in a temporary directory that is deleted afterwards.
withTempPath :: (FilePath -> IO a) -> IO a
withTempPath = withSystemTempDirectory "rocksdb-tests"

-- | A new 'tuned' database with the given column families.
withTunedDB :: [String] -> (DB -> IO a) -> IO a
withTunedDB cfs go =
  withTempPath $ \path -> withDBCF path tuned (map (,tuned) cfs) go

-- | A new 'plain' database with one column family besides the default.
withPlainDB :: (DB -> IO a) -> IO a
withPlainDB go =
  withTempPath $ \path ->
    withDBCF path plain {createMissingColumnFamilies = True} [("other", plain)] go

-------------------------------------------------------------------------------
-- Helpers
-------------------------------------------------------------------------------

-- | The first column family of a database opened with some.
firstFamily :: DB -> IO ColumnFamily
firstFamily db = case columnFamilies db of
  cf : _ -> return cf
  [] -> fail "the database has no column families"

-- | The column families of a database opened with exactly two.
twoFamilies :: DB -> IO (ColumnFamily, ColumnFamily)
twoFamilies db = case columnFamilies db of
  [a, b] -> return (a, b)
  cfs -> fail ("expected two column families, got " <> show (length cfs))

-- | A key that sorts by its number.
key :: Int -> ByteString
key = C.pack . printf "k%07d"

-- | The entries from where the iterator is until it stops being valid, moving
-- it with the given step: 'iterNext' to read forwards, 'iterPrev' backwards.
scan :: (Iterator -> IO ()) -> Iterator -> IO [(ByteString, ByteString)]
scan step itr = do
  valid <- iterValid itr
  if valid
    then do
      entry <- iterEntry itr
      step itr
      maybe id (:) entry <$> scan step itr
    else return []

-- | Every entry the iterator can reach, in ascending order of key. Fails if
-- the iterator stopped because of an error rather than at the end.
forwards :: Iterator -> IO [(ByteString, ByteString)]
forwards itr = do
  iterFirst itr
  entries <- scan iterNext itr
  iterGetError itr `shouldReturn` Nothing
  return entries

-- | Every entry the iterator can reach, in descending order of key.
backwards :: Iterator -> IO [(ByteString, ByteString)]
backwards itr = do
  iterLast itr
  entries <- scan iterPrev itr
  iterGetError itr `shouldReturn` Nothing
  return entries

-- | The time that so many runs of an action take, in seconds.
timed :: Int -> IO a -> IO Double
timed n action = do
  t0 <- getMonotonicTime
  replicateM_ n action
  t1 <- getMonotonicTime
  return (t1 - t0)

-- | Whether a property value is a number greater than zero.
positive :: Maybe ByteString -> Bool
positive = maybe False (maybe False ((> 0) . fst) . C.readInt)

-- | A number in the text of the @rocksdb.aggregated-table-properties@
-- property, which reads @name=value; name=value; ...@.
tableProperty :: ByteString -> ByteString -> Maybe Int
tableProperty name text =
  listToMaybe
    [ n
    | field <- C.split ';' text,
      let (k, v) = C.break (== '=') (C.dropWhile (== ' ') field),
      k == name,
      Just (n, _) <- [C.readInt (C.drop 1 v)]
    ]

-------------------------------------------------------------------------------
-- Examples against a tuned database
-------------------------------------------------------------------------------

boundSpec :: Spec
boundSpec = describe "The bound that ends a prefix" $ do
  it "gives the bound that ends a prefix" $ do
    prefixUpperBound "user:" `shouldBe` Just "user;"
    prefixUpperBound "a\xff\xff" `shouldBe` Just "b"
    prefixUpperBound "\xff\xff" `shouldBe` Nothing
    prefixUpperBound "" `shouldBe` Nothing
  prop "bounds exactly the keys with the prefix" $ \(ws, vs) ->
    let prefix = BS.pack ws
        rest = BS.pack vs
        inside b k = (prefix `BS.isPrefixOf` k) == (k >= prefix && k < b)
     in case prefixUpperBound prefix of
          Nothing -> BS.all (== 0xff) prefix
          -- a key that has the prefix, and one that most likely has not
          Just b -> inside b (prefix <> rest) && inside b rest

tunedSpec :: SpecWith DB
tunedSpec = do
  describe "Database" $ do
    it "puts and gets an item" $ \db -> do
      put db "aaa" "zzz"
      get db "aaa" `shouldReturn` Just "zzz"
    it "puts and gets from different column families" $ \db -> do
      two <- firstFamily db
      put db "aaa_key" "aaa_value"
      get db "aaa_key" `shouldReturn` Just "aaa_value"
      getCF db two "aaa_key" `shouldReturn` Nothing
      putCF db two "two_key" "two_value"
      getCF db two "two_key" `shouldReturn` Just "two_value"
      get db "two_key" `shouldReturn` Nothing
  describe "Multi-get" $ do
    it "reads many keys at once, in order, with missing ones" $ \db -> do
      one <- firstFamily db
      forM_ [1 .. 100 :: Int] $ \i -> do
        put db (C.pack (show i)) (C.pack ("v" <> show i))
        putCF db one (C.pack (show i)) (C.pack ("one" <> show i))
      let keys = map (C.pack . show) [50, 0, 1, 100, 101, 50 :: Int]
      multiGet db keys
        `shouldReturn` [Just "v50", Nothing, Just "v1", Just "v100", Nothing, Just "v50"]
      multiGetCF db one keys
        `shouldReturn` [Just "one50", Nothing, Just "one1", Just "one100", Nothing, Just "one50"]
      multiGet db [] `shouldReturn` []
      -- more keys than fit in one small buffer, most of them repeated
      let numbers = map (`mod` 150) [1 .. 2000 :: Int]
          expected i
            | i >= 1 && i <= 100 = Just (C.pack ("v" <> show i))
            | otherwise = Nothing
      multiGet db (map (C.pack . show) numbers) `shouldReturn` map expected numbers
  describe "Multithreading" $ do
    it "stores and retrieves items from multiple threads" $ \db -> do
      let val i = C.pack $ printf "val_%04d" i
          indices = [0 .. 9999] :: [Int]
      forConcurrently_ indices $ \i -> put db (key i) (val i)
      mapConcurrently (get db . key) indices `shouldReturn` map (Just . val) indices
  describe "Iterators on a tuned database" $ do
    it "retrieves entries written from many threads, in order" $ \db -> do
      let val i = C.pack $ printf "val_%03d" i
          indices = [0 .. 999] :: [Int]
          kvs = [(key i, val i) | i <- indices]
      forConcurrently_ kvs $ uncurry (put db)
      kvs' <- withIter db $ \itr -> do
        iterSeek itr (key 500)
        scan iterNext itr
      kvs' `shouldBe` drop 500 kvs
    it "seeks to the first key with a prefix" $ \db -> do
      forM_ ["aaa1", "aaa2", "bbb1", "bbb2", "ccc1"] $ \k -> put db k ("v" <> k)
      withIter db $ \itr -> do
        iterSeek itr "bbb"
        iterEntry itr `shouldReturn` Just ("bbb1", "vbbb1")
        iterNext itr
        iterEntry itr `shouldReturn` Just ("bbb2", "vbbb2")
  describe "Iterators and prefixes" $ do
    -- the prefix of this database is three bytes
    let keys = ["aaa1", "aaa2", "bbb1", "bbb2", "ccc1"] :: [ByteString]
        fill db = forM_ keys $ \k -> put db k k
        from k itr = iterSeek itr k >> map fst <$> scan iterNext itr
    it "stays within the prefix it was sent to" $ \db -> do
      fill db
      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do
        from "bbb" itr `shouldReturn` ["bbb1", "bbb2"]
        iterGetError itr `shouldReturn` Nothing
        -- the same iterator, sent elsewhere, has its bound there
        from "aaa2" itr `shouldReturn` ["aaa2"]
        from "ccc" itr `shouldReturn` ["ccc1"]
        from "abc" itr `shouldReturn` []
    it "stays within the prefix of the key it finds at either end" $ \db -> do
      fill db
      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do
        map fst <$> forwards itr `shouldReturn` ["aaa1", "aaa2"]
        map fst <$> backwards itr `shouldReturn` ["ccc1"]
    it "stays within the prefix going backwards" $ \db -> do
      fill db
      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do
        iterSeek itr "bbb2"
        map fst <$> scan iterPrev itr `shouldReturn` ["bbb2", "bbb1"]
    it "stays within the prefix when read in chunks" $ \db -> do
      fill db
      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do
        iterSeek itr "bbb"
        iterChunk itr def `shouldReturn` ([("bbb1", "bbb1"), ("bbb2", "bbb2")], False)
        iterValid itr `shouldReturn` False
        iterSeek itr "ccc"
        iterEntriesBack itr 10 `shouldReturn` [("ccc1", "ccc1")]
    it "stays within the prefix when the data is in table files" $ \db -> do
      fill db
      -- enough writes to flush the keys out of memory, where the prefix
      -- filters are
      forM_ [0 .. 20000] $ \i -> put db ("zzz" <> key i) (BS.replicate 1000 0)
      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do
        from "bbb" itr `shouldReturn` ["bbb1", "bbb2"]
        from "abc" itr `shouldReturn` []
    it "walks every prefix in order when asked for the total order" $ \db -> do
      fill db
      withIterConfig db Nothing def {totalOrderSeek = True} $ \itr -> do
        map fst <$> forwards itr `shouldReturn` keys
        map fst <$> backwards itr `shouldReturn` reverse keys
        from "abc" itr `shouldReturn` ["bbb1", "bbb2", "ccc1"]
    it "takes an upper bound across prefixes with the total order" $ \db -> do
      fill db
      let cfg = def {totalOrderSeek = True, upperBound = Just "bbb2"}
      withIterConfig db Nothing cfg (from "aaa2") `shouldReturn` ["aaa2", "bbb1"]

  describe "Properties" $ do
    it "reports memory use, per database and per column family" $ \db -> do
      one <- firstFamily db
      let isNumber = maybe False (\v -> not (C.null v) && C.all (`elem` ['0' .. '9']) v)
      forM_ [1 .. 1000] $ \i -> putCF db one (key i) "value"
      mem <- getPropertyCF db one CurSizeAllMemTables
      mem `shouldSatisfy` isNumber
      mem `shouldSatisfy` positive
      getProperty db EstimateTableReadersMem >>= (`shouldSatisfy` isNumber)
      getProperty db BlockCacheUsage >>= (`shouldSatisfy` isNumber)
      getProperty db (PropertyName "rocksdb.num-immutable-mem-table")
        >>= (`shouldSatisfy` isNumber)
      getProperty db (PropertyName "rocksdb.no-such-property")
        `shouldReturn` Nothing

-------------------------------------------------------------------------------
-- Examples against a plain database
-------------------------------------------------------------------------------

plainSpec :: SpecWith DB
plainSpec = do
  describe "Keys and values" $ do
    it "overwrites a value" $ \db -> do
      put db "k" "first"
      put db "k" "second"
      get db "k" `shouldReturn` Just "second"
    it "tells an empty value from an absent key" $ \db -> do
      put db "empty" ""
      get db "empty" `shouldReturn` Just ""
      get db "absent" `shouldReturn` Nothing
      multiGet db ["empty", "absent"] `shouldReturn` [Just "", Nothing]
    it "keeps bytes that C takes for the end of a string" $ \db -> do
      -- keys and values cross to C with their lengths, not as C strings
      let k = "a\0b"
          v = BS.pack [0, 255, 0, 10, 0]
      put db k v
      put db "a" "short"
      get db k `shouldReturn` Just v
      get db "a" `shouldReturn` Just "short"
      withIter db forwards `shouldReturn` [("a", "short"), (k, v)]
    it "stores a value of several megabytes" $ \db -> do
      let big = BS.replicate (4 * 1024 * 1024) 7
      put db "big" big
      get db "big" `shouldReturn` Just big
  describe "Deletes" $ do
    it "removes a key" $ \db -> do
      put db "k" "v"
      delete db "k"
      get db "k" `shouldReturn` Nothing
      withIter db forwards `shouldReturn` []
    it "accepts a key that is not there" $ \db -> do
      delete db "never written"
      get db "never written" `shouldReturn` Nothing
    it "removes a key from one column family only" $ \db -> do
      other <- firstFamily db
      put db "k" "default"
      putCF db other "k" "other"
      deleteCF db other "k"
      getCF db other "k" `shouldReturn` Nothing
      get db "k" `shouldReturn` Just "default"
      delete db "k"
      putCF db other "k" "again"
      get db "k" `shouldReturn` Nothing
      getCF db other "k" `shouldReturn` Just "again"
  describe "Batches" $ do
    it "applies puts and deletes across column families" $ \db -> do
      other <- firstFamily db
      put db "old" "v"
      putCF db other "old" "v"
      write
        db
        [ Put "a" "1",
          PutCF other "b" "2",
          Del "old",
          DelCF other "old"
        ]
      withIter db forwards `shouldReturn` [("a", "1")]
      withIterCF db other forwards `shouldReturn` [("b", "2")]
    it "applies operations in order" $ \db -> do
      write db [Put "k" "first", Put "k" "second", Put "gone" "v", Del "gone", Del "back", Put "back" "v"]
      withIter db forwards `shouldReturn` [("back", "v"), ("k", "second")]
    it "accepts an empty batch" $ \db -> do
      write db []
      withIter db forwards `shouldReturn` []
    it "writes a large batch" $ \db -> do
      let kvs = [(key i, C.pack (show i)) | i <- [1 .. 20000]]
      write db (map (uncurry Put) kvs)
      withIter db forwards `shouldReturn` kvs
  describe "Iterators" $ do
    it "is invalid on an empty database" $ \db ->
      withIter db $ \itr -> do
        iterFirst itr
        iterValid itr `shouldReturn` False
        iterLast itr
        iterValid itr `shouldReturn` False
        iterSeek itr "hello"
        iterKey itr `shouldReturn` Nothing
        iterValue itr `shouldReturn` Nothing
        iterEntry itr `shouldReturn` Nothing
        iterGetError itr `shouldReturn` Nothing
    it "walks back and forth" $ \db -> do
      put db "a" "aaa"
      put db "b" "bbb"
      put db "c" "ccc"
      withIter db $ \itr -> do
        iterSeek itr "b"
        iterEntry itr `shouldReturn` Just ("b", "bbb")
        iterNext itr
        iterEntry itr `shouldReturn` Just ("c", "ccc")
        iterNext itr -- after the last entry
        iterValid itr `shouldReturn` False
        iterKey itr `shouldReturn` Nothing
        iterValue itr `shouldReturn` Nothing
        iterPrev itr -- it cannot come back
        iterKey itr `shouldReturn` Nothing
        iterValue itr `shouldReturn` Nothing
      withIter db $ \itr -> do
        iterSeek itr "b"
        iterPrev itr
        iterEntry itr `shouldReturn` Just ("a", "aaa")
        iterPrev itr -- before the first entry
        iterValid itr `shouldReturn` False
        iterNext itr -- an invalid iterator stays invalid
        iterKey itr `shouldReturn` Nothing
        iterValue itr `shouldReturn` Nothing
    it "reads everything in both directions" $ \db -> do
      let kvs = [(key i, C.pack (show i)) | i <- [1 .. 100]]
      forM_ kvs $ uncurry (put db)
      withIter db forwards `shouldReturn` kvs
      withIter db backwards `shouldReturn` reverse kvs
    it "seeks to the next key when the one sought is absent" $ \db -> do
      forM_ [10, 20, 30] $ \i -> put db (key i) "v"
      withIter db $ \itr -> do
        iterSeek itr (key 15)
        iterKey itr `shouldReturn` Just (key 20)
        iterSeek itr (key 30)
        iterKey itr `shouldReturn` Just (key 30)
        iterSeek itr (key 31)
        iterValid itr `shouldReturn` False
    it "does not see writes made after it was created" $ \db -> do
      put db "a" "1"
      withIter db $ \itr -> do
        put db "b" "2"
        delete db "a"
        forwards itr `shouldReturn` [("a", "1")]
      withIter db forwards `shouldReturn` [("b", "2")]
    it "stays within its column family" $ \db -> do
      other <- firstFamily db
      put db "d" "default"
      putCF db other "o" "other"
      withIter db forwards `shouldReturn` [("d", "default")]
      withIterCF db other forwards `shouldReturn` [("o", "other")]
    it "can be created and destroyed by hand" $ \db -> do
      put db "a" "1"
      bracket (createIterator db Nothing) destroyIterator forwards
        `shouldReturn` [("a", "1")]
  describe "Bounded iterators" $ do
    let keys = ["a1", "a2", "b1", "b2", "c1", "c2"] :: [ByteString]
        fill db = forM_ keys $ \k -> put db k k
        from k itr = iterSeek itr k >> map fst <$> scan iterNext itr
    it "stops below an upper bound, which is outside" $ \db -> do
      fill db
      withIterConfig db Nothing def {upperBound = Just "b2"} $ \itr -> do
        from "a2" itr `shouldReturn` ["a2", "b1"]
        iterGetError itr `shouldReturn` Nothing
        map fst <$> backwards itr `shouldReturn` ["b1", "a2", "a1"]
        from "b2" itr `shouldReturn` []
    it "stops at a lower bound, which is inside" $ \db -> do
      fill db
      withIterConfig db Nothing def {lowerBound = Just "b1"} $ \itr -> do
        map fst <$> backwards itr `shouldReturn` ["c2", "c1", "b2", "b1"]
        map fst <$> forwards itr `shouldReturn` ["b1", "b2", "c1", "c2"]
        from "a1" itr `shouldReturn` ["b1", "b2", "c1", "c2"]
    it "keeps between two bounds" $ \db -> do
      fill db
      let cfg = def {lowerBound = Just "a2", upperBound = Just "c1"}
      withIterConfig db Nothing cfg $ \itr -> do
        map fst <$> forwards itr `shouldReturn` ["a2", "b1", "b2"]
        map fst <$> backwards itr `shouldReturn` ["b2", "b1", "a2"]
    it "scans a prefix with the bound that ends it" $ \db -> do
      fill db
      withIterConfig db Nothing def {upperBound = prefixUpperBound "b"} $ \itr ->
        from "b" itr `shouldReturn` ["b1", "b2"]
    it "returns nothing below an empty upper bound" $ \db -> do
      fill db
      withIterConfig db Nothing def {upperBound = Just ""} $ \itr ->
        forwards itr `shouldReturn` []
    it "is an ordinary iterator without bounds" $ \db -> do
      fill db
      withIterConfig db Nothing def $ \itr ->
        map fst <$> forwards itr `shouldReturn` keys
    it "keeps bounds with bytes that C takes for the end of a string" $ \db -> do
      let ks = ["k\0a", "k\0b", "k\0c"]
      forM_ ks $ \k -> put db k k
      withIterConfig db Nothing def {upperBound = Just "k\0c"} $ \itr ->
        map fst <$> forwards itr `shouldReturn` ["k\0a", "k\0b"]
    it "stays within its column family" $ \db -> do
      cf <- firstFamily db
      fill db
      putCF db cf "b3" "other"
      withIterConfig db (Just cf) def {upperBound = Just "c"} $ \itr ->
        forwards itr `shouldReturn` [("b3", "other")]
    it "reads from the snapshot of its database" $ \db -> do
      fill db
      withSnapshot db $ \snap -> do
        put db "b15" "late"
        delete db "b2"
        let cfg = def {upperBound = prefixUpperBound "b"}
        withIterConfig snap Nothing cfg (from "b") `shouldReturn` ["b1", "b2"]
        withIterConfig db Nothing cfg (from "b") `shouldReturn` ["b1", "b15"]
    it "can be created and destroyed by hand" $ \db -> do
      fill db
      (itr, destroyIt) <- createIteratorConfig db Nothing def {upperBound = Just "b"}
      from "a" itr `shouldReturn` ["a1", "a2"]
      destroyIt
    it "does not keep its bounds in memory that Haskell moves" $ \db -> do
      forM_ [0 .. 999] $ \i -> put db (key i) "v"
      -- the bound is built at run time, used by many iterators, and the
      -- heap is churned between seeks
      forM_ [1 .. 50 :: Int] $ \n ->
        withIterConfig db Nothing def {upperBound = Just (key (n * 10))} $ \itr -> do
          let junk = sum (map BS.length [key j | j <- [1 .. 20000]])
          junk `shouldBe` 160000
          iterSeek itr (key 0)
          length <$> scan iterNext itr `shouldReturn` n * 10
    it "does not step over deleted keys past its upper bound" $ \db -> do
      -- keys of "b" that are all deleted, between two keys that live: an
      -- unbounded scan of "a" reads every marker to find "c"
      let dead = [C.pack (printf "b%06d" i) | i <- [1 .. 20000 :: Int]]
      put db "a1" "v"
      put db "c1" "v"
      write db (map (\k -> Put k "v") dead)
      write db (map Del dead)
      let bounded = withIterConfig db Nothing def {upperBound = prefixUpperBound "a"} (from "a2")
          unbounded = withIter db $ \itr -> iterSeek itr "a2" >> iterKey itr
      bounded `shouldReturn` []
      unbounded `shouldReturn` Just "c1"
      slow <- timed 20 unbounded
      fast <- timed 20 bounded
      -- measured at 2,600 microseconds against 2.5; ten times leaves room
      -- for a busy machine
      (fast * 10 < slow) `shouldBe` True

  describe "Snapshots" $ do
    it "hides later writes and deletes from every kind of read" $ \db -> do
      other <- firstFamily db
      put db "a" "1"
      put db "b" "2"
      putCF db other "x" "100"
      withSnapshot db $ \snap -> do
        put db "a" "changed"
        delete db "b"
        put db "c" "3"
        putCF db other "x" "changed"
        get snap "a" `shouldReturn` Just "1"
        multiGet snap ["a", "b", "c"] `shouldReturn` [Just "1", Just "2", Nothing]
        getCF snap other "x" `shouldReturn` Just "100"
        withIter snap forwards `shouldReturn` [("a", "1"), ("b", "2")]
        withIterCF snap other forwards `shouldReturn` [("x", "100")]
        bracket (createIterator snap Nothing) destroyIterator forwards
          `shouldReturn` [("a", "1"), ("b", "2")]
      withIter db forwards `shouldReturn` [("a", "changed"), ("c", "3")]
    it "writes through a snapshot to the live database" $ \db ->
      withSnapshot db $ \snap -> do
        put snap "k" "v"
        get snap "k" `shouldReturn` Nothing
        get db "k" `shouldReturn` Just "v"
    it "agrees between point reads and iterators during concurrent writes" $ \db -> do
      cf <- firstFamily db
      let keys = ["key1", "key2", "key3"]
          original = [(k, "original") | k <- keys]
      forM_ original $ uncurry (putCF db cf)
      bracket (createSnapshot db) releaseSnapshot $ \(snap, _) -> do
        started <- newEmptyMVar
        let writer n = do
              forM_ keys $ \k -> putCF db cf k (C.pack ("v" <> show (n :: Int)))
              when (n == 0) $ putMVar started ()
              threadDelay 500
              writer (n + 1)
        withAsync (writer 0) $ \_ -> do
          takeMVar started
          forM_ original $ \(k, v) -> do
            getCF snap cf k `shouldReturn` Just v
            threadDelay 5000
          withIterCF snap cf forwards `shouldReturn` original
    it "pins iterators to a snapshot given to them" $ \db -> do
      other <- firstFamily db
      put db "a" "1"
      put db "b" "2"
      putCF db other "x" "100"
      bracket (createSnapshot db) releaseSnapshot $ \(_, snap) -> do
        put db "a" "modified"
        put db "c" "3"
        putCF db other "x" "modified"
        putCF db other "z" "300"
        -- the live handle, with the snapshot passed to the iterator
        withIterSnap db (Just snap) forwards `shouldReturn` [("a", "1"), ("b", "2")]
        withIterSnapCF db (Just snap) other forwards `shouldReturn` [("x", "100")]
        -- without one, they read the database as it is now
        withIterSnap db Nothing forwards
          `shouldReturn` [("a", "modified"), ("b", "2"), ("c", "3")]
        withIterSnapCF db Nothing other forwards
          `shouldReturn` [("x", "modified"), ("z", "300")]
    it "pins an iterator created by hand, which owns its read options" $ \db -> do
      put db "m" "10"
      put db "n" "20"
      bracket (createSnapshot db) releaseSnapshot $ \(_, snap) -> do
        put db "m" "changed"
        let create = createIteratorSnap db (Just snap) Nothing
            destroy' (itr, opts) = destroyIterator itr >> forM_ opts destroyReadOpts
        bracket create destroy' $ \(itr, opts) -> do
          opts `shouldSatisfy` isJust
          forwards itr `shouldReturn` [("m", "10"), ("n", "20")]
        bracket (createIteratorSnap db Nothing Nothing) destroy' $ \(itr, opts) -> do
          opts `shouldSatisfy` isNothing
          forwards itr `shouldReturn` [("m", "changed"), ("n", "20")]

-------------------------------------------------------------------------------
-- Reading many entries in one call
-------------------------------------------------------------------------------

-- | The bytes that the keys and values of some entries take, which is what
-- 'chunkBytes' limits.
sizeOf :: [(ByteString, ByteString)] -> Int
sizeOf entries = sum [BS.length k + BS.length v | (k, v) <- entries]

-- | Read chunk after chunk until one says that no more follow, and give the
-- chunks. Fails if a chunk is empty when the one before promised more: the
-- loop would never end.
chunksOf :: Iterator -> ChunkConfig -> IO [[(ByteString, ByteString)]]
chunksOf itr cfg = go []
  where
    go acc = do
      (entries, more) <- iterChunk itr cfg
      if more
        then do
          entries `shouldNotBe` []
          go (entries : acc)
        else return (reverse (entries : acc))

chunkSpec :: SpecWith DB
chunkSpec = describe "Reading many entries in one call" $ do
  let keys = ["a1", "a2", "b1", "b2", "c1"] :: [ByteString]
      fill db = forM_ keys $ \k -> put db k k
      same = map (\k -> (k, k))
      -- ten entries of 108 bytes each: a key of 8 and a value of 100
      wide = [(key i, BS.replicate 100 (fromIntegral i)) | i <- [0 .. 9]]
  it "reads the next entries and leaves the iterator after them" $ \db -> do
    fill db
    withIter db $ \itr -> do
      iterFirst itr
      iterEntries itr 2 `shouldReturn` same ["a1", "a2"]
      iterKey itr `shouldReturn` Just "b1"
      iterEntries itr 100 `shouldReturn` same ["b1", "b2", "c1"]
      iterValid itr `shouldReturn` False
      iterEntries itr 100 `shouldReturn` []
  it "reads backwards, in descending order" $ \db -> do
    fill db
    withIter db $ \itr -> do
      iterLast itr
      iterEntriesBack itr 2 `shouldReturn` same ["c1", "b2"]
      iterKey itr `shouldReturn` Just "b1"
      iterEntriesBack itr 100 `shouldReturn` same ["b1", "a2", "a1"]
      iterValid itr `shouldReturn` False
  it "reads nothing, and stays, when asked for no entries" $ \db -> do
    fill db
    withIter db $ \itr -> do
      iterSeek itr "b1"
      iterEntries itr 0 `shouldReturn` []
      iterEntries itr (-3) `shouldReturn` []
      iterEntriesBack itr minBound `shouldReturn` []
      iterChunk itr def {chunkEntries = 0} `shouldReturn` ([], True)
      iterKey itr `shouldReturn` Just "b1"
  it "stops at the first key outside the prefix, and stays on it" $ \db -> do
    fill db
    withIter db $ \itr -> do
      iterSeek itr "b"
      iterEntriesPrefix itr "b" 100 `shouldReturn` same ["b1", "b2"]
      iterKey itr `shouldReturn` Just "c1"
      iterEntriesPrefix itr "b" 100 `shouldReturn` []
      iterKey itr `shouldReturn` Just "c1"
      iterSeek itr "b2"
      iterEntriesPrefixBack itr "b" 100 `shouldReturn` same ["b2", "b1"]
      iterKey itr `shouldReturn` Just "a2"
  it "takes a key equal to the prefix, and not one shorter than it" $ \db -> do
    forM_ ["a", "ab", "abc", "b"] $ \k -> put db k ""
    withIter db $ \itr -> do
      iterFirst itr
      iterEntriesPrefix itr "ab" 100 `shouldReturn` []
      iterSeek itr "ab"
      map fst <$> iterEntriesPrefix itr "ab" 100 `shouldReturn` ["ab", "abc"]
  it "tells whether more entries follow" $ \db -> do
    fill db
    withIter db $ \itr -> do
      let cfg = def {chunkPrefix = "a"}
      iterFirst itr
      iterChunk itr cfg {chunkEntries = 1} `shouldReturn` (same ["a1"], True)
      -- the limit is reached where the prefix ends: nothing follows
      iterFirst itr
      iterChunk itr cfg {chunkEntries = 2} `shouldReturn` (same ["a1", "a2"], False)
      iterChunk itr cfg `shouldReturn` ([], False)
      -- and where the data ends
      iterSeek itr "c1"
      iterChunk itr def {chunkEntries = 1} `shouldReturn` (same ["c1"], False)
  it "stops before the limit of bytes" $ \db -> do
    forM_ wide $ uncurry (put db)
    withIter db $ \itr -> do
      let sizes bytes = do
            iterFirst itr
            map length <$> chunksOf itr def {chunkBytes = bytes}
      -- two entries are 216 bytes
      sizes 250 `shouldReturn` [2, 2, 2, 2, 2]
      sizes 216 `shouldReturn` [2, 2, 2, 2, 2]
      sizes 215 `shouldReturn` [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
      sizes 500 `shouldReturn` [4, 4, 2]
      sizes maxBound `shouldReturn` [10]
  it "reads one entry at least, whatever the limit of bytes" $ \db -> do
    forM_ wide $ uncurry (put db)
    withIter db $ \itr -> forM_ [0, 1, 107, -1, minBound] $ \bytes -> do
      iterFirst itr
      chunks <- chunksOf itr def {chunkBytes = bytes}
      chunks `shouldBe` map (: []) wide
  it "gets past an entry larger than the limit of bytes" $ \db -> do
    -- three megabytes between small entries, with a limit of one
    let big = BS.replicate (3 * 1024 * 1024) 7
        entries = [("a", "small"), ("b", big), ("c", "small"), ("d", "small")]
    forM_ entries $ uncurry (put db)
    withIter db $ \itr -> do
      iterFirst itr
      chunks <- chunksOf itr def
      map (map fst) chunks `shouldBe` [["a"], ["b"], ["c", "d"]]
      concat chunks `shouldBe` entries
      iterLast itr
      back <- chunksOf itr def {chunkBackwards = True}
      map (map fst) back `shouldBe` [["d", "c"], ["b"], ["a"]]
  it "reads across many chunks what single steps read" $ \db -> do
    let entries = [(key i, C.pack (show i)) | i <- [0 .. 9999]]
    write db (map (uncurry Put) entries)
    withIter db $ \itr -> forM_ [1, 7, 256, 10000, 20000] $ \n -> do
      iterFirst itr
      chunks <- chunksOf itr def {chunkEntries = n}
      concat chunks `shouldBe` entries
      map length (init chunks) `shouldSatisfy` all (== n)
      iterLast itr
      back <- chunksOf itr def {chunkEntries = n, chunkBackwards = True}
      concat back `shouldBe` reverse entries
  it "stops at the bounds of the iterator" $ \db -> do
    fill db
    withIterConfig db Nothing def {lowerBound = Just "a2", upperBound = Just "b2"} $ \itr -> do
      iterFirst itr
      iterChunk itr def `shouldReturn` (same ["a2", "b1"], False)
      iterValid itr `shouldReturn` False
      iterLast itr
      iterChunk itr def {chunkBackwards = True} `shouldReturn` (same ["b1", "a2"], False)
      iterValid itr `shouldReturn` False
  it "reads a prefix backwards from the bound that ends it" $ \db -> do
    fill db
    withIterConfig db Nothing def {upperBound = prefixUpperBound "a"} $ \itr -> do
      iterLast itr
      iterEntriesPrefixBack itr "a" 100 `shouldReturn` same ["a2", "a1"]
  it "returns nothing where there is nothing" $ \db -> do
    withIter db $ \itr -> do
      iterFirst itr
      iterChunk itr def `shouldReturn` ([], False)
      iterEntries itr 10 `shouldReturn` []
    fill db
    withIter db $ \itr -> do
      -- not sent anywhere yet
      iterChunk itr def `shouldReturn` ([], False)
      -- a prefix that no key has
      iterSeek itr "b3"
      iterChunk itr def {chunkPrefix = "b3"} `shouldReturn` ([], False)
      iterKey itr `shouldReturn` Just "c1"
      -- past the last key
      iterSeek itr "d"
      iterChunk itr def `shouldReturn` ([], False)
      iterChunk itr def {chunkBackwards = True} `shouldReturn` ([], False)
  it "keeps bytes that C takes for the end of a string, and empty keys and values" $ \db -> do
    let entries = [("", "empty key"), ("\0", ""), ("\0\0a", "\0b\0"), ("\0\255", "\255\0")]
    forM_ entries $ uncurry (put db)
    withIter db $ \itr -> do
      iterFirst itr
      iterEntries itr 100 `shouldReturn` entries
      iterSeek itr "\0"
      iterEntriesPrefix itr "\0\0" 100 `shouldReturn` []
      iterEntriesPrefix itr "\0" 100 `shouldReturn` drop 1 entries
  it "stays within its column family" $ \db -> do
    other <- firstFamily db
    fill db
    putCF db other "b9" "other"
    withIterCF db other $ \itr -> do
      iterFirst itr
      iterEntries itr 100 `shouldReturn` [("b9", "other")]
  it "returns entries that outlive the iterator" $ \db -> do
    let entries = [(key i, BS.replicate 50 (fromIntegral i)) | i <- [0 .. 999]]
    write db (map (uncurry Put) entries)
    got <- withIter db $ \itr -> iterFirst itr >> iterEntries itr 1000
    -- the heap is churned before the entries are looked at
    sum (map BS.length [key j | j <- [1 .. 20000]]) `shouldBe` 160000
    got `shouldBe` entries
  it "reads the same from many threads at once" $ \db -> do
    let entries = [(key i, C.pack (show i)) | i <- [0 .. 19999]]
    write db (map (uncurry Put) entries)
    results <- forConcurrently [1 .. 16 :: Int] $ \n ->
      withIter db $ \itr -> do
        iterFirst itr
        concat <$> chunksOf itr def {chunkEntries = n * 10}
    forM_ results (`shouldBe` entries)

-- | An iterator that meets a block it cannot read is no longer valid, which
-- is also how it looks at the end of the data. A scan in chunks has to tell
-- the two apart by itself, since its caller gets a list and nothing else.
chunkErrorSpec :: Spec
chunkErrorSpec = describe "Reading many entries from a damaged file" $ do
  it "throws, where single steps look as if the data had ended" $
    withTempPath $ \path -> do
      -- compacted, so that the entries are in a table file
      withDB path plain $ \db -> do
        forM_ [0 .. 999] $ \i -> put db (key i) (BS.replicate 100 (fromIntegral i))
        compactRange db Nothing Nothing Nothing
      tables <- filter (".sst" `isSuffixOf`) <$> listDirectory path
      tables `shouldNotBe` []
      -- garbage over the start of each file, where the first block of
      -- entries is: its checksum no longer matches
      forM_ tables $ \table ->
        withBinaryFile (path </> table) ReadWriteMode $ \h -> do
          hSeek h AbsoluteSeek 100
          BS.hPut h (BS.replicate 100 0xa5)
      withDB path plain $ \db -> withIter db $ \itr -> do
        iterFirst itr
        iterValid itr `shouldReturn` False
        iterGetError itr >>= (`shouldSatisfy` isJust)
        iterFirst itr
        iterChunk itr def `shouldThrow` anyIOException
        iterFirst itr
        iterEntries itr 10 `shouldThrow` anyIOException

-------------------------------------------------------------------------------
-- Packed batches
-------------------------------------------------------------------------------

-- | A write to a column family that is named by its number, so that the same
-- operation can be given to two databases: zero is the default family, and
-- the others are those of 'columnFamilies' from one. 'Nothing' deletes.
data FamilyOp = FamilyOp Int ByteString (Maybe ByteString)

-- | The operation of a batch for a database.
batchOp :: DB -> FamilyOp -> BatchOp
batchOp _ (FamilyOp 0 k (Just v)) = Put k v
batchOp _ (FamilyOp 0 k Nothing) = Del k
batchOp db (FamilyOp n k mv) = case drop (n - 1) (columnFamilies db) of
  cf : _ -> maybe (DelCF cf k) (PutCF cf k) mv
  [] -> error ("no column family " <> show n)

-- | Every entry of every column family of a database, the default one
-- first.
contents :: DB -> IO [[(ByteString, ByteString)]]
contents db = (:) <$> withIter db forwards <*> forM (columnFamilies db) (\cf -> withIterCF db cf forwards)

-- | Two new databases with the same three column families besides the
-- default: one to write with 'write', and one with 'writePacked'.
withTwoDBs :: (DB -> DB -> IO a) -> IO a
withTwoDBs go = new (new . go)
  where
    families = map (,plain) ["one", "two", "three"]
    new f = withTempPath $ \path -> withDBCF path plain {createMissingColumnFamilies = True} families f

-- | Require that the operations, cut into chunks of so many, leave what
-- they leave when they are written with 'write': in every column family.
shouldWriteAs :: Int -> [FamilyOp] -> IO ()
shouldWriteAs size ops = withTwoDBs $ \expected packed -> do
  write expected (map (batchOp expected) ops)
  writePacked packed (map packOps (groupsOf size (map (batchOp packed) ops)))
  written <- contents packed
  wanted <- contents expected
  map length written `shouldBe` map length wanted
  written `shouldBe` wanted

-- | A list in pieces of a length, the last one shorter.
groupsOf :: Int -> [a] -> [[a]]
groupsOf _ [] = []
groupsOf n xs = let (a, b) = splitAt n xs in a : groupsOf n b

-- | A chunk with one record, written as a program that packs its own
-- chunks does: room for the header, the key and the value after it, and
-- then the header. The record starts at an odd address, since records are
-- not aligned.
record :: Maybe ColumnFamily -> PackedOp -> ByteString -> ByteString -> ByteString
record mcf op k v =
  BS.drop 1 . BI.unsafeCreate (1 + size) $ \buffer -> do
    let start = buffer `plusPtr` 1 :: Ptr Word8
        key_ptr = start `plusPtr` packedHeaderSize
    copy k key_ptr
    copy v (key_ptr `plusPtr` BS.length k)
    pokePackedHeader start mcf op (BS.length k) (BS.length v)
  where
    size = packedHeaderSize + BS.length k + BS.length v
    copy bytes to =
      BS.useAsCStringLen bytes $ \(from, len) -> copyBytes to (castPtr from) len

-- | Replace the bytes at an offset.
patch :: Int -> [Word8] -> ByteString -> ByteString
patch at bytes whole = BS.take at whole <> BS.pack bytes <> BS.drop (at + length bytes) whole

-- | A batch that a small C function of the package hands to RocksDB, a few
-- thousand operations at a call. It has to do what 'write' does with the
-- same operations, and it reads a buffer that the caller made: so it must
-- not believe what the buffer says about its own lengths.
packedSpec :: Spec
packedSpec = describe "Packed batches" $ do
  let several =
        [ FamilyOp 0 "a" (Just "default"),
          FamilyOp 1 "a" (Just "one"),
          FamilyOp 2 "a" (Just "two"),
          FamilyOp 3 "a" (Just "three"),
          FamilyOp 0 "empty value" (Just ""),
          FamilyOp 2 "" (Just "empty key"),
          FamilyOp 3 "zero\0inside" (Just "\0\0"),
          FamilyOp 1 "gone" (Just "v"),
          FamilyOp 1 "gone" Nothing,
          FamilyOp 2 "never there" Nothing
        ]
      -- twenty thousand operations over four families: every key is set,
      -- every third one is set again and every seventh deleted
      many =
        concat
          [ [FamilyOp (i `mod` 4) (key i) (Just (C.pack (show i)))]
              <> [FamilyOp (i `mod` 4) (key i) (Just "again") | i `mod` 3 == 0]
              <> [FamilyOp (i `mod` 4) (key i) Nothing | i `mod` 7 == 0]
          | i <- [1 .. 14000]
          ]
  it "writes what the same operations written with write leave, in every column family" $ do
    shouldWriteAs (length several) several
    withTwoDBs $ \_ db -> do
      writePacked db [packOps (map (batchOp db) several)]
      contents db
        `shouldReturn` [ [("a", "default"), ("empty value", "")],
                         [("a", "one")],
                         [("", "empty key"), ("a", "two")],
                         [("a", "three"), ("zero\0inside", "\0\0")]
                       ]
  it "applies operations in order, within a chunk and from one chunk to the next" $ do
    let ops =
          [ FamilyOp 0 "k" (Just "first"),
            FamilyOp 0 "k" (Just "second"),
            FamilyOp 1 "gone" (Just "v"),
            FamilyOp 1 "gone" Nothing,
            FamilyOp 1 "back" Nothing,
            FamilyOp 1 "back" (Just "v")
          ]
    forM_ [1, 2, 3, 6] $ \size -> do
      shouldWriteAs size ops
      withTwoDBs $ \_ db -> do
        writePacked db (map packOps (groupsOf size (map (batchOp db) ops)))
        contents db `shouldReturn` [[("k", "second")], [("back", "v")], [], []]
  it "accepts no chunk, and empty chunks among the others" $
    withTwoDBs $ \_ db -> do
      writePacked db []
      writePacked db [BS.empty]
      contents db `shouldReturn` [[], [], [], []]
      writePacked db [BS.empty, packOps [Put "a" "1"], BS.empty, packOps [], packOps [Put "b" "2"]]
      contents db `shouldReturn` [[("a", "1"), ("b", "2")], [], [], []]
  it "writes a large batch, in one chunk and over many" $ do
    length many `shouldSatisfy` (> 20000)
    shouldWriteAs (length many) many
    shouldWriteAs 97 many
    shouldWriteAs 1 (take 3000 many)
  it "takes records that a program wrote into a buffer of its own" $
    withTwoDBs $ \_ db -> do
      other <- firstFamily db
      packedHeaderSize `shouldBe` BS.length (packOps [Put "" ""])
      record Nothing PackedPut "key" "value" `shouldBe` packOps [Put "key" "value"]
      record (Just other) PackedPut "key" "" `shouldBe` packOps [PutCF other "key" ""]
      record (Just other) PackedDel "key" "" `shouldBe` packOps [DelCF other "key"]
      put db "old" "v"
      writePacked
        db
        [ record Nothing PackedPut "a" "1" <> record (Just other) PackedPut "b" "2",
          record Nothing PackedDel "old" ""
        ]
      contents db `shouldReturn` [[("a", "1")], [("b", "2")], [], []]
  it "refuses a header that cannot be: a length that is negative, a delete with a value" $ do
    evaluate (record Nothing PackedPut "k" "v") `shouldReturn` packOps [Put "k" "v"]
    evaluate (record Nothing PackedDel "k" "v") `shouldThrow` anyIOException
    BI.create 64 (\p -> pokePackedHeader p Nothing PackedPut (-1) 0) `shouldThrow` anyIOException
    BI.create 64 (\p -> pokePackedHeader p Nothing PackedPut 0 (-1)) `shouldThrow` anyIOException
  describe "A chunk that is not made of whole records" $ do
    let good = packOps [Put "before" "v"]
        -- two records of 17 bytes of header, a key of 3 and a value of 5
        chunk = packOps [Put "aaa" "11111", Put "bbb" "22222"]
        size = BS.length chunk `div` 2
        operation = packedHeaderSize - 1
        key_len = packedHeaderSize - 9
        value_len = packedHeaderSize - 5
        -- the chunk is refused, by this package and not by RocksDB, with
        -- the number of its first bad record, and nothing of the batch is
        -- written: not the good chunks around it either
        refused n bad = withTwoDBs $ \_ db -> do
          writePacked db [good, bad, good] `shouldThrow` \e ->
            ("writePacked: chunk 1 " `isPrefixOf` ioeGetErrorString e)
              && ((": record " <> show (n :: Int) <> " is") `isInfixOf` ioeGetErrorString e)
          writePacked db [bad] `shouldThrow` anyIOException
          contents db `shouldReturn` [[], [], [], []]
          -- and the database is still good for a batch
          writePacked db [good]
          contents db `shouldReturn` [[("before", "v")], [], [], []]
    it "is written when nothing is wrong with it" $
      withTwoDBs $ \_ db -> do
        writePacked db [good, chunk, good]
        contents db `shouldReturn` [[("aaa", "11111"), ("bbb", "22222"), ("before", "v")], [], [], []]
    it "is refused when it ends within a value" $
      refused 1 (BS.init chunk)
    it "is refused when it ends within a key" $
      refused 1 (BS.take (size + packedHeaderSize + 1) chunk)
    it "is refused when it ends within a header, or right after one" $ do
      refused 1 (BS.take (size + 1) chunk)
      refused 1 (BS.take (size + packedHeaderSize - 1) chunk)
      refused 1 (BS.take (size + packedHeaderSize) chunk)
      refused 0 (BS.take 1 chunk)
    it "is refused when bytes follow its last record" $
      refused 2 (chunk <> "\0")
    it "is refused when a length says more than there is" $ do
      refused 1 (patch (size + key_len) [9, 0, 0, 0] chunk)
      refused 1 (patch (size + value_len) [6, 0, 0, 0] chunk)
      refused 0 (patch key_len [255, 255, 255, 255] chunk)
      refused 0 (patch value_len [255, 255, 255, 255] chunk)
      refused 0 (patch key_len [255, 255, 255, 255] (patch value_len [255, 255, 255, 255] chunk))
    it "is refused when it names an operation that does not exist" $ do
      refused 1 (patch (size + operation) [3] chunk)
      refused 0 (patch operation [255] chunk)
    it "is refused when a delete has a value" $
      refused 1 (patch (size + operation) [1] chunk)
  describe "A merge" $ do
    -- What a merge does to a value is for the tests of merge records. Here:
    -- that a packed record is taken for a merge and handed to RocksDB as
    -- one. RocksDB 11 says so itself, by refusing the batch for want of a
    -- merge operator. A RocksDB that took such a batch would have a merge
    -- record under the key, and no way to read it.
    it "is handed to RocksDB as a merge, in the default column family and in another" $
      withTwoDBs $ \_ db -> do
        other <- firstFamily db
        let asMerge chunks reading = do
              written <- try (writePacked db chunks)
              case written of
                Left e -> do
                  ioeGetErrorString e `shouldSatisfy` (not . ("writePacked" `isPrefixOf`))
                  ioeGetErrorString e `shouldSatisfy` ("erge" `isInfixOf`)
                  -- the merge was not written; the put that came before
                  -- it in the batch was not either with RocksDB 11, and
                  -- was with RocksDB 8.9
                  contents db >>= (`shouldSatisfy` (`elem` [[[], [], [], []], [[("a", "1")], [], [], []]]))
                Right () -> reading `shouldThrow` anyIOException
        asMerge [packOps [Put "a" "1"], record Nothing PackedMerge "k" "v"] (get db "k")
        asMerge [record (Just other) PackedMerge "k" "v", packOps [Put "a" "1"]] (getCF db other "k")
        record Nothing PackedMerge "k" "v" `shouldBe` packOps [Merge "k" "v"]
        record (Just other) PackedMerge "k" "v" `shouldBe` packOps [MergeCF other "k" "v"]

-------------------------------------------------------------------------------
-- Merge records and merge operators
-------------------------------------------------------------------------------

-- The merge operator of the tests, in @test\/cbits\/merge_test.c@: the
-- value of a key is the value it had and its merge records, oldest first,
-- joined with commas. The value shows which records were merged and in
-- which order, which a sum would not.
foreign import ccall "&rocksdb_haskell_test_join_full" joinFull :: FunPtr FullMerge

foreign import ccall "&rocksdb_haskell_test_join_partial" joinPartial :: FunPtr PartialMerge

foreign import ccall "&rocksdb_haskell_test_no_partial" noPartial :: FunPtr PartialMerge

-- | Join with commas.
joining :: MergeOperator
joining = MergeFunctions {mergeName = "test-join", fullMerge = joinFull, partialMerge = joinPartial}

-- | Join with commas, with a partial merge that always fails: RocksDB has
-- to keep every record until it has the value under them.
joiningWhole :: MergeOperator
joiningWhole = MergeFunctions {mergeName = "test-join-whole", fullMerge = joinFull, partialMerge = noPartial}

-- | A number as RocksDB's own operator for counters reads and writes it:
-- eight bytes, the least significant first.
counter :: Word64 -> ByteString
counter n = BS.pack [fromIntegral (n `shiftR` (8 * i)) | i <- [0 .. 7]]

-- | The configuration of a column family, or of the database, with a merge
-- operator. Nothing is compacted behind the back of a test, so that each
-- flush leaves a table file of its own and merge records stay where they
-- were written until the test compacts.
merging :: Maybe MergeOperator -> Config
merging op = plain {createMissingColumnFamilies = True, mergeOperator = op, disableAutoCompactions = True}

-- | The families of 'withMergeDB' besides the default.
mergeFamilies :: [(String, Config)]
mergeFamilies =
  [ ("count", merging (Just UInt64Add)),
    ("whole", merging (Just joiningWhole)),
    ("none", merging Nothing)
  ]

-- | A database whose default column family joins with commas, with three
-- more: one that counts, one that joins and cannot merge records without
-- the value, and one without a merge operator.
withMergeDB :: (DB -> ColumnFamily -> ColumnFamily -> ColumnFamily -> IO a) -> IO a
withMergeDB go = withTempPath $ \path -> openMergeDB path go

openMergeDB :: FilePath -> (DB -> ColumnFamily -> ColumnFamily -> ColumnFamily -> IO a) -> IO a
openMergeDB path go =
  withDBCF path (merging (Just joining)) mergeFamilies $ \db -> case columnFamilies db of
    [count, whole, none] -> go db count whole none
    cfs -> fail ("expected three column families, got " <> show (length cfs))

-- | Flush every column family of a database.
flushAll :: DB -> IO ()
flushAll db = flush db Nothing >> mapM_ (flush db . Just) (columnFamilies db)

-- | Compact every column family of a database, to its last level.
compactAll :: DB -> IO ()
compactAll db = do
  compactRange db Nothing Nothing Nothing
  forM_ (columnFamilies db) $ \cf -> compactRange db (Just cf) Nothing Nothing

-- | A merge record says how a value changes, and the merge operator of the
-- column family works out the value when it is read or compacted. What can
-- go wrong is the order of the records, what a put or a delete among them
-- hides, and a value that depends on where its parts happen to be: in the
-- memtable, in several table files, or compacted into one.
mergeSpec :: Spec
mergeSpec = describe "Merge records" $ do
  it "adds to a counter, from zero where the key has no value" $
    withMergeDB $ \db count _ _ -> do
      mergeCF db count "k" (counter 5)
      getCF db count "k" `shouldReturn` Just (counter 5)
      mergeCF db count "k" (counter 7)
      getCF db count "k" `shouldReturn` Just (counter 12)
      putCF db count "set" (counter 100)
      mergeCF db count "set" (counter 1)
      getCF db count "set" `shouldReturn` Just (counter 101)
      -- modulo 2^64, so a record can take away as well
      mergeCF db count "set" (counter (negate 101))
      getCF db count "set" `shouldReturn` Just (counter 0)
      getCF db count "absent" `shouldReturn` Nothing
  it "gives a custom operator the value and the records, oldest first" $
    withMergeDB $ \db _ _ _ -> do
      merge db "new" "a"
      get db "new" `shouldReturn` Just "a"
      merge db "new" "b"
      merge db "new" "c"
      get db "new" `shouldReturn` Just "a,b,c"
      put db "old" "x"
      merge db "old" "y"
      get db "old" `shouldReturn` Just "x,y"
      -- a value of no bytes is a value, and a record of no bytes a record
      put db "empty" ""
      merge db "empty" ""
      get db "empty" `shouldReturn` Just ","
  it "hides the records before a put or a delete, and applies those after" $
    withMergeDB $ \db _ _ _ -> do
      merge db "put" "a" >> put db "put" "x" >> merge db "put" "b"
      get db "put" `shouldReturn` Just "x,b"
      merge db "del" "a" >> delete db "del"
      get db "del" `shouldReturn` Nothing
      merge db "del" "b"
      get db "del" `shouldReturn` Just "b"
      put db "last" "x" >> merge db "last" "a" >> delete db "last"
      get db "last" `shouldReturn` Nothing
      -- and the same when each write is in a table file of its own
      forM_ [merge db "files" "a", put db "files" "x", merge db "files" "b", delete db "files", merge db "files" "c"] $
        \step -> step >> flush db Nothing
      get db "files" `shouldReturn` Just "c"
      merge db "files" "d"
      get db "files" `shouldReturn` Just "c,d"
  it "takes merges in a batch, among puts and deletes, written either way" $ do
    let ops count whole =
          [ Put "a" "1",
            Merge "a" "2",
            MergeCF count "n" (counter 3),
            Merge "b" "x",
            MergeCF whole "a" "w",
            Merge "a" "3",
            MergeCF count "n" (counter 4),
            Put "gone" "v",
            Merge "gone" "w",
            Del "gone",
            MergeCF whole "a" "v"
          ]
        wanted = [[("a", "1,2,3"), ("b", "x")], [("n", counter 7)], [("a", "w,v")], []]
    withMergeDB $ \db count whole _ -> do
      write db (ops count whole)
      contents db `shouldReturn` wanted
    withMergeDB $ \db count whole _ -> do
      writePacked db [packOps (ops count whole)]
      contents db `shouldReturn` wanted
    withMergeDB $ \db count whole _ -> do
      writePacked db (map packOps (groupsOf 2 (ops count whole)))
      contents db `shouldReturn` wanted
  it "gives the same values from the memtable, from table files and after a compaction" $
    withMergeDB $ \db count whole _ -> do
      let keys = ["both", "records", "value"] :: [ByteString]
          wanted =
            [ [("both", "x,a,b,c"), ("records", "a,b,c"), ("value", "x")],
              [("both", counter 16), ("records", counter 6), ("value", counter 10)],
              [("both", "x,a,b,c"), ("records", "a,b,c"), ("value", "x")],
              []
            ]
          -- every way of reading, in every family
          agree = do
            contents db `shouldReturn` wanted
            forM_ (zip (Nothing : map Just (columnFamilies db)) wanted) $ \(mcf, entries) -> do
              let values = map (`lookup` entries) keys
              case mcf of
                Nothing -> do
                  mapM (get db) keys `shouldReturn` values
                  multiGet db keys `shouldReturn` values
                  withIter db backwards `shouldReturn` reverse entries
                  withIter db (\itr -> iterFirst itr >> iterEntries itr 10) `shouldReturn` entries
                Just cf -> do
                  mapM (getCF db cf) keys `shouldReturn` values
                  multiGetCF db cf keys `shouldReturn` values
                  withIterCF db cf backwards `shouldReturn` reverse entries
                  withIterCF db cf (\itr -> iterFirst itr >> iterEntries itr 10) `shouldReturn` entries
          each k v n = do
            merge db k v
            mergeCF db whole k v
            mergeCF db count k (counter n)
      forM_ ["both", "value"] $ \k -> do
        put db k "x"
        putCF db whole k "x"
        putCF db count k (counter 10)
      flushAll db
      forM_ [("a", 1), ("b", 2)] $ \(v, n) -> do
        each "both" v n
        each "records" v n
        flushAll db
      -- the last record of each key is in the memtable, the others in a
      -- table file each, and the value in another
      each "both" "c" 3
      each "records" "c" 3
      agree
      withSnapshot db $ \snap -> do
        merge db "both" "later"
        get snap "both" `shouldReturn` Just "x,a,b,c"
        delete db "both" >> put db "both" "x,a,b,c"
      flushAll db
      agree
      compactAll db
      agree
      -- and what is merged after the compaction is merged with its result
      each "both" "d" 4
      get db "both" `shouldReturn` Just "x,a,b,c,d"
      getCF db whole "both" `shouldReturn` Just "x,a,b,c,d"
      getCF db count "both" `shouldReturn` Just (counter 20)
  it "keeps its values when the database is closed and opened again" $
    withTempPath $ \path -> do
      openMergeDB path $ \db count whole _ -> do
        put db "k" "x" >> merge db "k" "a"
        flushAll db
        -- these are in the write-ahead log only
        merge db "k" "b"
        mergeCF db count "n" (counter 2)
        mergeCF db whole "k" "w"
      openMergeDB path $ \db _ _ _ ->
        contents db `shouldReturn` [[("k", "x,a,b")], [("n", counter 2)], [("k", "w")], []]
  it "throws at the read of a key whose merge fails, and at no other" $
    withMergeDB $ \db _ _ _ -> do
      merge db "bad" "a" >> merge db "bad" "!" >> merge db "bad" "b"
      put db "good" "x" >> merge db "good" "y"
      get db "bad" `shouldThrow` anyIOException
      get db "good" `shouldReturn` Just "x,y"
      withIter db (\itr -> iterFirst itr >> iterEntries itr 10) `shouldThrow` anyIOException
      -- a put hides the record that cannot be merged
      put db "bad" "mended"
      get db "bad" `shouldReturn` Just "mended"
      withIter db forwards `shouldReturn` [("bad", "mended"), ("good", "x,y")]
  it "refuses a merge in a column family that has no merge operator" $
    withMergeDB $ \db _ _ none -> do
      mergeCF db none "k" "v" `shouldThrow` anyIOException
      write db [Put "a" "1", MergeCF none "k" "v"] `shouldThrow` anyIOException
      writePacked db [packOps [Put "a" "1", MergeCF none "k" "v"]] `shouldThrow` anyIOException
      -- the merge is nowhere; RocksDB 8.9 keeps the put that came before
      -- it in the refused batch, RocksDB 11 does not
      contents db >>= (`shouldSatisfy` (`elem` [[[], [], [], []], [[("a", "1")], [], [], []]]))
  -- A database is opened without the merge operator that its records need
  -- by a program that does not know of them. RocksDB opens it all the
  -- same. This is what RocksDB 11 does with records that are in table
  -- files, as far as it can be tried: a read of a key that has a value
  -- under its records, with 'get' or 'multiGet', crashes the process.
  it "cannot read merge records in table files without their operator, and keeps them" $
    withTempPath $ \path -> do
      let without = [(name, cfg {mergeOperator = Nothing}) | (name, cfg) <- mergeFamilies]
      openMergeDB path $ \db _ _ _ -> do
        put db "plain" "x"
        merge db "records" "a" >> merge db "records" "b"
        flushAll db
      withDBCF path (merging Nothing) without $ \db -> do
        get db "plain" `shouldReturn` Just "x"
        get db "records" `shouldThrow` anyIOException
        withIter db (\itr -> iterFirst itr >> iterEntries itr 10) `shouldThrow` anyIOException
        merge db "records" "c" `shouldThrow` anyIOException
        -- it can still be written, flushed and compacted
        put db "more" "y"
        flushAll db
        compactAll db
      openMergeDB path $ \db _ _ _ ->
        withIter db forwards `shouldReturn` [("more", "y"), ("plain", "x"), ("records", "a,b")]
  -- Records that are still in the write-ahead log fare worse. RocksDB 11
  -- drops them when it opens the database without the operator, and says
  -- nothing: they are lost for the program that has the operator too. It
  -- refuses to open a database without all its column families, and does
  -- so before it reads the log: a column family that the other program
  -- does not know of keeps the records safe.
  it "loses the merge records of the log to an open without their operator, unless the open is refused" $ do
    let without = [(name, cfg {mergeOperator = Nothing}) | (name, cfg) <- mergeFamilies]
        -- a value in a table file, and merge records that are in the log
        -- and in no table file when the database is closed
        records path = openMergeDB path $ \db _ _ _ -> do
          put db "value" "x"
          flush db Nothing
          merge db "value" "a" >> merge db "new" "b"
    withTempPath $ \path -> do
      records path
      withDBCF path (merging Nothing) without $ \_ -> return ()
      openMergeDB path $ \db _ _ _ ->
        withIter db forwards `shouldReturn` [("value", "x")]
    withTempPath $ \path -> do
      records path
      withDBCF path (merging Nothing) (take 2 without) (\_ -> return ()) `shouldThrow` anyIOException
      openMergeDB path $ \db _ _ _ ->
        withIter db forwards `shouldReturn` [("new", "b"), ("value", "x,a")]

-------------------------------------------------------------------------------
-- Opening and closing
-------------------------------------------------------------------------------

openingSpec :: Spec
openingSpec = describe "Opening" $ do
  it "keeps the data when the database is closed and opened again" $
    withTempPath $ \path -> do
      withDB path plain $ \db -> put db "key" "value" >> delete db "gone"
      withDB path plain $ \db -> do
        get db "key" `shouldReturn` Just "value"
        withIter db forwards `shouldReturn` [("key", "value")]
  it "throws if the database is missing and may not be created" $
    withTempPath $ \path ->
      withDB path def (\_ -> return ()) `shouldThrow` anyIOException
  it "throws if the database exists and must not" $
    withTempPath $ \path -> do
      withDB path plain $ \_ -> return ()
      withDB path plain {errorIfExists = True} (\_ -> return ())
        `shouldThrow` anyIOException
  it "throws if the database is already open" $
    withTempPath $ \path ->
      withDB path plain $ \_ ->
        withDB path plain (\_ -> return ()) `shouldThrow` anyIOException
  it "closes the database when the function throws" $
    withTempPath $ \path -> do
      withDB path plain (\db -> put db "k" "v" >> ioError (userError "stop"))
        `shouldThrow` anyIOException
      -- the lock is released, and what was written is there
      withDB path plain $ \db -> get db "k" `shouldReturn` Just "v"
  it "throws if a column family of the database is left out" $
    withTempPath $ \path -> do
      let create = plain {createMissingColumnFamilies = True}
      withDBCF path create [("one", plain)] $ \_ -> return ()
      withDB path plain (\_ -> return ()) `shouldThrow` anyIOException
  it "throws if a column family is missing and may not be created" $
    withTempPath $ \path -> do
      withDB path plain $ \_ -> return ()
      withDBCF path plain [("one", plain)] (\_ -> return ())
        `shouldThrow` anyIOException
  it "adds a column family to an existing database" $
    withTempPath $ \path -> do
      let create = plain {createMissingColumnFamilies = True}
      withDBCF path create [("one", plain)] $ \db -> do
        one <- firstFamily db
        put db "key" "value"
        putCF db one "key" "one"
      withDBCF path create [("one", plain), ("two", plain)] $ \db -> do
        (one, two) <- twoFamilies db
        get db "key" `shouldReturn` Just "value"
        getCF db one "key" `shouldReturn` Just "one"
        getCF db two "key" `shouldReturn` Nothing
        putCF db two "new" "cf"
        getCF db two "new" `shouldReturn` Just "cf"
  it "gives the column families in the order they were asked for" $
    withTempPath $ \path -> do
      let create = plain {createMissingColumnFamilies = True}
      withDBCF path create [("one", plain), ("two", plain)] $ \db -> do
        (one, two) <- twoFamilies db
        putCF db one "name" "one"
        putCF db two "name" "two"
      withDBCF path plain [("two", plain), ("one", plain)] $ \db -> do
        (two, one) <- twoFamilies db
        getCF db one "name" `shouldReturn` Just "one"
        getCF db two "name" `shouldReturn` Just "two"

-------------------------------------------------------------------------------
-- Settings, checked by their effect
-------------------------------------------------------------------------------

tuningSpec :: Spec
tuningSpec = describe "Tuning" $ do
  it "flushes small memtables and keeps the data" $ do
    let small =
          tuned
            { writeBufferSize = Just (64 * 1024),
              dbWriteBufferSize = Just (256 * 1024)
            }
        cfConf = small {dbWriteBufferSize = Nothing}
        value = C.replicate 100 'v'
    withTempPath $ \path ->
      withDBCF path small [("one", cfConf), ("two", cfConf)] $ \db -> do
        (one, two) <- twoFamilies db
        forM_ [1 .. 20000] $ \i -> do
          put db (key i) value
          putCF db one (key i) value
          putCF db two (key i) value
        get db (key 1) `shouldReturn` Just value
        getCF db one (key 10000) `shouldReturn` Just value
        getCF db two (key 20000) `shouldReturn` Just value
        -- the memtables are far smaller than the data, so it is in files
        files <- getProperty db SSTables
        files `shouldSatisfy` maybe False (not . C.null)
  it "builds Bloom filters for a family that asks for one, and only for it" $
    withTempPath $ \path -> do
      let open = plain {createMissingColumnFamilies = True}
          families = [("with", def {bloomFilter = True}), ("without", def)]
          tableProps = PropertyName "rocksdb.aggregated-table-properties"
          -- bytes of filter blocks in the table files of a family
          filters d cf =
            getPropertyCF d cf tableProps
              >>= maybe (fail "no table properties") (return . tableProperty "filter block size")
      withDBCF path open families $ \db -> do
        (with, without) <- twoFamilies db
        forM_ [1 .. 5000] $ \i -> do
          putCF db with (key i) "value"
          putCF db without (key i) "value"
      -- opening the database again moves what was written from the
      -- write-ahead log to table files, which is where filters are
      withDBCF path open families $ \db -> do
        (with, without) <- twoFamilies db
        -- ten bits for each of the 5000 keys is 6250 bytes
        filters db with >>= (`shouldSatisfy` maybe False (> 5000))
        filters db without `shouldReturn` Just 0
        getCF db with (key 2500) `shouldReturn` Just "value"
        getCF db with "absent" `shouldReturn` Nothing
  it "estimates the space used by a range of keys" $
    withTempPath $ \path -> do
      withDB path plain $ \db ->
        forM_ [1 .. 5000] $ \i -> put db (key i) (C.pack (printf "%0100d" i))
      -- sizes are those of table files; see the test of Bloom filters
      withDB path plain $ \db -> do
        approximateSize db (key 1, key 5000) >>= (`shouldSatisfy` (> 0))
        approximateSize db ("x", "y") `shouldReturn` 0
  it "shares one block cache, holding index and filter blocks" $ do
    let size = 8 * 1024 * 1024 :: Int
        cached =
          tuned
            { errorIfExists = False,
              blockCacheSize = Just size,
              cacheIndexAndFilterBlocks = True,
              writeBufferSize = Just (64 * 1024)
            }
        value = C.replicate 100 'v'
        capacity = PropertyName "rocksdb.block-cache-capacity"
    withTempPath $ \path -> do
      withDBCF path cached [("one", cached)] $ \db -> do
        one <- firstFamily db
        forM_ [1 .. 20000] $ \i -> putCF db one (key i) value
      withDBCF path cached [("one", cached)] $ \db -> do
        one <- firstFamily db
        getProperty db capacity `shouldReturn` Just (C.pack (show size))
        getPropertyCF db one capacity `shouldReturn` Just (C.pack (show size))
        multiGetCF db one (map key [1, 10000, 20000])
          `shouldReturn` replicate 3 (Just value)
        getProperty db BlockCacheUsage >>= (`shouldSatisfy` positive)
  it "loads a piece of the index and of the filter for a lookup, not all of them" $ do
    -- One table file of 200,000 keys has a filter of some 250 kB and an
    -- index of about as much. A lookup in a file that the cache does not
    -- know loads both whole, or two pieces of 4 KiB.
    let size = 64 * 1024 * 1024 :: Int
        whole =
          tuned
            { errorIfExists = False,
              bloomFilter = True,
              blockCacheSize = Just size,
              cacheIndexAndFilterBlocks = True
            }
        pieces = whole {partitionIndexAndFilters = True}
        value = C.replicate 20 'v'
        afterOneLookup cfg =
          withTempPath $ \path -> do
            withDBCF path cfg [("one", cfg)] $ \db -> do
              one <- firstFamily db
              forM_ [1 .. 200000] $ \i -> putCF db one (key i) value
            -- opening it writes what was in memory to a file of the first
            -- level, all of whose index and filter the cache keeps: the
            -- compaction moves it down, where they are loaded as needed
            withDBCF path cfg [("one", cfg)] $ \db -> do
              one <- firstFamily db
              compactRange db (Just one) Nothing Nothing
            withDBCF path cfg [("one", cfg)] $ \db -> do
              one <- firstFamily db
              getCF db one (key 100000) `shouldReturn` Just value
              usage <- getProperty db BlockCacheUsage
              return (maybe 0 (read . C.unpack) usage :: Int)
    held <- afterOneLookup whole
    heldInPieces <- afterOneLookup pieces
    putStrLn $ "block cache after one lookup: " <> show held <> " bytes whole, " <> show heldInPieces <> " in pieces"
    held `shouldSatisfy` (> 200 * 1024)
    heldInPieces `shouldSatisfy` (< held `div` 4)
  it "opens with a bound on the write-ahead log" $
    withTempPath $ \path ->
      withDBCF path tuned {maxTotalWalSize = Just (1024 * 1024)} [("one", tuned)] $ \db -> do
        put db "key" "value"
        get db "key" `shouldReturn` Just "value"
  it "opens with the number of background jobs that it is given" $
    withTempPath $ \path -> do
      let setting = "max_background_jobs="
          -- RocksDB writes the options that it runs with to a file
          jobs = do
            files <- filter ("OPTIONS-" `isPrefixOf`) <$> listDirectory path
            concat <$> forM files (fmap (settings . lines) . readFile . (path </>))
          settings = filter (setting `isPrefixOf`) . map (dropWhile (== ' '))
      withDB path plain {maxBackgroundJobs = Just 5} $ \db -> put db "key" "value"
      jobs >>= (`shouldSatisfy` elem (setting <> "5"))
  it "works with few open files and paranoid checks" $
    withTempPath $ \path -> do
      let strict =
            plain
              { maxFiles = Just 20,
                paranoidChecks = True,
                writeBufferSize = Just (64 * 1024)
              }
          kvs = [(key i, C.replicate 100 'v') | i <- [1 .. 20000]]
      withDB path strict $ \db -> forM_ kvs $ uncurry (put db)
      withDB path strict $ \db -> withIter db forwards `shouldReturn` kvs

-------------------------------------------------------------------------------
-- Properties: the database against a Map
-------------------------------------------------------------------------------

-- | A write to the default column family.
data Op
  = Set ByteString ByteString
  | Unset ByteString
  deriving (Show)

-- | Short keys over four bytes, so that random operations often meet on the
-- same key. The bytes are the ones a binding is most likely to mishandle: zero,
-- which ends a C string, and 255, which is negative as a signed @char@ and
-- must still sort last.
genKey :: Gen ByteString
genKey = do
  n <- choose (0, 3)
  BS.pack <$> vectorOf n (elements [0, 1, 97, 255])

-- | Values of any bytes, often empty.
genValue :: Gen ByteString
genValue = do
  n <- frequency [(1, return 0), (4, choose (1, 24))]
  BS.pack <$> vectorOf n arbitrary

-- | A prefix that keys of 'genKey' often start with, and often the empty
-- one, which every key starts with.
genPrefix :: Gen ByteString
genPrefix = do
  n <- frequency [(2, return 0), (2, return 1), (1, return 2)]
  BS.pack <$> vectorOf n (elements [0, 1, 97, 255])

-- | Chunks small enough that a scan of a few entries takes several, with a
-- limit of bytes that is often below the size of one entry: 'genKey' and
-- 'genValue' give entries of up to 27 bytes.
genChunk :: Gen ChunkConfig
genChunk = do
  entries <- choose (1, 5)
  bytes <- frequency [(1, return 0), (3, choose (1, 60)), (1, return maxBound)]
  prefix <- genPrefix
  back <- arbitrary
  return
    ChunkConfig
      { chunkEntries = entries,
        chunkBytes = bytes,
        chunkPrefix = prefix,
        chunkBackwards = back
      }

-- | An iterator with no bound, one, or two that leave a range between them.
genBounds :: Gen IterConfig
genBounds = do
  a <- genKey
  b <- genKey
  lower <- elements [Nothing, Just (min a b)]
  upper <- elements [Nothing, Just (max a b)]
  return def {lowerBound = lower, upperBound = upper}

genOps :: Gen [Op]
genOps = listOf $ frequency [(3, Set <$> genKey <*> genValue), (1, Unset <$> genKey)]

-- | Random operations, shrinking a failure to the fewest that still fail.
forAllOps :: (Testable p) => ([Op] -> p) -> QC.Property
forAllOps = forAllShrink genOps (shrinkList (const []))

opKey :: Op -> ByteString
opKey (Set k _) = k
opKey (Unset k) = k

-- | A step of a history with merge records: a write, a merge record for the
-- operator that joins with commas, or a flush of the memtable to a table
-- file of its own.
data Step
  = Write Op
  | Join ByteString ByteString
  | Flush
  deriving (Show)

stepKey :: Step -> Maybe ByteString
stepKey (Write op) = Just (opKey op)
stepKey (Join k _) = Just k
stepKey Flush = Nothing

-- | Histories in which keys often have several merge records, with puts,
-- deletes and flushes among them. The records are letters: the one byte
-- that makes the operator of the tests fail is not among them.
genMergeOps :: Gen [Step]
genMergeOps =
  listOf . frequency $
    [ (2, Write <$> (Set <$> genKey <*> genValue)),
      (1, Write . Unset <$> genKey),
      (5, Join <$> genKey <*> (BS.pack <$> listOf (elements [97 .. 122]))),
      (2, return Flush)
    ]

-- | What the database should hold after a history, with the operator that
-- joins with commas: a record on a key without a value is the value, and
-- on a key with one it follows a comma.
joinModel :: [Step] -> Map ByteString ByteString
joinModel = foldl apply Map.empty
  where
    apply m (Write (Set k v)) = Map.insert k v m
    apply m (Write (Unset k)) = Map.delete k m
    apply m (Join k v) = Map.insertWith (\new old -> old <> "," <> new) k v m
    apply m Flush = m

-- | What the database should hold after the operations, in order.
model :: [Op] -> Map ByteString ByteString
model = foldl apply Map.empty
  where
    apply m (Set k v) = Map.insert k v m
    apply m (Unset k) = Map.delete k m

-- | Apply the operations one write at a time.
runOps :: DB -> [Op] -> IO ()
runOps db = mapM_ run
  where
    run (Set k v) = put db k v
    run (Unset k) = delete db k

-- | The operations as one atomic batch.
batchOf :: [Op] -> [BatchOp]
batchOf = map op
  where
    op (Set k v) = Put k v
    op (Unset k) = Del k

-- | Require that every way of reading the default column family agrees with
-- the map: iteration in both directions, in the order of the map's keys, and
-- point reads of the given keys.
shouldHold :: DB -> [ByteString] -> Map ByteString ByteString -> IO ()
shouldHold db keys m = do
  withIter db forwards `shouldReturn` Map.toAscList m
  withIter db backwards `shouldReturn` Map.toDescList m
  forM_ keys $ \k -> get db k `shouldReturn` Map.lookup k m
  multiGet db keys `shouldReturn` map (`Map.lookup` m) keys

-- | A new database with only the default column family, for one test case.
inNewDB :: (DB -> IO ()) -> QC.Property
inNewDB go = ioProperty $ withTempPath $ \path -> withDB path plain go

modelSpec :: Spec
modelSpec = describe "Agreement with a Map" $ do
  prop "after single writes" $
    forAllOps $ \ops -> inNewDB $ \db -> do
      runOps db ops
      shouldHold db (map opKey ops) (model ops)
  prop "after one batch" $
    forAllOps $ \ops -> inNewDB $ \db -> do
      write db (batchOf ops)
      shouldHold db (map opKey ops) (model ops)
  prop "after one packed batch, however it is cut into chunks" $
    forAllOps $ \ops -> forAll (choose (1, 5)) $ \size -> inNewDB $ \db -> do
      writePacked db (map packOps (groupsOf size (batchOf ops)))
      shouldHold db (map opKey ops) (model ops)
  prop "with merge records among the writes, in memtables, in table files and compacted" $
    forAll genMergeOps $ \steps -> ioProperty $ withTempPath $ \path ->
      withDB path (merging (Just joining)) $ \db -> do
        let keys = [k | Just k <- map stepKey steps]
            wanted = joinModel steps
        forM_ steps $ \case
          Write (Set k v) -> put db k v
          Write (Unset k) -> delete db k
          Join k v -> merge db k v
          Flush -> flush db Nothing
        shouldHold db keys wanted
        flush db Nothing
        shouldHold db keys wanted
        compactRange db Nothing Nothing Nothing
        shouldHold db keys wanted
  prop "with merge records in one batch, plain or packed" $
    forAll genMergeOps $ \steps -> forAll arbitrary $ \packed -> ioProperty $ withTempPath $ \path ->
      withDB path (merging (Just joining)) $ \db -> do
        let batch =
              [ op
              | step <- steps,
                op <- case step of
                  Write (Set k v) -> [Put k v]
                  Write (Unset k) -> [Del k]
                  Join k v -> [Merge k v]
                  Flush -> []
              ]
        if packed then writePacked db (map packOps (groupsOf 3 batch)) else write db batch
        shouldHold db [k | Just k <- map stepKey steps] (joinModel steps)
  prop "after the database is closed and opened again" $
    forAllOps $ \ops -> ioProperty $ withTempPath $ \path -> do
      withDB path plain $ \db -> runOps db ops
      withDB path plain $ \db -> shouldHold db (map opKey ops) (model ops)
  prop "in a column family, leaving the default one alone" $
    forAllOps $ \ops -> forAllOps $ \others -> ioProperty $ withPlainDB $ \db -> do
      other <- firstFamily db
      runOps db ops
      forM_ others $ \o -> case o of
        Set k v -> putCF db other k v
        Unset k -> deleteCF db other k
      shouldHold db (map opKey (ops <> others)) (model ops)
      withIterCF db other forwards `shouldReturn` Map.toAscList (model others)
      let keys = map opKey (ops <> others)
      multiGetCF db other keys `shouldReturn` map (`Map.lookup` model others) keys
  prop "when seeking: the first key not below the one sought" $
    forAllOps $ \ops -> forAll (listOf genKey) $ \targets -> inNewDB $ \db -> do
      runOps db ops
      withIter db $ \itr -> forM_ targets $ \target -> do
        iterSeek itr target
        iterEntry itr `shouldReturn` Map.lookupGE target (model ops)
  prop "in chunks, as one step at a time" $
    forAllOps $ \ops -> forAll genChunk $ \cfg -> forAll genBounds $ \bounds ->
      forAll genKey $ \start -> inNewDB $ \db -> do
        runOps db ops
        withIterConfig db Nothing bounds $ \itr -> do
          let step = if chunkBackwards cfg then iterPrev else iterNext
              place = do
                iterSeek itr start
                valid <- iterValid itr
                when (chunkBackwards cfg && not valid) (iterLast itr)
          -- what single steps read from there to the end, and the part of
          -- it that the chunks are to return
          place
          rest <- scan step itr
          let wanted = takeWhile ((chunkPrefix cfg `BS.isPrefixOf`) . fst) rest
          place
          let go done = do
                (entries, more) <- iterChunk itr cfg
                let done' = done + length entries
                    left = drop done' wanted
                -- the entries that come next, within both limits
                entries `shouldBe` take (length entries) (drop done wanted)
                length entries `shouldSatisfy` (<= chunkEntries cfg)
                when (length entries > 1) $
                  sizeOf entries `shouldSatisfy` (<= chunkBytes cfg)
                -- and not fewer than the limits allow
                when (length entries < chunkEntries cfg) $
                  sizeOf (entries <> take 1 left) `shouldSatisfy` (\n -> null left || n > chunkBytes cfg)
                -- the flag says whether anything is left
                more `shouldBe` not (null left)
                -- the iterator is on the first entry that was not returned
                iterEntry itr `shouldReturn` listToMaybe (drop done' rest)
                when more $ do
                  entries `shouldNotBe` []
                  go done'
          go 0
          iterGetError itr `shouldReturn` Nothing
  prop "a number of entries at once, as one step at a time" $
    forAllOps $ \ops -> forAll (choose (0, 8)) $ \n -> forAll arbitrary $ \back ->
      forAll genPrefix $ \prefix -> forAll genKey $ \start -> inNewDB $ \db -> do
        runOps db ops
        withIter db $ \itr -> do
          let step = if back then iterPrev else iterNext
          iterSeek itr start
          rest <- scan step itr
          iterSeek itr start
          (if back then iterEntriesBack else iterEntries) itr n `shouldReturn` take n rest
          iterEntry itr `shouldReturn` listToMaybe (drop n rest)
          let wanted = take n (takeWhile ((prefix `BS.isPrefixOf`) . fst) rest)
          iterSeek itr start
          (if back then iterEntriesPrefixBack else iterEntriesPrefix) itr prefix n `shouldReturn` wanted
          iterEntry itr `shouldReturn` listToMaybe (drop (length wanted) rest)
  prop "through a snapshot, whatever is written afterwards" $
    forAllOps $ \earlier -> forAllOps $ \later -> inNewDB $ \db -> do
      let keys = map opKey (earlier <> later)
      runOps db earlier
      withSnapshot db $ \snap -> do
        runOps db later
        shouldHold snap keys (model earlier)
      shouldHold db keys (model (earlier <> later))