Router in Gin¶
Given a URL /api/users/1234/pages, how an HTTP server finds the corresponding handler for it? Router helps to convert the concrete URL to a pattern and its handler.
This blog introduces the routers in Gin framework. In short, Gin uses trie(prefix tree) to maintain the URL-handler mapping.
Gin Router¶
Gin Router Matching Mode¶
Gin router supports to match URLs exactly, wildly and catch all, and the table below shown how the matching works.
+----------+--------------------+------------------------+---------+
| | URL | Pattern | Note |
+==========+====================+========================+=========+
| Exact | /api/users | /api/users | matched |
| | +------------------------+---------+
| | | /api/user | x |
+----------+--------------------+------------------------+---------+
| Wild | /api/users/:id | /api/users/123 | matched |
| | +------------------------+---------+
| | | /api/users/ | x |
| | +------------------------+---------+
| | | /api/users/123/profile | x |
+----------+--------------------+------------------------+---------+
| CatchAll | /api/users/*action | /api/users/123 | matched |
| | +------------------------+---------+
| | | /api/users/ | matched |
| | +------------------------+---------+
| | | /api/users/123/profile | matched |
+----------+--------------------+------------------------+---------+
Construct Patterns Trees in Gin Router¶
Basic Types and Representation¶
Gin router uses the idea of http router to implement its router. Gin router defines a map to store patterns of different methods because the patterns of methods vary.
type methodTree struct {
method string
root *node
}
type Engine struct {
// ignore many fields, modified by blog author
trees methodTrees
}
The basic unit of common prefix is struct node and it has several types as listed below.
The root means this node is the root node of a method under methodTrees. The static refers to the exact match, param refers to the wild match and the catchAll matches as its name means. The node types are generally used for pattern matching when analyzing a concrete URL, but the topic here focus on the tree construction.
Different Nodes for Different Cases¶
Given /api/users, the standard trie uses one node to store its whole content. This idea works well if we support exact matching in HTTP router. However, this strategy breaks when we want to support the wild/catchAll matching because the placeholder is not a normal string but a placeholder.
To analyze them, (param or catchAll) node will be created once * or : is encountered. Registering a single pattern /api/users/:id produces a routing tree looks like this:
Moreover, the methodTrees look like this if /api/users and /api/users/:id are registered.
The routing tree looks like this if we register the following patterns.
- /api/version
- /api/users/:id
- /api/users
- /api/users/:id/messages
- /api/users/:id/messages/*action
(root node)
/api/
├── version ==> /api/version/ (static node)
└── users
└── / ==> /api/users/ (static node)
└── :id ==> /api/users/:id (param node)
└── messages
└── / ==> /api/users/:id/messages (param node)
└── *action
/api/users/:id/messages/*action (catchAll node)
Indices of Children Nodes¶
The trie implementation doesn't use the integer value of character as the index to access the children nodes. Instead, it stores the indices in field indices as a string, so we can loop the string and find the index as well.
type node struct {
path string
indices string
wildChild bool
nType nodeType
priority uint32
// child nodes, at most 1 :param style node at the end of the array
children []*node
handlers HandlersChain
fullPath string
}
Unicode is supported as well by converting unicode to bytes as well, you can see httprouter#65 to learn more.
Resolve Concrete URLs¶
Gin router helps to resolve concrete URLs into pattern and the corresponding handlers and the resolving entry is at the implementation of ServerHTTP interface.
After receiving the request, Gin engine gets the handlers by finding a pattern of the URL via node.getValue. Besides the trie finding functionality, resolving wild and catchAll pattern and redirecting are supported in Gin.
During resolving, it truncates the current path until a slash to extract the parameter value, creates the parameter key-value pair and appends it to parameter result. Due to the natural structure of HTTP URL is well seperated by slash, wild and catchAll matching are easy to implement.
// Find param end (either '/' or path end)
end := 0
for end < len(path) && path[end] != '/' {
end++
}
// Save param value
if params != nil {
// ignore trivial lines, added by blog author xieyuschen
// got next index to insert the new analyzed key-value process
i := len(*value.params)
*value.params = (*value.params)[:i+1]
val := path[:end]
if unescape {
if v, err := url.QueryUnescape(val); err == nil {
val = v
}
}
(*value.params)[i] = Param{
Key: n.path[1:],
Value: val,
}
}