-- | Type checker building blocks that do not involve unification.
module Language.Futhark.TypeChecker.Types
  ( checkTypeExp,
    renameRetType,
    checkForDuplicateNames,
    checkTypeParams,
    typeParamToArg,
    Subst (..),
    substFromAbbr,
    TypeSubs,
    Substitutable (..),
    substTypesAny,

    -- * Witnesses
    mustBeExplicitInType,
    mustBeExplicitInBinding,
    determineSizeWitnesses,
  )
where

import Control.Monad
import Control.Monad.Identity
import Control.Monad.Reader
import Control.Monad.State
import Data.Bifunctor
import Data.List (find, foldl', sort, unzip4, (\\))
import Data.Map.Strict qualified as M
import Data.Set qualified as S
import Futhark.Util (nubOrd)
import Futhark.Util.Pretty
import Language.Futhark
import Language.Futhark.Traversals
import Language.Futhark.TypeChecker.Monad

mustBeExplicitAux :: StructType -> M.Map VName Bool
mustBeExplicitAux :: StructType -> Map VName Bool
mustBeExplicitAux StructType
t =
  State (Map VName Bool) (TypeBase () NoUniqueness)
-> Map VName Bool -> Map VName Bool
forall s a. State s a -> s -> s
execState ((Set VName
 -> DimPos
 -> ExpBase Info VName
 -> StateT (Map VName Bool) Identity ())
-> StructType -> State (Map VName Bool) (TypeBase () NoUniqueness)
forall (f :: * -> *) fdim tdim als.
Applicative f =>
(Set VName -> DimPos -> fdim -> f tdim)
-> TypeBase fdim als -> f (TypeBase tdim als)
traverseDims Set VName
-> DimPos
-> ExpBase Info VName
-> StateT (Map VName Bool) Identity ()
forall {m :: * -> *}.
MonadState (Map VName Bool) m =>
Set VName -> DimPos -> ExpBase Info VName -> m ()
onDim StructType
t) Map VName Bool
forall a. Monoid a => a
mempty
  where
    onDim :: Set VName -> DimPos -> ExpBase Info VName -> m ()
onDim Set VName
bound DimPos
_ (Var QualName VName
d Info StructType
_ SrcLoc
_)
      | QualName VName -> VName
forall vn. QualName vn -> vn
qualLeaf QualName VName
d VName -> Set VName -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set VName
bound =
          (Map VName Bool -> Map VName Bool) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Map VName Bool -> Map VName Bool) -> m ())
-> (Map VName Bool -> Map VName Bool) -> m ()
forall a b. (a -> b) -> a -> b
$ \Map VName Bool
s -> (Bool -> Bool -> Bool)
-> VName -> Bool -> Map VName Bool -> Map VName Bool
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith Bool -> Bool -> Bool
(&&) (QualName VName -> VName
forall vn. QualName vn -> vn
qualLeaf QualName VName
d) Bool
False Map VName Bool
s
    onDim Set VName
_ DimPos
PosImmediate (Var QualName VName
d Info StructType
_ SrcLoc
_) =
      (Map VName Bool -> Map VName Bool) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Map VName Bool -> Map VName Bool) -> m ())
-> (Map VName Bool -> Map VName Bool) -> m ()
forall a b. (a -> b) -> a -> b
$ \Map VName Bool
s -> (Bool -> Bool -> Bool)
-> VName -> Bool -> Map VName Bool -> Map VName Bool
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith Bool -> Bool -> Bool
(&&) (QualName VName -> VName
forall vn. QualName vn -> vn
qualLeaf QualName VName
d) Bool
False Map VName Bool
s
    onDim Set VName
_ DimPos
_ ExpBase Info VName
e =
      (Map VName Bool -> Map VName Bool) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Map VName Bool -> Map VName Bool) -> m ())
-> (Map VName Bool -> Map VName Bool) -> m ()
forall a b. (a -> b) -> a -> b
$ (Map VName Bool -> Set VName -> Map VName Bool)
-> Set VName -> Map VName Bool -> Map VName Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((VName -> Map VName Bool -> Map VName Bool)
-> Map VName Bool -> Set VName -> Map VName Bool
forall a b. (a -> b -> b) -> b -> Set a -> b
S.foldr (\VName
v -> (Bool -> Bool -> Bool)
-> VName -> Bool -> Map VName Bool -> Map VName Bool
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith Bool -> Bool -> Bool
(&&) VName
v Bool
True)) (Set VName -> Map VName Bool -> Map VName Bool)
-> Set VName -> Map VName Bool -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ FV -> Set VName
fvVars (FV -> Set VName) -> FV -> Set VName
forall a b. (a -> b) -> a -> b
$ ExpBase Info VName -> FV
freeInExp ExpBase Info VName
e

-- | Determine which of the sizes in a type are used as sizes outside
-- of functions in the type, and which are not.  The former are said
-- to be "witnessed" by this type, while the latter are not.  In
-- practice, the latter means that the actual sizes must come from
-- somewhere else.
determineSizeWitnesses :: StructType -> (S.Set VName, S.Set VName)
determineSizeWitnesses :: StructType -> (Set VName, Set VName)
determineSizeWitnesses StructType
t =
  (Map VName Bool -> Set VName)
-> (Map VName Bool -> Set VName)
-> (Map VName Bool, Map VName Bool)
-> (Set VName, Set VName)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap ([VName] -> Set VName
forall a. Ord a => [a] -> Set a
S.fromList ([VName] -> Set VName)
-> (Map VName Bool -> [VName]) -> Map VName Bool -> Set VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map VName Bool -> [VName]
forall k a. Map k a -> [k]
M.keys) ([VName] -> Set VName
forall a. Ord a => [a] -> Set a
S.fromList ([VName] -> Set VName)
-> (Map VName Bool -> [VName]) -> Map VName Bool -> Set VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map VName Bool -> [VName]
forall k a. Map k a -> [k]
M.keys) ((Map VName Bool, Map VName Bool) -> (Set VName, Set VName))
-> (Map VName Bool, Map VName Bool) -> (Set VName, Set VName)
forall a b. (a -> b) -> a -> b
$
    (Bool -> Bool)
-> Map VName Bool -> (Map VName Bool, Map VName Bool)
forall a k. (a -> Bool) -> Map k a -> (Map k a, Map k a)
M.partition Bool -> Bool
not (Map VName Bool -> (Map VName Bool, Map VName Bool))
-> Map VName Bool -> (Map VName Bool, Map VName Bool)
forall a b. (a -> b) -> a -> b
$
      StructType -> Map VName Bool
mustBeExplicitAux StructType
t

-- | Figure out which of the sizes in a binding type must be passed
-- explicitly, because their first use is as something else than just
-- an array dimension.
mustBeExplicitInBinding :: StructType -> S.Set VName
mustBeExplicitInBinding :: StructType -> Set VName
mustBeExplicitInBinding StructType
bind_t =
  let ([TypeBase (ExpBase Info VName) Diet]
ts, StructType
ret) = StructType -> ([TypeBase (ExpBase Info VName) Diet], StructType)
forall dim as.
TypeBase dim as -> ([TypeBase dim Diet], TypeBase dim NoUniqueness)
unfoldFunType StructType
bind_t
      alsoRet :: Map VName Bool -> Map VName Bool
alsoRet = (Bool -> Bool -> Bool)
-> Map VName Bool -> Map VName Bool -> Map VName Bool
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith Bool -> Bool -> Bool
(&&) (Map VName Bool -> Map VName Bool -> Map VName Bool)
-> Map VName Bool -> Map VName Bool -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ [(VName, Bool)] -> Map VName Bool
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(VName, Bool)] -> Map VName Bool)
-> [(VName, Bool)] -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ (VName -> (VName, Bool)) -> [VName] -> [(VName, Bool)]
forall a b. (a -> b) -> [a] -> [b]
map (,Bool
True) (Set VName -> [VName]
forall a. Set a -> [a]
S.toList (FV -> Set VName
fvVars (StructType -> FV
forall u. TypeBase (ExpBase Info VName) u -> FV
freeInType StructType
ret)))
   in [VName] -> Set VName
forall a. Ord a => [a] -> Set a
S.fromList ([VName] -> Set VName) -> [VName] -> Set VName
forall a b. (a -> b) -> a -> b
$ Map VName Bool -> [VName]
forall k a. Map k a -> [k]
M.keys (Map VName Bool -> [VName]) -> Map VName Bool -> [VName]
forall a b. (a -> b) -> a -> b
$ (Bool -> Bool) -> Map VName Bool -> Map VName Bool
forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter Bool -> Bool
forall a. a -> a
id (Map VName Bool -> Map VName Bool)
-> Map VName Bool -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ Map VName Bool -> Map VName Bool
alsoRet (Map VName Bool -> Map VName Bool)
-> Map VName Bool -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ (Map VName Bool -> StructType -> Map VName Bool)
-> Map VName Bool -> [StructType] -> Map VName Bool
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Map VName Bool -> StructType -> Map VName Bool
onType Map VName Bool
forall a. Monoid a => a
mempty ([StructType] -> Map VName Bool) -> [StructType] -> Map VName Bool
forall a b. (a -> b) -> a -> b
$ (TypeBase (ExpBase Info VName) Diet -> StructType)
-> [TypeBase (ExpBase Info VName) Diet] -> [StructType]
forall a b. (a -> b) -> [a] -> [b]
map TypeBase (ExpBase Info VName) Diet -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct [TypeBase (ExpBase Info VName) Diet]
ts
  where
    onType :: Map VName Bool -> StructType -> Map VName Bool
onType Map VName Bool
uses StructType
t = Map VName Bool
uses Map VName Bool -> Map VName Bool -> Map VName Bool
forall a. Semigroup a => a -> a -> a
<> StructType -> Map VName Bool
mustBeExplicitAux StructType
t -- Left-biased union.

-- | Figure out which of the sizes in a parameter type must be passed
-- explicitly, because their first use is as something else than just
-- an array dimension.
mustBeExplicitInType :: StructType -> S.Set VName
mustBeExplicitInType :: StructType -> Set VName
mustBeExplicitInType = (Set VName, Set VName) -> Set VName
forall a b. (a, b) -> b
snd ((Set VName, Set VName) -> Set VName)
-> (StructType -> (Set VName, Set VName))
-> StructType
-> Set VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StructType -> (Set VName, Set VName)
determineSizeWitnesses

-- | Ensure that the dimensions of the RetType are unique by
-- generating new names for them.  This is to avoid name capture.
renameRetType :: (MonadTypeChecker m) => ResRetType -> m ResRetType
renameRetType :: forall (m :: * -> *).
MonadTypeChecker m =>
ResRetType -> m ResRetType
renameRetType (RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
st)
  | [VName]
dims [VName] -> [VName] -> Bool
forall a. Eq a => a -> a -> Bool
/= [VName]
forall a. Monoid a => a
mempty = do
      [VName]
dims' <- (VName -> m VName) -> [VName] -> m [VName]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM VName -> m VName
forall (m :: * -> *). MonadTypeChecker m => VName -> m VName
newName [VName]
dims
      let mkSubst :: VName -> Subst t
mkSubst = ExpBase Info VName -> Subst t
forall t. ExpBase Info VName -> Subst t
ExpSubst (ExpBase Info VName -> Subst t)
-> (VName -> ExpBase Info VName) -> VName -> Subst t
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (QualName VName -> SrcLoc -> ExpBase Info VName)
-> SrcLoc -> QualName VName -> ExpBase Info VName
forall a b c. (a -> b -> c) -> b -> a -> c
flip QualName VName -> SrcLoc -> ExpBase Info VName
sizeFromName SrcLoc
forall a. Monoid a => a
mempty (QualName VName -> ExpBase Info VName)
-> (VName -> QualName VName) -> VName -> ExpBase Info VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VName -> QualName VName
forall v. v -> QualName v
qualName
          m :: Map VName (Subst t)
m = [(VName, Subst t)] -> Map VName (Subst t)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(VName, Subst t)] -> Map VName (Subst t))
-> ([Subst t] -> [(VName, Subst t)])
-> [Subst t]
-> Map VName (Subst t)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [VName] -> [Subst t] -> [(VName, Subst t)]
forall a b. [a] -> [b] -> [(a, b)]
zip [VName]
dims ([Subst t] -> Map VName (Subst t))
-> [Subst t] -> Map VName (Subst t)
forall a b. (a -> b) -> a -> b
$ (VName -> Subst t) -> [VName] -> [Subst t]
forall a b. (a -> b) -> [a] -> [b]
map VName -> Subst t
forall {t}. VName -> Subst t
mkSubst [VName]
dims'
          st' :: TypeBase (ExpBase Info VName) Uniqueness
