packages feed

lattest-lib-0.2: test/Test/Lattest/Model/Symbolic/Expr.hs

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE FlexibleContexts #-}

module Test.Lattest.Model.Symbolic.Expr (
prop_evalSymbolic,
PropEvalSymbolic,
prop_solveSymbolic,
evalTests,
solveTests,
testQuantifiers,
propShowReadType
)
where

import Lattest.Model.Symbolic.Internal.FreeMonoidX as FM
import Lattest.Model.Symbolic.Expr
import Lattest.Model.Symbolic.SolveSymPrim

import qualified Data.Set as Set
import qualified Debug.Trace as Trace
import qualified Control.Monad as CM
import Test.HUnit
import Test.QuickCheck hiding (Some(..))
import Test.QuickCheck.Monadic
import Data.Constraint.Extras (Has(..))
import Lattest.Model.Symbolic.Internal.ExprDefs (Expr (..))
import qualified Data.Dependent.Map as DMap
import Data.Some (Some (..))
import Data.Maybe (isJust)
import Data.GADT.Compare (GEq(..))
import Data.GADT.Show (gread)
import qualified Data.Maybe as Maybe



class ConcreteGenExpr t where
    genExpr :: Int -> Gen (ExprView t)
    shrinkConst :: t -> [t]

instance ConcreteGenExpr Integer where
    genExpr n | n <= 0 = oneof [
        arbitraryVar IntType,
        CM.liftM Const arbitrary
        ]
    genExpr n = oneof [
        arbitraryVar IntType,
        CM.liftM Const arbitrary,
        CM.liftM3 Ite subexpr3 subexpr3 subexpr3,
        CM.liftM2 Divide subexpr2 subexpr2,
        CM.liftM2 Modulo subexpr2 subexpr2,
        CM.liftM (Sum IntType) (FM.fromListT <$> genList subexpr2),
        CM.liftM (Product IntType) (FM.fromListT <$> genList subexprSqrt)
        ]
        where
        subexpr :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr = genExpr (n - 1)
        subexpr2 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr2 = genExpr $ (n `div` 2) - 1
        subexpr3 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr3 = genExpr $ (n `div` 3) - 1
        subexprSqrt :: ConcreteGenExpr t => Gen (ExprView t)
        subexprSqrt = genExpr (intSqrt n - 1)
    shrinkConst = shrink

instance ConcreteGenExpr Bool where
    genExpr n | n <= 0 = oneof [
        arbitraryVar BoolType,
        CM.liftM Const arbitrary
        ]
    genExpr n = oneof [
        arbitraryVar BoolType,
        CM.liftM Const arbitrary,
        CM.liftM3 Ite subexpr3 subexpr3 subexpr3,
        CM.liftM2 (Equal IntType) subexpr2 subexpr2,
        CM.liftM2 (Equal BoolType) subexpr2 subexpr2,
        CM.liftM2 (Equal CharType) subexpr2 subexpr2,
        CM.liftM (Gez @Integer) subexpr,
        CM.liftM Not subexpr,
        CM.liftM And (Set.fromList <$> genList subexprSqrt)
        ]
        where
        subexpr :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr = genExpr (n - 1)
        subexpr2 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr2 = genExpr $ (n `div` 2) - 1
        subexpr3 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr3 = genExpr $ (n `div` 3) - 1
        subexprSqrt :: ConcreteGenExpr t => Gen (ExprView t)
        subexprSqrt = genExpr (intSqrt n - 1)
    shrinkConst = shrink

instance ConcreteGenExpr Char where
    genExpr n | n <= 0 = oneof [
        arbitraryVar CharType,
        CM.liftM Const arbitrary
        ]
    genExpr n = oneof [
        arbitraryVar CharType,
        CM.liftM Const arbitrary,
        CM.liftM3 Ite subexpr3 subexpr3 subexpr3
        ]
        where
        subexpr :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr = genExpr (n - 1)
        subexpr2 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr2 = genExpr $ (n `div` 2) - 1
        subexpr3 :: ConcreteGenExpr t => Gen (ExprView t)
        subexpr3 = genExpr $ (n `div` 3) - 1
        subexprSqrt :: ConcreteGenExpr t => Gen (ExprView t)
        subexprSqrt = genExpr (intSqrt n - 1)
    shrinkConst = shrink

charExpr :: Gen Char
charExpr = elements $ ['A'..'Z'] ++ ['a'..'z']
stringExpr :: Gen String
stringExpr = CM.liftM2 (++) (return <$> charExpr) (genList charExpr)

