{-# LANGUAGE TypeFamilies #-}

-- | This module provides facilities for obtaining the types of
-- various Futhark constructs.  Typically, you will need to execute
-- these in a context where type information is available as a
-- 'Scope'; usually by using a monad that is an instance of
-- 'HasScope'.  The information is returned as a list of 'ExtType'
-- values - one for each of the values the Futhark construct returns.
-- Some constructs (such as subexpressions) can produce only a single
-- value, and their typing functions hence do not return a list.
--
-- Some representations may have more specialised facilities enabling
-- even more information - for example,
-- "Futhark.IR.Mem" exposes functionality for
-- also obtaining information about the storage location of results.
module Futhark.IR.Prop.TypeOf
  ( expExtType,
    expExtTypeSize,
    subExpType,
    subExpResType,
    basicOpType,
    mapType,

    -- * Return type
    module Futhark.IR.RetType,

    -- * Type environment
    module Futhark.IR.Prop.Scope,

    -- * Extensibility
    TypedOp (..),
  )
where

import Data.List.NonEmpty (NonEmpty (..))
import Futhark.IR.Prop.Constants
import Futhark.IR.Prop.Scope
import Futhark.IR.Prop.Types
import Futhark.IR.RetType
import Futhark.IR.Syntax

-- | The type of a subexpression.
subExpType :: HasScope t m => SubExp -> m Type
subExpType :: forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType (Constant PrimValue
val) = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall shape u. PrimType -> TypeBase shape u
Prim forall a b. (a -> b) -> a -> b
$ PrimValue -> PrimType
primValueType PrimValue
val
subExpType (Var VName
name) = forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
name

-- | Type type of a 'SubExpRes' - not that this might refer to names
-- bound in the body containing the result.
subExpResType :: HasScope t m => SubExpRes -> m Type
subExpResType :: forall {k} (t :: k) (m :: * -> *).
HasScope t m =>
SubExpRes -> m Type
subExpResType = forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType forall b c a. (b -> c) -> (a -> b) -> a -> c
. SubExpRes -> SubExp
resSubExp

-- | @mapType f arrts@ wraps each element in the return type of @f@ in
-- an array with size equal to the outermost dimension of the first
-- element of @arrts@.
mapType :: SubExp -> Lambda rep -> [Type]
mapType :: forall {k} (rep :: k). SubExp -> Lambda rep -> [Type]
mapType SubExp
outersize Lambda rep
f =
  [ forall shape u_unused u.
ArrayShape shape =>
TypeBase shape u_unused -> shape -> u -> TypeBase shape u
arrayOf Type
t (forall d. [d] -> ShapeBase d
Shape [SubExp
outersize]) NoUniqueness
NoUniqueness
    | Type
t <- forall {k} (rep :: k). Lambda rep -> [Type]
lambdaReturnType Lambda rep
f
  ]

-- | The type of a primitive operation.
basicOpType :: HasScope rep m => BasicOp -> m [Type]
basicOpType :: forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
BasicOp -> m [Type]
basicOpType (SubExp SubExp
se) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType SubExp
se
basicOpType (Opaque OpaqueOp
_ SubExp
se) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType SubExp
se
basicOpType (ArrayLit [SubExp]
es Type
rt) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u_unused u.
ArrayShape shape =>
TypeBase shape u_unused -> shape -> u -> TypeBase shape u
arrayOf Type
rt (forall d. [d] -> ShapeBase d
Shape [SubExp
n]) NoUniqueness
NoUniqueness]
  where
    n :: SubExp
n = IntType -> Integer -> SubExp
intConst IntType
Int64 forall a b. (a -> b) -> a -> b
$ forall a. Integral a => a -> Integer
toInteger forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t a -> Int
length [SubExp]
es
basicOpType (BinOp BinOp
bop SubExp
_ SubExp
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u. PrimType -> TypeBase shape u
Prim forall a b. (a -> b) -> a -> b
$ BinOp -> PrimType
binOpType BinOp
bop]
basicOpType (UnOp UnOp
_ SubExp
x) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType SubExp
x
basicOpType CmpOp {} =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u. PrimType -> TypeBase shape u
Prim PrimType
Bool]
basicOpType (ConvOp ConvOp
conv SubExp
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u. PrimType -> TypeBase shape u
Prim forall a b. (a -> b) -> a -> b
$ forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ ConvOp -> (PrimType, PrimType)
convOpType ConvOp
conv]
basicOpType (Index VName
ident Slice SubExp
slice) =
  Type -> [Type]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
ident
  where
    result :: Type -> [Type]
result Type
t = [forall shape u. PrimType -> TypeBase shape u
Prim (forall shape u. TypeBase shape u -> PrimType
elemType Type
t) Type -> Shape -> Type
`arrayOfShape` Shape
shape]
    shape :: Shape
