Add file enumeration extensibility points

[JeremyKuhne]

We need low-allocating high-performance extensibility points to build solutions for enumerating files.

(This is the API review for dotnet/designs#24)

Rationale and Usage

Enumerating files in .NET provides limited configurability. You can specify a simple DOS style pattern and whether or not to look recursively. More complicated filtering requires post filtering all results which can introduce a significant performance drain.

Recursive enumeration is also problematic in that there is no way to handle error states such as access issues or cycles created by links.

These restrictions have a significant impact on file system intensive applications, a key example being MSBuild. This document proposes a new set of primitive file and directory traversal APIs that are optimized for providing more flexibility while keeping the overhead to a minimum so that enumeration becomes both more powerful as well as more performant.

To write a wrapper that gets files with a given set of extensions you would need to write something similar to:

public static IEnumerable<string> GetFilePathsWithExtensions(string directory, bool recursive, params string[] extensions)
{
    return new DirectoryInfo(directory)
        .GetFiles("*", recursive ? SearchOption.AllDirectories : SearchOption.TopDirectoryOnly)
        .Where(f => extensions.Any(e => f.Name.EndsWith(e, StringComparison.OrdinalIgnoreCase)))
        .Select(r => r.FullName);
}

Not complicated to write, but this can do an enormous amount of extra allocations. You have to create full strings and FileInfo's for every single item in the file system. We can cut this down significantly with the extension point:

public static IEnumerable<string> GetFileFullPathsWithExtension(string directory,
    bool recursive, params string[] extensions)
{
    return new FileSystemEnumerable<string>(
        directory,
        (ref FileSystemEntry entry) => entry.ToFullPath(),
        new EnumerationOptions() { RecurseSubdirectories = recursive })
        {
            ShouldIncludePredicate = (ref FileSystemEntry entry) =>
            {
                if (entry.IsDirectory) return false;
                foreach (string extension in extensions)
                {
                    if (Path.GetExtension(entry.FileName).EndsWith(extension, StringComparison.OrdinalIgnoreCase))
                        return true;
                }
                return false;
            }
        };
}

The number of allocation reductions with the above solution is significant.

• No FileInfo allocations
• No fullpath string allocations for paths that don't match
• No filename allocations for paths that don't match (as the filename will still be in the native buffer at this point)

Note that while you can write a solution that doesn't allocate a FileInfo by using the string[] APIs and GetFullPath() it would still allocate unneeded strings and introduce costly normalization overhead.

Proposed API

namespace System.IO
{
    public static partial class Directory
    {
        public static IEnumerable<string> EnumerateDirectories(string path, string searchPattern, EnumerationOptions enumerationOptions);
        public static IEnumerable<string> EnumerateFiles(string path, string searchPattern, EnumerationOptions enumerationOptions);
        public static IEnumerable<string> EnumerateFileSystemEntries(string path, string searchPattern, EnumerationOptions enumerationOptions);
        public static string[] GetDirectories(string path, string searchPattern, EnumerationOptions enumerationOptions);
        public static string[] GetFiles(string path, string searchPattern, EnumerationOptions enumerationOptions);
        public static string[] GetFileSystemEntries(string path, string searchPattern, EnumerationOptions enumerationOptions);
    }

    public sealed partial class DirectoryInfo
    {
        public IEnumerable<DirectoryInfo> EnumerateDirectories(string searchPattern, EnumerationOptions enumerationOptions);
        public IEnumerable<FileSystemInfo> EnumerateFileSystemInfos(string searchPattern, EnumerationOptions enumerationOptions);
        public IEnumerable<FileInfo> EnumerateFiles(string searchPattern, EnumerationOptions enumerationOptions);
        public DirectoryInfo[] GetDirectories(string searchPattern, EnumerationOptions enumerationOptions);
        public FileInfo[] GetFiles(string searchPattern, EnumerationOptions enumerationOptions);
        public FileSystemInfo[] GetFileSystemInfos(string searchPattern, EnumerationOptions enumerationOptions);
    }

    public enum MatchType
    {
        /// <summary>
        /// Match using '*' and '?' wildcards.
        /// </summary>
        Simple,

        /// <summary>
        /// Match using DOS style matching semantics. '*', '?', '&lt;', '&gt;', and '"'
        /// are all considered wildcards.
        /// </summary>
        Dos
    }

    public enum MatchCasing
    {
        /// <summary>
        /// Match the default casing for the given platform
        /// </summary>
        PlatformDefault,

        /// <summary>
        /// Match respecting character casing
        /// </summary>
        CaseSensitive,

        /// <summary>
        /// Match ignoring character casing
        /// </summary>
        CaseInsensitive
    }

    public class EnumerationOptions
    {
        /// <summary>
        /// Should we recurse into subdirectories while enumerating?
        /// Default is false.
        /// </summary>
        public bool RecurseSubdirectories { get; set; }

        /// <summary>
        /// Skip files/directories when access is denied (e.g. AccessDeniedException/SecurityException).
        /// Default is true.
        /// </summary>
        public bool IgnoreInaccessible { get; set; }

        /// <summary>
        /// Suggested buffer size, in bytes. Default is 0 (no suggestion).
        /// </summary>
        /// <remarks>
        /// Not all platforms use user allocated buffers, and some require either fixed buffers or a
        /// buffer that has enough space to return a full result. One scenario where this option is
        /// useful is with remote share enumeration on Windows. Having a large buffer may result in
        /// better performance as more results can be batched over the wire (e.g. over a network
        /// share). A "large" buffer, for example, would be 16K. Typical is 4K.
        /// 
        /// We will not use the suggested buffer size if it has no meaning for the native APIs on the
        /// current platform or if it would be too small for getting at least a single result.
        /// </remarks>
        public int BufferSize { get; set; }

        /// <summary>
        /// Skip entries with the given attributes. Default is FileAttributes.Hidden | FileAttributes.System.
        /// </summary>
        public FileAttributes AttributesToSkip { get; set; }

        /// <summary>
        /// For APIs that allow specifying a match expression this will allow you to specify how
        /// to interpret the match expression.
        /// </summary>
        /// <remarks>
        /// The default is simple matching where '*' is always 0 or more characters and '?' is a single character.
        /// </remarks>
        public MatchType MatchType { get; set; }

        /// <summary>
        /// For APIs that allow specifying a match expression this will allow you to specify case matching behavior.
        /// </summary>
        /// <remarks>
        /// Default is to match platform defaults, which are gleaned from the case sensitivity of the temporary folder.
        /// </remarks>
        public MatchCasing MatchCasing { get; set; }

        /// <summary>
        /// Set to true to return "." and ".." directory entries. Default is false.
        /// </summary>
        public bool ReturnSpecialDirectories { get; set; }
    }
}

namespace System.IO.Enumeration
{
    public ref struct FileSystemEntry
    {
        /// <summary>
        /// The full path of the directory this entry resides in.
        /// </summary>
        public ReadOnlySpan<char> Directory { get; }

        /// <summary>
        /// The full path of the root directory used for the enumeration.
        /// </summary>
        public ReadOnlySpan<char> RootDirectory { get; }

        /// <summary>
        /// The root directory for the enumeration as specified in the constructor.
        /// </summary>
        public ReadOnlySpan<char>  OriginalRootDirectory { get; }

        public ReadOnlySpan<char> FileName { get; }
        public FileAttributes Attributes { get; }
        public long Length { get; }
        public DateTimeOffset CreationTimeUtc { get; }
        public DateTimeOffset LastAccessTimeUtc { get; }
        public DateTimeOffset LastWriteTimeUtc { get; }
        public bool IsDirectory { get; }
        public FileSystemInfo ToFileSystemInfo();

        /// <summary>
        /// Returns the full path for find results, based on the initially provided path.
        /// </summary>
        public string ToSpecifiedFullPath();

        /// <summary>
        /// Returns the full path of the find result.
        /// </summary>
        public string ToFullPath();
    }
    public abstract class FileSystemEnumerator<TResult> : CriticalFinalizerObject, IEnumerator<TResult>
    {
        public FileSystemEnumerator(string directory, EnumerationOptions options = null);

        /// <summary>
        /// Return true if the given file system entry should be included in the results.
        /// </summary>
        protected virtual bool ShouldIncludeEntry(ref FileSystemEntry entry);

        /// <summary>
        /// Return true if the directory entry given should be recursed into.
        /// </summary>
        protected virtual bool ShouldRecurseIntoEntry(ref FileSystemEntry entry);

        /// <summary>
        /// Generate the result type from the current entry;
        /// </summary>
        protected abstract TResult TransformEntry(ref FileSystemEntry entry);

        /// <summary>
        /// Called whenever the end of a directory is reached.
        /// </summary>
        /// <param name="directory">The path of the directory that finished.</param>
        protected virtual void OnDirectoryFinished(ReadOnlySpan<char> directory);

        /// <summary>
        /// Called when a native API returns an error. Return true to continue, or false
        /// to throw the default exception for the given error.
        /// </summary>
        /// <param name="error">The native error code.</param>
        protected virtual bool ContinueOnError(int error);

        public TResult Current { get; }
        object IEnumerator.Current { get; }
        public bool MoveNext();
        public void Reset();
        public void Dispose();
        protected virtual void Dispose(bool disposing);
    }

    /// <summary>
    /// Enumerable that allows utilizing custom filter predicates and tranform delegates.
    /// </summary>
    public class FileSystemEnumerable<TResult> : IEnumerable<TResult>
    {
        public FileSystemEnumerable(string directory, FindTransform transform, EnumerationOptions options = null) { }
        public FindPredicate ShouldRecursePredicate { get; set; }
        public FindPredicate ShouldIncludePredicate { get; set; }
        public IEnumerator<TResult> GetEnumerator();
        IEnumerator GetEnumerator();

        /// <summary>
        /// Delegate for filtering out find results.
        /// </summary>
        public delegate bool FindPredicate(ref FileSystemEntry entry);

        /// <summary>
        /// Delegate for transforming raw find data into a result.
        /// </summary>
        public delegate TResult FindTransform(ref FileSystemEntry entry);
    }
    public static class FileSystemName
    {
        /// <summary>
        /// Change unescaped '*' and '?' to '&lt;', '&gt;' and '"' to match Win32 behavior. For compatibility, Windows
        /// changes some wildcards to provide a closer match to historical DOS 8.3 filename matching.
        /// </summary>
        public static string TranslateDosExpression(string expression);

        /// <summary>
        /// This matcher uses the Windows wildcards (which includes `*`, `?`, `>`, `<`, and `"`).
        /// </summary>
        public static bool MatchesDosExpression(ReadOnlySpan<char> expression, ReadOnlySpan<char> name, bool ignoreCase = true);

        /// <summary>
        /// This matcher will only process `*` and `?`.
        /// </summary>       
        public static bool MatchesSimpleExpression(ReadOnlySpan<char> expression, ReadOnlySpan<char> name, bool ignoreCase = true);
    }
}

Implementation Notes

Changes to existing behavior

• Match expressions will no longer consider 8.3 filenames
  • This obscure behavior is costly and gives unexpected results
  • 8.3 filename generation is not always on, can be disabled
  • *.htm will no longer match *.html if 8.3 filenames exist
• Option defaults (when calling new APIs)
  • System & hidden files/directories are skipped by default
  • Access denied folders are skipped by default (no errors are thrown)
  • Simple matching is used by default (*.* means any file with a period, foo.* matches foo.txt, not foo)

FileSystemEnumerable

• directory, and transform will throw ArgumentNullException if null.
• If predicates are not specified, all entries will be accepted

FileSystemEnumerator

• directory, and transform will throw ArgumentNullException if null.
• all directory entries will be returned before processing additional directories (e.g. subdirectories)
• order of directory entries is not guaranteed
• timing of opening subdirectories is not guaranteed

FileSystemEntry

• translation of data that has non-trivial cost will be lazily done (applies specifically to Unix)
  • properties that require an additional OS call
  • UTF-8 to UTF-16 conversion
  • initial property values can potentially be unexpected based on timing of accessing data (i.e. the underlying file could disappear)
• property values will not change after being accessed
• FileSystemEntry should not be cached
  • FileName will only contain valid data for the duration of filter/transform calls, hence the struct being passed by ref

Matchers

• Matchers will support escaping of supported wildcards and \ using the \ character
  • \*, \\, ? (and \>, \<, \" for MatchesDosExpression)
• Empty expresion will match all

[JeremyKuhne]

@terrajobst, @danmosemsft, @pjanotti

[danmoseley]

I would rename Matcher to more specific eg SimpleMatcher since nobody would know whether it is using regexes or simple */?

[danmoseley]

Should FindData.Directory usefully be ROS<char> ? I imagine there could be a lot of differen t ones.

[JeremyKuhne]

I would rename Matcher to more specific eg SimpleMatcher since nobody would know whether it is using regexes or simple */?

I agree, updating.

Should FindData.Directory usefully be ROS ? I imagine there could be a lot of differen t ones.

It would be possible to do so. I was conflicted on this one as I wasn't sure whether or not we'd want to output it frequent, as it would reallocate an existing string as we currently have to create it. Further/future optimizations could potentially be done where that could be avoided on some platforms. Pretty complicated to optimize the full path to the directory we're looking at away as we can't keep a single character array for the directory, so I'm pretty unsure of if this is practically possible.

[jkotas]

This API feels very complicated. Should it be part of the platform, or should it rather live in separate NuGet package that the few folks who really need it will reference?

[JeremyKuhne]

This API feels very complicated.

It is, but out of necessity. I couldn't find a better solution that kept performance high and allocations low. Note that I'm measuring impact against hitting the same folders more than once (which is super common, particularly in the MSBuild scenario). Once caches below us are hot (OS, hardware) we consume a much more significant portion of the time spent.

Should it be part of the platform, or should it rather live in separate NuGet package that the few folks who really need it will reference?

We use it internally already. I'm not sure if there is value in doing the gymnastics to isolate by package. If people are particularly concerned about visibility in the "normal" namespace we could put things in something like System.IO.Extensibility. I'd prefer to keep things attached to the standard classes, but I'm open to arguments here.

[jkotas]

I am concerned about things like being able to evolve this independently on the platform, or requiring all current and future platforms to implement it.

We use it internally already.

We have number of other cases where we use one limited flavor of the functionality internally, and we expose the same thing in independent package. And we are reversing course on a few more for the reasons above.

[JeremyKuhne]

I am concerned about things like being able to evolve this independently on the platform, or requiring all current and future platform to implement it.

While I like the idea of OOB'ing this from a quick distribution standpoint (VS really wants this), there are some things that I'd want to ensure:

• It would require new, rather wordy, public constructors on the *Info classes to keep the allocations low for those transforms (presuming that we don't want to use InternalsVisibleTo or reflection)
• I want one implementation in CoreFX, presumably we can do that by just including common sources and not adding to ref for S.IO.FS
• I'd want to make sure we're doing the option adds in such a way that we're able to light up new useful functionality on the core APIs (Build failures in 'prodcon/corefx/master/' - '20180411.05' #25875)

[danmoseley]

It would require new, rather wordy, public constructors

Presumably it would need a .NET Framework target that used the existing constructors, or quick distribution is not solved.

[JeremyKuhne]

Presumably it would need a .NET Framework target that used the existing constructors, or quick distribution is not solved.

We'd need to do some contortions and lose some perf if the APIs aren't there. I don't think any of the scenarios that are currently in play for the build teams actually use the *Info classes, so there is still benefit to getting this fast-pathed with this caveat.

[iSazonov]

Currently .Net Core implement DOS-like globbing for Windows and fnmatch-like globing on Unix.
.Net Core assume that applications should have the same behavior on all platform. So .Net Core should implement 3th model for globbing - unified/modern globbing which has the same behavior on all platforms. Perhaps it should be POSIX 1003.2, 3.13.

PowerShell implementation
https://msdn.microsoft.com/en-us/library/aa717088%28v=vs.85%29.aspx?f=255&MSPPError=-2147217396#Anchor_1
https://github.com/PowerShell/PowerShell/blob/master/src/System.Management.Automation/namespaces/LocationGlobber.cs
It support wildcards ('*', '?', '[', ']') in file and directory names.
Currently it haven't case matching, it is not optimal and we expect to get high performance solution from .Net Core.

Case matching is needed for IntelliSense scenarios.
The scenarios also require sorted file enumeration. Currently PowerShell collect paths, sort and enumarate for IntelliSense - it can result in huge extra allocations. Perhaps .Net Core can do this more optimal.

For performance .Net Core could use low level API for enumeration:

• On Windows FindFirstFileEx (not clear about hard/soft link cycle detection)
• On Linux/Unix
  • modern FTS (it seems present on Linux only)
  • glob(3)

FTS support hard/soft link cycle detection (and case matching). In PowerShell we have to implement this by inode cache and checks.

[JeremyKuhne]

@iSazonov, #21362 is the general discussion around adding new globbing support.

With this issues changes we now use a unified matching algorithm for all platforms. Existing APIs use the DOS-like behavior and the new APIs (that take FindOptions directly) default to a simple match that honors * and ? with no DOS-like strangeness.

I absolutely want to add more matching options. If anyone is game to implement the Posix one (or others) I'll do what I can to help shepherd them along.

This is the current, checked-in shape of the current API based on reviews (this is the source code from the reference assembly). All existing APIs that took SearchOption now have an overload that takes EnumerationOptions:

namespace System.IO.Enumeration
{
    public enum MatchType
    {
        Simple,
        Dos
    }
    public enum MatchCasing
    {
        PlatformDefault,
        CaseSensitive,
        CaseInsensitive
    }
    public class EnumerationOptions
    {
        public EnumerationOptions() { }
        public bool RecurseSubdirectories { get { throw null; } set { } }
        public bool IgnoreInaccessible { get { throw null; } set { } }
        public int BufferSize { get { throw null; } set { } }
        public FileAttributes AttributesToSkip { get { throw null; } set { } }
        public MatchType MatchType { get { throw null; } set { } }
        public MatchCasing MatchCasing { get { throw null; } set { } }
        public bool ReturnSpecialDirectories { get { throw null; } set { } }
    }
    public ref struct FileSystemEntry
    {
        public ReadOnlySpan<char> Directory { get { throw null; } }
        public string RootDirectory { get { throw null; } }
        public string OriginalRootDirectory { get { throw null; } }
        public ReadOnlySpan<char> FileName { get { throw null; } }
        public FileAttributes Attributes { get { throw null; } }
        public long Length { get { throw null; } }
        public DateTimeOffset CreationTimeUtc { get { throw null; } }
        public DateTimeOffset LastAccessTimeUtc { get { throw null; } }
        public DateTimeOffset LastWriteTimeUtc { get { throw null; } }
        public bool IsDirectory { get { throw null; } }
        public FileSystemInfo ToFileSystemInfo() { throw null; }
        public string ToSpecifiedFullPath() { throw null; }
        public string ToFullPath() { throw null; }
    }
    public abstract class FileSystemEnumerator<TResult> : Runtime.ConstrainedExecution.CriticalFinalizerObject, Collections.Generic.IEnumerator<TResult>
    {
        public FileSystemEnumerator(string directory, EnumerationOptions options = null) { }
        protected virtual bool ShouldIncludeEntry(ref FileSystemEntry entry) { throw null; }
        protected virtual bool ShouldRecurseIntoEntry(ref FileSystemEntry entry) { throw null; }
        protected abstract TResult TransformEntry(ref FileSystemEntry entry);
        protected virtual void OnDirectoryFinished(ReadOnlySpan<char> directory) { throw null; }
        protected virtual bool ContinueOnError(int error) { throw null; }
        public TResult Current { get { throw null; } }
        object System.Collections.IEnumerator.Current { get { throw null; } }
        public bool MoveNext() { throw null; }
        public void Reset() { throw null; }
        public void Dispose() { throw null; }
        protected virtual void Dispose(bool disposing) { throw null; }
    }
    public class FileSystemEnumerable<TResult> : Collections.Generic.IEnumerable<TResult>
    {
        public FileSystemEnumerable(string directory, FindTransform transform, EnumerationOptions options = null) { }
        public FindPredicate ShouldRecursePredicate { get { throw null; } set { } }
        public FindPredicate ShouldIncludePredicate { get { throw null; } set { } }
        public Collections.Generic.IEnumerator<TResult> GetEnumerator() { throw null; }
        Collections.IEnumerator Collections.IEnumerable.GetEnumerator() { throw null; }
        public delegate bool FindPredicate(ref FileSystemEntry entry);
        public delegate TResult FindTransform(ref FileSystemEntry entry);
    }
    public static class FileSystemName
    {
        public static string TranslateDosExpression(string expression) { throw null; }
        public static bool MatchesDosExpression(ReadOnlySpan<char> expression, ReadOnlySpan<char> name, bool ignoreCase = true) { throw null; }
        public static bool MatchesSimpleExpression(ReadOnlySpan<char> expression, ReadOnlySpan<char> name, bool ignoreCase = true) { throw null; }
    }
}

I'm currently iterating on the Unix implementation, fixing the last few corner cases and improving the allocation count.

[iSazonov]

I duplicate my post in #21362.

For PowerShell we are very interested in implementing simple wildcards like '[a-z]' for paths - c:\windows\[d-fs]*\*.exe (Named Posix char classes are not so interesting I suppose).

[terrajobst]

Video

Looks good. Comments:

• MatchType, MatchCasing, EnumerationOptions should live in System.IO. Please submit a proposal with the updated System.IO APIs
• EnumerationOptions.IgnoreInaccessible should be true by default
• EnumerationOptions.AttributesToSkip should include system and hidden files.

[JeremyKuhne]

Updated original comment per latest feedback.