Repository: labstack/echo (go)

Issue:
static routing and dynamic routing  conflicts problems.
### Issue Description
If static routing and dynamic routing have only the last or several characters different, there will be routing conflicts.

### Checklist

 e.GET("/ups/person",hello)
 e.GET("/users/new", hello)
 e.GET("users/:name", hello)

curl localhost:1323/users/new   --- ok
curl localhost:1323/users/new2 --- 404


- [ ] Dependencies installed
- [ ] No typos
- [ ] Searched existing issues and docs

### Expected behaviour

curl localhost:1323/users/new   --- ok
curl localhost:1323/users/new2 --- ok

### Actual behaviour

curl localhost:1323/users/new   --- ok
curl localhost:1323/users/new2 --- 404

### Steps to reproduce

### Working code to debug

```go
package main
  
import (
  "net/http"
  "github.com/labstack/echo"
  "github.com/labstack/echo/middleware"
)

func main() {
  // Echo instance
  e := echo.New()

  // Middleware
  e.Use(middleware.Logger())
  e.Use(middleware.Recover())

  // Routes
  e.GET("/", hello)
  e.GET("/ups/person",hello)
  e.GET("/users/new", hello)
  e.GET("/users/:name", hello)

  // Start server
  e.Logger.Fatal(e.Start(":1323"))
}

// Handler
func hello(c echo.Context) error {
  return c.String(http.StatusOK, "Hello, World!")
}
```

### Version/commit


Pull request description:
Fix multi level match any routes
This is a pull request for issue #1412 which probably also fixes #1406 .

The benchmarks also indicate a slight improvement for the route tests (although that was not intential). So this should probably be verified elsewhere too.

As a side-effect also a small issue for the router not returning the correct remaining path in c.Param("*") with overlapping any routes has been fixed (and a test added)

The route tests have also been improved which can also be provided as part of this PR are separately.

Patch:
diff --git a/go.sum b/go.sum
index 5aedb2e..d09df32 100644
--- a/go.sum
+++ b/go.sum
@@ -26,9 +26,11 @@ golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn
 golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20190222072716-a9d3bda3a223/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20190813064441-fde4db37ae7a h1:aYOabOQFp6Vj6W1F80affTUvO9UxmJRx8K0gsfABByQ=
 golang.org/x/sys v0.0.0-20190813064441-fde4db37ae7a/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/text v0.3.0 h1:g61tztE5qeGQ89tm6NTjjM9VPIm088od1l6aSorWRWg=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
 gopkg.in/yaml.v2 v2.2.2 h1:ZCJp+EgiOT7lHqUV2J862kp8Qj64Jo6az82+3Td9dZw=
 gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
diff --git a/router.go b/router.go
index 70bf409..8b15e65 100644
--- a/router.go
+++ b/router.go
@@ -1,6 +1,9 @@
 package echo
 
-import "net/http"
+import (
+	"net/http"
+	"strings"
+)
 
 type (
 	// Router is the registry of all registered routes for an `Echo` instance for
@@ -20,8 +23,8 @@ type (
 		pnames        []string
 		methodHandler *methodHandler
 	}
-	kind uint8
-	children []*node
+	kind          uint8
+	children      []*node
 	methodHandler struct {
 		connect  HandlerFunc
 		delete   HandlerFunc
@@ -133,6 +136,11 @@ func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string
 			// Split node
 			n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames)
 
+			// Update parent path for all children to new node
+			for _, child := range cn.children {
+				child.parent = n
+			}
+
 			// Reset parent node
 			cn.kind = skind
 			cn.label = cn.prefix[0]
@@ -336,7 +344,6 @@ func (r *Router) Find(method, path string, c Context) {
 			}
 		}
 
