{-
    Checks whether the type constructor name matches the return constraint
    of the data constructor
    and at the same time generate coercions for every parameter of result type type constructor
    then generate fresh variables for parameter and coercions that are either trivial
    variable ones or to concrete types

    e.g.
      checkAndGenerateSubstitution Maybe (a' -> Maybe a') [Type]
      > (a' -> Maybe a, [a |-> a'], [a : Type])

      checkAndGenerateSubstitution Other (a' -> Maybe a') [Type]
      > *** fails

      checkAndGenerateSubstitution Vec (Vec 0 t') [Nat, Type]
      > (Vec n t', [n |-> Subst 0, t |-> t'], [n : Type, ])

      checkAndGenerateSubstitution Vec (t' -> Vec n' t' -> Vec (n'+1) t') [Nat, Type]
      > (t' -> Vec n' t' -> Vec n t, [n |-> Subst (n'+1), t |-> t'], [])

      checkAndGenerateSubstitution Foo (Int -> Foo Int) [Type]
      > (Int -> Foo t1, [t1 |-> Subst Int], [t1 : Type])

-}

checkAndGenerateSubstitution ::
       Span                     -- ^ Location of this application
    -> Id                       -- ^ Name of the type constructor
    -> Type                     -- ^ Type of the data constructor
    -> [Kind]                   -- ^ Types of the remaining data type indices
    -> Checker (Type, Substitution, Ctxt Kind)
checkAndGenerateSubstitution sp tName ty ixkinds =
    checkAndGenerateSubstitution' sp tName ty (reverse ixkinds)
  where
    checkAndGenerateSubstitution' sp tName (TyCon tC) []
        | tC == tName = return (TyCon tC, [], [])
        | otherwise = throw UnexpectedTypeConstructor
          { errLoc = sp, tyConActual = tC, tyConExpected = tName }

    checkAndGenerateSubstitution' sp tName (FunTy arg res) kinds = do
      (res', subst, tyVarsNew) <- checkAndGenerateSubstitution' sp tName res kinds
      return (FunTy arg res', subst, tyVarsNew)

    checkAndGenerateSubstitution' sp tName (TyApp fun arg) (kind:kinds) = do
      varSymb <- freshIdentifierBase "t"
      let var = mkId varSymb
      (fun', subst, tyVarsNew) <-  checkAndGenerateSubstitution' sp tName fun kinds
      return (TyApp fun' (TyVar var), (var, SubstT arg) : subst, (var, kind) : tyVarsNew)

    checkAndGenerateSubstitution' sp _ t _ =
      throw InvalidTypeDefinition { errLoc = sp, errTy = t }
checkAndGenerateSubstitution ::
       Span                     -- ^ Location of this application
    -> Id                       -- ^ Name of the type constructor
    -> Type                     -- ^ Type of the data constructor
    -> [Kind]                   -- ^ Types of the remaining data type indices
    -> Checker (Type, Substitution, Ctxt Kind)
checkAndGenerateSubstitution sp tName ty ixkinds =
    checkAndGenerateSubstitution' sp tName ty (reverse ixkinds)
  where
    checkAndGenerateSubstitution' sp tName (TyCon tC) []
        | tC == tName = return (TyCon tC, [], [])
        | otherwise = throw UnexpectedTypeConstructor
          { errLoc = sp, tyConActual = tC, tyConExpected = tName }

    checkAndGenerateSubstitution' sp tName (FunTy arg res) kinds = do
      (res', subst, tyVarsNew) <- checkAndGenerateSubstitution' sp tName res kinds
      return (FunTy arg res', subst, tyVarsNew)

    checkAndGenerateSubstitution' sp tName (TyApp fun arg) (kind:kinds) = do
      varSymb <- freshIdentifierBase "t"
      let var = mkId varSymb
      (fun', subst, tyVarsNew) <-  checkAndGenerateSubstitution' sp tName fun kinds
      return (TyApp fun' (TyVar var), (var, SubstT arg) : subst, (var, kind) : tyVarsNew)

    checkAndGenerateSubstitution' sp _ t _ =
      throw InvalidTypeDefinition { errLoc = sp, errTy = t }
checkAndGenerateSubstitution sp tName ty ixkinds =
    checkAndGenerateSubstitution' sp tName ty (reverse ixkinds)
  where
    checkAndGenerateSubstitution' sp tName (TyCon tC) []
        | tC == tName = return (TyCon tC, [], [])
        | otherwise = throw UnexpectedTypeConstructor
          { errLoc = sp, tyConActual = tC, tyConExpected = tName }

    checkAndGenerateSubstitution' sp tName (FunTy arg res) kinds = do
      (res', subst, tyVarsNew) <- checkAndGenerateSubstitution' sp tName res kinds
      return (FunTy arg res', subst, tyVarsNew)

    checkAndGenerateSubstitution' sp tName (TyApp fun arg) (kind:kinds) = do
      varSymb <- freshIdentifierBase "t"
      let var = mkId varSymb
      (fun', subst, tyVarsNew) <-  checkAndGenerateSubstitution' sp tName fun kinds
      return (TyApp fun' (TyVar var), (var, SubstT arg) : subst, (var, kind) : tyVarsNew)

    checkAndGenerateSubstitution' sp _ t _ =
      throw InvalidTypeDefinition { errLoc = sp, errTy = t }