1. 前言

net/http的ServeMux提供了一个路由分发功能，但是功能比较简单，主要有以下几点缺陷:

1. 注册路由处理函数时不区分http方法
2. 在有大量有相同前缀path情况下空间率不高

httprouter为每一种http方法维护一颗路由树，节省空间又更加高效，仓库路径: https://github.com/julienschmidt/httprouter

2. httprouter使用

package main

import (
    "fmt"
    "github.com/julienschmidt/httprouter"
    "net/http"
)

func handler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()  // 创建一个Router实例
    r.GET("/home/index", handler)
    http.ListenAndServe(addr, r)
}

func main() {
    startHTTPServer(":10092")
}

Router实现了ServeHTTP(w, r)方法，所以也是Handler类型，上面代码只做个两件事:

1. 创建一个Router实例，并注册/home/index的处理函数
2. 启动http服务器，并传入Router实例

因为传入了Router实例，所以最终处理http请求的将是Router的ServeHTTP(w, r)方法，先来看看Router类型定义:

// Router is a http.Handler which can be used to dispatch requests to different
// handler functions via configurable routes
type Router struct {
    // Router把GET/POST/PUT等方法的路由挂在独立的一颗radix(基数数)上
    // key即为http方法如GET/POST/PUT...
    // node即为radix树的根节点
    trees map[string]*node

    // Enables automatic redirection if the current route can't be matched but a
    // handler for the path with (without) the trailing slash exists.
    // For example if /foo/ is requested but a route only exists for /foo, the
    // client is redirected to /foo with http status code 301 for GET requests
    // and 307 for all other request methods.
    // 如果/home匹配不成功，/home/能匹配，或者/home/匹配不成功，但是/home能匹配
    // 在该值为true的情况下可以把/home重定向到/home/或者把/home/重定向到/home
    RedirectTrailingSlash bool

    // If enabled, the router tries to fix the current request path, if no
    // handle is registered for it.
    // First superfluous path elements like ../ or // are removed.
    // Afterwards the router does a case-insensitive lookup of the cleaned path.
    // If a handle can be found for this route, the router makes a redirection
    // to the corrected path with status code 301 for GET requests and 307 for
    // all other request methods.
    // For example /FOO and /..//Foo could be redirected to /foo.
    // RedirectTrailingSlash is independent of this option.
    // 如果path匹配不成功，在该值为true情况下可以把path先重新清理再重定向，如:/home../
    // 在清理之后就变成了/，如果/home../匹配不成功，在该值为true时重定向到/
    RedirectFixedPath bool

    // If enabled, the router checks if another method is allowed for the
    // current route, if the current request can not be routed.
    // If this is the case, the request is answered with 'Method Not Allowed'
    // and HTTP status code 405.
    // If no other Method is allowed, the request is delegated to the NotFound
    // handler.
    // 该选项配合下面MethodNotAllowed选项一起使用，如果请求不能被route则调用MethodNotAllowed
    // 方法处理
    HandleMethodNotAllowed bool

    // If enabled, the router automatically replies to OPTIONS requests.
    // Custom OPTIONS handlers take priority over automatic replies.
    // 该选项配合GlobalOPTIONS选项一起使用，如果该选项为true，则options请求优先
    // 使用GlobalOPTIONS方法处理
    HandleOPTIONS bool

    // An optional http.Handler that is called on automatic OPTIONS requests.
    // The handler is only called if HandleOPTIONS is true and no OPTIONS
    // handler for the specific path was set.
    // The "Allowed" header is set before calling the handler.
    GlobalOPTIONS http.Handler

    // Cached value of global (*) allowed methods
    globalAllowed string

    // Configurable http.Handler which is called when no matching route is
    // found. If it is not set, http.NotFound is used.
    NotFound http.Handler

    // Configurable http.Handler which is called when a request
    // cannot be routed and HandleMethodNotAllowed is true.
    // If it is not set, http.Error with http.StatusMethodNotAllowed is used.
    // The "Allow" header with allowed request methods is set before the handler
    // is called.
    MethodNotAllowed http.Handler

    // Function to handle panics recovered from http handlers.
    // It should be used to generate a error page and return the http error code
    // 500 (Internal Server Error).
    // The handler can be used to keep your server from crashing because of
    // unrecovered panics.
    // 如果设置了该方法，则http服务器pandic时调用该方法
    PanicHandler func(http.ResponseWriter, *http.Request, interface{})
}

