Gogee-Day3-Trie木ルータ

Last renew: April 7, 2022 pm

注：本文仅为个人学习笔记，无任何版权。

本篇主要内容：1. 使用Trie树实现动态路由(dynamic route)解析。

支持两种模式:name和*filepath*

Trie Tree Router

之前，我们用了一个非常简单的map结构储存了路由表(router map)，使用map存储键值对，索引非常高效，但是有一个弊端，键值对存储的方式只适用于静态路由.

如果我们想要支持/hello/:name这样的动态路由怎么办呢？所谓动态路由，即一条路由规则可以匹配某一类而非某一条固定的路由。比如/hello/:name，可以匹配/hello/xiaogeamadeus、hello/tom等。

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

实现动态路由最常用的数据结构，被称为前缀树(Trie Tree)：每一个节点的所有子节点都拥有相同的前缀。这种结构非常适用于路由匹配。例如，我们定义了如下路由规则：

1
2
3
4
5
6
/:lang/doc
/:lang/tutorial
/:lang/intro
/about
/p/blog
/p/related

我们用前缀树来表示的话就会变成三颗子树/:lang、/about、/p

HTTP请求的路径恰好是由/分隔的多段构成的，因此，每一段可以作为前缀树的一个节点。我们通过树结构查询，如果中间某一层的节点都不满足条件，那么就说明没有匹配到的路由，查询结束。

我们接下来实现的路由具有如下两个功能。

  1. 参数匹配：/p/:lang/doc可以匹配/p/c/doc或者/p/go/doc
  2. 通配符*。例如/static/*filepath，可以匹配/static/fav.ico，也可以匹配/static/js/jQuery.js，这种模式常用于静态服务器，能够递归的匹配子路径。

Trie木の実現

1
2
3
4
5
6
ttype node struct {
  pattern string //带匹配路由，例如/p/:lang
  part string //路由中的一部分，例如:lang
  children []*node //子节点，例如[doc, tutorial,intro]
  isWild bool //是否精确匹配，part含有:或*时为true
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//第一个匹配成功的节点，用于插入
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
}

对于路由来说，注册和匹配是最重要的。开发服务时，注册路由规则，映射handler; 访问时，匹配路由规则，查找到对应的handler。因此，Trie树需要支持节点的插入与查询。插入功能很简单，递归查找每一层的节点，如果没有匹配到当前part的节点，则新建一个。有一点需要注意，/p/:lang/doc只有在第三层节点，即doc节点，pattern才会设置为/p/:lang/doc。

p和:lang节点的pattern属性皆为空。因此，当匹配结束时，我们可以使用n.pattern == ""来判断路由规则是否匹配成功。例如，/p/python虽能成功匹配到:lang，但lang的pattern值为空，因此匹配失败。查询功能，同样也是递归查询每一层的节点，退出规则是，匹配到了*，匹

配失败，或者匹配到了第len(parts)层节点。

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
// Trie tree's insert
func (n *node) insert(pattern string, parts []string, height int) {
  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)
}

//Trie tree's search
func (n *node) search(parts []string, height int) *node{
  if len(parts) == height || strings.HasPrefix(n.part, '*') {
    if n.pattern == ""{
      return nil
    }
    return n
  }
  
  part := parts[height]
  children := n.matchChildren(part)
  
  for _, child := range children {
    result := child.search(parts, height+1)
    if result != nil {
      return result
    }
  }
  
  return nil
}

Router

Trie 树的插入和查找实现之后，就可以将Trie树应用到路由之中了。使用roots来储存每种请求方式的Trie树根节点。使用handlers存储每种请求方式的HandlerFunc。getRoute函数中，还解析了:和*两种匹配符的参数，返回一个map。例如/p/go/doc匹配到/p/:lang/doc，解析结果为：{lang:"go"}，/static/css/xiaogeamadeus.css匹配到/static/*filepath，解析结果为{file path:"css/xiaogeamadeus.css"}

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
61
62
63
64
65
66
67
68
69
70
type router struct{
  roots    map[string]*node
  handlers map[string]HandlerFunc
}

// roots key eg, roots['GET'] roots['POST']
// handlers 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),
  }
}

// Only one * is allowed
func parsePattern(pattern stirng) []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)
  
  if n != nil {
    parts : parsePattern(n.pattern)
    for index, part := range parts {
      if part[0] == ':'{
        params[part[1:]] = searchParts[index]
      }
      if parts[0] == '*'&& len(part) >1{
        params[part[1:]] = strings.Join(searchParts[index:],"/")
        break
      }
    }
    return n, params
  }
  
  return nil, nil
}

Contextとhandleの変化

在HandleFunc 中，希望能够访问到解析的参数。因此，我们需要对Context对象增加一个属性和方法，来提供对路由参数的访问。我们将解析后的参数存储到Params中，通过c/Param("lang")的方式获取到对应的值。