路由树
上一章最后我们写到了处理restful风格的api。但是实现的太简陋了。自然我们需要一个路由树来处理请求。
那么我们从最简单的情况开始。
最简单的路由树
1.不考虑路径参数问题。
2.不考虑路由冲突。
3.不考虑性能问题。
那么我们自然就可以得到树的结构定义，Tree记录根节点，path表示节点本身的路径，children表示子节点的路径，handler表示该路由下有没有注册的handlerFunc，如果有则执行，如果没有则执行父节点的。
考虑到我们注册的函数定义func(ctx *Context)声明的地方比较多，这边也可以给个类型handlerFunc，方便理解。
代码语言：go复制type handlerFunc func(ctx *Context)
type Tree struct {
root *node
}
type node struct {
path string
children []*node
handler handlerFunc
method string
}新增路由
那么当我们声明一个新的路由时，我们的新增逻辑是这样的。
新增一条 temp/user/hello。
将temp作为根节点出发，查找user。
如果children里有user则将user作为当前节点。
如果没有则创建一个新节点user，加入children。并将新节点作为当前节点。
由于不考虑路由冲突，在hello节点直接将handlerFunc赋值给handler即可。
代码语言：go复制func (t *Tree) Route(method string, pattern string, hundler handlerFunc) {
pattern = strings.Trim(pattern, "/")
paths := strings.Split(pattern, "/")
cur := t.root
matchChild, ok := cur.findMatchChild(paths)
if ok {
matchChild.handler = hundler
matchChild.method = method
}
}
func (r *node) findMatchChild(paths []string) (*node, bool) {
if len(paths) == 0 {
return r, true
}
for _, childNode := range r.children {
if childNode.path == paths[0] {
return childNode.findMatchChild(paths[1:])
}
}
newChildNode := r.createNode(paths[0])
r.children = append(r.children, newChildNode)
return newChildNode.findMatchChild(paths[1:])
}
func (r *node) createNode(path string) *node {
return &node{
path: path,
children: make([]*node, 0, 2),
}
}支持*匹配路由
刚才我们的路由只能所有的路径都完全匹配。我们可以尝试扩展一下，例如注册temp/user/*，那么temp/user/other1,temp/user/other2都能匹配上。我们一般会用 /*来匹配所有没有注册的路由，并在handlerfunc里返回404。
匹配路由和新增路由其实方法是一样的。直接复用即可。
代码语言：go复制func (t *Tree) FindRoute(method string, pattern string) (*node, bool) {
pattern = strings.Trim(pattern, "/")
paths := strings.Split(pattern, "/")
cur := t.root
return cur.findMatchChild(paths)
}那么我们要修改的，其实只有这个地方。
代码语言：go复制if childNode.path == paths[0] {
return childNode.findMatchChild(paths[1:])
}修改一下
代码语言：go复制if childNode.path == paths[0] || paths[0] == "*" {
return childNode.findMatchChild(paths[1:])
}但是有这么简单吗？有两个问题：
1.比如我们注册了两个路由，temp/user/hello，temp/user/*，当我们访问temp/user/hello时，两个路由都能匹配上。
这么写会按照注册路由的顺序返回。但是我们希望的肯定是优先匹配具体的路由，都匹配不上时再匹配通配符。即优先挑选匹配path最多的路由。
2.比如我注册了 temp/* ，temp/*/hello两个路由，这时候我请求了 temp/user/greet，我应该匹配上 temp/*吗？
我认为我们不能允许注册第二种路由，因为如果要支持第二种路由，那么我们在匹配路由失败时，又要回溯路由树，看看有没有其他的通配符可以重新匹配。
那么我们重新新增两条规则。
1.校验*，如果*存在，必须在路由的最后一个。即我们只接受/*结尾。
2.优先匹配具体的路由，都匹配不上再匹配通配符。
那么我们创建路由和匹配路由时的方法也有了些许不同。
代码语言：go复制func (t *Tree) Route(method string, pattern string, hundler handlerFunc) {
pattern = strings.Trim(pattern, "/")
//校验通配符的使用是否合法，非法时直接返回。
if strings.Contains(pattern, "*") && !strings.HasSuffix(pattern, "/*") {
return
}
paths := strings.Split(pattern, "/")
cur := t.root
matchChild, ok := cur.findMatchChild(paths)
if ok {
matchChild.handler = hundler
matchChild.method = method
}
}func (t *Tree) FindRoute(method string, pattern string) (*node, bool) {
pattern = strings.Trim(pattern, "/")
paths := strings.Split(pattern, "/")
cur := t.root
return cur.matchChild(paths)
}func (r *node) matchChild(paths []string) (*node, bool) {
if len(paths) == 0 {
return r, true
}
var wildCardNode *node
//有匹配时优先返回能匹配上的，如果都匹配不上再看是否有通配符的。
for _, childNode := range r.children {
if childNode.path == paths[0] && childNode.path != "*" {
return childNode.matchChild(paths[1:])
}
if childNode.path == "*" {
wildCardNode = childNode
}
}
return wildCardNode, wildCardNode != nil
}还有一个问题
temp/* 能否匹配 temp ？
这是一个典型的设计问题，因为无论是否匹配，似乎都可以说出合理的理由。
这里我们的实现没有支持，仅仅是因为我认为用户注册temp/*是期望temp之后有存在子路由的。如果要处理temp这个路由本身，那么用户可以直接注册一个temp的路由。
题外
很多时候写代码，难题并不在于代码本身，而在于设计上的取舍。而这种取舍很多时候又仅代表作者本人的偏好。当我们有时候遇到一些写法不被支持的时候，不妨思考一下这样写真的是不好的实践，还是仅仅是作者本身的偏好。
