Generating unique strings in FsCheck

Question

I need generate unique non-null strings to be used as Dictionary keys. I tried something like:

 public static Gen<NonNull<string>> UniqueStrings()
 {
     return from s in Arb.Default.NonNull<string>().Generator
            select s;
 }

Then I use UniqueString() in:

public static Arb<Foo> Foos()
{
    // Foo's constructor will use the string parameter
    // as key to an internal Dictionary
    return (from nonNullString in UniqueStrings()
            select new Foo(nonNullString.Item)).ToArbitrary();
}

However, I get an exception in properties testing Foo because FsCheck sometimes generates the same string twice, resulting in a DuplicateKeyException.

How can I generate unique strings to be passed into the constructor of Foo?

Grimsley

Have I missed something? Guid-based Guid.NewGuid().ToString(); will be unique string. – Anglesite

Answer 1

You can not force an FsCheck generator to generate unique values, because you essentially have no access to the history of previously generated values, nor will FsCheck itself guarantee uniqueness.

What you can do in this case is say generate say a list of strings, and then unique-ify the list using Distinct() for example. You can then also generate a list of Foo's using a similar approach.

For example:

Gen<Foo[]> res = from s in Arb.Default.Set<string>().Generator
                 select s.Select(ss => new Foo(ss)).ToArray();

(Note you can't use from to get the ss out because C# doesn't allow you to mix different LINQ methods, one is on Gen, one is on IEnumerable)

A propos, I'm wondering if this is not an extra property you want to check. If the user of Foo is supposed to give it a unique string, how is that supported? What happens if they don't?

Pestilential

Do you mind showing an example on how to unique-ify a list of string then pass it to the constructor of Foo? I tried something like from ss in Gen.Default.Set<NonNull<string>>().Generator from s in ss select new Foo(s) but I get a compile error saying there is no SelectMany for the type Gen – Grimsley

I mean Arb.Default – Grimsley

The constructor of Foo will insert the string to an internal Dictionary so if the string parameter is not unique, it will throw. IMHO it's not a great design because the preconditions are so unclear but I have no choice but to stick with this implementation. All I can do is generate more tests hoping to uncover its flaws. – Grimsley

Answer 2

To generate unique strings you can use a Guid generator, it's the standard way to generate unique strings, even across multiple computers.

Appetizer

While guids are unique, they also have the same lenght and set of characters, which may or may not be enough to test an algorithm with a diverse enough set of inputs (null values, long strings, special characters, etc...). – Blackjack

Answer 3

Instead of generating uniq strings you can add a simple check before insert in to the dictionary.

Update: Ok. Do shuffling your string after generation. You can read here
it is about Integer array but you can easily customize it for the string

Thresher

I am trying my best not to modify the implementation of Foo because I just want to prevent FsCheck from generating identical string keys. Modifying Foo's implementation is like avoiding the question instead of solving it. – Grimsley