lattest-lib-0.2: src/Lattest/Model/Symbolic/MCDCSTS.hs
{-# LANGUAGE GADTs #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
-- | Split the guarded input switches of an STS into their unique-cause MC/DC
-- rows. A test suite that covers every switch of the result has MC/DC coverage
-- of the original guards.
module Lattest.Model.Symbolic.MCDCSTS
( completeMCDC
, completeMCDCWith
, completeMCDCReport
, completeMCDCReportWith
, SplitMode (..)
, MCDCReport (..)
, GuardReport (..)
, RowReport (..)
, RowStatus (..)
, prettyMCDCReport
, defaultListLengths
, splitGuard
) where
import Control.Monad (filterM, forM, forM_, unless, when, (<=<))
import Data.Bifunctor (first)
import qualified Data.Foldable as Foldable
import Data.Function (on)
import Data.GADT.Compare (geq)
import Data.IORef (modifyIORef', newIORef, readIORef)
import Data.List (groupBy, intercalate)
import qualified Data.Map.Strict as Map
import qualified Data.Set as Set
import Data.Some (Some (Some))
import Data.Type.Equality ((:~:) (Refl))
import Lattest.Model.Alphabet (IOAct (In), SymGuard, SymInteract (SymInteract))
import Lattest.Model.Automaton (AutSyntax, STStdest (STSLoc), automaton, alphabet, initConf,
stsTLoc, transRel)
import Lattest.Model.BoundedMonad (BoundedMonad, MeetSemiLattice ((/\)), ordBind,
ordReturn)
import qualified Lattest.Model.Internal.MCDCGeneration as MCDC
import Lattest.Model.StandardAutomata (STS)
import Lattest.Model.Symbolic.Expr (Variable, freeVars, varType, (.&&), (.==), (.||))
import Lattest.Model.Symbolic.Internal.ExprDefs (Expr (Expr),
ExprConstraints,
ExprView (And, Const, Equal, Filter, Foldr, Gez, Length, Map, Not, Product, Sum, Var),
Type (BoolType), view, withExprConstraints)
import qualified Lattest.Model.Symbolic.Internal.FreeMonoidX as FMX
import Lattest.Model.Symbolic.Internal.FreeMonoidX (distinctTermsT)
import Lattest.Model.Symbolic.Internal.ExprImpls (assign, noAssignment, reduce, sAnd, sConst, sFalse,
sHead, sIfThenElse, sIsNonNegative, sLength, sNot,
sProduct, sSum, sTail, sTrue, sVar, subst)
import Lattest.Model.Symbolic.SolveSymPrim (isGuardSatisfiable)
{- |
A guard, or a part of a guard, after opening its lists for a fixed length.
A list of length @n@ is opened into its @n@ elements: a condition on all
elements becomes a condition per element, and the length of the list is a
constant. The length of a list is then never an atom.
-}
data Opened
= Known Bool -- ^ a constant for this length
| Counted (ExprView Integer) [Bool] -- ^ a condition on a count @length (filter x cond xs)@: its value per number of elements that satisfy @cond@
| Decision (MCDC.Expr (ExprView Bool))
-- | True for the list parameters of the gate: the lists that are opened.
isOpenList :: Set.Set (Some Variable) -> ExprView [a] -> Bool
isOpenList params (Var v) = Some v `Set.member` params
isOpenList _ _ = False
lengthOf :: ExprView [a] -> ExprView Integer
lengthOf xs = view (sLength (Expr xs))
-- | The lengths @length xs@ of the lists that a guard is opened on. These are
-- the list parameters with a condition on all elements (@forall@ or @exists@),
-- a count of elements, or a length in the guard.
openLists :: Set.Set (Some Variable) -> ExprView t -> Set.Set (ExprView Integer)
openLists params e = case e of
Not x -> openLists params x
And es -> Set.unions (map (openLists params) (Set.toList es))
Foldr _ _ _ _ (Map _ cond xs)
| isOpenList params xs -> Set.insert (lengthOf xs) (openLists params cond)
Length _ (Filter _ cond xs)
| isOpenList params xs -> Set.insert (lengthOf xs) (openLists params cond)
Length _ xs
| isOpenList params xs -> Set.singleton e
Equal _ l r -> openLists params l `Set.union` openLists params r
Gez x -> openLists params x
Sum _ (distinctTermsT -> es) -> Set.unions (map (openLists params) es)
Product _ (distinctTermsT -> es) -> Set.unions (map (openLists params) es)
_ -> Set.empty
-- | The lengths and counts of opened lists in an integer comparison. The search
-- looks through sums and products only.
lengthTerms :: Set.Set (Some Variable) -> ExprView t -> Set.Set (ExprView Integer)
lengthTerms params e = case e of
Length _ (Filter _ _ xs)
| isOpenList params xs -> Set.singleton e
Length _ xs
| isOpenList params xs -> Set.singleton e
Equal _ l r -> lengthTerms params l `Set.union` lengthTerms params r
Gez x -> lengthTerms params x
Sum _ (distinctTermsT -> es) -> Set.unions (map (lengthTerms params) es)
Product _ (distinctTermsT -> es) -> Set.unions (map (lengthTerms params) es)
_ -> Set.empty
-- | True for a comparison with the length of a fold over an opened list, such
-- as the uniqueness of its elements. The search looks through sums and
-- products only.
hasFoldLength :: Set.Set (Some Variable) -> ExprView t -> Bool
hasFoldLength params e = case e of
Length _ (Foldr _ _ _ _ xs) -> isOpenList params xs
Equal _ l r -> hasFoldLength params l || hasFoldLength params r
Gez x -> hasFoldLength params x
Sum _ (distinctTermsT -> es) -> any (hasFoldLength params) es
Product _ (distinctTermsT -> es) -> any (hasFoldLength params) es
_ -> False
{- |
Split a guard into @(side conditions, rest)@. A side condition is a
length guard or a domain guard, met by all possible values of a parameter,
regardless of MC/DC rows.
A domain conjunct on the length of an opened list is not a side condition:
it is a constant for each length, like any other condition on the length.
-}
sideConditions :: Set.Set (Some Variable) -> Set.Set (ExprView Bool) -> SymGuard -> (SymGuard, SymGuard)
sideConditions params domain guard = case view guard of
And es -> let (side, rest) = Set.partition isSide es in (conj side, conj rest)
e | isSide e -> (guard, sTrue)
| otherwise -> (sTrue, guard)
where
isSide :: ExprView Bool -> Bool
isSide e = hasFoldLength params e || (e `Set.member` domain && Set.null (lengthTerms params e))
conj es = if Set.null es then sTrue else sAnd (Set.map Expr es)
-- | The conjuncts of the given domain guards: guards that restrict the values
-- of a parameter to its domain, such as the range of the elements of a list.
domainConjuncts :: [SymGuard] -> Set.Set (ExprView Bool)
domainConjuncts guards = Set.unions [ conjuncts (view guard) | guard <- guards ]
where
conjuncts (And es) = es
conjuncts e = Set.singleton e
isCount :: ExprView Integer -> Bool
isCount (Length _ (Filter {})) = True
isCount _ = False
-- | Replace lengths in an integer comparison by constants. The search looks
-- through sums and products only.
replaceLengths :: (ExprView Integer -> Maybe Integer) -> ExprView t -> Expr t
replaceLengths value e = case e of
Length _ _
| Just k <- value e -> sConst k
Sum t s -> withExprConstraints t $ sSum $ FMX.fromOccurListT $
map (first (replaceLengths value)) $ FMX.toDistinctAscOccurListT s
Product t p -> withExprConstraints t $ sProduct $ FMX.fromOccurListT $
map (first (replaceLengths value)) $ FMX.toDistinctAscOccurListT p
Equal _ l r -> replaceLengths value l .== replaceLengths value r
Gez x -> sIsNonNegative (replaceLengths value x)
_ -> Expr e
-- | The condition on each of the first @n@ elements of a list: the element is
-- substituted for the variable of the condition.
elementConditions :: ExprConstraints a => Int -> Variable a -> ExprView Bool -> ExprView [a] -> [ExprView Bool]
elementConditions n x cond xs =
[ view $ subst (assign x (sHead (iterate sTail (Expr xs) !! i)) noAssignment) (Expr cond) | i <- [0 .. n - 1] ]
{- |
Open a guard for lists of length @n@. Each sub-expression that is not a
'Not', an 'And', or a condition on all elements of an opened list is an
atom. There is no 'Or' case: the constructors store @a || b@ as
@Not (And [Not a, Not b])@.
* @forall@ and @exists@ over an opened list become the conjunction and
the disjunction of the condition on each element.
* A comparison with a count @length (filter x cond xs)@ of an opened list
becomes a count ('MCDC.Count') of the condition on each element.
Conditions on the same count are combined, e.g.
@count >= 1 && count <= 2@.
-}
openGuard :: Int -> Set.Set (Some Variable) -> ExprView Bool -> Either String Opened
openGuard n params = close <=< open
where
open :: ExprView Bool -> Either String Opened
open (Not e) = negation <$> open e
open (And es) = conjunction =<< mapM open (Set.toList es)
open e@(Foldr x y body (Const start) (Map z cond xs))
| Just Refl <- varType x `geq` BoolType, isOpenList params xs, start, Expr body == (sVar x .&& sVar y) =
conjunction =<< mapM open (elementConditions n z cond xs)
| Just Refl <- varType x `geq` BoolType, isOpenList params xs, not start, Expr body == (sVar x .|| sVar y) =
fmap negation . conjunction . map negation =<< mapM open (elementConditions n z cond xs)
| otherwise = openAtom e
open e = openAtom e
openAtom :: ExprView Bool -> Either String Opened
openAtom e
| Set.null terms = Right (Decision (MCDC.Atom e))
| otherwise = case filter isCount (Set.toList terms) of
[] -> Right $ case at 0 of
Const b -> Known b
e' -> Decision (MCDC.Atom e')
[count] -> fmap (Counted count) $ forM [0 .. toInteger n] $ \k -> case at k of
Const b -> Right b
_ -> Left $ "a count of list elements can only be compared with constants and list lengths, in " ++ show (Expr e)
_ -> Left $ "more than one count of list elements in " ++ show (Expr e)
where
terms = lengthTerms params e
-- the atom for k elements that satisfy the condition of the count
at k = reduce $ view $ replaceLengths (value k) e
value k term
| isCount term = Just k
| term `Set.member` terms = Just (toInteger n)
| otherwise = Nothing -- not the length of an opened list
negation :: Opened -> Opened
negation (Known b) = Known (not b)
negation (Counted c table) = Counted c (map not table)
negation (Decision d) = Decision (MCDC.Not d)
-- conditions on the same count are combined before the count is closed
conjunction :: [Opened] -> Either String Opened
conjunction parts
| not (null [ () | Known False <- combined ]) = Right (Known False)
| otherwise = case [ part | part <- combined, not (isKnown part) ] of
[] -> Right (Known True)
[part] -> Right part
parts'
| not (null [ () | Counted {} <- parts' ]) -> conjunction =<< mapM close parts'
| otherwise -> Right $ Decision $ foldl1 MCDC.And [ d | Decision d <- parts' ]
where
counted = Map.fromListWith (zipWith (&&)) [ (c, table) | Counted c table <- parts ]
combined = [ Counted c table | (c, table) <- Map.toList counted ] ++ [ part | part <- parts, not (isCounted part) ]
isKnown (Known _) = True
isKnown _ = False
isCounted (Counted {}) = True
isCounted _ = False
-- a count becomes a constant, or a decision on the elements of the list
close :: Opened -> Either String Opened
close (Counted count table)
| and table || not (or table) = Right (Known (and table))
| otherwise = case count of
Length _ (Filter x cond xs) -> do
elements <- mapM (close <=< open) (elementConditions n x cond xs)
decisions <- forM elements $ \case
Decision d -> Right d
_ -> Left $ "the condition of a count of list elements is a constant, in " ++ show (Expr count)
Right (Decision (MCDC.Count table decisions))
_ -> Left "MCDCSTS.openGuard: not a count" -- unreachable: 'isCount' holds
close opened = Right opened
-- | Convert a row to a guard: the conjunction of its literals.
rowGuard :: MCDC.Row (ExprView Bool) -> SymGuard
rowGuard row = sAnd $ Set.fromList [ literal a v | (a, v) <- Map.toList row ]
where
literal a True = Expr a
literal a False = sNot (Expr a)
-- | Convert a decision back to a guard.
decisionGuard :: MCDC.Expr (ExprView Bool) -> SymGuard
decisionGuard (MCDC.Atom a) = Expr a
decisionGuard (MCDC.Not e) = sNot (decisionGuard e)
decisionGuard (MCDC.And x y) = decisionGuard x .&& decisionGuard y
decisionGuard (MCDC.Or x y) = decisionGuard x .|| decisionGuard y
decisionGuard (MCDC.Count table es) = foldr (.||) sFalse [ holding .== sConst k | (k, True) <- zip [0 ..] table ]
where
holding = sSum $ FMX.fromOccurListT [ (sIfThenElse (decisionGuard e) (sConst 1) (sConst (0 :: Integer)), 1) | e <- es ]
{- |
A guard as it is on lists of length @n@: opened like the rows of that
length, so without conditions on all elements of a list. The solver can
compare this with a row, which is on the elements of the list. The side
conditions of the guard are kept as they are.
The guard is not changed if it has no opened list, or an opened list other
than the given ones, which are the lists that have length @n@.
-}
guardAtLength :: Int -> Set.Set (Some Variable) -> Set.Set (ExprView Bool) -> Set.Set (ExprView Integer) -> SymGuard
-> SymGuard
guardAtLength n params domain lists guard
| Set.null ownLists || not (ownLists `Set.isSubsetOf` lists) = guard
| otherwise = case openGuard n params (view decided) of
Right (Known b) -> if b then side else sFalse
Right (Decision d) -> decisionGuard d .&& side
_ -> guard
where
ownLists = openLists params (view guard)
(side, decided) = sideConditions params domain guard
-- | An MC/DC row of a guard as a guard, with its outcome. A false row has the
-- atoms that it is the false row of an independence pair for: flipping such an
-- atom gives a true row. A row of a guard on lists has the length of the lists.
-- The last part is the value of each atom on the row, in the order of the guard.
type GuardRow = (SymGuard, Bool, [ExprView Bool], Maybe Int, [(ExprView Bool, Bool)])
{- |
The unique-cause MC/DC rows of a guard. A guard without list parameters
with @N@ atoms has @N+1@ rows.
A guard on a list parameter of the given gate parameters is opened once for
each of the given list lengths, with the atoms of each element as separate atoms.
Each row also fixes the length of the list.
The side conditions of a guard, such as the uniqueness of the elements and the
domain conjuncts, are not part of the MC/DC decision. They are added to each row.
-}
guardRows :: [Int] -> Set.Set (Some Variable) -> Set.Set (ExprView Bool) -> SymGuard -> Either String [GuardRow]
guardRows lengths params domain guard
| view guard == Const True = Right [(guard, True, [], Nothing, [])] -- no decision to cover: its own single true row
| Set.null lists = if view side == Const True then rowsFor guard guard id Nothing 0
else rowsFor decided side (.&& side) Nothing 0
| otherwise = concat <$> mapM (\n -> rowsFor decided (hasLength n .&& side) (atLength n . (.&& side)) (Just n) n) lengths
where
lists = openLists params (view guard)
(side, decided) = sideConditions params domain guard
hasLength n = sAnd $ Set.map (\len -> Expr len .== sConst (toInteger n)) lists
-- the elements of a row do not exist in a shorter list, so they are only evaluated on a list of this length
atLength n row = sIfThenElse (hasLength n) row sFalse
rowsFor decision always wrap len n = do
-- a guard with side conditions only has no decision to cover
-- TODO: opening an array guard could be made optional (if not selected, the condition over the list is considered a single atom)
opened <- if view decision == Const True then Right (Known True) else openGuard n params (view decision)
case opened of
Known True -> Right [(always, True, [], len, [])]
Known False -> Right []
Counted {} -> Left "MCDCSTS.guardRows: count is not closed" -- unreachable: 'openGuard' closes counts
Decision opened' -> do
rows <- MCDC.mcdcRows opened'
let trueRows = Set.fromList [ row | (row, True) <- rows ]
causes row = [ a | a <- Map.keys row, Map.adjust not a row `Set.member` trueRows ]
values row = [ (a, v) | a <- MCDC.atoms opened', v <- Foldable.toList (Map.lookup a row) ]
return [ (wrap (rowGuard row), value, if value then [] else causes row, len, values row) | (row, value) <- rows ]
{- |
Split a guard into its unique-cause MC/DC rows, for the given lengths of
the lists in the given gate parameters. The result is @(true rows, false rows)@.
E.g. @x > 1 || y > 1@ gives
> ([x > 1 && not (y > 1), not (x > 1) && y > 1], [not (x > 1) && not (y > 1)])
-}
splitGuard :: [Int] -> [Some Variable] -> SymGuard -> Either String ([SymGuard], [SymGuard])
splitGuard lengths params guard = do
rows <- guardRows lengths (Set.fromList params) Set.empty guard
return ([ row | (row, True, _, _, _) <- rows ], [ row | (row, False, _, _, _) <- rows ])
-- | The list lengths that 'completeMCDC' opens the list parameters for.
-- TODO: This is a temporary workaround. The correct thing would be to infere the possible lengths based
-- on the length guard (if existent) or other guards.
defaultListLengths :: [Int]
defaultListLengths = [0 .. 3]
-- | 'completeMCDCWith' for lists of the 'defaultListLengths'.
completeMCDC
:: (Ord loc, Show loc, Ord i, Show i, Ord o, Show o, BoundedMonad m, Foldable m,
MeetSemiLattice (m (STStdest, loc)))
=> STS m loc (IOAct i o) -> [i] -> IO (STS m loc (IOAct i o))
completeMCDC = completeMCDCWith defaultListLengths
-- | 'completeMCDCReportWith' without the report.
completeMCDCWith
:: (Ord loc, Show loc, Ord i, Show i, Ord o, Show o, BoundedMonad m, Foldable m,
MeetSemiLattice (m (STStdest, loc)))
=> [Int] -> STS m loc (IOAct i o) -> [i] -> IO (STS m loc (IOAct i o))
completeMCDCWith lengths aut inputGates = fst <$> completeMCDCReportWith SplitEverywhere lengths [] aut inputGates
-- | 'completeMCDCReportWith' for lists of the 'defaultListLengths'.
completeMCDCReport
:: (Ord loc, Show loc, Ord i, Show i, Ord o, Show o, BoundedMonad m, Foldable m,
MeetSemiLattice (m (STStdest, loc)))
=> STS m loc (IOAct i o) -> [i] -> IO (STS m loc (IOAct i o), MCDCReport)
completeMCDCReport = completeMCDCReportWith SplitEverywhere defaultListLengths []
-- | The locations at which 'completeMCDCReportWith' splits the switches of a guard.
data SplitMode
= SplitEverywhere -- ^ every location
| SplitInitial -- ^ the locations of the initial configuration only
deriving (Eq, Show)
-- | What happened to an MC/DC row of a guard.
data RowStatus
= Added -- ^ a true row: a switch is added for it
| NoSolution -- ^ no values satisfy the row; a true row still has its switch, but no test can take it
| Covered -- ^ a false row that is covered by the other switches on the gate
| NotCovered -- ^ a false row that is underspecified, so no test exercises it
| Skipped -- ^ a false row for atoms without a gate parameter: a test can not choose their value
deriving (Eq, Ord, Show)
-- | An MC/DC row of a guard.
data RowReport = RowReport
{ rowLength :: Maybe Int -- ^ the length of the lists, for a guard on list parameters
, rowValues :: [(SymGuard, Bool)] -- ^ the value of each atom, in the order of the guard
, rowOutcome :: Bool -- ^ the value of the guard on the row
, rowCauses :: [SymGuard] -- ^ for a false row, the atoms that it is the false row of an independence pair for
, rowStatus :: RowStatus
} deriving (Eq, Ord)
-- | The MC/DC rows of the guard of a switch. Switches with the same gate,
-- guard and rows are reported once.
data GuardReport = GuardReport
{ reportGate :: String
, reportGuard :: SymGuard
, reportSwitches :: [(String, String)] -- ^ the source and destination location of each split switch with this guard
, reportEmptyLengths :: [Int] -- ^ the list lengths for which the guard does not hold for any list
, reportRows :: [RowReport]
} deriving (Eq, Ord)
-- | The rows of all switches that 'completeMCDCReportWith' has split.
newtype MCDCReport = MCDCReport [GuardReport]
{- |
Show a report as one truth table per guard and list length, with a row per
MC/DC row and a column per atom, and a summary of the rows that have no
solution and the false rows that are not covered.
-}
prettyMCDCReport :: MCDCReport -> String
prettyMCDCReport (MCDCReport guards) = unlines $ concatMap prettyGuard guards ++ [summary]
where
names = [ "c" ++ show k | k <- [1 :: Int ..] ]
prettyGuard g =
[ "gate " ++ reportGate g ++ ", guard " ++ show (reportGuard g)
, " " ++ splitAt' (reportSwitches g) ++ " split into " ++ show (switchesFor g) ++ " switch(es)"
] ++
concatMap section (groupBy ((==) `on` rowLength) (reportRows g)) ++
[ " length " ++ show n ++ ": the guard does not hold for any list" | n <- reportEmptyLengths g ] ++
[ "" ]
section [] = []
section rows@(r : _) =
[ " length " ++ show n ++ ":" | Just n <- [rowLength r] ] ++
case map fst (rowValues r) of
[] -> [ " no conditions, the guard holds: " ++ status [] row | row <- rows ]
atoms ->
let named = zip names atoms
cell row (name, atom) = pad (length name) (maybe "-" truth (lookup atom (rowValues row)))
in [ " " ++ name ++ " = " ++ show atom | (name, atom) <- named ] ++
[ " " ++ unwords (map fst named) ++ " | out | status" ] ++
[ " " ++ unwords (map (cell row) named) ++ " | " ++ truth (rowOutcome row) ++ " | " ++ status named row
| row <- rows ]
-- the locations of a few switches, the number of many
splitAt' switches
| length switches <= 3 = "at " ++ intercalate ", " [ from ++ " -> " ++ to | (from, to) <- switches ] ++ ","
| otherwise = show (length switches) ++ " switch(es), each"
truth True = "T"
truth False = "F"
pad width s = s ++ replicate (width - length s) ' '
status named row = case rowStatus row of
Added -> "added"
NoSolution -> if rowOutcome row then "added, but no solution" else "no solution"
Covered -> "covered" ++ causes
NotCovered -> "NOT COVERED" ++ causes
Skipped -> "skipped, no gate parameter" ++ causes
where
causes = case [ name | (name, atom) <- named, atom `elem` rowCauses row ] of
[] -> ""
cs -> " (false row for " ++ intercalate ", " cs ++ ")"
-- a guard without true rows keeps one switch, that is never taken
switchesFor g = max 1 (length (filter rowOutcome (reportRows g)))
count s = length [ () | g <- guards, row <- reportRows g, rowStatus row == s ]
summary =
"summary: " ++ show (sum (map (length . reportSwitches) guards)) ++ " switch(es) split into " ++
show (sum [ length (reportSwitches g) * switchesFor g | g <- guards ]) ++ "; " ++
show (count NoSolution) ++ " row(s) without solution, " ++
show (count NotCovered) ++ " false row(s) not covered by any other switch, in " ++
show (length guards) ++ " distinct guard(s)"
{- |
Replace each switch on the given input gates by one switch per true row of
its guard. Each new switch keeps the assignment and the destination.
With 'SplitInitial', only the switches at the locations of the initial
configuration are split. The switches at the other locations are kept as
they are, and they are not in the report.
A guard on a list parameter of the gate is split once for each of the given
list lengths, with the atoms of each element of the list as separate atoms.
A list of another length is underspecified.
Limitations:
* Only lists that are gate parameters are opened.
* Only @forall@, @exists@, counts @length (filter x cond xs)@ and
@length xs@ are opened; any other condition on a list is one atom.
* A length or count is only recognised inside sums, products and
comparisons. A count may only be compared with constants and list
lengths, and an atom may have at most one count.
* Lists are only tested up to the longest given length
('defaultListLengths' is @[0 .. 3]@).
Use the result to steer test generation, not as a specification: values
that satisfy the original guard but are not an MCDC row become
underspecified.
The false rows of a guard should be covered by the other switches with the
same gate in the given location. A false row that is not covered is
underspecified, so no test exercises it; the report marks it as
'NotCovered'. Only the parameters of the gate can be controlled by a test,
so a false row is ignored if the atoms that it is a false row for have no
gate parameter.
The report has the rows of each split guard, including the rows that have
no solution.
The given domain guards restrict the values of a parameter to its domain,
such as the range of the elements of a list. A conjunct of a guard that
is a conjunct of a domain guard is a side condition: it holds on every
row and it has no atoms, so no row has a value outside the domain.
An error is raised if, at a reachable location,
* an atom occurs more than once in a guard,
* a guard other than the constant @True@ always holds, or
* two guards of the same location can hold at the same time.
Guards of different locations in a configuration may overlap.
-}
completeMCDCReportWith
:: (Ord loc, Show loc, Ord i, Show i, Ord o, Show o, BoundedMonad m, Foldable m,
MeetSemiLattice (m (STStdest, loc)))
=> SplitMode -> [Int] -> [SymGuard] -> STS m loc (IOAct i o) -> [i] -> IO (STS m loc (IOAct i o), MCDCReport)
completeMCDCReportWith mode lengths domainGuards aut inputGates = do
-- the same guards and rows occur at several locations, so each of them is solved once
solved <- newIORef Map.empty
let satisfiable guard = do
known <- Map.lookup guard <$> readIORef solved
case known of
Just result -> return result
Nothing -> do
result <- isGuardSatisfiable (Set.toList (freeVars guard)) guard
modifyIORef' solved (Map.insert guard result)
return result
configs = Set.toList (reachableConfigs aut)
selectedGates =
[ (loc, gate, mval) | loc <- Set.toList (Set.unions configs), (gate, mval) <- Map.toList (transRel aut loc)
, selected gate ]
initLocs = Set.fromList (Foldable.toList (initConf aut))
isSplit loc = case mode of
SplitEverywhere -> True
SplitInitial -> loc `Set.member` initLocs
-- check all selected gates first, then split
unsolvable <- forM selectedGates $ \(loc, gate, mval) -> do
rows <- checkGate satisfiable (rowsOf gate) loc gate (guards mval)
return ((loc, gate), rows)
-- per location and gate, the guards of that gate elsewhere in a configuration; equal checks are done once
let elsewhereIn config loc gate =
[ guard | loc' <- Set.toList config, loc' /= loc, mval <- Foldable.toList (Map.lookup gate (transRel aut loc'))
, guard <- guards mval ]
coverChecks = Map.fromList
[ ((loc, gate, Set.fromList (elsewhereIn config loc gate)), config)
| config <- configs, loc <- Set.toList config, gate <- Map.keys (transRel aut loc), selected gate ]
uncovered <- forM (Map.keys coverChecks) $ \(loc, gate, elsewhere) -> do
rows <- checkCovered satisfiable (rowsOf gate) domain (params gate)
(guards (transRel aut loc Map.! gate)) (Set.toList elsewhere)
return ((loc, gate), rows)
let unsolvableAt = Map.fromList unsolvable
-- a false row is not covered if it is not covered in one of the configurations of the location
uncoveredAt = Map.fromListWith (zipWith Set.union) uncovered
rowsAt rows key = Map.findWithDefault (repeat Set.empty) key rows
-- split switches with the same gate, guard and rows are reported once, with all their locations
reports = Map.fromListWith (flip (++))
[ (GuardReport (show gate) guard [] (emptyLengths gate guard rows)
(zipWith (rowReport (Set.fromList (params gate)) noSolution notCovered) [0 ..] rows), [(show loc, show dest)])
| (loc, gate, mval) <- selectedGates
, isSplit loc
, ((guard, dest), noSolution, notCovered) <-
zip3 (switches mval) (rowsAt unsolvableAt (loc, gate)) (rowsAt uncoveredAt (loc, gate))
, Right rows <- [rowsOf gate guard] ]
report = MCDCReport [ guard { reportSwitches = at } | (guard, at) <- Map.toList reports ]
return (automaton (initConf aut) (alphabet aut) (\loc -> Map.mapWithKey (splitGate (isSplit loc)) (transRel aut loc)), report)
where
selected (SymInteract (In i) _) = i `elem` inputGates
selected _ = False
params (SymInteract _ vars) = vars
domain = domainConjuncts domainGuards
rowsOf gate = guardRows lengths (Set.fromList (params gate)) domain
switches mval = [ (guard, dest) | (STSLoc (guard, _), dest) <- Foldable.toList mval ]
guards = map fst . switches
-- the lengths of an opened guard that have no rows
emptyLengths gate guard rows
| Set.null (openLists (Set.fromList (params gate)) (view guard)) = []
| otherwise = [ n | n <- lengths, Just n `notElem` [ len | (_, _, _, len, _) <- rows ] ]
splitGate split gate mval
| split && selected gate = mval `ordBind` splitSwitch gate
| otherwise = mval
splitSwitch gate (STSLoc (guard, assign'), destLoc) = case rowsOf gate guard of
Right rows -> case [ row | (row, True, _, _, _) <- rows ] of
[] -> ordReturn (stsTLoc sFalse assign', destLoc) -- the guard does not hold for any list of the given lengths
trueRows -> foldr1 (/\) [ ordReturn (stsTLoc row assign', destLoc) | row <- trueRows ]
Left err -> errorWithoutStackTrace $ "completeMCDC: " ++ err -- unreachable after 'checkGate'
{- |
The location configurations that are syntactically reachable from the
initial configuration, each as the set of its locations. The successor of a
configuration for a transition label is the set of all destinations of that
label from its locations.
Like 'reachable', this does not interpret the automaton: guards are ignored,
and so is the lattice structure of a configuration. A configuration may thus
contain locations that never occur together.
-}
reachableConfigs :: (Ord loc, Ord t, Foldable m) => AutSyntax m loc t tdest -> Set.Set (Set.Set loc)
reachableConfigs aut = explore Set.empty [Set.fromList (Foldable.toList (initConf aut))]
where
explore seen [] = seen
explore seen (config : todo)
| Set.null config || config `Set.member` seen = explore seen todo
| otherwise = explore (Set.insert config seen) (Map.elems (configSuccessors aut config) ++ todo)
-- | The successor of a configuration for each transition label.
configSuccessors :: (Ord loc, Ord t, Foldable m) => AutSyntax m loc t tdest -> Set.Set loc -> Map.Map t (Set.Set loc)
configSuccessors aut config = Map.unionsWith Set.union
[ Map.map (Set.fromList . map snd . Foldable.toList) (transRel aut loc) | loc <- Set.toList config ]
-- | The report of the row with the given index, given the indices of the rows
-- of its guard that have no solution and of those that are not covered.
rowReport :: Set.Set (Some Variable) -> Set.Set Int -> Set.Set Int -> Int -> GuardRow -> RowReport
rowReport params noSolution notCovered k (_, outcome, causes, len, values) =
RowReport len [ (Expr a, v) | (a, v) <- values ] outcome (map Expr causes) status
where
status
| k `Set.member` noSolution = NoSolution
| outcome = Added
| not (controllable params causes) = Skipped
| k `Set.member` notCovered = NotCovered
| otherwise = Covered
-- | True if a test can choose the value of one of the atoms that a false row
-- is a false row for: the atom has one of the given gate parameters.
controllable :: Set.Set (Some Variable) -> [ExprView Bool] -> Bool
controllable params causes = null causes || any hasParam causes
where
hasParam a = not $ Set.null $ freeVars (Expr a) `Set.intersection` params
-- | Check the guards of one gate at one location, apart from the coverage of
-- their false rows. The result is, per guard, the indices of its rows that
-- have no solution.
checkGate :: (Show loc, Show gate)
=> (SymGuard -> IO Bool) -> (SymGuard -> Either String [GuardRow]) -> loc -> gate -> [SymGuard]
-> IO [Set.Set Int]
checkGate satisfiable rowsOf loc gate guards = do
-- a guard that always holds has no false outcome, so no atom of it can have an independence pair
forM_ indexed $ \(i, guard) -> when (view guard /= Const True) $ do
falsifiable <- satisfiable (sNot guard)
unless falsifiable $ failWith $
"guard #" ++ show i ++ " (" ++ show guard ++ ") is a tautology, so it can not have MC/DC coverage"
-- the guards must be pairwise disjoint
forM_ pairs $ \((i, gi), (j, gj)) -> do
overlap <- satisfiable (gi .&& gj)
when overlap $ failWith $
"guard #" ++ show i ++ " (" ++ show gi ++ ") and guard #" ++ show j ++ " (" ++ show gj ++
") are not disjoint"
forM indexed $ \(i, guard) -> case rowsOf guard of
Left err -> failWith $ "guard #" ++ show i ++ " (" ++ show guard ++ "): " ++ err
Right rows -> do
unsolvable <- filterM (fmap not . satisfiable . snd) (zip [0 :: Int ..] [ row | (row, _, _, _, _) <- rows ])
return (Set.fromList (map fst unsolvable))
where
indexed = zip [0 :: Int ..] guards
pairs = [ (a, b) | a@(i, _) <- indexed, b@(j, _) <- indexed, i < j ]
failWith :: String -> IO a
failWith msg = errorWithoutStackTrace $ context ++ msg
context = "completeMCDC: at location " ++ show loc ++ ", gate " ++ show gate ++ ": "
{- |
The false rows of the guards of one gate at one location that are not
covered: neither by the other guards at that location, nor by the given
guards of that gate elsewhere in the location configuration. The result
is, per guard, the indices of these rows.
A false row is skipped if none of the atoms that it is a false row for has
one of the given gate parameters: its atoms depend on the location variables
only, so a test can not choose their value.
-}
checkCovered :: (SymGuard -> IO Bool) -> (SymGuard -> Either String [GuardRow]) -> Set.Set (ExprView Bool)
-> [Some Variable] -> [SymGuard] -> [SymGuard] -> IO [Set.Set Int]
checkCovered satisfiable rowsOf domain params guards elsewhere =
forM indexed $ \(i, guard) -> case rowsOf guard of
Left _ -> return Set.empty -- unreachable after 'checkGate'
Right rows -> do
let others = [ g | (j, g) <- indexed, j /= i ] ++ elsewhere
lists = openLists paramSet (view guard)
-- on a row for lists of some length, the other guards are compared as they are on lists of that length
othersAt len = map (maybe id (\n -> guardAtLength n paramSet domain lists) len) others
outsideOthers (row, _, len)
| null others = row
| otherwise = row .&& sNot (foldl1 (.||) (othersAt len))
falseRows = [ (k, (row, causes, len)) | (k, (row, False, causes, len, _)) <- zip [0 :: Int ..] rows
, controllable paramSet causes ]
uncovered <- filterM (satisfiable . outsideOthers . snd) falseRows
return (Set.fromList (map fst uncovered))
where
indexed = zip [0 :: Int ..] guards
paramSet = Set.fromList params