Asp.net MVC Route class that supports catch-all parameter anywhere in the URL

Question

the more I think about it the more I believe it's possible to write a custom route that would consume these URL definitions:

{var1}/{var2}/{var3}
Const/{var1}/{var2}
Const1/{var1}/Const2/{var2}
{var1}/{var2}/Const

as well as having at most one greedy parameter on any position within any of the upper URLs like

{*var1}/{var2}/{var3}
{var1}/{*var2}/{var3}
{var1}/{var2}/{*var3}

There is one important constraint. Routes with greedy segment can't have any optional parts. All of them are mandatory.

Example

This is an exemplary request

http://localhost/Show/Topic/SubTopic/SubSubTopic/123/This-is-an-example

This is URL route definition

{action}/{*topicTree}/{id}/{title}

Algorithm

Parsing request route inside GetRouteData() should work like this:

1. Split request into segments:
   • Show
   • Topic
   • SubTopic
   • SubSubTopic
   • 123
   • This-is-an-example
2. Process route URL definition starting from the left and assigning single segment values to parameters (or matching request segment values to static route constant segments).
3. When route segment is defined as greedy, reverse parsing and go to the last segment.
4. Parse route segments one by one backwards (assigning them request values) until you get to the greedy catch-all one again.
5. When you reach the greedy one again, join all remaining request segments (in original order) and assign them to the greedy catch-all route parameter.

Questions

As far as I can think of this, it could work. But I would like to know:

1. Has anyone already written this so I don't have to (because there are other aspects to parsing as well that I didn't mention (constraints, defaults etc.)
2. Do you see any flaws in this algorithm, because I'm going to have to write it myself if noone has done it so far.

I haven't thought about GetVirtuaPath() method at all.

Answer 1

Lately I'm asking questions in urgence, so I usually solve problems on my own. Sorry for that, but here's my take on the kind of route I was asking about. Anyone finds any problems with it: let me know.

Route with catch-all segment anywhere in the URL

/// <summary>
/// This route is used for cases where we want greedy route segments anywhere in the route URL definition
/// </summary>
public class GreedyRoute : Route
{
    #region Properties

    public new string Url { get; private set; }

    private LinkedList<GreedyRouteSegment> urlSegments = new LinkedList<GreedyRouteSegment>();

    private bool hasGreedySegment = false;

    public int MinRequiredSegments { get; private set; }

    #endregion

    #region Constructors

