{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE OverloadedStrings #-}
module Tokstyle.Analysis.PointsTo.Types
( MemLoc (..)
, IMemLoc (..)
, MemLocPool (..)
, Context
, FunctionSummary(..)
, GlobalEnv(..)
, PointsToFact(..)
, RelevantInputState(..)
, PointsToContext(..)
, PointsToAnalysis
, intern
) where
import Control.Monad.State.Strict (State, get, put)
import Data.Hashable (Hashable)
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Set (Set)
import Data.Text (Text)
import GHC.Generics (Generic)
import qualified Language.Cimple as C
import Tokstyle.Analysis.Scope (ScopedId)
import Tokstyle.Analysis.VTable (VTableMap)
import Tokstyle.Common.TypeSystem (TypeSystem)
data MemLoc
= StackLoc { MemLoc -> ScopedId
locId :: ScopedId }
| HeapLoc { MemLoc -> Text
allocSite :: Text }
| GlobalVarLoc { locId :: ScopedId }
| ExternalParamLoc { MemLoc -> Text
funcName :: Text, MemLoc -> Text
paramName :: Text }
| FieldLoc { MemLoc -> MemLoc
baseLoc :: MemLoc, MemLoc -> Text
fieldName :: Text }
| NullLoc
| UnknownLoc
deriving (MemLoc -> MemLoc -> Bool
(MemLoc -> MemLoc -> Bool)
-> (MemLoc -> MemLoc -> Bool) -> Eq MemLoc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: MemLoc -> MemLoc -> Bool
$c/= :: MemLoc -> MemLoc -> Bool
== :: MemLoc -> MemLoc -> Bool
$c== :: MemLoc -> MemLoc -> Bool
Eq, Eq MemLoc
Eq MemLoc
-> (MemLoc -> MemLoc -> Ordering)
-> (MemLoc -> MemLoc -> Bool)
-> (MemLoc -> MemLoc -> Bool)
-> (MemLoc -> MemLoc -> Bool)
-> (MemLoc -> MemLoc -> Bool)
-> (MemLoc -> MemLoc -> MemLoc)
-> (MemLoc -> MemLoc -> MemLoc)
-> Ord MemLoc
MemLoc -> MemLoc -> Bool
MemLoc -> MemLoc -> Ordering
MemLoc -> MemLoc -> MemLoc
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: MemLoc -> MemLoc -> MemLoc
$cmin :: MemLoc -> MemLoc -> MemLoc
max :: MemLoc -> MemLoc -> MemLoc
$cmax :: MemLoc -> MemLoc -> MemLoc
>= :: MemLoc -> MemLoc -> Bool
$c>= :: MemLoc -> MemLoc -> Bool
> :: MemLoc -> MemLoc -> Bool
$c> :: MemLoc -> MemLoc -> Bool
<= :: MemLoc -> MemLoc -> Bool
$c<= :: MemLoc -> MemLoc -> Bool
< :: MemLoc -> MemLoc -> Bool
$c< :: MemLoc -> MemLoc -> Bool
compare :: MemLoc -> MemLoc -> Ordering
$ccompare :: MemLoc -> MemLoc -> Ordering
$cp1Ord :: Eq MemLoc
Ord, Int -> MemLoc -> ShowS
[MemLoc] -> ShowS
MemLoc -> String
(Int -> MemLoc -> ShowS)
-> (MemLoc -> String) -> ([MemLoc] -> ShowS) -> Show MemLoc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [MemLoc] -> ShowS
$cshowList :: [MemLoc] -> ShowS
show :: MemLoc -> String
$cshow :: MemLoc -> String
showsPrec :: Int -> MemLoc -> ShowS
$cshowsPrec :: Int -> MemLoc -> ShowS
Show, (forall x. MemLoc -> Rep MemLoc x)
-> (forall x. Rep MemLoc x -> MemLoc) -> Generic MemLoc
forall x. Rep MemLoc x -> MemLoc
forall x. MemLoc -> Rep MemLoc x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep MemLoc x -> MemLoc
$cfrom :: forall x. MemLoc -> Rep MemLoc x
Generic)
instance Hashable MemLoc
newtype IMemLoc = IMemLoc { IMemLoc -> Int
unIMemLoc :: Int }
deriving (IMemLoc -> IMemLoc -> Bool
(IMemLoc -> IMemLoc -> Bool)
-> (IMemLoc -> IMemLoc -> Bool) -> Eq IMemLoc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: IMemLoc -> IMemLoc -> Bool
$c/= :: IMemLoc -> IMemLoc -> Bool
== :: IMemLoc -> IMemLoc -> Bool
$c== :: IMemLoc -> IMemLoc -> Bool
Eq, Eq IMemLoc
Eq IMemLoc
-> (IMemLoc -> IMemLoc -> Ordering)
-> (IMemLoc -> IMemLoc -> Bool)
-> (IMemLoc -> IMemLoc -> Bool)
-> (IMemLoc -> IMemLoc -> Bool)
-> (IMemLoc -> IMemLoc -> Bool)
-> (IMemLoc -> IMemLoc -> IMemLoc)
-> (IMemLoc -> IMemLoc -> IMemLoc)
-> Ord IMemLoc
IMemLoc -> IMemLoc -> Bool
IMemLoc -> IMemLoc -> Ordering
IMemLoc -> IMemLoc -> IMemLoc
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: IMemLoc -> IMemLoc -> IMemLoc
$cmin :: IMemLoc -> IMemLoc -> IMemLoc
max :: IMemLoc -> IMemLoc -> IMemLoc
$cmax :: IMemLoc -> IMemLoc -> IMemLoc
>= :: IMemLoc -> IMemLoc -> Bool
$c>= :: IMemLoc -> IMemLoc -> Bool
> :: IMemLoc -> IMemLoc -> Bool
$c> :: IMemLoc -> IMemLoc -> Bool
<= :: IMemLoc -> IMemLoc -> Bool
$c<= :: IMemLoc -> IMemLoc -> Bool
< :: IMemLoc -> IMemLoc -> Bool
$c< :: IMemLoc -> IMemLoc -> Bool
compare :: IMemLoc -> IMemLoc -> Ordering
$ccompare :: IMemLoc -> IMemLoc -> Ordering
$cp1Ord :: Eq IMemLoc
Ord, Int -> IMemLoc -> ShowS
[IMemLoc] -> ShowS
IMemLoc -> String
(Int -> IMemLoc -> ShowS)
-> (IMemLoc -> String) -> ([IMemLoc] -> ShowS) -> Show IMemLoc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [IMemLoc] -> ShowS
$cshowList :: [IMemLoc] -> ShowS
show :: IMemLoc -> String
$cshow :: IMemLoc -> String
showsPrec :: Int -> IMemLoc -> ShowS
$cshowsPrec :: Int -> IMemLoc -> ShowS
Show, Eq IMemLoc
Eq IMemLoc
-> (Int -> IMemLoc -> Int) -> (IMemLoc -> Int) -> Hashable IMemLoc
Int -> IMemLoc -> Int
IMemLoc -> Int
forall a. Eq a -> (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: IMemLoc -> Int
$chash :: IMemLoc -> Int
hashWithSalt :: Int -> IMemLoc -> Int
$chashWithSalt :: Int -> IMemLoc -> Int
$cp1Hashable :: Eq IMemLoc
Hashable)
data MemLocPool = MemLocPool
{ MemLocPool -> Int
nextMemLocId :: !Int
, MemLocPool -> Map MemLoc IMemLoc
memLocToId :: !(Map MemLoc IMemLoc)
, MemLocPool -> IntMap MemLoc
idToMemLoc :: !(IntMap MemLoc)
, MemLocPool -> IntMap IntSet
fieldIndex :: !(IntMap IntSet)
} deriving (Int -> MemLocPool -> ShowS
[MemLocPool] -> ShowS
MemLocPool -> String
(Int -> MemLocPool -> ShowS)
-> (MemLocPool -> String)
-> ([MemLocPool] -> ShowS)
-> Show MemLocPool
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [MemLocPool] -> ShowS
$cshowList :: [MemLocPool] -> ShowS
show :: MemLocPool -> String
$cshow :: MemLocPool -> String
showsPrec :: Int -> MemLocPool -> ShowS
$cshowsPrec :: Int -> MemLocPool -> ShowS
Show)
type PointsToAnalysis = State MemLocPool
intern :: MemLoc -> PointsToAnalysis IMemLoc
intern :: MemLoc -> PointsToAnalysis IMemLoc
intern MemLoc
loc = do
MemLocPool
pool <- StateT MemLocPool Identity MemLocPool
forall s (m :: * -> *). MonadState s m => m s
get
case MemLoc -> Map MemLoc IMemLoc -> Maybe IMemLoc
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup MemLoc
loc (MemLocPool -> Map MemLoc IMemLoc
memLocToId MemLocPool
pool) of
Just IMemLoc
iloc -> IMemLoc -> PointsToAnalysis IMemLoc
forall (m :: * -> *) a. Monad m => a -> m a
return IMemLoc
iloc
Maybe IMemLoc
Nothing -> do
Maybe IMemLoc
maybeBaseIloc <- case MemLoc
loc of
FieldLoc MemLoc
base Text
_ -> IMemLoc -> Maybe IMemLoc
forall a. a -> Maybe a
Just (IMemLoc -> Maybe IMemLoc)
-> PointsToAnalysis IMemLoc
-> StateT MemLocPool Identity (Maybe IMemLoc)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MemLoc -> PointsToAnalysis IMemLoc
intern MemLoc
base
MemLoc
_ -> Maybe IMemLoc -> StateT MemLocPool Identity (Maybe IMemLoc)
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe IMemLoc
forall a. Maybe a
Nothing
MemLocPool
pool' <- StateT MemLocPool Identity MemLocPool
forall s (m :: * -> *). MonadState s m => m s
get
let nextId :: Int
nextId = MemLocPool -> Int
nextMemLocId MemLocPool
pool'
let iloc :: IMemLoc
iloc = Int -> IMemLoc
IMemLoc Int
nextId
let newFieldIndex :: IntMap IntSet
newFieldIndex = case Maybe IMemLoc
maybeBaseIloc of
Just IMemLoc
baseIloc -> (IntSet -> IntSet -> IntSet)
-> Int -> IntSet -> IntMap IntSet -> IntMap IntSet
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IntMap.insertWith IntSet -> IntSet -> IntSet
IntSet.union (IMemLoc -> Int
unIMemLoc IMemLoc
baseIloc) (Int -> IntSet
IntSet.singleton Int
nextId) (MemLocPool -> IntMap IntSet
fieldIndex MemLocPool
pool')
Maybe IMemLoc
Nothing -> MemLocPool -> IntMap IntSet
fieldIndex MemLocPool
pool'
MemLocPool -> StateT MemLocPool Identity ()
forall s (m :: * -> *). MonadState s m => s -> m ()
put (MemLocPool -> StateT MemLocPool Identity ())
-> MemLocPool -> StateT MemLocPool Identity ()
forall a b. (a -> b) -> a -> b
$ MemLocPool
pool'
{ nextMemLocId :: Int
nextMemLocId = Int
nextId Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
, memLocToId :: Map MemLoc IMemLoc
memLocToId = MemLoc -> IMemLoc -> Map MemLoc IMemLoc -> Map MemLoc IMemLoc
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert MemLoc
loc IMemLoc
iloc (MemLocPool -> Map MemLoc IMemLoc
memLocToId MemLocPool
pool')
, idToMemLoc :: IntMap MemLoc
idToMemLoc = Int -> MemLoc -> IntMap MemLoc -> IntMap MemLoc
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert Int
nextId MemLoc
loc (MemLocPool -> IntMap MemLoc
idToMemLoc MemLocPool
pool')
, fieldIndex :: IntMap IntSet
fieldIndex = IntMap IntSet
newFieldIndex
}
IMemLoc -> PointsToAnalysis IMemLoc
forall (m :: * -> *) a. Monad m => a -> m a
return IMemLoc
iloc
type Context = [ScopedId]
data FunctionSummary = FunctionSummary
{ FunctionSummary -> IntSet
fsReturnValue :: !IntSet
, FunctionSummary -> Map Int IntSet
fsParamEffects :: !(Map Int IntSet)
, FunctionSummary -> IntMap IntSet
fsMemEffects :: !(IntMap IntSet)
} deriving (Int -> FunctionSummary -> ShowS
[FunctionSummary] -> ShowS
FunctionSummary -> String
(Int -> FunctionSummary -> ShowS)
-> (FunctionSummary -> String)
-> ([FunctionSummary] -> ShowS)
-> Show FunctionSummary
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FunctionSummary] -> ShowS
$cshowList :: [FunctionSummary] -> ShowS
show :: FunctionSummary -> String
$cshow :: FunctionSummary -> String
showsPrec :: Int -> FunctionSummary -> ShowS
$cshowsPrec :: Int -> FunctionSummary -> ShowS
Show, FunctionSummary -> FunctionSummary -> Bool
(FunctionSummary -> FunctionSummary -> Bool)
-> (FunctionSummary -> FunctionSummary -> Bool)
-> Eq FunctionSummary
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FunctionSummary -> FunctionSummary -> Bool
$c/= :: FunctionSummary -> FunctionSummary -> Bool
== :: FunctionSummary -> FunctionSummary -> Bool
$c== :: FunctionSummary -> FunctionSummary -> Bool
Eq)
data PointsToFact = PointsToFact
{ PointsToFact -> Map ScopedId IntSet
varMap :: !(Map ScopedId IntSet)
, PointsToFact -> IntMap IntSet
memMap :: !(IntMap IntSet)
, PointsToFact -> IntSet
unknownWrites :: !IntSet
} deriving (Int -> PointsToFact -> ShowS
[PointsToFact] -> ShowS
PointsToFact -> String
(Int -> PointsToFact -> ShowS)
-> (PointsToFact -> String)
-> ([PointsToFact] -> ShowS)
-> Show PointsToFact
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PointsToFact] -> ShowS
$cshowList :: [PointsToFact] -> ShowS
show :: PointsToFact -> String
$cshow :: PointsToFact -> String
showsPrec :: Int -> PointsToFact -> ShowS
$cshowsPrec :: Int -> PointsToFact -> ShowS
Show, PointsToFact -> PointsToFact -> Bool
(PointsToFact -> PointsToFact -> Bool)
-> (PointsToFact -> PointsToFact -> Bool) -> Eq PointsToFact
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PointsToFact -> PointsToFact -> Bool
$c/= :: PointsToFact -> PointsToFact -> Bool
== :: PointsToFact -> PointsToFact -> Bool
$c== :: PointsToFact -> PointsToFact -> Bool
Eq, Eq PointsToFact
Eq PointsToFact
-> (PointsToFact -> PointsToFact -> Ordering)
-> (PointsToFact -> PointsToFact -> Bool)
-> (PointsToFact -> PointsToFact -> Bool)
-> (PointsToFact -> PointsToFact -> Bool)
-> (PointsToFact -> PointsToFact -> Bool)
-> (PointsToFact -> PointsToFact -> PointsToFact)
-> (PointsToFact -> PointsToFact -> PointsToFact)
-> Ord PointsToFact
PointsToFact -> PointsToFact -> Bool
PointsToFact -> PointsToFact -> Ordering
PointsToFact -> PointsToFact -> PointsToFact
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: PointsToFact -> PointsToFact -> PointsToFact
$cmin :: PointsToFact -> PointsToFact -> PointsToFact
max :: PointsToFact -> PointsToFact -> PointsToFact
$cmax :: PointsToFact -> PointsToFact -> PointsToFact
>= :: PointsToFact -> PointsToFact -> Bool
$c>= :: PointsToFact -> PointsToFact -> Bool
> :: PointsToFact -> PointsToFact -> Bool
$c> :: PointsToFact -> PointsToFact -> Bool
<= :: PointsToFact -> PointsToFact -> Bool
$c<= :: PointsToFact -> PointsToFact -> Bool
< :: PointsToFact -> PointsToFact -> Bool
$c< :: PointsToFact -> PointsToFact -> Bool
compare :: PointsToFact -> PointsToFact -> Ordering
$ccompare :: PointsToFact -> PointsToFact -> Ordering
$cp1Ord :: Eq PointsToFact
Ord)
newtype RelevantInputState = RelevantInputState PointsToFact
deriving (Int -> RelevantInputState -> ShowS
[RelevantInputState] -> ShowS
RelevantInputState -> String
(Int -> RelevantInputState -> ShowS)
-> (RelevantInputState -> String)
-> ([RelevantInputState] -> ShowS)
-> Show RelevantInputState
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RelevantInputState] -> ShowS
$cshowList :: [RelevantInputState] -> ShowS
show :: RelevantInputState -> String
$cshow :: RelevantInputState -> String
showsPrec :: Int -> RelevantInputState -> ShowS
$cshowsPrec :: Int -> RelevantInputState -> ShowS
Show, RelevantInputState -> RelevantInputState -> Bool
(RelevantInputState -> RelevantInputState -> Bool)
-> (RelevantInputState -> RelevantInputState -> Bool)
-> Eq RelevantInputState
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RelevantInputState -> RelevantInputState -> Bool
$c/= :: RelevantInputState -> RelevantInputState -> Bool
== :: RelevantInputState -> RelevantInputState -> Bool
$c== :: RelevantInputState -> RelevantInputState -> Bool
Eq, Eq RelevantInputState
Eq RelevantInputState
-> (RelevantInputState -> RelevantInputState -> Ordering)
-> (RelevantInputState -> RelevantInputState -> Bool)
-> (RelevantInputState -> RelevantInputState -> Bool)
-> (RelevantInputState -> RelevantInputState -> Bool)
-> (RelevantInputState -> RelevantInputState -> Bool)
-> (RelevantInputState -> RelevantInputState -> RelevantInputState)
-> (RelevantInputState -> RelevantInputState -> RelevantInputState)
-> Ord RelevantInputState
RelevantInputState -> RelevantInputState -> Bool
RelevantInputState -> RelevantInputState -> Ordering
RelevantInputState -> RelevantInputState -> RelevantInputState
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: RelevantInputState -> RelevantInputState -> RelevantInputState
$cmin :: RelevantInputState -> RelevantInputState -> RelevantInputState
max :: RelevantInputState -> RelevantInputState -> RelevantInputState
$cmax :: RelevantInputState -> RelevantInputState -> RelevantInputState
>= :: RelevantInputState -> RelevantInputState -> Bool
$c>= :: RelevantInputState -> RelevantInputState -> Bool
> :: RelevantInputState -> RelevantInputState -> Bool
$c> :: RelevantInputState -> RelevantInputState -> Bool
<= :: RelevantInputState -> RelevantInputState -> Bool
$c<= :: RelevantInputState -> RelevantInputState -> Bool
< :: RelevantInputState -> RelevantInputState -> Bool
$c< :: RelevantInputState -> RelevantInputState -> Bool
compare :: RelevantInputState -> RelevantInputState -> Ordering
$ccompare :: RelevantInputState -> RelevantInputState -> Ordering
$cp1Ord :: Eq RelevantInputState
Ord)
newtype GlobalEnv = GlobalEnv (Map (ScopedId, RelevantInputState) (FunctionSummary, PointsToFact))
deriving (Int -> GlobalEnv -> ShowS
[GlobalEnv] -> ShowS
GlobalEnv -> String
(Int -> GlobalEnv -> ShowS)
-> (GlobalEnv -> String)
-> ([GlobalEnv] -> ShowS)
-> Show GlobalEnv
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [GlobalEnv] -> ShowS
$cshowList :: [GlobalEnv] -> ShowS
show :: GlobalEnv -> String
$cshow :: GlobalEnv -> String
showsPrec :: Int -> GlobalEnv -> ShowS
$cshowsPrec :: Int -> GlobalEnv -> ShowS
Show, GlobalEnv -> GlobalEnv -> Bool
(GlobalEnv -> GlobalEnv -> Bool)
-> (GlobalEnv -> GlobalEnv -> Bool) -> Eq GlobalEnv
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: GlobalEnv -> GlobalEnv -> Bool
$c/= :: GlobalEnv -> GlobalEnv -> Bool
== :: GlobalEnv -> GlobalEnv -> Bool
$c== :: GlobalEnv -> GlobalEnv -> Bool
Eq)
data PointsToContext l = PointsToContext
{ PointsToContext l -> String
pcFilePath :: FilePath
, PointsToContext l -> TypeSystem
pcTypeSystem :: TypeSystem
, PointsToContext l -> VTableMap
pcVTableMap :: VTableMap
, PointsToContext l -> GlobalEnv
pcGlobalEnv :: GlobalEnv
, PointsToContext l -> Map ScopedId [Node (Lexeme ScopedId)]
pcFuncs :: Map ScopedId [C.Node (C.Lexeme ScopedId)]
, PointsToContext l -> ScopedId
pcCurrentFunc :: ScopedId
, PointsToContext l -> Map ScopedId (Node (Lexeme ScopedId))
pcVarTypes :: Map ScopedId (C.Node (C.Lexeme ScopedId))
}