{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

{-| Tests for lock waiting structure.

-}

{-

Copyright (C) 2014 Google Inc.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

-}

module Test.Ganeti.Locking.Waiting (testLocking_Waiting) where

import Control.Applicative ((<$>), (<*>), liftA2)
import Control.Monad (liftM)
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Text.JSON as J

import Test.QuickCheck

import Test.Ganeti.TestCommon
import Test.Ganeti.TestHelper
import Test.Ganeti.Locking.Allocation (TestLock, TestOwner, requestSucceeded)

import Ganeti.BasicTypes (isBad, genericResult, runListHead)
import Ganeti.Locking.Allocation (LockRequest, listLocks)
import qualified Ganeti.Locking.Allocation as L
import Ganeti.Locking.Types (Lock)
import Ganeti.Locking.Waiting

{-

Ganeti.Locking.Waiting is polymorphic in the types of locks, lock owners,
and priorities. So we can use much simpler types here than Ganeti's
real locks and lock owners, knowning that polymorphic functions cannot
exploit the simplicity of the types they're deling with. To avoid code
duplication, we use the test structure from Test.Ganeti.Locking.Allocation.

-}

{-

All states of a LockWaiting ever available outside the module can be
obtained from @emptyWaiting@ applying one of the update operations.

-}

data UpdateRequest a b c = Update b [LockRequest a]
                         | UpdateWaiting c b [LockRequest a]
                         | RemovePending b
                         | IntersectRequest b [a]
                         | OpportunisticUnion b [(a, L.OwnerState)]
                         deriving Show

instance (Arbitrary a, Arbitrary b, Arbitrary c)
         => Arbitrary (UpdateRequest a b c) where
  arbitrary =
    frequency [ (2, Update <$> arbitrary <*> (choose (1, 4) >>= vector))
              , (4, UpdateWaiting <$> arbitrary <*> arbitrary
                                  <*> (choose (1, 4) >>= vector))
              , (1, RemovePending <$> arbitrary)
              , (1, IntersectRequest <$> arbitrary
                                     <*> (choose (1, 4) >>= vector))
              , (1, OpportunisticUnion <$> arbitrary
                                       <*> (choose (1, 4) >>= vector))
              ]

-- | Transform an UpdateRequest into the corresponding state transformer.
asWaitingTrans :: (Lock a, Ord b, Ord c)
               => LockWaiting a b c -> UpdateRequest a b c -> LockWaiting a b c
asWaitingTrans state (Update owner req) = fst $ updateLocks owner req state
asWaitingTrans state (UpdateWaiting prio owner req) =
  fst $ updateLocksWaiting prio owner req state
asWaitingTrans state (RemovePending owner) = removePendingRequest owner state
asWaitingTrans state (IntersectRequest owner locks) =
  fst $ intersectLocks locks owner state
asWaitingTrans state (OpportunisticUnion owner locks) =
  fst $ opportunisticLockUnion owner locks state


-- | Fold a sequence of requests to transform a waiting strucutre onto the
-- empty waiting. As we consider all exported transformations, any waiting
-- structure can be obtained this way.
foldUpdates :: (Lock a, Ord b, Ord c)
            => [UpdateRequest a b c] -> LockWaiting a b c
foldUpdates = foldl asWaitingTrans emptyWaiting

instance (Arbitrary a, Lock a, Arbitrary b, Ord b, Arbitrary c, Ord c)
         => Arbitrary (LockWaiting a b c) where
  arbitrary = foldUpdates <$> (choose (0, 8) >>= vector)

-- | Verify that an owner with a pending request cannot make any
-- changes to the lock structure.
prop_NoActionWithPendingRequests :: Property
prop_NoActionWithPendingRequests =
  forAll (arbitrary :: Gen TestOwner) $ \a ->
  forAll ((arbitrary :: Gen (LockWaiting TestLock TestOwner Integer))
          `suchThat` (S.member a . getPendingOwners)) $ \state ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  forAll arbitrary $ \prio ->
  counterexample "Owners with pending requests may not update locks"
  . all (isBad . fst . snd)
  $ [updateLocks, updateLocksWaiting prio] <*> [a] <*> [req] <*> [state]

-- | Quantifier for blocked requests. Quantifies over the generic situation
-- that there is a state, an owner, and a request that is blocked for that
-- owner. To obtain such a situation, we use the fact that there must be a
-- different owner having at least one lock.
forAllBlocked :: (Testable prop)
              => (LockWaiting TestLock TestOwner Integer -- State
                  -> TestOwner -- The owner of the blocked request
                  -> Integer -- The priority
                  -> [LockRequest TestLock] -- Request
                  -> prop)
              -> Property
forAllBlocked predicate =
  forAll (arbitrary :: Gen TestOwner) $ \a ->
  forAll (arbitrary :: Gen Integer) $ \prio ->
  forAll (arbitrary `suchThat` (/=) a) $ \b ->
  forAll ((arbitrary :: Gen (LockWaiting TestLock TestOwner Integer))
          `suchThat` foldl (liftA2 (&&)) (const True)
              [ not . S.member a . getPendingOwners
              , M.null . listLocks a . getAllocation
              , not . M.null . listLocks b . getAllocation]) $ \state ->
  forAll ((arbitrary :: Gen [LockRequest TestLock])
          `suchThat` (genericResult (const False) (not . S.null)
                      . fst . snd . flip (updateLocksWaiting prio a) state))
          $ \req ->
  predicate state a prio req

-- | Verify that an owner has a pending request after a waiting request
-- not fullfilled immediately.
prop_WaitingRequestsGetPending :: Property
prop_WaitingRequestsGetPending =
  forAllBlocked $ \state owner prio req ->
  counterexample "After a not immediately fulfilled waiting request, owner\
                 \ must have a pending request"
  . S.member owner . getPendingOwners . fst
  $ updateLocksWaiting prio owner req state

-- | Verify that pending requests get fullfilled once all blockers release
-- their resources.
prop_PendingGetFulfilledEventually :: Property
prop_PendingGetFulfilledEventually =
  forAllBlocked $ \state owner prio req ->
  let oldpending = getPendingOwners state
      (state', (resultBlockers, _)) = updateLocksWaiting prio owner req state
      blockers = genericResult (const S.empty) id resultBlockers
      state'' = S.foldl (\s a -> fst $ releaseResources a s) state'
                  $ S.union oldpending blockers
      finallyOwned = listLocks  owner $ getAllocation state''
  in counterexample "After all blockers and old pending owners give up their\
                    \ resources, a pending request must be granted\
                    \ automatically"
     $ all (requestSucceeded finallyOwned) req

-- | Verify that the owner of a pending request gets notified once all blockers
-- release their resources.
prop_PendingGetNotifiedEventually :: Property
prop_PendingGetNotifiedEventually =
  forAllBlocked $ \state owner prio req ->
  let oldpending = getPendingOwners state
      (state', (resultBlockers, _)) = updateLocksWaiting prio owner req state
      blockers = genericResult (const S.empty) id resultBlockers
      releaseOneOwner (s, tonotify) o =
        let (s', newnotify) = releaseResources o s
        in (s', newnotify `S.union` tonotify)
      (_, notified) = S.foldl releaseOneOwner (state', S.empty)
                        $ S.union oldpending blockers
  in counterexample "After all blockers and old pending owners give up their\
                    \ resources, a pending owner must be notified"
     $ S.member owner notified

-- | Verify that some progress is made after the direct blockers give up their
-- locks. Note that we cannot guarantee that the original requester gets its
-- request granted, as someone else might have a more important priority.
prop_Progress :: Property
prop_Progress =
  forAllBlocked $ \state owner prio req ->
  let (state', (resultBlockers, _)) = updateLocksWaiting prio owner req state
      blockers = genericResult (const S.empty) id resultBlockers
      releaseOneOwner (s, tonotify) o =
        let (s', newnotify) = releaseResources o s
        in (s', newnotify `S.union` tonotify)
      (_, notified) = S.foldl releaseOneOwner (state', S.empty) blockers
  in counterexample "Some progress must be made after all blockers release\
                    \ their locks"
     . not . S.null $ notified S.\\ blockers

-- | Verify that the notifications send out are sound, i.e., upon notification
-- the requests actually are fulfilled. To be sure to have at least one
-- notification we, again, use the scenario that a request is blocked and then
-- all the blockers release their resources.
prop_ProgressSound :: Property
prop_ProgressSound =
  forAllBlocked $ \state owner prio req ->
  let (state', (resultBlockers, _)) = updateLocksWaiting prio owner req state
      blockers = genericResult (const S.empty) id resultBlockers
      releaseOneOwner (s, tonotify) o =
        let (s', newnotify) = releaseResources o s
        in (s', newnotify `S.union` tonotify)
      (state'', notified) = S.foldl releaseOneOwner (state', S.empty) blockers
      requestFulfilled o =
        runListHead False
          (\(_, _, r) ->
              all (requestSucceeded . listLocks o $ getAllocation state'') r)
          . S.toList . S.filter (\(_, b, _) -> b == o)
          . getPendingRequests $ state'
  in counterexample "If an owner gets notified, his request must be satisfied"
     . all requestFulfilled . S.toList $ notified S.\\ blockers

-- | Verify that all pending requests are valid and cannot be fulfilled in
-- the underlying lock allocation.
prop_PendingJustified :: Property
prop_PendingJustified =
  forAll ((arbitrary :: Gen (LockWaiting TestLock TestOwner Integer))
          `suchThat` (not . S.null . getPendingRequests)) $ \state ->
  let isJustified (_, b, req) =
        genericResult (const False) (not . S.null) . snd
        . L.updateLocks b req $ getAllocation state
  in counterexample "Pending requests must be good and not fulfillable"
     . all isJustified . S.toList $ getPendingRequests state

-- | Verify that `updateLocks` is idempotent, except that in the repetition,
-- no waiters are notified.
prop_UpdateIdempotent :: Property
prop_UpdateIdempotent =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \owner ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  let (state', (answer', _)) = updateLocks owner req state
      (state'', (answer'', nfy)) = updateLocks owner req state'
  in conjoin [ counterexample ("repeated updateLocks waiting gave different\
                               \ answers: " ++ show answer' ++ " /= "
                               ++ show answer'') $ answer' == answer''
             , counterexample "updateLocks not idempotent"
               $ extRepr state' == extRepr state''
             , counterexample ("notifications (" ++ show nfy ++ ") on replay")
               $ S.null nfy
             ]

-- | Verify that extRepr . fromExtRepr = id for all valid extensional
-- representations.
prop_extReprPreserved :: Property
prop_extReprPreserved =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  let rep = extRepr state
      rep' = extRepr $ fromExtRepr rep
  in counterexample "a lock waiting obtained from an extensional representation\
                    \ must have the same extensional representation"
     $ rep' == rep

-- | Verify that any state is indistinguishable from its canonical version
-- (i.e., the one obtained from the extensional representation) with respect
-- to updateLocks.
prop_SimulateUpdateLocks :: Property
prop_SimulateUpdateLocks =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \owner ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  let state' = fromExtRepr $ extRepr state
      (finState, (result, notify)) = updateLocks owner req state
      (finState', (result', notify')) = updateLocks owner req state'
  in counterexample "extRepr-equal states must behave equal on updateLocks"
     $ and [ result == result'
           , notify == notify'
           , extRepr finState == extRepr finState'
           ]
-- | Verify that any state is indistinguishable from its canonical version
-- (i.e., the one obtained from the extensional representation) with respect
-- to updateLocksWaiting.
prop_SimulateUpdateLocksWaiting :: Property
prop_SimulateUpdateLocksWaiting =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \owner ->
  forAll (arbitrary :: Gen Integer) $ \prio ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  let state' = fromExtRepr $ extRepr state
      (finState, (result, notify)) = updateLocksWaiting prio owner req state
      (finState', (result', notify')) = updateLocksWaiting prio owner req state'
  in counterexample "extRepr-equal states must behave equal on updateLocks"
     $ and [ result == result'
           , notify == notify'
           , extRepr finState == extRepr finState'
           ]

-- | Verify that if a requestor has no pending requests, `safeUpdateWaiting`
-- conincides with `updateLocksWaiting`.
prop_SafeUpdateWaitingCorrect :: Property
prop_SafeUpdateWaitingCorrect  =
  forAll (arbitrary :: Gen TestOwner) $ \owner ->
  forAll ((arbitrary :: Gen (LockWaiting TestLock TestOwner Integer))
          `suchThat` (not . hasPendingRequest owner)) $ \state ->
  forAll (arbitrary :: Gen Integer) $ \prio ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  let (state', answer') = updateLocksWaiting prio owner req state
      (state'', answer'') = safeUpdateLocksWaiting prio owner req state
  in conjoin [ counterexample ("safeUpdateLocksWaiting gave different answer: "
                              ++ show answer' ++ " /= " ++ show answer'')
               $ answer' == answer''
             , counterexample ("safeUpdateLocksWaiting gave different states\
                               \ after answer " ++ show answer' ++ ": "
                               ++ show (extRepr state') ++ " /= "
                               ++ show (extRepr state''))
               $ extRepr state' == extRepr state''
             ]

-- | Verify that `safeUpdateLocksWaiting` is idempotent, that in the repetition
-- no notifications are done.
prop_SafeUpdateWaitingIdempotent :: Property
prop_SafeUpdateWaitingIdempotent =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \owner ->
  forAll (arbitrary :: Gen Integer) $ \prio ->
  forAll (arbitrary :: Gen [LockRequest TestLock]) $ \req ->
  let (state', (answer', _)) = safeUpdateLocksWaiting prio owner req state
      (state'', (answer'', nfy)) = safeUpdateLocksWaiting prio owner req state'
  in conjoin [ counterexample ("repeated safeUpdateLocks waiting gave different\
                               \ answers: " ++ show answer' ++ " /= "
                               ++ show answer'') $ answer' == answer''
             , counterexample "safeUpdateLocksWaiting not idempotent"
               $ extRepr state' == extRepr state''
             , counterexample ("notifications (" ++ show nfy ++ ") on replay")
               $ S.null nfy
             ]

-- | Verify that for LockWaiting we have readJSON . showJSON is extensionally
-- equivalent to Ok.
prop_ReadShow :: Property
prop_ReadShow =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  (liftM extRepr . J.readJSON $ J.showJSON state) ==? (J.Ok $ extRepr state)

-- | Verify that opportunistic union only increases the locks held.
prop_OpportunisticMonotone :: Property
prop_OpportunisticMonotone =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \a ->
  forAll ((choose (1,3) >>= vector) :: Gen [(TestLock, L.OwnerState)]) $ \req ->
  let (state', _) = opportunisticLockUnion a req state
      oldOwned = listLocks a $ getAllocation state
      oldLocks = M.keys oldOwned
      newOwned = listLocks a $ getAllocation state'
  in counterexample "Opportunistic union may only increase the set of locks\
                    \ held"
     . flip all oldLocks $ \lock ->
       M.lookup lock newOwned >= M.lookup lock oldOwned

-- | Verify the result list of the opportunistic union: if a lock is not in
-- the result that, than its state has not changed, and if it is, it is as
-- requested. The latter property is tested in that liberal way, so that we
-- really can take arbitrary requests, including those that require both, shared
-- and exlusive state for the same lock.
prop_OpportunisticAnswer :: Property
prop_OpportunisticAnswer =
  forAll (arbitrary :: Gen (LockWaiting TestLock TestOwner Integer)) $ \state ->
  forAll (arbitrary :: Gen TestOwner) $ \a ->
  forAll ((choose (1,3) >>= vector) :: Gen [(TestLock, L.OwnerState)]) $ \req ->
  let (state', (result, _)) = opportunisticLockUnion a req state
      oldOwned = listLocks a $ getAllocation state
      newOwned = listLocks a $ getAllocation state'
      involvedLocks = M.keys oldOwned ++ map fst req
  in conjoin [ counterexample ("Locks not in the answer set " ++ show result
                                 ++ " may not be changed, but found "
                                 ++ show state')
               . flip all involvedLocks $ \lock ->
                 (lock `elem` result)
                 || (M.lookup lock oldOwned == M.lookup lock newOwned)
             , counterexample ("Locks not in the answer set " ++ show result
                                ++ " must be as requested, but found "
                                ++ show state')
               . flip all involvedLocks $ \lock ->
                 notElem lock result
                 || maybe False (flip elem req . (,) lock)
                      (M.lookup lock newOwned)
             ]


testSuite "Locking/Waiting"
 [ 'prop_NoActionWithPendingRequests
 , 'prop_WaitingRequestsGetPending
 , 'prop_PendingGetFulfilledEventually
 , 'prop_PendingGetNotifiedEventually
 , 'prop_Progress
 , 'prop_ProgressSound
 , 'prop_PendingJustified
 , 'prop_extReprPreserved
 , 'prop_UpdateIdempotent
 , 'prop_SimulateUpdateLocks
 , 'prop_SimulateUpdateLocksWaiting
 , 'prop_ReadShow
 , 'prop_SafeUpdateWaitingCorrect
 , 'prop_SafeUpdateWaitingIdempotent
 , 'prop_OpportunisticMonotone
 , 'prop_OpportunisticAnswer
 ]