Go语言动手写Web框架 - Gee第三天 路由Router | 极客兔兔

[geektutu]

https://geektutu.com/post/gee-day3.html

7天用 Go语言 从零实现Web框架教程(7 days implement golang web framework from scratch tutorial)，用 Go语言/golang 动手写Web框架，从零实现一个Web框架，从零设计一个Web框架。本文介绍了如何用 Trie 前缀树实现路由。支持简单的参数解析和通配符的场景。

[fakecheck]

我感觉大家理解有点困难跟注释有些关系 比如 isWild的注释是 是否是精确匹配 这个注释写成：是否是模糊匹配感觉更达意一些

[DurantVivado]

感觉单元例子还是太少了。 然后应用场景受限，无法真正实现通配符匹配

[qizong007]

@geektutu @liweiforeveryoung 非常感谢，指出了非常关键的问题。

第一个bug，存在覆盖的问题，gin 的做法才是对的，应该把问题暴露给用户。 第二个问题，http 请求是并发的，但每一个请求都会调用 ServeHTTP ，这个方法中，context 每次都创建新的，不会对同一个context进行写入。

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
  c := newContext(w, req)
  engine.router.handle(c)
}

大佬，我目前写了一个思路，测试是可行的：

（1）把matchChild()拆成两个函数：

// 寻找第一个模糊匹配的节点，用于[插入]
func (n *node) findWildChild(part string) *node {
    for _, child := range n.children {
        if child.isWild {
            return child
        }
    }
    return nil
}

// 寻找第一个精确匹配的节点，用于[插入]
func (n *node) findSpecificChild(part string) *node {
    for _, child := range n.children {
        if child.part == part {
            return child
        }
    }
    return nil
}

插入逻辑相应的需要改为：

// 插入
func (n *node) insert(pattern string, parts []string, height int) {
    if len(parts) == height {
        n.pattern = pattern
        return
    }
    part := parts[height]
    // ---------- here ----------
    child := n.findWildChild(part)
    if child != nil && child.isWild && (part[0] == ':' || part[0] == '*') {
        panic(fmt.Sprintf("now %s(in %s) is conflict with %s", part, pattern, child.part))
    }
    child = n.findSpecificChild(part)
    // ---------- here ----------
    if child == nil {
        child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
        n.children = append(n.children, child)
    }
    child.insert(pattern, parts, height+1)
}

大致主要是为了解决冲突问题：如果已有模糊匹配的节点，且当前节点也为模糊匹配节点，直接panic；接着就是再找一遍有没有其他节点，没有的话就插入

（2）做优先级处理（在addRoute()的末尾加上r.roots[method].sort()）

插入代码：

// 优先级保证 eg. /18 > /:age
func (n *node) sort() {
    if n == nil {
        return
    }
    list := n.children
    sort.Slice(n.children, func(i, j int) bool {
        if !n.children[i].isWild &&  n.children[j].isWild {
            return true
        } else if n.children[i].isWild && !n.children[j].isWild {
            return false
        } else {
            return len(n.children[i].pattern) < len(n.children[j].pattern)
        }
    })
    if list != nil && len(list) > 0 {
        for i := range list {
            list[i].sort()
        }
    }
}

[fatFire]

感觉这个前缀树的实现太简单粗暴了，每个Part都直接作为一个节点，这样子插入是方便了，但是每次匹配子节点效率很低，也有点浪费空间。

你有什么好的改善思路吗

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[fatFire]

@BrianQy 对比了一下github的代码，在trie.go里多了一个方法travel，在router.go里多了一个getRouters的方法，在文中并没有提到，可以麻烦介绍说明一下吗？

travel是遍历某个root下的所有存在pattern的route，getRouters里面就是通过传入一个指定的Method(比如GET,POST)，调用travel这个方法来获取该Method作为root下的所有route，返回的nodes就是一个个已注册的route，比如/p/:lang/hello 等

想问下对于travel的参数以下两个写法有区别吗