上面最重要的就是trees成员，trees图示:

image.png

接下来还是从示例代码跟踪到httprouter里查看相应实现:

2.1 GET()方法

r.GET("/home/index", handler)

// GET is a shortcut for router.Handle(http.MethodGet, path, handle)
func (r *Router) GET(path string, handle Handle) {
    r.Handle(http.MethodGet, path, handle)
}
// Handle registers a new request handle with the given path and method.
//
// For GET, POST, PUT, PATCH and DELETE requests the respective shortcut
// functions can be used.
//
// This function is intended for bulk loading and to allow the usage of less
// frequently used, non-standardized or custom methods (e.g. for internal
// communication with a proxy).
func (r *Router) Handle(method, path string, handle Handle) {
    if len(path) < 1 || path[0] != '/' {
        panic("path must begin with '/' in path '" + path + "'")
    }

    if r.trees == nil {
        r.trees = make(map[string]*node)
    }

    root := r.trees[method]
    if root == nil {
        root = new(node)
        r.trees[method] = root

        r.globalAllowed = r.allowed("*", "")
    }

    root.addRoute(path, handle)
}

可以看到不管是GET/PUT/POST/HEAD等，内部都是调用Router的Handle方法，GET方法主要做了如下几件事:

1. 如果trees为nil则创建它，如果GET方法对应的radix树根节点不存在，则创建它
2. 把path和handler添加到路由树中

其他http方法类似，只是把path，handler添加到各自独立的路由树结构中，我们知道http服务器最终是通过注册Handler来处理http请求的(如果传入的Handler为nil则用DefaultServeMux)，这里我们传入的是Router实例，接下来我们看它的ServeHTTP(w, r)方法实现。

2.2 ServeHTTP(w, r)

// ServeHTTP makes the router implement the http.Handler interface.
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
    // 如果设置PanicHandler则在defer中会调用该函数
    if r.PanicHandler != nil {
        defer r.recv(w, req)
    }

    path := req.URL.Path

    // 通过方法找到radix树根节点
    if root := r.trees[req.Method]; root != nil {
        // 在路由树中找到path对应的handler，用它来处理http请求，正常的话这里就返回了
        // 剩下的就是错误处理,注意返回的tsr用来提示对path的请求是否可以满足重定向
        // 满足为true，不满足为false
        if handle, ps, tsr := root.getValue(path); handle != nil {
            handle(w, req, ps)
            return
        } else if req.Method != http.MethodConnect && path != "/" {
            // 判断是否需要重定向，GET/POST重定向分别用301, 307
            code := 301 // Permanent redirect, request with GET method
            if req.Method != http.MethodGet {
                // Temporary redirect, request with same method
                // As of Go 1.3, Go does not support status code 308.
                code = 307
            }
            // 判断是需要在path添加`/`还是去掉`/`，并重定向
            if tsr && r.RedirectTrailingSlash {
                if len(path) > 1 && path[len(path)-1] == '/' {
                    req.URL.Path = path[:len(path)-1]
                } else {
                    req.URL.Path = path + "/"
                }
                http.Redirect(w, req, req.URL.String(), code)
                return
            }

            // Try to fix the request path
            // 清理path，并在能匹配path情况下重定向
            if r.RedirectFixedPath {
                fixedPath, found := root.findCaseInsensitivePath(
                    CleanPath(path),
                    r.RedirectTrailingSlash,
                )
                if found {
                    req.URL.Path = string(fixedPath)
                    http.Redirect(w, req, req.URL.String(), code)
                    return
                }
            }
        }
    }

    // 以下处理OPTIONS方法、路由不能匹配(NotFound)、路由不允许(MethodNotAllowed)
    // 有自定义handler则优先使用自定义handler处理，没有的话默认处理
    if req.Method == http.MethodOptions && r.HandleOPTIONS {
        // Handle OPTIONS requests
        if allow := r.allowed(path, http.MethodOptions); allow != "" {
            w.Header().Set("Allow", allow)
            if r.GlobalOPTIONS != nil {
                r.GlobalOPTIONS.ServeHTTP(w, req)
            }
            return
        }
    } else if r.HandleMethodNotAllowed { // Handle 405
        if allow := r.allowed(path, req.Method); allow != "" {
            w.Header().Set("Allow", allow)
            if r.MethodNotAllowed != nil {
                r.MethodNotAllowed.ServeHTTP(w, req)
            } else {
                http.Error(w,
                    http.StatusText(http.StatusMethodNotAllowed),
                    http.StatusMethodNotAllowed,
                )
            }
            return
        }
    }

    // Handle 404
    if r.NotFound != nil {
        r.NotFound.ServeHTTP(w, req)
    } else {
        http.NotFound(w, req)
    }
}