st' = TypeSubs
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a. Substitutable a => TypeSubs -> a -> a
applySubst (VName
-> Map VName (Subst StructRetType) -> Maybe (Subst StructRetType)
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map VName (Subst StructRetType)
forall {t}. Map VName (Subst t)
m) TypeBase (ExpBase Info VName) Uniqueness
st
      ResRetType -> m ResRetType
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ResRetType -> m ResRetType) -> ResRetType -> m ResRetType
forall a b. (a -> b) -> a -> b
$ [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims' TypeBase (ExpBase Info VName) Uniqueness
st'
  | Bool
otherwise =
      ResRetType -> m ResRetType
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ResRetType -> m ResRetType) -> ResRetType -> m ResRetType
forall a b. (a -> b) -> a -> b
$ [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
st

evalTypeExp ::
  (MonadTypeChecker m) =>
  TypeExp NoInfo Name ->
  m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp :: forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp (TEVar QualName Name
name SrcLoc
loc) = do
  (QualName VName
name', [TypeParam]
ps, StructRetType
t, Liftedness
l) <- SrcLoc
-> QualName Name
-> m (QualName VName, [TypeParam], StructRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
SrcLoc
-> QualName Name
-> m (QualName VName, [TypeParam], StructRetType, Liftedness)
lookupType SrcLoc
loc QualName Name
name
  ResRetType
t' <- ResRetType -> m ResRetType
forall (m :: * -> *).
MonadTypeChecker m =>
ResRetType -> m ResRetType
renameRetType (ResRetType -> m ResRetType) -> ResRetType -> m ResRetType
forall a b. (a -> b) -> a -> b
$ Uniqueness -> StructRetType -> ResRetType
forall u.
Uniqueness -> RetTypeBase (ExpBase Info VName) u -> ResRetType
toResRet Uniqueness
Nonunique StructRetType
t
  case [TypeParam]
ps of
    [] -> (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (QualName VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn. QualName vn -> SrcLoc -> TypeExp f vn
TEVar QualName VName
name' SrcLoc
loc, [], ResRetType
t', Liftedness
l)
    [TypeParam]
_ ->
      SrcLoc
-> Notes
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Type constructor"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes ([Doc ()] -> Doc ()
forall ann. [Doc ann] -> Doc ann
hsep (QualName Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. QualName Name -> Doc ann
pretty QualName Name
name Doc () -> [Doc ()] -> [Doc ()]
forall a. a -> [a] -> [a]
: (TypeParam -> Doc ()) -> [TypeParam] -> [Doc ()]
forall a b. (a -> b) -> [a] -> [b]
map TypeParam -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeParam -> Doc ann
pretty [TypeParam]
ps))
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"used without any arguments."
--
evalTypeExp (TEParens TypeExp NoInfo Name
te SrcLoc
loc) = do
  (TypeExp Info VName
te', [VName]
svars, ResRetType
ts, Liftedness
ls) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
te
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeExp Info VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn. TypeExp f vn -> SrcLoc -> TypeExp f vn
TEParens TypeExp Info VName
te' SrcLoc
loc, [VName]
svars, ResRetType
ts, Liftedness
ls)
--
evalTypeExp (TETuple [TypeExp NoInfo Name]
ts SrcLoc
loc) = do
  ([TypeExp Info VName]
ts', [[VName]]
svars, [ResRetType]
ts_s, [Liftedness]
ls) <- [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> ([TypeExp Info VName], [[VName]], [ResRetType], [Liftedness])
forall a b c d. [(a, b, c, d)] -> ([a], [b], [c], [d])
unzip4 ([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> ([TypeExp Info VName], [[VName]], [ResRetType], [Liftedness]))
-> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> m ([TypeExp Info VName], [[VName]], [ResRetType], [Liftedness])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TypeExp NoInfo Name
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> [TypeExp NoInfo Name]
-> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp [TypeExp NoInfo Name]
ts
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    ( [TypeExp Info VName] -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn. [TypeExp f vn] -> SrcLoc -> TypeExp f vn
TETuple [TypeExp Info VName]
ts' SrcLoc
loc,
      [[VName]] -> [VName]
forall a. Monoid a => [a] -> a
mconcat [[VName]]
svars,
      [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ((ResRetType -> [VName]) -> [ResRetType] -> [VName]
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ResRetType -> [VName]
forall dim as. RetTypeBase dim as -> [VName]
retDims [ResRetType]
ts_s) (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) Uniqueness
 -> TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ [TypeBase (ExpBase Info VName) Uniqueness]
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall dim as. [TypeBase dim as] -> ScalarTypeBase dim as
tupleRecord ([TypeBase (ExpBase Info VName) Uniqueness]
 -> ScalarTypeBase (ExpBase Info VName) Uniqueness)
-> [TypeBase (ExpBase Info VName) Uniqueness]
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ (ResRetType -> TypeBase (ExpBase Info VName) Uniqueness)
-> [ResRetType] -> [TypeBase (ExpBase Info VName) Uniqueness]
forall a b. (a -> b) -> [a] -> [b]
map ResRetType -> TypeBase (ExpBase Info VName) Uniqueness
forall dim as. RetTypeBase dim as -> TypeBase dim as
retType [ResRetType]
ts_s,
      (Liftedness -> Liftedness -> Liftedness)
-> Liftedness -> [Liftedness] -> Liftedness
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Liftedness -> Liftedness -> Liftedness
forall a. Ord a => a -> a -> a
max Liftedness
Unlifted [Liftedness]
ls
    )
--
evalTypeExp t :: TypeExp NoInfo Name
t@(TERecord [(Name, TypeExp NoInfo Name)]
fs SrcLoc
loc) = do
  -- Check for duplicate field names.
  let field_names :: [Name]
field_names = ((Name, TypeExp NoInfo Name) -> Name)
-> [(Name, TypeExp NoInfo Name)] -> [Name]
forall a b. (a -> b) -> [a] -> [b]
map (Name, TypeExp NoInfo Name) -> Name
forall a b. (a, b) -> a
fst [(Name, TypeExp NoInfo Name)]
fs
  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless ([Name] -> [Name]
forall a. Ord a => [a] -> [a]
sort [Name]
field_names [Name] -> [Name] -> Bool
forall a. Eq a => a -> a -> Bool
== [Name] -> [Name]
forall a. Ord a => [a] -> [a]
sort ([Name] -> [Name]
forall a. Ord a => [a] -> [a]
nubOrd [Name]
field_names)) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
    SrcLoc -> Notes -> Doc () -> m ()
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m ()) -> Doc () -> m ()
forall a b. (a -> b) -> a -> b
$
      Doc ()
"Duplicate record fields in" Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> TypeExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeExp NoInfo Name -> Doc ann
pretty TypeExp NoInfo Name
t Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."

  Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
checked <- (TypeExp NoInfo Name
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Map Name (TypeExp NoInfo Name)
-> m (Map
        Name (TypeExp Info VName, [VName], ResRetType, Liftedness))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map Name a -> f (Map Name b)
traverse TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp (Map Name (TypeExp NoInfo Name)
 -> m (Map
         Name (TypeExp Info VName, [VName], ResRetType, Liftedness)))
-> Map Name (TypeExp NoInfo Name)
-> m (Map
        Name (TypeExp Info VName, [VName], ResRetType, Liftedness))
forall a b. (a -> b) -> a -> b
$ [(Name, TypeExp NoInfo Name)] -> Map Name (TypeExp NoInfo Name)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [(Name, TypeExp NoInfo Name)]
fs
  let fs' :: Map Name (TypeExp Info VName)
fs' = ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> TypeExp Info VName)
-> Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> Map Name (TypeExp Info VName)
forall a b. (a -> b) -> Map Name a -> Map Name b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(TypeExp Info VName
x, [VName]
_, ResRetType
_, Liftedness
_) -> TypeExp Info VName
x) Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
checked
      fs_svars :: [VName]
fs_svars = ((TypeExp Info VName, [VName], ResRetType, Liftedness) -> [VName])
-> Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> [VName]
forall m a. Monoid m => (a -> m) -> Map Name a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (\(TypeExp Info VName
_, [VName]
y, ResRetType
_, Liftedness
_) -> [VName]
y) Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
checked
      ts_s :: Map Name ResRetType
ts_s = ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> ResRetType)
-> Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> Map Name ResRetType
forall a b. (a -> b) -> Map Name a -> Map Name b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(TypeExp Info VName
_, [VName]
_, ResRetType
z, Liftedness
_) -> ResRetType
z) Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
checked
      ls :: Map Name Liftedness
ls = ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> Liftedness)
-> Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> Map Name Liftedness
forall a b. (a -> b) -> Map Name a -> Map Name b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(TypeExp Info VName
_, [VName]
_, ResRetType
_, Liftedness
v) -> Liftedness
v) Map Name (TypeExp Info VName, [VName], ResRetType, Liftedness)
checked
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    ( [(Name, TypeExp Info VName)] -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn.
[(Name, TypeExp f vn)] -> SrcLoc -> TypeExp f vn
TERecord (Map Name (TypeExp Info VName) -> [(Name, TypeExp Info VName)]
forall k a. Map k a -> [(k, a)]
M.toList Map Name (TypeExp Info VName)
fs') SrcLoc
loc,
      [VName]
fs_svars,
      [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ((ResRetType -> [VName]) -> Map Name ResRetType -> [VName]
forall m a. Monoid m => (a -> m) -> Map Name a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ResRetType -> [VName]
forall dim as. RetTypeBase dim as -> [VName]
retDims Map Name ResRetType
ts_s) (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) Uniqueness
 -> TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ Map Name (TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall dim u. Map Name (TypeBase dim u) -> ScalarTypeBase dim u
Record (Map Name (TypeBase (ExpBase Info VName) Uniqueness)
 -> ScalarTypeBase (ExpBase Info VName) Uniqueness)
-> Map Name (TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ (ResRetType -> TypeBase (ExpBase Info VName) Uniqueness)
-> Map Name ResRetType
-> Map Name (TypeBase (ExpBase Info VName) Uniqueness)
forall a b k. (a -> b) -> Map k a -> Map k b
M.map ResRetType -> TypeBase (ExpBase Info VName) Uniqueness
forall dim as. RetTypeBase dim as -> TypeBase dim as
retType Map Name ResRetType
ts_s,
      (Liftedness -> Liftedness -> Liftedness)
-> Liftedness -> Map Name Liftedness -> Liftedness
forall b a. (b -> a -> b) -> b -> Map Name a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Liftedness -> Liftedness -> Liftedness
forall a. Ord a => a -> a -> a
max Liftedness
Unlifted Map Name Liftedness
ls
    )
--
evalTypeExp (TEArray SizeExp NoInfo Name
d TypeExp NoInfo Name
t SrcLoc
loc) = do
  ([VName]
d_svars, SizeExp Info VName
d', ExpBase Info VName
d'') <- SizeExp NoInfo Name
-> m ([VName], SizeExp Info VName, ExpBase Info VName)
forall {m :: * -> *}.
MonadTypeChecker m =>
SizeExp NoInfo Name
-> m ([VName], SizeExp Info VName, ExpBase Info VName)
checkSizeExp SizeExp NoInfo Name
d
  (TypeExp Info VName
t', [VName]
svars, RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
st, Liftedness
l) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t
  case (Liftedness
l, Uniqueness
-> Shape (ExpBase Info VName)
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall u dim. u -> Shape dim -> TypeBase dim u -> TypeBase dim u
arrayOfWithAliases Uniqueness
Nonunique ([ExpBase Info VName] -> Shape (ExpBase Info VName)
forall dim. [dim] -> Shape dim
Shape [ExpBase Info VName
d'']) TypeBase (ExpBase Info VName) Uniqueness
st) of
    (Liftedness
Unlifted, TypeBase (ExpBase Info VName) Uniqueness
st') ->
      (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( SizeExp Info VName
-> TypeExp Info VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn.
SizeExp f vn -> TypeExp f vn -> SrcLoc -> TypeExp f vn
TEArray SizeExp Info VName
d' TypeExp Info VName
t' SrcLoc
loc,
          [VName]
svars,
          [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
d_svars [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
dims) TypeBase (ExpBase Info VName) Uniqueness
st',
          Liftedness
Unlifted
        )
    (Liftedness
SizeLifted, TypeBase (ExpBase Info VName) Uniqueness
_) ->
      SrcLoc
-> Notes
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Cannot create array with elements of size-lifted type"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (TypeExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeExp NoInfo Name -> Doc ann
pretty TypeExp NoInfo Name
t)
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"(might cause irregular array)."
    (Liftedness
Lifted, TypeBase (ExpBase Info VName) Uniqueness
_) ->
      SrcLoc
-> Notes
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Cannot create array with elements of lifted type"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (TypeExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeExp NoInfo Name -> Doc ann
pretty TypeExp NoInfo Name
t)
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"(might contain function)."
  where
    checkSizeExp :: SizeExp NoInfo Name
-> m ([VName], SizeExp Info VName, ExpBase Info VName)
checkSizeExp (SizeExpAny SrcLoc
dloc) = do
      VName
dv <- Name -> m VName
forall (m :: * -> *). MonadTypeChecker m => Name -> m VName
newTypeName Name
"d"
      ([VName], SizeExp Info VName, ExpBase Info VName)
-> m ([VName], SizeExp Info VName, ExpBase Info VName)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([VName
dv], SrcLoc -> SizeExp Info VName
forall (f :: * -> *) vn. SrcLoc -> SizeExp f vn
SizeExpAny SrcLoc
dloc, QualName VName -> SrcLoc -> ExpBase Info VName
sizeFromName (VName -> QualName VName
forall v. v -> QualName v
qualName VName
dv) SrcLoc
dloc)
    checkSizeExp (SizeExp ExpBase NoInfo Name
e SrcLoc
dloc) = do
      ExpBase Info VName
e' <- ExpBase NoInfo Name -> m (ExpBase Info VName)
forall (m :: * -> *).
MonadTypeChecker m =>
ExpBase NoInfo Name -> m (ExpBase Info VName)
checkExpForSize ExpBase NoInfo Name
e
      ([VName], SizeExp Info VName, ExpBase Info VName)
-> m ([VName], SizeExp Info VName, ExpBase Info VName)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([], ExpBase Info VName -> SrcLoc -> SizeExp Info VName
forall (f :: * -> *) vn. ExpBase f vn -> SrcLoc -> SizeExp f vn
SizeExp ExpBase Info VName
e' SrcLoc
dloc, ExpBase Info VName
e')
--
evalTypeExp (TEUnique TypeExp NoInfo Name
t SrcLoc
loc) = do
  (TypeExp Info VName
t', [VName]
svars, RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
st, Liftedness
l) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t
  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (TypeBase (ExpBase Info VName) Uniqueness -> Bool
forall {dim} {u}. TypeBase dim u -> Bool
mayContainArray TypeBase (ExpBase Info VName) Uniqueness
st) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
    SrcLoc -> Doc () -> m ()
forall loc. Located loc => loc -> Doc () -> m ()
forall (m :: * -> *) loc.
(MonadTypeChecker m, Located loc) =>
loc -> Doc () -> m ()
warn SrcLoc
loc (Doc () -> m ()) -> Doc () -> m ()
forall a b. (a -> b) -> a -> b
$
      Doc ()
"Declaring" Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (TypeBase (ExpBase Info VName) Uniqueness -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeBase (ExpBase Info VName) Uniqueness -> Doc ann
pretty TypeBase (ExpBase Info VName) Uniqueness
st) Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"as unique has no effect."
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeExp Info VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn. TypeExp f vn -> SrcLoc -> TypeExp f vn
TEUnique TypeExp Info VName
t' SrcLoc
loc, [VName]
svars, [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness
st TypeBase (ExpBase Info VName) Uniqueness
-> Uniqueness -> TypeBase (ExpBase Info VName) Uniqueness
forall dim u1 u2. TypeBase dim u1 -> u2 -> TypeBase dim u2
`setUniqueness` Uniqueness
Unique, Liftedness
l)
  where
    mayContainArray :: TypeBase dim u -> Bool
mayContainArray (Scalar Prim {}) = Bool
False
    mayContainArray Array {} = Bool
True
    mayContainArray (Scalar (Record Map Name (TypeBase dim u)
fs)) = (TypeBase dim u -> Bool) -> Map Name (TypeBase dim u) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any TypeBase dim u -> Bool
mayContainArray Map Name (TypeBase dim u)
fs
    mayContainArray (Scalar TypeVar {}) = Bool
True
    mayContainArray (Scalar Arrow {}) = Bool
False
    mayContainArray (Scalar (Sum Map Name [TypeBase dim u]
cs)) = (([TypeBase dim u] -> Bool) -> Map Name [TypeBase dim u] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (([TypeBase dim u] -> Bool) -> Map Name [TypeBase dim u] -> Bool)
-> ((TypeBase dim u -> Bool) -> [TypeBase dim u] -> Bool)
-> (TypeBase dim u -> Bool)
-> Map Name [TypeBase dim u]
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (TypeBase dim u -> Bool) -> [TypeBase dim u] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any) TypeBase dim u -> Bool
mayContainArray Map Name [TypeBase dim u]
cs
--
evalTypeExp (TEArrow (Just Name
v) TypeExp NoInfo Name
t1 TypeExp NoInfo Name
t2 SrcLoc
loc) = do
  (TypeExp Info VName
t1', [VName]
svars1, RetType [VName]
dims1 TypeBase (ExpBase Info VName) Uniqueness
st1, Liftedness
_) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t1
  [(Namespace, Name)]
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *) a.
MonadTypeChecker m =>
[(Namespace, Name)] -> m a -> m a
bindSpaced [(Namespace
Term, Name
v)] (m (TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$ do
    VName
v' <- Namespace -> Name -> SrcLoc -> m VName
forall (m :: * -> *).
MonadTypeChecker m =>
Namespace -> Name -> SrcLoc -> m VName
checkName Namespace
Term Name
v SrcLoc
loc
    VName
-> BoundV
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. VName -> BoundV -> m a -> m a
forall (m :: * -> *) a.
MonadTypeChecker m =>
VName -> BoundV -> m a -> m a
bindVal VName
v' ([TypeParam] -> StructType -> BoundV
BoundV [] (StructType -> BoundV) -> StructType -> BoundV
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct TypeBase (ExpBase Info VName) Uniqueness
st1) (m (TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$ do
      (TypeExp Info VName
t2', [VName]
svars2, RetType [VName]
dims2 TypeBase (ExpBase Info VName) Uniqueness
st2, Liftedness
_) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t2
      (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( Maybe VName
-> TypeExp Info VName
-> TypeExp Info VName
-> SrcLoc
-> TypeExp Info VName
forall (f :: * -> *) vn.
Maybe vn -> TypeExp f vn -> TypeExp f vn -> SrcLoc -> TypeExp f vn
TEArrow (VName -> Maybe VName
forall a. a -> Maybe a
Just VName
v') TypeExp Info VName
t1' TypeExp Info VName
t2' SrcLoc
loc,
          [VName]
svars1 [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
dims1 [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
svars2,
          [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [] (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) Uniqueness
 -> TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ Uniqueness
-> PName
-> Diet
-> StructType
-> ResRetType
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall dim u.
u
-> PName
-> Diet
-> TypeBase dim NoUniqueness
-> RetTypeBase dim Uniqueness
-> ScalarTypeBase dim u
Arrow Uniqueness
Nonunique (VName -> PName
Named VName
v') (TypeBase (ExpBase Info VName) Diet -> Diet
forall shape. TypeBase shape Diet -> Diet
diet (TypeBase (ExpBase Info VName) Diet -> Diet)
-> TypeBase (ExpBase Info VName) Diet -> Diet
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Diet
resToParam TypeBase (ExpBase Info VName) Uniqueness
st1) (TypeBase (ExpBase Info VName) Uniqueness -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct TypeBase (ExpBase Info VName) Uniqueness
st1) ([VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims2 TypeBase (ExpBase Info VName) Uniqueness
st2),
          Liftedness
Lifted
        )
--
evalTypeExp (TEArrow Maybe Name
Nothing TypeExp NoInfo Name
t1 TypeExp NoInfo Name
t2 SrcLoc
loc) = do
  (TypeExp Info VName
t1', [VName]
svars1, RetType [VName]
dims1 TypeBase (ExpBase Info VName) Uniqueness
st1, Liftedness
_) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t1
  (TypeExp Info VName
t2', [VName]
svars2, RetType [VName]
dims2 TypeBase (ExpBase Info VName) Uniqueness
st2, Liftedness
_) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t2
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    ( Maybe VName
-> TypeExp Info VName
-> TypeExp Info VName
-> SrcLoc
-> TypeExp Info VName
forall (f :: * -> *) vn.
Maybe vn -> TypeExp f vn -> TypeExp f vn -> SrcLoc -> TypeExp f vn
TEArrow Maybe VName
forall a. Maybe a
Nothing TypeExp Info VName
t1' TypeExp Info VName
t2' SrcLoc
loc,
      [VName]
svars1 [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
dims1 [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
svars2,
      [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [] (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> (ScalarTypeBase (ExpBase Info VName) Uniqueness
    -> TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
-> ResRetType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$
        Uniqueness
-> PName
-> Diet
-> StructType
-> ResRetType
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall dim u.
u
-> PName
-> Diet
-> TypeBase dim NoUniqueness
-> RetTypeBase dim Uniqueness
-> ScalarTypeBase dim u
Arrow Uniqueness
Nonunique PName
Unnamed (TypeBase (ExpBase Info VName) Diet -> Diet
forall shape. TypeBase shape Diet -> Diet
diet (TypeBase (ExpBase Info VName) Diet -> Diet)
-> TypeBase (ExpBase Info VName) Diet -> Diet
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Diet
resToParam TypeBase (ExpBase Info VName) Uniqueness
st1) (TypeBase (ExpBase Info VName) Uniqueness -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct TypeBase (ExpBase Info VName) Uniqueness
st1) (ResRetType -> ScalarTypeBase (ExpBase Info VName) Uniqueness)
-> ResRetType -> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$
          [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims2 TypeBase (ExpBase Info VName) Uniqueness
st2,
      Liftedness
Lifted
    )
--
evalTypeExp (TEDim [Name]
dims TypeExp NoInfo Name
t SrcLoc
loc) = do
  [(Namespace, Name)]
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *) a.
MonadTypeChecker m =>
[(Namespace, Name)] -> m a -> m a
bindSpaced ((Name -> (Namespace, Name)) -> [Name] -> [(Namespace, Name)]
forall a b. (a -> b) -> [a] -> [b]
map (Namespace
Term,) [Name]
dims) (m (TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$ do
    [VName]
dims' <- (Name -> m VName) -> [Name] -> m [VName]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM ((Name -> SrcLoc -> m VName) -> SrcLoc -> Name -> m VName
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Namespace -> Name -> SrcLoc -> m VName
forall (m :: * -> *).
MonadTypeChecker m =>
Namespace -> Name -> SrcLoc -> m VName
checkName Namespace
Term) SrcLoc
loc) [Name]
dims
    [VName]
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall {m :: * -> *} {a}.
MonadTypeChecker m =>
[VName] -> m a -> m a
bindDims [VName]
dims' (m (TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$ do
      (TypeExp Info VName
t', [VName]
svars, RetType [VName]
t_dims TypeBase (ExpBase Info VName) Uniqueness
st, Liftedness
l) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
t
      let (Set VName
witnessed, Set VName
_) = StructType -> (Set VName, Set VName)
determineSizeWitnesses (StructType -> (Set VName, Set VName))
-> StructType -> (Set VName, Set VName)
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct TypeBase (ExpBase Info VName) Uniqueness
st
      case (VName -> Bool) -> [VName] -> Maybe VName
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
find (VName -> Set VName -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.notMember` Set VName
witnessed) [VName]
dims' of
        Just VName
d ->
          SrcLoc
-> Notes
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> (Doc () -> Doc ())
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
withIndexLink Doc ()
"unused-existential" (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$
            Doc ()
"Existential size "
              Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (VName -> Doc ()
forall a. VName -> Doc a
forall v a. IsName v => v -> Doc a
prettyName VName
d)
              Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
" not used as array size."
        Maybe VName
Nothing ->
          (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
            ( [VName] -> TypeExp Info VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn.
[vn] -> TypeExp f vn -> SrcLoc -> TypeExp f vn
TEDim [VName]
dims' TypeExp Info VName
t' SrcLoc
loc,
              [VName]
svars,
              [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
dims' [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
t_dims) TypeBase (ExpBase Info VName) Uniqueness
st,
              Liftedness -> Liftedness -> Liftedness
forall a. Ord a => a -> a -> a
max Liftedness
l Liftedness
SizeLifted
            )
  where
    bindDims :: [VName] -> m a -> m a
bindDims [] m a
m = m a
m
    bindDims (VName
d : [VName]
ds) m a
m =
      VName -> BoundV -> m a -> m a
forall a. VName -> BoundV -> m a -> m a
forall (m :: * -> *) a.
MonadTypeChecker m =>
VName -> BoundV -> m a -> m a
bindVal VName
d ([TypeParam] -> StructType -> BoundV
BoundV [] (StructType -> BoundV) -> StructType -> BoundV
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType)
-> ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType
forall a b. (a -> b) -> a -> b
$ PrimType -> ScalarTypeBase (ExpBase Info VName) NoUniqueness
forall dim u. PrimType -> ScalarTypeBase dim u
Prim (PrimType -> ScalarTypeBase (ExpBase Info VName) NoUniqueness)
-> PrimType -> ScalarTypeBase (ExpBase Info VName) NoUniqueness
forall a b. (a -> b) -> a -> b
$ IntType -> PrimType
Signed IntType
Int64) (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ [VName] -> m a -> m a
bindDims [VName]
ds m a
m
--
evalTypeExp t :: TypeExp NoInfo Name
t@(TESum [(Name, [TypeExp NoInfo Name])]
cs SrcLoc
loc) = do
  let constructors :: [Name]
constructors = ((Name, [TypeExp NoInfo Name]) -> Name)
-> [(Name, [TypeExp NoInfo Name])] -> [Name]
forall a b. (a -> b) -> [a] -> [b]
map (Name, [TypeExp NoInfo Name]) -> Name
forall a b. (a, b) -> a
fst [(Name, [TypeExp NoInfo Name])]
cs
  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless ([Name] -> [Name]
forall a. Ord a => [a] -> [a]
sort [Name]
constructors [Name] -> [Name] -> Bool
forall a. Eq a => a -> a -> Bool
== [Name] -> [Name]
forall a. Ord a => [a] -> [a]
sort ([Name] -> [Name]
forall a. Ord a => [a] -> [a]
nubOrd [Name]
constructors)) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
    SrcLoc -> Notes -> Doc () -> m ()
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m ()) -> Doc () -> m ()
forall a b. (a -> b) -> a -> b
$
      Doc ()
"Duplicate constructors in" Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> TypeExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeExp NoInfo Name -> Doc ann
pretty TypeExp NoInfo Name
t

  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless ([Name] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Name]
constructors Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
256) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$
    SrcLoc -> Notes -> Doc () -> m ()
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty Doc ()
"Sum types must have less than 256 constructors."

  Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
checked <- (([TypeExp NoInfo Name]
 -> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
-> Map Name [TypeExp NoInfo Name]
-> m (Map
        Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map Name a -> f (Map Name b)
traverse (([TypeExp NoInfo Name]
  -> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
 -> Map Name [TypeExp NoInfo Name]
 -> m (Map
         Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]))
-> ((TypeExp NoInfo Name
     -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
    -> [TypeExp NoInfo Name]
    -> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
-> (TypeExp NoInfo Name
    -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Map Name [TypeExp NoInfo Name]
-> m (Map
        Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (TypeExp NoInfo Name
 -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> [TypeExp NoInfo Name]
-> m [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse) TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp (Map Name [TypeExp NoInfo Name]
 -> m (Map
         Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]))
-> Map Name [TypeExp NoInfo Name]
-> m (Map
        Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)])
forall a b. (a -> b) -> a -> b
$ [(Name, [TypeExp NoInfo Name])] -> Map Name [TypeExp NoInfo Name]
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [(Name, [TypeExp NoInfo Name])]
cs
  let cs' :: Map Name [TypeExp Info VName]
cs' = (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [TypeExp Info VName])
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> Map Name [TypeExp Info VName]
forall a b. (a -> b) -> Map Name a -> Map Name b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
  -> [TypeExp Info VName])
 -> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> Map Name [TypeExp Info VName])
-> (((TypeExp Info VName, [VName], ResRetType, Liftedness)
     -> TypeExp Info VName)
    -> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
    -> [TypeExp Info VName])
-> ((TypeExp Info VName, [VName], ResRetType, Liftedness)
    -> TypeExp Info VName)
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> Map Name [TypeExp Info VName]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> TypeExp Info VName)
-> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [TypeExp Info VName]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap) (\(TypeExp Info VName
x, [VName]
_, ResRetType
_, Liftedness
_) -> TypeExp Info VName
x) Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
checked
      cs_svars :: [VName]
cs_svars = (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [VName])
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [VName]
forall m a. Monoid m => (a -> m) -> Map Name a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
  -> [VName])
 -> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [VName])
-> (((TypeExp Info VName, [VName], ResRetType, Liftedness)
     -> [VName])
    -> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
    -> [VName])
-> ((TypeExp Info VName, [VName], ResRetType, Liftedness)
    -> [VName])
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [VName]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((TypeExp Info VName, [VName], ResRetType, Liftedness) -> [VName])
-> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [VName]
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap) (\(TypeExp Info VName
_, [VName]
y, ResRetType
_, Liftedness
_) -> [VName]
y) Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
checked
      ts_s :: Map Name [ResRetType]
ts_s = (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [ResRetType])
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> Map Name [ResRetType]
forall a b. (a -> b) -> Map Name a -> Map Name b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
  -> [ResRetType])
 -> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> Map Name [ResRetType])
-> (((TypeExp Info VName, [VName], ResRetType, Liftedness)
     -> ResRetType)
    -> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
    -> [ResRetType])
-> ((TypeExp Info VName, [VName], ResRetType, Liftedness)
    -> ResRetType)
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> Map Name [ResRetType]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> ResRetType)
-> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [ResRetType]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap) (\(TypeExp Info VName
_, [VName]
_, ResRetType
z, Liftedness
_) -> ResRetType
z) Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
checked
      ls :: [Liftedness]
ls = (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [Liftedness])
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [Liftedness]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (([(TypeExp Info VName, [VName], ResRetType, Liftedness)]
  -> [Liftedness])
 -> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
 -> [Liftedness])
-> (((TypeExp Info VName, [VName], ResRetType, Liftedness)
     -> Liftedness)
    -> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
    -> [Liftedness])
-> ((TypeExp Info VName, [VName], ResRetType, Liftedness)
    -> Liftedness)
-> Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [Liftedness]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((TypeExp Info VName, [VName], ResRetType, Liftedness)
 -> Liftedness)
-> [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
-> [Liftedness]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap) (\(TypeExp Info VName
_, [VName]
_, ResRetType
_, Liftedness
v) -> Liftedness
v) Map Name [(TypeExp Info VName, [VName], ResRetType, Liftedness)]
checked
  (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    ( [(Name, [TypeExp Info VName])] -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn.
[(Name, [TypeExp f vn])] -> SrcLoc -> TypeExp f vn
TESum (Map Name [TypeExp Info VName] -> [(Name, [TypeExp Info VName])]
forall k a. Map k a -> [(k, a)]
M.toList Map Name [TypeExp Info VName]
cs') SrcLoc
loc,
      [VName]
cs_svars,
      [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType (([ResRetType] -> [VName]) -> Map Name [ResRetType] -> [VName]
forall m a. Monoid m => (a -> m) -> Map Name a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((ResRetType -> [VName]) -> [ResRetType] -> [VName]
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ResRetType -> [VName]
forall dim as. RetTypeBase dim as -> [VName]
retDims) Map Name [ResRetType]
ts_s) (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$
        ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) Uniqueness
 -> TypeBase (ExpBase Info VName) Uniqueness)
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$
          Map Name [TypeBase (ExpBase Info VName) Uniqueness]
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall dim u. Map Name [TypeBase dim u] -> ScalarTypeBase dim u
Sum (Map Name [TypeBase (ExpBase Info VName) Uniqueness]
 -> ScalarTypeBase (ExpBase Info VName) Uniqueness)
-> Map Name [TypeBase (ExpBase Info VName) Uniqueness]
-> ScalarTypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$
            ([ResRetType] -> [TypeBase (ExpBase Info VName) Uniqueness])
-> Map Name [ResRetType]
-> Map Name [TypeBase (ExpBase Info VName) Uniqueness]
forall a b k. (a -> b) -> Map k a -> Map k b
M.map ((ResRetType -> TypeBase (ExpBase Info VName) Uniqueness)
-> [ResRetType] -> [TypeBase (ExpBase Info VName) Uniqueness]
forall a b. (a -> b) -> [a] -> [b]
map ResRetType -> TypeBase (ExpBase Info VName) Uniqueness
forall dim as. RetTypeBase dim as -> TypeBase dim as
retType) Map Name [ResRetType]
ts_s,
      (Liftedness -> Liftedness -> Liftedness)
-> Liftedness -> [Liftedness] -> Liftedness
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Liftedness -> Liftedness -> Liftedness
forall a. Ord a => a -> a -> a
max Liftedness
Unlifted [Liftedness]
ls
    )
evalTypeExp ote :: TypeExp NoInfo Name
ote@TEApply {} = do
  (QualName Name
tname, SrcLoc
tname_loc, [TypeArgExp NoInfo Name]
targs) <- TypeExp NoInfo Name
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
rootAndArgs TypeExp NoInfo Name
ote
  (QualName VName
tname', [TypeParam]
ps, StructRetType
tname_t, Liftedness
l) <- SrcLoc
-> QualName Name
-> m (QualName VName, [TypeParam], StructRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
SrcLoc
-> QualName Name
-> m (QualName VName, [TypeParam], StructRetType, Liftedness)
lookupType SrcLoc
tloc QualName Name
tname
  RetType [VName]
t_dims TypeBase (ExpBase Info VName) Uniqueness
t <- ResRetType -> m ResRetType
forall (m :: * -> *).
MonadTypeChecker m =>
ResRetType -> m ResRetType
renameRetType (ResRetType -> m ResRetType) -> ResRetType -> m ResRetType
forall a b. (a -> b) -> a -> b
$ Uniqueness -> StructRetType -> ResRetType
forall u.
Uniqueness -> RetTypeBase (ExpBase Info VName) u -> ResRetType
toResRet Uniqueness
Nonunique StructRetType
tname_t
  if [TypeParam] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [TypeParam]
ps Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= [TypeArgExp NoInfo Name] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [TypeArgExp NoInfo Name]
targs
    then
      SrcLoc
-> Notes
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
tloc Notes
forall a. Monoid a => a
mempty (Doc () -> m (TypeExp Info VName, [VName], ResRetType, Liftedness))
-> Doc ()
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Type constructor"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (QualName Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. QualName Name -> Doc ann
pretty QualName Name
tname)
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"requires"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Int -> Doc ()
forall ann. Int -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty ([TypeParam] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [TypeParam]
ps)
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"arguments, but provided"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Int -> Doc ()
forall ann. Int -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty ([TypeArgExp NoInfo Name] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [TypeArgExp NoInfo Name]
targs) Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."
    else do
      ([TypeArgExp Info VName]
targs', [[VName]]
dims, [Map VName (Subst StructRetType)]
substs) <- [(TypeArgExp Info VName, [VName], Map VName (Subst StructRetType))]
-> ([TypeArgExp Info VName], [[VName]],
    [Map VName (Subst StructRetType)])
forall a b c. [(a, b, c)] -> ([a], [b], [c])
unzip3 ([(TypeArgExp Info VName, [VName],
   Map VName (Subst StructRetType))]
 -> ([TypeArgExp Info VName], [[VName]],
     [Map VName (Subst StructRetType)]))
-> m [(TypeArgExp Info VName, [VName],
       Map VName (Subst StructRetType))]
-> m ([TypeArgExp Info VName], [[VName]],
      [Map VName (Subst StructRetType)])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TypeParam
 -> TypeArgExp NoInfo Name
 -> m (TypeArgExp Info VName, [VName],
       Map VName (Subst StructRetType)))
-> [TypeParam]
-> [TypeArgExp NoInfo Name]
-> m [(TypeArgExp Info VName, [VName],
       Map VName (Subst StructRetType))]
forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> [a] -> [b] -> m [c]
zipWithM TypeParam
-> TypeArgExp NoInfo Name
-> m (TypeArgExp Info VName, [VName],
      Map VName (Subst StructRetType))
forall {m :: * -> *} {k}.
(MonadTypeChecker m, Eq k, IsName k) =>
TypeParamBase k
-> TypeArgExp NoInfo Name
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
checkArgApply [TypeParam]
ps [TypeArgExp NoInfo Name]
targs
      (TypeExp Info VName, [VName], ResRetType, Liftedness)
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( (TypeExp Info VName -> TypeArgExp Info VName -> TypeExp Info VName)
-> TypeExp Info VName
-> [TypeArgExp Info VName]
-> TypeExp Info VName
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\TypeExp Info VName
x TypeArgExp Info VName
y -> TypeExp Info VName
-> TypeArgExp Info VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn.
TypeExp f vn -> TypeArgExp f vn -> SrcLoc -> TypeExp f vn
TEApply TypeExp Info VName
x TypeArgExp Info VName
y SrcLoc
tloc) (QualName VName -> SrcLoc -> TypeExp Info VName
forall (f :: * -> *) vn. QualName vn -> SrcLoc -> TypeExp f vn
TEVar QualName VName
tname' SrcLoc
tname_loc) [TypeArgExp Info VName]
targs',
          [],
          [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
t_dims [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [[VName]] -> [VName]
forall a. Monoid a => [a] -> a
mconcat [[VName]]
dims) (TypeBase (ExpBase Info VName) Uniqueness -> ResRetType)
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall a b. (a -> b) -> a -> b
$
            TypeSubs
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a. Substitutable a => TypeSubs -> a -> a
applySubst (VName
-> Map VName (Subst StructRetType) -> Maybe (Subst StructRetType)
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` [Map VName (Subst StructRetType)]
-> Map VName (Subst StructRetType)
forall a. Monoid a => [a] -> a
mconcat [Map VName (Subst StructRetType)]
substs) TypeBase (ExpBase Info VName) Uniqueness
t,
          Liftedness
l
        )
  where
    tloc :: SrcLoc
tloc = TypeExp NoInfo Name -> SrcLoc
forall a. Located a => a -> SrcLoc
srclocOf TypeExp NoInfo Name
ote

    rootAndArgs ::
      (MonadTypeChecker m) =>
      TypeExp NoInfo Name ->
      m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
    rootAndArgs :: forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
rootAndArgs (TEVar QualName Name
qn SrcLoc
loc) = (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (QualName Name
qn, SrcLoc
loc, [])
    rootAndArgs (TEApply TypeExp NoInfo Name
op TypeArgExp NoInfo Name
arg SrcLoc
_) = do
      (QualName Name
op', SrcLoc
loc, [TypeArgExp NoInfo Name]
args) <- TypeExp NoInfo Name
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
rootAndArgs TypeExp NoInfo Name
op
      (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (QualName Name
op', SrcLoc
loc, [TypeArgExp NoInfo Name]
args [TypeArgExp NoInfo Name]
-> [TypeArgExp NoInfo Name] -> [TypeArgExp NoInfo Name]
forall a. [a] -> [a] -> [a]
++ [TypeArgExp NoInfo Name
arg])
    rootAndArgs TypeExp NoInfo Name
te' =
      SrcLoc
-> Notes
-> Doc ()
-> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError (TypeExp NoInfo Name -> SrcLoc
forall a. Located a => a -> SrcLoc
srclocOf TypeExp NoInfo Name
te') Notes
forall a. Monoid a => a
mempty (Doc () -> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name]))
-> Doc () -> m (QualName Name, SrcLoc, [TypeArgExp NoInfo Name])
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Type" Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (TypeExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeExp NoInfo Name -> Doc ann
pretty TypeExp NoInfo Name
te') Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"is not a type constructor."

    checkSizeExp :: SizeExp NoInfo Name -> m (TypeArgExp Info VName, [VName], Subst t)
checkSizeExp (SizeExp ExpBase NoInfo Name
e SrcLoc
dloc) = do
      ExpBase Info VName
e' <- ExpBase NoInfo Name -> m (ExpBase Info VName)
forall (m :: * -> *).
MonadTypeChecker m =>
ExpBase NoInfo Name -> m (ExpBase Info VName)
checkExpForSize ExpBase NoInfo Name
e
      (TypeArgExp Info VName, [VName], Subst t)
-> m (TypeArgExp Info VName, [VName], Subst t)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( SizeExp Info VName -> TypeArgExp Info VName
forall (f :: * -> *) vn. SizeExp f vn -> TypeArgExp f vn
TypeArgExpSize (ExpBase Info VName -> SrcLoc -> SizeExp Info VName
forall (f :: * -> *) vn. ExpBase f vn -> SrcLoc -> SizeExp f vn
SizeExp ExpBase Info VName
e' SrcLoc
dloc),
          [],
          ExpBase Info VName -> Subst t
forall t. ExpBase Info VName -> Subst t
ExpSubst ExpBase Info VName
e'
        )
    checkSizeExp (SizeExpAny SrcLoc
loc) = do
      VName
d <- Name -> m VName
forall (m :: * -> *). MonadTypeChecker m => Name -> m VName
newTypeName Name
"d"
      (TypeArgExp Info VName, [VName], Subst t)
-> m (TypeArgExp Info VName, [VName], Subst t)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( SizeExp Info VName -> TypeArgExp Info VName
forall (f :: * -> *) vn. SizeExp f vn -> TypeArgExp f vn
TypeArgExpSize (SrcLoc -> SizeExp Info VName
forall (f :: * -> *) vn. SrcLoc -> SizeExp f vn
SizeExpAny SrcLoc
loc),
          [VName
d],
          ExpBase Info VName -> Subst t
forall t. ExpBase Info VName -> Subst t
ExpSubst (ExpBase Info VName -> Subst t) -> ExpBase Info VName -> Subst t
forall a b. (a -> b) -> a -> b
$ QualName VName -> SrcLoc -> ExpBase Info VName
sizeFromName (VName -> QualName VName
forall v. v -> QualName v
qualName VName
d) SrcLoc
loc
        )

    checkArgApply :: TypeParamBase k
-> TypeArgExp NoInfo Name
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
checkArgApply (TypeParamDim k
pv SrcLoc
_) (TypeArgExpSize SizeExp NoInfo Name
d) = do
      (TypeArgExp Info VName
d', [VName]
svars, Subst StructRetType
subst) <- SizeExp NoInfo Name
-> m (TypeArgExp Info VName, [VName], Subst StructRetType)
forall {m :: * -> *} {t}.
MonadTypeChecker m =>
SizeExp NoInfo Name -> m (TypeArgExp Info VName, [VName], Subst t)
checkSizeExp SizeExp NoInfo Name
d
      (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeArgExp Info VName
d', [VName]
svars, k -> Subst StructRetType -> Map k (Subst StructRetType)
forall k a. k -> a -> Map k a
M.singleton k
pv Subst StructRetType
subst)
    checkArgApply (TypeParamType Liftedness
_ k
pv SrcLoc
_) (TypeArgExpType TypeExp NoInfo Name
te) = do
      (TypeExp Info VName
te', [VName]
svars, RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
st, Liftedness
_) <- TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
te
      (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
        ( TypeExp Info VName -> TypeArgExp Info VName
forall (f :: * -> *) vn. TypeExp f vn -> TypeArgExp f vn
TypeArgExpType TypeExp Info VName
te',
          [VName]
svars [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
dims,
          k -> Subst StructRetType -> Map k (Subst StructRetType)
forall k a. k -> a -> Map k a
M.singleton k
pv (Subst StructRetType -> Map k (Subst StructRetType))
-> Subst StructRetType -> Map k (Subst StructRetType)
forall a b. (a -> b) -> a -> b
$ [TypeParam] -> StructRetType -> Subst StructRetType
forall t. [TypeParam] -> t -> Subst t
Subst [] (StructRetType -> Subst StructRetType)
-> StructRetType -> Subst StructRetType
forall a b. (a -> b) -> a -> b
$ [VName] -> StructType -> StructRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [] (StructType -> StructRetType) -> StructType -> StructRetType
forall a b. (a -> b) -> a -> b
$ TypeBase (ExpBase Info VName) Uniqueness -> StructType
forall dim u. TypeBase dim u -> TypeBase dim NoUniqueness
toStruct TypeBase (ExpBase Info VName) Uniqueness
st
        )
    checkArgApply TypeParamBase k
p TypeArgExp NoInfo Name
a =
      SrcLoc
-> Notes
-> Doc ()
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
tloc Notes
forall a. Monoid a => a
mempty (Doc ()
 -> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType)))
-> Doc ()
-> m (TypeArgExp Info VName, [VName], Map k (Subst StructRetType))
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Type argument"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> TypeArgExp NoInfo Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeArgExp NoInfo Name -> Doc ann
pretty TypeArgExp NoInfo Name
a
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"not valid for a type parameter"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> TypeParamBase k -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeParamBase k -> Doc ann
pretty TypeParamBase k
p Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."

-- | Check a type expression, producing:
--
-- * The checked expression.
-- * Size variables for any anonymous sizes in the expression.
-- * The elaborated type.
-- * The liftedness of the type.
checkTypeExp ::
  (MonadTypeChecker m) =>
  TypeExp NoInfo Name ->
  m (TypeExp Info VName, [VName], ResRetType, Liftedness)
checkTypeExp :: forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
checkTypeExp TypeExp NoInfo Name
te = do
  TypeExp NoInfo Name -> m ()
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name -> m ()
checkForDuplicateNamesInType TypeExp NoInfo Name
te
  TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name
-> m (TypeExp Info VName, [VName], ResRetType, Liftedness)
evalTypeExp TypeExp NoInfo Name
te

-- | Check for duplication of names inside a binding group.
checkForDuplicateNames ::
  (MonadTypeChecker m) => [UncheckedTypeParam] -> [UncheckedPat t] -> m ()
checkForDuplicateNames :: forall (m :: * -> *) t.
MonadTypeChecker m =>
[UncheckedTypeParam] -> [UncheckedPat t] -> m ()
checkForDuplicateNames [UncheckedTypeParam]
tps [UncheckedPat t]
pats = (StateT (Map (Namespace, Name) SrcLoc) m ()
-> Map (Namespace, Name) SrcLoc -> m ()
forall (m :: * -> *) s a. Monad m => StateT s m a -> s -> m a
`evalStateT` Map (Namespace, Name) SrcLoc
forall a. Monoid a => a
mempty) (StateT (Map (Namespace, Name) SrcLoc) m () -> m ())
-> StateT (Map (Namespace, Name) SrcLoc) m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
  (UncheckedTypeParam -> StateT (Map (Namespace, Name) SrcLoc) m ())
-> [UncheckedTypeParam]
-> StateT (Map (Namespace, Name) SrcLoc) m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ UncheckedTypeParam -> StateT (Map (Namespace, Name) SrcLoc) m ()
forall {b} {m :: * -> *} {t :: (* -> *) -> * -> *}.
(Pretty b, MonadTypeChecker m, MonadTrans t, Ord b,
 MonadState (Map (Namespace, b) SrcLoc) (t m)) =>
TypeParamBase b -> t m ()
checkTypeParam [UncheckedTypeParam]
tps
  (UncheckedPat t -> StateT (Map (Namespace, Name) SrcLoc) m ())
-> [UncheckedPat t] -> StateT (Map (Namespace, Name) SrcLoc) m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ UncheckedPat t -> StateT (Map (Namespace, Name) SrcLoc) m ()
forall {b} {m :: * -> *} {t :: (* -> *) -> * -> *} {f :: * -> *}
       {t}.
(Pretty b, MonadTypeChecker m, MonadTrans t, Ord b,
 MonadState (Map (Namespace, b) SrcLoc) (t m)) =>
PatBase f b t -> t m ()
checkPat [UncheckedPat t]
pats
  where
    checkTypeParam :: TypeParamBase b -> t m ()
checkTypeParam (TypeParamType Liftedness
_ b
v SrcLoc
loc) = Namespace -> b -> SrcLoc -> t m ()
forall {a} {b} {m :: * -> *} {t :: (* -> *) -> * -> *} {a}.
(Located a, Pretty b, MonadTypeChecker m, MonadTrans t, Ord b,
 Ord a, MonadState (Map (a, b) a) (t m)) =>
a -> b -> a -> t m ()
seen Namespace
Type b
v SrcLoc
loc
    checkTypeParam (TypeParamDim b
v SrcLoc
loc) = Namespace -> b -> SrcLoc -> t m ()
forall {a} {b} {m :: * -> *} {t :: (* -> *) -> * -> *} {a}.
(Located a, Pretty b, MonadTypeChecker m, MonadTrans t, Ord b,
 Ord a, MonadState (Map (a, b) a) (t m)) =>
a -> b -> a -> t m ()
seen Namespace
Term b
v SrcLoc
loc

    checkPat :: PatBase f b t -> t m ()
checkPat (Id b
v f t
_ SrcLoc
loc) = Namespace -> b -> SrcLoc -> t m ()
forall {a} {b} {m :: * -> *} {t :: (* -> *) -> * -> *} {a}.
(Located a, Pretty b, MonadTypeChecker m, MonadTrans t, Ord b,
 Ord a, MonadState (Map (a, b) a) (t m)) =>
a -> b -> a -> t m ()
seen Namespace
Term b
v SrcLoc
loc
    checkPat (PatParens PatBase f b t
p SrcLoc
_) = PatBase f b t -> t m ()
checkPat PatBase f b t
p
    checkPat (PatAttr AttrInfo b
_ PatBase f b t
p SrcLoc
_) = PatBase f b t -> t m ()
checkPat PatBase f b t
p
    checkPat Wildcard {} = () -> t m ()
forall a. a -> t m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    checkPat (TuplePat [PatBase f b t]
ps SrcLoc
_) = (PatBase f b t -> t m ()) -> [PatBase f b t] -> t m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ PatBase f b t -> t m ()
checkPat [PatBase f b t]
ps
    checkPat (RecordPat [(Name, PatBase f b t)]
fs SrcLoc
_) = ((Name, PatBase f b t) -> t m ())
-> [(Name, PatBase f b t)] -> t m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (PatBase f b t -> t m ()
checkPat (PatBase f b t -> t m ())
-> ((Name, PatBase f b t) -> PatBase f b t)
-> (Name, PatBase f b t)
-> t m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Name, PatBase f b t) -> PatBase f b t
forall a b. (a, b) -> b
snd) [(Name, PatBase f b t)]
fs
    checkPat (PatAscription PatBase f b t
p TypeExp f b
_ SrcLoc
_) = PatBase f b t -> t m ()
checkPat PatBase f b t
p
    checkPat PatLit {} = () -> t m ()
forall a. a -> t m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    checkPat (PatConstr Name
_ f t
_ [PatBase f b t]
ps SrcLoc
_) = (PatBase f b t -> t m ()) -> [PatBase f b t] -> t m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ PatBase f b t -> t m ()
checkPat [PatBase f b t]
ps

    seen :: a -> b -> a -> t m ()
seen a
ns b
v a
loc = do
      Maybe a
already <- (Map (a, b) a -> Maybe a) -> t m (Maybe a)
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets ((Map (a, b) a -> Maybe a) -> t m (Maybe a))
-> (Map (a, b) a -> Maybe a) -> t m (Maybe a)
forall a b. (a -> b) -> a -> b
$ (a, b) -> Map (a, b) a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup (a
ns, b
v)
      case Maybe a
already of
        Just a
prev_loc ->
          m () -> t m ()
forall (m :: * -> *) a. Monad m => m a -> t m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m () -> t m ()) -> m () -> t m ()
forall a b. (a -> b) -> a -> b
$
            a -> Notes -> Doc () -> m ()
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError a
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m ()) -> Doc () -> m ()
forall a b. (a -> b) -> a -> b
$
              Doc ()
"Name"
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (b -> Doc ()
forall ann. b -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty b
v)
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"also bound at"
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> String -> Doc ()
forall ann. String -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty (a -> String
forall a. Located a => a -> String
locStr a
prev_loc) Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."
        Maybe a
Nothing ->
          (Map (a, b) a -> Map (a, b) a) -> t m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Map (a, b) a -> Map (a, b) a) -> t m ())
-> (Map (a, b) a -> Map (a, b) a) -> t m ()
forall a b. (a -> b) -> a -> b
$ (a, b) -> a -> Map (a, b) a -> Map (a, b) a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert (a
ns, b
v) a
loc

-- | Check whether the type contains arrow types that define the same
-- parameter.  These might also exist further down, but that's not
-- really a problem - we mostly do this checking to help the user,
-- since it is likely an error, but it's easy to assign a semantics to
-- it (normal name shadowing).
checkForDuplicateNamesInType ::
  (MonadTypeChecker m) =>
  TypeExp NoInfo Name ->
  m ()
checkForDuplicateNamesInType :: forall (m :: * -> *).
MonadTypeChecker m =>
TypeExp NoInfo Name -> m ()
checkForDuplicateNamesInType = Map Name SrcLoc -> TypeExp NoInfo Name -> m ()
forall {m :: * -> *} {a} {f :: * -> *}.
(MonadTypeChecker m, Pretty a, Ord a) =>
Map a SrcLoc -> TypeExp f a -> m ()
check Map Name SrcLoc
forall a. Monoid a => a
mempty
  where
    bad :: a -> loc -> a -> m a
bad a
v loc
loc a
prev_loc =
      loc -> Notes -> Doc () -> m a
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError loc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m a) -> Doc () -> m a
forall a b. (a -> b) -> a -> b
$
        Doc ()
"Name"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (a -> Doc ()
forall ann. a -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty a
v)
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"also bound at"
          Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> String -> Doc ()
forall ann. String -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty (a -> String
forall a. Located a => a -> String
locStr a
prev_loc) Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."

    check :: Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen (TEArrow (Just a
v) TypeExp f a
t1 TypeExp f a
t2 SrcLoc
loc)
      | Just SrcLoc
prev_loc <- a -> Map a SrcLoc -> Maybe SrcLoc
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
v Map a SrcLoc
seen =
          a -> SrcLoc -> SrcLoc -> m ()
forall {m :: * -> *} {a} {loc} {a} {a}.
(MonadTypeChecker m, Pretty a, Located loc, Located a) =>
a -> loc -> a -> m a
bad a
v SrcLoc
loc SrcLoc
prev_loc
      | Bool
otherwise =
          Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen' TypeExp f a
t1 m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen' TypeExp f a
t2
      where
        seen' :: Map a SrcLoc
seen' = a -> SrcLoc -> Map a SrcLoc -> Map a SrcLoc
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v SrcLoc
loc Map a SrcLoc
seen
    check Map a SrcLoc
seen (TEArrow Maybe a
Nothing TypeExp f a
t1 TypeExp f a
t2 SrcLoc
_) =
      Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t1 m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t2
    check Map a SrcLoc
seen (TETuple [TypeExp f a]
ts SrcLoc
_) = (TypeExp f a -> m ()) -> [TypeExp f a] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen) [TypeExp f a]
ts
    check Map a SrcLoc
seen (TERecord [(Name, TypeExp f a)]
fs SrcLoc
_) = ((Name, TypeExp f a) -> m ()) -> [(Name, TypeExp f a)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen (TypeExp f a -> m ())
-> ((Name, TypeExp f a) -> TypeExp f a)
-> (Name, TypeExp f a)
-> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Name, TypeExp f a) -> TypeExp f a
forall a b. (a, b) -> b
snd) [(Name, TypeExp f a)]
fs
    check Map a SrcLoc
seen (TEUnique TypeExp f a
t SrcLoc
_) = Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t
    check Map a SrcLoc
seen (TESum [(Name, [TypeExp f a])]
cs SrcLoc
_) = ((Name, [TypeExp f a]) -> m [()])
-> [(Name, [TypeExp f a])] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ ((TypeExp f a -> m ()) -> [TypeExp f a] -> m [()]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM (Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen) ([TypeExp f a] -> m [()])
-> ((Name, [TypeExp f a]) -> [TypeExp f a])
-> (Name, [TypeExp f a])
-> m [()]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Name, [TypeExp f a]) -> [TypeExp f a]
forall a b. (a, b) -> b
snd) [(Name, [TypeExp f a])]
cs
    check Map a SrcLoc
seen (TEApply TypeExp f a
t1 (TypeArgExpType TypeExp f a
t2) SrcLoc
_) =
      Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t1 m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t2
    check Map a SrcLoc
seen (TEApply TypeExp f a
t1 TypeArgExpSize {} SrcLoc
_) =
      Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t1
    check Map a SrcLoc
seen (TEDim (a
v : [a]
vs) TypeExp f a
t SrcLoc
loc)
      | Just SrcLoc
prev_loc <- a -> Map a SrcLoc -> Maybe SrcLoc
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
v Map a SrcLoc
seen =
          a -> SrcLoc -> SrcLoc -> m ()
forall {m :: * -> *} {a} {loc} {a} {a}.
(MonadTypeChecker m, Pretty a, Located loc, Located a) =>
a -> loc -> a -> m a
bad a
v SrcLoc
loc SrcLoc
prev_loc
      | Bool
otherwise =
          Map a SrcLoc -> TypeExp f a -> m ()
check (a -> SrcLoc -> Map a SrcLoc -> Map a SrcLoc
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v SrcLoc
loc Map a SrcLoc
seen) ([a] -> TypeExp f a -> SrcLoc -> TypeExp f a
forall (f :: * -> *) vn.
[vn] -> TypeExp f vn -> SrcLoc -> TypeExp f vn
TEDim [a]
vs TypeExp f a
t SrcLoc
loc)
    check Map a SrcLoc
seen (TEDim [] TypeExp f a
t SrcLoc
_) =
      Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
t
    check Map a SrcLoc
_ TEArray {} = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    check Map a SrcLoc
_ TEVar {} = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    check Map a SrcLoc
seen (TEParens TypeExp f a
te SrcLoc
_) = Map a SrcLoc -> TypeExp f a -> m ()
check Map a SrcLoc
seen TypeExp f a
te

-- | @checkTypeParams ps m@ checks the type parameters @ps@, then
-- invokes the continuation @m@ with the checked parameters, while
-- extending the monadic name map with @ps@.
checkTypeParams ::
  (MonadTypeChecker m) =>
  [TypeParamBase Name] ->
  ([TypeParamBase VName] -> m a) ->
  m a
checkTypeParams :: forall (m :: * -> *) a.
MonadTypeChecker m =>
[UncheckedTypeParam] -> ([TypeParam] -> m a) -> m a
checkTypeParams [UncheckedTypeParam]
ps [TypeParam] -> m a
m =
  [(Namespace, Name)] -> m a -> m a
forall (m :: * -> *) a.
MonadTypeChecker m =>
[(Namespace, Name)] -> m a -> m a
bindSpaced ((UncheckedTypeParam -> (Namespace, Name))
-> [UncheckedTypeParam] -> [(Namespace, Name)]
forall a b. (a -> b) -> [a] -> [b]
map UncheckedTypeParam -> (Namespace, Name)
forall {b}. TypeParamBase b -> (Namespace, b)
typeParamSpace [UncheckedTypeParam]
ps) (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$
    [TypeParam] -> m a
m ([TypeParam] -> m a) -> m [TypeParam] -> m a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< StateT (Map (Namespace, Name) SrcLoc) m [TypeParam]
-> Map (Namespace, Name) SrcLoc -> m [TypeParam]
forall (m :: * -> *) s a. Monad m => StateT s m a -> s -> m a
evalStateT ((UncheckedTypeParam
 -> StateT (Map (Namespace, Name) SrcLoc) m TypeParam)
-> [UncheckedTypeParam]
-> StateT (Map (Namespace, Name) SrcLoc) m [TypeParam]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM UncheckedTypeParam
-> StateT (Map (Namespace, Name) SrcLoc) m TypeParam
forall {m :: * -> *} {t :: (* -> *) -> * -> *}.
(MonadTypeChecker m, MonadTrans t,
 MonadState (Map (Namespace, Name) SrcLoc) (t m)) =>
UncheckedTypeParam -> t m TypeParam
checkTypeParam [UncheckedTypeParam]
ps) Map (Namespace, Name) SrcLoc
forall a. Monoid a => a
mempty
  where
    typeParamSpace :: TypeParamBase b -> (Namespace, b)
typeParamSpace (TypeParamDim b
pv SrcLoc
_) = (Namespace
Term, b
pv)
    typeParamSpace (TypeParamType Liftedness
_ b
pv SrcLoc
_) = (Namespace
Type, b
pv)

    checkParamName :: Namespace -> Name -> SrcLoc -> t m VName
checkParamName Namespace
ns Name
v SrcLoc
loc = do
      Maybe SrcLoc
seen <- (Map (Namespace, Name) SrcLoc -> Maybe SrcLoc)
-> t m (Maybe SrcLoc)
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets ((Map (Namespace, Name) SrcLoc -> Maybe SrcLoc)
 -> t m (Maybe SrcLoc))
-> (Map (Namespace, Name) SrcLoc -> Maybe SrcLoc)
-> t m (Maybe SrcLoc)
forall a b. (a -> b) -> a -> b
$ (Namespace, Name) -> Map (Namespace, Name) SrcLoc -> Maybe SrcLoc
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup (Namespace
ns, Name
v)
      case Maybe SrcLoc
seen of
        Just SrcLoc
prev ->
          m VName -> t m VName
forall (m :: * -> *) a. Monad m => m a -> t m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m VName -> t m VName) -> m VName -> t m VName
forall a b. (a -> b) -> a -> b
$
            SrcLoc -> Notes -> Doc () -> m VName
forall loc a. Located loc => loc -> Notes -> Doc () -> m a
forall (m :: * -> *) loc a.
(MonadTypeChecker m, Located loc) =>
loc -> Notes -> Doc () -> m a
typeError SrcLoc
loc Notes
forall a. Monoid a => a
mempty (Doc () -> m VName) -> Doc () -> m VName
forall a b. (a -> b) -> a -> b
$
              Doc ()
"Type parameter"
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann
dquotes (Name -> Doc ()
forall a ann. Pretty a => a -> Doc ann
forall ann. Name -> Doc ann
pretty Name
v)
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> Doc ()
"previously defined at"
                Doc () -> Doc () -> Doc ()
forall ann. Doc ann -> Doc ann -> Doc ann
<+> String -> Doc ()
forall ann. String -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty (SrcLoc -> String
forall a. Located a => a -> String
locStr SrcLoc
prev) Doc () -> Doc () -> Doc ()
forall a. Semigroup a => a -> a -> a
<> Doc ()
"."
        Maybe SrcLoc
Nothing -> do
          (Map (Namespace, Name) SrcLoc -> Map (Namespace, Name) SrcLoc)
-> t m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Map (Namespace, Name) SrcLoc -> Map (Namespace, Name) SrcLoc)
 -> t m ())
-> (Map (Namespace, Name) SrcLoc -> Map (Namespace, Name) SrcLoc)
-> t m ()
forall a b. (a -> b) -> a -> b
$ (Namespace, Name)
-> SrcLoc
-> Map (Namespace, Name) SrcLoc
-> Map (Namespace, Name) SrcLoc
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert (Namespace
ns, Name
v) SrcLoc
loc
          m VName -> t m VName
forall (m :: * -> *) a. Monad m => m a -> t m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m VName -> t m VName) -> m VName -> t m VName
forall a b. (a -> b) -> a -> b
$ Namespace -> Name -> SrcLoc -> m VName
forall (m :: * -> *).
MonadTypeChecker m =>
Namespace -> Name -> SrcLoc -> m VName
checkName Namespace
ns Name
v SrcLoc
loc

    checkTypeParam :: UncheckedTypeParam -> t m TypeParam
checkTypeParam (TypeParamDim Name
pv SrcLoc
loc) =
      VName -> SrcLoc -> TypeParam
forall vn. vn -> SrcLoc -> TypeParamBase vn
TypeParamDim (VName -> SrcLoc -> TypeParam)
-> t m VName -> t m (SrcLoc -> TypeParam)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Namespace -> Name -> SrcLoc -> t m VName
forall {m :: * -> *} {t :: (* -> *) -> * -> *}.
(MonadTypeChecker m, MonadTrans t,
 MonadState (Map (Namespace, Name) SrcLoc) (t m)) =>
Namespace -> Name -> SrcLoc -> t m VName
checkParamName Namespace
Term Name
pv SrcLoc
loc t m (SrcLoc -> TypeParam) -> t m SrcLoc -> t m TypeParam
forall a b. t m (a -> b) -> t m a -> t m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> SrcLoc -> t m SrcLoc
forall a. a -> t m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure SrcLoc
loc
    checkTypeParam (TypeParamType Liftedness
l Name
pv SrcLoc
loc) =
      Liftedness -> VName -> SrcLoc -> TypeParam
forall vn. Liftedness -> vn -> SrcLoc -> TypeParamBase vn
TypeParamType Liftedness
l (VName -> SrcLoc -> TypeParam)
-> t m VName -> t m (SrcLoc -> TypeParam)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Namespace -> Name -> SrcLoc -> t m VName
forall {m :: * -> *} {t :: (* -> *) -> * -> *}.
(MonadTypeChecker m, MonadTrans t,
 MonadState (Map (Namespace, Name) SrcLoc) (t m)) =>
Namespace -> Name -> SrcLoc -> t m VName
checkParamName Namespace
Type Name
pv SrcLoc
loc t m (SrcLoc -> TypeParam) -> t m SrcLoc -> t m TypeParam
forall a b. t m (a -> b) -> t m a -> t m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> SrcLoc -> t m SrcLoc
forall a. a -> t m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure SrcLoc
loc

-- | Construct a type argument corresponding to a type parameter.
typeParamToArg :: TypeParam -> StructTypeArg
typeParamToArg :: TypeParam -> StructTypeArg
typeParamToArg (TypeParamDim VName
v SrcLoc
ploc) =
  ExpBase Info VName -> StructTypeArg
forall dim. dim -> TypeArg dim
TypeArgDim (ExpBase Info VName -> StructTypeArg)
-> ExpBase Info VName -> StructTypeArg
forall a b. (a -> b) -> a -> b
$ QualName VName -> SrcLoc -> ExpBase Info VName
sizeFromName (VName -> QualName VName
forall v. v -> QualName v
qualName VName
v) SrcLoc
ploc
typeParamToArg (TypeParamType Liftedness
_ VName
v SrcLoc
_) =
  StructType -> StructTypeArg
forall dim. TypeBase dim NoUniqueness -> TypeArg dim
TypeArgType (StructType -> StructTypeArg) -> StructType -> StructTypeArg
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType)
-> ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType
forall a b. (a -> b) -> a -> b
$ NoUniqueness
-> QualName VName
-> [StructTypeArg]
-> ScalarTypeBase (ExpBase Info VName) NoUniqueness
forall dim u.
u -> QualName VName -> [TypeArg dim] -> ScalarTypeBase dim u
TypeVar NoUniqueness
forall a. Monoid a => a
mempty (VName -> QualName VName
forall v. v -> QualName v
qualName VName
v) []

-- | A type substitution may be a substitution or a yet-unknown
-- substitution (but which is certainly an overloaded primitive
-- type!).
data Subst t = Subst [TypeParam] t | ExpSubst Exp
  deriving (Int -> Subst t -> ShowS
[Subst t] -> ShowS
Subst t -> String
(Int -> Subst t -> ShowS)
-> (Subst t -> String) -> ([Subst t] -> ShowS) -> Show (Subst t)
forall t. Show t => Int -> Subst t -> ShowS
forall t. Show t => [Subst t] -> ShowS
forall t. Show t => Subst t -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall t. Show t => Int -> Subst t -> ShowS
showsPrec :: Int -> Subst t -> ShowS
$cshow :: forall t. Show t => Subst t -> String
show :: Subst t -> String
$cshowList :: forall t. Show t => [Subst t] -> ShowS
showList :: [Subst t] -> ShowS
Show)

instance (Pretty t) => Pretty (Subst t) where
  pretty :: forall ann. Subst t -> Doc ann
pretty (Subst [] t
t) = t -> Doc ann
forall ann. t -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty t
t
  pretty (Subst [TypeParam]
tps t
t) = [Doc ann] -> Doc ann
forall a. Monoid a => [a] -> a
mconcat ((TypeParam -> Doc ann) -> [TypeParam] -> [Doc ann]
forall a b. (a -> b) -> [a] -> [b]
map TypeParam -> Doc ann
forall a ann. Pretty a => a -> Doc ann
forall ann. TypeParam -> Doc ann
pretty [TypeParam]
tps) Doc ann -> Doc ann -> Doc ann
forall a. Semigroup a => a -> a -> a
<> Doc ann
forall ann. Doc ann
colon Doc ann -> Doc ann -> Doc ann
forall ann. Doc ann -> Doc ann -> Doc ann
<+> t -> Doc ann
forall ann. t -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty t
t
  pretty (ExpSubst ExpBase Info VName
e) = ExpBase Info VName -> Doc ann
forall a ann. Pretty a => a -> Doc ann
forall ann. ExpBase Info VName -> Doc ann
pretty ExpBase Info VName
e

instance Functor Subst where
  fmap :: forall a b. (a -> b) -> Subst a -> Subst b
fmap a -> b
f (Subst [TypeParam]
ps a
t) = [TypeParam] -> b -> Subst b
forall t. [TypeParam] -> t -> Subst t
Subst [TypeParam]
ps (b -> Subst b) -> b -> Subst b
forall a b. (a -> b) -> a -> b
$ a -> b
f a
t
  fmap a -> b
_ (ExpSubst ExpBase Info VName
e) = ExpBase Info VName -> Subst b
forall t. ExpBase Info VName -> Subst t
ExpSubst ExpBase Info VName
e

-- | Create a type substitution corresponding to a type binding.
substFromAbbr :: TypeBinding -> Subst StructRetType
substFromAbbr :: TypeBinding -> Subst StructRetType
substFromAbbr (TypeAbbr Liftedness
_ [TypeParam]
ps StructRetType
rt) = [TypeParam] -> StructRetType -> Subst StructRetType
forall t. [TypeParam] -> t -> Subst t
Subst [TypeParam]
ps StructRetType
rt

-- | Substitutions to apply in a type.
type TypeSubs = VName -> Maybe (Subst StructRetType)

-- | Class of types which allow for substitution of types with no
-- annotations for type variable names.
class Substitutable a where
  applySubst :: TypeSubs -> a -> a

instance Substitutable (RetTypeBase Size Uniqueness) where
  applySubst :: TypeSubs -> ResRetType -> ResRetType
applySubst TypeSubs
f (RetType [VName]
dims TypeBase (ExpBase Info VName) Uniqueness
t) =
    let RetType [VName]
more_dims TypeBase (ExpBase Info VName) Uniqueness
t' = (VName -> Maybe (Subst ResRetType))
-> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet VName -> Maybe (Subst ResRetType)
f' TypeBase (ExpBase Info VName) Uniqueness
t
     in [VName] -> TypeBase (ExpBase Info VName) Uniqueness -> ResRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
dims [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
more_dims) TypeBase (ExpBase Info VName) Uniqueness
t'
    where
      f' :: VName -> Maybe (Subst ResRetType)
f' = (Subst StructRetType -> Subst ResRetType)
-> Maybe (Subst StructRetType) -> Maybe (Subst ResRetType)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((StructRetType -> ResRetType)
-> Subst StructRetType -> Subst ResRetType
forall a b. (a -> b) -> Subst a -> Subst b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((NoUniqueness -> Uniqueness) -> StructRetType -> ResRetType
forall b c a. (b -> c) -> RetTypeBase a b -> RetTypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (Uniqueness -> NoUniqueness -> Uniqueness
forall a b. a -> b -> a
const Uniqueness
forall a. Monoid a => a
mempty))) (Maybe (Subst StructRetType) -> Maybe (Subst ResRetType))
-> TypeSubs -> VName -> Maybe (Subst ResRetType)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
f

instance Substitutable (RetTypeBase Size NoUniqueness) where
  applySubst :: TypeSubs -> StructRetType -> StructRetType
applySubst TypeSubs
f (RetType [VName]
dims StructType
t) =
    let RetType [VName]
more_dims StructType
t' = TypeSubs -> StructType -> StructRetType
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet TypeSubs
f StructType
t
     in [VName] -> StructType -> StructRetType
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
dims [VName] -> [VName] -> [VName]
forall a. [a] -> [a] -> [a]
++ [VName]
more_dims) StructType
t'

instance Substitutable StructType where
  applySubst :: TypeSubs -> StructType -> StructType
applySubst = TypeSubs -> StructType -> StructType
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
substTypesAny

instance Substitutable ParamType where
  applySubst :: TypeSubs
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
applySubst TypeSubs
f = (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet)))
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
substTypesAny ((VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet)))
 -> TypeBase (ExpBase Info VName) Diet
 -> TypeBase (ExpBase Info VName) Diet)
-> (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet)))
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
forall a b. (a -> b) -> a -> b
$ (Subst StructRetType
 -> Subst (RetTypeBase (ExpBase Info VName) Diet))
