Rollup 分包算法 源码阅读

0120

源码基于v3.26.0： rollup/rollup at v3.26.0 (github.com)

首先明确一些概念，

  1. 将模块A导入模块B记为 A->B, 代码类似这样: import B from 'B'
  2. 模块A动态导入模块B记为 A=>B, 代码类似这样: import(B)

考虑下面的模块结构：

  • A -> B, A => C，
  • C -> B

其中

  1. 模块A称为入口点
  2. 模块C称为动态入口点
  3. 模块B为普通模块

从 A, C两个模块， 通过静态导入可以到达B, 那么我们说 [A, C]是B的”依赖入口点集合” ， 同理：

  • A的依赖入口点集合是[A]
  • C的依赖入口点集合是[C]

打包时， 会将依赖入口点集合相等的模块分入同一个Chunk， 所以上面的模块结构会形成下面3个Chunk：

  • Chunk_0, 包含模块B
  • Chunk_1, 包含模块A
  • Chunk_2, 包含模块D

这就是Rollup的Chunk分配算法的本质。 在此基础上， Rollup进行了多项优化。

  1. 首先是排除不必要的Chunk， 比如现在有一个动态入口点C, 它被加载进来的时候内存里会有一些已经加载好的模块， 如果这些模块里有些也是C的依赖，那么C就可以直接从内存中加载他们， 反过来说， C可以从这些模块的依赖入口点集合中被移除。

    以上面的模块结构为例， C只会从A中通过动态导入加载进来， 而A会通过静态导入加载B， 所以此时B一定已经在内存中了， C可以直接从内存中导入B， 那么可以从B的依赖入口点集中删除D。

    这样， 重新调整的各模块的依赖入口点如下

    • B: [A]
    • A: [A]
    • C: [C]

    B, A的依赖入口点集合相等了， 所以最终形成了两个Chunk：

    • Chunk_0, 包含模块A， B
    • Chunk_1，包含模块C

    这样就优化了最终产物的数量。

    再看一个更复杂的模块结构：

    • X -> A, X -> B, X -> C,
    • Y -> A, Y -> B,
    • A => D,
    • D -> B, D -> C

    从X， Y两个模块，通过静态导入可以到达A， 那么我们认为[X, Y]是A的”依赖入口点集合“，
    同理：

    • B的依赖入口点集合是[X, Y, D]
    • C的依赖入口点集合是[X, D]
    • X的依赖入口点集合是[X]
    • Y的依赖入口点集合是[Y]
    • D的依赖入口点集合是[D]

    没有优化时， 上面的模块结构会形成下面6个chunk：

    1. Chunk_0, 包含模块A
    2. Chunk_1, 包含模块B
    3. Chunk_2, 包含模块C
    4. Chunk_3, 包含模块X
    5. Chunk_4, 包含模块Y
    6. Chunk_5, 包含模块D

    和第一个例子不同，A动态引入了D，没有其他静态引入， 而A的依赖入口点有两个: [X，Y], 那么当D加载进来的时候， 内存中的模块应该是X的依赖和Y的依赖的交集， 或者说， 所有依赖入口点包含[X, Y]的模块， 也就是A和B，那么现在就可以从B的依赖入口点集中移除D， 调整过后的A和B的依赖入口点都是[X, Y], 这意味着他们可以打包到一个Chunk中去了。

    真实项目中， 一个动态入口点可能会有多个引入者， 也就是说， 上面的例子中， 除了A， 可能还会有其他模块E, F, G…也会动态加载D， 我们需要统计这些引入者的依赖入口点的交集， 而依赖入口点包含这个交集的模块， 就是此时已经在内存中的模块。

  2. 另外就是大量使用位运算来替代Set，来降低算法的复杂度, 提高打包性能，据说之前会爆炸(10000+ files 俩小时)…这个主要体现在代码里，下面就来到源码里看看吧。

打包阶段的入口是 src/Bundle fn generate, 有两个主要的函数：generateChunks 和 renderChunks， 其中 generateChunks函数就是我们前面说的算法实现了， 主要逻辑部分是在 src/utils/chunkAssignment

源码分析

代码位于src/utils/chunkAssignment, 入口函数为getChunkAssignments, 主要就是三个函数。

  1. analyzeModuleGraph
  2. getChunksFromDependentEntries
  3. removeUnnecessaryDependentEntries
analyzeModuleGraph

这一步主要是获取分包的前置信息，提供后续使用， 包括

  1. 所有入口点
  2. 每个模块的依赖入口点集
  3. 每个动态入口点的每个导入者的依赖入口点集的并集
  4. 每个入口点的动态导入

下面来看代码

// file: src/utils/chunkAssignment
/**
 * @param entries 第一层入口点 大部分情况下就一个
 */
