Autofixture: Creating dictionaries with relatively small key type fails ocasionally

[dzendras]

There is a problem with generating dictionaries that have a relatively small key type (like System.Byte).
Sometimes unit tests fail because of duplicate keys:

_System.ArgumentException : An item with the same key has already been added._

So even though AutoFixture creates dictionaries that have only 3 elements (well at least that's what I can observe), it doesn't check whether the generated keys are unique.

In order to reproduce it, please run the following test:

    [Fact]
    public void Duplicate_entries()
    {
        var fixture = new Fixture();
        for (int i = 0; i < 1000; ++i)
        {
            fixture.Create<IDictionary<byte, string>>();
        }
    }

The question is: is it a bug that can be fixed, or is it a corner case where AutoFixture is not supposed to be used?

[moodmosaic]

Thank you for reporting this. – By default, the Fixture is configured to create numbers using a constrained non-deterministic sequence.

One way to solve your problem is by making the Fixture instance _more_ deterministic:

c# fixture.Customizations.Add(new NumericSequenceGenerator());

This changes the Fixture so that it generates sequences of consecutive numbers, starting at 1.

---

It looks weird to me the fact that this behaves erratically _as-is_, since a HashSet<T> is used internally... This _might_ be a bug.

[dzendras]

Thanks. Using NumericSequenceGenerator worked.

[ploeh]

@moodmosaic, according to the documentation of RandomNumericSequenceGenerator, it

Creates a sequence of random, unique, numbers starting at 1.

Note the word _uniqe_ here...

This looks strange to me, then, because fixture.Create<IDictionary<byte, string>>() should create a dictionary with only three elements, and I would expect the keys to be unique.

Here's a theory, though:

Since a default Fixture is used in the above repro, RepeatCount is 3, which means that it's going to create in all 3000 byte values. This means that it's going to exhaust the byte range of 256 numbers multiple (approximately 12) times.

Every time this happens, I'd expect RandomNumericSequenceGenerator to start over with a new sequence of 256 unique numbers. However, if this happens in the midst of populating a dictionary, it may use 1-2 values from the set that becomes exhausted, and then 1-2 values from the new set. There's a small risk that one of the values drawn from the new set is equal to one of the values from the old set. However, unless my back-of-the-envelope calculations are wrong, this should only happen with a chance of approximately 1.5 %, so even repeated 12 times, the above repro should only fail 16-17 % of the time it's run. (I actually haven't have time to run it, so I don't know if it fails more or less often.)

[dzendras]

I might be wrong as I didn't go deep into how RandomNumericSequenceGenerator works.
What if we've already generated so many ints we are in a range that exceeds the byte size?

Then all numbers mod 256 cause a collision, don't they?

Example:
number = 0, CreateRandom(byte) returns 0
number = 256, CreateRandom(byte) returns 0
number = 512, CreateRandom(byte) returns 0

[adamchester]

@ploeh what if it also prevents the last ’n' numbers from being regenerated after a new sequence starts? Would that make the risk far lower?

[ploeh]

Here's what I think RandomNumericSequenceGenerator _ought_ to do:

Bytes

Draw values from the set [1 .. 255], making sure that each value is drawn only once. The 256th time a value is drawn, it would have to reset the set to [1 .. 255] and start over.

Shorts

Draw values from the set [1 .. 255], making sure that each value is drawn only once. The 256th time a value is drawn, it should draw values from the set [256 .. 32767], making sure that each value is drawn only once. The 32768th time a value is drawn, it would have to reset the set to [1 .. 255] and start over.

Ints

Draw values from the set [1 .. 255], making sure that each value is drawn only once. The 256th time a value is drawn, it should draw values from the set [256 .. 32767], making sure that each value is drawn only once. The 32768th time a value is drawn, it should draw values from the set [32768 .. 2147483647], making sure that each value is drawn only once. The 2147483648th time a value is drawn, it would have to reset the set to [1 .. 255] and start over.

I'm sure you can extrapolate the algorithm for long integers :wink:

If it doesn't do this ATM, I would consider that a bug. The above was the original specification.

[moodmosaic]

Nope, I think the original spec was slightly different; when the 256th time a value is drawn, the set [1 .. 255] is exhausted, and then random numbers are drawn from the next set [256 .. 32767], and so on.

Numbers drawn from the set(s) are converted currently – e.g. for a byte, _20410_ will be converted to _186_.

---

The test below always passes, unless the _exercise_ and _verification_ phases are wrapped in an infinite loop.

``` c#
[Fact]
public void Test()
{
var fixture = new Fixture();

// See the test failing by wrapping this part and below in a `while` loop.

var actual = new List<byte>();
for (int i = 1; i <= byte.MaxValue; i++)
    actual.Add(fixture.Create<byte>());
actual.Sort();

var expected = new List<byte>();
for (int i = 1; i <= byte.MaxValue; i++)
    expected.Add((byte)i);
expected.Sort();
Assert.True(expected.SequenceEqual(actual));

}
```

---

TBH, I'd prefer the algorithm that @ploeh describes above, as it doesn't seem to requires conversions :wink:

[ploeh]

@moodmosaic, I always had the algorithm described _here_ in mind - that other comment implicitly described the algorithm for 'larger' number types, such as 32- and 64-bit integers. Sorry that I wasn't more precise.

However, I think the current _observable_ behaviour fits that description. Although it internally works by conversion from long to byte, that conversion seems to uniformly distribute values drawn from that set.

To test that hypotheses, I wrote the following F# expression:

F# [256L .. 32767L] |> List.map byte |> Seq.countBy id |> Seq.iter (fun (v, l) -> printfn "%i, %i" v l)

This prints out CSVs that I then pasted into Excel and used to produce this bar chart:

It clearly shows that the byte values are uniformly distributed, so if the original selection of values from [256L .. 32767L] is sufficiently random, wouldn't we expect the resulting byte value series to be random?

That would be my immediate conclusion, but experience has also taught me to be quite cautious when it comes to thinking about mathematical randomness :flushed:

[ploeh]

Now that I think about this some more, I've come to realise that the current behaviour isn't _quite_ what it ought to be. Because values above 255 are randomly drawn from the set [256L .. 32767L], it means that it'd be possible for example to draw these three values: [20410L; 20666L; 20922L]. These are all in the set, and are all distinct.

However, when converted to bytes, this happens:

``` F#

[20410L; 20666L; 20922L] |> List.map byte;;
val it : byte list = [186uy; 186uy; 186uy]
```

Related to the originally reported problem here, when you ask AutoFixture to produce lots of byte values, you're only guaranteed that the first 255 values are distinct. After that, there are no more guarantees.

[ploeh]

Here's a repro of the problem:

``` F#
open Ploeh.AutoFixture

let dupes count =
let fixture = Fixture ()

List.init count (fun _ -> fixture.Create<byte>())
|> Seq.windowed 2
|> Seq.map (Seq.distinct >> Seq.length)
|> Seq.filter ((=) 1)
|> Seq.length

[1 .. 1000] |> List.map dupes
```

The dupes function reports the number of immediate duplicates if finds in the list of created byte values. By a duplicate here is meant that the the same value is produced twice in a row, e.g. in [132; 111; 77; 77; 123; 132], the numbers 77 would be considered duplicates. Notice that this list also has 132 appearing twice (which seems suspect), but the dupes function doesn't report such duplicates.

If you take the reported values and plot them in a bar chart, you get something like this:

Notice that below 255, no duplicates are present. This is expected.

However, the higher the number of values requested becomes, the more duplicates are observed.

As described above, we can't rule out the occasional duplicate around 256, 512, 768, 1024, 1280, etc., but _only one_. However, in this bar chart, we see observations of up to 10 duplicates in some sequences.

This explains the OP.

[moodmosaic]

@ploeh, agreed. The current observable behaviour ought to fit the algorithm you described here.

[..] when you ask AutoFixture to produce lots of byte values, you're only guaranteed that the first 255 values are distinct. After that, there are no more guarantees.

Yes, exactly. – That's the current situation...

The converted values might be uniformly distributed, however there are still chances to get the same byte value multiple times, due to conversion, as you show in this great repro.

---

I'd _love_ to rewrite the algorithm in F#, ...if it was possible to use 2 languages in the _same_ Class Library :smiley:

[Pvlerick]

I'm happy to pick this up if nobody is already working on it.

[moodmosaic]

@Pvlerick Go ahead :smiley:

[Pvlerick]

On a side note, the header comment on the class

Creates a sequence of random, unique, numbers starting at 1.

is not really correct since it's possible to give limits to the constructor - they might be negative for example.

[Pvlerick]

Re-reading the intended specification, I'm starting to wonder if multiple generators should be created instead of one that handles all the types.

Here is a scenario:

• I start by requesting 255 bytes, I will get 255 uniques from [1 .. 255] - and deplete that set
• I request a short and I should get something from [256 .. 32767] - the [1 .. 255] set is depleted so we start getting value from the next set
• I request a byte, I should get something from [1 .. 255] - the [1 .. 255] set is reset and one value is taken
• I request a short: what now? Do I get something from [256 .. 32767], or do I get something from [1 .. 255] ?

Getting a value from [1 .. 255] seems weird in that case, so it might be that the same generator should not be in charge of answering all those requests.

[ploeh]

It sounds like a good idea to have a generator instance for bytes, another for Int16s, another for Int32s, another for Int64s.

[Pvlerick]

I'm still fiddling with this, and I have a few comments/thoughts that you might help me address.

Currently, RandomNumericSequenceGenerator has a constructor that takes an array of long that are used as limits. The first number is the lower bound and the following are successive upper bounds; i.e: if you give it [5;42;98] the first numbers will be drawn from [5..42] until depleted, then from [43...98] until depleted. This contradicts with the header comment on the class that states Creates a sequence of random, unique, numbers starting at 1.

I somehow feel that it would be best to have a parameterless constructor and simply respect the algorithm you describe there.
However, going down that path introduces a breaking change, even inside the project as some other class are using RandomNumericSequenceGenerator internally. Having said that, most of those classes simply want a way to generates unique random numbers between two boundaries and reset when all numbers have been drawn, so I am wondering if we couldn't write another class to do that and use it instead.

The other issue I have with the limits in the constructor is that they give rise to weird scenarios. If I give it limits such as [1000;2500] and then draw a byte, what should I return? I think it's confusing to convert the drawn value to a byte since it won't be between the limits I set (you can also call it quite dumb to request a value between 0 and 255 to a generator you explicitly told to generate between 1000 and 2500 :smile:).

On a side note, implementing the intended algorithm is a nice problem to think about and I'm happy to do it, but I don't think it'll fix the original issue of this topic.
I actually think that there is no way we can fix that issue: if you keep on drawing sets of 3 bytes from the same generator, you are bound to eventually get duplicates.

[ploeh]

I think we can safely change the wording of the API documentation without calling it a breaking change. Given that RandomNumericSequenceGenerator already has a constructor overload that enables a user to supply an array of limits, that sentence is already incorrect today.

What breaking changes are introduced?

[Pvlerick]

If the constructor taking limits it kept as it is but multiple generators are used behind the scene, let's consider the following code

C# fixture.Customizations.Add(new RandomNumericSequenceGenerator(42000, int.MaxValue)); var r = fixture.Create<byte>(); //What is the value of that byte?

To me it looks counter intuitive to be able to give limits to RandomNumericSequenceGenerator and then request an object of a type that has boundaries lower than those limits and still get something in return. At the moment this is handled by casting the generated number in the requested type.

The other option is to change RandomNumericSequenceGenerator to not take limits and strictly respect the algorithm described here and always start at 1. But that'll break existing code.

[ploeh]

Don't we have that problem already today?

[Pvlerick]

Yes, the current implementation has that problem. A more compelling example:

``` C#
var f = new Fixture();
f.Customizations.Add(new RandomNumericSequenceGenerator(240, byte.MaxValue, int.MaxValue));

foreach (var item in f.CreateMany(300))
{
Console.WriteLine(item);
}

Will return something like

245
252
254
247
246
244
248
253
250
251
240
255
243
242
249
5
77
135
210
218
51
220
108
242
```

We can see that after the initial 15 draws, we are back in the [1..255] set, while our lower limit was explicitly set to 240.

Having a separate generator for each type should solve the issue, but comes with other issues: should we have a separate generator for byte, short, int and long and one single generator for all other types or one for each type (double, float, etc...). In both cases I think we'll end up with very similar code in all those classes, and I'm wondering if it's worth it :pensive:

[ploeh]

Since we already have that problem, I don't think doing a new implementation (that fixes some other problems) will make AutoFixture _worse_.

It _could_ be safer to define a public generator per type, but I agree that it'd most likely involve a lot of duplication, so I'm not sure it'd be worth it.

If only .NET had type classes... :broken_heart:

[moodmosaic]

If only .NET had type classes... :broken_heart:

If _only_... :disappointed:

[Pvlerick]

Since it doesn't solve the original issue, I think it's best to leave it as is for now.

The only _issue_ is that we don't get that behavior with the current implementation.

[moodmosaic]

The only _issue_ is that we don't get that behavior with the current implementation.

That's true...

[Pvlerick]

To be honest, I don't see how to move on my own, design wise. I see three ways forward:

1. Rewrite RandomNumericSequenceGenerator to follow the desired algorithm, but IMHO then it should only have a default constructor - breaking change.
2. Write multiple generators - code duplication
3. Do nothing

[moodmosaic]

Thinking out loud, doing nothing can be a wise decision, e.g. given 1 and 2 above. :confused:

[ploeh]

Couldn't this bug be addressed in DictionaryFiller by making sure that duplicate keys don't occur?

[moodmosaic]

Yes, probably with defensive coding; by checking first whether the key already exists in the dictionary.

[Pvlerick]

I didn't know that existed :frowning:

I'll check if what you suggest is possible, thanks!