-- (c) The University of Glasgow 2006
-- (c) The GRASP/AQUA Project, Glasgow University, 1998
--
-- Type - public interface

{-# LANGUAGE FlexibleContexts, PatternSynonyms, ViewPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}
{-# OPTIONS_GHC -Wno-incomplete-record-updates #-}

-- | Main functions for manipulating types and type-related things
module GHC.Core.Type (
        -- Note some of this is just re-exports from TyCon..

        -- * Main data types representing Types
        -- $type_classification

        -- $representation_types
        Type, ArgFlag(..), AnonArgFlag(..),
        Specificity(..),
        KindOrType, PredType, ThetaType, FRRType,
        Var, TyVar, isTyVar, TyCoVar, TyCoBinder, TyCoVarBinder, TyVarBinder,
        Mult, Scaled,
        KnotTied,

        -- ** Constructing and deconstructing types
        mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, repGetTyVar_maybe,
        getCastedTyVar_maybe, tyVarKind, varType,

        mkAppTy, mkAppTys, splitAppTy, splitAppTys, repSplitAppTys,
        splitAppTy_maybe, repSplitAppTy_maybe, tcRepSplitAppTy_maybe,

        mkFunTy, mkVisFunTy, mkInvisFunTy,
        mkVisFunTys,
        mkVisFunTyMany, mkInvisFunTyMany,
        mkVisFunTysMany, mkInvisFunTysMany,
        splitFunTy, splitFunTy_maybe,
        splitFunTys, funResultTy, funArgTy,

        mkTyConApp, mkTyConTy, mkTYPEapp,
        tyConAppTyCon_maybe, tyConAppTyConPicky_maybe,
        tyConAppArgs_maybe, tyConAppTyCon, tyConAppArgs,
        splitTyConApp_maybe, splitTyConApp, tyConAppArgN,
        tcSplitTyConApp_maybe,
        splitListTyConApp_maybe,
        repSplitTyConApp_maybe,
        tcRepSplitTyConApp_maybe,

        mkForAllTy, mkForAllTys, mkInvisForAllTys, mkTyCoInvForAllTys,
        mkSpecForAllTy, mkSpecForAllTys,
        mkVisForAllTys, mkTyCoInvForAllTy,
        mkInfForAllTy, mkInfForAllTys,
        splitForAllTyCoVars,
        splitForAllReqTVBinders, splitForAllInvisTVBinders,
        splitForAllTyCoVarBinders,
        splitForAllTyCoVar_maybe, splitForAllTyCoVar,
        splitForAllTyVar_maybe, splitForAllCoVar_maybe,
        splitPiTy_maybe, splitPiTy, splitPiTys,
        getRuntimeArgTys,
        mkTyConBindersPreferAnon,
        mkPiTy, mkPiTys,
        piResultTy, piResultTys,
        applyTysX, dropForAlls,
        mkFamilyTyConApp,
        buildSynTyCon,

        mkNumLitTy, isNumLitTy,
        mkStrLitTy, isStrLitTy,
        mkCharLitTy, isCharLitTy,
        isLitTy,

        isPredTy,

        getRuntimeRep_maybe, kindRep_maybe, kindRep,

        mkCastTy, mkCoercionTy, splitCastTy_maybe,

        userTypeError_maybe, pprUserTypeErrorTy,

        coAxNthLHS,
        stripCoercionTy,

        splitInvisPiTys, splitInvisPiTysN,
        invisibleTyBndrCount,
        filterOutInvisibleTypes, filterOutInferredTypes,
        partitionInvisibleTypes, partitionInvisibles,
        tyConArgFlags, appTyArgFlags,

        -- ** Analyzing types
        TyCoMapper(..), mapTyCo, mapTyCoX,
        TyCoFolder(..), foldTyCo, noView,

        -- (Newtypes)
        newTyConInstRhs,

        -- ** Binders
        sameVis,
        mkTyCoVarBinder, mkTyCoVarBinders,
        mkTyVarBinder, mkTyVarBinders,
        tyVarSpecToBinders,
        mkAnonBinder,
        isAnonTyCoBinder,
        binderVar, binderVars, binderType, binderArgFlag,
        tyCoBinderType, tyCoBinderVar_maybe,
        tyBinderType,
        binderRelevantType_maybe,
        isVisibleArgFlag, isInvisibleArgFlag, isVisibleBinder,
        isInvisibleBinder, isNamedBinder,
        tyConBindersTyCoBinders,

        -- ** Common type constructors
        funTyCon, unrestrictedFunTyCon,

        -- ** Predicates on types
        isTyVarTy, isFunTy, isCoercionTy,
        isCoercionTy_maybe, isForAllTy,
        isForAllTy_ty, isForAllTy_co,
        isPiTy, isTauTy, isFamFreeTy,
        isCoVarType, isAtomicTy,

        isValidJoinPointType,
        tyConAppNeedsKindSig,

        -- *** Levity and boxity
        typeLevity_maybe,
        isLiftedTypeKind, isUnliftedTypeKind, pickyIsLiftedTypeKind,
        isLiftedRuntimeRep, isUnliftedRuntimeRep, runtimeRepLevity_maybe,
        isBoxedRuntimeRep,
        isLiftedLevity, isUnliftedLevity,
        isUnliftedType, isBoxedType, isUnboxedTupleType, isUnboxedSumType,
        kindBoxedRepLevity_maybe,
        mightBeLiftedType, mightBeUnliftedType,
        isAlgType, isDataFamilyAppType,
        isPrimitiveType, isStrictType,
        isLevityTy, isLevityVar,
        isRuntimeRepTy, isRuntimeRepVar, isRuntimeRepKindedTy,
        dropRuntimeRepArgs,
        getRuntimeRep, getLevity, getLevity_maybe,

        -- * Multiplicity

        isMultiplicityTy, isMultiplicityVar,
        unrestricted, linear, tymult,
        mkScaled, irrelevantMult, scaledSet,
        pattern One, pattern Many,
        isOneDataConTy, isManyDataConTy,
        isLinearType,

        -- * Main data types representing Kinds
        Kind,

        -- ** Finding the kind of a type
        typeKind, tcTypeKind, typeHasFixedRuntimeRep, argsHaveFixedRuntimeRep,
        tcIsLiftedTypeKind, tcIsConstraintKind, tcReturnsConstraintKind,
        tcIsBoxedTypeKind, tcIsRuntimeTypeKind,

        -- ** Common Kind
        liftedTypeKind, unliftedTypeKind,

        -- * Type free variables
        tyCoFVsOfType, tyCoFVsBndr, tyCoFVsVarBndr, tyCoFVsVarBndrs,
        tyCoVarsOfType, tyCoVarsOfTypes,
        tyCoVarsOfTypeDSet,
        coVarsOfType,
        coVarsOfTypes,

        anyFreeVarsOfType, anyFreeVarsOfTypes,
        noFreeVarsOfType,
        splitVisVarsOfType, splitVisVarsOfTypes,
        expandTypeSynonyms,
        typeSize, occCheckExpand,

        -- ** Closing over kinds
        closeOverKindsDSet, closeOverKindsList,
        closeOverKinds,

        -- * Well-scoped lists of variables
        scopedSort, tyCoVarsOfTypeWellScoped,
        tyCoVarsOfTypesWellScoped,

        -- * Type comparison
        eqType, eqTypeX, eqTypes, nonDetCmpType, nonDetCmpTypes, nonDetCmpTypeX,
        nonDetCmpTypesX, nonDetCmpTc,
        eqVarBndrs,

        -- * Forcing evaluation of types
        seqType, seqTypes,

        -- * Other views onto Types
        coreView, tcView,

        tyConsOfType,

        -- * Main type substitution data types
        TvSubstEnv,     -- Representation widely visible
        IdSubstEnv,
        Subst(..),    -- Representation visible to a few friends

        -- ** Manipulating type substitutions
        emptyTvSubstEnv, emptySubst, mkEmptySubst,

        mkSubst, zipTvSubst, mkTvSubstPrs,
        zipTCvSubst,
        notElemSubst,
        getTvSubstEnv,
        zapSubst, getSubstInScope, setInScope, getSubstRangeTyCoFVs,
        extendSubstInScope, extendSubstInScopeList, extendSubstInScopeSet,
        extendTCvSubst, extendCvSubst,
        extendTvSubst, extendTvSubstBinderAndInScope,
        extendTvSubstList, extendTvSubstAndInScope,
        extendTCvSubstList,
        extendTvSubstWithClone,
        extendTCvSubstWithClone,
        isInScope, composeTCvSubst, zipTyEnv, zipCoEnv,
        isEmptySubst, unionSubst, isEmptyTCvSubst,

        -- ** Performing substitution on types and kinds
        substTy, substTys, substScaledTy, substScaledTys, substTyWith, substTysWith, substTheta,
        substTyAddInScope,
        substTyUnchecked, substTysUnchecked, substScaledTyUnchecked, substScaledTysUnchecked,
        substThetaUnchecked, substTyWithUnchecked,
        substCoUnchecked, substCoWithUnchecked,
        substTyVarBndr, substTyVarBndrs, substTyVar, substTyVars,
        substVarBndr, substVarBndrs,
        substTyCoBndr,
        cloneTyVarBndr, cloneTyVarBndrs, lookupTyVar,

        -- * Tidying type related things up for printing
        tidyType,      tidyTypes,
        tidyOpenType,  tidyOpenTypes,
        tidyVarBndr, tidyVarBndrs, tidyFreeTyCoVars,
        tidyOpenTyCoVar, tidyOpenTyCoVars,
        tidyTyCoVarOcc,
        tidyTopType,
        tidyTyCoVarBinder, tidyTyCoVarBinders,

        -- * Kinds
        isConstraintKindCon,
        classifiesTypeWithValues,
        isConcrete, isFixedRuntimeRepKind,
    ) where

import GHC.Prelude

import GHC.Types.Basic

-- We import the representation and primitive functions from GHC.Core.TyCo.Rep.
-- Many things are reexported, but not the representation!

import GHC.Core.TyCo.Rep
import GHC.Core.TyCo.Subst
import GHC.Core.TyCo.Tidy
import GHC.Core.TyCo.FVs

-- friends:
import GHC.Types.Var
import GHC.Types.Var.Env
import GHC.Types.Var.Set
import GHC.Types.Unique.Set

import GHC.Core.TyCon
import GHC.Builtin.Types.Prim
import {-# SOURCE #-} GHC.Builtin.Types
                                 ( charTy, naturalTy, listTyCon
                                 , typeSymbolKind, liftedTypeKind, unliftedTypeKind
                                 , liftedRepTy, unliftedRepTy, zeroBitRepTy
                                 , boxedRepDataConTyCon
                                 , constraintKind, zeroBitTypeKind
                                 , unrestrictedFunTyCon
                                 , manyDataConTy, oneDataConTy )
import GHC.Types.Name( Name )
import GHC.Builtin.Names
import GHC.Core.Coercion.Axiom
import {-# SOURCE #-} GHC.Core.Coercion
   ( mkNomReflCo, mkGReflCo, mkReflCo
   , mkTyConAppCo, mkAppCo, mkCoVarCo, mkAxiomRuleCo
   , mkForAllCo, mkFunCo, mkAxiomInstCo, mkUnivCo
   , mkSymCo, mkTransCo, mkNthCo, mkLRCo, mkInstCo
   , mkKindCo, mkSubCo
   , decomposePiCos, coercionKind, coercionLKind
   , coercionRKind, coercionType
   , isReflexiveCo, seqCo
   , topNormaliseNewType_maybe
   )
import {-# SOURCE #-} GHC.Tc.Utils.TcType ( isConcreteTyVar )

-- others
import GHC.Utils.Misc
import GHC.Utils.FV
import GHC.Utils.Outputable
import GHC.Utils.Panic
import GHC.Utils.Panic.Plain
import GHC.Data.FastString
import GHC.Data.Pair
import GHC.Data.List.SetOps
import GHC.Types.Unique ( nonDetCmpUnique )

import GHC.Base (reallyUnsafePtrEquality#)
import GHC.Data.Maybe   ( orElse, expectJust, isJust )
import Control.Monad    ( guard )
import qualified Data.Semigroup as S

-- $type_classification
-- #type_classification#
--
-- Types are any, but at least one, of:
--
-- [Boxed]              Iff its representation is a pointer to an object on the
--                      GC'd heap. Operationally, heap objects can be entered as
--                      a means of evaluation.
--
-- [Lifted]             Iff it has bottom as an element: An instance of a
--                      lifted type might diverge when evaluated.
--                      GHC Haskell's unboxed types are unlifted.
--                      An unboxed, but lifted type is not very useful.
--                      (Example: A byte-represented type, where evaluating 0xff
--                      computes the 12345678th collatz number modulo 0xff.)
--                      Only lifted types may be unified with a type variable.
--
-- [Algebraic]          Iff it is a type with one or more constructors, whether
--                      declared with @data@ or @newtype@.
--                      An algebraic type is one that can be deconstructed
--                      with a case expression. There are algebraic types that
--                      are not lifted types, like unlifted data types or
--                      unboxed tuples.
--
-- [Data]               Iff it is a type declared with @data@, or a boxed tuple.
--                      There are also /unlifted/ data types.
--
-- [Primitive]          Iff it is a built-in type that can't be expressed in Haskell.
--
-- [Unlifted]           Anything that isn't lifted is considered unlifted.
--
-- Currently, all primitive types are unlifted, but that's not necessarily
-- the case: for example, @Int@ could be primitive.
--
-- Some primitive types are unboxed, such as @Int#@, whereas some are boxed
-- but unlifted (such as @ByteArray#@).  The only primitive types that we
-- classify as algebraic are the unboxed tuples.
--
-- Some examples of type classifications that may make this a bit clearer are:
--
-- @
-- Type          primitive       boxed           lifted          algebraic
-- -----------------------------------------------------------------------------
-- Int#          Yes             No              No              No
-- ByteArray#    Yes             Yes             No              No
-- (\# a, b \#)  Yes             No              No              Yes
-- (\# a | b \#) Yes             No              No              Yes
-- (  a, b  )    No              Yes             Yes             Yes
-- [a]           No              Yes             Yes             Yes
-- @

-- $representation_types
-- A /source type/ is a type that is a separate type as far as the type checker is
-- concerned, but which has a more low-level representation as far as Core-to-Core
-- passes and the rest of the back end is concerned.
--
-- You don't normally have to worry about this, as the utility functions in
-- this module will automatically convert a source into a representation type
-- if they are spotted, to the best of its abilities. If you don't want this
-- to happen, use the equivalent functions from the "TcType" module.

{-
************************************************************************
*                                                                      *
                Type representation
*                                                                      *
************************************************************************

Note [coreView vs tcView]
~~~~~~~~~~~~~~~~~~~~~~~~~
So far as the typechecker is concerned, 'Constraint' and 'TYPE
LiftedRep' are distinct kinds.

But in Core these two are treated as identical.

We implement this by making 'coreView' convert 'Constraint' to 'TYPE
LiftedRep' on the fly.  The function tcView (used in the type checker)
does not do this. Accordingly, tcView is used in type-checker-oriented
functions (including the pure unifier, used in instance resolution),
while coreView is used during e.g. optimisation passes.

See also #11715, which tracks removing this inconsistency.

In order to prevent users from discerning between Type and Constraint
(which could create inconsistent axioms -- see #21092), we say that
Type and Constraint are not SurelyApart in the pure unifier. See
GHC.Core.Unify.unify_ty, where this case produces MaybeApart.

One annoying consequence of this inconsistency is that we can get ill-kinded
updates to metavariables. #20356 is a case in point. Simplifying somewhat,
we end up with
  [W] (alpha :: Constraint)  ~  (Int :: Type)
This is heterogeneous, so we produce
  [W] co :: (Constraint ~ Type)
and transform our original wanted to become
  [W] alpha ~ Int |> sym co
in accordance with Note [Equalities with incompatible kinds] in GHC.Tc.Solver.Canonical.
Our transformed wanted is now homogeneous (both sides have kind Constraint)
and so we unify alpha := Int |> sym co.

However, it's not so easy: when we build the cast (Int |> sym co), we actually
just get Int back. This is because we forbid reflexive casts (invariant (EQ2) of
Note [Respecting definitional equality] in GHC.Core.TyCo.Rep), and co looks
reflexive: it relates Type and Constraint, even though these are considered
identical in Core. Above, when we tried to say alpha := Int |> sym co, we
really ended up doing alpha := Int -- even though alpha :: Constraint and
Int :: Type have different kinds. Nothing has really gone wrong, though:
we still emitted [W] co :: (Constraint ~ Type), which will be insoluble
and lead to a decent error message. We simply need not to fall over at the
moment of unification, because all will be OK in the end. We thus use the
Core eqType, not the Haskell tcEqType, in the kind check for a meta-tyvar
unification in GHC.Tc.Utils.TcMType.writeMetaTyVarRef.

-}

-- | Gives the typechecker view of a type. This unwraps synonyms but
-- leaves 'Constraint' alone. c.f. 'coreView', which turns 'Constraint' into
-- 'Type'. Returns 'Nothing' if no unwrapping happens.
-- See also Note [coreView vs tcView]
tcView :: Type -> Maybe Type
tcView :: Type -> Maybe Type
tcView (TyConApp TyCon
tc [Type]
tys)
  | res :: Maybe Type
res@(Just Type
_) <- TyCon -> [Type] -> Maybe Type
expandSynTyConApp_maybe TyCon
tc [Type]
tys
  = Maybe Type
res
tcView Type
_ = forall a. Maybe a
Nothing
-- See Note [Inlining coreView].
{-# INLINE tcView #-}

coreView :: Type -> Maybe Type
-- ^ This function strips off the /top layer only/ of a type synonym
-- application (if any) its underlying representation type.
-- Returns 'Nothing' if there is nothing to look through.
-- This function considers 'Constraint' to be a synonym of @Type@.
--
-- This function does not look through type family applications.
--
-- By being non-recursive and inlined, this case analysis gets efficiently
-- joined onto the case analysis that the caller is already doing
coreView :: Type -> Maybe Type
coreView ty :: Type
ty@(TyConApp TyCon
tc [Type]
tys)
  | res :: Maybe Type
res@(Just Type
_) <- TyCon -> [Type] -> Maybe Type
expandSynTyConApp_maybe TyCon
tc [Type]
tys
  = Maybe Type
res

  -- At the Core level, Constraint = Type
  -- See Note [coreView vs tcView]
  | TyCon -> Bool
isConstraintKindCon TyCon
tc
  = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
tys) (forall a. Outputable a => a -> SDoc
ppr Type
ty) forall a b. (a -> b) -> a -> b
$
    forall a. a -> Maybe a
Just Type
liftedTypeKind

coreView Type
_ = forall a. Maybe a
Nothing
-- See Note [Inlining coreView].
{-# INLINE coreView #-}

-----------------------------------------------

-- | @expandSynTyConApp_maybe tc tys@ expands the RHS of type synonym @tc@
-- instantiated at arguments @tys@, or returns 'Nothing' if @tc@ is not a
-- synonym.
expandSynTyConApp_maybe :: TyCon -> [Type] -> Maybe Type
{-# INLINE expandSynTyConApp_maybe #-}
-- This INLINE will inline the call to expandSynTyConApp_maybe in coreView,
-- which will eliminate the allocat ion Just/Nothing in the result
-- Don't be tempted to make `expand_syn` (which is NOINLIN) return the
-- Just/Nothing, else you'll increase allocation
expandSynTyConApp_maybe :: TyCon -> [Type] -> Maybe Type
expandSynTyConApp_maybe TyCon
tc [Type]
arg_tys
  | Just ([TyVar]
tvs, Type
rhs) <- TyCon -> Maybe ([TyVar], Type)
synTyConDefn_maybe TyCon
tc
  , [Type]
arg_tys forall a. [a] -> Int -> Bool
`lengthAtLeast` (TyCon -> Int
tyConArity TyCon
tc)
  = forall a. a -> Maybe a
Just ([TyVar] -> Type -> [Type] -> Type
expand_syn [TyVar]
tvs Type
rhs [Type]
arg_tys)
  | Bool
otherwise
  = forall a. Maybe a
Nothing

-- | A helper for 'expandSynTyConApp_maybe' to avoid inlining this cold path
-- into call-sites.
--
-- Precondition: the call is saturated or over-saturated;
--               i.e. length tvs <= length arg_tys
expand_syn :: [TyVar]  -- ^ the variables bound by the synonym
           -> Type     -- ^ the RHS of the synonym
           -> [Type]   -- ^ the type arguments the synonym is instantiated at.
           -> Type
{-# NOINLINE expand_syn #-} -- We never want to inline this cold-path.

expand_syn :: [TyVar] -> Type -> [Type] -> Type
expand_syn [TyVar]
tvs Type
rhs [Type]
arg_tys
  -- No substitution necessary if either tvs or tys is empty
  -- This is both more efficient, and steers clear of an infinite
  -- loop; see Note [Care using synonyms to compress types]
  | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
arg_tys  = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [TyVar]
tvs) Type
rhs
  | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [TyVar]
tvs      = Type -> [Type] -> Type
mkAppTys Type
rhs [Type]
arg_tys
  | Bool
otherwise     = Subst -> [TyVar] -> [Type] -> Type
go Subst
empty_subst [TyVar]
tvs [Type]
arg_tys
  where
    empty_subst :: Subst
empty_subst = InScopeSet -> Subst
mkEmptySubst InScopeSet
in_scope
    in_scope :: InScopeSet
in_scope = TyCoVarSet -> InScopeSet
mkInScopeSet forall a b. (a -> b) -> a -> b
$ [Type] -> TyCoVarSet
shallowTyCoVarsOfTypes forall a b. (a -> b) -> a -> b
$ [Type]
arg_tys
      -- The free vars of 'rhs' should all be bound by 'tenv',
      -- so we only need the free vars of tys
      -- See also Note [The substitution invariant] in GHC.Core.TyCo.Subst.

    go :: Subst -> [TyVar] -> [Type] -> Type
go Subst
subst [] [Type]
tys
      | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
tys  = Type
rhs'  -- Exactly Saturated
      | Bool
otherwise = Type -> [Type] -> Type
mkAppTys Type
rhs' [Type]
tys
          -- Its important to use mkAppTys, rather than (foldl AppTy),
          -- because the function part might well return a
          -- partially-applied type constructor; indeed, usually will!
      where
        rhs' :: Type
rhs' = HasDebugCallStack => Subst -> Type -> Type
substTy Subst
subst Type
rhs

    go Subst
subst (TyVar
tv:[TyVar]
tvs) (Type
ty:[Type]
tys) = Subst -> [TyVar] -> [Type] -> Type
go (Subst -> TyVar -> Type -> Subst
extendTvSubst Subst
subst TyVar
tv Type
ty) [TyVar]
tvs [Type]
tys

    go Subst
_ (TyVar
_:[TyVar]
_) [] = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"expand_syn" (forall a. Outputable a => a -> SDoc
ppr [TyVar]
tvs SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr Type
rhs SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [Type]
arg_tys)
                   -- Under-saturated, precondition failed



coreFullView :: Type -> Type
-- ^ Iterates 'coreView' until there is no more to synonym to expand.
-- See Note [Inlining coreView].
coreFullView :: Type -> Type
coreFullView ty :: Type
ty@(TyConApp TyCon
tc [Type]
_)
  | TyCon -> Bool
isTypeSynonymTyCon TyCon
tc Bool -> Bool -> Bool
|| TyCon -> Bool
isConstraintKindCon TyCon
tc = Type -> Type
go Type
ty
  where
    go :: Type -> Type
go Type
ty
      | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type
go Type
ty'
      | Bool
otherwise = Type
ty

coreFullView Type
ty = Type
ty
{-# INLINE coreFullView #-}

{- Note [Inlining coreView]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
It is very common to have a function

  f :: Type -> ...
  f ty | Just ty' <- coreView ty = f ty'
  f (TyVarTy ...) = ...
  f ...           = ...

If f is not otherwise recursive, the initial call to coreView
causes f to become recursive, which kills the possibility of
inlining. Instead, for non-recursive functions, we prefer to
use coreFullView, which guarantees to unwrap top-level type
synonyms. It can be inlined and is efficient and non-allocating
in its fast path. For this to really be fast, all calls made
on its fast path must also be inlined, linked back to this Note.
-}

-----------------------------------------------
expandTypeSynonyms :: Type -> Type
-- ^ Expand out all type synonyms.  Actually, it'd suffice to expand out
-- just the ones that discard type variables (e.g.  type Funny a = Int)
-- But we don't know which those are currently, so we just expand all.
--
-- 'expandTypeSynonyms' only expands out type synonyms mentioned in the type,
-- not in the kinds of any TyCon or TyVar mentioned in the type.
--
-- Keep this synchronized with 'synonymTyConsOfType'
expandTypeSynonyms :: Type -> Type
expandTypeSynonyms Type
ty
  = Subst -> Type -> Type
go (InScopeSet -> Subst
mkEmptySubst InScopeSet
in_scope) Type
ty
  where
    in_scope :: InScopeSet
in_scope = TyCoVarSet -> InScopeSet
mkInScopeSet (Type -> TyCoVarSet
tyCoVarsOfType Type
ty)

    go :: Subst -> Type -> Type
go Subst
subst (TyConApp TyCon
tc [Type]
tys)
      | ExpandsSyn [(TyVar, Type)]
tenv Type
rhs [Type]
tys' <- forall tyco. TyCon -> [tyco] -> ExpandSynResult tyco
expandSynTyCon_maybe TyCon
tc [Type]
expanded_tys
      = let subst' :: Subst
subst' = InScopeSet -> TvSubstEnv -> Subst
mkTvSubst InScopeSet
in_scope (forall a. [(TyVar, a)] -> VarEnv a
mkVarEnv [(TyVar, Type)]
tenv)
            -- Make a fresh substitution; rhs has nothing to
            -- do with anything that has happened so far
            -- NB: if you make changes here, be sure to build an
            --     /idempotent/ substitution, even in the nested case
            --        type T a b = a -> b
            --        type S x y = T y x
            -- (#11665)
        in  Type -> [Type] -> Type
mkAppTys (Subst -> Type -> Type
go Subst
subst' Type
rhs) [Type]
tys'
      | Bool
otherwise
      = TyCon -> [Type] -> Type
TyConApp TyCon
tc [Type]
expanded_tys
      where
        expanded_tys :: [Type]
expanded_tys = (forall a b. (a -> b) -> [a] -> [b]
map (Subst -> Type -> Type
go Subst
subst) [Type]
tys)

    go Subst
_     (LitTy TyLit
l)     = TyLit -> Type
LitTy TyLit
l
    go Subst
subst (TyVarTy TyVar
tv)  = Subst -> TyVar -> Type
substTyVar Subst
subst TyVar
tv
    go Subst
subst (AppTy Type
t1 Type
t2) = Type -> Type -> Type
mkAppTy (Subst -> Type -> Type
go Subst
subst Type
t1) (Subst -> Type -> Type
go Subst
subst Type
t2)
    go Subst
subst ty :: Type
ty@(FunTy AnonArgFlag
_ Type
mult Type
arg Type
res)
      = Type
ty { ft_mult :: Type
ft_mult = Subst -> Type -> Type
go Subst
subst Type
mult, ft_arg :: Type
ft_arg = Subst -> Type -> Type
go Subst
subst Type
arg, ft_res :: Type
ft_res = Subst -> Type -> Type
go Subst
subst Type
res }
    go Subst
subst (ForAllTy (Bndr TyVar
tv ArgFlag
vis) Type
t)
      = let (Subst
subst', TyVar
tv') = (Subst -> Type -> Type) -> Subst -> TyVar -> (Subst, TyVar)
substVarBndrUsing Subst -> Type -> Type
go Subst
subst TyVar
tv in
        VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv' ArgFlag
vis) (Subst -> Type -> Type
go Subst
subst' Type
t)
    go Subst
subst (CastTy Type
ty KindCoercion
co)  = Type -> KindCoercion -> Type
mkCastTy (Subst -> Type -> Type
go Subst
subst Type
ty) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go Subst
subst (CoercionTy KindCoercion
co) = KindCoercion -> Type
mkCoercionTy (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)

    go_mco :: Subst -> MCoercionN -> MCoercionN
go_mco Subst
_     MCoercionN
MRefl    = MCoercionN
MRefl
    go_mco Subst
subst (MCo KindCoercion
co) = KindCoercion -> MCoercionN
MCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)

    go_co :: Subst -> KindCoercion -> KindCoercion
go_co Subst
subst (Refl Type
ty)
      = Type -> KindCoercion
mkNomReflCo (Subst -> Type -> Type
go Subst
subst Type
ty)
    go_co Subst
subst (GRefl Role
r Type
ty MCoercionN
mco)
      = Role -> Type -> MCoercionN -> KindCoercion
mkGReflCo Role
r (Subst -> Type -> Type
go Subst
subst Type
ty) (Subst -> MCoercionN -> MCoercionN
go_mco Subst
subst MCoercionN
mco)
       -- NB: coercions are always expanded upon creation
    go_co Subst
subst (TyConAppCo Role
r TyCon
tc [KindCoercion]
args)
      = HasDebugCallStack =>
Role -> TyCon -> [KindCoercion] -> KindCoercion
mkTyConAppCo Role
r TyCon
tc (forall a b. (a -> b) -> [a] -> [b]
map (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst) [KindCoercion]
args)
    go_co Subst
subst (AppCo KindCoercion
co KindCoercion
arg)
      = KindCoercion -> KindCoercion -> KindCoercion
mkAppCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
arg)
    go_co Subst
subst (ForAllCo TyVar
tv KindCoercion
kind_co KindCoercion
co)
      = let (Subst
subst', TyVar
tv', KindCoercion
kind_co') = Subst -> TyVar -> KindCoercion -> (Subst, TyVar, KindCoercion)
go_cobndr Subst
subst TyVar
tv KindCoercion
kind_co in
        TyVar -> KindCoercion -> KindCoercion -> KindCoercion
mkForAllCo TyVar
tv' KindCoercion
kind_co' (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst' KindCoercion
co)
    go_co Subst
subst (FunCo Role
r KindCoercion
w KindCoercion
co1 KindCoercion
co2)
      = Role
-> KindCoercion -> KindCoercion -> KindCoercion -> KindCoercion
mkFunCo Role
r (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
w) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co1) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co2)
    go_co Subst
subst (CoVarCo TyVar
cv)
      = Subst -> TyVar -> KindCoercion
substCoVar Subst
subst TyVar
cv
    go_co Subst
subst (AxiomInstCo CoAxiom Branched
ax Int
ind [KindCoercion]
args)
      = CoAxiom Branched -> Int -> [KindCoercion] -> KindCoercion
mkAxiomInstCo CoAxiom Branched
ax Int
ind (forall a b. (a -> b) -> [a] -> [b]
map (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst) [KindCoercion]
args)
    go_co Subst
subst (UnivCo UnivCoProvenance
p Role
r Type
t1 Type
t2)
      = UnivCoProvenance -> Role -> Type -> Type -> KindCoercion
mkUnivCo (Subst -> UnivCoProvenance -> UnivCoProvenance
go_prov Subst
subst UnivCoProvenance
p) Role
r (Subst -> Type -> Type
go Subst
subst Type
t1) (Subst -> Type -> Type
go Subst
subst Type
t2)
    go_co Subst
subst (SymCo KindCoercion
co)
      = KindCoercion -> KindCoercion
mkSymCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_co Subst
subst (TransCo KindCoercion
co1 KindCoercion
co2)
      = KindCoercion -> KindCoercion -> KindCoercion
mkTransCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co1) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co2)
    go_co Subst
subst (NthCo Role
r Int
n KindCoercion
co)
      = HasDebugCallStack => Role -> Int -> KindCoercion -> KindCoercion
mkNthCo Role
r Int
n (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_co Subst
subst (LRCo LeftOrRight
lr KindCoercion
co)
      = LeftOrRight -> KindCoercion -> KindCoercion
mkLRCo LeftOrRight
lr (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_co Subst
subst (InstCo KindCoercion
co KindCoercion
arg)
      = KindCoercion -> KindCoercion -> KindCoercion
mkInstCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co) (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
arg)
    go_co Subst
subst (KindCo KindCoercion
co)
      = KindCoercion -> KindCoercion
mkKindCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_co Subst
subst (SubCo KindCoercion
co)
      = HasDebugCallStack => KindCoercion -> KindCoercion
mkSubCo (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_co Subst
subst (AxiomRuleCo CoAxiomRule
ax [KindCoercion]
cs)
      = CoAxiomRule -> [KindCoercion] -> KindCoercion
AxiomRuleCo CoAxiomRule
ax (forall a b. (a -> b) -> [a] -> [b]
map (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst) [KindCoercion]
cs)
    go_co Subst
_ (HoleCo CoercionHole
h)
      = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"expandTypeSynonyms hit a hole" (forall a. Outputable a => a -> SDoc
ppr CoercionHole
h)

    go_prov :: Subst -> UnivCoProvenance -> UnivCoProvenance
go_prov Subst
subst (PhantomProv KindCoercion
co)    = KindCoercion -> UnivCoProvenance
PhantomProv (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_prov Subst
subst (ProofIrrelProv KindCoercion
co) = KindCoercion -> UnivCoProvenance
ProofIrrelProv (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst KindCoercion
co)
    go_prov Subst
_     p :: UnivCoProvenance
p@(PluginProv String
_)    = UnivCoProvenance
p
    go_prov Subst
_     p :: UnivCoProvenance
p@(CorePrepProv Bool
_)  = UnivCoProvenance
p

      -- the "False" and "const" are to accommodate the type of
      -- substForAllCoBndrUsing, which is general enough to
      -- handle coercion optimization (which sometimes swaps the
      -- order of a coercion)
    go_cobndr :: Subst -> TyVar -> KindCoercion -> (Subst, TyVar, KindCoercion)
go_cobndr Subst
subst = Bool
-> (KindCoercion -> KindCoercion)
-> Subst
-> TyVar
-> KindCoercion
-> (Subst, TyVar, KindCoercion)
substForAllCoBndrUsing Bool
False (Subst -> KindCoercion -> KindCoercion
go_co Subst
subst) Subst
subst

-- | An INLINE helper for function such as 'kindRep_maybe' below.
--
-- @isTyConKeyApp_maybe key ty@ returns @Just tys@ iff
-- the type @ty = T tys@, where T's unique = key
isTyConKeyApp_maybe :: Unique -> Type -> Maybe [Type]
isTyConKeyApp_maybe :: Unique -> Type -> Maybe [Type]
isTyConKeyApp_maybe Unique
key Type
ty
  | TyConApp TyCon
tc [Type]
args <- Type -> Type
coreFullView Type
ty
  , TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
key
  = forall a. a -> Maybe a
Just [Type]
args
  | Bool
otherwise
  = forall a. Maybe a
Nothing
{-# INLINE isTyConKeyApp_maybe #-}

-- | Extract the RuntimeRep classifier of a type from its kind. For example,
-- @kindRep * = LiftedRep@; Panics if this is not possible.
-- Treats * and Constraint as the same
kindRep :: HasDebugCallStack => Kind -> RuntimeRepType
kindRep :: HasDebugCallStack => Type -> Type
kindRep Type
k = case HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
k of
              Just Type
r  -> Type
r
              Maybe Type
Nothing -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"kindRep" (forall a. Outputable a => a -> SDoc
ppr Type
k)

-- | Given a kind (TYPE rr), extract its RuntimeRep classifier rr.
-- For example, @kindRep_maybe * = Just LiftedRep@
-- Returns 'Nothing' if the kind is not of form (TYPE rr)
-- Treats * and Constraint as the same
kindRep_maybe :: HasDebugCallStack => Kind -> Maybe RuntimeRepType
kindRep_maybe :: HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
kind
  | Just [Type
arg] <- Unique -> Type -> Maybe [Type]
isTyConKeyApp_maybe Unique
tYPETyConKey Type
kind = forall a. a -> Maybe a
Just Type
arg
  | Bool
otherwise                                           = forall a. Maybe a
Nothing

-- | This version considers Constraint to be the same as *. Returns True
-- if the argument is equivalent to Type/Constraint and False otherwise.
-- See Note [Kind Constraint and kind Type]
isLiftedTypeKind :: Kind -> Bool
isLiftedTypeKind :: Type -> Bool
isLiftedTypeKind Type
kind
  = case HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
kind of
      Just Type
rep -> Type -> Bool
isLiftedRuntimeRep Type
rep
      Maybe Type
Nothing  -> Bool
False

pickyIsLiftedTypeKind :: Kind -> Bool
-- Checks whether the kind is literally
--      TYPE LiftedRep
-- or   TYPE ('BoxedRep 'Lifted)
-- or   Type
-- without expanding type synonyms or anything
-- Used only when deciding whether to suppress the ":: *" in
-- (a :: *) when printing kinded type variables
-- See Note [Suppressing * kinds] in GHC.Core.TyCo.Ppr
pickyIsLiftedTypeKind :: Type -> Bool
pickyIsLiftedTypeKind Type
kind
  | TyConApp TyCon
tc [Type
arg] <- Type
kind
  , TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
tYPETyConKey
  , TyConApp TyCon
rr_tc [Type]
rr_args <- Type
arg = case [Type]
rr_args of
      [] -> TyCon
rr_tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
liftedRepTyConKey
      [Type
rr_arg]
        | TyCon
rr_tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
boxedRepDataConKey
        , TyConApp TyCon
lev [] <- Type
rr_arg
        , TyCon
lev forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
liftedDataConKey -> Bool
True
      [Type]
_ -> Bool
False
  | TyConApp TyCon
tc [] <- Type
kind
  , TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
liftedTypeKindTyConKey = Bool
True
  | Bool
otherwise                          = Bool
False

-- | Returns True if the kind classifies unlifted types (like 'Int#') and False
-- otherwise. Note that this returns False for representation-polymorphic
-- kinds, which may be specialized to a kind that classifies unlifted types.
isUnliftedTypeKind :: Kind -> Bool
isUnliftedTypeKind :: Type -> Bool
isUnliftedTypeKind Type
kind
  = case HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
kind of
      Just Type
rep -> Type -> Bool
isUnliftedRuntimeRep Type
rep
      Maybe Type
Nothing  -> Bool
False

-- | See 'isBoxedRuntimeRep_maybe'.
isBoxedRuntimeRep :: Type -> Bool
isBoxedRuntimeRep :: Type -> Bool
isBoxedRuntimeRep Type
rep = forall a. Maybe a -> Bool
isJust (Type -> Maybe Type
isBoxedRuntimeRep_maybe Type
rep)

-- | `isBoxedRuntimeRep_maybe (rep :: RuntimeRep)` returns `Just lev` if `rep`
-- expands to `Boxed lev` and returns `Nothing` otherwise.
--
-- Types with this runtime rep are represented by pointers on the GC'd heap.
isBoxedRuntimeRep_maybe :: Type -> Maybe Type
isBoxedRuntimeRep_maybe :: Type -> Maybe Type
isBoxedRuntimeRep_maybe Type
rep
  | Just [Type
lev] <- Unique -> Type -> Maybe [Type]
isTyConKeyApp_maybe Unique
boxedRepDataConKey Type
rep
  = forall a. a -> Maybe a
Just Type
lev
  | Bool
otherwise
  = forall a. Maybe a
Nothing

-- | Check whether a type of kind 'RuntimeRep' is lifted, unlifted, or unknown.
--
-- @isLiftedRuntimeRep rr@ returns:
--
--   * @Just Lifted@ if @rr@ is @LiftedRep :: RuntimeRep@
--   * @Just Unlifted@ if @rr@ is definitely unlifted, e.g. @IntRep@
--   * @Nothing@ if not known (e.g. it's a type variable or a type family application).
runtimeRepLevity_maybe :: Type -> Maybe Levity
runtimeRepLevity_maybe :: Type -> Maybe Levity
runtimeRepLevity_maybe Type
rep
  | TyConApp TyCon
rr_tc [Type]
args <- Type -> Type
coreFullView Type
rep
  , TyCon -> Bool
isPromotedDataCon TyCon
rr_tc =
      -- NB: args might be non-empty e.g. TupleRep [r1, .., rn]
      if (TyCon
rr_tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
boxedRepDataConKey)
        then case [Type]
args of
          [Type
lev] | Type -> Bool
isLiftedLevity   Type
lev -> forall a. a -> Maybe a
Just Levity
Lifted
                | Type -> Bool
isUnliftedLevity Type
lev -> forall a. a -> Maybe a
Just Levity
Unlifted
          [Type]
_                            -> forall a. Maybe a
Nothing
        else forall a. a -> Maybe a
Just Levity
Unlifted
        -- Avoid searching all the unlifted RuntimeRep type cons
        -- In the RuntimeRep data type, only LiftedRep is lifted
        -- But be careful of type families (F tys) :: RuntimeRep,
        -- hence the isPromotedDataCon rr_tc
runtimeRepLevity_maybe Type
_ = forall a. Maybe a
Nothing

-- | Check whether a kind is of the form @TYPE (BoxedRep Lifted)@
-- or @TYPE (BoxedRep Unlifted)@.
--
-- Returns:
--
--  - @Just Lifted@ for @TYPE (BoxedRep Lifted)@ and @Type@,
--  - @Just Unlifted@ for @TYPE (BoxedRep Unlifted)@ and @UnliftedType@,
--  - @Nothing@ for anything else, e.g. @TYPE IntRep@, @TYPE (BoxedRep l)@, etc.
kindBoxedRepLevity_maybe :: Type -> Maybe Levity
kindBoxedRepLevity_maybe :: Type -> Maybe Levity
kindBoxedRepLevity_maybe Type
ty
  | Just Type
rep <- HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
ty
  , Type -> Bool
isBoxedRuntimeRep Type
rep
  = Type -> Maybe Levity
runtimeRepLevity_maybe Type
rep
  | Bool
otherwise
  = forall a. Maybe a
Nothing

-- | Check whether a type of kind 'RuntimeRep' is lifted.
--
-- 'isLiftedRuntimeRep' is:
--
--  * True of @LiftedRep :: RuntimeRep@
--  * False of type variables, type family applications,
--    and of other reps such as @IntRep :: RuntimeRep@.
isLiftedRuntimeRep :: Type -> Bool
isLiftedRuntimeRep :: Type -> Bool
isLiftedRuntimeRep Type
rep =
  Type -> Maybe Levity
runtimeRepLevity_maybe Type
rep forall a. Eq a => a -> a -> Bool
== forall a. a -> Maybe a
Just Levity
Lifted

-- | Check whether a type of kind 'RuntimeRep' is unlifted.
--
--  * True of definitely unlifted 'RuntimeRep's such as
--    'UnliftedRep', 'IntRep', 'FloatRep', ...
--  * False of 'LiftedRep',
--  * False for type variables and type family applications.
isUnliftedRuntimeRep :: Type -> Bool
isUnliftedRuntimeRep :: Type -> Bool
isUnliftedRuntimeRep Type
rep =
  Type -> Maybe Levity
runtimeRepLevity_maybe Type
rep forall a. Eq a => a -> a -> Bool
== forall a. a -> Maybe a
Just Levity
Unlifted

-- | An INLINE helper for functions such as 'isLiftedLevity' and 'isUnliftedLevity'.
--
-- Checks whether the type is a nullary 'TyCon' application,
-- for a 'TyCon' with the given 'Unique'.
isNullaryTyConKeyApp :: Unique -> Type -> Bool
isNullaryTyConKeyApp :: Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
key Type
ty
  | Just [Type]
args <- Unique -> Type -> Maybe [Type]
isTyConKeyApp_maybe Unique
key Type
ty
  = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) Bool
True
  | Bool
otherwise
  = Bool
False
{-# INLINE isNullaryTyConKeyApp #-}

isLiftedLevity :: Type -> Bool
isLiftedLevity :: Type -> Bool
isLiftedLevity = Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
liftedDataConKey

isUnliftedLevity :: Type -> Bool
isUnliftedLevity :: Type -> Bool
isUnliftedLevity = Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
unliftedDataConKey

-- | Is this the type 'Levity'?
isLevityTy :: Type -> Bool
isLevityTy :: Type -> Bool
isLevityTy = Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
levityTyConKey

-- | Is this the type 'RuntimeRep'?
isRuntimeRepTy :: Type -> Bool
isRuntimeRepTy :: Type -> Bool
isRuntimeRepTy = Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
runtimeRepTyConKey

-- | Is a tyvar of type 'RuntimeRep'?
isRuntimeRepVar :: TyVar -> Bool
isRuntimeRepVar :: TyVar -> Bool
isRuntimeRepVar = Type -> Bool
isRuntimeRepTy forall b c a. (b -> c) -> (a -> b) -> a -> c
. TyVar -> Type
tyVarKind

-- | Is a tyvar of type 'Levity'?
isLevityVar :: TyVar -> Bool
isLevityVar :: TyVar -> Bool
isLevityVar = Type -> Bool
isLevityTy forall b c a. (b -> c) -> (a -> b) -> a -> c
. TyVar -> Type
tyVarKind

-- | Is this the type 'Multiplicity'?
isMultiplicityTy :: Type -> Bool
isMultiplicityTy :: Type -> Bool
isMultiplicityTy  = Unique -> Type -> Bool
isNullaryTyConKeyApp Unique
multiplicityTyConKey

-- | Is a tyvar of type 'Multiplicity'?
isMultiplicityVar :: TyVar -> Bool
isMultiplicityVar :: TyVar -> Bool
isMultiplicityVar = Type -> Bool
isMultiplicityTy forall b c a. (b -> c) -> (a -> b) -> a -> c
. TyVar -> Type
tyVarKind

{- *********************************************************************
*                                                                      *
               mapType
*                                                                      *
************************************************************************

These functions do a map-like operation over types, performing some operation
on all variables and binding sites. Primarily used for zonking.

Note [Efficiency for ForAllCo case of mapTyCoX]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As noted in Note [Forall coercions] in GHC.Core.TyCo.Rep, a ForAllCo is a bit redundant.
It stores a TyCoVar and a Coercion, where the kind of the TyCoVar always matches
the left-hand kind of the coercion. This is convenient lots of the time, but
not when mapping a function over a coercion.

The problem is that tcm_tybinder will affect the TyCoVar's kind and
mapCoercion will affect the Coercion, and we hope that the results will be
the same. Even if they are the same (which should generally happen with
correct algorithms), then there is an efficiency issue. In particular,
this problem seems to make what should be a linear algorithm into a potentially
exponential one. But it's only going to be bad in the case where there's
lots of foralls in the kinds of other foralls. Like this:

  forall a : (forall b : (forall c : ...). ...). ...

This construction seems unlikely. So we'll do the inefficient, easy way
for now.

Note [Specialising mappers]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
These INLINE pragmas are indispensable. mapTyCo and mapTyCoX are used
to implement zonking, and it's vital that they get specialised to the TcM
monad and the particular mapper in use.

Even specialising to the monad alone made a 20% allocation difference
in perf/compiler/T5030.

See Note [Specialising foldType] in "GHC.Core.TyCo.Rep" for more details of this
idiom.
-}

-- | This describes how a "map" operation over a type/coercion should behave
data TyCoMapper env m
  = TyCoMapper
      { forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> m Type
tcm_tyvar :: env -> TyVar -> m Type
      , forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> m KindCoercion
tcm_covar :: env -> CoVar -> m Coercion
      , forall env (m :: * -> *).
TyCoMapper env m -> env -> CoercionHole -> m KindCoercion
tcm_hole  :: env -> CoercionHole -> m Coercion
          -- ^ What to do with coercion holes.
          -- See Note [Coercion holes] in "GHC.Core.TyCo.Rep".

      , forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> ArgFlag -> m (env, TyVar)
tcm_tycobinder :: env -> TyCoVar -> ArgFlag -> m (env, TyCoVar)
          -- ^ The returned env is used in the extended scope

      , forall env (m :: * -> *). TyCoMapper env m -> TyCon -> m TyCon
tcm_tycon :: TyCon -> m TyCon
          -- ^ This is used only for TcTyCons
          -- a) To zonk TcTyCons
          -- b) To turn TcTyCons into TyCons.
          --    See Note [Type checking recursive type and class declarations]
          --    in "GHC.Tc.TyCl"
      }

{-# INLINE mapTyCo #-}  -- See Note [Specialising mappers]
mapTyCo :: Monad m => TyCoMapper () m
         -> ( Type       -> m Type
            , [Type]     -> m [Type]
            , Coercion   -> m Coercion
            , [Coercion] -> m[Coercion])
mapTyCo :: forall (m :: * -> *).
Monad m =>
TyCoMapper () m
-> (Type -> m Type, [Type] -> m [Type],
    KindCoercion -> m KindCoercion, [KindCoercion] -> m [KindCoercion])
mapTyCo TyCoMapper () m
mapper
  = case forall (m :: * -> *) env.
Monad m =>
TyCoMapper env m
-> (env -> Type -> m Type, env -> [Type] -> m [Type],
    env -> KindCoercion -> m KindCoercion,
    env -> [KindCoercion] -> m [KindCoercion])
mapTyCoX TyCoMapper () m
mapper of
     (() -> Type -> m Type
go_ty, () -> [Type] -> m [Type]
go_tys, () -> KindCoercion -> m KindCoercion
go_co, () -> [KindCoercion] -> m [KindCoercion]
go_cos)
        -> (() -> Type -> m Type
go_ty (), () -> [Type] -> m [Type]
go_tys (), () -> KindCoercion -> m KindCoercion
go_co (), () -> [KindCoercion] -> m [KindCoercion]
go_cos ())

{-# INLINE mapTyCoX #-}  -- See Note [Specialising mappers]
mapTyCoX :: Monad m => TyCoMapper env m
         -> ( env -> Type       -> m Type
            , env -> [Type]     -> m [Type]
            , env -> Coercion   -> m Coercion
            , env -> [Coercion] -> m[Coercion])
mapTyCoX :: forall (m :: * -> *) env.
Monad m =>
TyCoMapper env m
-> (env -> Type -> m Type, env -> [Type] -> m [Type],
    env -> KindCoercion -> m KindCoercion,
    env -> [KindCoercion] -> m [KindCoercion])
mapTyCoX (TyCoMapper { tcm_tyvar :: forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> m Type
tcm_tyvar = env -> TyVar -> m Type
tyvar
                     , tcm_tycobinder :: forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> ArgFlag -> m (env, TyVar)
tcm_tycobinder = env -> TyVar -> ArgFlag -> m (env, TyVar)
tycobinder
                     , tcm_tycon :: forall env (m :: * -> *). TyCoMapper env m -> TyCon -> m TyCon
tcm_tycon = TyCon -> m TyCon
tycon
                     , tcm_covar :: forall env (m :: * -> *).
TyCoMapper env m -> env -> TyVar -> m KindCoercion
tcm_covar = env -> TyVar -> m KindCoercion
covar
                     , tcm_hole :: forall env (m :: * -> *).
TyCoMapper env m -> env -> CoercionHole -> m KindCoercion
tcm_hole = env -> CoercionHole -> m KindCoercion
cohole })
  = (env -> Type -> m Type
go_ty, env -> [Type] -> m [Type]
go_tys, env -> KindCoercion -> m KindCoercion
go_co, env -> [KindCoercion] -> m [KindCoercion]
go_cos)
  where
    go_tys :: env -> [Type] -> m [Type]
go_tys env
_   []       = forall (m :: * -> *) a. Monad m => a -> m a
return []
    go_tys env
env (Type
ty:[Type]
tys) = (:) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> Type -> m Type
go_ty env
env Type
ty forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> [Type] -> m [Type]
go_tys env
env [Type]
tys

    go_ty :: env -> Type -> m Type
go_ty env
env (TyVarTy TyVar
tv)    = env -> TyVar -> m Type
tyvar env
env TyVar
tv
    go_ty env
env (AppTy Type
t1 Type
t2)   = Type -> Type -> Type
mkAppTy forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> Type -> m Type
go_ty env
env Type
t1 forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> Type -> m Type
go_ty env
env Type
t2
    go_ty env
_   ty :: Type
ty@(LitTy {})   = forall (m :: * -> *) a. Monad m => a -> m a
return Type
ty
    go_ty env
env (CastTy Type
ty KindCoercion
co)  = Type -> KindCoercion -> Type
mkCastTy forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> Type -> m Type
go_ty env
env Type
ty forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_ty env
env (CoercionTy KindCoercion
co) = KindCoercion -> Type
CoercionTy forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co

    go_ty env
env ty :: Type
ty@(FunTy AnonArgFlag
_ Type
w Type
arg Type
res)
      = do { Type
w' <- env -> Type -> m Type
go_ty env
env Type
w; Type
arg' <- env -> Type -> m Type
go_ty env
env Type
arg; Type
res' <- env -> Type -> m Type
go_ty env
env Type
res
           ; forall (m :: * -> *) a. Monad m => a -> m a
return (Type
ty { ft_mult :: Type
ft_mult = Type
w', ft_arg :: Type
ft_arg = Type
arg', ft_res :: Type
ft_res = Type
res' }) }

    go_ty env
env ty :: Type
ty@(TyConApp TyCon
tc [Type]
tys)
      | TyCon -> Bool
isTcTyCon TyCon
tc
      = do { TyCon
tc' <- TyCon -> m TyCon
tycon TyCon
tc
           ; TyCon -> [Type] -> Type
mkTyConApp TyCon
tc' forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [Type] -> m [Type]
go_tys env
env [Type]
tys }

      -- Not a TcTyCon
      | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
tys    -- Avoid allocation in this very
      = forall (m :: * -> *) a. Monad m => a -> m a
return Type
ty   -- common case (E.g. Int, LiftedRep etc)

      | Bool
otherwise
      = TyCon -> [Type] -> Type
mkTyConApp TyCon
tc forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [Type] -> m [Type]
go_tys env
env [Type]
tys

    go_ty env
env (ForAllTy (Bndr TyVar
tv ArgFlag
vis) Type
inner)
      = do { (env
env', TyVar
tv') <- env -> TyVar -> ArgFlag -> m (env, TyVar)
tycobinder env
env TyVar
tv ArgFlag
vis
           ; Type
inner' <- env -> Type -> m Type
go_ty env
env' Type
inner
           ; forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv' ArgFlag
vis) Type
inner' }

    go_cos :: env -> [KindCoercion] -> m [KindCoercion]
go_cos env
_   []       = forall (m :: * -> *) a. Monad m => a -> m a
return []
    go_cos env
env (KindCoercion
co:[KindCoercion]
cos) = (:) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> [KindCoercion] -> m [KindCoercion]
go_cos env
env [KindCoercion]
cos

    go_mco :: env -> MCoercionN -> m MCoercionN
go_mco env
_   MCoercionN
MRefl    = forall (m :: * -> *) a. Monad m => a -> m a
return MCoercionN
MRefl
    go_mco env
env (MCo KindCoercion
co) = KindCoercion -> MCoercionN
MCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co)

    go_co :: env -> KindCoercion -> m KindCoercion
go_co env
env (Refl Type
ty)           = Type -> KindCoercion
Refl forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> Type -> m Type
go_ty env
env Type
ty
    go_co env
env (GRefl Role
r Type
ty MCoercionN
mco)    = Role -> Type -> MCoercionN -> KindCoercion
mkGReflCo Role
r forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> Type -> m Type
go_ty env
env Type
ty forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> MCoercionN -> m MCoercionN
go_mco env
env MCoercionN
mco
    go_co env
env (AppCo KindCoercion
c1 KindCoercion
c2)       = KindCoercion -> KindCoercion -> KindCoercion
mkAppCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c1 forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c2
    go_co env
env (FunCo Role
r KindCoercion
cw KindCoercion
c1 KindCoercion
c2)   = Role
-> KindCoercion -> KindCoercion -> KindCoercion -> KindCoercion
mkFunCo Role
r forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
cw forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c1 forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c2
    go_co env
env (CoVarCo TyVar
cv)        = env -> TyVar -> m KindCoercion
covar env
env TyVar
cv
    go_co env
env (HoleCo CoercionHole
hole)       = env -> CoercionHole -> m KindCoercion
cohole env
env CoercionHole
hole
    go_co env
env (UnivCo UnivCoProvenance
p Role
r Type
t1 Type
t2)  = UnivCoProvenance -> Role -> Type -> Type -> KindCoercion
mkUnivCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> UnivCoProvenance -> m UnivCoProvenance
go_prov env
env UnivCoProvenance
p forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (f :: * -> *) a. Applicative f => a -> f a
pure Role
r
                                    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> Type -> m Type
go_ty env
env Type
t1 forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> Type -> m Type
go_ty env
env Type
t2
    go_co env
env (SymCo KindCoercion
co)          = KindCoercion -> KindCoercion
mkSymCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_co env
env (TransCo KindCoercion
c1 KindCoercion
c2)     = KindCoercion -> KindCoercion -> KindCoercion
mkTransCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c1 forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
c2
    go_co env
env (AxiomRuleCo CoAxiomRule
r [KindCoercion]
cos) = CoAxiomRule -> [KindCoercion] -> KindCoercion
AxiomRuleCo CoAxiomRule
r forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [KindCoercion] -> m [KindCoercion]
go_cos env
env [KindCoercion]
cos
    go_co env
env (NthCo Role
r Int
i KindCoercion
co)      = HasDebugCallStack => Role -> Int -> KindCoercion -> KindCoercion
mkNthCo Role
r Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_co env
env (LRCo LeftOrRight
lr KindCoercion
co)        = LeftOrRight -> KindCoercion -> KindCoercion
mkLRCo LeftOrRight
lr forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_co env
env (InstCo KindCoercion
co KindCoercion
arg)     = KindCoercion -> KindCoercion -> KindCoercion
mkInstCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
arg
    go_co env
env (KindCo KindCoercion
co)         = KindCoercion -> KindCoercion
mkKindCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_co env
env (SubCo KindCoercion
co)          = HasDebugCallStack => KindCoercion -> KindCoercion
mkSubCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_co env
env (AxiomInstCo CoAxiom Branched
ax Int
i [KindCoercion]
cos) = CoAxiom Branched -> Int -> [KindCoercion] -> KindCoercion
mkAxiomInstCo CoAxiom Branched
ax Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [KindCoercion] -> m [KindCoercion]
go_cos env
env [KindCoercion]
cos
    go_co env
env co :: KindCoercion
co@(TyConAppCo Role
r TyCon
tc [KindCoercion]
cos)
      | TyCon -> Bool
isTcTyCon TyCon
tc
      = do { TyCon
tc' <- TyCon -> m TyCon
tycon TyCon
tc
           ; HasDebugCallStack =>
Role -> TyCon -> [KindCoercion] -> KindCoercion
mkTyConAppCo Role
r TyCon
tc' forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [KindCoercion] -> m [KindCoercion]
go_cos env
env [KindCoercion]
cos }

      -- Not a TcTyCon
      | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [KindCoercion]
cos    -- Avoid allocation in this very
      = forall (m :: * -> *) a. Monad m => a -> m a
return KindCoercion
co   -- common case (E.g. Int, LiftedRep etc)

      | Bool
otherwise
      = HasDebugCallStack =>
Role -> TyCon -> [KindCoercion] -> KindCoercion
mkTyConAppCo Role
r TyCon
tc forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> [KindCoercion] -> m [KindCoercion]
go_cos env
env [KindCoercion]
cos
    go_co env
env (ForAllCo TyVar
tv KindCoercion
kind_co KindCoercion
co)
      = do { KindCoercion
kind_co' <- env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
kind_co
           ; (env
env', TyVar
tv') <- env -> TyVar -> ArgFlag -> m (env, TyVar)
tycobinder env
env TyVar
tv ArgFlag
Inferred
           ; KindCoercion
co' <- env -> KindCoercion -> m KindCoercion
go_co env
env' KindCoercion
co
           ; forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ TyVar -> KindCoercion -> KindCoercion -> KindCoercion
mkForAllCo TyVar
tv' KindCoercion
kind_co' KindCoercion
co' }
        -- See Note [Efficiency for ForAllCo case of mapTyCoX]

    go_prov :: env -> UnivCoProvenance -> m UnivCoProvenance
go_prov env
env (PhantomProv KindCoercion
co)    = KindCoercion -> UnivCoProvenance
PhantomProv forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_prov env
env (ProofIrrelProv KindCoercion
co) = KindCoercion -> UnivCoProvenance
ProofIrrelProv forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> env -> KindCoercion -> m KindCoercion
go_co env
env KindCoercion
co
    go_prov env
_   p :: UnivCoProvenance
p@(PluginProv String
_)    = forall (m :: * -> *) a. Monad m => a -> m a
return UnivCoProvenance
p
    go_prov env
_   p :: UnivCoProvenance
p@(CorePrepProv Bool
_)  = forall (m :: * -> *) a. Monad m => a -> m a
return UnivCoProvenance
p


{-
************************************************************************
*                                                                      *
\subsection{Constructor-specific functions}
*                                                                      *
************************************************************************


---------------------------------------------------------------------
                                TyVarTy
                                ~~~~~~~
-}

-- | Attempts to obtain the type variable underlying a 'Type', and panics with the
-- given message if this is not a type variable type. See also 'getTyVar_maybe'
getTyVar :: String -> Type -> TyVar
getTyVar :: String -> Type -> TyVar
getTyVar String
msg Type
ty = case Type -> Maybe TyVar
getTyVar_maybe Type
ty of
                    Just TyVar
tv -> TyVar
tv
                    Maybe TyVar
Nothing -> forall a. String -> a
panic (String
"getTyVar: " forall a. [a] -> [a] -> [a]
++ String
msg)

isTyVarTy :: Type -> Bool
isTyVarTy :: Type -> Bool
isTyVarTy Type
ty = forall a. Maybe a -> Bool
isJust (Type -> Maybe TyVar
getTyVar_maybe Type
ty)

-- | Attempts to obtain the type variable underlying a 'Type'
getTyVar_maybe :: Type -> Maybe TyVar
getTyVar_maybe :: Type -> Maybe TyVar
getTyVar_maybe = Type -> Maybe TyVar
repGetTyVar_maybe forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> Type
coreFullView

-- | If the type is a tyvar, possibly under a cast, returns it, along
-- with the coercion. Thus, the co is :: kind tv ~N kind ty
getCastedTyVar_maybe :: Type -> Maybe (TyVar, CoercionN)
getCastedTyVar_maybe :: Type -> Maybe (TyVar, KindCoercion)
getCastedTyVar_maybe Type
ty = case Type -> Type
coreFullView Type
ty of
  CastTy (TyVarTy TyVar
tv) KindCoercion
co -> forall a. a -> Maybe a
Just (TyVar
tv, KindCoercion
co)
  TyVarTy TyVar
tv             -> forall a. a -> Maybe a
Just (TyVar
tv, Role -> Type -> KindCoercion
mkReflCo Role
Nominal (TyVar -> Type
tyVarKind TyVar
tv))
  Type
_                      -> forall a. Maybe a
Nothing

-- | Attempts to obtain the type variable underlying a 'Type', without
-- any expansion
repGetTyVar_maybe :: Type -> Maybe TyVar
repGetTyVar_maybe :: Type -> Maybe TyVar
repGetTyVar_maybe (TyVarTy TyVar
tv) = forall a. a -> Maybe a
Just TyVar
tv
repGetTyVar_maybe Type
_            = forall a. Maybe a
Nothing

{-
---------------------------------------------------------------------
                                AppTy
                                ~~~~~
We need to be pretty careful with AppTy to make sure we obey the
invariant that a TyConApp is always visibly so.  mkAppTy maintains the
invariant: use it.

Note [Decomposing fat arrow c=>t]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Can we unify (a b) with (Eq a => ty)?   If we do so, we end up with
a partial application like ((=>) Eq a) which doesn't make sense in
source Haskell.  In contrast, we *can* unify (a b) with (t1 -> t2).
Here's an example (#9858) of how you might do it:
   i :: (Typeable a, Typeable b) => Proxy (a b) -> TypeRep
   i p = typeRep p

   j = i (Proxy :: Proxy (Eq Int => Int))
The type (Proxy (Eq Int => Int)) is only accepted with -XImpredicativeTypes,
but suppose we want that.  But then in the call to 'i', we end
up decomposing (Eq Int => Int), and we definitely don't want that.

This really only applies to the type checker; in Core, '=>' and '->'
are the same, as are 'Constraint' and '*'.  But for now I've put
the test in repSplitAppTy_maybe, which applies throughout, because
the other calls to splitAppTy are in GHC.Core.Unify, which is also used by
the type checker (e.g. when matching type-function equations).

-}

-- | Applies a type to another, as in e.g. @k a@
mkAppTy :: Type -> Type -> Type
  -- See Note [Respecting definitional equality], invariant (EQ1).
mkAppTy :: Type -> Type -> Type
mkAppTy (CastTy Type
fun_ty KindCoercion
co) Type
arg_ty
  | ([KindCoercion
arg_co], KindCoercion
res_co) <- HasDebugCallStack =>
KindCoercion
-> Pair Type -> [Type] -> ([KindCoercion], KindCoercion)
decomposePiCos KindCoercion
co (KindCoercion -> Pair Type
coercionKind KindCoercion
co) [Type
arg_ty]
  = (Type
fun_ty Type -> Type -> Type
`mkAppTy` (Type
arg_ty Type -> KindCoercion -> Type
`mkCastTy` KindCoercion
arg_co)) Type -> KindCoercion -> Type
`mkCastTy` KindCoercion
res_co

mkAppTy (TyConApp TyCon
tc [Type]
tys) Type
ty2 = TyCon -> [Type] -> Type
mkTyConApp TyCon
tc ([Type]
tys forall a. [a] -> [a] -> [a]
++ [Type
ty2])
mkAppTy Type
ty1               Type
ty2 = Type -> Type -> Type
AppTy Type
ty1 Type
ty2
        -- Note that the TyConApp could be an
        -- under-saturated type synonym.  GHC allows that; e.g.
        --      type Foo k = k a -> k a
        --      type Id x = x
        --      foo :: Foo Id -> Foo Id
        --
        -- Here Id is partially applied in the type sig for Foo,
        -- but once the type synonyms are expanded all is well
        --
        -- Moreover in GHC.Tc.Types.tcInferTyApps we build up a type
        --   (T t1 t2 t3) one argument at a type, thus forming
        --   (T t1), (T t1 t2), etc

mkAppTys :: Type -> [Type] -> Type
mkAppTys :: Type -> [Type] -> Type
mkAppTys Type
ty1                []   = Type
ty1
mkAppTys (CastTy Type
fun_ty KindCoercion
co) [Type]
arg_tys  -- much more efficient then nested mkAppTy
                                     -- Why do this? See (EQ1) of
                                     -- Note [Respecting definitional equality]
                                     -- in GHC.Core.TyCo.Rep
  = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Type -> Type -> Type
AppTy ((Type -> [Type] -> Type
mkAppTys Type
fun_ty [Type]
casted_arg_tys) Type -> KindCoercion -> Type
`mkCastTy` KindCoercion
res_co) [Type]
leftovers
  where
    ([KindCoercion]
arg_cos, KindCoercion
res_co) = HasDebugCallStack =>
KindCoercion
-> Pair Type -> [Type] -> ([KindCoercion], KindCoercion)
decomposePiCos KindCoercion
co (KindCoercion -> Pair Type
coercionKind KindCoercion
co) [Type]
arg_tys
    ([Type]
args_to_cast, [Type]
leftovers) = forall b a. [b] -> [a] -> ([a], [a])
splitAtList [KindCoercion]
arg_cos [Type]
arg_tys
    casted_arg_tys :: [Type]
casted_arg_tys = forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Type -> KindCoercion -> Type
mkCastTy [Type]
args_to_cast [KindCoercion]
arg_cos
mkAppTys (TyConApp TyCon
tc [Type]
tys1) [Type]
tys2 = TyCon -> [Type] -> Type
mkTyConApp TyCon
tc ([Type]
tys1 forall a. [a] -> [a] -> [a]
++ [Type]
tys2)
mkAppTys Type
ty1                [Type]
tys2 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Type -> Type -> Type
AppTy Type
ty1 [Type]
tys2

-------------
splitAppTy_maybe :: Type -> Maybe (Type, Type)
-- ^ Attempt to take a type application apart, whether it is a
-- function, type constructor, or plain type application. Note
-- that type family applications are NEVER unsaturated by this!
splitAppTy_maybe :: Type -> Maybe (Type, Type)
splitAppTy_maybe = HasDebugCallStack => Type -> Maybe (Type, Type)
repSplitAppTy_maybe forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> Type
coreFullView

-------------
repSplitAppTy_maybe :: HasDebugCallStack => Type -> Maybe (Type,Type)
-- ^ Does the AppTy split as in 'splitAppTy_maybe', but assumes that
-- any Core view stuff is already done
repSplitAppTy_maybe :: HasDebugCallStack => Type -> Maybe (Type, Type)
repSplitAppTy_maybe (FunTy AnonArgFlag
_ Type
w Type
ty1 Type
ty2)
  = forall a. a -> Maybe a
Just (TyCon -> [Type] -> Type
TyConApp TyCon
funTyCon [Type
w, Type
rep1, Type
rep2, Type
ty1], Type
ty2)
  where
    rep1 :: Type
rep1 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty1
    rep2 :: Type
rep2 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty2

repSplitAppTy_maybe (AppTy Type
ty1 Type
ty2)
  = forall a. a -> Maybe a
Just (Type
ty1, Type
ty2)

repSplitAppTy_maybe (TyConApp TyCon
tc [Type]
tys)
  | Bool -> Bool
not (TyCon -> Bool
mustBeSaturated TyCon
tc) Bool -> Bool -> Bool
|| [Type]
tys forall a. [a] -> Int -> Bool
`lengthExceeds` TyCon -> Int
tyConArity TyCon
tc
  , Just ([Type]
tys', Type
ty') <- forall a. [a] -> Maybe ([a], a)
snocView [Type]
tys
  = forall a. a -> Maybe a
Just (TyCon -> [Type] -> Type
TyConApp TyCon
tc [Type]
tys', Type
ty')    -- Never create unsaturated type family apps!

repSplitAppTy_maybe Type
_other = forall a. Maybe a
Nothing

-- This one doesn't break apart (c => t).
-- See Note [Decomposing fat arrow c=>t]
-- Defined here to avoid module loops between Unify and TcType.
tcRepSplitAppTy_maybe :: Type -> Maybe (Type,Type)
-- ^ Does the AppTy split as in 'tcSplitAppTy_maybe', but assumes that
-- any coreView stuff is already done. Refuses to look through (c => t)
tcRepSplitAppTy_maybe :: Type -> Maybe (Type, Type)
tcRepSplitAppTy_maybe (FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af, ft_mult :: Type -> Type
ft_mult = Type
w, ft_arg :: Type -> Type
ft_arg = Type
ty1, ft_res :: Type -> Type
ft_res = Type
ty2 })
  | AnonArgFlag
VisArg <- AnonArgFlag
af   -- See Note [Decomposing fat arrow c=>t]

  -- See Note [The Purely Kinded Type Invariant (PKTI)] in GHC.Tc.Gen.HsType,
  -- Wrinkle around FunTy
  , Just Type
rep1 <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
ty1
  , Just Type
rep2 <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
ty2
  = forall a. a -> Maybe a
Just (TyCon -> [Type] -> Type
TyConApp TyCon
funTyCon [Type
w, Type
rep1, Type
rep2, Type
ty1], Type
ty2)

  | Bool
otherwise
  = forall a. Maybe a
Nothing

tcRepSplitAppTy_maybe (AppTy Type
ty1 Type
ty2)    = forall a. a -> Maybe a
Just (Type
ty1, Type
ty2)
tcRepSplitAppTy_maybe (TyConApp TyCon
tc [Type]
tys)
  | Bool -> Bool
not (TyCon -> Bool
mustBeSaturated TyCon
tc) Bool -> Bool -> Bool
|| [Type]
tys forall a. [a] -> Int -> Bool
`lengthExceeds` TyCon -> Int
tyConArity TyCon
tc
  , Just ([Type]
tys', Type
ty') <- forall a. [a] -> Maybe ([a], a)
snocView [Type]
tys
  = forall a. a -> Maybe a
Just (TyCon -> [Type] -> Type
TyConApp TyCon
tc [Type]
tys', Type
ty')    -- Never create unsaturated type family apps!
tcRepSplitAppTy_maybe Type
_other = forall a. Maybe a
Nothing

-------------
splitAppTy :: Type -> (Type, Type)
-- ^ Attempts to take a type application apart, as in 'splitAppTy_maybe',
-- and panics if this is not possible
splitAppTy :: Type -> (Type, Type)
splitAppTy Type
ty = case Type -> Maybe (Type, Type)
splitAppTy_maybe Type
ty of
                Just (Type, Type)
pr -> (Type, Type)
pr
                Maybe (Type, Type)
Nothing -> forall a. String -> a
panic String
"splitAppTy"

-------------
splitAppTys :: Type -> (Type, [Type])
-- ^ Recursively splits a type as far as is possible, leaving a residual
-- type being applied to and the type arguments applied to it. Never fails,
-- even if that means returning an empty list of type applications.
splitAppTys :: Type -> (Type, [Type])
splitAppTys Type
ty = Type -> Type -> [Type] -> (Type, [Type])
split Type
ty Type
ty []
  where
    split :: Type -> Type -> [Type] -> (Type, [Type])
split Type
orig_ty Type
ty [Type]
args | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type -> [Type] -> (Type, [Type])
split Type
orig_ty Type
ty' [Type]
args
    split Type
_       (AppTy Type
ty Type
arg)        [Type]
args = Type -> Type -> [Type] -> (Type, [Type])
split Type
ty Type
ty (Type
argforall a. a -> [a] -> [a]
:[Type]
args)
    split Type
_       (TyConApp TyCon
tc [Type]
tc_args) [Type]
args
      = let -- keep type families saturated
            n :: Int
n | TyCon -> Bool
mustBeSaturated TyCon
tc = TyCon -> Int
tyConArity TyCon
tc
              | Bool
otherwise          = Int
0
            ([Type]
tc_args1, [Type]
tc_args2) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [Type]
tc_args
        in
        (TyCon -> [Type] -> Type
TyConApp TyCon
tc [Type]
tc_args1, [Type]
tc_args2 forall a. [a] -> [a] -> [a]
++ [Type]
args)
    split Type
_   (FunTy AnonArgFlag
_ Type
w Type
ty1 Type
ty2) [Type]
args
      = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args )
        (TyCon -> [Type] -> Type
TyConApp TyCon
funTyCon [], [Type
w, Type
rep1, Type
rep2, Type
ty1, Type
ty2])
      where
        rep1 :: Type
rep1 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty1
        rep2 :: Type
rep2 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty2

    split Type
orig_ty Type
_                     [Type]
args  = (Type
orig_ty, [Type]
args)

-- | Like 'splitAppTys', but doesn't look through type synonyms
repSplitAppTys :: HasDebugCallStack => Type -> (Type, [Type])
repSplitAppTys :: HasDebugCallStack => Type -> (Type, [Type])
repSplitAppTys Type
ty = Type -> [Type] -> (Type, [Type])
split Type
ty []
  where
    split :: Type -> [Type] -> (Type, [Type])
split (AppTy Type
ty Type
arg) [Type]
args = Type -> [Type] -> (Type, [Type])
split Type
ty (Type
argforall a. a -> [a] -> [a]
:[Type]
args)
    split (TyConApp TyCon
tc [Type]
tc_args) [Type]
args
      = let n :: Int
n | TyCon -> Bool
mustBeSaturated TyCon
tc = TyCon -> Int
tyConArity TyCon
tc
              | Bool
otherwise          = Int
0
            ([Type]
tc_args1, [Type]
tc_args2) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [Type]
tc_args
        in
        (TyCon -> [Type] -> Type
TyConApp TyCon
tc [Type]
tc_args1, [Type]
tc_args2 forall a. [a] -> [a] -> [a]
++ [Type]
args)
    split (FunTy AnonArgFlag
_ Type
w Type
ty1 Type
ty2) [Type]
args
      = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args )
        (TyCon -> [Type] -> Type
TyConApp TyCon
funTyCon [], [Type
w, Type
rep1, Type
rep2, Type
ty1, Type
ty2])
      where
        rep1 :: Type
rep1 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty1
        rep2 :: Type
rep2 = HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty2

    split Type
ty [Type]
args = (Type
ty, [Type]
args)

{-
                      LitTy
                      ~~~~~
-}

mkNumLitTy :: Integer -> Type
mkNumLitTy :: Integer -> Type
mkNumLitTy Integer
n = TyLit -> Type
LitTy (Integer -> TyLit
NumTyLit Integer
n)

-- | Is this a numeric literal. We also look through type synonyms.
isNumLitTy :: Type -> Maybe Integer
isNumLitTy :: Type -> Maybe Integer
isNumLitTy Type
ty
  | LitTy (NumTyLit Integer
n) <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just Integer
n
  | Bool
otherwise                             = forall a. Maybe a
Nothing

mkStrLitTy :: FastString -> Type
mkStrLitTy :: FastString -> Type
mkStrLitTy FastString
s = TyLit -> Type
LitTy (FastString -> TyLit
StrTyLit FastString
s)

-- | Is this a symbol literal. We also look through type synonyms.
isStrLitTy :: Type -> Maybe FastString
isStrLitTy :: Type -> Maybe FastString
isStrLitTy Type
ty
  | LitTy (StrTyLit FastString
s) <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just FastString
s
  | Bool
otherwise                             = forall a. Maybe a
Nothing

mkCharLitTy :: Char -> Type
mkCharLitTy :: Char -> Type
mkCharLitTy Char
c = TyLit -> Type
LitTy (Char -> TyLit
CharTyLit Char
c)

-- | Is this a char literal? We also look through type synonyms.
isCharLitTy :: Type -> Maybe Char
isCharLitTy :: Type -> Maybe Char
isCharLitTy Type
ty
  | LitTy (CharTyLit Char
s) <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just Char
s
  | Bool
otherwise                              = forall a. Maybe a
Nothing


-- | Is this a type literal (symbol, numeric, or char)?
isLitTy :: Type -> Maybe TyLit
isLitTy :: Type -> Maybe TyLit
isLitTy Type
ty
  | LitTy TyLit
l <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just TyLit
l
  | Bool
otherwise                  = forall a. Maybe a
Nothing

-- | Is this type a custom user error?
-- If so, give us the kind and the error message.
userTypeError_maybe :: Type -> Maybe Type
userTypeError_maybe :: Type -> Maybe Type
userTypeError_maybe Type
t
  = do { (TyCon
tc, Type
_kind : Type
msg : [Type]
_) <- HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
t
          -- There may be more than 2 arguments, if the type error is
          -- used as a type constructor (e.g. at kind `Type -> Type`).

       ; forall (f :: * -> *). Alternative f => Bool -> f ()
guard (TyCon -> Name
tyConName TyCon
tc forall a. Eq a => a -> a -> Bool
== Name
errorMessageTypeErrorFamName)
       ; forall (m :: * -> *) a. Monad m => a -> m a
return Type
msg }

-- | Render a type corresponding to a user type error into a SDoc.
pprUserTypeErrorTy :: Type -> SDoc
pprUserTypeErrorTy :: Type -> SDoc
pprUserTypeErrorTy Type
ty =
  case HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
ty of

    -- Text "Something"
    Just (TyCon
tc,[Type
txt])
      | TyCon -> Name
tyConName TyCon
tc forall a. Eq a => a -> a -> Bool
== Name
typeErrorTextDataConName
      , Just FastString
str <- Type -> Maybe FastString
isStrLitTy Type
txt -> FastString -> SDoc
ftext FastString
str

    -- ShowType t
    Just (TyCon
tc,[Type
_k,Type
t])
      | TyCon -> Name
tyConName TyCon
tc forall a. Eq a => a -> a -> Bool
== Name
typeErrorShowTypeDataConName -> forall a. Outputable a => a -> SDoc
ppr Type
t

    -- t1 :<>: t2
    Just (TyCon
tc,[Type
t1,Type
t2])
      | TyCon -> Name
tyConName TyCon
tc forall a. Eq a => a -> a -> Bool
== Name
typeErrorAppendDataConName ->
        Type -> SDoc
pprUserTypeErrorTy Type
t1 SDoc -> SDoc -> SDoc
<> Type -> SDoc
pprUserTypeErrorTy Type
t2

    -- t1 :$$: t2
    Just (TyCon
tc,[Type
t1,Type
t2])
      | TyCon -> Name
tyConName TyCon
tc forall a. Eq a => a -> a -> Bool
== Name
typeErrorVAppendDataConName ->
        Type -> SDoc
pprUserTypeErrorTy Type
t1 SDoc -> SDoc -> SDoc
$$ Type -> SDoc
pprUserTypeErrorTy Type
t2

    -- An unevaluated type function
    Maybe (TyCon, [Type])
_ -> forall a. Outputable a => a -> SDoc
ppr Type
ty




{-
---------------------------------------------------------------------
                                FunTy
                                ~~~~~

Note [Representation of function types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Functions (e.g. Int -> Char) can be thought of as being applications
of funTyCon (known in Haskell surface syntax as (->)), (note that
`RuntimeRep' quantifiers are left inferred)

    (->) :: forall {r1 :: RuntimeRep} {r2 :: RuntimeRep}
                   (a :: TYPE r1) (b :: TYPE r2).
            a -> b -> Type

However, for efficiency's sake we represent saturated applications of (->)
with FunTy. For instance, the type,

    (->) r1 r2 a b

is equivalent to,

    FunTy (Anon a) b

Note how the RuntimeReps are implied in the FunTy representation. For this
reason we must be careful when reconstructing the TyConApp representation (see,
for instance, splitTyConApp_maybe).

In the compiler we maintain the invariant that all saturated applications of
(->) are represented with FunTy.

See #11714.
-}

splitFunTy :: Type -> (Mult, Type, Type)
-- ^ Attempts to extract the multiplicity, argument and result types from a type,
-- and panics if that is not possible. See also 'splitFunTy_maybe'
splitFunTy :: Type -> (Type, Type, Type)
splitFunTy = forall a. HasCallStack => String -> Maybe a -> a
expectJust String
"splitFunTy" forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> Maybe (Type, Type, Type)
splitFunTy_maybe

{-# INLINE splitFunTy_maybe #-}
splitFunTy_maybe :: Type -> Maybe (Mult, Type, Type)
-- ^ Attempts to extract the multiplicity, argument and result types from a type
splitFunTy_maybe :: Type -> Maybe (Type, Type, Type)
splitFunTy_maybe Type
ty
  | FunTy AnonArgFlag
_ Type
w Type
arg Type
res <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just (Type
w, Type
arg, Type
res)
  | Bool
otherwise                            = forall a. Maybe a
Nothing

splitFunTys :: Type -> ([Scaled Type], Type)
splitFunTys :: Type -> ([Scaled Type], Type)
splitFunTys Type
ty = [Scaled Type] -> Type -> Type -> ([Scaled Type], Type)
split [] Type
ty Type
ty
  where
      -- common case first
    split :: [Scaled Type] -> Type -> Type -> ([Scaled Type], Type)
split [Scaled Type]
args Type
_       (FunTy AnonArgFlag
_ Type
w Type
arg Type
res) = [Scaled Type] -> Type -> Type -> ([Scaled Type], Type)
split ((forall a. Type -> a -> Scaled a
Scaled Type
w Type
arg)forall a. a -> [a] -> [a]
:[Scaled Type]
args) Type
res Type
res
    split [Scaled Type]
args Type
orig_ty Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = [Scaled Type] -> Type -> Type -> ([Scaled Type], Type)
split [Scaled Type]
args Type
orig_ty Type
ty'
    split [Scaled Type]
args Type
orig_ty Type
_                   = (forall a. [a] -> [a]
reverse [Scaled Type]
args, Type
orig_ty)

funResultTy :: Type -> Type
-- ^ Extract the function result type and panic if that is not possible
funResultTy :: Type -> Type
funResultTy Type
ty
  | FunTy { ft_res :: Type -> Type
ft_res = Type
res } <- Type -> Type
coreFullView Type
ty = Type
res
  | Bool
otherwise                                 = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"funResultTy" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

funArgTy :: Type -> Type
-- ^ Extract the function argument type and panic if that is not possible
funArgTy :: Type -> Type
funArgTy Type
ty
  | FunTy { ft_arg :: Type -> Type
ft_arg = Type
arg } <- Type -> Type
coreFullView Type
ty = Type
arg
  | Bool
otherwise                                 = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"funArgTy" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- ^ Just like 'piResultTys' but for a single argument
-- Try not to iterate 'piResultTy', because it's inefficient to substitute
-- one variable at a time; instead use 'piResultTys"
piResultTy :: HasDebugCallStack => Type -> Type ->  Type
piResultTy :: HasDebugCallStack => Type -> Type -> Type
piResultTy Type
ty Type
arg = case Type -> Type -> Maybe Type
piResultTy_maybe Type
ty Type
arg of
                      Just Type
res -> Type
res
                      Maybe Type
Nothing  -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"piResultTy" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr Type
arg)

piResultTy_maybe :: Type -> Type -> Maybe Type
-- We don't need a 'tc' version, because
-- this function behaves the same for Type and Constraint
piResultTy_maybe :: Type -> Type -> Maybe Type
piResultTy_maybe Type
ty Type
arg = case Type -> Type
coreFullView Type
ty of
  FunTy { ft_res :: Type -> Type
ft_res = Type
res } -> forall a. a -> Maybe a
Just Type
res

  ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
res
    -> let empty_subst :: Subst
empty_subst = InScopeSet -> Subst
mkEmptySubst forall a b. (a -> b) -> a -> b
$ TyCoVarSet -> InScopeSet
mkInScopeSet forall a b. (a -> b) -> a -> b
$
                         [Type] -> TyCoVarSet
tyCoVarsOfTypes [Type
arg,Type
res]
       in forall a. a -> Maybe a
Just (HasDebugCallStack => Subst -> Type -> Type
substTy (Subst -> TyVar -> Type -> Subst
extendTCvSubst Subst
empty_subst TyVar
tv Type
arg) Type
res)

  Type
_ -> forall a. Maybe a
Nothing

-- | (piResultTys f_ty [ty1, .., tyn]) gives the type of (f ty1 .. tyn)
--   where f :: f_ty
-- 'piResultTys' is interesting because:
--      1. 'f_ty' may have more for-alls than there are args
--      2. Less obviously, it may have fewer for-alls
-- For case 2. think of:
--   piResultTys (forall a.a) [forall b.b, Int]
-- This really can happen, but only (I think) in situations involving
-- undefined.  For example:
--       undefined :: forall a. a
-- Term: undefined @(forall b. b->b) @Int
-- This term should have type (Int -> Int), but notice that
-- there are more type args than foralls in 'undefined's type.

-- If you edit this function, you may need to update the GHC formalism
-- See Note [GHC Formalism] in GHC.Core.Lint

-- This is a heavily used function (e.g. from typeKind),
-- so we pay attention to efficiency, especially in the special case
-- where there are no for-alls so we are just dropping arrows from
-- a function type/kind.
piResultTys :: HasDebugCallStack => Type -> [Type] -> Type
piResultTys :: HasDebugCallStack => Type -> [Type] -> Type
piResultTys Type
ty [] = Type
ty
piResultTys Type
ty orig_args :: [Type]
orig_args@(Type
arg:[Type]
args)
  | FunTy { ft_res :: Type -> Type
ft_res = Type
res } <- Type
ty
  = HasDebugCallStack => Type -> [Type] -> Type
piResultTys Type
res [Type]
args

  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
res <- Type
ty
  = Subst -> Type -> [Type] -> Type
go (Subst -> TyVar -> Type -> Subst
extendTCvSubst Subst
init_subst TyVar
tv Type
arg) Type
res [Type]
args

  | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty
  = HasDebugCallStack => Type -> [Type] -> Type
piResultTys Type
ty' [Type]
orig_args

  | Bool
otherwise
  = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"piResultTys1" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [Type]
orig_args)
  where
    init_subst :: Subst
init_subst = InScopeSet -> Subst
mkEmptySubst forall a b. (a -> b) -> a -> b
$ TyCoVarSet -> InScopeSet
mkInScopeSet ([Type] -> TyCoVarSet
tyCoVarsOfTypes (Type
tyforall a. a -> [a] -> [a]
:[Type]
orig_args))

    go :: Subst -> Type -> [Type] -> Type
    go :: Subst -> Type -> [Type] -> Type
go Subst
subst Type
ty [] = Subst -> Type -> Type
substTyUnchecked Subst
subst Type
ty

    go Subst
subst Type
ty all_args :: [Type]
all_args@(Type
arg:[Type]
args)
      | FunTy { ft_res :: Type -> Type
ft_res = Type
res } <- Type
ty
      = Subst -> Type -> [Type] -> Type
go Subst
subst Type
res [Type]
args

      | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
res <- Type
ty
      = Subst -> Type -> [Type] -> Type
go (Subst -> TyVar -> Type -> Subst
extendTCvSubst Subst
subst TyVar
tv Type
arg) Type
res [Type]
args

      | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty
      = Subst -> Type -> [Type] -> Type
go Subst
subst Type
ty' [Type]
all_args

      | Bool -> Bool
not (Subst -> Bool
isEmptyTCvSubst Subst
subst)  -- See Note [Care with kind instantiation]
      = Subst -> Type -> [Type] -> Type
go Subst
init_subst
          (HasDebugCallStack => Subst -> Type -> Type
substTy Subst
subst Type
ty)
          [Type]
all_args

      | Bool
otherwise
      = -- We have not run out of arguments, but the function doesn't
        -- have the right kind to apply to them; so panic.
        -- Without the explicit isEmptyVarEnv test, an ill-kinded type
        -- would give an infinite loop, which is very unhelpful
        -- c.f. #15473
        forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"piResultTys2" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [Type]
orig_args SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [Type]
all_args)

applyTysX :: [TyVar] -> Type -> [Type] -> Type
-- applyTysX beta-reduces (/\tvs. body_ty) arg_tys
-- Assumes that (/\tvs. body_ty) is closed
applyTysX :: [TyVar] -> Type -> [Type] -> Type
applyTysX [TyVar]
tvs Type
body_ty [Type]
arg_tys
  = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr ([TyVar]
tvs forall a b. [a] -> [b] -> Bool
`leLength` [Type]
arg_tys) SDoc
pp_stuff forall a b. (a -> b) -> a -> b
$
    forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr (Type -> TyCoVarSet
tyCoVarsOfType Type
body_ty TyCoVarSet -> TyCoVarSet -> Bool
`subVarSet` [TyVar] -> TyCoVarSet
mkVarSet [TyVar]
tvs) SDoc
pp_stuff forall a b. (a -> b) -> a -> b
$
    Type -> [Type] -> Type
mkAppTys (HasDebugCallStack => [TyVar] -> [Type] -> Type -> Type
substTyWith [TyVar]
tvs [Type]
arg_tys_prefix Type
body_ty)
             [Type]
arg_tys_rest
  where
    pp_stuff :: SDoc
pp_stuff = [SDoc] -> SDoc
vcat [forall a. Outputable a => a -> SDoc
ppr [TyVar]
tvs, forall a. Outputable a => a -> SDoc
ppr Type
body_ty, forall a. Outputable a => a -> SDoc
ppr [Type]
arg_tys]
    ([Type]
arg_tys_prefix, [Type]
arg_tys_rest) = forall b a. [b] -> [a] -> ([a], [a])
splitAtList [TyVar]
tvs [Type]
arg_tys



{- Note [Care with kind instantiation]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose we have
  T :: forall k. k
and we are finding the kind of
  T (forall b. b -> b) * Int
Then
  T (forall b. b->b) :: k[ k :-> forall b. b->b]
                     :: forall b. b -> b
So
  T (forall b. b->b) * :: (b -> b)[ b :-> *]
                       :: * -> *

In other words we must instantiate the forall!

Similarly (#15428)
   S :: forall k f. k -> f k
and we are finding the kind of
   S * (* ->) Int Bool
We have
   S * (* ->) :: (k -> f k)[ k :-> *, f :-> (* ->)]
              :: * -> * -> *
So again we must instantiate.

The same thing happens in GHC.CoreToIface.toIfaceAppArgsX.

---------------------------------------------------------------------
                                TyConApp
                                ~~~~~~~~
-}

-- splitTyConApp "looks through" synonyms, because they don't
-- mean a distinct type, but all other type-constructor applications
-- including functions are returned as Just ..

-- | Retrieve the tycon heading this type, if there is one. Does /not/
-- look through synonyms.
tyConAppTyConPicky_maybe :: Type -> Maybe TyCon
tyConAppTyConPicky_maybe :: Type -> Maybe TyCon
tyConAppTyConPicky_maybe (TyConApp TyCon
tc [Type]
_) = forall a. a -> Maybe a
Just TyCon
tc
tyConAppTyConPicky_maybe (FunTy {})      = forall a. a -> Maybe a
Just TyCon
funTyCon
tyConAppTyConPicky_maybe Type
_               = forall a. Maybe a
Nothing


-- | The same as @fst . splitTyConApp@
{-# INLINE tyConAppTyCon_maybe #-}
tyConAppTyCon_maybe :: Type -> Maybe TyCon
tyConAppTyCon_maybe :: Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty = case Type -> Type
coreFullView Type
ty of
  TyConApp TyCon
tc [Type]
_ -> forall a. a -> Maybe a
Just TyCon
tc
  FunTy {}      -> forall a. a -> Maybe a
Just TyCon
funTyCon
  Type
_             -> forall a. Maybe a
Nothing

tyConAppTyCon :: HasDebugCallStack => Type -> TyCon
tyConAppTyCon :: HasDebugCallStack => Type -> TyCon
tyConAppTyCon Type
ty = Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty forall a. Maybe a -> a -> a
`orElse` forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"tyConAppTyCon" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- | The same as @snd . splitTyConApp@
tyConAppArgs_maybe :: Type -> Maybe [Type]
tyConAppArgs_maybe :: Type -> Maybe [Type]
tyConAppArgs_maybe Type
ty = case Type -> Type
coreFullView Type
ty of
  TyConApp TyCon
_ [Type]
tys -> forall a. a -> Maybe a
Just [Type]
tys
  FunTy AnonArgFlag
_ Type
w Type
arg Type
res
    | Just Type
rep1 <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
arg
    , Just Type
rep2 <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
res
    -> forall a. a -> Maybe a
Just [Type
w, Type
rep1, Type
rep2, Type
arg, Type
res]
  Type
_ -> forall a. Maybe a
Nothing

tyConAppArgs :: HasCallStack => Type -> [Type]
tyConAppArgs :: HasCallStack => Type -> [Type]
tyConAppArgs Type
ty = Type -> Maybe [Type]
tyConAppArgs_maybe Type
ty forall a. Maybe a -> a -> a
`orElse` forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"tyConAppArgs" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

tyConAppArgN :: Int -> Type -> Type
-- Executing Nth
tyConAppArgN :: Int -> Type -> Type
tyConAppArgN Int
n Type
ty
  = case Type -> Maybe [Type]
tyConAppArgs_maybe Type
ty of
      Just [Type]
tys -> [Type]
tys forall a. Outputable a => [a] -> Int -> a
`getNth` Int
n
      Maybe [Type]
Nothing  -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"tyConAppArgN" (forall a. Outputable a => a -> SDoc
ppr Int
n SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- | Attempts to tease a type apart into a type constructor and the application
-- of a number of arguments to that constructor. Panics if that is not possible.
-- See also 'splitTyConApp_maybe'
splitTyConApp :: Type -> (TyCon, [Type])
splitTyConApp :: Type -> (TyCon, [Type])
splitTyConApp Type
ty = case HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
ty of
                   Just (TyCon, [Type])
stuff -> (TyCon, [Type])
stuff
                   Maybe (TyCon, [Type])
Nothing    -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"splitTyConApp" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- | Attempts to tease a type apart into a type constructor and the application
-- of a number of arguments to that constructor
splitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe = HasDebugCallStack => Type -> Maybe (TyCon, [Type])
repSplitTyConApp_maybe forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> Type
coreFullView

-- | Split a type constructor application into its type constructor and
-- applied types. Note that this may fail in the case of a 'FunTy' with an
-- argument of unknown kind 'FunTy' (e.g. @FunTy (a :: k) Int@. since the kind
-- of @a@ isn't of the form @TYPE rep@). Consequently, you may need to zonk your
-- type before using this function.
--
-- This does *not* split types headed with (=>), as that's not a TyCon in the
-- type-checker.
--
-- If you only need the 'TyCon', consider using 'tcTyConAppTyCon_maybe'.
tcSplitTyConApp_maybe :: HasCallStack => Type -> Maybe (TyCon, [Type])
-- Defined here to avoid module loops between Unify and TcType.
tcSplitTyConApp_maybe :: HasCallStack => Type -> Maybe (TyCon, [Type])
tcSplitTyConApp_maybe Type
ty | Just Type
ty' <- Type -> Maybe Type
tcView Type
ty = HasCallStack => Type -> Maybe (TyCon, [Type])
tcSplitTyConApp_maybe Type
ty'
                         | Bool
otherwise             = HasDebugCallStack => Type -> Maybe (TyCon, [Type])
tcRepSplitTyConApp_maybe Type
ty

-------------------
repSplitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
-- ^ Like 'splitTyConApp_maybe', but doesn't look through synonyms. This
-- assumes the synonyms have already been dealt with.
repSplitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
repSplitTyConApp_maybe (TyConApp TyCon
tc [Type]
tys) = forall a. a -> Maybe a
Just (TyCon
tc, [Type]
tys)
repSplitTyConApp_maybe (FunTy AnonArgFlag
_ Type
w Type
arg Type
res)
  -- NB: we're in Core, so no check for VisArg
  = forall a. a -> Maybe a
Just (TyCon
funTyCon, [Type
w, Type
arg_rep, Type
res_rep, Type
arg, Type
res])
  where
    arg_rep :: Type
arg_rep = HasDebugCallStack => Type -> Type
getRuntimeRep Type
arg
    res_rep :: Type
res_rep = HasDebugCallStack => Type -> Type
getRuntimeRep Type
res
repSplitTyConApp_maybe Type
_ = forall a. Maybe a
Nothing

tcRepSplitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
-- ^ Like 'tcSplitTyConApp_maybe', but doesn't look through synonyms. This
-- assumes the synonyms have already been dealt with.
--
-- Moreover, for a FunTy, it only succeeds if the argument types
-- have enough info to extract the runtime-rep arguments that
-- the funTyCon requires.  This will usually be true;
-- but may be temporarily false during canonicalization:
--     see Note [Decomposing FunTy] in GHC.Tc.Solver.Canonical
--     and Note [The Purely Kinded Type Invariant (PKTI)] in GHC.Tc.Gen.HsType,
--         Wrinkle around FunTy
tcRepSplitTyConApp_maybe :: HasDebugCallStack => Type -> Maybe (TyCon, [Type])
tcRepSplitTyConApp_maybe (TyConApp TyCon
tc [Type]
tys) = forall a. a -> Maybe a
Just (TyCon
tc, [Type]
tys)
tcRepSplitTyConApp_maybe (FunTy AnonArgFlag
VisArg Type
w Type
arg Type
res)
  -- NB: VisArg. See Note [Decomposing fat arrow c=>t]
  | Just Type
arg_rep <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
arg
  , Just Type
res_rep <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
res
  = forall a. a -> Maybe a
Just (TyCon
funTyCon, [Type
w, Type
arg_rep, Type
res_rep, Type
arg, Type
res])
tcRepSplitTyConApp_maybe Type
_ = forall a. Maybe a
Nothing

-------------------
-- | Attempts to tease a list type apart and gives the type of the elements if
-- successful (looks through type synonyms)
splitListTyConApp_maybe :: Type -> Maybe Type
splitListTyConApp_maybe :: Type -> Maybe Type
splitListTyConApp_maybe Type
ty = case HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
ty of
  Just (TyCon
tc,[Type
e]) | TyCon
tc forall a. Eq a => a -> a -> Bool
== TyCon
listTyCon -> forall a. a -> Maybe a
Just Type
e
  Maybe (TyCon, [Type])
_other                          -> forall a. Maybe a
Nothing

newTyConInstRhs :: TyCon -> [Type] -> Type
-- ^ Unwrap one 'layer' of newtype on a type constructor and its
-- arguments, using an eta-reduced version of the @newtype@ if possible.
-- This requires tys to have at least @newTyConInstArity tycon@ elements.
newTyConInstRhs :: TyCon -> [Type] -> Type
newTyConInstRhs TyCon
tycon [Type]
tys
    = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr ([TyVar]
tvs forall a b. [a] -> [b] -> Bool
`leLength` [Type]
tys) (forall a. Outputable a => a -> SDoc
ppr TyCon
tycon SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [Type]
tys SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [TyVar]
tvs) forall a b. (a -> b) -> a -> b
$
      [TyVar] -> Type -> [Type] -> Type
applyTysX [TyVar]
tvs Type
rhs [Type]
tys
  where
    ([TyVar]
tvs, Type
rhs) = TyCon -> ([TyVar], Type)
newTyConEtadRhs TyCon
tycon

{-
---------------------------------------------------------------------
                           CastTy
                           ~~~~~~
A casted type has its *kind* casted into something new.
-}

splitCastTy_maybe :: Type -> Maybe (Type, Coercion)
splitCastTy_maybe :: Type -> Maybe (Type, KindCoercion)
splitCastTy_maybe Type
ty
  | CastTy Type
ty' KindCoercion
co <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just (Type
ty', KindCoercion
co)
  | Bool
otherwise                        = forall a. Maybe a
Nothing

-- | Make a 'CastTy'. The Coercion must be nominal. Checks the
-- Coercion for reflexivity, dropping it if it's reflexive.
-- See @Note [Respecting definitional equality]@ in "GHC.Core.TyCo.Rep"
mkCastTy :: Type -> Coercion -> Type
mkCastTy :: Type -> KindCoercion -> Type
mkCastTy Type
orig_ty KindCoercion
co | KindCoercion -> Bool
isReflexiveCo KindCoercion
co = Type
orig_ty  -- (EQ2) from the Note
-- NB: Do the slow check here. This is important to keep the splitXXX
-- functions working properly. Otherwise, we may end up with something
-- like (((->) |> something_reflexive_but_not_obviously_so) biz baz)
-- fails under splitFunTy_maybe. This happened with the cheaper check
-- in test dependent/should_compile/dynamic-paper.
mkCastTy Type
orig_ty KindCoercion
co = Type -> KindCoercion -> Type
mk_cast_ty Type
orig_ty KindCoercion
co

-- | Like 'mkCastTy', but avoids checking the coercion for reflexivity,
-- as that can be expensive.
mk_cast_ty :: Type -> Coercion -> Type
mk_cast_ty :: Type -> KindCoercion -> Type
mk_cast_ty Type
orig_ty KindCoercion
co = Type -> Type
go Type
orig_ty
  where
    go :: Type -> Type
    -- See Note [Using coreView in mk_cast_ty]
    go :: Type -> Type
go Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type
go Type
ty'

    go (CastTy Type
ty KindCoercion
co1)
      -- (EQ3) from the Note
      = Type -> KindCoercion -> Type
mkCastTy Type
ty (KindCoercion
co1 KindCoercion -> KindCoercion -> KindCoercion
`mkTransCo` KindCoercion
co)
          -- call mkCastTy again for the reflexivity check

    go (ForAllTy (Bndr TyVar
tv ArgFlag
vis) Type
inner_ty)
      -- (EQ4) from the Note
      -- See Note [Weird typing rule for ForAllTy] in GHC.Core.TyCo.Rep.
      | TyVar -> Bool
isTyVar TyVar
tv
      , let fvs :: TyCoVarSet
fvs = KindCoercion -> TyCoVarSet
tyCoVarsOfCo KindCoercion
co
      = -- have to make sure that pushing the co in doesn't capture the bound var!
        if TyVar
tv TyVar -> TyCoVarSet -> Bool
`elemVarSet` TyCoVarSet
fvs
        then let empty_subst :: Subst
empty_subst = InScopeSet -> Subst
mkEmptySubst (TyCoVarSet -> InScopeSet
mkInScopeSet TyCoVarSet
fvs)
                 (Subst
subst, TyVar
tv') = HasDebugCallStack => Subst -> TyVar -> (Subst, TyVar)
substVarBndr Subst
empty_subst TyVar
tv
             in VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv' ArgFlag
vis) (HasDebugCallStack => Subst -> Type -> Type
substTy Subst
subst Type
inner_ty Type -> KindCoercion -> Type
`mk_cast_ty` KindCoercion
co)
        else VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
vis) (Type
inner_ty Type -> KindCoercion -> Type
`mk_cast_ty` KindCoercion
co)

    go Type
_ = Type -> KindCoercion -> Type
CastTy Type
orig_ty KindCoercion
co -- NB: orig_ty: preserve synonyms if possible

{-
Note [Using coreView in mk_cast_ty]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Invariants (EQ3) and (EQ4) of Note [Respecting definitional equality] in
GHC.Core.TyCo.Rep must apply regardless of type synonyms. For instance,
consider this example (#19742):

   type EqSameNat = () |> co
   useNatEq :: EqSameNat |> sym co

(Those casts aren't visible in the user-source code, of course; see #19742 for
what the user might write.)

The type `EqSameNat |> sym co` looks as if it satisfies (EQ3), as it has no
nested casts, but if we expand EqSameNat, we see that it doesn't.
And then Bad Things happen.

The solution is easy: just use `coreView` when establishing (EQ3) and (EQ4) in
`mk_cast_ty`.
-}

tyConBindersTyCoBinders :: [TyConBinder] -> [TyCoBinder]
-- Return the tyConBinders in TyCoBinder form
tyConBindersTyCoBinders :: [TyConBinder] -> [TyCoBinder]
tyConBindersTyCoBinders = forall a b. (a -> b) -> [a] -> [b]
map TyConBinder -> TyCoBinder
to_tyb
  where
    to_tyb :: TyConBinder -> TyCoBinder
to_tyb (Bndr TyVar
tv (NamedTCB ArgFlag
vis)) = VarBndr TyVar ArgFlag -> TyCoBinder
Named (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
vis)
    to_tyb (Bndr TyVar
tv (AnonTCB AnonArgFlag
af))   = AnonArgFlag -> Scaled Type -> TyCoBinder
Anon AnonArgFlag
af (forall a. a -> Scaled a
tymult (TyVar -> Type
varType TyVar
tv))

-- | (mkTyConTy tc) returns (TyConApp tc [])
-- but arranges to share that TyConApp among all calls
-- See Note [Sharing nullary TyConApps] in GHC.Core.TyCon
mkTyConTy :: TyCon -> Type
mkTyConTy :: TyCon -> Type
mkTyConTy TyCon
tycon = TyCon -> Type
tyConNullaryTy TyCon
tycon

-- | A key function: builds a 'TyConApp' or 'FunTy' as appropriate to
-- its arguments.  Applies its arguments to the constructor from left to right.
mkTyConApp :: TyCon -> [Type] -> Type
mkTyConApp :: TyCon -> [Type] -> Type
mkTyConApp TyCon
tycon []
  = -- See Note [Sharing nullary TyConApps] in GHC.Core.TyCon
    TyCon -> Type
mkTyConTy TyCon
tycon

mkTyConApp TyCon
tycon tys :: [Type]
tys@(Type
ty1:[Type]
rest)
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
funTyConKey
  = case [Type]
tys of
      [Type
w, Type
_rep1,Type
_rep2,Type
arg,Type
res] -> FunTy { ft_af :: AnonArgFlag
ft_af = AnonArgFlag
VisArg, ft_mult :: Type
ft_mult = Type
w
                                        , ft_arg :: Type
ft_arg = Type
arg, ft_res :: Type
ft_res = Type
res }
      [Type]
_ -> Type
bale_out

  -- See Note [Using synonyms to compress types]
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
tYPETyConKey
  = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
rest) forall a b. (a -> b) -> a -> b
$
--    mkTYPEapp_maybe ty1 `orElse` bale_out
    case Type -> Maybe Type
mkTYPEapp_maybe Type
ty1 of
      Just Type
ty -> Type
ty -- pprTrace "mkTYPEapp:yes" (ppr ty) ty
      Maybe Type
Nothing -> Type
bale_out -- pprTrace "mkTYPEapp:no" (ppr bale_out) bale_out

  -- See Note [Using synonyms to compress types]
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
boxedRepDataConTyConKey
  = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
rest) forall a b. (a -> b) -> a -> b
$
--     mkBoxedRepApp_maybe ty1 `orElse` bale_out
    case Type -> Maybe Type
mkBoxedRepApp_maybe Type
ty1 of
      Just Type
ty -> Type
ty -- pprTrace "mkBoxedRepApp:yes" (ppr ty) ty
      Maybe Type
Nothing -> Type
bale_out -- pprTrace "mkBoxedRepApp:no" (ppr bale_out) bale_out

  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
tupleRepDataConTyConKey
  = case Type -> Maybe Type
mkTupleRepApp_maybe Type
ty1 of
      Just Type
ty -> Type
ty -- pprTrace "mkTupleRepApp:yes" (ppr ty) ty
      Maybe Type
Nothing -> Type
bale_out -- pprTrace "mkTupleRepApp:no" (ppr bale_out) bale_out

  -- The catch-all case
  | Bool
otherwise
  = Type
bale_out
  where
    key :: Unique
key = TyCon -> Unique
tyConUnique TyCon
tycon
    bale_out :: Type
bale_out = TyCon -> [Type] -> Type
TyConApp TyCon
tycon [Type]
tys

mkTYPEapp :: RuntimeRepType -> Type
mkTYPEapp :: Type -> Type
mkTYPEapp Type
rr
  = case Type -> Maybe Type
mkTYPEapp_maybe Type
rr of
       Just Type
ty -> Type
ty
       Maybe Type
Nothing -> TyCon -> [Type] -> Type
TyConApp TyCon
tYPETyCon [Type
rr]

mkTYPEapp_maybe :: RuntimeRepType -> Maybe Type
-- ^ Given a @RuntimeRep@, applies @TYPE@ to it.
-- On the fly it rewrites
--      TYPE LiftedRep      -->   liftedTypeKind    (a synonym)
--      TYPE UnliftedRep    -->   unliftedTypeKind  (ditto)
--      TYPE ZeroBitRep     -->   zeroBitTypeKind   (ditto)
-- NB: no need to check for TYPE (BoxedRep Lifted), TYPE (BoxedRep Unlifted)
--     because those inner types should already have been rewritten
--     to LiftedRep and UnliftedRep respectively, by mkTyConApp
--
-- see Note [TYPE and RuntimeRep] in GHC.Builtin.Types.Prim.
-- See Note [Using synonyms to compress types] in GHC.Core.Type
{-# NOINLINE mkTYPEapp_maybe #-}
mkTYPEapp_maybe :: Type -> Maybe Type
mkTYPEapp_maybe (TyConApp TyCon
tc [Type]
args)
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
liftedRepTyConKey    = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
liftedTypeKind   -- TYPE LiftedRep
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
unliftedRepTyConKey  = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
unliftedTypeKind -- TYPE UnliftedRep
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
zeroBitRepTyConKey   = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
zeroBitTypeKind  -- TYPE ZeroBitRep
  where
    key :: Unique
key = TyCon -> Unique
tyConUnique TyCon
tc
mkTYPEapp_maybe Type
_ = forall a. Maybe a
Nothing

mkBoxedRepApp_maybe :: Type -> Maybe Type
-- ^ Given a `Levity`, apply `BoxedRep` to it
-- On the fly, rewrite
--      BoxedRep Lifted     -->   liftedRepTy    (a synonym)
--      BoxedRep Unlifted   -->   unliftedRepTy  (ditto)
-- See Note [TYPE and RuntimeRep] in GHC.Builtin.Types.Prim.
-- See Note [Using synonyms to compress types] in GHC.Core.Type
{-# NOINLINE mkBoxedRepApp_maybe #-}
mkBoxedRepApp_maybe :: Type -> Maybe Type
mkBoxedRepApp_maybe (TyConApp TyCon
tc [Type]
args)
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
liftedDataConKey   = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
liftedRepTy    -- BoxedRep Lifted
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
unliftedDataConKey = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
unliftedRepTy  -- BoxedRep Unlifted
  where
    key :: Unique
key = TyCon -> Unique
tyConUnique TyCon
tc
mkBoxedRepApp_maybe Type
_ = forall a. Maybe a
Nothing

mkTupleRepApp_maybe :: Type -> Maybe Type
-- ^ Given a `[RuntimeRep]`, apply `TupleRep` to it
-- On the fly, rewrite
--      TupleRep [] -> zeroBitRepTy   (a synonym)
-- See Note [TYPE and RuntimeRep] in GHC.Builtin.Types.Prim.
-- See Note [Using synonyms to compress types] in GHC.Core.Type
{-# NOINLINE mkTupleRepApp_maybe #-}
mkTupleRepApp_maybe :: Type -> Maybe Type
mkTupleRepApp_maybe (TyConApp TyCon
tc [Type]
args)
  | Unique
key forall a. Eq a => a -> a -> Bool
== Unique
nilDataConKey = forall a. HasCallStack => Bool -> a -> a
assert (forall a. [a] -> Bool
isSingleton [Type]
args) forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Type
zeroBitRepTy  -- ZeroBitRep
  where
    key :: Unique
key = TyCon -> Unique
tyConUnique TyCon
tc
mkTupleRepApp_maybe Type
_ = forall a. Maybe a
Nothing

{- Note [Using synonyms to compress types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Was: Prefer Type over TYPE (BoxedRep Lifted)]

The Core of nearly any program will have numerous occurrences of the Types

   TyConApp BoxedRep [TyConApp Lifted []]    -- Synonym LiftedRep
   TyConApp BoxedRep [TyConApp Unlifted []]  -- Synonym UnliftedREp
   TyConApp TYPE [TyConApp LiftedRep []]     -- Synonym Type
   TyConApp TYPE [TyConApp UnliftedRep []]   -- Synonym UnliftedType

While investigating #17292 we found that these constituted a majority
of all TyConApp constructors on the heap:

    (From a sample of 100000 TyConApp closures)
    0x45f3523    - 28732 - `Type`
    0x420b840702 - 9629  - generic type constructors
    0x42055b7e46 - 9596
    0x420559b582 - 9511
    0x420bb15a1e - 9509
    0x420b86c6ba - 9501
    0x42055bac1e - 9496
    0x45e68fd    - 538   - `TYPE ...`

Consequently, we try hard to ensure that operations on such types are
efficient. Specifically, we strive to

 a. Avoid heap allocation of such types; use a single static TyConApp
 b. Use a small (shallow in the tree-depth sense) representation
    for such types

Goal (b) is particularly useful as it makes traversals (e.g. free variable
traversal, substitution, and comparison) more efficient.
Comparison in particular takes special advantage of nullary type synonym
applications (e.g. things like @TyConApp typeTyCon []@), Note [Comparing
nullary type synonyms] in "GHC.Core.Type".

To accomplish these we use a number of tricks, implemented by mkTyConApp.

 1. Instead of (TyConApp BoxedRep [TyConApp Lifted []]),
    we prefer a statically-allocated (TyConApp LiftedRep [])
    where `LiftedRep` is a type synonym:
       type LiftedRep = BoxedRep Lifted
    Similarly for UnliftedRep

 2. Instead of (TyConApp TYPE [TyConApp LiftedRep []])
    we prefer the statically-allocated (TyConApp Type [])
    where `Type` is a type synonym
       type Type = TYPE LiftedRep
    Similarly for UnliftedType

These serve goal (b) since there are no applied type arguments to traverse,
e.g., during comparison.

 3. We have a single, statically allocated top-level binding to
    represent `TyConApp GHC.Types.Type []` (namely
    'GHC.Builtin.Types.Prim.liftedTypeKind'), ensuring that we don't
    need to allocate such types (goal (a)).  See functions
    mkTYPEapp and mkBoxedRepApp

 4. We use the sharing mechanism described in Note [Sharing nullary TyConApps]
    in GHC.Core.TyCon to ensure that we never need to allocate such
    nullary applications (goal (a)).

See #17958, #20541

Note [Care using synonyms to compress types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Using a synonym to compress a types has a tricky wrinkle. Consider
coreView applied to (TyConApp LiftedRep [])

* coreView expands the LiftedRep synonym:
     type LiftedRep = BoxedRep Lifted

* Danger: we might apply the empty substitution to the RHS of the
  synonym.  And substTy calls mkTyConApp BoxedRep [Lifted]. And
  mkTyConApp compresses that back to LiftedRep.  Loop!

* Solution: in expandSynTyConApp_maybe, don't call substTy for nullary
  type synonyms.  That's more efficient anyway.
-}



{-
--------------------------------------------------------------------
                            CoercionTy
                            ~~~~~~~~~~
CoercionTy allows us to inject coercions into types. A CoercionTy
should appear only in the right-hand side of an application.
-}

mkCoercionTy :: Coercion -> Type
mkCoercionTy :: KindCoercion -> Type
mkCoercionTy = KindCoercion -> Type
CoercionTy

isCoercionTy :: Type -> Bool
isCoercionTy :: Type -> Bool
isCoercionTy (CoercionTy KindCoercion
_) = Bool
True
isCoercionTy Type
_              = Bool
False

isCoercionTy_maybe :: Type -> Maybe Coercion
isCoercionTy_maybe :: Type -> Maybe KindCoercion
isCoercionTy_maybe (CoercionTy KindCoercion
co) = forall a. a -> Maybe a
Just KindCoercion
co
isCoercionTy_maybe Type
_               = forall a. Maybe a
Nothing

stripCoercionTy :: Type -> Coercion
stripCoercionTy :: Type -> KindCoercion
stripCoercionTy (CoercionTy KindCoercion
co) = KindCoercion
co
stripCoercionTy Type
ty              = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"stripCoercionTy" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

{-
---------------------------------------------------------------------
                                SynTy
                                ~~~~~

Notes on type synonyms
~~~~~~~~~~~~~~~~~~~~~~
The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
to return type synonyms wherever possible. Thus

        type Foo a = a -> a

we want
        splitFunTys (a -> Foo a) = ([a], Foo a)
not                                ([a], a -> a)

The reason is that we then get better (shorter) type signatures in
interfaces.  Notably this plays a role in tcTySigs in GHC.Tc.Gen.Bind.


---------------------------------------------------------------------
                                ForAllTy
                                ~~~~~~~~
-}

-- | Make a dependent forall over an 'Inferred' variable
mkTyCoInvForAllTy :: TyCoVar -> Type -> Type
mkTyCoInvForAllTy :: TyVar -> Type -> Type
mkTyCoInvForAllTy TyVar
tv Type
ty
  | TyVar -> Bool
isCoVar TyVar
tv
  , Bool -> Bool
not (TyVar
tv TyVar -> TyCoVarSet -> Bool
`elemVarSet` Type -> TyCoVarSet
tyCoVarsOfType Type
ty)
  = Type -> Type -> Type
mkVisFunTyMany (TyVar -> Type
varType TyVar
tv) Type
ty
  | Bool
otherwise
  = VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
Inferred) Type
ty

-- | Like 'mkTyCoInvForAllTy', but tv should be a tyvar
mkInfForAllTy :: TyVar -> Type -> Type
mkInfForAllTy :: TyVar -> Type -> Type
mkInfForAllTy TyVar
tv Type
ty = forall a. HasCallStack => Bool -> a -> a
assert (TyVar -> Bool
isTyVar TyVar
tv )
                      VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
Inferred) Type
ty

-- | Like 'mkForAllTys', but assumes all variables are dependent and
-- 'Inferred', a common case
mkTyCoInvForAllTys :: [TyCoVar] -> Type -> Type
mkTyCoInvForAllTys :: [TyVar] -> Type -> Type
mkTyCoInvForAllTys [TyVar]
tvs Type
ty = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr TyVar -> Type -> Type
mkTyCoInvForAllTy Type
ty [TyVar]
tvs

-- | Like 'mkTyCoInvForAllTys', but tvs should be a list of tyvar
mkInfForAllTys :: [TyVar] -> Type -> Type
mkInfForAllTys :: [TyVar] -> Type -> Type
mkInfForAllTys [TyVar]
tvs Type
ty = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr TyVar -> Type -> Type
mkInfForAllTy Type
ty [TyVar]
tvs

-- | Like 'mkForAllTy', but assumes the variable is dependent and 'Specified',
-- a common case
mkSpecForAllTy :: TyVar -> Type -> Type
mkSpecForAllTy :: TyVar -> Type -> Type
mkSpecForAllTy TyVar
tv Type
ty = forall a. HasCallStack => Bool -> a -> a
assert (TyVar -> Bool
isTyVar TyVar
tv )
                       -- covar is always Inferred, so input should be tyvar
                       VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
Specified) Type
ty

-- | Like 'mkForAllTys', but assumes all variables are dependent and
-- 'Specified', a common case
mkSpecForAllTys :: [TyVar] -> Type -> Type
mkSpecForAllTys :: [TyVar] -> Type -> Type
mkSpecForAllTys [TyVar]
tvs Type
ty = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr TyVar -> Type -> Type
mkSpecForAllTy Type
ty [TyVar]
tvs

-- | Like mkForAllTys, but assumes all variables are dependent and visible
mkVisForAllTys :: [TyVar] -> Type -> Type
mkVisForAllTys :: [TyVar] -> Type -> Type
mkVisForAllTys [TyVar]
tvs = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all TyVar -> Bool
isTyVar [TyVar]
tvs )
                     -- covar is always Inferred, so all inputs should be tyvar
                     [VarBndr TyVar ArgFlag] -> Type -> Type
mkForAllTys [ forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv ArgFlag
Required | TyVar
tv <- [TyVar]
tvs ]

-- | Given a list of type-level vars and the free vars of a result kind,
-- makes TyCoBinders, preferring anonymous binders
-- if the variable is, in fact, not dependent.
-- e.g.    mkTyConBindersPreferAnon [(k:*),(b:k),(c:k)] (k->k)
-- We want (k:*) Named, (b:k) Anon, (c:k) Anon
--
-- All non-coercion binders are /visible/.
mkTyConBindersPreferAnon :: [TyVar]      -- ^ binders
                         -> TyCoVarSet   -- ^ free variables of result
                         -> [TyConBinder]
mkTyConBindersPreferAnon :: [TyVar] -> TyCoVarSet -> [TyConBinder]
mkTyConBindersPreferAnon [TyVar]
vars TyCoVarSet
inner_tkvs = forall a. HasCallStack => Bool -> a -> a
assert (forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all TyVar -> Bool
isTyVar [TyVar]
vars)
                                           forall a b. (a, b) -> a
fst ([TyVar] -> ([TyConBinder], TyCoVarSet)
go [TyVar]
vars)
  where
    go :: [TyVar] -> ([TyConBinder], VarSet) -- also returns the free vars
    go :: [TyVar] -> ([TyConBinder], TyCoVarSet)
go [] = ([], TyCoVarSet
inner_tkvs)
    go (TyVar
v:[TyVar]
vs) | TyVar
v TyVar -> TyCoVarSet -> Bool
`elemVarSet` TyCoVarSet
fvs
              = ( forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
v (ArgFlag -> TyConBndrVis
NamedTCB ArgFlag
Required) forall a. a -> [a] -> [a]
: [TyConBinder]
binders
                , TyCoVarSet
fvs TyCoVarSet -> TyVar -> TyCoVarSet
`delVarSet` TyVar
v TyCoVarSet -> TyCoVarSet -> TyCoVarSet
`unionVarSet` TyCoVarSet
kind_vars )
              | Bool
otherwise
              = ( forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
v (AnonArgFlag -> TyConBndrVis
AnonTCB AnonArgFlag
VisArg) forall a. a -> [a] -> [a]
: [TyConBinder]
binders
                , TyCoVarSet
fvs TyCoVarSet -> TyCoVarSet -> TyCoVarSet
`unionVarSet` TyCoVarSet
kind_vars )
      where
        ([TyConBinder]
binders, TyCoVarSet
fvs) = [TyVar] -> ([TyConBinder], TyCoVarSet)
go [TyVar]
vs
        kind_vars :: TyCoVarSet
kind_vars      = Type -> TyCoVarSet
tyCoVarsOfType forall a b. (a -> b) -> a -> b
$ TyVar -> Type
tyVarKind TyVar
v

-- | Take a ForAllTy apart, returning the list of tycovars and the result type.
-- This always succeeds, even if it returns only an empty list. Note that the
-- result type returned may have free variables that were bound by a forall.
splitForAllTyCoVars :: Type -> ([TyCoVar], Type)
splitForAllTyCoVars :: Type -> ([TyVar], Type)
splitForAllTyCoVars Type
ty = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
ty Type
ty []
  where
    split :: Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
_       (ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
ty)    [TyVar]
tvs = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
ty Type
ty (TyVar
tvforall a. a -> [a] -> [a]
:[TyVar]
tvs)
    split Type
orig_ty Type
ty [TyVar]
tvs | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
orig_ty Type
ty' [TyVar]
tvs
    split Type
orig_ty Type
_                            [TyVar]
tvs = (forall a. [a] -> [a]
reverse [TyVar]
tvs, Type
orig_ty)

-- | Splits the longest initial sequence of 'ForAllTy's that satisfy
-- @argf_pred@, returning the binders transformed by @argf_pred@
splitSomeForAllTyCoVarBndrs :: (ArgFlag -> Maybe af) -> Type -> ([VarBndr TyCoVar af], Type)
splitSomeForAllTyCoVarBndrs :: forall af.
(ArgFlag -> Maybe af) -> Type -> ([VarBndr TyVar af], Type)
splitSomeForAllTyCoVarBndrs ArgFlag -> Maybe af
argf_pred Type
ty = Type -> Type -> [VarBndr TyVar af] -> ([VarBndr TyVar af], Type)
split Type
ty Type
ty []
  where
    split :: Type -> Type -> [VarBndr TyVar af] -> ([VarBndr TyVar af], Type)
split Type
_ (ForAllTy (Bndr TyVar
tcv ArgFlag
argf) Type
ty) [VarBndr TyVar af]
tvs
      | Just af
argf' <- ArgFlag -> Maybe af
argf_pred ArgFlag
argf               = Type -> Type -> [VarBndr TyVar af] -> ([VarBndr TyVar af], Type)
split Type
ty Type
ty (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tcv af
argf' forall a. a -> [a] -> [a]
: [VarBndr TyVar af]
tvs)
    split Type
orig_ty Type
ty [VarBndr TyVar af]
tvs | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type -> [VarBndr TyVar af] -> ([VarBndr TyVar af], Type)
split Type
orig_ty Type
ty' [VarBndr TyVar af]
tvs
    split Type
orig_ty Type
_                            [VarBndr TyVar af]
tvs = (forall a. [a] -> [a]
reverse [VarBndr TyVar af]
tvs, Type
orig_ty)

-- | Like 'splitForAllTyCoVars', but only splits 'ForAllTy's with 'Required' type
-- variable binders. Furthermore, each returned tyvar is annotated with '()'.
splitForAllReqTVBinders :: Type -> ([ReqTVBinder], Type)
splitForAllReqTVBinders :: Type -> ([ReqTVBinder], Type)
splitForAllReqTVBinders Type
ty = forall af.
(ArgFlag -> Maybe af) -> Type -> ([VarBndr TyVar af], Type)
splitSomeForAllTyCoVarBndrs ArgFlag -> Maybe ()
argf_pred Type
ty
  where
    argf_pred :: ArgFlag -> Maybe ()
    argf_pred :: ArgFlag -> Maybe ()
argf_pred ArgFlag
Required       = forall a. a -> Maybe a
Just ()
    argf_pred (Invisible {}) = forall a. Maybe a
Nothing

-- | Like 'splitForAllTyCoVars', but only splits 'ForAllTy's with 'Invisible' type
-- variable binders. Furthermore, each returned tyvar is annotated with its
-- 'Specificity'.
splitForAllInvisTVBinders :: Type -> ([InvisTVBinder], Type)
splitForAllInvisTVBinders :: Type -> ([InvisTVBinder], Type)
splitForAllInvisTVBinders Type
ty = forall af.
(ArgFlag -> Maybe af) -> Type -> ([VarBndr TyVar af], Type)
splitSomeForAllTyCoVarBndrs ArgFlag -> Maybe Specificity
argf_pred Type
ty
  where
    argf_pred :: ArgFlag -> Maybe Specificity
    argf_pred :: ArgFlag -> Maybe Specificity
argf_pred ArgFlag
Required         = forall a. Maybe a
Nothing
    argf_pred (Invisible Specificity
spec) = forall a. a -> Maybe a
Just Specificity
spec

-- | Like 'splitForAllTyCoVars', but split only for tyvars.
-- This always succeeds, even if it returns only an empty list. Note that the
-- result type returned may have free variables that were bound by a forall.
splitForAllTyVars :: Type -> ([TyVar], Type)
splitForAllTyVars :: Type -> ([TyVar], Type)
splitForAllTyVars Type
ty = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
ty Type
ty []
  where
    split :: Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
_ (ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
ty) [TyVar]
tvs | TyVar -> Bool
isTyVar TyVar
tv = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
ty Type
ty (TyVar
tvforall a. a -> [a] -> [a]
:[TyVar]
tvs)
    split Type
orig_ty Type
ty [TyVar]
tvs | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty     = Type -> Type -> [TyVar] -> ([TyVar], Type)
split Type
orig_ty Type
ty' [TyVar]
tvs
    split Type
orig_ty Type
_                   [TyVar]
tvs              = (forall a. [a] -> [a]
reverse [TyVar]
tvs, Type
orig_ty)

-- | Checks whether this is a proper forall (with a named binder)
isForAllTy :: Type -> Bool
isForAllTy :: Type -> Bool
isForAllTy Type
ty
  | ForAllTy {} <- Type -> Type
coreFullView Type
ty = Bool
True
  | Bool
otherwise                      = Bool
False

-- | Like `isForAllTy`, but returns True only if it is a tyvar binder
isForAllTy_ty :: Type -> Bool
isForAllTy_ty :: Type -> Bool
isForAllTy_ty Type
ty
  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
_ <- Type -> Type
coreFullView Type
ty
  , TyVar -> Bool
isTyVar TyVar
tv
  = Bool
True

  | Bool
otherwise = Bool
False

-- | Like `isForAllTy`, but returns True only if it is a covar binder
isForAllTy_co :: Type -> Bool
isForAllTy_co :: Type -> Bool
isForAllTy_co Type
ty
  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
_ <- Type -> Type
coreFullView Type
ty
  , TyVar -> Bool
isCoVar TyVar
tv
  = Bool
True

  | Bool
otherwise = Bool
False

-- | Is this a function or forall?
isPiTy :: Type -> Bool
isPiTy :: Type -> Bool
isPiTy Type
ty = case Type -> Type
coreFullView Type
ty of
  ForAllTy {} -> Bool
True
  FunTy {}    -> Bool
True
  Type
_           -> Bool
False

-- | Is this a function?
isFunTy :: Type -> Bool
isFunTy :: Type -> Bool
isFunTy Type
ty
  | FunTy {} <- Type -> Type
coreFullView Type
ty = Bool
True
  | Bool
otherwise                   = Bool
False

-- | Take a forall type apart, or panics if that is not possible.
splitForAllTyCoVar :: Type -> (TyCoVar, Type)
splitForAllTyCoVar :: Type -> (TyVar, Type)
splitForAllTyCoVar Type
ty
  | Just (TyVar, Type)
answer <- Type -> Maybe (TyVar, Type)
splitForAllTyCoVar_maybe Type
ty = (TyVar, Type)
answer
  | Bool
otherwise                                  = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"splitForAllTyCoVar" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- | Drops all ForAllTys
dropForAlls :: Type -> Type
dropForAlls :: Type -> Type
dropForAlls Type
ty = Type -> Type
go Type
ty
  where
    go :: Type -> Type
go (ForAllTy VarBndr TyVar ArgFlag
_ Type
res)            = Type -> Type
go Type
res
    go Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type
go Type
ty'
    go Type
res                         = Type
res

-- | Attempts to take a forall type apart, but only if it's a proper forall,
-- with a named binder
splitForAllTyCoVar_maybe :: Type -> Maybe (TyCoVar, Type)
splitForAllTyCoVar_maybe :: Type -> Maybe (TyVar, Type)
splitForAllTyCoVar_maybe Type
ty
  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
inner_ty <- Type -> Type
coreFullView Type
ty = forall a. a -> Maybe a
Just (TyVar
tv, Type
inner_ty)
  | Bool
otherwise                                        = forall a. Maybe a
Nothing

-- | Like 'splitForAllTyCoVar_maybe', but only returns Just if it is a tyvar binder.
splitForAllTyVar_maybe :: Type -> Maybe (TyCoVar, Type)
splitForAllTyVar_maybe :: Type -> Maybe (TyVar, Type)
splitForAllTyVar_maybe Type
ty
  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
inner_ty <- Type -> Type
coreFullView Type
ty
  , TyVar -> Bool
isTyVar TyVar
tv
  = forall a. a -> Maybe a
Just (TyVar
tv, Type
inner_ty)

  | Bool
otherwise = forall a. Maybe a
Nothing

-- | Like 'splitForAllTyCoVar_maybe', but only returns Just if it is a covar binder.
splitForAllCoVar_maybe :: Type -> Maybe (TyCoVar, Type)
splitForAllCoVar_maybe :: Type -> Maybe (TyVar, Type)
splitForAllCoVar_maybe Type
ty
  | ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
inner_ty <- Type -> Type
coreFullView Type
ty
  , TyVar -> Bool
isCoVar TyVar
tv
  = forall a. a -> Maybe a
Just (TyVar
tv, Type
inner_ty)

  | Bool
otherwise = forall a. Maybe a
Nothing

-- | Attempts to take a forall type apart; works with proper foralls and
-- functions
{-# INLINE splitPiTy_maybe #-}  -- callers will immediately deconstruct
splitPiTy_maybe :: Type -> Maybe (TyCoBinder, Type)
splitPiTy_maybe :: Type -> Maybe (TyCoBinder, Type)
splitPiTy_maybe Type
ty = case Type -> Type
coreFullView Type
ty of
  ForAllTy VarBndr TyVar ArgFlag
bndr Type
ty -> forall a. a -> Maybe a
Just (VarBndr TyVar ArgFlag -> TyCoBinder
Named VarBndr TyVar ArgFlag
bndr, Type
ty)
  FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af, ft_mult :: Type -> Type
ft_mult = Type
w, ft_arg :: Type -> Type
ft_arg = Type
arg, ft_res :: Type -> Type
ft_res = Type
res}
                   -> forall a. a -> Maybe a
Just (AnonArgFlag -> Scaled Type -> TyCoBinder
Anon AnonArgFlag
af (forall a. Type -> a -> Scaled a
mkScaled Type
w Type
arg), Type
res)
  Type
_                -> forall a. Maybe a
Nothing

-- | Takes a forall type apart, or panics
splitPiTy :: Type -> (TyCoBinder, Type)
splitPiTy :: Type -> (TyCoBinder, Type)
splitPiTy Type
ty
  | Just (TyCoBinder, Type)
answer <- Type -> Maybe (TyCoBinder, Type)
splitPiTy_maybe Type
ty = (TyCoBinder, Type)
answer
  | Bool
otherwise                         = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"splitPiTy" (forall a. Outputable a => a -> SDoc
ppr Type
ty)

-- | Split off all TyCoBinders to a type, splitting both proper foralls
-- and functions
splitPiTys :: Type -> ([TyCoBinder], Type)
splitPiTys :: Type -> ([TyCoBinder], Type)
splitPiTys Type
ty = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
ty Type
ty []
  where
    split :: Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
_       (ForAllTy VarBndr TyVar ArgFlag
b Type
res) [TyCoBinder]
bs = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
res Type
res (VarBndr TyVar ArgFlag -> TyCoBinder
Named VarBndr TyVar ArgFlag
b  forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
    split Type
_       (FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af, ft_mult :: Type -> Type
ft_mult = Type
w, ft_arg :: Type -> Type
ft_arg = Type
arg, ft_res :: Type -> Type
ft_res = Type
res }) [TyCoBinder]
bs
                                      = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
res Type
res (AnonArgFlag -> Scaled Type -> TyCoBinder
Anon AnonArgFlag
af (forall a. Type -> a -> Scaled a
Scaled Type
w Type
arg) forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
    split Type
orig_ty Type
ty [TyCoBinder]
bs | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
orig_ty Type
ty' [TyCoBinder]
bs
    split Type
orig_ty Type
_                [TyCoBinder]
bs = (forall a. [a] -> [a]
reverse [TyCoBinder]
bs, Type
orig_ty)

-- | Extracts a list of run-time arguments from a function type,
-- looking through newtypes to the right of arrows.
--
-- Examples:
--
-- @
--    newtype Identity a = I a
--
--    getRuntimeArgTys (Int -> Bool -> Double) == [(Int, VisArg), (Bool, VisArg)]
--    getRuntimeArgTys (Identity Int -> Bool -> Double) == [(Identity Int, VisArg), (Bool, VisArg)]
--    getRuntimeArgTys (Int -> Identity (Bool -> Identity Double)) == [(Int, VisArg), (Bool, VisArg)]
--    getRuntimeArgTys (forall a. Show a => Identity a -> a -> Int -> Bool) == [(Show a, InvisArg), (Identity a, VisArg),(a, VisArg),(Int, VisArg)]
-- @
--
-- Note that, in the last case, the returned types might mention an out-of-scope
-- type variable. This function is used only when we really care about the /kinds/
-- of the returned types, so this is OK.
--
-- **Warning**: this function can return an infinite list. For example:
--
-- @
--   newtype N a = MkN (a -> N a)
--   getRuntimeArgTys (N a) == repeat (a, VisArg)
-- @
getRuntimeArgTys :: Type -> [(Scaled Type, AnonArgFlag)]
getRuntimeArgTys :: Type -> [(Scaled Type, AnonArgFlag)]
getRuntimeArgTys = Type -> [(Scaled Type, AnonArgFlag)]
go
  where
    go :: Type -> [(Scaled Type, AnonArgFlag)]
    go :: Type -> [(Scaled Type, AnonArgFlag)]
go (ForAllTy VarBndr TyVar ArgFlag
_ Type
res)
      = Type -> [(Scaled Type, AnonArgFlag)]
go Type
res
    go (FunTy { ft_mult :: Type -> Type
ft_mult = Type
w, ft_arg :: Type -> Type
ft_arg = Type
arg, ft_res :: Type -> Type
ft_res = Type
res, ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af })
      = (forall a. Type -> a -> Scaled a
Scaled Type
w Type
arg, AnonArgFlag
af) forall a. a -> [a] -> [a]
: Type -> [(Scaled Type, AnonArgFlag)]
go Type
res
    go Type
ty
      | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty
      = Type -> [(Scaled Type, AnonArgFlag)]
go Type
ty'
      | Just (KindCoercion
_,Type
ty') <- Type -> Maybe (KindCoercion, Type)
topNormaliseNewType_maybe Type
ty
      = Type -> [(Scaled Type, AnonArgFlag)]
go Type
ty'
      | Bool
otherwise
      = []

-- | Like 'splitPiTys' but split off only /named/ binders
--   and returns 'TyCoVarBinder's rather than 'TyCoBinder's
splitForAllTyCoVarBinders :: Type -> ([TyCoVarBinder], Type)
splitForAllTyCoVarBinders :: Type -> ([VarBndr TyVar ArgFlag], Type)
splitForAllTyCoVarBinders Type
ty = Type
-> Type
-> [VarBndr TyVar ArgFlag]
-> ([VarBndr TyVar ArgFlag], Type)
split Type
ty Type
ty []
  where
    split :: Type
-> Type
-> [VarBndr TyVar ArgFlag]
-> ([VarBndr TyVar ArgFlag], Type)
split Type
orig_ty Type
ty [VarBndr TyVar ArgFlag]
bs | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type
-> Type
-> [VarBndr TyVar ArgFlag]
-> ([VarBndr TyVar ArgFlag], Type)
split Type
orig_ty Type
ty' [VarBndr TyVar ArgFlag]
bs
    split Type
_       (ForAllTy VarBndr TyVar ArgFlag
b Type
res) [VarBndr TyVar ArgFlag]
bs = Type
-> Type
-> [VarBndr TyVar ArgFlag]
-> ([VarBndr TyVar ArgFlag], Type)
split Type
res Type
res (VarBndr TyVar ArgFlag
bforall a. a -> [a] -> [a]
:[VarBndr TyVar ArgFlag]
bs)
    split Type
orig_ty Type
_                [VarBndr TyVar ArgFlag]
bs = (forall a. [a] -> [a]
reverse [VarBndr TyVar ArgFlag]
bs, Type
orig_ty)
{-# INLINE splitForAllTyCoVarBinders #-}

invisibleTyBndrCount :: Type -> Int
-- Returns the number of leading invisible forall'd binders in the type
-- Includes invisible predicate arguments; e.g. for
--    e.g.  forall {k}. (k ~ *) => k -> k
-- returns 2 not 1
invisibleTyBndrCount :: Type -> Int
invisibleTyBndrCount Type
ty = forall (t :: * -> *) a. Foldable t => t a -> Int
length (forall a b. (a, b) -> a
fst (Type -> ([TyCoBinder], Type)
splitInvisPiTys Type
ty))

-- | Like 'splitPiTys', but returns only *invisible* binders, including constraints.
-- Stops at the first visible binder.
splitInvisPiTys :: Type -> ([TyCoBinder], Type)
splitInvisPiTys :: Type -> ([TyCoBinder], Type)
splitInvisPiTys Type
ty = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
ty Type
ty []
   where
    split :: Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
_ (ForAllTy VarBndr TyVar ArgFlag
b Type
res) [TyCoBinder]
bs
      | Bndr TyVar
_ ArgFlag
vis <- VarBndr TyVar ArgFlag
b
      , ArgFlag -> Bool
isInvisibleArgFlag ArgFlag
vis   = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
res Type
res (VarBndr TyVar ArgFlag -> TyCoBinder
Named VarBndr TyVar ArgFlag
b  forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
    split Type
_ (FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
InvisArg, ft_mult :: Type -> Type
ft_mult = Type
mult, ft_arg :: Type -> Type
ft_arg = Type
arg, ft_res :: Type -> Type
ft_res = Type
res })  [TyCoBinder]
bs
                                 = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
res Type
res (AnonArgFlag -> Scaled Type -> TyCoBinder
Anon AnonArgFlag
InvisArg (forall a. Type -> a -> Scaled a
mkScaled Type
mult Type
arg) forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
    split Type
orig_ty Type
ty [TyCoBinder]
bs
      | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty  = Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Type
orig_ty Type
ty' [TyCoBinder]
bs
    split Type
orig_ty Type
_          [TyCoBinder]
bs  = (forall a. [a] -> [a]
reverse [TyCoBinder]
bs, Type
orig_ty)

splitInvisPiTysN :: Int -> Type -> ([TyCoBinder], Type)
-- ^ Same as 'splitInvisPiTys', but stop when
--   - you have found @n@ 'TyCoBinder's,
--   - or you run out of invisible binders
splitInvisPiTysN :: Int -> Type -> ([TyCoBinder], Type)
splitInvisPiTysN Int
n Type
ty = forall {t}.
(Eq t, Num t) =>
t -> Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split Int
n Type
ty Type
ty []
   where
    split :: t -> Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split t
n Type
orig_ty Type
ty [TyCoBinder]
bs
      | t
n forall a. Eq a => a -> a -> Bool
== t
0                  = (forall a. [a] -> [a]
reverse [TyCoBinder]
bs, Type
orig_ty)
      | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = t -> Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split t
n Type
orig_ty Type
ty' [TyCoBinder]
bs
      | ForAllTy VarBndr TyVar ArgFlag
b Type
res <- Type
ty
      , Bndr TyVar
_ ArgFlag
vis <- VarBndr TyVar ArgFlag
b
      , ArgFlag -> Bool
isInvisibleArgFlag ArgFlag
vis  = t -> Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split (t
nforall a. Num a => a -> a -> a
-t
1) Type
res Type
res (VarBndr TyVar ArgFlag -> TyCoBinder
Named VarBndr TyVar ArgFlag
b  forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
      | FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
InvisArg, ft_mult :: Type -> Type
ft_mult = Type
mult, ft_arg :: Type -> Type
ft_arg = Type
arg, ft_res :: Type -> Type
ft_res = Type
res } <- Type
ty
                                = t -> Type -> Type -> [TyCoBinder] -> ([TyCoBinder], Type)
split (t
nforall a. Num a => a -> a -> a
-t
1) Type
res Type
res (AnonArgFlag -> Scaled Type -> TyCoBinder
Anon AnonArgFlag
InvisArg (forall a. Type -> a -> Scaled a
Scaled Type
mult Type
arg) forall a. a -> [a] -> [a]
: [TyCoBinder]
bs)
      | Bool
otherwise               = (forall a. [a] -> [a]
reverse [TyCoBinder]
bs, Type
orig_ty)

-- | Given a 'TyCon' and a list of argument types, filter out any invisible
-- (i.e., 'Inferred' or 'Specified') arguments.
filterOutInvisibleTypes :: TyCon -> [Type] -> [Type]
filterOutInvisibleTypes :: TyCon -> [Type] -> [Type]
filterOutInvisibleTypes TyCon
tc [Type]
tys = forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ TyCon -> [Type] -> ([Type], [Type])
partitionInvisibleTypes TyCon
tc [Type]
tys

-- | Given a 'TyCon' and a list of argument types, filter out any 'Inferred'
-- arguments.
filterOutInferredTypes :: TyCon -> [Type] -> [Type]
filterOutInferredTypes :: TyCon -> [Type] -> [Type]
filterOutInferredTypes TyCon
tc [Type]
tys =
  forall a. [Bool] -> [a] -> [a]
filterByList (forall a b. (a -> b) -> [a] -> [b]
map (forall a. Eq a => a -> a -> Bool
/= ArgFlag
Inferred) forall a b. (a -> b) -> a -> b
$ TyCon -> [Type] -> [ArgFlag]
tyConArgFlags TyCon
tc [Type]
tys) [Type]
tys

-- | Given a 'TyCon' and a list of argument types, partition the arguments
-- into:
--
-- 1. 'Inferred' or 'Specified' (i.e., invisible) arguments and
--
-- 2. 'Required' (i.e., visible) arguments
partitionInvisibleTypes :: TyCon -> [Type] -> ([Type], [Type])
partitionInvisibleTypes :: TyCon -> [Type] -> ([Type], [Type])
partitionInvisibleTypes TyCon
tc [Type]
tys =
  forall a. [Bool] -> [a] -> ([a], [a])
partitionByList (forall a b. (a -> b) -> [a] -> [b]
map ArgFlag -> Bool
isInvisibleArgFlag forall a b. (a -> b) -> a -> b
$ TyCon -> [Type] -> [ArgFlag]
tyConArgFlags TyCon
tc [Type]
tys) [Type]
tys

-- | Given a list of things paired with their visibilities, partition the
-- things into (invisible things, visible things).
partitionInvisibles :: [(a, ArgFlag)] -> ([a], [a])
partitionInvisibles :: forall a. [(a, ArgFlag)] -> ([a], [a])
partitionInvisibles = forall a b c. (a -> Either b c) -> [a] -> ([b], [c])
partitionWith forall a. (a, ArgFlag) -> Either a a
pick_invis
  where
    pick_invis :: (a, ArgFlag) -> Either a a
    pick_invis :: forall a. (a, ArgFlag) -> Either a a
pick_invis (a
thing, ArgFlag
vis) | ArgFlag -> Bool
isInvisibleArgFlag ArgFlag
vis = forall a b. a -> Either a b
Left a
thing
                            | Bool
otherwise              = forall a b. b -> Either a b
Right a
thing

-- | Given a 'TyCon' and a list of argument types to which the 'TyCon' is
-- applied, determine each argument's visibility
-- ('Inferred', 'Specified', or 'Required').
--
-- Wrinkle: consider the following scenario:
--
-- > T :: forall k. k -> k
-- > tyConArgFlags T [forall m. m -> m -> m, S, R, Q]
--
-- After substituting, we get
--
-- > T (forall m. m -> m -> m) :: (forall m. m -> m -> m) -> forall n. n -> n -> n
--
-- Thus, the first argument is invisible, @S@ is visible, @R@ is invisible again,
-- and @Q@ is visible.
tyConArgFlags :: TyCon -> [Type] -> [ArgFlag]
tyConArgFlags :: TyCon -> [Type] -> [ArgFlag]
tyConArgFlags TyCon
tc = Type -> [Type] -> [ArgFlag]
fun_kind_arg_flags (TyCon -> Type
tyConKind TyCon
tc)

-- | Given a 'Type' and a list of argument types to which the 'Type' is
-- applied, determine each argument's visibility
-- ('Inferred', 'Specified', or 'Required').
--
-- Most of the time, the arguments will be 'Required', but not always. Consider
-- @f :: forall a. a -> Type@. In @f Type Bool@, the first argument (@Type@) is
-- 'Specified' and the second argument (@Bool@) is 'Required'. It is precisely
-- this sort of higher-rank situation in which 'appTyArgFlags' comes in handy,
-- since @f Type Bool@ would be represented in Core using 'AppTy's.
-- (See also #15792).
appTyArgFlags :: Type -> [Type] -> [ArgFlag]
appTyArgFlags :: Type -> [Type] -> [ArgFlag]
appTyArgFlags Type
ty = Type -> [Type] -> [ArgFlag]
fun_kind_arg_flags (HasDebugCallStack => Type -> Type
typeKind Type
ty)

-- | Given a function kind and a list of argument types (where each argument's
-- kind aligns with the corresponding position in the argument kind), determine
-- each argument's visibility ('Inferred', 'Specified', or 'Required').
fun_kind_arg_flags :: Kind -> [Type] -> [ArgFlag]
fun_kind_arg_flags :: Type -> [Type] -> [ArgFlag]
fun_kind_arg_flags = Subst -> Type -> [Type] -> [ArgFlag]
go Subst
emptySubst
  where
    go :: Subst -> Type -> [Type] -> [ArgFlag]
go Subst
subst Type
ki [Type]
arg_tys
      | Just Type
ki' <- Type -> Maybe Type
coreView Type
ki = Subst -> Type -> [Type] -> [ArgFlag]
go Subst
subst Type
ki' [Type]
arg_tys
    go Subst
_ Type
_ [] = []
    go Subst
subst (ForAllTy (Bndr TyVar
tv ArgFlag
argf) Type
res_ki) (Type
arg_ty:[Type]
arg_tys)
      = ArgFlag
argf forall a. a -> [a] -> [a]
: Subst -> Type -> [Type] -> [ArgFlag]
go Subst
subst' Type
res_ki [Type]
arg_tys
      where
        subst' :: Subst
subst' = Subst -> TyVar -> Type -> Subst
extendTvSubst Subst
subst TyVar
tv Type
arg_ty
    go Subst
subst (TyVarTy TyVar
tv) [Type]
arg_tys
      | Just Type
ki <- Subst -> TyVar -> Maybe Type
lookupTyVar Subst
subst TyVar
tv = Subst -> Type -> [Type] -> [ArgFlag]
go Subst
subst Type
ki [Type]
arg_tys
    -- This FunTy case is important to handle kinds with nested foralls, such
    -- as this kind (inspired by #16518):
    --
    --   forall {k1} k2. k1 -> k2 -> forall k3. k3 -> Type
    --
    -- Here, we want to get the following ArgFlags:
    --
    -- [Inferred,   Specified, Required, Required, Specified, Required]
    -- forall {k1}. forall k2. k1 ->     k2 ->     forall k3. k3 ->     Type
    go Subst
subst (FunTy{ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af, ft_res :: Type -> Type
ft_res = Type
res_ki}) (Type
_:[Type]
arg_tys)
      = ArgFlag
argf forall a. a -> [a] -> [a]
: Subst -> Type -> [Type] -> [ArgFlag]
go Subst
subst Type
res_ki [Type]
arg_tys
      where
        argf :: ArgFlag
argf = case AnonArgFlag
af of
                 AnonArgFlag
VisArg   -> ArgFlag
Required
                 AnonArgFlag
InvisArg -> ArgFlag
Inferred
    go Subst
_ Type
_ [Type]
arg_tys = forall a b. (a -> b) -> [a] -> [b]
map (forall a b. a -> b -> a
const ArgFlag
Required) [Type]
arg_tys
                        -- something is ill-kinded. But this can happen
                        -- when printing errors. Assume everything is Required.

-- @isTauTy@ tests if a type has no foralls or (=>)
isTauTy :: Type -> Bool
isTauTy :: Type -> Bool
isTauTy Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Bool
isTauTy Type
ty'
isTauTy (TyVarTy TyVar
_)       = Bool
True
isTauTy (LitTy {})        = Bool
True
isTauTy (TyConApp TyCon
tc [Type]
tys) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Type -> Bool
isTauTy [Type]
tys Bool -> Bool -> Bool
&& TyCon -> Bool
isTauTyCon TyCon
tc
isTauTy (AppTy Type
a Type
b)       = Type -> Bool
isTauTy Type
a Bool -> Bool -> Bool
&& Type -> Bool
isTauTy Type
b
isTauTy (FunTy AnonArgFlag
af Type
w Type
a Type
b)    = case AnonArgFlag
af of
                                AnonArgFlag
InvisArg -> Bool
False                               -- e.g., Eq a => b
                                AnonArgFlag
VisArg   -> Type -> Bool
isTauTy Type
w Bool -> Bool -> Bool
&& Type -> Bool
isTauTy Type
a Bool -> Bool -> Bool
&& Type -> Bool
isTauTy Type
b -- e.g., a -> b
isTauTy (ForAllTy {})     = Bool
False
isTauTy (CastTy Type
ty KindCoercion
_)     = Type -> Bool
isTauTy Type
ty
isTauTy (CoercionTy KindCoercion
_)    = Bool
False  -- Not sure about this

isAtomicTy :: Type -> Bool
-- True if the type is just a single token, and can be printed compactly
-- Used when deciding how to lay out type error messages; see the
-- call in GHC.Tc.Errors
isAtomicTy :: Type -> Bool
isAtomicTy (TyVarTy {})    = Bool
True
isAtomicTy (LitTy {})      = Bool
True
isAtomicTy (TyConApp TyCon
_ []) = Bool
True

isAtomicTy Type
ty | Type -> Bool
isLiftedTypeKind Type
ty = Bool
True
   -- 'Type' prints compactly as *
   -- See GHC.Iface.Type.ppr_kind_type

isAtomicTy Type
_ = Bool
False

{-
%************************************************************************
%*                                                                      *
   TyCoBinders
%*                                                                      *
%************************************************************************
-}

-- | Make an anonymous binder
mkAnonBinder :: AnonArgFlag -> Scaled Type -> TyCoBinder
mkAnonBinder :: AnonArgFlag -> Scaled Type -> TyCoBinder
mkAnonBinder = AnonArgFlag -> Scaled Type -> TyCoBinder
Anon

-- | Does this binder bind a variable that is /not/ erased? Returns
-- 'True' for anonymous binders.
isAnonTyCoBinder :: TyCoBinder -> Bool
isAnonTyCoBinder :: TyCoBinder -> Bool
isAnonTyCoBinder (Named {}) = Bool
False
isAnonTyCoBinder (Anon {})  = Bool
True

tyCoBinderVar_maybe :: TyCoBinder -> Maybe TyCoVar
tyCoBinderVar_maybe :: TyCoBinder -> Maybe TyVar
tyCoBinderVar_maybe (Named VarBndr TyVar ArgFlag
tv) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall tv argf. VarBndr tv argf -> tv
binderVar VarBndr TyVar ArgFlag
tv
tyCoBinderVar_maybe TyCoBinder
_          = forall a. Maybe a
Nothing

tyCoBinderType :: TyCoBinder -> Type
tyCoBinderType :: TyCoBinder -> Type
tyCoBinderType (Named VarBndr TyVar ArgFlag
tvb) = forall argf. VarBndr TyVar argf -> Type
binderType VarBndr TyVar ArgFlag
tvb
tyCoBinderType (Anon AnonArgFlag
_ Scaled Type
ty)   = forall a. Scaled a -> a
scaledThing Scaled Type
ty

tyBinderType :: TyBinder -> Type
tyBinderType :: TyCoBinder -> Type
tyBinderType (Named (Bndr TyVar
tv ArgFlag
_))
  = forall a. HasCallStack => Bool -> a -> a
assert (TyVar -> Bool
isTyVar TyVar
tv )
    TyVar -> Type
tyVarKind TyVar
tv
tyBinderType (Anon AnonArgFlag
_ Scaled Type
ty)   = forall a. Scaled a -> a
scaledThing Scaled Type
ty

-- | Extract a relevant type, if there is one.
binderRelevantType_maybe :: TyCoBinder -> Maybe Type
binderRelevantType_maybe :: TyCoBinder -> Maybe Type
binderRelevantType_maybe (Named {}) = forall a. Maybe a
Nothing
binderRelevantType_maybe (Anon AnonArgFlag
_ Scaled Type
ty)  = forall a. a -> Maybe a
Just (forall a. Scaled a -> a
scaledThing Scaled Type
ty)

{-
************************************************************************
*                                                                      *
\subsection{Type families}
*                                                                      *
************************************************************************
-}

mkFamilyTyConApp :: TyCon -> [Type] -> Type
-- ^ Given a family instance TyCon and its arg types, return the
-- corresponding family type.  E.g:
--
-- > data family T a
-- > data instance T (Maybe b) = MkT b
--
-- Where the instance tycon is :RTL, so:
--
-- > mkFamilyTyConApp :RTL Int  =  T (Maybe Int)
mkFamilyTyConApp :: TyCon -> [Type] -> Type
mkFamilyTyConApp TyCon
tc [Type]
tys
  | Just (TyCon
fam_tc, [Type]
fam_tys) <- TyCon -> Maybe (TyCon, [Type])
tyConFamInst_maybe TyCon
tc
  , let tvs :: [TyVar]
tvs = TyCon -> [TyVar]
tyConTyVars TyCon
tc
        fam_subst :: Subst
fam_subst = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr ([TyVar]
tvs forall a b. [a] -> [b] -> Bool
`equalLength` [Type]
tys) (forall a. Outputable a => a -> SDoc
ppr TyCon
tc SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr [Type]
tys) forall a b. (a -> b) -> a -> b
$
                    HasDebugCallStack => [TyVar] -> [Type] -> Subst
zipTvSubst [TyVar]
tvs [Type]
tys
  = TyCon -> [Type] -> Type
mkTyConApp TyCon
fam_tc (HasDebugCallStack => Subst -> [Type] -> [Type]
substTys Subst
fam_subst [Type]
fam_tys)
  | Bool
otherwise
  = TyCon -> [Type] -> Type
mkTyConApp TyCon
tc [Type]
tys

-- | Get the type on the LHS of a coercion induced by a type/data
-- family instance.
coAxNthLHS :: CoAxiom br -> Int -> Type
coAxNthLHS :: forall (br :: BranchFlag). CoAxiom br -> Int -> Type
coAxNthLHS CoAxiom br
ax Int
ind =
  TyCon -> [Type] -> Type
mkTyConApp (forall (br :: BranchFlag). CoAxiom br -> TyCon
coAxiomTyCon CoAxiom br
ax) (CoAxBranch -> [Type]
coAxBranchLHS (forall (br :: BranchFlag). CoAxiom br -> Int -> CoAxBranch
coAxiomNthBranch CoAxiom br
ax Int
ind))

isFamFreeTy :: Type -> Bool
isFamFreeTy :: Type -> Bool
isFamFreeTy Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Bool
isFamFreeTy Type
ty'
isFamFreeTy (TyVarTy TyVar
_)       = Bool
True
isFamFreeTy (LitTy {})        = Bool
True
isFamFreeTy (TyConApp TyCon
tc [Type]
tys) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Type -> Bool
isFamFreeTy [Type]
tys Bool -> Bool -> Bool
&& TyCon -> Bool
isFamFreeTyCon TyCon
tc
isFamFreeTy (AppTy Type
a Type
b)       = Type -> Bool
isFamFreeTy Type
a Bool -> Bool -> Bool
&& Type -> Bool
isFamFreeTy Type
b
isFamFreeTy (FunTy AnonArgFlag
_ Type
w Type
a Type
b)   = Type -> Bool
isFamFreeTy Type
w Bool -> Bool -> Bool
&& Type -> Bool
isFamFreeTy Type
a Bool -> Bool -> Bool
&& Type -> Bool
isFamFreeTy Type
b
isFamFreeTy (ForAllTy VarBndr TyVar ArgFlag
_ Type
ty)   = Type -> Bool
isFamFreeTy Type
ty
isFamFreeTy (CastTy Type
ty KindCoercion
_)     = Type -> Bool
isFamFreeTy Type
ty
isFamFreeTy (CoercionTy KindCoercion
_)    = Bool
False  -- Not sure about this

-- | Does this type classify a core (unlifted) Coercion?
-- At either role nominal or representational
--    (t1 ~# t2) or (t1 ~R# t2)
-- See Note [Types for coercions, predicates, and evidence] in "GHC.Core.TyCo.Rep"
isCoVarType :: Type -> Bool
  -- ToDo: should we check saturation?
isCoVarType :: Type -> Bool
isCoVarType Type
ty
  | Just TyCon
tc <- Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty
  = TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
eqPrimTyConKey Bool -> Bool -> Bool
|| TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
eqReprPrimTyConKey
  | Bool
otherwise
  = Bool
False

buildSynTyCon :: Name -> [KnotTied TyConBinder] -> Kind   -- ^ /result/ kind
              -> [Role] -> KnotTied Type -> TyCon
-- This function is here because here is where we have
--   isFamFree and isTauTy
buildSynTyCon :: Name -> [TyConBinder] -> Type -> [Role] -> Type -> TyCon
buildSynTyCon Name
name [TyConBinder]
binders Type
res_kind [Role]
roles Type
rhs
  = Name
-> [TyConBinder]
-> Type
-> [Role]
-> Type
-> Bool
-> Bool
-> Bool
-> TyCon
mkSynonymTyCon Name
name [TyConBinder]
binders Type
res_kind [Role]
roles Type
rhs Bool
is_tau Bool
is_fam_free Bool
is_forgetful
  where
    is_tau :: Bool
is_tau       = Type -> Bool
isTauTy Type
rhs
    is_fam_free :: Bool
is_fam_free  = Type -> Bool
isFamFreeTy Type
rhs
    is_forgetful :: Bool
is_forgetful = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. (TyVar -> TyCoVarSet -> Bool
`elemVarSet` Type -> TyCoVarSet
tyCoVarsOfType Type
rhs) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall tv argf. VarBndr tv argf -> tv
binderVar) [TyConBinder]
binders Bool -> Bool -> Bool
||
                   forall a. (a -> Bool) -> UniqSet a -> Bool
uniqSetAny TyCon -> Bool
isForgetfulSynTyCon (Type -> UniqSet TyCon
tyConsOfType Type
rhs)
         -- NB: This is allowed to be conservative, returning True more often
         -- than it should. See comments on GHC.Core.TyCon.isForgetfulSynTyCon

{-
************************************************************************
*                                                                      *
\subsection{Liftedness}
*                                                                      *
************************************************************************
-}

-- | Tries to compute the 'Levity' of the given type. Returns either
-- a definite 'Levity', or 'Nothing' if we aren't sure (e.g. the
-- type is representation-polymorphic).
--
-- Panics if the kind does not have the shape @TYPE r@.
typeLevity_maybe :: HasDebugCallStack => Type -> Maybe Levity
typeLevity_maybe :: HasDebugCallStack => Type -> Maybe Levity
typeLevity_maybe Type
ty = Type -> Maybe Levity
runtimeRepLevity_maybe (HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty)

-- | Is the given type definitely unlifted?
-- See "Type#type_classification" for what an unlifted type is.
--
-- Panics on representation-polymorphic types; See 'mightBeUnliftedType' for
-- a more approximate predicate that behaves better in the presence of
-- representation polymorphism.
isUnliftedType :: HasDebugCallStack => Type -> Bool
        -- isUnliftedType returns True for forall'd unlifted types:
        --      x :: forall a. Int#
        -- I found bindings like these were getting floated to the top level.
        -- They are pretty bogus types, mind you.  It would be better never to
        -- construct them
isUnliftedType :: HasDebugCallStack => Type -> Bool
isUnliftedType Type
ty =
  case HasDebugCallStack => Type -> Maybe Levity
typeLevity_maybe Type
ty of
    Just Levity
Lifted   -> Bool
False
    Just Levity
Unlifted -> Bool
True
    Maybe Levity
Nothing       ->
      forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"isUnliftedType" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
<+> SDoc
dcolon SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr (HasDebugCallStack => Type -> Type
typeKind Type
ty))

-- | Returns:
--
-- * 'False' if the type is /guaranteed/ unlifted or
-- * 'True' if it lifted, OR we aren't sure
--    (e.g. in a representation-polymorphic case)
mightBeLiftedType :: Type -> Bool
mightBeLiftedType :: Type -> Bool
mightBeLiftedType = Maybe Levity -> Bool
mightBeLifted forall b c a. (b -> c) -> (a -> b) -> a -> c
. HasDebugCallStack => Type -> Maybe Levity
typeLevity_maybe

-- | Returns:
--
-- * 'False' if the type is /guaranteed/ lifted or
-- * 'True' if it is unlifted, OR we aren't sure
--    (e.g. in a representation-polymorphic case)
mightBeUnliftedType :: Type -> Bool
mightBeUnliftedType :: Type -> Bool
mightBeUnliftedType = Maybe Levity -> Bool
mightBeUnlifted forall b c a. (b -> c) -> (a -> b) -> a -> c
. HasDebugCallStack => Type -> Maybe Levity
typeLevity_maybe

-- | See "Type#type_classification" for what a boxed type is.
-- Panics on representation-polymorphic types; See 'mightBeUnliftedType' for
-- a more approximate predicate that behaves better in the presence of
-- representation polymorphism.
isBoxedType :: Type -> Bool
isBoxedType :: Type -> Bool
isBoxedType Type
ty = Type -> Bool
isBoxedRuntimeRep (HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty)

-- | Is this a type of kind RuntimeRep? (e.g. LiftedRep)
isRuntimeRepKindedTy :: Type -> Bool
isRuntimeRepKindedTy :: Type -> Bool
isRuntimeRepKindedTy = Type -> Bool
isRuntimeRepTy forall b c a. (b -> c) -> (a -> b) -> a -> c
. HasDebugCallStack => Type -> Type
typeKind

-- | Drops prefix of RuntimeRep constructors in 'TyConApp's. Useful for e.g.
-- dropping 'LiftedRep arguments of unboxed tuple TyCon applications:
--
--   dropRuntimeRepArgs [ 'LiftedRep, 'IntRep
--                      , String, Int# ] == [String, Int#]
--
dropRuntimeRepArgs :: [Type] -> [Type]
dropRuntimeRepArgs :: [Type] -> [Type]
dropRuntimeRepArgs = forall a. (a -> Bool) -> [a] -> [a]
dropWhile Type -> Bool
isRuntimeRepKindedTy

-- | Extract the RuntimeRep classifier of a type. For instance,
-- @getRuntimeRep_maybe Int = Just LiftedRep@. Returns 'Nothing' if this is not
-- possible.
getRuntimeRep_maybe :: HasDebugCallStack
                    => Type -> Maybe RuntimeRepType
getRuntimeRep_maybe :: HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe = HasDebugCallStack => Type -> Maybe Type
kindRep_maybe forall b c a. (b -> c) -> (a -> b) -> a -> c
. HasDebugCallStack => Type -> Type
typeKind

-- | Extract the RuntimeRep classifier of a type. For instance,
-- @getRuntimeRep_maybe Int = LiftedRep@. Panics if this is not possible.
getRuntimeRep :: HasDebugCallStack => Type -> RuntimeRepType
getRuntimeRep :: HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty
  = case HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
ty of
      Just Type
r  -> Type
r
      Maybe Type
Nothing -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"getRuntimeRep" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
<+> SDoc
dcolon SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr (HasDebugCallStack => Type -> Type
typeKind Type
ty))

-- | Extract the 'Levity' of a type. For example, @getLevity_maybe Int = Just Lifted@,
-- @getLevity (Array# Int) = Just Unlifted@, @getLevity Float# = Nothing@.
--
-- Returns 'Nothing' if this is not possible. Does not look through type family applications.
getLevity_maybe :: HasDebugCallStack => Type -> Maybe Type
getLevity_maybe :: HasDebugCallStack => Type -> Maybe Type
getLevity_maybe Type
ty
  | Just Type
rep <- HasDebugCallStack => Type -> Maybe Type
getRuntimeRep_maybe Type
ty
  , Just (TyCon
tc, [Type
lev]) <- HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
rep
  , TyCon
tc forall a. Eq a => a -> a -> Bool
== TyCon
boxedRepDataConTyCon
  = forall a. a -> Maybe a
Just Type
lev
  | Bool
otherwise
  = forall a. Maybe a
Nothing

-- | Extract the 'Levity' of a type. For example, @getLevity Int = Lifted@,
-- or @getLevity (Array# Int) = Unlifted@.
--
-- Panics if this is not possible. Does not look through type family applications.
getLevity :: HasDebugCallStack => Type -> Type
getLevity :: HasDebugCallStack => Type -> Type
getLevity Type
ty
  | Just Type
lev <- HasDebugCallStack => Type -> Maybe Type
getLevity_maybe Type
ty
  = Type
lev
  | Bool
otherwise
  = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"getLevity" (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
<+> SDoc
dcolon SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr (HasDebugCallStack => Type -> Type
typeKind Type
ty))

isUnboxedTupleType :: Type -> Bool
isUnboxedTupleType :: Type -> Bool
isUnboxedTupleType Type
ty
  = HasDebugCallStack => Type -> TyCon
tyConAppTyCon (HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty) forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
tupleRepDataConKey
  -- NB: Do not use typePrimRep, as that can't tell the difference between
  -- unboxed tuples and unboxed sums


isUnboxedSumType :: Type -> Bool
isUnboxedSumType :: Type -> Bool
isUnboxedSumType Type
ty
  = HasDebugCallStack => Type -> TyCon
tyConAppTyCon (HasDebugCallStack => Type -> Type
getRuntimeRep Type
ty) forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
sumRepDataConKey

-- | See "Type#type_classification" for what an algebraic type is.
-- Should only be applied to /types/, as opposed to e.g. partially
-- saturated type constructors
isAlgType :: Type -> Bool
isAlgType :: Type -> Bool
isAlgType Type
ty
  = case HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
ty of
      Just (TyCon
tc, [Type]
ty_args) -> forall a. HasCallStack => Bool -> a -> a
assert ([Type]
ty_args forall a. [a] -> Int -> Bool
`lengthIs` TyCon -> Int
tyConArity TyCon
tc )
                            TyCon -> Bool
isAlgTyCon TyCon
tc
      Maybe (TyCon, [Type])
_other             -> Bool
False

-- | Check whether a type is a data family type
isDataFamilyAppType :: Type -> Bool
isDataFamilyAppType :: Type -> Bool
isDataFamilyAppType Type
ty = case Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty of
                           Just TyCon
tc -> TyCon -> Bool
isDataFamilyTyCon TyCon
tc
                           Maybe TyCon
_       -> Bool
False

-- | Computes whether an argument (or let right hand side) should
-- be computed strictly or lazily, based only on its type.
-- Currently, it's just 'isUnliftedType'.
-- Panics on representation-polymorphic types.
isStrictType :: HasDebugCallStack => Type -> Bool
isStrictType :: HasDebugCallStack => Type -> Bool
isStrictType = HasDebugCallStack => Type -> Bool
isUnliftedType

isPrimitiveType :: Type -> Bool
-- ^ Returns true of types that are opaque to Haskell.
isPrimitiveType :: Type -> Bool
isPrimitiveType Type
ty = case HasDebugCallStack => Type -> Maybe (TyCon, [Type])
splitTyConApp_maybe Type
ty of
                        Just (TyCon
tc, [Type]
ty_args) -> forall a. HasCallStack => Bool -> a -> a
assert ([Type]
ty_args forall a. [a] -> Int -> Bool
`lengthIs` TyCon -> Int
tyConArity TyCon
tc )
                                              TyCon -> Bool
isPrimTyCon TyCon
tc
                        Maybe (TyCon, [Type])
_                  -> Bool
False

{-
************************************************************************
*                                                                      *
\subsection{Join points}
*                                                                      *
************************************************************************
-}

-- | Determine whether a type could be the type of a join point of given total
-- arity, according to the polymorphism rule. A join point cannot be polymorphic
-- in its return type, since given
--   join j @a @b x y z = e1 in e2,
-- the types of e1 and e2 must be the same, and a and b are not in scope for e2.
-- (See Note [The polymorphism rule of join points] in "GHC.Core".) Returns False
-- also if the type simply doesn't have enough arguments.
--
-- Note that we need to know how many arguments (type *and* value) the putative
-- join point takes; for instance, if
--   j :: forall a. a -> Int
-- then j could be a binary join point returning an Int, but it could *not* be a
-- unary join point returning a -> Int.
--
-- TODO: See Note [Excess polymorphism and join points]
isValidJoinPointType :: JoinArity -> Type -> Bool
isValidJoinPointType :: Int -> Type -> Bool
isValidJoinPointType Int
arity Type
ty
  = forall {t}. (Eq t, Num t) => TyCoVarSet -> t -> Type -> Bool
valid_under TyCoVarSet
emptyVarSet Int
arity Type
ty
  where
    valid_under :: TyCoVarSet -> t -> Type -> Bool
valid_under TyCoVarSet
tvs t
arity Type
ty
      | t
arity forall a. Eq a => a -> a -> Bool
== t
0
      = TyCoVarSet
tvs TyCoVarSet -> TyCoVarSet -> Bool
`disjointVarSet` Type -> TyCoVarSet
tyCoVarsOfType Type
ty
      | Just (TyVar
t, Type
ty') <- Type -> Maybe (TyVar, Type)
splitForAllTyCoVar_maybe Type
ty
      = TyCoVarSet -> t -> Type -> Bool
valid_under (TyCoVarSet
tvs TyCoVarSet -> TyVar -> TyCoVarSet
`extendVarSet` TyVar
t) (t
arityforall a. Num a => a -> a -> a
-t
1) Type
ty'
      | Just (Type
_, Type
_, Type
res_ty) <- Type -> Maybe (Type, Type, Type)
splitFunTy_maybe Type
ty
      = TyCoVarSet -> t -> Type -> Bool
valid_under TyCoVarSet
tvs (t
arityforall a. Num a => a -> a -> a
-t
1) Type
res_ty
      | Bool
otherwise
      = Bool
False

{- Note [Excess polymorphism and join points]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In principle, if a function would be a join point except that it fails
the polymorphism rule (see Note [The polymorphism rule of join points] in
GHC.Core), it can still be made a join point with some effort. This is because
all tail calls must return the same type (they return to the same context!), and
thus if the return type depends on an argument, that argument must always be the
same.

For instance, consider:

  let f :: forall a. a -> Char -> [a]
      f @a x c = ... f @a y 'a' ...
  in ... f @Int 1 'b' ... f @Int 2 'c' ...

(where the calls are tail calls). `f` fails the polymorphism rule because its
return type is [a], where [a] is bound. But since the type argument is always
'Int', we can rewrite it as:

  let f' :: Int -> Char -> [Int]
      f' x c = ... f' y 'a' ...
  in ... f' 1 'b' ... f 2 'c' ...

and now we can make f' a join point:

  join f' :: Int -> Char -> [Int]
       f' x c = ... jump f' y 'a' ...
  in ... jump f' 1 'b' ... jump f' 2 'c' ...

It's not clear that this comes up often, however. TODO: Measure how often and
add this analysis if necessary.  See #14620.


************************************************************************
*                                                                      *
\subsection{Sequencing on types}
*                                                                      *
************************************************************************
-}

seqType :: Type -> ()
seqType :: Type -> ()
seqType (LitTy TyLit
n)                   = TyLit
n seq :: forall a b. a -> b -> b
`seq` ()
seqType (TyVarTy TyVar
tv)                = TyVar
tv seq :: forall a b. a -> b -> b
`seq` ()
seqType (AppTy Type
t1 Type
t2)               = Type -> ()
seqType Type
t1 seq :: forall a b. a -> b -> b
`seq` Type -> ()
seqType Type
t2
seqType (FunTy AnonArgFlag
_ Type
w Type
t1 Type
t2)           = Type -> ()
seqType Type
w seq :: forall a b. a -> b -> b
`seq` Type -> ()
seqType Type
t1 seq :: forall a b. a -> b -> b
`seq` Type -> ()
seqType Type
t2
seqType (TyConApp TyCon
tc [Type]
tys)           = TyCon
tc seq :: forall a b. a -> b -> b
`seq` [Type] -> ()
seqTypes [Type]
tys
seqType (ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
ty)   = Type -> ()
seqType (TyVar -> Type
varType TyVar
tv) seq :: forall a b. a -> b -> b
`seq` Type -> ()
seqType Type
ty
seqType (CastTy Type
ty KindCoercion
co)              = Type -> ()
seqType Type
ty seq :: forall a b. a -> b -> b
`seq` KindCoercion -> ()
seqCo KindCoercion
co
seqType (CoercionTy KindCoercion
co)             = KindCoercion -> ()
seqCo KindCoercion
co

seqTypes :: [Type] -> ()
seqTypes :: [Type] -> ()
seqTypes []       = ()
seqTypes (Type
ty:[Type]
tys) = Type -> ()
seqType Type
ty seq :: forall a b. a -> b -> b
`seq` [Type] -> ()
seqTypes [Type]
tys

{-
************************************************************************
*                                                                      *
                Comparison for types
        (We don't use instances so that we know where it happens)
*                                                                      *
************************************************************************

Note [Equality on AppTys]
~~~~~~~~~~~~~~~~~~~~~~~~~
In our cast-ignoring equality, we want to say that the following two
are equal:

  (Maybe |> co) (Int |> co')   ~?       Maybe Int

But the left is an AppTy while the right is a TyConApp. The solution is
to use repSplitAppTy_maybe to break up the TyConApp into its pieces and
then continue. Easy to do, but also easy to forget to do.

Note [Comparing nullary type synonyms]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider the task of testing equality between two 'Type's of the form

  TyConApp tc []

where @tc@ is a type synonym. A naive way to perform this comparison these
would first expand the synonym and then compare the resulting expansions.

However, this is obviously wasteful and the RHS of @tc@ may be large; it is
much better to rather compare the TyCons directly. Consequently, before
expanding type synonyms in type comparisons we first look for a nullary
TyConApp and simply compare the TyCons if we find one. Of course, if we find
that the TyCons are *not* equal then we still need to perform the expansion as
their RHSs may still be equal.

We perform this optimisation in a number of places:

 * GHC.Core.Types.eqType
 * GHC.Core.Types.nonDetCmpType
 * GHC.Core.Unify.unify_ty
 * TcCanonical.can_eq_nc'
 * TcUnify.uType

This optimisation is especially helpful for the ubiquitous GHC.Types.Type,
since GHC prefers to use the type synonym over @TYPE 'LiftedRep@ applications
whenever possible. See Note [Using synonyms to compress types] in
GHC.Core.Type for details.

-}

eqType :: Type -> Type -> Bool
-- ^ Type equality on source types. Does not look through @newtypes@,
-- 'PredType's or type families, but it does look through type synonyms.
-- This first checks that the kinds of the types are equal and then
-- checks whether the types are equal, ignoring casts and coercions.
-- (The kind check is a recursive call, but since all kinds have type
-- @Type@, there is no need to check the types of kinds.)
-- See also Note [Non-trivial definitional equality] in "GHC.Core.TyCo.Rep".
eqType :: Type -> Type -> Bool
eqType Type
t1 Type
t2 = Ordering -> Bool
isEqual forall a b. (a -> b) -> a -> b
$ Type -> Type -> Ordering
nonDetCmpType Type
t1 Type
t2
  -- It's OK to use nonDetCmpType here and eqType is deterministic,
  -- nonDetCmpType does equality deterministically

-- | Compare types with respect to a (presumably) non-empty 'RnEnv2'.
eqTypeX :: RnEnv2 -> Type -> Type -> Bool
eqTypeX :: RnEnv2 -> Type -> Type -> Bool
eqTypeX RnEnv2
env Type
t1 Type
t2 = Ordering -> Bool
isEqual forall a b. (a -> b) -> a -> b
$ RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
env Type
t1 Type
t2
  -- It's OK to use nonDetCmpType here and eqTypeX is deterministic,
  -- nonDetCmpTypeX does equality deterministically

-- | Type equality on lists of types, looking through type synonyms
-- but not newtypes.
eqTypes :: [Type] -> [Type] -> Bool
eqTypes :: [Type] -> [Type] -> Bool
eqTypes [Type]
tys1 [Type]
tys2 = Ordering -> Bool
isEqual forall a b. (a -> b) -> a -> b
$ [Type] -> [Type] -> Ordering
nonDetCmpTypes [Type]
tys1 [Type]
tys2
  -- It's OK to use nonDetCmpType here and eqTypes is deterministic,
  -- nonDetCmpTypes does equality deterministically

eqVarBndrs :: RnEnv2 -> [Var] -> [Var] -> Maybe RnEnv2
-- Check that the var lists are the same length
-- and have matching kinds; if so, extend the RnEnv2
-- Returns Nothing if they don't match
eqVarBndrs :: RnEnv2 -> [TyVar] -> [TyVar] -> Maybe RnEnv2
eqVarBndrs RnEnv2
env [] []
 = forall a. a -> Maybe a
Just RnEnv2
env
eqVarBndrs RnEnv2
env (TyVar
tv1:[TyVar]
tvs1) (TyVar
tv2:[TyVar]
tvs2)
 | RnEnv2 -> Type -> Type -> Bool
eqTypeX RnEnv2
env (TyVar -> Type
varType TyVar
tv1) (TyVar -> Type
varType TyVar
tv2)
 = RnEnv2 -> [TyVar] -> [TyVar] -> Maybe RnEnv2
eqVarBndrs (RnEnv2 -> TyVar -> TyVar -> RnEnv2
rnBndr2 RnEnv2
env TyVar
tv1 TyVar
tv2) [TyVar]
tvs1 [TyVar]
tvs2
eqVarBndrs RnEnv2
_ [TyVar]
_ [TyVar]
_= forall a. Maybe a
Nothing

-- Now here comes the real worker

{-
Note [nonDetCmpType nondeterminism]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nonDetCmpType is implemented in terms of nonDetCmpTypeX. nonDetCmpTypeX
uses nonDetCmpTc which compares TyCons by their Unique value. Using Uniques for
ordering leads to nondeterminism. We hit the same problem in the TyVarTy case,
comparing type variables is nondeterministic, note the call to nonDetCmpVar in
nonDetCmpTypeX.
See Note [Unique Determinism] for more details.

Note [Type comparisons using object pointer comparisons]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Quite often we substitute the type from a definition site into
occurances without a change. This means for code like:
    \x -> (x,x,x)
The type of every `x` will often be represented by a single object
in the heap. We can take advantage of this by shortcutting the equality
check if two types are represented by the same pointer under the hood.
In some cases this reduces compiler allocations by ~2%.

Note [Computing equality on types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
There are several places within GHC that depend on the precise choice of
definitional equality used. If we change that definition, all these places
must be updated. This Note merely serves as a place for all these places
to refer to, so searching for references to this Note will find every place
that needs to be updated.

See also Note [Non-trivial definitional equality] in GHC.Core.TyCo.Rep.

-}

nonDetCmpType :: Type -> Type -> Ordering
nonDetCmpType :: Type -> Type -> Ordering
nonDetCmpType !Type
t1 !Type
t2
  -- See Note [Type comparisons using object pointer comparisons]
  | Int#
1# <- forall a. a -> a -> Int#
reallyUnsafePtrEquality# Type
t1 Type
t2
  = Ordering
EQ
nonDetCmpType (TyConApp TyCon
tc1 []) (TyConApp TyCon
tc2 []) | TyCon
tc1 forall a. Eq a => a -> a -> Bool
== TyCon
tc2
  = Ordering
EQ
nonDetCmpType Type
t1 Type
t2 =
  -- we know k1 and k2 have the same kind, because they both have kind *.
  RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
rn_env Type
t1 Type
t2
  where
    rn_env :: RnEnv2
rn_env = InScopeSet -> RnEnv2
mkRnEnv2 (TyCoVarSet -> InScopeSet
mkInScopeSet ([Type] -> TyCoVarSet
tyCoVarsOfTypes [Type
t1, Type
t2]))
{-# INLINE nonDetCmpType #-}

nonDetCmpTypes :: [Type] -> [Type] -> Ordering
nonDetCmpTypes :: [Type] -> [Type] -> Ordering
nonDetCmpTypes [Type]
ts1 [Type]
ts2 = RnEnv2 -> [Type] -> [Type] -> Ordering
nonDetCmpTypesX RnEnv2
rn_env [Type]
ts1 [Type]
ts2
  where
    rn_env :: RnEnv2
rn_env = InScopeSet -> RnEnv2
mkRnEnv2 (TyCoVarSet -> InScopeSet
mkInScopeSet ([Type] -> TyCoVarSet
tyCoVarsOfTypes ([Type]
ts1 forall a. [a] -> [a] -> [a]
++ [Type]
ts2)))

-- | An ordering relation between two 'Type's (known below as @t1 :: k1@
-- and @t2 :: k2@)
data TypeOrdering = TLT  -- ^ @t1 < t2@
                  | TEQ  -- ^ @t1 ~ t2@ and there are no casts in either,
                         -- therefore we can conclude @k1 ~ k2@
                  | TEQX -- ^ @t1 ~ t2@ yet one of the types contains a cast so
                         -- they may differ in kind.
                  | TGT  -- ^ @t1 > t2@
                  deriving (TypeOrdering -> TypeOrdering -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: TypeOrdering -> TypeOrdering -> Bool
$c/= :: TypeOrdering -> TypeOrdering -> Bool
== :: TypeOrdering -> TypeOrdering -> Bool
$c== :: TypeOrdering -> TypeOrdering -> Bool
Eq, Eq TypeOrdering
TypeOrdering -> TypeOrdering -> Bool
TypeOrdering -> TypeOrdering -> Ordering
TypeOrdering -> TypeOrdering -> TypeOrdering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: TypeOrdering -> TypeOrdering -> TypeOrdering
$cmin :: TypeOrdering -> TypeOrdering -> TypeOrdering
max :: TypeOrdering -> TypeOrdering -> TypeOrdering
$cmax :: TypeOrdering -> TypeOrdering -> TypeOrdering
>= :: TypeOrdering -> TypeOrdering -> Bool
$c>= :: TypeOrdering -> TypeOrdering -> Bool
> :: TypeOrdering -> TypeOrdering -> Bool
$c> :: TypeOrdering -> TypeOrdering -> Bool
<= :: TypeOrdering -> TypeOrdering -> Bool
$c<= :: TypeOrdering -> TypeOrdering -> Bool
< :: TypeOrdering -> TypeOrdering -> Bool
$c< :: TypeOrdering -> TypeOrdering -> Bool
compare :: TypeOrdering -> TypeOrdering -> Ordering
$ccompare :: TypeOrdering -> TypeOrdering -> Ordering
Ord, Int -> TypeOrdering
TypeOrdering -> Int
TypeOrdering -> [TypeOrdering]
TypeOrdering -> TypeOrdering
TypeOrdering -> TypeOrdering -> [TypeOrdering]
TypeOrdering -> TypeOrdering -> TypeOrdering -> [TypeOrdering]
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: TypeOrdering -> TypeOrdering -> TypeOrdering -> [TypeOrdering]
$cenumFromThenTo :: TypeOrdering -> TypeOrdering -> TypeOrdering -> [TypeOrdering]
enumFromTo :: TypeOrdering -> TypeOrdering -> [TypeOrdering]
$cenumFromTo :: TypeOrdering -> TypeOrdering -> [TypeOrdering]
enumFromThen :: TypeOrdering -> TypeOrdering -> [TypeOrdering]
$cenumFromThen :: TypeOrdering -> TypeOrdering -> [TypeOrdering]
enumFrom :: TypeOrdering -> [TypeOrdering]
$cenumFrom :: TypeOrdering -> [TypeOrdering]
fromEnum :: TypeOrdering -> Int
$cfromEnum :: TypeOrdering -> Int
toEnum :: Int -> TypeOrdering
$ctoEnum :: Int -> TypeOrdering
pred :: TypeOrdering -> TypeOrdering
$cpred :: TypeOrdering -> TypeOrdering
succ :: TypeOrdering -> TypeOrdering
$csucc :: TypeOrdering -> TypeOrdering
Enum, TypeOrdering
forall a. a -> a -> Bounded a
maxBound :: TypeOrdering
$cmaxBound :: TypeOrdering
minBound :: TypeOrdering
$cminBound :: TypeOrdering
Bounded)

nonDetCmpTypeX :: RnEnv2 -> Type -> Type -> Ordering  -- Main workhorse
    -- See Note [Non-trivial definitional equality] in GHC.Core.TyCo.Rep
    -- See Note [Computing equality on types]
nonDetCmpTypeX :: RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
env Type
orig_t1 Type
orig_t2 =
    case RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
orig_t1 Type
orig_t2 of
      -- If there are casts then we also need to do a comparison of the kinds of
      -- the types being compared
      TypeOrdering
TEQX          -> TypeOrdering -> Ordering
toOrdering forall a b. (a -> b) -> a -> b
$ RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
k1 Type
k2
      TypeOrdering
ty_ordering   -> TypeOrdering -> Ordering
toOrdering TypeOrdering
ty_ordering
  where
    k1 :: Type
k1 = HasDebugCallStack => Type -> Type
typeKind Type
orig_t1
    k2 :: Type
k2 = HasDebugCallStack => Type -> Type
typeKind Type
orig_t2

    toOrdering :: TypeOrdering -> Ordering
    toOrdering :: TypeOrdering -> Ordering
toOrdering TypeOrdering
TLT  = Ordering
LT
    toOrdering TypeOrdering
TEQ  = Ordering
EQ
    toOrdering TypeOrdering
TEQX = Ordering
EQ
    toOrdering TypeOrdering
TGT  = Ordering
GT

    liftOrdering :: Ordering -> TypeOrdering
    liftOrdering :: Ordering -> TypeOrdering
liftOrdering Ordering
LT = TypeOrdering
TLT
    liftOrdering Ordering
EQ = TypeOrdering
TEQ
    liftOrdering Ordering
GT = TypeOrdering
TGT

    thenCmpTy :: TypeOrdering -> TypeOrdering -> TypeOrdering
    thenCmpTy :: TypeOrdering -> TypeOrdering -> TypeOrdering
thenCmpTy TypeOrdering
TEQ  TypeOrdering
rel  = TypeOrdering
rel
    thenCmpTy TypeOrdering
TEQX TypeOrdering
rel  = TypeOrdering -> TypeOrdering
hasCast TypeOrdering
rel
    thenCmpTy TypeOrdering
rel  TypeOrdering
_    = TypeOrdering
rel

    hasCast :: TypeOrdering -> TypeOrdering
    hasCast :: TypeOrdering -> TypeOrdering
hasCast TypeOrdering
TEQ = TypeOrdering
TEQX
    hasCast TypeOrdering
rel = TypeOrdering
rel

    -- Returns both the resulting ordering relation between the two types
    -- and whether either contains a cast.
    go :: RnEnv2 -> Type -> Type -> TypeOrdering
    -- See Note [Comparing nullary type synonyms].
    go :: RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
_   (TyConApp TyCon
tc1 []) (TyConApp TyCon
tc2 [])
      | TyCon
tc1 forall a. Eq a => a -> a -> Bool
== TyCon
tc2
      = TypeOrdering
TEQ
    go RnEnv2
env Type
t1 Type
t2
      | Just Type
t1' <- Type -> Maybe Type
coreView Type
t1 = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1' Type
t2
      | Just Type
t2' <- Type -> Maybe Type
coreView Type
t2 = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1 Type
t2'

    go RnEnv2
env (TyVarTy TyVar
tv1)       (TyVarTy TyVar
tv2)
      = Ordering -> TypeOrdering
liftOrdering forall a b. (a -> b) -> a -> b
$ RnEnv2 -> TyVar -> TyVar
rnOccL RnEnv2
env TyVar
tv1 TyVar -> TyVar -> Ordering
`nonDetCmpVar` RnEnv2 -> TyVar -> TyVar
rnOccR RnEnv2
env TyVar
tv2
    go RnEnv2
env (ForAllTy (Bndr TyVar
tv1 ArgFlag
_) Type
t1) (ForAllTy (Bndr TyVar
tv2 ArgFlag
_) Type
t2)
      = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env (TyVar -> Type
varType TyVar
tv1) (TyVar -> Type
varType TyVar
tv2)
        TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> Type -> Type -> TypeOrdering
go (RnEnv2 -> TyVar -> TyVar -> RnEnv2
rnBndr2 RnEnv2
env TyVar
tv1 TyVar
tv2) Type
t1 Type
t2
        -- See Note [Equality on AppTys]
    go RnEnv2
env (AppTy Type
s1 Type
t1) Type
ty2
      | Just (Type
s2, Type
t2) <- HasDebugCallStack => Type -> Maybe (Type, Type)
repSplitAppTy_maybe Type
ty2
      = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
s1 Type
s2 TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1 Type
t2
    go RnEnv2
env Type
ty1 (AppTy Type
s2 Type
t2)
      | Just (Type
s1, Type
t1) <- HasDebugCallStack => Type -> Maybe (Type, Type)
repSplitAppTy_maybe Type
ty1
      = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
s1 Type
s2 TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1 Type
t2
    go RnEnv2
env (FunTy AnonArgFlag
_ Type
w1 Type
s1 Type
t1) (FunTy AnonArgFlag
_ Type
w2 Type
s2 Type
t2)
        -- NB: nonDepCmpTypeX does the kind check requested by
        -- Note [Equality on FunTys] in GHC.Core.TyCo.Rep
      = Ordering -> TypeOrdering
liftOrdering (RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
env Type
s1 Type
s2 forall a. Semigroup a => a -> a -> a
S.<> RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
env Type
t1 Type
t2)
          TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
w1 Type
w2
        -- Comparing multiplicities last because the test is usually true
    go RnEnv2
env (TyConApp TyCon
tc1 [Type]
tys1) (TyConApp TyCon
tc2 [Type]
tys2)
      = Ordering -> TypeOrdering
liftOrdering (TyCon
tc1 TyCon -> TyCon -> Ordering
`nonDetCmpTc` TyCon
tc2) TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> [Type] -> [Type] -> TypeOrdering
gos RnEnv2
env [Type]
tys1 [Type]
tys2
    go RnEnv2
_   (LitTy TyLit
l1)          (LitTy TyLit
l2)          = Ordering -> TypeOrdering
liftOrdering (TyLit -> TyLit -> Ordering
nonDetCmpTyLit TyLit
l1 TyLit
l2)
    go RnEnv2
env (CastTy Type
t1 KindCoercion
_)       Type
t2                  = TypeOrdering -> TypeOrdering
hasCast forall a b. (a -> b) -> a -> b
$ RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1 Type
t2
    go RnEnv2
env Type
t1                  (CastTy Type
t2 KindCoercion
_)       = TypeOrdering -> TypeOrdering
hasCast forall a b. (a -> b) -> a -> b
$ RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
t1 Type
t2

    go RnEnv2
_   (CoercionTy {})     (CoercionTy {})     = TypeOrdering
TEQ

        -- Deal with the rest: TyVarTy < CoercionTy < AppTy < LitTy < TyConApp < ForAllTy
    go RnEnv2
_ Type
ty1 Type
ty2
      = Ordering -> TypeOrdering
liftOrdering forall a b. (a -> b) -> a -> b
$ (Type -> Int
get_rank Type
ty1) forall a. Ord a => a -> a -> Ordering
`compare` (Type -> Int
get_rank Type
ty2)
      where get_rank :: Type -> Int
            get_rank :: Type -> Int
get_rank (CastTy {})
              = forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"nonDetCmpTypeX.get_rank" (forall a. Outputable a => a -> SDoc
ppr [Type
ty1,Type
ty2])
            get_rank (TyVarTy {})    = Int
0
            get_rank (CoercionTy {}) = Int
1
            get_rank (AppTy {})      = Int
3
            get_rank (LitTy {})      = Int
4
            get_rank (TyConApp {})   = Int
5
            get_rank (FunTy {})      = Int
6
            get_rank (ForAllTy {})   = Int
7

    gos :: RnEnv2 -> [Type] -> [Type] -> TypeOrdering
    gos :: RnEnv2 -> [Type] -> [Type] -> TypeOrdering
gos RnEnv2
_   []         []         = TypeOrdering
TEQ
    gos RnEnv2
_   []         [Type]
_          = TypeOrdering
TLT
    gos RnEnv2
_   [Type]
_          []         = TypeOrdering
TGT
    gos RnEnv2
env (Type
ty1:[Type]
tys1) (Type
ty2:[Type]
tys2) = RnEnv2 -> Type -> Type -> TypeOrdering
go RnEnv2
env Type
ty1 Type
ty2 TypeOrdering -> TypeOrdering -> TypeOrdering
`thenCmpTy` RnEnv2 -> [Type] -> [Type] -> TypeOrdering
gos RnEnv2
env [Type]
tys1 [Type]
tys2

-------------
nonDetCmpTypesX :: RnEnv2 -> [Type] -> [Type] -> Ordering
nonDetCmpTypesX :: RnEnv2 -> [Type] -> [Type] -> Ordering
nonDetCmpTypesX RnEnv2
_   []        []        = Ordering
EQ
nonDetCmpTypesX RnEnv2
env (Type
t1:[Type]
tys1) (Type
t2:[Type]
tys2) = RnEnv2 -> Type -> Type -> Ordering
nonDetCmpTypeX RnEnv2
env Type
t1 Type
t2 forall a. Semigroup a => a -> a -> a
S.<>
                                          RnEnv2 -> [Type] -> [Type] -> Ordering
nonDetCmpTypesX RnEnv2
env [Type]
tys1 [Type]
tys2
nonDetCmpTypesX RnEnv2
_   []        [Type]
_         = Ordering
LT
nonDetCmpTypesX RnEnv2
_   [Type]
_         []        = Ordering
GT

-------------
-- | Compare two 'TyCon's. NB: This should /never/ see 'Constraint' (as
-- recognized by Kind.isConstraintKindCon) which is considered a synonym for
-- 'Type' in Core.
-- See Note [Kind Constraint and kind Type] in "GHC.Core.Type".
-- See Note [nonDetCmpType nondeterminism]
nonDetCmpTc :: TyCon -> TyCon -> Ordering
nonDetCmpTc :: TyCon -> TyCon -> Ordering
nonDetCmpTc TyCon
tc1 TyCon
tc2
  = forall a. HasCallStack => Bool -> a -> a
assert (Bool -> Bool
not (TyCon -> Bool
isConstraintKindCon TyCon
tc1) Bool -> Bool -> Bool
&& Bool -> Bool
not (TyCon -> Bool
isConstraintKindCon TyCon
tc2)) forall a b. (a -> b) -> a -> b
$
    Unique
u1 Unique -> Unique -> Ordering
`nonDetCmpUnique` Unique
u2
  where
    u1 :: Unique
u1  = TyCon -> Unique
tyConUnique TyCon
tc1
    u2 :: Unique
u2  = TyCon -> Unique
tyConUnique TyCon
tc2

{-
************************************************************************
*                                                                      *
        The kind of a type
*                                                                      *
************************************************************************

Note [typeKind vs tcTypeKind]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We have two functions to get the kind of a type

  * typeKind   ignores  the distinction between Constraint and *
  * tcTypeKind respects the distinction between Constraint and *

tcTypeKind is used by the type inference engine, for which Constraint
and * are different; after that we use typeKind.

See also Note [coreView vs tcView]

Note [Kinding rules for types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In typeKind we consider Constraint and (TYPE LiftedRep) to be identical.
We then have

         t1 : TYPE rep1
         t2 : TYPE rep2
   (FUN) ----------------
         t1 -> t2 : Type

         ty : TYPE rep
         `a` is not free in rep
(FORALL) -----------------------
         forall a. ty : TYPE rep

In tcTypeKind we consider Constraint and (TYPE LiftedRep) to be distinct:

          t1 : TYPE rep1
          t2 : TYPE rep2
    (FUN) ----------------
          t1 -> t2 : Type

          t1 : Constraint
          t2 : TYPE rep
  (PRED1) ----------------
          t1 => t2 : Type

          t1 : Constraint
          t2 : Constraint
  (PRED2) ---------------------
          t1 => t2 : Constraint

          ty : TYPE rep
          `a` is not free in rep
(FORALL1) -----------------------
          forall a. ty : TYPE rep

          ty : Constraint
(FORALL2) -------------------------
          forall a. ty : Constraint

Note that:
* The only way we distinguish '->' from '=>' is by the fact
  that the argument is a PredTy.  Both are FunTys

Note [Phantom type variables in kinds]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider

  type K (r :: RuntimeRep) = Type   -- Note 'r' is unused
  data T r :: K r                   -- T :: forall r -> K r
  foo :: forall r. T r

The body of the forall in foo's type has kind (K r), and
normally it would make no sense to have
   forall r. (ty :: K r)
because the kind of the forall would escape the binding
of 'r'.  But in this case it's fine because (K r) expands
to Type, so we explicitly /permit/ the type
   forall r. T r

To accommodate such a type, in typeKind (forall a.ty) we use
occCheckExpand to expand any type synonyms in the kind of 'ty'
to eliminate 'a'.  See kinding rule (FORALL) in
Note [Kinding rules for types]

See also
 * GHC.Core.Type.occCheckExpand
 * GHC.Core.Utils.coreAltsType
 * GHC.Tc.Validity.checkEscapingKind
all of which grapple with the same problem.

See #14939.
-}

-----------------------------
typeKind :: HasDebugCallStack => Type -> Kind
-- No need to expand synonyms
typeKind :: HasDebugCallStack => Type -> Type
typeKind (TyConApp TyCon
tc [Type]
tys) = HasDebugCallStack => Type -> [Type] -> Type
piResultTys (TyCon -> Type
tyConKind TyCon
tc) [Type]
tys
typeKind (LitTy TyLit
l)         = TyLit -> Type
typeLiteralKind TyLit
l
typeKind (FunTy {})        = Type
liftedTypeKind
typeKind (TyVarTy TyVar
tyvar)   = TyVar -> Type
tyVarKind TyVar
tyvar
typeKind (CastTy Type
_ty KindCoercion
co)   = KindCoercion -> Type
coercionRKind KindCoercion
co
typeKind (CoercionTy KindCoercion
co)   = KindCoercion -> Type
coercionType KindCoercion
co

typeKind (AppTy Type
fun Type
arg)
  = Type -> [Type] -> Type
go Type
fun [Type
arg]
  where
    -- Accumulate the type arguments, so we can call piResultTys,
    -- rather than a succession of calls to piResultTy (which is
    -- asymptotically costly as the number of arguments increases)
    go :: Type -> [Type] -> Type
go (AppTy Type
fun Type
arg) [Type]
args = Type -> [Type] -> Type
go Type
fun (Type
argforall a. a -> [a] -> [a]
:[Type]
args)
    go Type
fun             [Type]
args = HasDebugCallStack => Type -> [Type] -> Type
piResultTys (HasDebugCallStack => Type -> Type
typeKind Type
fun) [Type]
args

typeKind ty :: Type
ty@(ForAllTy {})
  = case [TyVar] -> Type -> Maybe Type
occCheckExpand [TyVar]
tvs Type
body_kind of
      -- We must make sure tv does not occur in kind
      -- As it is already out of scope!
      -- See Note [Phantom type variables in kinds]
      Just Type
k' -> Type
k'
      Maybe Type
Nothing -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"typeKind"
                  (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [TyVar]
tvs SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr Type
body SDoc -> SDoc -> SDoc
<+> SDoc
dcolon SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr Type
body_kind)
  where
    ([TyVar]
tvs, Type
body) = Type -> ([TyVar], Type)
splitForAllTyVars Type
ty
    body_kind :: Type
body_kind   = HasDebugCallStack => Type -> Type
typeKind Type
body

---------------------------------------------
-- Utilities to be used in GHC.Core.Unify,
-- which uses "tc" functions
---------------------------------------------

tcTypeKind :: HasDebugCallStack => Type -> Kind
-- No need to expand synonyms
tcTypeKind :: HasDebugCallStack => Type -> Type
tcTypeKind (TyConApp TyCon
tc [Type]
tys) = HasDebugCallStack => Type -> [Type] -> Type
piResultTys (TyCon -> Type
tyConKind TyCon
tc) [Type]
tys
tcTypeKind (LitTy TyLit
l)         = TyLit -> Type
typeLiteralKind TyLit
l
tcTypeKind (TyVarTy TyVar
tyvar)   = TyVar -> Type
tyVarKind TyVar
tyvar
tcTypeKind (CastTy Type
_ty KindCoercion
co)   = KindCoercion -> Type
coercionRKind KindCoercion
co
tcTypeKind (CoercionTy KindCoercion
co)   = KindCoercion -> Type
coercionType KindCoercion
co

tcTypeKind (FunTy { ft_af :: Type -> AnonArgFlag
ft_af = AnonArgFlag
af, ft_res :: Type -> Type
ft_res = Type
res })
  | AnonArgFlag
InvisArg <- AnonArgFlag
af
  , Type -> Bool
tcIsConstraintKind (HasDebugCallStack => Type -> Type
tcTypeKind Type
res)
  = Type
constraintKind     -- Eq a => Ord a         :: Constraint
  | Bool
otherwise          -- Eq a => a -> a        :: TYPE LiftedRep
  = Type
liftedTypeKind     -- Eq a => Array# Int    :: TYPE LiftedRep (not TYPE PtrRep)

tcTypeKind (AppTy Type
fun Type
arg)
  = Type -> [Type] -> Type
go Type
fun [Type
arg]
  where
    -- Accumulate the type arguments, so we can call piResultTys,
    -- rather than a succession of calls to piResultTy (which is
    -- asymptotically costly as the number of arguments increases)
    go :: Type -> [Type] -> Type
go (AppTy Type
fun Type
arg) [Type]
args = Type -> [Type] -> Type
go Type
fun (Type
argforall a. a -> [a] -> [a]
:[Type]
args)
    go Type
fun             [Type]
args = HasDebugCallStack => Type -> [Type] -> Type
piResultTys (HasDebugCallStack => Type -> Type
tcTypeKind Type
fun) [Type]
args

tcTypeKind ty :: Type
ty@(ForAllTy {})
  | Type -> Bool
tcIsConstraintKind Type
body_kind
  = Type
constraintKind

  | Bool
otherwise
  = case [TyVar] -> Type -> Maybe Type
occCheckExpand [TyVar]
tvs Type
body_kind of
      -- We must make sure tv does not occur in kind
      -- As it is already out of scope!
      -- See Note [Phantom type variables in kinds]
      Just Type
k' -> Type
k'
      Maybe Type
Nothing -> forall a. HasCallStack => String -> SDoc -> a
pprPanic String
"tcTypeKind"
                  (forall a. Outputable a => a -> SDoc
ppr Type
ty SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr [TyVar]
tvs SDoc -> SDoc -> SDoc
$$ forall a. Outputable a => a -> SDoc
ppr Type
body SDoc -> SDoc -> SDoc
<+> SDoc
dcolon SDoc -> SDoc -> SDoc
<+> forall a. Outputable a => a -> SDoc
ppr Type
body_kind)
  where
    ([TyVar]
tvs, Type
body) = Type -> ([TyVar], Type)
splitForAllTyVars Type
ty
    body_kind :: Type
body_kind = HasDebugCallStack => Type -> Type
tcTypeKind Type
body


isPredTy :: HasDebugCallStack => Type -> Bool
-- See Note [Types for coercions, predicates, and evidence] in GHC.Core.TyCo.Rep
isPredTy :: HasDebugCallStack => Type -> Bool
isPredTy Type
ty = Type -> Bool
tcIsConstraintKind (HasDebugCallStack => Type -> Type
tcTypeKind Type
ty)

-- tcIsConstraintKind stuff only makes sense in the typechecker
-- After that Constraint = Type
-- See Note [coreView vs tcView]
-- Defined here because it is used in isPredTy and tcRepSplitAppTy_maybe (sigh)
tcIsConstraintKind :: Kind -> Bool
tcIsConstraintKind :: Type -> Bool
tcIsConstraintKind Type
ty
  | Just (TyCon
tc, [Type]
args) <- HasCallStack => Type -> Maybe (TyCon, [Type])
tcSplitTyConApp_maybe Type
ty    -- Note: tcSplit here
  , TyCon -> Bool
isConstraintKindCon TyCon
tc
  = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr (forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Type]
args) (forall a. Outputable a => a -> SDoc
ppr Type
ty) Bool
True

  | Bool
otherwise
  = Bool
False

-- | Like 'kindRep_maybe', but considers 'Constraint' to be distinct
-- from 'Type'. For a version that treats them as the same type, see
-- 'kindRep_maybe'.
tcKindRep_maybe :: HasDebugCallStack => Kind -> Maybe RuntimeRepType
tcKindRep_maybe :: HasDebugCallStack => Type -> Maybe Type
tcKindRep_maybe Type
kind
  | Just (TyCon
tc, [Type
arg]) <- HasCallStack => Type -> Maybe (TyCon, [Type])
tcSplitTyConApp_maybe Type
kind    -- Note: tcSplit here
  , TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
tYPETyConKey    = forall a. a -> Maybe a
Just Type
arg
  | Bool
otherwise                   = forall a. Maybe a
Nothing

-- | Is this kind equivalent to 'Type'?
--
-- This considers 'Constraint' to be distinct from 'Type'. For a version that
-- treats them as the same type, see 'isLiftedTypeKind'.
tcIsLiftedTypeKind :: Kind -> Bool
tcIsLiftedTypeKind :: Type -> Bool
tcIsLiftedTypeKind Type
kind
  = case HasDebugCallStack => Type -> Maybe Type
tcKindRep_maybe Type
kind of
      Just Type
rep -> Type -> Bool
isLiftedRuntimeRep Type
rep
      Maybe Type
Nothing  -> Bool
False

-- | Is this kind equivalent to @TYPE (BoxedRep l)@ for some @l :: Levity@?
--
-- This considers 'Constraint' to be distinct from 'Type'. For a version that
-- treats them as the same type, see 'isLiftedTypeKind'.
tcIsBoxedTypeKind :: Kind -> Bool
tcIsBoxedTypeKind :: Type -> Bool
tcIsBoxedTypeKind Type
kind
  = case HasDebugCallStack => Type -> Maybe Type
tcKindRep_maybe Type
kind of
      Just Type
rep -> Type -> Bool
isBoxedRuntimeRep Type
rep
      Maybe Type
Nothing  -> Bool
False

-- | Is this kind equivalent to @TYPE r@ (for some unknown r)?
--
-- This considers 'Constraint' to be distinct from @*@.
tcIsRuntimeTypeKind :: Kind -> Bool
tcIsRuntimeTypeKind :: Type -> Bool
tcIsRuntimeTypeKind Type
kind = forall a. Maybe a -> Bool
isJust (HasDebugCallStack => Type -> Maybe Type
tcKindRep_maybe Type
kind)

tcReturnsConstraintKind :: Kind -> Bool
-- True <=> the Kind ultimately returns a Constraint
--   E.g.  * -> Constraint
--         forall k. k -> Constraint
tcReturnsConstraintKind :: Type -> Bool
tcReturnsConstraintKind Type
kind
  | Just Type
kind' <- Type -> Maybe Type
tcView Type
kind = Type -> Bool
tcReturnsConstraintKind Type
kind'
tcReturnsConstraintKind (ForAllTy VarBndr TyVar ArgFlag
_ Type
ty)         = Type -> Bool
tcReturnsConstraintKind Type
ty
tcReturnsConstraintKind (FunTy { ft_res :: Type -> Type
ft_res = Type
ty }) = Type -> Bool
tcReturnsConstraintKind Type
ty
tcReturnsConstraintKind (TyConApp TyCon
tc [Type]
_)         = TyCon -> Bool
isConstraintKindCon TyCon
tc
tcReturnsConstraintKind Type
_                       = Bool
False

--------------------------
typeLiteralKind :: TyLit -> Kind
typeLiteralKind :: TyLit -> Type
typeLiteralKind (NumTyLit {}) = Type
naturalTy
typeLiteralKind (StrTyLit {}) = Type
typeSymbolKind
typeLiteralKind (CharTyLit {}) = Type
charTy

-- | Returns True if a type has a syntactically fixed runtime rep,
-- as per Note [Fixed RuntimeRep] in GHC.Tc.Utils.Concrete.
--
-- This function is equivalent to @('isFixedRuntimeRepKind' . 'typeKind')@,
-- but much faster.
--
-- __Precondition:__ The type has kind @('TYPE' blah)@
typeHasFixedRuntimeRep :: Type -> Bool
typeHasFixedRuntimeRep :: Type -> Bool
typeHasFixedRuntimeRep = Type -> Bool
go
  where
    go :: Type -> Bool
go (TyConApp TyCon
tc [Type]
_)
      | TyCon -> Bool
tcHasFixedRuntimeRep TyCon
tc = Bool
True
    go (FunTy {})               = Bool
True
    go (LitTy {})               = Bool
True
    go (ForAllTy VarBndr TyVar ArgFlag
_ Type
ty)          = Type -> Bool
go Type
ty
    go Type
ty                       = HasDebugCallStack => Type -> Bool
isFixedRuntimeRepKind (HasDebugCallStack => Type -> Type
typeKind Type
ty)

argsHaveFixedRuntimeRep :: Type -> Bool
-- ^ True if the argument types of this function type
-- all have a fixed-runtime-rep
argsHaveFixedRuntimeRep :: Type -> Bool
argsHaveFixedRuntimeRep Type
ty
  = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all TyCoBinder -> Bool
ok [TyCoBinder]
bndrs
  where
    ok :: TyCoBinder -> Bool
    ok :: TyCoBinder -> Bool
ok (Anon AnonArgFlag
_ Scaled Type
ty) = Type -> Bool
typeHasFixedRuntimeRep (forall a. Scaled a -> a
scaledThing Scaled Type
ty)
    ok TyCoBinder
_           = Bool
True

    bndrs :: [TyCoBinder]
    ([TyCoBinder]
bndrs, Type
_) = Type -> ([TyCoBinder], Type)
splitPiTys Type
ty

{- **********************************************************************
*                                                                       *
           Occurs check expansion
%*                                                                      *
%********************************************************************* -}

{- Note [Occurs check expansion]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(occurCheckExpand tv xi) expands synonyms in xi just enough to get rid
of occurrences of tv outside type function arguments, if that is
possible; otherwise, it returns Nothing.

For example, suppose we have
  type F a b = [a]
Then
  occCheckExpand b (F Int b) = Just [Int]
but
  occCheckExpand a (F a Int) = Nothing

We don't promise to do the absolute minimum amount of expanding
necessary, but we try not to do expansions we don't need to.  We
prefer doing inner expansions first.  For example,
  type F a b = (a, Int, a, [a])
  type G b   = Char
We have
  occCheckExpand b (F (G b)) = Just (F Char)
even though we could also expand F to get rid of b.

Note [Occurrence checking: look inside kinds]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose we are considering unifying
   (alpha :: *)  ~  Int -> (beta :: alpha -> alpha)
This may be an error (what is that alpha doing inside beta's kind?),
but we must not make the mistake of actually unifying or we'll
build an infinite data structure.  So when looking for occurrences
of alpha in the rhs, we must look in the kinds of type variables
that occur there.

occCheckExpand tries to expand type synonyms to remove
unnecessary occurrences of a variable, and thereby get past an
occurs-check failure.  This is good; but
     we can't do it in the /kind/ of a variable /occurrence/

For example #18451 built an infinite type:
    type Const a b = a
    data SameKind :: k -> k -> Type
    type T (k :: Const Type a) = forall (b :: k). SameKind a b

We have
  b :: k
  k :: Const Type a
  a :: k   (must be same as b)

So if we aren't careful, a's kind mentions a, which is bad.
And expanding an /occurrence/ of 'a' doesn't help, because the
/binding site/ is the master copy and all the occurrences should
match it.

Here's a related example:
   f :: forall a b (c :: Const Type b). Proxy '[a, c]

The list means that 'a' gets the same kind as 'c'; but that
kind mentions 'b', so the binders are out of order.

Bottom line: in occCheckExpand, do not expand inside the kinds
of occurrences.  See bad_var_occ in occCheckExpand.  And
see #18451 for more debate.
-}

occCheckExpand :: [Var] -> Type -> Maybe Type
-- See Note [Occurs check expansion]
-- We may have needed to do some type synonym unfolding in order to
-- get rid of the variable (or forall), so we also return the unfolded
-- version of the type, which is guaranteed to be syntactically free
-- of the given type variable.  If the type is already syntactically
-- free of the variable, then the same type is returned.
occCheckExpand :: [TyVar] -> Type -> Maybe Type
occCheckExpand [TyVar]
vs_to_avoid Type
ty
  | forall (t :: * -> *) a. Foldable t => t a -> Bool
null [TyVar]
vs_to_avoid  -- Efficient shortcut
  = forall a. a -> Maybe a
Just Type
ty           -- Can happen, eg. GHC.Core.Utils.mkSingleAltCase

  | Bool
otherwise
  = (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go ([TyVar] -> TyCoVarSet
mkVarSet [TyVar]
vs_to_avoid, forall a. VarEnv a
emptyVarEnv) Type
ty
  where
    go :: (VarSet, VarEnv TyCoVar) -> Type -> Maybe Type
          -- The VarSet is the set of variables we are trying to avoid
          -- The VarEnv carries mappings necessary
          -- because of kind expansion
    go :: (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet
as, VarEnv TyVar
env) ty :: Type
ty@(TyVarTy TyVar
tv)
      | Just TyVar
tv' <- forall a. VarEnv a -> TyVar -> Maybe a
lookupVarEnv VarEnv TyVar
env TyVar
tv = forall (m :: * -> *) a. Monad m => a -> m a
return (TyVar -> Type
mkTyVarTy TyVar
tv')
      | TyCoVarSet -> TyVar -> Bool
bad_var_occ TyCoVarSet
as TyVar
tv               = forall a. Maybe a
Nothing
      | Bool
otherwise                       = forall (m :: * -> *) a. Monad m => a -> m a
return Type
ty

    go (TyCoVarSet, VarEnv TyVar)
_   ty :: Type
ty@(LitTy {}) = forall (m :: * -> *) a. Monad m => a -> m a
return Type
ty
    go (TyCoVarSet, VarEnv TyVar)
cxt (AppTy Type
ty1 Type
ty2) = do { Type
ty1' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty1
                                ; Type
ty2' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty2
                                ; forall (m :: * -> *) a. Monad m => a -> m a
return (Type -> Type -> Type
mkAppTy Type
ty1' Type
ty2') }
    go (TyCoVarSet, VarEnv TyVar)
cxt ty :: Type
ty@(FunTy AnonArgFlag
_ Type
w Type
ty1 Type
ty2)
       = do { Type
w'   <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
w
            ; Type
ty1' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty1
            ; Type
ty2' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty2
            ; forall (m :: * -> *) a. Monad m => a -> m a
return (Type
ty { ft_mult :: Type
ft_mult = Type
w', ft_arg :: Type
ft_arg = Type
ty1', ft_res :: Type
ft_res = Type
ty2' }) }
    go cxt :: (TyCoVarSet, VarEnv TyVar)
cxt@(TyCoVarSet
as, VarEnv TyVar
env) (ForAllTy (Bndr TyVar
tv ArgFlag
vis) Type
body_ty)
       = do { Type
ki' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt (TyVar -> Type
varType TyVar
tv)
            ; let tv' :: TyVar
tv'  = TyVar -> Type -> TyVar
setVarType TyVar
tv Type
ki'
                  env' :: VarEnv TyVar
env' = forall a. VarEnv a -> TyVar -> a -> VarEnv a
extendVarEnv VarEnv TyVar
env TyVar
tv TyVar
tv'
                  as' :: TyCoVarSet
as'  = TyCoVarSet
as TyCoVarSet -> TyVar -> TyCoVarSet
`delVarSet` TyVar
tv
            ; Type
body' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet
as', VarEnv TyVar
env') Type
body_ty
            ; forall (m :: * -> *) a. Monad m => a -> m a
return (VarBndr TyVar ArgFlag -> Type -> Type
ForAllTy (forall var argf. var -> argf -> VarBndr var argf
Bndr TyVar
tv' ArgFlag
vis) Type
body') }

    -- For a type constructor application, first try expanding away the
    -- offending variable from the arguments.  If that doesn't work, next
    -- see if the type constructor is a type synonym, and if so, expand
    -- it and try again.
    go (TyCoVarSet, VarEnv TyVar)
cxt ty :: Type
ty@(TyConApp TyCon
tc [Type]
tys)
      = case forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ((TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt) [Type]
tys of
          Just [Type]
tys' -> forall (m :: * -> *) a. Monad m => a -> m a
return (TyCon -> [Type] -> Type
mkTyConApp TyCon
tc [Type]
tys')
          Maybe [Type]
Nothing | Just Type
ty' <- Type -> Maybe Type
tcView Type
ty -> (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty'
                  | Bool
otherwise             -> forall a. Maybe a
Nothing
                      -- Failing that, try to expand a synonym

    go (TyCoVarSet, VarEnv TyVar)
cxt (CastTy Type
ty KindCoercion
co) =  do { Type
ty' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty
                                ; KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                ; forall (m :: * -> *) a. Monad m => a -> m a
return (Type -> KindCoercion -> Type
mkCastTy Type
ty' KindCoercion
co') }
    go (TyCoVarSet, VarEnv TyVar)
cxt (CoercionTy KindCoercion
co) = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> Type
mkCoercionTy KindCoercion
co') }

    ------------------
    bad_var_occ :: VarSet -> Var -> Bool
    -- Works for TyVar and CoVar
    -- See Note [Occurrence checking: look inside kinds]
    bad_var_occ :: TyCoVarSet -> TyVar -> Bool
bad_var_occ TyCoVarSet
vs_to_avoid TyVar
v
       =  TyVar
v                          TyVar -> TyCoVarSet -> Bool
`elemVarSet`       TyCoVarSet
vs_to_avoid
       Bool -> Bool -> Bool
|| Type -> TyCoVarSet
tyCoVarsOfType (TyVar -> Type
varType TyVar
v) TyCoVarSet -> TyCoVarSet -> Bool
`intersectsVarSet` TyCoVarSet
vs_to_avoid

    ------------------
    go_mco :: (TyCoVarSet, VarEnv TyVar) -> MCoercionN -> Maybe MCoercionN
go_mco (TyCoVarSet, VarEnv TyVar)
_   MCoercionN
MRefl = forall (m :: * -> *) a. Monad m => a -> m a
return MCoercionN
MRefl
    go_mco (TyCoVarSet, VarEnv TyVar)
ctx (MCo KindCoercion
co) = KindCoercion -> MCoercionN
MCo forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
ctx KindCoercion
co

    ------------------
    go_co :: (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt (Refl Type
ty)                 = do { Type
ty' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (Type -> KindCoercion
mkNomReflCo Type
ty') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (GRefl Role
r Type
ty MCoercionN
mco)          = do { MCoercionN
mco' <- (TyCoVarSet, VarEnv TyVar) -> MCoercionN -> Maybe MCoercionN
go_mco (TyCoVarSet, VarEnv TyVar)
cxt MCoercionN
mco
                                             ; Type
ty' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (Role -> Type -> MCoercionN -> KindCoercion
mkGReflCo Role
r Type
ty' MCoercionN
mco') }
      -- Note: Coercions do not contain type synonyms
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (TyConAppCo Role
r TyCon
tc [KindCoercion]
args)    = do { [KindCoercion]
args' <- forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ((TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt) [KindCoercion]
args
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (HasDebugCallStack =>
Role -> TyCon -> [KindCoercion] -> KindCoercion
mkTyConAppCo Role
r TyCon
tc [KindCoercion]
args') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (AppCo KindCoercion
co KindCoercion
arg)            = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; KindCoercion
arg' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
arg
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> KindCoercion -> KindCoercion
mkAppCo KindCoercion
co' KindCoercion
arg') }
    go_co cxt :: (TyCoVarSet, VarEnv TyVar)
cxt@(TyCoVarSet
as, VarEnv TyVar
env) (ForAllCo TyVar
tv KindCoercion
kind_co KindCoercion
body_co)
      = do { KindCoercion
kind_co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
kind_co
           ; let tv' :: TyVar
tv' = TyVar -> Type -> TyVar
setVarType TyVar
tv forall a b. (a -> b) -> a -> b
$
                       KindCoercion -> Type
coercionLKind KindCoercion
kind_co'
                 env' :: VarEnv TyVar
env' = forall a. VarEnv a -> TyVar -> a -> VarEnv a
extendVarEnv VarEnv TyVar
env TyVar
tv TyVar
tv'
                 as' :: TyCoVarSet
as'  = TyCoVarSet
as TyCoVarSet -> TyVar -> TyCoVarSet
`delVarSet` TyVar
tv
           ; KindCoercion
body' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet
as', VarEnv TyVar
env') KindCoercion
body_co
           ; forall (m :: * -> *) a. Monad m => a -> m a
return (TyVar -> KindCoercion -> KindCoercion -> KindCoercion
ForAllCo TyVar
tv' KindCoercion
kind_co' KindCoercion
body') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (FunCo Role
r KindCoercion
w KindCoercion
co1 KindCoercion
co2)       = do { KindCoercion
co1' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co1
                                             ; KindCoercion
co2' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co2
                                             ; KindCoercion
w' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
w
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (Role
-> KindCoercion -> KindCoercion -> KindCoercion -> KindCoercion
mkFunCo Role
r KindCoercion
w' KindCoercion
co1' KindCoercion
co2') }
    go_co (TyCoVarSet
as,VarEnv TyVar
env) co :: KindCoercion
co@(CoVarCo TyVar
c)
      | Just TyVar
c' <- forall a. VarEnv a -> TyVar -> Maybe a
lookupVarEnv VarEnv TyVar
env TyVar
c   = forall (m :: * -> *) a. Monad m => a -> m a
return (TyVar -> KindCoercion
mkCoVarCo TyVar
c')
      | TyCoVarSet -> TyVar -> Bool
bad_var_occ TyCoVarSet
as TyVar
c                = forall a. Maybe a
Nothing
      | Bool
otherwise                       = forall (m :: * -> *) a. Monad m => a -> m a
return KindCoercion
co

    go_co (TyCoVarSet
as,VarEnv TyVar
_) co :: KindCoercion
co@(HoleCo CoercionHole
h)
      | TyCoVarSet -> TyVar -> Bool
bad_var_occ TyCoVarSet
as (CoercionHole -> TyVar
ch_co_var CoercionHole
h)    = forall a. Maybe a
Nothing
      | Bool
otherwise                       = forall (m :: * -> *) a. Monad m => a -> m a
return KindCoercion
co

    go_co (TyCoVarSet, VarEnv TyVar)
cxt (AxiomInstCo CoAxiom Branched
ax Int
ind [KindCoercion]
args) = do { [KindCoercion]
args' <- forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ((TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt) [KindCoercion]
args
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (CoAxiom Branched -> Int -> [KindCoercion] -> KindCoercion
mkAxiomInstCo CoAxiom Branched
ax Int
ind [KindCoercion]
args') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (UnivCo UnivCoProvenance
p Role
r Type
ty1 Type
ty2)      = do { UnivCoProvenance
p' <- (TyCoVarSet, VarEnv TyVar)
-> UnivCoProvenance -> Maybe UnivCoProvenance
go_prov (TyCoVarSet, VarEnv TyVar)
cxt UnivCoProvenance
p
                                             ; Type
ty1' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty1
                                             ; Type
ty2' <- (TyCoVarSet, VarEnv TyVar) -> Type -> Maybe Type
go (TyCoVarSet, VarEnv TyVar)
cxt Type
ty2
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (UnivCoProvenance -> Role -> Type -> Type -> KindCoercion
mkUnivCo UnivCoProvenance
p' Role
r Type
ty1' Type
ty2') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (SymCo KindCoercion
co)                = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> KindCoercion
mkSymCo KindCoercion
co') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (TransCo KindCoercion
co1 KindCoercion
co2)         = do { KindCoercion
co1' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co1
                                             ; KindCoercion
co2' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co2
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> KindCoercion -> KindCoercion
mkTransCo KindCoercion
co1' KindCoercion
co2') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (NthCo Role
r Int
n KindCoercion
co)            = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (HasDebugCallStack => Role -> Int -> KindCoercion -> KindCoercion
mkNthCo Role
r Int
n KindCoercion
co') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (LRCo LeftOrRight
lr KindCoercion
co)              = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (LeftOrRight -> KindCoercion -> KindCoercion
mkLRCo LeftOrRight
lr KindCoercion
co') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (InstCo KindCoercion
co KindCoercion
arg)           = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; KindCoercion
arg' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
arg
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> KindCoercion -> KindCoercion
mkInstCo KindCoercion
co' KindCoercion
arg') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (KindCo KindCoercion
co)               = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (KindCoercion -> KindCoercion
mkKindCo KindCoercion
co') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (SubCo KindCoercion
co)                = do { KindCoercion
co' <- (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (HasDebugCallStack => KindCoercion -> KindCoercion
mkSubCo KindCoercion
co') }
    go_co (TyCoVarSet, VarEnv TyVar)
cxt (AxiomRuleCo CoAxiomRule
ax [KindCoercion]
cs)       = do { [KindCoercion]
cs' <- forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM ((TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt) [KindCoercion]
cs
                                             ; forall (m :: * -> *) a. Monad m => a -> m a
return (CoAxiomRule -> [KindCoercion] -> KindCoercion
mkAxiomRuleCo CoAxiomRule
ax [KindCoercion]
cs') }

    ------------------
    go_prov :: (TyCoVarSet, VarEnv TyVar)
-> UnivCoProvenance -> Maybe UnivCoProvenance
go_prov (TyCoVarSet, VarEnv TyVar)
cxt (PhantomProv KindCoercion
co)    = KindCoercion -> UnivCoProvenance
PhantomProv forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
    go_prov (TyCoVarSet, VarEnv TyVar)
cxt (ProofIrrelProv KindCoercion
co) = KindCoercion -> UnivCoProvenance
ProofIrrelProv forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (TyCoVarSet, VarEnv TyVar) -> KindCoercion -> Maybe KindCoercion
go_co (TyCoVarSet, VarEnv TyVar)
cxt KindCoercion
co
    go_prov (TyCoVarSet, VarEnv TyVar)
_   p :: UnivCoProvenance
p@(PluginProv String
_)    = forall (m :: * -> *) a. Monad m => a -> m a
return UnivCoProvenance
p
    go_prov (TyCoVarSet, VarEnv TyVar)
_   p :: UnivCoProvenance
p@(CorePrepProv Bool
_)  = forall (m :: * -> *) a. Monad m => a -> m a
return UnivCoProvenance
p


{-
%************************************************************************
%*                                                                      *
        Miscellaneous functions
%*                                                                      *
%************************************************************************

-}
-- | All type constructors occurring in the type; looking through type
--   synonyms, but not newtypes.
--  When it finds a Class, it returns the class TyCon.
tyConsOfType :: Type -> UniqSet TyCon
tyConsOfType :: Type -> UniqSet TyCon
tyConsOfType Type
ty
  = Type -> UniqSet TyCon
go Type
ty
  where
     go :: Type -> UniqSet TyCon  -- The UniqSet does duplicate elim
     go :: Type -> UniqSet TyCon
go Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> UniqSet TyCon
go Type
ty'
     go (TyVarTy {})                = forall a. UniqSet a
emptyUniqSet
     go (LitTy {})                  = forall a. UniqSet a
emptyUniqSet
     go (TyConApp TyCon
tc [Type]
tys)           = forall {a}. Uniquable a => a -> UniqSet a
go_tc TyCon
tc forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` forall {t :: * -> *}. Foldable t => t Type -> UniqSet TyCon
go_s [Type]
tys
     go (AppTy Type
a Type
b)                 = Type -> UniqSet TyCon
go Type
a forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` Type -> UniqSet TyCon
go Type
b
     go (FunTy AnonArgFlag
_ Type
w Type
a Type
b)             = Type -> UniqSet TyCon
go Type
w forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets`
                                      Type -> UniqSet TyCon
go Type
a forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` Type -> UniqSet TyCon
go Type
b forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` forall {a}. Uniquable a => a -> UniqSet a
go_tc TyCon
funTyCon
     go (ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
ty)   = Type -> UniqSet TyCon
go Type
ty forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` Type -> UniqSet TyCon
go (TyVar -> Type
varType TyVar
tv)
     go (CastTy Type
ty KindCoercion
co)              = Type -> UniqSet TyCon
go Type
ty forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go (CoercionTy KindCoercion
co)             = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co

     go_co :: KindCoercion -> UniqSet TyCon
go_co (Refl Type
ty)               = Type -> UniqSet TyCon
go Type
ty
     go_co (GRefl Role
_ Type
ty MCoercionN
mco)        = Type -> UniqSet TyCon
go Type
ty forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` MCoercionN -> UniqSet TyCon
go_mco MCoercionN
mco
     go_co (TyConAppCo Role
_ TyCon
tc [KindCoercion]
args)  = forall {a}. Uniquable a => a -> UniqSet a
go_tc TyCon
tc forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` [KindCoercion] -> UniqSet TyCon
go_cos [KindCoercion]
args
     go_co (AppCo KindCoercion
co KindCoercion
arg)          = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
arg
     go_co (ForAllCo TyVar
_ KindCoercion
kind_co KindCoercion
co) = KindCoercion -> UniqSet TyCon
go_co KindCoercion
kind_co forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (FunCo Role
_ KindCoercion
co_mult KindCoercion
co1 KindCoercion
co2) = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co_mult forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
co1 forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
co2
     go_co (AxiomInstCo CoAxiom Branched
ax Int
_ [KindCoercion]
args) = forall {br :: BranchFlag}. CoAxiom br -> UniqSet TyCon
go_ax CoAxiom Branched
ax forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` [KindCoercion] -> UniqSet TyCon
go_cos [KindCoercion]
args
     go_co (UnivCo UnivCoProvenance
p Role
_ Type
t1 Type
t2)      = UnivCoProvenance -> UniqSet TyCon
go_prov UnivCoProvenance
p forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` Type -> UniqSet TyCon
go Type
t1 forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` Type -> UniqSet TyCon
go Type
t2
     go_co (CoVarCo {})            = forall a. UniqSet a
emptyUniqSet
     go_co (HoleCo {})             = forall a. UniqSet a
emptyUniqSet
     go_co (SymCo KindCoercion
co)              = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (TransCo KindCoercion
co1 KindCoercion
co2)       = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co1 forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
co2
     go_co (NthCo Role
_ Int
_ KindCoercion
co)          = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (LRCo LeftOrRight
_ KindCoercion
co)             = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (InstCo KindCoercion
co KindCoercion
arg)         = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co forall a. UniqSet a -> UniqSet a -> UniqSet a
`unionUniqSets` KindCoercion -> UniqSet TyCon
go_co KindCoercion
arg
     go_co (KindCo KindCoercion
co)             = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (SubCo KindCoercion
co)              = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_co (AxiomRuleCo CoAxiomRule
_ [KindCoercion]
cs)      = [KindCoercion] -> UniqSet TyCon
go_cos [KindCoercion]
cs

     go_mco :: MCoercionN -> UniqSet TyCon
go_mco MCoercionN
MRefl    = forall a. UniqSet a
emptyUniqSet
     go_mco (MCo KindCoercion
co) = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co

     go_prov :: UnivCoProvenance -> UniqSet TyCon
go_prov (PhantomProv KindCoercion
co)    = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_prov (ProofIrrelProv KindCoercion
co) = KindCoercion -> UniqSet TyCon
go_co KindCoercion
co
     go_prov (PluginProv String
_)      = forall a. UniqSet a
emptyUniqSet
     go_prov (CorePrepProv Bool
_)    = forall a. UniqSet a
emptyUniqSet
        -- this last case can happen from the tyConsOfType used from
        -- checkTauTvUpdate

     go_s :: t Type -> UniqSet TyCon
go_s t Type
tys     = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a. UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> UniqSet TyCon
go)     forall a. UniqSet a
emptyUniqSet t Type
tys
     go_cos :: [KindCoercion] -> UniqSet TyCon
go_cos [KindCoercion]
cos   = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a. UniqSet a -> UniqSet a -> UniqSet a
unionUniqSets forall b c a. (b -> c) -> (a -> b) -> a -> c
. KindCoercion -> UniqSet TyCon
go_co)  forall a. UniqSet a
emptyUniqSet [KindCoercion]
cos

     go_tc :: a -> UniqSet a
go_tc a
tc = forall {a}. Uniquable a => a -> UniqSet a
unitUniqSet a
tc
     go_ax :: CoAxiom br -> UniqSet TyCon
go_ax CoAxiom br
ax = forall {a}. Uniquable a => a -> UniqSet a
go_tc forall a b. (a -> b) -> a -> b
$ forall (br :: BranchFlag). CoAxiom br -> TyCon
coAxiomTyCon CoAxiom br
ax

-- | Retrieve the free variables in this type, splitting them based
-- on whether they are used visibly or invisibly. Invisible ones come
-- first.
splitVisVarsOfType :: Type -> Pair TyCoVarSet
splitVisVarsOfType :: Type -> Pair TyCoVarSet
splitVisVarsOfType Type
orig_ty = forall a. a -> a -> Pair a
Pair TyCoVarSet
invis_vars TyCoVarSet
vis_vars
  where
    Pair TyCoVarSet
invis_vars1 TyCoVarSet
vis_vars = Type -> Pair TyCoVarSet
go Type
orig_ty
    invis_vars :: TyCoVarSet
invis_vars = TyCoVarSet
invis_vars1 TyCoVarSet -> TyCoVarSet -> TyCoVarSet
`minusVarSet` TyCoVarSet
vis_vars

    go :: Type -> Pair TyCoVarSet
go (TyVarTy TyVar
tv)      = forall a. a -> a -> Pair a
Pair (Type -> TyCoVarSet
tyCoVarsOfType forall a b. (a -> b) -> a -> b
$ TyVar -> Type
tyVarKind TyVar
tv) (TyVar -> TyCoVarSet
unitVarSet TyVar
tv)
    go (AppTy Type
t1 Type
t2)     = Type -> Pair TyCoVarSet
go Type
t1 forall a. Monoid a => a -> a -> a
`mappend` Type -> Pair TyCoVarSet
go Type
t2
    go (TyConApp TyCon
tc [Type]
tys) = TyCon -> [Type] -> Pair TyCoVarSet
go_tc TyCon
tc [Type]
tys
    go (FunTy AnonArgFlag
_ Type
w Type
t1 Type
t2) = Type -> Pair TyCoVarSet
go Type
w forall a. Monoid a => a -> a -> a
`mappend` Type -> Pair TyCoVarSet
go Type
t1 forall a. Monoid a => a -> a -> a
`mappend` Type -> Pair TyCoVarSet
go Type
t2
    go (ForAllTy (Bndr TyVar
tv ArgFlag
_) Type
ty)
      = ((TyCoVarSet -> TyVar -> TyCoVarSet
`delVarSet` TyVar
tv) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Type -> Pair TyCoVarSet
go Type
ty) forall a. Monoid a => a -> a -> a
`mappend`
        (TyCoVarSet -> Pair TyCoVarSet
invisible (Type -> TyCoVarSet
tyCoVarsOfType forall a b. (a -> b) -> a -> b
$ TyVar -> Type
varType TyVar
tv))
    go (LitTy {}) = forall a. Monoid a => a
mempty
    go (CastTy Type
ty KindCoercion
co) = Type -> Pair TyCoVarSet
go Type
ty forall a. Monoid a => a -> a -> a
`mappend` TyCoVarSet -> Pair TyCoVarSet
invisible (KindCoercion -> TyCoVarSet
tyCoVarsOfCo KindCoercion
co)
    go (CoercionTy KindCoercion
co) = TyCoVarSet -> Pair TyCoVarSet
invisible forall a b. (a -> b) -> a -> b
$ KindCoercion -> TyCoVarSet
tyCoVarsOfCo KindCoercion
co

    invisible :: TyCoVarSet -> Pair TyCoVarSet
invisible TyCoVarSet
vs = forall a. a -> a -> Pair a
Pair TyCoVarSet
vs TyCoVarSet
emptyVarSet

    go_tc :: TyCon -> [Type] -> Pair TyCoVarSet
go_tc TyCon
tc [Type]
tys = let ([Type]
invis, [Type]
vis) = TyCon -> [Type] -> ([Type], [Type])
partitionInvisibleTypes TyCon
tc [Type]
tys in
                   TyCoVarSet -> Pair TyCoVarSet
invisible ([Type] -> TyCoVarSet
tyCoVarsOfTypes [Type]
invis) forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Type -> Pair TyCoVarSet
go [Type]
vis

splitVisVarsOfTypes :: [Type] -> Pair TyCoVarSet
splitVisVarsOfTypes :: [Type] -> Pair TyCoVarSet
splitVisVarsOfTypes = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Type -> Pair TyCoVarSet
splitVisVarsOfType

{-
************************************************************************
*                                                                      *
        Functions over Kinds
*                                                                      *
************************************************************************

Note [Kind Constraint and kind Type]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The kind Constraint is the kind of classes and other type constraints.
The special thing about types of kind Constraint is that
 * They are displayed with double arrow:
     f :: Ord a => a -> a
 * They are implicitly instantiated at call sites; so the type inference
   engine inserts an extra argument of type (Ord a) at every call site
   to f.

However, once type inference is over, there is *no* distinction between
Constraint and Type. Indeed we can have coercions between the two. Consider
   class C a where
     op :: a -> a
For this single-method class we may generate a newtype, which in turn
generates an axiom witnessing
    C a ~ (a -> a)
so on the left we have Constraint, and on the right we have Type.
See #7451.

Because we treat Constraint/Type differently during and after type inference,
GHC has two notions of equality that differ in whether they equate
Constraint/Type or not:

* GHC.Tc.Utils.TcType.tcEqType implements typechecker equality (see
  Note [Typechecker equality vs definitional equality] in GHC.Tc.Utils.TcType),
  which treats Constraint and Type as distinct. This is used during type
  inference. See #11715 for issues that arise from this.
* GHC.Core.TyCo.Rep.eqType implements definitional equality (see
  Note [Non-trivial definitional equality] in GHC.Core.TyCo.Rep), which treats
  Constraint and Type as equal. This is used after type inference.

Bottom line: although 'Type' and 'Constraint' are distinct TyCons, with
distinct uniques, they are treated as equal at all times except
during type inference.
-}

-- | Checks that a kind of the form 'Type', 'Constraint'
-- or @'TYPE r@ is concrete. See 'isConcrete'.
--
-- __Precondition:__ The type has kind @('TYPE' blah)@.
isFixedRuntimeRepKind :: HasDebugCallStack => Kind -> Bool
isFixedRuntimeRepKind :: HasDebugCallStack => Type -> Bool
isFixedRuntimeRepKind Type
k
  = forall a. HasCallStack => Bool -> SDoc -> a -> a
assertPpr (Type -> Bool
isLiftedTypeKind Type
k Bool -> Bool -> Bool
|| Bool
_is_type) (forall a. Outputable a => a -> SDoc
ppr Type
k) forall a b. (a -> b) -> a -> b
$
    -- the isLiftedTypeKind check is necessary b/c of Constraint
    Type -> Bool
isConcrete Type
k
  where
    _is_type :: Bool
_is_type = Type -> Bool
classifiesTypeWithValues Type
k

-- | Tests whether the given type is concrete, i.e. it
-- whether it consists only of concrete type constructors,
-- concrete type variables, and applications.
--
-- See Note [Concrete types] in GHC.Tc.Utils.Concrete.
isConcrete :: Type -> Bool
isConcrete :: Type -> Bool
isConcrete = Type -> Bool
go
  where
    go :: Type -> Bool
go Type
ty | Just Type
ty' <- Type -> Maybe Type
coreView Type
ty = Type -> Bool
go Type
ty'
    go (TyVarTy TyVar
tv)        = TyVar -> Bool
isConcreteTyVar TyVar
tv
    go (AppTy Type
ty1 Type
ty2)     = Type -> Bool
go Type
ty1 Bool -> Bool -> Bool
&& Type -> Bool
go Type
ty2
    go (TyConApp TyCon
tc [Type]
tys)
      | TyCon -> Bool
isConcreteTyCon TyCon
tc = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Type -> Bool
go [Type]
tys
      | Bool
otherwise          = Bool
False
    go ForAllTy{}          = Bool
False
    go (FunTy AnonArgFlag
_ Type
w Type
t1 Type
t2)   =  Type -> Bool
go Type
w
                           Bool -> Bool -> Bool
&& Type -> Bool
go (HasDebugCallStack => Type -> Type
typeKind Type
t1) Bool -> Bool -> Bool
&& Type -> Bool
go Type
t1
                           Bool -> Bool -> Bool
&& Type -> Bool
go (HasDebugCallStack => Type -> Type
typeKind Type
t2) Bool -> Bool -> Bool
&& Type -> Bool
go Type
t2
    go LitTy{}             = Bool
True
    go CastTy{}            = Bool
False
    go CoercionTy{}        = Bool
False

-----------------------------------------
-- | Does this classify a type allowed to have values? Responds True to things
-- like *, TYPE Lifted, TYPE IntRep, TYPE v, Constraint.
classifiesTypeWithValues :: Kind -> Bool
-- ^ True of any sub-kind of OpenTypeKind
classifiesTypeWithValues :: Type -> Bool
classifiesTypeWithValues Type
k = forall a. Maybe a -> Bool
isJust (HasDebugCallStack => Type -> Maybe Type
kindRep_maybe Type
k)

{-
%************************************************************************
%*                                                                      *
         Pretty-printing
%*                                                                      *
%************************************************************************

Most pretty-printing is either in GHC.Core.TyCo.Rep or GHC.Iface.Type.

-}

-- | Does a 'TyCon' (that is applied to some number of arguments) need to be
-- ascribed with an explicit kind signature to resolve ambiguity if rendered as
-- a source-syntax type?
-- (See @Note [When does a tycon application need an explicit kind signature?]@
-- for a full explanation of what this function checks for.)
tyConAppNeedsKindSig
  :: Bool  -- ^ Should specified binders count towards injective positions in
           --   the kind of the TyCon? (If you're using visible kind
           --   applications, then you want True here.
  -> TyCon
  -> Int   -- ^ The number of args the 'TyCon' is applied to.
  -> Bool  -- ^ Does @T t_1 ... t_n@ need a kind signature? (Where @n@ is the
           --   number of arguments)
tyConAppNeedsKindSig :: Bool -> TyCon -> Int -> Bool
tyConAppNeedsKindSig Bool
spec_inj_pos TyCon
tc Int
n_args
  | Ordering
LT <- forall a. [a] -> Int -> Ordering
listLengthCmp [TyConBinder]
tc_binders Int
n_args
  = Bool
False
  | Bool
otherwise
  = let ([TyConBinder]
dropped_binders, [TyConBinder]
remaining_binders)
          = forall a. Int -> [a] -> ([a], [a])
splitAt Int
n_args [TyConBinder]
tc_binders
        result_kind :: Type
result_kind  = [TyConBinder] -> Type -> Type
mkTyConKind [TyConBinder]
remaining_binders Type
tc_res_kind
        result_vars :: TyCoVarSet
result_vars  = Type -> TyCoVarSet
tyCoVarsOfType Type
result_kind
        dropped_vars :: TyCoVarSet
dropped_vars = FV -> TyCoVarSet
fvVarSet forall a b. (a -> b) -> a -> b
$
                       forall a. (a -> FV) -> [a] -> FV
mapUnionFV TyConBinder -> FV
injective_vars_of_binder [TyConBinder]
dropped_binders

    in Bool -> Bool
not (TyCoVarSet -> TyCoVarSet -> Bool
subVarSet TyCoVarSet
result_vars TyCoVarSet
dropped_vars)
  where
    tc_binders :: [TyConBinder]
tc_binders  = TyCon -> [TyConBinder]
tyConBinders TyCon
tc
    tc_res_kind :: Type
tc_res_kind = TyCon -> Type
tyConResKind TyCon
tc

    -- Returns the variables that would be fixed by knowing a TyConBinder. See
    -- Note [When does a tycon application need an explicit kind signature?]
    -- for a more detailed explanation of what this function does.
    injective_vars_of_binder :: TyConBinder -> FV
    injective_vars_of_binder :: TyConBinder -> FV
injective_vars_of_binder (Bndr TyVar
tv TyConBndrVis
vis) =
      case TyConBndrVis
vis of
        AnonTCB AnonArgFlag
VisArg -> Bool -> Type -> FV
injectiveVarsOfType Bool
False -- conservative choice
                                              (TyVar -> Type
varType TyVar
tv)
        NamedTCB ArgFlag
argf  | ArgFlag -> Bool
source_of_injectivity ArgFlag
argf
                       -> TyVar -> FV
unitFV TyVar
tv FV -> FV -> FV
`unionFV`
                          Bool -> Type -> FV
injectiveVarsOfType Bool
False (TyVar -> Type
varType TyVar
tv)
        TyConBndrVis
_              -> FV
emptyFV

    source_of_injectivity :: ArgFlag -> Bool
source_of_injectivity ArgFlag
Required  = Bool
True
    source_of_injectivity ArgFlag
Specified = Bool
spec_inj_pos
    source_of_injectivity ArgFlag
Inferred  = Bool
False

{-
Note [When does a tycon application need an explicit kind signature?]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
There are a couple of places in GHC where we convert Core Types into forms that
more closely resemble user-written syntax. These include:

1. Template Haskell Type reification (see, for instance, GHC.Tc.Gen.Splice.reify_tc_app)
2. Converting Types to LHsTypes (such as in Haddock.Convert in haddock)

This conversion presents a challenge: how do we ensure that the resulting type
has enough kind information so as not to be ambiguous? To better motivate this
question, consider the following Core type:

  -- Foo :: Type -> Type
  type Foo = Proxy Type

There is nothing ambiguous about the RHS of Foo in Core. But if we were to,
say, reify it into a TH Type, then it's tempting to just drop the invisible
Type argument and simply return `Proxy`. But now we've lost crucial kind
information: we don't know if we're dealing with `Proxy Type` or `Proxy Bool`
or `Proxy Int` or something else! We've inadvertently introduced ambiguity.

Unlike in other situations in GHC, we can't just turn on
-fprint-explicit-kinds, as we need to produce something which has the same
structure as a source-syntax type. Moreover, we can't rely on visible kind
application, since the first kind argument to Proxy is inferred, not specified.
Our solution is to annotate certain tycons with their kinds whenever they
appear in applied form in order to resolve the ambiguity. For instance, we
would reify the RHS of Foo like so:

  type Foo = (Proxy :: Type -> Type)

We need to devise an algorithm that determines precisely which tycons need
these explicit kind signatures. We certainly don't want to annotate _every_
tycon with a kind signature, or else we might end up with horribly bloated
types like the following:

  (Either :: Type -> Type -> Type) (Int :: Type) (Char :: Type)

We only want to annotate tycons that absolutely require kind signatures in
order to resolve some sort of ambiguity, and nothing more.

Suppose we have a tycon application (T ty_1 ... ty_n). Why might this type
require a kind signature? It might require it when we need to fill in any of
T's omitted arguments. By "omitted argument", we mean one that is dropped when
reifying ty_1 ... ty_n. Sometimes, the omitted arguments are inferred and
specified arguments (e.g., TH reification in GHC.Tc.Gen.Splice), and sometimes the
omitted arguments are only the inferred ones (e.g., in situations where
specified arguments are reified through visible kind application).
Regardless, the key idea is that _some_ arguments are going to be omitted after
reification, and the only mechanism we have at our disposal for filling them in
is through explicit kind signatures.

What do we mean by "fill in"? Let's consider this small example:

  T :: forall {k}. Type -> (k -> Type) -> k

Moreover, we have this application of T:

  T @{j} Int aty

When we reify this type, we omit the inferred argument @{j}. Is it fixed by the
other (non-inferred) arguments? Yes! If we know the kind of (aty :: blah), then
we'll generate an equality constraint (kappa -> Type) and, assuming we can
solve it, that will fix `kappa`. (Here, `kappa` is the unification variable
that we instantiate `k` with.)

Therefore, for any application of a tycon T to some arguments, the Question We
Must Answer is:

* Given the first n arguments of T, do the kinds of the non-omitted arguments
  fill in the omitted arguments?

(This is still a bit hand-wavy, but we'll refine this question incrementally
as we explain more of the machinery underlying this process.)

Answering this question is precisely the role that the `injectiveVarsOfType`
and `injective_vars_of_binder` functions exist to serve. If an omitted argument
`a` appears in the set returned by `injectiveVarsOfType ty`, then knowing
`ty` determines (i.e., fills in) `a`. (More on `injective_vars_of_binder` in a
bit.)

More formally, if
`a` is in `injectiveVarsOfType ty`
and  S1(ty) ~ S2(ty),
then S1(a)  ~ S2(a),
where S1 and S2 are arbitrary substitutions.

For example, is `F` is a non-injective type family, then

  injectiveVarsOfType(Either c (Maybe (a, F b c))) = {a, c}

Now that we know what this function does, here is a second attempt at the
Question We Must Answer:

* Given the first n arguments of T (ty_1 ... ty_n), consider the binders
  of T that are instantiated by non-omitted arguments. Do the injective
  variables of these binders fill in the remainder of T's kind?

Alright, we're getting closer. Next, we need to clarify what the injective
variables of a tycon binder are. This the role that the
`injective_vars_of_binder` function serves. Here is what this function does for
each form of tycon binder:

* Anonymous binders are injective positions. For example, in the promoted data
  constructor '(:):

    '(:) :: forall a. a -> [a] -> [a]

  The second and third tyvar binders (of kinds `a` and `[a]`) are both
  anonymous, so if we had '(:) 'True '[], then the kinds of 'True and
  '[] would contribute to the kind of '(:) 'True '[]. Therefore,
  injective_vars_of_binder(_ :: a) = injectiveVarsOfType(a) = {a}.
  (Similarly, injective_vars_of_binder(_ :: [a]) = {a}.)
* Named binders:
  - Inferred binders are never injective positions. For example, in this data
    type:

      data Proxy a
      Proxy :: forall {k}. k -> Type

    If we had Proxy 'True, then the kind of 'True would not contribute to the
    kind of Proxy 'True. Therefore,
    injective_vars_of_binder(forall {k}. ...) = {}.
  - Required binders are injective positions. For example, in this data type:

      data Wurble k (a :: k) :: k
      Wurble :: forall k -> k -> k

  The first tyvar binder (of kind `forall k`) has required visibility, so if
  we had Wurble (Maybe a) Nothing, then the kind of Maybe a would
  contribute to the kind of Wurble (Maybe a) Nothing. Hence,
  injective_vars_of_binder(forall a -> ...) = {a}.
  - Specified binders /might/ be injective positions, depending on how you
    approach things. Continuing the '(:) example:

      '(:) :: forall a. a -> [a] -> [a]

    Normally, the (forall a. ...) tyvar binder wouldn't contribute to the kind
    of '(:) 'True '[], since it's not explicitly instantiated by the user. But
    if visible kind application is enabled, then this is possible, since the
    user can write '(:) @Bool 'True '[]. (In that case,
    injective_vars_of_binder(forall a. ...) = {a}.)

    There are some situations where using visible kind application is appropriate
    and others where it is not (e.g., TH
    reification), so the `injective_vars_of_binder` function is parameterized by
    a Bool which decides if specified binders should be counted towards
    injective positions or not.

Now that we've defined injective_vars_of_binder, we can refine the Question We
Must Answer once more:

* Given the first n arguments of T (ty_1 ... ty_n), consider the binders
  of T that are instantiated by non-omitted arguments. For each such binder
  b_i, take the union of all injective_vars_of_binder(b_i). Is this set a
  superset of the free variables of the remainder of T's kind?

If the answer to this question is "no", then (T ty_1 ... ty_n) needs an
explicit kind signature, since T's kind has kind variables leftover that
aren't fixed by the non-omitted arguments.

One last sticking point: what does "the remainder of T's kind" mean? You might
be tempted to think that it corresponds to all of the arguments in the kind of
T that would normally be instantiated by omitted arguments. But this isn't
quite right, strictly speaking. Consider the following (silly) example:

  S :: forall {k}. Type -> Type

And suppose we have this application of S:

  S Int Bool

The Int argument would be omitted, and
injective_vars_of_binder(_ :: Type) = {}. This is not a superset of {k}, which
might suggest that (S Bool) needs an explicit kind signature. But
(S Bool :: Type) doesn't actually fix `k`! This is because the kind signature
only affects the /result/ of the application, not all of the individual
arguments. So adding a kind signature here won't make a difference. Therefore,
the fourth (and final) iteration of the Question We Must Answer is:

* Given the first n arguments of T (ty_1 ... ty_n), consider the binders
  of T that are instantiated by non-omitted arguments. For each such binder
  b_i, take the union of all injective_vars_of_binder(b_i). Is this set a
  superset of the free variables of the kind of (T ty_1 ... ty_n)?

Phew, that was a lot of work!

How can be sure that this is correct? That is, how can we be sure that in the
event that we leave off a kind annotation, that one could infer the kind of the
tycon application from its arguments? It's essentially a proof by induction: if
we can infer the kinds of every subtree of a type, then the whole tycon
application will have an inferrable kind--unless, of course, the remainder of
the tycon application's kind has uninstantiated kind variables.

What happens if T is oversaturated? That is, if T's kind has fewer than n
arguments, in the case that the concrete application instantiates a result
kind variable with an arrow kind? If we run out of arguments, we do not attach
a kind annotation. This should be a rare case, indeed. Here is an example:

   data T1 :: k1 -> k2 -> *
   data T2 :: k1 -> k2 -> *

   type family G (a :: k) :: k
   type instance G T1 = T2

   type instance F Char = (G T1 Bool :: (* -> *) -> *)   -- F from above

Here G's kind is (forall k. k -> k), and the desugared RHS of that last
instance of F is (G (* -> (* -> *) -> *) (T1 * (* -> *)) Bool). According to
the algorithm above, there are 3 arguments to G so we should peel off 3
arguments in G's kind. But G's kind has only two arguments. This is the
rare special case, and we choose not to annotate the application of G with
a kind signature. After all, we needn't do this, since that instance would
be reified as:

   type instance F Char = G (T1 :: * -> (* -> *) -> *) Bool

So the kind of G isn't ambiguous anymore due to the explicit kind annotation
on its argument. See #8953 and test th/T8953.
-}

{-
************************************************************************
*                                                                      *
        Multiplicities
*                                                                      *
************************************************************************

These functions would prefer to be in GHC.Core.Multiplicity, but
they some are used elsewhere in this module, and wanted to bring
their friends here with them.
-}

unrestricted, linear, tymult :: a -> Scaled a

-- | Scale a payload by Many
unrestricted :: forall a. a -> Scaled a
unrestricted = forall a. Type -> a -> Scaled a
Scaled Type
Many

-- | Scale a payload by One
linear :: forall a. a -> Scaled a
linear = forall a. Type -> a -> Scaled a
Scaled Type
One

-- | Scale a payload by Many; used for type arguments in core
tymult :: forall a. a -> Scaled a
tymult = forall a. Type -> a -> Scaled a
Scaled Type
Many

irrelevantMult :: Scaled a -> a
irrelevantMult :: forall a. Scaled a -> a
irrelevantMult = forall a. Scaled a -> a
scaledThing

mkScaled :: Mult -> a -> Scaled a
mkScaled :: forall a. Type -> a -> Scaled a
mkScaled = forall a. Type -> a -> Scaled a
Scaled

scaledSet :: Scaled a -> b -> Scaled b
scaledSet :: forall a b. Scaled a -> b -> Scaled b
scaledSet (Scaled Type
m a
_) b
b = forall a. Type -> a -> Scaled a
Scaled Type
m b
b

pattern One :: Mult
pattern $bOne :: Type
$mOne :: forall {r}. Type -> ((# #) -> r) -> ((# #) -> r) -> r
One <- (isOneDataConTy -> True)
  where One = Type
oneDataConTy

pattern Many :: Mult
pattern $bMany :: Type
$mMany :: forall {r}. Type -> ((# #) -> r) -> ((# #) -> r) -> r
Many <- (isManyDataConTy -> True)
  where Many = Type
manyDataConTy

isManyDataConTy :: Mult -> Bool
isManyDataConTy :: Type -> Bool
isManyDataConTy Type
ty
  | Just TyCon
tc <- Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty
  = TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
manyDataConKey
isManyDataConTy Type
_ = Bool
False

isOneDataConTy :: Mult -> Bool
isOneDataConTy :: Type -> Bool
isOneDataConTy Type
ty
  | Just TyCon
tc <- Type -> Maybe TyCon
tyConAppTyCon_maybe Type
ty
  = TyCon
tc forall a. Uniquable a => a -> Unique -> Bool
`hasKey` Unique
oneDataConKey
isOneDataConTy Type
_ = Bool
False

isLinearType :: Type -> Bool
-- ^ @isLinear t@ returns @True@ of a if @t@ is a type of (curried) function
-- where at least one argument is linear (or otherwise non-unrestricted). We use
-- this function to check whether it is safe to eta reduce an Id in CorePrep. It
-- is always safe to return 'True', because 'True' deactivates the optimisation.
isLinearType :: Type -> Bool
isLinearType Type
ty = case Type
ty of
                      FunTy AnonArgFlag
_ Type
Many Type
_ Type
res -> Type -> Bool
isLinearType Type
res
                      FunTy AnonArgFlag
_ Type
_ Type
_ Type
_ -> Bool
True
                      ForAllTy VarBndr TyVar ArgFlag
_ Type
res -> Type -> Bool
isLinearType Type
res
                      Type
_ -> Bool
False