-
 		if l == pl {
 			// Continue search
 			search = search[l:]
@@ -398,16 +405,32 @@ func (r *Router) Find(method, path string, c Context) {
 	Any:
 		if cn = cn.findChildByKind(akind); cn == nil {
 			if nn != nil {
-				cn = nn
-				nn = cn.parent // Next (Issue #954)
-				if nn != nil {
-					nk = nn.kind
-				}
+				// No next node to go down in routing (issue #954)
+				// Find nearest "any" route going up the routing tree
 				search = ns
-				if nk == pkind {
-					goto Param
-				} else if nk == akind {
-					goto Any
+				np := nn.parent
+				// Consider param route one level up only
+				// if no slash is remaining in search string
+				if cn = nn.findChildByKind(pkind); cn != nil && strings.IndexByte(ns, '/') == -1 {
+					break
+				}
+				for {
+					np = nn.parent
+					if cn = nn.findChildByKind(akind); cn != nil {
+						break
+					}
+					if np == nil {
+						break // no further parent nodes in tree, abort
+					}
+					var str strings.Builder
+					str.WriteString(nn.prefix)
+					str.WriteString(search)
+					search = str.String()
+					nn = np
+				}
+				if cn != nil { // use the found "any" route and update path
+					pvalues[len(cn.pnames)-1] = search
+					break
 				}
 			}
 			return // Not found


Test patch:
diff --git a/group_test.go b/group_test.go
index de98ce3..342cd29 100644
--- a/group_test.go
+++ b/group_test.go
@@ -65,3 +65,42 @@ func TestGroupRouteMiddleware(t *testing.T) {
 	c, _ = request(http.MethodGet, "/group/405", e)
 	assert.Equal(t, 405, c)
 }
+
+func TestGroupRouteMiddlewareWithMatchAny(t *testing.T) {
+	// Ensure middleware and match any routes do not conflict
+	e := New()
+	g := e.Group("/group")
+	m1 := func(next HandlerFunc) HandlerFunc {
+		return func(c Context) error {
+			return next(c)
+		}
+	}
+	m2 := func(next HandlerFunc) HandlerFunc {
+		return func(c Context) error {
+			return c.String(http.StatusOK, c.Path())
+		}
+	}
+	h := func(c Context) error {
+		return c.String(http.StatusOK, c.Path())
+	}
+	g.Use(m1)
+	g.GET("/help", h, m2)
+	g.GET("/*", h, m2)
+	g.GET("", h, m2)
+	e.GET("unrelated", h, m2)
+	e.GET("*", h, m2)
+
+	_, m := request(http.MethodGet, "/group/help", e)
+	assert.Equal(t, "/group/help", m)
+	_, m = request(http.MethodGet, "/group/help/other", e)
+	assert.Equal(t, "/group/*", m)
+	_, m = request(http.MethodGet, "/group/404", e)
+	assert.Equal(t, "/group/*", m)
+	_, m = request(http.MethodGet, "/group", e)
+	assert.Equal(t, "/group", m)
+	_, m = request(http.MethodGet, "/other", e)
+	assert.Equal(t, "/*", m)
+	_, m = request(http.MethodGet, "/", e)
+	assert.Equal(t, "/*", m)
+
+}
diff --git a/router_test.go b/router_test.go
index 80f1d0e..cd0817d 100644
--- a/router_test.go
+++ b/router_test.go
@@ -499,6 +499,15 @@ var (
 		{"GET", "/people/:userId/moments/:collection", ""},
 		{"DELETE", "/moments/:id", ""},
 	}
+
+	// handlerHelper created a function that will set a context key for assertion
+	handlerHelper = func(key string, value int) func(c Context) error {
+		return func(c Context) error {
+			c.Set(key, value)
+			c.Set("path", c.Path())
+			return nil
+		}
+	}
 )
 
 func TestRouterStatic(t *testing.T) {
@@ -595,20 +604,91 @@ func TestRouterMatchAnyMultiLevel(t *testing.T) {
 	// Routes
 	r.Add(http.MethodGet, "/api/users/jack", handler)
 	r.Add(http.MethodGet, "/api/users/jill", handler)
+	r.Add(http.MethodGet, "/api/users/*", handler)
+	r.Add(http.MethodGet, "/api/*", handler)
+	r.Add(http.MethodGet, "/other/*", handler)
 	r.Add(http.MethodGet, "/*", handler)
 
 	c := e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/api/users/jack", c)
 	c.handler(c)
 	assert.Equal(t, "/api/users/jack", c.Get("path"))
+	assert.Equal(t, "", c.Param("*"))
 
 	r.Find(http.MethodGet, "/api/users/jill", c)
 	c.handler(c)
 	assert.Equal(t, "/api/users/jill", c.Get("path"))
+	assert.Equal(t, "", c.Param("*"))
 
 	r.Find(http.MethodGet, "/api/users/joe", c)
 	c.handler(c)
+	assert.Equal(t, "/api/users/*", c.Get("path"))
+	assert.Equal(t, "joe", c.Param("*"))
+
+	r.Find(http.MethodGet, "/api/nousers/joe", c)
+	c.handler(c)
+	assert.Equal(t, "/api/*", c.Get("path"))
+	assert.Equal(t, "nousers/joe", c.Param("*"))
+
+	r.Find(http.MethodGet, "/api/none", c)
+	c.handler(c)
+	assert.Equal(t, "/api/*", c.Get("path"))
+	assert.Equal(t, "none", c.Param("*"))
+
+	r.Find(http.MethodGet, "/noapi/users/jim", c)
+	c.handler(c)
 	assert.Equal(t, "/*", c.Get("path"))
+	assert.Equal(t, "noapi/users/jim", c.Param("*"))
+}
+func TestRouterMatchAnyMultiLevelWithPost(t *testing.T) {
+	e := New()
+	r := e.router
+	handler := func(c Context) error {
+		c.Set("path", c.Path())
+		return nil
+	}
+
+	// Routes
+	e.POST("/api/auth/login", handler)
+	e.POST("/api/auth/forgotPassword", handler)
+	e.Any("/api/*", handler)
+	e.Any("/*", handler)
+
+	// POST /api/auth/login shall choose login method
+	c := e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodPost, "/api/auth/login", c)
+	c.handler(c)
+	assert.Equal(t, "/api/auth/login", c.Get("path"))
+	assert.Equal(t, "", c.Param("*"))
+
+	// GET /api/auth/login shall choose any route
+	// c = e.NewContext(nil, nil).(*context)
+	// r.Find(http.MethodGet, "/api/auth/login", c)
+	// c.handler(c)
+	// assert.Equal(t, "/api/*", c.Get("path"))
+	// assert.Equal(t, "auth/login", c.Param("*"))
+
+	// POST /api/auth/logout shall choose nearest any route
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodPost, "/api/auth/logout", c)
+	c.handler(c)
+	assert.Equal(t, "/api/*", c.Get("path"))
+	assert.Equal(t, "auth/logout", c.Param("*"))
+
+	// POST to /api/other/test shall choose nearest any route
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodPost, "/api/other/test", c)
+	c.handler(c)
+	assert.Equal(t, "/api/*", c.Get("path"))
+	assert.Equal(t, "other/test", c.Param("*"))
+
+	// GET to /api/other/test shall choose nearest any route
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/api/other/test", c)
+	c.handler(c)
+	assert.Equal(t, "/api/*", c.Get("path"))
+	assert.Equal(t, "other/test", c.Param("*"))
+
 }
 
 func TestRouterMicroParam(t *testing.T) {
@@ -674,71 +754,123 @@ func TestRouterPriority(t *testing.T) {
 	r := e.router
 
 	// Routes
-	r.Add(http.MethodGet, "/users", func(c Context) error {
-		c.Set("a", 1)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/new", func(c Context) error {
-		c.Set("b", 2)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/:id", func(c Context) error {
-		c.Set("c", 3)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/dew", func(c Context) error {
-		c.Set("d", 4)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/:id/files", func(c Context) error {
-		c.Set("e", 5)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/newsee", func(c Context) error {
-		c.Set("f", 6)
-		return nil
-	})
-	r.Add(http.MethodGet, "/users/*", func(c Context) error {
-		c.Set("g", 7)
-		return nil
-	})
-	c := e.NewContext(nil, nil).(*context)
+	r.Add(http.MethodGet, "/users", handlerHelper("a", 1))
+	r.Add(http.MethodGet, "/users/new", handlerHelper("b", 2))
+	r.Add(http.MethodGet, "/users/:id", handlerHelper("c", 3))
+	r.Add(http.MethodGet, "/users/dew", handlerHelper("d", 4))
+	r.Add(http.MethodGet, "/users/:id/files", handlerHelper("e", 5))
+	r.Add(http.MethodGet, "/users/newsee", handlerHelper("f", 6))
+	r.Add(http.MethodGet, "/users/*", handlerHelper("g", 7))
+	r.Add(http.MethodGet, "/users/new/*", handlerHelper("h", 8))
+	r.Add(http.MethodGet, "/*", handlerHelper("i", 9))
 
 	// Route > /users
+	c := e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users", c)
 	c.handler(c)
 	assert.Equal(t, 1, c.Get("a"))
+	assert.Equal(t, "/users", c.Get("path"))
 
 	// Route > /users/new
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/new", c)
 	c.handler(c)
 	assert.Equal(t, 2, c.Get("b"))
+	assert.Equal(t, "/users/new", c.Get("path"))
 
 	// Route > /users/:id
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/1", c)
 	c.handler(c)
 	assert.Equal(t, 3, c.Get("c"))
+	assert.Equal(t, "/users/:id", c.Get("path"))
 
 	// Route > /users/dew
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/dew", c)
 	c.handler(c)
 	assert.Equal(t, 4, c.Get("d"))
+	assert.Equal(t, "/users/dew", c.Get("path"))
 
 	// Route > /users/:id/files
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/1/files", c)
 	c.handler(c)
 	assert.Equal(t, 5, c.Get("e"))
+	assert.Equal(t, "/users/:id/files", c.Get("path"))
 
 	// Route > /users/:id
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/news", c)
 	c.handler(c)
 	assert.Equal(t, 3, c.Get("c"))
+	assert.Equal(t, "/users/:id", c.Get("path"))
+
+	// Route > /users/newsee
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/users/newsee", c)
+	c.handler(c)
+	assert.Equal(t, 6, c.Get("f"))
+	assert.Equal(t, "/users/newsee", c.Get("path"))
+
+	// Route > /users/newsee
+	r.Find(http.MethodGet, "/users/newsee", c)
+	c.handler(c)
+	assert.Equal(t, 6, c.Get("f"))
+
+	// Route > /users/newsee
+	r.Find(http.MethodGet, "/users/newsee", c)
+	c.handler(c)
+	assert.Equal(t, 6, c.Get("f"))
 
 	// Route > /users/*
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/joe/books", c)
 	c.handler(c)
 	assert.Equal(t, 7, c.Get("g"))
+	assert.Equal(t, "/users/*", c.Get("path"))
 	assert.Equal(t, "joe/books", c.Param("*"))
+
+	// Route > /users/new/* should be matched
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/users/new/someone", c)
+	c.handler(c)
+	assert.Equal(t, 8, c.Get("h"))
+	assert.Equal(t, "/users/new/*", c.Get("path"))
+	assert.Equal(t, "someone", c.Param("*"))
+
+	// Route > /users/* should be matched although /users/dew exists
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/users/dew/someone", c)
+	c.handler(c)
+	assert.Equal(t, 7, c.Get("g"))
+	assert.Equal(t, "/users/*", c.Get("path"))
+
+	assert.Equal(t, "dew/someone", c.Param("*"))
+
+	// Route > /users/* should be matched although /users/dew exists
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/users/notexists/someone", c)
+	c.handler(c)
+	assert.Equal(t, 7, c.Get("g"))
+	assert.Equal(t, "/users/*", c.Get("path"))
+	assert.Equal(t, "notexists/someone", c.Param("*"))
+
+	// Route > *
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/nousers", c)
+	c.handler(c)
+	assert.Equal(t, 9, c.Get("i"))
+	assert.Equal(t, "/*", c.Get("path"))
+	assert.Equal(t, "nousers", c.Param("*"))
+
+	// Route > *
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/nousers/new", c)
+	c.handler(c)
+	assert.Equal(t, 9, c.Get("i"))
+	assert.Equal(t, "/*", c.Get("path"))
+	assert.Equal(t, "nousers/new", c.Param("*"))
 }
 
 func TestRouterIssue1348(t *testing.T) {
@@ -819,36 +951,59 @@ func TestRouterParamNames(t *testing.T) {
 	assert.Equal(t, "1", c.Param("fid"))
 }
 
-// Issue #623
+// Issue #623 and #1406
 func TestRouterStaticDynamicConflict(t *testing.T) {
 	e := New()
 	r := e.router
-	c := e.NewContext(nil, nil)
 
-	r.Add(http.MethodGet, "/dictionary/skills", func(c Context) error {
-		c.Set("a", 1)
-		return nil
-	})
-	r.Add(http.MethodGet, "/dictionary/:name", func(c Context) error {
-		c.Set("b", 2)
-		return nil
-	})
-	r.Add(http.MethodGet, "/server", func(c Context) error {
-		c.Set("c", 3)
-		return nil
-	})
+	r.Add(http.MethodGet, "/dictionary/skills", handlerHelper("a", 1))
+	r.Add(http.MethodGet, "/dictionary/:name", handlerHelper("b", 2))
+	r.Add(http.MethodGet, "/users/new", handlerHelper("d", 4))
+	r.Add(http.MethodGet, "/users/:name", handlerHelper("e", 5))
+	r.Add(http.MethodGet, "/server", handlerHelper("c", 3))
+	r.Add(http.MethodGet, "/", handlerHelper("f", 6))
 
+	c := e.NewContext(nil, nil)
 	r.Find(http.MethodGet, "/dictionary/skills", c)
 	c.Handler()(c)
 	assert.Equal(t, 1, c.Get("a"))
+	assert.Equal(t, "/dictionary/skills", c.Get("path"))
+
+	c = e.NewContext(nil, nil)
+	r.Find(http.MethodGet, "/dictionary/skillsnot", c)
+	c.Handler()(c)
+	assert.Equal(t, 2, c.Get("b"))
+	assert.Equal(t, "/dictionary/:name", c.Get("path"))
+
 	c = e.NewContext(nil, nil)
 	r.Find(http.MethodGet, "/dictionary/type", c)
 	c.Handler()(c)
 	assert.Equal(t, 2, c.Get("b"))
+	assert.Equal(t, "/dictionary/:name", c.Get("path"))
+
 	c = e.NewContext(nil, nil)
 	r.Find(http.MethodGet, "/server", c)
 	c.Handler()(c)
 	assert.Equal(t, 3, c.Get("c"))
+	assert.Equal(t, "/server", c.Get("path"))
+
+	c = e.NewContext(nil, nil)
+	r.Find(http.MethodGet, "/users/new", c)
+	c.Handler()(c)
+	assert.Equal(t, 4, c.Get("d"))
+	assert.Equal(t, "/users/new", c.Get("path"))
+
+	c = e.NewContext(nil, nil)
+	r.Find(http.MethodGet, "/users/new2", c)
+	c.Handler()(c)
+	assert.Equal(t, 5, c.Get("e"))
+	assert.Equal(t, "/users/:name", c.Get("path"))
+
+	c = e.NewContext(nil, nil)
+	r.Find(http.MethodGet, "/", c)
+	c.Handler()(c)
+	assert.Equal(t, 6, c.Get("f"))
+	assert.Equal(t, "/", c.Get("path"))
 }
 
 // Issue #1348