1、前言

在项目中，当执行npm intall时，会根据package.json中的依赖项在node_modules目录中安装依赖包。这一稀松平常的动作，看似简单，实则背后原理充满复杂和艺术性。下面我们通过npm源码对install包安装的过程进行解析。

2、Arborist树木栽培家

2.1 class Install

通过上一篇《npm源码解析之启动流程》的分析，我们了解到：当在控制台输入npm命令时，会实例化一个class Npm，然后通过实例调用exec()方法，根据命令行参数动态require对应的模块。而npm install载入的是lib/commands/install.js的class Install。

// lib/commands/install.js
class Install extends ArboristWorkspaceCmd {
   // ...
   async exec (args) {
     // ...
     const Arborist = require('@npmcli/arborist')
     const arb = new Arborist(opts)
     await arb.reify(opts)
   }
}

可以看出，class Install的exec()方法核心是实例化class Arborist并调用reify()实例方法。

2.2 class Arborist

Arborist译为树木栽培家，顾名思义，它的作用就是构建node_modules依赖树，对依赖包进行检查和管理。

// @npmcli/arborist/lib/arborist/index.js
const mixins = [
  require('../tracker.js'),
  require('./pruner.js'),
  require('./deduper.js'),
  require('./audit.js'),
  require('./build-ideal-tree.js'),
  require('./set-workspaces.js'),
  require('./load-actual.js'),
  require('./load-virtual.js'),
  require('./rebuild.js'),
  require('./reify.js'),
  require('./isolated-reifier.js'),
]
const Base = mixins.reduce((a, b) => b(a), require('events'))
class Arborist extends Base {
  // ...
}

// ./reify.js
module.exports = cls => class Reifier extends cls {
  // ...


}

// ./load-actual.js
module.exports = cls => class ActualLoader extends cls {

  // ...


}

class Arboris继承class Base，而Base是通过reduce()函数累加器特性，将mixins数组里的类混入其中，简单理解就是实现类的多继承。

• Reifier：具体化依赖树，将实际的依赖包写入磁盘中。
• ActualLoader：加载actualTree真实树，即磁盘中node_modules下的依赖包结构。
• IdealTreeBuilder：构建idealTree理想树，即理想状态下一颗完整的依赖树。
• VirtualLoader：加载virtualTree虚拟树，通过它进一步转化成idealTree。
• Builder：对依赖包自身做build处理，如bin可执行命令、scripts脚本等。

2.3 class Reifier

class Arboris实例化调用reify()方法，该方法的具体实现在class Reifier中。它的作用是将最终的依赖包写入磁盘中。

// @npmcli/arborist/lib/arborist/reify.js

async reify (options = {}) {
    // ...
    await this[_validatePath]()
    await this[_loadTrees](options)
    
    await this[_diffTrees]()
    await this[_reifyPackages]()
    
    await this[_saveIdealTree](options)
    await this[_copyIdealToActual]()
   
    return treeCheck(this.actualTree)
}

npm install执行过程：

• [_validatePath]：校验目录，检查node_modules目录是否存在，不存在则创建，存在的话还要判断是否为软链接，是则删除重新创建。
• [_loadTrees]：加载依赖树（actualTree、virtualTree和idealTree），并将它们挂载到class Arborist对应的属性中。

• [_diffTrees]：对比依赖树，Diff计算actualTree和idealTree之间的差异，并将结果存储至diff属性中。计算结果用于依赖包的构建，也可以直接使用idealTree去创建，但要做到最小化更新，提高性能，diff过程是必不可少的。

• [_reifyPackages]：构建依赖包，也就是构建依赖包。它提供了一种可回滚的安装方式，遇到错误，可以向上回溯，保证整个构建流程的可靠性。依赖包的下载是通过pacote.extract()模块进行拉取。
• [_saveIdealTree]：保存依赖树，将idealTree的元数据保存到包锁中或shrinkwrap文件，以及对package.json文件进行修改。
• [_copyIdealToActual]：同步依赖树，将actualTree转化为idealTree。actualTree代表的是磁盘node_modules依赖包的真实数据。

3、actualTree、idealTree和virtualTree三棵树

3.1 class ActualLoader

// @npmcli/arborist/lib/arborist/reify.js

