Repository: labstack/echo
Pull request #1512 (2020-02-19 21:59:52)

Fix routing conflict for dynamic routes and static route with common prefix (#1509)
This PR resolves issue #1509 

A routing conflict is caused by radix tree node splits on common prefix of static routes together with a param route on the same level. An additional test has been added for this issue.

This patch actually ensures that routing will continue back up the route tree in that case.

codecov[bot]: # [Codecov](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=h1) Report
> Merging [#1512](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=desc) into [master](https://codecov.io/gh/labstack/echo/commit/f4b5a90ad3d3d1817d4e87d349d699d5ad272110?src=pr&el=desc) will **not change** coverage.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/labstack/echo/pull/1512/graphs/tree.svg?width=650&token=vqnT76l79i&height=150&src=pr)](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=tree)

```diff
@@           Coverage Diff           @@
##           master    #1512   +/-   ##
=======================================
  Coverage   84.54%   84.54%           
=======================================
  Files          27       27           
  Lines        2097     2097           
=======================================
  Hits         1773     1773           
  Misses        211      211           
  Partials      113      113
```


| [Impacted Files](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [router.go](https://codecov.io/gh/labstack/echo/pull/1512/diff?src=pr&el=tree#diff-cm91dGVyLmdv) | `97.13% <100%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=footer). Last update [f4b5a90...4174846](https://codecov.io/gh/labstack/echo/pull/1512?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

lammel: This PR has an impact on the routing performance of ~15% in the worst case.
Numbers are taken using the available test benchmarks on my local system.

Before the patch (master, f4b5a90a):

```
sh# /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-16     	   66543	     17475 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI-16        	   31058	     38630 ns/op	       2 B/op	       0 allocs/op
BenchmarkRouterParseAPI-16         	  174482	      5884 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPI-16    	  123810	      9144 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/labstack/echo/v4	5.274s
```

With this patch applied:

```
sh# /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-16     	   56984	     20068 ns/op	       1 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI-16        	   26817	     44528 ns/op	       2 B/op	       0 allocs/op
BenchmarkRouterParseAPI-16         	  192571	      5751 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPI-16    	  100843	     11578 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/labstack/echo/v4	5.476s
```
lammel: Managed to save some CPU cylces by avoiding backing up the tree for static only route trees (where no next param or any nodes are stored)
```
goos: linux
goarch: amd64
pkg: github.com/labstack/echo/v4
BenchmarkRouterStaticRoutes-16     	   63564	     18446 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI-16        	   27559	     43419 ns/op	       2 B/op	       0 allocs/op
BenchmarkRouterParseAPI-16         	  194587	      5777 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPI-16    	  107343	     11036 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/labstack/echo/v4	5.501s
```

Patch:
diff --git a/router.go b/router.go
index cb2cc16..15a3398 100644
--- a/router.go
+++ b/router.go
@@ -347,7 +347,14 @@ func (r *Router) Find(method, path string, c Context) {
 		if l == pl {
 			// Continue search
 			search = search[l:]
-		} else {
+			// Finish routing if no remaining search and we are on an leaf node
+			if search == "" && (nn == nil || cn.parent == nil || cn.ppath != "") {
+				break
+			}
+		}
+
+		// Attempt to go back up the tree on no matching prefix or no remaining search
+		if l != pl || search == "" {
 			if nn == nil { // Issue #1348
 				return // Not found
 			}
@@ -360,10 +367,6 @@ func (r *Router) Find(method, path string, c Context) {
 			}
 		}
 
-		if search == "" {
-			break
-		}
-
 		// Static node
 		if child = cn.findChild(search[0], skind); child != nil {
 			// Save next


Test patch:
diff --git a/router_test.go b/router_test.go
index 92db9d9..8c27b9f 100644
--- a/router_test.go
+++ b/router_test.go
@@ -567,6 +567,32 @@ func TestRouterParamWithSlash(t *testing.T) {
 	})
 }
 
+// Issue #1509
+func TestRouterParamStaticConflict(t *testing.T) {
+	e := New()
+	r := e.router
+	handler := func(c Context) error {
+		c.Set("path", c.Path())
+		return nil
+	}
+
+	g := e.Group("/g")
+	g.GET("/skills", handler)
+	g.GET("/status", handler)
+	g.GET("/:name", handler)
+
+	c := e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/g/s", c)
+	c.handler(c)
+	assert.Equal(t, "s", c.Param("name"))
+	assert.Equal(t, "/g/:name", c.Get("path"))
+
+	c = e.NewContext(nil, nil).(*context)
+	r.Find(http.MethodGet, "/g/status", c)
+	c.handler(c)
+	assert.Equal(t, "/g/status", c.Get("path"))
+}
+
 func TestRouterMatchAny(t *testing.T) {
 	e := New()
 	r := e.router