resolve duplicate npm dependencies correctly (#1970)

* resolve duplicate npm dependencies correctly

fixes #1952

* modify the correct reference

3 files changed, 90 insertions, 142 deletions

diff --git a/src/install/install.zig b/src/install/install.zig
index 7ec5fe378..2c98666df 100644
--- a/src/install/install.zig
+++ b/src/install/install.zig
@@ -117,7 +117,7 @@ pub fn ExternalSliceAligned(comptime Type: type, comptime alignment_: ?u29) type
         }
 
         pub fn init(buf: []const Type, in: []const Type) Slice {
-            // if (comptime isDebug or isTest) {
+            // if (comptime Environment.allow_assert) {
             //     std.debug.assert(@ptrToInt(buf.ptr) <= @ptrToInt(in.ptr));
             //     std.debug.assert((@ptrToInt(in.ptr) + in.len) <= (@ptrToInt(buf.ptr) + buf.len));
             // }
@@ -132,7 +132,6 @@ pub fn ExternalSliceAligned(comptime Type: type, comptime alignment_: ?u29) type
 
 pub const PackageID = u32;
 pub const DependencyID = u32;
-pub const PackageIDMultiple = [*:invalid_package_id]PackageID;
 pub const invalid_package_id = std.math.maxInt(PackageID);
 
 pub const ExternalStringList = ExternalSlice(ExternalString);
@@ -2232,36 +2231,26 @@ pub const PackageManager = struct {
 
         if (comptime Environment.allow_assert) std.debug.assert(package.meta.id != invalid_package_id);
         defer successFn(this, dependency_id, package.meta.id);
-        switch (preinstall) {
+        return switch (preinstall) {
             // Is this package already in the cache?
             // We don't need to download the tarball, but we should enqueue dependencies
-            .done => {
-                return ResolvedPackageResult{ .package = package, .is_first_time = true };
-            },
-
+            .done => .{ .package = package, .is_first_time = true },
             // Do we need to download the tarball?
-            .extract => {
-                const task_id = Task.Id.forNPMPackage(
-                    Task.Tag.extract,
-                    this.lockfile.str(&name),
-                    package.resolution.value.npm.version,
-                );
-
-                if (try this.generateNetworkTaskForTarball(task_id, manifest.str(&find_result.package.tarball_url), package)) |network_task| {
-                    return ResolvedPackageResult{
-                        .package = package,
-                        .is_first_time = true,
-                        .network_task = network_task,
-                    };
-                }
-
-                // if we are in the middle of extracting this package, we should wait for it to finish
-                return ResolvedPackageResult{ .package = package };
+            .extract => .{
+                .package = package,
+                .is_first_time = true,
+                .network_task = try this.generateNetworkTaskForTarball(
+                    Task.Id.forNPMPackage(
+                        Task.Tag.extract,
+                        this.lockfile.str(&name),
+                        package.resolution.value.npm.version,
+                    ),
+                    manifest.str(&find_result.package.tarball_url),
+                    package,
+                ) orelse unreachable,
             },
             else => unreachable,
-        }
-
-        return ResolvedPackageResult{ .package = package };
+        };
     }
 
     pub fn generateNetworkTaskForTarball(this: *PackageManager, task_id: u64, url: string, package: Lockfile.Package) !?*NetworkTask {
@@ -2320,19 +2309,30 @@ pub const PackageManager = struct {
     const SuccessFn = *const fn (*PackageManager, PackageID, PackageID) void;
     const FailFn = *const fn (*PackageManager, *const Dependency, PackageID, anyerror) void;
     fn assignResolution(this: *PackageManager, dependency_id: PackageID, package_id: PackageID) void {
+        if (comptime Environment.allow_assert) {
+            std.debug.assert(dependency_id < this.lockfile.buffers.resolutions.items.len);
+            std.debug.assert(package_id < this.lockfile.packages.len);
+            std.debug.assert(this.lockfile.buffers.resolutions.items[dependency_id] == invalid_package_id);
+        }
         this.lockfile.buffers.resolutions.items[dependency_id] = package_id;
     }
 
     fn assignRootResolution(this: *PackageManager, dependency_id: PackageID, package_id: PackageID) void {
+        if (comptime Environment.allow_assert) {
+            std.debug.assert(package_id < this.lockfile.packages.len);
+        }
         if (this.dynamic_root_dependencies) |*dynamic| {
+            if (comptime Environment.allow_assert) {
+                std.debug.assert(dependency_id < dynamic.items.len);
+                std.debug.assert(dynamic.items[dependency_id].resolution_id == invalid_package_id);
+            }
             dynamic.items[dependency_id].resolution_id = package_id;
         } else {
-            if (this.lockfile.buffers.resolutions.items.len > dependency_id) {
-                this.lockfile.buffers.resolutions.items[dependency_id] = package_id;
-            } else {
-                // this means a bug
-                bun.unreachablePanic("assignRootResolution: dependency_id: {d} out of bounds (package_id: {d})", .{ dependency_id, package_id });
+            if (comptime Environment.allow_assert) {
+                std.debug.assert(dependency_id < this.lockfile.buffers.resolutions.items.len);
+                std.debug.assert(this.lockfile.buffers.resolutions.items[dependency_id] == invalid_package_id);
             }
+            this.lockfile.buffers.resolutions.items[dependency_id] = package_id;
         }
     }
 
@@ -2581,7 +2581,7 @@ pub const PackageManager = struct {
         const name = dependency.realname();
 
         const name_hash = switch (dependency.version.tag) {
-            .dist_tag, .npm, .github => Lockfile.stringHash(this.lockfile.str(&name)),
+            .dist_tag, .npm, .github => String.Builder.stringHash(this.lockfile.str(&name)),
             else => dependency.name_hash,
         };
         const version = dependency.version;
@@ -2772,7 +2772,7 @@ pub const PackageManager = struct {
                                 this.enqueueNetworkTask(network_task);
                             }
 
-                            if (comptime Environment.isDebug) std.debug.assert(task_id != 0);
+                            if (comptime Environment.allow_assert) std.debug.assert(task_id != 0);
 
                             var manifest_entry_parse = try this.task_queue.getOrPutContext(this.allocator, task_id, .{});
                             if (!manifest_entry_parse.found_existing) {
@@ -2870,7 +2870,7 @@ pub const PackageManager = struct {
                     }
 
                     // should not trigger a network call
-                    std.debug.assert(result.network_task == null);
+                    if (comptime Environment.allow_assert) std.debug.assert(result.network_task == null);
                 } else if (dependency.behavior.isRequired()) {
                     this.log.addErrorFmt(
                         null,
@@ -3177,6 +3177,7 @@ pub const PackageManager = struct {
 
         while (manager.network_channel.tryReadItem() catch null) |task_| {
             var task: *NetworkTask = task_;
+            if (comptime Environment.allow_assert) std.debug.assert(manager.pending_tasks > 0);
             manager.pending_tasks -|= 1;
 
             switch (task.callback) {
@@ -3476,7 +3477,8 @@ pub const PackageManager = struct {
         }
 
         while (manager.resolve_tasks.tryReadItem() catch null) |task_| {
-            manager.pending_tasks -= 1;
+            if (comptime Environment.allow_assert) std.debug.assert(manager.pending_tasks > 0);
+            manager.pending_tasks -|= 1;
 
             var task: Task = task_;
             if (task.log.msgs.items.len > 0) {
@@ -6089,7 +6091,7 @@ pub const PackageManager = struct {
                                     );
                                 },
                                 .npm => {
-                                    std.debug.assert(resolution.value.npm.url.len() > 0);
+                                    if (comptime Environment.allow_assert) std.debug.assert(!resolution.value.npm.url.isEmpty());
                                     this.manager.enqueuePackageForDownload(
                                         name,
                                         package_id,
diff --git a/src/install/lockfile.zig b/src/install/lockfile.zig
index 9e1f29c40..084ad7616 100644
--- a/src/install/lockfile.zig
+++ b/src/install/lockfile.zig
@@ -78,7 +78,6 @@ const initializeStore = @import("./install.zig").initializeStore;
 const invalid_package_id = @import("./install.zig").invalid_package_id;
 const JSAst = bun.JSAst;
 const Origin = @import("./install.zig").Origin;
-const PackageIDMultiple = @import("./install.zig").PackageIDMultiple;
 const Crypto = @import("../sha.zig").Hashers;
 pub const MetaHash = [std.crypto.hash.sha2.Sha512256.digest_length]u8;
 const zero_hash = std.mem.zeroes(MetaHash);
@@ -441,7 +440,7 @@ pub const Tree = struct {
         if (resolutions.len == 0) return;
 
         const name_hashes: []const PackageNameHash = builder.name_hashes;
-        const max_package_id = name_hashes.len;
+        const max_package_id = @truncate(PackageID, name_hashes.len);
         const dependencies: []const Dependency = builder.dependencies[resolution_list.off..][0..resolution_list.len];
 
         for (resolutions) |pid, j| {
@@ -759,7 +758,7 @@ const Cloner = struct {
 
             const mapping = this.mapping[to_clone.old_resolution];
             if (mapping < max_package_id) {
-                this.lockfile.buffers.resolutions.items[to_clone.resolve_id] = this.mapping[to_clone.old_resolution];
+                this.lockfile.buffers.resolutions.items[to_clone.resolve_id] = mapping;
                 continue;
             }
 
@@ -1391,14 +1390,14 @@ pub fn verifyData(this: *Lockfile) !void {
         while (i < this.packages.len) : (i += 1) {
             const package: Lockfile.Package = this.packages.get(i);
             std.debug.assert(this.str(&package.name).len == @as(usize, package.name.len()));
-            std.debug.assert(stringHash(this.str(&package.name)) == @as(usize, package.name_hash));
+            std.debug.assert(String.Builder.stringHash(this.str(&package.name)) == @as(usize, package.name_hash));
             std.debug.assert(package.dependencies.get(this.buffers.dependencies.items).len == @as(usize, package.dependencies.len));
             std.debug.assert(package.resolutions.get(this.buffers.resolutions.items).len == @as(usize, package.resolutions.len));
             std.debug.assert(package.resolutions.get(this.buffers.resolutions.items).len == @as(usize, package.dependencies.len));
             const dependencies = package.dependencies.get(this.buffers.dependencies.items);
             for (dependencies) |dependency| {
                 std.debug.assert(this.str(&dependency.name).len == @as(usize, dependency.name.len()));
-                std.debug.assert(stringHash(this.str(&dependency.name)) == dependency.name_hash);
+                std.debug.assert(String.Builder.stringHash(this.str(&dependency.name)) == dependency.name_hash);
             }
         }
     }
@@ -1538,49 +1537,33 @@ pub fn getPackageID(
 ) ?PackageID {
     const entry = this.package_index.get(name_hash) orelse return null;
     const resolutions: []const Resolution = this.packages.items(.resolution);
+    const npm_version = if (version) |v| switch (v.tag) {
+        .npm => v.value.npm.version,
+        else => null,
+    } else null;
+
     switch (entry) {
         .PackageID => |id| {
-            if (comptime Environment.isDebug or Environment.isTest) {
-                std.debug.assert(id != invalid_package_id);
-                std.debug.assert(id != invalid_package_id - 1);
-            }
+            if (comptime Environment.allow_assert) std.debug.assert(id < resolutions.len);
 
-            if (id < resolutions.len and resolutions[id].eql(
-                resolution,
-                this.buffers.string_bytes.items,
-                this.buffers.string_bytes.items,
-            )) {
+            if (resolutions[id].eql(resolution, this.buffers.string_bytes.items, this.buffers.string_bytes.items)) {
                 return id;
-            } else if (version) |version_| {
-                switch (version_.tag) {
-                    .npm => {
-                        // is it a peerDependency satisfied by a parent package?
-                        if (version_.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
-                            return id;
-                        }
-                    },
-                    else => return null,
-                }
             }
-        },
-        .PackageIDMultiple => |multi_| {
-            const multi = std.mem.span(multi_);
-
-            const can_satisfy = version != null and version.?.tag == .npm;
 
-            for (multi) |id| {
-                if (comptime Environment.isDebug or Environment.isTest) {
-                    std.debug.assert(id != invalid_package_id);
-                }
-
-                if (id >= resolutions.len) return null;
+            if (npm_version) |range| {
+                if (range.satisfies(resolutions[id].value.npm.version)) return id;
+            }
+        },
+        .PackageIDMultiple => |ids| {
+            for (ids.items) |id| {
+                if (comptime Environment.allow_assert) std.debug.assert(id < resolutions.len);
 
                 if (resolutions[id].eql(resolution, this.buffers.string_bytes.items, this.buffers.string_bytes.items)) {
                     return id;
                 }
 
-                if (can_satisfy and version.?.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
-                    return id;
+                if (npm_version) |range| {
+                    if (range.satisfies(resolutions[id].value.npm.version)) return id;
                 }
             }
         },
@@ -1599,48 +1582,18 @@ pub fn getOrPutID(this: *Lockfile, id: PackageID, name_hash: PackageNameHash) !v
         this.unique_packages.unset(id);
 
         switch (index.*) {
-            .PackageID => |single_| {
-                var ids = try this.allocator.alloc(PackageID, 8);
-                std.mem.set(PackageID, ids, invalid_package_id - 1);
-
-                ids[0] = single_;
-                ids[1] = id;
-                this.unique_packages.unset(single_);
+            .PackageID => |single| {
+                this.unique_packages.unset(single);
 
-                // stage1 compiler doesn't like this
-                ids[7] = invalid_package_id;
-                var ids_sentinel = ids.ptr[0 .. ids.len - 1 :invalid_package_id];
+                var ids = try PackageIDList.initCapacity(this.allocator, 8);
+                ids.appendAssumeCapacity(single);
+                ids.appendAssumeCapacity(id);
                 index.* = .{
-                    .PackageIDMultiple = ids_sentinel,
+                    .PackageIDMultiple = ids,
                 };
             },
-            .PackageIDMultiple => |ids_| {
-                var ids = bun.sliceTo(ids_, invalid_package_id - 1);
-                for (ids) |id2, i| {
-                    if (id2 == invalid_package_id - 1) {
-                        ids[i] = id;
-                        return;
-                    }
-                }
-
-                var new_ids = try this.allocator.alloc(PackageID, ids.len + 8);
-                std.mem.set(PackageID, new_ids, invalid_package_id - 1);
-
-                defer this.allocator.free(ids);
-                for (ids) |id2, i| {
-                    new_ids[i] = id2;
-                }
-                new_ids[ids.len - 1] = id;
-                for (new_ids[ids.len .. new_ids.len - 2]) |_, i| {
-                    new_ids[i + ids.len] = invalid_package_id - 1;
-                }
-
-                // stage1 compiler doesn't like this
-                new_ids[new_ids.len - 1] = invalid_package_id;
-                var new_ids_sentinel = new_ids.ptr[0 .. new_ids.len - 1 :invalid_package_id];
-                index.* = .{
-                    .PackageIDMultiple = new_ids_sentinel,
-                };
+            .PackageIDMultiple => {
+                try index.PackageIDMultiple.append(this.allocator, id);
             },
         }
     } else {
@@ -1670,12 +1623,8 @@ fn appendPackageWithID(this: *Lockfile, package_: Lockfile.Package, id: PackageI
 
 const StringPool = String.Builder.StringPool;
 
-pub inline fn stringHash(in: []const u8) u64 {
-    return std.hash.Wyhash.hash(0, in);
-}
-
 pub inline fn stringBuilder(this: *Lockfile) Lockfile.StringBuilder {
-    return Lockfile.StringBuilder{
+    return .{
         .lockfile = this,
     };
 }
@@ -1708,7 +1657,7 @@ pub const StringBuilder = struct {
 
     pub inline fn count(this: *StringBuilder, slice: string) void {
         if (String.canInline(slice)) return;
-        return countWithHash(this, slice, stringHash(slice));
+        return countWithHash(this, slice, String.Builder.stringHash(slice));
     }
 
     pub inline fn countWithHash(this: *StringBuilder, slice: string, hash: u64) void {
@@ -1743,7 +1692,7 @@ pub const StringBuilder = struct {
     }
 
     pub fn append(this: *StringBuilder, comptime Type: type, slice: string) Type {
-        return @call(.always_inline, appendWithHash, .{ this, Type, slice, stringHash(slice) });
+        return @call(.always_inline, appendWithHash, .{ this, Type, slice, String.Builder.stringHash(slice) });
     }
 
     // SlicedString is not supported due to inline strings.
@@ -1825,7 +1774,7 @@ pub const PackageIndex = struct {
     pub const Map = std.HashMap(PackageNameHash, PackageIndex.Entry, IdentityContext(PackageNameHash), 80);
     pub const Entry = union(Tag) {
         PackageID: PackageID,
-        PackageIDMultiple: PackageIDMultiple,
+        PackageIDMultiple: PackageIDList,
 
         pub const Tag = enum(u8) {
             PackageID = 0,
@@ -3624,34 +3573,31 @@ pub fn generateMetaHash(this: *Lockfile, print_name_version_string: bool) !MetaH
 }
 
 pub fn resolve(this: *Lockfile, package_name: []const u8, version: Dependency.Version) ?PackageID {
-    const name_hash = bun.hash(package_name);
+    const name_hash = String.Builder.stringHash(package_name);
     const entry = this.package_index.get(name_hash) orelse return null;
-    const can_satisfy = version.tag == .npm;
 
-    switch (entry) {
-        .PackageID => |id| {
-            const resolutions = this.packages.items(.resolution);
+    switch (version.tag) {
+        .npm => switch (entry) {
+            .PackageID => |id| {
+                const resolutions = this.packages.items(.resolution);
 
-            if (can_satisfy and version.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
-                return id;
-            }
-        },
-        .PackageIDMultiple => |multi_| {
-            const multi = std.mem.span(multi_);
-            const resolutions = this.packages.items(.resolution);
-
-            for (multi) |id| {
-                if (comptime Environment.isDebug or Environment.isTest) {
-                    std.debug.assert(id != invalid_package_id);
+                if (comptime Environment.allow_assert) std.debug.assert(id < resolutions.len);
+                if (version.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
+                    return id;
                 }
+            },
+            .PackageIDMultiple => |ids| {
+                const resolutions = this.packages.items(.resolution);
 
-                if (id == invalid_package_id - 1) return null;
-
-                if (can_satisfy and version.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
-                    return id;
+                for (ids.items) |id| {
+                    if (comptime Environment.allow_assert) std.debug.assert(id < resolutions.len);
+                    if (version.value.npm.version.satisfies(resolutions[id].value.npm.version)) {
+                        return id;
+                    }
                 }
-            }
+            },
         },
+        else => {},
     }
 
     return null;
diff --git a/src/resolver/package_json.zig b/src/resolver/package_json.zig
index 9a0aea6a2..ec7c94816 100644
--- a/src/resolver/package_json.zig
+++ b/src/resolver/package_json.zig
@@ -887,7 +887,7 @@ pub const PackageJSON = struct {
                                         const dependency = Dependency{
                                             .name = name,
                                             .version = dependency_version,
-                                            .name_hash = bun.hash(name_str),
+                                            .name_hash = String.Builder.stringHash(name_str),
                                             .behavior = group.behavior,
                                         };
                                         package_json.dependencies.map.putAssumeCapacityContext(