Implement cstringLength# and FinalPtr

This function and its accompanying rule resolve issue #5218.
A future PR to the bytestring library will make the internal
Data.ByteString.Internal.unsafePackAddress compute string length
with cstringLength#. This will improve the status quo because it is
eligible for constant folding.

Additionally, introduce a new data constructor to ForeignPtrContents
named FinalPtr. This additional data constructor, when used in the
IsString instance for ByteString, leads to more Core-to-Core
optimization opportunities, fewer runtime allocations, and smaller
binaries.

Also, this commit re-exports all the functions from GHC.CString
(including cstringLength#) in GHC.Exts. It also adds a new test
driver. This test driver is used to perform substring matches on Core
that is dumped after all the simplifier passes. In this commit, it is
used to check that constant folding of cstringLength# works.

4 files changed, 205 insertions, 20 deletions

diff --git a/libraries/base/GHC/Exts.hs b/libraries/base/GHC/Exts.hs
index 894ffad509..8f878b813b 100755
--- a/libraries/base/GHC/Exts.hs
+++ b/libraries/base/GHC/Exts.hs
@@ -54,6 +54,14 @@ module GHC.Exts
         -- * Overloaded string literals
         IsString(..),
 
+        -- * CString
+        unpackCString#,
+        unpackAppendCString#,
+        unpackFoldrCString#,
+        unpackCStringUtf8#,
+        unpackNBytes#,
+        cstringLength#,
+
         -- * Debugging
         breakpoint, breakpointCond,
 
diff --git a/libraries/base/GHC/ForeignPtr.hs b/libraries/base/GHC/ForeignPtr.hs
index 92aef540d1..9ba6a2b017 100644
--- a/libraries/base/GHC/ForeignPtr.hs
+++ b/libraries/base/GHC/ForeignPtr.hs
@@ -23,11 +23,13 @@
 
 module GHC.ForeignPtr
   (
+        -- * Types
         ForeignPtr(..),
         ForeignPtrContents(..),
         Finalizers(..),
         FinalizerPtr,
         FinalizerEnvPtr,
+        -- * Create
         newForeignPtr_,
         mallocForeignPtr,
         mallocPlainForeignPtr,
@@ -35,15 +37,20 @@ module GHC.ForeignPtr
         mallocPlainForeignPtrBytes,
         mallocForeignPtrAlignedBytes,
         mallocPlainForeignPtrAlignedBytes,
+        newConcForeignPtr,
+        -- * Add Finalizers
         addForeignPtrFinalizer,
         addForeignPtrFinalizerEnv,
-        touchForeignPtr,
+        addForeignPtrConcFinalizer,
+        -- * Conversion
         unsafeForeignPtrToPtr,
         castForeignPtr,
         plusForeignPtr,
-        newConcForeignPtr,
-        addForeignPtrConcFinalizer,
+        -- * Finalization
+        touchForeignPtr,
         finalizeForeignPtr
+        -- * Commentary
+        -- $commentary
   ) where
 
 import Foreign.Storable
@@ -86,15 +93,121 @@ data ForeignPtr a = ForeignPtr Addr# ForeignPtrContents
         -- object, because that ensures that whatever the finalizer is
         -- attached to is kept alive.
 
+-- | Functions called when a 'ForeignPtr' is finalized. Note that
+-- C finalizers and Haskell finalizers cannot be mixed.
 data Finalizers
   = NoFinalizers
+    -- ^ No finalizer. If there is no intent to add a finalizer at
+    -- any point in the future, consider 'FinalPtr' or 'PlainPtr' instead
+    -- since these perform fewer allocations.
   | CFinalizers (Weak# ())
+    -- ^ Finalizers are all C functions.
   | HaskellFinalizers [IO ()]
+    -- ^ Finalizers are all Haskell functions.
 
+-- | Controls finalization of a 'ForeignPtr', that is, what should happen
+-- if the 'ForeignPtr' becomes unreachable. Visually, these data constructors
+-- are appropriate in these scenarios:
+--
+-- >                           Memory backing pointer is
+-- >                            GC-Managed   Unmanaged
+-- > Finalizer functions are: +------------+-----------------+
+-- >                 Allowed  | MallocPtr  | PlainForeignPtr |
+-- >                          +------------+-----------------+
+-- >              Prohibited  | PlainPtr   | FinalPtr        |
+-- >                          +------------+-----------------+
 data ForeignPtrContents
   = PlainForeignPtr !(IORef Finalizers)
-  | MallocPtr      (MutableByteArray# RealWorld) !(IORef Finalizers)
-  | PlainPtr       (MutableByteArray# RealWorld)
+    -- ^ The pointer refers to unmanaged memory that was allocated by
+    -- a foreign function (typically using @malloc@). The finalizer
+    -- frequently calls the C function @free@ or some variant of it.
+  | FinalPtr
+    -- ^ The pointer refers to unmanaged memory that should not be freed when
+    -- the 'ForeignPtr' becomes unreachable. Functions that add finalizers
+    -- to a 'ForeignPtr' throw exceptions when the 'ForeignPtr' is backed by
+    -- 'PlainPtr'Most commonly, this is used with @Addr#@ literals.
+    -- See Note [Why FinalPtr].
+    --
+    -- @since 4.15
+  | MallocPtr (MutableByteArray# RealWorld) !(IORef Finalizers)
+    -- ^ The pointer refers to a byte array.
+    -- The 'MutableByteArray#' field means that the 'MutableByteArray#' is
+    -- reachable (by GC) whenever the 'ForeignPtr' is reachable. When the
+    -- 'ForeignPtr' becomes unreachable, the runtime\'s normal GC recovers
+    -- the memory backing it. Here, the finalizer function intended to be used
+    -- to @free()@ any ancilliary *unmanaged* memory pointed to by the
+    -- 'MutableByteArray#'. See the @zlib@ library for an example of this use.
+    --
+    -- 1. Invariant: The 'Addr#' in the parent 'ForeignPtr' is an interior
+    --    pointer into this 'MutableByteArray#'.
+    -- 2. Invariant: The 'MutableByteArray#' is pinned, so the 'Addr#' does not
+    --    get invalidated by the GC moving the byte array.
+    -- 3. Invariant: A 'MutableByteArray#' must not be associated with more than
+    --    one set of finalizers. For example, this is sound:
+    --
+    --    > incrGood :: ForeignPtr Word8 -> ForeignPtr Word8
+    --    > incrGood (ForeignPtr p (MallocPtr m f)) = ForeignPtr (plusPtr p 1) (MallocPtr m f)
+    --
+    --    But this is unsound:
+    --
+    --    > incrBad :: ForeignPtr Word8 -> IO (ForeignPtr Word8)
+    --    > incrBad (ForeignPtr p (MallocPtr m _)) = do
+    --    >   f <- newIORef NoFinalizers
+    --    >   pure (ForeignPtr p (MallocPtr m f))
+  | PlainPtr (MutableByteArray# RealWorld)
+    -- ^ The pointer refers to a byte array. Finalization is not
+    -- supported. This optimizes @MallocPtr@ by avoiding the allocation
+    -- of a @MutVar#@ when it is known that no one will add finalizers to
+    -- the @ForeignPtr@. Functions that add finalizers to a 'ForeignPtr'
+    -- throw exceptions when the 'ForeignPtr' is backed by 'PlainPtr'.
+    -- The invariants that apply to 'MallocPtr' apply to 'PlainPtr' as well.
+
+-- Note [Why FinalPtr]
+--
+-- FinalPtr exists as an optimization for foreign pointers created
+-- from Addr# literals. Most commonly, this happens in the bytestring
+-- library, where the combination of OverloadedStrings and a rewrite
+-- rule overloads String literals as ByteString literals. See the
+-- rule "ByteString packChars/packAddress" in
+-- bytestring:Data.ByteString.Internal. Prior to the
+-- introduction of FinalPtr, bytestring used PlainForeignPtr (in
+-- Data.ByteString.Internal.unsafePackAddress) to handle such literals.
+-- With O2 optimization, the resulting Core from a GHC patched with a
+-- known-key cstringLength# function but without FinalPtr looked like:
+--
+--   RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0}
+--   stringOne1 = "hello beautiful world"#
+--   RHS size: {terms: 11, types: 17, coercions: 0, joins: 0/0}
+--   stringOne
+--     = case newMutVar# NoFinalizers realWorld# of
+--       { (# ipv_i7b6, ipv1_i7b7 #) ->
+--       PS stringOne1 (PlainForeignPtr ipv1_i7b7) 0# 21#
+--       }
+--
+-- After the introduction of FinalPtr, the bytestring library was modified
+-- so that the resulting Core was instead:
+--
+--   RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0}
+--   stringOne1 = "hello beautiful world"#
+--   RHS size: {terms: 5, types: 0, coercions: 0, joins: 0/0}
+--   stringOne = PS stringOne1 FinalPtr 0# 21#
+--
+-- This improves performance in three ways:
+--
+-- 1. More optimization opportunities. GHC is willing to inline the FinalPtr
+--    variant of stringOne into its use sites. This means the offset and length
+--    are eligible for case-of-known-literal. Previously, this never happened.
+-- 2. Smaller binaries. Setting up the thunk to call newMutVar# required
+--    machine instruction in the generated code. On x86_64, FinalPtr reduces
+--    the size of binaries by about 450 bytes per ByteString literal.
+-- 3. Smaller memory footprint. Previously, every ByteString literal resulted
+--    in the allocation of a MutVar# and a PlainForeignPtr data constructor.
+--    These both hang around until the ByteString goes out of scope. FinalPtr
+--    eliminates both of these sources of allocations. The MutVar# is not
+--    allocated because FinalPtr does not allow it, and the data constructor
+--    is not allocated because FinalPtr is a nullary data constructor.
+--
+-- For more discussion of FinalPtr, see GHC MR #2165 and bytestring PR #191.
 
 -- | @since 2.01
 instance Eq (ForeignPtr a) where
@@ -259,7 +372,7 @@ addForeignPtrFinalizer :: FinalizerPtr a -> ForeignPtr a -> IO ()
 addForeignPtrFinalizer (FunPtr fp) (ForeignPtr p c) = case c of
   PlainForeignPtr r -> insertCFinalizer r fp 0# nullAddr# p ()
   MallocPtr     _ r -> insertCFinalizer r fp 0# nullAddr# p c
-  _ -> errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to a plain pointer"
+  _ -> errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to a plain pointer or a final pointer"
 
 -- Note [MallocPtr finalizers] (#10904)
 --
@@ -277,7 +390,7 @@ addForeignPtrFinalizerEnv ::
 addForeignPtrFinalizerEnv (FunPtr fp) (Ptr ep) (ForeignPtr p c) = case c of
   PlainForeignPtr r -> insertCFinalizer r fp 1# ep p ()
   MallocPtr     _ r -> insertCFinalizer r fp 1# ep p c
-  _ -> errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to a plain pointer"
+  _ -> errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to a plain pointer or a final pointer"
 
 addForeignPtrConcFinalizer :: ForeignPtr a -> IO () -> IO ()
 -- ^This function adds a finalizer to the given @ForeignPtr@.  The
@@ -319,7 +432,7 @@ addForeignPtrConcFinalizer_ f@(MallocPtr fo r) finalizer = do
     finalizer' = unIO (foreignPtrFinalizer r >> touch f)
 
 addForeignPtrConcFinalizer_ _ _ =
-  errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to plain pointer"
+  errorWithoutStackTrace "GHC.ForeignPtr: attempt to add a finalizer to plain pointer or a final pointer"
 
 insertHaskellFinalizer :: IORef Finalizers -> IO () -> IO Bool
 insertHaskellFinalizer r f = do
@@ -345,6 +458,8 @@ insertCFinalizer r fp flag ep p val = do
       -- replaced the content of r before calling finalizeWeak#.
       (# s1, _ #) -> unIO (insertCFinalizer r fp flag ep p val) s1
 
+-- Read the weak reference from an IORef Finalizers, creating it if necessary.
+-- Throws an exception if HaskellFinalizers is encountered.
 ensureCFinalizerWeak :: IORef Finalizers -> value -> IO MyWeak
 ensureCFinalizerWeak ref@(IORef (STRef r#)) value = do
   fin <- readIORef ref
@@ -370,6 +485,7 @@ noMixingError = errorWithoutStackTrace $
    "GHC.ForeignPtr: attempt to mix Haskell and C finalizers " ++
    "in the same ForeignPtr"
 
+-- Swap out the finalizers with NoFinalizers and then run them.
 foreignPtrFinalizer :: IORef Finalizers -> IO ()
 foreignPtrFinalizer r = do
   fs <- atomicSwapIORef r NoFinalizers
@@ -455,13 +571,53 @@ plusForeignPtr :: ForeignPtr a -> Int -> ForeignPtr b
 plusForeignPtr (ForeignPtr addr c) (I# d) = ForeignPtr (plusAddr# addr d) c
 
 -- | Causes the finalizers associated with a foreign pointer to be run
--- immediately.
+-- immediately. The foreign pointer must not be used again after this
+-- function is called.
 finalizeForeignPtr :: ForeignPtr a -> IO ()
-finalizeForeignPtr (ForeignPtr _ (PlainPtr _)) = return () -- no effect
-finalizeForeignPtr (ForeignPtr _ foreignPtr) = foreignPtrFinalizer refFinalizers
-        where
-                refFinalizers = case foreignPtr of
-                        (PlainForeignPtr ref) -> ref
-                        (MallocPtr     _ ref) -> ref
-                        PlainPtr _            ->
-                            errorWithoutStackTrace "finalizeForeignPtr PlainPtr"
+finalizeForeignPtr (ForeignPtr _ c) = case c of
+  PlainForeignPtr ref -> foreignPtrFinalizer ref
+  MallocPtr _ ref -> foreignPtrFinalizer ref
+  _ -> errorWithoutStackTrace "finalizeForeignPtr PlainPtr"
+
+{- $commentary
+
+This is a high-level overview of how 'ForeignPtr' works.
+The implementation of 'ForeignPtr' must accomplish several goals:
+
+1. Invoke a finalizer once a foreign pointer becomes unreachable.
+2. Support augmentation of finalizers, i.e. 'addForeignPtrFinalizer'.
+   As a motivating example, suppose that the payload of a foreign
+   pointer is C struct @bar@ that has an optionally NULL pointer field
+   @foo@ to an unmanaged heap object. Initially, @foo@ is NULL, and
+   later the program uses @malloc@, initializes the object, and assigns
+   @foo@ the address returned by @malloc@. When the foreign pointer
+   becomes unreachable, it is now necessary to first @free@ the object
+   pointed to by @foo@ and then invoke whatever finalizer was associated
+   with @bar@. That is, finalizers must be invoked in the opposite order
+   they are added.
+3. Allow users to invoke a finalizer promptly if they know that the
+   foreign pointer is unreachable, i.e. 'finalizeForeignPtr'.
+
+How can these goals be accomplished? Goal 1 suggests that weak references
+and finalizers (via 'Weak#' and 'mkWeak#') are necessary. But how should
+they be used and what should their key be?  Certainly not 'ForeignPtr' or
+'ForeignPtrContents'. See the warning in "GHC.Weak" about weak pointers with
+lifted (non-primitive) keys. The two finalizer-supporting data constructors of
+'ForeignPtr' have an @'IORef' 'Finalizers'@ (backed by 'MutVar#') field.
+This gets used in two different ways depending on the kind of finalizer:
+
+* 'HaskellFinalizers': The first @addForeignPtrConcFinalizer_@ call uses
+  'mkWeak#' to attach the finalizer @foreignPtrFinalizer@ to the 'MutVar#'.
+  The resulting 'Weak#' is discarded (see @addForeignPtrConcFinalizer_@).
+  Subsequent calls to @addForeignPtrConcFinalizer_@ (goal 2) just add
+  finalizers onto the list in the 'HaskellFinalizers' data constructor.
+* 'CFinalizers': The first 'addForeignPtrFinalizer' call uses
+  'mkWeakNoFinalizer#' to create a 'Weak#'. The 'Weak#' is preserved in the
+  'CFinalizers' data constructor. Both the first call and subsequent
+  calls (goal 2) use 'addCFinalizerToWeak#' to attach finalizers to the
+  'Weak#' itself. Also, see Note [MallocPtr finalizers] for discussion of
+  the key and value of this 'Weak#'.
+
+In either case, the runtime invokes the appropriate finalizers when the
+'ForeignPtr' becomes unreachable.
+-}
diff --git a/libraries/ghc-prim/GHC/CString.hs b/libraries/ghc-prim/GHC/CString.hs
index 8c0d272a67..514fb0e9f9 100644
--- a/libraries/ghc-prim/GHC/CString.hs
+++ b/libraries/ghc-prim/GHC/CString.hs
@@ -1,5 +1,4 @@
-{-# LANGUAGE MagicHash, NoImplicitPrelude, BangPatterns #-}
-
+{-# LANGUAGE MagicHash, NoImplicitPrelude, BangPatterns, UnliftedFFITypes #-}
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  GHC.CString
@@ -18,7 +17,7 @@
 
 module GHC.CString (
         unpackCString#, unpackAppendCString#, unpackFoldrCString#,
-        unpackCStringUtf8#, unpackNBytes#
+        unpackCStringUtf8#, unpackNBytes#, cstringLength#
     ) where
 
 import GHC.Types
@@ -174,3 +173,17 @@ unpackNBytes#  addr len# = unpack [] (len# -# 1#)
          case indexCharOffAddr# addr i# of
             ch -> unpack (C# ch : acc) (i# -# 1#)
 
+-- The return type is not correct here. We really want CSize,
+-- but that type is defined in base. However, CSize should always
+-- match the size of a machine word (I hope), so this is probably
+-- alright on all platforms that GHC supports.
+foreign import ccall unsafe "strlen" c_strlen :: Addr# -> Int#
+
+-- | Compute the length of a NUL-terminated string. This address
+-- must refer to immutable memory. GHC includes a built-in rule for
+-- constant folding when the argument is a statically-known literal.
+-- That is, a core-to-core pass reduces the expression
+-- @cstringLength# "hello"#@ to the constant @5#@.
+cstringLength# :: Addr# -> Int#
+{-# INLINE[0] cstringLength# #-}
+cstringLength# = c_strlen
diff --git a/libraries/ghc-prim/changelog.md b/libraries/ghc-prim/changelog.md
index cf14d21c81..9cfbe99dbe 100644
--- a/libraries/ghc-prim/changelog.md
+++ b/libraries/ghc-prim/changelog.md
@@ -1,3 +1,11 @@
+## 0.6.2 (edit as necessary)
+
+- Shipped with GHC 8.12.1
+
+- Add known-key `cstringLength#` to `GHC.CString`. This is just the
+  C function `strlen`, but a built-in rewrite rule allows GHC to
+  compute the result at compile time when the argument is known.
+
 ## 0.6.1 (edit as necessary)
 
 - Shipped with GHC 8.10.1