-- generate lists, more conservatively than with listOf, in order to avoid exponential blowup
genList :: Gen a -> Gen [a]
genList g = sized $ \n -> do
    _ <- choose (0, intSqrt n - 1)
    CM.replicateM (intSqrt n) g

intSqrt :: Int -> Int
intSqrt = floor . (sqrt :: Double -> Double) . fromIntegral


arbitraryVar :: Type t -> Gen (ExprView t)
arbitraryVar t =
    let prefix :: Type a -> String
        prefix tp = case tp of
                    IntType -> "i"
                    FloatType -> "f"
                    BoolType -> "b"
                    CharType -> "c"
                    ListType x -> "[" ++ prefix x ++ "]"
                    TupleType x y -> "(" ++ prefix x ++ "," ++ prefix y ++ ")"
                    SumType x y -> "<" ++ prefix x ++ "," ++ prefix y ++ ">"
    in CM.liftM (\n -> Var $ Variable (prefix t++n) t) (return <$> charExpr)

type PropEvalSymbolic t = Expr t -> Bool

-- If you squint a bit, this is really just two interpreters (`concreteEval'` defined below, and `reduce` defined in lattest-lib),
-- that are defined almost identically, and then a check whether they give the same result.
-- Does it really give us anything? Is it worth maintaining two interpreters?
--  - A person who did not feel like updating this interpreter after a large update to Expr
prop_evalSymbolic :: (Eq t, ConcreteEval t) => Expr t -> Bool
prop_evalSymbolic e =
    let l = concreteEval e
        r = symbolicEval e
    --in if l == r then True else Trace.trace ("concrete eval: " ++ show l ++ "\nsymbolic eval: " ++ show r ++ "\n") False
    in l == r

symbolicEval :: Expr t -> Maybe t
symbolicEval = rightToMaybe . eval
    where
    rightToMaybe :: Either a b -> Maybe b
    rightToMaybe (Left _) = Nothing
    rightToMaybe (Right b) = Just b

prop_solveSymbolic :: Expr Bool -> Property
prop_solveSymbolic guard = monadicIO $ do
    mValuation <- run $ solveGuardIO (Set.toList $ freeVars guard) guard
    case mValuation of
        Nothing -> return ()
        Just valuation ->
            let val = substConst valuation guard
            in case concreteEval val of
                Nothing -> return () -- we may generate an expression which can have an undefined value, e.g. division by zero, for which the SMT solver may pick an arbitrary valuation
                Just sat -> Trace.trace ("[" ++ show valuation ++ "]" ++ show guard) $ assertWith sat ("Substituting solved value doesn't yield True for [" ++ show valuation ++ "] " ++ show guard)

concreteEval :: ConcreteEval t => Expr t -> Maybe t
concreteEval = concreteEval' . view

class ConcreteEval t where
    concreteEval' :: ExprView t -> Maybe t

instance ConcreteEval Integer where
    concreteEval' (Var _) = Nothing
    concreteEval' (Const c) = Just c
    concreteEval' (First _ x) = fst <$> concreteEval' x
    concreteEval' (Second _ x) = snd <$> concreteEval' x
    concreteEval' (Head xs) = head <$> concreteEval' xs
    concreteEval' (Either a b c d e) = concreteEither a b c d e
    concreteEval' (Ite i t e) = concreteIfThenElse i t e
    concreteEval' (Divide e1 e2) = concreteBinOpMaybe (safeZero div) e1 e2
    concreteEval' (Modulo e1 e2) = concreteBinOpMaybe (safeZero mod) e1 e2
    concreteEval' (Length _ e) = concreteUnaryOp (Prelude.toInteger . length) e
    concreteEval' (Sum _ es)   = foldOccur (\(concreteEval' . unwrap -> x) i y -> (+) <$> y <*> ((* i) <$> x)) (Just 0) es
    concreteEval' (Product _ es) = foldOccur (\(concreteEval' . unwrap -> x) i y -> (*) <$> y <*> ((^ i) <$> x)) (Just 0) es

instance ConcreteEval Double where
    concreteEval' (Var _) = Nothing
    concreteEval' (Const c) = Just c
    concreteEval' (First _ x) = fst <$> concreteEval' x
    concreteEval' (Second _ x) = snd <$> concreteEval' x
    concreteEval' (Head xs) = head <$> concreteEval' xs
    concreteEval' (Either a b c d e) = concreteEither a b c d e
    concreteEval' (Ite i t e) = concreteIfThenElse i t e
    concreteEval' (DivideFloat e1 e2) = concreteBinOpMaybe (safeZero (/)) e1 e2

safeZero :: (Num a, Eq a) => (a -> a -> a) -> (a -> a -> Maybe a)
safeZero _ _ 0 = Nothing
safeZero op n m = Just $ n `op` m


