Repository: artusjs/core
Pull request #262 (2023-08-24 09:44:37)

refactor(plugin): use standard dfs instead of topological for stable sort
## Background

之前插件的按依赖排序使用了拓扑排序算法；

- 优点是有向无环图理论复杂度低，可以较容易检查循环依赖；
- 缺点是不稳定排序，可能造成 config 内锚定的无关依赖顺序漂移；

而插件排序场景中对于不能靠 `dependencies` 声明来实现的，较普遍使用 pluginConfig 中的顺序做依赖顺序保障，而拓扑排序使顺序漂移问题变得不易发现和处理。

## Example

例如，当我们有这段配置时：

```js
[
  { name: 'a', deps: [ 'b', 'c' ] },
  { name: 'b', deps: [ 'c' ] },
  { name: 'c', deps: [] },
  { name: 'd', deps: [ 'c' ] }
]
```

依赖链路为：

```plain
a -> b -> c
a -> c
b -> c
d -> c
```

期待的顺序为 `c, b, a, d`，即对于 a / d 作为无关项保持配置中的顺序；

然而，因为拓扑排序不稳定，最终顺序与依赖链长度有关（indegree 出队顺序），所以结果会是 `c, b, d, a`，如果 a / d 间有相互影响，将产生不可用现象

## Solution

综上，有必要对该部分做出改变

该 PR 通过 DFS 重新实现 `PluginFactory.createFromConfig` 方法，在递归过程中进行 `optional` 和循环依赖检查；

同时优化了 Plugin 类的实现代码，移除了无用方法;

