Repository: labstack/echo (go)

Issue:
Function looping router.go#Find
### Issue Description

Example code has the one registered route 

```golang
e := echo.New()
// Routes
e.GET("/assets/:id", assetID)
...
// assetID mock of the real handler
func assetID(c echo.Context) error {
	return c.String(http.StatusOK, "assetID")
}
```  

when request uri is `/assets/tree/free` application is looping...

if application is simple then another requests are processing, but in complex application it's don't answer to any requests and need `kill -9 pid`  
current request deadlocking...
### Checklist

- [ x] Dependencies installed
- [ x] No typos
- [ x] Searched existing issues and docs  
very similar issue#1461

### Expected behaviour

`404 {"message":"Not Found"}`

### Actual behaviour

```bash
curl  http://localhost:1323/assets/3/e
{"message":"Not Found"}

curl  http://localhost:1323/assets/tree/free
# looping and stop answer...
```

### Steps to reproduce

- run code below
- make curl request `curl  http://localhost:1323/assets/tree/free`

### Working code to debug

```go
package main

import (
	"github.com/labstack/echo/v4"
	"github.com/labstack/echo/v4/middleware"
	"net/http"
)

func main() {
	// Echo instance
	e := echo.New()

	// Middleware
	e.Use(middleware.Logger())
	e.Use(middleware.Recover())

	// Routes
	e.GET("/assets/:id", assetID)
	// Start server
	e.Logger.Fatal(e.Start(":1323"))
}

// assetID mock of the real handler
func assetID(c echo.Context) error {
	return c.String(http.StatusOK, "assetID")
}
```

### Version/commit

**4.1.14**

Pull request:
Fix #1493 router loop for param routes
This pull request fixes issue #1493, which refers to a router loop recently introduced with commit 5bf6888 to fix param values. The router Find function will now correctly set the parameters and avoid the endless routing loop.

An additional test for the loop has been added (it is reproducable) and some router tests have been corrected to use a fresh context for the tests (to avoid leaking state). 

### Benchmark

Benchmarks are looking good, only minimal changes (~1% for static route performance)

With this patch:

```
rl@slimboy branch:bugfix/1493-# /usr/bin/go test -benchmem -run=^$ github.com/labstack/echo/v4 -bench '^(BenchmarkRouterStaticRoutes|BenchmarkRouterGitHubAPI|BenchmarkRouterParseAPI|BenchmarkRouterGooglePlusAPI)$'
goos: linux
goarch: amd64
pkg: github.com/labstack/echo/v4
BenchmarkRouterStaticRoutes-8    	  91005	    11681 ns/op	      0 B/op	      0 allocs/op
BenchmarkRouterGitHubAPI-8       	  48444	    24682 ns/op	      1 B/op	      0 allocs/op
BenchmarkRouterParseAPI-8        	 293914	     3933 ns/op	      0 B/op	      0 allocs/op
BenchmarkRouterGooglePlusAPI-8   	 187198	     6247 ns/op	      0 B/op	      0 allocs/op
PASS
ok  	github.com/labstack/echo/v4	5.083s
```

Before the patch (master@75620e6, some commits after v4.1.14):

```
rl@slimboy branch:master# /usr/bin/go test -benchmem -run=^$ github.com/labstack/echo/v4 -bench '^(BenchmarkRouterStaticRoutes|BenchmarkRouterGitHubAPI|BenchmarkRouterParseAPI|BenchmarkRouterGooglePlusAPI)$'
goos: linux
goarch: amd64
pkg: github.com/labstack/echo/v4
BenchmarkRouterStaticRoutes-8    	  93324	    11502 ns/op	      0 B/op	      0 allocs/op
BenchmarkRouterGitHubAPI-8       	  46220	    25976 ns/op	      1 B/op	      0 allocs/op
BenchmarkRouterParseAPI-8        	 276850	     3974 ns/op	      0 B/op	      0 allocs/op
BenchmarkRouterGooglePlusAPI-8   	 193024	     6177 ns/op	      0 B/op	      0 allocs/op
PASS
ok  	github.com/labstack/echo/v4	5.075s
```


