前言

在一个框架的设计中，参考是有必要的，从Gin的设计来说，他确实是非常优秀的一个web框架，也没有什么可挑剔的。从他的源码上确确实实学到了很多东西。那么，我们继续。

本系列抄了参考了这个项目:

https://geektutu.com/post/gee.html

Trie

之前用了非常简单的map结构来存储了路由表，使用map存储键值对，索引非常高效，但是有一个弊端，键值对的存储的方式，只能用来索引静态路由。那如果我们想支持类似于/hello/:name这样的动态路由怎么办呢？所谓动态路由，即一条路由规则可以匹配某一类型而非某一条固定的路由。例如/hello/:name，可以匹配/hello/geektutu、hello/jack等。

动态路由有很多种实现方式，支持的规则、性能等有很大的差异。例如开源的路由实现gorouter支持在路由规则中嵌入正则表达式，例如/p/[0-9A-Za-z]+，即路径中的参数仅匹配数字和字母；另一个开源实现httprouter就不支持正则表达式。著名的Web开源框架gin 在早期的版本，并没有实现自己的路由，而是直接使用了httprouter，后来不知道什么原因，放弃了httprouter，自己实现了一个版本。

新建trie.go

package GoMatrix

import (
	"strings"
)

// 树节点需要存储的信息

type node struct {
	pattern  string // 待匹配路由，例如 /p/:lang
	part     string // 路由中的一部分，例如 :lang
	children []*node // 子节点
	isWild   bool // 是否精确匹配，part 含有 : 或 * 时为true
}

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


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

func (n *node) insert(pattern string, parts []string, height int) {
	// parts为处理过的路由组：路由为/func/:cid   [func :cid] <-- parts为
	if len(parts) == height {
		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)
}


func (n *node) search(parts []string, height int) *node {
	// 解析到最后一层或者是匹配到*号，则认为该节点是最子节点
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}
	// 查询该height下所有子节点
	part := parts[height]
	children := n.matchChildren(part)
	for _, child := range children {
		// 递归查询子节点
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}
	return nil
}

与普通的树不同，为了实现动态路由匹配，加上了isWild这个参数。即当我们匹配 /p/go/doc/这个路由时，第一层节点，p精准匹配到了p，第二层节点，go模糊匹配到:lang，那么将会把lang这个参数赋值为go，继续下一层匹配。我们将匹配的逻辑，包装为一个辅助函数。

改造router.go

package GoMatrix

import (
	"net/http"
	"strings"
)

// 抽离router
type router struct {
	roots    map[string]*node
	handlers map[string]HandlerFunc
}

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

// 解析路由

func parsePattern(pattern string) []string {
	vs := strings.Split(pattern, "/")
	parts := make([]string, 0)
	for _, item := range vs {
		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)
	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) 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)
	//fmt.Println(n) // &{/func/:cid :cid [] true}
	if n != nil {
		parts := parsePattern(n.pattern)
		for index, part := range parts {
			// 如果该子节点以:或者*开头
			if part[0] == ':' {
				// 将值赋值到params
				params[part[1:]] = searchParts[index]
			}
			// 如果*开头并且长度大于1，则这个节点的值赋值到params，并停止循环
			if part[0] == '*' && len(part) > 1 {
				params[part[1:]] = strings.Join(searchParts[index:], "/")
				break
			}
		}
		return n, params
	}

	return nil, nil
}


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

router.go的变化比较小，比较重要的一点是，在调用匹配到的handler前，将解析出来的路由参数赋值给了c.Params。这样就能够在handler中，通过Context对象访问到具体的值了。

context.go新增：

type Context struct {
	// 原对象
	Writer http.ResponseWriter
	Req    *http.Request
	// 请求信息
	Path   string
	Method string
  // 新增动态路由值
	Params map[string]string
	// 响应信息
	StatusCode int
}


// 从上下文中读取param参数

func (c *Context) Param(key string) string {
	value, _ := c.Params[key]
	return value
}

总结

关于路由树，可以参考这篇文章，基于目前的实现来说，树比原来使用的hash存储更加的灵活，能够解析的了动态路由。不过像上面提及的httprouter和gorouter，也不失为一种实现方法。不过目前模仿胜于创造。等以后有了自己想法再说。