Iterator bug of (more likely) a very subtle behavior ?

Question

Hi all,

My problem requires 3 (not too long functions) to reproduce (VS2010 / .NET 4)
In the first case, my IEnumerable is not evaluated (through the ToList() method)
I can't see why..

// Main program

private void ButtonTest_Click(object sender, RoutedEventArgs args)  
{  
    int[] indexes = new int[] { 2, 2, 2, 2, 2, 2 };  
    var query = Odometer(indexes);  
    // 1) Iterator not evaluated ???  
    var temp = query.ToList();  
    MessageBox.Show(AsString(temp[3]));   

    // 2) OK in this case  
    int count = 0;  
    foreach (int[] item in query)  
    {  
        count++;  
        if (count == 3)  
            MessageBox.Show(AsString(item));  
    }  
}  

/// <summary>  
/// Generate all tuples between 0 and indexes[i]-1  
/// Ex :   
/// Odometer(new int[]{2, 3}); // (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2)  
/// </summary>  
/// <param name="indexes"></param>  
/// <returns></returns>  
public static IEnumerable<int[]> Odometer(int[] indexes)  
{  
    int[] result = new int[indexes.Length];  
    for (int i = 0; i < indexes.Length; i++)  
        result[i] = -1;  

    int ptr = 0;  
    while (ptr >= 0)  
    {  
        while (ptr < indexes.Length)  
        {  
            result[ptr++]++;  
            continue;  
        }  

        ptr--;  
        while (result[ptr] < indexes[ptr])  
        {  
            yield return result;  
            result[ptr]++;  
        }  

        result[ptr]--;  
        while (result[ptr] == indexes[ptr] - 1)  
        {  
            result[ptr] = -1;  
            ptr--;  
            if (ptr < 0)  
                break;  
        }  
    }  
}  

/// <summary>  
/// Format an IList of T    
/// </summary>  
/// <typeparam name="T"></typeparam>  
/// <param name="array"></param>  
/// <returns></returns>  
private static string AsString<T>(IList<T> array)  
{  
    StringBuilder builder = new StringBuilder();  
    foreach (T item in array)  
        builder.AppendFormat("{0}, ", item);  
    if (builder.Length >= 2)  
        builder.Length -= 2;  
    return builder.ToString();  
}  

Thanks in advance for your help
Philippe

Answer 1

Your IEnumerable is runned when:

var temp = query.ToList();

I made a break point in Odometer and sure enough it breaked. It contains a lots of list of -1. Maybe you need a better Odometer method?

EDIT: The problem is that you are yield returning the same array all the time. So it will always have the same value. You should read something about references in .Net/C#. Also, the method does only need the length so only send the length with it.

public static IEnumerable<int[]> Odometer(int[] indexes)
{
    int[] result = new int[indexes.Length];
    for (int i = 0; i < indexes.Length; i++)
        result[i] = -1;

    int ptr = 0;
    while (ptr >= 0)
    {
        while (ptr < indexes.Length)
        {
            result[ptr++]++;
            continue;
        }

        ptr--;
        while (result[ptr] < indexes[ptr])
        {
            //HERE
            //Clones the array so you are returning a new array - thanks Jon, for improvement on the Array.Copy code.
            yield return result.ToArray();

            result[ptr]++;
        }

        result[ptr]--;
        while (result[ptr] == indexes[ptr] - 1)
        {
            result[ptr] = -1;
            ptr--;
            if (ptr < 0)
                break;
        }
    }
}

Answer 2

As lasseespeholt says, the problem is that you're repeatedly yielding references to the same array, then mutating that array.

Calling ToList() will iterate over the whole iterator, so you'll end up with a list of the same reference multiple times, and by the time you examine the contents it will all be -1.

One simple fix is to change Odometer's yield return statement to:

yield return result.ToArray();

This will clone the array at the point where you yield it, so the list will have different array references.