packages feed

kenshou-check-0.1.0.0: src/Kenshou/Check/Model/Linearizability.hs

module Kenshou.Check.Model.Linearizability
  ( Completion (..),
    Operation (..),
    SeqModel (..),
    LinConfig (..),
    LinResult (..),
    RegisterOp (..),
    RegisterResult (..),
    LogOp (..),
    LogResult (..),
    defaultLinConfig,
    checkLinearizable,
    registerModel,
    appendLogModel,
    linearizability,
  )
where

import Data.Aeson (object, (.=))
import Data.Int (Int64)
import Data.Map.Strict qualified as Map
import Data.Set (Set)
import Data.Set qualified as Set
import Data.Text (Text)
import Kenshou.Check.Fact (Fact)
import Kenshou.Check.Invariant
import Kenshou.Check.Ledger.Sort (SortOrder (ByKeyWall))
import Kenshou.Check.Verdict

data Completion output = Returned output | Failed | Indeterminate
  deriving stock (Eq, Ord, Show)

data Operation input output = Operation
  { process :: !Text,
    key :: !Text,
    input :: !input,
    invoked :: !Int64,
    completed :: !(Maybe Int64),
    completion :: !(Completion output)
  }
  deriving stock (Eq, Ord, Show)

data SeqModel state input output = SeqModel
  { initial :: !state,
    apply :: state -> input -> (output, state),
    agrees :: output -> output -> Bool
  }

newtype LinConfig = LinConfig {maxSteps :: Int}
  deriving stock (Eq, Ord, Show)

data LinResult = Linearizable | NotLinearizable [Text] | Undecided
  deriving stock (Eq, Show)

data RegisterOp = ReadRegister | WriteRegister Int64 | CompareAndSet (Maybe Int64) Int64
  deriving stock (Eq, Ord, Show)

data RegisterResult = ReadValue (Maybe Int64) | Written | Compared Bool
  deriving stock (Eq, Ord, Show)

data LogOp = Append Text | ReadLog
  deriving stock (Eq, Ord, Show)

data LogResult = Appended Int | LogContents [Text]
  deriving stock (Eq, Ord, Show)

defaultLinConfig :: LinConfig
defaultLinConfig = LinConfig 5000000

checkLinearizable :: (Ord state) => LinConfig -> SeqModel state input output -> [Operation input output] -> LinResult
checkLinearizable config model operations =
  case search 0 Set.empty model.initial indexed of
    SearchYes -> Linearizable
    SearchBudget -> Undecided
    SearchNo -> NotLinearizable ["No legal sequential history agrees with the completed operations."]
  where
    indexed = [(index, operation) | (index, operation) <- zip [0 :: Int ..] operations, isPending operation]
    isPending operation = case operation.completion of Failed -> False; _ -> True

    search steps visited state pending
      | steps >= config.maxSteps = SearchBudget
      | null pending = SearchYes
      | Set.member (Set.fromList (fmap fst pending), state) visited = SearchNo
      | otherwise =
          let visited' = Set.insert (Set.fromList (fmap fst pending), state) visited
              choices = filter (eligible . snd) pending
              outcomes = concatMap (advance (steps + 1) visited' state pending) choices
           in combine outcomes
      where
        eligible candidate = all (not . happensBefore candidate . snd) pending

    happensBefore candidate other = case other.completed of
      Just ended -> ended < candidate.invoked
      Nothing -> False

    advance steps visited state pending selected@(index, operation) =
      let remaining = filter ((/= index) . fst) pending
          (expected, nextState) = model.apply state operation.input
          applied = search steps visited nextState remaining
       in case operation.completion of
            Returned actual | model.agrees expected actual -> [applied]
            Returned _ -> []
            Failed -> [search steps visited state remaining]
            Indeterminate -> [search steps visited state remaining, applied]

    combine outcomes
      | SearchYes `elem` outcomes = SearchYes
      | SearchBudget `elem` outcomes = SearchBudget
      | otherwise = SearchNo

registerModel :: SeqModel (Maybe Int64) RegisterOp RegisterResult
registerModel = SeqModel Nothing applyRegister (==)
  where
    applyRegister state ReadRegister = (ReadValue state, state)
    applyRegister _ (WriteRegister value) = (Written, Just value)
    applyRegister state (CompareAndSet expected replacement)
      | state == expected = (Compared True, Just replacement)
      | otherwise = (Compared False, state)

appendLogModel :: SeqModel [Text] LogOp LogResult
appendLogModel = SeqModel [] applyLog (==)
  where
    applyLog state (Append value) = (Appended (length state), state <> [value])
    applyLog state ReadLog = (LogContents state, state)

linearizability :: (Ord state) => Text -> InvariantClass -> SeqModel state input output -> (Fact -> Maybe (Operation input output)) -> Checker
linearizability checkerName cls model decode =
  Checker checkerName "linearizability" cls ByKeyWall (maybe False (const True) . decode) False (CheckFold [] step finish)
  where
    step operations fact = maybe operations (: operations) (decode fact)
    finish reversed =
      let operations = reverse reversed
          byKey = Map.elems (Map.fromListWith (<>) [(operation.key, [operation]) | operation <- operations])
          results = fmap (checkLinearizable defaultLinConfig model) byKey
          violations = length [() | NotLinearizable _ <- results]
          undecided = any (== Undecided) results
          status | undecided = NotEvaluated | violations > 0 = Violated | otherwise = Held
          reason = if undecided then Just "search-budget-exhausted" else Nothing
       in CheckResult
            status
            reason
            "Completed operations admit a legal sequential history per key."
            (Map.fromList [("examined", fromIntegral (length operations)), ("violations", fromIntegral violations)])
            (object ["maxSteps" .= defaultLinConfig.maxSteps])
            [object ["reason" .= reasons] | NotLinearizable reasons <- results]

data SearchResult = SearchYes | SearchNo | SearchBudget
  deriving stock (Eq, Show)