instance ConcreteEval Bool where
    concreteEval' (Var _) = Nothing
    concreteEval' (Const c) = Just c
    concreteEval' (First _ x) = fst <$> concreteEval' x
    concreteEval' (Second _ x) = snd <$> concreteEval' x
    concreteEval' (Head xs) = head <$> concreteEval' xs
    concreteEval' (Either a b c d e) = concreteEither a b c d e
    concreteEval' (Ite i t e) = concreteIfThenElse i t e
    concreteEval' (Equal t e1 e2) = has @ConcreteEval t $ concreteBinOp (==) e1 e2
    concreteEval' (Gez e) = withExprConstraints e $ concreteUnaryOp (>= 0) e
    concreteEval' (Not e) = concreteUnaryOp not e
    concreteEval' (And es) = and <$> mapM concreteEval' (Set.toList es)
    concreteEval' (LElem t x xs) = has @ConcreteEval t $ (\y ys -> has @Eq t $ y `elem` ys) <$> concreteEval' x <*> concreteEval' xs

instance ConcreteEval Char where
  concreteEval' (Var _) = Nothing
  concreteEval' (Const c) = Just c
  concreteEval' (First _ x) = fst <$> concreteEval' x
  concreteEval' (Second _ x) = snd <$> concreteEval' x
  concreteEval' (Head xs) = head <$> concreteEval' xs
  concreteEval' (Either a b c d e) = concreteEither a b c d e
  concreteEval' (Ite i t e) = concreteIfThenElse i t e

