packages feed

kenshou-check-0.1.0.0: src/Kenshou/Check/Invariant.hs

{-# LANGUAGE ExistentialQuantification #-}

module Kenshou.Check.Invariant
  ( CheckResult (..),
    CheckFold (..),
    Checker (..),
    DuplicateBudget (..),
    Deadline (..),
    runCheckers,
    evaluateChecker,
    noLoss,
    duplicatesWithin,
    perKeyOrder,
    globalOrder,
    gaplessPositions,
    exactlyNEffects,
    eventualQuiescence,
    monotonicCheckpoints,
    disjointOwnership,
  )
where

import Data.Aeson
import Data.Aeson.Key qualified as Key
import Data.Aeson.KeyMap qualified as KeyMap
import Data.Foldable (foldl')
import Data.Int (Int64)
import Data.List (groupBy, sort, sortOn)
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Maybe (mapMaybe)
import Data.Scientific (toBoundedInteger)
import Data.Set (Set)
import Data.Set qualified as Set
import Data.Text (Text)
import Data.Time (getCurrentTime)
import Kenshou.Check.Fact
import Kenshou.Check.Ledger.Read
import Kenshou.Check.Ledger.Sort
import Kenshou.Check.Scenario
import Kenshou.Check.Verdict
import Kenshou.Check.Window
import System.FilePath ((</>))

data CheckResult = CheckResult
  { status :: !VerdictStatus,
    reason :: !(Maybe Text),
    summary :: !Text,
    counts :: !(Map Text Int64),
    parameters :: !Value,
    counterExamples :: ![Value]
  }
  deriving stock (Eq, Show)

data CheckFold = forall state. CheckFold
  { initial :: state,
    step :: state -> Fact -> state,
    finish :: state -> CheckResult
  }

data Checker = Checker
  { name :: !Text,
    invariant :: !Text,
    cls :: !InvariantClass,
    order :: !SortOrder,
    select :: Fact -> Bool,
    allowEmpty :: !Bool,
    fold :: !CheckFold
  }

data DuplicateBudget = DuplicateBudget
  { maxPerWindow :: !(Maybe Int),
    maxRedeliveryDelayMicros :: !(Maybe Int64)
  }
  deriving stock (Eq, Show)

newtype Deadline = Deadline {micros :: Int64}
  deriving stock (Eq, Ord, Show)

data Running = forall state. Running Checker state Int (state -> Fact -> state) (state -> CheckResult)

runCheckers :: CheckEnv -> LedgerSet -> [Checker] -> IO [Verdict]
runCheckers environment ledger checkers = concat <$> traverse runGroup grouped
  where
    grouped = groupBy (\left right -> left.order == right.order) (sortOn (.order) checkers)
    inputs = [InputRef segment.relativePath segment.sha256 | segment <- ledger.segments]
    runGroup [] = pure []
    runGroup group@(first : _) = do
      let running = fmap startChecker group
          config = defaultSortConfig (environment.ledgerDirectory </> ".sort")
      completed <- sortedFacts config first.order (const True) ledger (drain running)
      now <- getCurrentTime
      pure [toVerdict now inputs checker selected result | (checker, selected, result) <- fmap finishRunning completed]

evaluateChecker :: Checker -> [Fact] -> CheckResult
evaluateChecker checker facts =
  let (_, selected, result) = finishRunning (foldl' feed (startChecker checker) facts)
   in if selected == 0 && not checker.allowEmpty then vacuous else result

startChecker :: Checker -> Running
startChecker checker = case checker.fold of CheckFold initial step finish -> Running checker initial 0 step finish

feed :: Running -> Fact -> Running
feed (Running checker state selected step finish) fact
  | checker.select fact = Running checker (step state fact) (selected + 1) step finish
  | otherwise = Running checker state selected step finish

finishRunning :: Running -> (Checker, Int, CheckResult)
finishRunning (Running checker state selected _ finish) = (checker, selected, if selected == 0 && not checker.allowEmpty then vacuous else finish state)

drain :: [Running] -> FactSource -> IO [Running]
drain running source = source.next >>= \case Nothing -> pure running; Just fact -> drain (fmap (`feed` fact) running) source

toVerdict now inputs checker _selected result =
  Verdict checker.name checker.invariant checker.cls result.status result.reason result.summary result.counts result.parameters (take 20 result.counterExamples) (length result.counterExamples > 20) inputs Nothing now 0

vacuous :: CheckResult
vacuous = CheckResult NotEvaluated (Just "vacuous") "No relevant facts were observed." (Map.fromList [("examined", 0), ("violations", 0)]) Null []

result :: Text -> Int -> Int -> [Value] -> CheckResult
result summary examined violations examples =
  CheckResult
    (if violations == 0 then Held else Violated)
    Nothing
    summary
    (Map.fromList [("examined", fromIntegral examined), ("violations", fromIntegral violations)])
    (object [])
    examples

noLoss :: Text -> InvariantClass -> Text -> Checker
noLoss checkerName cls consumerScope =
  Checker checkerName "no-loss" cls ByKeySeq relevant False (CheckFold (Set.empty, Set.empty, Set.empty) step finish)
  where
    relevant fact = fact.kind `elem` [Intent, Produced, Observed]
    identity :: Fact -> (Text, Int64, Text)
    identity fact = (fact.key, fact.seq, fact.id)
    step (intents, produced, observed) fact = case fact.kind of
      Intent -> (Set.insert (identity fact) intents, produced, observed)
      Produced -> (intents, Set.insert (identity fact) produced, observed)
      Observed | fact.scope == consumerScope -> (intents, produced, Set.insert (identity fact) observed)
      _ -> (intents, produced, observed)
    finish :: (Set (Text, Int64, Text), Set (Text, Int64, Text), Set (Text, Int64, Text)) -> CheckResult
    finish (intents, produced, observed) =
      let missing = Set.toList (produced `Set.difference` observed)
          phantom = Set.toList (observed `Set.difference` intents)
          violations = length missing + length phantom
          examples = fmap (example "missing") missing <> fmap (example "phantom") phantom
       in result "Acknowledged items are observed and observations have intents." (Set.size produced + Set.size observed) violations examples

duplicatesWithin :: Text -> InvariantClass -> Text -> DuplicateBudget -> [DisturbanceWindow] -> Checker
duplicatesWithin checkerName cls consumerScope budget windows =
  Checker checkerName "duplicates-within-windows" cls ByKeySeq relevant False (CheckFold Map.empty step finish)
  where
    relevant fact = fact.kind == Observed && fact.scope == consumerScope
    identity fact = (fact.key, fact.seq, fact.id)
    step observations fact = Map.insertWith (<>) (identity fact) [fact] observations
    finish observations =
      let duplicates = [(key, sortOn (.wall) facts) | (key, facts) <- Map.toList observations, length facts > 1]
          classify (key, first : rest) =
            let extra = length rest
                windowed = any (\window -> first.wall <= maybe maxBound id window.end && any (\fact -> fact.wall >= window.start) rest) windows
                overBudget = maybe False (extra >) budget.maxPerWindow
             in (if windowed && not overBudget then 0 else extra, object ["item" .= showIdentity key, "duplicates" .= extra, "windowed" .= windowed])
          classify _ = (0, Null)
          classified = fmap classify duplicates
          violations = sum (fmap fst classified)
          base = result "Duplicates occur only inside declared disturbance budgets." (sum (fmap (length . snd) duplicates)) violations (fmap snd (filter ((> 0) . fst) classified))
          parameters = object ["maxPerWindow" .= budget.maxPerWindow, "maxRedeliveryDelayMicros" .= budget.maxRedeliveryDelayMicros]
          counts = Map.fromList [("examined", fromIntegral (sum (fmap (length . snd) duplicates))), ("violations", fromIntegral violations), ("duplicates", fromIntegral (sum [length facts - 1 | (_, facts) <- duplicates]))]
       in setCounts counts (setParameters parameters base)

perKeyOrder :: Text -> InvariantClass -> Text -> Checker
perKeyOrder checkerName cls consumerScope = orderChecker checkerName "per-key-order" cls ByScopeKeyArrival (\fact -> fact.scope == consumerScope) (\fact -> (fact.scope, fact.key)) (.seq)

globalOrder :: Text -> InvariantClass -> Text -> Text -> Checker
globalOrder checkerName cls consumerScope attribute = orderCheckerMaybe checkerName "global-order" cls ByScopeArrival (\fact -> fact.scope == consumerScope && fact.kind == Observed) (.scope) (attrInt attribute)

gaplessPositions :: Text -> InvariantClass -> Checker
gaplessPositions checkerName cls =
  Checker checkerName "gapless-positions" cls ByKeySeq (\fact -> fact.kind == Produced) False (CheckFold Set.empty (\seen fact -> Set.insert fact.seq seen) finish)
  where
    finish seen = case (Set.lookupMin seen, Set.lookupMax seen) of
      (Just low, Just high) ->
        let missing = [value | value <- [low .. high], Set.notMember value seen]
         in result "Acknowledged positions form a contiguous range." (Set.size seen) (length missing) (fmap (object . pure . ("missing" .=)) (take 20 missing))
      _ -> vacuous

exactlyNEffects :: Text -> InvariantClass -> Int -> Checker
exactlyNEffects checkerName cls expected =
  Checker checkerName "exactly-n-effects" cls ByKeySeq (\fact -> fact.kind == Effect) False (CheckFold Map.empty (\counts fact -> Map.insertWith (+) fact.id 1 counts) finish)
  where
    finish counts =
      let wrong = [(item, count) | (item, count) <- Map.toList counts, count /= expected]
       in setParameters (object ["expected" .= expected]) (result "Each idempotency key has exactly the expected number of effects." (sum (Map.elems counts)) (length wrong) [object ["id" .= item, "actual" .= count, "expected" .= expected] | (item, count) <- wrong])

eventualQuiescence :: Text -> InvariantClass -> Deadline -> Checker
eventualQuiescence checkerName cls deadline =
  Checker checkerName "eventual-quiescence" cls ByKeySeq (\fact -> fact.kind `elem` [Produced, Terminal]) False (CheckFold (Map.empty, Map.empty) step finish)
  where
    step (produced, terminal) fact = case fact.kind of
      Produced -> (Map.insert fact.id fact.wall produced, terminal)
      Terminal -> (produced, Map.insert fact.id fact.wall terminal)
      _ -> (produced, terminal)
    finish (produced, terminal) =
      let violations = [(item, started, Map.lookup item terminal) | (item, started) <- Map.toList produced, maybe True (> started + deadline.micros) (Map.lookup item terminal)]
       in setParameters (object ["deadlineMicros" .= deadline.micros]) (result "Every acknowledged item reaches a terminal state before its deadline." (Map.size produced) (length violations) [object ["id" .= item, "producedAt" .= started, "terminalAt" .= ended] | (item, started, ended) <- violations])

monotonicCheckpoints :: Text -> InvariantClass -> Checker
monotonicCheckpoints checkerName cls = orderChecker checkerName "monotonic-checkpoints" cls ByScopeArrival (\fact -> fact.kind == Checkpoint) (.key) (.seq)

disjointOwnership :: Text -> InvariantClass -> Checker
disjointOwnership checkerName cls =
  Checker checkerName "disjoint-ownership" cls ByKeyWall relevant False (CheckFold (Map.empty, []) step finish)
  where
    relevant fact = fact.kind `elem` [Acquired, Acted, Released]
    step (owners, violations) fact = case fact.kind of
      Acquired -> (Map.insertWith Set.union fact.key (Set.singleton fact.scope) owners, violations)
      Released -> (Map.adjust (Set.delete fact.scope) fact.key owners, violations)
      Acted ->
        let active = Map.findWithDefault Set.empty fact.key owners
         in if Set.null active || active == Set.singleton fact.scope then (owners, violations) else (owners, fact : violations)
      _ -> (owners, violations)
    finish (_, violations) = result "No owner acts while another owner holds the same lease." (length violations + 1) (length violations) (fmap factExample violations)

orderChecker :: (Ord group) => Text -> Text -> InvariantClass -> SortOrder -> (Fact -> Bool) -> (Fact -> group) -> (Fact -> Int64) -> Checker
orderChecker checkerName invariantName cls order select group value =
  Checker checkerName invariantName cls order select False (CheckFold Map.empty (\groups fact -> Map.insertWith (<>) (group fact) [value fact] groups) finish)
  where
    finish groups =
      let sequences = fmap reverse (Map.elems groups)
          violations = sum (fmap inversions sequences)
       in result ("Observed values are monotonic for " <> invariantName <> ".") (sum (fmap length sequences)) violations []

orderCheckerMaybe :: (Ord group) => Text -> Text -> InvariantClass -> SortOrder -> (Fact -> Bool) -> (Fact -> group) -> (Fact -> Maybe Int64) -> Checker
orderCheckerMaybe checkerName invariantName cls order select group value =
  Checker checkerName invariantName cls order select False (CheckFold Map.empty step finish)
  where
    step groups fact = maybe groups (\item -> Map.insertWith (<>) (group fact) [item] groups) (value fact)
    finish groups =
      let sequences = fmap reverse (Map.elems groups)
          violations = sum (fmap inversions sequences)
       in result ("Observed values are monotonic for " <> invariantName <> ".") (sum (fmap length sequences)) violations []

inversions :: [Int64] -> Int
inversions values = length [() | (left, right) <- zip values (drop 1 values), right < left]

attrInt :: Text -> Fact -> Maybe Int64
attrInt attribute fact = case KeyMap.lookup (Key.fromText attribute) fact.attrs of Just (Number value) -> toBoundedInteger value; _ -> Nothing

factExample :: Fact -> Value
factExample fact = object ["kind" .= fact.kind, "key" .= fact.key, "seq" .= fact.seq, "id" .= fact.id, "scope" .= fact.scope]

example :: Text -> (Text, Int64, Text) -> Value
example label (key, sequenceNumber, item) = object ["type" .= label, "key" .= key, "seq" .= sequenceNumber, "id" .= item]

showIdentity (key, sequenceNumber, item) = object ["key" .= key, "seq" .= sequenceNumber, "id" .= item]

setParameters :: Value -> CheckResult -> CheckResult
setParameters parameters (CheckResult status reason summary counts _ counterExamples) = CheckResult status reason summary counts parameters counterExamples

setCounts :: Map Text Int64 -> CheckResult -> CheckResult
setCounts counts (CheckResult status reason summary _ parameters counterExamples) = CheckResult status reason summary counts parameters counterExamples