• 从零实现Web框架Geo教程-前缀树路由-03



    本教程参考:七天用Go从零实现Web框架Gee教程


    引言

    本文主要看点;

    • 使用 Trie 树实现动态路由(dynamic route)解析。
    • 支持两种模式:name和*filepath

    Trie 树简介

    之前,我们用了一个非常简单的map结构存储了路由表,使用map存储键值对,索引非常高效,但是有一个弊端,键值对的存储的方式,只能用来索引静态路由。那如果我们想支持类似于/hello/:name这样的动态路由怎么办呢?所谓动态路由,即一条路由规则可以匹配某一类型而非某一条固定的路由。例如/hello/:name,可以匹配/hello/geektutu、hello/jack等。

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

    在这里插入图片描述
    实现动态路由最常用的数据结构,被称为前缀树(Trie树)。看到名字你大概也能知道前缀树长啥样了:每一个节点的所有的子节点都拥有相同的前缀。这种结构非常适用于路由匹配,比如我们定义了如下路由规则:

    • /:lang/doc
    • /:lang/tutorial
    • /:lang/intro
    • /about
    • /p/blog
    • /p/related

    我们用前缀树来表示,是这样的。

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

    接下来我们实现的动态路由具备以下两个功能。

    • 参数匹配:。例如 /p/:lang/doc,可以匹配 /p/c/doc 和 /p/go/doc。
    • 通配*。例如/static/*,可以匹配/static/fav.ico,也可以匹配/static/js/jQuery.js,这种模式常用于静态服务器,能够递归地匹配子路径。

    Trie 树实现

    首先我们需要设计树节点上应该存储那些信息。

    type node struct {
    	pattern  string // 待匹配路由,例如 /p/:lang
    	part     string // 当前节点代表的请求路径中的一部分,例如 :lang
    	children []*node // 子节点,例如 [doc, tutorial, intro]
    	isWild   bool // 当前节点是否是模糊匹配,part 含有 : 或 * 时为true
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

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

    对于路由来说,最重要的当然是注册与匹配了。

    开发服务时,注册路由规则,映射handler;访问时,匹配路由规则,查找到对应的handler。

    因此,Trie 树需要支持节点的插入与查询。


    插入功能很简单,递归查找每一层的节点,如果没有匹配到当前part的节点,则新建一个,有一点需要注意,/p/:lang/doc只有在第三层节点,即doc节点,pattern才会设置为/p/:lang/doc。p和:lang节点的pattern属性皆为空。
    在这里插入图片描述
    在上图中,其实我们是新增了两个路径映射,一个是/dhy/xpy,另一个是/xpy,我们不能将/dhy节点的pattern设置为/dhy,因为我们并没有添加能够处理/dhy请求的handler,而只有处理/dhy/xpy请求的handler。

    因此,如果某个节点的pattern不为空,则表示当前节点对应一个有效的路径映射,而如果pattern为空。则表示当前节点并不是一个有效的路径映射。

    //新增一条路由映射信息
    //insert 例如: /dhy/xpy/:name --> parts=['dhy','xpy',':name']
    //dhy是第一层---height=0
    //xpy ---> height=1
    //:name ---> height=2
    //假设当前前缀树:
    //               /
    //      /dhy    /dhx     /dha
    //    /xpy /xpa
    func (n *node) insert(pattern string, parts []string, height int) {
    	//只有到当前请求最后一层,pattern才会被设置
    	if len(parts) == height {
    		//在 :name层时,对应的node的pattern才会被设置为dhy/xpy/:name
    		n.pattern = pattern
    		return
    	}
    	//取出当前part
    	part := parts[height]
    	//取出当前节点下第一个匹配的子节点
    	child := n.matchChild(part)
    	//当去查询/xpy下的子节点哪一个为/:name时,会发现没有匹配的,然后返回nil
    	//此时就需要新创建一个节点到/xpy下的子节点中
    	if child == nil {
    		//创建一个子节点,例如: part= :name, isWild=true
    		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
    		n.children = append(n.children, child)
    	}
    	//调用子节点的insert
    	child.insert(pattern, parts, height+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
    • 28
    • 29
    • 30

    目前的insert版本还存在重复路由无法甄别而导致请求映射偏离预期的bug,这个在本文最后会进行分析


    查询功能,同样也是递归查询每一层的节点,退出规则是,匹配到了*,匹配失败,或者匹配到了第len(parts)层节点。

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

    //假设当前前缀树:
    //               /
    //      /dhy    /dhx     /dha
    //    /xpy /xpa
    //   /:name
    //我要查询 /dhy/xpy/hhh 对应的node节点
    //parts= ['dhy','xpy','hhh'] ,height=0
    func (n *node) search(parts []string, height int) *node {
    	//已经匹配到hhh节点层了,或者当前part对应*号,等于任意多层
    	if len(parts) == height || strings.HasPrefix(n.part, "*") {
    		//判断当前节点是否映射一个有效请求路径
    		if n.pattern == "" {
    			return nil
    		}
    		return n
    	}
    	//获取当前高度对应的part
    	part := parts[height]
    	//从前缀树中寻找当前请求匹配的所有children
    	children := n.matchChildren(part)
    	//遍历所有子节点
    	for _, child := range children {
    		//去每个子节点下寻找,直到找到最终匹配的那个节点
    		result := child.search(parts, height+1)
    		if result != nil {
    			return result
    		}
    	}
    
    	return nil
    }
    
    • 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

    Router

    Trie 树的插入与查找都成功实现了,接下来我们将 Trie 树应用到路由中去吧。我们使用 roots 来存储每种请求方式的Trie 树根节点。使用 handlers 存储每种请求方式的 HandlerFunc 。

    getRoute 函数中,还解析了:和*两种匹配符的参数,返回一个 map 。例如/p/go/doc匹配到/p/:lang/doc,解析结果为:{lang: “go”},/static/css/dhy.css匹配到/static/*filepath,解析结果为{filepath: “css/dhy.css”}。

    package geo
    
    import (
    	"strings"
    )
    
    type router struct {
    	//key存储请求方式, eg: roots['GET'] roots['POST']
    	roots map[string]*node
    	//key存储请求路径,eg, handlers['GET-/p/:lang/doc'], handlers['POST-/p/book']
    	handlers map[string]HandlerFunc
    }
    
    func newRouter() *router {
    	return &router{
    		roots:    make(map[string]*node),
    		handlers: make(map[string]HandlerFunc),
    	}
    }
    
    //如果请求路径只有一个单独的*,代表无论多少层路径都可以匹配上
    //否则,将一个普通的请求路径: /dhy/xpy/:name --->按照'/'分割为[dhy,xpy,:name]数组后返回
    // /dhy/*xpy/hhh --> [dhy,*xpy]---> *xpy节点对应的isWild为true
    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
    }
    
    //请求方式: GET,POST等
    //请路径: /dhy/xpy等
    //对应的处理器
    func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
    	///dhy/xpy/:name --->按照'/'分割为[dhy,xpy,:name]数组后返回
    	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
    }
    
    //此时的path是实际请求路径,例如: /dhy/xpy/hhh
    func (r *router) getRoute(method string, path string) (*node, map[string]string) {
    	///dhy/xpy/hhh --->按照'/'分割为[dhy,xpy,hhh]数组后返回
    	searchParts := parsePattern(path)
    	//存放动态参数 --> /dhy/xpy/:name 这里:name对应的实际值
    	params := make(map[string]string)
    	//先按请求方式,取出对应的前缀树
    	root, ok := r.roots[method]
    	//如果不存在,直接返回
    	if !ok {
    		return nil, nil
    	}
    	//从第一层开始搜索起来
    	n := root.search(searchParts, 0)
    	//如果搜索到了
    	if n != nil {
    		//取出当前节点对应的pattern,假设这里为/dhy/xpy/:name
    		parts := parsePattern(n.pattern)
    		for index, part := range parts {
    			//判断是否存在动态参数
    			if part[0] == ':' {
    				//实际请求: /dhy/xpy/hhh 匹配到的路径: /dhy/xpy/:name
    				//这里取出name ,对应hhh
    				//因此,这里实际保存的是: params[name]=hhh
    				params[part[1:]] = searchParts[index]
    			}
    			//实际请求: /dhy/xpy/hhh 匹配到的路径: /dhy/*x/dhy
    			//*x第一个字符为*,并且本身字符长度大于1
    			if part[0] == '*' && len(part) > 1 {
    				//params[x]=xpy/hhh
    				params[part[1:]] = strings.Join(searchParts[index:], "/")
    				break
    			}
    		}
    		//返回对应的node节点和动态参数
    		return n, params
    	}
    	//如果没找到
    	return nil, nil
    }
    
    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    Context与handle的变化

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

    • context.go
    //Context 内部维护当前请求的一系列信息
    type Context struct {
    	//req和res
    	Writer http.ResponseWriter
    	Req    *http.Request
    	//关于请求的相关信息
    	Path   string
    	Method string
    	Params map[string]string
    	//关于响应相关信息
    	StatusCode int
    }
    
    func (c *Context) Param(key string) string {
    	value, _ := c.Params[key]
    	return value
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • router.go
    func (r *router) handle(c *Context) {
    	//先通过当前请求方法,和真实请求路径
    	//从前缀树中获取到对应的node节点和动态参数
    	n, params := r.getRoute(c.Method, c.Path)
    	if n != nil {
    		//将当前请求对应的动态参数绑定到context上
    		c.Params = params
    		key := c.Method + "-" + n.pattern
    		//构造key,取出对应的处理器,来处理当前请求
    		r.handlers[key](c)
    	} else {
    		//如果没有获取到对应node节点,说明没有相关处理器
    		c.String(http.StatusNotFound, "404 NOT FOUND: %s\n", c.Path)
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    router.go的变化比较小,比较重要的一点是,在调用匹配到的handler前,将解析出来的路由参数赋值给了c.Params。这样就能够在handler中,通过Context对象访问到具体的值了。


    单元测试

    func newTestRouter() *router {
    	r := newRouter()
    	r.addRoute("GET", "/", nil)
    	r.addRoute("GET", "/hello/:name", nil)
    	r.addRoute("GET", "/hello/b/c", nil)
    	r.addRoute("GET", "/hi/:name", nil)
    	r.addRoute("GET", "/assets/*filepath", nil)
    	return r
    }
    
    func TestParsePattern(t *testing.T) {
    	ok := reflect.DeepEqual(parsePattern("/p/:name"), []string{"p", ":name"})
    	ok = ok && reflect.DeepEqual(parsePattern("/p/*"), []string{"p", "*"})
    	ok = ok && reflect.DeepEqual(parsePattern("/p/*name/*"), []string{"p", "*name"})
    	if !ok {
    		t.Fatal("test parsePattern failed")
    	}
    }
    
    func TestGetRoute(t *testing.T) {
    	r := newTestRouter()
    	n, ps := r.getRoute("GET", "/hello/dhy")
    
    	if n == nil {
    		t.Fatal("nil shouldn't be returned")
    	}
    
    	if n.pattern != "/hello/:name" {
    		t.Fatal("should match /hello/:name")
    	}
    
    	if ps["name"] != "dhy" {
    		t.Fatal("name should be equal to 'dhy'")
    	}
    
    	fmt.Printf("matched path: %s, params['name']: %s\n", n.pattern, ps["name"])
    
    }
    
    • 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

    使用Demo

    package main
    
    import (
    	"geo"
    	"net/http"
    )
    
    func main() {
    	r := geo.New()
    	r.GET("/", func(c *geo.Context) {
    		c.HTML(http.StatusOK, "

    Hello geo

    "
    ) }) r.GET("/hello", func(c *geo.Context) { c.String(http.StatusOK, "hello %s, you're at %s\n", c.Query("name"), c.Path) }) r.GET("/hello/:name", func(c *geo.Context) { c.String(http.StatusOK, "hello %s, you're at %s\n", c.Param("name"), c.Path) }) r.GET("/assets/*filepath", func(c *geo.Context) { c.JSON(http.StatusOK, geo.H{"filepath": c.Param("filepath")}) }) r.Run(":9999") }
    • 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

    Bug分析

    前缀树的insert Bug

    目前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)
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    如果第一次插入的pattern为/:age,method 为 GET,handlefunc 为 handleAge()

    那么会生成一个这样的 node

    nodeAge = node{
        pattern:  "/:age",
        part:     ":age",
        children: nil,
        isWild:   true,
    }
    handlers["GET-:age"] = handleAge
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    第二次插入的 pattern 为 /18 ,method 与第一次相同,仍然为 GET,handlefunc 为 handle18(),此时并不会修改之前的 node,而是修改了之前 nodeAge 的 pattern。

    nodeAge = node{
        pattern:  "/18",
        part:     ":age",
        children: nil,
        isWild:   true,
    }
    handlers["GET-:age"] = handleAge
    handlers["GET-18"] =  handle18
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    接下来看看handle()函数

    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)
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    当有一个 /19 的请求到来时,将会匹配到 nodeAge,但是由于 nodeAge 的 pattern 变成了 18,因此将会被 handle18() 处理,这不太合适。

    GIN的做法是将冲突的路由直接panic了。


    完整源码

    • tire.go
    package geo
    
    import "strings"
    
    type node struct {
    	pattern  string  // 待匹配路由,例如 /p/:lang
    	part     string  // 当前节点代表的请求路径中的一部分,例如 :lang
    	children []*node // 子节点,例如 [doc, tutorial, intro]
    	isWild   bool    // 当前节点是否是模糊匹配,part 含有 : 或 * 时为true
    }
    
    // 第一个匹配成功的节点,用于插入
    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
    }
    
    //新增一条路由映射信息
    //insert 例如: /dhy/xpy/:name --> parts=['dhy','xpy',':name']
    //dhy是第一层---height=0
    //xpy ---> height=1
    //:name ---> height=2
    //假设当前前缀树:
    //               /
    //      /dhy    /dhx     /dha
    //    /xpy /xpa
    func (n *node) insert(pattern string, parts []string, height int) {
    	//只有到当前请求最后一层,pattern才会被设置
    	if len(parts) == height {
    		//在 :name层时,对应的node的pattern才会被设置为dhy/xpy/:name
    		n.pattern = pattern
    		return
    	}
    	//取出当前part
    	part := parts[height]
    	//取出当前节点下第一个匹配的子节点
    	child := n.matchChild(part)
    	//当去查询/xpy下的子节点哪一个为/:name时,会发现没有匹配的,然后返回nil
    	//此时就需要新创建一个节点到/xpy下的子节点中
    	if child == nil {
    		//创建一个子节点,例如: part= :name, isWild=true
    		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
    		n.children = append(n.children, child)
    	}
    	//调用子节点的insert
    	child.insert(pattern, parts, height+1)
    }
    
    //假设当前前缀树:
    //               /
    //      /dhy    /dhx     /dha
    //    /xpy /xpa
    //   /:name
    //我要查询 /dhy/xpy/hhh 对应的node节点
    //parts= ['dhy','xpy','hhh'] ,height=0
    func (n *node) search(parts []string, height int) *node {
    	//已经匹配到hhh节点层了,或者当前part对应*号,等于任意多层
    	if len(parts) == height || strings.HasPrefix(n.part, "*") {
    		//判断当前节点是否映射一个有效请求路径
    		if n.pattern == "" {
    			return nil
    		}
    		return n
    	}
    	//获取当前高度对应的part
    	part := parts[height]
    	//从前缀树中寻找当前请求匹配的所有children
    	children := n.matchChildren(part)
    	//遍历所有子节点
    	for _, child := range children {
    		//去每个子节点下寻找,直到找到最终匹配的那个节点
    		result := child.search(parts, height+1)
    		if result != nil {
    			return result
    		}
    	}
    
    	return nil
    }
    
    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • router.go
    package geo
    
    import (
    	"net/http"
    	"strings"
    )
    
    type router struct {
    	//key存储请求方式, eg: roots['GET'] roots['POST']
    	roots map[string]*node
    	//key存储请求路径,eg, handlers['GET-/p/:lang/doc'], handlers['POST-/p/book']
    	handlers map[string]HandlerFunc
    }
    
    func newRouter() *router {
    	return &router{
    		roots:    make(map[string]*node),
    		handlers: make(map[string]HandlerFunc),
    	}
    }
    
    //如果请求路径只有一个单独的*,代表无论多少层路径都可以匹配上
    //否则,将一个普通的请求路径: /dhy/xpy/:name --->按照'/'分割为[dhy,xpy,:name]数组后返回
    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
    }
    
    //请求方式: GET,POST等
    //请路径: /dhy/xpy等
    //对应的处理器
    func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
    	///dhy/xpy/:name --->按照'/'分割为[dhy,xpy,:name]数组后返回
    	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
    }
    
    //此时的path是实际请求路径,例如: /dhy/xpy/hhh
    func (r *router) getRoute(method string, path string) (*node, map[string]string) {
    	///dhy/xpy/hhh --->按照'/'分割为[dhy,xpy,hhh]数组后返回
    	searchParts := parsePattern(path)
    	//存放动态参数 --> /dhy/xpy/:name 这里:name对应的实际值
    	params := make(map[string]string)
    	//先按请求方式,取出对应的前缀树
    	root, ok := r.roots[method]
    	//如果不存在,直接返回
    	if !ok {
    		return nil, nil
    	}
    	//从第一层开始搜索起来
    	n := root.search(searchParts, 0)
    	//如果搜索到了
    	if n != nil {
    		//取出当前节点对应的pattern,假设这里为/dhy/xpy/:name
    		parts := parsePattern(n.pattern)
    		for index, part := range parts {
    			//判断是否存在动态参数
    			if part[0] == ':' {
    				//实际请求: /dhy/xpy/hhh 匹配到的路径: /dhy/xpy/:name
    				//这里取出name ,对应hhh
    				//因此,这里实际保存的是: params[name]=hhh
    				params[part[1:]] = searchParts[index]
    			}
    			//实际请求: /dhy/xpy/hhh 匹配到的路径: /dhy/*x/dhy
    			//*x第一个字符为*,并且本身字符长度大于1
    			if part[0] == '*' && len(part) > 1 {
    				//params[x]=xpy/hhh
    				params[part[1:]] = strings.Join(searchParts[index:], "/")
    				break
    			}
    		}
    		//返回对应的node节点和动态参数
    		return n, params
    	}
    	//如果没找到
    	return nil, nil
    }
    
    func (r *router) handle(c *Context) {
    	//先通过当前请求方法,和真实请求路径
    	//从前缀树中获取到对应的node节点和动态参数
    	n, params := r.getRoute(c.Method, c.Path)
    	if n != nil {
    		//将当前请求对应的动态参数绑定到context上
    		c.Params = params
    		key := c.Method + "-" + n.pattern
    		//构造key,取出对应的处理器,来处理当前请求
    		r.handlers[key](c)
    	} else {
    		//如果没有获取到对应node节点,说明没有相关处理器
    		c.String(http.StatusNotFound, "404 NOT FOUND: %s\n", c.Path)
    	}
    }
    
    
    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • context.go
    package geo
    
    import (
    	"encoding/json"
    	"fmt"
    	"net/http"
    )
    
    type H map[string]interface{}
    
    //Context 内部维护当前请求的一系列信息
    type Context struct {
    	//req和res
    	Writer http.ResponseWriter
    	Req    *http.Request
    	//关于请求的相关信息
    	Path   string
    	Method string
    	Params map[string]string
    	//关于响应相关信息
    	StatusCode int
    }
    
    func (c *Context) Param(key string) string {
    	value, _ := c.Params[key]
    	return value
    }
    
    func newContext(w http.ResponseWriter, req *http.Request) *Context {
    	return &Context{
    		Writer: w,
    		Req:    req,
    		Path:   req.URL.Path,
    		Method: req.Method,
    	}
    }
    
    func (c *Context) PostForm(key string) string {
    	return c.Req.FormValue(key)
    }
    
    func (c *Context) Query(key string) string {
    	return c.Req.URL.Query().Get(key)
    }
    
    //Status 设置响应状态码
    func (c *Context) Status(code int) {
    	c.StatusCode = code
    	//如果不手动调用WriteHeader设置响应状态码,那么默认会调用WriteHeader(http.StatusOK)
    	c.Writer.WriteHeader(code)
    }
    
    func (c *Context) SetHeader(key string, value string) {
    	c.Writer.Header().Set(key, value)
    }
    
    func (c *Context) String(code int, format string, values ...interface{}) {
    	c.SetHeader("Content-Type", "text/plain")
    	c.Status(code)
    	c.Writer.Write([]byte(fmt.Sprintf(format, values...)))
    }
    
    func (c *Context) JSON(code int, obj interface{}) {
    	c.SetHeader("Content-Type", "application/json")
    	c.Status(code)
    	encoder := json.NewEncoder(c.Writer)
    	if err := encoder.Encode(obj); err != nil {
    		http.Error(c.Writer, err.Error(), 500)
    	}
    }
    
    func (c *Context) Data(code int, data []byte) {
    	c.Status(code)
    	c.Writer.Write(data)
    }
    
    func (c *Context) HTML(code int, html string) {
    	c.SetHeader("Content-Type", "text/html")
    	c.Status(code)
    	c.Writer.Write([]byte(html))
    }
    
    
    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • geo.go
    package geo
    
    import (
    	"net/http"
    )
    
    type HandlerFunc func(*Context)
    
    type Engine struct {
    	//路由表
    	router *router
    }
    
    func New() *Engine {
    	return &Engine{router: newRouter()}
    }
    
    //路由的添加
    
    func (engine *Engine) addRoute(method string, pattern string, handler HandlerFunc) {
    	engine.router.addRoute(method, pattern, handler)
    }
    
    func (engine *Engine) GET(pattern string, handler HandlerFunc) {
    	engine.addRoute("GET", pattern, handler)
    }
    
    func (engine *Engine) POST(pattern string, handler HandlerFunc) {
    	engine.addRoute("POST", pattern, handler)
    }
    
    // 服务器启动
    
    func (engine *Engine) Run(addr string) (err error) {
    	return http.ListenAndServe(addr, engine)
    }
    
    // 处理请求---请求统一派发的入口
    func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
    	//为当前请求构建上下文环境,然后去路由表中查询出对应的处理器进行处理
    	c := newContext(w, req)
    	engine.router.handle(c)
    }
    
    
    • 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
    • main.go
    package main
    
    import (
    	"geo"
    	"net/http"
    )
    
    func main() {
    	r := geo.New()
    	r.GET("/", func(c *geo.Context) {
    		c.HTML(http.StatusOK, "

    Hello geo

    "
    ) }) r.GET("/hello", func(c *geo.Context) { c.String(http.StatusOK, "hello %s, you're at %s\n", c.Query("name"), c.Path) }) r.GET("/hello/:name", func(c *geo.Context) { c.String(http.StatusOK, "hello %s, you're at %s\n", c.Param("name"), c.Path) }) r.GET("/assets/*filepath", func(c *geo.Context) { c.JSON(http.StatusOK, geo.H{"filepath": c.Param("filepath")}) }) r.Run(":9999") }
    • 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
  • 相关阅读:
    使用Python 创建 AI Voice Cover
    Linux---Socket
    昭通市鲁甸县卯家湾安置区:凝心聚力 共谱民族团结进步新篇章
    CertiK CSO Dr. Kang Li 确认出席Hack .Summit() 香港区块链盛会
    DStream转换介绍_大数据培训
    Camera-Related Architecture
    【大数据】-- dataworks 创建odps 的 hudi 外表
    SLAM ORB-SLAM2(1)总体框架
    【全3D打印坦克——基于Arduino履带式机器人】
    Android学习笔记 25. Activity与Fragment通信
  • 原文地址:https://blog.csdn.net/m0_53157173/article/details/126558988