instance ConcreteEval [a] where
  concreteEval' = \case
    Var _ -> Nothing
    Const c -> Just c
    First _ x -> fst <$> concreteEval' x
    Second _ x -> snd <$> concreteEval' x
    Either a b c d e -> concreteEither a b c d e
    Head xs -> head <$> concreteEval' xs
    Concat xs -> concat <$> concreteEval' xs
    Tail xs -> tail <$> concreteEval' xs
    Take i xs -> take . fromInteger <$> concreteEval' i <*> concreteEval' xs
    Drop i xs -> drop . fromInteger <$> concreteEval' i <*> concreteEval' xs
    Ite i t e -> concreteIfThenElse i t e
    Cons x xs -> has @ExprType x $ has @ConcreteEval (typeOf' x) $ (:) <$> concreteEval' x <*> concreteEval' xs
    Append x y -> (++) <$> concreteEval' x <*> concreteEval' y
    Map v f xs -> has @ExprType f $ has @ConcreteEval (typeOf' f) $ do
      ys <- concreteEval' xs
      traverse (\y -> concreteEval' $ view $ subst (VarModel $ DMap.singleton v $ Expr $ Const y) $ Expr f) ys

instance ConcreteEval (a,b) where
  concreteEval' = \case
    Var _ -> Nothing
    Const c -> Just c
    First _ x -> fst <$> concreteEval' x
    Second _ x -> snd <$> concreteEval' x
    Head xs -> head <$> concreteEval' xs
    Either a b c d e -> concreteEither a b c d e
    Ite i t e -> concreteIfThenElse i t e
    Pair a b -> has @ExprType a $ has @ExprType b $ has @ConcreteEval (typeOf' a) $ has @ConcreteEval (typeOf' b) $ (,) <$> concreteEval' a <*> concreteEval' b
instance ConcreteEval (Either a b) where
  concreteEval' = \case
    Var _ -> Nothing
    Const c -> Just c
    First _ x -> fst <$> concreteEval' x
    Head xs -> head <$> concreteEval' xs
    Second _ x -> snd <$> concreteEval' x
    Either a b c d e -> concreteEither a b c d e
    Ite i t e -> concreteIfThenElse i t e
    ELeft x -> has @ExprType x $ has @ConcreteEval (typeOf' x) $ Left <$> concreteEval' x
    ERight x -> has @ExprType x $ has @ConcreteEval (typeOf' x) $ Right <$> concreteEval' x

instance Has ConcreteEval Type where
  has tp k = case tp of
    IntType -> k
    FloatType -> k
    CharType -> k
    BoolType -> k
    ListType _ -> k
    TupleType _ _ -> k
    SumType _ _ -> k

concreteUnaryOp :: (t1 -> t2) -> ExprView t1 -> Maybe t2
concreteUnaryOp op e = has @ExprType e $ has @ConcreteEval (typeOf' e) $ do
    x <- concreteEval' e
    return $ op x

concreteBinOp :: (ConcreteEval t1, ConcreteEval t2) => (t1 -> t2 -> t3) -> ExprView t1 -> ExprView t2 -> Maybe t3
concreteBinOp binop e1 e2 = do
    x <- concreteEval' e1
    y <- concreteEval' e2
    return $ x `binop` y

concreteBinOpMaybe :: (ConcreteEval t1, ConcreteEval t2) => (t1 -> t2 -> Maybe t3) -> ExprView t1 -> ExprView t2 -> Maybe t3
concreteBinOpMaybe binop e1 e2 = do
    x <- concreteEval' e1
    y <- concreteEval' e2
    x `binop` y

concreteIfThenElse :: (ConcreteEval t) => ExprView Bool -> ExprView t -> ExprView t -> Maybe t
concreteIfThenElse i t e = do
    cond <- concreteEval' i
    if cond
        then concreteEval' t
        else concreteEval' e

concreteEither :: (ConcreteEval t) => Variable a -> Variable b -> ExprView t -> ExprView t -> ExprView (Either a b) -> Maybe t
concreteEither vl vr l r x = has @ExprType x $ case typeOf' x of
  SumType ta tb -> case concreteEval' x of
    Nothing -> Nothing
    Just (Left y) -> concreteEval' $ view $ subst (VarModel $ DMap.singleton vl $ Expr $ withExprConstraints ta Const y) $ Expr l
    Just (Right y) -> concreteEval' $ view $ subst (VarModel $ DMap.singleton vr $ Expr $ withExprConstraints tb Const y) $ Expr r

evalTests :: [Test]
evalTests = [testEvalEmptyProduct, testEvalNegativeModulo]

testQuantifiers :: [Test]
testQuantifiers =
  [ mkTest (sExists v $ sVar v .>= 3 .&& sVar v `sElem` sConst [1,2,5,2,3] , Maybe.isJust)
  , mkTest (sExists v $ sVar v .>= 3 .&& sVar v `sElem` sConst [1,2,1,2,0] , Maybe.isNothing)
  , mkTest (sForall v $ sVar v .>= 3, Maybe.isNothing)
  , mkTest (sForall w $ sVar w .== sTrue .|| sVar w .== sFalse, Maybe.isJust)
  , mkTest (sForall v $ sVar v .>= 4 .|| sVar v .< 8, Maybe.isJust)
  ]
  where
    v = Variable "foo" IntType
    w = Variable "foo" BoolType
    mkTest :: (Expr Bool, Maybe Valuation -> Bool) -> Test
    mkTest (expr, predicate) = TestCase $ do
      x <- solveGuardIO [] expr
      Test.HUnit.assert $ predicate x

solveTests :: [Test]
solveTests = [testSolveNegativeModulo]

testEvalExpression :: (Eq a, Show a, ConcreteEval a) => Expr a -> String -> Test
testEvalExpression e msg = TestCase $ assertEqual msg (concreteEval e) (symbolicEval e)

testEvalEmptyProduct :: Test
testEvalEmptyProduct = testEvalExpression (sProduct @Integer []) "empty product evaluation incorrect"

testSolveExpression :: Expr Bool -> Test
testSolveExpression guard = TestCase $ do
    mValuation <- solveGuardIO (Set.toList $ freeVars guard) guard
    case mValuation of
        Nothing -> return ()
        Just valuation ->
            let val = substConst valuation guard
            in CM.forM_ (concreteEval val)
                $ \sat -> assertBool ("Substituting solved value doesn't yield True for [" ++ show valuation ++ "] " ++ show guard) sat

testEvalNegativeModulo :: Test
testEvalNegativeModulo = testEvalExpression ((-2) .% (-2)) "negative mod evaluates incorrectly"

testSolveNegativeModulo :: Test
testSolveNegativeModulo = testSolveExpression ((-2) .% (-2) .== sVar (Variable "ix" IntType))

newtype SomeType = ST (Some Type) deriving Show
instance Arbitrary SomeType where
  arbitrary = oneof
    [ return . ST $ Some IntType
    , return . ST $ Some FloatType
    , return . ST $ Some RationalType
    , return . ST $ Some BoolType
    , return . ST $ Some UnitType
    , return . ST $ Some CharType
    , (\(ST (Some t)) -> ST (Some $ ListType t)) <$> arbitrary
    , (\(ST (Some a)) (ST (Some b)) -> ST (Some $ SumType   a b)) <$> arbitrary <*> arbitrary
    , (\(ST (Some a)) (ST (Some b)) -> ST (Some $ TupleType a b)) <$> arbitrary <*> arbitrary
    ]

propShowReadType :: SomeType -> Bool
propShowReadType (ST (Some t)) = gread (withExprConstraints t $ show t) $ \t' -> isJust $ geq t t'