shape = forall d. [d] -> ShapeBase d
Shape forall a b. (a -> b) -> a -> b
$ forall d. Slice d -> [d]
sliceDims Slice SubExp
slice
basicOpType (Update Safety
_ VName
src Slice SubExp
_ SubExp
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
src
basicOpType (FlatIndex VName
ident FlatSlice SubExp
slice) =
  Type -> [Type]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
ident
  where
    result :: Type -> [Type]
result Type
t = [forall shape u. PrimType -> TypeBase shape u
Prim (forall shape u. TypeBase shape u -> PrimType
elemType Type
t) Type -> Shape -> Type
`arrayOfShape` Shape
shape]
    shape :: Shape
shape = forall d. [d] -> ShapeBase d
Shape forall a b. (a -> b) -> a -> b
$ forall d. FlatSlice d -> [d]
flatSliceDims FlatSlice SubExp
slice
basicOpType (FlatUpdate VName
src FlatSlice SubExp
_ VName
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
src
basicOpType (Iota SubExp
n SubExp
_ SubExp
_ IntType
et) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u_unused u.
ArrayShape shape =>
TypeBase shape u_unused -> shape -> u -> TypeBase shape u
arrayOf (forall shape u. PrimType -> TypeBase shape u
Prim (IntType -> PrimType
IntType IntType
et)) (forall d. [d] -> ShapeBase d
Shape [SubExp
n]) NoUniqueness
NoUniqueness]
basicOpType (Replicate (Shape []) SubExp
e) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType SubExp
e
basicOpType (Replicate Shape
shape SubExp
e) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip Type -> Shape -> Type
arrayOfShape Shape
shape forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (t :: k) (m :: * -> *). HasScope t m => SubExp -> m Type
subExpType SubExp
e
basicOpType (Scratch PrimType
t [SubExp]
shape) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u_unused u.
ArrayShape shape =>
TypeBase shape u_unused -> shape -> u -> TypeBase shape u
arrayOf (forall shape u. PrimType -> TypeBase shape u
Prim PrimType
t) (forall d. [d] -> ShapeBase d
Shape [SubExp]
shape) NoUniqueness
NoUniqueness]
basicOpType (Reshape ReshapeKind
_ (Shape []) VName
e) =
  forall {shape} {u} {shape} {u}.
TypeBase shape u -> [TypeBase shape u]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
e
  where
    result :: TypeBase shape u -> [TypeBase shape u]
result TypeBase shape u
t = [forall shape u. PrimType -> TypeBase shape u
Prim forall a b. (a -> b) -> a -> b
$ forall shape u. TypeBase shape u -> PrimType
elemType TypeBase shape u
t]
basicOpType (Reshape ReshapeKind
_ Shape
shape VName
e) =
  Type -> [Type]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
e
  where
    result :: Type -> [Type]
result Type
t = [Type
t forall newshape oldshape u.
ArrayShape newshape =>
TypeBase oldshape u -> newshape -> TypeBase newshape u
`setArrayShape` Shape
shape]
basicOpType (Rearrange [Int]
perm VName
e) =
  Type -> [Type]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
e
  where
    result :: Type -> [Type]
result Type
t = [[Int] -> Type -> Type
rearrangeType [Int]
perm Type
t]
basicOpType (Rotate [SubExp]
_ VName
e) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
e
basicOpType (Concat Int
i (VName
x :| [VName]
_) SubExp
ressize) =
  Type -> [Type]
result forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
x
  where
    result :: Type -> [Type]
result Type
xt = [forall d u.
ArrayShape (ShapeBase d) =>
Int -> TypeBase (ShapeBase d) u -> d -> TypeBase (ShapeBase d) u
setDimSize Int
i Type
xt SubExp
ressize]
basicOpType (Copy VName
v) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
v
basicOpType (Manifest [Int]
_ VName
v) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
v
basicOpType Assert {} =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure [forall shape u. PrimType -> TypeBase shape u
Prim PrimType
Unit]
basicOpType (UpdateAcc VName
v [SubExp]
_ [SubExp]
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType VName
v

-- | The type of an expression.
expExtType ::
  (HasScope rep m, TypedOp (Op rep)) =>
  Exp rep ->
  m [ExtType]
expExtType :: forall {k} (rep :: k) (m :: * -> *).
(HasScope rep m, TypedOp (Op rep)) =>
Exp rep -> m [ExtType]
expExtType (Apply Name
_ [(SubExp, Diet)]
_ [RetType rep]
rt (Safety, SrcLoc, [SrcLoc])
_) = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map (forall shape.
TypeBase shape Uniqueness -> TypeBase shape NoUniqueness
fromDecl forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall t. DeclExtTyped t => t -> DeclExtType
declExtTypeOf) [RetType rep]
rt
expExtType (Match [SubExp]
_ [Case (Body rep)]
_ Body rep
_ MatchDec (BranchType rep)
rt) = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall t. ExtTyped t => t -> ExtType
extTypeOf forall a b. (a -> b) -> a -> b
$ forall rt. MatchDec rt -> [rt]
matchReturns MatchDec (BranchType rep)
rt
expExtType (DoLoop [(FParam rep, SubExp)]
merge LoopForm rep
_ Body rep
_) =
  forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall dec. Typed dec => [Param dec] -> [ExtType]
loopExtType forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst [(FParam rep, SubExp)]
merge
expExtType (BasicOp BasicOp
op) = forall u. [TypeBase Shape u] -> [TypeBase ExtShape u]
staticShapes forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
BasicOp -> m [Type]
basicOpType BasicOp
op
expExtType (WithAcc [WithAccInput rep]
inputs Lambda rep
lam) =
  forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall u. [TypeBase Shape u] -> [TypeBase ExtShape u]
staticShapes forall a b. (a -> b) -> a -> b
$
    forall a. Semigroup a => a -> a -> a
(<>)
      forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall {k} {t :: * -> *} {f :: * -> *} {rep :: k} {a} {c}.
(Traversable t, HasScope rep f) =>
(a, t VName, c) -> f (t Type)
inputType [WithAccInput rep]
inputs)
      forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall a. Int -> [a] -> [a]
