blob: 1ce35e69dccda9c832f404d675611664b5f0cf46 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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);
}
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[]>();
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);
}
}
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);
}
}
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;
}
|
