GetEntitiesRecursive method stack overflow possible?

[vector-man]

It looks like one of the methods, GetEntitiesRecursive, uses recursion, which could potentially cause a stack overflow. Maybe it should be turned into an iterative method?

[bobvanderlinden]

Yes, a stack overflow exception is possible at the moment. I'm not sure how deep the directory structure will get to hit that limitation though. It might not be a problem in practice, but it is possible to create a directory structure of infinite depth. That would certainly hit the limit. Making it iterative would not help in those cases.

Best solution would be to add a maximum depth parameter to GetEntitiesRecursive. I'm not quite sure whether the function should result in an exception (MaximumDepthReachedException?) or whether it should skip directories at that depth. Throwing MaximumDepthReachedException would be the most straightforward solution, but it will block usage of GetEntitiesRecursive for infinite filesystems.

[Corey-M]

This can be easily rewritten using a Stack<> object to store the list, with a check on the stack count to limit depth. Something like:

const int MaxSearchDepth = 1024;

public static IEnumerable<FileSystemPath> GetEntitiesRecursive(this IFileSystem fileSystem, FileSystemPath path)
{
    if (!path.IsDirectory())
        throw new ArgumentException("The specified path is not a directory.");
    Stack<FileSystemPath> stack = new Stack<FileSystemPath>();
    stack.Enqueue(path);

    while (stack.Any())
    {
        var curr = stack.Pop();
        foreach (var entity in fileSystem.GetEntities(curr))
        {
            yield return entity;
            if (entity.IsDirectory())
            {
                stack.Push(entity);
                if (stack.Count > MaxSearchDepth)
                    throw new Exception("Path search depth limit exceeded.");
            }
        }
    }

This ensures that there is no recursion and significantly reduces memory usage as there is only one instance of the enumerator class created no matter how deep you go.

The only issue is that it reverses the order of enumeration of folders at each level. This can be resolved by sorting the entity list from GetEntities as an array:

var entities = fileSystem.GetEntities(curr).OrderBy(e => e.EntityName).ToArray();
foreach (var entity in entities)
    yield return entity;
foreach (var entity in entities.Where(e => e.IsDirectory).OrderByDescending(e => e.EntityName))
{
    stack.Push(entity);
    if (stack.Count > MaxSearchDepth)
        throw new Exception("Path search depth limit exceeded.");
}