-> Maybe (Subst StructRetType)
-> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet))
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((StructRetType -> RetTypeBase (ExpBase Info VName) Diet)
-> Subst StructRetType
-> Subst (RetTypeBase (ExpBase Info VName) Diet)
forall a b. (a -> b) -> Subst a -> Subst b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((StructRetType -> RetTypeBase (ExpBase Info VName) Diet)
 -> Subst StructRetType
 -> Subst (RetTypeBase (ExpBase Info VName) Diet))
-> (StructRetType -> RetTypeBase (ExpBase Info VName) Diet)
-> Subst StructRetType
-> Subst (RetTypeBase (ExpBase Info VName) Diet)
forall a b. (a -> b) -> a -> b
$ (NoUniqueness -> Diet)
-> StructRetType -> RetTypeBase (ExpBase Info VName) Diet
forall b c a. (b -> c) -> RetTypeBase a b -> RetTypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second ((NoUniqueness -> Diet)
 -> StructRetType -> RetTypeBase (ExpBase Info VName) Diet)
-> (NoUniqueness -> Diet)
-> StructRetType
-> RetTypeBase (ExpBase Info VName) Diet
forall a b. (a -> b) -> a -> b
$ Diet -> NoUniqueness -> Diet
forall a b. a -> b -> a
const Diet
Observe) (Maybe (Subst StructRetType)
 -> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet)))
