packages feed

lattest-lib-0.2: src/Lattest/Model/Symbolic/Internal/ExprDefs.hs

{-# OPTIONS_HADDOCK hide, prune #-}
{-
This is a modified version of:
TorXakis - Model Based Testing
See LICENSE in the parent Symbolic folder.
-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE EmptyDataDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeApplications   #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE ViewPatterns #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}
{- HLINT ignore "Use typeRep" -}

module Lattest.Model.Symbolic.Internal.ExprDefs
( ExprView(..)
, Expr(..)       -- for local usage only!
, Variable(..)
, Type(..)
, Constant(..)
, constType
, fromConst
, ExprType
, typeOf
, typeOf'
, isConst
, freeVars
, freeVars'
, ExprConstraints
, withExprConstraints
, withExprNumConstraint
, int
, unit
, float
, rational
, real
, bool
, char
, string
, list
, tuple
, option
, enumIndex
, prettyValue
, prettyConstant
)
where

import qualified Data.List as List
import           Data.Set         (Set)
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe
import qualified Data.Text as Text(pack, unpack)

import           Lattest.Model.Symbolic.Internal.FreeMonoidX
import           Lattest.Model.Symbolic.Internal.Product
import           Lattest.Model.Symbolic.Internal.Sum

import qualified Data.Aeson as JSON
import qualified Data.Aeson.KeyMap as JSON

import Data.Scientific (fromFloatDigits)
import qualified Data.Scientific as DS
import qualified Data.Some.Church as Church
import Data.Some (Some(..))
import Data.GADT.Compare (GEq(..), GOrdering (..), GCompare (..))
import Data.Type.Equality ((:~:)(..))
import Data.GADT.Show (GRead (..), GShow (..), defaultGshowsPrec)
import Data.SBV (SymVal(..), SBV, OrdSymbolic (..), sFalse, SBool, sNot, (.&&), AlgReal)
import Data.EqP (EqP (..))
import Data.Maybe (isJust, maybeToList)
import Data.Constraint.Extras (Has (..))
import Data.Constraint.Compose (ComposeC)
import qualified Data.Vector as Vec
import Data.String (IsString(..))
import Control.Monad ((<=<))
import Data.Data (Data)
import Data.Bifunctor (Bifunctor(..))
import qualified Data.Aeson.Types as JSON
import Data.List (stripPrefix)

data Type a where
  IntType :: Type Integer
  FloatType :: Type Double
  RationalType :: Type Rational
  RealType :: Type AlgReal
  BoolType :: Type Bool
  CharType :: Type Char
  UnitType :: Type ()
  ListType :: Type a -> Type [a]
  TupleType :: Type a -> Type b -> Type (a,b)
  SumType :: Type a -> Type b -> Type (Either a b)

deriving instance Eq (Type a)
deriving instance Ord (Type a)
instance EqP Type where
  eqp x y = isJust $ geq x y
instance GEq Type where
  geq IntType IntType = Just Refl
  geq FloatType FloatType = Just Refl
  geq RationalType RationalType = Just Refl
  geq RealType RealType = Just Refl
  geq BoolType BoolType = Just Refl
  geq CharType CharType = Just Refl
  geq UnitType UnitType = Just Refl
  geq (ListType a) (ListType b) = (\Refl -> Refl) <$> geq a b
  geq (TupleType a b) (TupleType x y) = (\Refl Refl -> Refl) <$> geq a x <*> geq b y
  geq (SumType a b) (SumType x y) = (\Refl Refl -> Refl) <$> geq a x <*> geq b y
  geq _ _ = Nothing
instance GCompare Type where
  gcompare a b = case (a, b) of
    (ListType a', ListType b')   -> case gcompare a' b' of
      GLT -> GLT
      GEQ -> GEQ
      GGT -> GGT
    (TupleType a1 b1, TupleType a2 b2) -> case gcompare a1 a2 of
      GLT -> GLT
      GEQ -> case gcompare b1 b2 of
        GLT -> GLT
        GEQ -> GEQ
        GGT -> GGT
      GGT -> GGT
    (SumType a1 b1, SumType a2 b2) -> case gcompare a1 a2 of
      GLT -> GLT
      GEQ -> case gcompare b1 b2 of
        GLT -> GLT
        GEQ -> GEQ
        GGT -> GGT
      GGT -> GGT
    _ -> case compare (typeTag a) (typeTag b) of
        LT -> GLT
        EQ -> case a `geq` b of
          Just Refl -> GEQ
          Nothing -> error "tags match but geq doesn't; forgot to add a new type to gcompare or geq?"
        GT -> GGT
    where
      -- NOTE: when adding a new recursive case below, make sure to add it above too!
      typeTag :: Type a -> Int
      typeTag IntType    = 0
      typeTag FloatType  = 1
      typeTag BoolType   = 2
      typeTag CharType   = 3
      typeTag UnitType   = 4
      typeTag (ListType _)   = 5
      typeTag (TupleType _ _) = 7
      typeTag (SumType _ _)   = 8
      typeTag RationalType = 9
      typeTag RealType = 10

instance Show (Type a) where
    show IntType = "Int"
    show UnitType = "()"
    show BoolType = "Bool"
    show CharType = "Char"
    show FloatType = "Float"
    show RationalType = "Rational"
    show RealType = "Real"
    show (ListType t) = "[" ++ show t ++ "]"
    show (TupleType a b) = "(" ++ show a ++ ", " ++ show b ++ ")"
    show (SumType a b) = "<" ++ show a ++ ", " ++ show b ++ ">"
instance GShow Type where
  gshowsPrec = defaultGshowsPrec

instance ExprType a => Read (Type a) where
  readsPrec _ =
    readParen False $ \s ->
      let tp = typeOf (undefined :: a)
          target = show tp
          len = length target
          (test, rest) = splitAt len s
      in ([(tp, rest) | test == target])
instance GRead Type where
  greadsPrec _ =
    readParen False $ \s ->
         [ (Church.mkSome CharType, rest)
         | rest <- mylex "Char" s
         ]
      ++ [ (Church.mkSome IntType, rest)
         | rest <- mylex "Int" s
         ]
      ++ [ (Church.mkSome FloatType, rest)
         | rest <- mylex "Float" s
         ]
      ++ [ (Church.mkSome RationalType, rest)
         | rest <- mylex "Rational" s
         ]
      ++ [ (Church.mkSome RealType, rest)
         | rest <- mylex "Real" s
         ]
      ++ [ (Church.mkSome BoolType, rest)
         | rest <- mylex "Bool" s
         ]
      ++ [ (Church.mkSome UnitType, rest)
         | rest <- mylex "()" s
         ]
      ++ do
          s1 <- mylex "[" s
          (t, s2) <- greadsPrec 11 s1
          rest <- mylex "]" s2
          Church.withSome t $ \(tp :: Type t) ->
            return (Church.mkSome $ ListType tp, rest)
      ++ do
          s1 <- mylex "(" s
          (a, s2) <- greadsPrec 11 s1
          s3 <- mylex ", " s2
          (b, s4) <- greadsPrec 11 s3
          rest <- mylex ")" s4
          Church.withSome a $ \(ta :: Type a) ->
            Church.withSome b $ \(tb :: Type b) ->
              return (Church.mkSome $ TupleType ta tb, rest)
      ++ do
          s1 <- mylex "<" s
          (a, s2) <- greadsPrec 11 s1
          s3 <- mylex ", " s2
          (b, s4) <- greadsPrec 11 s3
          rest <- mylex ">" s4
          Church.withSome a $ \(ta :: Type a) ->
            Church.withSome b $ \(tb :: Type b) ->
              return (Church.mkSome $ SumType ta tb, rest)
    where
      mylex prefix = maybeToList . stripPrefix prefix

withExprConstraints :: Has ExprType f => f a -> (ExprConstraints a => r) -> r
withExprConstraints f k = let t = has @ExprType f (typeOf' f) in has @Data t $ has @Read t $ has @Ord t $ has @Show t $ has @ExprType t $ has @SymVal t $ has @Eq t $ hasOrdSymbolic t k

withExprNumConstraint :: (Has ExprType f, Num a) => f a -> (Num (SBV a) => r) -> r
withExprNumConstraint f k = case has @ExprType f (typeOf' f) of
  IntType -> k
  FloatType -> k
  RationalType -> k
  RealType -> k
  _ -> error "impossible Num instance"

instance Has ExprType Type where
  has t k = case t of
    IntType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    UnitType -> k
    CharType -> k
    ListType t' -> has @ExprType t' k
    TupleType a b -> has @ExprType a $ has @ExprType b k
    SumType a b -> has @ExprType a $ has @ExprType b k

instance Has Eq Type where
  has t k = case t of
    IntType -> k
    UnitType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    CharType -> k
    ListType t' -> has @Eq t' k
    TupleType a b -> has @Eq a $ has @Eq b k
    SumType a b -> has @Eq a $ has @Eq b k

instance Has Ord Type where
  has t k = case t of
    IntType -> k
    UnitType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    CharType -> k
    ListType t' -> has @Ord t' k
    TupleType a b -> has @Ord a $ has @Ord b k
    SumType a b -> has @Ord a $ has @Ord b k

hasOrdSymbolic :: Type a -> (OrdSymbolic (SBV a) => r) -> r
hasOrdSymbolic t k = case t of
  IntType -> k
  FloatType -> k
  RationalType -> k
  RealType -> k
  CharType -> k
  UnitType -> k
  BoolType -> k
  ListType t' -> has @SymVal t' k
  TupleType a b -> has @SymVal a $ has @SymVal b k
  SumType a b -> has @SymVal a $ has @SymVal b $ hasOrdSymbolic a $ hasOrdSymbolic b k
instance OrdSymbolic (SBV ()) where
  (.<) _ _ = sFalse
instance OrdSymbolic SBool where
  x .< y = y .&& sNot x

instance Has Show Type where
  has t k = case t of
    IntType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    UnitType -> k
    CharType -> k
    ListType t' -> has @Show t' k
    TupleType a b -> has @Show a $ has @Show b k
    SumType a b -> has @Show a $ has @Show b k

instance Has SymVal Type where
  has t k = case t of
    IntType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    UnitType -> k
    CharType -> k
    ListType t' -> has @SymVal t' k
    TupleType a b -> has @SymVal a $ has @SymVal b k
    SumType a b -> has @SymVal a $ has @SymVal b k

instance Has Read Type where
  has t k = case t of
    IntType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    UnitType -> k
    BoolType -> k
    CharType -> k
    ListType t' -> has @Read t' k
    TupleType a b -> has @Read a $ has @Read b k
    SumType a b -> has @Read a $ has @Read b k

instance Read AlgReal where
  readsPrec = error "TODO"

instance Has Data Type where
  has t k = case t of
    IntType -> k
    UnitType -> k
    FloatType -> k
    RationalType -> k
    RealType -> k
    BoolType -> k
    CharType -> k
    ListType t' -> has @Data t' k
    TupleType a b -> has @Data a $ has @Data b k
    SumType a b -> has @Data a $ has @Data b k

class ExprType t where
    typeOf :: t -> Type t
    typeOf' :: f t -> Type t

instance ExprType Integer where
    typeOf _ = IntType
    typeOf' _ = IntType
instance ExprType Bool where
    typeOf _ = BoolType
    typeOf' _ = BoolType
instance ExprType Double where
    typeOf _ = FloatType
    typeOf' _ = FloatType
instance ExprType Rational where
    typeOf _ = RationalType
    typeOf' _ = RationalType
instance ExprType AlgReal where
    typeOf _ = RealType
    typeOf' _ = RealType
instance ExprType Char where
    typeOf _ = CharType
    typeOf' _ = CharType
instance ExprType a => ExprType [a] where
    typeOf _ = ListType $ typeOf undefined
    typeOf' _ = ListType $ typeOf undefined
instance (ExprType a, ExprType b) => ExprType (a,b) where
    typeOf _ = TupleType (typeOf undefined) (typeOf undefined)
    typeOf' _ = TupleType (typeOf undefined) (typeOf undefined)
instance (ExprType a, ExprType b) => ExprType (Either a b) where
    typeOf _ = SumType (typeOf undefined) (typeOf undefined)
    typeOf' _ = SumType (typeOf undefined) (typeOf undefined)
instance ExprType () where
    typeOf _ = UnitType
    typeOf' _ = UnitType

data Variable t = Variable {varName :: String, varType :: Type t} deriving (Eq, Ord)
instance GEq Variable where
  geq (Variable lname ltype) (Variable rname rtype)
    | lname == rname
    , Just Refl <- ltype `geq` rtype
    = Just Refl
    | otherwise = Nothing
instance GCompare Variable where
  gcompare (Variable lname ltype) (Variable rname rtype) =
    case compare lname rname of
      LT -> GLT
      GT -> GGT
      EQ -> gcompare ltype rtype
instance GShow Variable where
  gshowsPrec = defaultGshowsPrec
instance Has (ComposeC Eq Expr) Variable where
  has _ k = k
instance Has (ComposeC Ord Expr) Variable where
  has _ k = k
instance Has (ComposeC Show Expr) Variable where
  has _ k = k
instance Has ExprType Variable where
  has v = has @ExprType (varType v)

instance Show (Variable a) where
    show (Variable name stype) = name ++ ":" ++ show stype

data Constant a where
  Constant :: ExprConstraints a => { constValue :: a } -> Constant a
constType :: Constant a -> Type a
constType (Constant x) = typeOf x
fromConst :: Constant a -> a
fromConst = constValue
deriving instance Eq (Constant a)
deriving instance Ord (Constant a)
instance Show (Constant a) where
  show (Constant a) = show a
instance (ExprConstraints a) => Read (Constant a) where
  readsPrec x y = withExprConstraints (typeOf @a undefined) $ first Constant <$> readsPrec x y

int :: Integer -> Some Constant
int i = Some (Constant i)
unit :: Some Constant
unit = Some (Constant ())
bool :: Bool -> Some Constant
bool b = Some (Constant b)
float :: Double -> Some Constant
float f = Some (Constant f)
rational :: Rational -> Some Constant
rational f = Some (Constant f)
real :: AlgReal -> Some Constant
real f = Some (Constant f)
char :: Char -> Some Constant
char c = Some (Constant c)
string :: String -> Some Constant
string s = Some (Constant s)
list :: ExprConstraints a => [a] -> Some Constant
list xs = Some (Constant xs)
tuple :: (ExprConstraints a, ExprConstraints b) => a -> b -> Some Constant
tuple a b = Some (Constant (a, b))
option :: (ExprConstraints a, ExprConstraints b) => Either a b -> Some Constant
option x = Some (Constant x)

-- | Recovers the position of the enum in the original range.
enumIndex :: Type a -> a -> Maybe Int
enumIndex tp val
  | isEnum tp = go tp val
  | otherwise = Nothing
  where
    go :: Type a -> a -> Maybe Int
    go UnitType () = Just 0
    go (SumType t _) (Left x) = go t x
    go (SumType _ t) (Right x) = (+1) <$> go t x
    go _ _ = Nothing
    -- Is this type a sum of units?
    -- Note: this is an overapproximation. For example, if 'Maybe a := SumType () a',
    -- 'Nothing' gets printed as 'Left 0'. A sum of two enums gets printed as a single enum.
    isEnum :: Type a -> Bool
    isEnum UnitType = True
    isEnum (SumType a b) = isEnum a && isEnum b
    isEnum _ = False

-- | Show a value, printing enums as their position in the original range.
prettyValue :: Type a -> a -> String
prettyValue t x | Just i <- enumIndex t x = show i
prettyValue (ListType CharType) s = show s
prettyValue (ListType t) xs = "[" ++ List.intercalate "," (map (prettyValue t) xs) ++ "]"
prettyValue (TupleType a b) (x, y) = "(" ++ prettyValue a x ++ "," ++ prettyValue b y ++ ")"
prettyValue (SumType a _) (Left x) = "Left " ++ prettyValue a x
prettyValue (SumType _ b) (Right y) = "Right " ++ prettyValue b y
prettyValue t x = has @Show t $ show x

prettyConstant :: Some Constant -> String
prettyConstant (Some (Constant x)) = prettyValue (typeOf x) x

instance GEq Constant where
  a `geq` b = case constType a `geq` constType b of
    Just Refl -> if has @Eq (constType a) $ constValue a == constValue b then Just Refl else Nothing
    Nothing -> Nothing
instance GCompare Constant where
  gcompare a b = case gcompare (constType a) (constType b) of
    GLT -> GLT
    GGT -> GGT
    GEQ -> case has @Ord a $ compare a b of
      LT -> GLT
      GT -> GGT
      EQ -> GEQ

instance GShow Constant where
  gshowsPrec i c = has @Show c $ defaultGshowsPrec i c
instance GRead Constant where
  greadsPrec _ =
    readParen False $ \s -> do
    ("Constant", s1) <- lex s
    (tp', s2) <- greadsPrec 11 s1
    Church.withSome tp' $ \(tp :: Type a) -> withExprConstraints tp $ do
      (x, rest) <- readsPrec 11 s2
      return (Church.mkSome (Constant @a x), rest)

instance Has c Type => Has c Constant where
  has (Constant x) = has @c $ typeOf x

instance JSON.FromJSON (Some Constant) where
    parseJSON (JSON.Object m)
        | not $ JSON.member "value" m = fail "expected Constant with a value field"
        | not $ JSON.member "type" m = fail "expected Constant with a type field"
    parseJSON (JSON.Object m)
        | Just val <- JSON.lookup "type" m = parseType val >>= \case
            Some BoolType -> parseBool $ lkup "value" m
            Some IntType -> parseInt $ lkup "value" m
            Some FloatType -> parseFloat $ lkup "value" m
            Some RationalType -> parseRational $ lkup "value" m
            Some RealType -> parseReal $ lkup "value" m
            Some UnitType -> parseUnit $ lkup "value" m
            Some CharType -> parseChar $ lkup "value" m
            Some (ListType t) -> withExprConstraints t $ parseList t $ lkup "value" m
            Some (TupleType a b) -> parseTuple a b $ lkup "value" m
            Some (SumType a b) -> parseSum a b $ lkup "value" m
        where
        parseType (JSON.String (Text.unpack -> s)) = case s of
          "char" -> pure $ Some CharType
          "int" -> pure $ Some IntType
          "float" -> pure $ Some FloatType
          "rational" -> pure $ Some RationalType
          "real" -> pure $ Some RealType
          "bool" -> pure $ Some BoolType
          "()" -> pure $ Some UnitType
          '[':(init -> cs) -> (\(Some t) -> Some $ ListType t) <$> parseType (JSON.String (Text.pack cs))
          '(':(parseTupleType 0 . init -> (a,b))
            -> (\(Some a') (Some b') -> Some $ TupleType a' b')
                      <$> parseType (JSON.String (Text.pack a))
                      <*> parseType (JSON.String (Text.pack b))
          '<':(parseTupleType 0 . init -> (a,b))
            -> (\(Some a') (Some b') -> Some $ SumType a' b')
                      <$> parseType (JSON.String (Text.pack a))
                      <*> parseType (JSON.String (Text.pack b))
          _ -> fail $ "bad type: " <> s
        parseType _ = fail "type is not a string"
        -- splits the string at the first comma that isn't part of a new tuple
        -- inefficient, but simple, and types should never be large
        parseTupleType :: Int -> String -> (String, String)
        parseTupleType 0 (',':xs) = ("",xs)
        parseTupleType n ('(':xs) = first ('(':) $ parseTupleType (n+1) xs
        parseTupleType n (')':xs) = first (')':) $ parseTupleType (n-1) xs
        parseTupleType n (x:xs)   = first (x:) $ parseTupleType n xs
        parseTupleType _ [] = error "comma not found in tuple"
        lkup :: JSON.Key -> JSON.KeyMap v -> v
        lkup k = Maybe.fromJust . JSON.lookup k
        parseBool (JSON.Bool b) = return $ bool b
        parseBool _ = fail "type indicates bool, but value is not of type bool"
        parseInt (JSON.Number (DS.floatingOrInteger @Double -> Right i)) = return $ int i
        parseInt _ = fail "type indicates int, but value is not of type int"
        parseUnit (JSON.String s)
          | "()" <- Text.unpack s = return unit
        parseUnit _ = fail "failed to parse a unit"
        parseChar (JSON.String s)
         | [c] <- Text.unpack s
         = return $ char c
        parseChar _ = fail "type indicates char, but value is not of type char"
        parseFloat (JSON.Number (DS.toRealFloat -> f)) = return $ float f
        parseFloat _ = fail "type indicates float, but value is not a number"
        parseRational (JSON.Number f) = return $ rational $ toRational f
        parseRational _ = fail "type indicates rational, but value is not a number"
        parseReal (JSON.Number f) = return $ real $ fromRational $ toRational f
        parseReal _ = fail "type indicates rational, but value is not a number"
        parseList t (JSON.Array xs) = has @ExprType t list <$> mapM (unSome t <=< JSON.parseJSON @(Some Constant)) (Vec.toList xs)
          where
            unSome :: Type a -> Some Constant -> JSON.Parser a
            unSome tp (Some (Constant v)) = case typeOf v `geq` tp of
              Nothing -> fail $ "type indicates list of " <> show tp <> ", but at least one element was a " <> show (typeOf v)
              Just Refl -> pure v
        parseList _ _ = fail "type indicates list, but value is not of type array"
        parseTuple :: Type a -> Type b -> JSON.Value -> JSON.Parser (Some Constant)
        parseTuple a b (JSON.Object m')
          | Just x <- JSON.lookup "left" m'
          , Just y <- JSON.lookup "right" m'
          = do
          Some (Constant xv) <- JSON.parseJSON x
          Some (Constant yv) <- JSON.parseJSON y
          let xt = typeOf xv
          let yt = typeOf yv
          case a `geq` xt of
            Nothing -> fail "type of left element of tuple doesn't match"
            Just Refl -> case b `geq` yt of
              Nothing -> fail "type of right element of tuple doesn't match"
              Just Refl -> has @ExprType xt $ has @ExprType yt $ return $ tuple xv yv
        parseTuple _ _ _ = fail "type indicates pair, but value is not of type object"
        parseSum :: forall a b. Type a -> Type b -> JSON.Value -> JSON.Parser (Some Constant)
        parseSum a b (JSON.Object m')
          | Just x <- JSON.lookup "left" m'
          = do
          Some (Constant xv) <- JSON.parseJSON x
          let xt = typeOf xv
          case a `geq` xt of
            Nothing -> fail "type of left element of tuple doesn't match"
            Just Refl -> has @ExprType xt $ withExprConstraints b $ return $ Some $ Constant (Left @a @b xv)
          | Just y <- JSON.lookup "right" m'
          = do
          Some (Constant yv) <- JSON.parseJSON y
          let yt = typeOf yv
          case b `geq` yt of
            Nothing -> fail "type of right element of tuple doesn't match"
            Just Refl -> has @ExprType yt $ withExprConstraints a $ return $ Some $ Constant (Right @a @b yv)
        parseSum _ _ _ = fail "type indicates either, but value is not of type object"
    parseJSON _ = fail "expected Constant JSON"

instance JSON.ToJSON (Some Constant) where
    toJSON (Some (Constant x)) = case typeOf x of
      BoolType -> JSON.Object $ JSON.insert "type" "bool" $ JSON.insert "value" (JSON.Bool x) JSON.empty
      UnitType -> JSON.Object $ JSON.insert "type" "()" $ JSON.insert "value" (JSON.String $ Text.pack "()") JSON.empty
      IntType -> JSON.Object $ JSON.insert "type" "int" $ JSON.insert "value" (JSON.Number $ fromInteger x) JSON.empty
      FloatType -> JSON.Object $ JSON.insert "type" "float" $ JSON.insert "value" (JSON.Number $ fromFloatDigits x) JSON.empty
      RationalType -> JSON.Object $ JSON.insert "type" "rational" $ JSON.insert "value" (JSON.Number $ fst $ DS.fromRationalRepetendUnlimited x) JSON.empty
      RealType -> JSON.Object $ JSON.insert "type" "real" $ JSON.insert "value" (JSON.Number $ fromRational $ toRational x) JSON.empty
      CharType -> JSON.Object $ JSON.insert "type" "string" $ JSON.insert "value" (JSON.String $ Text.pack [x]) JSON.empty
      ListType t -> JSON.Object
       $ JSON.insert "type" (fromString . show $ ListType t)
       $ JSON.insert "value" (JSON.Array $ Vec.fromList $ map (JSON.toJSON . Some . withExprConstraints t Constant) x)
       JSON.empty
      TupleType a b -> JSON.Object $ withExprConstraints a $ withExprConstraints b
       $ JSON.insert "type" (fromString . show $ TupleType a b)
       $ JSON.insert "value" (JSON.Object $ JSON.insert "left" (JSON.toJSON . Some $ Constant $ fst x) $ JSON.insert "right" (JSON.toJSON . Some $ Constant $ snd x) JSON.empty)
       JSON.empty
      SumType a b -> JSON.Object
       $ JSON.insert "type" (fromString . show $ SumType a b)
       $ JSON.insert "value" (case x of
         Left  y -> withExprConstraints a $ JSON.Object $ JSON.insert "left"  (JSON.toJSON . Some $ Constant y) JSON.empty
         Right y -> withExprConstraints b $ JSON.Object $ JSON.insert "right" (JSON.toJSON . Some $ Constant y) JSON.empty)
       JSON.empty


-- ----------------------------------------------------------------------------------------- --
-- value expression

data ExprView t where
    Var :: {variable :: Variable t} -> ExprView t
    Const :: ExprConstraints t => {constant :: t} -> ExprView t
    Ite :: {conditional :: ExprView Bool, trueBranch :: ExprView t, falseBranch :: ExprView t} -> ExprView t
    Equal :: ExprConstraints t => {eqType :: Type t, left :: ExprView t, right :: ExprView t} -> ExprView Bool
    Divide :: {dividend2 :: ExprView Integer, divisor2 :: ExprView Integer} -> ExprView Integer
    Modulo :: {dividend2 :: ExprView Integer, divisor2 :: ExprView Integer} -> ExprView Integer
    DivideFloat :: Fractional a => {dividendF :: ExprView a, divisorF :: ExprView a} -> ExprView a
    Sum :: Num a => Type a -> FreeSum (ExprView a) -> ExprView a
    Product :: Num a => Type a -> FreeProduct (ExprView a) -> ExprView a
    Gez :: Num a => ExprView a -> ExprView Bool
    Not :: ExprView Bool -> ExprView Bool
    And :: Set (ExprView Bool) -> ExprView Bool
    Concat :: ExprConstraints a => ExprView [[a]] -> ExprView [a]
    Cons :: ExprView x -> ExprView [x] -> ExprView [x]
    Append :: ExprView [a] -> ExprView [a] -> ExprView [a]
    Length :: Type a -> ExprView [a] -> ExprView Integer
    LElem :: Type a -> ExprView a -> ExprView [a] -> ExprView Bool
    Take :: ExprView Integer -> ExprView [a] -> ExprView [a]
    Drop :: ExprView Integer -> ExprView [a] -> ExprView [a]
    First :: Type b -> ExprView (a,b) -> ExprView a
    Second :: Type a -> ExprView (a,b) -> ExprView b
    Pair :: ExprView a -> ExprView b -> ExprView (a,b)
    Head :: ExprConstraints x => ExprView [x] -> ExprView x
    Tail :: ExprConstraints x => ExprView [x] -> ExprView [x]
    ELeft  :: (ExprConstraints a, ExprConstraints b) => ExprView a -> ExprView (Either a b)
    ERight  :: (ExprConstraints a, ExprConstraints b) => ExprView b -> ExprView (Either a b)
    Zip :: Type a -> Type b -> ExprView [a] -> ExprView [b] -> ExprView [(a,b)]
    -- Adding Lam and App would make it impossible to implement some typeclasses that SBV wants,
    -- and is also stronger than we need: we don't need lists of functions, top-level functions, etc.
    -- Lam :: Variable t -> ExprView a -> ExprView (a -> t)
    -- App :: Type a -> ExprView (a -> b) -> ExprView a -> ExprView b
    -- Instead, 'Map', 'Filter', 'Fold's, and 'Either' (the only places where we want a function)
    -- just inline the definition of Lam: they carry the bound variable and the function body (which may reference this variable)
    Map :: (ExprConstraints a, ExprConstraints b) => Variable a -> ExprView b -> ExprView [a] -> ExprView [b]
    Filter :: ExprConstraints a => Variable a -> ExprView Bool -> ExprView [a] -> ExprView [a]
    -- for folds, the first `ExprView b` is the function and the second is the initial value
    Foldr :: ExprConstraints a => Variable a -> Variable b -> ExprView b -> ExprView b -> ExprView [a] -> ExprView b
    Foldl :: ExprConstraints a => Variable b -> Variable a -> ExprView b -> ExprView b -> ExprView [a] -> ExprView b
    -- The first 'ExprView x' has the 'Variable a' in scope, the second 'ExprView x' has the 'Variable b' in scope.
    -- This is the `either` deconstructor in Haskell: (a -> x) -> (b -> x) -> Either a b -> x
    Either :: (ExprConstraints a, ExprConstraints b, ExprConstraints x) => Variable a -> Variable b -> ExprView x -> ExprView x -> ExprView (Either a b) -> ExprView x
    -- Quantifiers: Introduce a variable that is in scope within the subexpression
    Forall :: ExprConstraints a => Variable a -> ExprView Bool -> ExprView Bool
    Exists :: ExprConstraints a => Variable a -> ExprView Bool -> ExprView Bool
    -- NOTE: when adding more fields, check the Eq instance

type ExprConstraints t = (Data t, Eq t, Ord t, OrdSymbolic (SBV t), Show t, ExprType t, SymVal t, Eq t, Read t)

viewType :: ExprView a -> Type a
viewType v = withExprConstraints v $ typeOf' v

instance Eq (ExprView t) where
  Var x == Var y = x == y
  Const x == Const y = x == y
  Ite c1 l1 r1 == Ite c2 l2 r2 = c1 == c2 && l1 == l2 && r1 == r2
  Equal t1 a b == Equal t2 x y
    | Just Refl <- t1 `geq` t2 = a == x && b == y
  Divide a b == Divide x y = a == x && b == y
  Modulo a b == Modulo x y = a == x && b == y
  DivideFloat a b == DivideFloat x y = a == x && b == y
  Sum _ x == Sum _ y = x == y
  Product _ x == Product _ y = x == y
  Gez x == Gez y
    | Just Refl <- viewType x `geq` viewType y = x == y
  Not x == Not y = x == y
  And x == And y = x == y
  Concat x == Concat y = x == y
  Cons x xs == Cons y ys = x == y && xs == ys
  Append x xs == Append y ys = x == y && xs == ys
  Length a x == Length b y
    | Just Refl <- a `geq` b = x == y
  LElem t1 x y == LElem t2 a b
    | Just Refl <- t1 `geq` t2 = x == a && y == b
  Take x xs == Take y ys = x == y && xs == ys
  Drop x xs == Drop y ys = x == y && xs == ys
  First t1 x == First t2 y
   | Just Refl <- geq t1 t2
   = x == y
  Second t1 x == Second t2 y
   | Just Refl <- geq t1 t2
   = x == y
  Pair a b == Pair x y = a == x && b == y
  Head x == Head y = x == y
  Tail x == Tail y = x == y
  ELeft x == ELeft y
    | Just Refl <- geq (typeOf' x) (typeOf' y) = x == y
  ERight x == ERight y
    | Just Refl <- geq (typeOf' x) (typeOf' y) = x == y
  Zip ta tb x y == Zip ta' tb' x' y'
    | Just Refl <- ta `geq` ta'
    , Just Refl <- tb `geq` tb'
    = x == x' && y == y'
  Map v1 f xs == Map v2 g ys
    | Just Refl <- geq v1 v2
    = f == g && xs == ys
  Foldr v1 v2 f x xs == Foldr v1' v2' g y ys
    | Just Refl <- geq (typeOf' xs) (typeOf' ys)
    = v1 == v1' && v2 == v2' && f == g && x == y && xs == ys
  Foldl v1 v2 f x xs == Foldl v1' v2' g y ys
    | Just Refl <- geq (typeOf' xs) (typeOf' ys)
    = v1 == v1' && v2 == v2' && f == g && x == y && xs == ys
  Filter v f xs == Filter v' g ys = v == v' && f == g && xs == ys
  Either ta tb a b c == Either tx ty x y z
    | Just Refl <- geq ta tx
    , Just Refl <- geq tb ty
    = a == x && b == y && c == z
  Forall a x == Forall b y
    | Just Refl <- geq a b
    = a == b && x == y
  Exists a x == Exists b y
    | Just Refl <- geq a b
    = a == b && x == y
  _ == _ = False

instance Ord (ExprView t) where
  compare l r =
    case (l, r) of
      (Var a, Var b) -> compare a b
      (Const a, Const b) -> compare a b
      (Ite c1 l1 r1, Ite c2 l2 r2) ->
        compare (c1, l1, r1) (c2, l2, r2)
      (Equal t1 a b, Equal t2 x y) ->
        case gcompare t1 t2 of
          GLT -> LT
          GGT -> GT
          GEQ -> compare (a,b) (x,y)
      (Divide a b, Divide x y) ->
        compare (a, b) (x, y)
      (Modulo a b, Modulo x y) ->
        compare (a, b) (x, y)
      (DivideFloat a b, DivideFloat x y) ->
        compare (a, b) (x, y)
      (Sum _ x, Sum _ y) ->
        compare x y
      (Product _ x, Product _ y) ->
        compare x y
      (Gez a, Gez b) ->
        case gcompare (viewType a) (viewType b) of
          GLT -> LT
          GGT -> GT
          GEQ -> compare a b
      (Not a, Not b) ->
        compare a b
      (And a, And b) ->
        compare a b
      (Concat a, Concat b) ->
        compare a b
      (Cons x xs, Cons y ys) ->
        compare (x,xs) (y,ys)
      (Append as bs, Append xs ys) ->
        compare (as,bs) (xs,ys)
      (Length a x, Length b y) -> case gcompare a b of
        GLT -> LT
        GGT -> GT
        GEQ -> compare x y
      (LElem t1 x xs, LElem t2 y ys) ->
        case gcompare t1 t2 of
          GLT -> LT
          GGT -> GT
          GEQ -> compare (x,xs) (y,ys)
      (Take i xs, Take j ys) ->
        compare (i,xs) (j,ys)
      (Drop i xs, Drop j ys) ->
        compare (i,xs) (j,ys)
      (First t1 x, First t2 a) ->
        case gcompare t1 t2 of
          GLT -> LT
          GGT -> GT
          GEQ -> compare x a
      (Second t1 x, Second t2 a) ->
        case gcompare t1 t2 of
          GLT -> LT
          GGT -> GT
          GEQ -> compare x a
      (Pair x y, Pair a b) ->
        compare (x,y) (a,b)
      (Head x, Head a) ->
        compare x a
      (Tail x, Tail a) ->
        compare x a
      (ELeft x, ELeft y) -> case gcompare (typeOf' x) (typeOf' y) of
        GLT -> LT
        GGT -> GT
        GEQ -> compare x y
      (ERight x, ERight y) -> case gcompare (typeOf' x) (typeOf' y) of
        GLT -> LT
        GGT -> GT
        GEQ -> compare x y
      (Zip ta tb a b, Zip tx ty x y) ->
        case gcompare ta tx of
          GLT -> LT
          GGT -> GT
          GEQ -> case gcompare tb ty of
            GLT -> LT
            GGT -> GT
            GEQ -> compare (a,b) (x,y)
      (Either ta tb a b c, Either tx ty x y z) ->
        case gcompare ta tx of
          GLT -> LT
          GGT -> GT
          GEQ -> case gcompare tb ty of
            GLT -> LT
            GGT -> GT
            GEQ -> compare (a,b,c) (x,y,z)
      (Map x y z, Map a b c) ->
        case gcompare x a of
          GLT -> LT
          GGT -> GT
          GEQ -> compare (y,z) (b,c)
      (Foldr v1 v2 f x xs, Foldr v1' v2' g y ys) ->
        case gcompare v1 v1' of
          GLT -> LT
          GGT -> GT
          GEQ -> compare (v2, f, x, xs) (v2', g, y, ys)
      (Foldl v1 v2 f x xs, Foldl v1' v2' g y ys) ->
        case gcompare v2 v2' of
          GLT -> LT
          GGT -> GT
          GEQ -> compare (v1, f, x, xs) (v1', g, y, ys)
      (Filter v1 f xs, Filter v2 g ys) -> compare (v1, f, xs) (v2, g, ys)
      (Forall a x, Forall b y) -> case gcompare a b of
        GLT -> LT
        GGT -> GT
        GEQ -> compare x y
      (Exists a x, Exists b y) -> case gcompare a b of
        GLT -> LT
        GGT -> GT
        GEQ -> compare x y
      _ ->
        compare (tag l) (tag r)
    where
      tag :: ExprView t -> Int
      tag = \case
        Var{}     -> 0
        Const{}   -> 1
        Ite{}     -> 2
        Equal{}   -> 3
        Divide{}  -> 4
        Modulo{}  -> 5
        Sum{}     -> 6
        Product{} -> 7
        Length{}  -> 8
        Gez{}     -> 9
        Not{}     -> 10
        And{}     -> 11
        Concat{}  -> 12
        Cons{}    -> 13
        Append{}  -> 14
        LElem{}   -> 15
        Take{}    -> 16
        Drop{}    -> 17
        DivideFloat{} -> 18
        Filter{} -> 22
        ELeft{} -> 23
        ERight{} -> 24
        First{} -> 25
        Second{} -> 26
        Pair{} -> 27
        Head{} -> 28
        Tail{} -> 29
        Either{} -> 30
        Map{} -> 31
        Foldr{} -> 34
        Foldl{} -> 35
        Zip{} -> 36
        Forall{} -> 37
        Exists{} -> 38


instance Show (ExprView t) where
  show = \case
    (Var v) -> varName v
    (Const c) -> show c
    (Ite cond e1 e2) -> "if " ++ bshow cond ++ " then " ++ bshow e1 ++ " else " ++ bshow e2
    (Divide e1 e2) -> bshow e1 ++ " / " ++ bshow e2
    (Modulo e1 e2) -> bshow e1 ++ " % " ++ bshow e2
    (DivideFloat e1 e2) -> bshow e1 ++ " / " ++ bshow e2
    (Sum _ es) | es == mempty -> "∑∅"
    (Sum _ es) -> showFreeMonoid "+" bshowSumTerm es
      where
      bshowSumTerm (-1)     t = "-" ++ t
      bshowSumTerm 1 t = t
      bshowSumTerm n t = bshow n ++ "⋅" ++ t
    (Product _ es) | es == mempty -> "∏∅"
    (Product _ es) -> showFreeMonoid "⋅" (\n t -> bshow n ++ "^" ++ t) es -- "(" ++ bshow e2 ++ ")" --FreeProduct Expr
    (Length _ e) -> "length " ++ bshow e
    (Equal _ e1 e2) -> bshow e1 ++ " = " ++ bshow e2
    (Gez e) -> bshow e ++ " ≥ 0"
    (Not e) -> "¬" ++ bshow e
    (And (Set.toList -> [])) -> "⋀∅"
    (And (Set.toList -> es)) -> List.intercalate "∧" $ bshow <$> es
    (Concat es) -> "concat " <> bshow es
    (Cons x xs) -> bshow x ++ ":" ++ bshow xs
    (Append xs ys) -> bshow xs ++ "++" ++ bshow ys
    (LElem _ x xs) -> bshow x ++ "`elem`" ++ bshow xs
    (Take i xs) -> "take " ++ bshow i ++ " " ++ bshow xs
    (Drop i xs) -> "drop " ++ bshow i ++ " " ++ bshow xs
    (Head x) -> "head " <> bshow x
    (Tail x) -> "tail " <> bshow x
    (First _ x) -> "fst " <> bshow x
    (Second _ x) -> "snd " <> bshow x
    (Pair x y) -> "(" <> show x <> ", " <> show y <> ")"
    (Either _ _ l r x) -> "either " <> bshow l <> " " <> bshow r <> " " <> bshow x
    (Zip _ _ x y) -> "zip " <> bshow x <> " " <> bshow y
    (Map v f xs) -> "map (\\" <> show v <> " -> " <> show f <> ") " <> bshow xs
    (ELeft x) -> "Left " <> bshow x
    (ERight x) -> "Right " <> bshow x
    (Filter _ f xs) -> "filter " <> bshow f <> " " <> bshow xs
    (Foldr _ _ f i xs) -> "foldr " <> bshow f <> " " <> bshow i <> " " <> bshow xs
    (Foldl _ _ f i xs) -> "foldl " <> bshow f <> " " <> bshow i <> " " <> bshow xs
    (Forall v x) -> "∀" <> show v <> " " <> show x
    (Exists v x) -> "∃" <> show v <> " " <> show x
    where
      bshow x = let y = show x in if isJust (List.elemIndex ' ' y) then '(' : y <> ")" else y

instance Has ExprType Expr where
  has (Expr v) = has @ExprType v

instance Has ExprType ExprView where
  has e k = case e of
    Var v -> has @ExprType (varType v) k
    Const _ -> k
    Ite _ x _ -> has @ExprType x k
    Equal t _ _ -> has @ExprType t k
    Divide _ _ -> k
    DivideFloat x _ -> has @ExprType x k
    Modulo _ _ -> k
    Sum t _ -> has @ExprType t k
    Product t _ -> has @ExprType t k
    Length t _ -> has @ExprType t k
    Gez _ -> k
    Not _ -> k
    And _ -> k
    Concat _ -> k
    Cons _ x -> has @ExprType x k
    Append _ x -> has @ExprType x k
    LElem t _ _ -> has @ExprType t k
    Take _ x -> has @ExprType x k
    Drop _ x -> has @ExprType x k
    First _ x -> case has @ExprType x $ typeOf' x of
      TupleType t _ -> has @ExprType t k
    Second _ x -> case has @ExprType x $ typeOf' x of
      TupleType _ t -> has @ExprType t k
    Pair x y -> has @ExprType x $ has @ExprType y k
    Head x -> case typeOf' x of
      ListType t -> has @ExprType t k
    Tail x -> case typeOf' x of
      ListType t -> has @ExprType t k
    Zip x y _ _ -> has @ExprType x $ has @ExprType y k
    Either _ _ x _ _ -> has @ExprType x k
    Map _ x _ -> has @ExprType x k
    ELeft x -> has @ExprType x k
    ERight x -> has @ExprType x k
    Filter _ _ x -> has @ExprType x k
    Foldr _ x _ _ _ -> has @ExprType x k
    Foldl x _ _ _ _ -> has @ExprType x k
    Forall _ x -> has @ExprType x k
    Exists _ x -> has @ExprType x k

showFreeMonoid :: Show a => String -> (Integer -> String -> String) -> FreeMonoidX a -> String
showFreeMonoid plusRepr multRepr (FMX p) = List.intercalate plusRepr $ showTerm <$> Map.assocs p
    where
    showTerm (x, i) = multRepr i (show x)


-- | Expr: value expression
-- Only 'view' is exported, not the constructor, to safeguard invariants.
newtype Expr t = Expr {view :: ExprView t} deriving (Eq, Ord)
-- TODO: which invariants? I can't find any other mention of them,
-- so I've been assuming that any representable ExprView is fair game

instance Show (Expr t) where
  show = show . view

instance GShow Expr where
  gshowsPrec = defaultGshowsPrec

instance GEq Expr where
  geq x y = withExprConstraints x $ withExprConstraints y $ geq (typeOf' x) (typeOf' y)

instance GCompare Expr where
  gcompare x y = withExprConstraints x $ withExprConstraints y $ case gcompare (typeOf' x) (typeOf' y) of
    GLT -> GLT
    GGT -> GGT
    GEQ -> case compare x y of
      GT -> GGT
      LT -> GLT
      EQ -> GEQ


isConst :: ExprView v -> Bool
isConst (Const _) = True
isConst _ = False


freeVars :: Expr t -> Set.Set (Some Variable)
freeVars = Set.fromList . freeVars' . view

freeVars' :: ExprView t -> [Some Variable]
freeVars' (Var v) = [Some v]
freeVars' (Const _) = []
freeVars' (Ite cond e1 e2) = freeVars' cond ++ freeVars' e1 ++ freeVars' e2
freeVars' (Divide e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (Modulo e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (DivideFloat e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (Sum _ (distinctTermsT -> es)) = concatMap freeVars' es
freeVars' (Product _ (distinctTermsT -> es)) = concatMap freeVars' es
freeVars' (Length _ e) = freeVars' e
freeVars' (Equal _ e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (Gez e) = freeVars' e
freeVars' (Not e) = freeVars' e
freeVars' (And (Set.toList -> es)) = concatMap freeVars' es
freeVars' (Concat es) = freeVars' es
freeVars' (Cons e es) = freeVars' e ++ freeVars' es
freeVars' (Append e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (LElem _ e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (Take e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (Drop e1 e2) = freeVars' e1 ++ freeVars' e2
freeVars' (First _ x) = freeVars' x
freeVars' (Second _ x) = freeVars' x
freeVars' (Pair x y) = freeVars' x ++ freeVars' y
freeVars' (Head xs) = freeVars' xs
freeVars' (Tail xs) = freeVars' xs
freeVars' (ELeft x) = freeVars' x
freeVars' (ERight x) = freeVars' x
freeVars' (Zip _ _ x y) = freeVars' x ++ freeVars' y
-- v, vl, and vr are not free
freeVars' (Map v f xs) = filter (/= Some v) (freeVars' f) ++ freeVars' xs
freeVars' (Either vl vr l r x) = filter (/= Some vl) (freeVars' l) ++ filter (/= Some vr) (freeVars' r) ++ freeVars' x
freeVars' (Filter v f xs) = filter (/= Some v) (freeVars' f) ++ freeVars' xs
freeVars' (Foldr v1 v2 f i xs) = filter (not . flip elem [Some v1, Some v2]) (freeVars' f) ++ freeVars' i ++ freeVars' xs
freeVars' (Foldl v1 v2 f i xs) = filter (not . flip elem [Some v1, Some v2]) (freeVars' f) ++ freeVars' i ++ freeVars' xs
freeVars' (Forall v x) = filter (/= Some v) (freeVars' x)
freeVars' (Exists v x) = filter (/= Some v) (freeVars' x)