之前,我们用了一个非常简单的map结构存储了路由表,使用map存储键值对,索引非常高效,但是有一个弊端,键值对的存储的方式,只能用来索引静态路由。那如果我们想支持类似于/hello/:name这样的动态路由怎么办呢?所谓动态路由,即一条路由规则可以匹配某一类型而非某一条固定的路由。例如/hello/:name,可以匹配/hello/geektutu、hello/jack等。
所以今天我们的任务就是:
- 使用 Tire 树实现动态路由(dynamic route)解析
- 支持两种模式:name和*filepath
接下来我们实现的动态路由具备以下两个功能:
- 参数匹配":",例如 /p/:lang/doc,可以匹配 /p/c/doc 和 /p/go/doc
- 通配"*",例如 /static/*filepath,可以匹配/static/fav.ico,也可以匹配/static/js/jQuery.js,这种模式常用于静态服务器,能够递归地匹配子路径
Tire树实现
首先我们需要设计树节点上应该存储那些信息,其中pattern表示当前节点可以匹配的路由;part表示当前节点对应的路由某一部分的内容;children则存储当前节点的子节点,即后续可匹配路由;isWild 则表示当前节点是否是模糊匹配。与普通的树不同,为了实现动态路由匹配,加上了isWild
这个参数。即当我们匹配/p/go/doc/
这个路由时,第一层节点,p
精准匹配到了p
,第二层节点,go
模糊匹配到:lang
,那么将会把lang
这个参数赋值为go
,继续下一层匹配。我们将匹配的逻辑,包装为一个辅助函数。
type node struct {
pattern string // 待匹配路由,例如 /p/:lang
part string // 路由中的一部分,例如 :lang
children []*node // 子节点,例如 [doc, tutorial, intro]
isWild bool // 是否精确匹配,part 含有 : 或 * 时为true
}
接下来就是定义node对象对应的方法,首先是两个匹配方法
- 查找子树中第一个匹配:遍历当前节点对象的所有子节点,遇到第一个 part 部分可匹配的节点即返回
// 找到匹配的子节点,场景是用在插入时使用,找到1个匹配的就立即返回
func (n *node) matchChild(part string) *node {
// 遍历n节点的所有子节点,看是否能找到匹配的子节点,将其返回
for _, child := range n.children {
// 如果有模糊匹配的也会成功匹配上
if child.part == part || child.isWild {
return child
}
}
return nil
}
- 查找子树中所有可能的匹配:遍历当前节点对象的所有子节点,将所有可匹配的节点放入 slice 中,遍历所有节点后,返回 slice
// 找到匹配的子节点,场景是用在插入时使用,找到1个匹配的就立即返回
func (n *node) matchChild(part string) *node {
// 遍历n节点的所有子节点,看是否能找到匹配的子节点,将其返回
for _, child := range n.children {
// 如果有模糊匹配的也会成功匹配上
if child.part == part || child.isWild {
return child
}
}
return nil
}
对于路由来说,最重要的当然是注册与匹配。开发服务时,注册路由规则,映射handler;访问时,匹配路由规则,查找到对应的handler。
因此,Trie 树需要支持节点的插入与查询。插入功能对应路由中的注册过程,根据目标路由内容,在当前节点的子树中找第一个可匹配的节点。如果可匹配的节点不存在,根据目标路由内容,构建新的节点,并将该新节点插入到当前节点的子树中,然后再根据完整路由,插入下一个路由内容,递归完成整个路由内容的节点插入,即完成路由的注册。有一点需要注意,/p/:lang/doc只有遍历到第三层节点,即doc节点,pattern才会设置为/p/:lang/doc。p和:lang节点的pattern属性皆为空。因此,当匹配结束时,我们可以使用n.pattern == ""来判断路由规则是否匹配成功。例如,/p/python虽能成功匹配到:lang,但:lang的pattern值为空,因此匹配失败。
// 一边匹配一边插入的方法
//r.roots[method].insert(pattern, parts, 0)
//parts = [] parts = [hello] parts = [hello :name] parts = [assets *filepath]
//pattren= / ```/hello ```/hello/:name ```/assets/*filepath
func (n *node) insert(pattern string, parts []string, height int) {
if len(parts) == height {
// 如果已经匹配完了,那么将pattern赋值给该node,表示它是一个完整的url
// 这是递归的终止条件
n.pattern = pattern
return
}
part := parts[height]
child := n.matchChild(part)
if child == nil {
// 没有匹配上,那么进行生成,放到n节点的子列表中
child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
n.children = append(n.children, child)
}
// 接着插入下一个part节点
child.insert(pattern, parts, height+1)
}
查询功能对应路由中的注册过程,根据已有的trie树,查找所给的路由对应的树节点。当查找到最后一个节点或者当前节点包含*通配符,证明路由成功匹配,返回当前节点。否则查找子树中所有可以匹配的节点,遍历这些节点,递归查找下一层是否匹配,直至找到完全匹配路由的叶子节点,并将该叶子节点返回。
//n := root.search(searchParts, 0)
//[] [hello] [hello :name] [assets *filepath]
func (n *node) search(parts []string, height int) *node {
if len(parts) == height || strings.HasPrefix(n.part, "*") {
// 递归终止条件,找到末尾了或者通配符
if n.pattern == "" {
// pattern为空字符串表示它不是一个完整的url,匹配失败
return nil
}
return n
}
part := parts[height]
// 获取所有可能的子路径
children := n.matchChildren(part)
for _, child := range children {
// 对于每条路径接着用下一part去查找
result := child.search(parts, height+1)
if result != nil {
// 找到了即返回
return result
}
}
return nil
}
// 查找所有完整的url,保存到列表中
func (n *node) travel(list *([]*node)) {
if n.pattern != "" {
// 递归终止条件
*list = append(*list, n)
}
for _, child := range n.children {
// 一层一层的递归找pattern是非空的节点
child.travel(list)
}
}
Router路由实现
- 数据结构
Trie
树的插入与查找都成功实现后,接下来我们将Tire树放到router.go中,其中,roots 是请求的路由对应的树根节点,用于判断路由是否匹配,起始的树节点为 GET/POST等请求类型节点(key eg, roots['GET'] roots['POST']);handlers存储对应的响应处理函数,键值通常为 “请求类型-完整路由” 例如 handlers['GET-/p/:lang/doc'], handlers['POST-/p/book']。
将router.go中的router结构体和newRouter方法改为如下
type router struct {
roots map[string]*node // 请求的路由对应的树根节点,用于判断路由是否匹配(key eg, roots['GET'] roots['POST'])
handlers map[string]HandlerFunc // 对应的处理函数(key eg, handlers['GET-/p/:lang/doc'], handlers['POST-/p/book'])
}
// ---构造函数
func newRouter() *router {
return &router{
roots: make(map[string]*node),
handlers: make(map[string]HandlerFunc),
}
}
- 路由解析
根据”/“对路由进行划分,将其拆分成可作为node.part的各个部分,注意:理由中只能有一个*,*后的所有内容均被视为文件路径。getRoute
函数中,还解析了:
和*
两种匹配符的参数,返回一个 map
。例如/p/go/doc
匹配到/p/:lang/doc
,解析结果为:{lang: "go"}
,/static/css/geektutu.css
匹配到/static/*filepath
,解析结果为{filepath: "css/geektutu.css"}
。
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
}
- Router对象对应的方法
首先是注册路由,根据所给的请求类型以及路由,构建可匹配的 trie 树。将路由拆分后依次插入到请求类型对应的子树中,同时在handlers中存储对应的响应方式。
func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
//parts = [] parts = [hello] parts = [hello :name] parts = [assets *filepath]
parts := parsePattern(pattern) // 完成对路由的分析,获取其中的各个部分
//key= GET-/ key= GET-/hello key= GET-/hello/:name key= GET-/assets/*filepath
key := method + "-" + pattern // 构建router中handlers的注册路由
//method=/ 以/为root节点
_, ok := r.roots[method]
if !ok { // 该方法还没有树根节点,添加一个空节点便于插入
r.roots[method] = &node{}
}
//pattren= / ```/hello ```/hello/:name ```/assets/*filepath
r.roots[method].insert(pattern, parts, 0) // 像树中添加该路由的各个节点
//把key= GET-/ key= GET-/hello key= GET-/hello/:name key= GET-/assets/*filepath 与回调绑定
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) // 解析当前找到的节点的路由
for index, part := range parts { // 遍历路由的各个部分
if part[0] == ':' { // 遇到模糊匹配:
params[part[1:]] = searchParts[index] // key:除匹配符(:)的其余字符,value:待匹配路由的对应位置内容
}
if part[0] == '*' && len(part) > 1 { // 遇到模糊匹配*
params[part[1:]] = strings.Join(searchParts[index:], "/") // key:除匹配符(*)的其余字符,value:待匹配路由之后的内容
break // 后续可不再匹配
}
}
return n, params // 返回匹配的节点,以及模糊匹配对应的内容
}
return nil, nil // 没有匹配的节点,直接返回空
}
最后根据路由给出响应,根据请求的类型以及路由找到匹配的节点后,返回对应的响应内容。比较重要的一点是,在调用匹配到的handler
前,将解析出来的路由参数赋值给了c.Params
。这样就能够在handler
中,通过Context
对象访问到具体的值了文章来源:https://www.toymoban.com/news/detail-443782.html
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)
}
}
Context修改
在HandlerFunc
中,希望能够访问到解析的参数,因此,需要对 Context
对象增加一个属性和方法,来提供对路由参数的访问。我们将解析后的参数存储到Params
中,通过c.Param("lang")
的方式获取到对应的值。因此对context结构进行如下修改:文章来源地址https://www.toymoban.com/news/detail-443782.html
- 结构体中增加 Params: make(map[string]string),Params存储模糊匹配对应的内容(例如 param[”:lang“]=”go“),需要时可通过Param获取相应的模糊匹配参数
- 构造函数增加对Params的初始化
- 新增方法,根据所给的模糊匹配的内容,返回对应路由中的匹配内容
func (c *Context) Param(key string) string {
value, _ := c.Params[key]
return value
}
到了这里,关于七天从零实现Web框架Gee - 3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!