Linear types (#15981)

This is the first step towards implementation of the linear types proposal
(https://github.com/ghc-proposals/ghc-proposals/pull/111).

It features

* A language extension -XLinearTypes
* Syntax for linear functions in the surface language
* Linearity checking in Core Lint, enabled with -dlinear-core-lint
* Core-to-core passes are mostly compatible with linearity
* Fields in a data type can be linear or unrestricted; linear fields
  have multiplicity-polymorphic constructors.
  If -XLinearTypes is disabled, the GADT syntax defaults to linear fields

The following items are not yet supported:

* a # m -> b syntax (only prefix FUN is supported for now)
* Full multiplicity inference (multiplicities are really only checked)
* Decent linearity error messages
* Linear let, where, and case expressions in the surface language
  (each of these currently introduce the unrestricted variant)
* Multiplicity-parametric fields
* Syntax for annotating lambda-bound or let-bound with a multiplicity
* Syntax for non-linear/multiple-field-multiplicity records
* Linear projections for records with a single linear field
* Linear pattern synonyms
* Multiplicity coercions (test LinearPolyType)

A high-level description can be found at
https://ghc.haskell.org/trac/ghc/wiki/LinearTypes/Implementation
Following the link above you will find a description of the changes made to Core.
This commit has been authored by

* Richard Eisenberg
* Krzysztof Gogolewski
* Matthew Pickering
* Arnaud Spiwack

With contributions from:

* Mark Barbone
* Alexander Vershilov

Updates haddock submodule.

2 files changed, 13 insertions, 6 deletions

diff --git a/compiler/GHC/Parser/Lexer.x b/compiler/GHC/Parser/Lexer.x
index 6778d5aa3f..2df6400a19 100644
--- a/compiler/GHC/Parser/Lexer.x
+++ b/compiler/GHC/Parser/Lexer.x
@@ -762,6 +762,7 @@ data Token
   | ITvbar
   | ITlarrow            IsUnicodeSyntax
   | ITrarrow            IsUnicodeSyntax
+  | ITlolly             IsUnicodeSyntax
   | ITdarrow            IsUnicodeSyntax
   | ITminus
   | ITbang     -- Prefix (!) only, e.g. f !x = rhs
@@ -984,6 +985,9 @@ reservedSymsFM = listToUFM $
        ,("→",   ITrarrow UnicodeSyntax,     UnicodeSyntax, 0 )
        ,("←",   ITlarrow UnicodeSyntax,     UnicodeSyntax, 0 )
 
+       ,("#->", ITlolly NormalSyntax, NormalSyntax, 0)
+       ,("⊸",   ITlolly UnicodeSyntax, UnicodeSyntax, 0)
+
        ,("⤙",   ITlarrowtail UnicodeSyntax, UnicodeSyntax, xbit ArrowsBit)
        ,("⤚",   ITrarrowtail UnicodeSyntax, UnicodeSyntax, xbit ArrowsBit)
        ,("⤛",   ITLarrowtail UnicodeSyntax, UnicodeSyntax, xbit ArrowsBit)
@@ -2475,6 +2479,7 @@ data ExtBits
   | MultiWayIfBit
   | GadtSyntaxBit
   | ImportQualifiedPostBit
+  | LinearTypesBit
 
   -- Flags that are updated once parsing starts
   | InRulePragBit
@@ -2561,6 +2566,7 @@ mkParserFlags' warningFlags extensionFlags homeUnitId
       .|. MultiWayIfBit               `xoptBit` LangExt.MultiWayIf
       .|. GadtSyntaxBit               `xoptBit` LangExt.GADTSyntax
       .|. ImportQualifiedPostBit      `xoptBit` LangExt.ImportQualifiedPost
+      .|. LinearTypesBit              `xoptBit` LangExt.LinearTypes
     optBits =
           HaddockBit        `setBitIf` isHaddock
       .|. RawTokenStreamBit `setBitIf` rawTokStream
diff --git a/compiler/GHC/Parser/PostProcess.hs b/compiler/GHC/Parser/PostProcess.hs
index 645f56fc54..018ce7bb60 100644
--- a/compiler/GHC/Parser/PostProcess.hs
+++ b/compiler/GHC/Parser/PostProcess.hs
@@ -115,7 +115,7 @@ import GHC.Types.Name
 import GHC.Types.Basic
 import GHC.Parser.Lexer
 import GHC.Utils.Lexeme ( isLexCon )
-import GHC.Core.Type    ( TyThing(..), funTyCon, Specificity(..) )
+import GHC.Core.Type    ( TyThing(..), unrestrictedFunTyCon, Specificity(..) )
 import GHC.Builtin.Types( cTupleTyConName, tupleTyCon, tupleDataCon,
                           nilDataConName, nilDataConKey,
                           listTyConName, listTyConKey, eqTyCon_RDR,
@@ -710,7 +710,7 @@ mkGadtDecl names ty
   where
     mb_record_gadt ty
       | (mtvs, mcxt, body_ty) <- splitLHsGADTPrefixTy ty
-      , L _ (HsFunTy _ (L loc (HsRecTy _ rf)) res_ty) <- body_ty
+      , L _ (HsFunTy _ _w (L loc (HsRecTy _ rf)) res_ty) <- body_ty
       = Just (mtvs, mcxt, RecCon (L loc rf), res_ty)
       | otherwise
       = Nothing
@@ -1650,7 +1650,7 @@ mergeDataCon all_xs =
     goFirst [L l (TyElOpd (HsTupleTy _ HsBoxedOrConstraintTuple ts))]
       = return ( pure ()
                , ( L l (getRdrName (tupleDataCon Boxed (length ts)))
-                 , PrefixCon ts
+                 , PrefixCon (map hsLinear ts)
                  , mTrailingDoc ) )
     goFirst ((L l (TyElOpd t)):xs)
       | (_, t', addAnns, xs') <- pBangTy (L l t) xs
@@ -1662,7 +1662,7 @@ mergeDataCon all_xs =
 
     go addAnns mLastDoc ts [ L l (TyElOpd (HsTyVar _ _ (L _ tc))) ]
       = do { data_con <- tyConToDataCon l tc
-           ; return (addAnns, (data_con, PrefixCon ts, mkConDoc mLastDoc)) }
+           ; return (addAnns, (data_con, PrefixCon (map hsLinear ts), mkConDoc mLastDoc)) }
     go addAnns mLastDoc ts ((L l (TyElDocPrev doc)):xs) =
       go addAnns (mLastDoc `mplus` Just (L l doc)) ts xs
     go addAnns mLastDoc ts ((L l (TyElOpd t)):xs)
@@ -1697,7 +1697,7 @@ mergeDataCon all_xs =
          ; let rhs = mkLHsDocTyMaybe rhs_t trailingFieldDoc
                lhs = mkLHsDocTyMaybe lhs_t mLhsDoc
                addAnns = lhs_addAnns >> rhs_addAnns
-         ; return (addAnns, (op, InfixCon lhs rhs, mkConDoc mOpDoc)) }
+         ; return (addAnns, (op, InfixCon (hsLinear lhs) (hsLinear rhs), mkConDoc mOpDoc)) }
       where
         malformedErr =
           ( foldr combineSrcSpans noSrcSpan (map getLoc all_xs')
@@ -2565,8 +2565,9 @@ checkPrecP (L l (_,i)) (L _ ol)
  | all specialOp ol = pure ()
  | otherwise = addFatalError l (text ("Precedence out of range: " ++ show i))
   where
+    -- If you change this, consider updating Note [Fixity of (->)] in GHC/Types.hs
     specialOp op = unLoc op `elem` [ eqTyCon_RDR
-                                   , getRdrName funTyCon ]
+                                   , getRdrName unrestrictedFunTyCon ]
 
 mkRecConstrOrUpdate
         :: LHsExpr GhcPs