【Golang学习笔记】从零开始搭建一个Web框架（二）

文章目录

- 模块化路由
- 前缀树路由

前情提示：

【Golang学习笔记】从零开始搭建一个Web框架（一）-CSDN博客

模块化路由

路由在kilon.go文件中导致路由和引擎交织在一起，如果要实现路由功能的拓展增强，那将会非常麻烦，这无疑降低了代码的可读性和可维护性。现在的工作是将路由从引擎里剥离出来，引擎中仅对路由进行包装。

新建文件router.go，当前目录结构为：

myframe/
    ├── kilon/
    │   ├── context.go
    │   ├── go.mod      [1]
    │   ├── kilon.go
    │   ├── router.go
    ├── go.mod          [2]
    ├── main.go

在router中添加下面内容：

package kilon

import (
	"net/http"
)

type router struct {
	Handlers map[string]HandlerFunc
}
// 创建router对象
func newRouter() *router {
	return &router{make(map[string]HandlerFunc)}
}
// 剥离路由注册的具体实现
func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
	key := method + "-" + pattern
	r.Handlers[key] = handler
}
// 剥离SeverHTTP中路由处理的具体实现
func (r *router) handle(ctx *Context) {
	key := ctx.Method + "-" + ctx.Path
	if handler, ok := r.Handlers[key]; ok {
		handler(ctx)
	} else {
		ctx.String(http.StatusNotFound, "404 NOT FOUND: %s\n", ctx.Path)
	}
}

修改kilon.go文件：

package kilon

import (
	"net/http"
)

type HandlerFunc func(*Context)

type Origin struct {
	router *router // 修改路由
}

func New() *Origin {
	return &Origin{router: newRouter()} // 修改构造函数
}

func (origin *Origin) addRoute(method string, pattern string, handler HandlerFunc) {
	origin.router.addRoute(method, pattern, handler) // 修改调用
}

func (origin *Origin) GET(pattern string, hander HandlerFunc) {
	origin.addRoute("GET", pattern, hander) 
}

func (origin *Origin) POST(pattern string, hander HandlerFunc) {
	origin.addRoute("POST", pattern, hander) 
}

func (origin *Origin) ServeHTTP(w http.ResponseWriter, req *http.Request) {
	ctx := newContext(w, req)
	origin.router.handle(ctx) // 调用router.go中的处理方法
}

func (origin *Origin) Run(addr string) (err error) {
	return http.ListenAndServe(addr, origin)
}

至此，实现了路由的模块化，后续路由功能的增强将不会改动kilon.go文件。

前缀树路由

目前的路由表使用map存储键值对，索引非常高效，但是有一个弊端，键值对的存储的方式，只能用来索引静态路由而无法实现动态路由。在实际的应用中，可能需要使用正则表达式或者其他匹配规则来实现更复杂的路由匹配，而 map 无法提供这种功能。接下来，将使用前缀树（Tire树）实现动态路由，主要实现两个功能：

