router not found

[Duslia]

Code:
`

func main() {
    h := echo.New()
    h.GET("/a/:b/c", func(ctx echo.Context) error{
    	return ctx.String(http.StatusOK, "Hello, World!")
    })
    h.GET("/a/c/d", func(ctx echo.Context) error{
	return ctx.String(http.StatusOK, "Hello, World!")
    })
    h.GET("/:e/c/f", func(ctx echo.Context)error {
	return ctx.String(http.StatusOK, "Hello, World!")
    })
    h.Logger.Fatal(h.Start(":1323"))
}

`
When I send /a/c/f, it will return not found.

[aldas]

So for case

Route tree is built as:

// Issue #1754 - router needs to backtrack multiple levels upwards in tree to find the matching route
// route evaluation order
//                            +-0,7--------+
//                            | "/" (root) |
//                            +------------+
//                                 |      |
//                                 |      |
//             +-1,6-----------+   |      |          +-8-----------+
//             | "a/" (static) +<--+      +--------->+ ":" (param) |
//             +---------------+                     +-------------+
//                |          |                             |
//     +-2--------v-----+   +v-3,5--------+       +-9------v--------+
//     | "c/d" (static) |   | ":" (param) |       | "/c/f" (static) |
//     +----------------+   +-------------+       +-----------------+
//                           |
//                      +-4--v----------+
//                      | "/c" (static) |
//                      +---------------+
func TestRouteMultiLevelBacktracking(t *testing.T) {
	e := New()
	r := e.router

	r.Add(http.MethodGet, "/a/:b/c", handlerHelper("case", 1))
	r.Add(http.MethodGet, "/a/c/d", handlerHelper("case", 2))
	r.Add(http.MethodGet, "/:e/c/f", handlerHelper("case", 3))

	c := e.NewContext(nil, nil).(*context)
	r.Find(http.MethodGet, "/a/c/f", c)

	c.handler(c)
	assert.Equal(t, 3, c.Get("case"))
	assert.Equal(t, "/:e/c/f", c.Get("path"))
}

so when searching match for request uri /a/c/f everything is fine till tree traversial reaches dead end at 4th node "/c (static) and tree search starts to backtrack up in tree. Backtracking stops at "a/ (static)" and request ends up as 404

In theory backtracking should be as (upwards 4->5->6->7 and 7->8->9 downwards) to root level and choose adjacent node ":" (param) that is right to "a/" (static) as it also matches uri as param node and then reach our needed match "/c/f" (static)

[lammel]

I guess this needs to be investigated, why the backtracking does not reach the root now.

@Duslia997 Which version of echo are you using?

[Duslia]

I guess this needs to be investigated, why the backtracking does not reach the root now.

@Duslia997 Which version of echo are you using?

github.com/labstack/echo/v4 v4.1.17

[aldas]

after looking router.Find I would say it needs definitely some refactoring to be done:

Some remarks:

