summaryrefslogtreecommitdiffhomepage
path: root/packages/kernel/src/host/dag.ts
diff options
context:
space:
mode:
Diffstat (limited to 'packages/kernel/src/host/dag.ts')
-rw-r--r--packages/kernel/src/host/dag.ts104
1 files changed, 52 insertions, 52 deletions
diff --git a/packages/kernel/src/host/dag.ts b/packages/kernel/src/host/dag.ts
index 5cde2f5..1ce35e6 100644
--- a/packages/kernel/src/host/dag.ts
+++ b/packages/kernel/src/host/dag.ts
@@ -1,64 +1,64 @@
import type { Manifest } from "../contracts/extension.js";
export function resolveActivationOrder(manifests: readonly Manifest[]): Manifest[] {
- const byId = new Map<string, Manifest>();
- for (const m of manifests) {
- if (byId.has(m.id)) {
- throw new Error(`Duplicate extension id: "${m.id}"`);
- }
- byId.set(m.id, m);
- }
+ const byId = new Map<string, Manifest>();
+ for (const m of manifests) {
+ if (byId.has(m.id)) {
+ throw new Error(`Duplicate extension id: "${m.id}"`);
+ }
+ byId.set(m.id, m);
+ }
- for (const m of manifests) {
- for (const dep of m.dependsOn ?? []) {
- if (!byId.has(dep)) {
- throw new Error(`Extension "${m.id}" depends on "${dep}", which is not available.`);
- }
- }
- }
+ for (const m of manifests) {
+ for (const dep of m.dependsOn ?? []) {
+ if (!byId.has(dep)) {
+ throw new Error(`Extension "${m.id}" depends on "${dep}", which is not available.`);
+ }
+ }
+ }
- const inDegree = new Map<string, number>();
- const dependents = new Map<string, string[]>();
+ const inDegree = new Map<string, number>();
+ const dependents = new Map<string, string[]>();
- for (const m of manifests) {
- inDegree.set(m.id, 0);
- dependents.set(m.id, []);
- }
+ for (const m of manifests) {
+ inDegree.set(m.id, 0);
+ dependents.set(m.id, []);
+ }
- for (const m of manifests) {
- for (const dep of m.dependsOn ?? []) {
- const list = dependents.get(dep);
- if (list !== undefined) list.push(m.id);
- inDegree.set(m.id, (inDegree.get(m.id) ?? 0) + 1);
- }
- }
+ for (const m of manifests) {
+ for (const dep of m.dependsOn ?? []) {
+ const list = dependents.get(dep);
+ if (list !== undefined) list.push(m.id);
+ inDegree.set(m.id, (inDegree.get(m.id) ?? 0) + 1);
+ }
+ }
- const queue: string[] = [];
- for (const [id, deg] of inDegree) {
- if (deg === 0) queue.push(id);
- }
+ const queue: string[] = [];
+ for (const [id, deg] of inDegree) {
+ if (deg === 0) queue.push(id);
+ }
- const result: Manifest[] = [];
- let idx = 0;
- while (idx < queue.length) {
- const id = queue[idx];
- if (id === undefined) break;
- idx++;
- const m = byId.get(id);
- if (m === undefined) continue;
- result.push(m);
- for (const dep of dependents.get(id) ?? []) {
- const newDeg = (inDegree.get(dep) ?? 1) - 1;
- inDegree.set(dep, newDeg);
- if (newDeg === 0) queue.push(dep);
- }
- }
+ const result: Manifest[] = [];
+ let idx = 0;
+ while (idx < queue.length) {
+ const id = queue[idx];
+ if (id === undefined) break;
+ idx++;
+ const m = byId.get(id);
+ if (m === undefined) continue;
+ result.push(m);
+ for (const dep of dependents.get(id) ?? []) {
+ const newDeg = (inDegree.get(dep) ?? 1) - 1;
+ inDegree.set(dep, newDeg);
+ if (newDeg === 0) queue.push(dep);
+ }
+ }
- if (result.length !== manifests.length) {
- const remaining = manifests.filter((m) => !result.some((r) => r.id === m.id));
- const ids = remaining.map((m) => m.id).join(", ");
- throw new Error(`Dependency cycle detected among extensions: ${ids}`);
- }
+ if (result.length !== manifests.length) {
+ const remaining = manifests.filter((m) => !result.some((r) => r.id === m.id));
+ const ids = remaining.map((m) => m.id).join(", ");
+ throw new Error(`Dependency cycle detected among extensions: ${ids}`);
+ }
- return result;
+ return result;
}