Router的ServeHTTP(w, r)比较简单，主要做如下处理:

1. 根据http请求方法找到路由树(radix)，并通过path找到对应handler
2. 如果path匹配不成功，则判断是否需要重定向
3. 如果path匹配不成功，也不满足重定向，则进行错误处理(NotFound或MethodNotAllowed)

可以看到httprouter结构非常简单，注册handler到http方法对应的路由树中(radix)，在处理http请求时从方法对应的路由树上查找handler，接下来通过查看代码了解路由树是怎么实现的。

3. 路由树

先来看下节点结构:

type node struct {
    path      string  // 节点路径
    wildChild bool  // 子节点是否是`:`或`*`通配节点
    nType     nodeType  // 节点类型
    maxParams uint8  // 最大参数
    priority  uint32  // 优先级
    indices   string  // 子节点首字母组成的字符串，方便查找子节点
    children  []*node  // 子节点
    handle    Handle  // 处理函数
}

3.1 insertChild

先来分析insertChild函数，因为addRoute(path,handler)在空节点插入时调用它:

func (n *node) insertChild(numParams uint8, path, fullPath string, handle Handle) {
    var offset int // already handled bytes of the path

    // find prefix until first wildcard (beginning with ':'' or '*'')
    // 遍历path，找到其中的通配符 `:` or `*`
    for i, max := 0, len(path); numParams > 0; i++ {
        c := path[i]
        if c != ':' && c != '*' {
            continue
        }

        // find wildcard end (either '/' or path end)
        // 通配符必须有名称，并且名称中不能包含`:` or `*`
        // 比如/home/first:name,这里name为统配符名称，该名称不能为na*me，na:me等
        // 这里遍历到path末尾或者遍历到下一个segment(以/分割)
        end := i + 1
        for end < max && path[end] != '/' {
            switch path[end] {
            // the wildcard name must not contain ':' and '*'
            case ':', '*':
                panic("only one wildcard per path segment is allowed, has: '" +
                    path[i:] + "' in path '" + fullPath + "'")
            default:
                end++
            }
        }

        // check if this Node existing children which would be
        // unreachable if we insert the wildcard here
        // 判断是否和已有的path冲突，比如/home/first:name和/home/firstone就会冲突
        // 其实本质上是如果有wildcard子节点，那么就只能有唯一一个子节点(就是wildcard节点)
        if len(n.children) > 0 {
            panic("wildcard route '" + path[i:end] +
                "' conflicts with existing children in path '" + fullPath + "'")
        }

        // check if the wildcard has a name
        // 通配符必须有名字，意味着end在上面for{}必须有变动，所以end - i >= 2
        if end-i < 2 {
            panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
        }

        // 对通配符`:`的处理
        if c == ':' { // param
            // split path at the beginning of the wildcard
            // 截取通配符`:`之前的路径，比如/home/first:name，截取的是/home/first
            if i > 0 {
                n.path = path[offset:i]
                offset = i
            }

            // 创建子节点，并设置当前节点的wildChild为true，表示添加的是一个包含通配符
            // 的子节点，添加子节点后把n替换成子节点地址
            child := &node{
                nType:     param,
                maxParams: numParams,
            }
            n.children = []*node{child}
            n.wildChild = true
            n = child
            n.priority++
            numParams--

            // if the path doesn't end with the wildcard, then there
            // will be another non-wildcard subpath starting with '/'
            // 如果通配符不是path的最后一个segment，则更新子节点路径，比如:/home/first:name/sub
            // 则把子节点path设置为`:name`,注意这里没有/字符
            // 如果通配符就是path的最后一个segment，如:/home/first:name，则这里会跳出for{}循环，
            // 那么该通配符子节点会变成叶子节点，直接存放path和handler，在这个函数最后两行实现
            if end < max {
                n.path = path[offset:end]
                offset = end

                child := &node{
                    maxParams: numParams,
                    priority:  1,
                }
                n.children = []*node{child}
                n = child
            }

        } else { // catchAll
            // 找到`*`通配符，该通配符必须是在path的最后一个segment
            if end != max || numParams > 1 {
                panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
            }
            // `*`通配符segment不能以/结尾，比如：/*name/是错误的
            // 但其实这种情况在上面的判断中就会panic，感觉是多余的
            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 + "'")
            }

            // currently fixed width 1 for '/'
            // 通配符`*`前面必须是`/`,如：/home/*name, 但是不能为/home/na*me(通配符:可以)
            i--
            if path[i] != '/' {
                panic("no / before catch-all in path '" + fullPath + "'")
            }
            // 注意上面i--操作，offset定位到`*`前的/
            // 如果path是/home/first:name/sub/*information， 则
            // 节点path为/sub,注意不是/sub/
            n.path = path[offset:i]
            // first node: catchAll node with empty path
            // 创建一个path为空的子节点， 注意该节点的wildChild=true，标识它有一个wildcard的子节点
            // 同时又把n设置为子节点的地址
            child := &node{
                wildChild: true,
                nType:     catchAll,
                maxParams: 1,
            }
            // update maxParams of the parent node
            if n.maxParams < 1 {
                n.maxParams = 1
            }
            n.children = []*node{child}
            // 这里其实就是赋值/, gin里就直接给赋值/了
            n.indices = string(path[i])
            n = child
            n.priority++

            // second node: node holding the variable
            // 再添加一个子节点，因为`*`必须是path的最后一个segment，所以它必定为叶子节点，叶子节点中保存
            // path和handler,如果path=/home/first:name/sub/*information，则该节点的path=/*information
            // 因为是叶子节点，保存完path和handler后可以直接返回
            child = &node{
                path:      path[i:],
                nType:     catchAll,
                maxParams: 1,
                handle:    handle,
                priority:  1,
            }
            n.children = []*node{child}

            return
        }
    }

    // insert remaining path part and handle to the leaf
    // 把剩余的path和handler保存在叶子节点中
    // 如path=/home/:name，这里path=:name
    n.path = path[offset:]
    n.handle = handle
}

