用 rust 从零开发一套 web 框架：day3

站长

2022年12月17日 10:35 · 阅读数 54

金丹初成

在前面一章里，我们对AppContext进行了拓展，同时也对路由的 query 参数进行解析和 hashMap 存储。现在，我们来搭建动态路由系统，并进行params 参数的解析和存储。

RouterNode 动态路由节点树

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

参数匹配: 例如 /index/:id/b，可以匹配 /index/c/b 和 /index/go/c。
通配符* 例如 /static/*filepath，可以匹配/static/fav.ico，也可以匹配/static/vue.js，这种模式常用于静态服务器，能够递归地匹配子路径。
无参数路由匹配例如 http://localhost:3000/admin，可以精准匹配到路由/admin，http://localhost:3000/admin/index则精准匹配到/admin/index。

首先设计 Trie 树的结构，作为路由节点树：

//Trie 树
#[derive(Debug, Clone)]
pub struct RouterNode {
    pub pattern: Option<String>,   // 待匹配路由，例如 /p/:lang
    pub part: Option<String>,      // 路由中的一部分，例如 :lang
    pub children: Vec<RouterNode>, // 子节点，例如 [doc, tutorial, intro]
    pub is_match: bool,            // 是否精确匹配，part 含有 : 或 * 时为true
    pub hooks: Vec<String>,        //中间件钩子函数，暂时用字符串替位
    pub method: Option<String>,    //请求方法
}

接着为这个结构体实现一些方法,比如初始化的 new 方法：

impl RouterNode {
    pub fn new() -> Self {
        RouterNode {
            pattern: None,
            children: Vec::new(),
            part: None,
            is_match: false,
            hooks: Vec::new(),
            method: None,
        }
    }
}

对于路由来说，最重要的当然是注册与匹配了。开发服务时，注册路由规则，映射 handler。访问时，匹配路由规则，查找到对应的 handler。因此，Trie 树需要支持节点的插入与查询。

插入功能很简单，递归查找每一层的节点，如果没有匹配到当前pattern或者part 的节点，则新建一个。

有一点需要注意，/admin/:id 存在两层节点，第一层为/admin，因为没有参数，所以part和method皆为None。第二层即 :id节点，pattern 会设置为/admin/:id。part为:id。

因此，当匹配结束时，我们可以使用 node.pattern、node.part和method是否为 None 来判断路由规则是否匹配成功。例如，/admin/123 能成功匹配到:id，但第一层的/admin节点的 part 和method值为空，因此匹配失败。接着递归查找下一层。通配符*也是同理。

查询功能，同样也是递归查询每一层的节点，退出规则是，匹配到了*就匹配完成，或者匹配到了(parts/pattern)的节点。

当然，前面说了这么多，还是让人感觉云里雾里，不明所以。

最直接的，还是先看一个简单的插入结果：

RouterNode {
    pattern: None,
    part: None,
    children: [
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [],
            is_match: false,
            hooks: [],
            method: Some(
                "GET",
            ),
        },
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [],
            is_match: false,
            hooks: [],
            method: Some(
                "POST",
            ),
        },
        RouterNode {
            pattern: Some(
                "/admin",
            ),
            part: None,
            children: [
                RouterNode {
                    pattern: Some(
                        "/admin/:id",
                    ),
                    part: Some(
                        ":id",
                    ),
                    children: [],
                    is_match: true,
                    hooks: [],
                    method: Some(
                        "POST",
                    ),
                },
                RouterNode {
                    pattern: Some(
                        "/admin/*id",
                    ),
                    part: Some(
                        "*id",
                    ),
                    children: [],
                    is_match: true,
                    hooks: [],
                    method: Some(
                        "GET",
                    ),
                },
            ],
            is_match: false,
            hooks: [],
            method: None,
        },
    ],
    is_match: false,
    hooks: [],
    method: None,
}

从这个节点树，我们看出，有/user和/admin/:id、/admin/*id这三种路由，就算路径相同，也会因为请求方法不同而保存为两个不同的节点（用 method 区分）。后面我们所有插入、查询的方法，都是围绕这样的节点树进行编写。

我们先来梳理一下插入逻辑：

拆分路径，比如/admin/:id或者/admin/index，按照/符号拆分为[admin,id]和[admin,index]。
如果路径长度和层级相等，比如/admin和/admin/:id的层级分别是 1 和 2，则第一、二层的pattern分别为/admin和/admin/:id。
遍历匹配路径数组，如果已存在相应的节点如/admin且该节点method为 none，则在该节点上新增下一级。否则新增该节点。
路径含有:和*，则在新节点part字段插入相应参数，并且is_match标记为true。否则在pattern字段插入路径
在最后一层，将pattern和method赋值到节点上

拆分路径

把解析路径的函数提取出来，暂时放在utils.rs 中作为工具函数：

//解析路径，排除""号和*号之后的内容
pub fn parse_pattern(pattern: &str) -> Vec<&str> {
    let list: Vec<&str> = pattern.split('/').collect();
    let mut parts: Vec<_> = Vec::new();
    for item in list.into_iter() {
        if item != "" {
            parts.push(item);
            if item.starts_with('*') {
                break;
            }
        }
    }
    return parts;
}

下面开始为 RouterNode 节点树实现插入方法：

impl RouterNode {

    ...
     //模糊匹配pattern组
    pub fn match_child_list(&mut self, pattern: &str) -> Vec<&mut RouterNode> {
        let mut children = Vec::new();
        for child in self.children.iter_mut() {
            if let Some(path) = &child.pattern {
                if pattern.starts_with("/") && path == pattern {
                    children.push(child);
                } else {
                    let raw_path = format!("/{}", pattern);
                    if path == &raw_path {
                        children.push(child);
                    }
                }
            }
        }
        return children;
    }

    //合并兄弟节点
    pub fn merge(&mut self, mut node: RouterNode) {
        if self.pattern == node.pattern {
            self.children.append(&mut node.children)
        } else {
            self.children.push(node)
        }
    }

    //新增子节点
    pub fn new_child(&mut self, part: &str) -> RouterNode {
        let mut children = RouterNode::new();
        if part.starts_with(':') || part.starts_with('*') {
            children.part = Some(String::from(part));
        } else {
            children.pattern = Some(format!("/{}", part));
        }
        children.is_match = part.starts_with(':') || part.starts_with('*');
        children
    }

    //插入节点
    pub fn insert(&mut self, method: Method, path: &str, parts: Vec<&str>, height: usize) {
      if parts.len() == height {
            self.pattern = Some(String::from(path));
            self.method = Some(String::from(method.as_str()));
            return;
        }

        if let Some(&part) = parts.get(height) {
            let level_path = format!("/{}", part);
            //模糊匹配level_path,获取同路径节点组
            let children = self.match_child_list(&level_path);
            match children.len() {
                //没有同路径，则主节点新增该路径
                0 => {
                    let mut children = self.new_child(part);
                    children.insert(method, path, parts, height + 1);
                    self.merge(children);
                }
                _ => {
                    //检查其中是否有下级节点（method为none则存在下级节点）
                    let has_item = children.into_iter().find(|child| child.method == None);
                    match has_item {
                        //路由完整路径path与level_path不相等，则在该节点新增
                        Some(node) if path != &level_path => {
                            node.insert(method.clone(), path, parts.clone(), height + 1);
                        }
                        _ => {
                            //在主节点新增
                            let mut children = self.new_child(part);
                            children.insert(method, path, parts, height + 1);
                            self.merge(children);
                        }
                    }
                }
            }
        }
    }
}

这里要特别注意match_child_list这个工具函数，它接收&mut self作为节点，经过匹配之后返回Option<&mut RouterNode>。同学们可以思考一下返回值为什么要这样写，能不能改成Option<RouterNode>或者其他形式。

匹配查找 RouterNode 节点

在前面完成了节点的新增插入，我们来处理节点的匹配查找。

以/admin/:id和/user/index这俩个路由为例子，来梳理一下路由节点的匹配流程：

先拆分路径，比如/admin/123或者/user/index，按照/符号拆分为[admin,123]和[user,index]。
递归匹配pattern是否有相应的路由如/admin、/user同时匹配method,有则获取该节点，无则返回None。
继续检查该节点，匹配下面的子节点，检查节点内 part 字段是否有动态参数（:和*），以及pattern是否有相应的路由如/user/index，同时匹配method。有则返回子节点，无则返回None。

整个匹配流程梳理好了，我们来写两个工具函数match_children和match_path，分别用来匹配动态参数（:和*）以及pattern和method。

impl RouterNode {
   ...
    // 匹配part中的:和*的节点，用于查找
    pub fn match_children(&self, part: &str) -> Vec<&RouterNode> {
        let mut nodes: Vec<_> = Vec::new();

        for child in self.children.iter() {
            if let Some(p) = &child.part {
                if p == part || child.is_match {
                    nodes.push(child)
                }
            }
        }
        return nodes;
    }

    // 递归匹配pattern和method的节点，用于查找
    pub fn match_path(&self, path: &str, method: Option<String>) -> Option<&RouterNode> {
        if let Some(parse_path) = &self.pattern {
            if parse_path == path && self.method == method.clone() {
                return Some(self);
            }
        }

        //遍历子路由
        if self.children.len() > 0 {
            for child in self.children.iter() {
                if let Some(p) = child.match_path(path, method.clone()) {
                    return Some(p);
                }
            }
        }
        return None;
    }
}

接下来,得好好想想整个路由的匹配查找要怎样编写了。因为要用到递归和遍历。那代码书写顺序应该和前面的匹配流程相反。（别问我为什么，我也不知道，只是直觉如此-因为要实现递归！）

检查节点内 part 字段，存在动态参数（:和*）则直接返回该节点
获取解析后的路径数组，遍历路径数组匹配pattern，先匹配完整路径pattern和method，存在则直接返回
检查节点method 是否为none，method 为 none 则存在下级节点, 然后递归函数，重复上述步骤
如果无法匹配到动态参数，则说明路由节点不存在，返回 none

impl RouterNode {
    ...
    //搜索节点
    pub fn search(&self, raw_path: &str, parts: Vec<&str>, height: usize) -> Option<RouterNode> {
        //检查是否匹配到最后一层或者有*号，有则返回当前节点的
        if let Some(part) = &self.part {
            if parts.len() == height || part.starts_with('*') || part.starts_with(':') {
                let res = match self.pattern {
                    Some(_) => Some(self),
                    None => None,
                };
                return res;
            }
        }

        //遍历路由parts，检查pattern和part
        if let Some(&part) = parts.get(height) {
            let router_path = format!("/{}", part);
            //先检查完整路径和方法是否匹配
            if let Some(node) = self.match_path(raw_path, method.clone()) {
                return Some(node);
                //检查其中是否有下级节点（method为none则存在下级节点）,然后递归下一层
            } else if let Some(node) = self.match_path(&router_path, None) {
                for child in node.match_children(part) {
                    return child.search(method, raw_path, parts, height + 1);
                }
            }
        }

        return None;
    }
}

Trie 树的插入与查找都成功实现了，接下来我们将 Trie 树应用到路由中去吧。我们使用 roots 来存储每种请求方式的 Trie 树根节点。使用 handlers 存储每种请求方式的 HandlerFun 。get_route 函数中，还解析了:和*两种匹配符的参数，返回一个map 。例如/admin/123 匹配到/admin/:id，解析结果为：{id: "123"}，/static/index.js 匹配到/static/\*filepath，解析结果为{filepath: "index.js"}。

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


pub struct Router {
    pub roots: HashMap<String, RouterNode>,
    pub handlers: HashMap<String, Box<Handler>>,
}
impl Router {
    pub fn new() -> Self {
           Router {
               roots: HashMap::new(),
               handlers: HashMap::new(),
           }
    }

    //新增路由
    fn add_route<F>(mut self, pattern: &str, method: Method, handler: F) -> Router
    where
        F: Fn(&mut AppContext) + Send + Sync + 'static,
    {
        //println!("路径: {:?}", pattern);
        let parts = parse_pattern(pattern);
        // println!("解析参数: {:#?}", parts);
        let mut node = match self.roots.get(method.as_ref()) {
            Some(mut node) => node.to_owned(),
            None => RouterNode::new(),
        };
        node.insert(pattern, parts, 0);
        // println!("1节点树：{:#?}", node);
        let key = format!("{}+{}", method.as_ref(), pattern);
        self.roots.insert(method.to_string(), node);
        self.handlers.insert(key, Box::new(handler));
        self
    }

    //获取路由
    pub fn get_route(&self, method: &Method, path: &str) -> (Option<RouterNode>, HashMap<String, String>) {
        let search_parts = parse_pattern(path);
        println!("路径{:#?}解析为 :{:#?}", path, search_parts);
        let mut params = HashMap::new();
        if let Some(root) = self.roots.get(method.as_str()) {
            println!("当前节点：{:#?}", root);
            let n = root.search(path, search_parts.clone(), 0);
            if let Some(ref node) = n {
                println!("获取匹配节点：{:#?}", n);
                if let Some(ref pattern) = node.pattern {
                    let parts = parse_pattern(pattern.as_str());
                    println!("解析节点参数{:#?}", parts);
                    for (index, part) in parts.into_iter().enumerate() {
                        if part.starts_with(':') {
                            params.insert(String::from(&part[1..]), String::from(search_parts[index]));
                        }
                        if part.starts_with('*') && part.len() > 1 {
                            let v = search_parts.get(index..).unwrap().to_vec();
                            let mut s = v
                                .into_iter()
                                .map(|s| {
                                    let mut val = String::from(s);
                                    val.push_str("/");
                                    return val;
                                })
                                .collect::<String>();
                            s.pop();
                            params.insert(String::from(&part[1..]), s);
                            break;
                        }
                    }
                };
            }
            return (n, params);
        } else {
            (None, params)
        }
    }
}

对比前面动态路由节点树的生成和解析匹配，现在新增路由和查询路由，那可是简单多了。但是吧，为了处理参数，也是费了我不少功夫。因为 rust 处理字符串实在是麻烦！

在调用匹配到的 handler 前，将解析出来的路由参数赋值给了 c.Params。这样就能够在 handler 中，通过 AppContext 对象访问到具体的值了。

async fn handler(addr: SocketAddr, req: Request<Body>, router: Arc<Router>) -> Result<Response<Body>, Infallible> {
    let mut context = AppContext::default();
    let (node, params) = router.get_route(req.method(), req.uri().path());
    println!("node:{:#?}, params:{:#?}", node, params);
	if let Some(node) = node {
        context.params = params;
        context.path = req.uri().path().to_string();
        context.method = req.method().clone().into();
        ...//上一章中的queries和headers等代码
        if let Some(handle) = router.routes.get(&key) {
            println!("AppContext:{:#?}", context);
            (handle)(&mut context);
            Ok(context.response)
        }
	} else {
        context.string(Some(StatusCode::NOT_FOUND), "404 not found");
        Ok(context.response)
    }
}

测试

下面来检验一下成果。在main.rs中的 main 函数写上：

#[tokio::main]
async fn main() {
    let handle_hello = |c: &mut AppContext| c.string(None, "hello world from handler");
    let get_hello = |c: &mut AppContext| {
        let key = format!("hello world from post,query: {}", c.params.get("id").unwrap());
        return c.string(None, &key);
    };
    let  router = Router::new()
        .get("/user", get_hello)
        .post("/user", handle_hello)
        .patch("/user", handle_hello)
        .post("/admin/:id", get_hello)
        .get("/user/*id", handle_hello);;

    // Run the server like above...
    let addr = SocketAddr::from(([127, 0, 0, 1], 3000));

    server::run(addr, router).await;
}

打开浏览器，访问一下上面的路由，可以看到相应内容。

同时，可以在终端查看生成的节点树如下：

当前节点: RouterNode {
    pattern: None,
    part: None,
    children: [
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [],
            is_match: false,
            hooks: [],
            method: Some(
                "GET",
            ),
        },
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [],
            is_match: false,
            hooks: [],
            method: Some(
                "POST",
            ),
        },
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [],
            is_match: false,
            hooks: [],
            method: Some(
                "PATCH",
            ),
        },
        RouterNode {
            pattern: Some(
                "/admin",
            ),
            part: None,
            children: [
                RouterNode {
                    pattern: Some(
                        "/admin/:id",
                    ),
                    part: Some(
                        ":id",
                    ),
                    children: [],
                    is_match: true,
                    hooks: [],
                    method: Some(
                        "POST",
                    ),
                },
            ],
            is_match: false,
            hooks: [],
            method: None,
        },
        RouterNode {
            pattern: Some(
                "/user",
            ),
            part: None,
            children: [
                RouterNode {
                    pattern: Some(
                        "/user/*id",
                    ),
                    part: Some(
                        "*id",
                    ),
                    children: [],
                    is_match: true,
                    hooks: [],
                    method: Some(
                        "GET",
                    ),
                },
            ],
            is_match: false,
            hooks: [],
            method: None,
        },
    ],
    is_match: false,
    hooks: [],
    method: None,
}

至此，我们终于是把动态路由解析完成了。 AppContext这颗金丹总算是凝结成功！

这一章可以说是目前难度最大的内容了，定下这个路由节点树的数据结构。光是路由节点的插入和查询算法，我就断断续续花了一周时间来进行编写、修改。中间改了好几个版本，最终才写出这个相对简单易懂的算法。上面的流程只是我个人思考+实践后想到的算法，有兴趣的同学可以自己编写一个匹配路由算法。个人能力有限，该算法仅仅只是抛砖引玉，也欢迎各位来讨论和完善。最后，看在我这一周以来疯狂优化路由系统算法的份上，向大家要个赞，不过分吧😋。

转载自:https://juejin.cn/post/7173502914508357646