/** * Version selection (docs/design/package-manager.md, "Version * selection"): which versions of each package a workspace installs, given * the ranges its packages and their dependencies accept. * * Selection installs as few versions of each package as the ranges asking * for it allow, and a second version only when no one version is in all * of them. Each range then uses the highest selected version in it. This * is the design's first phase: one package at a time, repeated over every * package until nothing changes. The second phase, a search for a better * answer, is #1089. * * The result is a `Resolution`: for each selected version, its release and * source CIDs and the version each of its own dependency names stands * for. */ import {HashMap, HashSet, OrderedHashMap} from 'zena:collections'; import {Cid} from 'atproto/cid'; import {Release, SOURCE} from './records.zena'; import {Resolution, ResolutionError, ResolvedPackage, packageKey} from './resolution.zena'; import {Range, Version} from 'zena-lang:semver'; /** A published package a package depends on, and the versions it accepts. */ export final class Requirement { did: String; range: Range; new(did: String, range: Range) : did = did, range = range; } /** A release record, and its CID, fetched with its proof. */ export final class CheckedRelease { release: Release; cid: Cid; new(release: Release, cid: Cid) : release = release, cid = cid; } /** The versions a package's repository lists, and which of them are retracted. */ export final class Versions { releases: GrowableArray; /** The retracted versions, as text. */ retracted: HashSet; new(releases: GrowableArray, retracted: HashSet) : releases = releases, retracted = retracted; /** * The highest version that is not retracted, on the compatible line * `line` when it is given (`Version.compatibleLine`: `1`, or `0.2` before * 1.0). Pre-releases count only with `prereleases`. */ latest(line: String | null = null, prereleases: boolean = false): Version | null { var best: Version | null = null; for (let version in this.releases) { if (this.retracted.has(version.toString())) { continue; } if (line != null && version.compatibleLine() != line) { continue; } if (version.isPrerelease && !prereleases) { continue; } let current = best; if (current == null || version.compareTo(current) > 0) { best = version; } } return best; } /** * The version to add a package at when none is named: the highest * release that is neither retracted nor a pre-release, or, for a package * with no such release, its highest pre-release that is not retracted. * Null when every release is retracted, or there is none. */ preferred(): Version | null { return this.latest() ?? this.latest(null, true); } has(version: Version): boolean { for (let listed in this.releases) { if (listed.compareTo(version) == 0) { return true; } } return false; } } /** * Where selection reads what it chooses from: the versions a package * lists, and a release record, checked against the account's key. */ export interface PackageSource { versions(did: String): Future; /** `did`'s release `version`. Throws when there is no such release. */ release(did: String, version: Version): Future; } /** How many times the first phase goes over every package before it stops. */ let MAX_PASSES = 32; /** * Selects versions of every package `requirements` lead to, from what * `source` lists. A retracted version is chosen only when `preferred`, the * keys of the versions the lockfile pins, has it; among versions equally * good for the number installed, a pinned one is chosen first. Throws * `ResolutionError` for a range no usable version is in, and for a * selected release with no source artifact, and whatever `source` throws. */ export async function resolve(requirements: Array, source: PackageSource, preferred: HashSet = new HashSet()): Future { let available = new HashMap>(); let usable = async (did: String): Future> => { if (let (true, known) = available.get(did)) { return known; } let listed = await source.versions(did); let versions = new GrowableArray(); for (let version in listed.releases) { if (!listed.retracted.has(version.toString()) || preferred.has(packageKey(did, version))) { versions.push(version); } } let sorted = sortVersions(versions); available[did] = sorted; return sorted; }; let releases = new HashMap(); let read = async (did: String, version: Version): Future => { let key = packageKey(did, version); if (let (true, checked) = releases.get(key)) { return checked; } let checked = await source.release(did, version); releases[key] = checked; return checked; }; var selected = new HashMap>(); var pass = 0; while (pass < MAX_PASSES) { pass += 1; // Every range asking for each package now: the workspace's, and those // of the releases selected so far. let requests = new HashMap>(); for (let requirement in requirements) { request(requests, requirement.did, requirement.range); } for (let did in sortedKeys(selected)) { for (let version in selected[did]) { for (let dependency in (await read(did, version)).release.dependencies) { request(requests, dependency.did, dependency.range); } } } let next = new HashMap>(); for (let did in sortedKeys(requests)) { next[did] = choose(did, await usable(did), requests[did], preferred); } let settled = sameSelection(selected, next); selected = next; if (settled) { break; } } let packages = new OrderedHashMap(); for (let did in sortedKeys(selected)) { for (let version in selected[did]) { let key = packageKey(did, version); let checked = await read(did, version); let artifact = checked.release.artifact(SOURCE); if (artifact == null) { throw new ResolutionError(`${key}: release ${version.toString()} has no source artifact`); } let dependencies = new OrderedHashMap(); for (let dependency in checked.release.dependencies) { let used = highestIn(selected[dependency.did], dependency.range); if (used == null) { throw new ResolutionError(`${key}: no selected version of '${dependency.name}' is in '${dependency.range.text}'`); } dependencies[dependency.name] = packageKey(dependency.did, used); } packages[key] = new ResolvedPackage(key, did, version, checked.cid, artifact.cid, dependencies); } } return new Resolution(packages); } function request(requests: HashMap>, did: String, range: Range): void { if (let (true, ranges) = requests.get(did)) { ranges.push(range); } else { let ranges = new GrowableArray(); ranges.push(range); requests[did] = ranges; } } /** * The fewest of `versions` (ascending) that every range in `ranges` has * one of, for the package `did`. Repeatedly: of the ranges no chosen * version is in yet, take the one whose highest version is lowest; every * version of it that is in each of those ranges its highest version is in * is as good for the count as that highest one; of those, choose a * version `preferred` pins, then the one in the most ranges, then the * highest. For ranges that are intervals this is the fewest versions * there can be (docs/design/package-manager.md, "Finding the selection"). */ function choose(did: String, versions: GrowableArray, ranges: GrowableArray, preferred: HashSet): GrowableArray { // inRange[r][v]: whether version v is in range r. let inRange = new GrowableArray>(); let tops = new GrowableArray(); for (let range in ranges) { let row = new FixedArray(versions.length, false); var top = -1; for (var v = 0; v < versions.length; v += 1) { if (range.includes(versions[v])) { row[v] = true; top = v; } } if (top < 0) { throw new ResolutionError(`no usable release of ${did} is in '${range.text}'`); } inRange.push(row); tops.push(top); } let met = new FixedArray(ranges.length, false); let chosen = new HashSet(); while (true) { // The unmet range whose highest version is lowest. var first = -1; for (var r = 0; r < ranges.length; r += 1) { if (!met[r] && (first < 0 || tops[r] < tops[first])) { first = r; } } if (first < 0) { break; } let top = tops[first]; var best = -1; var bestPinned = false; var bestCount = -1; for (var v = 0; v <= top; v += 1) { if (!inRange[first][v] || !inEveryRangeOf(inRange, met, top, v)) { continue; } let pinned = preferred.has(packageKey(did, versions[v])); var count = 0; for (var r = 0; r < ranges.length; r += 1) { if (inRange[r][v]) { count += 1; } } // Later versions are higher, so a tie goes to the later one. if (best < 0 || (pinned && !bestPinned) || (pinned == bestPinned && count >= bestCount)) { best = v; bestPinned = pinned; bestCount = count; } } chosen.add(best); for (var r = 0; r < ranges.length; r += 1) { if (inRange[r][best]) { met[r] = true; } } } let out = new GrowableArray(); for (var v = 0; v < versions.length; v += 1) { if (chosen.has(v)) { out.push(versions[v]); } } return out; } /** Whether version `v` is in every unmet range that version `top` is in. */ function inEveryRangeOf(inRange: GrowableArray>, met: FixedArray, top: i32, v: i32): boolean { for (var r = 0; r < inRange.length; r += 1) { if (!met[r] && inRange[r][top] && !inRange[r][v]) { return false; } } return true; } /** The highest of `versions` in `range`, or null when none is. */ function highestIn(versions: GrowableArray, range: Range): Version | null { var found: Version | null = null; for (let version in versions) { if (range.includes(version)) { found = version; } } return found; } function sameSelection(a: HashMap>, b: HashMap>): boolean { if (a.size != b.size) { return false; } for (let did in a.keys()) { if (!b.has(did)) { return false; } let x = a[did]; let y = b[did]; if (x.length != y.length) { return false; } for (var i = 0; i < x.length; i += 1) { if (x[i].compareTo(y[i]) != 0) { return false; } } } return true; } // TODO(#450): use the standard library's sort once it has one. function sortVersions(versions: GrowableArray): GrowableArray { let out = new GrowableArray(); for (let version in versions) { out.push(version); var j = out.length - 1; while (j > 0 && out[j - 1].compareTo(version) > 0) { out[j] = out[j - 1]; j -= 1; } out[j] = version; } return out; } // TODO(#450): use the standard library's sort once it has one. function sortedKeys(map: HashMap): FixedArray { let keys = new FixedArray(map.size, ''); var n = 0; for (let key in map.keys()) { var j = n; while (j > 0 && keys[j - 1].compareTo(key) > 0) { keys[j] = keys[j - 1]; j -= 1; } keys[j] = key; n += 1; } return keys; }