-----------------------------------------------------------------------------
-- |
-- Module    : Documentation.SBV.Examples.BitPrecise.BrokenSearch
-- Copyright : (c) Levent Erkok
-- License   : BSD3
-- Maintainer: erkokl@gmail.com
-- Stability : experimental
--
-- The classic "binary-searches are broken" example:
--     <http://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html>
-----------------------------------------------------------------------------

{-# OPTIONS_GHC -Wall -Werror #-}

module Documentation.SBV.Examples.BitPrecise.BrokenSearch where

import Data.SBV
import Data.SBV.Tools.Overflow

-- $setup
-- >>> import Data.SBV
-- >>> import Data.Int

-- | Model the mid-point computation of the binary search, which is broken due to arithmetic overflow.
-- Note how we use the overflow checking variants of the arithmetic operators. We have:
--
-- >>> checkArithOverflow midPointBroken
-- ./Documentation/SBV/Examples/BitPrecise/BrokenSearch.hs:39:32:+!: SInt32 addition overflows: Violated. Model:
--   low  = 2147475456 :: Int32
--   high = 2147483646 :: Int32
--
-- Indeed:
--
-- >>> (2147475456 + 2147483646) `div` (2::Int32)
-- -4097
--
-- giving us a negative mid-point value!
midPointBroken :: SInt32 -> SInt32 -> SInt32
midPointBroken :: SInt32 -> SInt32 -> SInt32
midPointBroken SInt32
low SInt32
high = (SInt32
low forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
+! SInt32
high) forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
/! SInt32
2

-- | The correct version of how to compute the mid-point. As expected, this version doesn't have any
-- underflow or overflow issues:
--
-- >>> checkArithOverflow midPointFixed
-- No violations detected.
--
-- As expected, the value is computed correctly too:
--
-- >>> checkCorrectMidValue midPointFixed
-- Q.E.D.
midPointFixed :: SInt32 -> SInt32 -> SInt32
midPointFixed :: SInt32 -> SInt32 -> SInt32
midPointFixed SInt32
low SInt32
high = SInt32
low forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
+! ((SInt32
high forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
-! SInt32
low) forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
/! SInt32
2)

-- | Show that the variant suggested by the blog post is good as well:
--
--       @mid = ((unsigned int)low + (unsigned int)high) >> 1;@
--
-- In this case the overflow is eliminated by doing the computation at a wider
-- range:
--
-- >>> checkArithOverflow midPointAlternative
-- No violations detected.
--
-- And the value computed is indeed correct:
--
-- >>> checkCorrectMidValue midPointAlternative
-- Q.E.D.
midPointAlternative :: SInt32 -> SInt32 -> SInt32
midPointAlternative :: SInt32 -> SInt32 -> SInt32
midPointAlternative SInt32
low SInt32
high = forall a b.
(Integral a, HasKind a, Num a, SymVal a, HasKind b, Num b,
 SymVal b) =>
SBV a -> SBV b
sFromIntegral ((SBV Word32
low' forall a.
(CheckedArithmetic a, ?loc::CallStack) =>
SBV a -> SBV a -> SBV a
+! SBV Word32
high') forall a. Bits a => a -> Int -> a
`shiftR` Int
1)
  where low', high' :: SWord32
        low' :: SBV Word32
low'  = forall a b.
(?loc::CallStack, Integral a, HasKind a, HasKind b, Num a,
 SymVal a, HasKind b, Num b, SymVal b) =>
SBV a -> SBV b
sFromIntegralChecked SInt32
low
        high' :: SBV Word32
high' = forall a b.
(?loc::CallStack, Integral a, HasKind a, HasKind b, Num a,
 SymVal a, HasKind b, Num b, SymVal b) =>
SBV a -> SBV b
sFromIntegralChecked SInt32
high

-------------------------------------------------------------------------------------
-- * Helpers
-------------------------------------------------------------------------------------

-- | A helper predicate to check safety under the conditions that @low@ is at least 0
-- and @high@ is at least @low@.
checkArithOverflow :: (SInt32 -> SInt32 -> SInt32) -> IO ()
checkArithOverflow :: (SInt32 -> SInt32 -> SInt32) -> IO ()
checkArithOverflow SInt32 -> SInt32 -> SInt32
f = do [SafeResult]
sr <- forall a. SExecutable IO a => a -> IO [SafeResult]
safe forall a b. (a -> b) -> a -> b
$ do SInt32
low   <- String -> SymbolicT IO SInt32
sInt32 String
"low"
                                          SInt32
high <- String -> SymbolicT IO SInt32
sInt32 String
"high"

                                          forall (m :: * -> *). SolverContext m => SBool -> m ()
constrain forall a b. (a -> b) -> a -> b
$ SInt32
low forall a. OrdSymbolic a => a -> a -> SBool
.>= SInt32
0
                                          forall (m :: * -> *). SolverContext m => SBool -> m ()
constrain forall a b. (a -> b) -> a -> b
$ SInt32
low forall a. OrdSymbolic a => a -> a -> SBool
.<= SInt32
high

                                          forall a. Outputtable a => a -> Symbolic a
output forall a b. (a -> b) -> a -> b
$ SInt32 -> SInt32 -> SInt32
f SInt32
low SInt32
high

                          case forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. SafeResult -> Bool
isSafe) [SafeResult]
sr of
                                 [] -> String -> IO ()
putStrLn String
"No violations detected."
                                 [SafeResult]
xs -> forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ forall a. Show a => a -> IO ()
print [SafeResult]
xs

-- | Another helper to show that the result is actually the correct value, if it was done over
-- 64-bit integers, which is sufficiently large enough.
checkCorrectMidValue :: (SInt32 -> SInt32 -> SInt32) -> IO ThmResult
checkCorrectMidValue :: (SInt32 -> SInt32 -> SInt32) -> IO ThmResult
checkCorrectMidValue SInt32 -> SInt32 -> SInt32
f = forall a. Provable a => a -> IO ThmResult
prove forall a b. (a -> b) -> a -> b
$ do SInt32
low  <- String -> SymbolicT IO SInt32
sInt32 String
"low"
                                    SInt32
high <- String -> SymbolicT IO SInt32
sInt32 String
"high"

                                    forall (m :: * -> *). SolverContext m => SBool -> m ()
constrain forall a b. (a -> b) -> a -> b
$ SInt32
low forall a. OrdSymbolic a => a -> a -> SBool
.>= SInt32
0
                                    forall (m :: * -> *). SolverContext m => SBool -> m ()
constrain forall a b. (a -> b) -> a -> b
$ SInt32
low forall a. OrdSymbolic a => a -> a -> SBool
.<= SInt32
high

                                    let low', high' :: SInt64
                                        low' :: SBV Int64
low'  = forall a b.
(Integral a, HasKind a, Num a, SymVal a, HasKind b, Num b,
 SymVal b) =>
SBV a -> SBV b
sFromIntegral SInt32
low
                                        high' :: SBV Int64
high' = forall a b.
(Integral a, HasKind a, Num a, SymVal a, HasKind b, Num b,
 SymVal b) =>
SBV a -> SBV b
sFromIntegral SInt32
high
                                        mid' :: SBV Int64
mid'  = (SBV Int64
low' forall a. Num a => a -> a -> a
+ SBV Int64
high') forall a. SDivisible a => a -> a -> a
`sDiv` SBV Int64
2

                                        mid :: SInt32
mid   = SInt32 -> SInt32 -> SInt32
f SInt32
low SInt32
high

                                    forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a b.
(Integral a, HasKind a, Num a, SymVal a, HasKind b, Num b,
 SymVal b) =>
SBV a -> SBV b
sFromIntegral SInt32
mid forall a. EqSymbolic a => a -> a -> SBool
.== SBV Int64
mid'

{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}