vue-router 还给路由排了序？解析路由匹配，vue-router Matcher 解析
前情提要
之前的两篇文章讲了, vue-router 的 Matcher 对初始的 routes 进行了标准化(normalized)处理以及别名(alias)处理，详情链接参考文章尾部
本篇文章会介绍 matcher 处理 route 的匹配部分, 即 vue-router 文档的路由的匹配语法
注：本篇文章关于 matcher 的解析和源码均对应 vue-router4 即 vue3 版本的 router
注意区分文章中的, routes 和 route, route 指 { path: "/", Redirect: "/test" }, routes 指 [route,route,...]
matcher 数组
之前提到过, 类似 routes 这样的数组其实是一种多叉树结构, 然后整个 matcher 数组生成的过程中使用了递归式的多叉树遍历,并在遍历过程中处理了别名以及别名子路由,将子路由的 path 修改为正确的, 比如 /a/1, 其实这个在 matcher 里面都是一个次要的功能,真正的功能是去生成 matchers 数组,对,虽然之前文章花了重点介绍 addRoute,但是不要被它 语义 给迷惑了,它的真正目的是给 matchers 添加 route 转化的 matcher(小细节)
// routes 其实是多叉树 const routes = [ { path: "/", component: Home, }, { path: "/a", alias: "/ab", component: null, children: [{ component: null, path: "1" }], }, { path: "/b", component: Home, }, ]; 复制代码区分路由
前面说了 addRoute 目的是给 matchers 添加 route 转化的 matcher, 这个证明在于 addRoute 的底部 router/src/matcher/index.ts 179
function addRoute(...) { // ... insertMatcher(matcher); } // ... function insertMatcher(matcher: RouteRecordMatcher) {} 复制代码而 insertMatcher() 就是今天这篇文章的主角
为什么说区分路由? 我们先看一下 insertMatcher 的源码 router/src/matcher/index.ts 214
function insertMatcher(matcher: RouteRecordMatcher) { let i = 0; while ( i < matchers.length && comparePathParserScore(matcher, matchers[i]) >= 0 ) i++; // 关键的下面三行 matchers.splice(i, 0, matcher); if (matcher.record.name && !isAliasRecord(matcher)) matcherMap.set(matcher.record.name, matcher); } 复制代码insertMatcher() 主要作用就是找到 matcher(由 route 转化的) 在 matchers 中的位置, 这也就是我标题为什么说 matchers 是一个有顺序的数组, 而区分路由就是指 matchers 和 matcherMap 两个数据结构, 一个数组一个哈希表, 在上面标注的源码中有一个性能优化的点, 就是命名路由的 matcher 是有另一份存放在 matcherMap 里面的, 这很重要, 因为 Map 这种数据结构的查询时间复杂度是 O(1), 是很快的, 所以我们在编写路由的, 应该尽可能的使用命名路由, 它的查询时间远远快于普通路由, 普通路由的查询时间复杂度是 O(n), matcher 里面的 resolve 就是我们匹配路由是调用的方法, 里面其实就写了命名路由和普通路由的匹配方式
// router/src/matcher/index.ts 283 resolve() matcher = currentLocation.name ? matcherMap.get(currentLocation.name) : matchers.find((m) => m.re.test(currentLocation.path)); 复制代码
为了方便理解, 请参考下面原始 routes 的数据结构和 matchers 的数据结构
const routes = [ { path: "/", component: Home, }, { path: "/a", alias: "/ab", component: null, children: [{ component: null, path: "1" }], }, { path: "/b", component: Home, }, ]; 复制代码matchers
前排提示, score 是一个伏笔
路径排名
前面说了, insertMatcher() 是通过 while() 遍历找到 matchers 的正确的插入位置的, 源码如下
// 生成 matchers 的代价是 O(n^2) while (i < matchers.length && comparePathParserScore(matcher, matchers[i]) >= 0) i++; 复制代码
// 模拟 matchers 的生成过程 1. [/] 2. [/,/a/1] 3. [/,/a,/a/1] 4. ... 复制代码
小细节来了, 这个 matchers 它其实是一个有顺序的数组, 不是乱排的, 它有个路径排名的功能, 里面核心有两个函数 comparePathParserScore 和 compareScoreArray
简单介绍一下 matcher 它这个排名的实现, 生成 matcher 的时候, 根据你传入的 route 的 path 打分, 然后根据这个分的高低去给你排序看你适合排在哪里, 它的主要目的是什么呢?这就要说到这个设计者在北京分享的一个讲座的小细节了
const routes = [ { path: "/movie/:id", }, { path: "/movie/new", }, ]; 复制代码像上面这个路由, 如果你传入 /movie/new 其实两个都是满足条件的, 但是很明显第二个才是我们想要的, 所以为了正确的匹配我们必须让 /movie/new 在之前 /movie/:id 被匹配到, 注意, 我们前面说过, 普通路由匹配的方式就是 matchers.find(), 就是从 0 到 n 匹配是返回第一个适合的, 所以为什么需要路径排名? 为什么 matchers 是一个有顺序的数组? 就是要让 /movie/new 这种静态路由能够比 /movie/:id 这种动态路由先匹配到, 先静后动
回到它的底层实现, 看之前关于 matchers 的数据结构截图, 里面有个属性叫 score, 它里面存放的就是根据 path 打分得到的 number 数组, 像 /movie/new 这种静态路由的分数要比 /movie/:id 这种动态路由高, 因此匹配的时候就不会出错, 可以参考下面 Chrome 里面的调试截图
剩余的排名就是按照源码(指你写的 routes)的顺序, 比如
// routes const routes = [ { path: "/a", }, { path: "/b", }, ]; // matchers const matchers = ["/a", "/b"]; 复制代码说实话，我是有点失望的, vue-router matcher 的 diff 算法, 和存放 matcher 的数组似乎不是我认识的数据结构和算法，我一开始看到 vue-router 的几个特征, 1. N 叉树, 2. matcher 用数组存放 3. matchers 生成顺序依靠 vue-router 自定义得分, 几乎那两个数据结构是呼之欲出，但是竟然不是，这两个数据结构就是, 二叉搜索树(BST) 和 二叉堆(优先级队列), 为什么认为是这两个数据结构，一是我认为二叉搜索树的查找效率为 O(logn) 很快, 二就是我单纯的看到数组以为会用到二叉堆
但是回过头一想, routes 是 N 叉树, 可能上面这两种数据结构并不合适, 所以纯属是我刷题刷魔怔了
总结
vue-router matcher 基本都讲完了, 算是非常细节了, 百度 google 都找不到几篇讲 matcher 的, 更不要说是 vue-router4 的源码解析, 不知道还会不会继续写关于 matcher 部分的内容, 其实 matcher 部分还有 path 的解析没有细细展开讲解, 可能还会再出一篇, 剩下的就是 matcher 和 history 以及 component 的联调解析了
作者：2分钟速写快排
链接：https://juejin.cn/post/7064223990385999885