-> TypeSubs
-> VName
-> Maybe (Subst (RetTypeBase (ExpBase Info VName) Diet))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
f

instance Substitutable (TypeBase Size Uniqueness) where
  applySubst :: TypeSubs
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
applySubst TypeSubs
f = (VName -> Maybe (Subst ResRetType))
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
substTypesAny ((VName -> Maybe (Subst ResRetType))
 -> TypeBase (ExpBase Info VName) Uniqueness
 -> TypeBase (ExpBase Info VName) Uniqueness)
-> (VName -> Maybe (Subst ResRetType))
-> TypeBase (ExpBase Info VName) Uniqueness
-> TypeBase (ExpBase Info VName) Uniqueness
forall a b. (a -> b) -> a -> b
$ (Subst StructRetType -> Subst ResRetType)
-> Maybe (Subst StructRetType) -> Maybe (Subst ResRetType)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((StructRetType -> ResRetType)
-> Subst StructRetType -> Subst ResRetType
forall a b. (a -> b) -> Subst a -> Subst b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((StructRetType -> ResRetType)
 -> Subst StructRetType -> Subst ResRetType)
-> (StructRetType -> ResRetType)
-> Subst StructRetType
-> Subst ResRetType
forall a b. (a -> b) -> a -> b
$ (NoUniqueness -> Uniqueness) -> StructRetType -> ResRetType
forall b c a. (b -> c) -> RetTypeBase a b -> RetTypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second ((NoUniqueness -> Uniqueness) -> StructRetType -> ResRetType)
-> (NoUniqueness -> Uniqueness) -> StructRetType -> ResRetType
forall a b. (a -> b) -> a -> b
$ Uniqueness -> NoUniqueness -> Uniqueness
forall a b. a -> b -> a
const Uniqueness
Nonunique) (Maybe (Subst StructRetType) -> Maybe (Subst ResRetType))
-> TypeSubs -> VName -> Maybe (Subst ResRetType)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
f