调整了 plugin 相关单测，顺序保证增加到 4 个，并使用上述的依赖链 case 做验证

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs) Report
Patch coverage: **`95.00%`** and project coverage change: **`-0.05%`** :warning:
> Comparison is base [(`6e591b4`)](https://app.codecov.io/gh/artusjs/core/commit/6e591b4260f5c0152b9ac81a70e57733908b4800?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs) 91.68% compared to head [(`43f61ca`)](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs) 91.63%.

:exclamation: Your organization is not using the GitHub App Integration. As a result you may experience degraded service beginning May 15th. Please [install the Github App Integration](https://github.com/apps/codecov) for your organization. [Read more](https://about.codecov.io/blog/codecov-is-updating-its-github-integration/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs).

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master     #262      +/-   ##
==========================================
- Coverage   91.68%   91.63%   -0.05%     
==========================================
  Files          49       49              
  Lines        1203     1184      -19     
  Branches      213      212       -1     
==========================================
- Hits         1103     1085      -18     
+ Misses        100       99       -1     
```


| [Files Changed](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs) | Coverage Δ | |
|---|---|---|
| [src/plugin/types.ts](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs#diff-c3JjL3BsdWdpbi90eXBlcy50cw==) | `100.00% <ø> (ø)` | |
| [src/plugin/impl.ts](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs#diff-c3JjL3BsdWdpbi9pbXBsLnRz) | `80.00% <66.66%> (-6.89%)` | :arrow_down: |
| [src/plugin/common.ts](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs#diff-c3JjL3BsdWdpbi9jb21tb24udHM=) | `98.00% <97.05%> (+0.38%)` | :arrow_up: |
| [src/plugin/factory.ts](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs#diff-c3JjL3BsdWdpbi9mYWN0b3J5LnRz) | `100.00% <100.00%> (+8.33%)` | :arrow_up: |


</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/artusjs/core/pull/262?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=artusjs).


Patch:
diff --git a/package.json b/package.json
index 8aef6e3..6a9bc96 100644
--- a/package.json
+++ b/package.json
@@ -1,6 +1,6 @@
 {
   "name": "@artus/core",
-  "version": "2.0.5",
+  "version": "2.1.0",
   "description": "Core package of Artus",
   "main": "./lib/index.js",
   "types": "./lib/index.d.ts",
diff --git a/src/plugin/common.ts b/src/plugin/common.ts
index 58638d7..7b3d89f 100644
--- a/src/plugin/common.ts
+++ b/src/plugin/common.ts
@@ -1,62 +1,86 @@
-import path from 'path';
-import compatibleRequire from '../utils/compatible_require';
-import { PluginType } from './types';
+import path from "path";
+import compatibleRequire from "../utils/compatible_require";
+import { PluginType } from "./types";
+import { LoggerType } from "../logger";
 
-// A utils function that toplogical sort plugins
-export function topologicalSort(pluginInstanceMap: Map<string, PluginType>, pluginDepEdgeList: [string, string][]): string[] {
-  const res: string[] = [];
-  const indegree: Map<string, number> = new Map();
+export function sortPlugins(
+  pluginInstanceMap: Map<string, PluginType>,
+  logger: LoggerType,
+): PluginType[] {
+  const sortedPlugins: PluginType[] = [];
+  const visited: Record<string, boolean> = {};
 
-  pluginDepEdgeList.forEach(([to]) => {
-    indegree.set(to, (indegree.get(to) ?? 0) + 1);
-  });
+  const visit = (pluginName: string, depChain: string[] = []) => {
+    if (depChain.includes(pluginName)) {
+      throw new Error(
+        `Circular dependency found in plugins: ${depChain.join(", ")}`,
+      );
+    }
 
-  const queue: string[] = [];
+    if (visited[pluginName]) return;
 
-  for (const [name] of pluginInstanceMap) {
-    if (!indegree.has(name)) {
-      queue.push(name);
-    }
-  }
+    visited[pluginName] = true;
 
-  while(queue.length) {
-    const cur = queue.shift()!;
-    res.push(cur);
-    for (const [to, from] of pluginDepEdgeList) {
-      if (from === cur) {
-        indegree.set(to, (indegree.get(to) ?? 0) - 1);
-        if (indegree.get(to) === 0) {
-          queue.push(to);
+    const plugin = pluginInstanceMap.get(pluginName);
+    if (plugin) {
+      for (const dep of plugin.metadata.dependencies ?? []) {
+        const depPlugin = pluginInstanceMap.get(dep.name);
+        if (!depPlugin || !depPlugin.enable) {
+          if (dep.optional) {
+            logger?.warn(
+              `Plugin ${plugin.name} need have optional dependency: ${dep.name}.`,
+            );
+          } else {
+            throw new Error(
+              `Plugin ${plugin.name} need have dependency: ${dep.name}.`,
+            );
+          }
+        } else {
+          // Plugin exist and enabled, need visit
+          visit(dep.name, depChain.concat(pluginName));
         }
       }
+      sortedPlugins.push(plugin);
     }
+  };
+
+  for (const pluginName of pluginInstanceMap.keys()) {
+    visit(pluginName);
   }
-  return res;
+
+  return sortedPlugins;
 }
 
 // A util function of get package path for plugin
-export function getPackagePath(packageName: string, paths: string[] = []): string {
+export function getPackagePath(
+  packageName: string,
+  paths: string[] = [],
+): string {
   const opts = {
     paths: paths.concat(__dirname),
   };
   return path.dirname(require.resolve(packageName, opts));
 }
 
-export async function getInlinePackageEntryPath(packagePath: string): Promise<string> {
+export async function getInlinePackageEntryPath(
+  packagePath: string,
+): Promise<string> {
   const pkgJson = await compatibleRequire(`${packagePath}/package.json`);
-  let entryFilePath = '';
+  let entryFilePath = "";
   if (pkgJson.exports) {
     if (Array.isArray(pkgJson.exports)) {
       throw new Error(`inline package multi exports is not supported`);
-    } else if (typeof pkgJson.exports === 'string') {
+    } else if (typeof pkgJson.exports === "string") {
       entryFilePath = pkgJson.exports;
-    } else if (pkgJson.exports?.['.']) {
-      entryFilePath = pkgJson.exports['.'];
+    } else if (pkgJson.exports?.["."]) {
+      entryFilePath = pkgJson.exports["."];
     }
   }
   if (!entryFilePath && pkgJson.main) {
     entryFilePath = pkgJson.main;
   }
   // will use package root path if no entry file found
-  return entryFilePath ? path.resolve(packagePath, entryFilePath, '..') : packagePath;
+  return entryFilePath
+    ? path.resolve(packagePath, entryFilePath, "..")
+    : packagePath;
 }
diff --git a/src/plugin/factory.ts b/src/plugin/factory.ts
index e8cdd42..b1299ac 100644
--- a/src/plugin/factory.ts
+++ b/src/plugin/factory.ts
@@ -1,33 +1,17 @@
-import { topologicalSort } from './common';
+import { sortPlugins } from './common';
 import { Plugin } from './impl';
 import { PluginConfigItem, PluginCreateOptions, PluginMap, PluginType } from './types';
 
 export class PluginFactory {
-  static async create(name: string, item: PluginConfigItem, opts?: PluginCreateOptions): Promise<PluginType> {
-    const pluginInstance = new Plugin(name, item, opts);
-    await pluginInstance.init();
-    return pluginInstance;
-  }
-
   static async createFromConfig(config: Record<string, PluginConfigItem>, opts?: PluginCreateOptions): Promise<PluginType[]> {
     const pluginInstanceMap: PluginMap = new Map();
     for (const [name, item] of Object.entries(config)) {
-      const pluginInstance = await PluginFactory.create(name, item, opts);
-      if (pluginInstance.enable) {
+      if (item.enable) {
+        const pluginInstance = new Plugin(name, item);
+        await pluginInstance.init();
         pluginInstanceMap.set(name, pluginInstance);
       }
     }
-    let pluginDepEdgeList: [string, string][] = [];
-    // Topological sort plugins
-    for (const [_name, pluginInstance] of pluginInstanceMap) {
-      pluginInstance.checkDepExisted(pluginInstanceMap);
-      pluginDepEdgeList = pluginDepEdgeList.concat(pluginInstance.getDepEdgeList());
-    }
-    const pluginSortResult: string[] = topologicalSort(pluginInstanceMap, pluginDepEdgeList);
-    if (pluginSortResult.length !== pluginInstanceMap.size) {
-      const diffPlugin = [...pluginInstanceMap.keys()].filter(name => !pluginSortResult.includes(name));
-      throw new Error(`There is a cycle in the dependencies, wrong plugin is ${diffPlugin.join(',')}.`);
-    }
-    return pluginSortResult.map(name => pluginInstanceMap.get(name)!);
+    return sortPlugins(pluginInstanceMap, opts?.logger);
   }
 }
diff --git a/src/plugin/impl.ts b/src/plugin/impl.ts
index fe42bbc..8b5bd21 100644
--- a/src/plugin/impl.ts
+++ b/src/plugin/impl.ts
@@ -2,9 +2,8 @@ import path from 'path';
 import { loadMetaFile } from '../utils/load_meta_file';
 import { exists } from '../utils/fs';
 import { PLUGIN_META_FILENAME } from '../constant';
-import { PluginConfigItem, PluginCreateOptions, PluginMap, PluginMetadata, PluginType } from './types';
+import { PluginConfigItem, PluginMetadata, PluginType } from './types';
 import { getPackagePath } from './common';
-import { LoggerType } from '../logger';
 
 export class Plugin implements PluginType {
   public name: string;
@@ -13,9 +12,7 @@ export class Plugin implements PluginType {
   public metadata: Partial<PluginMetadata>;
   public metaFilePath = '';
 
-  private logger?: LoggerType;
-
-  constructor(name: string, configItem: PluginConfigItem, opts?: PluginCreateOptions) {
+  constructor(name: string, configItem: PluginConfigItem) {
     this.name = name;
     this.enable = configItem.enable ?? false;
     if (this.enable) {
@@ -34,10 +31,9 @@ export class Plugin implements PluginType {
     if (configItem.metadata) {
       this.metadata = configItem.metadata;
     }
-    this.logger = opts?.logger;
   }
 
-  async init() {
+  public async init() {
     if (!this.enable) {
       return;
     }
@@ -50,33 +46,6 @@ export class Plugin implements PluginType {
     }
   }
 
-  public checkDepExisted(pluginMap: PluginMap) {
-    if (!this.metadata.dependencies) {
-      return;
-    }
-
-    for (let i = 0; i < this.metadata.dependencies.length; i++) {
-      const { name: pluginName, optional } = this.metadata.dependencies[i];
-      const instance = pluginMap.get(pluginName);
-      if (!instance || !instance.enable) {
-        if (optional) {
-          this.logger?.warn(`Plugin ${this.name} need have optional dependency: ${pluginName}.`);
-        } else {
-          throw new Error(`Plugin ${this.name} need have dependency: ${pluginName}.`);
-        }
-      } else {
-        // Plugin exist and enabled, need calc edge
-        this.metadata.dependencies[i]._enabled = true;
-      }
-    }
-  }
-
-  public getDepEdgeList(): [string, string][] {
-    return this.metadata.dependencies
-      ?.filter(({ optional, _enabled }) => !optional || _enabled)
-      ?.map(({ name: depPluginName }) => [this.name, depPluginName]) ?? [];
-  }
-
   private async checkAndLoadMetadata() {
     // check metadata from configItem
     if (this.metadata) {
diff --git a/src/plugin/types.ts b/src/plugin/types.ts
index b271b07..8c6c713 100644
--- a/src/plugin/types.ts
+++ b/src/plugin/types.ts
@@ -39,6 +39,4 @@ export interface PluginType {
   metaFilePath: string;
 
   init(): Promise<void>;
-  checkDepExisted(map: PluginMap): void;
-  getDepEdgeList(): [string, string][];
 }


Test patch:
diff --git a/test/plugin.test.ts b/test/plugin.test.ts
index 42ed5bc..284de25 100644
--- a/test/plugin.test.ts
+++ b/test/plugin.test.ts
@@ -4,51 +4,34 @@ import { Logger, Plugin, PluginFactory } from '../src';
 
 const pluginPrefix = 'fixtures/plugins';
 
-describe('test/app.test.ts', () => {
+describe('test/plugin.test.ts', () => {
   describe('app with config', () => {
     it('should load plugin with dep order', async () => {
       const mockPluginConfig = {
         'plugin-a': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_a`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_a/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-b': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_b`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_b/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-c': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_c`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_c/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
+        },
+        'plugin-d': {
+          enable: true,
+          path: path.resolve(__dirname, `${pluginPrefix}/plugin_d`),
         },
       };
       const pluginList = await PluginFactory.createFromConfig(mockPluginConfig);
-      expect(pluginList.length).toEqual(3);
+      expect(pluginList.length).toEqual(4);
       pluginList.forEach(plugin => {
         expect(plugin).toBeInstanceOf(Plugin);
         expect(plugin.enable).toBeTruthy();
       });
-      expect(pluginList.map(plugin => plugin.name)).toStrictEqual(['plugin-c', 'plugin-b', 'plugin-a']);
+      expect(pluginList.map(plugin => plugin.name)).toStrictEqual(['plugin-c', 'plugin-b', 'plugin-a', 'plugin-d']);
     });
 
     it('should not load plugin with wrong order', async () => {
@@ -56,62 +39,31 @@ describe('test/app.test.ts', () => {
         'plugin-a': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_a`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_a/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-b': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_b`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_b/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-c': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_c`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_c/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
+        },
+        'plugin-d': {
+          enable: true,
+          path: path.resolve(__dirname, `${pluginPrefix}/plugin_d`),
         },
         'plugin-wrong-a': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_wrong_a`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_wrong_a/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-wrong-b': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_wrong_b`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_wrong_b/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };
-      expect(async () => {
+      await expect(async () => {
         await PluginFactory.createFromConfig(mockPluginConfig);
-      }).rejects.toThrowError(new Error(`There is a cycle in the dependencies, wrong plugin is plugin-wrong-a,plugin-wrong-b.`));
+      }).rejects.toThrowError(new Error(`Circular dependency found in plugins: plugin-wrong-a, plugin-wrong-b`));
     });
 
     it('should throw if dependencies missing', async () => {
@@ -119,13 +71,6 @@ describe('test/app.test.ts', () => {
         'plugin-a': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_a`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_a/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };
       expect(async () => {
@@ -138,38 +83,17 @@ describe('test/app.test.ts', () => {
         'plugin-a': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_a`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_a/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-b': {
           enable: false,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_b`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_b/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-c': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_c`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_c/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };
-      expect(async () => {
+      await expect(async () => {
         await PluginFactory.createFromConfig(mockPluginConfig);
       }).rejects.toThrowError(new Error(`Plugin plugin-a need have dependency: plugin-b.`));
     });
@@ -179,13 +103,6 @@ describe('test/app.test.ts', () => {
         'plugin-d': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_d`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_d/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };
 
@@ -209,27 +126,13 @@ describe('test/app.test.ts', () => {
 
     it('should not throw if optional dependence disabled', async () => {
       const mockPluginConfig = {
-        'plugin-c': {
+        'plugin-b': {
           enable: false,
-          path: path.resolve(__dirname, `${pluginPrefix}/plugin_c`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_c/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
+          path: path.resolve(__dirname, `${pluginPrefix}/plugin_b`),
         },
         'plugin-d': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_d`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_d/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };
 
@@ -256,24 +159,10 @@ describe('test/app.test.ts', () => {
         'plugin-d': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_d`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_d/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
         'plugin-c': {
           enable: true,
           path: path.resolve(__dirname, `${pluginPrefix}/plugin_c`),
-          manifest: {
-            pluginMeta: {
-              path: path.resolve(__dirname, `${pluginPrefix}/plugin_c/meta.js`),
-              extname: '.js',
-              filename: 'meta.js',
-            },
-          },
         },
       };