前情提要

之前的两篇文章讲了, 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 的联调解析了

vue-router matcher 部分的 path ranking(路径排名) 就先讲到这里，如果你对 vue-router4 的源码感兴趣的话，觉得文章讲的还行，可以看之后发的几篇源码解析（关注就能看到后续更新, 欢迎点赞催更）, Matcher 部分文章如下

1. vue-router 如何找到待渲染的 vue 组件？vue-router Matcher 解析（一）) - 标准化 route
2. vue-router 如何找到待渲染的 vue 组件？详解 route 别名处理，vue-router Matcher 解析（二 - 别名处理
3. [vue-router 如何匹配路由？解析路径排名，vue-router Matcher 解析（三）] - 路径排名