-
Notifications
You must be signed in to change notification settings - Fork 11
/
hydrate.ts
162 lines (138 loc) · 5.31 KB
/
hydrate.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
import { PackageRequirement, Package } from "../types.ts"
import * as semver from "../utils/semver.ts"
import usePantry from "../hooks/usePantry.ts"
import { is_what } from "../deps.ts"
const { isArray } = is_what
//TODO linktime cyclic dependencies cannot be allowed
//NOTE however if they aren’t link time it's presumably ok in some scenarios
// eg a tool that lists a directory may depend on a tool that identifies the
// mime types of files which could depend on the listing tool
//FIXME actually we are not refining the constraints currently
//TODO we are not actually restricting subsequent asks, eg. deno^1 but then deno^1.2
interface ReturnValue {
/// full list topologically sorted (ie dry + wet)
pkgs: PackageRequirement[]
/// your input, but version constraints refined based on the whole graph
/// eg. you hydrate the graph for a and b, but b depends on a tighter range of a than you input
dry: PackageRequirement[]
/// packages that were not supplied to input or that require bootstrap
wet: PackageRequirement[]
/// the graph cycles at these packages
/// this is only a problem if you need to build one of these,
// in which case TADA! here's the list!
bootstrap_required: Set<string>
}
const get = (x: PackageRequirement) => usePantry().project(x).runtime.deps()
/// sorts a list of packages topologically based on their
/// dependencies. Throws if there is a cycle in the input.
/// ignores changes in dependencies based on versions
export default async function hydrate(
input: (PackageRequirement | Package)[] | (PackageRequirement | Package),
get_deps: (pkg: PackageRequirement, dry: boolean) => Promise<PackageRequirement[]> = get,
): Promise<ReturnValue>
{
if (!isArray(input)) input = [input]
const dry = condense(input.map(spec => {
if ("version" in spec) {
return {project: spec.project, constraint: new semver.Range(`=${spec.version}`)}
} else {
return spec
}
}))
const graph: Record<string, Node> = {}
const bootstrap = new Set<string>()
const initial_set = new Set(dry.map(x => x.project))
const stack: Node[] = []
const additional_unicodes: semver.Range[] = []
// Starting the DFS loop for each package in the dry list
for (const pkg of dry) {
let new_node = graph[pkg.project]
if (new_node) {
// Intersect constraints for existing nodes
new_node.pkg.constraint = semver.intersect(new_node.pkg.constraint, pkg.constraint)
} else {
new_node = new Node(pkg)
graph[pkg.project] = new_node
stack.push(new_node)
}
while (stack.length > 0) {
const current_node = stack.pop()!
const children = current_node.children
for (const dep of await get_deps(current_node.pkg, initial_set.has(current_node.project))) {
if (children.has(dep.project)) {
if (!bootstrap.has(dep.project)) {
console.warn(`pkgx: cyclic dep: ${dep.project}: ${current_node.project}`)
bootstrap.add(dep.project)
}
} else {
let child_node = graph[dep.project]
if (child_node) {
try {
// Intersect constraints
child_node.pkg.constraint = semver.intersect(child_node.pkg.constraint, dep.constraint)
} catch (e) {
if (dep.project == 'unicode.org') {
// we handle unicode.org for now to allow situations like:
// https://github.com/pkgxdev/pantry/issues/4104
// https://github.com/pkgxdev/pkgx/issues/899
additional_unicodes.push(dep.constraint)
} else {
throw e
}
}
} else {
child_node = new Node(dep, current_node)
graph[dep.project] = child_node
stack.push(child_node)
}
current_node.children.add(dep.project)
}
}
}
}
// Sorting and constructing the return value
const pkgs = Object.values(graph)
.sort((a, b) => b.count() - a.count())
.map(({pkg}) => pkg)
// see above explanation
pkgs.push(...additional_unicodes.map(constraint => ({ project: "unicode.org", constraint })))
//TODO strictly we need to record precisely the bootstrap version constraint
const bootstrap_required = new Set(pkgs.compact(({project}) => bootstrap.has(project) && project))
return {
pkgs,
dry: pkgs.filter(({project}) => initial_set.has(project)),
wet: pkgs.filter(({project}) => !initial_set.has(project) || bootstrap_required.has(project)),
bootstrap_required
}
}
function condense(pkgs: PackageRequirement[]) {
const out: PackageRequirement[] = []
for (const pkg of pkgs) {
const found = out.find(x => x.project === pkg.project)
if (found) {
found.constraint = semver.intersect(found.constraint, pkg.constraint)
} else {
out.push(pkg)
}
}
return out
}
/////////////////////////////////////////////////////////////////////////// lib
class Node {
parent: Node | undefined
readonly pkg: PackageRequirement
readonly project: string
children: Set<string> = new Set()
constructor(pkg: PackageRequirement, parent?: Node) {
this.parent = parent
this.pkg = pkg
this.project = pkg.project
}
count(): number {
let n = 0
// deno-lint-ignore no-this-alias
let node: Node | undefined = this
while ((node = node?.parent)) n++
return n
}
}