beego 是一个快速开发 Go 应用的 HTTP 框架，可以用来快速开发 API、Web 及后端服务等各种应用，是一个 RESTful 的框架。
那么这种RESTfule路由到底是怎么实现的？带着这个疑问，我们来了解一下实现过程。
一、使用方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
package main
import (
beego "github.com/beego/beego/v2/server/web"
)
type MainController struct {
beego.Controller
}
func (this *MainController) Get() {
this.Ctx.WriteString("Hello world")
}
func main() {
beego.Router("/", &MainController{})
beego.Run()
}
|
这个就是beego框架的简单使用。当然还有一些RESTful的使用，这里就不一一赘述了。
二、前缀树
Tire树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
那么在字典树中搜索添加过的单词的步骤如下：
1、从根节点开始搜索
2、取得要查找单词的第一个字母，并根据该字母对应的字符路径向下搜索
3、字符路径指向的第二层节点上，根据第二个字母选择对应的字符路径向下继续搜索
4、一直向下搜索，如果单词搜索完成，找到的最后一个节点是叶子节点，说明字典树中存在这个单词，如果找到的不是叶子节点，说明单词不是字典树中添加过的单词。
三、beego的前缀树
1、数据结构
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
|
// 路由树
type ControllerRegister struct {
routers map[string]*Tree
}
// 树节点结构
type Tree struct {
// 路由前缀
prefix string
// 完全路由信息
fixrouters []*Tree
// if set, failure to match fixrouters search then search wildcard
wildcard *Tree
// if set, failure to match wildcard search
leaves []*leafInfo
}
// 叶子节点结构
type leafInfo struct {
// names of wildcards that lead to this leaf. eg, ["id" "name"] for the wildcard ":id" and ":name"
wildcards []string
// if the leaf is regexp
regexps *regexp.Regexp
runObject interface{}
}
|
ControllerRegister是所有路由的集合，里面的routers是方法的集合，key是http的方法：GET,POST,PUT等，Tree就是路由的前缀树了。
只不过这个路由前缀树和前缀树并不完全相同，还存在通配符/user/:id和/user/*这种情况，所以添加了wildcard用于匹配这两种情况。
2、路由注册
我们的路由由以下几种情况：
1、全匹配路由
/user/list
2、正则路由
/user/:id
/user/:id()[0-9]+)
/user/*
添加路由的时候，实际是调用了
1
2
3
4
5
6
7
8
9
10
11
12
|
func (p *ControllerRegister) addToRouter(method, pattern string, r *ControllerInfo) {
if !p.cfg.RouterCaseSensitive {
pattern = strings.ToLower(pattern)
}
if t, ok := p.routers[method]; ok {
t.AddRouter(pattern, r)
} else {
t := NewTree()
t.AddRouter(pattern, r)
p.routers[method] = t
}
}
|
这个代码也简单明了，查找这个路由的方法树，如果存在就添加这个方法，如果不存在就新建方法树，然后再添加。
而调用的是AddRouter这个函数。
1
2
3
4
|
// 在路由树上添加路由，pattern是路由信息，runObject是执行方法
func (t *Tree) AddRouter(pattern string, runObject interface{}) {
t.addseg(splitPath(pattern), runObject, nil, "")
}
|
这个splitPath函数就是将路由以/分割。
而添加的过程当然是全匹配路由在fixrouters，正则路由在wildcard。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
func (t *Tree) addseg(segments []string, route interface{}, wildcards []string, reg string) {
if len(segments) == 0 {
// 在叶子节点上添加方法
if reg != "" {
t.leaves = append(t.leaves, &leafInfo{runObject: route, wildcards: wildcards, regexps: regexp.MustCompile("^" + reg + "$")})
} else {
t.leaves = append(t.leaves, &leafInfo{runObject: route, wildcards: wildcards})
}
} else {
seg := segments[0]
// splitSegment起到的作用是分析seg
// "admin" -> false, nil, ""
// ":id" -> true, [:id], ""
// "?:id" -> true, [: :id], "" : meaning can empty
// "🆔int" -> true, [:id], ([0-9]+)
// ":name:string" -> true, [:name], ([\w]+)
// ":id([0-9]+)" -> true, [:id], ([0-9]+)
// ":id([0-9]+)_:name" -> true, [:id :name], ([0-9]+)_(.+)
// "cms_:id_:page.html" -> true, [:id_ :page], cms_(.+)(.+).html
// "cms_:id(.+)_:page.html" -> true, [:id :page], cms_(.+)_(.+).html
// "*" -> true, [:splat], ""
// "*.*" -> true,[. :path :ext], "" . meaning separator
iswild, params, regexpStr := splitSegment(seg)
// if it's ? meaning can igone this, so add one more rule for it
if len(params) > 0 && params[0] == ":" {
t.addseg(segments[1:], route, wildcards, reg)
params = params[1:]
}
// Rule: /login/*/access match /login/2009/11/access
// if already has *, and when loop the access, should as a regexpStr
if !iswild && utils.InSlice(":splat", wildcards) {
iswild = true
regexpStr = seg
}
// Rule: /user/:id/*
if seg == "*" && len(wildcards) > 0 && reg == "" {
regexpStr = "(.+)"
}
if iswild {
// ... 省略代码
// 主要是通配符判断逻辑
t.wildcard.addseg(segments[1:], route, append(wildcards, params...), reg+regexpStr)
} else {
var subTree *Tree
// 这里添加的是全匹配路由
for _, sub := range t.fixrouters {
if sub.prefix == seg {
subTree = sub
break
}
}
if subTree == nil {
subTree = NewTree()
subTree.prefix = seg
t.fixrouters = append(t.fixrouters, subTree)
}
subTree.addseg(segments[1:], route, wildcards, reg)
}
}
}
|
主要就是判断给的路由数据是否存在通配符，然后分情况讨论。
最简单的就是普通路由了，直接添加到fixrouters里。
而正则路由根据各种情况，添加到wildcards里。
3、路由查找
很显然，是要先匹配fixrouters，如果没有对应的路由，再到wildcards中查找路由，返回对应的leaves里的方法。
查找路由的方法和插入的差不多，这里就不贴代码了。
四、总结
beego的路由对前缀树做了一点优化，按照/分割路由，把这部分放到前缀树的值中，减少了前缀树的深度，毕竟如果按照字符切分的话，前缀树会很深，而且对正则表现也不会友好。