function analyzeModuleGraph(entries: Iterable<Module>): {
	allEntries: ReadonlyArray<Module>;
	dependentEntriesByModule: Map<Module, Set<number>>;
	dynamicImportsByEntry: ReadonlyArray<ReadonlySet<number>>;
	dynamicallyDependentEntriesByDynamicEntry: Map<number, Set<number>>;
} {
	const dynamicEntryModules = new Set<Module>();
	// 每个模块的 依赖入口点
	const dependentEntriesByModule: Map<Module, Set<number>> = new Map();
	// 每个入口点内拥有的 动态导入模块的集合 的数组
	const dynamicImportModulesByEntry: Set<Module>[] = [];
	// 所有入口点
	const allEntriesSet = new Set(entries);

	// 入口递增索引
	let entryIndex = 0;

	// 遍历所有入口点
	// 这是一个双循环,
	// 1. 首先每个模块进行搜索, 遍历自己的每一个静态导入,
  //    对于每个模块, 主要是把当前的入口点的索引放入 dependentEntriesByModule 中
  //    还有就是处理动态导入, [具体如何处理动态导入的]
	//
	// 2. 在循环体内, 某个module如果存在动态导入, 导入的模块就会被压入 allEntriesSet 中, 作为一个入口点进入后面的外层循环
	for (const currentEntry of allEntriesSet) {
	  // 当前入口点的动态导入模块
	  const dynamicImportsForCurrentEntry = new Set<Module>(); 
	  dynamicImportModulesByEntry.push(dynamicImportsForCurrentEntry);

	  // 初始化循环集合, 入口点就是内层循环的第一个被处理的模块
	  const modulesToHandle = new Set([currentEntry]);
	  // 这个循环中, 遇到静态导入的都会被压入modulesToHandle进行下一次循环
	  for (const module of modulesToHandle) {
	    // 从 dependentEntriesByModule 中拿到 module 的依赖项集合, 如果没有就通过 getNewSet 初始化一个新的
	    // getNewSet 就是返回一个空的, 包含数字的集合 (Set<number>)
	    // 也就是给 [[当前的module的][依赖入口点集]] 加上 [当前的入口索引]
	    getOrCreate(dependentEntriesByModule, module, getNewSet<number>).add(entryIndex);

	    // 遍历当前模块的所有静态导入的module, 加入到待处理队列
	    for (const dependency of module.getDependenciesToBeIncluded()) {
	      // 如果不是 ExternalModule 就加入 modulesToHandle
	      // 等后面的循环内处理
	      if (!(dependency instanceof ExternalModule)) {
	        modulesToHandle.add(dependency);
	      }
	    }

	    // 遍历动态导入
	    for (const { resolution } of module.dynamicImports) {
	      if (
	        // 是模块(而非外部模块,字符串, null)...
	        resolution instanceof Module &&
		// 动态导入的模块的 includedDynamicImporters 长度大于0
	        // 也就是 [有至少一个模块动态导入了这个模块]，
		resolution.includedDynamicImporters.length > 0 &&
		// 动态导入的模块不在 allEntriesSet 中
		!allEntriesSet.has(resolution)
	      ) {
		// 压入当前入口点的动态导入模块集合
		dynamicEntryModules.add(resolution);
		// 压入 allEntriesSet, 作为入口点进入后续的外层循环
		allEntriesSet.add(resolution);
		// 压入当前入口点的所有动态引入模块
		dynamicImportsForCurrentEntry.add(resolution);
	      }
	    }
	    // implicitlyLoadedBefore 应该是插件行为设置的
	    // 插件上下文内有个函数 emitFile, 如果产出了type为chunk的file, 会需要设置implicitlyLoadedBefore
	    // 这里暂时先不管
	    for (const dependency of module.implicitlyLoadedBefore) {
	      if (!allEntriesSet.has(dependency)) {
	        dynamicEntryModules.add(dependency);
		allEntriesSet.add(dependency);
	      }
	    }
	  }
	  entryIndex++;
	}

	// 除了一开始的入口点， 遇到动态导入的模块就生成一个新的入口点
	const allEntries = [...allEntriesSet];
	const { dynamicEntries, dynamicImportsByEntry } = getDynamicEntries(
	  allEntries,
	  dynamicEntryModules,
	  dynamicImportModulesByEntry
	);
	return {
	  allEntries,
	  dependentEntriesByModule,

	  // 动态入口点的每个导入者的依赖入口点的并集
	  dynamicallyDependentEntriesByDynamicEntry: getDynamicallyDependentEntriesByDynamicEntry(
	    dependentEntriesByModule,
	    dynamicEntries,
	    allEntries
	  ),

	  // 每个入口点的动态导入
	  dynamicImportsByEntry
	};
}
getChunksFromDependentEntries

