aspnetcore/modules/Routing

commit fd83b300b8d3a0223762c18e4a3b6a6c32c3bb01
Author: Jass Bagga <[email protected]>
Date:   Tue Nov 7 10:51:50 2017 -0800

    Port TreeMatcher (#488)
    
    Addresses #472

diff --git a/benchmarks/Microsoft.AspNetCore.Dispatcher.Performance/DispatcherBenchmark.cs b/benchmarks/Microsoft.AspNetCore.Dispatcher.Performance/DispatcherBenchmark.cs
index a8232e0b026..befa1725ecc 100644
--- a/benchmarks/Microsoft.AspNetCore.Dispatcher.Performance/DispatcherBenchmark.cs
+++ b/benchmarks/Microsoft.AspNetCore.Dispatcher.Performance/DispatcherBenchmark.cs
@@ -2,15 +2,11 @@
 // Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
 
 using System;
-using System.Text.Encodings.Web;
+using System.Collections.Generic;
 using System.Threading.Tasks;
 using BenchmarkDotNet.Attributes;
 using Microsoft.AspNetCore.Http;
 using Microsoft.AspNetCore.Routing;
-using Microsoft.AspNetCore.Routing.Tree;
-using Microsoft.Extensions.Logging.Abstractions;
-using Microsoft.Extensions.ObjectPool;
-using Microsoft.Extensions.Options;
 
 namespace Microsoft.AspNetCore.Dispatcher.Performance
 {
@@ -19,25 +15,25 @@ namespace Microsoft.AspNetCore.Dispatcher.Performance
         private const int NumberOfRequestTypes = 3;
         private const int Iterations = 100;
 
-        private readonly IRouter _treeRouter;
+        private readonly IMatcher _treeMatcher;
         private readonly RequestEntry[] _requests;
 
         public DispatcherBenchmark()
         {
-            var handler = new RouteHandler((next) => Task.FromResult<object>(null));
-
-            var treeBuilder = new TreeRouteBuilder(
-                NullLoggerFactory.Instance,
-                new RoutePatternBinderFactory(UrlEncoder.Default, new DefaultObjectPoolProvider()),
-                new DefaultInlineConstraintResolver(Options.Create(new RouteOptions())));
-
-            treeBuilder.MapInbound(handler, Routing.Template.TemplateParser.Parse("api/Widgets"), "default", 0);
-            treeBuilder.MapInbound(handler, Routing.Template.TemplateParser.Parse("api/Widgets/{id}"), "default", 0);
-            treeBuilder.MapInbound(handler, Routing.Template.TemplateParser.Parse("api/Widgets/search/{term}"), "default", 0);
-            treeBuilder.MapInbound(handler, Routing.Template.TemplateParser.Parse("admin/users/{id}"), "default", 0);
-            treeBuilder.MapInbound(handler, Routing.Template.TemplateParser.Parse("admin/users/{id}/manage"), "default", 0);
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("api/Widgets", Benchmark_Delegate),
+                    new RoutePatternEndpoint("api/Widgets/{id}", Benchmark_Delegate),
+                    new RoutePatternEndpoint("api/Widgets/search/{term}", Benchmark_Delegate),
+                    new RoutePatternEndpoint("admin/users/{id}", Benchmark_Delegate),
+                    new RoutePatternEndpoint("admin/users/{id}/manage", Benchmark_Delegate),
+                },
+            };
 
-            _treeRouter = treeBuilder.Build();
+            var factory = new TreeMatcherFactory();
+            _treeMatcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
 
             _requests = new RequestEntry[NumberOfRequestTypes];
 
@@ -64,38 +60,38 @@ namespace Microsoft.AspNetCore.Dispatcher.Performance
             {
                 for (var j = 0; j < _requests.Length; j++)
                 {
-                    var context = new RouteContext(_requests[j].HttpContext);
+                    var context = new MatcherContext(_requests[j].HttpContext);
 
-                    await _treeRouter.RouteAsync(context);
+                    await _treeMatcher.MatchAsync(context);
 
                     Verify(context, j);
                 }
             }
         }
 
-        private void Verify(RouteContext context, int i)
+        private void Verify(MatcherContext context, int i)
         {
             if (_requests[i].IsMatch)
             {
-                if (context.Handler == null)
+                if (context.Endpoint == null)
                 {
                     throw new InvalidOperationException($"Failed {i}");
                 }
 
                 var values = _requests[i].Values;
-                if (values.Count != context.RouteData.Values.Count)
+                if (values.Count != context.Values.Count)
                 {
                     throw new InvalidOperationException($"Failed {i}");
                 }
             }
             else
             {
-                if (context.Handler != null)
+                if (context.Endpoint != null)
                 {
                     throw new InvalidOperationException($"Failed {i}");
                 }
 
-                if (context.RouteData.Values.Count != 0)
+                if (context.Values.Count != 0)
                 {
                     throw new InvalidOperationException($"Failed {i}");
                 }
@@ -108,5 +104,10 @@ namespace Microsoft.AspNetCore.Dispatcher.Performance
             public bool IsMatch;
             public RouteValueDictionary Values;
         }
+
+        private static Task Benchmark_Delegate(HttpContext httpContext)
+        {
+            return Task.CompletedTask;
+        }
     }
 }
diff --git a/samples/DispatcherSample/Startup.cs b/samples/DispatcherSample/Startup.cs
index 7317e8c2575..a9259cc14ef 100644
--- a/samples/DispatcherSample/Startup.cs
+++ b/samples/DispatcherSample/Startup.cs
@@ -1,13 +1,11 @@
 // Copyright (c) .NET Foundation. All rights reserved.
 // Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
 
-using System.Linq;
 using System.Threading.Tasks;
 using Microsoft.AspNetCore.Builder;
 using Microsoft.AspNetCore.Dispatcher;
 using Microsoft.AspNetCore.Hosting;
 using Microsoft.AspNetCore.Http;
