Introduction to MSIL – Part 8 – The for each Statement

The for each statement; popularized by Visual Basic, humbly accepted by C++, and forever immortalized by a creation lovingly known as ECMA-334 (OK so some people simply call it C#).

In this installment of my open-ended series entitled Introduction to MSIL, I am talking about one of the most popular statements in commercially successful programming languages. Whether your focus has been on Visual Basic, COM, Standard C++, or .NET (or all of the above) you’ve inevitably come across some form of the for each statement.

You may have noticed a trend in this series. As we dig deeper into more interesting constructs, the focus is less and less on MSIL instructions and more on language design and compiler implementations. There is really nothing especially new in the instructions you might use to implement a for each statement. Nevertheless it is useful to understand what makes the statement work and how it is interpreted and converted to MSIL instructions depending on the context in which it is used. This is where you thank your lucky stars that your boss lets you write code in a language with statements that abstract away the dirty secrets hidden behind their elegant exteriors. for each is just such a statement.

Variations of the for each statement, as it relates to .NET, can be found in C#, Visual Basic .NET and C++/CLI. There may also be other languages with a similar statement that I’m not aware of. The examples in this part of the series use C++/CLI only because C# and VB get enough press as it is. As I’ve said before, I am not focusing on a particular compiler’s implementation, but rather demonstrating the techniques that may be used by compilers in general.

Let’s start with a simple example:

array<int>^ numbers = gcnew array<int> { 1, 2, 3 };
 
for each (int element in numbers)
{
    Console::WriteLine(element);
}

numbers is a synthesized reference type extending the built-in System.Array type. It is initialized with three elements and the for each statement executes the statements in the scope block for each of the elements. Pretty straight forward; I’m sure you can imagine the equivalent code in your language of choice. Quite predictably this can be implemented in terms of the following set of instructions:

    .locals init (int32[] numbers,
                  int32 index)
   
// Create the array
                 
    ldc.i4.3
    newarr int32
    stloc numbers
   
// Populate the array
   
    ldloc numbers
    ldc.i4.0 // index
    ldc.i4.1 // value
    stelem.i4
 
    ldloc numbers
    ldc.i4.1 // index
    ldc.i4.2 // value
    stelem.i4
 
    ldloc numbers
    ldc.i4.2 // index
    ldc.i4.3 // value
    stelem.i4
   
    br.s _CONDITION
 
_LOOP:
 
    ldc.i4.1
    ldloc index
    add
    stloc index
    
_CONDITION:
   
    ldloc numbers
    ldlen
    ldloc index
    beq _CONTINUE
   
// for each statements
 
    ldloc numbers
    ldloc index
    ldelem.i4
    call void [mscorlib]System.Console::WriteLine(int32)
   
    br.s _LOOP
 
_CONTINUE:

The only instructions not already discussed in this series are those related to arrays. The newarr instruction pops an integer off the stack indicating the number of elements in the array. It then creates the array of the given type and pushes a reference to it onto the stack. The stelem instruction replaces an element in an array with a given value. The stack needs to be prepopulated with a reference to the array, the index of the element in the array, and the value to store at the given position. Finally, the ldelem instruction loads an element from an array and pushes it onto the stack by first popping off a reference to an array as well as the index into the array.

As you can see, this is not unlike the code that might be generated for a for statement looping over the same elements, as discussed in part 6. Of course the for each statement can be used with more than just types deriving from System.Array. In fact it is capable of enumerating the elements of any type that either implements the IEnumerable interface or even a type providing the same functionality without actually implementing that interface. The degree of support naturally depends on the scope of your language specific implementation. Some languages could even, nay, do provide support for completely unrelated containers in the for each statement. Consider the following example using the Standard C++ Library vector container class:

std::vector<int> numbers;
numbers.reserve(3);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
 
for each (int element in numbers)
{
    std::cout << element << std::endl;
}

In this example, the compiler calls the vector’s begin method to get an iterator pointing to the first element in the container. This iterator is then used to enumerate the elements, incrementing the iterator until it compares equal to the iterator returned by vector’s end method. For each iteration, the iterator is dereferenced with the resulting value assigned to the element variable. The beauty here is that using the for each statement avoids many common errors related to buffer overruns and the like.

Let’s get back to managed code. If the for each statement has to support collections other than arrays, surely this leads to different implementations depending on the use of the statement. Consider the following example:

Collections::ArrayList numbers(3);
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
 
for each (int element in %numbers)
{
    Console::WriteLine(element);
}

As an aside, keep in mind that most of the Standard C++ Library containers that include a constructor taking a single integer typically set the initial size of the container, whereas the .NET collection types use this constructor to set the initial capacity.

So what does for each do in this case? Well the ArrayList type implements the IEnumerable interface with its single GetEnumerator method. The for each statement calls the GetEnumerator method to get an implementation of the IEnumerator interface that is then used to enumerate the collection. Let’s examine a simple implementation for this code:

    .locals init (class [mscorlib]System.Collections.ArrayList numbers,
                  class [mscorlib]System.Collections.IEnumerator enumerator)
   
// Create the array
                 
    ldc.i4.3
    newobj instance void [mscorlib]System.Collections.ArrayList::.ctor(int32)
    stloc numbers
   
// Populate the array
   
    ldloc numbers
    ldc.i4.1
    box int32
    callvirt instance int32 [mscorlib]System.Collections.ArrayList::Add(object)
    pop
 
    ldloc numbers
    ldc.i4.2
    box int32
    callvirt instance int32 [mscorlib]System.Collections.ArrayList::Add(object)
    pop
 
    ldloc numbers
    ldc.i4.2
    box int32
    callvirt instance int32 [mscorlib]System.Collections.ArrayList::Add(object)
    pop
   
// Get the enumerator
 
    ldloc numbers
 
    callvirt instance class [mscorlib]System.Collections.IEnumerator
        [mscorlib]System.Collections.IEnumerable::GetEnumerator()
 
    stloc enumerator
   
    br.s _CONDITION
 
_CONDITION:
   
    ldloc enumerator
    callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
    brfalse.s _CONTINUE
   
// for each statements
 
    ldloc enumerator
    callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()
    call void [mscorlib]System.Console::WriteLine(object)
   
    br.s _CONDITION
 
_CONTINUE:

Well that looks good, but there’s something missing. Can you tell what it is? Since the for each statement is resulting in a new object being created by virtue of calling the GetEnumerator method, it is conceivable that this object requires deterministic cleanup to avoid resource leaks. The enumerator expresses this by implementing the IDisposable interface. Unfortunately, the compiler is not always capable of discerning this at compile time, though if the compiler has enough static type information there is certainly value in taking advantage of it to optimize the generated instructions. As it turns out, the enumerator provided by the ArrayList type does not implement the IDisposable interface. Of course this could change in future so “optimizing” your code for this type of thing is not a wise move. Compilers can use the isinst instruction to determine whether the enumerator implements the IDisposable interface. Arguably this is an oversight in the design of the IEnumerable and IEnumerator interfaces.

To address this quirk, the generic IEnumerator interface introduced in version 2.0 of the .NET Framework makes it explicit by deriving from IDisposable so implementations have to provide a Dispose method even if it does nothing. This certainly simplifies matters for the caller. Collections.Generic.IEnumerator<T> is the return type for the GetEnumerator method from the Collections.Generic.IEnumerable<T> interface implemented by the new generic collection types. For compatibility with existing code, the enumerator implementations also implement the older, non-generic IEnumerator interface. Consider the following example:

Collections::Generic::List<int> numbers(3);
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
 
for each (int element in %numbers)
{
    Console::WriteLine(element);
}

In this case there is no question of whether the enumerator implements IDisposable. The only issue remaining is coming up with a reliable way of calling the Dispose method in the face of exceptions. Here’s a reasonable solution using the exception handling constructs discussed in part 5.

    .locals init (class [mscorlib]System.Collections.Generic.'List`1'<int32> numbers,
                  class [mscorlib]System.Collections.Generic.'IEnumerator`1'<int32> enumerator)
   
// Create the array
                 
    ldc.i4.3
    newobj instance void class [mscorlib]System.Collections.Generic.'List`1'<int32>::.ctor(int32)
    stloc numbers
   
// Populate the array
   
    ldloc numbers
    ldc.i4.1 // value
    callvirt instance void class [mscorlib]System.Collections.Generic.'List`1'<int32>::Add(!0)
 
    ldloc numbers
    ldc.i4.2 // value
    callvirt instance void class [mscorlib]System.Collections.Generic.'List`1'<int32>::Add(!0)
 
    ldloc numbers
    ldc.i4.3 // value
    callvirt instance void class [mscorlib]System.Collections.Generic.'List`1'<int32>::Add(!0)
   
// Get the enumerator
   
    ldloc numbers
   
    callvirt instance class [mscorlib]System.Collections.Generic.'IEnumerator`1'<!0>
        class [mscorlib]System.Collections.Generic.'IEnumerable`1'<int32>::GetEnumerator()
   
    stloc enumerator
   
    .try
    {
       
    _CONDITION:
       
        ldloc enumerator
        callvirt instance bool class [mscorlib]System.Collections.Generic.'IEnumerator`1'<int32>::MoveNext()
        brfalse.s _LEAVE
       
    _STATEMENTS:
   
        ldloc enumerator
        callvirt instance !0 class [mscorlib]System.Collections.Generic.'IEnumerator`1'<int32>::get_Current()
        call void [mscorlib]System.Console::WriteLine(int32)
        br.s _CONDITION
       
    _LEAVE:
       
        leave.s _CONTINUE
    }
    finally
    {
        ldloc enumerator
        callvirt instance void [mscorlib]System.IDisposable::Dispose()
   
        endfinally
    }
   
_CONTINUE:

With the comments and labels in place, it should be pretty easy to follow this code. Let’s walk through it quickly. Two local variables are required, one for the list and one for the enumerator. The strange-looking type names are to support generics in MSIL. 'List`1' indicates that the List type with a single type parameter is to be used. This distinguishes between generic types with the same name but with a different number of type parameters. The type list between the angle brackets denotes the actual types to use in runtime specialization. With the local variables defined, the next step is to create the list using the newobj instruction and populate it by calling its Add method. Generics are primarily intended for creating type-safe collections. A good example of this is the code for adding the numbers to the list. The previous example used an ArrayList so the numbers first had to be boxed before adding them to the collection. In this case we can simply push the number on the stack and call the Add method. We just need to make sure to indicate the particular specialization we require. The Add method’s single parameter is !0 which indicates the zero-based type parameter. Now that the collection is ready, we can implement the actual for each loop. To begin enumerating we first get the IEnumerator<T> implementation from the collection and store it in out enumerator local variable. At this point we enter the protected range of instructions, calling the enumerator’s MoveNext method until it returns false. The finally exception handler is then used to call the enumerator’s Dispose method.


© 2004 Kenny Kerr

Published Wednesday, December 15, 2004 11:26 AM by KennyKerr

Comments

# re: Introduction to MSIL – Part 8 – The for each Statement

Monday, June 12, 2006 4:18 AM by Saqlain Abbas
Excellent Tutorial