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, } } }; const DependencySpec = struct { install_name: []const u8, package_name: []const u8, constraint: []const u8, }; const NpmAliasSpec = struct { package_name: []const u8, constraint: []const u8, }; fn parseNpmAliasSpec(spec: []const u8) ?NpmAliasSpec { if (!std.mem.startsWith(u8, spec, "npm:")) return null; const rest = spec["npm:".len..]; if (rest.len == 0) return null; const version_at: ?usize = if (rest[0] == '@') blk: { const slash = std.mem.indexOfScalar(u8, rest, '/') orelse return null; if (slash + 1 >= rest.len) return null; if (std.mem.indexOfScalar(u8, rest[slash + 1 ..], '@')) |rel_at| { break :blk slash + 1 + rel_at; } break :blk null; } else std.mem.indexOfScalar(u8, rest, '@'); const package_name = if (version_at) |at| rest[0..at] else rest; if (package_name.len == 0) return null; const constraint = if (version_at) |at| blk: { const alias_constraint = rest[at + 1 ..]; break :blk if (alias_constraint.len > 0) alias_constraint else "latest"; } else "latest"; return .{ .package_name = package_name, .constraint = constraint }; } fn dependencySpec(install_name: []const u8, constraint: []const u8) DependencySpec { if (parseNpmAliasSpec(constraint)) |alias| { return .{ .install_name = install_name, .package_name = alias.package_name, .constraint = alias.constraint, }; } return .{ .install_name = install_name, .package_name = install_name, .constraint = constraint, }; } 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 { package_name: []const u8, 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.package_name); 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| { const spec = dependencySpec(item.name, item.constraint_str); if (!self.metadata_cache.contains(spec.package_name)) { var loaded_from_disk = false; if (self.cache_db) |db| { if (db.lookupMetadata(spec.package_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, spec.package_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, spec.package_name)) { already_listed = true; break; } } if (!already_listed) try to_fetch.append(self.allocator, spec.package_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| { const spec = dependencySpec(item.name, item.constraint_str); if (!std.mem.eql(u8, spec.package_name, name)) continue; const constraint = Constraint.parse(spec.constraint) 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_spec = dependencySpec(entry.key_ptr.*, entry.value_ptr.*); if (ctx.resolver.metadata_cache.contains(dep_spec.package_name)) continue; var already_queued = false; for (ctx.prefetch_queue.items) |q| { if (std.mem.eql(u8, q, dep_spec.package_name)) { already_queued = true; break; } } if (!already_queued) ctx.prefetch_queue.append(ctx.allocator, dep_spec.package_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 spec = dependencySpec(item.name, item.constraint_str); const constraint = Constraint.parse(spec.constraint) catch continue; const gop = try all_constraints.getOrPut(spec.install_name); if (!gop.found_existing) { gop.key_ptr.* = try self.allocator.dupe(u8, spec.install_name); gop.value_ptr.* = .{}; } try gop.value_ptr.append(self.allocator, .{ .package_name = try self.allocator.dupe(u8, spec.package_name), .constraint = constraint, .constraint_str = try self.allocator.dupe(u8, spec.constraint), .requester = try self.allocator.dupe(u8, item.requester), .depth = item.depth, }); if (self.metadata_cache.get(spec.package_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| { const opt_spec = dependencySpec(entry.key_ptr.*, entry.value_ptr.*); if (self.metadata_cache.get(opt_spec.package_name)) |opt_meta| { const opt_con = Constraint.parse(opt_spec.constraint) 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 install_name = entry.key_ptr.*; const constraint_list = entry.value_ptr.items; if (constraint_list.len == 0) continue; const package_name = constraint_list[0].package_name; if (self.metadata_cache.get(package_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(install_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)", .{ install_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)", .{ install_name, b.version.major, b.version.minor, b.version.patch, self.countSatisfied(&metadata, b, constraint_list), constraint_list.len, }); } try optimal_versions.put(install_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}@{s}", .{ item.parent_name orelse "", 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}@{s}", .{ pkg_install_path, 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 dep_spec = dependencySpec(name, constraint_str); const constraint = try Constraint.parse(dep_spec.constraint); if (self.resolved.get(dep_spec.install_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(dep_spec.package_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})", .{ dep_spec.install_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(dep_spec.install_name, nested_best, depth, parent); } return existing_pkg; } var metadata = try self.fetchMetadata(dep_spec.package_name); const version_info = blk: { if (optimal_versions.get(dep_spec.install_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(dep_spec.install_name); if (!cons_gop.found_existing) { cons_gop.key_ptr.* = try self.allocator.dupe(u8, dep_spec.install_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(dep_spec.install_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, dep_spec.install_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| { const opt_spec = dependencySpec(entry.key_ptr.*, entry.value_ptr.*); if (self.metadata_cache.get(opt_spec.package_name)) |opt_meta| { const opt_con = Constraint.parse(opt_spec.constraint) 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 dep_spec = dependencySpec(name, constraint_str); const constraint = try Constraint.parse(dep_spec.constraint); if (self.resolved.get(dep_spec.install_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(dep_spec.install_name); if (!cons_gop.found_existing) { cons_gop.key_ptr.* = try self.allocator.dupe(u8, dep_spec.install_name); cons_gop.value_ptr.* = .{}; } try cons_gop.value_ptr.append(self.allocator, constraint); var metadata = try self.fetchMetadata(dep_spec.package_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}", .{ dep_spec.install_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}", .{ dep_spec.install_name, dep_spec.constraint }); return existing_pkg; }; if (!nested_best.matchesPlatform()) return existing_pkg; debug.log(" nested: {s}@{d}.{d}.{d} under {s} (hoisted: {d}.{d}.{d})", .{ dep_spec.install_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(dep_spec.install_name, nested_best, depth, parent); } else { debug.log(" version conflict for {s}: no version satisfies all constraints", .{dep_spec.install_name}); return existing_pkg; } } } const cons_gop = try self.constraints.getOrPut(dep_spec.install_name); if (!cons_gop.found_existing) { cons_gop.key_ptr.* = try self.allocator.dupe(u8, dep_spec.install_name); cons_gop.value_ptr.* = .{}; } try cons_gop.value_ptr.append(self.allocator, constraint); var metadata = try self.fetchMetadata(dep_spec.package_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(dep_spec.install_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, dep_spec.install_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.*; const opt_spec = dependencySpec(dep_name, dep_constraint); if (self.metadata_cache.get(opt_spec.package_name)) |opt_metadata| { const opt_constraint = Constraint.parse(opt_spec.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.*; const opt_spec = dependencySpec(dep_name, dep_constraint); if (self.metadata_cache.get(opt_spec.package_name)) |opt_metadata| { const opt_constraint = Constraint.parse(opt_spec.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 dep_spec = dependencySpec(name, constraint_str); const constraint = try Constraint.parse(dep_spec.constraint); const cons_gop = try self.constraints.getOrPut(dep_spec.install_name); if (!cons_gop.found_existing) { cons_gop.key_ptr.* = try self.allocator.dupe(u8, dep_spec.install_name); cons_gop.value_ptr.* = .{}; } try cons_gop.value_ptr.append(self.allocator, constraint); if (self.resolved.get(dep_spec.install_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(dep_spec.package_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", .{dep_spec.install_name}); return existing_pkg; }; if (best.version.order(existing_pkg.version) != .eq) { debug.log(" re-resolve {s}: {d}.{d}.{d} -> {d}.{d}.{d}", .{ dep_spec.install_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(dep_spec.package_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(dep_spec.install_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, dep_spec.install_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_spec = dependencySpec(dep_name, dep_constraint); const opt_metadata = self.fetchMetadata(opt_spec.package_name) catch continue; const opt_constraint = Constraint.parse(opt_spec.constraint) catch continue; const opt_best = self.selectBestVersion(&opt_metadata, opt_constraint) orelse continue; if (!opt_best.matchesPlatform()) { if (self.resolved.fetchRemove(opt_spec.install_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); } };