// class Reifier
module.exports = cls => class Reifier extends cls {
  async reify (options = {}) {
    // ...

    await this[_loadTrees](options)
  }
  [_loadTrees] (options) {
    return Promise.all([
      this.loadActual(actualOpt),
      this.buildIdealTree(bitOpt),
    ])
  }

}

install流程执行到_loadTrees（加载依赖树）环节，会分别调用this.loadActual()和this.buildIdealTree()方法，它们分别来自class ActualLoader和class IdealTreeBuilder。

• ActualLoader：加载真实依赖树，它代表磁盘实际依赖包的数据结构。
• IdealTreeBuilder：构建理想依赖树，它代表完整依赖包的数据结构。

// @npmcli/arborist/lib/arborist/load-actual.js
module.exports = cls => class ActualLoader extends cls {

  async loadActual (options = {}) {
    // ...
    this.#actualTreePromise = this.#loadActual(options)
      .then(tree => {
        // tree是通过#loadActual()方法返回的Node实例。
        this.actualTree = treeCheck(tree)
        return this.actualTree
      })
  }
  async #loadActual (options) {
    // ...
    this.#actualTree = await this.#loadFSNode({
      path: this.path,
      real: await realpath(this.path, this[_rpcache], this[_stcache]),
      loadOverrides: true,
    })
    // ...
    // 使用隐藏锁，即通过node_modules/.package-lock.json文件解析依赖包。
    const meta = await Shrinkwrap.load({
      path: this.#actualTree.path,
      hiddenLockfile: true,
      resolveOptions: this.options,
    })
    this.#actualTree.meta = meta
   
    return this.#actualTree
    
  }
  
  // 创建Node
  async #loadFSNode ({ path, parent, real, root, loadOverrides, useRootOverrides }) {
    // ...
    let node
    const params = {
     // ...
    }
    // 读取package.json文件数据挂到node pkg属性上
    const pkg = await rpj(join(real, 'package.json'))
    params.pkg = pkg
  
    if (normalize(path) === real) {
      node = this.#newNode(params)
    } else {
      node = await this.#newLink(params)
    }
  
    return node
  }

  #newNode (options) {
    return new Node(options)
  }
}

可以看出actualTree是一个class Node的实例，而Node代表依赖树的完整数据结构。后续的idealTree和virtualTree也同样是class Node的实例。

class Shrinkwrap获取依赖包的元数据，即通过解析npm-shrinkwrap.json、package-lock.json和yarn.lock所得到的数据。

3.2 class IdealTreeBuilder

class IdealTreeBuilder作用是构建理想依赖树，buildIdealTree()方法是核心流程：

// @npmcli/arborist/lib/arborist/build-ideal-tree.js
module.exports = cls => class IdealTreeBuilder extends cls {
  // ...


  async buildIdealTree (options = {}) {
    // ...

    await this.#initTree()
    await this.#inflateAncientLockfile()
    await this.#applyUserRequests(options)
    await this.#buildDeps()
    await this.#fixDepFlags()
    await this.#pruneFailedOptional()
    await this.#checkEngineAndPlatform()
  }

}

• #initTree：构建virtualTree虚拟树，深度遍历树，修剪无效边缘的节点，最后得到idealTree理想树。
• #inflateAncientLockfile：如果lockfile来自v5或更早的版本，需要重置包清单信息（package manifest）。
• #applyUserRequests：将待安装的包节点压入依赖队列中（depsQueue），等待后续的处理。
• #buildDeps：构建依赖，从根节点开始遍历树，分析节点中dependencies、bundleDependencies和peerDependencies依赖项之间关系，获取完整的依赖列表，将结果记录在idealTree.children属性中。依赖包的扁平化、冲突处理也在这里完成。
• #fixDepFlags：重置所有依赖标志位。
• #pruneFailedOptional：修剪掉所有加载失败的依赖。
• #checkEngineAndPlatform：校验每个依赖package.json下的engines及os字段是否满足当前node版本及平台类型要求。

3.2 class VirtualLoader

通过调用堆栈，可以看出loadVirtual()方法是在#initTree方法中调用的，#initTree的目的是构建idealTree。

// class IdealTreeBuilder

