httprouter 解读

核心思想

• 与 defaultServeMux 的实现区别在于什么？采取特殊的数据结构作路由。
• defaultServeMux 的实现采用什么样的数据结构？
• httprouter 的实现采用什么样的数据结构？
• router 的架构图是怎样的，与 server.go 有何异同
• 一些 http 相关的细节
• 其他细节

细读源码

• Router 的 paramsPool？sync.Pool 需要看看 done
• 修复重定向是代码大头，得细细解读重定向相关的协议内容 这部分先跳过吧，细节太多了
• http 包的 server.go 里面 req 的 context 里面包含了 params 怎么取消的。done

“server.serve => conn.serve ==>defer cancleCtx/ w.cancelCtx()”

因此，最要紧的就是看 tree.go 里面定义的数据结构。曹大的图可以帮助理解。

tree

• addRoute 方法为切入口
• 初次阅读有几个不明白的地方，还需要回顾 router.go

• 具体的路由规则要烂熟，由此解读 node 的几个类型
• priority/wildchild/indices 的意思和作用
• test 文件的测试有没有没覆盖到的情况？

node 的结构

type node struct {
    path      string
    indices   string 
    wildChild bool
    nType     nodeType
    priority  uint32
    children  []*node
    handle    Handle
}

疑难字段名

-path

一截儿 path，绝非全路径，这点可以确定。具体怎么表述？

• indices

// incrementChildPrio
if newPos != pos {n.indices = n.indices[:newPos] +
   n.indices[pos:pos+1] +
   n.indices[newPos:pos] + n.indices[pos+1:] 
 }

可见每个 node 为 chidren 指定唯一的一字节字符，和排好序的 chidren slice 一一对应。问题是怎么指定的呢？

• wildchild

是什么？干嘛的？

• priority

干嘛的？

“加”的两个重头方法 addRoute 和 insertChild

解读

1. 事实上，在 router.go 中，只用到了 addRoute 为我们的 router 添加路由以及对应的 handle, insertChild 为 addRoute 服务。
2. 进一步的事实是，调用 addRoute 的总是根节点 root.

• 我们根据以上事实，参照代码，在脑海中模拟运行。找到点感觉再更细致的分析（其实还有一个不错的方法是参照测试文件看看，找找感觉）。

// router.go Handle
if root == nil {root = new(node)
    r.trees[method] = root
    // 其他逻辑
    ]}

// tree.go addRoute
fullpath := path
n.priority ++

//Empty tree
if len(n.path) == 0 && len(n.indices) == 0 {n.insertChild(path, fullpath, handle)
    n.nType == root // 常量：root
    return
}

• insertChild 的逻辑是怎么样？

• 没有“:”“*”都好说，直接：

//insertChild
n.path = path
n.handle = handle

• 有呢？有点复杂。将情况简单化，如果之前是空树的话（现在要有第一个节点了），我们想想，有“:”“*”有什么说头？
• 问题一：遇到无效的 wildcard 怎么处理？
• 问题二：可能要设置 wildcard 冲突，怎么设置呢？

• 问题一已经被枪毙了

if !valid {panic("only one wildcard per path segment is allowed, has:'" + wildcard + "'in path'" + fullPath + "'")
}

• 另外还赠送了两种枪毙情况，“光杆司令”“鸠占鹊巢（初次插入时不会出现，但是很好理解，即冲突，后会提及此事）”
• 好了，开始好循环了吗？因为 findWildCard 只会找到离根部最近的那个。
• param，这个简单点，先从这儿开始吧。先贴源码。

if wildcard[0] == ':' {   // param
    if i > 0 {
        // Insert prefix before the current wildcard
        n.path = path[:i]
        path = path[i:]
    }

    n.wildChild = true
    child := &node{
        nType: param,
        path: wildcard,
    }
    n.children = []*node{child}
    n = child
    n.priority++

    // If the path doesn't end with the wildcard, then there will be another non-wildcard subpath starting with'/'
    if len(wildcard) < len(path) {path = path[len(wildcard):]
        child := &node{priority: 1,}
        n.children = []*node{child}
        n = child
        continue
    }

    // Otherwise we're done. Insert the handle in the new leaf
    n.handle = handle
    return
}

• 其实很简单。当前节点 n 不是没 children 嘛（有 chidren 的之前已经被枪毙），我 param 给你当吧。别高兴的太早，你得把我爹妈照顾好，于是有了：

    if i > 0 {n.path = path[:i]
        path = path[i:]
    }

