Add native delimited continuations to the RTS

This patch implements GHC proposal 313, "Delimited continuation
primops", by adding native support for delimited continuations to the
GHC RTS.

All things considered, the patch is relatively small. It almost
exclusively consists of changes to the RTS; the compiler itself is
essentially unaffected. The primops come with fairly extensive Haddock
documentation, and an overview of the implementation strategy is given
in the Notes in rts/Continuation.c.

This first stab at the implementation prioritizes simplicity over
performance. Most notably, every continuation is always stored as a
single, contiguous chunk of stack. If one of these chunks is
particularly large, it can result in poor performance, as the current
implementation does not attempt to cleverly squeeze a subset of the
stack frames into the existing stack: it must fit all at once. If this
proves to be a performance issue in practice, a cleverer strategy would
be a worthwhile target for future improvements.

4 files changed, 29 insertions, 1 deletions

diff --git a/libraries/base/Control/Exception/Base.hs b/libraries/base/Control/Exception/Base.hs
index 3cc6a24433..c2c675c65d 100644
--- a/libraries/base/Control/Exception/Base.hs
+++ b/libraries/base/Control/Exception/Base.hs
@@ -42,6 +42,7 @@ module Control.Exception.Base (
         RecUpdError(..),
         ErrorCall(..),
         TypeError(..), -- #10284, custom error type for deferred type errors
+        NoMatchingContinuationPrompt(..),
 
         -- * Throwing exceptions
         throwIO,
@@ -96,7 +97,7 @@ module Control.Exception.Base (
         recSelError, recConError, runtimeError,
         nonExhaustiveGuardsError, patError, noMethodBindingError,
         typeError,
-        nonTermination, nestedAtomically,
+        nonTermination, nestedAtomically, noMatchingContinuationPrompt,
   ) where
 
 import           GHC.Base
@@ -391,6 +392,22 @@ instance Exception NestedAtomically
 
 -----
 
+-- | Thrown when the program attempts a continuation capture, but no prompt with
+-- the given prompt tag exists in the current continuation.
+--
+-- @since 4.18
+data NoMatchingContinuationPrompt = NoMatchingContinuationPrompt
+
+-- | @since 4.18
+instance Show NoMatchingContinuationPrompt where
+  showsPrec _ NoMatchingContinuationPrompt =
+    showString "GHC.Exts.control0#: no matching prompt in the current continuation"
+
+-- | @since 4.18
+instance Exception NoMatchingContinuationPrompt
+
+-----
+
 -- See Note [Compiler error functions] in ghc-prim:GHC.Prim.Panic
 recSelError, recConError, runtimeError,
   nonExhaustiveGuardsError, patError, noMethodBindingError,
@@ -414,3 +431,7 @@ nonTermination = toException NonTermination
 -- GHC's RTS calls this
 nestedAtomically :: SomeException
 nestedAtomically = toException NestedAtomically
+
+-- GHC's RTS calls this
+noMatchingContinuationPrompt :: SomeException
+noMatchingContinuationPrompt = toException NoMatchingContinuationPrompt
diff --git a/libraries/base/GHC/Exts.hs b/libraries/base/GHC/Exts.hs
index f5b2498542..90a37be35b 100755
--- a/libraries/base/GHC/Exts.hs
+++ b/libraries/base/GHC/Exts.hs
@@ -59,6 +59,7 @@ module GHC.Exts
         sameMutVar#,
         sameTVar#,
         sameIOPort#,
+        samePromptTag#,
 
         -- ** Compat wrapper
         atomicModifyMutVar#,
diff --git a/libraries/ghc-heap/GHC/Exts/Heap/ClosureTypes.hs b/libraries/ghc-heap/GHC/Exts/Heap/ClosureTypes.hs
index 5eefe02d0d..70da80d66b 100644
--- a/libraries/ghc-heap/GHC/Exts/Heap/ClosureTypes.hs
+++ b/libraries/ghc-heap/GHC/Exts/Heap/ClosureTypes.hs
@@ -80,6 +80,7 @@ data ClosureType
     | SMALL_MUT_ARR_PTRS_FROZEN_DIRTY
     | SMALL_MUT_ARR_PTRS_FROZEN_CLEAN
     | COMPACT_NFDATA
+    | CONTINUATION
     | N_CLOSURE_TYPES
  deriving (Enum, Eq, Ord, Show, Generic)
 
diff --git a/libraries/ghc-prim/GHC/Prim/PtrEq.hs b/libraries/ghc-prim/GHC/Prim/PtrEq.hs
index 34285a879a..49e78b1713 100644
--- a/libraries/ghc-prim/GHC/Prim/PtrEq.hs
+++ b/libraries/ghc-prim/GHC/Prim/PtrEq.hs
@@ -30,6 +30,7 @@ module GHC.Prim.PtrEq
     sameTVar#,
     sameMVar#,
     sameIOPort#,
+    samePromptTag#,
     eqStableName#
   ) where
 
@@ -113,6 +114,10 @@ sameMVar# = reallyUnsafePtrEquality#
 sameIOPort# :: IOPort# s a -> IOPort# s a -> Int#
 sameIOPort# = reallyUnsafePtrEquality#
 
+-- | Compare the underlying pointers of two 'PromptTag#'s.
+samePromptTag# :: PromptTag# a -> PromptTag# a -> Int#
+samePromptTag# = reallyUnsafePtrEquality#
+
 -- Note [Comparing stable names]
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 -- A StableName# is actually a pointer to a stable name object (SNO)