High Performance UriTemplate resolution with low-allocation C#

Do you want a drop-in replacemant for the already excellent Tavis.UriTemplates with 50% better performance, and minimal allocation? Or a 3x improvement with zero allocation, for a tiny bit more work? Or a 5x improvement and zero allocation for specialist scenarios? OK - read on...

TL;DR I know Tavis. Just give me the bits to play with

You can install the Corvus.UriTemplates package from nuget.org. This is a preview build with net6.0 (LTS) and net7.0 RC assemblies.

The code is on github.

But read on for information about the lower-level, zero allocation APIs.

What is a URI Template?

A URI template is a standardized way of parameterising a URI.

Here's an example of a URI template

http://example.com/{customerId}/updateName/{?firstName,lastName}

You can see how this defines a URL parameterised by a customerId in the path, and the query parameters firstName and lastName.

You might substitute values in for those parameters:

customerId=1234, firstName="Henry", lastname="Higgins"

To produce the resolved URL:

http://example.com/1234/updateName/?firstName=Henry&lastName=Higgins

Or extract parameter values from a URL

http://example.com/5678/updateName/?firstName=June&lastName=Whitfield

to produce the result

customerId=5678, firstName="June", lastname="Whitfield"

Commonly, you also want to determine whether a URI template matches a URL.

For example:

Given the URL below (note the change of updateName to doSomethingElse):

http://example.com/5678/doSomethingElse/?firstName=June&lastName=Whitfield

it does match the URI template

http://example.com/{customerId}/doSomethingElse/{?firstName,lastName}

But it doesn't match

http://example.com/{customerId}/updateName/{?firstName,lastName}

Common uses for URI Templates include route matching for dispatching HTTP requests, and URI-building in HTTP responses.

You want them to be as efficient as possible to lower the "cost of doing business" overhead in HTTP request handling. That is what motivated the creation of this library.

Benchmarks

First, let's have a look at the benchmarks. There are two basic scenarios for URI Templates:

1. Resolving a template by subsituting parameter values and producing a URI (or another partially-resolved URI Template).
2. Extracting parameter values from a URI by matching it to a URI template.

Here are some benchmarks for template resolution.

And here are some benchmarks for parameter extraction

For people who are looking for a drop-in replacement for the Tavis API, you want to compare ResolveUriTavis with ResolveUriCorvusTavis and ExtractParametersTavis with ExtractParametersCorvusTavis.

As you can see, there are considerable performance and memory allocation benefits, just for switching, with no other code changes.

Supported platforms and long-term support commitments

We package assemblies for net6.0 or later.

While netcore3.1 is not technically out of support until December 2022 (and at time of writing it is October 2022), we have elected not to support that version.

We also include a specific version for net7.0 and later (currently a release candidate) which takes advantage of some C#11/net7.0 features.

We will continue to produce net6.0 builds until it goes out of support in December 2024.

Likewise, net7.0 builds will be produced until it goes out of support (likely May 2024).

We also commit to producing net8.0 builds as the next LTS dotnet framework.

This will likely take us to November 2026, which is the latest date we have on the Microsoft horizon.

Replacing Tavis.UriTemplates

We expect one of the most popular scenarios being a drop-in replacement for Tavis.UriTemplates.

We have 100% support for the existing Tavis API and test our Tavis-compliant API against the full Tavis Test suite.

In order to convert your project to use the Tavis API

• Replace the package reference.

  <PackageReference Include="Tavis.UriTemplates" Version="1.1.1" />
  

  with

  <PackageReference Include="Corvus.UriTemplates" Version="1.0.0-preview.2" />
  

• Replace any using statements

  using Tavis.UriTemplates;
  

  with

  using Corvus.UriTemplates.TavisApi;
  

  If you then rebuild your code you will benefit from the performance improvements across the whole API surface area.

Using the low-level API directly

Our Corvus.UriTemplates.TavisApi implementation is built over an underlying low-allocation API.

Unlike the UriTemplate type, which smooshes the various behaviours into a single class, the underlying API comes in two parts

1. Resolving a template by substituting parameter values and producing a URI (or another partially-resolved URI Template)

   This uses a type called a UriTemplateResolver<TParameterProvider, TParameterPayload>. The parameters values are supplied by that TParamaterProvider type. By allowing you to plug in a parameter provider, you can efficiently deliver parameter values to the template resolution engine, minimizing allcoations for your particular scenario. We supply a couple of different parameter providers out-of-the-box; one for generic dotnet type instances, and one for JSON values.