drop Int
num_accs (forall {k} (rep :: k). Lambda rep -> [Type]
lambdaReturnType Lambda rep
lam))
  where
    inputType :: (a, t VName, c) -> f (t Type)
inputType (a
_, t VName
arrs, c
_) = forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall {k} (rep :: k) (m :: * -> *).
HasScope rep m =>
VName -> m Type
lookupType t VName
arrs
    num_accs :: Int
num_accs = forall (t :: * -> *) a. Foldable t => t a -> Int
length [WithAccInput rep]
inputs
expExtType (Op Op rep
op) = forall op {k} (t :: k) (m :: * -> *).
(TypedOp op, HasScope t m) =>
op -> m [ExtType]
opType Op rep
op

-- | The number of values returned by an expression.
expExtTypeSize ::
  (RepTypes rep, TypedOp (Op rep)) =>
  Exp rep ->
  Int
expExtTypeSize :: forall {k} (rep :: k).
(RepTypes rep, TypedOp (Op rep)) =>
Exp rep -> Int
expExtTypeSize = forall (t :: * -> *) a. Foldable t => t a -> Int
length forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (rep :: k) a. FeelBad rep a -> a
feelBad forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (rep :: k) (m :: * -> *).
(HasScope rep m, TypedOp (Op rep)) =>
Exp rep -> m [ExtType]
expExtType

-- FIXME, this is a horrible quick hack.
newtype FeelBad rep a = FeelBad {forall {k} (rep :: k) a. FeelBad rep a -> a
feelBad :: a}

instance Functor (FeelBad rep) where
  fmap :: forall a b. (a -> b) -> FeelBad rep a -> FeelBad rep b
fmap a -> b
f = forall {k} (rep :: k) a. a -> FeelBad rep a
FeelBad forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (rep :: k) a. FeelBad rep a -> a
feelBad

instance Applicative (FeelBad rep) where
  pure :: forall a. a -> FeelBad rep a
pure = forall {k} (rep :: k) a. a -> FeelBad rep a
FeelBad
  FeelBad rep (a -> b)
f <*> :: forall a b. FeelBad rep (a -> b) -> FeelBad rep a -> FeelBad rep b
<*> FeelBad rep a
x = forall {k} (rep :: k) a. a -> FeelBad rep a
FeelBad forall a b. (a -> b) -> a -> b
$ forall {k} (rep :: k) a. FeelBad rep a -> a
feelBad FeelBad rep (a -> b)
f forall a b. (a -> b) -> a -> b
$ forall {k} (rep :: k) a. FeelBad rep a -> a
feelBad FeelBad rep a
x

instance RepTypes rep => HasScope rep (FeelBad rep) where
  lookupType :: VName -> FeelBad rep Type
lookupType = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall shape u. PrimType -> TypeBase shape u
Prim forall a b. (a -> b) -> a -> b
$ IntType -> PrimType
IntType IntType
Int64
  askScope :: FeelBad rep (Scope rep)
askScope = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a. Monoid a => a
mempty

-- | Given the parameters of a loop, produce the return type.
loopExtType :: Typed dec => [Param dec] -> [ExtType]
loopExtType :: forall dec. Typed dec => [Param dec] -> [ExtType]
loopExtType [Param dec]
params =
  [VName] -> [ExtType] -> [ExtType]
existentialiseExtTypes [VName]
inaccessible forall a b. (a -> b) -> a -> b
$ forall u. [TypeBase Shape u] -> [TypeBase ExtShape u]
staticShapes forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall t. Typed t => t -> Type
typeOf [Param dec]
params
  where
    inaccessible :: [VName]
inaccessible = forall a b. (a -> b) -> [a] -> [b]
map forall dec. Param dec -> VName
paramName [Param dec]
params

-- | Any operation must define an instance of this class, which
-- describes the type of the operation (at the value level).
class TypedOp op where
  opType :: HasScope t m => op -> m [ExtType]

instance TypedOp () where
  opType :: forall {k} (t :: k) (m :: * -> *).
HasScope t m =>
() -> m [ExtType]
opType () = forall (f :: * -> *) a. Applicative f => a -> f a
pure []