[RFC] Extensible routing in Tide

[gameldar]

Summary

This RFC tries to determine if extensible routing is needed in Tide

Motivation

Discussions around PRs #254 (largely on discord) and #258 addressed the question of being able to replace or change the implementation of routing within Tide to address different needs for different applications. The existing routing within Tide has issues that need addressing (#12) and how these issues are resolved tie into the question of extensible routing.

Detailed Explanation

I was initially going to look to address this as a two part question - does Tide need extensible routing, and if so what form should it take. But this actually makes it a large scope and will lead to distraction from the fundamental question - does Tide need extensible routing, or does having a good, understandable and configurable core routing implementation meet the requirements.

Looking back at the the original design goals (see the Digging Deeper section) we have the following goals:

• Make it very straightforward to understand how URLs map to code.
• Make extraction and response serialization ergonomic
• Avoid macros and code generation at the core; prefer simple, “plain Rust” APIs
• Provide a clean mechanism for middleware and configuration

With the further clarification:

For routing, to achieve the clarity goals, we follow these principles:

• Separate out routing via a “table of contents” approach, making it easy to see the overall app structure.
• No “fallback” in route matching; use match specificity. In particular, the order in which routes are added has no effect, and you cannot have two identical routes.
• Drive endpoint selection solely by URL and HTTP method. Other aspects of a request can affect middleware and the behavior of the endpoint, but not which endpoint is used in the successful case. So for example, middleware can perform authentication and avoid invoking the endpoint on failure, but it does this by explicitly choosing a separate way of providing a response, rather than relying on “fallback” in the router.

The existing routing uses route-recognizer which doesn't appear to be maintained and has some implementation issues that need addressing (Route (metadata) ordering is incorrect.) to provide a more robust routing implementation.
This is integrated into the core of Tide, although WIP in PR #258 did extract this out into a separate module.

Other open issues that relate to routing include:

• Interrnal redirects Internal redirects #82
• URL generation URL generation #24
• Permit routing without invoking actions Permit routing without invoking actions #155
• Implement OPTIONS http method Implement OPTIONS http method #51
• Allow the routing methods to open a static file Allow the routing methods to open a static file #63

Discussion points

So with an aim of trying to guide some discussion around this issue I've opened this RFC. If you have previously discussed this issue please reiterate your comments here so we can centralize the discussion.

Some questions that might be helpful for the discussion:

• What alternative use cases are there for replacing or extending the routing implementation? Can it be attained through a middleware implementation?
• Is there something missing in the existing routing that should be addressed to make it more robust, while keeping to the original goals?

[fundon]

Use path-tree instead of route-recognizer?

[fairingrey]

Just my thoughts, but the solution of least resistance it seems to me is to somehow get the maintainers of route-recognizer to accept http-rs/route-recognizer#21 (along with the tests) and update Tide to use that version with that particular routing behavior, and to keep the router as a core component of Tide for now.

I think that's fine, and that would actually likely be my first approach. But given that route-recognizer hasn't been updated in a long time (more than a year), and that its one of the few core dependencies of Tide where documentation is pretty much non-existent, it kind of drives me away from wanting to use it.

An ideal router would also have named routes as per #24 in addition to fulfilling the goals mentioned in the RFC. In regards to implementation and usage on Tide, it would seem to me at least intuitively that we key routes on their URI first, instead of the HTTP method, as it would simplify implementing #51 among other things.

With that said I'm probably most likely in favor of using https://github.com/rustasync/path-table in Tide, as its a fairly neat looking routing library that fulfills most of these goals (in addition to being a crate under the rustasync umbrella). It just needs a little bit of maintenance, minor/non-breaking in regards to style and documentation.

I haven't taken a look at path-tree, actually, but if there's a good demonstration of its' benefits that would be neat 👍

