路由匹配引擎

服务端的 Express 与前端的 React Router，内核是同一件事：拿一张路由表，自上而下用一条 path 去匹配每一条 pattern，第一条命中者胜，并把 path 里对应的片段提取成 params 交给 handler。本页把这台引擎拆开：三种 segment、参数提取，以及让「最该命中的那条」命中的三种做法。

图 0-1 · 一条 path 在路由表上逐条匹配的过程，命中者高亮并列出提取到的 params。可改 path，或勾开关重现一次 route shadowing。

路由表是线性扫描、第一条命中就停，所以越具体的越要排前面。/users/new 必须排在 /users/:id 之前，否则匹配 /users/new 时会先撞上 :id、把 new 当成一个 id 吃掉，后面真正的 /users/new handler 永远不会被执行。这种「被排在前面、更宽的规则提前匹配走」叫 route shadowing。

引擎的内核就是下面这两个函数。

// 一张路由表上跑匹配: 第一条命中者胜 (顺序即优先级)
function matchTable(routes, path) {
  for (const route of routes) {       // 自上而下, 线性扫
    const r = matchPattern(route.pattern, path);
    if (r.ok) return { route, params: r.params };  // ← 命中即停, 不再检查后面的
  }
  return null;                        // 落空 → 交给 catch-all / 404
}

// 单条 pattern 对单条 path: 按 "/" 切段, 逐段对齐
function matchPattern(pattern, path) {
  const ps = segsOf(pattern), xs = segsOf(path), params = {};
  for (let i = 0; i < ps.length; i++) {
    const p = ps[i];
    if (p[0] === '*') { params['*'] = xs.slice(i).join('/'); return ok(params); }
    if (i >= xs.length) return miss();          // path 太短
    if (p[0] === ':') params[p.slice(1)] = xs[i];  // 命名参数: 吃一段
    else if (p !== xs[i]) return miss();         // 字面段: 必须相等
  }
  return xs.length > ps.length ? miss() : ok(params);  // path 还有剩 → 不匹配
}

// 把 path 按 "/" 切成 segment 数组: 先去掉 fragment 与 query, 再丢掉空段
// "/users/42/posts/" → ["users", "42", "posts"]
function segsOf(path) {
  return path.split('#')[0].split('?')[0].split('/').filter(Boolean);
}

1 · 逐段对齐与顺序优先级

匹配 = 把 pattern 和 path 都按 / 切成 segment 数组，再逐段对齐：字面段要求相等、:param 消费一段并记下值、* 匹配剩余全部。任一段对不上、或两边段数不齐（且没有通配 catch-all），这条就 miss。全表没有一条命中，通常落到末尾的 * catch-all 渲染 404——这也是「为什么 404 页本质上也是一条路由」。

建议 · 让「最该命中的那条」命中，真实世界有三种做法。顺序（Express 风格）：书写的先后就是优先级，作者自己负责把具体的排前面，排错就 shadowing。specificity 自动排序（React Router 与 path-to-regexp 风格）：框架给每条路由算具体度、自动重排，与书写先后无关。radix tree：换数据结构，让优先级内建在下行顺序里，连排序都省了。§1 讲完了顺序法，§2 与 §3 各演示后两种。

2 · specificity 自动排序

与其要作者手动把具体的排前面，不如让框架代劳：给每条路由算一个 specificity（具体度）并自动重排，字面段计 3、:param 计 2、* 计 0。于是不管路由表写得多乱，/users/new 都会被排到 /users/:id 前面、* 沉到最后，「取第一条命中」就不再 shadowing。

有个关键细节：不能把整条路由压成一个标量分求和，那会丢掉位置信息。实测 /users/:id 的逐段分是 [3,2]、/:resource/new 是 [2,3]，两者求和都是 5，求和法会判它们同分。正确做法是按逐段 score 数组做字典序比较：第一处不同的 segment 就定胜负、越靠前权重越高，完全同分才退回定义顺序。按这个比较器，/users/:id 排在 /:resource/new 之前。

图 2-1 · 一张故意打乱顺序的路由表，勾开关看它被重排成什么样。每行末尾的方括号是该条的逐段 score 数组。

