Skip to content

Instantly share code, notes, and snippets.

@rynowak
Created January 23, 2017 06:10
Show Gist options
  • Save rynowak/a41dc558230e610d71584e8673a8849c to your computer and use it in GitHub Desktop.
Save rynowak/a41dc558230e610d71584e8673a8849c to your computer and use it in GitHub Desktop.
The fever dreams of a madman
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using Microsoft.AspNetCore.Routing;
using Microsoft.AspNetCore.Routing.Internal;
using Microsoft.AspNetCore.Routing.Template;
using Microsoft.AspNetCore.Routing.Tree;
using Microsoft.Extensions.Logging;
namespace PackedRouting
{
public class PackedRouter : IRouter
{
private static readonly Task CompletedTask = Task.FromResult<object>(null);
private readonly ILogger _logger;
private readonly ILogger _constraintLogger;
private Entry[] _entries;
public PackedRouter(TreeRouteBuilder builder, ILoggerFactory loggerFactory)
{
_logger = loggerFactory.CreateLogger("Foo");
_constraintLogger = loggerFactory.CreateLogger("Bar");
var trees = new List<TreeNode>();
foreach (var route in builder.InboundEntries.OrderByDescending(e => e.Precedence))
{
var parent = trees;
for (var i = 0; i < route.RouteTemplate.Segments.Count; i++)
{
var segment = route.RouteTemplate.Segments[i];
if (segment.IsSimple && segment.Parts[0].IsLiteral)
{
var value = segment.Parts[0].Text;
TreeNode next = null;
for (var j = 0; j < parent.Count; j++)
{
var node = parent[j];
if (node.Kind == EntryKind.Literal && string.Equals(value, node.Value, StringComparison.OrdinalIgnoreCase))
{
next = node;
break;
}
}
if (next == null)
{
next = new TreeNode()
{
Kind = EntryKind.Literal,
Value = value,
};
parent.Add(next);
}
if (i == route.RouteTemplate.Segments.Count - 1)
{
next.Matches.Add(new MatchEntry()
{
Constraints = route.Constraints,
Handler = (IRouteHandler)route.Handler,
Matcher = new TemplateMatcher(route.RouteTemplate, route.Defaults),
});
}
parent = next.Children;
}
if (segment.IsSimple && segment.Parts[0].IsParameter && !segment.Parts[0].IsCatchAll)
{
TreeNode next = null;
for (var j = 0; j < parent.Count; i++)
{
var node = parent[j];
if (node.Kind == EntryKind.Parameter)
{
next = node;
break;
}
}
if (next == null)
{
next = new TreeNode()
{
Kind = EntryKind.Parameter,
};
parent.Add(next);
}
if (i == route.RouteTemplate.Segments.Count - 1)
{
next.Matches.Add(new MatchEntry()
{
Constraints = route.Constraints,
Handler = (IRouteHandler)route.Handler,
Matcher = new TemplateMatcher(route.RouteTemplate, route.Defaults),
});
}
parent = next.Children;
}
}
}
var entries = new List<Entry>();
var roots = new List<int>();
var index = 0;
var queue = new Queue<TreeNode>();
for (; index < trees.Count; index++)
{
var node = trees[index];
node.Index = index;
entries.Add(new Entry()
{
Kind = node.Kind,
Matches = node.Matches.ToArray(),
Value = node.Value,
FirstChild = -1,
NextSibling = index == trees.Count - 1 ? -1 : index + 1,
});
queue.Enqueue(node);
}
while (queue.Count > 0)
{
var parent = queue.Dequeue();
for (var j = 0; j < parent.Children.Count; index++, j++)
{
if (j == 0)
{
var temp = entries[parent.Index];
temp.FirstChild = index;
entries[parent.Index] = temp;
}
var node = parent.Children[j];
node.Index = index;
entries.Add(new Entry()
{
Kind = node.Kind,
Matches = node.Matches.ToArray(),
Value = node.Value,
FirstChild = -1,
NextSibling = j == parent.Children.Count - 1 ? -1 : index + 1,
});
queue.Enqueue(node);
}
}
_entries = entries.ToArray();
}
public VirtualPathData GetVirtualPath(VirtualPathContext context)
{
throw new NotImplementedException();
}
public Task RouteAsync(RouteContext context)
{
var next = _entries.Length == 0 ? -1 : 0;
while (next != -1)
{
var tokenizer = new PathTokenizer(context.HttpContext.Request.Path);
var root = _entries[next];
if (Match(context, ref root, tokenizer.GetEnumerator()))
{
return CompletedTask;
}
next = root.NextSibling;
}
return CompletedTask;
}
private bool Match(RouteContext context, ref Entry entry, PathTokenizer.Enumerator path)
{
switch (entry.Kind)
{
case EntryKind.Literal:
if (!path.MoveNext())
{
return false;
}
if (path.Current.Equals(entry.Value, StringComparison.OrdinalIgnoreCase))
{
// This is a terminal node and we're at the end of the string.
if (entry.Matches != null && path.Current.Offset + path.Current.Length == path.Current.Buffer.Length)
{
for (var i = 0; i < entry.Matches.Length; i++)
{
var match = entry.Matches[i];
if (TryMatch(context, ref match))
{
return true;
}
}
return false;
}
if (entry.FirstChild != -1)
{
var next = entry.FirstChild;
Entry child;
do
{
child = _entries[next];
if (Match(context, ref child, path))
{
return true;
}
}
while ((next = child.NextSibling) != -1);
return false;
}
}
return false;
case EntryKind.Parameter:
if (!path.MoveNext())
{
return false;
}
// This is a terminal node and we're at the end of the string.
if (entry.Matches != null && path.Current.Offset + path.Current.Length == path.Current.Buffer.Length)
{
for (var i = 0; i < entry.Matches.Length; i++)
{
var match = entry.Matches[i];
if (TryMatch(context, ref match))
{
return true;
}
}
return false;
}
if (entry.FirstChild != -1)
{
var next = entry.FirstChild;
Entry child;
do
{
child = _entries[next];
if (Match(context, ref child, path))
{
return true;
}
}
while ((next = child.NextSibling) != -1);
return false;
}
return false;
case EntryKind.Catchall:
return false;
default:
return false;
}
}
private bool TryMatch(RouteContext context, ref MatchEntry entry)
{
// Create a snapshot before processing the route. We'll restore this snapshot before running each
// to restore the state. This is likely an "empty" snapshot, which doesn't allocate.
var snapshot = context.RouteData.PushState(router: null, values: null, dataTokens: null);
try
{
if (!entry.Matcher.TryMatch(context.HttpContext.Request.Path, context.RouteData.Values))
{
return false;
}
if (!RouteConstraintMatcher.Match(
entry.Constraints,
context.RouteData.Values,
context.HttpContext,
this,
RouteDirection.IncomingRequest,
_constraintLogger))
{
return false;
}
context.Handler = entry.Handler.GetRequestHandler(context.HttpContext, context.RouteData);
return context.Handler != null;
}
finally
{
if (context.Handler == null)
{
// Restore the original values to prevent polluting the route data.
snapshot.Restore();
}
}
}
private class TreeNode
{
public int Index = -1;
public EntryKind Kind;
public List<TreeNode> Children = new List<TreeNode>();
public List<MatchEntry> Matches = new List<MatchEntry>();
public string Value;
}
private enum EntryKind : byte
{
Literal,
Parameter,
Catchall,
}
private struct Entry
{
public EntryKind Kind;
public int FirstChild;
public int NextSibling;
public string Value;
public MatchEntry[] Matches;
}
private struct MatchEntry
{
public IDictionary<string, IRouteConstraint> Constraints;
public TemplateMatcher Matcher;
public IRouteHandler Handler;
}
}
}
using System;
using System.Linq;
using System.Text.Encodings.Web;
using System.Threading.Tasks;
using BenchmarkDotNet.Attributes;
using Microsoft.AspNetCore.Http;
using Microsoft.AspNetCore.Routing;
using Microsoft.AspNetCore.Routing.Internal;
using Microsoft.AspNetCore.Routing.Template;
using Microsoft.AspNetCore.Routing.Tree;
using Microsoft.Extensions.Logging;
using Microsoft.Extensions.ObjectPool;
using Microsoft.Extensions.Options;
namespace PackedRouting.Benchmarks
{
public class AttributeRoutingBenchmark
{
private readonly IRouter _treeRouter;
private readonly IRouter _packedRouter;
private readonly RequestEntry[] _requests;
public AttributeRoutingBenchmark()
{
var handler = new RouteHandler((next) => Task.FromResult<object>(null));
var treeBuilder = new TreeRouteBuilder(
new LoggerFactory(),
UrlEncoder.Default,
new DefaultObjectPool<UriBuildingContext>(new UriBuilderContextPooledObjectPolicy(UrlEncoder.Default)),
new DefaultInlineConstraintResolver(new OptionsManager<RouteOptions>(Enumerable.Empty<IConfigureOptions<RouteOptions>>())));
treeBuilder.MapInbound(handler, TemplateParser.Parse("api/Widgets"), "default", 0);
treeBuilder.MapInbound(handler, TemplateParser.Parse("api/Widgets/{id}"), "default", 0);
treeBuilder.MapInbound(handler, TemplateParser.Parse("api/Widgets/search/{term}"), "default", 0);
treeBuilder.MapInbound(handler, TemplateParser.Parse("admin/users/{id}"), "default", 0);
treeBuilder.MapInbound(handler, TemplateParser.Parse("admin/users/{id}/manage"), "default", 0);
_treeRouter = treeBuilder.Build();
_packedRouter = new PackedRouter(treeBuilder, new LoggerFactory());
_requests = new RequestEntry[3];
_requests[0].HttpContext = new DefaultHttpContext();
_requests[0].HttpContext.Request.Path = "/api/Widgets/5";
_requests[0].IsMatch = true;
_requests[0].Values = new RouteValueDictionary(new { id = 5 });
_requests[1].HttpContext = new DefaultHttpContext();
_requests[1].HttpContext.Request.Path = "/admin/users/17/mAnage";
_requests[1].IsMatch = true;
_requests[1].Values = new RouteValueDictionary(new { id = 17 });
_requests[2].HttpContext = new DefaultHttpContext();
_requests[2].HttpContext.Request.Path = "/api/Widgets/search/dldldldldld/ddld";
_requests[2].IsMatch = false;
_requests[2].Values = new RouteValueDictionary();
}
[Benchmark]
public async Task Regular()
{
for (var i = 0; i < _requests.Length; i++)
{
var context = new RouteContext(_requests[i].HttpContext);
await _treeRouter.RouteAsync(context);
Verify(context, i);
}
}
[Benchmark]
public async Task Packed()
{
for (var i = 0; i < _requests.Length; i++)
{
var context = new RouteContext(_requests[i].HttpContext);
await _packedRouter.RouteAsync(context);
Verify(context, i);
}
}
private void Verify(RouteContext context, int i)
{
if (_requests[i].IsMatch)
{
if (context.Handler == null)
{
throw new InvalidOperationException($"Failed {i}");
}
var values = _requests[i].Values;
if (values.Count != context.RouteData.Values.Count)
{
throw new InvalidOperationException($"Failed {i}");
}
}
else
{
if (context.Handler != null)
{
throw new InvalidOperationException($"Failed {i}");
}
if (context.RouteData.Values.Count != 0)
{
throw new InvalidOperationException($"Failed {i}");
}
}
}
private struct RequestEntry
{
public HttpContext HttpContext;
public bool IsMatch;
public RouteValueDictionary Values;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment