Skip to content

Commit f4cb053

Browse files
committed
Speed up shrinking
1 parent e72975c commit f4cb053

File tree

1 file changed

+26
-2
lines changed

1 file changed

+26
-2
lines changed

lib/Echidna/ABI.hs

Lines changed: 26 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
module Echidna.ABI where
22

33
import Control.Monad (liftM2, liftM3, foldM, replicateM)
4-
import Control.Monad.Random.Strict (MonadRandom, join, getRandom, getRandoms, getRandomR)
4+
import Control.Monad.Random.Strict (MonadRandom, join, getRandom, getRandoms, getRandomR, uniform, fromList)
55
import Control.Monad.Random.Strict qualified as Random
66
import Data.Binary.Put (runPut, putWord32be)
77
import Data.BinaryWord (unsignedWord)
@@ -274,7 +274,31 @@ shrinkAbiValue = \case
274274

275275
-- | Given a 'SolCall', generate a random \"smaller\" (simpler) call.
276276
shrinkAbiCall :: MonadRandom m => SolCall -> m SolCall
277-
shrinkAbiCall = traverse $ traverse shrinkAbiValue
277+
shrinkAbiCall (name, vals) = do
278+
let numShrinkable = length $ filter canShrinkAbiValue vals
279+
280+
halfwayVal <- getRandomR (0, numShrinkable)
281+
-- This list was made arbitrarily. Feel free to change
282+
let numToShrinkOptions = [1, 2, halfwayVal, numShrinkable]
283+
284+
numToShrink <- min numShrinkable <$> uniform numToShrinkOptions
285+
shrunkVals <- shrinkVals (fromIntegral numShrinkable) (fromIntegral numToShrink) vals
286+
pure (name, shrunkVals)
287+
where
288+
shrinkVals 0 _ l = pure l
289+
shrinkVals _ 0 l = pure l
290+
shrinkVals _ _ [] = pure []
291+
shrinkVals numShrinkable numToShrink (h:t)
292+
| not (canShrinkAbiValue h) = (h:) <$> shrinkVals numShrinkable numToShrink t
293+
| otherwise = do
294+
-- We want to pick which ones to shrink uniformly from the vals list.
295+
-- Odds of shrinking one element is numToShrink/numShrinkable.
296+
shouldShrink <- fromList [(True, numToShrink), (False, numShrinkable-numToShrink)]
297+
h' <- if shouldShrink then shrinkAbiValue h else pure h
298+
let
299+
numShrinkable' = numShrinkable-1
300+
numToShrink' = if shouldShrink then numToShrink-1 else numToShrink
301+
(h':) <$> shrinkVals numShrinkable' numToShrink' t
278302

279303
-- | Given an 'AbiValue', generate a random \"similar\" value of the same 'AbiType'.
280304
mutateAbiValue :: MonadRandom m => AbiValue -> m AbiValue

0 commit comments

Comments
 (0)