wip slow hoister

2 files changed, 78 insertions, 7 deletions

diff --git a/src/install/hoister.zig b/src/install/hoister.zig
new file mode 100644
index 000000000..334f3a7c4
--- /dev/null
+++ b/src/install/hoister.zig
@@ -0,0 +1,69 @@
+usingnamespace @import("../global.zig");
+
+const Lockfile = @import("./install.zig").Lockfile;
+const PackageManager = @import("./install.zig").PackageManager;
+const std = @import("std");
+const PackageID = @import("./install.zig").PackageID;
+const invalid_package_id = @import("./install.zig").invalid_package_id;
+const ExternalSlice = @import("./install.zig").ExternalSlice;
+const Resolution = @import("./resolution.zig").Resolution;
+const PackageNameHash = @import("./install.zig").PackageNameHash;
+
+const Tree = struct {
+    id: Id = invalid_id,
+    package_id: PackageID,
+
+    parent: Id = invalid_id,
+    packages: Lockfile.PackageIDSlice,
+
+    pub const Slice = ExternalSlice(Tree);
+    pub const List = std.ArrayListUnmanaged(Tree);
+    pub const Id = u16;
+    const invalid_id: Id = std.math.maxInt(Id);
+    const dependency_loop = invalid_id - 1;
+
+    // todo: use error type when it no longer takes up extra stack space
+    pub fn addDependency(
+        this: *Tree,
+        name_hash: PackageNameHash,
+        package_id: PackageID,
+        lockfile: *Lockfile,
+        list: *Lockfile.PackageIDList,
+        trees: []Tree,
+        allocator: *std.mem.Allocator,
+    ) Id {
+        if (this.package_id == package_id) return this.id;
+        
+        const this_packages = this.packages.get(name_hashes);
+
+        for (this_packages) |pid, slot| {
+            if (name_hashes[pid] == name_hash) {
+                if (pid != package_id) {
+                    return dependency_loop;
+                }
+
+                return this.id;
+            }
+        }
+
+        var parent = this.parent;
+        while (parent < dependency_loop) {
+            const id = trees[parent].addDependency(name_hash, package_id, lockfile, list, trees);
+            if (id >= dependency_loop) {
+                break;
+            }
+            parent = id;
+        }
+
+        if (parent != this.parent) return parent;
+
+        list.append(allocator, package_id) catch unreachable;
+        this.packages.len += 1;
+        return this.id;
+    }
+};
+
+pub const Hoister = struct {
+    allocator: *std.mem.Allocator,
+    lockfile: *Lockfile,
+};
diff --git a/src/install/install.zig b/src/install/install.zig
index 6b2bfafc2..36afeb8e1 100644
--- a/src/install/install.zig
+++ b/src/install/install.zig
@@ -1322,14 +1322,14 @@ pub const Lockfile = struct {
         _,
     };
 
-    const DependencySlice = ExternalSlice(Dependency);
-    const PackageIDSlice = ExternalSlice(PackageID);
-    const NodeModulesFolderSlice = ExternalSlice(NodeModulesFolder);
+    pub const DependencySlice = ExternalSlice(Dependency);
+    pub const PackageIDSlice = ExternalSlice(PackageID);
+    pub const NodeModulesFolderSlice = ExternalSlice(NodeModulesFolder);
 
-    const PackageIDList = std.ArrayListUnmanaged(PackageID);
-    const DependencyList = std.ArrayListUnmanaged(Dependency);
-    const StringBuffer = std.ArrayListUnmanaged(u8);
-    const SmallExternalStringBuffer = std.ArrayListUnmanaged(String);
+    pub const PackageIDList = std.ArrayListUnmanaged(PackageID);
+    pub const DependencyList = std.ArrayListUnmanaged(Dependency);
+    pub const StringBuffer = std.ArrayListUnmanaged(u8);
+    pub const SmallExternalStringBuffer = std.ArrayListUnmanaged(String);
 
     const NodeModulesFolder = extern struct {
         in: PackageID = 0,
@@ -3695,9 +3695,11 @@ pub const PackageManager = struct {
 
     fn runTasks(
         manager: *PackageManager,
+
         comptime ExtractCompletionContext: type,
         extract_ctx: ExtractCompletionContext,
         comptime callback_fn: anytype,
+        
         comptime log_level: Options.LogLevel,
     ) anyerror!void {
         var batch = ThreadPool.Batch{};