async #initTree () {
  return this[_setWorkspaces](root)
    .then(root => /* 略掉其它逻辑 */ this.loadVirtual({ root }))
    .then(async root => { /* ... */ })
    .then(tree => {
       // ...
       this.idealTree = tree
       this.virtualTree = null
        
       return tree
    })
}

// class IdealTreeBuilder

module.exports = cls => class VirtualLoader extends cls {
  async loadVirtual (options = {}) {
     const s = await Shrinkwrap.load({ /* ... */ })
     
     const {
       root = await this.#loadRoot(s), // 创建root节点，即new Node()
     } = options

     
     // 从Shrinkwrap中加载虚拟树
     await this.#loadFromShrinkwrap(s, root)
     return treeCheck(this.virtualTree)
  }

}

4、依赖树Diff算法

// class Reifier


[_diffTrees] () {
  this.diff = Diff.calculate({
    shrinkwrapInflated: this[_shrinkwrapInflated],
    filterNodes,
    actual: this.actualTree,
    ideal: this.idealTree,
  })
}

class Diff {
  constructor ({ actual, ideal, filterSet, shrinkwrapInflated }) {
    this.filterSet = filterSet
    this.shrinkwrapInflated = shrinkwrapInflated
    this.children = []
    this.actual = actual
    this.ideal = ideal
    if (this.ideal) {
      this.resolved = this.ideal.resolved
      this.integrity = this.ideal.integrity
    }
    // actual与ideal对比，得到变动行为：ADD、CHANGE、REMOVE。
    this.action = getAction(this)
  }

  
  const getAction = ({ actual, ideal }) => {
    // ideal节点不存在，则代表该节点被删除
    if (!ideal) {
      return 'REMOVE'
    }

    // 真实节点不存在，则代表该节点属性新增
    if (!actual) {
      // inDepBundle为true说明是捆绑依赖，不属于新增，返回null
      return ideal.inDepBundle ? null : 'ADD'
    }

    // 根节点返回null
    if (ideal.isRoot && actual.isRoot) {
      return null
    }

    // 相同包版本不同，属于CHANGE
    if (ideal.version !== actual.version) {
      return 'CHANGE'
    }



    const binsExist = ideal.binPaths.every((path) => existsSync(path))

    // ...
    return null
  }
  
  static calculate ({
    actual,
    ideal,
    filterNodes = [],
    shrinkwrapInflated = new Set(),
  }) {
    // depth方法可以深度遍历树的每个节点
    return depth({
      tree: new Diff({ actual, ideal, filterSet, shrinkwrapInflated }),
      getChildren,
      leave,
    })
  }
}

依赖树Diff算法核心是class Diff。通过传入actualTree真实树和idealTree理想树，深度遍历两棵树，然后进行横向对比，得出节点间的差异（ADD新增、CHANGE修改、REMOVE删除），并最终返回diff实例，该实例是两棵树对比的结果，用于最后依赖包的磁盘写入操作。

5、构建依赖包

// class Reifier


async [_reifyPackages] () {
  // [rollbackfn, [...actions]]
  // rollbackfn：回滚函数，
  // actions：步骤方法
  const steps = [
    [_rollbackRetireShallowNodes, [
      _retireShallowNodes,
    ]],
    [_rollbackCreateSparseTree, [
      _createSparseTree,
      _addOmitsToTrashList,
      _loadShrinkwrapsAndUpdateTrees,
      _loadBundlesAndUpdateTrees,
      _submitQuickAudit,
      _unpackNewModules,
    ]],
    [_rollbackMoveBackRetiredUnchanged, [
      _moveBackRetiredUnchanged,
      _build,
    ]],
  ]
  
  // 通过两层循环处理steps二维数组
  for (const [rollback, actions] of steps) {
    for (const action of actions) {
      try {
        await this[action]()
        if (reifyTerminated) {
          throw reifyTerminated
        }
      } catch (er) {
        await this[rollback](er)
          throw er
      }
    }

  }
}

_reifyPackages()方法用于构建依赖包，拆分步骤，并将它们放在一个二维数组，然后循环执行方法。如果执行错误，将通过try catch捕获错误，并作回滚操作。具体可查看tree reification文档。

