C# in Depth

Cover of C# in Depth
Order now (3rd edition)

The bug (fixed before printing) in listing 6.7

Chapter 6: Implementing iterators the easy way: 6.3.3

Created: 24/02/2008
Last updated: 25/02/2008

There was a subtle bug in my original code for listing 6.8. I think it's instructive to have a look at it, just so you know to avoid it yourselves. (At the same time, it allows me to thank Eric for finding it. I suspect relatively few reviewers would have done so, even though it's nothing to do with knowing C# inside out.)

Here's the correct code:

public IEnumerator<T> GetEnumerator()
{
    T value = start;
    while (value.CompareTo(end) < 0)
    {
        yield return value;
        value = GetNextValue(value);
    }
    if (value.CompareTo(end) == 0)
    {
        yield return value;
    }
}

And here's the broken code:

// Broken! Do not use!
public IEnumerator<T> GetEnumerator()
{
    T value = start;
    while (value.CompareTo(end) <= 0)
    {
        yield return value;
        value = GetNextValue(value);
    }
}

So what's wrong with the broken code? Well, consider a Range<byte> with a lower bound of 0, an upper bound of 255, stepping up by 1 each time. Clearly that should produce 0, 1, 2 ... 254, 255 and then stop. But how would it stop in the broken code? It can't - once you add 1 to 255 (as a byte) you start back at 0, so no comparison with 255 is ever going to yield a positive value.

The working code finishes when the value just returned reaches or exceeds the end point. In fact, there's still a bug here. Although we carefully stop if we reach the end point (carefully yielding it due to the range being inclusive) we could still overflow. Take the same example as before, but stepping up by 2 bytes each time. We'd go straight from 254 to 0, creating the same problem as before.

The most appropriate solution may be to change GetNextValue to indicate when it's noticed overflow (or any other reason not to return a value). For instance, we could change the signature to:

bool GetNextValue(ref T value)

The iteration code could then become:

public IEnumerator<T> GetEnumerator()
{
    bool hasMore;
    T value = start;
    do
    {
        yield return value;
        hasMore = GetNextValue(ref value);
    }
    while (hasMore && value.CompareTo(end) <= 0)
}

I haven't yet implemented this in MiscUtil - it's relatively tricky, compared with the previous simple stepping - but I hope to do so at some point.

The moral of the story is to never claim that something is "quite straightforward" - it will do its best to prove you wrong!