Corvus.Globbing

A zero allocation globbing library.

Repository Structure

• Solutions - Contains source code files, benchmarks and specs.
• Documentation - Contains documentation, including polyglot notebooks containing code examples inside the Examples subfolder.

Getting Started

Corvus.Globbing is available on NuGet. To add a reference to the package in your project, run the following command

dotnet add package Corvus.Globbing

Use the --version option to specify a version to install.

dotnet add package Corvus.Globbing --version 0.1.0

Purpose

We built this to provide a zero-allocation globbing library with performance comparable to (or better than) https://github.com/dazinator/DotNet.Glob and raw Regular Expressions, when running under net6.0.

Use cases

The particular use case we have optimized for is a case-sensitive glob that will be matched against a large number of paths (100+), but will not necessarily be cachable.

We want a very high-performance parse of that glob, and then a performant application of the glob to a large number of candidate paths.

Our motivation for this came when "link stripping" documents to be returned from an HTTP request, to remove links that the requesting identity is not permitted to see (perhaps for security, feature enablement, or just local context).

We also want to minimize allocations on the hot-path of a request handler.

Performance targets

We offer better raw matching performance (~50-80%) against a pre-tokenized glob pattern, for the StringComparison.Ordinal (case sensitive) default, than Dotnet.Glob.

Our tokenization is also ~10x faster than Dotnet.Glob so it is significantly faster in the single use/throwaway case.

Usage

The simplest case just requires you to pass the glob and the candidate path to match. Note that it actually takes a ReadonlySpan<char> - to which strings are implicitly converted.

bool isMatch = Glob.Match("path/*atstand", "path/fooatstand"); 

We support all the standard string-comparison types. The default is StringComparison.Ordinal (i.e. case sensitive), but you could do a case insensitive match:

bool isMatch = Glob.Match("path/*atstand", "PATH/fooatstand", StringComparison.OrdinalIgnoreCase); 

If you want to hold on to the tokenized glob and match against a number of paths, you can stack allocate a tokenized glob array, and reuse it:

string pattern = "path/*atstand";

// There can't be more tokens than there are characters in the glob pattern, so we allocate an array at least that long.
Span<GlobToken> tokenizedGlob = stackalloc GlobToken[pattern.Length];
int tokenCount = Corvus.Globbing.GlobTokenizer.Tokenize(pattern, ref tokenizedGlob);
// And then slice off the number of tokens we actually used
ReadOnlySpan<GlobToken> glob = tokenizedGlob[..tokenCount];

bool firstMatch = Glob.Match(pattern, glob, "path/fooatstand"); // Returns: true
bool secondMatch = Glob.Match(pattern, glob, "badpath/fooatstand"); // Returns: false

For very long potential globs, you could fall back to the ArrayPool allocation technique:

    // Pick a token array length threshold
    int MaxGlobTokenArrayLength = 1024;

    string pattern = "path/*atstand";

    // There can't be more tokens than there are characters the glob.
    GlobToken[]? globTokenArray = null;
    Span<GlobToken> globTokens = pattern.Length > MaxGlobTokenArrayLength ? stackalloc GlobToken[0] : stackalloc GlobToken[pattern.Length];

    if (pattern.Length > MaxGlobTokenArrayLength)
    {
        globTokenArray = ArrayPool<GlobToken>.Shared.Rent(pattern.Length);
        globTokens = globTokenArray.AsSpan();
    }

    try
    {
        int tokenCount = GlobTokenizer.Tokenize(pattern, ref globTokens);
        ReadOnlySpan<GlobToken> tokenizedGlob = globTokens[..tokenCount];

        // Do your matching here...
        bool firstMatch = Glob.Match(pattern, tokenizedGlob, "path/fooatstand"); // Returns: true

        bool secondMatch = Glob.Match(pattern, tokenizedGlob, "badpath/fooatstand"); // Returns: false
    }
    finally
    {
        if (pattern.Length > MaxGlobTokenArrayLength)
        {
            ArrayPool<GlobToken>.Shared.Return(globTokenArray);
        }
    }
}

Supported patterns

(Derived from Wikipedia)

Escaping special characters using []

The special characters *, ?, \, /, [ can be escaped by using the [] 'match one character given in the bracket' list - e.g. [[] matches the literal [ and [*] matches the literal *.

Benchmarks

We have used Benchmark Dotnet to compare the performance with raw RegEx and DotNet.Glob. This represents a current example run.

(note that we have re-baselined on the Corvus implementation for ease of comparison)

Compile

Compile and match false

Compile and match true

Match false

Match true

Credits

This library would not exist without Dotnet Glob - I've built the specs from its unit tests, and modelled the actual matching algorithms on the implementation in that library (although it is somewhat different in structure). The project has a "give back" mechanism so I've donated a small amount. You could consider doing so too.