f# - Inconsistent IEnumerable ArgumentException while generating a complex object using FsCheck

Question

The Problem

In F#, I am using FsCheck to generate an object (which I'm then using in an Xunit test, but I can recreate entirely outside of Xunit, so I think we can forget about Xunit). Running the generation 20 times in FSI,

50% of the time, the generation runs successfully.

25% of the time, the generation throws:

System.ArgumentException: The input must be non-negative.
Parameter name: index
>    at Microsoft.FSharp.Collections.SeqModule.Item[T](Int32 index, IEnumerable`1 source)
   at FsCheck.GenBuilder.bind@62.Invoke(Int32 n, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 63
   at FsCheck.Gen.go@290-1[b](FSharpList`1 gs, FSharpList`1 acc, Int32 size, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 295
   at FsCheck.Gen.SequenceToList@297.Invoke(Int32 n, StdGen r) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 297
   at FsCheck.GenBuilder.bind@62.Invoke(Int32 n, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 63
   at FsCheck.Gen.sample@155[a](Int32 size, Gen`1 gn, Int32 i, StdGen seed, FSharpList`1 samples) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 157
   at FsCheck.Gen.Sample[a](Int32 size, Int32 n, Gen`1 gn) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 155
   at <StartupCode$FSI_0026>.$FSI_0026.main@() in C:\projects\Alberta\Core\TestFunc\Script.fsx:line 57
Stopped due to error

25% of the time, the generation throws:

