gin 框架作为 Golang 的轻量级 web 框架，包含了路由的 dispatch 功能，本文将重点分析根据设置的请求 path 构建路由前缀树的相关功能。本文分析是基于 gin 1.6.3 版本的代码实现。
1. 路由存储的结构和算法
Engine 是 gin 框架的实例，在 Engine 结构中，trees 是一个数组，针对框架支持的每一种方法，都会创建一个节点。例如 GET、POST 是 trees 的两个元素。
type Engine struct { trees methodTrees}type methodTrees []methodTreetype methodTree struct { method string root *node}
复制代码
1.1 前缀树节点的定义
type node struct { path string indices string children []*node handlers HandlersChain priority uint32 nType nodeType maxParams uint8 wildChild bool fullPath string}
复制代码
方法树是通过节点包含 children 的节点数组的结构形成的，在 node 结构中：
path：表示当前节点的 path；
indices：通常情况下维护了 children 列表的 path 的各首字符组成的 string，之所以是通常情况，是在处理包含通配符的 path 处理中会有一些例外情况；
priority：代表了有几条路由会经过此节点，用于在节点进行排序时使用；
nType：是节点的类型，默认是 static 类型，还包括了 root 类型，对于 path 包含冒号通配符的情况，nType 是 param 类型，对于包含 * 通配符的情况，nType 类型是 catchAll 类型；
wildChild：默认是 false，当 children 是 通配符类型时，wildChild 为 true；
fullPath：是从 root 节点到当前节点的全部 path 部分；如果此节点为终结节点 handlers 为对应的处理链，否则为 nil；maxParams 是当前节点到各个叶子节点的包含的通配符的最大数量。
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) { root := engine.trees.get(method) if root == nil { root = new(node) root.fullPath = "/" engine.trees = append(engine.trees, methodTree{method: method, root: root}) } 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 for end, c := range []byte(path[start+1:]) { switch c { case '/': return path[start : start+1+end], start, valid
case ':', '*': valid = false } } return path[start:], start, valid } 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 { wildcard, i, valid := findWildcard(path) if i < 0 { break }
if !valid { panic("only one wildcard per path segment is allowed, has: '" + wildcard + "' in path '" + fullPath + "'") }
if len(wildcard) < 2 { panic("wildcards must be named with a non-empty name in path '" + fullPath + "'") }
if len(n.children) > 0 { panic("wildcard segment '" + wildcard + "' conflicts with existing children in path '" + fullPath + "'") } if wildcard[0] == ':' { if i > 0 { n.path = path[:i] path = path[i:] } n.wildChild = true child := &node{ nType: param, path: wildcard, maxParams: numParams, fullPath: fullPath, } n.children = []*node{child} n = child n.priority++ numParams--
if len(wildcard) < len(path) { path = path[len(wildcard):]
child := &node{ maxParams: numParams, priority: 1, fullPath: fullPath, } n.children = []*node{child} n = child continue }
n.handlers = handlers return }
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 + "'") }
i-- if path[i] != '/' { panic("no / before catch-all in path '" + fullPath + "'") }
n.path = path[:i]
child := &node{ wildChild: true, nType: catchAll, maxParams: 1, fullPath: fullPath, } if n.maxParams < 1 { n.maxParams = 1 } n.children = []*node{child} n.indices = string('/') n = child n.priority++
child = &node{ path: path[i:], nType: catchAll, maxParams: 1, handlers: handlers, priority: 1, fullPath: fullPath, } n.children = []*node{child}
return }
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++ numParams := countParams(path)
if len(n.path) == 0 && len(n.children) == 0 { n.insertChild(numParams, path, fullPath, handlers) n.nType = root return } parentFullPathIndex := 0
walk: for { if numParams > n.maxParams { n.maxParams = numParams }
i := longestCommonPrefix(path, n.path)
if i < len(n.path) { child := node{ path: n.path[i:], wildChild: n.wildChild, indices: n.indices, children: n.children, handlers: n.handlers, priority: n.priority - 1, fullPath: n.fullPath, }
for _, v := range child.children { if v.maxParams > child.maxParams { child.maxParams = v.maxParams } }
n.children = []*node{&child} n.indices = string([]byte{n.path[i]}) n.path = path[:i] n.handlers = nil n.wildChild = false n.fullPath = fullPath[:parentFullPathIndex+i] }
if i < len(path) { path = path[i:]
if n.wildChild { parentFullPathIndex += len(n.path) n = n.children[0] n.priority++
if numParams > n.maxParams { n.maxParams = numParams } numParams--
if len(path) >= len(n.path) && n.path == path[:len(n.path)] { if 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]
if n.nType == param && c == '/' && len(n.children) == 1 { parentFullPathIndex += len(n.path) n = n.children[0] n.priority++ continue walk }
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 } }
if c != ':' && c != '*' { 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 }
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"】，在查找的时候只会匹配成功第一个路由，但是第二个路由会新增成功。
本文转载自公众号（ID：）。
原文链接：
gin框架之路由前缀树初始化分析
评论