Does LINQ try to solve things in one pass?

Question

Say we have list.Where(p=>p.Number > n).Select(p=> p.Name).Where(n=> n.StartsWith(a)).ToList(); will this be ran one pass algorithm or it will be 3 passes?

Answer 1

list would only be iterated once in that code, not 3 times.

Of course, if you want to test if any arbitrary query iterates the source multiple times it's easy enough to test experimentally, just create an IEnumerable that throws an exception when you attempt to iterate it multiple times:

public static IEnumerable<T> ThereCanBeOnlyOne<T>(this IEnumerable<T> source)
{
    return new SingleEnumerable<T>(source);
}

private class SingleEnumerable<T> : IEnumerable<T>
{
    private bool hasRun = false;
    private IEnumerable<T> wrapped;
    public SingleEnumerable(IEnumerable<T> wrapped)
    {
        this.wrapped = wrapped;
    }
    public IEnumerator<T> GetEnumerator()
    {
        if (hasRun)
            throw new InvalidOperationException(
                "Sequence cannot be enumerated multilpe times");
        else
        {
            hasRun = true;
            return wrapped.GetEnumerator();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Now you can just write:

list.ThereCanBeOnlyOne()
    .Where(p=>p.Number > n)
    .Select(p=> p.Name)
    .Where(n=> n.StartsWith(a))
    .ToList();

If the code throws an exception, you tried to iterate the underlying list multiple times. If not, you didn't.

Answer 2

It will build up the list in one pass, due to the way that LINQ streams the data.

For example, take this:

var query = list.Where(p => p.Number > n);

That in itself doesn't look at any of the elements of the list. Instead, it remembers the list you're looking at, and when you start iterating over query, each time you ask for the next element, it will check the elements of the list in turn until it finds a match - then stop. For example:

using (var iterator = query.GetEnumerator())
{
    iterator.MoveNext(); // This will look for the first match
    Console.WriteLine(iterator.Current);

    iterator.MoveNext(); // This will continue from just after the first match
}

Each of the operations works that way - so by the time you've got:

var query = list.Where(...)
                .Select(...)
                .Where(...);

... when you ask for the first item within query, it will chain back up (so the last Where will ask the result of Select, which will ask the result of the first Where, which will ask the list) and keep going until it's got a result. Then when you ask for the next item, that will ask the result of Select for the next item, etc.

ToList builds up a List<T> from all the items in its source, immediately - it's eager in that sense (rather than the other operators here which are lazy). But the original list itself will still only be iterated over once.

For a lot more detail on how LINQ to Objects works - including a sample implementation - you might want to read my Edulinq blog series.