`copilot-theorem`: Support translating struct updates to `what4`

[RyanGlScott]

Copilot 3.20 added support for struct updates via the new UpdateField operation. At the moment, there is no support on the copilot-theorem side for translating UpdateField operations into equivalent what4 expressions. For example, this means that the following Copilot specification will fail when executed:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE NoImplicitPrelude #-}
module Main (main) where

import Data.Foldable (for_)
import Data.Functor (void)
import Data.Word (Word32)

import qualified Copilot.Theorem.What4 as CT
import Language.Copilot

data S = S
  { unS :: Field "unS" Word32
  }

instance Struct S where
  typeName _ = "s"
  toValues s = [Value typeOf (unS s)]

instance Typed S where
  typeOf = Struct (S (Field 0))

spec :: Spec
spec = do
  let externS :: Stream S
      externS = extern "extern_s" Nothing

      example :: Stream Word32
      example = (externS ## unS =: 42) # unS

  void $ prop "example" (forAll $ example == example)

main :: IO ()
main = do
  spec' <- reify spec

  -- Use Z3 to prove the properties.
  results <- CT.prove CT.Z3 spec'

  -- Print the results.
  for_ results $ \(nm, res) -> do
    putStr $ nm <> ": "
    case res of
      CT.Valid -> putStrLn "valid"
      CT.Invalid -> putStrLn "invalid"
      CT.Unknown -> putStrLn "unknown"

$ runghc UpdateField.hs 
UpdateField.hs: src/Copilot/Theorem/What4/Translate.hs:(707,40)-(802,2): Non-exhaustive patterns in case

This limitation currently blocks copilot-verifier support for struct updates, as copilot-verifier makes us of copilot-theorem's what4 translation capabilities.

I have a prototype implementation in this branch which could be used as a starting point for a patch.

[ivanperez-keera]

Description

Copilot currently supports modifying values from streams of structs, but not reasoning about them using copilot-theorem.

Type

• Bug: exception produced when executing valid specification.

Additional context

• Issue copilot-language: Support modifying fields of structs #520 introduced support for modifying structs.

Requester

• Ryan Scott (Galois)

Method to check presence of bug

Running the following specification that tries to assert a trivial equality:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE NoImplicitPrelude #-}
module Main (main) where

import Data.Foldable (for_)
import Data.Functor (void)
import Data.Word (Word32)

import qualified Copilot.Theorem.What4 as CT
import Language.Copilot

data S = S
  { unS :: Field "unS" Word32
  }

instance Struct S where
  typeName _ = "s"
  toValues s = [Value typeOf (unS s)]

instance Typed S where
  typeOf = Struct (S (Field 0))

spec :: Spec
spec = do
  let externS :: Stream S
      externS = extern "extern_s" Nothing

      example :: Stream Word32
      example = (externS ## unS =: 42) # unS

  void $ prop "example" (forAll $ example == example)

main :: IO ()
main = do
  spec' <- reify spec

  -- Use Z3 to prove the properties.
  results <- CT.prove CT.Z3 spec'

  -- Print the results.
  for_ results $ \(nm, res) -> do
    putStr $ nm <> ": "
    case res of
      CT.Valid -> putStrLn "valid"
      CT.Invalid -> putStrLn "invalid"
      CT.Unknown -> putStrLn "unknown"

produces an error message:

$ runghc UpdateField.hs 
UpdateField.hs: src/Copilot/Theorem/What4/Translate.hs:(707,40)-(802,2): Non-exhaustive patterns in case

when it should instead execute correctly and print valid, invalid, or unknown.

Expected result

Copilot allows using struct updates in copilot-theorem and to reason about them.

Desired result

Copilot allows using struct updates in copilot-theorem and to reason about them.

Proposed solution

Translate struct updates to what4.

Include an example that demonstrates the support for struct updates in copilot-theorem.

Include a test that checks that struct updates are supported in copilot-theorem.

Further notes

None.

[ivanperez-keera]

Change Manager: Confirmed that the issue exists.

[ivanperez-keera]

Technical Lead: Confirmed that the issue should be addressed.

[ivanperez-keera]

Technical Lead: Issue scheduled for fixing in Copilot 4.

Fix assigned to: @RyanGlScott .