这个函数比较简单， 就是使用上一步的每个模块的依赖入口点信息，将具有相同依赖入口点的所有模块集合在一起， 得到所有的Chunks， 当然这里的Chunks是没有经过优化的。

function getChunksFromDependentEntries(
	modulesWithDependentEntries: Iterable<ModulesWithDependentEntries>
): ModulesWithDependentEntries[] {
	const chunkModules: {
	  [signature: string]: ModulesWithDependentEntries;
	} = Object.create(null);
	for (const { dependentEntries, modules } of modulesWithDependentEntries) {
    // 初始化每个chunk的唯一签名
	  let chunkSignature = 0n;
	  for (const entryIndex of dependentEntries) {
      // 每个入口点都有唯一的索引，用1左移索引位，就在二进制数上标记了这个入口
      // 所有入口的二进制数在一起按位或，每个chunk就有了一个唯一的二进制数作为签名
	    chunkSignature |= 1n << BigInt(entryIndex);
	  }
	  (chunkModules[String(chunkSignature)] ||= {
	    dependentEntries: new Set(dependentEntries),
	      modules: []
	  }).modules.push(...modules);
	}
	return Object.values(chunkModules);
}

以前面提到的那个模块结构为例

  • A -> B, A -> C, A => D，
  • D -> B, D -> C

这个函数最终得到的结果如下：

[
  { dependentEntries: Set(1) { 0 }, modules: [ [Module] ] },
  { dependentEntries: Set(1) { 1 }, modules: [ [Module] ] },
  { dependentEntries: Set(2) { 0, 1 }, modules: [ [Module] ] }
]
removeUnnecessaryDependentEntries

这个函数实现对chunk的优化

function removeUnnecessaryDependentEntries(
	chunks: ModulesWithDependentEntries[],
	dynamicallyDependentEntriesByDynamicEntry: Map<number, Set<number>>,
	dynamicImportsByEntry: ReadonlyArray<ReadonlySet<number>>,
	allEntries: ReadonlyArray<Module>
) {
  // 用一个二进制数来表示所有的chunk， chunk0在最低位
  
  // staticDependenciesPerEntry 用于记录一个入口点静态导入了哪些chunk，或者说，是哪些chunk的依赖入口点
  // 以 a->b, a=>c, c->b 的模块结构来说，这个结构形成的chunks如下
  // chunk_0, 包含a, 依赖入口点是 [a]
  // chunk_1, 包含c，依赖入口点是 [c]
  // chunk_2, 包含b, 依赖入口点是 [a, c]
  // 那么，对于入口点a, 它是chunk_0和chunk_2的依赖入口点，表示为 001b 和 100b 按位或，值为 101b
  // 对于入口点c,它是chunk_1和chunk_2的依赖入口点，表示为 010b 和 100b 按位或，值为 110b
  const staticDependenciesPerEntry: bigint[] = allEntries.map(() => 0n);

  // alreadyLoadedChunksPerEntry 用于记录一个入口点导入了哪些chunk, 
  // 可以认为是 staticDependenciesPerEntry 的超集，多了通过动态导入的chunk
  const alreadyLoadedChunksPerEntry: bigint[] = allEntries.map((_entry, entryIndex) =>
    // 如果是动态入口点，在被加载进来时可能会存在已经加载的chunk， 所以初始化为-1
    // -1转为二进制的话每个位上都是1， 可以作为按位与（求交集）运算时的初始值
    // 如果不是动态入口点， 一般就是整个应用的入口点， 这种入口点加载进来时不会有已经加载的chunk
    // 所以初始化为0
    dynamicallyDependentEntriesByDynamicEntry.has(entryIndex) ? -1n : 0n
  );

  // 开始填充 staticDependenciesPerEntry 
  let chunkMask = 1n;
  for (const { dependentEntries } of chunks) {
    for (const entryIndex of dependentEntries) {
      // 按位或，收集所有依赖入口点集中包含当前入口点的chunk
      staticDependenciesPerEntry[entryIndex] |= chunkMask;
    }
    // 掩码随着遍历所有chunks，依次左移，代表每个chunk在二进制上的位置
    chunkMask <<= 1n;
  }
  
  const updatedDynamicallyDependentEntriesByDynamicEntry = dynamicallyDependentEntriesByDynamicEntry;
  // 开始填充 alreadyLoadedChunksPerEntry
  for (const [
    // 动态入口点的索引
    dynamicEntryIndex,
    // 加载这个动态入口点的模块的依赖入口点的并集
    updatedDynamicallyDependentEntries
  ] of updatedDynamicallyDependentEntriesByDynamicEntry) {
    // 消耗掉
    updatedDynamicallyDependentEntriesByDynamicEntry.delete(dynamicEntryIndex);
    // 动态入口点的 alreadyLoadedChunksPerEntry 初始化为 -1
    const previousLoadedModules = alreadyLoadedChunksPerEntry[dynamicEntryIndex];
    let newLoadedModules = previousLoadedModules;

    //得到当前入口点被加载时的所有已加载chunk
    for (const entryIndex of updatedDynamicallyDependentEntries) {
      // 所有入口点各自导入的chunks通过按位与求交集
      newLoadedModules &=
        // 每个入口点通过静态导入和动态导入的chunks通过按位或求并集
        staticDependenciesPerEntry[entryIndex] | alreadyLoadedChunksPerEntry[entryIndex];
    }

    // 上面的例子来说的话， newLoadedModules现在应该是 101b, 也就是， c被动态加载进来的时候， 内存里应该有chunk0， chunk2
    // 而 previousLoadedModules 是初始化的 -1， 111b
    // 两者不等， 进入条件语句块
		
    if (newLoadedModules !== previousLoadedModules) {
      // 填充 alreadyLoadedChunksPerEntry
      alreadyLoadedChunksPerEntry[dynamicEntryIndex] = newLoadedModules;

      // 动态入口点自己也动态引入了一些其他模块， 比如c=>d
      // 用于后续处理
      for (const dynamicImport of dynamicImportsByEntry[dynamicEntryIndex]) {
        getOrCreate(
          updatedDynamicallyDependentEntriesByDynamicEntry,
          dynamicImport,
          getNewSet<number>
        ).add(dynamicEntryIndex);
      }
    }
  }
  
  // 开始优化(从chunk中删除不必要的依赖入口点)
  chunkMask = 1n;
  // 以上面的结构为例
  // [
  //   { dependentEntries: Set(1) { 0 }, modules: [ [Module] ] },
  //   { dependentEntries: Set(1) { 1 }, modules: [ [Module] ] },
  //   { dependentEntries: Set(2) { 0, 1 }, modules: [ [Module] ] }
  // ]
  // chunk0, entry0， 也就是a， 在a进来时没有任何已经加载的chunk， 因此是 000b， 按位与后不满足条件
  // chunk1, entry1， 也就是c, c是动态入口点， 已经加载的chunk是chunk0， chunk2， 因此是 101b， 和010b 按位与后是 000b， 不满足条件
  // chunk2，entry0， 是a， 同第一次循环， 按位与后不满足条件
  // chunk2，entry1， 是c，已经加载的chunk是chunk0， chunk2， 也就是 101b， 和100b按位与后是 100b, 满足条件， 删除
  for (const { dependentEntries } of chunks) {
    for (const entryIndex of dependentEntries) {
      if ((alreadyLoadedChunksPerEntry[entryIndex] & chunkMask) === chunkMask) {
        dependentEntries.delete(entryIndex);
      }
    }
    chunkMask <<= 1n;
  }
}
experimentalMinChunkSize