• _retireShallowNodes：备份要替换的浅层节点。将要替换的节点进行备份，正常情况下它们会被移除，但如果出现错误，还可以将它们移回。
• _createSparseTree：创建节点目录。
• _addOmitsToTrashList：添加到废弃列表，该节点将跳过安装。
• _loadShrinkwrapsAndUpdateTrees：通过npm-shrinkwrap.json字义的依赖节点，需要分析该文件，调用loadVirtual进行更新。
• _loadBundlesAndUpdateTrees：深度遍历树，获取节点bundled依赖项进行分组，然后移动到实际的父节点之下，最后调用loadVirtual进行更新。
• _submitQuickAudit： 提交审查，扫描查找依赖项是否存在漏洞。实际和npm audit命令等同。
• _unpackNewModules： 解析安装依赖包，核心步骤，通过深度遍历diff（真实树与理想树差异计算），最后调用pacote.extract安装依赖包。

// class Reifier


[_unpackNewModules] () {
  // 深度遍diff
  dfwalk({
    tree: this.diff,
    visit: diff => {
      // 节点没有新增和修改则跳出遍历
      if (diff.action !== 'CHANGE' && diff.action !== 'ADD') {
        return
      }

      const node = diff.idea
      const bd = this[_bundleUnpacked].has(node)
      const sw = this[_shrinkwrapInflated].has(node)
      const bundleMissing = this[_bundleMissing].has(node)   
      const doUnpack = node && 
        // 不为根节点
        !node.isRoot &&
        // 不为bundle依赖包
        !bd &&
        // 不为已读取过的shrinkwrap
        !sw &&
        // 不为已经被另一个依赖的bundle过的包
        (bundleMissing || !node.inDepBundle)

      if (doUnpack) {
        // 将节点加入微队列中，等待执行。
        unpacks.push(this[_reifyNode](node))
      }
    },
    getChildren: diff => diff.children,
  })
  // 执行队列中的this[_reifyNode](node)方法。
  return promiseAllRejectLate(unpacks)
    .then(() => process.emit('timeEnd', 'reify:unpack'))
}


[_reifyNode] (node) {
  // ...
  const p = Promise.resolve().then(async () => {
      await this[_checkBins](node)
      // 提取包
      await this[_extractOrLink](node)
      await this[_warnDeprecated](node)
  })
  // ...
}

async [_extractOrLink] (node) {
  if (!node.isLink) {
    // ...   
    let res = null
    // 解析完整包名
    if (node.resolved) {
      const registryResolved = this[_registryResolved](node.resolved)
      if (registryResolved) {
        res = `${node.name}@${registryResolved}`
      }
    } else if (node.package.name && node.version) {
      res = `${node.package.name}@${node.version}`
    }
    // ...
    // 提取包到指定文件中，即node.path对应的路径
    await pacote.extract(res, node.path, {
      ...this.options,
      resolved: node.resolved,
      integrity: node.integrity,
    })
    // ...
    return
  }
  if (node.isInStore) {
    // 读取package.json修改node.package.scripts字段
    const pkg = await rpj(join(node.path, 'package.json'))           
    node.package.scripts = pkg.scripts
  }
  // 如果节点是软链接，直接删除
  await rm(node.path, { recursive: true, force: true })
  await this[_symlink](node)
}

• _moveBackRetiredUnchanged： 将不变的节点移回新树中。
• _build： 对新增的依赖包做build处理。遍历树，执行节点依赖包的scripts脚本。

6、总结

• npm install调用的是class Install实例方法exec()。
• class Arborist是整个包安装机制的核心类，它的作用是构建node_modules依赖树，并对依赖包进行检查和管理。
• Arborist管理着三棵树，分别是actualTree（真实树：磁盘依赖包数据结构）、virtualTree（虚拟树：通过解析npm-shrinkwrap.json、package-lock.json和yarn.lock所得到的依赖树）和idealTree（理想树：通过虚拟树转化而来，最完整的依赖树）。
• 依赖树Diff，是通过actualTree和virtualTree进行差异计算而得到的Diff实例，用于最终依赖包的安装。
• 构建依赖包的过程是可回溯的，原理是通过遍历二维数组[rollbackfn, […actions]]（rollbackfn：回退方法，actions：执行步骤方法），然后逐步执行步骤方法，通过try catch捕获错误，作回滚操作。

往期文章：

npm源码解析之启动流程

npm包安装机制历史演变过程