Server & 路由树
Server
Web 核心
对于一个 Web 框架，至少要提供三个抽象：
Server：代表服务器的抽象Context：表示上下文的抽象路由树Server
从特性上来说，至少要提供三部分功能：
生命周期控制：即启动，关闭，生命周期的回调；路由注册接口：提供路由注册功能；作为 http 包到 Web 框架的桥梁http.Handler接口
http 包暴露了一个接口 Handler。
它是我们引入自定义 Web 框架相关的连接点。
// ListenAndServe listens on the TCP network address addr and then calls// Serve with handler to handle requests on incoming connections.// Accepted connections are configured to enable TCP keep-alives.//// The handler is typically nil, in which case the DefaultServeMux is used.//// ListenAndServe always returns a non-nil error.func ListenAndServe(addr string, handler Handler) error {server := &Server{Addr: addr, Handler: handler}return server.ListenAndServe()}接口的定义
版本一：只组合 http.Handler
//Server filetype Server interface {http.Handler}//Server_test filefunc TestServer(t *testing.T) {var s Serverhttp.ListenAndServe("localhost:8080", s)}优点：
用户在使用的时候只需要调用 http.ListenAndServe 就可以和 HTTPS 协议完全无缝衔接极简设计缺点：
难以控制生命周期，并且在控制生命周期的时候增加回调支持缺乏控制力：如果将来希望支持优雅退出的功能，将难以支持版本二：组合 http.Handler 并且增加 Start 方法。
//Server filetype Server interface {http.HandlerStart(addr string) error}//Server_test filefunc TestServer(t *testing.T) {var s Serverhttp.ListenAndServe("localhost:8080", s)s.Start(":8080")//Start 方法可以不需要 addr 参数，那么在创建实现类的时候传入地址就可以。}优点：
Server 既可以当成普通的 http.Handler 来使用，又可以作为一个独立的实体，拥有自己的管理生命周期的能力完全的控制，可以为所欲为缺点：
如果用户不希望使用 ListenAndServeTLS，那么 Server 需要提供 HTTPS 的支持版本一和版本二都直接耦合了 Go 自带的 http 包，如果我们希望切换为 fasthttp 或者类似的 http 包，则会非常困难。
HTTPServer 实现 Server
// Server_test filetype HTTPServer struct {}var _Server = &HTTPServer{}func (s *HTTPServer) ServerHTTP(writer http.ResponseWriter, request *http.Request) {}func (s *HTTPServer) Start(addr string) error {return http.ListenAndServe(addr, s)}该实现直接使用 http.ListenAndServe 来启动，后续可以根据需要替换为：
内部创建 http.Server 来启动使用 http.Serve 来启动，换取更大的灵活性，如将端口监听和服务器启动分离等ServeHTTP 则是我们整个 Web 框架的核心入口。我们将在整个方法内部完成：
Context 构建路由匹配执行业务逻辑路由树
实现路由树得步骤：
全静态匹配支持通配符匹配支持参数路由不同框架路由树的实现：
Beego： ControllerRegister：类似于容器，放着所有的路由树 路由树是按照 HTTP method 来组织的，例如 GET 方法会对应有一棵路由树 Tree：它代表的就是路由树，在 Beego 里面，一棵路由树被看做是由子树组成的leafInfo：代表叶子节点树的设计并没有采用 children 式来定义，而是采用递归式的定义，即一棵树是由根节点 + 子树构成
路由树的设计总结：
归根结底就是设计一颗多叉树。
同时我们按照 HTTP 方法来组织路由树，每个 HTTP 方法一棵树节点维持住自己的子节点静态匹配
所谓的静态匹配，就是路径的每一段都必须严格相等。
接口设计
关键类型：
router：维持住了所有的路由树，它是整个路由注册和查找的总入口。router 里面维护了一个 map，是按照 HTTP 方法来组织路由树的node：代表的是节点。它里面有一个 children 的 map 结构，使用 map 结构是为了快速查找到子节点type router struct {// trees 是按照 HTTP 方法来组织的// 如 GET => *nodetrees map[string]*node}type node struct {path string//children 子节点//子节点的 path => *nodechildren map[string]*node//handler 命中路由之后的逻辑handler HandlerFunc}func newRouter() router {return router{trees: map[string]*node{},}}用简化版的 TDD，即：
定义 API定义测试添加测试用例实现，并且确保实现能够通过测试用例重复 3-4 直到考虑了所有的场景重复步骤 1-5全局静态匹配
方法路由设计{method: http.MethodGet,path: "/",},{method: http.MethodGet,path: "/user",},{method: http.MethodGet,path: "/user/home",},{method: http.MethodGet,path: "/order/detail",},{method: http.MethodPost,path: "/order/create",},{method: http.MethodPost,path: "/login",},//非法样例r = newRouter()//空字符串assert.PanicsWithValue(t, "web: 路由是空字符串", func() {r.addRoute(http.MethodGet, "", mockHandler)})//前导没有 /assert.PanicsWithValue(t, "web: 路由必须以 / 开头", func() {r.addRoute(http.MethodGet, "a/b/c", mockHandler)})//后缀有 /assert.PanicsWithValue(t, "web: 路由不能以 / 结尾", func() {r.addRoute(http.MethodGet, "/a/b/c/", mockHandler)})r.addRoute(http.MethodGet, "/", mockHandler)// 根节点重复注册assert.PanicsWithValue(t, "web: 路由重复注册", func() {r.addRoute(http.MethodGet, "/", mockHandler)})// 普通节点重复注册r.addRoute(http.MethodGet, "/a/b/c", mockHandler)assert.PanicsWithValue(t, http.MethodGet, func() {r.addRoute(http.MethodGet, "/a/b/c", mockHandler)})// 多个assert.PanicsWithValue(t, "web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [/a//b]", func() {r.addRoute(http.MethodGet, "/a//b", mockHandler)})assert.PanicsWithValue(t, "web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [//a/b]", func() {r.addRoute(http.MethodGet, "//a/b", mockHandler)})// addRoute 注册路由// method 是 HTTP 方法//path 必须以 / 开始并且结尾不能有 /，中间也不允许有连续的 /func (r *router) addRoute(method string, path string, handler HandlerFunc) {// 空字符串判断if path == "" {panic("web: 路由是空字符串")}// 必须以 / 为开头判断if path[0] != '/' {panic("web: 路由必须以 / 开头")}// 结尾不能有 /if path != "/" && path[len(path)-1] == '/' {panic("web: 不能以 / 为结尾")}root, ok := r.trees[method]//这是一个全新的 HTTP 方法，我们必须创建根节点if !ok {root = &node{path: "/",}r.trees[method] = root}// 路径冲突if path == "/" {if root.handler != nil {panic("web: 路径冲突")}root.handler = handlerreturn}// 对路由进行切割segs := strings.Split(path[1:], "/")//开始进行处理for _, s := range segs {// 对空路径进行判断if s == "" {panic(fmt.Sprintf("web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [%s]", path))}root = root.childrenOfCreate(s)}if root.handler != nil {panic(fmt.Sprintf("web: 路由冲突[%s]", path))}}//子节点不存在则创建一个子节点func (n *node) childrenOfCreate(path string) *node {if n.children == nil {n.children = make(map[string]*node)}child, ok := n.children[path]if !ok {child = &node{path: path}n.children[path] = child}return child}对 method 进行校验
定义为私有的 addRoute 即可实现：
用户只能通过 Get 或者 Post 方法来注册，那么可以确保 method 参数永远都是对的addRoute 在接口里面是私有的，限制了用户将无法实现 Server。实际上如果用户想要实现 Server，就约等于自己实现一个 Web 框架了。path 之所以会有那么强的约束，是因为我希望用户写出来的代码风格要一致，就是注册的路由有些人喜欢加 /，有些人不喜欢加 /。
路由查找// test_file// 待测试路由testRoutes := []struct {method stringpath string}{{method: http.MethodGet,path: "/",},{method: http.MethodGet,path: "/user",},{method: http.MethodGet,path: "/order/create",},{method: http.MethodGet,path: "/user/*/home",},{method: http.MethodGet,path: "/order/*",},}// 测试样例testCase := []struct {name stringmethod stringpath stringfound boolwantNode *node}{{name: "method not found",method: http.MethodHead,},{name: "path not found",method: http.MethodGet,path: "/abc",},{name: "root",method: http.MethodGet,found: true,path: "/",wantNode: &node{path: "/",handler: mockHandler,},},{name: "user",method: http.MethodGet,found: true,path: "/user",wantNode: &node{path: "user",handler: mockHandler,},},{name: "no handler",method: http.MethodPost,found: true,path: "/order",wantNode: &node{path: "order",},},{name: "two layer",method: http.MethodPost,found: true,path: "/order/create",wantNode: &node{path: "create",handler: mockHandler,},},}// 路由查找实现func (r *router) findRoute(method string, path string) (*node, bool) {root, ok := r.trees[method]if !ok {return nil, false}if path == "/" {return root, true}segs := strings.Split(strings.Trim(path, "/"), "/")for _, s := range segs {root, ok = root.childof(s)if !ok {return nil, false}}return root, true}//判断是否存在子节点func (n *node) childof(path string) (*node, bool) {if n.children == nil {return nil, false}res, ok := n.children[path]return res, ok}这种情况下，用户只能使用 NewHTTPServer 来创建服务器实例。
如果考虑到用户可能自己 s := &HTTPServer 引起 panic，那么可以将 HTTPServer
做成私有的，即改名为 httpServer。
type HTTPServer struct{ router }func NewHTTPServer() *HTTPServer {return &HTTPServer{router: newRouter(),}}func (s *HTTPServer) server(ctx *Context) {n, ok := s.findRoute(ctx.Req.Method, ctx.Req.URL.Path)if !ok || n.handler == nil {ctx.Resp.WriteHeader(404)ctx.Resp.Write([]byte("Not Found"))return}n.handler(ctx)}通配符匹配
所谓通配符匹配，是指用 * 号来表达匹配任何路径。要考虑几个问题：
/a/b/c 能不能命中 /a/* 路由？如果注册了两个路由 /user/123/home 和 /user/*/*。那么输入路径 /user/123/detail 能不能命中 /user/*/*? 这两个都是理论上可以，但是不应该命中。
从实现的角度来说，其实并不难。从用户的角度来说，他们不应该设计这种路由。给用户自由，但是也要限制不良实践。后者要求的是一种可回溯的路由匹配，即发现/user/123/home 匹配不上之后要回溯回去 /user/* 进一步查找，典型的投入大产出低的特性。 对 node 进行修改：
// node 代表路由树的节点// 路由树的匹配顺序为：// 1、静态完全匹配// 2、通配符匹配// 这是不回溯匹配type node struct {path string//children 子节点//子节点的 path => *nodechildren map[string]*node//handler 命中路由之后的逻辑handler HandlerFunc//通配符 * 表示的节点，任意匹配starChild *node}对 childof 进行修改：
func (n *node) childof(path string) (*node, bool) {if n.children == nil {return n.starChild, n.starChild != nil}res, ok := n.children[path]if !ok {return n.starChild, n.starChild != nil}return res, ok}对 childOrCreate 进行修改：
func (n *node) childrenOfCreate(path string) *node {if path == "*" {if n.children == nil {n.starChild = &node{path: "*"}}}if n.children == nil {n.children = make(map[string]*node)}child, ok := n.children[path]if !ok {child = &node{path: path}n.children[path] = child}return child}增加 addRouter 测试用例
{method: http.MethodGet,path: "/order/*",},{method: http.MethodGet,path: "/*",},{method: http.MethodGet,path: "/*/*",},{method: http.MethodGet,path: "/*/abc",},{method: http.MethodGet,path: "/*/abc/**",},增加 findRoute 测试用例
// 通配符匹配{ // 命中/order/* name: "star match", method: http.MethodPost, path: "/order/delete", found: true, wantNode: &node{path: "*",handler: mockHandler,},},{//命中中间的通配符 // user/*/homename: "start in middle",method: http.MethodGet,path: "/user/Tom/home",wantNode: &node{ path: "home", handler: mockHandler,},},{// 比/order/* 多一段name: "overflow",method: http.MethodPost,path: "/order/delete/123",},参数路径
所谓参数路径，就是指在路径中带上参数，同时这些参数对应的值可以被业务取出来使用。
例如：/user/:id ，如果输入路径 /user/123，那么会命中这个路由，并且 id = 123。
那么要考虑：
允不允许同样的参数路径和通配符匹配一起注册？例如同时注册/user/* 和 /user/:id 可以，但是没必要，用户也不应该设计这种路由。
对 node 进行修改
type HandlerFunc func(ctx *Context)// node 代表路由树的节点// 路由树的匹配顺序为：// 1、静态完全匹配// 2、通配符匹配// 这是不回溯匹配type node struct {path string//children 子节点//子节点的 path => *nodechildren map[string]*node//handler 命中路由之后的逻辑handler HandlerFunc//通配符 * 表示的节点，任意匹配starChild *node//路径参数paramchild *node}对 childrenOfCreate 进行变更
func (n *node) childrenOfCreate(path string) *node {if path == "*" {if n.children == nil {n.starChild = &node{path: "*"}}}if path == "*" {if n.paramchild != nil {panic(fmt.Sprintf("web: 非法路由，已有路径参数路由。不允许同时注册通配符路由和参数路由 [%s]", path))}if n.starChild == nil {n.starChild = &node{path: path}}return n.starChild}// 以 ： 开头，我们一般认为是参数路由if path[0] == ':' {if n.starChild != nil {panic(fmt.Sprintf("web: 非法路由，已有路径参数路由，不允许同时注册通配符路由和参数路由 [%s]", path))}if n.paramchild != nil {if n.paramchild.path != path {panic(fmt.Sprintf("web： 路由冲突， 参数路由冲突，已有 %s，新注册 %s", &n.paramchild.path, path))}} else {n.paramchild = &node{path: path}}return n.paramchild}if n.children == nil {n.children = make(map[string]*node)}child, ok := n.children[path]if !ok {child = &node{path: path}n.children[path] = child}return child}对 childof 进行修改
// childof 返回子节点// 第一个返回值为 *node 是命中的节点// 第二个返回值为 bool 代表是否命中参数值// 第三个返回值为 bool 代表是否命中func (n *node) childof(path string) (*node, bool, bool) {if n.children == nil {if n.paramchild != nil {return n.paramchild, true, true}return n.starChild, true, n.starChild != nil}res, ok := n.children[path]if !ok {if n.paramchild != nil {return n.paramchild, true, true}return n.starChild, false, n.starChild != nil}return res, true, true}获取路径参数
// 修改Context文件type Context struct {Req *http.RequestResp http.ResponseWriterPathParams map[string]string}//新增 matchInfo 表示参数信息type matchInfo struct {n *nodepathParams map[string]string}// 对 findRoute 进行修改func (r *router) findRoute1(method string, path string) (*matchInfo, bool) {root, ok := r.trees[method]if !ok {return nil, false}if path == "/" {return &matchInfo{n: root}, true}segs := strings.Split(strings.Trim(path, "/"), "/")mi := &matchInfo{}for _, s := range segs {var matchParam boolroot, matchParam, ok = root.childOf1(s)if !ok {return nil, false}if matchParam {mi.addValue(root.path[1:], s)}}mi.n = rootreturn mi, true}如/user/:id，输入路径 /user/123，那么就相当于把 id = 123 这样一个键值对放进去了 mi (matchInfo) 里面。
路由树总结
已经注册了的路由，无法被覆盖，例如/user/home 注册两次，会冲突path 必须以 / 开始并且结尾不能有 /，中间也不允许有连续的 /不能在同一个位置注册不同的参数路由，例如 /user/:id 和 /user/:name 冲突不能在同一个位置同时注册通配符路由和参数路由，例如 /user/:id 和 /user/* 冲突同名路径参数，在路由匹配的时候，值会被覆盖，例如 /user/:id/abc/:id，那么 /user/123/abc/456 最终 id = 456 路由树疑问
Q： 为什么在注册路由用 panic？
A： 俗话说，遇事不决用 error。为什么注册路由的过程我们有一大堆 panic ？
这个地方确实可以考虑返回 error。例如 Get 方法，但是这要求用户必须处理返回的 error。
从另外一个角度来说，用户必须要注册完路由，才能启动 HTTPServer。那么我们就可以采用 panic，因为启动之前就代表应用还没运行。
Q：路由树是线程安全的吗？
A：显然不是线程安全的。
我们要求用户必须要注册完路由才能启动 HTTPServer。而正常的用法都是在启动之前依次注册路由，不存在并发场景。
至于运行期间动态注册路由，没必要支持。这是典型的为了解决 1% 的问题，引入 99% 的代码。
总结
为了尽最大可能方便各位同学能够电脑上进行调试和提交代码，我将我自己的写文章时的代码提交至 Github仓库当中。
如果大家对我所写代码有修改或者优化的话，欢迎大家提交 优化后的代码。
最后欢迎大家 Follow Github 作者。
