Understanding LINQ to Objects (3) Iterator Pattern and foreach

1562 words

8 minutes

Understanding LINQ to Objects (3) Iterator Pattern and foreach

2010-03-14

.NET

/

C#

/

LINQ

/

LINQ to Objects

/

LINQ via C#

[LINQ via C#] - [LINQ to Objects]

LINQ to Objects provides fluent query methods in a functional paradigm. All these queries work with IEnumerable sequence, and the values in the sequence will be processed with either deferred execution or immediate execution. To sequentially access the values in an IEnumerable sequence, iterator pattern is widely used in .NET and is also a built-in feature of C# language.

Iteration pattern#

Iteration pattern includes a sequence and an iterator. In .NET, they are like:

1
public class Sequence
2
{
3
    public Iterator GetEnumerator() => new Iterator();
4
}
5

6
public class Iterator
7
{
8
    public bool MoveNext() => false;
9

10
    public object Current { get; }
11
}

And the generic version is:

1
public class Sequence<T>
2
{
3
    public Iterator<T> GetEnumerator() => new Iterator<T>();
4
}
5

6
public class Iterator<T>
7
{
8
    public bool MoveNext() => false;
9

10
    public T Current { get; }
11
}

Above sequence/Iterator classes demonstrate the minimum requirements of using a foreach loop to iterate and access each value in the container:

The container should have
- a GetEnumerable method, which returns an iterator with:
  - a MoveNext method returns a boolean value to indicate if there are still a value that can be puuled.
  - a Current property with a getter, which returns the current value to be pulled from the container when MoveNext returns true.

The foreach and in keywords#

Now foreach loop can be compiled for above non-generic and generic containers:

1
public static partial class IteratorPattern
2
{
3
    public static void ForEach<T>(Sequence sequence, Action<T> processValue)
4
    {
5
        foreach (T value in sequence)
6
        {
7
            processValue(value);
8
        }
9
    }
10

11
    public static void ForEach<T>(Sequence<T> sequence, Action<T> processValue)
12
    {
13
        foreach (T value in sequence)
14
        {
15
            processValue(value);
16
        }
17
    }
18
}

These foreach loops are compiled to while loops, and GetEnumeraotor/MoveNext/Current calls:

1
public static void CompiledForEach<T>(Sequence sequence, Action<T> next)
2
{
3
    Iterator iterator = sequence.GetEnumerator();
4
    try
5
    {
6
        while (iterator.MoveNext())
7
        {
8
            T value = (T)iterator.Current;
9
            next(value);
10
        }
11
    }
12
    finally
13
    {
14
        (iterator as IDisposable)?.Dispose();
15
    }
16
}
17

18
public static void CompiledForEach<T>(Sequence<T> sequence, Action<T> next)
19
{
20
    Iterator<T> iterator = sequence.GetEnumerator();
21
    try
22
    {
23
        while (iterator.MoveNext())
24
        {
25
            T value = iterator.Current;
26
            next(value);
27
        }
28
    }
29
    finally
30
    {
31
        (iterator as IDisposable)?.Dispose();
32
    }
33
}

The difference is, the non-generic Iterator’s Current property returns an object, it has to be explicitly casted to type T specified in the foreach loop, which is a chance to fail.

IEnumerable and IEnumerator#

To implements iterator pattern, IEnumerable for sequence and IEnumerator for iterator are built in .NET from the beginning:

1
namespace System.Collections
2
{
3
    public interface IEnumerable // Sequence.
4
    {
5
        IEnumerator GetEnumerator();
6
    }
7

8
    public interface IEnumerator // Iterator.
9
    {
10
        object Current { get; }
11

12
        bool MoveNext();
13

14
        void Reset(); // Only for COM interoperability.
15
    }
16
}

.NET 2.0 introduced generics, so IEnumerable and IEnumerator are added:

1
namespace System
2
{
3
    public interface IDisposable
4
    {
5
        void Dispose();
6
    }
7
}
8

9
namespace System.Collections.Generic
10
{
11
    public interface IEnumerable<T> : IEnumerable // Sequence.
12
    {
13
        IEnumerator<T> GetEnumerator();
14
    }
15

16
    public interface IEnumerator<T> : IDisposable, IEnumerator // Iterator.
17
    {
18
        T Current { get; }
19
    }
20
}

Later, .NET 4.0 introduces covariance and contravariance. T is covariant for generic interfaces IEnumerable and IEnumerable. So they became:

1
namespace System.Collections.Generic
2
{
3
    public interface IEnumerable<out T> : IEnumerable // Sequence.
4
    {
5
        IEnumerator<T> GetEnumerator();
6
    }
7

8
    public interface IEnumerator<out T> : IDisposable, IEnumerator // Iterator.
9
    {
10
        T Current { get; }
11
    }
12
}

When a type implements IEnumerable, its instance is guaranteed to be able to work in foreach loop.

S0 there are quite a few terms around iterator pattern, and here is a summary:

IEnumerable/IEnumerable: represents sequence, also called container, aggregate object, etc.
IEnumerator/IEnumerator: represents iterator.

It might be more straightforward if these interfaces were named IItorable/IIterator, just like in JavaScript. Just keep in mind C#’s foreach is a syntactic sugar for iterator pattern, or the enumerable/enumerator pattern (Actually, C# 5.0’s async/await syntactic sugar follows a similar awaitable/awaitor pattern).

foreach loop vs. for loop#

As fore mentioned, array T[] implements IEnumerable if it is single dimensional and zero–lower bound. foreach loop for array:

1
public static void ForEach<T>(T[] array, Action<T> next)
2
{
3
    foreach (T value in array)
4
    {
5
        next(value);
6
    }
7
}

will be compiled into a for loop for better performance:

1
public static void CompiledForEach<T>(T[] array, Action<T> next)
2
{
3
    for (int index = 0; index < array.Length; index++)
4
    {
5
        T value = array[index];
6
        next(value);
7
    }
8
}

And so is string:

1
public static void ForEach(string @string, Action<char> next)
2
{
3
    foreach (char value in @string)
4
    {
5
        next(value);
6
    }
7
}
8

9
public static void CompiledForEach(string @string, Action<char> next)
10
{
11
    for (int index = 0; index < @string.Length; index++)
12
    {
13
        char value = @string[index];
14
        next(value);
15
    }
16
}

Non-generic vs. generic sequence#

IEnumerable is stronger-typed and should always be preferred. However, for above historical reason, some types in .NET only implement IEnumerable. To inspect these types, just need to query the IEnumerable types, and the IEnumerable types, then use Except query method:

1
public static IEnumerable<Type> NonGenericSequences(Assembly assembly)
2
{
3
    Type nonGenericEnumerable = typeof(IEnumerable);
4
    Type genericEnumerable = typeof(IEnumerable<>);
5
    return assembly
6
        .ExportedTypes
7
        .Where(type => type != nonGenericEnumerable && nonGenericEnumerable.GetTypeInfo().IsAssignableFrom(type))
8
        .Except(assembly
9
            .ExportedTypes
10
            .Where(type => type != genericEnumerable && type.IsAssignableTo(genericEnumerable)))
11
        .OrderBy(type => type.FullName);
12
}

Here Type.IsAssignableFrom is a method provided by .NET. It only works for non-generic types, and closed generic types like typeof(IEnumerable). So another IsAssignableTo extension method has to be created for open generic types like typeof(IEnumerable<>):

1
public static partial class TypeExtensions
2
{
3
    public static bool IsAssignableTo(this Type from, Type to)
4
    {
5
        if (to.GetTypeInfo().IsAssignableFrom(from))
6
        {
7
            return true;
8
        }
9

10
        if (!to.GetTypeInfo().IsGenericTypeDefinition)
11
        {
12
            return false;
13
        }
14

15
        if (from.GetTypeInfo().IsGenericType && from.GetGenericTypeDefinition() == to)
16
        {
17
            return true; // Collection<int> is assignable to Collection<>.
18
        }
19

20
        if (to.GetTypeInfo().IsInterface && from.GetTypeInfo().GetInterfaces().Any(
21
            @interface => @interface.GetTypeInfo().IsGenericType && @interface.GetGenericTypeDefinition() == to))
22
        {
23
            return true; // Collection<>/Collection<int> assignable to IEnumerable<>/ICollection<>.
24
        }
25

26
        Type baseOfFrom = from.GetTypeInfo().BaseType;
27
        return baseOfFrom != null && IsAssignableTo(baseOfFrom, to);
28
    }
29
}

The following code queries non-generic sequences in mscorlib.dll and System.dll:

1
public static void NonGenericSequences()
2
{
3
    foreach (Type nonGenericSequence in NonGenericSequences(typeof(object).GetTypeInfo().Assembly)) // mscorlib.dll.
4
    {
5
        Trace.WriteLine(nonGenericSequence.FullName);
6
    }
7
    // System.Array
8
    // System.Collections.ArrayList
9
    // System.Collections.BitArray
10
    // System.Collections.CollectionBase
11
    // System.Collections.DictionaryBase
12
    // System.Collections.Hashtable
13
    // System.Collections.ICollection
14
    // System.Collections.IDictionary
15
    // System.Collections.IList
16
    // System.Collections.Queue
17
    // System.Collections.ReadOnlyCollectionBase
18
    // System.Collections.SortedList
19
    // System.Collections.Stack
20
    // System.Resources.IResourceReader
21
    // System.Resources.ResourceReader
22
    // System.Resources.ResourceSet
23
    // System.Runtime.Remoting.Channels.BaseChannelObjectWithProperties
24
    // System.Runtime.Remoting.Channels.BaseChannelSinkWithProperties
25
    // System.Runtime.Remoting.Channels.BaseChannelWithProperties
26
    // System.Security.AccessControl.AuthorizationRuleCollection
27
    // System.Security.AccessControl.CommonAcl
28
    // System.Security.AccessControl.DiscretionaryAcl
29
    // System.Security.AccessControl.GenericAcl
30
    // System.Security.AccessControl.RawAcl
31
    // System.Security.AccessControl.SystemAcl
32
    // System.Security.NamedPermissionSet
33
    // System.Security.Permissions.KeyContainerPermissionAccessEntryCollection
34
    // System.Security.PermissionSet
35
    // System.Security.Policy.ApplicationTrustCollection
36
    // System.Security.Policy.Evidence
37
    // System.Security.ReadOnlyPermissionSet
38

39
    foreach (Type nonGenericSequence in NonGenericSequences(typeof(Uri).GetTypeInfo().Assembly)) // System.dll.
40
    {
41
        nonGenericSequence.FullName.WriteLine();
42
    }
43
    // System.CodeDom.CodeAttributeArgumentCollection
44
    // System.CodeDom.CodeAttributeDeclarationCollection
45
    // System.CodeDom.CodeCatchClauseCollection
46
    // System.CodeDom.CodeCommentStatementCollection
47
    // System.CodeDom.CodeDirectiveCollection
48
    // System.CodeDom.CodeExpressionCollection
49
    // System.CodeDom.CodeNamespaceCollection
50
    // System.CodeDom.CodeNamespaceImportCollection
51
    // System.CodeDom.CodeParameterDeclarationExpressionCollection
52
    // System.CodeDom.CodeStatementCollection
53
    // System.CodeDom.CodeTypeDeclarationCollection
54
    // System.CodeDom.CodeTypeMemberCollection
55
    // System.CodeDom.CodeTypeParameterCollection
56
    // System.CodeDom.CodeTypeReferenceCollection
57
    // System.CodeDom.Compiler.CompilerErrorCollection
58
    // System.CodeDom.Compiler.TempFileCollection
59
    // System.Collections.Specialized.HybridDictionary
60
    // System.Collections.Specialized.IOrderedDictionary
61
    // System.Collections.Specialized.ListDictionary
62
    // System.Collections.Specialized.NameObjectCollectionBase
63
    // System.Collections.Specialized.NameObjectCollectionBase + KeysCollection
64
    // System.Collections.Specialized.NameValueCollection
65
    // System.Collections.Specialized.OrderedDictionary
66
    // System.Collections.Specialized.StringCollection
67
    // System.Collections.Specialized.StringDictionary
68
    // System.ComponentModel.AttributeCollection
69
    // System.ComponentModel.ComponentCollection
70
    // System.ComponentModel.Design.DesignerCollection
71
    // System.ComponentModel.Design.DesignerOptionService + DesignerOptionCollection
72
    // System.ComponentModel.Design.DesignerVerbCollection
73
    // System.ComponentModel.EventDescriptorCollection
74
    // System.ComponentModel.IBindingList
75
    // System.ComponentModel.IBindingListView
76
    // System.ComponentModel.ListSortDescriptionCollection
77
    // System.ComponentModel.PropertyDescriptorCollection
78
    // System.ComponentModel.TypeConverter + StandardValuesCollection
79
    // System.Configuration.ConfigXmlDocument
80
    // System.Configuration.SchemeSettingElementCollection
81
    // System.Configuration.SettingElementCollection
82
    // System.Configuration.SettingsAttributeDictionary
83
    // System.Configuration.SettingsContext
84
    // System.Configuration.SettingsPropertyCollection
85
    // System.Configuration.SettingsPropertyValueCollection
86
    // System.Configuration.SettingsProviderCollection
87
    // System.Diagnostics.CounterCreationDataCollection
88
    // System.Diagnostics.EventLogEntryCollection
89
    // System.Diagnostics.EventLogPermissionEntryCollection
90
    // System.Diagnostics.InstanceDataCollection
91
    // System.Diagnostics.InstanceDataCollectionCollection
92
    // System.Diagnostics.PerformanceCounterPermissionEntryCollection
93
    // System.Diagnostics.ProcessModuleCollection
94
    // System.Diagnostics.ProcessThreadCollection
95
    // System.Diagnostics.TraceListenerCollection
96
    // System.Net.Configuration.AuthenticationModuleElementCollection
97
    // System.Net.Configuration.BypassElementCollection
98
    // System.Net.Configuration.ConnectionManagementElementCollection
99
    // System.Net.Configuration.WebRequestModuleElementCollection
100
    // System.Net.CookieCollection
101
    // System.Net.CredentialCache
102
    // System.Net.WebHeaderCollection
103
    // System.Security.Authentication.ExtendedProtection.Configuration.ServiceNameElementCollection
104
    // System.Security.Authentication.ExtendedProtection.ServiceNameCollection
105
    // System.Security.Cryptography.AsnEncodedDataCollection
106
    // System.Security.Cryptography.OidCollection
107
    // System.Security.Cryptography.X509Certificates.X509Certificate2Collection
108
    // System.Security.Cryptography.X509Certificates.X509CertificateCollection
109
    // System.Security.Cryptography.X509Certificates.X509ChainElementCollection
110
    // System.Security.Cryptography.X509Certificates.X509ExtensionCollection
111
    // System.Text.RegularExpressions.CaptureCollection
112
    // System.Text.RegularExpressions.GroupCollection
113
    // System.Text.RegularExpressions.MatchCollection
114
}

As fore mentioned, most of these types can be converted to generic sequence by OfType query method.

EnumerableAssert class#

In Microsoft’s unit test framework MSTest, there are only 3 built-in assert classes provided:

Assert: for general purpose.
StringAssert: for string.
CollectionAssert: for ICollection

After understanding the IEnumerable/IEnumerator pattern in .NET, an EnumerableAssert class can be defined for IEnumerable.

1
public static partial class EnumerableAssert
2
{
3
    public static void AreSequentialEqual<T>(
4
        IEnumerable<T> expected,
5
        IEnumerable<T> actual,
6
        IEqualityComparer<T> comparer = null,
7
        string message = null,
8
        params object[] parameters)
9
    {
10
        if (expected == null && actual == null)
11
        {
12
            return;
13
        }
14

15
        message = string.IsNullOrEmpty(message) ? string.Empty : $"{message} ";
16
        if (expected == null)
17
        {
18
            Assert.IsNull(
19
                actual,
20
                $"{message}Expected sequence is null, but actual sequence is not null.",
21
                parameters);
22
            return;
23
        }
24

25
        Assert.IsNotNull(
26
            actual,
27
            $"{message}Expected sequence is not null, but actual sequence is null.",
28
            parameters);
29

30
        comparer = comparer ?? EqualityComparer<T>.Default;
31
        using (IEnumerator<T> expectedItorator = expected.GetEnumerator())
32
        using (IEnumerator<T> actualIterator = actual.GetEnumerator())
33
        {
34
            int expectedIndex = 0;
35
            for (; expectedItorator.MoveNext(); expectedIndex++)
36
            {
37
                Assert.IsTrue(
38
                    actualIterator.MoveNext(),
39
                    $"{message}Expected sequence has more than {expectedIndex} value(s), but actual sequence has {expectedIndex} value(s).",
40
                    parameters);
41

42
                T expectedValue = expectedItorator.Current;
43
                T actualValue = actualIterator.Current;
44
                Assert.IsTrue(
45
                    comparer.Equals(expectedValue, actualValue),
46
                    $"{message}Expected and actual sequences' values are not equal at index {expectedIndex}. Expected value is {expectedValue}, but actual value is {actualValue}.",
47
                    parameters);
48
            }
49

50
            Assert.IsFalse(
51
                actualIterator.MoveNext(),
52
                $"{message}Expected sequence has {expectedIndex} value(s), but actual sequence has more than {expectedIndex} value(s).",
53
                parameters);
54
        }
55
    }
56
}

And a few other assert methods:

1
public static void IsEmpty<T>(IEnumerable<T> actual, string message = null, params object[] parameters)
2
{
3
    Assert.IsNotNull(actual, message, parameters);
4
    Assert.IsTrue(actual.IsEmpty(), message, parameters);
5
}
6

7
public static void IsNullOrEmpty<T>
8
    (IEnumerable<T> actual, string message = null, params object[] parameters) =>
9
        Assert.IsTrue(actual.IsNullOrEmpty(), message, parameters);
10

11
public static void Any<T>(IEnumerable<T> actual, string message = null, params object[] parameters)
12
{
13
    Assert.IsNotNull(actual, message, parameters);
14
    Assert.IsTrue(actual.Any(), message, parameters);
15
}
16

17
public static void Single<T>(IEnumerable<T> actual, string message = null, params object[] parameters)
18
{
19
    Assert.IsNotNull(actual, message, parameters);
20
    Assert.AreEqual(1, actual.Count(), message, parameters);
21
}
22

23
public static void Multiple<T>(IEnumerable<T> actual, string message = null, params object[] parameters)
24
{
25
    Assert.IsNotNull(actual, message, parameters);
26
    using (IEnumerator<T> iterator = actual.GetEnumerator())
27
    {
28
        Assert.IsTrue(iterator.MoveNext() && iterator.MoveNext(), message, parameters);
29
    }
30
}
31

32
public static void Contains<T>(
33
    T expected,
34
    IEnumerable<T> actual,
35
    IEqualityComparer<T> comparer = null,
36
    string message = null,
37
    params object[] parameters)
38
{
39
    Assert.IsNotNull(actual, message, parameters);
40
    Assert.IsTrue(actual.Contains(expected, comparer ?? EqualityComparer<T>.Default), message, parameters);
41
}
42

43
public static void DoesNotContain<T>(
44
    T expected,
45
    IEnumerable<T> actual,
46
    IEqualityComparer<T> comparer = null,
47
    string message = null,
48
    params object[] parameters)
49
{
50
    Assert.IsNotNull(actual, message, parameters);
51
    Assert.IsFalse(actual.Contains(expected, comparer ?? EqualityComparer<T>.Default), message, parameters);
52
}
53

54
public static void Count<T>(
55
    int expected, IEnumerable<T> actual, string message = null, params object[] parameters)
56
{
57
    Assert.IsNotNull(actual, message, parameters);
58
    Assert.AreEqual(expected, actual.Count(), message, parameters);
59
}