instance Substitutable Exp where
  applySubst :: TypeSubs -> ExpBase Info VName -> ExpBase Info VName
applySubst TypeSubs
f = Identity (ExpBase Info VName) -> ExpBase Info VName
forall a. Identity a -> a
runIdentity (Identity (ExpBase Info VName) -> ExpBase Info VName)
-> (ExpBase Info VName -> Identity (ExpBase Info VName))
-> ExpBase Info VName
-> ExpBase Info VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp
    where
      mapOnExp :: ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp (Var (QualName [VName]
_ VName
v) Info StructType
_ SrcLoc
_)
        | Just (ExpSubst ExpBase Info VName
e') <- TypeSubs
f VName
v = ExpBase Info VName -> Identity (ExpBase Info VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ExpBase Info VName
e'
      mapOnExp ExpBase Info VName
e' = ASTMapper Identity
-> ExpBase Info VName -> Identity (ExpBase Info VName)
forall x (m :: * -> *).
(ASTMappable x, Monad m) =>
ASTMapper m -> x -> m x
forall (m :: * -> *).
Monad m =>
ASTMapper m -> ExpBase Info VName -> m (ExpBase Info VName)
astMap ASTMapper Identity
mapper ExpBase Info VName
e'

      mapper :: ASTMapper Identity
mapper =
        ASTMapper
          { ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp :: ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp :: ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp,
            mapOnName :: QualName VName -> Identity (QualName VName)
mapOnName = QualName VName -> Identity (QualName VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure,
            mapOnStructType :: StructType -> Identity StructType
mapOnStructType = StructType -> Identity StructType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (StructType -> Identity StructType)
-> (StructType -> StructType) -> StructType -> Identity StructType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> StructType -> StructType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnParamType :: TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
mapOnParamType = TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) Diet
 -> Identity (TypeBase (ExpBase Info VName) Diet))
-> (TypeBase (ExpBase Info VName) Diet
    -> TypeBase (ExpBase Info VName) Diet)
-> TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnResRetType :: ResRetType -> Identity ResRetType
mapOnResRetType = ResRetType -> Identity ResRetType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ResRetType -> Identity ResRetType)
-> (ResRetType -> ResRetType) -> ResRetType -> Identity ResRetType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> ResRetType -> ResRetType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f
          }

