-- | This module has various utility functions for accessing queries.
--   TODO: move the "clients" in Visitors into this module.

module Language.Fixpoint.Types.Utils (
  -- * Domain of a kvar
    kvarDomain

  -- * Free variables in a refinement
  , reftFreeVars

  -- * Deconstruct a SortedReft
  , sortedReftConcKVars

  -- * Operators on DataDecl
  , checkRegular
  , orderDeclarations

  ) where

import qualified Data.HashMap.Strict                  as M
import qualified Data.HashSet                         as S

import           Language.Fixpoint.Misc
import           Language.Fixpoint.Types.Names
import           Language.Fixpoint.Types.Refinements
import           Language.Fixpoint.Types.Environments
import           Language.Fixpoint.Types.Constraints
import           Language.Fixpoint.Types.Sorts
import qualified Language.Fixpoint.Misc as Misc

--------------------------------------------------------------------------------
-- | Compute the domain of a kvar
--------------------------------------------------------------------------------
kvarDomain :: SInfo a -> KVar -> [Symbol]
--------------------------------------------------------------------------------
kvarDomain :: forall a. SInfo a -> KVar -> [Symbol]
kvarDomain SInfo a
si KVar
k = forall a. BindEnv a -> WfC a -> [Symbol]
domain (forall (c :: * -> *) a. GInfo c a -> BindEnv a
bs SInfo a
si) (forall a. SInfo a -> KVar -> WfC a
getWfC SInfo a
si KVar
k)

domain :: BindEnv a -> WfC a -> [Symbol]
domain :: forall a. BindEnv a -> WfC a -> [Symbol]
domain BindEnv a
be WfC a
wfc = forall a b c. (a, b, c) -> a
fst3 (forall a. WfC a -> (Symbol, Sort, KVar)
wrft WfC a
wfc) forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst (forall a. BindEnv a -> IBindEnv -> [(Symbol, SortedReft)]
envCs BindEnv a
be forall a b. (a -> b) -> a -> b
$ forall a. WfC a -> IBindEnv
wenv WfC a
wfc)

getWfC :: SInfo a -> KVar -> WfC a
getWfC :: forall a. SInfo a -> KVar -> WfC a
getWfC SInfo a
si KVar
k = forall (c :: * -> *) a. GInfo c a -> HashMap KVar (WfC a)
ws SInfo a
si forall k v.
(Eq k, Hashable k, HasCallStack) =>
HashMap k v -> k -> v
M.! KVar
k

--------------------------------------------------------------------------------
-- | Free variables of a refinement
--------------------------------------------------------------------------------
--TODO deduplicate (also in Solver/UniqifyBinds)
reftFreeVars :: Reft -> S.HashSet Symbol
reftFreeVars :: Reft -> HashSet Symbol
reftFreeVars r :: Reft
r@(Reft (Symbol
v, Expr
_)) = forall a. (Eq a, Hashable a) => a -> HashSet a -> HashSet a
S.delete Symbol
v forall a b. (a -> b) -> a -> b
$ forall a. (Eq a, Hashable a) => [a] -> HashSet a
S.fromList forall a b. (a -> b) -> a -> b
$ forall a. Subable a => a -> [Symbol]
syms Reft
r

--------------------------------------------------------------------------------
-- | Split a SortedReft into its concrete and KVar components
--------------------------------------------------------------------------------
sortedReftConcKVars :: Symbol -> SortedReft -> ([Pred], [KVSub], [KVSub])
sortedReftConcKVars :: Symbol -> SortedReft -> ([Expr], [KVSub], [KVSub])
sortedReftConcKVars Symbol
x SortedReft
sr = [Expr]
-> [KVSub]
-> [KVSub]
-> [(Symbol, Expr)]
-> ([Expr], [KVSub], [KVSub])
go [] [] [] [(Symbol, Expr)]
ves
  where
    ves :: [(Symbol, Expr)]
ves                  = [(Symbol
v, Expr
p forall a. Subable a => a -> (Symbol, Expr) -> a
`subst1` (Symbol
v, forall a. Symbolic a => a -> Expr
eVar Symbol
x)) | Reft (Symbol
v, Expr
p) <- [Reft]
rs ]
    rs :: [Reft]
rs                   = Reft -> [Reft]
reftConjuncts (SortedReft -> Reft
sr_reft SortedReft
sr)
    t :: Sort
t                    = SortedReft -> Sort
sr_sort SortedReft
sr

    go :: [Expr]
-> [KVSub]
-> [KVSub]
-> [(Symbol, Expr)]
-> ([Expr], [KVSub], [KVSub])
go [Expr]
ps [KVSub]
ks [KVSub]
gs ((Symbol
v, PKVar KVar
k Subst
su    ):[(Symbol, Expr)]
xs) = [Expr]
-> [KVSub]
-> [KVSub]
-> [(Symbol, Expr)]
-> ([Expr], [KVSub], [KVSub])
go [Expr]
ps (Symbol -> Sort -> KVar -> Subst -> KVSub
KVS Symbol
v Sort
t KVar
k Subst
suforall a. a -> [a] -> [a]
:[KVSub]
ks) [KVSub]
gs [(Symbol, Expr)]
xs
    go [Expr]
