packages feed

lattest-lib-0.2: src/Lattest/Exec/StandardTestControllers/CompleteTestSuite.hs

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE QuantifiedConstraints #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TupleSections #-}
module Lattest.Exec.StandardTestControllers.CompleteTestSuite (
accessSeqSelector,
adgTestSelector,
nCompleteSingleState,
runNCompleteTestSuite,
randomCoveringTestSelector,
randomCoveringTestSelectorFromSeed,
randomCoveringTestSelectorFromGen,
slowRandomInputCoverer,
Switch,
allSwitches,
isInputSwitch,
switchesTaken,
observeInputCoverage,
mergeInputCoverage,
prettyPrintInputCoverage,
InputCoverageReport, InputCoverageKey, InputCoverageValue
)
where
import Lattest.Adapter.Adapter(Adapter,close)
import Lattest.Adapter.StandardAdapters(withQuiescenceMillis)
import Lattest.Exec.ADG.Aut(adgAutFromAutomaton)
import Lattest.Exec.ADG.DistGraph(computeAdaptiveDistGraph)
import Lattest.Exec.ADG.SplitGraph(Evidence(..))
import Lattest.Exec.StandardTestControllers(andThen,randomTestSelectorFromSeed,untilCondition,stopAfterSteps,observingOnly,printActions,traceObserver,andObserving,stateObserver, TestSelector, selector, solveRandomInput, TestObserver, observer)
import Lattest.Exec.Testing(TestController(..), runTester,Verdict)
import Lattest.Model.Alphabet(IOAct(..), IOSuspAct, Suspended(..), asSuspended, SymInteract (..), IOSymInteract, IOGateValue, GateValue(..), SymGuard)
import Lattest.Model.Automaton(AutIntrpr(..),AutSyntax (..), After, TransitionMapping (..), STStdest(..), IntrpState(..), buildGateValuation, evalBool, implicitDestination)
import Lattest.Model.BoundedMonad(Det(..), asConjunction, FreeLattice, ordBind, ordReturn)
import Lattest.Model.StandardAutomata(ConcreteSuspAutIntrpr, accessSequences, interpretQuiescentConcrete, IOSTSIntrp, allLocations, symStep)
import Lattest.Model.Symbolic.SolveSymPrim(substituteInGuard, isGuardSatisfiable, solveGuardAmong, valuationToGateValue)

import Control.Monad (forM, (>=>), filterM)
import qualified Data.List as List
import qualified Data.Map as Map
import Data.Dependent.Sum (DSum (..))
import qualified Data.Set as Set
import System.Random(StdGen, initStdGen, mkStdGen)
import Data.Maybe (fromMaybe)
import Data.Foldable (toList)
import Data.Either (fromRight)
import Lattest.Model.Symbolic.Expr (Variable (..), Constant (..), withExprConstraints, Type, sTrue, (.||), (.&&), VarModel, valuationToVarModel, getVariables, freeVars, ExprType (..), constType, Expr)
import Lattest.Model.Symbolic.SolveSTS (solveRandomInteractionWith, indexVar)
import Lattest.Util.PrettyExpr (prettyExpr, prettyVal)
import Data.Dependent.Map (DMap)
import Data.Some (Some(..), mapSome)
import Data.Type.Equality ((:~:)(..))
import Data.GADT.Compare (GEq(..), GCompare (..), GOrdering (..))
import qualified Data.Dependent.Map as DMap
import Data.GADT.Show (GShow (..), defaultGshowsPrec)
import Data.Constraint.Extras (Has (..))
import Data.Constraint.Compose (ComposeC)
import qualified Data.Maybe as Maybe
import Control.Monad.Extra (findM, anyM, firstJustM)
import Control.Monad.State (StateT, runStateT)
import Data.Containers.ListUtils (nubOrdOn)