// pattern → 逐段 specificity 数组   /users/:id → [3,2]   /files/* → [3,0]
const S = { static: 3, param: 2, end: 1, wild: 0 };   // 注意: end > wild
function scoreOf(pattern) {
  return segsOf(pattern).map(s =>
    (s === '*' || s[0] === '*') ? S.wild : s[0] === ':' ? S.param : S.static);
}

// 逐段字典序比较: 第一处不同的 segment 定胜负 (越靠前权重越高)。
// 不求和! 求和会让 /users/:id 和 /:resource/new 打平。
function compareSpecificity(a, b) {
  const sa = scoreOf(a), sb = scoreOf(b);
  for (let i = 0; i < Math.max(sa.length, sb.length); i++) {
    const va = i < sa.length ? sa[i] : S.end;   // 已走完 = end, 比 wild 具体
    const vb = i < sb.length ? sb[i] : S.end;
    if (va !== vb) return vb - va;              // specificity 高的排前面
  }
  return 0;                                     // 全等 → 退回定义顺序
}

// 按具体度重排; 同分回退到原始下标 i (stable)
const rankRoutes = (routes) => routes
  .map((r, i) => ({ r, i }))
  .sort((x, y) => compareSpecificity(x.r, y.r) || x.i - y.i)
  .map(o => o.r);

3 · radix tree 把优先级编进结构

前两种策略都在一张平表上做文章。高性能 router（Fastify 的 find-my-way、Go 的 httprouter、Echo）走第三条路：把整张路由表编译成一棵 radix tree（前缀树），每个节点是一段 path，共同前缀只存一份。优先级不再靠排表、也不靠打分，而是内建在下行的尝试顺序里。

规则只有一条：在每个节点要匹配 path 的下一段时，固定先试 static 子节点（逐字相等），不中再试 :param 节点，最后才是 * 通配。这个顺序就是优先级。于是 route shadowing 自动消失——在 users 节点下，new 这个 static 子节点天生先于 :id 被试到。实测把两条路由按两种顺序分别建树，/users/new 都命中 /users/new；而同样两种顺序喂给平表 matcher，写反那次就命中了 /users/:id。

图 3-1 · 路由表编译成的前缀树与一条 path 的下行过程，每个节点按 static、param、wild 的固定次序尝试子节点。

// 沿树下行: 每个节点按 static → param → wild 试子节点, 失配则回溯。
// children 在建树时已排成 static → param → wild —— 这个顺序就是优先级。
function descend(node, xs, i = 0) {
  if (i === xs.length) return node.handler || null;        // 段吃完, 此处须是 handler
  for (const c of node.children) {
    if (c.type === 'static' && c.seg !== xs[i]) continue;  // 静态: 逐字不等, 跳过
    if (c.type === 'wild') return c.handler;               // 通配: 吞掉剩余全部
    const hit = descend(c, xs, i + 1);    // 静态命中 / 参数吃一段 → 递归下行
    if (hit) return hit;                  // 子树没出路会回溯, 继续试下一个兄弟
  }
  return null;                            // 全不中 → 交给上层 catch-all
}

注 · 匹配是沿树下行，复杂度约为 path 的段数，与路由总条数无关；平表逐条扫是 $O(n)$ ，这是 radix tree 在大路由表下的核心优势。代价有两处：static 分支若深入后失配，要退回上一个节点改试 :param 或 *，并非一路到底；另外 * 一般只能放在末尾，给参数加正则约束 :id(\d+) 也会让「这段算不算 static 命中」的判定更复杂。本页引擎的 descend 就没处理 * 在中间的情形——它一撞上 wild 节点就直接返回，不检查该节点是否真有 handler，所以给它 /files/*/meta 这种表、再查 /files/a，会得到一条停在 * 上的假命中。换数据结构等于把「谁更具体」从运行时比较挪成了编译期结构，排序的烦恼没了，换来一棵要维护的树。

这台手工实现的 matcher，浏览器已经标准化成内建的 URLPattern，且匹配范围从 pathname 扩到整条 URL。匹配到 handler 之后，handler 也可以不渲染内容而回一个 3xx，那是路由的另一种出口；分享地址统一入口用一条 /s/:code 接住所有分享链接，code 正是本页这台引擎提取出的 param。