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 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
88export 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}