ps [KVSub]
ks [KVSub]
gs ((Symbol
v, PGrad KVar
k Subst
su GradInfo
_ Expr
_):[(Symbol, Expr)]
xs) = [Expr]
-> [KVSub]
-> [KVSub]
-> [(Symbol, Expr)]
-> ([Expr], [KVSub], [KVSub])
go [Expr]
ps [KVSub]
ks (Symbol -> Sort -> KVar -> Subst -> KVSub
KVS Symbol
v Sort
t KVar
k Subst
suforall a. a -> [a] -> [a]
:[KVSub]
gs) [(Symbol, Expr)]
xs
    go [Expr]
ps [KVSub]
ks [KVSub]
gs ((Symbol
_, Expr
p):[(Symbol, Expr)]
xs)              = [Expr]
-> [KVSub]
-> [KVSub]
-> [(Symbol, Expr)]
-> ([Expr], [KVSub], [KVSub])
go (Expr
pforall a. a -> [a] -> [a]
:[Expr]
ps) [KVSub]
ks [KVSub]
gs [(Symbol, Expr)]
xs
    go [Expr]
ps [KVSub]
ks [KVSub]
gs []                       = ([Expr]
ps, [KVSub]
ks, [KVSub]
gs)


-------------------------------------------------------------------------------
-- | @checkRegular ds@ returns the subset of ds that are _not_ regular
-------------------------------------------------------------------------------
checkRegular :: [DataDecl] -> [DataDecl]
-------------------------------------------------------------------------------
checkRegular :: [DataDecl] -> [DataDecl]
checkRegular [DataDecl]
ds = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ [DataDecl]
ds' | [DataDecl]
ds' <- [DataDecl] -> [[DataDecl]]
orderDeclarations [DataDecl]
ds, Bool -> Bool
not ([DataDecl] -> Bool
isRegular [DataDecl]
ds')]

-------------------------------------------------------------------------------
-- | @isRegular [d1,...]@ gets a non-empty list of mut-recursive datadecls
-------------------------------------------------------------------------------
isRegular :: [DataDecl] -> Bool
-------------------------------------------------------------------------------

isRegular :: [DataDecl] -> Bool
isRegular []       = forall a. HasCallStack => [Char] -> a
error [Char]
"impossible: isRegular"
isRegular ds :: [DataDecl]
ds@(DataDecl
d:[DataDecl]
_) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\DataDecl
d' -> DataDecl -> Int
ddVars DataDecl
d' forall a. Eq a => a -> a -> Bool
== Int
nArgs) [DataDecl]
ds   -- same number of tyArgs
                  Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Sort, [Sort]) -> Bool
isRegApp [(Sort, [Sort])]
fldSortApps         -- 'regular' application (tc @0 ... @n)
  where
    nArgs :: Int
nArgs          = DataDecl -> Int
ddVars DataDecl
d
    tcs :: HashSet Symbol
tcs            = forall a. (Eq a, Hashable a) => [a] -> HashSet a
S.fromList ( forall a. Symbolic a => a -> Symbol
symbol forall b c a. (b -> c) -> (a -> b) -> a -> c
. DataDecl -> FTycon
ddTyCon forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [DataDecl]
ds)
    fldSortApps :: [(Sort, [Sort])]
fldSortApps    = [ (Sort
c,[Sort]
ts) | DataDecl
d'          <- [DataDecl]
ds
                              , DataCtor
ctor        <- DataDecl -> [DataCtor]
ddCtors DataDecl
d'
                              , DField LocSymbol
_ Sort
t  <- DataCtor -> [DataField]
dcFields DataCtor
ctor
                              , (Sort
c, [Sort]
ts)     <- Sort -> [(Sort, [Sort])]
sortApps Sort
t
                     ]
    isRegApp :: (Sort, [Sort]) -> Bool
isRegApp (Sort, [Sort])
cts   = case (Sort, [Sort])
cts of
                        (FTC FTycon
c, [Sort]
ts) -> Bool -> Bool
not (forall a. (Eq a, Hashable a) => a -> HashSet a -> Bool
S.member (forall a. Symbolic a => a -> Symbol
symbol FTycon
c) HashSet Symbol
tcs) Bool -> Bool -> Bool
|| Int -> [Sort] -> Bool
isRegularArgs Int
nArgs [Sort]
ts
                        (Sort, [Sort])
_           -> Bool
False

isRegularArgs :: Int -> [Sort] -> Bool
isRegularArgs :: Int -> [Sort] -> Bool
isRegularArgs Int
n [Sort]
ts = [Sort]
ts forall a. Eq a => a -> a -> Bool
== [Int -> Sort
FVar Int
i | Int
i <- [Int
0 .. (Int
nforall a. Num a => a -> a -> a
-Int
1)]]