    /// <summary>
    /// Initializes a new instance of the <see cref="VivaRoute"/> class, using the specified URL pattern and handler class.
    /// </summary>
    /// <param name="url">The URL pattern for the route.</param>
    /// <param name="routeHandler">The object that processes requests for the route.</param>
    public GreedyRoute(string url, IRouteHandler routeHandler)
        : this(url, null, null, null, routeHandler)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="VivaRoute"/> class, using the specified URL pattern, handler class, and default parameter values.
    /// </summary>
    /// <param name="url">The URL pattern for the route.</param>
    /// <param name="defaults">The values to use if the URL does not contain all the parameters.</param>
    /// <param name="routeHandler">The object that processes requests for the route.</param>
    public GreedyRoute(string url, RouteValueDictionary defaults, IRouteHandler routeHandler)
        : this(url, defaults, null, null, routeHandler)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="VivaRoute"/> class, using the specified URL pattern, handler class, default parameter values, and constraints.
    /// </summary>
    /// <param name="url">The URL pattern for the route.</param>
    /// <param name="defaults">The values to use if the URL does not contain all the parameters.</param>
    /// <param name="constraints">A regular expression that specifies valid values for a URL parameter.</param>
    /// <param name="routeHandler">The object that processes requests for the route.</param>
    public GreedyRoute(string url, RouteValueDictionary defaults, RouteValueDictionary constraints, IRouteHandler routeHandler)
        : this(url, defaults, constraints, null, routeHandler)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="VivaRoute"/> class, using the specified URL pattern, handler class, default parameter values, constraints, and custom values.
    /// </summary>
    /// <param name="url">The URL pattern for the route.</param>
    /// <param name="defaults">The values to use if the URL does not contain all the parameters.</param>
    /// <param name="constraints">A regular expression that specifies valid values for a URL parameter.</param>
    /// <param name="dataTokens">Custom values that are passed to the route handler, but which are not used to determine whether the route matches a specific URL pattern. The route handler might need these values to process the request.</param>
    /// <param name="routeHandler">The object that processes requests for the route.</param>
    public GreedyRoute(string url, RouteValueDictionary defaults, RouteValueDictionary constraints, RouteValueDictionary dataTokens, IRouteHandler routeHandler)
        : base(url.Replace("*", ""), defaults, constraints, dataTokens, routeHandler)
    {
        this.Defaults = defaults ?? new RouteValueDictionary();
        this.Constraints = constraints;
        this.DataTokens = dataTokens;
        this.RouteHandler = routeHandler;
        this.Url = url;
        this.MinRequiredSegments = 0;

        // URL must be defined
        if (string.IsNullOrEmpty(url))
        {
            throw new ArgumentException("Route URL must be defined.", "url");
        }

        // correct URL definition can have AT MOST ONE greedy segment
        if (url.Split('*').Length > 2)
        {
            throw new ArgumentException("Route URL can have at most one greedy segment, but not more.", "url");
        }

        Regex rx = new Regex(@"^(?<isToken>{)?(?(isToken)(?<isGreedy>\*?))(?<name>[a-zA-Z0-9-_]+)(?(isToken)})$", RegexOptions.Compiled | RegexOptions.Singleline);
        foreach (string segment in url.Split('/'))
        {
            // segment must not be empty
            if (string.IsNullOrEmpty(segment))
            {
                throw new ArgumentException("Route URL is invalid. Sequence \"//\" is not allowed.", "url");
            }

            if (rx.IsMatch(segment))
            {
                Match m = rx.Match(segment);
                GreedyRouteSegment s = new GreedyRouteSegment {
                    IsToken = m.Groups["isToken"].Value.Length.Equals(1),
                    IsGreedy = m.Groups["isGreedy"].Value.Length.Equals(1),
                    Name = m.Groups["name"].Value
                };
                this.urlSegments.AddLast(s);
                this.hasGreedySegment |= s.IsGreedy;

                continue;
            }
            throw new ArgumentException("Route URL is invalid.", "url");
        }

        // get minimum required segments for this route
        LinkedListNode<GreedyRouteSegment> seg = this.urlSegments.Last;
        int sIndex = this.urlSegments.Count;
        while(seg != null && this.MinRequiredSegments.Equals(0))
        {
            if (!seg.Value.IsToken || !this.Defaults.ContainsKey(seg.Value.Name))
            {
                this.MinRequiredSegments = Math.Max(this.MinRequiredSegments, sIndex);
            }
            sIndex--;
            seg = seg.Previous;
        }

        // check that segments after greedy segment don't define a default
        if (this.hasGreedySegment)
        {
            LinkedListNode<GreedyRouteSegment> s = this.urlSegments.Last;
            while (s != null && !s.Value.IsGreedy)
            {
                if (s.Value.IsToken && this.Defaults.ContainsKey(s.Value.Name))
                {
                    throw new ArgumentException(string.Format("Defaults for route segment \"{0}\" is not allowed, because it's specified after greedy catch-all segment.", s.Value.Name), "defaults");
                }
                s = s.Previous;
            }
        }
    }

    #endregion

    #region GetRouteData
    /// <summary>
    /// Returns information about the requested route.
    /// </summary>
    /// <param name="httpContext">An object that encapsulates information about the HTTP request.</param>
    /// <returns>
    /// An object that contains the values from the route definition.
    /// </returns>
    public override RouteData GetRouteData(HttpContextBase httpContext)
    {
        string virtualPath = httpContext.Request.AppRelativeCurrentExecutionFilePath.Substring(2) + httpContext.Request.PathInfo;

        RouteValueDictionary values = this.ParseRoute(virtualPath);
        if (values == null)
        {
            return null;
        }

        RouteData result = new RouteData(this, this.RouteHandler);
        if (!this.ProcessConstraints(httpContext, values, RouteDirection.IncomingRequest))
        {
            return null;
        }

        // everything's fine, fill route data
        foreach (KeyValuePair<string, object> value in values)
        {
            result.Values.Add(value.Key, value.Value);
        }
        if (this.DataTokens != null)
        {
            foreach (KeyValuePair<string, object> token in this.DataTokens)
            {
                result.DataTokens.Add(token.Key, token.Value);
            }
        }
        return result;
    }
    #endregion

