2.1 依赖树的构建算法
2.1 依赖树的构建算法
本节摘要：依赖解析是把"版本范围的集合"翻译成"精确版本方案"的一次搜索过程。本节用一份只有四个包的小清单，手工模拟解析器从收集约束、查询候选、求解版本到去重剪枝的每一步，让黑盒算法变成看得见的桌面演算。读完后你应能预判任何一份清单的解析结果，也能解释为什么解析在依赖复杂时明显变慢、为什么同样清单不同时间解出不同方案。
从一次桌面演算开始
勘验算法最可靠的办法是缩小规模、亲手演算。给定这样一份清单：
{ "dependencies": { "my-ui": "^2.0.0", "moment": "^2.29.0" } }
远端仓库里，my-ui 的 2.3.1 版声明了两个依赖：vue: ^3.2.0 和 lodash: ^4.0.0；而它的另一个候选版本 2.1.0 只依赖 vue: ^3.0.0。moment 的 2.29.4 版没有运行时依赖。现在开始演算：
第1步 读清单：收集到两条根约束 my-ui 大于等于2.0.0且小于3.0.0 moment 大于等于2.29.0且小于3.0.0 第2步 查候选：my-ui 可用版本里 2.3.1 最大，选中它 moment 同理选中 2.29.4 第3步 展开新约束：my-ui 2.3.1 带来两条 vue 大于等于3.2.0小于4.0.0；lodash 大于等于4.0.0小于5.0.0 第4步 继续对 vue、lodash 查候选、选版本、展开它们的子约束…… 直到所有约束都被满足、没有新包需要展开
四个要点从演算里浮现。其一，解析是逐层展开的：根约束解出的每个包，其自身的依赖又成为新约束入队，循环往复直到队列为空。其二，默认贪心：每个约束都倾向选满足范围的最新版本。其三，候选集合是动态的：第 2 步选 2.3.1 是因为此刻它是最新——半年后远端多了 2.4.0，同样清单就会解出不同方案，这就是安装漂移的机制根源。其四，冲突时回溯：若 vue 的候选与其他约束打架，解析器会退回去尝试 my-ui 的其他版本，搜索树因此可能指数膨胀——大仓库解析慢的真凶通常在这里。
图 2-1 一次解析演算的搜索树全貌
去重与剪枝：解析不止求有解
演算里还有一笔没记：如果根清单的另一个包也依赖 lodash，且范围兼容，解析器不会装两份——相同精确版本只落盘一次，这就是 1.1 节看到的 deduped。去重发生在解析阶段：维护一张"已解析"表，同一包的同一版本只登记一次。
真正微妙的是范围兼容的判定。两个范围 ^4.0.0 与 ^4.17.0 的交集是 ^4.17.0，交集非空就可以共用一个落在交集里的版本；若一个要 3.x 一个要 4.x，交集为空，物理双份不可避免。由此得出一条排查心法：
$ npm ls lodash myapp@1.0.0 +-- my-ui@2.3.1 | `-- lodash@4.17.21 `-- data-tools@1.8.0 `-- lodash@3.10.1 # 范围不兼容 → 双版本并存，各回各家
看到同一包出现两行，不要急着当 bug 处理——先看两处声明的范围是否真的不兼容。这是"设计如此"，不是"装坏了"。
peer 约束：解析器里最特殊的输入
普通依赖说"我要某包的某范围"，peer 依赖说的是另一种话："我不安装它，但要求环境里必须已存在它，且版本要落在我的要求内"。插件与组件库是这个机制的主战场：一个 webpack 插件绝不希望给自己单独装一份 webpack，它必须与宿主共用同一个实例。
这让解析多了一类全局校验：所有 peer 约束指向同一个包时，必须能在一份版本上达成一致；达不成一致，安装直接报错而不是静默吞掉。当年的静默失败坑过太多人——插件运行时才发现宿主版本不匹配，报错位置离原因十万八千里。现在把冲突拦在安装时，报错信息会直接指出"谁要求什么范围、现有方案装的是什么"，处置路径清晰得多。依赖类型全谱系（dependencies、peerDependencies、optionalDependencies 等）的完整勘验在第五章 5.3，本节只需记住 peer 改变了解析的输入性质：它把"各装各的"改成了"必须协商"。
算法的工程镜像：解析器到底输出什么
桌面演算的产物在工程里有个对应的实物：解析完成后、落盘开始前，安装器内部持有的一棵"理想依赖树"——每个节点的包名、精确版本、来源地址、子约束全就位。日常命令里能间接看到它的影子：
$ npm install --dry-run --json # 输出 JSON 形态的安装计划：packages 数组里每个条目 # 都有 name、version、resolved、integrity——与锁文件字段同源
这个视角解释了两个现象。其一，锁文件为什么长得像"解析输出"——因为它就是解析输出的持久化，3.1 节的字段解剖此时应能完全对上。其二，为什么解析慢的仓库装什么都慢——解析阶段在下载开始前，瓶颈是约束求解的搜索而非网络，此时清缓存重装毫无帮助，正确动作是简化依赖图或排查哪条依赖带入了超大的约束网络。
性能敏感的团队还可以打开计时开关观测解析段的耗时占比：
$ npm install --timing # 日志末尾的计时报告里，理想树构建一项就是解析阶段的耗时； # reify 是落盘阶段——两者分开看才能定位瓶颈
看到解析占大头，说明该做依赖图减法（6.2 节的仓库层优化）；看到落盘占大头，说明瓶颈在文件系统 IO，缓存与磁盘才是对症的方向。把"解析"与"落盘"在日志里分开读，是排障效率的分水岭。
本节要点回顾
- 解析是搜索不是查表：约束入队、贪心选版、冲突回溯，搜索树在大依赖图上可能显著膨胀；
- 同清单不同结果的根源是候选集合随远端演化——这就是漂移，锁文件正是为此而来（第三章）；
- 去重条件是范围交集非空：交集内取一版共用；交集为空才物理双份，npm ls 看到双行先查范围；
- peer 约束把安装语义从"各装各的"改为"环境协商"，冲突在安装时报错而非运行时爆炸；
- 排查心法：解析异常先缩小输入——把清单砍到最小复现，逐个约束加回来，二分出问题约束。
下一节把"输入语言"本身讲透：^ 与 ~ 到底画了多大的区间，为什么声明里看似无害的一个符号，半年后会让两个环境装出两个世界。