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.

1 files changed, 11 insertions, 7 deletions

diff --git a/compiler/GHC/Core/Subst.hs b/compiler/GHC/Core/Subst.hs
index ddb5b61f7b..f2b25e17e5 100644
--- a/compiler/GHC/Core/Subst.hs
+++ b/compiler/GHC/Core/Subst.hs
@@ -476,11 +476,12 @@ substIdBndr _doc rec_subst subst@(Subst in_scope env tvs cvs) old_id
   where
     id1 = uniqAway in_scope old_id      -- id1 is cloned if necessary
     id2 | no_type_change = id1
-        | otherwise      = setIdType id1 (substTy subst old_ty)
+        | otherwise      = updateIdTypeAndMult (substTy subst) id1
 
     old_ty = idType old_id
+    old_w = idMult old_id
     no_type_change = (isEmptyVarEnv tvs && isEmptyVarEnv cvs) ||
-                     noFreeVarsOfType old_ty
+                     (noFreeVarsOfType old_ty && noFreeVarsOfType old_w)
 
         -- new_id has the right IdInfo
         -- The lazy-set is because we're in a loop here, with
@@ -600,13 +601,16 @@ substCo subst co = Coercion.substCo (getTCvSubst subst) co
 
 substIdType :: Subst -> Id -> Id
 substIdType subst@(Subst _ _ tv_env cv_env) id
-  | (isEmptyVarEnv tv_env && isEmptyVarEnv cv_env) || noFreeVarsOfType old_ty = id
-  | otherwise   = setIdType id (substTy subst old_ty)
-                -- The tyCoVarsOfType is cheaper than it looks
-                -- because we cache the free tyvars of the type
-                -- in a Note in the id's type itself
+  | (isEmptyVarEnv tv_env && isEmptyVarEnv cv_env)
+    || (noFreeVarsOfType old_ty && noFreeVarsOfType old_w) = id
+  | otherwise   =
+      updateIdTypeAndMult (substTy subst) id
+        -- The tyCoVarsOfType is cheaper than it looks
+        -- because we cache the free tyvars of the type
+        -- in a Note in the id's type itself
   where
     old_ty = idType id
+    old_w  = varMult id
 
 ------------------
 -- | Substitute into some 'IdInfo' with regard to the supplied new 'Id'.