resolver.zig
No OneTemporary
Actions

Size

61 KB

Referenced Files

None

Subscribers

None

resolver.zig
View Options

	const std = @import("std");
	const builtin = @import("builtin");
	const lockfile = @import("lockfile.zig");
	const intern = @import("intern.zig");
	const fetcher = @import("fetcher.zig");
	const json = @import("json.zig");
	const debug = @import("debug.zig");
	const cache = @import("cache.zig");

	pub const ResolveError = error{
	InvalidPackageJson,
	NetworkError,
	NoMatchingVersion,
	CyclicDependency,
	OutOfMemory,
	ParseError,
	IoError,
	};

	pub const Version = struct {
	major: u64,
	minor: u64,
	patch: u64,
	prerelease: ?[]const u8,
	build: ?[]const u8,

	pub fn parse(str: []const u8) !Version {
	var remaining = str;

	if (remaining.len > 0 and remaining[0] == 'v') {
	remaining = remaining[1..];
	}

	const major_end = std.mem.indexOfScalar(u8, remaining, '.') orelse return error.InvalidVersion;
	const major = try std.fmt.parseInt(u64, remaining[0..major_end], 10);
	remaining = remaining[major_end + 1 ..];

	const minor_end = std.mem.indexOfScalar(u8, remaining, '.') orelse return error.InvalidVersion;
	const minor = try std.fmt.parseInt(u64, remaining[0..minor_end], 10);
	remaining = remaining[minor_end + 1 ..];

	var patch_end = remaining.len;
	var prerelease: ?[]const u8 = null;
	var build: ?[]const u8 = null;

	if (std.mem.indexOfScalar(u8, remaining, '-')) \|dash\| {
	patch_end = dash;
	const after_patch = remaining[dash + 1 ..];
	if (std.mem.indexOfScalar(u8, after_patch, '+')) \|plus\| {
	prerelease = after_patch[0..plus];
	build = after_patch[plus + 1 ..];
	} else prerelease = after_patch;
	} else if (std.mem.indexOfScalar(u8, remaining, '+')) \|plus\| {
	patch_end = plus;
	build = remaining[plus + 1 ..];
	}

	const patch = try std.fmt.parseInt(u64, remaining[0..patch_end], 10);

	return .{
	.major = major,
	.minor = minor,
	.patch = patch,
	.prerelease = prerelease,
	.build = build,
	};
	}

	pub fn order(a: Version, b: Version) std.math.Order {
	if (a.major != b.major) return std.math.order(a.major, b.major);
	if (a.minor != b.minor) return std.math.order(a.minor, b.minor);
	if (a.patch != b.patch) return std.math.order(a.patch, b.patch);

	if (a.prerelease == null and b.prerelease != null) return .gt;
	if (a.prerelease != null and b.prerelease == null) return .lt;
	if (a.prerelease == null and b.prerelease == null) return .eq;

	return orderPrerelease(a.prerelease.?, b.prerelease.?);
	}

	fn orderPrerelease(a: []const u8, b: []const u8) std.math.Order {
	var a_rest: []const u8 = a;
	var b_rest: []const u8 = b;

	while (true) {
	const a_end = std.mem.indexOfScalar(u8, a_rest, '.') orelse a_rest.len;
	const b_end = std.mem.indexOfScalar(u8, b_rest, '.') orelse b_rest.len;

	const a_id = a_rest[0..a_end];
	const b_id = b_rest[0..b_end];

	const cmp = compareIdentifier(a_id, b_id);
	if (cmp != .eq) return cmp;

	const a_done = a_end >= a_rest.len;
	const b_done = b_end >= b_rest.len;
	if (a_done and b_done) return .eq;
	if (a_done) return .lt;
	if (b_done) return .gt;

	a_rest = a_rest[a_end + 1 ..];
	b_rest = b_rest[b_end + 1 ..];
	}
	}

	fn compareIdentifier(a: []const u8, b: []const u8) std.math.Order {
	const a_num = parseNumeric(a);
	const b_num = parseNumeric(b);

	if (a_num != null and b_num != null) {
	return std.math.order(a_num.?, b_num.?);
	}

	if (a_num != null) return .lt;
	if (b_num != null) return .gt;

	return std.mem.order(u8, a, b);
	}

	fn parseNumeric(s: []const u8) ?u64 {
	if (s.len == 0) return null;
	var val: u64 = 0;
	for (s) \|c\| {
	if (c < '0' or c > '9') return null;
	val = val * 10 + (c - '0');
	}
	return val;
	}

	pub fn format(self: Version, allocator: std.mem.Allocator) ![]u8 {
	if (self.prerelease) \|pre\| {
	return std.fmt.allocPrint(allocator, "{d}.{d}.{d}-{s}", .{
	self.major, self.minor, self.patch, pre,
	});
	}
	return std.fmt.allocPrint(allocator, "{d}.{d}.{d}", .{
	self.major, self.minor, self.patch,
	});
	}
	};

	pub const Constraint = struct {
	kind: Kind,
	version: Version,

	pub const Kind = enum {
	exact, // 1.2.3
	caret, // ^1.2.3 (>=1.2.3 <2.0.0)
	tilde, // ~1.2.3 (>=1.2.3 <1.3.0)
	gte, // >=1.2.3
	gt, // >1.2.3
	lte, // <=1.2.3
	lt, // <1.2.3
	any, // *
	};

	pub fn parse(str: []const u8) !Constraint {
	if (str.len == 0 or std.mem.eql(u8, str, "*") or std.mem.eql(u8, str, "latest")) {
	return .{ .kind = .any, .version = .{ .major = 0, .minor = 0, .patch = 0, .prerelease = null, .build = null } };
	}

	var remaining = str;
	var kind: Kind = .exact;

	if (std.mem.lastIndexOf(u8, remaining, "\|\|")) \|or_idx\| {
	remaining = std.mem.trim(u8, remaining[or_idx + 2 ..], " ");
	}

	if (std.mem.indexOf(u8, remaining, " ")) \|space\| {
	remaining = remaining[0..space];
	}

	if (std.mem.startsWith(u8, remaining, "^")) {
	kind = .caret;
	remaining = remaining[1..];
	} else if (std.mem.startsWith(u8, remaining, "~")) {
	kind = .tilde;
	remaining = remaining[1..];
	} else if (std.mem.startsWith(u8, remaining, ">=")) {
	kind = .gte;
	remaining = remaining[2..];
	} else if (std.mem.startsWith(u8, remaining, ">")) {
	kind = .gt;
	remaining = remaining[1..];
	} else if (std.mem.startsWith(u8, remaining, "<=")) {
	kind = .lte;
	remaining = remaining[2..];
	} else if (std.mem.startsWith(u8, remaining, "<")) {
	kind = .lt;
	remaining = remaining[1..];
	} else if (std.mem.startsWith(u8, remaining, "=")) {
	remaining = remaining[1..];
	}

	const dot_count = std.mem.count(u8, remaining, ".");
	if (dot_count == 0) {
	const major = std.fmt.parseInt(u64, remaining, 10) catch return .{
	.kind = .any,
	.version = .{ .major = 0, .minor = 0, .patch = 0, .prerelease = null, .build = null },
	};
	return .{
	.kind = if (kind == .exact) .caret else kind,
	.version = .{ .major = major, .minor = 0, .patch = 0, .prerelease = null, .build = null },
	};
	} else if (dot_count == 1) {
	var parts = std.mem.splitScalar(u8, remaining, '.');
	const major = std.fmt.parseInt(u64, parts.next().?, 10) catch 0;
	const minor = std.fmt.parseInt(u64, parts.next().?, 10) catch 0;
	return .{
	.kind = if (kind == .exact) .tilde else kind,
	.version = .{ .major = major, .minor = minor, .patch = 0, .prerelease = null, .build = null },
	};
	}

	const version = try Version.parse(remaining);
	return .{ .kind = kind, .version = version };
	}

	pub fn satisfies(self: Constraint, v: Version) bool {
	switch (self.kind) {
	.any => return true,
	.exact => {
	if (v.major != self.version.major or v.minor != self.version.minor or v.patch != self.version.patch) return false;
	if (self.version.prerelease == null and v.prerelease == null) return true;
	if (self.version.prerelease == null or v.prerelease == null) return false;
	return std.mem.eql(u8, self.version.prerelease.?, v.prerelease.?);
	},
	.caret => {
	// ^1.2.3 means >=1.2.3 <2.0.0 (for major > 0)
	// ^0.2.3 means >=0.2.3 <0.3.0 (for major = 0)
	// ^0.0.3 means >=0.0.3 <0.0.4 (for major = 0, minor = 0)
	if (v.order(self.version) == .lt) return false;
	if (self.version.major > 0) {
	return v.major == self.version.major;
	} else if (self.version.minor > 0) {
	return v.major == 0 and v.minor == self.version.minor;
	} else {
	return v.major == 0 and v.minor == 0 and v.patch == self.version.patch;
	}
	},
	.tilde => {
	// ~1.2.3 means >=1.2.3 <1.3.0
	if (v.order(self.version) == .lt) return false;
	return v.major == self.version.major and v.minor == self.version.minor;
	},
	.gte => return v.order(self.version) != .lt,
	.gt => return v.order(self.version) == .gt,
	.lte => return v.order(self.version) != .gt,
	.lt => return v.order(self.version) == .lt,
	}
	}
	};

	pub const VersionInfo = struct {
	version: Version,
	version_str: []const u8,
	integrity: [64]u8,
	tarball_url: []const u8,
	dependencies: std.StringHashMap([]const u8),
	optional_dependencies: std.StringHashMap([]const u8),
	peer_dependencies: std.StringHashMap([]const u8),
	peer_dependencies_meta: std.StringHashMap(bool),
	os: ?[]const u8, cpu: ?[]const u8, libc: ?[]const u8,
	bin: std.StringHashMap([]const u8),
	allocator: std.mem.Allocator,

	pub fn deinit(self: *VersionInfo) void {
	self.allocator.free(self.version_str);
	self.allocator.free(self.tarball_url);
	if (self.version.prerelease) \|pre\| self.allocator.free(pre);
	if (self.version.build) \|bld\| self.allocator.free(bld);
	var iter = self.dependencies.iterator();
	while (iter.next()) \|entry\| {
	self.allocator.free(entry.key_ptr.*);
	self.allocator.free(entry.value_ptr.*);
	}
	self.dependencies.deinit();
	var opt_iter = self.optional_dependencies.iterator();
	while (opt_iter.next()) \|entry\| {
	self.allocator.free(entry.key_ptr.*);
	self.allocator.free(entry.value_ptr.*);
	}
	self.optional_dependencies.deinit();
	var peer_iter = self.peer_dependencies.iterator();
	while (peer_iter.next()) \|entry\| {
	self.allocator.free(entry.key_ptr.*);
	self.allocator.free(entry.value_ptr.*);
	}
	self.peer_dependencies.deinit();
	var peer_meta_iter = self.peer_dependencies_meta.iterator();
	while (peer_meta_iter.next()) \|entry\| {
	self.allocator.free(entry.key_ptr.*);
	}
	self.peer_dependencies_meta.deinit();
	if (self.os) \|o\| self.allocator.free(o);
	if (self.cpu) \|c\| self.allocator.free(c);
	if (self.libc) \|l\| self.allocator.free(l);
	var bin_iter = self.bin.iterator();
	while (bin_iter.next()) \|entry\| {
	self.allocator.free(entry.key_ptr.*);
	self.allocator.free(entry.value_ptr.*);
	}
	self.bin.deinit();
	}

	pub fn matchesPlatform(self: *const VersionInfo) bool {
	const current_os = comptime switch (builtin.os.tag) {
	.macos => "darwin",
	.linux => "linux",
	.windows => "win32",
	.freebsd => "freebsd",
	else => "unknown",
	};

	const current_cpu = comptime switch (builtin.cpu.arch) {
	.aarch64 => "arm64",
	.x86_64 => "x64",
	.x86 => "ia32",
	.arm => "arm",
	else => "unknown",
	};

	const current_libc: ?[]const u8 = comptime if (builtin.os.tag != .linux) null
	else if (builtin.abi == .gnu or builtin.abi == .gnueabi or builtin.abi == .gnueabihf) "glibc"
	else if (builtin.abi == .musl or builtin.abi == .musleabi or builtin.abi == .musleabihf) "musl"
	else null;

	if (self.os) \|os_filter\| if (!matchesFilter(os_filter, current_os)) return false;
	if (self.cpu) \|cpu_filter\| if (!matchesFilter(cpu_filter, current_cpu)) return false;

	if (self.libc) \|libc_filter\| {
	if (current_libc) \|libc\| if (!matchesFilter(libc_filter, libc)) return false;
	}

	return true;
	}

	fn matchesFilter(filter: []const u8, value: []const u8) bool {
	var has_positive = false;
	var matches = false;

	var iter = std.mem.splitScalar(u8, filter, ',');
	while (iter.next()) \|part\| {
	const trimmed = std.mem.trim(u8, part, " ");
	if (trimmed.len == 0) continue;

	if (trimmed[0] == '!') {
	if (std.mem.eql(u8, trimmed[1..], value)) return false;
	} else {
	has_positive = true;
	if (std.mem.eql(u8, trimmed, value)) matches = true;
	}
	}

	return if (has_positive) matches else true;
	}
	};

	fn parseDepsMap(
	allocator: std.mem.Allocator,
	maybe_obj: ?std.json.Value,
	) std.StringHashMap([]const u8) {
	var map = std.StringHashMap([]const u8).init(allocator);

	const deps_obj = maybe_obj orelse return map;
	if (deps_obj != .object) return map;

	for (deps_obj.object.keys(), deps_obj.object.values()) \|dep_name, dep_ver\| {
	if (dep_ver != .string) continue;

	const key = allocator.dupe(u8, dep_name) catch continue;
	const val = allocator.dupe(u8, dep_ver.string) catch {
	allocator.free(key);
	continue;
	};

	map.put(key, val) catch {
	allocator.free(key);
	allocator.free(val);
	};
	}

	return map;
	}

	fn parsePeerMeta(
	allocator: std.mem.Allocator,
	maybe_obj: ?std.json.Value,
	) std.StringHashMap(bool) {
	var map = std.StringHashMap(bool).init(allocator);

	const meta_obj = maybe_obj orelse return map;
	if (meta_obj != .object) return map;

	for (meta_obj.object.keys(), meta_obj.object.values()) \|dep_name, meta_val\| {
	if (meta_val != .object) continue;

	const is_optional = if (meta_val.object.get("optional")) \|opt\| (opt == .bool and opt.bool)
	else false;

	if (is_optional) {
	const key = allocator.dupe(u8, dep_name) catch continue;
	map.put(key, true) catch allocator.free(key);
	}
	}
	return map;
	}

	pub const PackageMetadata = struct {
	allocator: std.mem.Allocator,
	name: []const u8,
	versions: std.ArrayListUnmanaged(VersionInfo),
	dist_tag_latest: ?Version = null,

	pub fn init(allocator: std.mem.Allocator, name: []const u8) !PackageMetadata {
	return .{
	.allocator = allocator,
	.name = try allocator.dupe(u8, name),
	.versions = .{},
	.dist_tag_latest = null,
	};
	}

	pub fn deinit(self: *PackageMetadata) void {
	if (self.dist_tag_latest) \|*dtl\| {
	if (dtl.prerelease) \|pre\| self.allocator.free(pre);
	if (dtl.build) \|bld\| self.allocator.free(bld);
	}
	for (self.versions.items) \|*v\| {
	v.deinit();
	}
	self.versions.deinit(self.allocator);
	self.allocator.free(self.name);
	}

	pub fn parseFromJson(allocator: std.mem.Allocator, json_data: []const u8) !PackageMetadata {
	const parsed = std.json.parseFromSlice(std.json.Value, allocator, json_data, .{}) catch {
	return error.ParseError;
	}; defer parsed.deinit();

	const root = parsed.value;
	if (root != .object) return error.ParseError;

	const name = if (root.object.get("name")) \|n\| switch (n) {
	.string => \|s\| s,
	else => return error.ParseError,
	} else return error.ParseError;

	var metadata = try PackageMetadata.init(allocator, name);
	errdefer metadata.deinit();

	metadata.dist_tag_latest = blk: {
	const dt = root.object.get("dist-tags") orelse break :blk null;
	if (dt != .object) break :blk null;
	const latest_val = dt.object.get("latest") orelse break :blk null;
	if (latest_val != .string) break :blk null;
	var pl = Version.parse(latest_val.string) catch break :blk null;
	if (pl.prerelease) \|pre\| pl.prerelease = allocator.dupe(u8, pre) catch null;
	if (pl.build) \|bld\| pl.build = allocator.dupe(u8, bld) catch null;
	break :blk pl;
	};

	const versions_obj = root.object.get("versions") orelse return metadata;
	if (versions_obj != .object) return metadata;

	for (versions_obj.object.keys(), versions_obj.object.values()) \|version_str, version_data\| {
	if (version_data != .object) continue;

	var version = Version.parse(version_str) catch continue;
	if (version.prerelease) \|pre\| {
	version.prerelease = allocator.dupe(u8, pre) catch null;
	}
	if (version.build) \|bld\| {
	version.build = allocator.dupe(u8, bld) catch null;
	}
	const dist = version_data.object.get("dist") orelse continue;
	if (dist != .object) continue;

	const tarball = if (dist.object.get("tarball")) \|t\| switch (t) {
	.string => \|s\| s,
	else => continue,
	} else continue;

	var integrity: [64]u8 = std.mem.zeroes([64]u8);
	if (dist.object.get("integrity")) \|i\| {
	if (i == .string) {
	const int_str = i.string;
	if (std.mem.startsWith(u8, int_str, "sha512-")) {
	const b64 = int_str[7..];
	_ = std.base64.standard.Decoder.decode(&integrity, b64) catch {};
	}
	}
	} else if (dist.object.get("shasum")) \|s\| {
	if (s == .string) {
	const hex = s.string;
	if (hex.len >= 40) {
	for (0..20) \|i\| integrity[i] = std.fmt.parseInt(u8, hex[i * 2 ..][0..2], 16) catch 0;
	}
	}
	}

	const deps = parseDepsMap(allocator, version_data.object.get("dependencies"));
	const opt_deps = parseDepsMap(allocator, version_data.object.get("optionalDependencies"));
	const peer_deps = parseDepsMap(allocator, version_data.object.get("peerDependencies"));
	const peer_meta = parsePeerMeta(allocator, version_data.object.get("peerDependenciesMeta"));

	var os_filter: ?[]const u8 = null;
	var cpu_filter: ?[]const u8 = null;

	if (version_data.object.get("os")) \|os_arr\| {
	if (os_arr == .array) {
	var os_buf = std.ArrayListUnmanaged(u8){};
	for (os_arr.array.items, 0..) \|item, i\| {
	if (item == .string) {
	if (i > 0) os_buf.append(allocator, ',') catch {};
	os_buf.appendSlice(allocator, item.string) catch {};
	}
	}
	if (os_buf.items.len > 0) {
	os_filter = os_buf.toOwnedSlice(allocator) catch null;
	} else os_buf.deinit(allocator);
	}
	}

	if (version_data.object.get("cpu")) \|cpu_arr\| {
	if (cpu_arr == .array) {
	var cpu_buf = std.ArrayListUnmanaged(u8){};
	for (cpu_arr.array.items, 0..) \|item, i\| {
	if (item == .string) {
	if (i > 0) cpu_buf.append(allocator, ',') catch {};
	cpu_buf.appendSlice(allocator, item.string) catch {};
	}
	}
	if (cpu_buf.items.len > 0) {
	cpu_filter = cpu_buf.toOwnedSlice(allocator) catch null;
	} else cpu_buf.deinit(allocator);
	}
	}

	var libc_filter: ?[]const u8 = null;
	if (version_data.object.get("libc")) \|libc_arr\| {
	if (libc_arr == .array) {
	var libc_buf = std.ArrayListUnmanaged(u8){};
	for (libc_arr.array.items, 0..) \|item, i\| {
	if (item == .string) {
	if (i > 0) libc_buf.append(allocator, ',') catch {};
	libc_buf.appendSlice(allocator, item.string) catch {};
	}
	}
	if (libc_buf.items.len > 0) {
	libc_filter = libc_buf.toOwnedSlice(allocator) catch null;
	} else libc_buf.deinit(allocator);
	}
	}

	var bin = std.StringHashMap([]const u8).init(allocator);
	if (version_data.object.get("bin")) \|bin_val\| {
	if (bin_val == .object) {
	for (bin_val.object.keys(), bin_val.object.values()) \|key, val\| {
	if (val == .string) bin.put(allocator.dupe(u8, key)
	catch continue, allocator.dupe(u8, val.string) catch continue) catch {};
	}
	} else if (bin_val == .string) {
	const bin_name = allocator.dupe(u8, name) catch continue;
	const bin_path = allocator.dupe(u8, bin_val.string) catch {
	allocator.free(bin_name); continue;
	};
	bin.put(bin_name, bin_path) catch {
	allocator.free(bin_name);
	allocator.free(bin_path);
	};
	}
	}

	try metadata.versions.append(allocator, .{
	.version = version,
	.version_str = try allocator.dupe(u8, version_str),
	.integrity = integrity,
	.tarball_url = try allocator.dupe(u8, tarball),
	.dependencies = deps,
	.optional_dependencies = opt_deps,
	.peer_dependencies = peer_deps,
	.peer_dependencies_meta = peer_meta,
	.os = os_filter, .cpu = cpu_filter, .libc = libc_filter,
	.bin = bin, .allocator = allocator,
	});
	}

	return metadata;
	}
	};

	pub const ResolvedPackage = struct {
	name: intern.InternedString,
	version: Version,
	integrity: [64]u8,
	tarball_url: []const u8,
	dependencies: std.ArrayListUnmanaged(Dep),
	depth: u32,
	direct: bool,
	parent_path: ?[]const u8,
	has_bin: bool,
	allocator: std.mem.Allocator,

	pub const DepFlags = struct {
	peer: bool = false,
	dev: bool = false,
	optional: bool = false,
	};

	pub const Dep = struct {
	name: intern.InternedString,
	constraint: []const u8,
	flags: DepFlags = .{},
	};

	pub fn deinit(self: *ResolvedPackage) void {
	self.allocator.free(self.tarball_url);
	if (self.parent_path) \|p\| self.allocator.free(p);
	for (self.dependencies.items) \|dep\| {
	self.allocator.free(dep.constraint);
	}
	self.dependencies.deinit(self.allocator);
	}

	pub fn installPath(self: *const ResolvedPackage, allocator: std.mem.Allocator) ![]const u8 {
	if (self.parent_path) \|parent\| {
	return std.fmt.allocPrint(allocator, "{s}/node_modules/{s}", .{ parent, self.name.slice() });
	} return allocator.dupe(u8, self.name.slice());
	}
	};


	pub const OnPackageResolvedFn = *const fn (
	pkg: *const ResolvedPackage,
	user_data: ?*anyopaque
	) void;

	pub const Resolver = struct {
	allocator: std.mem.Allocator,
	cache_allocator: std.mem.Allocator,
	string_pool: *intern.StringPool,
	http: *fetcher.Fetcher,
	cache_db: ?*cache.CacheDB,
	resolved: std.StringHashMap(*ResolvedPackage),
	constraints: std.StringHashMap(std.ArrayListUnmanaged(Constraint)),
	in_progress: std.StringHashMap(void),
	registry_url: []const u8,
	metadata_cache: *std.StringHashMap(PackageMetadata),
	on_package_resolved: ?OnPackageResolvedFn,
	on_package_resolved_data: ?*anyopaque,

	pub fn init(
	allocator: std.mem.Allocator,
	cache_allocator: std.mem.Allocator,
	string_pool: *intern.StringPool,
	http: *fetcher.Fetcher,
	cache_db: ?*cache.CacheDB,
	registry_url: []const u8,
	metadata_cache: *std.StringHashMap(PackageMetadata),
	) Resolver {
	return .{
	.allocator = allocator,
	.cache_allocator = cache_allocator,
	.string_pool = string_pool,
	.http = http,
	.cache_db = cache_db,
	.resolved = std.StringHashMap(*ResolvedPackage).init(allocator),
	.constraints = std.StringHashMap(std.ArrayListUnmanaged(Constraint)).init(allocator),
	.in_progress = std.StringHashMap(void).init(allocator),
	.registry_url = registry_url,
	.metadata_cache = metadata_cache,
	.on_package_resolved = null,
	.on_package_resolved_data = null,
	};
	}

	pub fn setOnPackageResolved(self: Resolver, callback: OnPackageResolvedFn, user_data: ?anyopaque) void {
	self.on_package_resolved = callback;
	self.on_package_resolved_data = user_data;
	}

	pub fn deinit(self: *Resolver) void {
	var key_iter = self.resolved.keyIterator();
	while (key_iter.next()) \|key\| {
	self.allocator.free(key.*);
	}

	var iter = self.resolved.valueIterator();
	while (iter.next()) \|pkg\| {
	pkg.*.deinit();
	self.allocator.destroy(pkg.*);
	} self.resolved.deinit();

	var cons_key_iter = self.constraints.keyIterator();
	while (cons_key_iter.next()) \|key\| {
	self.allocator.free(key.*);
	}

	var cons_iter = self.constraints.valueIterator();
	while (cons_iter.next()) \|list\| {
	list.deinit(self.allocator);
	}
	self.constraints.deinit();
	self.in_progress.deinit();
	}

	pub fn resolveFromPackageJson(self: *Resolver, path: []const u8) !void {
	const path_z = try self.allocator.dupeZ(u8, path);
	defer self.allocator.free(path_z);

	var pkg_json = try json.PackageJson.parse(self.allocator, path_z);
	defer pkg_json.deinit(self.allocator);

	debug.log("pass 1: collecting constraints", .{});
	var pass1_start: u64 = @intCast(std.time.nanoTimestamp());
	self.http.initiateTarballConnectionsAsync();

	const ConstraintInfo = struct {
	constraint: Constraint,
	constraint_str: []const u8,
	requester: []const u8,
	depth: u32,
	};

	var all_constraints = std.StringHashMap(std.ArrayListUnmanaged(ConstraintInfo)).init(self.allocator);
	defer {
	var iter = all_constraints.iterator();
	while (iter.next()) \|entry\| {
	for (entry.value_ptr.items) \|info\| {
	self.allocator.free(info.constraint_str);
	self.allocator.free(info.requester);
	}
	entry.value_ptr.deinit(self.allocator);
	self.allocator.free(entry.key_ptr.*);
	} all_constraints.deinit();
	}

	const CollectItem = struct {
	name: []const u8,
	constraint_str: []const u8,
	requester: []const u8,
	depth: u32,
	};

	var collect_queue = std.ArrayListUnmanaged(CollectItem){};
	defer collect_queue.deinit(self.allocator);

	var seen_collect = std.StringHashMap(void).init(self.allocator);
	defer {
	var key_iter = seen_collect.keyIterator();
	while (key_iter.next()) \|k\| self.allocator.free(k.*);
	seen_collect.deinit();
	}

	var dep_iter = pkg_json.dependencies.iterator();
	while (dep_iter.next()) \|entry\| {
	try collect_queue.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint_str = entry.value_ptr.*,
	.requester = "root",
	.depth = 0,
	});
	}

	var dev_iter = pkg_json.dev_dependencies.iterator();
	while (dev_iter.next()) \|entry\| {
	try collect_queue.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint_str = entry.value_ptr.*,
	.requester = "root",
	.depth = 0,
	});
	}

	var collect_level: u32 = 0;
	while (collect_queue.items.len > 0) {
	debug.log(" pass1 level {d}: {d} packages", .{ collect_level, collect_queue.items.len });

	var to_fetch = std.ArrayListUnmanaged([]const u8){};
	defer to_fetch.deinit(self.allocator);

	for (collect_queue.items) \|item\| {
	if (!self.metadata_cache.contains(item.name)) {
	var loaded_from_disk = false;
	if (self.cache_db) \|db\| {
	if (db.lookupMetadata(item.name, self.allocator)) \|json_data\| {
	const metadata = PackageMetadata.parseFromJson(self.cache_allocator, json_data) catch {
	self.allocator.free(json_data);
	continue;
	};
	self.allocator.free(json_data);
	const cache_key = self.cache_allocator.dupe(u8, item.name) catch continue;
	self.metadata_cache.put(cache_key, metadata) catch {
	self.cache_allocator.free(cache_key);
	continue;
	};
	loaded_from_disk = true;
	}
	}
	if (!loaded_from_disk) {
	var already_listed = false;
	for (to_fetch.items) \|f\| {
	if (std.mem.eql(u8, f, item.name)) {
	already_listed = true;
	break;
	}
	}
	if (!already_listed) try to_fetch.append(self.allocator, item.name);
	}
	}
	}

	const StreamContext = struct {
	resolver: *Resolver,
	prefetch_queue: *std.ArrayListUnmanaged([]const u8),
	collect_queue_items: []const CollectItem,
	allocator: std.mem.Allocator,

	fn onMetadata(name: []const u8, data: ?[]const u8, has_error: bool, userdata: ?*anyopaque) void {
	const ctx: *@This() = @ptrCast(@alignCast(userdata));
	if (has_error or data == null) return;

	if (ctx.resolver.cache_db) \|db\| {
	db.insertMetadata(name, data.?) catch {};
	}

	const metadata = PackageMetadata.parseFromJson(ctx.resolver.cache_allocator, data.?) catch return;
	const cache_key = ctx.resolver.cache_allocator.dupe(u8, name) catch return;
	ctx.resolver.metadata_cache.put(cache_key, metadata) catch {
	ctx.resolver.cache_allocator.free(cache_key);
	return;
	};

	for (ctx.collect_queue_items) \|item\| {
	if (!std.mem.eql(u8, item.name, name)) continue;

	const constraint = Constraint.parse(item.constraint_str) catch continue;
	const best = ctx.resolver.selectBestVersion(&metadata, constraint) orelse continue;
	if (!best.matchesPlatform()) continue;

	var dep_it = best.dependencies.iterator();
	while (dep_it.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	if (ctx.resolver.metadata_cache.contains(dep_name)) continue;

	var already_queued = false;
	for (ctx.prefetch_queue.items) \|q\| {
	if (std.mem.eql(u8, q, dep_name)) {
	already_queued = true; break;
	}
	}
	if (!already_queued) ctx.prefetch_queue.append(ctx.allocator, dep_name) catch {};
	} break;
	}
	}
	};

	var next_collect = std.ArrayListUnmanaged(CollectItem){};
	errdefer next_collect.deinit(self.allocator);

	var prefetch_queue = std.ArrayListUnmanaged([]const u8){};
	defer prefetch_queue.deinit(self.allocator);

	if (to_fetch.items.len > 0) {
	var stream_ctx = StreamContext{
	.resolver = self,
	.prefetch_queue = &prefetch_queue,
	.collect_queue_items = collect_queue.items,
	.allocator = self.allocator,
	};

	try self.http.fetchMetadataStreaming(
	to_fetch.items,
	self.allocator,
	StreamContext.onMetadata,
	&stream_ctx,
	);

	if (prefetch_queue.items.len > 0) {
	debug.log(" prefetch: queued {d} next-level packages", .{prefetch_queue.items.len});
	self.http.fetchMetadataStreaming(
	prefetch_queue.items,
	self.allocator,
	StreamContext.onMetadata,
	&stream_ctx,
	) catch {};
	}
	}

	for (collect_queue.items) \|item\| {
	const seen_key = std.fmt.allocPrint(self.allocator, "{s}@{s}@{s}", .{ item.name, item.constraint_str, item.requester }) catch continue;
	if (seen_collect.contains(seen_key)) {
	self.allocator.free(seen_key);
	continue;
	}
	try seen_collect.put(seen_key, {});

	const constraint = Constraint.parse(item.constraint_str) catch continue;
	const gop = try all_constraints.getOrPut(item.name);
	if (!gop.found_existing) {
	gop.key_ptr.* = try self.allocator.dupe(u8, item.name);
	gop.value_ptr.* = .{};
	}
	try gop.value_ptr.append(self.allocator, .{
	.constraint = constraint,
	.constraint_str = try self.allocator.dupe(u8, item.constraint_str),
	.requester = try self.allocator.dupe(u8, item.requester),
	.depth = item.depth,
	});

	if (self.metadata_cache.get(item.name)) \|metadata\| {
	const best = self.selectBestVersion(&metadata, constraint) orelse continue;
	if (!best.matchesPlatform()) continue;

	var dep_it = best.dependencies.iterator();
	while (dep_it.next()) \|entry\| {
	try next_collect.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint_str = entry.value_ptr.*,
	.requester = item.name,
	.depth = item.depth + 1,
	});
	}

	var opt_it = best.optional_dependencies.iterator();
	while (opt_it.next()) \|entry\| {
	if (self.metadata_cache.get(entry.key_ptr.*)) \|opt_meta\| {
	const opt_con = Constraint.parse(entry.value_ptr.*) catch continue;
	const opt_best = self.selectBestVersion(&opt_meta, opt_con) orelse continue;
	if (!opt_best.matchesPlatform()) continue;
	}
	try next_collect.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint_str = entry.value_ptr.*,
	.requester = item.name,
	.depth = item.depth + 1,
	});
	}

	var peer_it = best.peer_dependencies.iterator();
	while (peer_it.next()) \|entry\| {
	if (best.peer_dependencies_meta.contains(entry.key_ptr.*)) continue;
	try next_collect.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint_str = entry.value_ptr.*,
	.requester = item.name,
	.depth = item.depth + 1,
	});
	}
	}
	}

	collect_queue.deinit(self.allocator);
	collect_queue = next_collect;
	collect_level += 1;
	}

	pass1_start = debug.timer("pass 1 complete", pass1_start);
	debug.log(" collected constraints for {d} packages", .{all_constraints.count()});
	debug.log("computing optimal versions", .{});

	var optimal_versions = std.StringHashMap(*const VersionInfo).init(self.allocator);
	defer optimal_versions.deinit();

	var pkg_iter = all_constraints.iterator();
	while (pkg_iter.next()) \|entry\| {
	const pkg_name = entry.key_ptr.*;
	const constraint_list = entry.value_ptr.items;

	if (self.metadata_cache.get(pkg_name)) \|metadata\| {
	var plain_constraints = try self.allocator.alloc(Constraint, constraint_list.len);
	defer self.allocator.free(plain_constraints);
	for (constraint_list, 0..) \|info, i\| {
	plain_constraints[i] = info.constraint;
	}

	if (self.selectBestVersionForConstraints(&metadata, plain_constraints)) \|best\| {
	try optimal_versions.put(pkg_name, best);
	} else {
	const best = self.selectVersionSatisfyingMost(&metadata, constraint_list);
	if (best) \|b\| {
	if (b.version.prerelease) \|pre\| {
	debug.log(" {s}: optimal={d}.{d}.{d}-{s} (satisfies {d}/{d} constraints)", .{
	pkg_name, b.version.major, b.version.minor, b.version.patch, pre,
	self.countSatisfied(&metadata, b, constraint_list), constraint_list.len,
	});
	} else {
	debug.log(" {s}: optimal={d}.{d}.{d} (satisfies {d}/{d} constraints)", .{
	pkg_name, b.version.major, b.version.minor, b.version.patch,
	self.countSatisfied(&metadata, b, constraint_list), constraint_list.len,
	});
	}
	try optimal_versions.put(pkg_name, b);
	}
	}
	}
	}

	pass1_start = debug.timer("optimal versions computed", pass1_start);
	debug.log("pass 2: resolving with optimal versions", .{});

	const WorkItem = struct {
	name: []const u8,
	constraint: []const u8,
	depth: u32,
	direct: bool,
	parent_name: ?[]const u8,
	};

	var queue = std.ArrayListUnmanaged(WorkItem){};
	defer {
	for (queue.items) \|item\| if (item.parent_name) \|p\| self.allocator.free(p);
	queue.deinit(self.allocator);
	}

	dep_iter = pkg_json.dependencies.iterator();
	while (dep_iter.next()) \|entry\| {
	try queue.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint = entry.value_ptr.*,
	.depth = 0,
	.direct = true,
	.parent_name = null,
	});
	}
	dev_iter = pkg_json.dev_dependencies.iterator();
	while (dev_iter.next()) \|entry\| {
	try queue.append(self.allocator, .{
	.name = entry.key_ptr.*,
	.constraint = entry.value_ptr.*,
	.depth = 0,
	.direct = true,
	.parent_name = null,
	});
	}

	var processed = std.StringHashMap(void).init(self.allocator);
	defer {
	var key_iter = processed.keyIterator();
	while (key_iter.next()) \|k\| self.allocator.free(k.*);
	processed.deinit();
	}

	var level: u32 = 0;
	while (queue.items.len > 0) {
	const level_start: u64 = @intCast(std.time.nanoTimestamp());
	debug.log(" pass2 level {d}: {d} packages", .{ level, queue.items.len });

	var next_queue = std.ArrayListUnmanaged(WorkItem){};
	errdefer next_queue.deinit(self.allocator);

	for (queue.items) \|item\| {
	const key = std.fmt.allocPrint(self.allocator, "{s}@{s}", .{ item.name, item.constraint }) catch continue;
	if (processed.contains(key)) {
	self.allocator.free(key);
	continue;
	}
	try processed.put(key, {});

	const pkg = self.resolveSingleWithOptimal(item.name, item.constraint, item.depth, item.direct, item.parent_name, &optimal_versions) catch \|err\| {
	debug.log(" failed to resolve {s}: {}", .{ item.name, err });
	continue;
	};

	const pkg_install_path = pkg.installPath(self.allocator) catch continue;
	defer self.allocator.free(pkg_install_path);

	for (pkg.dependencies.items) \|dep\| {
	const dep_key = std.fmt.allocPrint(self.allocator, "{s}@{s}", .{ dep.name.slice(), dep.constraint }) catch continue;
	defer self.allocator.free(dep_key);
	if (!processed.contains(dep_key)) {
	try next_queue.append(self.allocator, .{
	.name = dep.name.slice(),
	.constraint = dep.constraint,
	.depth = item.depth + 1,
	.direct = false,
	.parent_name = try self.allocator.dupe(u8, pkg_install_path),
	});
	}
	}
	}
	_ = debug.timer(" resolve + queue next", level_start);

	const completed = self.http.tick();
	if (completed > 0) {
	debug.log(" tarballs: {d} completed, {d} in flight", .{ completed, self.http.pendingTarballCount() });
	}

	for (queue.items) \|item\| if (item.parent_name) \|p\| self.allocator.free(p);
	queue.deinit(self.allocator);
	queue = next_queue;
	level += 1;
	}
	}

	fn countSatisfied(_: Resolver, _: const PackageMetadata, version_info: *const VersionInfo, constraint_list: anytype) usize {
	var count: usize = 0;
	for (constraint_list) \|info\| {
	if (info.constraint.satisfies(version_info.version)) count += 1;
	}
	return count;
	}

	fn selectVersionSatisfyingMost(_: Resolver, metadata: const PackageMetadata, constraint_list: anytype) ?*const VersionInfo {
	var best: ?*const VersionInfo = null;
	var best_score: i64 = -1;

	var want_prerelease = false;
	for (constraint_list) \|info\| {
	if (info.constraint.version.prerelease != null) { want_prerelease = true; break; }
	}

	for (metadata.versions.items) \|*v\| {
	if (v.version.prerelease != null and !want_prerelease) continue;
	if (!v.matchesPlatform()) continue;

	var score: i64 = 0;
	for (constraint_list) \|info\| {
	if (info.constraint.satisfies(v.version)) {
	const weight: i64 = @intCast(1000 / (info.depth + 1));
	score += weight;
	}
	}

	if (score > best_score or (score == best_score and best != null and v.version.order(best.?.version) == .gt)) {
	best = v;
	best_score = score;
	}
	}

	return best;
	}

	fn resolveSingleWithOptimal(
	self: *Resolver,
	name: []const u8,
	constraint_str: []const u8,
	depth: u32,
	direct: bool,
	parent_name: ?[]const u8,
	optimal_versions: std.StringHashMap(const VersionInfo),
	) !*ResolvedPackage {
	const constraint = try Constraint.parse(constraint_str);

	if (self.resolved.get(name)) \|existing_pkg\| {
	if (constraint.satisfies(existing_pkg.version)) {
	if (direct) existing_pkg.direct = true;
	if (depth < existing_pkg.depth) existing_pkg.depth = depth;
	return existing_pkg;
	}

	if (parent_name) \|parent\| {
	var metadata = try self.fetchMetadata(name);
	const nested_best = self.selectBestVersion(&metadata, constraint) orelse return existing_pkg;
	if (!nested_best.matchesPlatform()) return existing_pkg;

	debug.log(" nested: {s}@{d}.{d}.{d} under {s} (hoisted: {d}.{d}.{d})", .{
	name,
	nested_best.version.major,
	nested_best.version.minor,
	nested_best.version.patch,
	parent,
	existing_pkg.version.major,
	existing_pkg.version.minor,
	existing_pkg.version.patch,
	});

	return try self.createNestedPackage(name, nested_best, depth, parent);
	}

	return existing_pkg;
	}

	var metadata = try self.fetchMetadata(name);
	const version_info = blk: {
	if (optimal_versions.get(name)) \|optimal\| {
	if (constraint.satisfies(optimal.version) and optimal.matchesPlatform()) break :blk optimal;
	}
	break :blk self.selectBestVersion(&metadata, constraint) orelse return error.NoMatchingVersion;
	};

	if (!version_info.matchesPlatform()) return error.PlatformMismatch;

	const cons_gop = try self.constraints.getOrPut(name);
	if (!cons_gop.found_existing) {
	cons_gop.key_ptr.* = try self.allocator.dupe(u8, name);
	cons_gop.value_ptr.* = .{};
	} try cons_gop.value_ptr.append(self.allocator, constraint);

	const pkg = try self.allocator.create(ResolvedPackage);
	errdefer self.allocator.destroy(pkg);

	pkg.* = .{
	.name = try self.string_pool.intern(name),
	.version = version_info.version,
	.integrity = version_info.integrity,
	.tarball_url = try self.allocator.dupe(u8, version_info.tarball_url),
	.dependencies = .{},
	.depth = depth,
	.direct = direct,
	.parent_path = null,
	.has_bin = version_info.bin.count() > 0,
	.allocator = self.allocator,
	};

	const name_key = try self.allocator.dupe(u8, name);
	errdefer self.allocator.free(name_key);
	try self.resolved.put(name_key, pkg);

	var dep_it = version_info.dependencies.iterator();
	while (dep_it.next()) \|entry\| {
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(entry.key_ptr.*),
	.constraint = try self.allocator.dupe(u8, entry.value_ptr.*),
	.flags = .{},
	});
	}

	var opt_it = version_info.optional_dependencies.iterator();
	while (opt_it.next()) \|entry\| {
	if (self.metadata_cache.get(entry.key_ptr.*)) \|opt_meta\| {
	const opt_con = Constraint.parse(entry.value_ptr.*) catch continue;
	const opt_best = self.selectBestVersion(&opt_meta, opt_con) orelse continue;
	if (!opt_best.matchesPlatform()) continue;
	}
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(entry.key_ptr.*),
	.constraint = try self.allocator.dupe(u8, entry.value_ptr.*),
	.flags = .{ .optional = true },
	});
	}

	var peer_it = version_info.peer_dependencies.iterator();
	while (peer_it.next()) \|entry\| {
	if (version_info.peer_dependencies_meta.contains(entry.key_ptr.*)) continue;
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(entry.key_ptr.*),
	.constraint = try self.allocator.dupe(u8, entry.value_ptr.*),
	.flags = .{ .peer = true },
	});
	}

	if (self.on_package_resolved) \|callback\| {
	callback(pkg, self.on_package_resolved_data);
	}

	return pkg;
	}

	fn resolveSingle(self: Resolver, name: []const u8, constraint_str: []const u8, depth: u32, direct: bool, parent_name: ?[]const u8) !ResolvedPackage {
	const constraint = try Constraint.parse(constraint_str);

	if (self.resolved.get(name)) \|existing_pkg\| {
	if (constraint.satisfies(existing_pkg.version)) {
	if (direct) existing_pkg.direct = true;
	if (depth < existing_pkg.depth) existing_pkg.depth = depth;
	return existing_pkg;
	}

	const cons_gop = try self.constraints.getOrPut(name);
	if (!cons_gop.found_existing) {
	cons_gop.key_ptr.* = try self.allocator.dupe(u8, name);
	cons_gop.value_ptr.* = .{};
	}
	try cons_gop.value_ptr.append(self.allocator, constraint);

	var metadata = try self.fetchMetadata(name);
	const all_constraints = cons_gop.value_ptr.items;
	const best = self.selectBestVersionForConstraints(&metadata, all_constraints);

	if (best) \|b\| {
	if (!b.matchesPlatform()) {
	return error.PlatformMismatch;
	}

	if (b.version.order(existing_pkg.version) != .eq) {
	debug.log(" re-resolve {s}: {d}.{d}.{d} -> {d}.{d}.{d}", .{
	name,
	existing_pkg.version.major,
	existing_pkg.version.minor,
	existing_pkg.version.patch,
	b.version.major,
	b.version.minor,
	b.version.patch,
	});

	existing_pkg.version = b.version;
	existing_pkg.integrity = b.integrity;
	self.allocator.free(existing_pkg.tarball_url);
	existing_pkg.tarball_url = try self.allocator.dupe(u8, b.tarball_url);
	existing_pkg.has_bin = b.bin.count() > 0;

	if (self.on_package_resolved) \|callback\| {
	callback(existing_pkg, self.on_package_resolved_data);
	}
	}

	if (direct) existing_pkg.direct = true;
	if (depth < existing_pkg.depth) existing_pkg.depth = depth;
	return existing_pkg;
	} else {
	if (parent_name) \|parent\| {
	const nested_best = self.selectBestVersion(&metadata, constraint) orelse {
	debug.log(" nested: no version for {s} {s}", .{ name, constraint_str });
	return existing_pkg;
	};

	if (!nested_best.matchesPlatform()) return existing_pkg;
	debug.log(" nested: {s}@{d}.{d}.{d} under {s} (hoisted: {d}.{d}.{d})", .{
	name,
	nested_best.version.major,
	nested_best.version.minor,
	nested_best.version.patch,
	parent,
	existing_pkg.version.major,
	existing_pkg.version.minor,
	existing_pkg.version.patch,
	});

	return try self.createNestedPackage(name, nested_best, depth, parent);
	} else {
	debug.log(" version conflict for {s}: no version satisfies all constraints", .{name});
	return existing_pkg;
	}
	}
	}

	const cons_gop = try self.constraints.getOrPut(name);
	if (!cons_gop.found_existing) {
	cons_gop.key_ptr.* = try self.allocator.dupe(u8, name);
	cons_gop.value_ptr.* = .{};
	}
	try cons_gop.value_ptr.append(self.allocator, constraint);

	var metadata = try self.fetchMetadata(name);
	const best = self.selectBestVersion(&metadata, constraint) orelse {
	return error.NoMatchingVersion;
	};

	if (!best.matchesPlatform()) {
	return error.PlatformMismatch;
	}

	const pkg = try self.allocator.create(ResolvedPackage);
	errdefer self.allocator.destroy(pkg);

	pkg.* = .{
	.name = try self.string_pool.intern(name),
	.version = best.version,
	.integrity = best.integrity,
	.tarball_url = try self.allocator.dupe(u8, best.tarball_url),
	.dependencies = .{},
	.depth = depth,
	.direct = direct,
	.parent_path = null,
	.has_bin = best.bin.count() > 0,
	.allocator = self.allocator,
	};

	const name_key = try self.allocator.dupe(u8, name);
	errdefer self.allocator.free(name_key);
	try self.resolved.put(name_key, pkg);

	var dep_iter = best.dependencies.iterator();
	while (dep_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{},
	});
	}

	var opt_iter = best.optional_dependencies.iterator();
	while (opt_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	if (self.metadata_cache.get(dep_name)) \|opt_metadata\| {
	const opt_constraint = Constraint.parse(dep_constraint) catch continue;
	const opt_best = self.selectBestVersion(&opt_metadata, opt_constraint) orelse continue;

	if (!opt_best.matchesPlatform()) continue;
	}

	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{ .optional = true },
	});
	}

	var peer_iter = best.peer_dependencies.iterator();
	while (peer_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	if (best.peer_dependencies_meta.contains(dep_name)) continue;
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{ .peer = true },
	});
	}

	if (self.on_package_resolved) \|callback\| {
	callback(pkg, self.on_package_resolved_data);
	}

	return pkg;
	}

	fn createNestedPackage(self: Resolver, name: []const u8, version_info: const VersionInfo, depth: u32, parent_path: []const u8) !*ResolvedPackage {
	const nested_key = try std.fmt.allocPrint(self.allocator, "{s}/node_modules/{s}", .{ parent_path, name });
	errdefer self.allocator.free(nested_key);

	if (self.resolved.get(nested_key)) \|existing\| {
	self.allocator.free(nested_key);
	return existing;
	}

	const pkg = try self.allocator.create(ResolvedPackage);
	errdefer self.allocator.destroy(pkg);

	pkg.* = .{
	.name = try self.string_pool.intern(name),
	.version = version_info.version,
	.integrity = version_info.integrity,
	.tarball_url = try self.allocator.dupe(u8, version_info.tarball_url),
	.dependencies = .{},
	.depth = depth,
	.direct = false,
	.parent_path = try self.allocator.dupe(u8, parent_path),
	.has_bin = version_info.bin.count() > 0,
	.allocator = self.allocator,
	};

	try self.resolved.put(nested_key, pkg);

	var dep_iter = version_info.dependencies.iterator();
	while (dep_iter.next()) \|entry\| {
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(entry.key_ptr.*),
	.constraint = try self.allocator.dupe(u8, entry.value_ptr.*),
	.flags = .{},
	});
	}

	var opt_iter = version_info.optional_dependencies.iterator();
	while (opt_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	if (self.metadata_cache.get(dep_name)) \|opt_metadata\| {
	const opt_constraint = Constraint.parse(dep_constraint) catch continue;
	const opt_best = self.selectBestVersion(&opt_metadata, opt_constraint) orelse continue;
	if (!opt_best.matchesPlatform()) continue;
	}

	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{ .optional = true },
	});
	}

	if (self.on_package_resolved) \|callback\| {
	callback(pkg, self.on_package_resolved_data);
	}

	return pkg;
	}

	pub fn resolve(self: Resolver, name: []const u8, constraint_str: []const u8, depth: u32) !ResolvedPackage {
	if (self.in_progress.contains(name)) {
	return error.CyclicDependency;
	}
	const in_progress_key = try self.allocator.dupe(u8, name);
	try self.in_progress.put(in_progress_key, {});
	defer {
	_ = self.in_progress.remove(name);
	self.allocator.free(in_progress_key);
	}

	const constraint = try Constraint.parse(constraint_str);
	const cons_gop = try self.constraints.getOrPut(name);

	if (!cons_gop.found_existing) {
	cons_gop.key_ptr.* = try self.allocator.dupe(u8, name);
	cons_gop.value_ptr.* = .{};
	}
	try cons_gop.value_ptr.append(self.allocator, constraint);

	if (self.resolved.get(name)) \|existing_pkg\| {
	if (constraint.satisfies(existing_pkg.version)) {
	if (depth == 0) existing_pkg.direct = true;
	if (depth < existing_pkg.depth) existing_pkg.depth = depth;
	return existing_pkg;
	}

	var metadata = try self.fetchMetadata(name);
	const all_constraints = cons_gop.value_ptr.items;
	const best = self.selectBestVersionForConstraints(&metadata, all_constraints) orelse {
	debug.log(" version conflict for {s}: no version satisfies all constraints", .{name});
	return existing_pkg;
	};

	if (best.version.order(existing_pkg.version) != .eq) {
	debug.log(" re-resolve {s}: {d}.{d}.{d} -> {d}.{d}.{d}", .{
	name,
	existing_pkg.version.major,
	existing_pkg.version.minor,
	existing_pkg.version.patch,
	best.version.major,
	best.version.minor,
	best.version.patch,
	});

	existing_pkg.version = best.version;
	existing_pkg.integrity = best.integrity;
	self.allocator.free(existing_pkg.tarball_url);
	existing_pkg.tarball_url = try self.allocator.dupe(u8, best.tarball_url);
	existing_pkg.has_bin = best.bin.count() > 0;
	}

	if (depth == 0) existing_pkg.direct = true;
	if (depth < existing_pkg.depth) existing_pkg.depth = depth;
	return existing_pkg;
	}

	var metadata = try self.fetchMetadata(name);
	const all_constraints = cons_gop.value_ptr.items;
	const best = self.selectBestVersionForConstraints(&metadata, all_constraints) orelse {
	return error.NoMatchingVersion;
	};

	const pkg = try self.allocator.create(ResolvedPackage);
	errdefer self.allocator.destroy(pkg);

	pkg.* = .{
	.name = try self.string_pool.intern(name),
	.version = best.version,
	.integrity = best.integrity,
	.tarball_url = try self.allocator.dupe(u8, best.tarball_url),
	.dependencies = .{},
	.depth = depth,
	.direct = (depth == 0),
	.parent_path = null,
	.has_bin = best.bin.count() > 0,
	.allocator = self.allocator,
	};

	const name_key = try self.allocator.dupe(u8, name);
	errdefer self.allocator.free(name_key);
	try self.resolved.put(name_key, pkg);

	var dep_iter = best.dependencies.iterator();
	while (dep_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	_ = self.resolve(dep_name, dep_constraint, depth + 1) catch \|err\| {
	std.log.debug("Skipping dep {s}: {}", .{ dep_name, err });
	continue;
	};

	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{},
	});
	}

	var opt_iter = best.optional_dependencies.iterator();
	while (opt_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	const resolved_opt = self.resolve(dep_name, dep_constraint, depth + 1) catch {
	continue;
	};

	const opt_metadata = self.fetchMetadata(dep_name) catch continue;
	const opt_constraint = Constraint.parse(dep_constraint) catch continue;
	const opt_best = self.selectBestVersion(&opt_metadata, opt_constraint) orelse continue;

	if (!opt_best.matchesPlatform()) {
	if (self.resolved.fetchRemove(dep_name)) \|kv\| {
	self.allocator.free(kv.key);
	kv.value.deinit();
	self.allocator.destroy(kv.value);
	}
	continue;
	}

	_ = resolved_opt;
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{ .optional = true },
	});
	}

	var peer_iter = best.peer_dependencies.iterator();
	while (peer_iter.next()) \|entry\| {
	const dep_name = entry.key_ptr.*;
	const dep_constraint = entry.value_ptr.*;

	if (best.peer_dependencies_meta.contains(dep_name)) continue;
	_ = self.resolve(dep_name, dep_constraint, depth + 1) catch continue;
	try pkg.dependencies.append(self.allocator, .{
	.name = try self.string_pool.intern(dep_name),
	.constraint = try self.allocator.dupe(u8, dep_constraint),
	.flags = .{ .peer = true },
	});
	}

	return pkg;
	}

	fn fetchMetadata(self: *Resolver, name: []const u8) !PackageMetadata {
	if (self.metadata_cache.get(name)) \|cached\| {
	debug.log(" metadata: {s} (memory cache)", .{name});
	return PackageMetadata{
	.allocator = cached.allocator,
	.name = cached.name,
	.versions = cached.versions,
	};
	}

	if (self.cache_db) \|db\| {
	if (db.lookupMetadata(name, self.allocator)) \|json_data\| {
	defer self.allocator.free(json_data);
	const metadata = PackageMetadata.parseFromJson(self.cache_allocator, json_data) catch {
	return self.fetchFromNetwork(name);
	};

	debug.log(" metadata: {s} (disk cache)", .{name});
	const cache_key = try self.cache_allocator.dupe(u8, name);
	try self.metadata_cache.put(cache_key, metadata);
	return self.metadata_cache.get(name).?;
	}
	}

	return self.fetchFromNetwork(name);
	}

	fn fetchFromNetwork(self: *Resolver, name: []const u8) !PackageMetadata {
	debug.log(" metadata: {s} (fetch)", .{name});
	const json_data = try self.http.fetchMetadata(name, self.allocator);
	defer self.allocator.free(json_data);

	if (self.cache_db) \|db\| {
	db.insertMetadata(name, json_data) catch {};
	}

	const metadata = try PackageMetadata.parseFromJson(self.cache_allocator, json_data);
	const cache_key = try self.cache_allocator.dupe(u8, name);

	try self.metadata_cache.put(cache_key, metadata);
	return self.metadata_cache.get(name).?;
	}

	fn selectBestVersion(_: Resolver, metadata: const PackageMetadata, constraint: Constraint) ?*const VersionInfo {
	if (constraint.kind == .any) for (metadata.versions.items) \|*v\| {
	const dtl = metadata.dist_tag_latest orelse break;
	if (v.version.order(dtl) == .eq) return v;
	};

	var best: ?*const VersionInfo = null;
	const want_prerelease = constraint.version.prerelease != null;

	for (metadata.versions.items) \|*v\| {
	if (v.version.prerelease != null and !want_prerelease) continue;
	if (constraint.satisfies(v.version)) {
	if (best == null or v.version.order(best.?.version) == .gt) best = v;
	}
	}

	if (best != null or constraint.kind != .any) return best;

	for (metadata.versions.items) \|*v\| {
	if (!constraint.satisfies(v.version)) continue;
	if (best == null or v.version.order(best.?.version) == .gt) best = v;
	}

	return best;
	}

	fn selectBestVersionForConstraints(_: Resolver, metadata: const PackageMetadata, all_constraints: []const Constraint) ?*const VersionInfo {
	var best: ?*const VersionInfo = null;

	var want_prerelease = false;
	var all_any = true;
	for (all_constraints) \|c\| {
	if (c.version.prerelease != null) want_prerelease = true;
	if (c.kind != .any) all_any = false;
	}

	if (all_any) for (metadata.versions.items) \|*v\| {
	const dtl = metadata.dist_tag_latest orelse break;
	if (v.version.order(dtl) == .eq) return v;
	};

	for (metadata.versions.items) \|*v\| {
	if (v.version.prerelease != null and !want_prerelease) continue;

	var satisfies_all = true;
	for (all_constraints) \|c\| {
	if (!c.satisfies(v.version)) {
	satisfies_all = false; break;
	}
	}

	if (satisfies_all) {
	if (best == null or v.version.order(best.?.version) == .gt) best = v;
	}
	}

	if (best != null or !all_any) return best;

	for (metadata.versions.items) \|*v\| {
	var satisfies_all = true;
	for (all_constraints) \|c\| {
	if (!c.satisfies(v.version)) { satisfies_all = false; break; }
	}
	if (satisfies_all and (best == null or v.version.order(best.?.version) == .gt)) best = v;
	}

	return best;
	}

	pub fn writeLockfile(self: *Resolver, path: []const u8) !void {
	var writer = lockfile.LockfileWriter.init(self.allocator);
	defer writer.deinit();

	var pkg_indices = std.StringHashMap(u32).init(self.allocator);
	defer {
	var key_iter = pkg_indices.keyIterator();
	while (key_iter.next()) \|k\| self.allocator.free(k.*);
	pkg_indices.deinit();
	}

	var idx: u32 = 0;
	var iter = self.resolved.valueIterator();
	while (iter.next()) \|pkg_ptr\| {
	const pkg = pkg_ptr.*;
	const install_path = try pkg.installPath(self.allocator);
	try pkg_indices.put(install_path, idx);
	idx += 1;
	}

	iter = self.resolved.valueIterator();
	while (iter.next()) \|pkg_ptr\| {
	const pkg = pkg_ptr.*;
	const name_ref = try writer.internString(pkg.name.slice());
	const url_ref = try writer.internString(pkg.tarball_url);
	const prerelease_ref = if (pkg.version.prerelease) \|pre\|
	try writer.internString(pre)
	else lockfile.StringRef.empty;
	const parent_ref = if (pkg.parent_path) \|parent\|
	try writer.internString(parent)
	else lockfile.StringRef.empty;

	const deps_start: u32 = @intCast(writer.dependencies.items.len);
	const pkg_install_path = try pkg.installPath(self.allocator);
	defer self.allocator.free(pkg_install_path);

	var deps_written: u32 = 0;
	for (pkg.dependencies.items) \|dep\| {
	const dep_name = dep.name.slice();
	var found_idx = pkg_indices.get(dep_name);

	if (found_idx == null) {
	const nested_path = std.fmt.allocPrint(self.allocator, "{s}/node_modules/{s}", .{ pkg_install_path, dep_name }) catch continue;
	defer self.allocator.free(nested_path);
	found_idx = pkg_indices.get(nested_path);
	}

	if (found_idx) \|fi\| {
	const constraint_ref = try writer.internString(dep.constraint);
	try writer.addDependency(.{
	.package_index = fi,
	.constraint = constraint_ref,
	.flags = .{
	.peer = dep.flags.peer,
	.dev = dep.flags.dev,
	.optional = dep.flags.optional,
	},
	}); deps_written += 1;
	}
	}

	_ = try writer.addPackage(.{
	.name = name_ref,
	.version_major = pkg.version.major,
	.version_minor = pkg.version.minor,
	.version_patch = pkg.version.patch,
	.prerelease = prerelease_ref,
	.integrity = pkg.integrity,
	.tarball_url = url_ref,
	.parent_path = parent_ref,
	.deps_start = deps_start,
	.deps_count = deps_written,
	.flags = .{
	.direct = pkg.direct,
	.has_bin = pkg.has_bin,
	},
	});
	}

	try writer.write(path);
	}
	};

File Metadata

Mime Type: text/plain
Expires: Sun, May 3, 8:01 AM (1 d, 22 h)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 539050
Default Alt Text: resolver.zig (61 KB)

resolver.zigNo OneTemporaryActions

resolver.zigView Options

File Metadata

Event Timeline

resolver.zig
No OneTemporary
Actions

resolver.zig
View Options