写在开头
非原创，网络收集，用于自己知识整理
1.IRoutes接口
官网gin的demo
r := gin.Default()
r.GET("/ping", func(ctx *gin.Context) {
ctx.JSON(200, gin.H{
"message": "pong",
})
})
使用gin的Default和New方法创建的实例是Engine，它也是框架的核心实例，包括了中间件、配置和路由等功能
vscode下ctrl+f12发现Engine是IRoutes接口的实现
type IRoutes interface {
Use(...HandlerFunc) IRoutes
Handle(string, string, ...HandlerFunc) IRoutes
Any(string, ...HandlerFunc) IRoutes
GET(string, ...HandlerFunc) IRoutes
POST(string, ...HandlerFunc) IRoutes
DELETE(string, ...HandlerFunc) IRoutes
PATCH(string, ...HandlerFunc) IRoutes
PUT(string, ...HandlerFunc) IRoutes
OPTIONS(string, ...HandlerFunc) IRoutes
HEAD(string, ...HandlerFunc) IRoutes
Match([]string, string, ...HandlerFunc) IRoutes
StaticFile(string, string) IRoutes
StaticFileFS(string, string, http.FileSystem) IRoutes
Static(string, string) IRoutes
StaticFS(string, http.FileSystem) IRoutes
}
主要分为3个功能：
- Use方法提供了用户接入自定义逻辑的能力，即插件或中间件机制
- Handle等方法是提供注册路由的抽象
- Static开头的方法是处理静态文件的接口
不同于传统MVC框架（例如PHP的ThinkPHP和GO的Beengo）,Gin没有Controller的抽象，也就是说，对于gin作者，他的设计理念是--MVC应该是用户组织web项目的模式，而不是框架设计者要考虑的
2.路由树设计
Engine本身也实现了net/http.Handler接口，即本身就可以作为一个Handler传递到http包中用于启动服务器
2.1添加路由
Engine->addRoute
方法签名如下
func (engine *Engine) addRoute(method, path string, handlers HandlersChain)
addroute根据要添加的方法获取对应的路由树（会先进行合法性检查）
// Engine.addRoute()
assert1(path[0] == '/', "path must begin with '/'")
root := engine.trees.get(method)
trees是存放methodTree实例的数组,因为请求方法最多有9个，所以使用数组足够
//methodTrees
type methodTree struct {
method string
root *node
}
type methodTrees []methodTree
func (trees methodTrees) get(method string) *node
由此可见，我们每次添加的一个路由就是一个node，这些node根据访问方法GET/POST等被组织在一颗methodTree路由树上，各种不同的路由树组成了一个路由森林methodTrees
type node struct {
path string
indices string
wildChild bool
nType nodeType
priority uint32
children []*node
handlers HandlersChain
fullPath string
}
回到Engine.addRoute中，在找到路由树后，就会根据路径添加对应的路由
//Engine.addRoute
root.addRoute(path, handlers)
这里是调用node.addRoute的逻辑，也是gin的前缀树核心逻辑所在
2.1.1什么是前缀树（Tire）
可以先尝试完成leet这道题
前缀树(Tire)是哈希树的变种，通常叫做单词查找树，能利用字符串的公共前缀减少查询时间，最大限度减少不必要的字符串比较，所以前缀树常被用于搜索引擎系统用于文本词频统计，前缀树拥有以下特点：
- 跟节点不包含字符（如上面的root只保存"/"路径)，其他节点包含字符
- 每一层节点内容不同
- 从跟节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的子节点，通常有一个标志位，用来标识单词的结束
在查找的过程中，我们根据首字母 x，找到 x 当中的 xi 这一共同部分，然后再根据不同的字母找到所对应的剩余部分。放到前缀树查找上，案例中的“心”对应 xi -> n，而“想”则对应 xi -> ang
2.1.2紧凑前缀树
GIN 中的前缀树相比普通的前缀树减少了查询的层级，比如说上方我们想查找的“心想”其中 xi 做为共有的部分，其实可以被分配在同一层同一个节点当中而不是分为两部分：
这样的就是紧凑前缀树，同理如果我们有如下四个路由，他们所形成的紧凑前缀树就会是这个样子：
r.GET("/", handle1)
r.GET("/product", handle2)
r.GET("/product/:id", handle3)
r.GET("/product/:name", handle4)
在有了这些数据结构知识储备的前提下，我们再回头看node.addRoute代码
//node.addRoute
fullPath := path
n.priority++
// Empty tree
if len(n.path) == 0 && len(n.children) == 0 {
n.insertChild(path, fullPath, handlers)
n.nType = root
return
}
node.fullpath存储完整路径，添加完成后，经过此节点的路由条数node.prority会+1(node.prority标识后续节点数量，满足tire特点4)，如果该树为空树，即跟节点"/"，则执行插入一个子节点逻辑
for {
//node.addRoute
i := longestCommonPrefix(path, n.path)
//longestCommonPrefix逻辑
func longestCommonPrefix(a, b string) int {
i := 0
max := min(len(a), len(b))
for i < max && a[i] == b[i] {
i++
}
return i
}
找到最长公共前缀的长度，path[i]==n.path[i],longestCommonPrefix的逻辑也很简单，依次移动下标对比
假设当前存在前缀信息n.path="hello"，现有"he"结点进入，则当前节点需要拆分成n.path="he"和n.path="llo"(需要满足前缀树特点3)，拆分逻辑如下
//node.addRoute
if i < len(n.path) {
child := node{
// 除去公共前缀部分，剩余的内容作为子节点
path: n.path[i:],
wildChild: n.wildChild,
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1,
fullPath: n.fullPath,
}
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = bytesconv.BytesToString([]byte{n.path[i]})
n.path = path[:i]
n.handlers = nil
n.wildChild = false
n.fullPath = fullPath[:parentFullPathIndex+i]
}
当公共前缀比已有path长度小时，拆分节点
上面"llo"被作为子节点放入n.children中，之后更新自己的n.path=path[:i]即"he"
node.indices是string类型，每个indices字符对应一个孩子节点的path的首字母
再来个例子加深印象
gin中注册路由如下
r.GET("/ping", func(c *gin.Context) {})
r.GET("/pii", func(c *gin.Context) {})
r.GET("/pin", func(c *gin.Context) {})
前缀树变化
当公共前缀长度小于要注册的路由时，说明需要新建子节点(因为tire特点3要求我们路径经过字符连接起来，是对应的路由)
//node.addRoute
if i < len(path) {
//提取剩下的字符串
path = path[i:]
c := path[0]
// '/' after param
if n.nType == param && c == '/' && len(n.children) == 1 {
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
continue walk
}
这上面是处理nType==param即参数路由"/:id"的逻辑
//node.addRoute
for i, max := 0, len(n.indices); i < max; i++ {
if c == n.indices[i] {
parentFullPathIndex += len(n.path)
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
因为n.indices存储所有子节点的首字母，如果相等，就说明还有公共部分，回到walk处继续处理干净
之后出现的字符再没有公共前缀
if c != ':' && c != '*' && n.nType != catchAll {
// []byte for proper unicode char conversion, see #65
n.indices += bytesconv.BytesToString([]byte{c})
child := &node{
fullPath: fullPath,
}
n.addChild(child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
上面是处理非通配符节点、非参数匹配节点和非正则匹配节点逻辑：
- 新增首字母到node.indices中
- 插入新增节点
- 处理新增节点
其他类型节点的处理逻辑代码就不再贴出，只需要注意当当前节点是通配符节点时，若再插入通配符的节点，即"/*/* "会发生覆盖
图示i<len(path)静态匹配逻辑
r.GET("/pi", func(c *gin.Context) {})
r.GET("/pin", func(c *gin.Context) {})
r.GET("/pii", func(c *gin.Context) {})
添加静态路由的主要逻辑阅读完毕，剩余类型的路由主要集中在node.insertChild逻辑中
3.寻找路由
了解上面前缀树的特点3后我们自然就想到了根据n.path去寻找n.fullpath,这里具体代码就不再贴出知道逻辑就行了，主要逻辑代码在node.getValue函数中