如果在rollup的config里配置了experimentalMinChunkSize, 接下来还会尝试合并较小的chunks， 主要考虑的是每个chunk的副作用， 也就是类似

import 'moduleMayhasSideEffect'

这种， 导入进来的模块会自动执行一些”side effect”, 诸如全局函数调用，修改全局变量，或者是有可能抛出错误， 总之只有两个chunk合并后， 不会触发合并之前也不会触发的副作用才有可能合并。

这部分不属于分包算法了， 源码暂时略过， 知道大概即可。

© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END

# rollup.js
喜欢就支持一下吧
点赞0

Warning: mysqli_query(): (HY000/3): Error writing file '/tmp/MYTCChCG' (Errcode: 28 - No space left on device) in /www/wwwroot/583.cn/wp-includes/class-wpdb.php on line 2345
admin的头像-五八三
相关推荐
Vite 打包 chunk 优化-五八三
Vite 打包 chunk 优化
Vite 打包 chunk 优化
2年前 36
如何使用 Rollup 插件开发-五八三
如何使用 Rollup 插件开发
如何使用 Rollup 插件开发
2年前 20
Rollup 从入门到熟悉-五八三
Rollup 从入门到熟悉
Rollup 从入门到熟悉
2年前 15
Rollup 分包算法 源码阅读-五八三
Rollup 分包算法 源码阅读
Rollup 分包算法 源码阅读
2年前 12
Rollup炼金术：打造NPM包提高开发效率！-五八三
Rollup炼金术：打造NPM包提高开发效率！
Rollup炼金术：打造NPM包提高开发效率！
2年前 8
使用rollup构建企业级的类antd组件库-五八三
使用rollup构建企业级的类antd组件库
使用rollup构建企业级的类antd组件库
2年前 6
评论 抢沙发
头像
欢迎您留下宝贵的见解！
提交
头像

昵称

图形验证码
取消
昵称

请填写用户信息：

  • 昵称(必填)
  • 邮箱(必填)
代码

请输入代码：

确认
图片
热门推荐