gin框架之路由前缀树初始化分析
gin框架作为Golang的轻量级web框架，包含了路由的dispatch功能，本文将重点分析根据设置的请求path构建路由前缀树的相关功能。本文分析是基于gin 1.6.3版本的代码实现。
1. 路由存储的结构和算法
Engine是gin框架的实例，在Engine结构中，trees 是一个数组，针对框架支持的每一种方法，都会创建一个节点。例如GET、POST是trees的两个元素。
//框架实例包含一个方法数数组
type Engine struct {
trees methodTrees
}
type methodTrees []methodTree
//方法树的定义
type methodTree struct {
method string
root *node
}
1.1 前缀树节点的定义
//path树的节点结构
type node struct {
path string
indices string
children []*node
handlers HandlersChain
priority uint32
nType nodeType
maxParams uint8
wildChild bool
fullPath string
}
方法树是通过节点包含children的节点数组的结构形成的，在node结构中：
1.2 一个普通的路由前缀树
以如下路由配置作为示例：
engine.GET("/admin/model/get", api.GetTemplate)
engine.GET("/admin/model/query", api.QueryTemplate)
engine.POST("/admin/model/set", api.SetTemplate)
engine.POST("/admin/model/upload", api.UploadTemplate)
engine.POST("/admin/model/uploadv2", api.GetTemplateWithSignature)
engine.POST("/admin/model/update", api.UpdateTemplate)
形成的前缀树如下图，左边是GET方法的树，右边是POST方法树。
2. 路由的初始化过程
路由的初始化过程，首先生成绝对path，然后调用Engine的addRoute方法，根据请求的method类型，找到根节点。再调用node的addRoute方法，将path增加到树的合适节点。这个过程是路由初始化过程中构建前缀树的核心流程。
2.1 Engine的addRoute方法
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
//根据调用的method获取对应的前缀树，如果为nil进行初始化
root := engine.trees.get(method)
if root == nil {
root = new(node)
root.fullPath = "/"
engine.trees = append(engine.trees, methodTree{method: method, root: root})
}
//调用node的addRoute方法，其中的path是绝对的path
root.addRoute(path, handlers)
}
2.2 查找wildCard
wildCard是指包含通配符的path段，例如path是 /:id/info 那么id代表了通配符的名字；这个方法用于查找path中是否包含 wildCard；通配支持了path上传参数，但是也增加了path设计的复杂性；如果没有通配符的设计，程序员需要定义每一个path。
func findWildcard(path string) (wildcard string, i int, valid bool) {
for start, c := range []byte(path) {
//如果没有遇到通配符就继续向后查找
if c != ':' && c != '*' {
continue
}
//找到通配符设置valid为true，那么通配符在path的起始位置就是start
valid = true
//从通配符后面继续查找
for end, c := range []byte(path[start+1:]) {
switch c {
//如果遇到下划线，返回wildCard（不包括下划线）、start、true
case '/':
return path[start : start+1+end], start, valid
//如果遇到通配符，valid设置为false
case ':', '*':
valid = false
}
}
//在这个位置返回，遍历完了path，valid为true和false的可能性都有
return path[start:], start, valid
}
//在path里没有找到通配符
return "", -1, false
}
2.3 增加孩子节点
node的addRoute方法分为两步，第一步是根据path和已有的前缀树的匹配，找到剩余的path需要插入的孩子节点的位置，第二步是插入到该节点。当一颗树是空树时，增加第一条path的过程便退化为只有第二步。本小节先分析插入孩子节点的操作。
numParams是path包含的通配符的数量，包含冒号和星号；如果path不包含通配符，直接设置当前节点的path为传入的path；按照通配符的数量逐个处理。
对于通配符为冒号的处理方法，当前节点设置一个path为 wildCard的子节点，设置handler后结束；特别的如果wildCard不是path的全部，将path更新为剩余的部分，n节点指向wildCard的孩子节点继续循环。循环如果后半部分没有通配符到结尾设置path，否则继续处理通配符节点。
对于通配符是星号的处理方法，校验必须是最后一个通配符，星号的前面符号是下划线，生成一个path为空的孩子节点和包含“/*name”的孙子节点。其中孩子节点wildChild设置为true，表明孩子节点是通配符类型。
在冒号通配符的处理过程中，当最后的通配符处理完成，但是还有剩余path的时候，n会更新为空path的child节点，循环处理剩下的path，保证了在调用的节点path为空。
func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
for numParams > 0 {
// Find prefix until first wildcard
wildcard, i, valid := findWildcard(path)
//path中不包含通配符，直接结束对numParams条件的for循环
if i < 0 { // No wildcard found
break
}
// valid为false的两种情况是没有找到通配符（之前已经break） 或者 一个path段有多个通配符
if !valid {
panic("only one wildcard per path segment is allowed, has: '" +
wildcard + "' in path '" + fullPath + "'")
}
// 如果path段只有通配符没有名字 也会panic；由于wildCard一定是以通配符开头的，通配符后面不能直接加下划线
if len(wildcard) < 2 {
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
n.path = path[:i] //设置当前节点的path
path = path[i:] //更新path
}
//孩子节点是通配符，当前节点设置为true
n.wildChild = true
child := &node{
nType: param, //冒号类型的通配符类型
path: wildcard, //设置path为wildCard path包含通配符和名字
maxParams: numParams,
fullPath: fullPath,
}
n.children = []*node{child} //children挂接到当前节点
n = child //n更新为下沉到孩子节点
n.priority++
numParams-- //控制循环的通配符数量减1
// if the path doesn't end with the wildcard, then there
// will be another non-wildcard subpath starting with '/'
//如果wildCard的长度小于path，则说明path中还包含以及path
if len(wildcard) < len(path) {
path = path[len(wildcard):] //重新更新path
child := &node{ //new一个child节点
maxParams: numParams,
priority: 1,
fullPath: fullPath,
}
n.children = []*node{child}
n = child //更新n节点为child节点
continue
}
// Otherwise we're done. Insert the handle in the new leaf
n.handlers = handlers
return
}
//星号通配符类型的处理
//星号通配符必须是path的最后一个通配符 否则会panic
if i+len(wildcard) != len(path) || numParams > 1 {
panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
}
if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
}
//星号通配符的前一个字符，必须为下划线，否则panic
i--
if path[i] != '/' {
panic("no / before catch-all in path '" + fullPath + "'")
}
//当前node的path为星号通配符之前的path
n.path = path[:i]
// First node: catchAll node with empty path
child := &node{ //一个path为空的节点
wildChild: true, //空节点的wildCard为true
nType: catchAll,
maxParams: 1,
fullPath: fullPath,
}
// update maxParams of the parent node
if n.maxParams < 1 {
n.maxParams = 1
}
n.children = []*node{child} //空节点挂接到当前node节点
n.indices = string('/') //node节点 indices设置为 下划线
n = child //node节点下沉为path为空的节点
n.priority++
// second node: node holding the variable
child = &node{
path: path[i:], //path 为从 下划线开始的包含星号通配符的path
nType: catchAll,
maxParams: 1,
handlers: handlers,
priority: 1,
fullPath: fullPath,
}
n.children = []*node{child} //将 包含星号通配符的path节点挂接到空节点下
return
}
// 剩下的path不再包含冒号或者星号
n.path = path
n.handlers = handlers
n.fullPath = fullPath
}
2.4 查找插入节点
当根节点不为空节点时候，需要查找前缀树，找到一个path为空的节点，插入剩余没有与已有树匹配完成的path。countParams 计算path通配符的数量，即冒号和星号的数量；longestCommonPrefix计算path和当前节点的path的共同前缀长度。incrementChildPrio用于对一个节点的孩子节点进行排序。
func (n *node) addRoute(path string, handlers HandlersChain) {
fullPath := path
n.priority++
//计算当前path的通配符的数量
numParams := countParams(path)
// 如果单前树是空树，直接在当前node插入path
if len(n.path) == 0 && len(n.children) == 0 {
n.insertChild(numParams, path, fullPath, handlers)
n.nType = root
return
}
//path的共同前缀位置
parentFullPathIndex := 0
walk:
for {
// Update maxParams of the current node
if numParams > n.maxParams {
n.maxParams = numParams
}
// Find the longest common prefix.
// This also implies that the common prefix contains no ':' or '*'
// since the existing key can't contain those chars.
i := longestCommonPrefix(path, n.path)
// 如果path与当前的node有部分匹配，需要拆分当前的node
if i < len(n.path) {
child := node{
path: n.path[i:], //新的节点包括 node path 没有匹配上的后半部分
wildChild: n.wildChild, //设置与当前节点相同
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1,
fullPath: n.fullPath,
}
// Update maxParams (max of all children)
for _, v := range child.children {
if v.maxParams > child.maxParams {
child.maxParams = v.maxParams
}
}
n.children = []*node{&child} //将后半部分设置为孩子节点
// []byte for proper unicode char conversion, see #65
n.indices = string([]byte{n.path[i]})
n.path = path[:i] //当前节点的path只保持前半部分
n.handlers = nil
n.wildChild = false //后半部分节点一定不包含通配符
n.fullPath = fullPath[:parentFullPathIndex+i] //当前节点的fullPath截取
}
// Make new node a child of this node
//path没有完成匹配，需要继续向下寻找
if i < len(path) {
path = path[i:] //path 更新为没有匹配上的后半部分
//如果当前节点是wildChild节点，那么子节点是通配符节点
if n.wildChild {
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
// Update maxParams of the child node
if numParams > n.maxParams {
n.maxParams = numParams
}
numParams--
// path为通配符的时候必须一致，然后继续向后
if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
// check for longer wildcard, e.g. :name and :names
//path与当前node的path长度相同 或者path有下划线，继续
if len(n.path) >= len(path) || path[len(n.path)] == '/' {
continue walk
}
}
//其他情况会panic
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
//冒号通配符后面的 下划线处理
if n.nType == param && c == '/' && len(n.children) == 1 {
parentFullPathIndex += len(n.path)
n = n.children[0] //更新node节点为孩子节点，继续查找
n.priority++
continue walk
}
// Check if a child with the next path byte exists
//当前节点的某个孩子与path有相同的前缀
for i, max := 0, len(n.indices); i < max; i++ {
if c == n.indices[i] {
parentFullPathIndex += len(n.path)
i = n.incrementChildPrio(i)
n = n.children[i] //更新当前节点为对应的孩子节点，继续查找
continue walk
}
}
// Otherwise insert it
//如果是其他情况，新增一个child节点，并且基于这个child节点，插入剩下的path
if c != ':' && c != '*' {
// []byte for proper unicode char conversion, see #65
n.indices += string([]byte{c})
child := &node{
maxParams: numParams,
fullPath: fullPath,
}
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
}
n.insertChild(numParams, path, fullPath, handlers)
return
}
// Otherwise and handle to current node
if n.handlers != nil {
panic("handlers are already registered for path '" + fullPath + "'")
}
n.handlers = handlers
return
}
}
对上面的查找节点总结，流程如下：
3. 路由初始化的case分析
本小节针对几种比较特殊的情况，做具体分析。前两种情况针对了初始路由信息为空的情况，可以了解到insertChild的过程，第三个case主要用于分析寻找路由的过程。
case1：单条包含两个冒号通配path的一颗前缀树
路由信息： "/user/:name/:age" name和age是通配符的名字；这条路径形成的前缀树如下。
形成的过程是这样的：
查找到当前path /user/:name/:age的wildCard为【:name】,开始的位置是第7个字符
判断wildCard是冒号通配符类型且起始位置大于0，那么path之前的部分【/user/】设置为当前节点（上面树中的第一层节点）的path，然后更新要处理的path为后半部分，即【:name/:age】
设置当前node wildChild为true。
新建孩子节点，path为wilCard【:name】,并且挂接到第一层节点，并将当前节点指向第二层的节点。
判断path是否处理结束，如果处理结束，则可以退出
如果path还没有处理结束，更新path为除去wildCard剩余部分【/:age】,新建孩子节点，挂接到当前的节点（当前还指向第二层）并且设置当前节点为第三层结点
更新后的path为【/:age】，当前的节点为第三层节点，继续从第一步开始处理。再次循环一遍，两个冒号通配符处理完成。
case2：单条包含星号通配path的一颗前缀树
路由信息："/user/:name/*age" ，其中包含一个冒号通配符和一个星号通配符；这条路径形成的前缀树如下：
对于这个路由，形成的过程如下：
查找当前path的wildCard，当前node指向第一层的node，wildCard的查找结果为【:name】位置在第七个
按照上面的处理步骤，处理完wildCard，path更新为【/*age】，当前node指向第三层，进行下一次循环处理
再次查找wildCard结果为【*age】位置是第二个符号，进入insertChild插入星号通配符的逻辑
查看通配符之前的是否是下划线，不是的话报错，将当前的节点path设置为下划线之前的path，这个时候当前节点path为空
生成子节点，即图中的第四层节点，设置节点类型为catchAll，挂接到当前节点，设置单前节点的indices为【/】，当前节点指向第四层节点
新建第五层节点，节点path设置为剩下的path（此处，星号通配符之后不再处理），并挂接到当前当前节点
处理结束
case3：多种path的寻找过程
路由信息：第一条【"/user/info"】，第二条【"/user/info/:name"】，第三条【"/user/info/:name/*age"】
对于上述的路由信息，前缀树的形成过程为：
第一条路由信息，root树为空树并且没有通配符，会在insertChild方法中直接设置当前节点（第一层节点）为path，即在第一层节点设置path为【"/user/info"】
对于第二条路由，先找到与当前节点的最长匹配长度，长度小于单前path长度，重置path为【/:name】且当前节点的wilChild为false，取出剩余path第一个字符进行判断
根据第一个字符逻辑 在当前节点新增孩子（图中第二级孩子），并将当前node指向第二层节点，调用insertChild将【/:name】插入到第二层节点，逻辑同case1，这样形成了第二层和第三层节点。
对于第三条路由，先找到与第一层节点的共同前缀，path更新为【/:name/*age】，取出剩余path第一个字符【/】，【/】在当前的indices里，对孩子节点做优先级调整，并且将当前节点更新下沉到孩子节点,也就是图中第二层节点，继续下一次循环查找。
path【/:name/*age】与第二层节点的共同前缀为【/】，当前第二层节点wildCard为true，这个时候将当前节点指定到孩子节点，即图中第三层节点，并且判断path在下划线之前的部分，即【:name】与三层节点的path相同，然后继续循环查找。
path剩余部分为【:name/*age】，当前node指向第三层节点，继续查找插入位置；共同前缀为【:name】, 更新path变为【/*age】，由于在第二部分处理完以后只有第三层节点。这个时候直接新增节点，进入insertChild逻辑。与case2的后半部分按照相同的逻辑，形成第四五六层节点
4. 使用问题
4.1 处于同层path的路由必须具有相同的通配符以及名字
【/user/:name/:age】和 【/user/*age】的第二段path，第一个是【:name】，第二个是【*age】会报错，这种情况会导致路由匹配失效；在做路由匹配的时候，当发现子节点是wildCard类型时候，会将子节点的path与当前path相同长度的前缀path进行比较，相同会继续比较，不同会报错。
4.2 星号通配符必须是最后一个通配符
在insertChild时候，进入星号通配符逻辑后，会进行检查
if i+len(wildcard) != len(path) || numParams > 1 {
panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
}
4.3 星号通配符的一个bug
对于路由【"/user/info/*name"】 和路由【"/user/info/*name/age"】，在查找的时候只会匹配成功第一个路由，但是第二个路由会新增成功。