instance (Substitutable d) => Substitutable (Shape d) where
  applySubst :: TypeSubs -> Shape d -> Shape d
applySubst TypeSubs
f = (d -> d) -> Shape d -> Shape d
forall a b. (a -> b) -> Shape a -> Shape b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((d -> d) -> Shape d -> Shape d) -> (d -> d) -> Shape d -> Shape d
forall a b. (a -> b) -> a -> b
$ TypeSubs -> d -> d
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f

instance Substitutable (Pat StructType) where
  applySubst :: TypeSubs -> Pat StructType -> Pat StructType
applySubst TypeSubs
f = Identity (Pat StructType) -> Pat StructType
forall a. Identity a -> a
runIdentity (Identity (Pat StructType) -> Pat StructType)
-> (Pat StructType -> Identity (Pat StructType))
-> Pat StructType
-> Pat StructType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ASTMapper Identity -> Pat StructType -> Identity (Pat StructType)
forall x (m :: * -> *).
(ASTMappable x, Monad m) =>
ASTMapper m -> x -> m x
forall (m :: * -> *).
Monad m =>
ASTMapper m -> Pat StructType -> m (Pat StructType)
astMap ASTMapper Identity
mapper
    where
      mapper :: ASTMapper Identity
mapper =
        ASTMapper
          { mapOnExp :: ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp = ExpBase Info VName -> Identity (ExpBase Info VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ExpBase Info VName -> Identity (ExpBase Info VName))
-> (ExpBase Info VName -> ExpBase Info VName)
-> ExpBase Info VName
-> Identity (ExpBase Info VName)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> ExpBase Info VName -> ExpBase Info VName
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnName :: QualName VName -> Identity (QualName VName)
mapOnName = QualName VName -> Identity (QualName VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure,
            mapOnStructType :: StructType -> Identity StructType
mapOnStructType = StructType -> Identity StructType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (StructType -> Identity StructType)
-> (StructType -> StructType) -> StructType -> Identity StructType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> StructType -> StructType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnParamType :: TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
mapOnParamType = TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) Diet
 -> Identity (TypeBase (ExpBase Info VName) Diet))
