195 lines
5.4 kB
1
import Logger from "./logger";
2
3
const logger = new Logger("core/util/dependency");
4
5
export type Dependency<T, D> = {
6
id: T;
7
data: D;
8
};
9
type Dependencies<T, D> = Dependency<T, D>[];
10
type DependencyGraph<T> = Map<T, Set<T> | null>;
11
12
type FetchDep<T, D> = (id: T) => D | null;
13
type GetDeps<T, D> = (item: Dependency<T, D>) => T[];
14
type GetIncompatible<T, D> = (item: Dependency<T, D>) => T[];
15
type GetEnabled<T, D> = (item: Dependency<T, D>) => boolean;
16
17
function buildDependencyGraph<T, D>(
18
origItems: Dependencies<T, D>,
19
{
20
fetchDep,
21
getDeps,
22
getIncompatible,
23
getEnabled
24
}: {
25
fetchDep: FetchDep<T, D>;
26
getDeps: GetDeps<T, D>;
27
getIncompatible?: GetIncompatible<T, D>;
28
getEnabled?: GetEnabled<T, D>;
29
}
30
): [Dependencies<T, D>, DependencyGraph<T>] {
31
let items = [...origItems];
32
const dependencyGraph: DependencyGraph<T> = new Map();
33
34
for (const item of items) {
35
const fullDeps: Set<T> = new Set();
36
let failed = false;
37
38
function resolveDeps(id: T, root: boolean) {
39
if (id === item.id && !root) {
40
logger.warn(`Circular dependency detected: "${item.id}"`);
41
failed = true;
42
return;
43
}
44
45
const obj = fetchDep(id);
46
if (obj == null) {
47
logger.warn(`Missing dependency detected`, id);
48
failed = true;
49
return;
50
}
51
52
if (!root) fullDeps.add(id);
53
54
for (const dep of getDeps({ id, data: obj })) {
55
resolveDeps(dep, false);
56
}
57
}
58
59
resolveDeps(item.id, true);
60
dependencyGraph.set(item.id, failed ? null : fullDeps);
61
}
62
63
logger.trace("Failed stage", items);
64
function isFailed(id: T) {
65
const deps = dependencyGraph.get(id);
66
if (deps === null) return true;
67
68
// For some reason this can be undefined. If it is, it's not null, so we
69
// didn't explicitly fail. FIXME too tired to investigate
70
if (deps === undefined) return false;
71
72
for (const dep of deps) {
73
if (isFailed(dep)) return true;
74
}
75
76
return false;
77
}
78
79
const failed = items.filter((item) => isFailed(item.id));
80
if (failed.length > 0) {
81
logger.warn("Skipping failed items", failed);
82
items = items.filter((item) => !failed.includes(item));
83
}
84
85
return [items, dependencyGraph];
86
}
87
88
export default function calculateDependencies<T, D>(
89
origItems: Dependencies<T, D>,
90
{
91
fetchDep,
92
getDeps,
93
getIncompatible,
94
getEnabled
95
}: {
96
fetchDep: FetchDep<T, D>;
97
getDeps: GetDeps<T, D>;
98
getIncompatible?: GetIncompatible<T, D>;
99
getEnabled?: GetEnabled<T, D>;
100
}
101
): [Dependencies<T, D>, DependencyGraph<T>] {
102
logger.trace("sortDependencies begin", origItems);
103
// eslint-disable-next-line prefer-const
104
let [itemsOrig, dependencyGraphOrig] = buildDependencyGraph(origItems, {
105
fetchDep,
106
getDeps,
107
getIncompatible,
108
getEnabled
109
});
110
111
if (getEnabled != null) {
112
logger.trace("Enabled stage", itemsOrig);
113
const implicitlyEnabled: T[] = [];
114
115
function validateDeps(dep: Dependency<T, D>) {
116
if (getEnabled!(dep)) {
117
const deps = dependencyGraphOrig.get(dep.id)!;
118
for (const id of deps.values()) {
119
const data = fetchDep(id)!;
120
validateDeps({ id, data });
121
}
122
} else {
123
const dependsOnMe = Array.from(dependencyGraphOrig.entries()).filter(([, v]) => v?.has(dep.id));
124
125
if (dependsOnMe.length > 0) {
126
logger.debug("Implicitly enabling dependency", dep.id);
127
implicitlyEnabled.push(dep.id);
128
}
129
}
130
}
131
132
for (const dep of itemsOrig) validateDeps(dep);
133
itemsOrig = itemsOrig.filter((x) => getEnabled(x) || implicitlyEnabled.includes(x.id));
134
}
135
136
if (getIncompatible != null) {
137
logger.trace("Incompatible stage", itemsOrig);
138
139
for (const item of itemsOrig) {
140
// JavaScript iterator moment
141
if (!itemsOrig.includes(item)) continue;
142
143
const incompatibleItems = getIncompatible(item);
144
for (const incompatibleItem of incompatibleItems) {
145
if (itemsOrig.find((x) => x.id === incompatibleItem) != null) {
146
logger.warn(
147
`Incompatible dependency detected: "${item.id}" and "${incompatibleItem}" - removing "${incompatibleItem}"`
148
);
149
150
itemsOrig = itemsOrig.filter((x) => x.id !== incompatibleItem);
151
}
152
}
153
}
154
}
155
156
logger.trace("Verification stage", itemsOrig);
157
const [items, dependencyGraph] = buildDependencyGraph(itemsOrig, {
158
fetchDep,
159
getDeps,
160
getIncompatible,
161
getEnabled
162
});
163
164
logger.trace("Sorting stage", items);
165
const sorted: Dependency<T, D>[] = [];
166
167
// Clone the dependency graph to return it later
168
const backupDependencyGraph = new Map(dependencyGraph);
169
for (const item of items) {
170
dependencyGraph.set(item.id, new Set(dependencyGraph.get(item.id)));
171
}
172
173
while (Array.from(dependencyGraph.values()).filter((x) => x != null).length > 0) {
174
const noDependents = items.filter((e) => dependencyGraph.get(e.id)?.size === 0);
175
176
if (noDependents.length === 0) {
177
logger.warn("Stuck dependency graph detected", dependencyGraph);
178
break;
179
}
180
181
for (const item of noDependents) {
182
sorted.push(item);
183
dependencyGraph.delete(item.id);
184
}
185
186
for (const deps of dependencyGraph.values()) {
187
for (const item of noDependents) {
188
deps?.delete(item.id);
189
}
190
}
191
}
192
193
logger.trace("sortDependencies end", sorted);
194
return [sorted, backupDependencyGraph];
195
}
196