The fever dreams of a madman

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;
        }
    }
}