func (n *node) travel(list *([]*node)) {
    if n.pattern != "" {
        *list = append(*list, n)
    }
    for _, child := range n.children {
        child.travel(list)
    }
}

func (n *node) travel(list []*node) {
    if n.pattern != "" {
        list = append(list, n)
    }
    for _, child := range n.children {
        child.travel(list)
    }
}

[greenhand123138]

开始蒙圈

[PeiLeizzz]

@fatFire

@BrianQy 对比了一下github的代码，在trie.go里多了一个方法travel，在router.go里多了一个getRouters的方法，在文中并没有提到，可以麻烦介绍说明一下吗？

travel是遍历某个root下的所有存在pattern的route，getRouters里面就是通过传入一个指定的Method(比如GET,POST)，调用travel这个方法来获取该Method作为root下的所有route，返回的nodes就是一个个已注册的route，比如/p/:lang/hello 等

想问下对于travel的参数以下两个写法有区别吗

func (n *node) travel(list *([]*node)) {
  if n.pattern != "" {
      *list = append(*list, n)
  }
  for _, child := range n.children {
      child.travel(list)
  }
}

func (n *node) travel(list []*node) {
  if n.pattern != "" {
      list = append(list, n)
  }
  for _, child := range n.children {
      child.travel(list)
  }
}

如果值传递，list 扩容后地址改变，函数返回后，对原 list 没影响；用指针会影响原 list 指向的地址

[ZAKLLL]

更新了下大佬的trie树，支持/ 多级匹配，存在模糊匹配时，优先匹配 静态pattern ,模糊匹配规则顺序为 :xxx -> / -> /

package gee

import (
    "log"
    "sort"
    "strings"
)

type node struct {
    pattern  string  // 待匹配路由，例如 /p/:lang
    part     string  // 路由中的一部分，例如 :lang
    children []*node // 子节点，例如 [doc, tutorial, intro]
    isWild   bool    // 是否模糊匹配，part 含有 : 或 * 时为true
    isLeaf   bool    //是否为叶子节点
}

