resolver.zig
8755416ca476master

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);
			}
			};

Owner Packages

No Owners

ant/src/pkg/resolver.zig8755416ca476master

resolver.zigView Options

Owner Packages

ant/src/pkg/resolver.zig
8755416ca476master

resolver.zig
View Options