注册如下处理函数，再画出路由树:

func myHandler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()
    r.GET("/home/first:name/sub/*information", myHandler)
    http.ListenAndServe(addr, r)
}

添加了个DumpTree方法，可以用来遍历树:

func DumpTree(r *Router, method string) {
    if r.trees != nil && r.trees[method] != nil {
        r.trees[method].printNode()
    }
}

func (n *node) printNode() {
    if n != nil {
        fmt.Println(n)
        for _, v := range n.children {
            v.printNode()
        }
    }
}

func (n *node) String() string {
    buf := bytes.Buffer{}
    switch n.nType {
    case static:
        buf.WriteString("nodeType: [" + "default" + "]\n")
    case root:
        buf.WriteString("nodeType: [" + "root" + "]\n")
    case param:
        buf.WriteString("nodeType: [" + "param" + "]\n")
    case catchAll:
        buf.WriteString("nodeType: [" + "catchAll" + "]\n")
    default:
        buf.WriteString("nodeType: [" + "unknow" + "]\n")
    }
    buf.WriteString("path: [" + n.path + "]\n")
    buf.WriteString("priority: [" + strconv.Itoa(int(n.priority)) + "]\n")
    buf.WriteString("indices: [" + n.indices + "]\n")
    if n.wildChild {
        buf.WriteString("wildChild: [" + "true" + "]\n")
    } else {
        buf.WriteString("wildChild: [" + "false" + "]\n")
    }
    if n.handle != nil {
        buf.WriteString("handler: [" + runtime.FuncForPC(reflect.ValueOf(n.handle).Pointer()).Name() + "]\n")
    } else {
        buf.WriteString("handler: [" + "nil" + "]\n")
    }

    return buf.String()
}

