Repository: gin-gonic/gin
Pull request #2663 (2021-03-26 15:51:01)

Add mixed param and non-param paths (port of httprouter#329)
This ports a PR I made to httprouter, https://github.com/julienschmidt/httprouter/pull/329.

It adds the ability to have route schemas like `/users/:name` and `/users/groups` without running into conflicts.

From https://github.com/julienschmidt/httprouter/pull/329:
> I updated the search tree, so that non-wildcard paths are resolved _before_ wildcard paths, but both can be valid children. For instance, now you can finally have `/users/roles/:role` and `/users/:id` at the same time without issue.
> 
> First, non-wildcard children are checked for matches. If those fail to match, then it tries the wildcard children routes. For existing compatible route configurations, there should be no (or negligible) performance impact. Many people prefer compact routes and expect a sort of precedence with `httprouter`, that mirrors this behavior.
> 
> This only works for param wildcards of the form `:name` and doesn't change the existing `*`
> 
> One thing to note, because of the prefix tree structure, if the path `/books/fantasy/2007` would matched a  `/books/fantasy/...` route because it takes priority over a `/books/: category/:year` template route, because exact prefixes take priority over wildcard prefixes. I think this is okay and is still a net positive. This can be merely a documentation issue.
> 
> 
> 
> Overall, I think the changes capture a pretty intuitive behavior, has little to no performance impact and is something many people expect from a router. Personally, I use gin and fizz and would love to have this behavior. So I played around with it and want to share and gather your thoughts @julienschmidt.
> 
> 
> **Related issues**
> Looks like there's a lot of issues in this repo, but mostly in Gin. I did my best to capture them, but I'm sure that I'm missing some.
> 
> 
> Partially resolves https://github.com/julienschmidt/httprouter/issues/73 (doesn't work for catch-all wildcards)
> Resolves https://github.com/julienschmidt/httprouter/issues/91
> Resolves https://github.com/julienschmidt/httprouter/issues/183
> Resolves https://github.com/julienschmidt/httprouter/issues/202
> Resolves https://github.com/julienschmidt/httprouter/issues/203
> 
> Resolves https://github.com/gin-gonic/gin/issues/136
> Resolves https://github.com/gin-gonic/gin/issues/205
> Resolves https://github.com/gin-gonic/gin/issues/360
> Resolves https://github.com/gin-gonic/gin/issues/388
> Resolves https://github.com/gin-gonic/gin/issues/574
> Resolves https://github.com/gin-gonic/gin/issues/957
> Resolves https://github.com/gin-gonic/gin/issues/1148
> Resolves https://github.com/gin-gonic/gin/issues/1065
> Resolves https://github.com/gin-gonic/gin/issues/1132
> Resolves https://github.com/gin-gonic/gin/issues/1301
> Resolves https://github.com/gin-gonic/gin/issues/1681 
> Resolves https://github.com/gin-gonic/gin/issues/1730
> Resolves https://github.com/gin-gonic/gin/issues/1756
> Resolves https://github.com/gin-gonic/gin/issues/1990
> Resolves https://github.com/gin-gonic/gin/issues/1993
> Resolves https://github.com/gin-gonic/gin/issues/2005
> Resolves https://github.com/gin-gonic/gin/issues/2016
> Resolves https://github.com/gin-gonic/gin/issues/2062
> Resolves https://github.com/gin-gonic/gin/issues/2195
> Resolves https://github.com/gin-gonic/gin/issues/2289
> Resolves https://github.com/gin-gonic/gin/issues/2416
> Resolves https://github.com/gin-gonic/gin/issues/2465
> Resolves https://github.com/gin-gonic/gin/issues/2537

codecov[bot]: # [Codecov](https://codecov.io/gh/gin-gonic/gin/pull/2663?src=pr&el=h1) Report
> Merging [#2663](https://codecov.io/gh/gin-gonic/gin/pull/2663?src=pr&el=desc) (4dd584f) into [master](https://codecov.io/gh/gin-gonic/gin/commit/ed6f85c478ba00e5168be1f29ffcdc9a983568b8?el=desc) (ed6f85c) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/gin-gonic/gin/pull/2663/graphs/tree.svg?width=650&height=150&src=pr&token=Qpqxhwery8)](https://codecov.io/gh/gin-gonic/gin/pull/2663?src=pr&el=tree)

```diff
@@           Coverage Diff           @@
##           master    #2663   +/-   ##
=======================================
  Coverage   98.64%   98.64%           
=======================================
  Files          41       41           
  Lines        1989     1990    +1     
=======================================
+ Hits         1962     1963    +1     
  Misses         15       15           
  Partials       12       12           
```


| [Impacted Files](https://codecov.io/gh/gin-gonic/gin/pull/2663?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [tree.go](https://codecov.io/gh/gin-gonic/gin/pull/2663/diff?src=pr&el=tree#diff-dHJlZS5nbw==) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/gin-gonic/gin/pull/2663?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/gin-gonic/gin/pull/2663?src=pr&el=footer). Last update [ed6f85c...4dd584f](https://codecov.io/gh/gin-gonic/gin/pull/2663?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

thinkerou: we also should have benchmark test result
rw-access: @thinkerou do you want me to run those benchmarks or is that something you or another maintainer would do?
I'm assuming that it means I would want to fork [go-http-routing-benchmark](https://github.com/gin-gonic/go-http-routing-benchmark) and point it to this branch
appleboy: @rw-access Yes, please fork the repo `go-http-routing-benchmark` and post the final benchmark result (before and after).
rw-access: * [Benchmarks](https://travis-ci.org/github/rw-access/go-http-routing-benchmark/builds/765440126) for **v1.6.3**
* [Benchmarks](https://travis-ci.org/github/rw-access/go-http-routing-benchmark/builds/765444417) for **master** using commit a331dc6a31473b7208c57ec32e14bfcec3062dbb
* [Benchmarks](https://travis-ci.org/github/rw-access/go-http-routing-benchmark/builds/765439756) for **rw-access:port-httprouter-329** using commit 32b29824c24dadfc6b3a2ab86730124e0ed39096
appleboy: @rw-access Thanks for your benchmark report. I make a new report using `benchstat` command.

```
$ benchstat router01.txt router02.txt router03.txt 
name \ time/op    router01.txt  router02.txt  router03.txt
Gin_Param          61.7ns ± 0%   66.9ns ± 0%   66.2ns ± 0%
Gin_Param5          108ns ± 0%    112ns ± 0%    117ns ± 0%
Gin_Param20         291ns ± 0%    287ns ± 0%    307ns ± 0%
Gin_ParamWrite      122ns ± 0%    122ns ± 0%    119ns ± 0%
Gin_GithubStatic   75.7ns ± 0%   81.8ns ± 0%   81.2ns ± 0%
Gin_GithubParam     124ns ± 0%    127ns ± 0%    126ns ± 0%
Gin_GithubAll      27.6µs ± 0%   26.3µs ± 0%   26.8µs ± 0%
Gin_GPlusStatic    60.0ns ± 0%   62.8ns ± 0%   65.8ns ± 0%
Gin_GPlusParam     78.1ns ± 0%   84.2ns ± 0%   83.8ns ± 0%
Gin_GPlus2Params    101ns ± 0%    113ns ± 0%    105ns ± 0%
Gin_GPlusAll       1.11µs ± 0%   1.25µs ± 0%   1.14µs ± 0%
Gin_ParseStatic    63.6ns ± 0%   65.3ns ± 0%   63.5ns ± 0%
Gin_ParseParam     73.8ns ± 0%   71.2ns ± 0%   70.5ns ± 0%
Gin_Parse2Params   83.7ns ± 0%   83.7ns ± 0%   84.3ns ± 0%
Gin_ParseAll       1.94µs ± 0%   1.99µs ± 0%   1.98µs ± 0%
Gin_StaticAll      19.1µs ± 0%   19.5µs ± 0%   18.4µs ± 0%

name \ alloc/op   router01.txt  router02.txt  router03.txt
Gin_Param           0.00B         0.00B         0.00B     
Gin_Param5          0.00B         0.00B         0.00B     
Gin_Param20         0.00B         0.00B         0.00B     
Gin_ParamWrite      0.00B         0.00B         0.00B     
Gin_GithubStatic    0.00B         0.00B         0.00B     
Gin_GithubParam     0.00B         0.00B         0.00B     
Gin_GithubAll       0.00B         0.00B         0.00B     
Gin_GPlusStatic     0.00B         0.00B         0.00B     
Gin_GPlusParam      0.00B         0.00B         0.00B     
Gin_GPlus2Params    0.00B         0.00B         0.00B     
Gin_GPlusAll        0.00B         0.00B         0.00B     
Gin_ParseStatic     0.00B         0.00B         0.00B     
Gin_ParseParam      0.00B         0.00B         0.00B     
Gin_Parse2Params    0.00B         0.00B         0.00B     
Gin_ParseAll        0.00B         0.00B         0.00B     
Gin_StaticAll       0.00B         0.00B         0.00B     

name \ allocs/op  router01.txt  router02.txt  router03.txt
Gin_Param            0.00          0.00          0.00     
Gin_Param5           0.00          0.00          0.00     
Gin_Param20          0.00          0.00          0.00     
Gin_ParamWrite       0.00          0.00          0.00     
Gin_GithubStatic     0.00          0.00          0.00     
Gin_GithubParam      0.00          0.00          0.00     
Gin_GithubAll        0.00          0.00          0.00     
Gin_GPlusStatic      0.00          0.00          0.00     
Gin_GPlusParam       0.00          0.00          0.00     
Gin_GPlus2Params     0.00          0.00          0.00     
Gin_GPlusAll         0.00          0.00          0.00     
Gin_ParseStatic      0.00          0.00          0.00     
Gin_ParseParam       0.00          0.00          0.00     
Gin_Parse2Params     0.00          0.00          0.00     
Gin_ParseAll         0.00          0.00          0.00     
Gin_StaticAll        0.00          0.00          0.00
```

* router01: for v1.6.3
* router02: for **master** using commit a331dc6
* router03: Benchmarks for **rw-access:port-httprouter-329** using commit 32b29824c24dadfc6b3a2ab86730124e0ed39096

Patch:
diff --git a/AUTHORS.md b/AUTHORS.md
index a477611..c634e6b 100644
--- a/AUTHORS.md
+++ b/AUTHORS.md
@@ -190,6 +190,8 @@ People and companies, who have contributed, in alphabetical order.
 **@rogierlommers (Rogier Lommers)**
 - Add updated static serve example
 
+**@rw-access (Ross Wolf)**
+- Added support to mix exact and param routes
 
 **@se77en (Damon Zhao)**
 - Improve color logging
diff --git a/CHANGELOG.md b/CHANGELOG.md
index ddf30e1..a56d4ff 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,5 +1,11 @@
 # Gin ChangeLog
 
+## Gin v1.7.0
+
+### ENHANCEMENTS
+
+* Support params and exact routes without creating conflicts [#2663](https://github.com/gin-gonic/gin/pull/2663)
+
 ## Gin v1.6.3
 
 ### ENHANCEMENTS
diff --git a/README.md b/README.md
index 119f945..eb84031 100644
--- a/README.md
+++ b/README.md
@@ -243,6 +243,13 @@ func main() {
 		c.FullPath() == "/user/:name/*action" // true
 	})
 
+	// This handler will add a new router for /user/groups.
+	// Exact routes are resolved before param routes, regardless of the order they were defined.
+	// Routes starting with /user/groups are never interpreted as /user/:name/... routes
+	router.GET("/user/groups", func(c *gin.Context) {
+		c.String(http.StatusOK, "The available groups are [...]", name)
+	})
+
 	router.Run(":8080")
 }
 ```
diff --git a/tree.go b/tree.go
index 74e07e8..ca753e6 100644
--- a/tree.go
+++ b/tree.go
@@ -80,6 +80,16 @@ func longestCommonPrefix(a, b string) int {
 	return i
 }
 
+// addChild will add a child node, keeping wildcards at the end
+func (n *node) addChild(child *node) {
+	if n.wildChild && len(n.children) > 0 {
+		wildcardChild := n.children[len(n.children)-1]
+		n.children = append(n.children[:len(n.children)-1], child, wildcardChild)
+	} else {
+		n.children = append(n.children, child)
+	}
+}
+
 func countParams(path string) uint16 {
 	var n uint16
 	s := bytesconv.StringToBytes(path)
@@ -103,7 +113,7 @@ type node struct {
 	wildChild bool
 	nType     nodeType
 	priority  uint32
-	children  []*node
+	children  []*node // child nodes, at most 1 :param style node at the end of the array
 	handlers  HandlersChain
 	fullPath  string
 }
@@ -177,36 +187,9 @@ walk:
 		// Make new node a child of this node
 		if i < len(path) {
 			path = path[i:]
-
-			if n.wildChild {
-				parentFullPathIndex += len(n.path)
-				n = n.children[0]
-				n.priority++
-
-				// Check if the wildcard matches
-				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
-					// Adding a child to a catchAll is not possible
-					n.nType != catchAll &&
-					// Check for longer wildcard, e.g. :name and :names
-					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
-					continue walk
-				}
-
-				pathSeg := path
-				if n.nType != catchAll {
-					pathSeg = strings.SplitN(path, "/", 2)[0]
-				}
-				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
-				panic("'" + pathSeg +
-					"' in new path '" + fullPath +
-					"' conflicts with existing wildcard '" + n.path +
-					"' in existing prefix '" + prefix +
-					"'")
-			}
-
 			c := path[0]
 
-			// slash after param
+			// '/' after param
 			if n.nType == param && c == '/' && len(n.children) == 1 {
 				parentFullPathIndex += len(n.path)
 				n = n.children[0]
@@ -225,21 +208,47 @@ walk:
 			}
 
 			// Otherwise insert it
-			if c != ':' && c != '*' {
+			if c != ':' && c != '*' && n.nType != catchAll {
 				// []byte for proper unicode char conversion, see #65
 				n.indices += bytesconv.BytesToString([]byte{c})
 				child := &node{
 					fullPath: fullPath,
 				}
-				n.children = append(n.children, child)
+				n.addChild(child)
 				n.incrementChildPrio(len(n.indices) - 1)
 				n = child
+			} else if n.wildChild {
+				// inserting a wildcard node, need to check if it conflicts with the existing wildcard
+				n = n.children[len(n.children)-1]
+				n.priority++
+
+				// Check if the wildcard matches
+				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
+					// Adding a child to a catchAll is not possible
+					n.nType != catchAll &&
+					// Check for longer wildcard, e.g. :name and :names
+					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
+					continue walk
+				}
+
+				// Wildcard conflict
+				pathSeg := path
+				if n.nType != catchAll {
+					pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
+				}
+				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
+				panic("'" + pathSeg +
+					"' in new path '" + fullPath +
+					"' conflicts with existing wildcard '" + n.path +
+					"' in existing prefix '" + prefix +
+					"'")
 			}
+
 			n.insertChild(path, fullPath, handlers)
 			return
 		}
 
-		// Otherwise and handle to current node
+		// Otherwise add handle to current node
 		if n.handlers != nil {
 			panic("handlers are already registered for path '" + fullPath + "'")
 		}
@@ -293,13 +302,6 @@ func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
 			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
 		}
 
-		// Check if this node has existing children which would be
-		// unreachable if we insert the wildcard here
-		if len(n.children) > 0 {
-			panic("wildcard segment '" + wildcard +
-				"' conflicts with existing children in path '" + fullPath + "'")
-		}
-
 		if wildcard[0] == ':' { // param
 			if i > 0 {
 				// Insert prefix before the current wildcard
@@ -307,13 +309,13 @@ func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
 				path = path[i:]
 			}
 
-			n.wildChild = true
 			child := &node{
 				nType:    param,
 				path:     wildcard,
 				fullPath: fullPath,
 			}
-			n.children = []*node{child}
+			n.addChild(child)
+			n.wildChild = true
 			n = child
 			n.priority++
 
@@ -326,7 +328,7 @@ func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
 					priority: 1,
 					fullPath: fullPath,
 				}
-				n.children = []*node{child}
+				n.addChild(child)
 				n = child
 				continue
 			}
@@ -360,7 +362,7 @@ func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
 			fullPath:  fullPath,
 		}
 
-		n.children = []*node{child}
+		n.addChild(child)
 		n.indices = string('/')
 		n = child
 		n.priority++
@@ -404,18 +406,18 @@ walk: // Outer loop for walking the tree
 		if len(path) > len(prefix) {
 			if path[:len(prefix)] == prefix {
 				path = path[len(prefix):]
-				// If this node does not have a wildcard (param or catchAll)
-				// child, we can just look up the next child node and continue
-				// to walk down the tree
-				if !n.wildChild {
-					idxc := path[0]
-					for i, c := range []byte(n.indices) {
-						if c == idxc {
-							n = n.children[i]
-							continue walk
-						}
+
+				// Try all the non-wildcard children first by matching the indices
+				idxc := path[0]
+				for i, c := range []byte(n.indices) {
+					if c == idxc {
+						n = n.children[i]
+						continue walk
 					}
+				}
 
+				// If there is no wildcard pattern, recommend a redirection
+				if !n.wildChild {
 					// Nothing found.
 					// We can recommend to redirect to the same URL without a
 					// trailing slash if a leaf exists for that path.
@@ -423,8 +425,9 @@ walk: // Outer loop for walking the tree
 					return
 				}
 
-				// Handle wildcard child
-				n = n.children[0]
+				// Handle wildcard child, which is always at the end of the array
+				n = n.children[len(n.children)-1]
+
 				switch n.nType {
 				case param:
 					// Find param end (either '/' or path end)


Test patch:
diff --git a/tree_test.go b/tree_test.go
index 1cb4f55..d7c4fb0 100644
--- a/tree_test.go
+++ b/tree_test.go
@@ -137,6 +137,8 @@ func TestTreeWildcard(t *testing.T) {
 		"/",
 		"/cmd/:tool/:sub",
 		"/cmd/:tool/",
+		"/cmd/whoami",
+		"/cmd/whoami/root/",
 		"/src/*filepath",
 		"/search/",
 		"/search/:query",
@@ -155,8 +157,12 @@ func TestTreeWildcard(t *testing.T) {
 
 	checkRequests(t, tree, testRequests{
 		{"/", false, "/", nil},
-		{"/cmd/test/", false, "/cmd/:tool/", Params{Param{Key: "tool", Value: "test"}}},
-		{"/cmd/test", true, "", Params{Param{Key: "tool", Value: "test"}}},
+		{"/cmd/test", true, "/cmd/:tool/", Params{Param{"tool", "test"}}},
+		{"/cmd/test/", false, "/cmd/:tool/", Params{Param{"tool", "test"}}},
+		{"/cmd/whoami", false, "/cmd/whoami", nil},
+		{"/cmd/whoami/", true, "/cmd/whoami", nil},
+		{"/cmd/whoami/root/", false, "/cmd/whoami/root/", nil},
+		{"/cmd/whoami/root", true, "/cmd/whoami/root/", nil},
 		{"/cmd/test/3", false, "/cmd/:tool/:sub", Params{Param{Key: "tool", Value: "test"}, Param{Key: "sub", Value: "3"}}},
 		{"/src/", false, "/src/*filepath", Params{Param{Key: "filepath", Value: "/"}}},
 		{"/src/some/file.png", false, "/src/*filepath", Params{Param{Key: "filepath", Value: "/some/file.png"}}},
@@ -245,20 +251,38 @@ func testRoutes(t *testing.T, routes []testRoute) {
 func TestTreeWildcardConflict(t *testing.T) {
 	routes := []testRoute{
 		{"/cmd/:tool/:sub", false},
-		{"/cmd/vet", true},
+		{"/cmd/vet", false},
+		{"/foo/bar", false},
+		{"/foo/:name", false},
+		{"/foo/:names", true},
+		{"/cmd/*path", true},
+		{"/cmd/:badvar", true},
+		{"/cmd/:tool/names", false},
+		{"/cmd/:tool/:badsub/details", true},
 		{"/src/*filepath", false},
+		{"/src/:file", true},
+		{"/src/static.json", true},
 		{"/src/*filepathx", true},
 		{"/src/", true},
+		{"/src/foo/bar", true},
 		{"/src1/", false},
 		{"/src1/*filepath", true},
 		{"/src2*filepath", true},
+		{"/src2/*filepath", false},
 		{"/search/:query", false},
-		{"/search/invalid", true},
+		{"/search/valid", false},
 		{"/user_:name", false},
-		{"/user_x", true},
+		{"/user_x", false},
 		{"/user_:name", false},
 		{"/id:id", false},
-		{"/id/:id", true},
+		{"/id/:id", false},
+	}
+	testRoutes(t, routes)
+}
+
+func TestCatchAllAfterSlash(t *testing.T) {
+	routes := []testRoute{
+		{"/non-leading-*catchall", true},
 	}
 	testRoutes(t, routes)
 }
@@ -266,14 +290,17 @@ func TestTreeWildcardConflict(t *testing.T) {
 func TestTreeChildConflict(t *testing.T) {
 	routes := []testRoute{
 		{"/cmd/vet", false},
-		{"/cmd/:tool/:sub", true},
+		{"/cmd/:tool", false},
+		{"/cmd/:tool/:sub", false},
+		{"/cmd/:tool/misc", false},
+		{"/cmd/:tool/:othersub", true},
 		{"/src/AUTHORS", false},
 		{"/src/*filepath", true},
 		{"/user_x", false},
-		{"/user_:name", true},
+		{"/user_:name", false},
 		{"/id/:id", false},
-		{"/id:id", true},
-		{"/:id", true},
+		{"/id:id", false},
+		{"/:id", false},
 		{"/*filepath", true},
 	}
 	testRoutes(t, routes)
@@ -688,8 +715,7 @@ func TestTreeWildcardConflictEx(t *testing.T) {
 		{"/who/are/foo", "/foo", `/who/are/\*you`, `/\*you`},
 		{"/who/are/foo/", "/foo/", `/who/are/\*you`, `/\*you`},
 		{"/who/are/foo/bar", "/foo/bar", `/who/are/\*you`, `/\*you`},
-		{"/conxxx", "xxx", `/con:tact`, `:tact`},
-		{"/conooo/xxx", "ooo", `/con:tact`, `:tact`},
+		{"/con:nection", ":nection", `/con:tact`, `:tact`},
 	}
 
 	for _, conflict := range conflicts {