System.ArgumentException: The input sequence has an insufficient number of elements.
Parameter name: index
>    at Microsoft.FSharp.Collections.IEnumerator.nth[T](Int32 index, IEnumerator`1 e)
   at Microsoft.FSharp.Collections.SeqModule.Item[T](Int32 index, IEnumerable`1 source)
   at FsCheck.GenBuilder.bind@62.Invoke(Int32 n, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 63
   at FsCheck.Gen.go@290-1[b](FSharpList`1 gs, FSharpList`1 acc, Int32 size, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 295
   at FsCheck.Gen.SequenceToList@297.Invoke(Int32 n, StdGen r) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 297
   at FsCheck.GenBuilder.bind@62.Invoke(Int32 n, StdGen r0) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 63
   at FsCheck.Gen.sample@155[a](Int32 size, Gen`1 gn, Int32 i, StdGen seed, FSharpList`1 samples) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 157
   at FsCheck.Gen.Sample[a](Int32 size, Int32 n, Gen`1 gn) in C:\Users\Kurt\Projects\FsCheck\FsCheck\src\FsCheck\Gen.fs:line 155
   at <StartupCode$FSI_0025>.$FSI_0025.main@() in C:\projects\Alberta\Core\TestFunc\Script.fsx:line 57
Stopped due to error

The Situation

The object is as follows:

type Event =
| InitEvent of string
| RefEvent of string
type Stream = Event seq

The object must be follow these rules to be valid:

All InitEvents must come before all RefEvents
All InitEvents strings must be unique
All RefEvent names must have an earlier corresponding InitEvent
But it's OK if some InitEvents NOT have later corresponding RefEvents
But it's OK if multiple RefEvents have the same name

The Working Workaround

If I have the generator call a function which returns a valid object and do a Gen.constant (function), I never run into the exceptions, but this is not the way FsCheck is meant to be run! :)

/// <summary>
/// This is a non-generator equivalent which is 100% reliable
/// </summary>
let randomStream size =
   // valid names for a sample
   let names = Gen.sample size size Arb.generate<string> |> List.distinct
   // init events
   let initEvents = names |> List.map( fun name -> name |> InitEvent )
   // reference events
   let createRefEvent name = name |> RefEvent
   let genRefEvent = createRefEvent <!> Gen.elements names
   let refEvents = Gen.sample size size genRefEvent
   // combine
   Seq.append initEvents refEvents


type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator = Gen.sized( fun size -> Gen.constant (randomStream size) )
   }

// repeatedly running the following two lines ALWAYS works
Arb.register<MyGenerators>()
let foo = Gen.sample 10 10 Arb.generate<Stream>

The Broken Right Way?

I cannot seem to completely get away from generating a constant (need to store the list of names outside of the InitEvents so that RefEvent generation can get at them, but I can get more in line with how FsCheck generators seem to work:

type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator = Gen.sized( fun size ->
            // valid names for a sample
            let names = Gen.sample size size Arb.generate<string> |> List.distinct
            // generate inits
            let genInits = Gen.constant (names |> List.map InitEvent) |> Gen.map List.toSeq
            // generate refs
            let makeRef name = name |> RefEvent
            let genName = Gen.elements names
            let genRef = makeRef <!> genName
            Seq.append <!> genInits <*> ( genRef |> Gen.listOf )
         )
   }

// repeatedly running the following two lines causes the inconsistent errors
// If I don't re-register my generator, I always get the same samples.
// Is this because FsCheck is trying to be deterministic?
Arb.register<MyGenerators>()
let foo = Gen.sample 10 10 Arb.generate<Stream>

What I've Already Checked

Sorry, forgot to mention in original question that I've tried to Debug in Interactive, and because of the inconsistent behavior, it's somewhat hard to track down. However, when the exceptions hit, it seems to be between the end of my generator code and what is asking for the generated samples -- while FsCheck is DOING the generation, it seems to be trying to process a malformed sequence. I'm further assuming that this is because I've incorrectly coded the generator.
IndexOutOfRangeException using FsCheck suggests a potentially similar situation. I have tried running my Xunit tests both via Resharper test runner as well as Xunit's console test runner on the real-world tests on which the above simplification is based. Both runners exhibit identical behavior, so the issue is somewhere else.
Other "How do I generate..." questions such as In FsCheck, how to generate a test record with non-negative fields? and How does one generate a "complex" object in FsCheck? deal with the creation of objects of a lesser complexity. The first was a great help for getting to the code I have, and the second gives a much-needed example of Arb.convert, but Arb.convert doesn't make sense if I'm converting from a "constant" list of randomly generated names. It all seems to come back to that -- the need to make random names, which are then pulled from to make a complete set of InitEvents, and some sequence of RefEvents, both which refer back to the "constant" list, doesn't match anything that I've yet come across.
I've looked through most examples of FsCheck generators I can find, including the included examples in FsCheck: https://github.com/fscheck/FsCheck/blob/master/examples/FsCheck.Examples/Examples.fs These also do not deal with an object needing internal consistency, and do not seem to apply to this case, even though they have been helpful overall.
Perhaps this means that I'm approaching the generation of the object from an unhelpful perspective. If there is a different way to generate an object which follows the above rules, I'm open to switching to it.
Further backing away from the problem, I've seen other SO posts which roughly say "If your object has such restrictions, then what happens when you receive an invalid object? Perhaps you need to rethink the way this object is consumed to better handle invalid cases." If, for example, I were able to initialize on-the-fly a never before seen name in a RefEvent, the entire need for giving an InitEvent first would go away -- the problem gracefully reduces to simply a sequence of RefEvents of some random name. I am open to this kind of solution, but it would require a bit of rework -- in the long run, it may be worth it. In the mean time, the question remains, how can you reliably generate a complex object which follows the above rules using FsCheck?

Thanks!

EDIT(S): Attempts to Solve

The code in Mark Seemann's answer works, but yields a slightly different object than I was looking for (I was unclear in my object rules -- now hopefully clarified). Putting his working code in my generator:

type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator =
            gen {
               let! uniqueStrings = Arb.Default.Set<string>().Generator
               let initEvents = uniqueStrings |> Seq.map InitEvent

               let! sortValues =
                  Arb.Default.Int32()
                  |> Arb.toGen
                  |> Gen.listOfLength uniqueStrings.Count
               let refEvents =
                  Seq.zip uniqueStrings sortValues
                  |> Seq.sortBy snd
                  |> Seq.map fst
                  |> Seq.map RefEvent

               return Seq.append initEvents refEvents
            }
    }

This yields an object where every InitEvent has a matching RefEvent, and there is only one RefEvent for each InitEvent. I'm trying to tweak the code so that I can get multiple RefEvents for each name, and not all names need to have a RefEvent. ex: Init foo, Init bar, Ref foo, Ref foo is perfectly valid. Trying to tweak this with:

type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator =
            gen {
               let! uniqueStrings = Arb.Default.Set<string>().Generator
               let initEvents = uniqueStrings |> Seq.map InitEvent

               // changed section starts
               let makeRef name = name |> RefEvent
               let genRef = makeRef <!> Gen.elements uniqueStrings
               return! Seq.append initEvents <!> ( genRef |> Gen.listOf )
               // changed section ends
            }
   }

The modified code still exhibits the inconsistent behavior. Interestingly, out of 20 sample runs, only three worked (down from 10), while the insufficient number of elements was thrown 8 times and The input must be non-negative was thrown 9 times -- these changes have made the edge case more than twice as likely to be hit. We're now down to a very small section of code with the error.

Mark quickly responded with another version to address changed requirements:

type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator =
            gen {
               let! uniqueStrings = Arb.Default.NonEmptySet<string>().Generator
               let initEvents = uniqueStrings.Get |> Seq.map InitEvent

               let! refEvents =
                  uniqueStrings.Get |> Seq.map RefEvent |> Gen.elements |> Gen.listOf

               return Seq.append initEvents refEvents
            }
   }

This allowed for some names to not have a RefEvent.

FINAL CODE A very minor tweak gets it so that duplicate RefEvents can happen:

type MyGenerators =
   static member Stream() = {
      new Arbitrary<Stream>() with
         override x.Generator =
            gen {
               let! uniqueStrings = Arb.Default.NonEmptySet<string>().Generator
               let initEvents = uniqueStrings.Get |> Seq.map InitEvent

               let! refEvents =
                  //uniqueStrings.Get |> Seq.map RefEvent |> Gen.elements |> Gen.listOf
                  Gen.elements uniqueStrings.Get |> Gen.map RefEvent |> Gen.listOf

               return Seq.append initEvents refEvents
            }
   }

Big thanks to Mark Seemann!

score 6 · Accepted Answer

创

这是解决要求的一种方法：

open FsCheck

let streamGen = gen {
    let! uniqueStrings = Arb.Default.Set<string>().Generator
    let initEvents = uniqueStrings |> Seq.map InitEvent

    let! sortValues =
        Arb.Default.Int32()
        |> Arb.toGen
        |> Gen.listOfLength uniqueStrings.Count
    let refEvents =
        Seq.zip uniqueStrings sortValues
        |> Seq.sortBy snd
        |> Seq.map fst
        |> Seq.map RefEvent

    return Seq.append initEvents refEvents }

关于如何生成唯一字符串的半官方答案是生成一个Set<string>. 由于Set<'a>也 implements 'a seq，您可以在其上使用所有正常Seq功能。

因此，生成InitEvent值是map对唯一字符串的简单操作。

由于每个都RefEvent必须有一个对应的InitEvent，因此您可以重复使用相同的唯一字符串，但您可能希望RefEvent在 option 上赋予值以不同的顺序出现。为此，您可以生成sortValues，这是一个随机int值列表。该列表与字符串集的长度相同。

此时，您有一个唯一字符串列表和一个随机整数列表。以下是一些说明这个概念的假值：

> let uniqueStrings = ["foo"; "bar"; "baz"];;
val uniqueStrings : string list = ["foo"; "bar"; "baz"]

> let sortValues = [42; 1337; 42];;    
val sortValues : int list = [42; 1337; 42]

您现在zip可以：

> List.zip uniqueStrings sortValues;;
val it : (string * int) list = [("foo", 42); ("bar", 1337); ("baz", 42)]

在第二个元素上对这样的序列进行排序会给你一个随机打乱的列表，然后你可以map只对第一个元素进行排序：

> List.zip uniqueStrings sortValues |> List.sortBy snd |> List.map fst;;
val it : string list = ["foo"; "baz"; "bar"]

由于所有InitEvent值都必须在RefEvent值之前，因此您现在可以附加refEvents到initEvents并返回此组合列表。

确认

您可以验证是否streamGen按预期工作：

open FsCheck.Xunit
open Swensen.Unquote

let isInitEvent = function InitEvent _ -> true | _ -> false
let isRefEvent =  function RefEvent  _ -> true | _ -> false

[<Property(MaxTest = 100000)>]
let ``All InitEvents must come before all RefEvents`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        test <@ s |> Seq.skipWhile isInitEvent |> Seq.forall isRefEvent @>

[<Property(MaxTest = 100000)>]
let ``All InitEvents strings must be unique`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        let initEventStrings =
            s |> Seq.choose (function InitEvent s -> Some s | _ -> None)
        let distinctStrings = initEventStrings |> Seq.distinct

        distinctStrings |> Seq.length =! (initEventStrings |> Seq.length)

[<Property(MaxTest = 100000)>]
let ``All RefEvent names must have an earlier corresponding InitEvent`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        let initEventStrings =
            s
            |> Seq.choose (function InitEvent s -> Some s | _ -> None)
            |> Seq.sort
            |> Seq.toList
        let refEventStrings =
            s
            |> Seq.choose (function RefEvent s -> Some s | _ -> None)
            |> Seq.sort
            |> Seq.toList

        initEventStrings =! refEventStrings

这三个属性都在我的机器上传递。

更宽松的要求

根据对此答案的评论中概述的更宽松的要求，这是一个更新的生成器，它从InitEvents字符串中提取值：

open FsCheck

let streamGen = gen {
    let! uniqueStrings = Arb.Default.NonEmptySet<string>().Generator
    let initEvents = uniqueStrings.Get |> Seq.map InitEvent

    let! refEvents =
        uniqueStrings.Get |> Seq.map RefEvent |> Gen.elements |> Gen.listOf

    return Seq.append initEvents refEvents }

这一次，uniqueStrings是一组非空字符串。

您可以使用基于Seq.map RefEvent生成所有有效值的序列，然后定义从该有效值序列中提取的有效值生成器。最后，创建该生成器生成的值列表。RefEventuniqueStringsGen.elementsRefEventGen.listOf

测试

这些测试表明streamGen根据规则生成值：

open FsCheck.Xunit
open Swensen.Unquote

let isInitEvent = function InitEvent _ -> true | _ -> false
let isRefEvent =  function RefEvent  _ -> true | _ -> false

[<Property(MaxTest = 100000)>]
let ``All InitEvents must come before all RefEvents`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        test <@ s |> Seq.skipWhile isInitEvent |> Seq.forall isRefEvent @>

[<Property(MaxTest = 100000)>]
let ``All InitEvents strings must be unique`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        let initEventStrings =
            s |> Seq.choose (function InitEvent s -> Some s | _ -> None)
        let distinctStrings = initEventStrings |> Seq.distinct

        distinctStrings |> Seq.length =! (initEventStrings |> Seq.length)

[<Property(MaxTest = 100000)>]
let ``All RefEvent names must have an earlier corresponding InitEvent`` () =
    Prop.forAll (streamGen |> Arb.fromGen) <| fun s ->
        let initEventStrings =
            s
            |> Seq.choose (function InitEvent s -> Some s | _ -> None)
            |> Seq.sort
            |> Set.ofSeq

        test <@ s
                |> Seq.choose (function RefEvent s -> Some s | _ -> None)
                |> Seq.forall initEventStrings.Contains @>

这三个属性都在我的机器上传递。

f# - Inconsistent IEnumerable ArgumentException while generating a complex object using FsCheck

1 回答 1

创

确认

更宽松的要求

测试

Related

Reference