参数匹配:。例如 /p/:name/doc，可以匹配 /p/zhangsan/doc 和 /p/lisi/doc。
通配*（仅允许最后一个有"*"号）。例如 /static/*filepath，可以匹配/static/fav.ico和/static/js/jQuery.js。

新建文件trie.go，当前文件目录结构为：

myframe/
    ├── kilon/
    │   ├── context.go
    │   ├── go.mod      [1]
    │   ├── kilon.go
    │   ├── router.go
    │   ├── tire.go
    ├── go.mod          [2]
    ├── main.go

在trie.go中创建前缀树的节点:

type node struct {
	patten   string  // 待匹配路由
    part     string  // 路由当前部分
	children []*node // 孩子节点
	isWild   bool    // 是否为模糊搜索，当含有":"和通配符"*"时为true
}

当注册路由"/p/:name/doc"、“/p/:name/png”、“/p/:lang/doc”、"/p/:lang/png"后，树中内容如下：

在这里插入图片描述

可以看到，pattern只有在插入最后一个子节点后才会设置，这是为了在查询路由信息时可以根据 pattern==""来判断改路由是否注册。isWaild的作用在于当part不匹配时，如果isWaild为true可以继续搜索，这样就实现了模糊匹配。

先实现路由注册时的前缀树插入逻辑：

func (n *node) insert(pattern string, parts[]string, index int)

pattern是注册路由地址，parts是解析pattern后的字符串数组（使用方法strings.Split(pattern, "/")进行解析）如"/p/:name/doc"对应 [“p”,“:name”,“doc”]，parts[index]是当前需要插入的part。可以通过index判断是否退出。（疑问：如果只用Split解析那pattren="/"的时候不就无法注册了吗？答：开始时树的根节点的part为空，不会匹配，“p"一定会插入到根节点的子节点切片中。而当pattern为”/“时解析字符串切片为空，进入根节点的时候len(parts) = index = 0,会将根节点的pattern设置为”/“，也可以实现路由”/"的注册。）

代码如下：

func (n *node) insert(pattern string, parts[]string, index int){
	// 进来的时候说明 n.part = parts[index-1] 即最后一个 part 则直接设置 patten
	if len(parts) == index {
		n.patten = pattern
		return
	}
	// 还需匹配 part
	// 先在 n.children 切片中匹配 part
	part := parts[index]
	child :=  n.matchChild(part)
	// 如果没有找到，则构建一个 child 并插入 n.children 切片中
	if child == nil {
		child = &node{
			part: part,
			// 含有":"或者通配符"*"时为 true
			isWild: part[0] ==':' || part[0] == '*',
		}
		// 插入 n.children 切片
		n.children = append(n.children, child)
	}
	// 递归插入
	child.insert(pattern, parts, index + 1)
}
// 查找匹配 child
func (n *node) matchChild(part string) *node {
	// 遍历 n.children 查找 part 相同的 child
	for _, child := range n.children {
		// 如果找到匹配返回 child， 当 isWild 为 true 时视为匹配实现模糊搜索
		if child.part == part || child.isWild == true {
			return child
		}
	}	
	// 没找到返回nil
	return nil
}

接下来实现接受请求时查询路由信息时的前缀树搜索逻辑：

func (n *node) search(parts []string, index int) *node

parts是路由地址的解析数组，index指向当前part索引

代码如下:

// 搜索
func (n *node) search(parts []string, index int) *node {
	// 如果匹配将节点返回
	if len(parts) == index || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}
	part := parts[index]
	// 获取匹配的所有孩子节点
	nodes := n.matchChildren(part)
	// 递归搜索匹配的child节点
	for _, child := range nodes {
		result := child.search(parts, index+1)
		if result != nil {
			return result
		}
	}
	return nil
}
// 查找匹配的孩子节点，由于有":"和"*"，所以可能会有多个匹配，因此返回一个节点切片
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild == true {
			nodes = append(nodes, child) // 将符合的孩子节点添入返回切片
		}
	}
	return nodes
}

至此trie.go暂时写完，现在在路由中进行应用，回到router.go文件。为了区分不同的方法如GET和POST，为每一个Method建立一颗前缀树，并以键值对的形式存储在一个map中：map[Method] = tire。修改router结构体与构造方法：

type router struct {
	roots     map[string]*node       // 前缀树map
	Handlers map[string]HandlerFunc // 将pattern作为key获取/注册方法
}
func newRouter() *router {
	return &router{
		make(map[string]*node),
		make(map[string]HandlerFunc),
	}
}

将pattern插入前缀树之前，要先解析成字符串切片，现在需要实现一个解析函数。

func parsePattern(pattern string) []string {
	temp := strings.Split(pattern, "/")
	parts := make([]string, 0)
	for _, item := range temp {
		if item != ""{
			parts = append(parts, item)
			if item[0] == '*' {
				break
			}
		}	
	}
	return parts
}

修改注册路由的逻辑：

func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
	parts := parsePattern(pattern) // 解析pattern

	key := method + "-" + pattern

	if _, ok := r.roots[key]; !ok {
		r.roots[method] = &node{} // 如果没有则创建一个节点
	}

	r.roots[method].insert(pattern, parts, 0) // 前缀树插入pattern
	r.Handlers[key] = handler			     // 注册方法
}

当接受请求时，需要对请求中携带的路由信息解析，并获取匹配的节点以及":“,”*"匹配到的参数，现在需要写一个路由获取方法：

func (r *router) getRoute(method string, path string) (*node, map[string]string) {
 	searchParts := parsePattern(path) // 解析路由信息
	params := make(map[string]string) // 参数字典
	root, ok := r.roots[method]

	if !ok {
		return nil, nil
	}
	// 搜索匹配节点
	n := root.search(searchParts, 0)

	if n!= nil {
		parts := parsePattern(n.pattern) // 解析pattern
        // 寻找'*'和':',找到对应的参数。
		for index, part := range parts {
			if part[0] == ':' {
				params[part[1:]] = searchParts[index]
			}
			if part[0] == '*' && len(part) >1 {
                // 将'*'后切片内容拼接成路径
				params[part[1:]] = strings.Join(searchParts[index:],"/")
                break // 仅允许一个通配符'*'
			}
            return n, params
		}
	}
	return nil, nil
}

路径中的参数应该交给上下文对象让用户便捷获取。在Context结构体中添加Params属性,并包装获取方法：

type Context struct {
	Writer     http.ResponseWriter
	Req        *http.Request
	Path       string
	Method     string
	Params     map[string]string // 路由参数属性
	StatusCode int
}
// 获取路径参数
func (c *Context) Param(key string) string {
	value := c.Params[key]
	return value
}

在router.go中的handle中应用路由获取方法，并将路径参数提交给上下文对象。

func (r *router) handle(ctx *Context) {
	n, params := r.getRoute(ctx.Method, ctx.Path) // 获取路由节点及参数字典
	ctx.Params = params
	if n != nil {
		key := ctx.Method + "-" + n.pattern // key为n的pattern
		r.Handlers[key](ctx) // 调用注册函数
	} else {
		ctx.String(http.StatusNotFound, "404 NOT FOUND: %s\n", ctx.Path)
	}
}

现在router.go内容为：

package kilon

import (
	"net/http"
	"strings"
)

type router struct {
	roots    map[string]*node
	Handlers map[string]HandlerFunc
}

func newRouter() *router {
	return &router{
		make(map[string]*node),
		make(map[string]HandlerFunc),
	}
}

func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
	parts := parsePattern(pattern)

	key := method + "-" + pattern

	_, ok := r.roots[method]
	if !ok {
		r.roots[method] = &node{}
	}

	r.roots[method].insert(pattern, parts, 0)
	r.Handlers[key] = handler
}

func (r *router) handle(ctx *Context) {
	n, params := r.getRoute(ctx.Method, ctx.Path)
	ctx.Params = params
	if n != nil {
		key := ctx.Method + "-" + n.pattern
		r.Handlers[key](ctx)
	} else {
		ctx.String(http.StatusNotFound, "404 NOT FOUND: %s\n", ctx.Path)
	}
}

func parsePattern(pattern string) []string {
	temp := strings.Split(pattern, "/")
	parts := make([]string, 0)
	for _, item := range temp {
		if item != "" {
			parts = append(parts, item)
			if item[0] == '*' {
				break
			}
		}
	}
	return parts
}

func (r *router) getRoute(method string, path string) (*node, map[string]string) {
	searchParts := parsePattern(path)
	params := make(map[string]string)
	root, ok := r.roots[method]

	if !ok {
		return nil, nil
	}

	n := root.search(searchParts, 0)

	if n != nil {
		parts := parsePattern(n.pattern)
		for index, part := range parts {
			if part[0] == ':' {
				params[part[1:]] = searchParts[index]
			}
			if part[0] == '*' && len(part) > 1 {
				params[part[1:]] = strings.Join(searchParts[index:], "/")
				break
			}
		}
		return n, params
	}

	return nil, nil
}

在main.go测试一下：

package main

import (
	"kilon"
	"net/http"
)

func main() {
	r := kilon.New()
	r.GET("/hello", func(ctx *kilon.Context) {
		ctx.JSON(http.StatusOK, kilon.H{
			"message": "Hello World",
		})
	})
	r.GET("/hello/:username", func(ctx *kilon.Context) {
		ctx.JSON(http.StatusOK, kilon.H{
			"message": ctx.Param("username"),
		})
	})
	r.GET("/hello/:username/*filename", func(ctx *kilon.Context) {
		ctx.JSON(http.StatusOK, kilon.H{
			"username": ctx.Param("username"),
			"filename": ctx.Param("filename"),
		})
	})
	r.Run(":8080")
}