• 需要注意的是这个 path 不是乱传的。path 和 fullpath 和树和当前节点是有一致性的，在 addRoute 里会体现。我们可以猜想一下，n.path 和参数 path 的关系，n.path 应该是参数 path 脱去通配内容之后的前缀 ，否则以上的语句就会无缘无故抹掉 n.path 的某种信息。设想 path 以 ”:” 开头的情况，也可以想通。这一点待验证。
• 我们当前关注的空树插节点不需要考虑这么深入，若“:”前有任何内容，直接给 n 即可，我们集中精力处理以 ”:” 开头的一段。path 在这个过程中不断的“脱”。无论如何，现在的 path 以 ”:” 开头了。

n.wildchild = true

• 出现了，wildchild 意思是，n 的孩子是 wildCard，并不是“野孩子”。当然 wildchild 也必须是独子，否则，会引起冲突，果然有点野。

    child := &node{
        nType: param,
        path: wildcard,
    }
    n.children = []*node{child}
    n = child
    n.priority++

• 注意，上面的 wildcard 是不包含 ”/” 的、以“:”开头的一段内容。如愿以偿的，这个野孩子当了 n 的孩子，不仅如此，还篡权了，成了新一代的 n，接手以下的朝政工作。刚创建死后 priority 为 0，现在为 1。如果 wildcard 后面没有内容了，即没有“/”了，完事儿了，到头了：

    n.handle = handle
    return

• 后面还有内容的话，必须还没完事儿，做好重走循环的准备

    if len(wildcard) < len(path) {path = path[len(wildcard):]
        child := &node{priority: 1,}
        n.children = []*node{child}
        n = child
        continue
    }

• path 又开始“脱”了，path 就像 python（非彼 python）一样一直蜕皮。这下 path 一定是以 ”/” 开头的，这是从 fildWildCard 函数的实现中得出的结论。现在的 n 的类型是之前的 param，形如“:xxx”的不含 ”/”，它创建了一个空孩子，并且这个空孩子当政成了 n，重走循环。看我们之前推测的，n.path 必须是参数 path 的前缀，空串当然是 path 的前缀。
• 接下来是 catchall 情况，感觉应该和 param 雷同，但是又有点不一样。根据 router.go 开头的注释和测试用例，猜想一下：catchall 一定是叶子节点，不以 ”/” 结尾。

if i+len(wildcard) < len(path) {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 + "'")
            }