In regards to whether routing should be a middleware or a core component of Tide (as mentioned in #258 (comment)), I have to say I definitely would like to keep it in tide-core as an integral component. We can always revisit it later, but I feel like breaking it out would cause some significant trouble with documentation and syntax changes.

EDIT: changed some stuff

[fairingrey]

Mentioned it in the Discord team channel, and I might as well mention it here too -- I'm in the middle of working on my implementation of the above idea on this branch https://github.com/fairingrey/tide/tree/path_table

Note that routes are declared differently in this implementation than in Tide's current form:

• Instead of declaring named segments via a leading colon e.g. :foo, you declare them through braces, i.e. {foo}
• Nameless/anonymous segments are just {} instead of : (Note that these cannot be captured, and your server will panic trying to retrieve the param with empty string "" as per the docs
• Wildpath segments are declared with {foo}*/{}* instead of :foo*/*
• Wildcard segments cannot be matched after a wildpath segment (that is, /{foo}*/{bar} will panic on route establishment). This is likely by design of path-table.

This also follows the suggestion at #51 (comment). If a request uses a method that is not allowed at a particular resource (e.g. trying to POST at a resource where only GET behavior exists), instead of returning a 404 it will return a 405.

I'm in the middle of trying to figure out how to work out returning automatic OPTIONS endpoints (such that #51 can close), but running into a bit of a snag. The concerning code is here: https://github.com/fairingrey/tide/blob/path_table/tide-core/src/router.rs#L46-L68

Anyways, hopefully that'll give us a good idea on where to go -- I actually don't mind path-table, I think its' general design has been pretty good. Thanks to @yoshuawuyts for helping create it!

[tirr-c]

To be fair: quoting @aturon from #141 (comment), route-recognizer is used in crates.io as a transitive dependency (crates.io > conduit-router > route-recognizer), it was just not needed to update often.

We've originally used path-table before (it was written to be used in Tide), but switched to route-recognizer (for now) as path-table had some confusing corner case that was hard to deal with.

[fundon]

Thoughts:

• Use {} instead of :
• Named parameters: {foo} / {} instead of :foo / :
• Catch-All parameters: {bar}* / {}* instead of :bar* / :* / *bar / *, and they must always be at the end of the pattern.
• Custom regex parameters: {id:[\d+]} ?

Example

/
/users
/users/{id}
/users/{id}/{org}
/users/{user_id}/repos
/users/{user_id}/repos/{id}
/users/{user_id}/repos/{id}/{any}*
/{username}
/{any}*
/about
/about/
/about/us
/users/repos/{any}*

A tree struct from path-tree, just show

[tests/basic.rs:29] &tree = PathTree(
    Node {
        kind: Static(
            "/",
        ),
        data: Some(
            0,
        ),
        indices: Some(
            "u:*a",
        ),
        nodes: Some(
            [
                Node {
                    kind: Static(
                        "users",
                    ),
                    data: Some(
                        1,
                    ),
                    indices: Some(
                        "/",
                    ),
                    nodes: Some(
                        [
                            Node {
                                kind: Static(
                                    "/",
                                ),
                                data: None,
                                indices: Some(
                                    ":r",
                                ),
                                nodes: Some(
                                    [
                                        Node {
                                            kind: Parameter,
                                            data: Some(
                                                2,
                                            ),
                                            indices: Some(
                                                "/",
                                            ),
                                            nodes: Some(
                                                [
                                                    Node {
                                                        kind: Static(
                                                            "/",
                                                        ),
                                                        data: None,
                                                        indices: Some(
                                                            ":r",
                                                        ),
                                                        nodes: Some(
                                                            [
                                                                Node {
                                                                    kind: Parameter,
                                                                    data: Some(
                                                                        3,
                                                                    ),
                                                                    indices: None,
                                                                    nodes: None,
                                                                    params: Some(
                                                                        [
                                                                            "id",
                                                                            "org",
                                                                        ],
                                                                    ),
                                                                },
                                                                Node {
                                                                    kind: Static(
                                                                        "repos",
                                                                    ),
                                                                    data: Some(
                                                                        4,
                                                                    ),
                                                                    indices: Some(
                                                                        "/",
                                                                    ),
                                                                    nodes: Some(
                                                                        [
                                                                            Node {
                                                                                kind: Static(
                                                                                    "/",
                                                                                ),
                                                                                data: None,
                                                                                indices: Some(
                                                                                    ":",
                                                                                ),
                                                                                nodes: Some(
                                                                                    [
                                                                                        Node {
                                                                                            kind: Parameter,
                                                                                            data: Some(
                                                                                                5,
                                                                                            ),
                                                                                            indices: Some(
                                                                                                "/",
                                                                                            ),
                                                                                            nodes: Some(
                                                                                                [
                                                                                                    Node {
                                                                                                        kind: Static(
                                                                                                            "/",
                                                                                                        ),
                                                                                                        data: None,
                                                                                                        indices: Some(
                                                                                                            "*",
                                                                                                        ),
                                                                                                        nodes: Some(
                                                                                                            [
                                                                                                                Node {
                                                                                                                    kind: CatchAll,
                                                                                                                    data: Some(
                                                                                                                        6,
                                                                                                                    ),
                                                                                                                    indices: None,
                                                                                                                    nodes: None,
                                                                                                                    params: Some(
                                                                                                                        [
                                                                                                                            "user_id",
                                                                                                                            "id",
                                                                                                                            "any",
                                                                                                                        ],
                                                                                                                    ),
                                                                                                                },
                                                                                                            ],
                                                                                                        ),
                                                                                                        params: None,
                                                                                                    },
                                                                                                ],
                                                                                            ),
                                                                                            params: Some(
                                                                                                [
                                                                                                    "user_id",
                                                                                                    "id",
                                                                                                ],
                                                                                            ),
                                                                                        },
                                                                                    ],
                                                                                ),
                                                                                params: None,
                                                                            },
                                                                        ],
                                                                    ),
                                                                    params: Some(
                                                                        [
                                                                            "user_id",
                                                                        ],
                                                                    ),
                                                                },
                                                            ],
                                                        ),
                                                        params: None,
                                                    },
                                                ],
                                            ),
                                            params: Some(
                                                [
                                                    "id",
                                                ],
                                            ),
                                        },
                                        Node {
                                            kind: Static(
                                                "repos/",
                                            ),
                                            data: None,
                                            indices: Some(
                                                "*",
                                            ),
                                            nodes: Some(
                                                [
                                                    Node {
                                                        kind: CatchAll,
                                                        data: Some(
                                                            12,
                                                        ),
                                                        indices: None,
                                                        nodes: None,
                                                        params: Some(
                                                            [
                                                                "any",
                                                            ],
                                                        ),
                                                    },
                                                ],
                                            ),
                                            params: None,
                                        },
                                    ],
                                ),
                                params: None,
                            },
                        ],
                    ),
                    params: None,
                },
                Node {
                    kind: Parameter,
                    data: Some(
                        7,
                    ),
                    indices: None,
                    nodes: None,
                    params: Some(
                        [
                            "username",
                        ],
                    ),
                },
                Node {
                    kind: CatchAll,
                    data: Some(
                        8,
                    ),
                    indices: None,
                    nodes: None,
                    params: Some(
                        [
                            "any",
                        ],
                    ),
                },
                Node {
                    kind: Static(
                        "about",
                    ),
                    data: Some(
                        9,
                    ),
                    indices: Some(
                        "/",
                    ),
                    nodes: Some(
                        [
                            Node {
                                kind: Static(
                                    "/",
                                ),
                                data: Some(
                                    10,
                                ),
                                indices: Some(
                                    "u",
                                ),
                                nodes: Some(
                                    [
                                        Node {
                                            kind: Static(
                                                "us",
                                            ),
                                            data: Some(
                                                11,
                                            ),
                                            indices: None,
                                            nodes: None,
                                            params: None,
                                        },
                                    ],
                                ),
                                params: None,
                            },
                        ],
                    ),
                    params: None,
                },
            ],
        ),
        params: None,
    },
)

How to match?

Recursive lookup, follow the steps below:

1. search static node
2. search name parameter node
3. search catch-all parameter node

How to generate URL?

let s = custom_format!("/users/{user_id}/repos/{id}/{any}*".trim_end_matches('*'),  user_id = 233, id = 377, any = "issues/610");
println!(s);

Performance

https://travis-ci.org/trek-rs/path-tree/jobs/535980099#L564-L601

[gameldar]

As @yoshuawuyts requested - I've rewritten this as PR #274 to following the template for RFCs that has been provided. This'll allow for more focused discussion around elements of the RFC and provides methods multiple threads of discussion.

So I'll close this issue and we can move discussion over there (note I've also fleshed out the RFC more as well, including discussing possible ways of addressing extensibility of routing)