    #region GetVirtualPath
    /// <summary>
    /// Returns information about the URL that is associated with the route.
    /// </summary>
    /// <param name="requestContext">An object that encapsulates information about the requested route.</param>
    /// <param name="values">An object that contains the parameters for a route.</param>
    /// <returns>
    /// An object that contains information about the URL that is associated with the route.
    /// </returns>
    public override VirtualPathData GetVirtualPath(RequestContext requestContext, RouteValueDictionary values)
    {
        RouteUrl url = this.Bind(requestContext.RouteData.Values, values);
        if (url == null)
        {
            return null;
        }
        if (!this.ProcessConstraints(requestContext.HttpContext, url.Values, RouteDirection.UrlGeneration))
        {
            return null;
        }

        VirtualPathData data = new VirtualPathData(this, url.Url);
        if (this.DataTokens != null)
        {
            foreach (KeyValuePair<string, object> pair in this.DataTokens)
            {
                data.DataTokens[pair.Key] = pair.Value;
            }
        }
        return data;
    }
    #endregion

    #region Private methods

    #region ProcessConstraints
    /// <summary>
    /// Processes constraints.
    /// </summary>
    /// <param name="httpContext">The HTTP context.</param>
    /// <param name="values">Route values.</param>
    /// <param name="direction">Route direction.</param>
    /// <returns><c>true</c> if constraints are satisfied; otherwise, <c>false</c>.</returns>
    private bool ProcessConstraints(HttpContextBase httpContext, RouteValueDictionary values, RouteDirection direction)
    {
        if (this.Constraints != null)
        {
            foreach (KeyValuePair<string, object> constraint in this.Constraints)
            {
                if (!this.ProcessConstraint(httpContext, constraint.Value, constraint.Key, values, direction))
                {
                    return false;
                }
            }
        }
        return true;
    }
    #endregion

    #region ParseRoute
    /// <summary>
    /// Parses the route into segment data as defined by this route.
    /// </summary>
    /// <param name="virtualPath">Virtual path.</param>
    /// <returns>Returns <see cref="System.Web.Routing.RouteValueDictionary"/> dictionary of route values.</returns>
    private RouteValueDictionary ParseRoute(string virtualPath)
    {
        Stack<string> parts = new Stack<string>(virtualPath.Split(new char[] {'/'}, StringSplitOptions.RemoveEmptyEntries));

        // number of request route parts must match route URL definition
        if (parts.Count < this.MinRequiredSegments)
        {
            return null;
        }

        RouteValueDictionary result = new RouteValueDictionary();

        // start parsing from the beginning
        bool finished = false;
        LinkedListNode<GreedyRouteSegment> currentSegment = this.urlSegments.First;
        while (!finished && !currentSegment.Value.IsGreedy)
        {
            object p = parts.Pop();
            if (currentSegment.Value.IsToken)
            {
                p = p ?? this.Defaults[currentSegment.Value.Name];
                result.Add(currentSegment.Value.Name, p);
                currentSegment = currentSegment.Next;
                finished = currentSegment == null;
                continue;
            }
            if (!currentSegment.Value.Equals(p))
            {
                return null;
            }
        }

        // continue from the end if needed
        parts = new Stack<string>(parts.Reverse());
        currentSegment = this.urlSegments.Last;
        while (!finished && !currentSegment.Value.IsGreedy)
        {
            object p = parts.Pop();
            if (currentSegment.Value.IsToken)
            {
                p = p ?? this.Defaults[currentSegment.Value.Name];
                result.Add(currentSegment.Value.Name, p);
                currentSegment = currentSegment.Previous;
                finished = currentSegment == null;
                continue;
            }
            if (!currentSegment.Value.Equals(p))
            {
                return null;
            }
        }

        // fill in the greedy catch-all segment
        if (!finished)
        {
            object remaining = string.Join("/", parts.Reverse().ToArray()) ?? this.Defaults[currentSegment.Value.Name];
            result.Add(currentSegment.Value.Name, remaining);
        }

        // add remaining default values
        foreach (KeyValuePair<string, object> def in this.Defaults)
        {
            if (!result.ContainsKey(def.Key))
            {
                result.Add(def.Key, def.Value);
            }
        }

        return result;
    }
    #endregion