添加/home/first:name/sub/*information路由树

3.2 addRoute

添加路由到路由树可能会知道以存在的节点分拆，新节点添加，路由冲突检测，接下来看代码如何实现:

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handle Handle) {
    fullPath := path
    n.priority++
    numParams := countParams(path)

    // non-empty tree
    // 如果路由树是空的，则直接走insertChild流程
    // 节点的path不为空则路由树肯定不为空
    // 如果第一次添加的path=/*information，则路由树根节点path=""，但子节点不为nil
    if len(n.path) > 0 || len(n.children) > 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 := 0
            max := min(len(path), len(n.path))
            for i < max && path[i] == n.path[i] {
                i++
            }

            // 说明需要分拆节点，提取公共的节点作为父节点
            // 节点path剩余的部门放到新建的节点中，新建的
            // 节点除了nodeType，其他属性和原先节点一样
            // Split edge
            if i < len(n.path) {
                child := node{
                    path:      n.path[i:],
                    wildChild: n.wildChild,
                    nType:     static,
                    indices:   n.indices,
                    children:  n.children,
                    handle:    n.handle,
                    priority:  n.priority - 1,
                }

                // Update maxParams (max of all children)
                for i := range child.children {
                    if child.children[i].maxParams > child.maxParams {
                        child.maxParams = child.children[i].maxParams
                    }
                }

                // 把原来的公共部门单独成一个node，该node变成一个普通节点了
                // 并把子节点path的首字母添加到node.indices中，indices中首字母
                // 按子节点优先级顺序排列，方便遍历，可以遍历indices快速找到子节点
                // 在父节点children成员中的下标
                n.children = []*node{&child}
                // []byte for proper unicode char conversion, see #65
                // 保存子节点path的首字母
                n.indices = string([]byte{n.path[i]})
                n.path = path[:i]
                n.handle = nil
                n.wildChild = false
            }

            // Make new node a child of this node
            // 新添加的路由去掉path公共部门，剩下的保存到新建的节点中
            if i < len(path) {
                path = path[i:]
                if n.wildChild {
                    n = n.children[0]
                    n.priority++

                    // Update maxParams of the child node
                    if numParams > n.maxParams {
                        n.maxParams = numParams
                    }
                    numParams--

                    // Check if the wildcard matches
                    // 如果子节点是通配符节点，那么只有一种情况不报错
                    // 已存在/home/first:name，添加/home/first:name/xxx，其他情况全部panic
                    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
                    } else {
                        // Wildcard conflict
                        var pathSeg string
                        if n.nType == catchAll {
                            pathSeg = path
                        } else {
                            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 +
                            "'")
                    }
                }
                // 其实就是子节点中path的第一个字母
                c := path[0]

                // slash after param
                // 针对有多个:通配符情况，如:已经存在/home/first:name/:second/
                // 添加/home/first:name/:second/sub
                if n.nType == param && c == '/' && len(n.children) == 1 {
                    n = n.children[0]
                    n.priority++
                    continue walk
                }

                // Check if a child with the next path byte exists
                // 在节点的indices中有匹配path首字母的字符存在，则说明path
                // 还能提供公共的部门，继续往下遍历
                for i := 0; i < len(n.indices); i++ {
                    if c == n.indices[i] {
                        i = n.incrementChildPrio(i)
                        n = n.children[i]
                        continue walk
                    }
                }

                // Otherwise insert it
                // 最终找到一个节点下不能再提供公共部门了，就在这个节点下新增一个节点
                // 在children成员后面添加，并按优先级重新排序，indices也重新排序
                if c != ':' && c != '*' {
                    // []byte for proper unicode char conversion, see #65
                    n.indices += string([]byte{c})
                    child := &node{
                        maxParams: numParams,
                    }
                    n.children = append(n.children, child)
                    n.incrementChildPrio(len(n.indices) - 1)
                    n = child
                }
                n.insertChild(numParams, path, fullPath, handle)
                return

            } else if i == len(path) { // Make node a (in-path) leaf
                if n.handle != nil {
                    panic("a handle is already registered for path '" + fullPath + "'")
                }
                n.handle = handle
            }
            return
        }
    } else { // Empty tree
        n.insertChild(numParams, path, fullPath, handle)
        n.nType = root
    }
}

接下来添加两条路由:

func myHandler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()
    r.GET("/home/first:name/sub/*information", myHandler)
    r.GET("/home/first:name/second", myHandler)
    r.GET("/house", myHandler)
    httprouter.DumpTree(r, "GET")
    http.ListenAndServe(addr, r)
}

添加/home/first:name/second之后的路由树，可知在sub和second有公共部分s，提取公共部分s成父节点，在该节点下添加两个子节点(子节点path需要去掉公共部分)，示意图如下：

添加/home/first:name/second后路由树

添加/house后路由树

3.3 getValue

getValue从路由树中查找path对应的handler:

// Returns the handle registered with the given path (key). The values of
// wildcards are saved to a map.
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
// made if a handle exists with an extra (without the) trailing slash for the
// given path.
func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) {
walk: // outer loop for walking the tree
    for {
        if len(path) > len(n.path) {
            if path[:len(n.path)] == n.path {
                path = path[len(n.path):]
                // 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
                // 沿着路由树往下遍历，如果不存在通配符节点，则node的indices中查看
                // 能否继续往下遍历，如果能则截取path剩余部门继续下次循环，直到匹配成功
                // 匹配成功则返回，不能匹配成功则判断是否满足重定向条件
                if !n.wildChild {
                    c := path[0]
                    for i := 0; i < len(n.indices); i++ {
                        if c == n.indices[i] {
                            n = n.children[i]
                            continue walk
                        }
                    }

                    // Nothing found.
                    // We can recommend to redirect to the same URL without a
                    // trailing slash if a leaf exists for that path.
                    tsr = (path == "/" && n.handle != nil)
                    return

                }

                // handle wildcard child
                // 有通配符则需要把通配符名称作为key，真实值作为value保存到参数p中
                n = n.children[0]
                switch n.nType {
                case param:
                    // find param end (either '/' or path end)
                    end := 0
                    for end < len(path) && path[end] != '/' {
                        end++
                    }

                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    // `:`通配符的路径是:name这种形式，所以必须跳过一个字符去取得名字
                    // 值则直接截取到下一个/或者到字符结尾
                    p[i].Key = n.path[1:]
                    p[i].Value = path[:end]

                    // we need to go deeper!
                    // 如果没有处理完则要循环处理
                    if end < len(path) {
                        if len(n.children) > 0 {
                            path = path[end:]
                            n = n.children[0]
                            continue walk
                        }

                        // ... but we can't
                        tsr = (len(path) == end+1)
                        return
                    }

                    // 如果找不到则查看是否存在可重定向的路由
                    if handle = n.handle; handle != nil {
                        return
                    } else if len(n.children) == 1 {
                        // No handle found. Check if a handle for this path + a
                        // trailing slash exists for TSR recommendation
                        n = n.children[0]
                        tsr = (n.path == "/" && n.handle != nil)
                    }

                    return

                case catchAll:
                    // catchAll只能存在path的最后一个segment
                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    // catchAll的形式是/*name，所以必须跳过两个字符才能取到name字符
                    // value直接取到字符串最后就行
                    p[i].Key = n.path[2:]
                    p[i].Value = path

                    handle = n.handle
                    return

                default:
                    panic("invalid node type")
                }
            }
        } else if path == n.path {
            // We should have reached the node containing the handle.
            // Check if this node has a handle registered.
            if handle = n.handle; handle != nil {
                return
            }

            if path == "/" && n.wildChild && n.nType != root {
                tsr = true
                return
            }

            // No handle found. Check if a handle for this path + a
            // trailing slash exists for trailing slash recommendation
            for i := 0; i < len(n.indices); i++ {
                if n.indices[i] == '/' {
                    n = n.children[i]
                    tsr = (len(n.path) == 1 && n.handle != nil) ||
                        (n.nType == catchAll && n.children[0].handle != nil)
                    return
                }
            }

            return
        }

        // Nothing found. We can recommend to redirect to the same URL with an
        // extra trailing slash if a leaf exists for that path
        tsr = (path == "/") ||
            (len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
                path == n.path[:len(n.path)-1] && n.handle != nil)
        return
    }
}

函数比较长，主要做了以下几件事:

1. 沿着树往下遍历，如果能匹配节点的path，则截取参数path的剩余部门继续往下遍历，通过节点indices成员知道是否可以继续往下遍历
2. 通配符节点需要从path中截取真实的值，把通配符名字作为key，真实值作为value保存到返回参数p中
3. 如果最终匹配成功，则返回handler，匹配不成功则返回的tsr标识能否满足重定向，true表示满足重定向，false表示不满足

比如注册了/home/，但是http请求路径是/home，则getValue返回tsr为true，并且httproute自动给重定向到/home/

总结:

1. httprouter为每一种http方法维护一棵路由树，存在大量路由情况下能提供更好的匹配效率
2. httprouter空间利用率更高(不同保存相同前缀)
3. httprouter不是线程安全的(本质上是addRoute(path, handler)不是线程安全的)