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