    #region Bind
    /// <summary>
    /// Binds the specified current values and values into a URL.
    /// </summary>
    /// <param name="currentValues">Current route data values.</param>
    /// <param name="values">Additional route values that can be used to generate the URL.</param>
    /// <returns>Returns a URL route string.</returns>
    private RouteUrl Bind(RouteValueDictionary currentValues, RouteValueDictionary values)
    {
        currentValues = currentValues ?? new RouteValueDictionary();
        values = values ?? new RouteValueDictionary();

        HashSet<string> required = new HashSet<string>(this.urlSegments.Where(seg => seg.IsToken).ToList().ConvertAll(seg => seg.Name), StringComparer.OrdinalIgnoreCase);
        RouteValueDictionary routeValues = new RouteValueDictionary();

        object dataValue = null;
        foreach (string token in new List<string>(required))
        {
            dataValue = values[token] ?? currentValues[token] ?? this.Defaults[token];
            if (this.IsUsable(dataValue))
            {
                string val = dataValue as string;
                if (val != null)
                {
                    val = val.StartsWith("/") ? val.Substring(1) : val;
                    val = val.EndsWith("/") ? val.Substring(0, val.Length - 1) : val;
                }
                routeValues.Add(token, val ?? dataValue);
                required.Remove(token);
            }
        }

        // this route data is not related to this route
        if (required.Count > 0)
        {
            return null;
        }

        // add all remaining values
        foreach (KeyValuePair<string, object> pair1 in values)
        {
            if (this.IsUsable(pair1.Value) && !routeValues.ContainsKey(pair1.Key))
            {
                routeValues.Add(pair1.Key, pair1.Value);
            }
        }

        // add remaining defaults
        foreach (KeyValuePair<string, object> pair2 in this.Defaults)
        {
            if (this.IsUsable(pair2.Value) && !routeValues.ContainsKey(pair2.Key))
            {
                routeValues.Add(pair2.Key, pair2.Value);
            }
        }

        // check that non-segment defaults are the same as those provided
        RouteValueDictionary nonRouteDefaults = new RouteValueDictionary(this.Defaults);
        foreach (GreedyRouteSegment seg in this.urlSegments.Where(ss => ss.IsToken))
        {
            nonRouteDefaults.Remove(seg.Name);
        }
        foreach (KeyValuePair<string, object> pair3 in nonRouteDefaults)
        {
            if (!routeValues.ContainsKey(pair3.Key) || !this.RoutePartsEqual(pair3.Value, routeValues[pair3.Key]))
            {
                // route data is not related to this route
                return null;
            }
        }

        StringBuilder sb = new StringBuilder();
        RouteValueDictionary valuesToUse = new RouteValueDictionary(routeValues);
        bool mustAdd = this.hasGreedySegment;

        // build URL string
        LinkedListNode<GreedyRouteSegment> s = this.urlSegments.Last;
        object segmentValue = null;
        while (s != null)
        {
            if (s.Value.IsToken)
            {
                segmentValue = valuesToUse[s.Value.Name];
                mustAdd = mustAdd || !this.RoutePartsEqual(segmentValue, this.Defaults[s.Value.Name]);
                valuesToUse.Remove(s.Value.Name);
            }
            else
            {
                segmentValue = s.Value.Name;
                mustAdd = true;
            }

            if (mustAdd)
            {
                sb.Insert(0, sb.Length > 0 ? "/" : string.Empty);
                sb.Insert(0, Uri.EscapeUriString(Convert.ToString(segmentValue, CultureInfo.InvariantCulture)));
            }

            s = s.Previous;
        }

        // add remaining values
        if (valuesToUse.Count > 0)
        {
            bool first = true;
            foreach (KeyValuePair<string, object> pair3 in valuesToUse)
            {
                // only add when different from defaults
                if (!this.RoutePartsEqual(pair3.Value, this.Defaults[pair3.Key]))
                {
                    sb.Append(first ? "?" : "&");
                    sb.Append(Uri.EscapeDataString(pair3.Key));
                    sb.Append("=");
                    sb.Append(Uri.EscapeDataString(Convert.ToString(pair3.Value, CultureInfo.InvariantCulture)));
                    first = false;
                }
            }
        }

        return new RouteUrl {
            Url = sb.ToString(),
            Values = routeValues
        };
    }
    #endregion

    #region IsUsable
    /// <summary>
    /// Determines whether an object actually is instantiated or has a value.
    /// </summary>
    /// <param name="value">Object value to check.</param>
    /// <returns>
    ///     <c>true</c> if an object is instantiated or has a value; otherwise, <c>false</c>.
    /// </returns>
    private bool IsUsable(object value)
    {
        string val = value as string;
        if (val != null)
        {
            return val.Length > 0;
        }
        return value != null;
    }
    #endregion

