Var machinery isn't expressive enough

[enolan]

I'm trying to use the abstract state machine testing support and I think the current library isn't powerful enough for what I want. I may be missing something though.

I'm testing a service that's supposed to keep track of the phone numbers my company owns. You can POST a number to store it in the service's database, and there is another endpoint which calls an external service to buy one. In the first case, the number is chosen randomly when commands are generated in my test. In the second case, the external service gets to pick the number. I actually have a mock so my tests don't cost money, but that's the principle. So in my model state, some of the numbers need to be Vars, but some of them are concrete both at generation and runtime. There's no way for me to make a Var Number Symbolic other than getting it from the result of a command, so I wrote something like this:

data ModelState (v :: * -> *) = ModelState {
  _numbers :: [HedgehogOrRuntime Number v]
  } deriving (Eq, Ord, Show)

-- Values which can come from hedgehog generation or the system under test.
type HedgehogOrRuntime t v = Either t (Var t v)

The idea being that POSTed numbers would be Lefts and numbers bought from the external service would be Rights. This is kinda ugly but oh well.

I still have problems. The first is that my endpoint for GETting a number accepts a literal phone number, type Phone, as a parameter but my state contains a record, type Number that includes some metadata along with the number. That metadata is a parameter to the POST endpoint and manipulated by other calls. I'd need to fmap or something on the Var Number v in my model state to get a Var Phone v to call the GET endpoint, but that doesn't exist. I can change it so my state is [Either (Phone, Number) (Var Phone v, Var Number v)], and have my updates modify that, but there are many other cases where I need to do computation on the number state when commands are generated. For instance I need to make queries based on the metadata, which I could do using the hypothetical Functor instance. On the other hand, I could have as my state [Either (Phone, Metadata) (Var Phone v, Metadata)]. But that's not how my client library is structured, so I'd have to duplicate the metadata structure in my tests and make sure to keep it in sync. That's more work than I want to do.

That's all ugly and annoying, but solvable in principle. One thing I can't figure out how to do is generate phone numbers that are not in the current state when the current state includes symbolic values. If I had a [Var Phone v], and there were a Functor instance, I'd still need to be able to commute Var and [] to get Var [Phone] v and make a Var (Set Phone) v or something. That doesn't even get me what I want, because I can't use my Var (Set Phone) v in a call to Gen.filter.

By the way, I think Hedgehog is really cool and I appreciate all the work you put into it!

[jacobstanley]

One thing I can't figure out how to do is generate phone numbers that are not in the current state when the current state includes symbolic values.

I don't think this can ever be possible in general, as you have no idea what the external service will return, and yet you need to model the expected state for commands which are generated ahead of time. Given you're controlling the external service, is it possible to ensure that the generated numbers never overlap with the numbers returned from the mock service? Then you'd only need to check against the concrete numbers which you've generated.

I'm confident that we can come up with a less fiddly state representation. Is there a way I can look at bit more of the code so I can see what you're trying to model a bit better?

[enolan]

Hmm. I think what I'd do is change the mock so it always returns numbers with some prefix, and change the random generation in the Hedgehog test to always generate numbers with some other non-overlapping prefix.

It looks like I wiped out the version of my code with Vars after I decided it wasn't going to work, but here are some parts of the version that doesn't support calling the external service.

data ModelState (v :: * -> *) = ModelState {
  -- Model update functions need to keep the indices in sync.
  _numbers :: Map Phone Number,
  _environments :: Set Text,
  _programs :: Map (Text, Text) (Set Number)
  } deriving (Eq, Show)
makeLenses ''ModelState

initialState :: ModelState v
initialState = ModelState mempty mempty mempty

Phone is a normalized, validated phone number, Number is a record with a Phone, the service that provided the number and optionally the program and environment the number is attached to. Without getting too far into what Signal Vine does, the program and environment are the context in which we want to use the number.