{- | A TestController that selects inputs that lead to the given targetState. If unexpected outputs are selected by the SUT the TestSelector still tries to provide the inputs of the access sequence, but this may result in reaching another state.
 Result Bool is True when access sequence has been followed and false when the SUT deviated
-}
accessSeqSelector :: (Ord q, Eq i, Eq o) => ConcreteSuspAutIntrpr Det q i o -> q -> TestController Det q q (IOAct i o) () (IOSuspAct i o) [IOAct i o] (Maybe i) Bool
accessSeqSelector aut targetState =
    let initState = case stateConf aut of
            Det q -> q
            _ -> error "Access sequence: model must be in a specified initial state"
        accSeqs = accessSequences aut initState
    in TestController {
        testControllerState = Maybe.fromJust $ accSeqs Map.!? targetState,
        selectTest = accSeqSelectTest,
        updateTestController = accSeqUpdateTest,
        handleTestClose = \testState' -> return $ case testState' of [] ->  True; _ -> False
    }
    where
    accSeqSelectTest [] _ _ = return $ Right True
    accSeqSelectTest (l:ls) _ _ = return $ case l of
        In i -> Left (Just i, l:ls)
        _ -> Left (Nothing, l:ls)
    accSeqUpdateTest [] _ _ _ = return $ Right True
    accSeqUpdateTest (l:ls) _ label _ = return $ if asSuspended l == label then Left ls else Right False

{- | A TestController that selects inputs according to the adaptive distinguishing sequence of the given automaton
-}
adgTestSelector :: (Ord q, Ord l) => ConcreteSuspAutIntrpr Det q l l -> l ->  TestController Det q q (IOAct l l) () (IOSuspAct l l) (Evidence l) (Maybe l) (Set.Set q)
adgTestSelector aut delta =
    let adgaut = case adgAutFromAutomaton aut delta of
                    Just a -> a
                    Nothing ->  error "could not transform Lattest auomaton into ADG automaton"
        adg = computeAdaptiveDistGraph adgaut False False True
    in TestController {
        testControllerState = adg,
        selectTest = adgSelectTest,
        updateTestController = adgUpdateTest,
        handleTestClose = \_ -> return Set.empty
    }
    where
    adgSelectTest testState _ _ =
        return $ case testState of
            Nil -> Right Set.empty
            Prefix l _ -> Left (Just l, testState)
            Plus _ -> Left (Nothing,testState)

    adgUpdateTest testState _ ioact _ =
       return $ case testState of
            Nil -> Right Set.empty
            Prefix l next -> if ioact == In l then Left next else error "Error: expected to have selected an input but seeing some ioact"
            Plus ls ->
                let nextList = concatMap getNextState ls
                in case nextList of
                    [next] -> Left next
                    _ -> error "ADG error: expected to have observed one output or quiescence"
                where
                getNextState ev = case ev of
                    Nil -> []
                    Prefix l next -> if l == delta
                                        then [next | ioact == Out Quiescence]
                                     else [next | ioact == Out (OutSusp l)]
                    Plus ls' -> concatMap getNextState ls'

{- | A TestController that yields tests that tries to take an access sequence to the targetState and then executes the adaptive distinguishing sequence
-}
nCompleteSingleState :: (Ord q, Ord l) => ConcreteSuspAutIntrpr Det q l l -> Int -> Int -> l -> q
                                                    -> TestController Det q q (IOAct l l) () (IOSuspAct l l) (((), [IOSuspAct l l]), Maybe (Det q)) i20 ([IOSuspAct l l], Maybe (Det q))
                                                    -> IO (TestController Det q q (IOAct l l) () (IOSuspAct l l) (Either (Either [IOAct l l] StdGen, Int) (Evidence l), (((), [IOSuspAct l l]), Maybe (Det q))) (Maybe l) ([IOSuspAct l l], Maybe (Det q)))
nCompleteSingleState model seed nrSteps delta targetState observer' = do
    return $ accessSeqSelector model targetState
        `andThen` randomTestSelectorFromSeed seed `untilCondition` stopAfterSteps nrSteps
            `andThen` adgTestSelector model delta `observingOnly` observer'

{- | Runs tests from nCompleteSingleState for each given targetState and seed
-}
runNCompleteTestSuite :: (Ord q, Ord l, Show q, Show l) => IO (Adapter (IOAct l l) l) -> AutSyntax Det q (IOAct l l) () -> Int -> l -> [(q, Int)] -> IO [(q, Verdict, ([IOSuspAct l l], Maybe (Det q)))]
runNCompleteTestSuite adapter spec nrSteps delta targetStatesAndSeeds =
        forM targetStatesAndSeeds $ \(targetState,seed) -> do
            putStrLn "connecting..."
            adap <- adapter
            imp <- withQuiescenceMillis 200 adap
            let model = interpretQuiescentConcrete spec
            putStrLn "starting test..."
            putStrLn $ "accessing state: " ++ show targetState
            selector' <- testSelector model seed targetState
            (verdict,(observed, maybeMq)) <- runTester model selector' imp
            close adap
            return (targetState, verdict, (observed, maybeMq))
    where testSelector model seed targetState = nCompleteSingleState model seed nrSteps delta targetState $ printActions `observingOnly` traceObserver `andObserving` stateObserver

