IEnumerable and Recursion using yield return

Question

I have an IEnumerable<T> method that I'm using to find controls in a WebForms page.

The method is recursive and I'm having some problems returning the type I want when the yield return is returnig the value of the recursive call.

My code looks as follows:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            yield return c.GetDeepControlsByType<T>();
        }
    }
}

This currently throws a "Cannot convert expression type" error. If however this method returns type IEnumerable<Object>, the code builds, but the wrong type is returned in the output.

Is there a way of using yield return whilst also using recursion?

Broder

#1815997 : link to "mrydengrens" answer on the thread "Enumerating Collections that are not inherently IEnumerable ?" His sample code is based on a blog article by Eric Lippert showing you how to use stacks in recursive enumeration with Linq, thus avoiding possibly expensive memory use by iterators. imho very useful ! – Colenecoleopteran

BTW. if(c.Controls.Count > 0) --> if(c.Controls.Any()), especially if you are yielding as well:) – Kelso

I don't think this case benefits from yielding. For completeness I provided an implementation without yield. Please see below :) And it's a one-liner too :) – Kelso

You should be careful to avoid yield return in recursive functions, the memory usage scales explosively. See https://mcmap.net/q/93132/-ienumerable-and-recursion-using-yield-return – Rathenau

Answer 1

Inside a method that returns IEnumerable<T>, yield return has to return T, not an IEnumerable<T>.

Replace

yield return c.GetDeepControlsByType<T>();

with:

foreach (var x in c.GetDeepControlsByType<T>())
{
  yield return x;
}

Prevision

Answer 2

You need to yield each of the items yielded by the recursive call:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            foreach (Control control in c.GetDeepControlsByType<T>())
            {
                yield return control;
            }
        }
    }
}

Note that there's a cost to recursing in this way - you'll end up creating a lot of iterators, which can create a performance issue if you have a really deep control tree. If you want to avoid that, you basically need to do the recursion yourself within the method, to make sure there's only one iterator (state machine) created. See this question for more details and a sample implementation - but this obviously adds a certain amount of complexity too.

Lor

I find it surprising that in a thread about yielding Jon hasn't mentioned c.Controls.Count > 0 vs. .Any() :) – Kelso

@Tymek actually it's mentioned in the linked answer. – Fruitarian

Answer 3

As Jon Skeet and Colonel Panic note in their answers, using yield return in recursive methods may cause performance problems if the tree is very deep.

Here's a generic non-recursive extension method that performs a depth-first traversal of a sequence of trees:

public static IEnumerable<TSource> RecursiveSelect<TSource>(
    this IEnumerable<TSource> source, Func<TSource, IEnumerable<TSource>> childSelector)
{
    var stack = new Stack<IEnumerator<TSource>>();
    var enumerator = source.GetEnumerator();

    try
    {
        while (true)
        {
            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                yield return element;

                stack.Push(enumerator);
                enumerator = childSelector(element).GetEnumerator();
            }
            else if (stack.Count > 0)
            {
                enumerator.Dispose();
                enumerator = stack.Pop();
            }
            else
            {
                yield break;
            }
        }
    }
    finally
    {
        enumerator.Dispose();

        while (stack.Count > 0) // Clean up in case of an exception.
        {
            enumerator = stack.Pop();
            enumerator.Dispose();
        }
    }
}

Unlike Eric Lippert's solution, RecursiveSelect works directly with enumerators so that it doesn't need to call Reverse (which buffers the entire sequence in memory).

Using RecursiveSelect, the OP's original method can be rewritten simply like this:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}

Upbear

To get this (excellent) code to work, I had to use 'OfType to get the ControlCollection into IEnumerable form; in Windows Forms, a ControlCollection is not enumerable: return control.Controls.OfType<Control>().RecursiveSelect<Control>(c => c.Controls.OfType<Control>()) .Where(c => c is T); – Colenecoleopteran

Answer 4

Others provided you with the correct answer, but I don't think your case benefits from yielding.

Here's a snippet which achieves the same without yielding.

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
   return control.Controls
                 .Where(c => c is T)
                 .Concat(control.Controls
                                .SelectMany(c =>c.GetDeepControlsByType<T>()));
}

Kelso

Doesn't use LINQ yieldas well? ;) – Ellison

This is slick. I've always been bothered by the additional foreach loop. Now I can do this with pure functional programming! – Corposant

I like this solution in terms of readability, but it faces the same performance issue with iterators as using yield. @PhilippM: Verified that LINQ uses yield referencesource.microsoft.com/System.Core/R/… – Sankaran

Thumb up for a great solution. – Attune

Answer 5

You need to return the items from the enumerator, not the enumerator itself, in your second yield return

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach (Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if (c.Controls.Count > 0)
        {
            foreach (Control ctrl in c.GetDeepControlsByType<T>())
            {
                yield return ctrl;
            }
        }
    }
}

Visual

Answer 6

Seredynski's syntax is correct, but you should be careful to avoid yield return in recursive functions because it's a disaster for memory usage. See https://mcmap.net/q/94307/-when-not-to-use-yield-return-duplicate it scales explosively with depth (a similar function was using 10% of memory in my app).

A simple solution is to use one list and pass it with the recursion https://codereview.stackexchange.com/a/5651/754

/// <summary>
/// Append the descendents of tree to the given list.
/// </summary>
private void AppendDescendents(Tree tree, List<Tree> descendents)
{
    foreach (var child in tree.Children)
    {
        descendents.Add(child);
        AppendDescendents(child, descendents);
    }
}

Alternatively you could use a stack and a while loop to eliminate recursive calls https://codereview.stackexchange.com/a/5661/754

Rathenau

Answer 7

I think you have to yield return each of the controls in the enumerables.

    public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
    {
        foreach (Control c in control.Controls)
        {
            if (c is T)
            {
                yield return c;
            }

            if (c.Controls.Count > 0)
            {
                foreach (Control childControl in c.GetDeepControlsByType<T>())
                {
                    yield return childControl;
                }
            }
        }
    }

Schnabel

Answer 8

While there are many good answers out there, I would still add that it is possible to use LINQ methods to accomplish the same thing, .

For instance, the original code of the OP could be rewritten as:

public static IEnumerable<Control> 
                           GetDeepControlsByType<T>(this Control control)
{
   return control.Controls.OfType<T>()
          .Union(control.Controls.SelectMany(c => c.GetDeepControlsByType<T>()));        
}

Pomelo

A solution using that same approach was posted three years ago. – Quattlebaum

@Quattlebaum Although it is similar (which BTW I missed between all the answers... while writing this answer), it is still different, as it uses .OfType<> to filter, and .Union() – Pomelo

The OfType is not really a meainingful different. At most a minor styalistic change. A control cannot be a child of multiple controls, so the traversed tree is already unqiue. Using Union instead of Concat is needlessly verifying the uniqueness of a sequence already guaranteed to be unique, and is therefore an objective downgrade. – Quattlebaum