• 也就是如果 n.path 非空，必须以 ”/” 结尾。什么意思？什么 node 不以 ”/” 结尾？比如 param 类型的，比如 catchall 类型的，还比如想通配一个，“/file/prefix_*filepath”统统不合法了。
• 但是 path 本身会不会是“/somesubpath/*cathall”类型的呢？这样接在 param 类型的 node 后面为什么是非法的？猜想：param 类型的 node 不会直接调用 insertChild 方法！（等待验证）
• 这时候又来了下面一句：

    i--
    if path[i] != '/' {panic("no / before catch-all in path'" + fullPath + "'")}

• 意思和上一条雷同。只不过非法情况来自
• i–? 如果 i == 0 呢？由此可见，path 不会以“*”开头（等待验证）

小结一下：调用插入方法的 node 的 path 会是参数 path 的前缀，是空串最保险了。参数 path 不会以“*”开头，以“:”开头是可能的。node 不会是 param 类型（catch 也不会）。

n.path = path[:i]

// First node: catchAll node with empty path
child := &node{
    wildChild: true,
    nType:     catchAll,
    }
    n.children = []*node{child}
    n.indices = string('/')
    n = child
    n.priority++

// Second node: node holding the variable
child = &node{path:     path[i:],
    nType:    catchAll,
    handle:   handle,
    priority: 1,
    }
    n.children = []*node{child}

    return

• path 脱了后（还记得我们的前缀论吗），进行了一波骚操作，一连插入两个 catchall 类型的节点。不明白为什么，似乎是作了一个保护，最后一个节点才是真正的通配符。并且这里首次出现了 indices. 更懵圈了。
• 毕竟 insertChild 只是一个辅助方法，使用的情况很多很多限制。

回到 addRoute 吧。

// 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)

再回顾一遍 insertChild 方法：设想向空树插入：“/:name”, “:name”, “/*catchall”, 根结点不会带“:”“*”，要么空串，要么 ”/”。注意插入“*catchall”非法 (index out of range!!!)。可以理解他的注释。

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,
    }

    n.children = []*node{&child}
    // []byte for proper unicode char conversion, see #65
    n.indices = string([]byte{n.path[i]})
    n.path = path[:i]
    n.handle = nil
    n.wildChild = false
}

• 好的。i 是 path 和 n.path 的最长公共前缀。最长公共前缀是要被剥离放在祖辈的。因为树生长的方向是向下，而越向下，生成的路径就会越长。这里相当于旧路径和新路径分叉了，自然要把前缀放在祖辈位置。
• 以上代码还有几个值得注意的细节。为什么接管 n.path 后半段的 child 的 priority 要 -1？暂时还不清楚。

-n.indices 的含义。从上可以瞥见一点端倪。记得我们说过，n.indices 和 n.children 一一对应？这里 n.indices 就是这个 child 的开头字母，正如其名，起到的是索引的作用。

• n.wildchild 是 false，因为我们说了，最长前缀不含“:””*”. 有个特殊情况：path 和 n.path 一样都是，:param 别的特殊情况也有，因此这个注释意思不明
• 还需要注意，n 作为原 n.path 的子串，是没有设置 handle 的，你可以之后为这条路径设置。就直接走到该方法的最后：

if n.handle != nil {panic("a handle is already registered for path'" + fullPath + "'")
    }
    n.handle = handle

• 我们继续往下走。先总览一下全貌。

if i < len(path) {path = path[i:]

    // 节点 n 的子节点是通配，杀伤力比较大，先掌权，后清洗
    if n.wildchild {
        // 1. 掌权
        // 2. 清洗，生存者可以进入下一轮。// 思考：// 1. 什么样的能逃过清洗？// 2. 进入下一轮的初始状态是怎样的：虚拟根结点
    }

    // 现在面临的情况：n 的孩子节点没有 param 或 catchall
    // 但是 n 本身可能是
    idxc := path[0]

    // 1. 一种简单的情况的处理 n 是 param，只有一个孩子
    // 那必然是“/”开头的或空串，直接重走循环

    // 2. n 的某个孩子和 path 有公共前缀，提升 priority 并重走循环

    // 3. 其他情况插入新的子节点，使树增长
    // 现在的情形是：n.path 和 path 绝对并没有公共前缀了
    // 3.1 等待拼接的全新 path 不以 ":" "*" 打头，需要做一点工作 
    // 插入空节点，作用不明，保护作用？// 结合 insertChild 的情况，有个情况可以排除：// 如果 idxc 是“:”"*" 打头的，n 必然没孩子
    // 如果 n 是 param, path 是普通字母打头的呢？按理来说，这是个不合法现象。这在上面的判断（wildcard 冲突判断中）已经枪毙。// 创建孩子（空串），插入此节点。n.insertChild(path, fullpPath, handle)
    }

}

• 需要注意的是，如果节点是 param 类型，path 必然是“:”和参数名，绝不含有“/”，也侧面说明两个 param 类型的节点不可能是父子。
• 如果是 staitc 类型，又没有“/”都是合法的，并且可以在任意位置（中间合法吗？），从上往下拼就可以了。
• continue walk 的情况：

• 公共前缀不为空或 n.path 为空串
• 若 n 为 param（模拟根结点无法做到的），path 一定是“:param”或“:param/”或“/”打头三种情况之一。
• param 子节点若有一定是独生子！！
• param 没孩子的话，要加一个空串“”

源码参考：

if i < len(path) {path = path[i:]

    if n.wildchild {n = n.children[0]
        n.prority ++

    // Check if the wildcard mathes
    if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
    n.nType != catchAll &&
    (len(n.path) >= len(path) || path[len(n.path)] == "/") {continue walk} else {
        pathSeg := path
        if n.nType != cathAll {pathSeg = strings.SplitN(pathSeg, "/", 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 +"'")
        }
    }

    idxc := path[0]

    if n.nType == param && idxc == "/" && len(n.children) == 1 {n = n.children[0]
        n.prority++
        continue walk
    }

    for i, c := range []byte(n.indices) {
        if c == idxc {i = n.incrementChildPrio(i)
            n = n.children[i]
            continue walk
        }
    }

    if idxc != ':' && idxc != '*' {n.indices += string([]byte{idxc})
        child := &node{}
        n.children = append(n.children, child)
        n.incrementChildPrio(len(n.indices) - 1)
        n = child
    }
    n.insertChild(path, fullpPath, handle)
}

“拿”的重要方法：getValue

作用猜想：根据树，匹配手头的 path，把所有参数取出来，放在从 sync.Pool 里拿出临时对象 []Params，不断把解析的 param 加入。catchall 怎么处理？拭目以待！