Patch:
diff --git a/router.go b/router.go
index 9db9ea9..cb2cc16 100644
--- a/router.go
+++ b/router.go
@@ -376,8 +376,8 @@ func (r *Router) Find(method, path string, c Context) {
 			continue
 		}
 
-		// Param node
 	Param:
+		// Param node
 		if child = cn.findChildByKind(pkind); child != nil {
 			// Issue #378
 			if len(pvalues) == n {
@@ -401,47 +401,58 @@ func (r *Router) Find(method, path string, c Context) {
 			continue
 		}
 
-		// Any node
 	Any:
-		if cn = cn.findChildByKind(akind); cn == nil {
-			if nn != nil {
-				// No next node to go down in routing (issue #954)
-				// Find nearest "any" route going up the routing tree
-				search = ns
-				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 {
+		// Any node
+		if cn = cn.findChildByKind(akind); cn != nil {
+			// If any node is found, use remaining path for pvalues
+			pvalues[len(cn.pnames)-1] = search
+			break
+		}
+
+		// No node found, continue at stored next node
+		// or find nearest "any" route
+		if nn != nil {
+			// No next node to go down in routing (issue #954)
+			// Find nearest "any" route going up the routing tree
+			search = ns
+			np := nn.parent
+			// Consider param route one level up only
+			if cn = nn.findChildByKind(pkind); cn != nil {
+				pos := strings.IndexByte(ns, '/')
+				if pos == -1 {
+					// If no slash is remaining in search string set param value
 					pvalues[len(cn.pnames)-1] = search
 					break
-				} else if cn != nil && strings.IndexByte(ns, '/') != 1 {
-					// If slash is present, it means that this is a parameterized route.
-					cn = cn.parent
+				} else if pos > 0 {
+					// Otherwise continue route processing with restored next node
+					cn = nn
+					nn = nil
+					ns = ""
 					goto Param
 				}
-				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
+			}
+			// No param route found, try to resolve nearest any route
+			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
 		}
-		pvalues[len(cn.pnames)-1] = search
-		break
+		return // Not found
+
 	}
 
 	ctx.handler = cn.findHandler(method)


Test patch:
diff --git a/router_test.go b/router_test.go
index f47225d..92db9d9 100644
--- a/router_test.go
+++ b/router_test.go
@@ -1031,12 +1031,15 @@ func TestRouterParamBacktraceNotFound(t *testing.T) {
 	r.Find(http.MethodGet, "/a", c)
 	assert.Equal(t, "a", c.Param("param1"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/a/foo", c)
 	assert.Equal(t, "a", c.Param("param1"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/a/bar", c)
 	assert.Equal(t, "a", c.Param("param1"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/a/bar/b", c)
 	assert.Equal(t, "a", c.Param("param1"))
 	assert.Equal(t, "b", c.Param("param2"))
@@ -1157,31 +1160,45 @@ func TestRouterParam1466(t *testing.T) {
 	r.Find(http.MethodGet, "/users/ajitem", c)
 	assert.Equal(t, "ajitem", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/sharewithme", c)
 	assert.Equal(t, "sharewithme", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/signup", c)
 	assert.Equal(t, "", c.Param("username"))
 	// Additional assertions for #1479
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/sharewithme/likes/projects/ids", c)
 	assert.Equal(t, "sharewithme", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/ajitem/likes/projects/ids", c)
 	assert.Equal(t, "ajitem", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/sharewithme/profile", c)
 	assert.Equal(t, "sharewithme", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/ajitem/profile", c)
 	assert.Equal(t, "ajitem", c.Param("username"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/sharewithme/uploads/self", c)
 	assert.Equal(t, "sharewithme", c.Param("username"))
 	assert.Equal(t, "self", c.Param("type"))
 
+	c = e.NewContext(nil, nil).(*context)
 	r.Find(http.MethodGet, "/users/ajitem/uploads/self", c)
 	assert.Equal(t, "ajitem", c.Param("username"))
 	assert.Equal(t, "self", c.Param("type"))
+
+	// Issue #1493 - check for routing loop
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/users/tree/free", c)
+	assert.Equal(t, "", c.Param("id"))
+	assert.Equal(t, 0, c.response.Status)
 }
 
 func benchmarkRouterRoutes(b *testing.B, routes []*Route) {