rynowak/attribute_routing_2_0.cs

## attribute_routing_2_0.cs
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;
        }
    }
}
	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;
	}
	}
	}