-> (TypeBase (ExpBase Info VName) Diet
    -> TypeBase (ExpBase Info VName) Diet)
-> TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnResRetType :: ResRetType -> Identity ResRetType
mapOnResRetType = ResRetType -> Identity ResRetType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ResRetType -> Identity ResRetType)
-> (ResRetType -> ResRetType) -> ResRetType -> Identity ResRetType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> ResRetType -> ResRetType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f
          }

instance Substitutable (Pat ParamType) where
  applySubst :: TypeSubs
-> Pat (TypeBase (ExpBase Info VName) Diet)
-> Pat (TypeBase (ExpBase Info VName) Diet)
applySubst TypeSubs
f = Identity (Pat (TypeBase (ExpBase Info VName) Diet))
-> Pat (TypeBase (ExpBase Info VName) Diet)
forall a. Identity a -> a
runIdentity (Identity (Pat (TypeBase (ExpBase Info VName) Diet))
 -> Pat (TypeBase (ExpBase Info VName) Diet))
-> (Pat (TypeBase (ExpBase Info VName) Diet)
    -> Identity (Pat (TypeBase (ExpBase Info VName) Diet)))
-> Pat (TypeBase (ExpBase Info VName) Diet)
-> Pat (TypeBase (ExpBase Info VName) Diet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ASTMapper Identity
-> Pat (TypeBase (ExpBase Info VName) Diet)
-> Identity (Pat (TypeBase (ExpBase Info VName) Diet))
forall x (m :: * -> *).
(ASTMappable x, Monad m) =>
ASTMapper m -> x -> m x
forall (m :: * -> *).
Monad m =>
ASTMapper m
-> Pat (TypeBase (ExpBase Info VName) Diet)
-> m (Pat (TypeBase (ExpBase Info VName) Diet))
astMap ASTMapper Identity
mapper
    where
      mapper :: ASTMapper Identity
mapper =
        ASTMapper
          { mapOnExp :: ExpBase Info VName -> Identity (ExpBase Info VName)
mapOnExp = ExpBase Info VName -> Identity (ExpBase Info VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ExpBase Info VName -> Identity (ExpBase Info VName))
-> (ExpBase Info VName -> ExpBase Info VName)
-> ExpBase Info VName
-> Identity (ExpBase Info VName)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> ExpBase Info VName -> ExpBase Info VName
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnName :: QualName VName -> Identity (QualName VName)
mapOnName = QualName VName -> Identity (QualName VName)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure,
            mapOnStructType :: StructType -> Identity StructType
mapOnStructType = StructType -> Identity StructType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (StructType -> Identity StructType)
-> (StructType -> StructType) -> StructType -> Identity StructType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> StructType -> StructType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnParamType :: TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
mapOnParamType = TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) Diet
 -> Identity (TypeBase (ExpBase Info VName) Diet))
-> (TypeBase (ExpBase Info VName) Diet
    -> TypeBase (ExpBase Info VName) Diet)
-> TypeBase (ExpBase Info VName) Diet
-> Identity (TypeBase (ExpBase Info VName) Diet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs
-> TypeBase (ExpBase Info VName) Diet
-> TypeBase (ExpBase Info VName) Diet
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f,
            mapOnResRetType :: ResRetType -> Identity ResRetType
mapOnResRetType = ResRetType -> Identity ResRetType
forall a. a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (ResRetType -> Identity ResRetType)
-> (ResRetType -> ResRetType) -> ResRetType -> Identity ResRetType
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TypeSubs -> ResRetType -> ResRetType
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
f
          }

applyType ::
  (Monoid als) =>
  [TypeParam] ->
  TypeBase Size als ->
  [StructTypeArg] ->
  TypeBase Size als
applyType :: forall als.
Monoid als =>
[TypeParam]
-> TypeBase (ExpBase Info VName) als
-> [StructTypeArg]
-> TypeBase (ExpBase Info VName) als
applyType [TypeParam]
ps TypeBase (ExpBase Info VName) als
t [StructTypeArg]
args = (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) als)))
-> TypeBase (ExpBase Info VName) als
-> TypeBase (ExpBase Info VName) als
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
substTypesAny (VName
-> Map VName (Subst (RetTypeBase (ExpBase Info VName) als))
-> Maybe (Subst (RetTypeBase (ExpBase Info VName) als))
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map VName (Subst (RetTypeBase (ExpBase Info VName) als))
substs) TypeBase (ExpBase Info VName) als
t
  where
    substs :: Map VName (Subst (RetTypeBase (ExpBase Info VName) als))
substs = [(VName, Subst (RetTypeBase (ExpBase Info VName) als))]
-> Map VName (Subst (RetTypeBase (ExpBase Info VName) als))
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(VName, Subst (RetTypeBase (ExpBase Info VName) als))]
 -> Map VName (Subst (RetTypeBase (ExpBase Info VName) als)))
-> [(VName, Subst (RetTypeBase (ExpBase Info VName) als))]
-> Map VName (Subst (RetTypeBase (ExpBase Info VName) als))
forall a b. (a -> b) -> a -> b
$ (TypeParam
 -> StructTypeArg
 -> (VName, Subst (RetTypeBase (ExpBase Info VName) als)))
-> [TypeParam]
-> [StructTypeArg]
-> [(VName, Subst (RetTypeBase (ExpBase Info VName) als))]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith TypeParam
-> StructTypeArg
-> (VName, Subst (RetTypeBase (ExpBase Info VName) als))
forall {as} {a}.
(Monoid as, Eq a, IsName a) =>
TypeParamBase a
-> StructTypeArg
-> (a, Subst (RetTypeBase (ExpBase Info VName) as))
mkSubst [TypeParam]
ps [StructTypeArg]
args
    -- We are assuming everything has already been type-checked for correctness.
    mkSubst :: TypeParamBase a
