Trie Tree matching problem

[stevapple]

Steps to reproduce

import RoutingKit
let router = Router<Int>()
router.register(0, at: [.constant("b"), .anything, .constant("c")])
router.register(1, at: [.constant("b"), .parameter("a")])
var params = Parameters()
router.route(path: ["b", "c", "c"], parameters: &params)

Expected behavior

$R0: Int? = 0

Actual behavior

$R0: Int? = nil

Environment

• vapor/router version: 4.0.0
• OS version: macOS 10.5.4

---

Reason

Different from lexicographic matching strategy, routing should follow a strategy like BFS to match the longest defined route. This issue is directly related to the following ones:

#48 Actually the same case. As for developers that really have such needs, vapor ought to provide an alternative, despite performance losses compared to the existing one.

#90 #91 Following the current model, RoutingKit is treating nodes with the same matching cases differently, which directly leads to unexpected notFounds.

#74 This bug is also caused by the matching stratergy, where .parameter is always prior to .catchall. The current solution is far from elegant as it’s using an awkward way to patch the matching solution. Neither extensible, nor clear; hardly Swifty.

Suggestion

If RoutingKit itself would not change its matching strategy, vapor does need to provide an alternative which has a more reliable and accurate model.

For RoutingKit, it means abstracting its APIs with Protocols.
For Vapor, it should allow developers to use their own routing backends in configure.swift.

Once it becomes necessary or performance-qualified, such module may become a vapor-community project.

[stevapple]

As for me, I recommend to implement a whole new router within this repo, as a new library or a non-default part of RoutingKit itself.

How do you think @Sorix @grosch ?

[tanner0101]

I think this would need just a bit more justification as to why Vapor should support it.

The examples given so far have relatively simple workarounds:

import RoutingKit
let router = Router<Int>()
- router.register(0, at: [.constant("b"), .anything, .constant("c")])
+ router.register(0, at: [.constant("b"), .parameter("a"), .constant("c")])
router.register(1, at: [.constant("b"), .parameter("a")])
var params = Parameters()
router.route(path: ["b", "c", "c"], parameters: &params)

- orders/:id
+ orders/:orderID
orders/:orderID/work/:workID

Perhaps the simplicity and good performance characteristics make these limitations worth it.

If we do decide this is a necessary feature, I think I'd prefer to try adding support for searching the entire tree to TrieRouter first before defining new types. If the performance numbers for currently supported cases become much worse then we could look at other options.

But before writing any code, I think we should take a look at how routers in other web frameworks work and what their performance characteristics are.

[grosch]

Forcing the second example is painful though. Something besides me might have added part of that route. JWT3PA and PassKit are both examples of packages that automatically add to your routes for you. Now I have to use the exact same names they do for the parameters.

What happens if those two items both add something like this:

foo/:someID/passkit
foo/:id/jwt3pa

Now I'm stuck because one implementer used the obvious ':id' while another took a more specific ':someID'.

[grosch]

In .NET, for example, I can call it whatever I want. I'd just give a routing attribute:

[Route("{id}/contact")]
public async Task<IHttpActionResult> DeleteContact(int id)

and that'll map the id paramater to the ID string part. Doesn't require they all be the same..

[ULazdins]

Stumbled upon this Issue when searching why my routes aren't working.

My example is:

func testMissingRoute() throws {
    let router = TrieRouter(Int.self)
    router.register(1, at: [":parameter", "bar"])
    router.register(2, at: ["foo", ":id"])
    var params = Parameters()
    XCTAssertEqual(router.route(path: ["foo", "bar"], parameters: &params), 1) // XCTAssertEqual failed: ("nil") is not equal to ("Optional(1)")
    XCTAssertEqual(router.route(path: ["foo", "1"], parameters: &params), 2)
}

It makes a lot of sense to me to have such structure, for example, use one route for all products, except "computers"
/products/:id
/products/computers

[ULazdins]

A follow up.

As TrieRouter implements Router protocol, I was kinda expecting a possibility to swap out TrieRouter dependency to a custom one. It turns out that's impossible because DefaultResponder uses a concrete implementation (private let router: TrieRouter<CachedRoute>) instead of a generic one.

I think it would be beneficial to change that so any Router implementation can be used. What does community think?
cc: @tanner0101

[0xTim]

Allowing changing the router should be allowed. Note that you can only have one dynamic parameter for a path component - your example of /products/:id and /products/computers works fine

[ULazdins]

@0xTim , hi!

Do you have an example of that? Only thing that comes into mind, is to replace DefaultResponder altogether. It's possible (just copy whole class and replace parts needed), but seems unmaintainable. Just replacing Router would be much better

[0xTim]

@ULazdins we could expose another initialiser on DefaultResponder that allows you to pass in your own Router. Due to the associated type on Router though they are pretty coupled

[ULazdins]

I could try to do a PR for that, but I'm not sure about some details.

Noticed that a custom responder can be configured via app.responder.use { (app) -> (Responder) in ... } call, but the DefaultResponder is marked as internal. So that means that the solution is to make DefaultResponder public and add an initalizer that allows custom router?

[0xTim]

Yeah I think that's probably the best way. I have no problem opening up DefaultResponder if there's a use-case for it. What are your thoughts @gwynne @calebkleveter @jdmcd @MrLotU since I know you have touched stuff like this?

[gwynne]

Closing this issue due to age, inactivity, and the fact that it'd take some investigation to figure out whether the problem still exists and is still relevant. Please feel free to open a new issue or ask for this one to be reopened if it seems apropos.