// 第一个匹配成功的节点，用于插入
func (n *node) matchChild(part string) *node {
    for _, child := range n.children {
        //完全相等 或者都是:xxx 或者都是* 的情况
        if child.part == part || (len(child.part) > 0 && len(part) > 0 && (child.part[0] == part[0] && part[0] == ':')) {
            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
}

func (n *node) insert(pattern string, parts []string, height int) {

    if len(parts) == height {
        if n.isLeaf {
            log.Fatalf("冲突: pattern: %s 与 pattern: %s 同义!", n.pattern, pattern)
        }
        n.isLeaf = true
        n.pattern = pattern
        return
    }

    part := parts[height]
    child := n.matchChild(part)
    if child == nil {
        child = &node{part: part, isWild: len(part) > 0 && (part[0] == ':' || part[0] == '*')}
        n.children = append(n.children, child)
    }
    child.insert(pattern, parts, height+1)
}

func (n *node) search(parts []string, height int) *node {
    //if height > len(parts) {
    //  return nil
    //}

    if height == len(parts) {
        if n.isLeaf {
            //精准匹配
            if n.part == parts[height-1] {
                return n
            }
            //:xxx /*
            if n.isWild {
                return n
            }
        } else {
            return nil
        }
    } else if n.part == "**" {
        return n
    }

    part := parts[height]
    children := n.matchChildren(part)
    indexMap := map[string]int{"": 0, ":": 1, "*": 2, "**": 3}
    //children
    sort.Slice(children, func(i, j int) bool {
        a := children[i]
        b := children[j]
        af := ""
        bf := ""
        if a.isWild {
            if strings.HasPrefix(a.part, ":") {
                af = ":"
            } else if strings.HasPrefix(a.part, "*") {
                af = "*"
            } else {
                af = "**"
            }
        }
        if b.isWild {
            if strings.HasPrefix(b.part, ":") {
                bf = ":"
            } else if strings.HasPrefix(b.part, "*") {
                bf = "*"
            } else {
                bf = "**"
            }
        }
        return indexMap[af] < indexMap[bf]
        //children[j]

        //// 优先精准
        //if !a.isWild && b.isWild {
        //  return true
        //}
        //// :xx -> /* -> /**
        //if a.isWild && b.isWild {
        //  if a.part == "**" {
        //      return false
        //  }
        //  if a.part == "*" {
        //      return false
        //  }
        //}
        //return true
    })
    for _, child := range children {
        result := child.search(parts, height+1)
        if result != nil {
            return result
        }
    }
    return nil
}

-----------------test code--------------

func Test(t *testing.T) {
    root := node{}
    for _, item := range []string{"/", "/hello", "/hi/:user/do", "/hi/:xxx/do1", "/hi/t1", "/hi/*", "/hi/**"} {
        root.insert(item, parsePattern(item), 0)
    }
    println(root.search([]string{"hi", "xxx", "do1x"}, 0).pattern)

    println(root.search([]string{""}, 0).pattern)

    println(root.search([]string{"hi", "xx", "do"}, 0).pattern)

    println(root.search([]string{"hi", "t1"}, 0).pattern)

    println(root.search([]string{"hi", "t2"}, 0).pattern)

    println(root.search([]string{"hi", "t3", "t4"}, 0).pattern)
}

[ueueQ]

【翻了翻评论，已经有人在两年前发现了】这节确实有问题，我没去github看，只在这里看的，如果r.addRoute("GET", "/hello/:name", nil) r.addRoute("GET", "/hello/b", nil) r.addRoute("GET", "/hello/c", nil) 连续执行这三个，b就会被覆盖掉

[ueueQ]

鼓捣了两天，去掉了*的通配符匹配。终于写完了

[l1chao]

这一章看得我猪脑过载呜呜

[ephonzhang]

建议可以insert方法之前，可以说明一下参数的含义或者举个例子，我看了好久才想明白呢

[deng565430]

小白想问问，路由匹配能用正则吗

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[limerence-yu]

感觉加点注释好些，看的好累。。。

[Malarkey-Jhu]

這里的trie樹，跟一般寫的字典樹不同的地方在於，同一樹層裡可能出現“多個”匹配。這是因為模糊匹配的原因，所以需要 matchChildren 方法找到同一樹層中匹配的節點，一個一個去深度遍歷查找。

[Park-Jiyeonn]

acmer表示，能在项目中用到学过的算法，非常开心！

[blight19]

这里其实还可以将带参数的node中的位置和类型记录在一个map中，省去getRoute函数中每次都遍历的时间

[ZirongCai]

啊好久没写递归了，感谢大佬让我重新复习了一遍。习惯性的把insert和search两个接口简化成了只接收一个参数，虽然是内部使用还是觉得简洁点更舒服hhh

[fatrbaby]

child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'} 我不小心写成了 child := &node{part: part, isWild: part[0] == ':' || part[0] == '*'} 查了好久，玛得

[bynow2code]

child 那个地方很容易写成阴影变量

[haoliudoc]

非常好的线段树练习，算法与应用结合了属于

[Fencent]

@whitebluepants

@yufeifly 问一个比较蠢的问题。search函数中调用了matchChildren，matchChildren什么情况下会有多个匹配返回呢？

这个问题我也想知道，大概是添加了这两个路由/hello/:name, /hello/tutu. 然后访问/hello/tutu的时候，就会返回多个匹配了吧。 也就是前面评论说的路由冲突？（还没看gin的源码，会不会就是matchChildren返回多个的时候，直接panic呢？

试着回答一下，如果是先添加了动态路由再添加静态路由，就不会出现查找时返回多个值的问题。例如先插入 /hello/:name ,再插入 /hello/Fer ，此时 Fer 存储在 :name 这个节点中，其中 pattern=/hello/Fer,但也引发了一个Bug，若要继续添加 /hello/Sugar, 新添加的 route 会覆盖此前的pattern，导致 /hello/Fer 找不到了。

如果是先添加了静态路由再添加动态路由，就会在查询时返回多个值。例如先插入 /hello/Fer/age, 再插入 /hello/:name/sex, 此时若想查找 /hello/Fer/sex,会先匹配上 Fer，可是后来没有找到，便会匹配上 :name，从而找到 /hello/:name/sex.

才学疏浅，还请指正

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[vapausw]

这个测试name should be equal to 'geektutu'过不了报错死活找不到咋办

[vapausw]

靠找到报错了打错一个符号，找了两个小时

[limits220284]

太精华了

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[limits220284]

@haoliudoc 非常好的线段树练习，算法与应用结合了属于

这不是前缀树吗，怎么成了线段树

[lv997]

这个struct 给我整懵了，好好静下心来看才看懂 children 一直在嵌套

[SCUTking]

有个问题，r.addRoute("GET", "/hello/:name", nil) r.addRoute("GET", "/*", nil) 优先级如何匹配 还是说有报错处理

[SCUTking]

如果有多条路由满足规则，按照插入的顺序进行 比如插入/后，再添加/hello等路由都只会映射到/那里

[Boss-Li12]

通过Trie🌲解析了url中的参数了

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[cryacry]

有点bug，测试中先后添加了“/hello/:name”和"/hello/b/c"路由，在查找“/hello/geektutu/c”该路由时本该不存在的，但是匹配到了"/hello/b/c"这个路由上

[lv997]

@cryacry 有点bug，测试中先后添加了“/hello/:name”和"/hello/b/c"路由，在查找“/hello/geektutu/c”该路由时本该不存在的，但是匹配到了"/hello/b/c"这个路由上

尝试一下你的测试用例发现确实如此。

[coderZoe]

写了一个for循环版的而非递归版的insert，感觉for的版本更清晰些：

func (n *node) insertFor(pattern string, parts []string) {
    for _, part := range parts {
        child := n.matchChild(part)
        if child == nil {
            child = &node{
                part:   part,
                isWild: part[0] == ':' || part[0] == '*',
            }
            n.children = append(n.children, child)
        }
        n = child
    }
    n.pattern = pattern
}

[yufeifly]

您好，您的邮件已收到，谢谢。——熊宇飞

[coderZoe]

这里设计感觉有些割裂，router里面同时存了前缀树和handlerFunc的map，而这俩又各算各的，前缀树只拿来用来提取参数，handlerFunc的map只用来根据method+pattern获取handlerFunc。 我想是不是可以直接将handlerFunc存在前缀树的node里，这样拿到node后其实也就拿到了handlerFunc，代码大概如下： trie.go

package gee

import "strings"

// 需要注意pattern是整个路由 如/p/:lang/doc
// 而part是路由的一部分 如:lang
// 一个node其实是路由part的封装
// 只有叶子节点的pattern才有意义 也即只有doc节点 其pattern才是/p/:lang/doc
// 非叶子节点的pattern和handler属性为空
type node struct {
    pattern  string      //待匹配的路由
    handler  HandlerFunc //当前路由的处理函数，只有末节点才有处理函数
    part     string      //路由的一部分
    children []*node     //子节点
    isWild   bool        //是否模糊匹配
}

// 初始化 假的根节点
func NewTrie() *node {
    return &node{}
}

func (node *node) matchChild(part string) *node {
    for _, child := range node.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
}

// 将pattern拆为多个part，如p/:lang/doc拆为 [p,:lang,doc]
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
}

// 注册一个路径和这个路径的处理函数
func (n *node) insert(pattern string, handler HandlerFunc) {
    parts := parsePattern(pattern)
    for _, part := range parts {
        child := n.matchChild(part)
        if child == nil {
            child = &node{
                part:   part,
                isWild: part[0] == ':' || part[0] == '*',
            }
            n.children = append(n.children, child)
        }
        n = child
    }
    n.pattern = pattern
    n.handler = handler
}

// 搜索 根据URL搜索这个URL对应的叶节点node
// 解释下这里为什么使用matchChildren而非matchChild 假设如下：
// 我们insert一个路由 /p/c/doc，随后又insert一个路由/p/:lang/src
// 这里p节点下肯定是有两个子节点的，分别是c和:lang
// 假设此时一条请求url是/p/c/src
// 如果search的时候选择matchChild而非matchChildren，很容易匹配到/p/c这条路，但这条路叶节点是doc 因此会找不到路由
// 我们知道其实/p/:lang这条路也是符合的，因此应该走这条路，所以需要通过matchChildren查出所有符合的children
func (n *node) search(pattern string) *node {
    parts := parsePattern(pattern)
    children := []*node{n}
    for _, part := range parts {
        children = doSearch(children, part)
    }
    if len(children) == 0 {
        return nil
    }
    return children[0]
}

func doSearch(nodes []*node, part string) []*node {
    matched := make([]*node, 0)
    for _, n := range nodes {
        matched = append(matched, n.matchChildren(part)...)
    }
    return matched
}

router.go

package gee

import (
    "errors"
    "strings"
)

// 改了HandlerFunc入参为Context了
type HandlerFunc func(*Context)

type Router struct {
    roots map[string]*node
}

//如下整个按gin aoi 做了个封装，可以看出gin的Engine其实就是个Handler，然后用net库起了个http server

func newRouter() *Router {
    return &Router{roots: make(map[string]*node)}
}

func (r *Router) addRouter(method string, pattern string, handler HandlerFunc) {
    if _, ok := r.roots[method]; !ok {
        r.roots[method] = NewTrie()
    }
    r.roots[method].insert(pattern, handler)
}

func (r *Router) GET(pattern string, handler HandlerFunc) {
    r.addRouter("GET", pattern, handler)
}

func (r *Router) POST(pattern string, handler HandlerFunc) {
    r.addRouter("POST", pattern, handler)
}

func (r *Router) getRouter(method string, pattern string) *node {
    root := r.roots[method]
    if root == nil {
        return nil
    } else {
        return root.search(pattern)
    }
}

func setParams(n *node, c *Context) {
    params := make(map[string]string)
    parts := parsePattern(n.pattern)
    searchParts := parsePattern(c.Path)
    for index, part := range parts {
        if part[0] == ':' {
            params[part[1:]] = searchParts[index]
        }
        if part[0] == '*' && len(part) > 1 {
            params[part[1:]] = strings.Join(searchParts[index:], "/")
            break
        }
    }
    c.Params = params
}

func (r *Router) handle(c *Context) {
    if node := r.getRouter(c.Method, c.Path); node != nil && node.handler != nil {
        //在这一步将params解析并设置进来
        setParams(node, c)
        node.handler(c)
    } else {
        c.errorCode(404, errors.New("404 NOT FOUND: "+c.Path+"\n"))
    }
}

main.go

package main

import "mygee3/gee"

func main() {
    r := gee.New()
    r.GET("/hi", func(c *gee.Context) {
        c.String(200, "URL.Path = %q\n", c.Path)
    })

    r.GET("/hello", func(c *gee.Context) {
        c.JSON(200, map[string]any{"name": "Tom", "age": 12})
    })
    r.GET("/p/:lang/doc", func(c *gee.Context) {
        c.JSON(200, map[string]any{"lang": c.Params["lang"], "doc": "https://"+c.Params["lang"]+".dev/doc"})
    })
    r.POST("/p/go/src", func(c *gee.Context) {
        c.JSON(200, map[string]any{"lang": "go", "src": "https://github.com/golang/go/tree/master/src"})
    })
    r.Run(":9999")
}

当然这份代码依然没解决cryacry说的bug

测试中先后添加了“/hello/:name”和"/hello/b/c"路由，在查找“/hello/geektutu/c”该路由时本该不存在的，但是匹配到了"/hello/b/c"这个路由上

想解决这个bug 估计得区分精细路由和模糊路由，目前这种前缀树是不够的。