-> StructTypeArg
-> (a, Subst (RetTypeBase (ExpBase Info VName) as))
mkSubst (TypeParamDim a
pv SrcLoc
_) (TypeArgDim ExpBase Info VName
e) =
      (a
pv, ExpBase Info VName -> Subst (RetTypeBase (ExpBase Info VName) as)
forall t. ExpBase Info VName -> Subst t
ExpSubst ExpBase Info VName
e)
    mkSubst (TypeParamType Liftedness
_ a
pv SrcLoc
_) (TypeArgType StructType
at) =
      (a
pv, [TypeParam]
-> RetTypeBase (ExpBase Info VName) as
-> Subst (RetTypeBase (ExpBase Info VName) as)
forall t. [TypeParam] -> t -> Subst t
Subst [] (RetTypeBase (ExpBase Info VName) as
 -> Subst (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> Subst (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [] (TypeBase (ExpBase Info VName) as
 -> RetTypeBase (ExpBase Info VName) as)
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ (NoUniqueness -> as)
-> StructType -> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> TypeBase a b -> TypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second NoUniqueness -> as
forall a. Monoid a => a
mempty StructType
at)
    mkSubst TypeParamBase a
p StructTypeArg
a =
      String -> (a, Subst (RetTypeBase (ExpBase Info VName) as))
forall a. HasCallStack => String -> a
error (String -> (a, Subst (RetTypeBase (ExpBase Info VName) as)))
-> String -> (a, Subst (RetTypeBase (ExpBase Info VName) as))
forall a b. (a -> b) -> a -> b
$ String
"applyType mkSubst: cannot substitute " String -> ShowS
forall a. [a] -> [a] -> [a]
++ StructTypeArg -> String
forall a. Pretty a => a -> String
prettyString StructTypeArg
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" for " String -> ShowS
forall a. [a] -> [a] -> [a]
++ TypeParamBase a -> String
forall a. Pretty a => a -> String
prettyString TypeParamBase a
p

substTypesRet ::
  (Monoid as) =>
  (VName -> Maybe (Subst (RetTypeBase Size as))) ->
  TypeBase Size as ->
  RetTypeBase Size as
substTypesRet :: forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
lookupSubst TypeBase (ExpBase Info VName) as
ot =
  (TypeBase (ExpBase Info VName) as
 -> [VName] -> RetTypeBase (ExpBase Info VName) as)
-> (TypeBase (ExpBase Info VName) as, [VName])
-> RetTypeBase (ExpBase Info VName) as
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (([VName]
 -> TypeBase (ExpBase Info VName) as
 -> RetTypeBase (ExpBase Info VName) as)
-> TypeBase (ExpBase Info VName) as
-> [VName]
-> RetTypeBase (ExpBase Info VName) as
forall a b c. (a -> b -> c) -> b -> a -> c
flip [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType) ((TypeBase (ExpBase Info VName) as, [VName])
 -> RetTypeBase (ExpBase Info VName) as)
-> (TypeBase (ExpBase Info VName) as, [VName])
-> RetTypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ State [VName] (TypeBase (ExpBase Info VName) as)
-> [VName] -> (TypeBase (ExpBase Info VName) as, [VName])
forall s a. State s a -> s -> (a, s)
runState (TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType TypeBase (ExpBase Info VName) as
ot) []
  where
    -- In case we are substituting the same RetType in multiple
    -- places, we must ensure each instance is given distinct
    -- dimensions.  E.g. substituting 'a ↦ ?[n].[n]bool' into '(a,a)'
    -- should give '?[n][m].([n]bool,[m]bool)'.
    --
    -- XXX: the size names we invent here not globally unique.  This
    -- is _probably_ not a problem, since substituting types with
    -- outermost non-null existential sizes is done only when type
    -- checking modules.
    freshDims :: RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
freshDims (RetType [] TypeBase (ExpBase Info VName) as
t) = RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (RetTypeBase (ExpBase Info VName) as
 -> f (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [] TypeBase (ExpBase Info VName) as
t
    freshDims (RetType [VName]
ext TypeBase (ExpBase Info VName) as
t) = do
      [VName]
seen_ext <- f [VName]
forall s (m :: * -> *). MonadState s m => m s
get
      if Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (VName -> Bool) -> [VName] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (VName -> [VName] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [VName]
seen_ext) [VName]
ext
        then RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (RetTypeBase (ExpBase Info VName) as
 -> f (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
ext TypeBase (ExpBase Info VName) as
t
        else do
          let start :: Int
start = [Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([Int] -> Int) -> [Int] -> Int
forall a b. (a -> b) -> a -> b
$ (VName -> Int) -> [VName] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map VName -> Int
baseTag [VName]
seen_ext
              ext' :: [VName]
ext' = (Name -> Int -> VName) -> [Name] -> [Int] -> [VName]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Name -> Int -> VName
VName ((VName -> Name) -> [VName] -> [Name]
forall a b. (a -> b) -> [a] -> [b]
map VName -> Name
baseName [VName]
ext) [Int
start Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 ..]
              mkSubst :: VName -> Subst t
mkSubst = ExpBase Info VName -> Subst t
forall t. ExpBase Info VName -> Subst t
ExpSubst (ExpBase Info VName -> Subst t)
-> (VName -> ExpBase Info VName) -> VName -> Subst t
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (QualName VName -> SrcLoc -> ExpBase Info VName)
-> SrcLoc -> QualName VName -> ExpBase Info VName
forall a b c. (a -> b -> c) -> b -> a -> c
flip QualName VName -> SrcLoc -> ExpBase Info VName
sizeFromName SrcLoc
forall a. Monoid a => a
mempty (QualName VName -> ExpBase Info VName)
-> (VName -> QualName VName) -> VName -> ExpBase Info VName
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VName -> QualName VName
forall v. v -> QualName v
qualName
              extsubsts :: Map VName (Subst t)
extsubsts = [(VName, Subst t)] -> Map VName (Subst t)
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList ([(VName, Subst t)] -> Map VName (Subst t))
-> [(VName, Subst t)] -> Map VName (Subst t)
forall a b. (a -> b) -> a -> b
$ [VName] -> [Subst t] -> [(VName, Subst t)]
forall a b. [a] -> [b] -> [(a, b)]
zip [VName]
ext ([Subst t] -> [(VName, Subst t)])
-> [Subst t] -> [(VName, Subst t)]
forall a b. (a -> b) -> a -> b
$ (VName -> Subst t) -> [VName] -> [Subst t]
forall a b. (a -> b) -> [a] -> [b]
map VName -> Subst t
forall {t}. VName -> Subst t
mkSubst [VName]
ext'
              RetType [] TypeBase (ExpBase Info VName) as
t' = (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet (VName
-> Map VName (Subst (RetTypeBase (ExpBase Info VName) as))
-> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map VName (Subst (RetTypeBase (ExpBase Info VName) as))
forall {t}. Map VName (Subst t)
extsubsts) TypeBase (ExpBase Info VName) as
t
          RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (RetTypeBase (ExpBase Info VName) as
 -> f (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
ext' TypeBase (ExpBase Info VName) as
t'

    onType ::
      forall as.
      (Monoid as) =>
      TypeBase Size as ->
      State [VName] (TypeBase Size as)

    onType :: forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType (Array as
u Shape (ExpBase Info VName)
shape ScalarTypeBase (ExpBase Info VName) NoUniqueness
et) =
      as
-> Shape (ExpBase Info VName)
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall u dim. u -> Shape dim -> TypeBase dim u -> TypeBase dim u
arrayOfWithAliases as
u (TypeSubs
-> Shape (ExpBase Info VName) -> Shape (ExpBase Info VName)
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
lookupSubst' Shape (ExpBase Info VName)
shape)
        (TypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType ((NoUniqueness -> as)
-> StructType -> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> TypeBase a b -> TypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (as -> NoUniqueness -> as
forall a b. a -> b -> a
const as
forall a. Monoid a => a
mempty) (StructType -> TypeBase (ExpBase Info VName) as)
-> StructType -> TypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) NoUniqueness -> StructType
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar ScalarTypeBase (ExpBase Info VName) NoUniqueness
et)
    onType (Scalar (Prim PrimType
t)) = TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a. a -> StateT [VName] Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) as
 -> StateT [VName] Identity (TypeBase (ExpBase Info VName) as))
-> TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ PrimType -> ScalarTypeBase (ExpBase Info VName) as
forall dim u. PrimType -> ScalarTypeBase dim u
Prim PrimType
t
    onType (Scalar (TypeVar as
u QualName VName
v [StructTypeArg]
targs)) = do
      [StructTypeArg]
targs' <- (StructTypeArg -> StateT [VName] Identity StructTypeArg)
-> [StructTypeArg] -> StateT [VName] Identity [StructTypeArg]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM StructTypeArg -> StateT [VName] Identity StructTypeArg
forall {m :: * -> *}.
MonadState [VName] m =>
StructTypeArg -> m StructTypeArg
subsTypeArg [StructTypeArg]
targs
      case VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
lookupSubst (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
forall a b. (a -> b) -> a -> b
$ QualName VName -> VName
forall vn. QualName vn -> vn
qualLeaf QualName VName
v of
        Just (Subst [TypeParam]
ps RetTypeBase (ExpBase Info VName) as
rt) -> do
          RetType [VName]
ext TypeBase (ExpBase Info VName) as
t <- RetTypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (RetTypeBase (ExpBase Info VName) as)
forall {f :: * -> *} {as}.
(MonadState [VName] f, Monoid as) =>
RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
freshDims RetTypeBase (ExpBase Info VName) as
rt
          ([VName] -> [VName]) -> StateT [VName] Identity ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ([VName]
ext ++)
          TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a. a -> StateT [VName] Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) as
 -> StateT [VName] Identity (TypeBase (ExpBase Info VName) as))
-> TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ (as -> as)
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> TypeBase a b -> TypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (as -> as -> as
forall a. Semigroup a => a -> a -> a
<> as
u) (TypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ [TypeParam]
-> TypeBase (ExpBase Info VName) as
-> [StructTypeArg]
-> TypeBase (ExpBase Info VName) as
forall als.
Monoid als =>
[TypeParam]
-> TypeBase (ExpBase Info VName) als
-> [StructTypeArg]
-> TypeBase (ExpBase Info VName) als
applyType [TypeParam]
ps ((as -> as)
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> TypeBase a b -> TypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (as -> as -> as
forall a b. a -> b -> a
const as
u) TypeBase (ExpBase Info VName) as
t) [StructTypeArg]
targs'
        Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
_ ->
          TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a. a -> StateT [VName] Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (TypeBase (ExpBase Info VName) as
 -> StateT [VName] Identity (TypeBase (ExpBase Info VName) as))
-> TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall a b. (a -> b) -> a -> b
$ as
-> QualName VName
-> [StructTypeArg]
-> ScalarTypeBase (ExpBase Info VName) as
forall dim u.
u -> QualName VName -> [TypeArg dim] -> ScalarTypeBase dim u
TypeVar as
u QualName VName
v [StructTypeArg]
targs'
    onType (Scalar (Record Map Name (TypeBase (ExpBase Info VName) as)
ts)) =
      ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> (Map Name (TypeBase (ExpBase Info VName) as)
    -> ScalarTypeBase (ExpBase Info VName) as)
-> Map Name (TypeBase (ExpBase Info VName) as)
-> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map Name (TypeBase (ExpBase Info VName) as)
-> ScalarTypeBase (ExpBase Info VName) as
forall dim u. Map Name (TypeBase dim u) -> ScalarTypeBase dim u
Record (Map Name (TypeBase (ExpBase Info VName) as)
 -> TypeBase (ExpBase Info VName) as)
-> StateT
     [VName] Identity (Map Name (TypeBase (ExpBase Info VName) as))
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TypeBase (ExpBase Info VName) as
 -> StateT [VName] Identity (TypeBase (ExpBase Info VName) as))
-> Map Name (TypeBase (ExpBase Info VName) as)
-> StateT
     [VName] Identity (Map Name (TypeBase (ExpBase Info VName) as))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map Name a -> f (Map Name b)
traverse TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType Map Name (TypeBase (ExpBase Info VName) as)
ts
    onType (Scalar (Arrow as
als PName
v Diet
d StructType
t1 ResRetType
t2)) =
      ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity (ScalarTypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (as
-> PName
-> Diet
-> StructType
-> ResRetType
-> ScalarTypeBase (ExpBase Info VName) as
forall dim u.
u
-> PName
-> Diet
-> TypeBase dim NoUniqueness
-> RetTypeBase dim Uniqueness
-> ScalarTypeBase dim u
Arrow as
als PName
v Diet
d (StructType
 -> ResRetType -> ScalarTypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity StructType
-> StateT
     [VName]
     Identity
     (ResRetType -> ScalarTypeBase (ExpBase Info VName) as)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> StructType -> StateT [VName] Identity StructType
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType StructType
t1 StateT
  [VName]
  Identity
  (ResRetType -> ScalarTypeBase (ExpBase Info VName) as)
-> StateT [VName] Identity ResRetType
-> StateT [VName] Identity (ScalarTypeBase (ExpBase Info VName) as)
forall a b.
StateT [VName] Identity (a -> b)
-> StateT [VName] Identity a -> StateT [VName] Identity b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ResRetType -> StateT [VName] Identity ResRetType
forall {f :: * -> *} {as}.
(MonadState [VName] f, Monoid as) =>
RetTypeBase (ExpBase Info VName) as
-> f (RetTypeBase (ExpBase Info VName) as)
onRetType ResRetType
t2)
    onType (Scalar (Sum Map Name [TypeBase (ExpBase Info VName) as]
ts)) =
      ScalarTypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall dim u. ScalarTypeBase dim u -> TypeBase dim u
Scalar (ScalarTypeBase (ExpBase Info VName) as
 -> TypeBase (ExpBase Info VName) as)
-> (Map Name [TypeBase (ExpBase Info VName) as]
    -> ScalarTypeBase (ExpBase Info VName) as)
-> Map Name [TypeBase (ExpBase Info VName) as]
-> TypeBase (ExpBase Info VName) as
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map Name [TypeBase (ExpBase Info VName) as]
-> ScalarTypeBase (ExpBase Info VName) as
forall dim u. Map Name [TypeBase dim u] -> ScalarTypeBase dim u
Sum (Map Name [TypeBase (ExpBase Info VName) as]
 -> TypeBase (ExpBase Info VName) as)
-> StateT
     [VName] Identity (Map Name [TypeBase (ExpBase Info VName) as])
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([TypeBase (ExpBase Info VName) as]
 -> StateT [VName] Identity [TypeBase (ExpBase Info VName) as])
-> Map Name [TypeBase (ExpBase Info VName) as]
-> StateT
     [VName] Identity (Map Name [TypeBase (ExpBase Info VName) as])
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map Name a -> f (Map Name b)
traverse ((TypeBase (ExpBase Info VName) as
 -> StateT [VName] Identity (TypeBase (ExpBase Info VName) as))
-> [TypeBase (ExpBase Info VName) as]
-> StateT [VName] Identity [TypeBase (ExpBase Info VName) as]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse TypeBase (ExpBase Info VName) as
-> StateT [VName] Identity (TypeBase (ExpBase Info VName) as)
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType) Map Name [TypeBase (ExpBase Info VName) as]
ts

    onRetType :: RetTypeBase (ExpBase Info VName) as
-> m (RetTypeBase (ExpBase Info VName) as)
onRetType (RetType [VName]
dims TypeBase (ExpBase Info VName) as
t) = do
      [VName]
ext <- m [VName]
forall s (m :: * -> *). MonadState s m => m s
get
      let (TypeBase (ExpBase Info VName) as
t', [VName]
ext') = State [VName] (TypeBase (ExpBase Info VName) as)
-> [VName] -> (TypeBase (ExpBase Info VName) as, [VName])
forall s a. State s a -> s -> (a, s)
runState (TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
forall as.
Monoid as =>
TypeBase (ExpBase Info VName) as
-> State [VName] (TypeBase (ExpBase Info VName) as)
onType TypeBase (ExpBase Info VName) as
t) [VName]
ext
          new_ext :: [VName]
new_ext = [VName]
ext' [VName] -> [VName] -> [VName]
forall a. Eq a => [a] -> [a] -> [a]
\\ [VName]
ext
      case TypeBase (ExpBase Info VName) as
t of
        Scalar Arrow {} -> do
          [VName] -> m ()
forall s (m :: * -> *). MonadState s m => s -> m ()
put [VName]
ext'
          RetTypeBase (ExpBase Info VName) as
-> m (RetTypeBase (ExpBase Info VName) as)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (RetTypeBase (ExpBase Info VName) as
 -> m (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> m (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType [VName]
dims TypeBase (ExpBase Info VName) as
t'
        TypeBase (ExpBase Info VName) as
_ ->
          RetTypeBase (ExpBase Info VName) as
-> m (RetTypeBase (ExpBase Info VName) as)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (RetTypeBase (ExpBase Info VName) as
 -> m (RetTypeBase (ExpBase Info VName) as))
-> RetTypeBase (ExpBase Info VName) as
-> m (RetTypeBase (ExpBase Info VName) as)
forall a b. (a -> b) -> a -> b
$ [VName]
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall dim as. [VName] -> TypeBase dim as -> RetTypeBase dim as
RetType ([VName]
new_ext [VName] -> [VName] -> [VName]
forall a. Semigroup a => a -> a -> a
<> [VName]
dims) TypeBase (ExpBase Info VName) as
t'

    subsTypeArg :: StructTypeArg -> m StructTypeArg
subsTypeArg (TypeArgType StructType
t) = do
      let RetType [VName]
dims StructType
t' = TypeSubs -> StructType -> StructRetType
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet TypeSubs
lookupSubst' StructType
t
      ([VName] -> [VName]) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ([VName]
dims ++)
      StructTypeArg -> m StructTypeArg
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (StructTypeArg -> m StructTypeArg)
-> StructTypeArg -> m StructTypeArg
forall a b. (a -> b) -> a -> b
$ StructType -> StructTypeArg
forall dim. TypeBase dim NoUniqueness -> TypeArg dim
TypeArgType StructType
t'
    subsTypeArg (TypeArgDim ExpBase Info VName
v) =
      StructTypeArg -> m StructTypeArg
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (StructTypeArg -> m StructTypeArg)
-> StructTypeArg -> m StructTypeArg
forall a b. (a -> b) -> a -> b
$ ExpBase Info VName -> StructTypeArg
forall dim. dim -> TypeArg dim
TypeArgDim (ExpBase Info VName -> StructTypeArg)
-> ExpBase Info VName -> StructTypeArg
forall a b. (a -> b) -> a -> b
$ TypeSubs -> ExpBase Info VName -> ExpBase Info VName
forall a. Substitutable a => TypeSubs -> a -> a
applySubst TypeSubs
lookupSubst' ExpBase Info VName
v

    lookupSubst' :: TypeSubs
lookupSubst' = (Subst (RetTypeBase (ExpBase Info VName) as)
 -> Subst StructRetType)
-> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
-> Maybe (Subst StructRetType)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((RetTypeBase (ExpBase Info VName) as -> StructRetType)
-> Subst (RetTypeBase (ExpBase Info VName) as)
-> Subst StructRetType
forall a b. (a -> b) -> Subst a -> Subst b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((RetTypeBase (ExpBase Info VName) as -> StructRetType)
 -> Subst (RetTypeBase (ExpBase Info VName) as)
 -> Subst StructRetType)
-> (RetTypeBase (ExpBase Info VName) as -> StructRetType)
-> Subst (RetTypeBase (ExpBase Info VName) as)
-> Subst StructRetType
forall a b. (a -> b) -> a -> b
$ (as -> NoUniqueness)
-> RetTypeBase (ExpBase Info VName) as -> StructRetType
forall b c a. (b -> c) -> RetTypeBase a b -> RetTypeBase a c
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (NoUniqueness -> as -> NoUniqueness
forall a b. a -> b -> a
const NoUniqueness
NoUniqueness)) (Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
 -> Maybe (Subst StructRetType))
-> (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeSubs
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
lookupSubst

-- | Perform substitutions, from type names to types, on a type. Works
-- regardless of what shape and uniqueness information is attached to the type.
substTypesAny ::
  (Monoid as) =>
  (VName -> Maybe (Subst (RetTypeBase Size as))) ->
  TypeBase Size as ->
  TypeBase Size as
substTypesAny :: forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
substTypesAny VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
lookupSubst TypeBase (ExpBase Info VName) as
ot =
  case (VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
forall as.
Monoid as =>
(VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as)))
-> TypeBase (ExpBase Info VName) as
-> RetTypeBase (ExpBase Info VName) as
substTypesRet VName -> Maybe (Subst (RetTypeBase (ExpBase Info VName) as))
lookupSubst TypeBase (ExpBase Info VName) as
ot of
    RetType [] TypeBase (ExpBase Info VName) as
ot' -> TypeBase (ExpBase Info VName) as
ot'
    RetType [VName]
dims TypeBase (ExpBase Info VName) as
ot' ->
      -- XXX HACK FIXME: turn any sizes that propagate to the top into
      -- AnySize.  This should _never_ happen during type-checking, but
      -- may happen as we substitute types during monomorphisation and
      -- defunctorisation later on. See Note [AnySize]
      let toAny :: ExpBase Info VName -> ExpBase Info VName
toAny (Var QualName VName
v Info StructType
_ SrcLoc
_) | QualName VName -> VName
forall vn. QualName vn -> vn
qualLeaf QualName VName
v VName -> [VName] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [VName]
dims = ExpBase Info VName
anySize
          toAny ExpBase Info VName
d = ExpBase Info VName
d
       in (ExpBase Info VName -> ExpBase Info VName)
-> TypeBase (ExpBase Info VName) as
-> TypeBase (ExpBase Info VName) as
forall a b c. (a -> b) -> TypeBase a c -> TypeBase b c
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first ExpBase Info VName -> ExpBase Info VName
toAny TypeBase (ExpBase Info VName) as
ot'

-- Note [AnySize]
--
-- Consider a program:
--
-- module m : { type~ t } = { type~ t = ?[n].[n]bool }
-- let f (x: m.t) (y: m.t) = 0
--
-- After defunctorisation (and inlining the definitions of types), we
-- want this:
--
-- let f [n][m] (x: [n]bool) (y: [m]bool) = 0
--
-- But this means that defunctorisation would need to redo some amount
-- of size inference.  Not so complicated in the example above, but
-- what if loops and branches are involved?
--
-- So instead, what defunctorisation actually does is produce this:
--
-- let f (x: []bool) (y: []bool) = 0
--
-- I.e. we put in empty dimensions (AnySize), which are much later
-- turned into distinct sizes in Futhark.Internalise.Exps.  This will
-- result in unnecessary dynamic size checks, which will hopefully be
-- optimised away.
--
-- Important: The type checker will _never_ produce programs with
-- AnySize, but unfortunately some of the compilation steps
-- (defunctorisation, monomorphisation, defunctionalisation) will do
-- so.  Similarly, the core language is also perfectly well behaved.
--
-- Example with monomorphisation:
--
-- let f '~a (b: bool) (x: () -> a) (y: () -> a) : a = if b then x () else y ()
-- let g = f true (\() -> [1]) (\() -> [1,2])
--
-- This should produce:
--
-- let f (b: bool) (x: () -> ?[n].[n]i32) (y: () -> ?[m].[m]i32) : ?[k].[k]i32 =
--   if b then x () else y ()
--
-- Not so easy!  Again, what we actually produce is
--
-- let f (b: bool) (x: () -> []i32) (y: () -> []i32) : []i32 =
--   if b then x () else y ()