    {-# LANGUAGE UndecidableInstances #-}

    -- |
    --
    -- This module contains facilities for replacing variable names in
    -- syntactic constructs.
    module Futhark.Transform.Substitute
      ( Substitutions,
        Substitute (..),
        Substitutable,
      )
    where

    import Control.Monad.Identity
    import Data.Map.Strict qualified as M
    import Futhark.Analysis.PrimExp
    import Futhark.IR.Prop.Names
    import Futhark.IR.Prop.Scope
    import Futhark.IR.Syntax
    import Futhark.IR.Traversals

    -- | The substitutions to be made are given by a mapping from names to
    -- names.
    type Substitutions = M.Map VName VName

    -- | A type that is an instance of this class supports substitution of
    -- any names contained within.
    class Substitute a where
      -- | @substituteNames m e@ replaces the variable names in @e@ with
      -- new names, based on the mapping in @m@.  It is assumed that all
      -- names in @e@ are unique, i.e. there is no shadowing.
      substituteNames :: M.Map VName VName -> a -> a

    instance (Substitute a) => Substitute [a] where
      substituteNames :: Map VName VName -> [a] -> [a]
    substituteNames Map VName VName
    substs = (a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map ((a -> a) -> [a] -> [a]) -> (a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> a -> a
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute (Stm rep)) => Substitute (Stms rep) where
      substituteNames :: Map VName VName -> Stms rep -> Stms rep
    substituteNames Map VName VName
    substs = (Stm rep -> Stm rep) -> Stms rep -> Stms rep
    forall a b. (a -> b) -> Seq a -> Seq b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((Stm rep -> Stm rep) -> Stms rep -> Stms rep)
    -> (Stm rep -> Stm rep) -> Stms rep -> Stms rep
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> Stm rep -> Stm rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute a, Substitute b) => Substitute (a, b) where
      substituteNames :: Map VName VName -> (a, b) -> (a, b)
    substituteNames Map VName VName
    substs (a
    x, b
    y) =
        (Map VName VName -> a -> a
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs a
    x, Map VName VName -> b -> b
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs b
    y)

    instance (Substitute a, Substitute b, Substitute c) => Substitute (a, b, c) where
      substituteNames :: Map VName VName -> (a, b, c) -> (a, b, c)
    substituteNames Map VName VName
    substs (a
    x, b
    y, c
    z) =
        ( Map VName VName -> a -> a
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs a
    x,
          Map VName VName -> b -> b
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs b
    y,
          Map VName VName -> c -> c
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs c
    z
        )

    instance (Substitute a, Substitute b, Substitute c, Substitute d) => Substitute (a, b, c, d) where
      substituteNames :: Map VName VName -> (a, b, c, d) -> (a, b, c, d)
    substituteNames Map VName VName
    substs (a
    x, b
    y, c
    z, d
    u) =
        ( Map VName VName -> a -> a
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs a
    x,
          Map VName VName -> b -> b
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs b
    y,
          Map VName VName -> c -> c
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs c
    z,
          Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs d
    u
        )

    instance (Substitute a) => Substitute (Maybe a) where
      substituteNames :: Map VName VName -> Maybe a -> Maybe a
    substituteNames Map VName VName
    substs = (a -> a) -> Maybe a -> Maybe a
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((a -> a) -> Maybe a -> Maybe a) -> (a -> a) -> Maybe a -> Maybe a
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> a -> a
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance Substitute Bool where
      substituteNames :: Map VName VName -> Bool -> Bool
    substituteNames = (Bool -> Bool) -> Map VName VName -> Bool -> Bool
    forall a b. a -> b -> a
    const Bool -> Bool
    forall a. a -> a
    id

    instance Substitute VName where
      substituteNames :: Map VName VName -> VName -> VName
    substituteNames Map VName VName
    substs VName
    k = VName -> VName -> Map VName VName -> VName
    forall k a. Ord k => a -> k -> Map k a -> a
    M.findWithDefault VName
    k VName
    k Map VName VName
    substs

    instance Substitute SubExp where
      substituteNames :: Map VName VName -> SubExp -> SubExp
    substituteNames Map VName VName
    substs (Var VName
    v) = VName -> SubExp
    Var (VName -> SubExp) -> VName -> SubExp
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs VName
    v
      substituteNames Map VName VName
    _ (Constant PrimValue
    v) = PrimValue -> SubExp
    Constant PrimValue
    v

    instance (Substitutable rep) => Substitute (Exp rep) where
      substituteNames :: Map VName VName -> Exp rep -> Exp rep
    substituteNames Map VName VName
    substs = Mapper rep rep Identity -> Exp rep -> Exp rep
    forall frep trep. Mapper frep trep Identity -> Exp frep -> Exp trep
    mapExp (Mapper rep rep Identity -> Exp rep -> Exp rep)
    -> Mapper rep rep Identity -> Exp rep -> Exp rep
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> Mapper rep rep Identity
    forall rep.
    Substitutable rep =>
    Map VName VName -> Mapper rep rep Identity
    replace Map VName VName
    substs

    instance (Substitute dec) => Substitute (PatElem dec) where
      substituteNames :: Map VName VName -> PatElem dec -> PatElem dec
    substituteNames Map VName VName
    substs (PatElem VName
    ident dec
    dec) =
        VName -> dec -> PatElem dec
    forall dec. VName -> dec -> PatElem dec
    PatElem (Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs VName
    ident) (Map VName VName -> dec -> dec
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs dec
    dec)

    instance Substitute Attrs where
      substituteNames :: Map VName VName -> Attrs -> Attrs
    substituteNames Map VName VName
    _ Attrs
    attrs = Attrs
    attrs

    instance (Substitute dec) => Substitute (StmAux dec) where
      substituteNames :: Map VName VName -> StmAux dec -> StmAux dec
    substituteNames Map VName VName
    substs (StmAux Certs
    cs Attrs
    attrs Provenance
    loc dec
    dec) =
        Certs -> Attrs -> Provenance -> dec -> StmAux dec
    forall dec. Certs -> Attrs -> Provenance -> dec -> StmAux dec
    StmAux
          (Map VName VName -> Certs -> Certs
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Certs
    cs)
          (Map VName VName -> Attrs -> Attrs
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Attrs
    attrs)
          Provenance
    loc
          (Map VName VName -> dec -> dec
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs dec
    dec)

    instance (Substitute dec) => Substitute (Param dec) where
      substituteNames :: Map VName VName -> Param dec -> Param dec
    substituteNames Map VName VName
    substs (Param Attrs
    attrs VName
    name dec
    dec) =
        Attrs -> VName -> dec -> Param dec
    forall dec. Attrs -> VName -> dec -> Param dec
    Param
          (Map VName VName -> Attrs -> Attrs
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Attrs
    attrs)
          (Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs VName
    name)
          (Map VName VName -> dec -> dec
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs dec
    dec)

    instance Substitute SubExpRes where
      substituteNames :: Map VName VName -> SubExpRes -> SubExpRes
    substituteNames Map VName VName
    substs (SubExpRes Certs
    cs SubExp
    se) =
        Certs -> SubExp -> SubExpRes
    SubExpRes (Map VName VName -> Certs -> Certs
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Certs
    cs) (Map VName VName -> SubExp -> SubExp
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs SubExp
    se)

    instance (Substitute dec) => Substitute (Pat dec) where
      substituteNames :: Map VName VName -> Pat dec -> Pat dec
    substituteNames Map VName VName
    substs (Pat [PatElem dec]
    xs) =
        [PatElem dec] -> Pat dec
    forall dec. [PatElem dec] -> Pat dec
    Pat (Map VName VName -> [PatElem dec] -> [PatElem dec]
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs [PatElem dec]
    xs)

    instance Substitute Certs where
      substituteNames :: Map VName VName -> Certs -> Certs
    substituteNames Map VName VName
    substs (Certs [VName]
    cs) =
        [VName] -> Certs
    Certs ([VName] -> Certs) -> [VName] -> Certs
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> [VName] -> [VName]
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs [VName]
    cs

    instance (Substitutable rep) => Substitute (Stm rep) where
      substituteNames :: Map VName VName -> Stm rep -> Stm rep
    substituteNames Map VName VName
    substs (Let Pat (LetDec rep)
    pat StmAux (ExpDec rep)
    annot Exp rep
    e) =
        Pat (LetDec rep) -> StmAux (ExpDec rep) -> Exp rep -> Stm rep
    forall rep.
    Pat (LetDec rep) -> StmAux (ExpDec rep) -> Exp rep -> Stm rep
    Let
          (Map VName VName -> Pat (LetDec rep) -> Pat (LetDec rep)
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Pat (LetDec rep)
    pat)
          (Map VName VName -> StmAux (ExpDec rep) -> StmAux (ExpDec rep)
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs StmAux (ExpDec rep)
    annot)
          (Map VName VName -> Exp rep -> Exp rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Exp rep
    e)

    instance (Substitutable rep) => Substitute (Body rep) where
      substituteNames :: Map VName VName -> Body rep -> Body rep
    substituteNames Map VName VName
    substs (Body BodyDec rep
    dec Stms rep
    stms Result
    res) =
        BodyDec rep -> Stms rep -> Result -> Body rep
    forall rep. BodyDec rep -> Stms rep -> Result -> Body rep
    Body
          (Map VName VName -> BodyDec rep -> BodyDec rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs BodyDec rep
    dec)
          (Map VName VName -> Stms rep -> Stms rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Stms rep
    stms)
          (Map VName VName -> Result -> Result
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Result
    res)

    replace :: (Substitutable rep) => M.Map VName VName -> Mapper rep rep Identity
    replace :: forall rep.
    Substitutable rep =>
    Map VName VName -> Mapper rep rep Identity
    replace Map VName VName
    substs =
      Mapper
        { mapOnVName :: VName -> Identity VName
    mapOnVName = VName -> Identity VName
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (VName -> Identity VName)
    -> (VName -> VName) -> VName -> Identity VName
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnSubExp :: SubExp -> Identity SubExp
    mapOnSubExp = SubExp -> Identity SubExp
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (SubExp -> Identity SubExp)
    -> (SubExp -> SubExp) -> SubExp -> Identity SubExp
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> SubExp -> SubExp
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnBody :: Scope rep -> Body rep -> Identity (Body rep)
    mapOnBody = (Body rep -> Identity (Body rep))
    -> Scope rep -> Body rep -> Identity (Body rep)
    forall a b. a -> b -> a
    const ((Body rep -> Identity (Body rep))
     -> Scope rep -> Body rep -> Identity (Body rep))
    -> (Body rep -> Identity (Body rep))
    -> Scope rep
    -> Body rep
    -> Identity (Body rep)
    forall a b. (a -> b) -> a -> b
    $ Body rep -> Identity (Body rep)
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Body rep -> Identity (Body rep))
    -> (Body rep -> Body rep) -> Body rep -> Identity (Body rep)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> Body rep -> Body rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnRetType :: RetType rep -> Identity (RetType rep)
    mapOnRetType = RetType rep -> Identity (RetType rep)
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (RetType rep -> Identity (RetType rep))
    -> (RetType rep -> RetType rep)
    -> RetType rep
    -> Identity (RetType rep)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> RetType rep -> RetType rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnBranchType :: BranchType rep -> Identity (BranchType rep)
    mapOnBranchType = BranchType rep -> Identity (BranchType rep)
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (BranchType rep -> Identity (BranchType rep))
    -> (BranchType rep -> BranchType rep)
    -> BranchType rep
    -> Identity (BranchType rep)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> BranchType rep -> BranchType rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnFParam :: Param (FParamInfo rep) -> Identity (Param (FParamInfo rep))
    mapOnFParam = Param (FParamInfo rep) -> Identity (Param (FParamInfo rep))
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Param (FParamInfo rep) -> Identity (Param (FParamInfo rep)))
    -> (Param (FParamInfo rep) -> Param (FParamInfo rep))
    -> Param (FParamInfo rep)
    -> Identity (Param (FParamInfo rep))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> Param (FParamInfo rep) -> Param (FParamInfo rep)
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnLParam :: Param (LParamInfo rep) -> Identity (Param (LParamInfo rep))
    mapOnLParam = Param (LParamInfo rep) -> Identity (Param (LParamInfo rep))
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Param (LParamInfo rep) -> Identity (Param (LParamInfo rep)))
    -> (Param (LParamInfo rep) -> Param (LParamInfo rep))
    -> Param (LParamInfo rep)
    -> Identity (Param (LParamInfo rep))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> Param (LParamInfo rep) -> Param (LParamInfo rep)
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs,
          mapOnOp :: OpC rep rep -> Identity (OpC rep rep)
    mapOnOp = OpC rep rep -> Identity (OpC rep rep)
    forall a. a -> Identity a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (OpC rep rep -> Identity (OpC rep rep))
    -> (OpC rep rep -> OpC rep rep)
    -> OpC rep rep
    -> Identity (OpC rep rep)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> OpC rep rep -> OpC rep rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs
        }

    instance Substitute Rank where
      substituteNames :: Map VName VName -> Rank -> Rank
    substituteNames Map VName VName
    _ = Rank -> Rank
    forall a. a -> a
    id

    instance Substitute () where
      substituteNames :: Map VName VName -> () -> ()
    substituteNames Map VName VName
    _ = () -> ()
    forall a. a -> a
    id

    instance Substitute (NoOp rep) where
      substituteNames :: Map VName VName -> NoOp rep -> NoOp rep
    substituteNames Map VName VName
    _ = NoOp rep -> NoOp rep
    forall a. a -> a
    id

    instance (Substitute d) => Substitute (ShapeBase d) where
      substituteNames :: Map VName VName -> ShapeBase d -> ShapeBase d
    substituteNames Map VName VName
    substs = (d -> d) -> ShapeBase d -> ShapeBase d
    forall a b. (a -> b) -> ShapeBase a -> ShapeBase b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs)

    instance (Substitute d) => Substitute (NewShape d) where
      substituteNames :: Map VName VName -> NewShape d -> NewShape d
    substituteNames Map VName VName
    substs = (d -> d) -> NewShape d -> NewShape d
    forall a b. (a -> b) -> NewShape a -> NewShape b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs)

    instance (Substitute d) => Substitute (Ext d) where
      substituteNames :: Map VName VName -> Ext d -> Ext d
    substituteNames Map VName VName
    substs (Free d
    x) = d -> Ext d
    forall a. a -> Ext a
    Free (d -> Ext d) -> d -> Ext d
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs d
    x
      substituteNames Map VName VName
    _ (Ext Int
    x) = Int -> Ext d
    forall a. Int -> Ext a
    Ext Int
    x

    instance Substitute Names where
      substituteNames :: Map VName VName -> Names -> Names
    substituteNames = (VName -> VName) -> Names -> Names
    mapNames ((VName -> VName) -> Names -> Names)
    -> (Map VName VName -> VName -> VName)
    -> Map VName VName
    -> Names
    -> Names
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames

    instance Substitute PrimType where
      substituteNames :: Map VName VName -> PrimType -> PrimType
    substituteNames Map VName VName
    _ PrimType
    t = PrimType
    t

    instance (Substitute shape) => Substitute (TypeBase shape u) where
      substituteNames :: Map VName VName -> TypeBase shape u -> TypeBase shape u
    substituteNames Map VName VName
    _ (Prim PrimType
    et) =
        PrimType -> TypeBase shape u
    forall shape u. PrimType -> TypeBase shape u
    Prim PrimType
    et
      substituteNames Map VName VName
    substs (Acc VName
    acc Shape
    ispace [Type]
    ts u
    u) =
        VName -> Shape -> [Type] -> u -> TypeBase shape u
    forall shape u. VName -> Shape -> [Type] -> u -> TypeBase shape u
    Acc
          (Map VName VName -> VName -> VName
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs VName
    acc)
          (Map VName VName -> Shape -> Shape
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Shape
    ispace)
          (Map VName VName -> [Type] -> [Type]
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs [Type]
    ts)
          u
    u
      substituteNames Map VName VName
    substs (Array PrimType
    et shape
    sz u
    u) =
        PrimType -> shape -> u -> TypeBase shape u
    forall shape u. PrimType -> shape -> u -> TypeBase shape u
    Array (Map VName VName -> PrimType -> PrimType
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs PrimType
    et) (Map VName VName -> shape -> shape
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs shape
    sz) u
    u
      substituteNames Map VName VName
    _ (Mem Space
    space) =
        Space -> TypeBase shape u
    forall shape u. Space -> TypeBase shape u
    Mem Space
    space

    instance (Substitutable rep) => Substitute (Lambda rep) where
      substituteNames :: Map VName VName -> Lambda rep -> Lambda rep
    substituteNames Map VName VName
    substs (Lambda [Param (LParamInfo rep)]
    params [Type]
    rettype Body rep
    body) =
        [Param (LParamInfo rep)] -> [Type] -> Body rep -> Lambda rep
    forall rep. [LParam rep] -> [Type] -> Body rep -> Lambda rep
    Lambda
          (Map VName VName
    -> [Param (LParamInfo rep)] -> [Param (LParamInfo rep)]
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs [Param (LParamInfo rep)]
    params)
          ((Type -> Type) -> [Type] -> [Type]
    forall a b. (a -> b) -> [a] -> [b]
    map (Map VName VName -> Type -> Type
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs) [Type]
    rettype)
          (Map VName VName -> Body rep -> Body rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs Body rep
    body)

    instance Substitute Ident where
      substituteNames :: Map VName VName -> Ident -> Ident
    substituteNames Map VName VName
    substs Ident
    v =
        Ident
    v
          { identName = substituteNames substs $ identName v,
            identType = substituteNames substs $ identType v
          }

    instance (Substitute d) => Substitute (DimIndex d) where
      substituteNames :: Map VName VName -> DimIndex d -> DimIndex d
    substituteNames Map VName VName
    substs = (d -> d) -> DimIndex d -> DimIndex d
    forall a b. (a -> b) -> DimIndex a -> DimIndex b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((d -> d) -> DimIndex d -> DimIndex d)
    -> (d -> d) -> DimIndex d -> DimIndex d
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute d) => Substitute (Slice d) where
      substituteNames :: Map VName VName -> Slice d -> Slice d
    substituteNames Map VName VName
    substs = (d -> d) -> Slice d -> Slice d
    forall a b. (a -> b) -> Slice a -> Slice b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((d -> d) -> Slice d -> Slice d) -> (d -> d) -> Slice d -> Slice d
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute d) => Substitute (FlatDimIndex d) where
      substituteNames :: Map VName VName -> FlatDimIndex d -> FlatDimIndex d
    substituteNames Map VName VName
    substs = (d -> d) -> FlatDimIndex d -> FlatDimIndex d
    forall a b. (a -> b) -> FlatDimIndex a -> FlatDimIndex b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((d -> d) -> FlatDimIndex d -> FlatDimIndex d)
    -> (d -> d) -> FlatDimIndex d -> FlatDimIndex d
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute d) => Substitute (FlatSlice d) where
      substituteNames :: Map VName VName -> FlatSlice d -> FlatSlice d
    substituteNames Map VName VName
    substs = (d -> d) -> FlatSlice d -> FlatSlice d
    forall a b. (a -> b) -> FlatSlice a -> FlatSlice b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((d -> d) -> FlatSlice d -> FlatSlice d)
    -> (d -> d) -> FlatSlice d -> FlatSlice d
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> d -> d
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute v) => Substitute (PrimExp v) where
      substituteNames :: Map VName VName -> PrimExp v -> PrimExp v
    substituteNames Map VName VName
    substs = (v -> v) -> PrimExp v -> PrimExp v
    forall a b. (a -> b) -> PrimExp a -> PrimExp b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((v -> v) -> PrimExp v -> PrimExp v)
    -> (v -> v) -> PrimExp v -> PrimExp v
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> v -> v
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs

    instance (Substitute v) => Substitute (TPrimExp t v) where
      substituteNames :: Map VName VName -> TPrimExp t v -> TPrimExp t v
    substituteNames Map VName VName
    substs =
        PrimExp v -> TPrimExp t v
    forall {k} (t :: k) v. PrimExp v -> TPrimExp t v
    TPrimExp (PrimExp v -> TPrimExp t v)
    -> (TPrimExp t v -> PrimExp v) -> TPrimExp t v -> TPrimExp t v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (v -> v) -> PrimExp v -> PrimExp v
    forall a b. (a -> b) -> PrimExp a -> PrimExp b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Map VName VName -> v -> v
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    substs) (PrimExp v -> PrimExp v)
    -> (TPrimExp t v -> PrimExp v) -> TPrimExp t v -> PrimExp v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . TPrimExp t v -> PrimExp v
    forall {k} (t :: k) v. TPrimExp t v -> PrimExp v
    untyped

    instance (Substitutable rep) => Substitute (NameInfo rep) where
      substituteNames :: Map VName VName -> NameInfo rep -> NameInfo rep
    substituteNames Map VName VName
    subst (LetName LetDec rep
    dec) =
        LetDec rep -> NameInfo rep
    forall rep. LetDec rep -> NameInfo rep
    LetName (LetDec rep -> NameInfo rep) -> LetDec rep -> NameInfo rep
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> LetDec rep -> LetDec rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    subst LetDec rep
    dec
      substituteNames Map VName VName
    subst (FParamName FParamInfo rep
    dec) =
        FParamInfo rep -> NameInfo rep
    forall rep. FParamInfo rep -> NameInfo rep
    FParamName (FParamInfo rep -> NameInfo rep) -> FParamInfo rep -> NameInfo rep
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> FParamInfo rep -> FParamInfo rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    subst FParamInfo rep
    dec
      substituteNames Map VName VName
    subst (LParamName LParamInfo rep
    dec) =
        LParamInfo rep -> NameInfo rep
    forall rep. LParamInfo rep -> NameInfo rep
    LParamName (LParamInfo rep -> NameInfo rep) -> LParamInfo rep -> NameInfo rep
    forall a b. (a -> b) -> a -> b
    $ Map VName VName -> LParamInfo rep -> LParamInfo rep
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    subst LParamInfo rep
    dec
      substituteNames Map VName VName
    _ (IndexName IntType
    it) =
        IntType -> NameInfo rep
    forall rep. IntType -> NameInfo rep
    IndexName IntType
    it

    instance Substitute FV where
      substituteNames :: Map VName VName -> FV -> FV
    substituteNames Map VName VName
    subst = Names -> FV
    fvNames (Names -> FV) -> (FV -> Names) -> FV -> FV
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map VName VName -> Names -> Names
    forall a. Substitute a => Map VName VName -> a -> a
    substituteNames Map VName VName
    subst (Names -> Names) -> (FV -> Names) -> FV -> Names
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FV -> Names
    forall a. FreeIn a => a -> Names
    freeIn

    -- | Representations in which all annotations support name
    -- substitution.
    type Substitutable rep =
      ( RepTypes rep,
        Substitute (ExpDec rep),
        Substitute (BodyDec rep),
        Substitute (LetDec rep),
        Substitute (FParamInfo rep),
        Substitute (LParamInfo rep),
        Substitute (RetType rep),
        Substitute (BranchType rep),
        Substitute (Op rep)
      )