this repo has no description
notnite.com
1import Logger from "./logger";
2
3export type Dependency<T, D> = {
4 id: T;
5 data: D;
6};
7
8const logger = new Logger("core/util/dependency");
9
10export default function calculateDependencies<T, D>(
11 origItems: Dependency<T, D>[],
12 fetchDep: (id: T) => D | null,
13 getDeps: (item: Dependency<T, D>) => T[],
14 getIncompatible?: (item: Dependency<T, D>) => T[]
15): [Dependency<T, D>[], Map<T, Set<T> | null>] {
16 logger.trace("sortDependencies begin", origItems);
17 let items = [...origItems];
18
19 if (getIncompatible != null) {
20 for (const item of items) {
21 const incompatibleItems = getIncompatible(item);
22 for (const incompatibleItem of incompatibleItems) {
23 if (items.find((x) => x.id === incompatibleItem) != null) {
24 logger.warn(
25 `Incompatible dependency detected: "${item.id}" and "${incompatibleItem}" - removing "${incompatibleItem}"`
26 );
27
28 items = items.filter((x) => x.id !== incompatibleItem);
29 }
30 }
31 }
32 }
33
34 const dependencyGraph = new Map<T, Set<T> | null>();
35 for (const item of items) {
36 const fullDeps: Set<T> = new Set();
37 let failed = false;
38
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 logger.trace("Sorting stage", items);
87 const sorted: Dependency<T, D>[] = [];
88
89 // Clone the dependency graph to return it later
90 const backupDependencyGraph = new Map(dependencyGraph);
91 for (const item of items) {
92 dependencyGraph.set(item.id, new Set(dependencyGraph.get(item.id)));
93 }
94
95 while (
96 Array.from(dependencyGraph.values()).filter((x) => x != null).length > 0
97 ) {
98 const noDependents = items.filter(
99 (e) => dependencyGraph.get(e.id)?.size === 0
100 );
101
102 if (noDependents.length === 0) {
103 logger.warn("Stuck dependency graph detected", dependencyGraph);
104 break;
105 }
106
107 for (const item of noDependents) {
108 sorted.push(item);
109 dependencyGraph.delete(item.id);
110 }
111
112 for (const deps of dependencyGraph.values()) {
113 for (const item of noDependents) {
114 deps?.delete(item.id);
115 }
116 }
117 }
118
119 logger.trace("sortDependencies end", sorted);
120 return [sorted, backupDependencyGraph];
121}