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结构中：

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) {
   //根据调用的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"】，在查找的时候只会匹配成功第一个路由，但是第二个路由会新增成功。

本文转载自公众号（ID：）。

原文链接：

gin框架之路由前缀树初始化分析

创作场景

gin 框架之路由前缀树初始化分析