Dawn's Blogs

分享技术 记录成长

0%

从零实现一个Web框架 (3) 前缀树路由

发表于 更新于 分类于

在本节，最终的代码目录结构如下：

1
2
3
4
5
6
7
8
dain/
	|--context.go
	|--dain.go
	|--router.go
	|--trie.go
	|--go.mod
main.go
go.mod

实现目标

利用前缀树（Trie 树）实现动态路由解析，并且支持 :name 和 *filename 两种模式。

main.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func main() {
	e := dain.New()

	e.Get("/hello/:name", func(c *dain.Context) {
		name := c.Param("name")
		c.String(http.StatusOK, "Hello, you are %v, URL path = %v", name, c.Path)
	})

	e.Get("/file/*filename", func(c *dain.Context) {
		filename := c.Param("filename")
		c.JSON(http.StatusOK, dain.H{
			"filename": filename,
			"msg":      "OK",
		})
	})

	e.Run(":9000")
}

Trie 树

dain/trie.go

在之前的版本种，使用了 map 来存储路由与处理函数的映射，但是这不能支持动态路由。

Trie 树（前缀树）可以实现动态路由，一个节点的所有子节点都有相同的前缀。

/:user/info、/:user/doc、/p/video、/p/book、/file/*filepath 对应的前缀树如下所示：

1
2
3
4
5
6
7
                      /
       _______________|______________
      |               |              |
    :user             p            file
   ___|___         ___|___           |
  |       |       |       |          |
info     doc    video    book    *filepath

节点结构

首先需要知道前缀树的节点的结构。

其中，matchChild 匹配第一个节点，用于将剩余路由信息插入到匹配的节点之下。matchChildren 用于匹配所有的节点，用于查找请求的路径信息是否匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type node struct {
	pattern  string  // 待匹配的路由，只在pattern定义的最后一个节点存储
	part     string  // 路由中的一部分
	children []*node // 叶子节点
	isWild   bool    // 若不是精确匹配则为 true；否则为 false
}

// matchChild 匹配第一个节点，用于插入
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}

	return nil
}

// matchChildren 匹配所有的节点，用于查找
func (n *node) matchChildren(part string) []*node {
	children := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			children = append(children, child)
		}
	}

	return children
}

插入和搜索

在添加路由时，需要在前缀树中插入节点。

在匹配路由时，需要查找当前请求的路径是否能匹配到节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// insert 插入节点
func (n *node) insert(pattern string, parts []string, height int) {
	if len(parts) == height {
		// 到达叶子节点
		// 仅仅在pattern定义的最后一个节点存储
		n.pattern = pattern
		return
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		// 若当前层没有匹配，新建一个节点，并插入到孩子节点中
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}
	// 向下一层继续插入
	child.insert(pattern, parts, height+1)
}

// search 查找节点
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		// 到达叶子节点 或者 匹配到“*”
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		// 在下一层中继续查找
		result := child.search(parts, height+1)
		if result != nil {
			// 找到节点
			return result
		}
	}

	return nil
}

路由器 Router

dain/router.go

router 结构

在 router 中记录前缀树的根节点 roots，用于记录和匹配路由；handlers 用于记录 pattern 和 HandlerFunc 的映射关系：

1
2
3
4
5
6
7
8
9
10
11
type router struct {
	roots    map[string]*node       // 保存 trie 树的根，key为 Method，value为树根
	handlers map[string]HandlerFunc // 保存 pattern 与 HandlerFunc 的映射关系
}

func NewRouter() *router {
	return &router{
		roots:    make(map[string]*node),
		handlers: make(map[string]HandlerFunc),
	}
}

添加路由

因为增加了前缀树用来保存路由 pattern，所以需要在添加路由的同时在前缀树中插入节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// parsePattern 解析 pattern，返回对应的 parts（路由中的一部分）
// 如 pattern 为 /hello/world，那么对应的 parts 为 []{"hello", "world"}
func parsePattern(pattern string) []string {
	vs := strings.Split(pattern, "/")

	parts := make([]string, 0, len(vs))
	for _, item := range vs {
		if item != "" {
			// 不为空，加入到 parts 中
			parts = append(parts, item)
			if item[0] == '*' {
				// 遇到通配符直接退出
				break
			}
		}
	}

	return parts
}

// addRouter 实现路由注册功能
func (r *router) addRouter(method, pattern string, handler HandlerFunc) {
	log.Printf("Router %v - %v\n", method, pattern)
	key := method + "-" + pattern

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

	parts := parsePattern(pattern)
	r.roots[method].insert(pattern, parts, 0) // 插入到前缀树中
	r.handlers[key] = handler
}

路由功能

添加一个函数 getRouter 用于查找对应的叶子节点和路由参数，并且重新实现 handle 路由功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// getRoute 根据请求的 method 和 path，找到对应的前缀树叶子节点和路由参数
func (r *router) getRoute(method, path string) (*node, map[string]string) {
	searchParts := parsePattern(path) // 查找的 parts
	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
}

// handle 实现路由功能
func (r *router) handle(c *Context) {
	// 在前缀树种查找路由，获取路由参数
	n, params := r.getRoute(c.Method, c.Path)

	if n != nil {
		// 匹配路由
		key := c.Method + "-" + n.pattern
		c.Params = params
		r.handlers[key](c)
	} else {
		fmt.Fprintf(c.Writer, "404 NOT FOUND FOR PATH: %v", c.Path)
	}
}

Context

dain/context.go

Context 结构

为了访问到路由参数，所以需要修改 Context 结构体，向其中添加 Params，用来记录路由参数：

1
2
3
4
5
6
7
8
9
10
11
type Context struct {
	// HTTP 请求 响应
	Writer http.ResponseWriter
	Req    *http.Request
	// 请求信息
	Path   string            // 请求路径
	Method string            // 请求方法
	Params map[string]string // 路由参数，如 /hello/:user 匹配 /hello/dawn，则 Params["user"]=dawn
	// 响应信息
	StatusCode int // 响应码
}

获取路由参数

增加可以用过键值获取相应路由参数的函数：

1
2
3
4
5
// Param 获取路由参数
func (c *Context) Param(key string) string {
	value, _ := c.Params[key]
	return value
}