This repository has been archived by the owner on May 5, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
deps.dylan
298 lines (281 loc) · 13 KB
/
deps.dylan
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
Module: %pacman
Synopsis: Dependency specification and resolution
define class <dep-error> (<package-error>) end;
// TODO(cgay): all the errors explicitly convert there args to strings because, for
// reasons I never fully understood, the error printing code doesn't call the
// print-object methods to print the args.
define function dep-error
(format-string, #rest args)
signal(if (instance?(format-string, <condition>))
format-string
else
make(<dep-error>,
format-string: format-string,
format-arguments: args)
end);
end function;
define class <dep-conflict> (<dep-error>) end;
// A dependency on a specific version of a package.
define class <dep> (<object>)
constant slot package-name :: <string>, required-init-keyword: package-name:;
constant slot dep-version :: <version>, required-init-keyword: version:;
end class;
define method initialize
(dep :: <dep>, #key) => ()
next-method();
validate-package-name(dep.package-name);
end method;
define method print-object
(dep :: <dep>, stream :: <stream>) => ()
if (*print-escape?*)
printing-object (dep, stream)
write(stream, dep-to-string(dep));
end;
else
write(stream, dep-to-string(dep))
end;
end method;
define function dep-to-string
(dep :: <dep>) => (_ :: <string>)
if (dep.dep-version = $latest)
dep.package-name
else
concat(dep.package-name, "@", version-to-string(dep.dep-version))
end
end function;
// We want to avoid checking a lot of duplicate dependencies and this enables
// preventing those duplicates with add-new!(..., dep, test: \=)
define method \=
(d1 :: <dep>, d2 :: <dep>) => (_ :: <bool>)
istring=(d1.package-name, d2.package-name) & d1.dep-version = d2.dep-version
end method;
// Parse a dependency spec. Examples:
// foo -- same as "foo@latest", i.e., latest numbered release
// foo@1.0 -- same as "foo@1.0.0"
// foo@1.2.3
// foo@feature -- HEAD of the 'feature' branch
//
// TODO(cgay): I don't think "foo" or "foo@latest" should be supported at this level. It
// should probably be handled at the dylan-tool or workspaces level, and be explicitly
// resolved to the latest <semantic-version> immediately.
define function string-to-dep
(input :: <string>) => (d :: <dep>)
let (name, version) = apply(values, map(strip, split(strip(input), "@", count: 2)));
make(<dep>,
package-name: name,
version: if (version) string-to-version(version) else $latest end)
end function;
// A convenience interface to resolve-deps.
define function resolve-release-deps
(cat :: <catalog>, release :: <release>,
#key dev? :: <bool>, actives :: false-or(<istring-table>), cache)
=> (deps :: <seq>)
let dev-deps = if (dev?)
release.release-dev-dependencies
else
as(<dep-vector>, #())
end;
// Add the release as a dependency of itself so that it will be included in circular
// dependency checking. Note that this is mostly for releases in the catalog; workspace
// packages are normally included in `actives` and won't be checked.
let reldep = make(<dep>,
package-name: release.package-name,
version: release.release-version);
let deps = as(<dep-vector>, add!(release.release-deps, reldep));
resolve-deps(cat, deps, dev-deps, actives, cache: cache)
end function;
// Resolve `release` to a set of releases it depends on, using `cat` as the world of
// potential releases. `release` itself is not included in the result. `active` maps
// package names to releases that are "active" in the current workspace and therefore
// should be treated specially. If any package encountered during resolution has a
// dependency on one of the active packages, that dependency is ignored since the active
// package will be used during the build process anyway. The returned deps do not include
// the active releases.
//
// Signal <dep-error> if dependencies can't be resolved due to circularities,
// conflicting constraints, or if they are simply missing from the catalog.
//
// The algorithm used here is based on my understanding of
// https://research.swtch.com/vgo-principles, which can be very roughly summarized as
// "providing repeatable builds by preferring the lowest possible specified version of
// any package".
//
// We are given a release that needs to be built. This is the root of a graph. Its deps
// form the second layer of a graph. The releases that match those deps form the third
// level of the graph, and the deps of those releases form the fourth, etc. So we have a
// graph in which the layers alternate between potential releases and their deps. This
// tree gets big fast. The result for any given release is memoized.
//
// Each dep specifies only its minimum required version, e.g., P 1.2.3. These are
// semantic versions so if two dependencies on P specify different major versions it is
// an error.
//
// Releases with no deps terminate the recursion and as results percolate up the stack
// they are combined with other results to keep only the maximum minimum version for each
// package.
//
// (Note: We could support per-library dependencies (i.e., build deps). Test dependencies
// should not be included in the graph for the main library. For example, to build pacman
// testworks should not be a dependency. It's also possible to want to require D 1.0 for
// one library in a package and D 2.0 for a different library in the same package. I'm
// ignoring these issues for now to avoid unnecessary complexity. For now deps only work
// at the package level.)
define function resolve-deps
(cat :: <catalog>, deps :: <dep-vector>, dev-deps :: <dep-vector>,
actives :: false-or(<istring-table>), #key cache)
=> (releases :: <seq>)
let cache = cache | make(<table>);
local
// Use `dylan --debug --verbose update` to see this trace output. For tests I'm
// afraid one has to change log-trace to log-info.
method trace (depth, return-value, fmt, #rest format-args)
let indent = make(<string>, size: depth * 2, fill: ' ');
apply(log-trace, concat(indent, fmt), format-args);
return-value
end,
// Resolve the deps for a single release into a set of specific releases
// required in order to build it. The recursion terminates when a release
// has no deps or if a cached result exists.
method resolve-release (rel, seen, depth) => (releases :: <list>)
trace(depth, #f, "resolve-release(rel: %=, seen: %=)", rel, seen);
let memo = element(cache, rel, default: #f); // use memoized result
if (memo)
trace(depth, memo, "<= memoized result %s", memo)
else
let pname = rel.package-name;
if (member?(pname, seen, test: \=))
dep-error("circular dependency: %=", pair(pname, seen))
end;
// TODO: shouldn't need as(<list>) here
let resolved
= %resolve-deps(as(<list>, rel.release-deps), pair(pname, seen), depth + 1);
cache[rel] := resolved;
trace(depth, resolved, "caching %s => %s", rel, resolved);
end
end method,
// Iterate over a single release's deps resolving them to lists of specific minimum
// releases, then combine those releases into one list by taking the maximum minimum
// release version needed for each package. When looking up deps, always prefer the
// active packages, so that it isn't necessary for active packages to exist in the
// catalog.
method %resolve-deps (deps, seen, depth) => (releases :: <list>)
trace(depth, #f, "%%resolve-deps(deps: %s, seen: %=)", as(<list>, deps), seen);
let maxima = make(<istring-table>);
for (dep in deps)
let pname = dep.package-name;
let rel = (actives & element(actives, pname, default: #f))
| begin
let pkg = find-package(cat, pname)
| dep-error("package not found for %=", dep-to-string(dep));
find-release(pkg, dep.dep-version, exact?: #f)
| dep-error("no release found matching dependency %=",
dep-to-string(dep))
end;
for (release in pair(rel, resolve-release(rel, seen, depth + 1)))
let pkg-name = release.package-name;
if (~(actives & element(actives, pkg-name, default: #f)))
let current-max = element(maxima, pkg-name, default: #f);
maxima[pkg-name] := max-release(current-max, release, seen: pair(pkg-name, seen));
end;
end;
end;
let releases = as(<list>, value-sequence(maxima));
trace(depth, releases, "<= %s", releases);
end method;
block ()
let releases = %resolve-deps(deps, #(), 0);
if (~empty?(dev-deps))
// TODO: this doesn't need to be a separate call to %resolve-deps unless we want to
// give a more contextualized error message, which isn't currently done.
let dev-releases = %resolve-deps(dev-deps, #(), 0);
// Some refactoring may be needed, to make %resolve-deps return a list of deps
// instead of releases, but this'll do for now.
let all-deps = as(<dep-vector>,
map(method (r)
make(<dep>,
package-name: r.package-name,
version: r.release-version)
end,
concat(releases, dev-releases)));
// Re-resolve the combined list to ensure maximin'd versions of shared packages
// and no major version conflicts.
let combined = %resolve-deps(all-deps, #(), 0);
releases := reconcile-prod-dev-deps(combined, releases)
end;
releases
exception (ex :: <package-missing-error>)
dep-error(make(<dep-error>,
format-string: "package %= not in catalog",
format-arguments: list(ex.package-name)));
end
end function;
// Adjust result to prefer non-dev dependencies and ensure that what is tested is what is
// run in production. Ex: for prod-dep->a@1.0->b@1.0 and dev-dep->c@1.0->b@1.1 the b@1.0
// release should be preferred even though it's a lower minor version, because it's what
// will be used in production.
define function reconcile-prod-dev-deps
(combined-releases, main-releases) => (releases)
let releases = #();
for (combined in combined-releases)
let main = find-element(main-releases,
method (r)
r.package-name = combined.package-name
end);
if (~main | combined == main)
releases := pair(combined, releases);
else
// TODO: should have a flag to use the dev dependency if user believes it's safe.
log-warning("Using %s instead of higher dev dependency %s to ensure consistent"
" dev and non-dev builds.",
main, combined);
releases := pair(main, releases);
end
end;
releases
end function;
// Find the newest of two releases. They could have semantic versions or branch versions,
// which aren't really comparable. We prefer the branch version arbitrarily. Differing
// branch versions or differing major version number for semantic versions causes a
// `<dep-conflict>` error. `seen` is for better error messages only, and should be a
// sequence of package names seen so far during dependency resolution.
define method max-release
(current == #f, release :: <release>, #key seen = #[]) => (r :: <release>)
release
end method;
define method max-release
(current :: <release>, release :: <release>, #key seen = #[]) => (r :: <release>)
let relver = release.release-version;
let curver = current.release-version;
if (instance?(relver, <branch-version>))
if (instance?(curver, <branch-version>))
if (relver ~= curver)
dep-error(make(<dep-conflict>,
format-string: "dependencies on two different branches of"
" the same package: %= and %= (path: %s)",
format-arguments: list(release-to-string(current),
release-to-string(release),
join(reverse(seen), " => "))));
end;
current
else
release // prefer branch version
end
else
if (instance?(curver, <branch-version>))
current // prefer branch version
else
// Both releases are SemVer.
let release-major = release.release-version.version-major;
let current-major = current.release-version.version-major;
if (release-major ~= current-major)
dep-error(make(<dep-conflict>,
format-string: "dependencies on conflicting major versions"
" of the same package: %= and %= (path: %s)",
format-arguments: list(release-to-string(current),
release-to-string(release),
join(reverse(seen), " => "))));
end;
max(current, release)
end
end
end method;