The service's API supports looking up the metadata by phone number, getting a list of all the environments, getting a list of all the programs in an environment, getting all the numbers attached to a program in some particular environment and changing which environment/program a number is attached to. All of those are tested with commands. IIUC I can't have a Map (Var Phone v) (Var Number v) because the sort order of the symbolic values won't be the same as the sort order of the actual ones. That's why the design in my original comment was just a list.

Here's the command for looking up the metadata by phone number:

type RunClientM m = forall a. ClientM a -> m (Either ServantError a)

data GetNumber (v :: * -> *) = GetNumber Phone
  deriving (Eq, Show)

instance HTraversable GetNumber where
  htraverse _ (GetNumber ph) = pure $ GetNumber ph

getNumberCommand :: (MonadGen n, MonadIO m) => RunClientM m -> Command n m ModelState
getNumberCommand rcm = Command
  (\state -> fmap GetNumber <$> genPhoneInState state)
  (\(GetNumber ph) -> rcm $ getNumber ph)
  [
    Require $ \state (GetNumber ph) -> member ph (state ^. numbers),
    Ensure $ \before _after (GetNumber ph) res ->
      case before ^. numbers ^. at ph of
        Nothing -> failure
        Just numberToFind -> res === Right numberToFind
  ]

genPhoneInState takes the ModelState and picks a random phone number that is a member of the _numbers field.

Here's the command for updating a number record:

data PutNumber (v :: * -> *) = PutNumber Number
  deriving (Eq, Show)

instance HTraversable PutNumber where
  htraverse _ (PutNumber numb) = pure $ PutNumber numb

putNumberCommand :: (MonadGen n, MonadIO m) => RunClientM m -> Command n m ModelState
putNumberCommand rcm = Command
  (\state -> flip fmap (genPhoneInState state) $ \ph -> do
      mbClInfo <- genClaimInfo state
      PutNumber <$> (Number <$> ph <*> genProvider <*> pure mbClInfo))
  (\(PutNumber numb) -> rcm $ putNumber numb)
  [
    Require $ \state (PutNumber numb) -> member (numb ^. number) (state ^. numbers),
    Ensure $ \_before _after _cmd res -> res === Right NoContent,
    Update $ \before (PutNumber newNumb) _var ->
      let !oldNumb = before ^?! numbers . at (newNumb ^. number) . _Just
          cliModifyOld = case oldNumb ^. owner of
            Just clInfo ->
              (environments %~ deleteSet (clInfo ^. environment)) .
              (programs . at (clInfo ^. environment, clInfo ^. program) . _Just %~ deleteSet oldNumb)
            Nothing -> id
          cliModifyNew = case newNumb ^. owner of
            Just clInfo ->
              (environments %~ insertSet (clInfo ^. environment)) .
              (programs . at (clInfo ^. environment, clInfo ^. program) %~
               Just . maybe (singletonSet newNumb) (insertSet newNumb))
            Nothing -> id
          cliModify = cliModifyNew . cliModifyOld
      in numbers . at (newNumb ^. number) .~ Just newNumb $
         numbers . at (oldNumb ^. number) .~ Nothing $
         cliModify before
  ]

To support updating numbers that were provisioned by the external service, I'd have to have data PutNumber (v :: * -> *) = PutNumber (Either Number (Var Number v)). The Update needs to access the owner field of the old and new Numbers in order to update the indices in the state. Those indices are used by the Hedgehog commands that correspond to the endpoints that look things up by environment or program. Even if I didn't have the indices, those commands would still need to be able to access the programs and environments of all the numbers in the state to figure out what to return.

Does that help?

[ocharles]

Perhaps related to #113 ?

[dalaing]

I've been thinking about this a little. Is it strictly necessary to have the generate-list-of-actions phase and then the carry-out-the-actions phase?

Would it be possible to create a GenT directly from an initial state and a list of actions to choose from? That might require either a lot of care or building up some kind of log of various choices that get made along the way for use with shrinking, but if it could remove the need for the Var machinery then it might be a win.

Setting up the Ensure machinery might get a bit interesting though :) I'll have a play around with some ideas in the space once I get a chance.