packages feed

kenshou-check-0.1.0.0: src/Kenshou/Check/Ledger/Sort.hs

module Kenshou.Check.Ledger.Sort
  ( SortOrder (..),
    SortConfig (..),
    defaultSortConfig,
    sortedFacts,
  )
where

import Control.Exception (bracket)
import Control.Monad (foldM, unless)
import Data.Aeson (eitherDecodeStrict', encode)
import Data.ByteString.Char8 qualified as ByteString
import Data.ByteString.Lazy.Char8 qualified as LazyByteString
import Data.IORef
import Data.List (minimumBy, sortBy)
import Data.Ord (comparing)
import Kenshou.Check.Fact
import Kenshou.Check.Ledger.Read
import System.Directory (createDirectoryIfMissing, listDirectory, removeFile)
import System.FilePath ((</>))
import System.IO

data SortOrder = ByKeySeq | ByScopeKeyArrival | ByScopeArrival | ByKeyWall
  deriving stock (Eq, Ord, Show)

data SortConfig = SortConfig
  { directory :: !FilePath,
    runRecords :: !Int,
    mergeFanIn :: !Int
  }
  deriving stock (Eq, Show)

defaultSortConfig :: FilePath -> SortConfig
defaultSortConfig directory = SortConfig directory 200000 64

sortedFacts :: SortConfig -> SortOrder -> (Fact -> Bool) -> LedgerSet -> (FactSource -> IO value) -> IO value
sortedFacts config order select ledger action = bracket prepare cleanup (action <=< sourceFor)
  where
    prepare = do
      createDirectoryIfMissing True config.directory
      counter <- newIORef (0 :: Int)
      chunks <- buildRuns counter [] [] 0 ledger.segments
      collapse counter chunks
    cleanup finalPath = do
      names <- listDirectory config.directory
      mapM_ (removeFile . (config.directory </>)) names
      unless (null finalPath) (pure ())
    sourceFor "" = pure (FactSource (pure Nothing))
    sourceFor path = openRun path

    buildRuns counter paths chunk size [] = flushChunk counter paths chunk size
    buildRuns counter paths chunk size (segment : rest) = do
      (_, source) <- openSegment segment.path
      (paths', chunk', size') <- consume counter paths chunk size source
      buildRuns counter paths' chunk' size' rest

    consume counter paths chunk size source =
      source.next >>= \case
        Nothing -> pure (paths, chunk, size)
        Just fact
          | not (select fact) -> consume counter paths chunk size source
          | size + 1 >= max 1 config.runRecords -> do
              paths' <- flushChunk counter paths (fact : chunk) (size + 1)
              consume counter paths' [] 0 source
          | otherwise -> consume counter paths (fact : chunk) (size + 1) source

    flushChunk _ paths [] _ = pure paths
    flushChunk counter paths chunk _ = do
      path <- freshPath counter
      writeFacts path (sortBy (compareFact order) chunk)
      pure (paths <> [path])

    collapse _ [] = pure ""
    collapse _ [path] = pure path
    collapse counter paths = do
      merged <- traverse (mergeGroup counter) (chunksOf (max 2 config.mergeFanIn) paths)
      mapM_ removeFile paths
      collapse counter merged

    mergeGroup counter paths = do
      target <- freshPath counter
      sources <- traverse openRun paths
      mergeSources order target sources
      pure target

    freshPath counter = do
      number <- atomicModifyIORef' counter (\value -> (value + 1, value + 1))
      pure (config.directory </> ("run-" <> pad6 number <> ".jsonl"))

    pad6 number = replicate (max 0 (6 - length rendered)) '0' <> rendered where rendered = show number

compareFact :: SortOrder -> Fact -> Fact -> Ordering
compareFact ByKeySeq = comparing (\fact -> (fact.key, fact.seq, fact.kind, fact.wall, fact.n))
compareFact ByScopeKeyArrival = comparing (\fact -> (fact.scope, fact.key, fact.proc.incarnation, fact.n))
compareFact ByScopeArrival = comparing (\fact -> (fact.scope, fact.proc.incarnation, fact.n))
compareFact ByKeyWall = comparing (\fact -> (fact.key, fact.wall, fact.scope, fact.n))

writeFacts :: FilePath -> [Fact] -> IO ()
writeFacts path facts = withBinaryFile path WriteMode \handle -> mapM_ (LazyByteString.hPutStrLn handle . encode) facts

openRun :: FilePath -> IO FactSource
openRun path = do
  handle <- openBinaryFile path ReadMode
  pure (FactSource (nextFact handle))
  where
    nextFact handle = do
      done <- hIsEOF handle
      if done
        then hClose handle >> pure Nothing
        else do
          line <- ByteString.hGetLine handle
          either (ioError . userError) (pure . Just) (eitherDecodeStrict' line)

mergeSources :: SortOrder -> FilePath -> [FactSource] -> IO ()
mergeSources order path sources = withBinaryFile path WriteMode \handle -> do
  heads <- traverse (\source -> (source,) <$> source.next) sources
  go handle heads
  where
    go _ heads | all (maybe True (const False) . snd) heads = pure ()
    go handle heads = do
      let candidates = [(index, source, fact) | (index, (source, Just fact)) <- zip [0 :: Int ..] heads]
          (chosenIndex, chosenSource, chosenFact) = minimumBy (\(_, _, left) (_, _, right) -> compareFact order left right) candidates
      LazyByteString.hPutStrLn handle (encode chosenFact)
      replacement <- chosenSource.next
      go handle [if index == chosenIndex then (source, replacement) else pair | (index, pair@(source, _)) <- zip [0 :: Int ..] heads]

chunksOf :: Int -> [value] -> [[value]]
chunksOf _ [] = []
chunksOf size values = first : chunksOf size rest where (first, rest) = splitAt size values

(<=<) :: (b -> IO c) -> (a -> IO b) -> a -> IO c
(<=<) left right value = right value >>= left