pnpm
diff --git a/‎crates/graph-hasher/src/dep_state.rs‎
Lines changed: 268 additions & 1 deletion b/‎crates/graph-hasher/src/dep_state.rs‎
Lines changed: 268 additions & 1 deletion
@@ -131,9 +131,78 @@ where
     cache.get(dep_path).expect("just inserted").clone()
 }
 
+/// Recursive helper used by [`crate::calc_graph_node_hash`] to decide
+/// whether a snapshot's engine string should contribute to its global-
+/// virtual-store hash. Mirrors upstream's
+/// [`transitivelyRequiresBuild`](https://github.com/pnpm/pnpm/blob/94240bc046/deps/graph-hasher/src/index.ts#L221-L249).
+///
+/// Returns `true` if `dep_path` is either in `built_dep_paths`
+/// directly, or transitively depends on a snapshot that is. The
+/// returned boolean drives `includeEngine` at upstream's
+/// [`calcGraphNodeHash`](https://github.com/pnpm/pnpm/blob/94240bc046/deps/graph-hasher/src/index.ts#L140-L142)
+/// — pure-JS leaves (and their pure-JS ancestors) get
+/// `engine = null`, so their GVS hashes survive Node.js upgrades and
+/// architecture moves. Snapshots that *might* run a postinstall
+/// script keep `engine = ENGINE_NAME` so the hash partitions them by
+/// host environment.
+///
+/// The cycle guard uses `dep_path` itself, not `node.full_pkg_id`
+/// (unlike [`calc_dep_graph_hash`]). Upstream picked `depPath`
+/// because the same pkg id reachable through two different peer
+/// contexts is two distinct nodes — once one is mid-walk we still
+/// want to recurse into the other.
+///
+/// On cycle hit (`parents.contains(dep_path)`) the function returns
+/// `false` *without* caching. The "false in this particular cycle
+/// rotation" answer isn't the canonical one — a sibling visit might
+/// still find a builder upstream, and caching `false` here would
+/// poison the next visit at the same key.
+///
+/// `cache` is install-scoped and threaded across every snapshot
+/// visited inside one [`crate::calc_graph_node_hash`] walk. `parents`
+/// is the per-walk cycle-tracking set — callers always pass a fresh
+/// empty `HashSet`, the function inserts/removes `dep_path` around
+/// the recursion.
+pub(crate) fn transitively_requires_build<K>(
+    graph: &HashMap<K, DepsGraphNode<K>>,
+    built_dep_paths: &HashSet<K>,
+    cache: &mut HashMap<K, bool>,
+    dep_path: &K,
+    parents: &mut HashSet<K>,
+) -> bool
+where
+    K: Clone + Eq + std::hash::Hash,
+{
+    if let Some(&cached) = cache.get(dep_path) {
+        return cached;
+    }
+    if built_dep_paths.contains(dep_path) {
+        cache.insert(dep_path.clone(), true);
+        return true;
+    }
+    let Some(node) = graph.get(dep_path) else {
+        cache.insert(dep_path.clone(), false);
+        return false;
+    };
+    if parents.contains(dep_path) {
+        return false;
+    }
+    parents.insert(dep_path.clone());
+    let mut result = false;
+    for child in node.children.values() {
+        if transitively_requires_build(graph, built_dep_paths, cache, child, parents) {
+            result = true;
+            break;
+        }
+    }
+    parents.remove(dep_path);
+    cache.insert(dep_path.clone(), result);
+    result
+}
+
 #[cfg(test)]
 mod tests {
-    use super::{CalcDepStateOptions, DepsGraphNode, calc_dep_state};
+    use super::{CalcDepStateOptions, DepsGraphNode, calc_dep_state, transitively_requires_build};
     use pretty_assertions::assert_eq;
     use std::collections::HashMap;
 
@@ -338,4 +407,202 @@ mod tests {
         let patch_pos = result.find(";patch=").expect("patch section present");
         assert!(deps_pos < patch_pos, "deps must come before patch in {result:?}");
     }
+
+    /// Self-hit: a snapshot listed in `built_dep_paths` returns
+    /// `true` and caches `true` without looking at its children.
+    #[test]
+    fn transitively_requires_build_self_in_built_set() {
+        let mut graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-b".to_string(),
+                children: HashMap::new(),
+            },
+        );
+        let built: std::collections::HashSet<String> =
+            ["[email protected]".to_string()].into_iter().collect();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+        assert_eq!(cache.get("[email protected]"), Some(&true));
+    }
+
+    /// Transitive: a snapshot whose child is a builder returns
+    /// `true` and caches `true` at every level walked.
+    #[test]
+    fn transitively_requires_build_walks_to_descendant_builder() {
+        let mut graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        let mut root_children = HashMap::new();
+        root_children.insert("dep".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-r".to_string(),
+                children: root_children,
+            },
+        );
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-b".to_string(),
+                children: HashMap::new(),
+            },
+        );
+        let built: std::collections::HashSet<String> =
+            ["[email protected]".to_string()].into_iter().collect();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+        assert_eq!(cache.get("[email protected]"), Some(&true));
+        assert_eq!(cache.get("[email protected]"), Some(&true));
+    }
+
+    /// Unrelated: a snapshot whose subtree contains no builder
+    /// returns `false` and caches `false` at every visited node.
+    #[test]
+    fn transitively_requires_build_returns_false_for_unrelated_tree() {
+        let mut graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        let mut root_children = HashMap::new();
+        root_children.insert("dep".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-r".to_string(),
+                children: root_children,
+            },
+        );
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-l".to_string(),
+                children: HashMap::new(),
+            },
+        );
+        let built: std::collections::HashSet<String> =
+            ["[email protected]".to_string()].into_iter().collect();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(!transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+        assert_eq!(cache.get("[email protected]"), Some(&false));
+        assert_eq!(cache.get("[email protected]"), Some(&false));
+    }
+
+    /// Missing node: returns `false` and caches `false`. Mirrors
+    /// upstream's `if (!node) { cache[depPath] = false; return false }`
+    /// branch — the install-time graph build can drop entries for
+    /// resolutions the linker rejects later, so the walker must not
+    /// panic on missing keys.
+    #[test]
+    fn transitively_requires_build_caches_false_for_missing_node() {
+        let graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        let built: std::collections::HashSet<String> = std::collections::HashSet::new();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(!transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+        assert_eq!(cache.get("[email protected]"), Some(&false));
+    }
+
+    /// Cycle: a → b → a with no builder anywhere. The walk must
+    /// terminate and return `false`. Cache state on `a` is `false`
+    /// (the post-loop write), `b` is also `false`. The cycle short
+    /// circuit at upstream's `if (parents.has(depPath)) return false`
+    /// fires once but doesn't taint the eventual cache write at
+    /// the frame that owns `a`.
+    #[test]
+    fn transitively_requires_build_cycle_terminates() {
+        let mut graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        let mut a_children = HashMap::new();
+        a_children.insert("b".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode { full_pkg_id: "[email protected]:sha512-a".to_string(), children: a_children },
+        );
+        let mut b_children = HashMap::new();
+        b_children.insert("a".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode { full_pkg_id: "[email protected]:sha512-b".to_string(), children: b_children },
+        );
+        let built: std::collections::HashSet<String> = std::collections::HashSet::new();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(!transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+        assert_eq!(cache.get("[email protected]"), Some(&false));
+        assert_eq!(cache.get("[email protected]"), Some(&false));
+        assert!(parents.is_empty(), "parents set must be restored to empty");
+    }
+
+    /// Cycle with builder elsewhere in the tree: `a → b → a` plus
+    /// `a → builder`. The cycle must not short-circuit `a`'s overall
+    /// answer to `false` — the sibling builder visit still drives
+    /// `a` to `true`. Verifies that the no-cache-on-cycle behaviour
+    /// is what makes this work.
+    #[test]
+    fn transitively_requires_build_cycle_does_not_mask_sibling_builder() {
+        let mut graph: HashMap<String, DepsGraphNode<String>> = HashMap::new();
+        // Use a BTreeMap-style two-key insert so child iteration
+        // order can take either path; both must yield `true`.
+        let mut a_children = HashMap::new();
+        a_children.insert("b".to_string(), "[email protected]".to_string());
+        a_children.insert("c".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode { full_pkg_id: "[email protected]:sha512-a".to_string(), children: a_children },
+        );
+        let mut b_children = HashMap::new();
+        b_children.insert("a".to_string(), "[email protected]".to_string());
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode { full_pkg_id: "[email protected]:sha512-b".to_string(), children: b_children },
+        );
+        graph.insert(
+            "[email protected]".to_string(),
+            DepsGraphNode {
+                full_pkg_id: "[email protected]:sha512-x".to_string(),
+                children: HashMap::new(),
+            },
+        );
+        let built: std::collections::HashSet<String> =
+            ["[email protected]".to_string()].into_iter().collect();
+        let mut cache = HashMap::new();
+        let mut parents = std::collections::HashSet::new();
+        assert!(transitively_requires_build(
+            &graph,
+            &built,
+            &mut cache,
+            &"[email protected]".to_string(),
+            &mut parents
+        ));
+    }
 }