2. Extracting parameter values from a URI by matching it to a URI template.

   This uses a type called UriTemplateParserFactory to create an instance of an IUriTemplateParser from a URI template.

   Creating an IUriTemplateParser instance using the factory is a comparatively expensive operation, comparable with building the Regex in Tavis.UriTemplates - but the resulting IUriTemplateParser can be cached for a given URI Template pattern, and the parser itself is zero allocation.

Let's look at these two scenarios in turn.

Extracting parameter values from a URI by matching it to a URI template

First, you need to create an instance of a parser for a URI template. You do this by calling one of the UriTemplateParserFactory.CreateParser() overloads, passing it your URI template.

IUriTemplateParser UriTemplateParserFactory.CreateParser(string uriTemplate);

or

IUriTemplateParser UriTemplateParserFactory.CreateParser(ReadOnlySpan<char> uriTemplate);

As we mentioned, this is a comparatively expensive operation, so you would typically have some initialization code that is called once to build your parsers from your templates (either derived statically or from some configuration)

private const string UriTemplate = "http://example.com/Glimpse.axd?n=glimpse_ajax&parentRequestId={parentRequestId}{&hash,callback}";

private static readonly IUriTemplateParser CorvusTemplate = CreateParser();

private static IUriTemplateParser CreateParser()
{
    return
        UriTemplateParserFactory.CreateParser(UriTemplate)
}

You can then make use of that parser to extract parameter values from a URI.

The parser uses a callback model to deliver the parameters to you (to avoid allocations). If you are used to low allocation code, you will probably recognize the pattern.

You call EnumerateParmaeters(), passing the URI you wish to parse (as a ReadOnlySpan<char>), a callback, and the initial value of a state object, which will be passed to that callback.

The callback itself is called by the parser each time a matched parameter is discovered.

It is given ReadOnlySpan<char> instances for the name and value pairs, along with the current version of the state object. This state is passed by ref, so you can update its value to keep track of whatever processing you are doing with the parameters you have been passed.

Here's an example that just counts the parameters it has seen.

int state = 0;

CorvusTemplate.EnumerateParameters(Uri, HandleParameters, ref state);

static void HandleParameters(ReadOnlySpan<char> name, ReadOnlySpan<char> value, ref int state)
{
    state++;
}

If you want to dive a bit deeper into the source code, you will see that this itself is an extension method over an underlying mechanism in IUriTemplateParser that is a bit more complex still (with potential efficiencies for certain use cases). But that is a topic for another day!

OK - let's move on to template resolution.

Resolving a template by substituting parameter values and producing a URI

The other basic scenario is injecting parameter values into a URI template to produce a URI (or another URI template if we haven't replaced all the parameters in the template).

There a variety of different strategies for substituting parameters into a URI. These include rules for formatting compound types like arrays and maps, and handling prefixes.

The underlying type that does this work is called UriTemplateResolver<TParameterProvider,TParameterPayload>.

The TParameterProvider is an ITemplateParameterProvider<TParameterPayload> - an interface implemented by types which convert from a source of parameter values (the TParameterPayload), on behalf of the UriTemplateResolver.

We offer two of these providers "out of the box" - the JsonTemplateParameterProvider (which adapts to a JsonElement) and the DictionaryTemplateParameterProvider (which adapts to an IDictionary<string, object?> and is used by the underlying Tavis-compatible API).

To save you having to work directly with the UriTemplateResolver plugging in all the necessary generic parameters, most ITemplateParameterProvider implementations will offer a convenience type, and these are no exception.

JsonUriTemplateResolver and DictionaryUriTemplateResolver give you strongly typed TryResolveResult and TryGetParameterNames methods which you can use in your code.

Here's an example.

const string uriTemplate = "http://example.org/location{?value*}";

using var jsonValues = JsonDocument.Parse("{\"value\": { \"foo\": \"bar\", \"bar\": 3.4, \"baz\": null }}");
Dictionary<string, string> value = new() { { "foo", "bar" }, { "bar", "baz" }, { "baz", "bob" } };
Dictionary<string, object?> parameters = new() { { "value", value } };

object? nullState = default;

JsonUriTemplateResolver.TryResolveResult(uriTemplate.AsSpan(), false, jsonValues.RootElement, HandleResult, ref nullState);
DictionaryUriTemplateResolver.TryResolveResult(uriTemplate.AsSpan(), false, parameters, HandleResult, ref nullState);

static void HandleResult(ReadOnlySpan<char> resolvedTemplate, ref object? state)
{
    Console.WriteLine(resolvedTemplate.ToString());
}

Notice how this example uses the exact same callback that receives the resolved template, for both resolvers - the callback is not dependent on the particular parameter provider.

We'd love to hear your feedback on this API - and any benchmarks you produce (good or...less good) in your applications.

Let us know in the comments below, and/or in the github issues.