-using Microsoft.AspNetCore.Routing.Dispatcher;
 using Microsoft.Extensions.DependencyInjection;
 using Microsoft.Extensions.Logging;
 
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Constraints/AlphaDispatcherValueConstraint.cs b/src/Microsoft.AspNetCore.Dispatcher/Constraints/AlphaDispatcherValueConstraint.cs
new file mode 100644
index 00000000000..8291289ff13
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Constraints/AlphaDispatcherValueConstraint.cs
@@ -0,0 +1,18 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// Constrains a dispatcher value parameter to contain only lowercase or uppercase letters A through Z in the English alphabet.
+    /// </summary>
+    public class AlphaDispatcherValueConstraint : RegexDispatcherValueConstraint
+    {
+        /// <summary>
+        /// Initializes a new instance of the <see cref="AlphaDispatcherValueConstraint" /> class.
+        /// </summary>
+        public AlphaDispatcherValueConstraint() : base(@"^[a-z]*$")
+        {
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Constraints/DispatcherValueConstraintBuilder.cs b/src/Microsoft.AspNetCore.Dispatcher/Constraints/DispatcherValueConstraintBuilder.cs
index ed93324b98b..f1363f34e15 100644
--- a/src/Microsoft.AspNetCore.Dispatcher/Constraints/DispatcherValueConstraintBuilder.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/Constraints/DispatcherValueConstraintBuilder.cs
@@ -10,7 +10,7 @@ namespace Microsoft.AspNetCore.Dispatcher
     /// A builder for producing a mapping of keys to <see cref="IDispatcherValueConstraint"/>.
     /// </summary>
     /// <remarks>
-    /// <see cref="DispatcherValueConstraintBuilder"/> allows iterative building a set of route constraints, and will
+    /// <see cref="DispatcherValueConstraintBuilder"/> allows iterative building a set of dispatcher value constraints, and will
     /// merge multiple entries for the same key.
     /// </remarks>
     public class DispatcherValueConstraintBuilder
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Constraints/IntDispatcherValueConstraint.cs b/src/Microsoft.AspNetCore.Dispatcher/Constraints/IntDispatcherValueConstraint.cs
new file mode 100644
index 00000000000..77d9f70f747
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Constraints/IntDispatcherValueConstraint.cs
@@ -0,0 +1,36 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System;
+using System.Globalization;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// Constrains a dispatcher value parameter to represent only 32-bit integer values.
+    /// </summary>
+    public class IntDispatcherValueConstraint : IDispatcherValueConstraint
+    {
+        /// <inheritdoc />
+        public bool Match(DispatcherValueConstraintContext constraintContext)
+        {
+            if (constraintContext == null)
+            {
+                throw new ArgumentNullException(nameof(constraintContext));
+            }
+
+            if (constraintContext.Values.TryGetValue(constraintContext.Key, out var value) && value != null)
+            {
+                if (value is int)
+                {
+                    return true;
+                }
+
+                var valueString = Convert.ToString(value, CultureInfo.InvariantCulture);
+                return int.TryParse(valueString, NumberStyles.Integer, CultureInfo.InvariantCulture, out var result);
+            }
+
+            return false;
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Constraints/RegexStringDispatcherValueConstraint.cs b/src/Microsoft.AspNetCore.Dispatcher/Constraints/RegexStringDispatcherValueConstraint.cs
new file mode 100644
index 00000000000..67bcf263870
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Constraints/RegexStringDispatcherValueConstraint.cs
@@ -0,0 +1,20 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// Represents a regex constraint.
+    /// </summary>
+    public class RegexStringDispatcherValueConstraint : RegexDispatcherValueConstraint
+    {
+        /// <summary>
+        /// Initializes a new instance of the <see cref="RegexStringDispatcherValueConstraint" /> class.
+        /// </summary>
+        /// <param name="regexPattern">The regular expression pattern to match.</param>
+        public RegexStringDispatcherValueConstraint(string regexPattern)
+            : base(regexPattern)
+        {
+        }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/DependencyInjection/DispatcherServiceCollectionExtensions.cs b/src/Microsoft.AspNetCore.Dispatcher/DependencyInjection/DispatcherServiceCollectionExtensions.cs
index ea36a43083e..26d61305057 100644
--- a/src/Microsoft.AspNetCore.Dispatcher/DependencyInjection/DispatcherServiceCollectionExtensions.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/DependencyInjection/DispatcherServiceCollectionExtensions.cs
@@ -36,6 +36,7 @@ namespace Microsoft.Extensions.DependencyInjection
             // Misc Infrastructure
             //
             services.TryAddSingleton<RoutePatternBinderFactory>();
+            services.TryAddSingleton<IConstraintFactory, DefaultConstraintFactory>();
 
             services.TryAddEnumerable(ServiceDescriptor.Singleton<IHandlerFactory, RoutePatternEndpointHandlerFactory>());
 
diff --git a/src/Microsoft.AspNetCore.Dispatcher/DispatcherOptions.cs b/src/Microsoft.AspNetCore.Dispatcher/DispatcherOptions.cs
index a4a26f662f1..6e55164498a 100644
--- a/src/Microsoft.AspNetCore.Dispatcher/DispatcherOptions.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/DispatcherOptions.cs
@@ -10,6 +10,36 @@ namespace Microsoft.AspNetCore.Dispatcher
     {
         public MatcherCollection Matchers { get; } = new MatcherCollection();
 
-        public IDictionary<string, Type> ConstraintMap = new Dictionary<string, Type>();
+        private IDictionary<string, Type> _constraintTypeMap = GetDefaultConstraintMap();
+
+        public IDictionary<string, Type> ConstraintMap
+        {
+            get
+            {
+                return _constraintTypeMap;
+            }
+            set
+            {
+                if (value == null)
+                {
+                    throw new ArgumentNullException(nameof(ConstraintMap));
+                }
+
+                _constraintTypeMap = value;
+            }
+        }
+
+        private static IDictionary<string, Type> GetDefaultConstraintMap()
+        {
+            return new Dictionary<string, Type>(StringComparer.OrdinalIgnoreCase)
+            {
+                // Type-specific constraints
+                { "int", typeof(IntDispatcherValueConstraint) },
+
+                //// Regex-based constraints
+                { "alpha", typeof(AlphaDispatcherValueConstraint) },
+                { "regex", typeof(RegexStringDispatcherValueConstraint) },
+            };
+        }
     }
 }
diff --git a/src/Microsoft.AspNetCore.Dispatcher/EndpointOrderMetadata.cs b/src/Microsoft.AspNetCore.Dispatcher/EndpointOrderMetadata.cs
new file mode 100644
index 00000000000..eefbf1efa2b
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/EndpointOrderMetadata.cs
@@ -0,0 +1,15 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    public class EndpointOrderMetadata : IEndpointOrderMetadata
+    {
+        public EndpointOrderMetadata(int order)
+        {
+            Order = order;
+        }
+
+        public int Order { get; }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/IEndpointOrderMetadata.cs b/src/Microsoft.AspNetCore.Dispatcher/IEndpointOrderMetadata.cs
new file mode 100644
index 00000000000..31b270ae8f4
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/IEndpointOrderMetadata.cs
@@ -0,0 +1,10 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    public interface IEndpointOrderMetadata
+    {
+        int Order { get; }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/LoggerExtensions.cs b/src/Microsoft.AspNetCore.Dispatcher/LoggerExtensions.cs
index 89ff7048b6a..6143a9b3e18 100644
--- a/src/Microsoft.AspNetCore.Dispatcher/LoggerExtensions.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/LoggerExtensions.cs
@@ -83,7 +83,17 @@ namespace Microsoft.AspNetCore.Dispatcher
             new EventId(3, "NoEndpointMatchedRequestMethod"),
             "No endpoint matched request method '{Method}'.");
 
-        // DispatcherValueConstraintMatcher
+        // TreeMatcher
+        private static readonly Action<ILogger, string, Exception> _requestShortCircuited = LoggerMessage.Define<string>(
+            LogLevel.Information,
+            new EventId(3, "RequestShortCircuited"),
+            "The current request '{RequestPath}' was short circuited.");
+
+        private static readonly Action<ILogger, string, Exception> _matchedRoute = LoggerMessage.Define<string>(
+                LogLevel.Debug,
+                1,
+                "Request successfully matched the route pattern '{RoutePattern}'.");
+
         private static readonly Action<ILogger, object, string, IDispatcherValueConstraint, Exception> _routeValueDoesNotMatchConstraint = LoggerMessage.Define<object, string, IDispatcherValueConstraint>(
                 LogLevel.Debug,
                 1,
@@ -98,6 +108,19 @@ namespace Microsoft.AspNetCore.Dispatcher
             _routeValueDoesNotMatchConstraint(logger, routeValue, routeKey, routeConstraint, null);
         }
 
+        public static void RequestShortCircuited(this ILogger logger, MatcherContext matcherContext)
+        {
+            var requestPath = matcherContext.HttpContext.Request.Path;
+            _requestShortCircuited(logger, requestPath, null);
+        }
+
+        public static void MatchedRoute(
+            this ILogger logger,
+            string routePattern)
+        {
+            _matchedRoute(logger, routePattern, null);
+        }
+
         public static void AmbiguousEndpoints(this ILogger logger, string ambiguousEndpoints)
         {
             _ambiguousEndpoints(logger, ambiguousEndpoints, null);
diff --git a/src/Microsoft.AspNetCore.Dispatcher/RoutePatternEndpoint.cs b/src/Microsoft.AspNetCore.Dispatcher/RoutePatternEndpoint.cs
index 6e7a3ca3b07..1047159b6aa 100644
--- a/src/Microsoft.AspNetCore.Dispatcher/RoutePatternEndpoint.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/RoutePatternEndpoint.cs
@@ -2,8 +2,6 @@
 // Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
 
 using System;
-using System.Collections.Generic;
-using System.Linq;
 using Microsoft.AspNetCore.Http;
 
 namespace Microsoft.AspNetCore.Dispatcher
diff --git a/src/Microsoft.AspNetCore.Dispatcher/RoutePrecedence.cs b/src/Microsoft.AspNetCore.Dispatcher/RoutePrecedence.cs
new file mode 100644
index 00000000000..231b2f0945e
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/RoutePrecedence.cs
@@ -0,0 +1,77 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System;
+using System.Diagnostics;
+using System.Linq;
+using Microsoft.AspNetCore.Dispatcher.Patterns;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// Computes precedence for a route pattern.
+    /// </summary>
+    public static class RoutePrecedence
+    {
+        // Compute the precedence for matching a provided url
+        // e.g.: /api/template == 1.1
+        //       /api/template/{id} == 1.13
+        //       /api/{id:int} == 1.2
+        //       /api/template/{id:int} == 1.12
+        public static decimal ComputeInbound(RoutePattern routePattern)
+        {
+            // Each precedence digit corresponds to one decimal place. For example, 3 segments with precedences 2, 1,
+            // and 4 results in a combined precedence of 2.14 (decimal).
+            var precedence = 0m;
+
+            for (var i = 0; i < routePattern.PathSegments.Count; i++)
+            {
+                var segment = routePattern.PathSegments[i];
+
+                var digit = ComputeInboundPrecedenceDigit(segment);
+                Debug.Assert(digit >= 0 && digit < 10);
+
+                precedence += decimal.Divide(digit, (decimal)Math.Pow(10, i));
+            }
+
+            return precedence;
+        }
+
+        // Segments have the following order:
+        // 1 - Literal segments
+        // 2 - Constrained parameter segments / Multi-part segments
+        // 3 - Unconstrained parameter segments
+        // 4 - Constrained wildcard parameter segments
+        // 5 - Unconstrained wildcard parameter segments
+        private static int ComputeInboundPrecedenceDigit(RoutePatternPathSegment segment)
+        {
+            if (segment.Parts.Count > 1)
+            {
+                // Multi-part segments should appear after literal segments and along with parameter segments
+                return 2;
+            }
+
+            var part = segment.Parts[0];
+            // Literal segments always go first
+            if (part.IsLiteral)
+            {
+                return 1;
+            }
+            else
+            {
+                Debug.Assert(part.IsParameter);
+                var parameter = (RoutePatternParameter)part;
+                var digit = parameter.IsCatchAll ? 5 : 3;
+
+                // If there is a dispatcher value constraint for the parameter, reduce order by 1
+                // Constrained parameters end up with order 2, Constrained catch alls end up with order 4
+                if (parameter.Constraints != null && parameter.Constraints.Any())
+                {
+                    digit--;
+                }
+
+                return digit;
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundMatch.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundMatch.cs
new file mode 100644
index 00000000000..018fb02e9e6
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundMatch.cs
@@ -0,0 +1,29 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System.Diagnostics;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// A candidate endpoint to match incoming URLs in a <c>TreeMatcher</c>.
+    /// </summary>
+    [DebuggerDisplay("{DebuggerToString(),nq}")]
+    public class InboundMatch
+    {
+        /// <summary>
+        /// Gets or sets the <see cref="InboundRouteEntry"/>.
+        /// </summary>
+        public InboundRouteEntry Entry { get; set; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="RoutePatternMatcher"/>.
+        /// </summary>
+        public RoutePatternMatcher RoutePatternMatcher { get; set; }
+
+        private string DebuggerToString()
+        {
+            return RoutePatternMatcher?.RoutePattern?.RawText;
+        }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundRouteEntry.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundRouteEntry.cs
new file mode 100644
index 00000000000..e54d626d800
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/InboundRouteEntry.cs
@@ -0,0 +1,51 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System.Collections.Generic;
+using Microsoft.AspNetCore.Dispatcher.Patterns;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// Used to build a <see cref="TreeMatcher"/>. Represents a route pattern that will be used to match incoming
+    /// request URLs.
+    /// </summary>
+    public class InboundRouteEntry
+    {
+        /// <summary>
+        /// Gets or sets the dispatcher value constraints.
+        /// </summary>
+        public IDictionary<string, IDispatcherValueConstraint> Constraints { get; set; }
+
+        /// <summary>
+        /// Gets or sets the dispatcher value defaults.
+        /// </summary>
+        public DispatcherValueCollection Defaults { get; set; }
+
+        /// <summary>
+        /// Gets or sets the order of the entry.
+        /// </summary>
+        /// <remarks>
+        /// Entries are ordered first by <see cref="Order"/> (ascending) then by <see cref="Precedence"/> (descending).
+        /// </remarks>
+        public int Order { get; set; }
+
+        /// <summary>
+        /// Gets or sets the precedence of the entry.
+        /// </summary>
+        /// <remarks>
+        /// Entries are ordered first by <see cref="Order"/> (ascending) then by <see cref="Precedence"/> (descending).
+        /// </remarks>
+        public decimal Precedence { get; set; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="RoutePattern"/>.
+        /// </summary>
+        public RoutePattern RoutePattern { get; set; }
+
+        /// <summary>
+        /// Gets or sets an arbitrary value associated with the entry.
+        /// </summary>
+        public object Tag { get; set; }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcher.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcher.cs
new file mode 100644
index 00000000000..c53c2aa6faa
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcher.cs
@@ -0,0 +1,543 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Threading;
+using System.Threading.Tasks;
+using Microsoft.AspNetCore.Dispatcher.Internal;
+using Microsoft.AspNetCore.Dispatcher.Patterns;
+using Microsoft.AspNetCore.Http;
+using Microsoft.Extensions.DependencyInjection;
+using Microsoft.Extensions.Internal;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    public class TreeMatcher : MatcherBase
+    {
+        private bool _dataInitialized;
+        private object _lock;
+        private Cache _cache;
+        private IConstraintFactory _constraintFactory;
+
+        private readonly Func<Cache> _initializer;
+
+        public TreeMatcher()
+        {
+            _lock = new object();
+            _initializer = CreateCache;
+        }
+
+        public int Version { get; private set; }
+
+        public override async Task MatchAsync(MatcherContext context)
+        {
+            if (context == null)
+            {
+                throw new ArgumentNullException(nameof(context));
+            }
+
+            EnsureServicesInitialized(context);
+
+            var cache = LazyInitializer.EnsureInitialized(ref _cache, ref _dataInitialized, ref _lock, _initializer);
+
+            var values = new DispatcherValueCollection();
+            context.Values = values;
+
+            for (var i = 0; i < cache.Trees.Length; i++)
+            {
+                var tree = cache.Trees[i];
+                var tokenizer = new PathTokenizer(context.HttpContext.Request.Path);
+
+                var treenumerator = new Treenumerator(tree.Root, tokenizer);
+
+                while (treenumerator.MoveNext())
+                {
+                    var node = treenumerator.Current;
+                    foreach (var item in node.Matches)
+                    {
+                        var entry = item.Entry;
+                        var matcher = item.RoutePatternMatcher;
+
+                        values.Clear();
+                        if (!matcher.TryMatch(context.HttpContext.Request.Path, values))
+                        {
+                            continue;
+                        }
+
+                        Logger.MatchedRoute(entry.RoutePattern.RawText);
+
+                        if (!MatchConstraints(context.HttpContext, values, entry.Constraints))
+                        {
+                            continue;
+                        }
+
+                        await SelectEndpointAsync(context, (Endpoint[])entry.Tag);
+                        if (context.ShortCircuit != null)
+                        {
+                            Logger.RequestShortCircuited(context);
+                            return;
+                        }
+
+                        if (context.Endpoint != null)
+                        {
+                            if (context.Endpoint is IRoutePatternEndpoint templateEndpoint)
+                            {
+                                foreach (var kvp in templateEndpoint.Values)
+                                {
+                                    if (!context.Values.ContainsKey(kvp.Key))
+                                    {
+                                        context.Values[kvp.Key] = kvp.Value;
+                                    }
+                                }
+                            }
+
+                            return;
+                        }
+                    }
+                }
+            }
+        }
+
+        private bool MatchConstraints(HttpContext httpContext, DispatcherValueCollection values, IDictionary<string, IDispatcherValueConstraint> constraints)
+        {
+            if (constraints != null)
+            {
+                foreach (var kvp in constraints)
+                {
+                    var constraint = kvp.Value;
+                    var constraintContext = new DispatcherValueConstraintContext(httpContext, values, ConstraintPurpose.IncomingRequest)
+                    {
+                        Key = kvp.Key
+                    };
+
+                    if (!constraint.Match(constraintContext))
+                    {
+                        values.TryGetValue(kvp.Key, out var value);
+
+                        Logger.RouteValueDoesNotMatchConstraint(value, kvp.Key, kvp.Value);
+                        return false;
+                    }
+                }
+            }
+
+            return true;
+        }
+
+        internal Cache CreateCache()
+        {
+            var endpoints = GetEndpoints();
+
+            var groups = new Dictionary<Key, List<Endpoint>>();
+
+            for (var i = 0; i < endpoints.Count; i++)
+            {
+                var endpoint = endpoints[i];
+
+                var templateEndpoint = endpoint as IRoutePatternEndpoint;
+                if (templateEndpoint == null)
+                {
+                    continue;
+                }
+
+                var order = endpoint.Metadata?.GetMetadata<IEndpointOrderMetadata>()?.Order ?? 0;
+                if (!groups.TryGetValue(new Key(order, templateEndpoint.Pattern), out var group))
+                {
+                    group = new List<Endpoint>();
+                    groups.Add(new Key(order, templateEndpoint.Pattern), group);
+                }
+
+                group.Add(endpoint);
+            }
+
+            var entries = new List<InboundRouteEntry>();
+            foreach (var group in groups)
+            {
+                var routePattern = RoutePattern.Parse(group.Key.RoutePattern);
+                var entryExists = entries.Any(item => item.RoutePattern.RawText == routePattern.RawText);
+                if (!entryExists)
+                {
+                    entries.Add(MapInbound(routePattern, group.Value.ToArray(), group.Key.Order));
+                }
+            }
+
+            var trees = new List<UrlMatchingTree>();
+            for (var i = 0; i < entries.Count; i++)
+            {
+                var entry = entries[i];
+
+                while (trees.Count <= entry.Order)
+                {
+                    trees.Add(new UrlMatchingTree(entry.Order));
+                }
+
+                var tree = trees[entry.Order];
+
+                AddEntryToTree(tree, entry);
+            }
+
+            return new Cache(trees.ToArray());
+        }
+
+        private InboundRouteEntry MapInbound(
+            RoutePattern routePattern,
+            object tag,
+            int order)
+        {
+            if (routePattern == null)
+            {
+                throw new ArgumentNullException(nameof(routePattern));
+            }
+
+            var entry = new InboundRouteEntry()
+            {
+                Precedence = RoutePrecedence.ComputeInbound(routePattern),
+                RoutePattern = routePattern,
+                Order = order,
+                Tag = tag
+            };
+
+            var constraintBuilder = new DispatcherValueConstraintBuilder(_constraintFactory, routePattern.RawText);
+            foreach (var parameter in routePattern.Parameters)
+            {
+                if (parameter.Constraints != null)
+                {
+                    if (parameter.IsOptional)
+                    {
+                        constraintBuilder.SetOptional(parameter.Name);
+                    }
+
+                    foreach (var constraint in parameter.Constraints)
+                    {
+                        constraintBuilder.AddResolvedConstraint(parameter.Name, constraint.RawText);
+                    }
+                }
+            }
+
+            entry.Constraints = constraintBuilder.Build();
+
+            entry.Defaults = new DispatcherValueCollection();
+            foreach (var parameter in entry.RoutePattern.Parameters)
+            {
+                if (parameter.DefaultValue != null)
+                {
+                    entry.Defaults.Add(parameter.Name, parameter.DefaultValue);
+                }
+            }
+            return entry;
+        }
+
+        internal static void AddEntryToTree(UrlMatchingTree tree, InboundRouteEntry entry)
+        {
+            // The url matching tree represents all the routes asociated with a given
+            // order. Each node in the tree represents all the different categories
+            // a segment can have for which there is a defined inbound route entry.
+            // Each node contains a set of Matches that indicate all the routes for which
+            // a URL is a potential match. This list contains the routes with the same
+            // number of segments and the routes with the same number of segments plus an
+            // additional catch all parameter (as it can be empty).
+            // For example, for a set of routes like:
+            // 'Customer/Index/{id}'
+            // '{Controller}/{Action}/{*parameters}'
+            //
+            // The route tree will look like:
+            // Root ->
+            //     Literals: Customer ->
+            //                   Literals: Index ->
+            //                                Parameters: {id}
+            //                                                Matches: 'Customer/Index/{id}'
+            //     Parameters: {Controller} ->
+            //                     Parameters: {Action} ->
+            //                                     Matches: '{Controller}/{Action}/{*parameters}'
+            //                                     CatchAlls: {*parameters}
+            //                                                    Matches: '{Controller}/{Action}/{*parameters}'
+            //
+            // When the tree router tries to match a route, it iterates the list of url matching trees
+            // in ascending order. For each tree it traverses each node starting from the root in the
+            // following order: Literals, constrained parameters, parameters, constrained catch all routes, catch alls.
+            // When it gets to a node of the same length as the route its trying to match, it simply looks at the list of
+            // candidates (which is in precence order) and tries to match the url against it.
+
+            var current = tree.Root;
+            var matcher = new RoutePatternMatcher(entry.RoutePattern, entry.Defaults);
+
+            for (var i = 0; i < entry.RoutePattern.PathSegments.Count; i++)
+            {
+                var segment = entry.RoutePattern.PathSegments[i];
+                if (!segment.IsSimple)
+                {
+                    // Treat complex segments as a constrained parameter
+                    if (current.ConstrainedParameters == null)
+                    {
+                        current.ConstrainedParameters = new UrlMatchingNode(depth: i + 1);
+                    }
+
+                    current = current.ConstrainedParameters;
+                    continue;
+                }
+
+                Debug.Assert(segment.Parts.Count == 1);
+                var part = segment.Parts[0];
+                if (part.IsLiteral)
+                {
+                    var literal = (RoutePatternLiteral)part;
+                    if (!current.Literals.TryGetValue(literal.Content, out var next))
+                    {
+                        next = new UrlMatchingNode(depth: i + 1);
+                        current.Literals.Add(literal.Content, next);
+                    }
+
+                    current = next;
+                    continue;
+                }
+
+                // We accept templates that have intermediate optional values, but we ignore
+                // those values for route matching. For that reason, we need to add the entry
+                // to the list of matches, only if the remaining segments are optional. For example:
+                // /{controller}/{action=Index}/{id} will be equivalent to /{controller}/{action}/{id}
+                // for the purposes of route matching.
+                if (part.IsParameter &&
+                    RemainingSegmentsAreOptional(entry.RoutePattern.PathSegments, i))
+                {
+                    current.Matches.Add(new InboundMatch() { Entry = entry, RoutePatternMatcher = matcher });
+                }
+
+                var parameter = part as RoutePatternParameter;
+                if (parameter != null && parameter.Constraints.Any() && !parameter.IsCatchAll)
+                {
+                    if (current.ConstrainedParameters == null)
+                    {
+                        current.ConstrainedParameters = new UrlMatchingNode(depth: i + 1);
+                    }
+
+                    current = current.ConstrainedParameters;
+                    continue;
+                }
+
+                if (parameter != null && !parameter.IsCatchAll)
+                {
+                    if (current.Parameters == null)
+                    {
+                        current.Parameters = new UrlMatchingNode(depth: i + 1);
+                    }
+
+                    current = current.Parameters;
+                    continue;
+                }
+
+                if (parameter != null && parameter.Constraints.Any() && parameter.IsCatchAll)
+                {
+                    if (current.ConstrainedCatchAlls == null)
+                    {
+                        current.ConstrainedCatchAlls = new UrlMatchingNode(depth: i + 1) { IsCatchAll = true };
+                    }
+
+                    current = current.ConstrainedCatchAlls;
+                    continue;
+                }
+
+                if (parameter != null && parameter.IsCatchAll)
+                {
+                    if (current.CatchAlls == null)
+                    {
+                        current.CatchAlls = new UrlMatchingNode(depth: i + 1) { IsCatchAll = true };
+                    }
+
+                    current = current.CatchAlls;
+                    continue;
+                }
+
+                Debug.Fail("We shouldn't get here.");
+            }
+
+            current.Matches.Add(new InboundMatch() { Entry = entry, RoutePatternMatcher = matcher });
+            current.Matches.Sort((x, y) =>
+            {
+                var result = x.Entry.Precedence.CompareTo(y.Entry.Precedence);
+                return result == 0 ? x.Entry.RoutePattern.RawText.CompareTo(y.Entry.RoutePattern.RawText) : result;
+            });
+        }
+
+        private static bool RemainingSegmentsAreOptional(IReadOnlyList<RoutePatternPathSegment> segments, int currentParameterIndex)
+        {
+            for (var i = currentParameterIndex; i < segments.Count; i++)
+            {
+                if (!segments[i].IsSimple)
+                {
+                    // /{complex}-{segment}
+                    return false;
+                }
+
+                var part = segments[i].Parts[0];
+                if (!part.IsParameter)
+                {
+                    // /literal
+                    return false;
+                }
+
+                var parameter = (RoutePatternParameter)part;
+                var isOptionlCatchAllOrHasDefaultValue = parameter.IsOptional ||
+                    parameter.IsCatchAll ||
+                    parameter.DefaultValue != null;
+
+                if (!isOptionlCatchAllOrHasDefaultValue)
+                {
+                    // /{parameter}
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        private struct Key : IEquatable<Key>
+        {
+            public readonly int Order;
+            public readonly string RoutePattern;
+
+            public Key(int order, string routePattern)
+            {
+                Order = order;
+                RoutePattern = routePattern;
+            }
+
+            public bool Equals(Key other)
+            {
+                return Order == other.Order && string.Equals(RoutePattern, other.RoutePattern, StringComparison.OrdinalIgnoreCase);
+            }
+
+            public override bool Equals(object obj)
+            {
+                return obj is Key ? Equals((Key)obj) : false;
+            }
+
+            public override int GetHashCode()
+            {
+                var hash = new HashCodeCombiner();
+                hash.Add(Order);
+                hash.Add(RoutePattern, StringComparer.OrdinalIgnoreCase);
+                return hash;
+            }
+        }
+
+        internal class Cache
+        {
+            public readonly UrlMatchingTree[] Trees;
+
+            public Cache(UrlMatchingTree[] trees)
+            {
+                Trees = trees;
+            }
+        }
+
+        private struct Treenumerator : IEnumerator<UrlMatchingNode>
+        {
+            private readonly Stack<UrlMatchingNode> _stack;
+            private readonly PathTokenizer _tokenizer;
+
+            public Treenumerator(UrlMatchingNode root, PathTokenizer tokenizer)
+            {
+                _stack = new Stack<UrlMatchingNode>();
+                _tokenizer = tokenizer;
+                Current = null;
+
+                _stack.Push(root);
+            }
+
+            public UrlMatchingNode Current { get; private set; }
+
+            object IEnumerator.Current => Current;
+
+            public void Dispose()
+            {
+            }
+
+            public bool MoveNext()
+            {
+                if (_stack == null)
+                {
+                    return false;
+                }
+
+                while (_stack.Count > 0)
+                {
+                    var next = _stack.Pop();
+
+                    // In case of wild card segment, the request path segment length can be greater
+                    // Example:
+                    // Template:    a/{*path}
+                    // Request Url: a/b/c/d
+                    if (next.IsCatchAll && next.Matches.Count > 0)
+                    {
+                        Current = next;
+                        return true;
+                    }
+
+                    // Next template has the same length as the url we are trying to match
+                    // The only possible matching segments are either our current matches or
+                    // any catch-all segment after this segment in which the catch all is empty.
+                    else if (next.Depth >= _tokenizer.Count)
+                    {
+                        if (next.Matches.Count > 0)
+                        {
+                            Current = next;
+                            return true;
+                        }
+                        else
+                        {
+                            // We can stop looking as any other child node from this node will be
+                            // either a literal, a constrained parameter or a parameter.
+                            // (Catch alls and constrained catch alls will show up as candidate matches).
+                            continue;
+                        }
+                    }
+
+                    if (next.CatchAlls != null)
+                    {
+                        _stack.Push(next.CatchAlls);
+                    }
+
+                    if (next.ConstrainedCatchAlls != null)
+                    {
+                        _stack.Push(next.ConstrainedCatchAlls);
+                    }
+
+                    if (next.Parameters != null)
+                    {
+                        _stack.Push(next.Parameters);
+                    }
+
+                    if (next.ConstrainedParameters != null)
+                    {
+                        _stack.Push(next.ConstrainedParameters);
+                    }
+
+                    if (next.Literals.Count > 0)
+                    {
+                        Debug.Assert(next.Depth < _tokenizer.Count);
+                        if (next.Literals.TryGetValue(_tokenizer[next.Depth].Value, out var node))
+                        {
+                            _stack.Push(node);
+                        }
+                    }
+                }
+
+                return false;
+            }
+
+            public void Reset()
+            {
+                _stack.Clear();
+                Current = null;
+            }
+        }
+
+        protected override void InitializeServices(IServiceProvider services)
+        {
+            _constraintFactory = services.GetRequiredService<IConstraintFactory>();
+        }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcherFactory.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcherFactory.cs
similarity index 90%
rename from src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcherFactory.cs
rename to src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcherFactory.cs
index 694ebe6b67f..badcf48078e 100644
--- a/src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcherFactory.cs
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/TreeMatcherFactory.cs
@@ -3,9 +3,8 @@
 
 using System;
 using System.Collections.Generic;
-using Microsoft.AspNetCore.Dispatcher;
 
-namespace Microsoft.AspNetCore.Routing.Dispatcher
+namespace Microsoft.AspNetCore.Dispatcher
 {
     public class TreeMatcherFactory : IDefaultMatcherFactory
     {
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingNode.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingNode.cs
new file mode 100644
index 00000000000..84150fde776
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingNode.cs
@@ -0,0 +1,81 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// A node in a <see cref="UrlMatchingTree"/>.
+    /// </summary>
+    [DebuggerDisplay("{DebuggerToString(),nq}")]
+    public class UrlMatchingNode
+    {
+        /// <summary>
+        /// Initializes a new instance of <see cref="UrlMatchingNode"/>.
+        /// </summary>
+        /// <param name="depth">The length of the path to this node in the <see cref="UrlMatchingTree"/>.</param>
+        public UrlMatchingNode(int depth)
+        {
+            Depth = depth;
+
+            Matches = new List<InboundMatch>();
+            Literals = new Dictionary<string, UrlMatchingNode>(StringComparer.OrdinalIgnoreCase);
+        }
+
+        /// <summary>
+        /// Gets the length of the path to this node in the <see cref="UrlMatchingTree"/>.
+        /// </summary>
+        public int Depth { get; }
+
+        /// <summary>
+        /// Gets or sets a value indicating whether this node represents a catch all segment.
+        /// </summary>
+        public bool IsCatchAll { get; set; }
+
+        /// <summary>
+        /// Gets the list of matching route entries associated with this node.
+        /// </summary>
+        /// <remarks>
+        /// These entries are sorted by precedence then template.
+        /// </remarks>
+        public List<InboundMatch> Matches { get; }
+
+        /// <summary>
+        /// Gets the literal segments following this segment.
+        /// </summary>
+        public Dictionary<string, UrlMatchingNode> Literals { get; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="UrlMatchingNode"/> representing
+        /// parameter segments with constraints following this segment in the <see cref="TreeMatcher"/>.
+        /// </summary>
+        public UrlMatchingNode ConstrainedParameters { get; set; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="UrlMatchingNode"/> representing
+        /// parameter segments following this segment in the <see cref="TreeMatcher"/>.
+        /// </summary>
+        public UrlMatchingNode Parameters { get; set; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="UrlMatchingNode"/> representing
+        /// catch all parameter segments with constraints following this segment in the <see cref="TreeMatcher"/>.
+        /// </summary>
+        public UrlMatchingNode ConstrainedCatchAlls { get; set; }
+
+        /// <summary>
+        /// Gets or sets the <see cref="UrlMatchingNode"/> representing
+        /// catch all parameter segments following this segment in the <see cref="TreeMatcher"/>.
+        /// </summary>
+        public UrlMatchingNode CatchAlls { get; set; }
+
+        private string DebuggerToString()
+        {
+            return $"Length: {Depth}, Matches: {string.Join(" | ", Matches?.Select(m => $"({m.RoutePatternMatcher.RoutePattern.RawText})"))}";
+        }
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingTree.cs b/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingTree.cs
new file mode 100644
index 00000000000..5685b2aa719
--- /dev/null
+++ b/src/Microsoft.AspNetCore.Dispatcher/Tree/UrlMatchingTree.cs
@@ -0,0 +1,30 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    /// <summary>
+    /// A tree part of a <see cref="TreeMatcher"/>.
+    /// </summary>
+    public class UrlMatchingTree
+    {
+        /// <summary>
+        /// Initializes a new instance of <see cref="UrlMatchingTree"/>.
+        /// </summary>
+        /// <param name="order">The order associated with endpoints in this <see cref="UrlMatchingTree"/>.</param>
+        public UrlMatchingTree(int order)
+        {
+            Order = order;
+        }
+
+        /// <summary>
+        /// Gets the order of the endpoints associated with this <see cref="UrlMatchingTree"/>.
+        /// </summary>
+        public int Order { get; }
+
+        /// <summary>
+        /// Gets the root of the <see cref="UrlMatchingTree"/>.
+        /// </summary>
+        public UrlMatchingNode Root { get; } = new UrlMatchingNode(depth: 0);
+    }
+}
diff --git a/src/Microsoft.AspNetCore.Routing/DependencyInjection/RoutingServiceCollectionExtensions.cs b/src/Microsoft.AspNetCore.Routing/DependencyInjection/RoutingServiceCollectionExtensions.cs
index 710ceba83c6..5c757965ad0 100644
--- a/src/Microsoft.AspNetCore.Routing/DependencyInjection/RoutingServiceCollectionExtensions.cs
+++ b/src/Microsoft.AspNetCore.Routing/DependencyInjection/RoutingServiceCollectionExtensions.cs
@@ -5,11 +5,9 @@ using System;
 using System.Text.Encodings.Web;
 using Microsoft.AspNetCore.Dispatcher;
 using Microsoft.AspNetCore.Routing;
-using Microsoft.AspNetCore.Routing.Dispatcher;
 using Microsoft.AspNetCore.Routing.Internal;
 using Microsoft.AspNetCore.Routing.Tree;
 using Microsoft.Extensions.DependencyInjection.Extensions;
-using Microsoft.Extensions.ObjectPool;
 
 namespace Microsoft.Extensions.DependencyInjection
 {
diff --git a/src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcher.cs b/src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcher.cs
deleted file mode 100644
index 443aff97d37..00000000000
--- a/src/Microsoft.AspNetCore.Routing/Dispatcher/TreeMatcher.cs
+++ /dev/null
@@ -1,331 +0,0 @@
-// Copyright (c) .NET Foundation. All rights reserved.
-// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
-
-using System;
-using System.Collections;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Threading;
-using System.Threading.Tasks;
-using Microsoft.AspNetCore.Dispatcher;
-using Microsoft.AspNetCore.Dispatcher.Internal;
-using Microsoft.AspNetCore.Http;
-using Microsoft.AspNetCore.Routing.Logging;
-using Microsoft.AspNetCore.Routing.Template;
-using Microsoft.AspNetCore.Routing.Tree;
-using Microsoft.Extensions.Internal;
-
-namespace Microsoft.AspNetCore.Routing.Dispatcher
-{
-    public class TreeMatcher : MatcherBase
-    {
-        private bool _dataInitialized;
-        private object _lock;
-        private Cache _cache;
-
-        private readonly Func<Cache> _initializer;
-
-        public TreeMatcher()
-        {
-            _lock = new object();
-            _initializer = CreateCache;
-        }
-
-        public override async Task MatchAsync(MatcherContext context)
-        {
-            if (context == null)
-            {
-                throw new ArgumentNullException(nameof(context));
-            }
-
-            EnsureServicesInitialized(context);
-
-            var cache = LazyInitializer.EnsureInitialized(ref _cache, ref _dataInitialized, ref _lock, _initializer);
-
-            var values = new RouteValueDictionary();
-            context.Values = values;
-
-            for (var i = 0; i < cache.Trees.Length; i++)
-            {
-                var tree = cache.Trees[i];
-                var tokenizer = new PathTokenizer(context.HttpContext.Request.Path);
-
-                var treenumerator = new Treenumerator(tree.Root, tokenizer);
-
-                while (treenumerator.MoveNext())
-                {
-                    var node = treenumerator.Current;
-                    foreach (var item in node.Matches)
-                    {
-                        var entry = item.Entry;
-                        var matcher = item.TemplateMatcher;
-
-                        values.Clear();
-                        if (!matcher.TryMatch(context.HttpContext.Request.Path, values))
-                        {
-                            continue;
-                        }
-
-                        Logger.MatchedRoute(entry.RouteName, entry.RouteTemplate.TemplateText);
-
-                        if (!MatchConstraints(context.HttpContext, values, entry.Constraints))
-                        {
-                            continue;
-                        }
-
-                        await SelectEndpointAsync(context, (Endpoint[])entry.Tag);
-                        if (context.ShortCircuit != null)
-                        {
-                            Logger.RequestShortCircuited(context);
-                            return;
-                        }
-
-                        if (context.Endpoint != null)
-                        {
-                            if (context.Endpoint is IRoutePatternEndpoint templateEndpoint)
-                            {
-                                foreach (var kvp in templateEndpoint.Values)
-                                {
-                                    context.Values[kvp.Key] = kvp.Value;
-                                }
-                            }
-
-                            return;
-                        }
-                    }
-                }
-            }
-        }
-
-        private bool MatchConstraints(HttpContext httpContext, RouteValueDictionary values, IDictionary<string, IRouteConstraint> constraints)
-        {
-            if (constraints != null)
-            {
-                foreach (var kvp in constraints)
-                {
-                    var constraint = kvp.Value;
-                    if (!constraint.Match(httpContext, null, kvp.Key, values, RouteDirection.IncomingRequest))
-                    {
-                        object value;
-                        values.TryGetValue(kvp.Key, out value);
-
-                        Logger.RouteValueDoesNotMatchConstraint(value, kvp.Key, kvp.Value);
-                        return false;
-                    }
-                }
-            }
-
-            return true;
-        }
-
-        private Cache CreateCache()
-        {
-            var endpoints = GetEndpoints();
-
-            var groups = new Dictionary<Key, List<Endpoint>>();
-
-            for (var i = 0; i < endpoints.Count; i++)
-            {
-                var endpoint = endpoints[i];
-
-                var templateEndpoint = endpoint as IRoutePatternEndpoint;
-                if (templateEndpoint == null)
-                {
-                    continue;
-                }
-
-                if (!groups.TryGetValue(new Key(0, templateEndpoint.Pattern), out var group))
-                {
-                    group = new List<Endpoint>();
-                    groups.Add(new Key(0, templateEndpoint.Pattern), group);
-                }
-
-                group.Add(endpoint);
-            }
-
-            var entries = new List<InboundRouteEntry>();
-            foreach (var group in groups)
-            {
-                var template = Template.TemplateParser.Parse(group.Key.RouteTemplate);
-
-                var defaults = new RouteValueDictionary();
-                for (var i = 0; i < template.Parameters.Count; i++)
-                {
-                    var parameter = template.Parameters[i];
-                    if (parameter.DefaultValue != null)
-                    {
-                        defaults.Add(parameter.Name, parameter.DefaultValue);
-                    }
-                }
-
-                entries.Add(new InboundRouteEntry()
-                {
-                    Defaults = defaults,
-                    Order = group.Key.Order,
-                    Precedence = RoutePrecedence.ComputeInbound(template),
-                    RouteTemplate = template,
-                    Tag = group.Value.ToArray(),
-                });
-            }
-
-            var trees = new List<UrlMatchingTree>();
-            for (var i = 0; i < entries.Count; i++)
-            {
-                var entry = entries[i];
-
-                while (trees.Count <= entry.Order)
-                {
-                    trees.Add(new UrlMatchingTree(trees.Count));
-                }
-
-                var tree = trees[entry.Order];
-
-                TreeRouteBuilder.AddEntryToTree(tree, entry);
-            }
-
-            return new Cache(trees.ToArray());
-        }
-
-        private struct Key : IEquatable<Key>
-        {
-            public readonly int Order;
-            public readonly string RouteTemplate;
-
-            public Key(int order, string routeTemplate)
-            {
-                Order = order;
-                RouteTemplate = routeTemplate;
-            }
-
-            public bool Equals(Key other)
-            {
-                return Order == other.Order && string.Equals(RouteTemplate, other.RouteTemplate, StringComparison.OrdinalIgnoreCase);
-            }
-
-            public override bool Equals(object obj)
-            {
-                return obj is Key ? Equals((Key)obj) : false;
-            }
-
-            public override int GetHashCode()
-            {
-                var hash = new HashCodeCombiner();
-                hash.Add(Order);
-                hash.Add(RouteTemplate, StringComparer.OrdinalIgnoreCase);
-                return hash;
-            }
-        }
-
-        private class Cache
-        {
-            public readonly UrlMatchingTree[] Trees;
-
-            public Cache(UrlMatchingTree[] trees)
-            {
-                Trees = trees;
-            }
-        }
-
-        private struct Treenumerator : IEnumerator<UrlMatchingNode>
-        {
-            private readonly Stack<UrlMatchingNode> _stack;
-            private readonly PathTokenizer _tokenizer;
-
-            public Treenumerator(UrlMatchingNode root, PathTokenizer tokenizer)
-            {
-                _stack = new Stack<UrlMatchingNode>();
-                _tokenizer = tokenizer;
-                Current = null;
-
-                _stack.Push(root);
-            }
-
-            public UrlMatchingNode Current { get; private set; }
-
-            object IEnumerator.Current => Current;
-
-            public void Dispose()
-            {
-            }
-
-            public bool MoveNext()
-            {
-                if (_stack == null)
-                {
-                    return false;
-                }
-
-                while (_stack.Count > 0)
-                {
-                    var next = _stack.Pop();
-
-                    // In case of wild card segment, the request path segment length can be greater
-                    // Example:
-                    // Template:    a/{*path}
-                    // Request Url: a/b/c/d
-                    if (next.IsCatchAll && next.Matches.Count > 0)
-                    {
-                        Current = next;
-                        return true;
-                    }
-                    // Next template has the same length as the url we are trying to match
-                    // The only possible matching segments are either our current matches or
-                    // any catch-all segment after this segment in which the catch all is empty.
-                    else if (next.Depth == _tokenizer.Count)
-                    {
-                        if (next.Matches.Count > 0)
-                        {
-                            Current = next;
-                            return true;
-                        }
-                        else
-                        {
-                            // We can stop looking as any other child node from this node will be
-                            // either a literal, a constrained parameter or a parameter.
-                            // (Catch alls and constrained catch alls will show up as candidate matches).
-                            continue;
-                        }
-                    }
-
-                    if (next.CatchAlls != null)
-                    {
-                        _stack.Push(next.CatchAlls);
-                    }
-
-                    if (next.ConstrainedCatchAlls != null)
-                    {
-                        _stack.Push(next.ConstrainedCatchAlls);
-                    }
-
-                    if (next.Parameters != null)
-                    {
-                        _stack.Push(next.Parameters);
-                    }
-
-                    if (next.ConstrainedParameters != null)
-                    {
-                        _stack.Push(next.ConstrainedParameters);
-                    }
-
-                    if (next.Literals.Count > 0)
-                    {
-                        UrlMatchingNode node;
-                        Debug.Assert(next.Depth < _tokenizer.Count);
-                        if (next.Literals.TryGetValue(_tokenizer[next.Depth].Value, out node))
-                        {
-                            _stack.Push(node);
-                        }
-                    }
-                }
-
-                return false;
-            }
-
-            public void Reset()
-            {
-                _stack.Clear();
-                Current = null;
-            }
-        }
-    }
-}
diff --git a/src/Microsoft.AspNetCore.Routing/Tree/TreeRouteBuilder.cs b/src/Microsoft.AspNetCore.Routing/Tree/TreeRouteBuilder.cs
index f44aebf160d..9b3c58df6b9 100644
--- a/src/Microsoft.AspNetCore.Routing/Tree/TreeRouteBuilder.cs
+++ b/src/Microsoft.AspNetCore.Routing/Tree/TreeRouteBuilder.cs
@@ -5,11 +5,9 @@ using System;
 using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
-using System.Text.Encodings.Web;
 using Microsoft.AspNetCore.Dispatcher;
 using Microsoft.AspNetCore.Routing.Template;
 using Microsoft.Extensions.Logging;
-using Microsoft.Extensions.ObjectPool;
 
 namespace Microsoft.AspNetCore.Routing.Tree
 {
@@ -78,7 +76,7 @@ namespace Microsoft.AspNetCore.Routing.Tree
             {
                 Handler = handler,
                 Order = order,
-                Precedence = RoutePrecedence.ComputeInbound(routeTemplate),
+                Precedence = Template.RoutePrecedence.ComputeInbound(routeTemplate),
                 RouteName = routeName,
                 RouteTemplate = routeTemplate,
             };
@@ -150,7 +148,7 @@ namespace Microsoft.AspNetCore.Routing.Tree
             {
                 Handler = handler,
                 Order = order,
-                Precedence = RoutePrecedence.ComputeOutbound(routeTemplate),
+                Precedence = Template.RoutePrecedence.ComputeOutbound(routeTemplate),
                 RequiredLinkValues = requiredLinkValues,
                 RouteName = routeName,
                 RouteTemplate = routeTemplate,
diff --git a/test/Microsoft.AspNetCore.Dispatcher.FunctionalTest/ApiAppStartup.cs b/test/Microsoft.AspNetCore.Dispatcher.FunctionalTest/ApiAppStartup.cs
index 9a193cc0154..d5d195c4362 100644
--- a/test/Microsoft.AspNetCore.Dispatcher.FunctionalTest/ApiAppStartup.cs
+++ b/test/Microsoft.AspNetCore.Dispatcher.FunctionalTest/ApiAppStartup.cs
@@ -1,11 +1,9 @@
 // Copyright (c) .NET Foundation. All rights reserved.
 // Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
 
-using System.Linq;
 using System.Threading.Tasks;
 using Microsoft.AspNetCore.Builder;
 using Microsoft.AspNetCore.Http;
-using Microsoft.AspNetCore.Routing.Dispatcher;
 using Microsoft.Extensions.DependencyInjection;
 using Microsoft.Extensions.Logging;
 
diff --git a/test/Microsoft.AspNetCore.Dispatcher.Test/RoutePatternMatcherTest.cs b/test/Microsoft.AspNetCore.Dispatcher.Test/Patterns/RoutePatternMatcherTest.cs
similarity index 100%
rename from test/Microsoft.AspNetCore.Dispatcher.Test/RoutePatternMatcherTest.cs
rename to test/Microsoft.AspNetCore.Dispatcher.Test/Patterns/RoutePatternMatcherTest.cs
diff --git a/test/Microsoft.AspNetCore.Dispatcher.Test/Tree/TreeMatcherTest.cs b/test/Microsoft.AspNetCore.Dispatcher.Test/Tree/TreeMatcherTest.cs
new file mode 100644
index 00000000000..a4d2ad88c57
--- /dev/null
+++ b/test/Microsoft.AspNetCore.Dispatcher.Test/Tree/TreeMatcherTest.cs
@@ -0,0 +1,808 @@
+// Copyright (c) .NET Foundation. All rights reserved.
+// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
+
+using System.Collections.Generic;
+using System.Threading.Tasks;
+using Microsoft.AspNetCore.Http;
+using Microsoft.Extensions.Logging;
+using Microsoft.Extensions.Logging.Abstractions;
+using Microsoft.Extensions.Options;
+using Moq;
+using Xunit;
+
+namespace Microsoft.AspNetCore.Dispatcher
+{
+    public class TreeMatcherTest
+    {
+        [Theory]
+        [InlineData("template/5", "template/{parameter:int}")]
+        [InlineData("template/5", "template/{parameter}")]
+        [InlineData("template/5", "template/{*parameter:int}")]
+        [InlineData("template/5", "template/{*parameter}")]
+        [InlineData("template/{parameter}", "template/{parameter:alpha}")] // constraint doesn't match
+        [InlineData("template/{parameter:int}", "template/{parameter}")]
+        [InlineData("template/{parameter:int}", "template/{*parameter:int}")]
+        [InlineData("template/{parameter:int}", "template/{*parameter}")]
+        [InlineData("template/{parameter}", "template/{*parameter:int}")]
+        [InlineData("template/{parameter}", "template/{*parameter}")]
+        [InlineData("template/5", "template/5/{*parameter}")]
+        [InlineData("template/{*parameter:int}", "template/{*parameter}")]
+        public async Task MatchAsync_RespectsPrecedence(
+            string firstTemplate,
+            string secondTemplate)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(firstTemplate, new { }, Test_Delegate, "Test1"),
+                    new RoutePatternEndpoint(secondTemplate, new { }, Test_Delegate, "Test2"),
+                },
+            };
+
+            var context = CreateMatcherContext("/template/5");
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("template/5", "template/{parameter:int}")]
+        [InlineData("template/5", "template/{parameter}")]
+        [InlineData("template/5", "template/{*parameter:int}")]
+        [InlineData("template/5", "template/{*parameter}")]
+        [InlineData("template/{parameter:int}", "template/{parameter}")]
+        [InlineData("template/{parameter:int}", "template/{*parameter:int}")]
+        [InlineData("template/{parameter:int}", "template/{*parameter}")]
+        [InlineData("template/{parameter}", "template/{*parameter:int}")]
+        [InlineData("template/{parameter}", "template/{*parameter}")]
+        [InlineData("template/5", "template/5/{*parameter}")]
+        [InlineData("template/{*parameter:int}", "template/{*parameter}")]
+        public async Task MatchAsync_RespectsOrderOverPrecedence(
+            string firstTemplate,
+            string secondTemplate)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(firstTemplate, new { }, Test_Delegate, "Test1", new EndpointOrderMetadata(1)),
+                    new RoutePatternEndpoint(secondTemplate, new { }, Test_Delegate, "Test2", new EndpointOrderMetadata(0)),
+                },
+            };
+
+            var context = CreateMatcherContext("/template/5");
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[1], context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("template/{first:int}", "template/{second:int}")]
+        [InlineData("template/{first}", "template/{second}")]
+        [InlineData("template/{*first:int}", "template/{*second:int}")]
+        [InlineData("template/{*first}", "template/{*second}")]
+        public async Task MatchAsync_EnsuresStableOrdering(string firstTemplate, string secondTemplate)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(firstTemplate, new { }, Test_Delegate, "Test1"),
+                    new RoutePatternEndpoint(secondTemplate, new { }, Test_Delegate, "Test2"),
+                },
+            };
+
+            var context = CreateMatcherContext("/template/5");
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("/", 0)]
+        [InlineData("/Literal1", 1)]
+        [InlineData("/Literal1/Literal2", 2)]
+        [InlineData("/Literal1/Literal2/Literal3", 3)]
+        [InlineData("/Literal1/Literal2/Literal3/4", 4)]
+        [InlineData("/Literal1/Literal2/Literal3/Literal4", 5)]
+        [InlineData("/1", 6)]
+        [InlineData("/1/2", 7)]
+        [InlineData("/1/2/3", 8)]
+        [InlineData("/1/2/3/4", 9)]
+        [InlineData("/1/2/3/CatchAll4", 10)]
+        [InlineData("/parameter1", 11)]
+        [InlineData("/parameter1/parameter2", 12)]
+        [InlineData("/parameter1/parameter2/parameter3", 13)]
+        [InlineData("/parameter1/parameter2/parameter3/4", 14)]
+        [InlineData("/parameter1/parameter2/parameter3/CatchAll4", 15)]
+        public async Task MatchAsync_MatchesEndpointWithTheRightLength(string url, int index)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("", Test_Delegate),
+                    new RoutePatternEndpoint("Literal1", Test_Delegate),
+                    new RoutePatternEndpoint("Literal1/Literal2", Test_Delegate),
+                    new RoutePatternEndpoint("Literal1/Literal2/Literal3", Test_Delegate),
+                    new RoutePatternEndpoint("Literal1/Literal2/Literal3/{*constrainedCatchAll:int}", Test_Delegate),
+                    new RoutePatternEndpoint("Literal1/Literal2/Literal3/{*catchAll}", Test_Delegate),
+                    new RoutePatternEndpoint("{constrained1:int}", Test_Delegate),
+                    new RoutePatternEndpoint("{constrained1:int}/{constrained2:int}", Test_Delegate),
+                    new RoutePatternEndpoint("{constrained1:int}/{constrained2:int}/{constrained3:int}", Test_Delegate),
+                    new RoutePatternEndpoint("{constrained1:int}/{constrained2:int}/{constrained3:int}/{*constrainedCatchAll:int}", Test_Delegate),
+                    new RoutePatternEndpoint("{constrained1:int}/{constrained2:int}/{constrained3:int}/{*catchAll}", Test_Delegate),
+                    new RoutePatternEndpoint("{parameter1}", Test_Delegate),
+                    new RoutePatternEndpoint("{parameter1}/{parameter2}", Test_Delegate),
+                    new RoutePatternEndpoint("{parameter1}/{parameter2}/{parameter3}", Test_Delegate),
+                    new RoutePatternEndpoint("{parameter1}/{parameter2}/{parameter3}/{*constrainedCatchAll:int}", Test_Delegate),
+                    new RoutePatternEndpoint("{parameter1}/{parameter2}/{parameter3}/{*catchAll}", Test_Delegate),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[index], context.Endpoint);
+        }
+
+        public static TheoryData<string, object[]> MatchesEndpointsWithDefaultsData =>
+            new TheoryData<string, object[]>
+            {
+                { "/", new object[] { "1", "2", "3", "4" } },
+                { "/a", new object[] { "a", "2", "3", "4" } },
+                { "/a/b", new object[] { "a", "b", "3", "4" } },
+                { "/a/b/c", new object[] { "a", "b", "c", "4" } },
+                { "/a/b/c/d", new object[] { "a", "b", "c", "d" } }
+            };
+
+        [Theory]
+        [MemberData(nameof(MatchesEndpointsWithDefaultsData))]
+        public async Task MatchAsync_MatchesEndpointsWithDefaults(string url, object[] values)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{parameter1=1}/{parameter2=2}/{parameter3=3}/{parameter4=4}",
+                    new { parameter1 = 1, parameter2 = 2, parameter3 = 3, parameter4 = 4 }, Test_Delegate, "Test"),
+                },
+            };
+
+            var valueKeys = new[] { "parameter1", "parameter2", "parameter3", "parameter4" };
+            var expectedValues = new DispatcherValueCollection();
+            for (int i = 0; i < valueKeys.Length; i++)
+            {
+                expectedValues.Add(valueKeys[i], values[i]);
+            }
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            foreach (var entry in expectedValues)
+            {
+                var data = Assert.Single(context.Values, v => v.Key == entry.Key);
+                Assert.Equal(entry.Value, data.Value);
+            }
+        }
+
+        public static TheoryData<string, object[]> MatchesConstrainedEndpointsWithDefaultsData =>
+            new TheoryData<string, object[]>
+            {
+                { "/", new object[] { "1", "2", "3", "4" } },
+                { "/10", new object[] { "10", "2", "3", "4" } },
+                { "/10/11", new object[] { "10", "11", "3", "4" } },
+                { "/10/11/12", new object[] { "10", "11", "12", "4" } },
+                { "/10/11/12/13", new object[] { "10", "11", "12", "13" } }
+            };
+
+        [Theory]
+        [MemberData(nameof(MatchesConstrainedEndpointsWithDefaultsData))]
+        public async Task MatchAsync_MatchesConstrainedEndpointsWithDefaults(string url, object[] values)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{parameter1:int=1}/{parameter2:int=2}/{parameter3:int=3}/{parameter4:int=4}",
+                    new { parameter1 = 1, parameter2 = 2, parameter3 = 3, parameter4 = 4 }, Test_Delegate, "Test"),
+                },
+            };
+
+            var valueKeys = new[] { "parameter1", "parameter2", "parameter3", "parameter4" };
+            var expectedValues = new DispatcherValueCollection();
+            for (int i = 0; i < valueKeys.Length; i++)
+            {
+                expectedValues.Add(valueKeys[i], values[i]);
+            }
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            foreach (var entry in expectedValues)
+            {
+                var data = Assert.Single(context.Values, v => v.Key == entry.Key);
+                Assert.Equal(entry.Value, data.Value);
+            }
+        }
+
+        [Fact]
+        public async Task MatchAsync_MatchesCatchAllEndpointsWithDefaults()
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{parameter1=1}/{parameter2=2}/{parameter3=3}/{*parameter4=4}",
+                    new { parameter1 = 1, parameter2 = 2, parameter3 = 3, parameter4 = 4 }, Test_Delegate, "Test"),
+                },
+            };
+
+            var url = "/a/b/c";
+            var values = new[] { "a", "b", "c", "4" };
+
+            var valueKeys = new[] { "parameter1", "parameter2", "parameter3", "parameter4" };
+            var expectedValues = new DispatcherValueCollection();
+            for (int i = 0; i < valueKeys.Length; i++)
+            {
+                expectedValues.Add(valueKeys[i], values[i]);
+            }
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            foreach (var entry in expectedValues)
+            {
+                var data = Assert.Single(context.Values, v => v.Key == entry.Key);
+                Assert.Equal(entry.Value, data.Value);
+            }
+        }
+
+        [Fact]
+        public async Task MatchAsync_DoesNotMatchEndpointsWithIntermediateDefaultValues()
+        {
+            // Arrange
+            var url = "/a/b";
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("a/b/{parameter3=3}/d",
+                    new { parameter3 = 3}, Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a")]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a/b")]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a/b/c")]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a/b/c/d")]
+        public async Task MatchAsync_DoesNotMatchEndpointsWithMultipleIntermediateDefaultOrOptionalValues(string template, string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new { b = 3}, Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a/b/c/d/e")]
+        [InlineData("a/{b=3}/c/{d?}/e/{*f}", "/a/b/c/d/e/f")]
+        public async Task MatchAsync_MatchRoutesWithMultipleIntermediateDefaultOrOptionalValues_WhenAllIntermediateValuesAreProvided(string template, string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new { b = 3}, Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.NotNull(context.Endpoint);
+        }
+
+        [Fact]
+        public void MatchAsync_DoesNotMatchShorterUrl()
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("Literal1/Literal2/Literal3",
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var routes = new[] {
+                "Literal1/Literal2/Literal3",
+            };
+
+            var context = CreateMatcherContext("/Literal1");
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("///")]
+        [InlineData("/a//")]
+        [InlineData("/a/b//")]
+        [InlineData("//b//")]
+        [InlineData("///c")]
+        [InlineData("///c/")]
+        public async Task MatchAsync_MultipleOptionalParameters_WithEmptyIntermediateSegmentsDoesNotMatch(string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{controller?}/{action?}/{id?}",
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("")]
+        [InlineData("/")]
+        [InlineData("/a")]
+        [InlineData("/a/")]
+        [InlineData("/a/b")]
+        [InlineData("/a/b/")]
+        [InlineData("/a/b/c")]
+        [InlineData("/a/b/c/")]
+        public async Task MatchAsync_MultipleOptionalParameters_WithIncrementalOptionalValues(string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{controller?}/{action?}/{id?}", new {}, Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.NotNull(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("///")]
+        [InlineData("////")]
+        [InlineData("/a//")]
+        [InlineData("/a///")]
+        [InlineData("//b/")]
+        [InlineData("//b//")]
+        [InlineData("///c")]
+        [InlineData("///c/")]
+        public async Task MatchAsync_MultipleParameters_WithEmptyValuesDoesNotMatch(string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{controller?}/{action?}/{id?}",
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("/a/b/c//")]
+        [InlineData("/a/b/c/////")]
+        public async Task MatchAsync_CatchAllParameters_WithEmptyValuesAtTheEnd(string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{controller}/{action}/{*id}",
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("/a/b//")]
+        [InlineData("/a/b///c")]
+        public async Task MatchAsync_CatchAllParameters_WithEmptyValues(string url)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint("{controller}/{action}/{*id}",
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(url);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        [Theory]
+        [InlineData("{*path}", "/a", "a")]
+        [InlineData("{*path}", "/a/b/c", "a/b/c")]
+        [InlineData("a/{*path}", "/a/b", "b")]
+        [InlineData("a/{*path}", "/a/b/c/d", "b/c/d")]
+        [InlineData("a/{*path:regex(10/20/30)}", "/a/10/20/30", "10/20/30")]
+        public async Task MatchAsync_MatchesWildCard_ForLargerPathSegments(
+            string template,
+            string requestPath,
+            string expectedResult)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(requestPath);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+            Assert.Equal(expectedResult, context.Values["path"]);
+        }
+
+        [Theory]
+        [InlineData("a/{*path}", "/a")]
+        [InlineData("a/{*path}", "/a/")]
+        public async Task MatchAsync_MatchesCatchAll_NullValue(
+            string template,
+            string requestPath)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var context = CreateMatcherContext(requestPath);
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+            Assert.Null(context.Values["path"]);
+        }
+
+        [Theory]
+        [InlineData("a/{*path=default}", "/a")]
+        [InlineData("a/{*path=default}", "/a/")]
+        public async Task MatchAsync_MatchesCatchAll_UsesDefaultValue(
+            string template,
+            string requestPath)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+
+            var context = CreateMatcherContext(requestPath);
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Same(dataSource.Endpoints[0], context.Endpoint);
+            Assert.Equal("default", context.Values["path"]);
+        }
+
+        [Theory]
+        [InlineData("template/{parameter:int}", "/template/5", true)]
+        [InlineData("template/{parameter:int?}", "/template/5", true)]
+        [InlineData("template/{parameter:int?}", "/template", true)]
+        [InlineData("template/{parameter:int?}", "/template/qwer", false)]
+        public async Task MatchAsync_WithOptionalConstraint(
+            string template,
+            string request,
+            bool expectedResult)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+            var context = CreateMatcherContext(request);
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            if (expectedResult)
+            {
+                Assert.NotNull(context.Endpoint);
+            }
+            else
+            {
+                Assert.Null(context.Endpoint);
+            }
+        }
+
+        [Theory]
+        [InlineData("moo/{p1}.{p2?}", "/moo/foo.bar", "foo", "bar", null)]
+        [InlineData("moo/{p1?}", "/moo/foo", "foo", null, null)]
+        [InlineData("moo/{p1?}", "/moo", null, null, null)]
+        [InlineData("moo/{p1}.{p2?}", "/moo/foo", "foo", null, null)]
+        [InlineData("moo/{p1}.{p2?}", "/moo/foo..bar", "foo.", "bar", null)]
+        [InlineData("moo/{p1}.{p2?}", "/moo/foo.moo.bar", "foo.moo", "bar", null)]
+        [InlineData("moo/{p1}.{p2}", "/moo/foo.bar", "foo", "bar", null)]
+        [InlineData("moo/foo.{p1}.{p2?}", "/moo/foo.moo.bar", "moo", "bar", null)]
+        [InlineData("moo/foo.{p1}.{p2?}", "/moo/foo.moo", "moo", null, null)]
+        [InlineData("moo/.{p2?}", "/moo/.foo", null, "foo", null)]
+        [InlineData("moo/{p1}.{p2?}", "/moo/....", "..", ".", null)]
+        [InlineData("moo/{p1}.{p2?}", "/moo/.bar", ".bar", null, null)]
+        [InlineData("moo/{p1}.{p2}.{p3?}", "/moo/foo.moo.bar", "foo", "moo", "bar")]
+        [InlineData("moo/{p1}.{p2}.{p3?}", "/moo/foo.moo", "foo", "moo", null)]
+        [InlineData("moo/{p1}.{p2}.{p3}.{p4?}", "/moo/foo.moo.bar", "foo", "moo", "bar")]
+        [InlineData("{p1}.{p2?}/{p3}", "/foo.moo/bar", "foo", "moo", "bar")]
+        [InlineData("{p1}.{p2?}/{p3}", "/foo/bar", "foo", null, "bar")]
+        [InlineData("{p1}.{p2?}/{p3}", "/.foo/bar", ".foo", null, "bar")]
+        public async Task MatchAsync_WithOptionalCompositeParameter_Valid(
+            string template,
+            string request,
+            string p1,
+            string p2,
+            string p3)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+            var context = CreateMatcherContext(request);
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.NotNull(context.Endpoint);
+            if (p1 != null)
+            {
+                Assert.Equal(p1, context.Values["p1"]);
+            }
+            if (p2 != null)
+            {
+                Assert.Equal(p2, context.Values["p2"]);
+            }
+            if (p3 != null)
+            {
+                Assert.Equal(p3, context.Values["p3"]);
+            }
+        }
+
+        [Theory]
+        [InlineData("moo/{p1}.{p2?}", "/moo/foo.")]
+        [InlineData("moo/{p1}.{p2?}", "/moo/.")]
+        [InlineData("moo/{p1}.{p2}", "/foo.")]
+        [InlineData("moo/{p1}.{p2}", "/foo")]
+        [InlineData("moo/{p1}.{p2}.{p3?}", "/moo/foo.moo.")]
+        [InlineData("moo/foo.{p2}.{p3?}", "/moo/bar.foo.moo")]
+        [InlineData("moo/foo.{p2}.{p3?}", "/moo/kungfoo.moo.bar")]
+        [InlineData("moo/foo.{p2}.{p3?}", "/moo/kungfoo.moo")]
+        [InlineData("moo/{p1}.{p2}.{p3?}", "/moo/foo")]
+        [InlineData("{p1}.{p2?}/{p3}", "/foo./bar")]
+        [InlineData("moo/.{p2?}", "/moo/.")]
+        [InlineData("{p1}.{p2}/{p3}", "/.foo/bar")]
+        public async Task MatchAsync_WithOptionalCompositeParameter_Invalid(
+            string template,
+            string request)
+        {
+            // Arrange
+            var dataSource = new DefaultDispatcherDataSource()
+            {
+                Endpoints =
+                {
+                    new RoutePatternEndpoint(template,
+                    new object(), Test_Delegate, "Test"),
+                },
+            };
+
+            var factory = new TreeMatcherFactory();
+            var matcher = factory.CreateMatcher(dataSource, new List<EndpointSelector>());
+            var context = CreateMatcherContext(request);
+
+            // Act
+            await matcher.MatchAsync(context);
+
+            // Assert
+            Assert.Null(context.Endpoint);
+        }
+
+        private static MatcherContext CreateMatcherContext(string requestPath)
+        {
+            var request = new Mock<HttpRequest>(MockBehavior.Strict);
+            request.SetupGet(r => r.Path).Returns(new PathString(requestPath));
+
+            var context = new Mock<HttpContext>(MockBehavior.Strict);
+            context.Setup(m => m.RequestServices.GetService(typeof(ILoggerFactory)))
+                .Returns(NullLoggerFactory.Instance);
+            context.Setup(m => m.RequestServices.GetService(typeof(IConstraintFactory)))
+                .Returns(CreateConstraintFactory);
+            context.SetupGet(c => c.Request).Returns(request.Object);
+
+            return new MatcherContext(context.Object);
+        }
+
+        private static DefaultConstraintFactory CreateConstraintFactory()
+        {
+            var options = new DispatcherOptions();
+            var optionsMock = new Mock<IOptions<DispatcherOptions>>();
+            optionsMock.SetupGet(o => o.Value).Returns(options);
+
+            return new DefaultConstraintFactory(optionsMock.Object);
+        }
+
+        private static Task Test_Delegate(HttpContext httpContext)
+        {
+            return Task.CompletedTask;
+        }
+    }
+}