-- The most basic version: randomly pick an uncovered input, if any, and otherwise just random
-- If a 'to cover' set is not provided, it gets initialized to the set of every transition
-- Using 'observeControllerState', the set of uncovered transitions can be passed on to the next test.
randomCoveringTestSelector
  :: forall m loc q t tdest act i' o i.
     (After m loc q t tdest act, Show i', Show o, Show loc, Ord i', Ord o, Ord q, Ord loc
     , tdest ~ STStdest, m ~ FreeLattice, t ~ IOSymInteract i' o, q ~ IntrpState loc, act ~ IOGateValue i' o, i ~ GateValue i') -- hardcoding to STS
  => AutIntrpr m loc q t tdest act
  -> Maybe (Set.Set (Switch loc i' o))
  -> Int -- ^ the number of additional solutions to pick input values randomly from, besides the first one the SMT solver finds
  -> IO (TestSelector m loc q t tdest act (StdGen, Set.Set (Switch loc i' o)) i)
randomCoveringTestSelector intrpr mtocover extraSolutions = randomCoveringTestSelectorFromGen intrpr mtocover extraSolutions <$> initStdGen

-- | As 'randomCoveringTestSelector', starting with the given random seed.
randomCoveringTestSelectorFromSeed
  :: forall m loc q t tdest act i' o i.
     (After m loc q t tdest act, Show i', Show o, Show loc, Ord i', Ord o, Ord q, Ord loc
     , tdest ~ STStdest, m ~ FreeLattice, t ~ IOSymInteract i' o, q ~ IntrpState loc, act ~ IOGateValue i' o, i ~ GateValue i') -- hardcoding to STS
  => AutIntrpr m loc q t tdest act
  -> Maybe (Set.Set (Switch loc i' o))
  -> Int -- ^ the number of additional solutions to pick input values randomly from, besides the first one the SMT solver finds
  -> Int
  -> TestSelector m loc q t tdest act (StdGen, Set.Set (Switch loc i' o)) i
randomCoveringTestSelectorFromSeed intrpr mtocover extraSolutions seed = randomCoveringTestSelectorFromGen intrpr mtocover extraSolutions (mkStdGen seed)

randomCoveringTestSelectorFromGen
  :: forall m loc q t tdest act i' o i.
     (After m loc q t tdest act, Show i', Show o, Show loc, Ord i', Ord o, Ord loc, Ord q,
     tdest ~ STStdest, m ~ FreeLattice, t ~ IOSymInteract i' o, q ~ IntrpState loc, act ~ IOGateValue i' o, i ~ GateValue i') -- hardcoding to STS
  => AutIntrpr m loc q t tdest act
  -> Maybe (Set.Set (Switch loc i' o))
  -> Int -- ^ the number of additional solutions to pick input values randomly from, besides the first one the SMT solver finds
  -> StdGen
  -> TestSelector m loc q t tdest act (StdGen, Set.Set (Switch loc i' o)) i
randomCoveringTestSelectorFromGen intrpr mtocover extraSolutions g = selector (g, fromMaybe (allSwitches intrpr) mtocover) select update
  where
    select :: (StdGen, Set.Set (Switch loc i' o))
           -> AutIntrpr m loc q t tdest act
           -> m q
           -> IO (Maybe (i, (StdGen, Set.Set (Switch loc i' o))))
    select (g', tocover) intrpr' mq = do
      -- as in randomDataTestSelectorFromGen, except we try to take new transitions
      (maybeGateValue, g'') <- solveRandomInteractionWith extraSolutions intrpr' maybeNewInAct g'
      case maybeGateValue of
        Just value -> pure $ Just (value, (g'',tocover))
        Nothing -> do
          (maybeGateValue', g''') <- solveRandomInput extraSolutions g'' maybeFromIOAct intrpr'
          return $ case maybeGateValue' of
            Just value -> Just (value, (g''',tocover))
            Nothing -> Nothing
      where
        maybeFromIOAct (SymInteract io xs) = case io of
          In i -> Just $ SymInteract i xs
          Out _ -> Nothing
        maybeNewInAct = maybeFromIOAct >=> \(SymInteract i vs) -> case asConjunction mq of
          -- The state has disjunction, so we're not covering any new transitions anyway.
          -- Just take a random transition.
          Left _ -> Just (SymInteract i vs, sTrue)
          -- The actual filtering: besides picking a gate with an uncovered switch, require the guard of some uncovered switch
          -- to hold. Otherwise the solver is free to keep picking values for the already covered switches of that gate.
          Right qs -> case [ substituteInGuard v guard | IntrpState l v <- Set.toList qs, Switch loc act (STSLoc (guard, _)) _dest <- Set.toList tocover, loc == l, act == SymInteract (In i) vs ] of
            [] -> Nothing
            gs -> Just (SymInteract i vs, foldr1 (.||) gs)  -- or'd guards of uncovered switches to make sure we cover at least one

    -- note: coverage is computed from the `m q` before the transition, which is passed in as the last argument.
    update :: (a, Set.Set (Switch loc i' o))
           -> AutIntrpr m loc q t tdest act
           -> IOGateValue i' o
           -> m q
           -> IO (Maybe (a, Set.Set (Switch loc i' o)))
    update (g', tocover) intrpr' act mq =
      let newcover = switchesTaken intrpr' mq act
      in pure $ Just (g', tocover Set.\\ newcover)

-- | A switch of an STS: source location, interaction (gate and parameters), guard and assignment, and target location.
data Switch loc i o = Switch loc (IOSymInteract i o) STStdest loc deriving (Eq, Ord, Show)

-- | All switches present in the model.
allSwitches :: (Ord loc, Ord i, Ord o) => IOSTSIntrp FreeLattice loc i o -> Set.Set (Switch loc i o)
allSwitches intrpr = let syn = syntacticAutomaton intrpr
  in Set.fromList [ Switch l t td l' | l <- Set.toList (allLocations syn), (t, dests) <- Map.toList (transRel syn l), (td, l') <- toList dests ]

isInputSwitch :: Switch loc i o -> Bool
isInputSwitch (Switch _ (SymInteract (In _) _) _ _) = True
isInputSwitch _ = False

{- |
    The switches taken by an action from the given state configuration. If the configuration contains a disjunction, it is unknown
    which switches were taken, so none are reported.
-}
switchesTaken :: (Ord loc, Ord i, Ord o)
  => IOSTSIntrp FreeLattice loc i o -> FreeLattice (IntrpState loc) -> IOGateValue i o -> Set.Set (Switch loc i o)
switchesTaken intrpr mq gv@(GateValue _ vals) = case (asConjunction mq, asTransition (alphabet syn) gv) of
  (Right qs, Just t@(SymInteract _ vars)) -> Set.unions
    [ fromRight mempty $ asConjunction $ dests `ordBind` \(td@(STSLoc (g, _)), l') ->
        if evalBool (buildGateValuation vars vals) (substituteInGuard v g)
          then ordReturn $ Switch l t td l'
          else implicitDestination gv
    | IntrpState l v <- Set.toList qs
    , Just dests <- [Map.lookup t (transRel syn l)] ]
  _ -> mempty
  where syn = syntacticAutomaton intrpr

data InputCoverageKey i tp = ICK i SymGuard (Variable tp) deriving Show
data InputCoverageValue tp = ICV (Type tp) (Set.Set (Constant tp)) deriving Show
type InputCoverageReport i = DMap (InputCoverageKey i) InputCoverageValue
instance GEq (InputCoverageKey i) where
  geq (ICK _ _ v) (ICK _ _ v') = geq v v'
instance Ord i => GCompare (InputCoverageKey i) where
  gcompare (ICK i g v) (ICK i' g' v') = case compare i i' of
    GT -> GGT
    LT -> GLT
    EQ -> case compare g g' of
      GT -> GGT
      LT -> GLT
      EQ -> gcompare v v'
instance Show i => GShow (InputCoverageKey i) where
  gshowsPrec = defaultGshowsPrec
instance Has a Type => Has a InputCoverageValue where
  has (ICV t _) = has @a t
instance Has (ComposeC Show InputCoverageValue) (InputCoverageKey i) where
  has (ICK _ _ v) = withExprConstraints v

{- |
    Combine two input coverage reports.
-}
mergeInputCoverage :: Ord i => InputCoverageReport i -> InputCoverageReport i -> InputCoverageReport i
mergeInputCoverage = DMap.unionWithKey (\_ (ICV t a) (ICV _ b) -> ICV t (Set.union a b))

{- |
    Render an input coverage report: per input gate, per guard, the values used for each parameter. Guards and values are
    written as in 'prettyExpr', given the enums and the names of the fields of the structures (as given by the parser).
-}
prettyPrintInputCoverage :: (Show i, Ord i) => Map.Map String (Some Expr) -> Map.Map (Some Type, [Bool]) String -> InputCoverageReport i -> String
prettyPrintInputCoverage enums fields icr = unlines $ concat
    [ show gate' : concat
        [ ("  guard: " <> prettyExpr enums fields guard) : [ "    " <> var <> ": " <> List.intercalate ", " vals <> " (" <> show (length vals) <> " different input values)" | (var, vals) <- params ]
        | (guard, params) <- Map.toList guards ]
    | (gate', guards) <- Map.toList grouped ]
  where
    grouped = Map.fromListWith (Map.unionWith (<>))
        [ (gate', Map.singleton guard [(varName v, prettyVal enums fields <$> Set.toList vals)]) | ICK gate' guard v :=> ICV _ vals <- DMap.toList icr ]

observeInputCoverage :: (Show i, Ord loc, Ord i, Ord o) => TestObserver FreeLattice loc (IntrpState loc) (IOSymInteract i o) STStdest (IOGateValue i o) (InputCoverageReport i) (InputCoverageReport i)
observeInputCoverage = observer mempty update pure
  where
    update icr _ (GateValue (Out _) _) _ = pure icr
    update icr intrpr (GateValue (In gate') consts) mq = pure $ foldr (\(guard, c :=> v) icr' -> DMap.insertWith (\(ICV t a) (ICV _ b) -> ICV t $ Set.union a b) (ICK gate' guard v) (ICV (constType c) $ Set.singleton c) icr') icr $ cartesian guards taggedvals
      where
        -- the guards of the switches that are taken: the ones that hold for the input values, in the state before the transition
        guards
          | Right qs <- asConjunction mq = concatMap (\(IntrpState loc v) -> case asConjunction $ transRel (syntacticAutomaton intrpr) loc Map.! SymInteract (In gate') vars of
                Right tdests -> [ guard | (STSLoc (guard, _), _) <- Set.toList tdests, evalBool (buildGateValuation vars consts) (substituteInGuard v guard) ]
                Left _ -> error "TODO: compute input coverage for disjunctions") $ Set.toList qs
          | otherwise = error "TODO: compute input coverage for disjunctions" -- mempty
        taggedvals :: [DSum Constant Variable]
        taggedvals = zipWith
          (\(Some c@(Constant x1)) (Some v@(Variable _ tp2)) -> case geq (typeOf x1) tp2 of
              Nothing -> error "type mismatch"
              Just Refl -> c :=> v)
          consts
          vars
        alph = alphabet $ syntacticAutomaton intrpr
        vars = case Set.toList $ flip Set.filter alph \case
          SymInteract (Out _) _ -> False
          SymInteract (In i) _ -> i == gate' of
            [SymInteract _ vs] -> vs
            _ -> error $ "zero or more than one inputs in the alphabet match " <> show gate'
        cartesian as bs = [(a,b) | a <- as, b <- bs]

slowRandomInputCoverer
  :: forall m loc q t tdest act i' o i.
     (After m loc q t tdest act, Show i', Show o, Show loc, Ord i', Ord o, Ord loc, Ord q,
     tdest ~ STStdest, m ~ FreeLattice, t ~ IOSymInteract i' o, q ~ IntrpState loc, act ~ IOGateValue i' o, i ~ GateValue i') -- hardcoding to STS
  => AutIntrpr m loc q t tdest act
  -> Maybe (Set.Set (Switch loc i' o))
  -> Int -- ^ the maximum number of steps
  -> Int -- ^ the number of additional solutions to pick input values randomly from, besides the first one the SMT solver finds
  -> StdGen
  -> TestSelector m loc q t tdest act (StdGen, Set.Set (Switch loc i' o), Maybe [act], Int) i
slowRandomInputCoverer intrpr mtocover maxSteps extraSolutions g = selector (g, fromMaybe (allSwitches intrpr) mtocover, Nothing, maxSteps) select update
  where
    select :: (StdGen, Set.Set (Switch loc i' o), Maybe [act], Int)
           -> AutIntrpr m loc q t tdest act
           -> m q
           -> IO (Maybe (i, (StdGen, Set.Set (Switch loc i' o), Maybe [act], Int)))
    select (g', tocover, Just (act:plan), budget) _ _ = case act of -- There is a plan; we execute it.
      GateValue (Out _) _ -> pure Nothing -- the plan is to wait for an output here, so we don't choose an input
      GateValue (In i) cs -> pure $ Just (GateValue i cs, (g', tocover, Just (act:plan), budget)) -- don't remove the act from the plan here, only in update!
    select (g', tocover, Just [], budget) intrpr' mq = select (g', tocover, Nothing, budget) intrpr' mq
    select (g', tocover, Nothing, budget) intrpr' mq = do
      -- don't currently have a plan. If there's immediately any untaken switches available, we take one
      (maybeGateValue, g'') <- solveRandomInteractionWith extraSolutions intrpr' maybeNewInAct g'
      case maybeGateValue of
        Just value -> pure $ Just (value, (g'',tocover, Nothing, budget))
        Nothing -> do
          -- There are no untaken switches available currently, so we create a plan
          case asConjunction mq of
            Left _ -> do -- Not going to BFS in a disjunction state, default to a random transition
              takeRandomInput g''
            Right currStates -> do
              let initial = [ (loc, (sTrue, valuationToVarModel v, 0)) | IntrpState loc v <- Set.toList currStates ]
              -- only look for plans that can be completed, including taking the uncovered switch afterwards, in the steps that are left
              found <- breadthFirstSearch key (Set.fromList $ map key initial) (map (,[]) initial) bfsStep bfsPred (budget - 1)
              (plan, g''') <- runStateT (maybe (pure Nothing) concretise found) g''
              case plan of
                -- Note: the plan only goes to a state where the switch _can_ be taken, but doens't take it.
                -- Could add taking it, but this testcontroller will, once the plan is done,
                -- just take a random untaken switch anyway (of which we know at least one is present).
                Just (act:acts) -> select (g''', tocover, Just (act:acts), budget) intrpr' mq
                _ -> takeRandomInput g'''
      where
        maybeFromIOAct (SymInteract io xs) = case io of
          In i -> Just $ SymInteract i xs
          Out _ -> Nothing
        maybeNewInAct = maybeFromIOAct >=> \(SymInteract i vs) -> case asConjunction mq of
          -- The state has disjunction, so we're not covering any new transitions anyway.
          -- Just take a random transition.
          Left _ -> Just (SymInteract i vs, sTrue)
          -- The actual filtering: besides picking a gate with an uncovered switch, require the guard of some uncovered switch
          -- to hold. Otherwise the solver is free to keep picking values for the already covered switches of that gate.
          Right qs -> case [ substituteInGuard v guard | IntrpState l v <- Set.toList qs, Switch loc act (STSLoc (guard, _)) _dest <- Set.toList tocover, loc == l, act == SymInteract (In i) vs ] of
            [] -> Nothing
            gs -> Just (SymInteract i vs, foldr1 (.||) gs)  -- or'd guards of uncovered switches to make sure we cover at least one
        takeRandomInput g'' = do
          (maybeGateValue', g''') <- solveRandomInput extraSolutions g'' maybeFromIOAct intrpr'
          return $ case maybeGateValue' of
            Just value -> Just (value, (g''',tocover, Nothing, budget))
            Nothing -> Nothing

        locVars = case toList mq of
          IntrpState _ v : _ -> getVariables v
          [] -> []
        isSat guard = isGuardSatisfiable (toList $ freeVars guard) guard
        -- the gate parameters as they occur in the guard of the n-th step of a path, see `symStep`
        indexParams n (SymInteract gate' vars) = SymInteract gate' (mapSome (indexVar n) <$> vars)

        -- arguments to the BFS
        -- branch to all satisfiable options
        bfsStep :: SymNode loc -> IO [(SymNode loc, IOSymInteract i' o)]
        bfsStep (loc, (pathCond, pvar, n)) = filterM (\((_, (pathCond', _, _)), _) -> isSat pathCond')
          [ ((loc', (pathCond .&& guard, pvar', n + 1)), indexParams n t)
          | (t, dests) <- Map.toList $ transRel (syntacticAutomaton intrpr') loc
          , (tdest, loc') <- Set.toList $ Set.fromList $ toList dests
          , let (guard, pvar') = symStep locVars n pvar tdest ]

        -- check whether an uncovered switch can be taken from this location
        bfsPred :: SymNode loc -> IO Bool
        bfsPred = anyM (isSat . snd) . targetConds

        -- We currently use just the set of visited locations in the BFS. Ideally, we want something
        -- that's stricter (i.e. considers less things to be equal), but the obvious candidates
        -- (namely (loc, [gate]) and (loc, VarModel)) are both too strict (making the search take too long, by revisiting nodes too often).
        -- The ideal 'key' would represent exactly the space of concrete Valuations that are possible at this location,
        -- and the ideal BFS would check whether the resulting space from a 'step' is a subset of the union of the spaces we have already seen,
        -- adding only the unseen part of it to the 'frontier'.
        -- Too strict keys make the search infeasibly slow, too lax keys make the search unable to find certain reachable states (e.g. coffee machine).
        -- Neither make the testcontroller unsound, they just make it worse at covering all switches.
        key :: SymNode loc -> loc
        key = fst

        -- per uncovered switch from this location: its gate parameters, and the condition to get to this location and then take that switch
        targetConds :: SymNode loc -> [([Some Variable], SymGuard)]
        targetConds (loc, (pathCond, pvar, n)) =
          [ (vars, pathCond .&& fst (symStep locVars n pvar tdest))
          | Switch src t tdest _ <- Set.toList tocover, src == loc
          , let SymInteract _ vars = indexParams n t ]

        -- pick values for the gates along the path, such that an uncovered switch can be taken at the end of it
        concretise :: (SymNode loc, [IOSymInteract i' o]) -> StateT StdGen IO (Maybe [act])
        concretise (node, path) = fmap (\valuation -> map (`valuationToGateValue` valuation) path)
          <$> firstJustM (\(targetVars, cond) -> solveGuardAmong extraSolutions (pathVars ++ targetVars) cond) (targetConds node)
          where pathVars = concat [ vars | SymInteract _ vars <- path ]

    -- note: coverage is computed from the `m q` before the transition, which is passed in as the last argument.
    update :: (a, Set.Set (Switch loc i' o), Maybe [act], Int)
           -> AutIntrpr m loc q t tdest act
           -> IOGateValue i' o
           -> m q
           -> IO (Maybe (a, Set.Set (Switch loc i' o), Maybe [act], Int))
    update (g', tocover, plan, budget) intrpr' act mq =
      let newcover = switchesTaken intrpr' mq act
          newplan = case plan of
            Nothing -> Nothing
            Just [] -> Nothing
            Just (act':acts) -> if act == act'
              then Just acts -- successfully acted on our plan
              else Nothing -- failed to follow the plan: did the SUT choose an output we didn't hope for?
      in pure $ Just (g', tocover Set.\\ newcover, newplan, budget - 1)

-- | A vertex of the symbolic search for a path: a location, with the path condition to get there, the symbolic values of the
-- state variables once there, and the number of steps taken to get there.
type SymNode loc = (loc, (SymGuard, VarModel, Int))

-- self-rolled BFS that: works with monadic steps, distinguishes between vertices and edges, and returns the vertex it found together with
-- the path it took as a list of edges. Vertices count as visited only if the location matches, but more info is carried.
-- I haven't looked much into what else is on Hackage, maybe there's a much more elegant solution using something like Data.Graph
breadthFirstSearch :: (Monad m, Ord k) => (a -> k) -> Set.Set k -> [(a, [b])] -> (a -> m [(a,b)]) -> (a -> m Bool) -> Int -> m (Maybe (a, [b]))
breadthFirstSearch key visited frontier step predicate maxdepth
  | maxdepth <= 0 || null frontier = pure Nothing -- failed to find a path
  | otherwise = do
      new <- nubOrdOn (key . fst) -- we only keep one of each state, if there were multiple paths to get somewhere
          . concatMap (filter (not . (`Set.member` visited) . key . fst))
          <$> mapM
                (\(a,bs) -> map (\(a',b') -> (a', b':bs)) <$> step a)
                frontier
      let newVisited = Set.union (Set.fromList $ map (key . fst) new) visited
      findM (predicate . fst) new >>= \case
        Nothing -> breadthFirstSearch key newVisited new step predicate (maxdepth - 1)
        Just (a, path) -> pure $ Just (a, reverse path) -- the path was built up back to front