2
\$\begingroup\$

Sometimes I save a file somewhere but can't find it after or I install something and want to see what files were added. For this reason, I created a winforms app which only displayes files created/changed/accessed in a certain timespan. Since the windows timestamps aren't reliable when it comes to folders (see here), I have to use my own filter for files and folders. This filter is first used to determine if a folder should be displayed (explorer-like tree-view) and will short-circuit if any file which matches the filter is found in any subdirectory of the folder. It's later on also used for each file to see if it should be displayed or not (explorer-like list-view).

I have an enum for the search categories.

[Flags]
enum SearchCriteria
{
    None            = 0,
    CreationTime    = 1 << 0,
    LastModified    = 1 << 1,
    LastAccess      = 1 << 2
}

When a user decides to filter for creation time, it will stay like this every time the filter is applied for at least one folder. This means, I don't want to check the search criteria every time the filter runs because that would be wasted comparisons and this one is all about performance. I came up with a solution using a cache for folders and expression trees from which I compile a function which is as efficient as possible so the search critera are only checked once and the actual filter will be compiled dynamically. There is a similar case with _considerFolderStamps (see the comments) which should be improved but I don't know how without using expression trees for the whole filter (not just the time comparisons).
Here's the code for that:

private readonly Dictionary<string, bool> _matchesCache = new Dictionary<string, bool>();

private Predicate<FileSystemInfo> GetFilter(DateTime start, DateTime end, SearchCriteria searchCriteria)
{
    if (searchCriteria == SearchCriteria.None)
    {
        // just include everything
        return f => true;
    }
    else
    {
        Expression<Predicate<FileSystemInfo>> expression = null;

        // add filter for creation time
        if (searchCriteria.HasFlag(SearchCriteria.CreationTime))
        {
            Expression<Predicate<FileSystemInfo>> checkCreationTime = info => info.CreationTime.Between(start, end);
            expression = checkCreationTime; // no need to check, expression is null
        }

        // add filter for modified time (|| existing if necessary)
        if (searchCriteria.HasFlag(SearchCriteria.LastModified))
        {
            Expression<Predicate<FileSystemInfo>> checkLastModified = info => info.LastWriteTime.Between(start, end);
            expression = expression.OrIfNotNull(checkLastModified);
        }

        // add filter for access time (|| existing if necessary)
        if (searchCriteria.HasFlag(SearchCriteria.LastAccess))
        {
            Expression<Predicate<FileSystemInfo>> checkLastAccess = info => info.LastAccessTime.Between(start, end);
            expression = expression.OrIfNotNull(checkLastAccess);
        }

        // compile to delegate
        Predicate<FileSystemInfo> coreFilter = expression.Compile();

        // return predicate which additionally uses cache for folders in combination with the core-filter
        return f => ContainsAnyChange(f, coreFilter);
    }
}

private bool ContainsAnyChange(FileSystemInfo info, Predicate<FileSystemInfo> coreFilter)
{
    if (info is DirectoryInfo dir)
    {
        if (_matchesCache.TryGetValue(info.FullName, out bool matchesFromCache))
        {
            // log entry
            return matchesFromCache;
        }

        // The user can decide if the timestamps of the folder itself should also be considered. 
        // Just like with the search criteria, this won't change and checking for _considerFolderStamps should only be done once. 
        // However, since it's not in the core-filter I would need to expand the expression stuff and build the whole filter using expressions.
        if (_considerFolderStamps && coreFilter(info))
        {
            _matchesCache.Add(info.FullName, true);
            return true;
        }

        try
        {
            // recursive call for the folder content
            bool containsChange = dir.EnumerateFileSystemInfos()
                .Any(f => ContainsAnyChange(f, coreFilter));

            _matchesCache.Add(info.FullName, containsChange);
            return containsChange;
        }
        catch (UnauthorizedAccessException)
        {
            // log entry
            _matchesCache.Add(info.FullName, false);
            return false;
        }
        catch (DirectoryNotFoundException) // this happens for symbolic links like Desktop
        {
            // log entry
            _matchesCache.Add(info.FullName, false);
            return false;
        }
    }

    // it's just a file at this point
    return coreFilter(info);
}

You also need these extensions along with a parameter-expression-visitor.

internal class SubstParameterExpressionVisitor : ExpressionVisitor
{
    private readonly Dictionary<Expression, Expression> _subst = new Dictionary<Expression, Expression>();

    protected override Expression VisitParameter(ParameterExpression node)
    {
        if (_subst.TryGetValue(node, out Expression newValue))
        {
            return newValue;
        }

        return node;
    }

    public Expression this[Expression original]
    {
        get => _subst[original];
        set => _subst[original] = value;
    }
}

public static Expression<Predicate<T>> Or<T>(this Expression<Predicate<T>> a, Expression<Predicate<T>> b)
{
    if (a == null)
        throw new ArgumentNullException(nameof(a));

    if (b == null)
        throw new ArgumentNullException(nameof(b));

    ParameterExpression parameter = a.Parameters[0];

    SubstParameterExpressionVisitor visitor = new SubstParameterExpressionVisitor();
    visitor[b.Parameters[0]] = parameter;

    Expression combinedBody = Expression.OrElse(a.Body, visitor.Visit(b.Body));
    return Expression.Lambda<Predicate<T>>(combinedBody, parameter);
}

public static Expression<Predicate<T>> OrIfNotNull<T>(this Expression<Predicate<T>> a, Expression<Predicate<T>> b) => 
    a == null ? b : a.Or(b);

public static bool Between(this DateTime input, DateTime inclStart, DateTime exclEnd) => 
    input >= inclStart && input < exclEnd;

Since this filter is applied to hundreds of folders and files (it's applied recursively), it has to be really performant. I know that there are other factors which can slow down the program especially when working with a TreeView and ListView but this question is solely about this filter.

Some things maybe worth mentioning:

  • GetFilter is called once to get a predicate which can decide if a file/folder should be included in the view.
  • The cache is a dictionary for fast access where filtered folders are saved. Files are not included in the cache since adding the full path for every file in your system to a dictionary uses a lot of memory.
  • The code for the full project can be found here.
  • I might ask another question later on about the other part (winforms etc) since performance is very important there too. In this question I'd only like feedback about the shown code though.
  • If it's not clear already, this question is all about performance but, as always, any constructive critisism is very welcome :)
  • The current speed is acceptable but when you choose a very small timespan which matches very few files in a big system.. you have quite a big waiting and it would be nice to reduce this a bit further.

Also here are debug views of two examples core-filters (expression) built from the search criteria using expression tree manipulation. They are working correctly.

.Lambda #Lambda1<System.Predicate`1[System.IO.FileSystemInfo]>(System.IO.FileSystemInfo $info) {
    .Call LastUpdatedExplorer.DateTimeExtensions.Between(
        $info.LastWriteTime,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).start,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).end)
}

.Lambda #Lambda1<System.Predicate`1[System.IO.FileSystemInfo]>(System.IO.FileSystemInfo $info) {
    .Call LastUpdatedExplorer.DateTimeExtensions.Between(
        $info.CreationTime,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).start,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).end)
    || .Call LastUpdatedExplorer.DateTimeExtensions.Between(
        $info.LastWriteTime,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).start,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).end)
    || .Call LastUpdatedExplorer.DateTimeExtensions.Between(
        $info.LastAccessTime,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).start,
        (.Constant<LastUpdatedExplorer.HostView+<>c__DisplayClass9_1>(LastUpdatedExplorer.HostView+<>c__DisplayClass9_1).CS$<>8__locals1).end)
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.