type SortApp = (Sort, [Sort])

sortApps :: Sort -> [SortApp]
sortApps :: Sort -> [(Sort, [Sort])]
sortApps = Sort -> [(Sort, [Sort])]
go
  where
    go :: Sort -> [(Sort, [Sort])]
go t :: Sort
t@FApp {}     = (Sort
f, [Sort]
ts) forall a. a -> [a] -> [a]
: forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Sort -> [(Sort, [Sort])]
go [Sort]
ts where (Sort
f, [Sort]
ts) = Sort -> (Sort, [Sort])
splitApp Sort
t
    go (FFunc Sort
t1 Sort
t2) = Sort -> [(Sort, [Sort])]
go Sort
t1 forall a. [a] -> [a] -> [a]
++ Sort -> [(Sort, [Sort])]
go Sort
t2
    go (FAbs Int
_ Sort
t)    = Sort -> [(Sort, [Sort])]
go Sort
t
    go Sort
_             = []

splitApp :: Sort -> SortApp
splitApp :: Sort -> (Sort, [Sort])
splitApp = [Sort] -> Sort -> (Sort, [Sort])
go []
  where
    go :: [Sort] -> Sort -> (Sort, [Sort])
go [Sort]
stk (FApp Sort
t1 Sort
t2) = [Sort] -> Sort -> (Sort, [Sort])
go (Sort
t2forall a. a -> [a] -> [a]
:[Sort]
stk) Sort
t1
    go [Sort]
stk Sort
t            = (Sort
t, [Sort]
stk)

--------------------------------------------------------------------------------
-- | 'orderDeclarations' sorts the data declarations such that each declarations
--   only refers to preceding ones.
--------------------------------------------------------------------------------
orderDeclarations :: [DataDecl] -> [[DataDecl]]
--------------------------------------------------------------------------------
orderDeclarations :: [DataDecl] -> [[DataDecl]]
orderDeclarations [DataDecl]
ds = {- reverse -} forall v a. Ord v => (a -> (v, [v])) -> [a] -> [[a]]
Misc.sccsWith DataDecl -> (FTycon, [FTycon])
f [DataDecl]
ds
  where
    dM :: HashMap FTycon DataDecl
dM               = forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
M.fromList [(DataDecl -> FTycon
ddTyCon DataDecl
d, DataDecl
d) | DataDecl
d <- [DataDecl]
ds]
    f :: DataDecl -> (FTycon, [FTycon])
f DataDecl
d              = (DataDecl -> FTycon
ddTyCon DataDecl
d, HashMap FTycon DataDecl -> DataDecl -> [FTycon]
dataDeclDeps HashMap FTycon DataDecl
dM DataDecl
d)

dataDeclDeps :: M.HashMap FTycon DataDecl -> DataDecl -> [FTycon]
dataDeclDeps :: HashMap FTycon DataDecl -> DataDecl -> [FTycon]
dataDeclDeps HashMap FTycon DataDecl
dM = forall a. (a -> Bool) -> [a] -> [a]
filter (forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
`M.member` HashMap FTycon DataDecl
dM) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> [a]
Misc.sortNub forall b c a. (b -> c) -> (a -> b) -> a -> c
. DataDecl -> [FTycon]
dataDeclFTycons

dataDeclFTycons :: DataDecl -> [FTycon]
dataDeclFTycons :: DataDecl -> [FTycon]
dataDeclFTycons = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap DataCtor -> [FTycon]
dataCtorFTycons forall b c a. (b -> c) -> (a -> b) -> a -> c
. DataDecl -> [DataCtor]
ddCtors

dataCtorFTycons :: DataCtor -> [FTycon]
dataCtorFTycons :: DataCtor -> [FTycon]
dataCtorFTycons = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap DataField -> [FTycon]
dataFieldFTycons forall b c a. (b -> c) -> (a -> b) -> a -> c
. DataCtor -> [DataField]
dcFields

dataFieldFTycons :: DataField -> [FTycon]
dataFieldFTycons :: DataField -> [FTycon]
dataFieldFTycons = Sort -> [FTycon]
sortFTycons forall b c a. (b -> c) -> (a -> b) -> a -> c
. DataField -> Sort
dfSort

sortFTycons :: Sort -> [FTycon]
sortFTycons :: Sort -> [FTycon]
sortFTycons = Sort -> [FTycon]
go
  where
    go :: Sort -> [FTycon]
go (FTC FTycon
c)       = [FTycon
c]
    go (FApp  Sort
t1 Sort
t2) = Sort -> [FTycon]
go Sort
t1 forall a. [a] -> [a] -> [a]
++ Sort -> [FTycon]
go Sort
t2
    go (FFunc Sort
t1 Sort
t2) = Sort -> [FTycon]
go Sort
t1 forall a. [a] -> [a] -> [a]
++ Sort -> [FTycon]
go Sort
t2
    go (FAbs Int
_ Sort
t)    = Sort -> [FTycon]
go Sort
t
    go Sort
_             = []