Change routing to search all possible routes and choose most specific…

[ULazdins]

Changes routing to match most specific of possible routes instead of current behaviour. Fixes #92

Consider attached test cases which currently fail, but are fixed in this Pull Request:

    func testMatchesLongestRoute() throws {
        let router = TrieRouter(String.self)
        
        router.register("longest", at: ["a", "b", ":param", "d"])
        router.register("shortest", at: ["a", "b", "c"])
        
        var params = Parameters()
        // Fails with:   // XCTAssertEqual failed: ("nil") is not equal to ("Optional("longest")")
        XCTAssertEqual(router.route(path: ["a", "b", "c", "d"], parameters: &params), "longest")
        XCTAssertEqual(params.get("param"), "c")
    }
    
    func testMatchesLongestRoute2() throws {
        let router = TrieRouter(String.self)
        
        router.register("longest", at: ["a", "b", ":param", .catchall])
        router.register("shortest", at: ["a", "b", "c"])
        
        var params = Parameters()

        // Fails with:   XCTAssertEqual failed: ("nil") is not equal to ("Optional("longest")")
        XCTAssertEqual(router.route(path: ["a", "b", "c", "d"], parameters: &params), "longest")
        XCTAssertEqual(params.get("param"), "c")
        XCTAssertEqual(params.getCatchall(), ["d"])
    }

These changes have small time and space complexity penalty, but I'm not able to wrap my head around what exactly is the new performance hit. The performance tests seems OK.

[twof]

@vapor-bot test performance

[0xTim]

Yeah this isn't getting merged. I've just run the performance tests locally. Current implementation took 25s to run them all. This PR took 5 minutes and 19 seconds. We could potentially give up a few percent of performance for improved behaviour of routing but 1200% is a bit much! 😅

[ULazdins]

@0xTim , sorry what? 😅 Runs fine on 2019 MBP

Can you post your test results?

[0xTim]

You need to change the configuration to release to actually enable the performance tests - you can see they all took 0.01s because they were ignored by https://github.com/vapor/routing-kit/blob/master/Tests/RoutingKitTests/RouterPerformanceTests.swift#L132

[ULazdins]

Got it. Will investigate if can be improved