• those short variable names make understanding logic quite hard when for loop itself is 150 lines. cn nn etc work only for short blocks.
• there are couple conditions in code to break out of loop for some corner case which feel for me out of place.
• I think some implement backtracking logic that is not valid requirement. See

  echo/router.go

  Line 465 in 7c8592a

  for {

  it just does not feel corrext that when doing multi level backtracking it could be that easy just go up and check only for any nodes. There is at least our failing case when backtracking should go up multiple levels and then start to down by paramChildren subtree
• some of the blocks are doing clever stuff but it hard to understand why and when. For example:
• • this block is executed only for when node is static kind. But that label check with not makes it quite hard to read. Problably if cn.kind == sKind { would be more readable for people that dot not this code.
• • this block relies heavily on previous loop iteration. To be exact - it is executed when static route has exact match or we are dealing with param/any routes. AND itself contains conditions to break out of loop - this is actually similar to line 348 block because for param/any node previous LCP block is not executed and lcpLen == prefixLen is always 0 == 0
• what is handled in FOR loop iteration is very confusing for me. For example ANY block has goto Param block. which mean in one FOR iteration the execution direction is not even clear (one way - top to bottom)
• inline assignements are hard to read if cn = cn.anyChildren; cn != nil { because there are code below that if block that depend this assignment to take place.

[pafuent]

@aldas I'm working on fixing #1744, maybe I can also use the PR to rename the variables with short names (as you mentioned it was hard for me to understand the code to fix some issues on the past)

[aldas]

@pafuent if you rename variables then definitely do it in separate commit. It is hard to search in history when many different things (cleaning code and fixing bugs) are in same commit. Looking from history how code evolves is very handy way to understand problems.

I created branch just for myself to be able to understand/read Find logic.

After 3 hours of read code/debugging, looking related issues - I would say I still do not feel comfortable explaining how execution flow goes and what should be done to fix backtracking. It does not feel right to hack another condition into that flow without understanding broader problem domain - tree traversal itself not hard problem most of the time.

[lammel]

For the first fixes it took me a day and a lot of debugging to understand where to start fixing ;-)
Renaming is fine for me, I generally prefer clear and expressive naming (with tight loops being an exception).

Now with the child for any/param/static being different entities we might have a chance for further improvement.
I also though about a rewrite of the router, based more on a path optimized radix tree (as routing is very dependent on fragments between / as defined by the RFC anyway). Quite a number of exceptions in the current code are needed, because we are traversing only a part of a path-fragment and going up is usually means find the upper path fragment.

The test-suite is quite extensive already, so changes in the router logic are quite save to do in term of detecting misbehaviour.

[aldas]

LCP and radix tree difference pretty much "only" this for loop which is executed for each sKind (static kind) route node. So this affects only static routes. Logic of moving/searching between static -> param -> any nodes is still same.

[aldas]

I think I'll create one complex example routing tree for additional testing - that tree should be multiple levels deep, having different variant of nodes with different mix of children (having only static leafs beneath, having static+param, param+any, static+any, multiple levels of static or param nodes etc).

actually thinking about it - I think there could be one problem (not defined requirement) with current implementation searching for matching node does not take HTTP method into consideration. It might match node too early that does not actually have that method registered (ala finds static route but it does not have DELETE, but delete exists in param routes)

[lammel]

Currently the router is not able to distinguish between HTTP methods, which also may cause a wrong routing decisions.
I think also #1726 touches this topic, but with the focus on parameter naming.

The methods (methodHandler in the the route nodes) are there, but are not considered for routing (probably to avoid performance hit during routing). To ensure correct routing the available methods for a node should also be considered and nodes skipped that do not have such an handler. This will avoid shadowing routes where a GET route might shadow other routes, aklthBut we need to think about how we define how the router should work.

But I think the tests already provide some complex router setups, which might be a good starting point.

Many frameworks allow an ANY route too, that will operator on all methods for that route (we would only need a special anymethod to support that too (but I guess that could be v5 too).

[stffabi]

Another simpler test case is the following:

func TestRouterBacktrackingFromParam(t *testing.T) {
	e := New()
	r := e.router

	r.Add(http.MethodGet, "/*", handlerHelper("case", 1))
	r.Add(http.MethodGet, "/users/:name/", handlerHelper("case", 2))

	c := e.NewContext(nil, nil).(*context)

	r.Find(http.MethodGet, "/users/firstname/no-match", c)

	c.handler(c)
	assert.Equal(t, 1, c.Get("case"))
	assert.Equal(t, "/*", c.Get("path"))
}

I think the main problem in the Find code is, that the next nodes for backtracking get simply overwritten from a downtree Save Next. As a result the original Saved Next is lost and will never be investigated anymore.
In the simple test case above, first nextNode is equal to the /* node but later on when /users/:name matches nextNode will be overwritten with /users/:name and /* is lost. Therefore backtracking never gets back to /*.
In order for a reliable backtracking wouldn't we have to store all nodes (and the state) on the path down the tree, and afterwards if we reach a dead end, go back to that state? So basically we would have to introduce a stack of the next states and roll them back whenever needed.

I've tried to hack together a PoC code with a very simple stack based on a slice. Currently all test cases pass, in addition also mine and the main test case from this issue pass. As I've mentioned it's pure PoC code and my intention was not to get a PR which would be ready for merge. But maybe we could use it as a starting point for a discussion. Which is why I will publish it as a Draft PR.

Thanks to all of you for your hard work on echo.

[aldas]

#1770 is interesting. I have been tinkering around with version without stack and simplifying code just because I'm pretty much unable to mentally follow current flow (my personal problem)

This is good that we could have multiple possible solutions as every approach has their pros and cons but we at least have choice.

Backtracking by multiple levels needs information about previous node where backtracking was made. This is because 1 node can have 3 different types of child nodes (static, param, any) and depending where you backtrack your next sibling changes (or parent).

For example when you backtrack from static node your next evaluation should be:

• sibling param route (if exists)
• sibling any route (if param does not exist)
• parents (next sibling by parent node kind or even its parent) (if anyroute does not exist)

I think good complex multilevel backtracking is this example:
because by traversing tree you reach dead end at node 4 and need to backtrack to parent parm node and as it does not have any node sibling you need to backtrack another level and check if that node has sibling (of param kind as "a/" is static kind)

r.Add(http.MethodGet, "/a/:b/c", handlerHelper("case", 1))
r.Add(http.MethodGet, "/a/c/d", handlerHelper("case", 2))
r.Add(http.MethodGet, "/a/c/df", handlerHelper("case", 3))
r.Add(http.MethodGet, "/:e/c/f", handlerHelper("case", 5))
r.Add(http.MethodGet, "/*", handlerHelper("case", 6))

// Request for "/a/c/f" should match "/:e/c/f"
//
//                            +-0,7--------+
//                            | "/" (root) |----------------------------------+
//                            +------------+                                  |
//                                 |      |                                   |
//                                 |      |                                   |
//             +-1,6-----------+   |      |          +-8-----------+   +------v----+
//             | "a/" (static) +<--+      +--------->+ ":" (param) |   | "*" (any) |
//             +---------------+                     +-------------+   +-----------+
//                |          |                             |
//     +-2--------v-----+   +v-3,5--------+       +-9------v--------+
//     | "c/d" (static) |   | ":" (param) |       | "/c/f" (static) |
//     +----------------+   +-------------+       +-----------------+
//                           |
//                      +-4--v----------+
//                      | "/c" (static) |
//                      +---------------+

[aldas]

Implemented with #1770 and merged in #1791