never executed always true always false
    1 
    2 {-# LANGUAGE ConstraintKinds #-}
    3 {-# LANGUAGE DeriveDataTypeable #-}
    4 {-# LANGUAGE FlexibleContexts #-}
    5 {-# LANGUAGE FlexibleInstances #-}
    6 {-# LANGUAGE ScopedTypeVariables #-}
    7 {-# LANGUAGE StandaloneDeriving #-}
    8 {-# LANGUAGE TypeFamilies #-}
    9 {-# LANGUAGE TypeApplications #-}
   10 {-# LANGUAGE DataKinds #-}
   11 {-# LANGUAGE UndecidableInstances #-} -- Wrinkle in Note [Trees That Grow]
   12                                       -- in module Language.Haskell.Syntax.Extension
   13 {-
   14 (c) The University of Glasgow 2006
   15 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   16 
   17 
   18 GHC.Hs.Type: Abstract syntax: user-defined types
   19 -}
   20 
   21 -- See Note [Language.Haskell.Syntax.* Hierarchy] for why not GHC.Hs.*
   22 module Language.Haskell.Syntax.Type (
   23         Mult, HsScaled(..),
   24         hsMult, hsScaledThing,
   25         HsArrow(..),
   26         HsLinearArrowTokens(..),
   27 
   28         HsType(..), HsCoreTy, LHsType, HsKind, LHsKind,
   29         HsForAllTelescope(..), HsTyVarBndr(..), LHsTyVarBndr,
   30         LHsQTyVars(..),
   31         HsOuterTyVarBndrs(..), HsOuterFamEqnTyVarBndrs, HsOuterSigTyVarBndrs,
   32         HsWildCardBndrs(..),
   33         HsPatSigType(..), HsPSRn(..),
   34         HsSigType(..), LHsSigType, LHsSigWcType, LHsWcType,
   35         HsTupleSort(..),
   36         HsContext, LHsContext,
   37         HsTyLit(..),
   38         HsIPName(..), hsIPNameFS,
   39         HsArg(..), numVisibleArgs, pprHsArgsApp,
   40         LHsTypeArg,
   41 
   42         LBangType, BangType,
   43         HsSrcBang(..), HsImplBang(..),
   44         SrcStrictness(..), SrcUnpackedness(..),
   45 
   46         ConDeclField(..), LConDeclField,
   47 
   48         HsConDetails(..), noTypeArgs,
   49 
   50         FieldOcc(..), LFieldOcc,
   51         AmbiguousFieldOcc(..), LAmbiguousFieldOcc,
   52 
   53         mapHsOuterImplicit,
   54         hsQTvExplicit,
   55         isHsKindedTyVar,
   56         hsPatSigType,
   57     ) where
   58 
   59 import GHC.Prelude
   60 
   61 import {-# SOURCE #-} Language.Haskell.Syntax.Expr ( HsSplice )
   62 
   63 import Language.Haskell.Syntax.Extension
   64 
   65 import GHC.Types.SourceText
   66 import GHC.Types.Name( Name )
   67 import GHC.Types.Name.Reader ( RdrName )
   68 import GHC.Core.DataCon( HsSrcBang(..), HsImplBang(..),
   69                          SrcStrictness(..), SrcUnpackedness(..) )
   70 import GHC.Core.Type
   71 import GHC.Hs.Doc
   72 import GHC.Types.Basic
   73 import GHC.Types.Fixity
   74 import GHC.Types.SrcLoc
   75 import GHC.Utils.Outputable
   76 import GHC.Data.FastString
   77 import GHC.Utils.Misc ( count )
   78 import GHC.Parser.Annotation
   79 
   80 import Data.Data hiding ( Fixity, Prefix, Infix )
   81 import Data.Void
   82 
   83 {-
   84 ************************************************************************
   85 *                                                                      *
   86 \subsection{Bang annotations}
   87 *                                                                      *
   88 ************************************************************************
   89 -}
   90 
   91 -- | Located Bang Type
   92 type LBangType pass = XRec pass (BangType pass)
   93 
   94 -- | Bang Type
   95 --
   96 -- In the parser, strictness and packedness annotations bind more tightly
   97 -- than docstrings. This means that when consuming a 'BangType' (and looking
   98 -- for 'HsBangTy') we must be ready to peer behind a potential layer of
   99 -- 'HsDocTy'. See #15206 for motivation and 'getBangType' for an example.
  100 type BangType pass  = HsType pass       -- Bangs are in the HsType data type
  101 
  102 {-
  103 ************************************************************************
  104 *                                                                      *
  105 \subsection{Data types}
  106 *                                                                      *
  107 ************************************************************************
  108 
  109 This is the syntax for types as seen in type signatures.
  110 
  111 Note [HsBSig binder lists]
  112 ~~~~~~~~~~~~~~~~~~~~~~~~~~
  113 Consider a binder (or pattern) decorated with a type or kind,
  114    \ (x :: a -> a). blah
  115    forall (a :: k -> *) (b :: k). blah
  116 Then we use a LHsBndrSig on the binder, so that the
  117 renamer can decorate it with the variables bound
  118 by the pattern ('a' in the first example, 'k' in the second),
  119 assuming that neither of them is in scope already
  120 See also Note [Kind and type-variable binders] in GHC.Rename.HsType
  121 
  122 Note [HsType binders]
  123 ~~~~~~~~~~~~~~~~~~~~~
  124 The system for recording type and kind-variable binders in HsTypes
  125 is a bit complicated.  Here's how it works.
  126 
  127 * In a HsType,
  128      HsForAllTy   represents an /explicit, user-written/ 'forall' that
  129                   is nested within another HsType
  130                    e.g.   forall a b.   {...} or
  131                           forall a b -> {...}
  132 
  133                   Note that top-level 'forall's are represented with a
  134                   different AST form. See the description of HsOuterTyVarBndrs
  135                   below.
  136      HsQualTy     represents an /explicit, user-written/ context
  137                    e.g.   (Eq a, Show a) => ...
  138                   The context can be empty if that's what the user wrote
  139   These constructors represent what the user wrote, no more
  140   and no less.
  141 
  142 * The ForAllTelescope field of HsForAllTy represents whether a forall is
  143   invisible (e.g., forall a b. {...}, with a dot) or visible
  144   (e.g., forall a b -> {...}, with an arrow).
  145 
  146 * HsTyVarBndr describes a quantified type variable written by the
  147   user.  For example
  148      f :: forall a (b :: *).  blah
  149   here 'a' and '(b::*)' are each a HsTyVarBndr.  A HsForAllTy has
  150   a list of LHsTyVarBndrs.
  151 
  152 * HsOuterTyVarBndrs is used to represent the outermost quantified type
  153   variables in a type that obeys the forall-or-nothing rule. An
  154   HsOuterTyVarBndrs can be one of the following:
  155 
  156     HsOuterImplicit (implicit quantification, added by renamer)
  157           f :: a -> a     -- Desugars to f :: forall {a}. a -> a
  158     HsOuterExplicit (explicit user quantifiation):
  159           f :: forall a. a -> a
  160 
  161   See Note [forall-or-nothing rule].
  162 
  163 * An HsSigType is an LHsType with an accompanying HsOuterTyVarBndrs that
  164   represents the presence (or absence) of its outermost 'forall'.
  165   See Note [Representing type signatures].
  166 
  167 * HsWildCardBndrs is a wrapper that binds the wildcard variables
  168   of the wrapped thing.  It is filled in by the renamer
  169      f :: _a -> _
  170   The enclosing HsWildCardBndrs binds the wildcards _a and _.
  171 
  172 * HsSigPatType describes types that appear in pattern signatures and
  173   the signatures of term-level binders in RULES. Like
  174   HsWildCardBndrs/HsOuterTyVarBndrs, they track the names of wildcard
  175   variables and implicitly bound type variables. Unlike
  176   HsOuterTyVarBndrs, however, HsSigPatTypes do not obey the
  177   forall-or-nothing rule. See Note [Pattern signature binders and scoping].
  178 
  179 * The explicit presence of these wrappers specifies, in the HsSyn,
  180   exactly where implicit quantification is allowed, and where
  181   wildcards are allowed.
  182 
  183 * LHsQTyVars is used in data/class declarations, where the user gives
  184   explicit *type* variable bindings, but we need to implicitly bind
  185   *kind* variables.  For example
  186       class C (a :: k -> *) where ...
  187   The 'k' is implicitly bound in the hsq_tvs field of LHsQTyVars
  188 
  189 Note [The wildcard story for types]
  190 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  191 Types can have wildcards in them, to support partial type signatures,
  192 like       f :: Int -> (_ , _a) -> _a
  193 
  194 A wildcard in a type can be
  195 
  196   * An anonymous wildcard,
  197         written '_'
  198     In HsType this is represented by HsWildCardTy.
  199     The renamer leaves it untouched, and it is later given a fresh
  200     meta tyvar in the typechecker.
  201 
  202   * A named wildcard,
  203         written '_a', '_foo', etc
  204     In HsType this is represented by (HsTyVar "_a")
  205     i.e. a perfectly ordinary type variable that happens
  206          to start with an underscore
  207 
  208 Note carefully:
  209 
  210 * When NamedWildCards is off, type variables that start with an
  211   underscore really /are/ ordinary type variables.  And indeed, even
  212   when NamedWildCards is on you can bind _a explicitly as an ordinary
  213   type variable:
  214         data T _a _b = MkT _b _a
  215   Or even:
  216         f :: forall _a. _a -> _b
  217   Here _a is an ordinary forall'd binder, but (With NamedWildCards)
  218   _b is a named wildcard.  (See the comments in #10982)
  219 
  220 * Named wildcards are bound by the HsWildCardBndrs (for types that obey the
  221   forall-or-nothing rule) and HsPatSigType (for type signatures in patterns
  222   and term-level binders in RULES), which wrap types that are allowed to have
  223   wildcards. Unnamed wildcards, however are left unchanged until typechecking,
  224   where we give them fresh wild tyvars and determine whether or not to emit
  225   hole constraints on each wildcard (we don't if it's a visible type/kind
  226   argument or a type family pattern). See related notes
  227   Note [Wildcards in visible kind application] and
  228   Note [Wildcards in visible type application] in GHC.Tc.Gen.HsType.
  229 
  230 * After type checking is done, we report what types the wildcards
  231   got unified with.
  232 
  233 Note [Ordering of implicit variables]
  234 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  235 Since the advent of -XTypeApplications, GHC makes promises about the ordering
  236 of implicit variable quantification. Specifically, we offer that implicitly
  237 quantified variables (such as those in const :: a -> b -> a, without a `forall`)
  238 will occur in left-to-right order of first occurrence. Here are a few examples:
  239 
  240   const :: a -> b -> a       -- forall a b. ...
  241   f :: Eq a => b -> a -> a   -- forall a b. ...  contexts are included
  242 
  243   type a <-< b = b -> a
  244   g :: a <-< b               -- forall a b. ...  type synonyms matter
  245 
  246   class Functor f where
  247     fmap :: (a -> b) -> f a -> f b   -- forall f a b. ...
  248     -- The f is quantified by the class, so only a and b are considered in fmap
  249 
  250 This simple story is complicated by the possibility of dependency: all variables
  251 must come after any variables mentioned in their kinds.
  252 
  253   typeRep :: Typeable a => TypeRep (a :: k)   -- forall k a. ...
  254 
  255 The k comes first because a depends on k, even though the k appears later than
  256 the a in the code. Thus, GHC does a *stable topological sort* on the variables.
  257 By "stable", we mean that any two variables who do not depend on each other
  258 preserve their existing left-to-right ordering.
  259 
  260 Implicitly bound variables are collected by the extract- family of functions
  261 (extractHsTysRdrTyVars, extractHsTyVarBndrsKVs, etc.) in GHC.Rename.HsType.
  262 These functions thus promise to keep left-to-right ordering.
  263 Look for pointers to this note to see the places where the action happens.
  264 
  265 Note that we also maintain this ordering in kind signatures. Even though
  266 there's no visible kind application (yet), having implicit variables be
  267 quantified in left-to-right order in kind signatures is nice since:
  268 
  269 * It's consistent with the treatment for type signatures.
  270 * It can affect how types are displayed with -fprint-explicit-kinds (see
  271   #15568 for an example), which is a situation where knowing the order in
  272   which implicit variables are quantified can be useful.
  273 * In the event that visible kind application is implemented, the order in
  274   which we would expect implicit variables to be ordered in kinds will have
  275   already been established.
  276 -}
  277 
  278 -- | Located Haskell Context
  279 type LHsContext pass = XRec pass (HsContext pass)
  280       -- ^ 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnUnit'
  281       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  282 
  283 -- | Haskell Context
  284 type HsContext pass = [LHsType pass]
  285 
  286 -- | Located Haskell Type
  287 type LHsType pass = XRec pass (HsType pass)
  288       -- ^ May have 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnComma' when
  289       --   in a list
  290 
  291       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  292 
  293 -- | Haskell Kind
  294 type HsKind pass = HsType pass
  295 
  296 -- | Located Haskell Kind
  297 type LHsKind pass = XRec pass (HsKind pass)
  298       -- ^ 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnDcolon'
  299 
  300       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  301 
  302 --------------------------------------------------
  303 --             LHsQTyVars
  304 --  The explicitly-quantified binders in a data/type declaration
  305 
  306 -- | The type variable binders in an 'HsForAllTy'.
  307 -- See also @Note [Variable Specificity and Forall Visibility]@ in
  308 -- "GHC.Tc.Gen.HsType".
  309 data HsForAllTelescope pass
  310   = HsForAllVis -- ^ A visible @forall@ (e.g., @forall a -> {...}@).
  311                 --   These do not have any notion of specificity, so we use
  312                 --   '()' as a placeholder value.
  313     { hsf_xvis      :: XHsForAllVis pass
  314     , hsf_vis_bndrs :: [LHsTyVarBndr () pass]
  315     }
  316   | HsForAllInvis -- ^ An invisible @forall@ (e.g., @forall a {b} c. {...}@),
  317                   --   where each binder has a 'Specificity'.
  318     { hsf_xinvis       :: XHsForAllInvis pass
  319     , hsf_invis_bndrs  :: [LHsTyVarBndr Specificity pass]
  320     }
  321   | XHsForAllTelescope !(XXHsForAllTelescope pass)
  322 
  323 -- | Located Haskell Type Variable Binder
  324 type LHsTyVarBndr flag pass = XRec pass (HsTyVarBndr flag pass)
  325                          -- See Note [HsType binders]
  326 
  327 -- | Located Haskell Quantified Type Variables
  328 data LHsQTyVars pass   -- See Note [HsType binders]
  329   = HsQTvs { hsq_ext :: XHsQTvs pass
  330 
  331            , hsq_explicit :: [LHsTyVarBndr () pass]
  332                 -- Explicit variables, written by the user
  333     }
  334   | XLHsQTyVars !(XXLHsQTyVars pass)
  335 
  336 hsQTvExplicit :: LHsQTyVars pass -> [LHsTyVarBndr () pass]
  337 hsQTvExplicit = hsq_explicit
  338 
  339 ------------------------------------------------
  340 --            HsOuterTyVarBndrs
  341 -- Used to quantify the outermost type variable binders of a type that obeys
  342 -- the forall-or-nothing rule. These are used to represent the outermost
  343 -- quantification in:
  344 --    * Type signatures (LHsSigType/LHsSigWcType)
  345 --    * Patterns in a type/data family instance (HsTyPats)
  346 --
  347 -- We support two forms:
  348 --   HsOuterImplicit (implicit quantification, added by renamer)
  349 --         f :: a -> a     -- Desugars to f :: forall {a}. a -> a
  350 --         type instance F (a,b) = a->b
  351 --   HsOuterExplicit (explicit user quantifiation):
  352 --         f :: forall a. a -> a
  353 --         type instance forall a b. F (a,b) = a->b
  354 --
  355 -- In constrast, when the user writes /visible/ quanitification
  356 --         T :: forall k -> k -> Type
  357 -- we use use HsOuterImplicit, wrapped around a HsForAllTy
  358 -- for the visible quantification
  359 --
  360 -- See Note [forall-or-nothing rule]
  361 
  362 -- | The outermost type variables in a type that obeys the @forall@-or-nothing
  363 -- rule. See @Note [forall-or-nothing rule]@.
  364 data HsOuterTyVarBndrs flag pass
  365   = HsOuterImplicit -- ^ Implicit forall, e.g.,
  366                     --    @f :: a -> b -> b@
  367     { hso_ximplicit :: XHsOuterImplicit pass
  368     }
  369   | HsOuterExplicit -- ^ Explicit forall, e.g.,
  370                     --    @f :: forall a b. a -> b -> b@
  371     { hso_xexplicit :: XHsOuterExplicit pass flag
  372     , hso_bndrs     :: [LHsTyVarBndr flag (NoGhcTc pass)]
  373     }
  374   | XHsOuterTyVarBndrs !(XXHsOuterTyVarBndrs pass)
  375 
  376 -- | Used for signatures, e.g.,
  377 --
  378 -- @
  379 -- f :: forall a {b}. blah
  380 -- @
  381 --
  382 -- We use 'Specificity' for the 'HsOuterTyVarBndrs' @flag@ to allow
  383 -- distinguishing between specified and inferred type variables.
  384 type HsOuterSigTyVarBndrs = HsOuterTyVarBndrs Specificity
  385 
  386 -- | Used for type-family instance equations, e.g.,
  387 --
  388 -- @
  389 -- type instance forall a. F [a] = Tree a
  390 -- @
  391 --
  392 -- The notion of specificity is irrelevant in type family equations, so we use
  393 -- @()@ for the 'HsOuterTyVarBndrs' @flag@.
  394 type HsOuterFamEqnTyVarBndrs = HsOuterTyVarBndrs ()
  395 
  396 -- | Haskell Wildcard Binders
  397 data HsWildCardBndrs pass thing
  398     -- See Note [HsType binders]
  399     -- See Note [The wildcard story for types]
  400   = HsWC { hswc_ext :: XHsWC pass thing
  401                 -- after the renamer
  402                 -- Wild cards, only named
  403                 -- See Note [Wildcards in visible kind application]
  404 
  405          , hswc_body :: thing
  406                 -- Main payload (type or list of types)
  407                 -- If there is an extra-constraints wildcard,
  408                 -- it's still there in the hsc_body.
  409     }
  410   | XHsWildCardBndrs !(XXHsWildCardBndrs pass thing)
  411 
  412 -- | Types that can appear in pattern signatures, as well as the signatures for
  413 -- term-level binders in RULES.
  414 -- See @Note [Pattern signature binders and scoping]@.
  415 --
  416 -- This is very similar to 'HsSigWcType', but with
  417 -- slightly different semantics: see @Note [HsType binders]@.
  418 -- See also @Note [The wildcard story for types]@.
  419 data HsPatSigType pass
  420   = HsPS { hsps_ext  :: XHsPS pass   -- ^ After renamer: 'HsPSRn'
  421          , hsps_body :: LHsType pass -- ^ Main payload (the type itself)
  422     }
  423   | XHsPatSigType !(XXHsPatSigType pass)
  424 
  425 -- | The extension field for 'HsPatSigType', which is only used in the
  426 -- renamer onwards. See @Note [Pattern signature binders and scoping]@.
  427 data HsPSRn = HsPSRn
  428   { hsps_nwcs    :: [Name] -- ^ Wildcard names
  429   , hsps_imp_tvs :: [Name] -- ^ Implicitly bound variable names
  430   }
  431   deriving Data
  432 
  433 -- | Located Haskell Signature Type
  434 type LHsSigType   pass = XRec pass (HsSigType pass)               -- Implicit only
  435 
  436 -- | Located Haskell Wildcard Type
  437 type LHsWcType    pass = HsWildCardBndrs pass (LHsType pass)    -- Wildcard only
  438 
  439 -- | Located Haskell Signature Wildcard Type
  440 type LHsSigWcType pass = HsWildCardBndrs pass (LHsSigType pass) -- Both
  441 
  442 -- | A type signature that obeys the @forall@-or-nothing rule. In other
  443 -- words, an 'LHsType' that uses an 'HsOuterSigTyVarBndrs' to represent its
  444 -- outermost type variable quantification.
  445 -- See @Note [Representing type signatures]@.
  446 data HsSigType pass
  447   = HsSig { sig_ext   :: XHsSig pass
  448           , sig_bndrs :: HsOuterSigTyVarBndrs pass
  449           , sig_body  :: LHsType pass
  450           }
  451   | XHsSigType !(XXHsSigType pass)
  452 
  453 hsPatSigType :: HsPatSigType pass -> LHsType pass
  454 hsPatSigType = hsps_body
  455 
  456 {-
  457 Note [forall-or-nothing rule]
  458 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  459 Free variables in signatures are usually bound in an implicit 'forall' at the
  460 beginning of user-written signatures. However, if the signature has an
  461 explicit, invisible forall at the beginning, this is disabled. This is referred
  462 to as the forall-or-nothing rule.
  463 
  464 The idea is nested foralls express something which is only expressible
  465 explicitly, while a top level forall could (usually) be replaced with an
  466 implicit binding. Top-level foralls alone ("forall.") are therefore an
  467 indication that the user is trying to be fastidious, so we don't implicitly
  468 bind any variables.
  469 
  470 Note that this rule only applies to outermost /in/visible 'forall's, and not
  471 outermost visible 'forall's. See #18660 for more on this point.
  472 
  473 Here are some concrete examples to demonstrate the forall-or-nothing rule in
  474 action:
  475 
  476   type F1 :: a -> b -> b                    -- Legal; a,b are implicitly quantified.
  477                                             -- Equivalently: forall a b. a -> b -> b
  478 
  479   type F2 :: forall a b. a -> b -> b        -- Legal; explicitly quantified
  480 
  481   type F3 :: forall a. a -> b -> b          -- Illegal; the forall-or-nothing rule says that
  482                                             -- if you quantify a, you must also quantify b
  483 
  484   type F4 :: forall a -> b -> b             -- Legal; the top quantifier (forall a) is a /visible/
  485                                             -- quantifer, so the "nothing" part of the forall-or-nothing
  486                                             -- rule applies, and b is therefore implicitly quantified.
  487                                             -- Equivalently: forall b. forall a -> b -> b
  488 
  489   type F5 :: forall b. forall a -> b -> c   -- Illegal; the forall-or-nothing rule says that
  490                                             -- if you quantify b, you must also quantify c
  491 
  492   type F6 :: forall a -> forall b. b -> c   -- Legal: just like F4.
  493 
  494 For a complete list of all places where the forall-or-nothing rule applies, see
  495 "The `forall`-or-nothing rule" section of the GHC User's Guide.
  496 
  497 Any type that obeys the forall-or-nothing rule is represented in the AST with
  498 an HsOuterTyVarBndrs:
  499 
  500 * If the type has an outermost, invisible 'forall', it uses HsOuterExplicit,
  501   which contains a list of the explicitly quantified type variable binders in
  502   `hso_bndrs`. After typechecking, HsOuterExplicit also stores a list of the
  503   explicitly quantified `InvisTVBinder`s in
  504   `hso_xexplicit :: XHsOuterExplicit GhcTc`.
  505 
  506 * Otherwise, it uses HsOuterImplicit. HsOuterImplicit is used for different
  507   things depending on the phase:
  508 
  509   * After parsing, it does not store anything in particular.
  510   * After renaming, it stores the implicitly bound type variable `Name`s in
  511     `hso_ximplicit :: XHsOuterImplicit GhcRn`.
  512   * After typechecking, it stores the implicitly bound `TyVar`s in
  513     `hso_ximplicit :: XHsOuterImplicit GhcTc`.
  514 
  515   NB: this implicit quantification is purely lexical: we bind any
  516       type or kind variables that are not in scope. The type checker
  517       may subsequently quantify over further kind variables.
  518       See Note [Binding scoped type variables] in GHC.Tc.Gen.Sig.
  519 
  520 HsOuterTyVarBndrs GhcTc is used in the typechecker as an intermediate data type
  521 for storing the outermost TyVars/InvisTVBinders in a type.
  522 See GHC.Tc.Gen.HsType.bindOuterTKBndrsX for an example of this.
  523 
  524 Note [Representing type signatures]
  525 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  526 HsSigType is used to represent an explicit user type signature. These are
  527 used in a variety of places. Some examples include:
  528 
  529 * Type signatures (e.g., f :: a -> a)
  530 * Standalone kind signatures (e.g., type G :: a -> a)
  531 * GADT constructor types (e.g., data T where MkT :: a -> T)
  532 
  533 A HsSigType is the combination of an HsOuterSigTyVarBndrs and an LHsType:
  534 
  535 * The HsOuterSigTyVarBndrs binds the /explicitly/ quantified type variables
  536   when the type signature has an outermost, user-written 'forall' (i.e,
  537   the HsOuterExplicit constructor is used). If there is no outermost 'forall',
  538   then it binds the /implicitly/ quantified type variables instead (i.e.,
  539   the HsOuterImplicit constructor is used).
  540 * The LHsType represents the rest of the type.
  541 
  542 E.g. For a signature like
  543    f :: forall k (a::k). blah
  544 we get
  545    HsSig { sig_bndrs = HsOuterExplicit { hso_bndrs = [k, (a :: k)] }
  546          , sig_body  = blah }
  547 
  548 Note [Pattern signature binders and scoping]
  549 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  550 Consider the pattern signatures like those on `t` and `g` in:
  551 
  552    f = let h = \(t :: (b, b) ->
  553                \(g :: forall a. a -> b) ->
  554                ...(t :: (Int,Int))...
  555        in woggle
  556 
  557 * The `b` in t's pattern signature is implicitly bound and scopes over
  558   the signature and the body of the lambda.  It stands for a type (any type);
  559   indeed we subsequently discover that b=Int.
  560   (See Note [TyVarTv] in GHC.Tc.Utils.TcMType for more on this point.)
  561 * The `b` in g's pattern signature is an /occurrence/ of the `b` bound by
  562   t's pattern signature.
  563 * The `a` in `forall a` scopes only over the type `a -> b`, not over the body
  564   of the lambda.
  565 * There is no forall-or-nothing rule for pattern signatures, which is why the
  566   type `forall a. a -> b` is permitted in `g`'s pattern signature, even though
  567   `b` is not explicitly bound. See Note [forall-or-nothing rule].
  568 
  569 Similar scoping rules apply to term variable binders in RULES, like in the
  570 following example:
  571 
  572    {-# RULES "h" forall (t :: (b, b)) (g :: forall a. a -> b). h t g = ... #-}
  573 
  574 Just like in pattern signatures, the `b` in t's signature is implicitly bound
  575 and scopes over the remainder of the RULE. As a result, the `b` in g's
  576 signature is an occurrence. Moreover, the `a` in `forall a` scopes only over
  577 the type `a -> b`, and the forall-or-nothing rule does not apply.
  578 
  579 While quite similar, RULE term binder signatures behave slightly differently
  580 from pattern signatures in two ways:
  581 
  582 1. Unlike in pattern signatures, where type variables can stand for any type,
  583    type variables in RULE term binder signatures are skolems.
  584    See Note [Typechecking pattern signature binders] in GHC.Tc.Gen.HsType for
  585    more on this point.
  586 
  587    In this sense, type variables in pattern signatures are quite similar to
  588    named wildcards, as both can refer to arbitrary types. The main difference
  589    lies in error reporting: if a named wildcard `_a` in a pattern signature
  590    stands for Int, then by default GHC will emit a warning stating as much.
  591    Changing `_a` to `a`, on the other hand, will cause it not to be reported.
  592 2. In the `h` RULE above, only term variables are explicitly bound, so any free
  593    type variables in the term variables' signatures are implicitly bound.
  594    This is just like how the free type variables in pattern signatures are
  595    implicitly bound. If a RULE explicitly binds both term and type variables,
  596    however, then free type variables in term signatures are /not/ implicitly
  597    bound. For example, this RULE would be ill scoped:
  598 
  599      {-# RULES "h2" forall b. forall (t :: (b, c)) (g :: forall a. a -> b).
  600                     h2 t g = ... #-}
  601 
  602    This is because `b` and `c` occur free in the signature for `t`, but only
  603    `b` was explicitly bound, leaving `c` out of scope. If the RULE had started
  604    with `forall b c.`, then it would have been accepted.
  605 
  606 The types in pattern signatures and RULE term binder signatures are represented
  607 in the AST by HsSigPatType. From the renamer onward, the hsps_ext field (of
  608 type HsPSRn) tracks the names of named wildcards and implicitly bound type
  609 variables so that they can be brought into scope during renaming and
  610 typechecking.
  611 
  612 Note [Lexically scoped type variables]
  613 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  614 The ScopedTypeVariables extension does two things:
  615 
  616 * It allows the use of type signatures in patterns
  617   (e.g., `f (x :: a -> a) = ...`). See
  618   Note [Pattern signature binders and scoping] for more on this point.
  619 * It brings lexically scoped type variables into scope for certain type
  620   signatures with outermost invisible 'forall's.
  621 
  622 This Note concerns the latter bullet point. Per the
  623 "Lexically scoped type variables" section of the GHC User's Guide, the
  624 following forms of type signatures can have lexically scoped type variables:
  625 
  626 * In declarations with type signatures, e.g.,
  627 
  628     f :: forall a. a -> a
  629     f x = e @a
  630 
  631   Here, the 'forall a' brings 'a' into scope over the body of 'f'.
  632 
  633   Note that ScopedTypeVariables does /not/ interact with standalone kind
  634   signatures, only type signatures.
  635 
  636 * In explicit type annotations in expressions, e.g.,
  637 
  638     id @a :: forall a. a -> a
  639 
  640 * In instance declarations, e.g.,
  641 
  642     instance forall a. C [a] where
  643       m = e @a
  644 
  645   Note that unlike the examples above, the use of an outermost 'forall' isn't
  646   required to bring 'a' into scope. That is, the following would also work:
  647 
  648     instance forall a. C [a] where
  649       m = e @a
  650 
  651 Note that all of the types above obey the forall-or-nothing rule. As a result,
  652 the places in the AST that can have lexically scoped type variables are a
  653 subset of the places that use HsOuterTyVarBndrs
  654 (See Note [forall-or-nothing rule].)
  655 
  656 Some other observations about lexically scoped type variables:
  657 
  658 * Only type variables bound by an /invisible/ forall can be lexically scoped.
  659   See Note [hsScopedTvs and visible foralls].
  660 * The lexically scoped type variables may be a strict subset of the type
  661   variables brought into scope by a type signature.
  662   See Note [Binding scoped type variables] in GHC.Tc.Gen.Sig.
  663 -}
  664 
  665 mapHsOuterImplicit :: (XHsOuterImplicit pass -> XHsOuterImplicit pass)
  666                    -> HsOuterTyVarBndrs flag pass
  667                    -> HsOuterTyVarBndrs flag pass
  668 mapHsOuterImplicit f (HsOuterImplicit{hso_ximplicit = imp}) =
  669   HsOuterImplicit{hso_ximplicit = f imp}
  670 mapHsOuterImplicit _ hso@(HsOuterExplicit{})    = hso
  671 mapHsOuterImplicit _ hso@(XHsOuterTyVarBndrs{}) = hso
  672 
  673 
  674 --------------------------------------------------
  675 -- | These names are used early on to store the names of implicit
  676 -- parameters.  They completely disappear after type-checking.
  677 newtype HsIPName = HsIPName FastString
  678   deriving( Eq, Data )
  679 
  680 hsIPNameFS :: HsIPName -> FastString
  681 hsIPNameFS (HsIPName n) = n
  682 
  683 instance Outputable HsIPName where
  684     ppr (HsIPName n) = char '?' <> ftext n -- Ordinary implicit parameters
  685 
  686 instance OutputableBndr HsIPName where
  687     pprBndr _ n   = ppr n         -- Simple for now
  688     pprInfixOcc  n = ppr n
  689     pprPrefixOcc n = ppr n
  690 
  691 --------------------------------------------------
  692 
  693 -- | Haskell Type Variable Binder
  694 -- The flag annotates the binder. It is 'Specificity' in places where
  695 -- explicit specificity is allowed (e.g. x :: forall {a} b. ...) or
  696 -- '()' in other places.
  697 data HsTyVarBndr flag pass
  698   = UserTyVar        -- no explicit kinding
  699          (XUserTyVar pass)
  700          flag
  701          (LIdP pass)
  702         -- See Note [Located RdrNames] in GHC.Hs.Expr
  703 
  704   | KindedTyVar
  705          (XKindedTyVar pass)
  706          flag
  707          (LIdP pass)
  708          (LHsKind pass)  -- The user-supplied kind signature
  709         -- ^
  710         --  - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen',
  711         --          'GHC.Parser.Annotation.AnnDcolon', 'GHC.Parser.Annotation.AnnClose'
  712 
  713         -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  714 
  715   | XTyVarBndr
  716       !(XXTyVarBndr pass)
  717 
  718 -- | Does this 'HsTyVarBndr' come with an explicit kind annotation?
  719 isHsKindedTyVar :: HsTyVarBndr flag pass -> Bool
  720 isHsKindedTyVar (UserTyVar {})   = False
  721 isHsKindedTyVar (KindedTyVar {}) = True
  722 isHsKindedTyVar (XTyVarBndr {})  = False
  723 
  724 -- | Haskell Type
  725 data HsType pass
  726   = HsForAllTy   -- See Note [HsType binders]
  727       { hst_xforall :: XForAllTy pass
  728       , hst_tele    :: HsForAllTelescope pass
  729                                      -- Explicit, user-supplied 'forall a {b} c'
  730       , hst_body    :: LHsType pass  -- body type
  731       }
  732       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnForall',
  733       --         'GHC.Parser.Annotation.AnnDot','GHC.Parser.Annotation.AnnDarrow'
  734       -- For details on above see note [exact print annotations] in "GHC.Parser.Annotation"
  735 
  736   | HsQualTy   -- See Note [HsType binders]
  737       { hst_xqual :: XQualTy pass
  738       , hst_ctxt  :: LHsContext pass  -- Context C => blah
  739       , hst_body  :: LHsType pass }
  740 
  741   | HsTyVar  (XTyVar pass)
  742               PromotionFlag    -- Whether explicitly promoted,
  743                                -- for the pretty printer
  744              (LIdP pass)
  745                   -- Type variable, type constructor, or data constructor
  746                   -- see Note [Promotions (HsTyVar)]
  747                   -- See Note [Located RdrNames] in GHC.Hs.Expr
  748       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  749 
  750       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  751 
  752   | HsAppTy             (XAppTy pass)
  753                         (LHsType pass)
  754                         (LHsType pass)
  755       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  756 
  757       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  758 
  759   | HsAppKindTy         (XAppKindTy pass) -- type level type app
  760                         (LHsType pass)
  761                         (LHsKind pass)
  762 
  763   | HsFunTy             (XFunTy pass)
  764                         (HsArrow pass)
  765                         (LHsType pass)   -- function type
  766                         (LHsType pass)
  767       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnRarrow',
  768 
  769       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  770 
  771   | HsListTy            (XListTy pass)
  772                         (LHsType pass)  -- Element type
  773       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'['@,
  774       --         'GHC.Parser.Annotation.AnnClose' @']'@
  775 
  776       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  777 
  778   | HsTupleTy           (XTupleTy pass)
  779                         HsTupleSort
  780                         [LHsType pass]  -- Element types (length gives arity)
  781     -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'(' or '(#'@,
  782     --         'GHC.Parser.Annotation.AnnClose' @')' or '#)'@
  783 
  784     -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  785 
  786   | HsSumTy             (XSumTy pass)
  787                         [LHsType pass]  -- Element types (length gives arity)
  788     -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'(#'@,
  789     --         'GHC.Parser.Annotation.AnnClose' '#)'@
  790 
  791     -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  792 
  793   | HsOpTy              (XOpTy pass)
  794                         (LHsType pass) (LIdP pass) (LHsType pass)
  795       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  796 
  797       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  798 
  799   | HsParTy             (XParTy pass)
  800                         (LHsType pass)   -- See Note [Parens in HsSyn] in GHC.Hs.Expr
  801         -- Parenthesis preserved for the precedence re-arrangement in
  802         -- GHC.Rename.HsType
  803         -- It's important that a * (b + c) doesn't get rearranged to (a*b) + c!
  804       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'('@,
  805       --         'GHC.Parser.Annotation.AnnClose' @')'@
  806 
  807       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  808 
  809   | HsIParamTy          (XIParamTy pass)
  810                         (XRec pass HsIPName) -- (?x :: ty)
  811                         (LHsType pass)   -- Implicit parameters as they occur in
  812                                          -- contexts
  813       -- ^
  814       -- > (?x :: ty)
  815       --
  816       -- - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnDcolon'
  817 
  818       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  819 
  820   | HsStarTy            (XStarTy pass)
  821                         Bool             -- Is this the Unicode variant?
  822                                          -- Note [HsStarTy]
  823       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  824 
  825   | HsKindSig           (XKindSig pass)
  826                         (LHsType pass)  -- (ty :: kind)
  827                         (LHsKind pass)  -- A type with a kind signature
  828       -- ^
  829       -- > (ty :: kind)
  830       --
  831       -- - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'('@,
  832       --         'GHC.Parser.Annotation.AnnDcolon','GHC.Parser.Annotation.AnnClose' @')'@
  833 
  834       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  835 
  836   | HsSpliceTy          (XSpliceTy pass)
  837                         (HsSplice pass)   -- Includes quasi-quotes
  838       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'$('@,
  839       --         'GHC.Parser.Annotation.AnnClose' @')'@
  840 
  841       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  842 
  843   | HsDocTy             (XDocTy pass)
  844                         (LHsType pass) LHsDocString -- A documented type
  845       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  846 
  847       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  848 
  849   | HsBangTy    (XBangTy pass)
  850                 HsSrcBang (LHsType pass)   -- Bang-style type annotations
  851       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' :
  852       --         'GHC.Parser.Annotation.AnnOpen' @'{-\# UNPACK' or '{-\# NOUNPACK'@,
  853       --         'GHC.Parser.Annotation.AnnClose' @'#-}'@
  854       --         'GHC.Parser.Annotation.AnnBang' @\'!\'@
  855 
  856       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  857 
  858   | HsRecTy     (XRecTy pass)
  859                 [LConDeclField pass]    -- Only in data type declarations
  860       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @'{'@,
  861       --         'GHC.Parser.Annotation.AnnClose' @'}'@
  862 
  863       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  864 
  865   | HsExplicitListTy       -- A promoted explicit list
  866         (XExplicitListTy pass)
  867         PromotionFlag      -- whether explicitly promoted, for pretty printer
  868         [LHsType pass]
  869       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @"'["@,
  870       --         'GHC.Parser.Annotation.AnnClose' @']'@
  871 
  872       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  873 
  874   | HsExplicitTupleTy      -- A promoted explicit tuple
  875         (XExplicitTupleTy pass)
  876         [LHsType pass]
  877       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnOpen' @"'("@,
  878       --         'GHC.Parser.Annotation.AnnClose' @')'@
  879 
  880       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  881 
  882   | HsTyLit (XTyLit pass) HsTyLit      -- A promoted numeric literal.
  883       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  884 
  885       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  886 
  887   | HsWildCardTy (XWildCardTy pass)  -- A type wildcard
  888       -- See Note [The wildcard story for types]
  889       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : None
  890 
  891       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
  892 
  893   -- Extension point; see Note [Trees That Grow] in Language.Haskell.Syntax.Extension
  894   | XHsType
  895       !(XXType pass)
  896 
  897 -- An escape hatch for tunnelling a Core 'Type' through 'HsType'.
  898 -- For more details on how this works, see:
  899 --
  900 -- * @Note [Renaming HsCoreTys]@ in "GHC.Rename.HsType"
  901 --
  902 -- * @Note [Typechecking HsCoreTys]@ in "GHC.Tc.Gen.HsType"
  903 type HsCoreTy = Type
  904 
  905 
  906 -- Note [Literal source text] in GHC.Types.Basic for SourceText fields in
  907 -- the following
  908 -- | Haskell Type Literal
  909 data HsTyLit
  910   = HsNumTy SourceText Integer
  911   | HsStrTy SourceText FastString
  912   | HsCharTy SourceText Char
  913     deriving Data
  914 
  915 -- | Denotes the type of arrows in the surface language
  916 data HsArrow pass
  917   = HsUnrestrictedArrow !(LHsUniToken "->" "→" pass)
  918     -- ^ a -> b or a → b
  919   | HsLinearArrow !(HsLinearArrowTokens pass)
  920     -- ^ a %1 -> b or a %1 → b, or a ⊸ b
  921   | HsExplicitMult !(LHsToken "%" pass) !(LHsType pass) !(LHsUniToken "->" "→" pass)
  922     -- ^ a %m -> b or a %m → b (very much including `a %Many -> b`!
  923     -- This is how the programmer wrote it). It is stored as an
  924     -- `HsType` so as to preserve the syntax as written in the
  925     -- program.
  926 
  927 data HsLinearArrowTokens pass
  928   = HsPct1 !(LHsToken "%1" pass) !(LHsUniToken "->" "→" pass)
  929   | HsLolly !(LHsToken "⊸" pass)
  930 
  931 -- | This is used in the syntax. In constructor declaration. It must keep the
  932 -- arrow representation.
  933 data HsScaled pass a = HsScaled (HsArrow pass) a
  934 
  935 hsMult :: HsScaled pass a -> HsArrow pass
  936 hsMult (HsScaled m _) = m
  937 
  938 hsScaledThing :: HsScaled pass a -> a
  939 hsScaledThing (HsScaled _ t) = t
  940 
  941 {-
  942 Note [Unit tuples]
  943 ~~~~~~~~~~~~~~~~~~
  944 Consider the type
  945     type instance F Int = ()
  946 We want to parse that "()"
  947     as HsTupleTy HsBoxedOrConstraintTuple [],
  948 NOT as HsTyVar unitTyCon
  949 
  950 Why? Because F might have kind (* -> Constraint), so we when parsing we
  951 don't know if that tuple is going to be a constraint tuple or an ordinary
  952 unit tuple.  The HsTupleSort flag is specifically designed to deal with
  953 that, but it has to work for unit tuples too.
  954 
  955 Note [Promotions (HsTyVar)]
  956 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  957 HsTyVar: A name in a type or kind.
  958   Here are the allowed namespaces for the name.
  959     In a type:
  960       Var: not allowed
  961       Data: promoted data constructor
  962       Tv: type variable
  963       TcCls before renamer: type constructor, class constructor, or promoted data constructor
  964       TcCls after renamer: type constructor or class constructor
  965     In a kind:
  966       Var, Data: not allowed
  967       Tv: kind variable
  968       TcCls: kind constructor or promoted type constructor
  969 
  970   The 'Promoted' field in an HsTyVar captures whether the type was promoted in
  971   the source code by prefixing an apostrophe.
  972 
  973 Note [HsStarTy]
  974 ~~~~~~~~~~~~~~~
  975 When the StarIsType extension is enabled, we want to treat '*' and its Unicode
  976 variant identically to 'Data.Kind.Type'. Unfortunately, doing so in the parser
  977 would mean that when we pretty-print it back, we don't know whether the user
  978 wrote '*' or 'Type', and lose the parse/ppr roundtrip property.
  979 
  980 As a workaround, we parse '*' as HsStarTy (if it stands for 'Data.Kind.Type')
  981 and then desugar it to 'Data.Kind.Type' in the typechecker (see tc_hs_type).
  982 When '*' is a regular type operator (StarIsType is disabled), HsStarTy is not
  983 involved.
  984 
  985 
  986 Note [Promoted lists and tuples]
  987 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  988 Notice the difference between
  989    HsListTy    HsExplicitListTy
  990    HsTupleTy   HsExplicitListTupleTy
  991 
  992 E.g.    f :: [Int]                      HsListTy
  993 
  994         g3  :: T '[]                   All these use
  995         g2  :: T '[True]                  HsExplicitListTy
  996         g1  :: T '[True,False]
  997         g1a :: T [True,False]             (can omit ' where unambiguous)
  998 
  999   kind of T :: [Bool] -> *        This kind uses HsListTy!
 1000 
 1001 E.g.    h :: (Int,Bool)                 HsTupleTy; f is a pair
 1002         k :: S '(True,False)            HsExplicitTypleTy; S is indexed by
 1003                                            a type-level pair of booleans
 1004         kind of S :: (Bool,Bool) -> *   This kind uses HsExplicitTupleTy
 1005 
 1006 Note [Distinguishing tuple kinds]
 1007 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1008 
 1009 Apart from promotion, tuples can have one of three different kinds:
 1010 
 1011         x :: (Int, Bool)                -- Regular boxed tuples
 1012         f :: Int# -> (# Int#, Int# #)   -- Unboxed tuples
 1013         g :: (Eq a, Ord a) => a         -- Constraint tuples
 1014 
 1015 For convenience, internally we use a single constructor for all of these,
 1016 namely HsTupleTy, but keep track of the tuple kind (in the first argument to
 1017 HsTupleTy, a HsTupleSort). We can tell if a tuple is unboxed while parsing,
 1018 because of the #. However, with -XConstraintKinds we can only distinguish
 1019 between constraint and boxed tuples during type checking, in general. Hence the
 1020 two constructors of HsTupleSort:
 1021 
 1022         HsUnboxedTuple                  -> Produced by the parser
 1023         HsBoxedOrConstraintTuple        -> Could be a boxed or a constraint
 1024                                         tuple. Produced by the parser only,
 1025                                         disappears after type checking
 1026 
 1027 After typechecking, we use TupleSort (which clearly distinguishes between
 1028 constraint tuples and boxed tuples) rather than HsTupleSort.
 1029 -}
 1030 
 1031 -- | Haskell Tuple Sort
 1032 data HsTupleSort = HsUnboxedTuple
 1033                  | HsBoxedOrConstraintTuple
 1034                  deriving Data
 1035 
 1036 -- | Located Constructor Declaration Field
 1037 type LConDeclField pass = XRec pass (ConDeclField pass)
 1038       -- ^ May have 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnComma' when
 1039       --   in a list
 1040 
 1041       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
 1042 
 1043 -- | Constructor Declaration Field
 1044 data ConDeclField pass  -- Record fields have Haddock docs on them
 1045   = ConDeclField { cd_fld_ext  :: XConDeclField pass,
 1046                    cd_fld_names :: [LFieldOcc pass],
 1047                                    -- ^ See Note [ConDeclField passs]
 1048                    cd_fld_type :: LBangType pass,
 1049                    cd_fld_doc  :: Maybe LHsDocString }
 1050       -- ^ - 'GHC.Parser.Annotation.AnnKeywordId' : 'GHC.Parser.Annotation.AnnDcolon'
 1051 
 1052       -- For details on above see note [exact print annotations] in GHC.Parser.Annotation
 1053   | XConDeclField !(XXConDeclField pass)
 1054 
 1055 -- | Describes the arguments to a data constructor. This is a common
 1056 -- representation for several constructor-related concepts, including:
 1057 --
 1058 -- * The arguments in a Haskell98-style constructor declaration
 1059 --   (see 'HsConDeclH98Details' in "GHC.Hs.Decls").
 1060 --
 1061 -- * The arguments in constructor patterns in @case@/function definitions
 1062 --   (see 'HsConPatDetails' in "GHC.Hs.Pat").
 1063 --
 1064 -- * The left-hand side arguments in a pattern synonym binding
 1065 --   (see 'HsPatSynDetails' in "GHC.Hs.Binds").
 1066 --
 1067 -- One notable exception is the arguments in a GADT constructor, which uses
 1068 -- a separate data type entirely (see 'HsConDeclGADTDetails' in
 1069 -- "GHC.Hs.Decls"). This is because GADT constructors cannot be declared with
 1070 -- infix syntax, unlike the concepts above (#18844).
 1071 data HsConDetails tyarg arg rec
 1072   = PrefixCon [tyarg] [arg]     -- C @t1 @t2 p1 p2 p3
 1073   | RecCon    rec               -- C { x = p1, y = p2 }
 1074   | InfixCon  arg arg           -- p1 `C` p2
 1075   deriving Data
 1076 
 1077 -- | An empty list that can be used to indicate that there are no
 1078 -- type arguments allowed in cases where HsConDetails is applied to Void.
 1079 noTypeArgs :: [Void]
 1080 noTypeArgs = []
 1081 
 1082 instance (Outputable tyarg, Outputable arg, Outputable rec)
 1083          => Outputable (HsConDetails tyarg arg rec) where
 1084   ppr (PrefixCon tyargs args) = text "PrefixCon:" <+> hsep (map (\t -> text "@" <> ppr t) tyargs) <+> ppr args
 1085   ppr (RecCon rec)            = text "RecCon:" <+> ppr rec
 1086   ppr (InfixCon l r)          = text "InfixCon:" <+> ppr [l, r]
 1087 
 1088 {-
 1089 Note [ConDeclField passs]
 1090 ~~~~~~~~~~~~~~~~~~~~~~~~~
 1091 
 1092 A ConDeclField contains a list of field occurrences: these always
 1093 include the field label as the user wrote it.  After the renamer, it
 1094 will additionally contain the identity of the selector function in the
 1095 second component.
 1096 
 1097 Due to DuplicateRecordFields, the OccName of the selector function
 1098 may have been mangled, which is why we keep the original field label
 1099 separately.  For example, when DuplicateRecordFields is enabled
 1100 
 1101     data T = MkT { x :: Int }
 1102 
 1103 gives
 1104 
 1105     ConDeclField { cd_fld_names = [L _ (FieldOcc "x" $sel:x:MkT)], ... }.
 1106 -}
 1107 
 1108 -----------------------
 1109 -- A valid type must have a for-all at the top of the type, or of the fn arg
 1110 -- types
 1111 
 1112 ---------------------
 1113 
 1114 {- Note [Scoping of named wildcards]
 1115 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1116 Consider
 1117   f :: _a -> _a
 1118   f x = let g :: _a -> _a
 1119             g = ...
 1120         in ...
 1121 
 1122 Currently, for better or worse, the "_a" variables are all the same. So
 1123 although there is no explicit forall, the "_a" scopes over the definition.
 1124 I don't know if this is a good idea, but there it is.
 1125 -}
 1126 
 1127 {- Note [hsScopedTvs and visible foralls]
 1128 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1129 -XScopedTypeVariables can be defined in terms of a desugaring to
 1130 -XTypeAbstractions (GHC Proposal #50):
 1131 
 1132     fn :: forall a b c. tau(a,b,c)            fn :: forall a b c. tau(a,b,c)
 1133     fn = defn(a,b,c)                   ==>    fn @x @y @z = defn(x,y,z)
 1134 
 1135 That is, for every type variable of the leading 'forall' in the type signature,
 1136 we add an invisible binder at term level.
 1137 
 1138 This model does not extend to visible forall, as discussed here:
 1139 
 1140 * https://gitlab.haskell.org/ghc/ghc/issues/16734#note_203412
 1141 * https://github.com/ghc-proposals/ghc-proposals/pull/238
 1142 
 1143 The conclusion of these discussions can be summarized as follows:
 1144 
 1145   > Assuming support for visible 'forall' in terms, consider this example:
 1146   >
 1147   >     vfn :: forall x y -> tau(x,y)
 1148   >     vfn = \a b -> ...
 1149   >
 1150   > The user has written their own binders 'a' and 'b' to stand for 'x' and
 1151   > 'y', and we definitely should not desugar this into:
 1152   >
 1153   >     vfn :: forall x y -> tau(x,y)
 1154   >     vfn x y = \a b -> ...         -- bad!
 1155 
 1156 This design choice is reflected in the design of HsOuterSigTyVarBndrs, which are
 1157 used in every place that ScopedTypeVariables takes effect:
 1158 
 1159   data HsOuterTyVarBndrs flag pass
 1160     = HsOuterImplicit { ... }
 1161     | HsOuterExplicit { ..., hso_bndrs :: [LHsTyVarBndr flag pass] }
 1162     | ...
 1163   type HsOuterSigTyVarBndrs = HsOuterTyVarBndrs Specificity
 1164 
 1165 The HsOuterExplicit constructor is only used in type signatures with outermost,
 1166 /invisible/ 'forall's. Any other type—including those with outermost,
 1167 /visible/ 'forall's—will use HsOuterImplicit. Therefore, when we determine
 1168 which type variables to bring into scope over the body of a function
 1169 (in hsScopedTvs), we /only/ bring the type variables bound by the hso_bndrs in
 1170 an HsOuterExplicit into scope. If we have an HsOuterImplicit instead, then we
 1171 do not bring any type variables into scope over the body of a function at all.
 1172 
 1173 At the moment, GHC does not support visible 'forall' in terms. Nevertheless,
 1174 it is still possible to write erroneous programs that use visible 'forall's in
 1175 terms, such as this example:
 1176 
 1177     x :: forall a -> a -> a
 1178     x = x
 1179 
 1180 Previous versions of GHC would bring `a` into scope over the body of `x` in the
 1181 hopes that the typechecker would error out later
 1182 (see `GHC.Tc.Validity.vdqAllowed`). However, this can wreak havoc in the
 1183 renamer before GHC gets to that point (see #17687 for an example of this).
 1184 Bottom line: nip problems in the bud by refraining from bringing any type
 1185 variables in an HsOuterImplicit into scope over the body of a function, even
 1186 if they correspond to a visible 'forall'.
 1187 -}
 1188 
 1189 {-
 1190 ************************************************************************
 1191 *                                                                      *
 1192                 Decomposing HsTypes
 1193 *                                                                      *
 1194 ************************************************************************
 1195 -}
 1196 
 1197 -- Arguments in an expression/type after splitting
 1198 data HsArg tm ty
 1199   = HsValArg tm   -- Argument is an ordinary expression     (f arg)
 1200   | HsTypeArg SrcSpan ty -- Argument is a visible type application (f @ty)
 1201                          -- SrcSpan is location of the `@`
 1202   | HsArgPar SrcSpan -- See Note [HsArgPar]
 1203 
 1204 numVisibleArgs :: [HsArg tm ty] -> Arity
 1205 numVisibleArgs = count is_vis
 1206   where is_vis (HsValArg _) = True
 1207         is_vis _            = False
 1208 
 1209 -- type level equivalent
 1210 type LHsTypeArg p = HsArg (LHsType p) (LHsKind p)
 1211 
 1212 -- | @'pprHsArgsApp' id fixity args@ pretty-prints an application of @id@
 1213 -- to @args@, using the @fixity@ to tell whether @id@ should be printed prefix
 1214 -- or infix. Examples:
 1215 --
 1216 -- @
 1217 -- pprHsArgsApp T Prefix [HsTypeArg Bool, HsValArg Int]                        = T \@Bool Int
 1218 -- pprHsArgsApp T Prefix [HsTypeArg Bool, HsArgPar, HsValArg Int]              = (T \@Bool) Int
 1219 -- pprHsArgsApp (++) Infix [HsValArg Char, HsValArg Double]                    = Char ++ Double
 1220 -- pprHsArgsApp (++) Infix [HsValArg Char, HsValArg Double, HsVarArg Ordering] = (Char ++ Double) Ordering
 1221 -- @
 1222 pprHsArgsApp :: (OutputableBndr id, Outputable tm, Outputable ty)
 1223              => id -> LexicalFixity -> [HsArg tm ty] -> SDoc
 1224 pprHsArgsApp thing fixity (argl:argr:args)
 1225   | Infix <- fixity
 1226   = let pp_op_app = hsep [ ppr_single_hs_arg argl
 1227                          , pprInfixOcc thing
 1228                          , ppr_single_hs_arg argr ] in
 1229     case args of
 1230       [] -> pp_op_app
 1231       _  -> ppr_hs_args_prefix_app (parens pp_op_app) args
 1232 
 1233 pprHsArgsApp thing _fixity args
 1234   = ppr_hs_args_prefix_app (pprPrefixOcc thing) args
 1235 
 1236 -- | Pretty-print a prefix identifier to a list of 'HsArg's.
 1237 ppr_hs_args_prefix_app :: (Outputable tm, Outputable ty)
 1238                         => SDoc -> [HsArg tm ty] -> SDoc
 1239 ppr_hs_args_prefix_app acc []         = acc
 1240 ppr_hs_args_prefix_app acc (arg:args) =
 1241   case arg of
 1242     HsValArg{}  -> ppr_hs_args_prefix_app (acc <+> ppr_single_hs_arg arg) args
 1243     HsTypeArg{} -> ppr_hs_args_prefix_app (acc <+> ppr_single_hs_arg arg) args
 1244     HsArgPar{}  -> ppr_hs_args_prefix_app (parens acc) args
 1245 
 1246 -- | Pretty-print an 'HsArg' in isolation.
 1247 ppr_single_hs_arg :: (Outputable tm, Outputable ty)
 1248                   => HsArg tm ty -> SDoc
 1249 ppr_single_hs_arg (HsValArg tm)    = ppr tm
 1250 ppr_single_hs_arg (HsTypeArg _ ty) = char '@' <> ppr ty
 1251 -- GHC shouldn't be constructing ASTs such that this case is ever reached.
 1252 -- Still, it's possible some wily user might construct their own AST that
 1253 -- allows this to be reachable, so don't fail here.
 1254 ppr_single_hs_arg (HsArgPar{})     = empty
 1255 
 1256 -- | This instance is meant for debug-printing purposes. If you wish to
 1257 -- pretty-print an application of 'HsArg's, use 'pprHsArgsApp' instead.
 1258 instance (Outputable tm, Outputable ty) => Outputable (HsArg tm ty) where
 1259   ppr (HsValArg tm)     = text "HsValArg"  <+> ppr tm
 1260   ppr (HsTypeArg sp ty) = text "HsTypeArg" <+> ppr sp <+> ppr ty
 1261   ppr (HsArgPar sp)     = text "HsArgPar"  <+> ppr sp
 1262 {-
 1263 Note [HsArgPar]
 1264 A HsArgPar indicates that everything to the left of this in the argument list is
 1265 enclosed in parentheses together with the function itself. It is necessary so
 1266 that we can recreate the parenthesis structure in the original source after
 1267 typechecking the arguments.
 1268 
 1269 The SrcSpan is the span of the original HsPar
 1270 
 1271 ((f arg1) arg2 arg3) results in an input argument list of
 1272 [HsValArg arg1, HsArgPar span1, HsValArg arg2, HsValArg arg3, HsArgPar span2]
 1273 
 1274 -}
 1275 
 1276 --------------------------------
 1277 
 1278 
 1279 {-
 1280 ************************************************************************
 1281 *                                                                      *
 1282                 FieldOcc
 1283 *                                                                      *
 1284 ************************************************************************
 1285 -}
 1286 
 1287 -- | Located Field Occurrence
 1288 type LFieldOcc pass = XRec pass (FieldOcc pass)
 1289 
 1290 -- | Field Occurrence
 1291 --
 1292 -- Represents an *occurrence* of a field. This may or may not be a
 1293 -- binding occurrence (e.g. this type is used in 'ConDeclField' and
 1294 -- 'RecordPatSynField' which bind their fields, but also in
 1295 -- 'HsRecField' for record construction and patterns, which do not).
 1296 --
 1297 -- We store both the 'RdrName' the user originally wrote, and after
 1298 -- the renamer we use the extension field to store the selector
 1299 -- function.
 1300 data FieldOcc pass
 1301   = FieldOcc {
 1302         foExt :: XCFieldOcc pass
 1303       , foLabel :: XRec pass RdrName -- See Note [Located RdrNames] in Language.Haskell.Syntax.Expr
 1304       }
 1305   | XFieldOcc !(XXFieldOcc pass)
 1306 deriving instance (
 1307     Eq (XRec pass RdrName)
 1308   , Eq (XCFieldOcc pass)
 1309   , Eq (XXFieldOcc pass)
 1310   ) => Eq (FieldOcc pass)
 1311 
 1312 instance Outputable (XRec pass RdrName) => Outputable (FieldOcc pass) where
 1313   ppr = ppr . foLabel
 1314 
 1315 instance (UnXRec pass, OutputableBndr (XRec pass RdrName)) => OutputableBndr (FieldOcc pass) where
 1316   pprInfixOcc  = pprInfixOcc . unXRec @pass . foLabel
 1317   pprPrefixOcc = pprPrefixOcc . unXRec @pass . foLabel
 1318 
 1319 instance (UnXRec pass, OutputableBndr (XRec pass RdrName)) => OutputableBndr (GenLocated SrcSpan (FieldOcc pass)) where
 1320   pprInfixOcc  = pprInfixOcc . unLoc
 1321   pprPrefixOcc = pprPrefixOcc . unLoc
 1322 
 1323 -- | Located Ambiguous Field Occurence
 1324 type LAmbiguousFieldOcc pass = XRec pass (AmbiguousFieldOcc pass)
 1325 
 1326 -- | Ambiguous Field Occurrence
 1327 --
 1328 -- Represents an *occurrence* of a field that is potentially
 1329 -- ambiguous after the renamer, with the ambiguity resolved by the
 1330 -- typechecker.  We always store the 'RdrName' that the user
 1331 -- originally wrote, and store the selector function after the renamer
 1332 -- (for unambiguous occurrences) or the typechecker (for ambiguous
 1333 -- occurrences).
 1334 --
 1335 -- See Note [HsRecField and HsRecUpdField] in "GHC.Hs.Pat".
 1336 -- See Note [Located RdrNames] in "GHC.Hs.Expr".
 1337 data AmbiguousFieldOcc pass
 1338   = Unambiguous (XUnambiguous pass) (LocatedN RdrName)
 1339   | Ambiguous   (XAmbiguous pass)   (LocatedN RdrName)
 1340   | XAmbiguousFieldOcc !(XXAmbiguousFieldOcc pass)
 1341 
 1342 
 1343 {-
 1344 ************************************************************************
 1345 *                                                                      *
 1346 \subsection{Pretty printing}
 1347 *                                                                      *
 1348 ************************************************************************
 1349 -}
 1350 
 1351 instance Outputable HsTyLit where
 1352     ppr = ppr_tylit
 1353 --------------------------
 1354 ppr_tylit :: HsTyLit -> SDoc
 1355 ppr_tylit (HsNumTy source i) = pprWithSourceText source (integer i)
 1356 ppr_tylit (HsStrTy source s) = pprWithSourceText source (text (show s))
 1357 ppr_tylit (HsCharTy source c) = pprWithSourceText source (text (show c))