    #region RoutePartsEqual
    /// <summary>
    /// Checks if two route parts are equal
    /// </summary>
    /// <param name="firstValue">The first value.</param>
    /// <param name="secondValue">The second value.</param>
    /// <returns><c>true</c> if both values are equal; otherwise, <c>false</c>.</returns>
    private bool RoutePartsEqual(object firstValue, object secondValue)
    {
        string sFirst = firstValue as string;
        string sSecond = secondValue as string;
        if ((sFirst != null) && (sSecond != null))
        {
            return string.Equals(sFirst, sSecond, StringComparison.OrdinalIgnoreCase);
        }
        if ((sFirst != null) && (sSecond != null))
        {
            return sFirst.Equals(sSecond);
        }
        return (sFirst == sSecond);
    }
    #endregion

    #endregion
}

And additional two classes that're used within upper code:

/// <summary>
/// Represents a route segment
/// </summary>
public class RouteSegment
{
    /// <summary>
    /// Gets or sets segment path or token name.
    /// </summary>
    /// <value>Route segment path or token name.</value>
    public string Name { get; set; }

    /// <summary>
    /// Gets or sets a value indicating whether this segment is greedy.
    /// </summary>
    /// <value><c>true</c> if this segment is greedy; otherwise, <c>false</c>.</value>
    public bool IsGreedy { get; set; }

    /// <summary>
    /// Gets or sets a value indicating whether this segment is a token.
    /// </summary>
    /// <value><c>true</c> if this segment is a token; otherwise, <c>false</c>.</value>
    public bool IsToken { get; set; }
}

and

/// <summary>
/// Represents a generated route url with route data
/// </summary>
public class RouteUrl
{
    /// <summary>
    /// Gets or sets the route URL.
    /// </summary>
    /// <value>Route URL.</value>
    public string Url { get; set; }

    /// <summary>
    /// Gets or sets route values.
    /// </summary>
    /// <value>Route values.</value>
    public RouteValueDictionary Values { get; set; }
}

That's all folks. Let me know of any issues.

I've also written a blog post related to this custom route class. It explains everything into great detail.

Answer 2

Well. It cannot be in default hierarchy. 'cause, Routing layer splitted from actions. You cannot manipulate parameter bindings. You have to write new ActionInvoker or have to use RegEx for catching.

Global.asax:

routes.Add(new RegexRoute("Show/(?<topics>.*)/(?<id>[\\d]+)/(?<title>.*)", 
    new { controller = "Home", action = "Index" }));

public class RegexRoute : Route
{
    private readonly Regex _regEx;
    private readonly RouteValueDictionary _defaultValues;

    public RegexRoute(string pattern, object defaultValues)
        : this(pattern, new RouteValueDictionary(defaultValues))
    { }

    public RegexRoute(string pattern, RouteValueDictionary defaultValues)
        : this(pattern, defaultValues, new MvcRouteHandler())
    { }

    public RegexRoute(string pattern, RouteValueDictionary defaultValues, 
        IRouteHandler routeHandler)
        : base(null, routeHandler)
    {
        this._regEx = new Regex(pattern);
        this._defaultValues = defaultValues;
    }

    private void AddDefaultValues(RouteData routeData)
    {
        if (this._defaultValues != null)
        {
            foreach (KeyValuePair<string, object> pair in this._defaultValues)
            {
                routeData.Values[pair.Key] = pair.Value;
            }
        }
    }

    public override RouteData GetRouteData(System.Web.HttpContextBase httpContext)
    {
        string requestedUrl = 
            httpContext.Request.AppRelativeCurrentExecutionFilePath.Substring(2) + 
            httpContext.Request.PathInfo;
        Match match = _regEx.Match(requestedUrl);

        if (match.Success)
        {
            RouteData routeData = new RouteData(this, this.RouteHandler);
            AddDefaultValues(routeData);

            for (int i = 0; i < match.Groups.Count; i++)
            {
                string key = _regEx.GroupNameFromNumber(i);
                Group group = match.Groups[i];
                if (!string.IsNullOrEmpty(key))
                {
                    routeData.Values[key] = group.Value;
                }
            }

            return routeData;
        }

        return null;
    }
}

Controller:

    public class HomeController : Controller
    {
        public ActionResult Index(string topics, int id, string title)
        {
            string[] arr = topics.Split('/')
        }
    }