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 // eslint-disable-next-line no-inner-declarations
40 function resolveDeps(id: T, root: boolean) {
41 if (id === item.id && !root) {
42 logger.warn(`Circular dependency detected: "${item.id}"`);
43 failed = true;
44 return;
45 }
46
47 const obj = fetchDep(id);
48 if (obj == null) {
49 logger.warn(`Missing dependency detected`, id);
50 failed = true;
51 return;
52 }
53
54 if (!root) fullDeps.add(id);
55
56 for (const dep of getDeps({ id, data: obj })) {
57 resolveDeps(dep, false);
58 }
59 }
60
61 resolveDeps(item.id, true);
62 dependencyGraph.set(item.id, failed ? null : fullDeps);
63 }
64
65 logger.trace("Failed stage", items);
66 function isFailed(id: T) {
67 const deps = dependencyGraph.get(id);
68 if (deps === null) return true;
69
70 // For some reason this can be undefined. If it is, it's not null, so we
71 // didn't explicitly fail. FIXME too tired to investigate
72 if (deps === undefined) return false;
73
74 for (const dep of deps) {
75 if (isFailed(dep)) return true;
76 }
77
78 return false;
79 }
80
81 const failed = items.filter((item) => isFailed(item.id));
82 if (failed.length > 0) {
83 logger.warn("Skipping failed items", failed);
84 items = items.filter((item) => !failed.includes(item));
85 }
86
87 logger.trace("Sorting stage", items);
88 const sorted: Dependency<T, D>[] = [];
89
90 // Clone the dependency graph to return it later
91 const backupDependencyGraph = new Map(dependencyGraph);
92 for (const item of items) {
93 dependencyGraph.set(item.id, new Set(dependencyGraph.get(item.id)));
94 }
95
96 while (
97 Array.from(dependencyGraph.values()).filter((x) => x != null).length > 0
98 ) {
99 const noDependents = items.filter(
100 (e) => dependencyGraph.get(e.id)?.size === 0
101 );
102
103 if (noDependents.length === 0) {
104 logger.warn("Stuck dependency graph detected", dependencyGraph);
105 break;
106 }
107
108 for (const item of noDependents) {
109 sorted.push(item);
110 dependencyGraph.delete(item.id);
111 }
112
113 for (const deps of dependencyGraph.values()) {
114 for (const item of noDependents) {
115 deps?.delete(item.id);
116 }
117 }
118 }
119
120 logger.trace("sortDependencies end", sorted);
121 return [sorted, backupDependencyGraph];
122}