Skip to content

feat(update): implement#452

Merged
zkochan merged 1 commit into
masterfrom
update
Oct 31, 2016
Merged

feat(update): implement#452
zkochan merged 1 commit into
masterfrom
update

Conversation

@zkochan

@zkochan zkochan commented Oct 30, 2016

Copy link
Copy Markdown
Member

Close #300

}

if (!(dependency.justFetched || dependency.firstFetch && options.keypath.length <= options.depth)) {
if (!dependency.justFetched && (!dependency.firstFetch || options.keypath.length >= options.depth)) {

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can you add a comment about this if expression?

@zkochan

zkochan commented Oct 31, 2016

Copy link
Copy Markdown
Member Author

I suggest to also skip cache when doing update

@zkochan zkochan merged commit a840c66 into master Oct 31, 2016
@zkochan zkochan deleted the update branch November 5, 2016 18:20
pull Bot pushed a commit to dwongdev/pnpm that referenced this pull request May 14, 2026
## Summary

Replaces the stub `nm_hoist` (landed in pnpm#448) with a working hoister and the surrounding guardrails: BFS over the result graph pulling every eligible descendant up to the root, plus upfront refusal of inputs the algorithm doesn't yet model.

### What the algorithm models

- **Free hoist.** A transitive dep with no name collision at the root surfaces at the root.
- **Identity dedup.** A dep reachable through multiple parents shares one `Rc` thanks to the wrapper's cache; the hoist preserves that identity and strips the duplicate reference at the other parent path.
- **Parent-wins on version conflict.** When two distinct deps share an alias but resolve to different snapshot keys, the first BFS visitor takes the root slot and the other stays under its declaring parent. Visit order matches the wrapper's alias-sorted insertion order, so the outcome is deterministic.
- **Deep chains flatten in one pass.** `root → a → b → c → d` becomes `root → {a, b, c, d}` — each node, once hoisted, is queued for further descent; its own children evaluate against root's slots rather than against the (now-empty) intermediate parent.
- **O(1) root-slot lookup.** A side `HashMap<String, RcByPtr<HoisterResult>>` mirrors root's direct deps, so the per-edge "is this name taken?" check doesn't degrade to O(N²) `IndexSet` scans on flat graphs.

### Fail-fast guards

The algorithm doesn't yet model peers, hoisting limits, or multi-importer (workspace) hoist trees. Rather than emit a layout pnpm would reject, the wrapper refuses these inputs upfront with three new `HoistError` variants:

- `UnsupportedPeerDependency { ident, peers }` — fires when scanning the constructed `HoisterTree` finds any node with non-empty `peer_names` (either `peerDependencies` from the `packages:` map or `transitive_peer_dependencies` on a `snapshots:` entry).
- `UnsupportedHoistingLimits { len }` — non-empty `opts.hoisting_limits`.
- `UnsupportedWorkspace { extra_importers }` — any importer beyond the root `.`.

Each carries enough context for an operator to identify what triggered it. The `UnsupportedWorkspace` help points at `SymlinkDirectDependencies` — workspaces *do* work in pacquet's wider install path (workspace support landed in pnpm#443 for the isolated linker); only the hoister is restricted.

### Rebase pickup

`collect_importer_deps` carries the `Link`-variant skip introduced by pnpm#443 (workspace support) — `spec.version.as_regular()` extracts the snapshot key for `Regular` deps and `continue`s past `Link` deps, since workspace siblings are direct symlinks materialised by `SymlinkDirectDependencies` and have no snapshot to hoist.

### Performance

Nothing in this PR is reachable from `pacquet install` today (`crates/package-manager/src/install*.rs` doesn't import `pacquet-real-hoist` — the crate is dead code from the install pipeline's perspective until the hoisted-linker wiring lands in later slices). The benchmark results bear that out: cold Frozen Lockfile is within CI variance (+3.2% mean, +3.5% median, driven by one outlier), Hot Cache is 6% *faster* (same `stat → lstat` improvement that shipped in slice 1's `import_indexed_dir`), micro is identical. No code path explains a real regression.

## What's deferred

- Peer-dependency-aware hoisting (`peer_names` constraints, peer-promise satisfaction).
- Multi-round convergence — the BFS handles deep chains in one pass, so the cases requiring true multi-round are limited to peer interactions.
- `hoistingLimits` runtime enforcement.
- `dependencyKind` distinctions for workspaces and external soft links (today only `ExternalSoftLink` placeholders are added by the wrapper and stripped post-hoist; `Workspace`-kind nodes are blocked by the `UnsupportedWorkspace` guard upfront).

## Upstream reference

- [`hoist.ts` algorithm overview](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L1-L51) — the recipe pacquet's single-pass BFS approximates.
- [`hoistTo` main loop](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L329) — the structural intent the port mirrors for the subset above.
pull Bot pushed a commit to dwongdev/pnpm that referenced this pull request May 14, 2026
…npm#461)

## Summary

Lifts the previous `UnsupportedPeerDependency` upfront guard and replaces it with the real peer check from upstream's `getNodeHoistInfo`. The hoister now accepts lockfiles whose packages declare peer dependencies and produces the layout pnpm would: a peer-constrained dep only floats up to the root when doing so doesn't change which package its peers resolve to.

## How it works

- `HoisterResult` carries the input `peer_names` set forward. Upstream's `HoisterResult` doesn't (peer info lives on its intermediate `HoisterWorkTree`); pacquet runs the algorithm on `HoisterResult` directly, so the peer set rides along.

- The hoist driver is a recursive `hoist_subtree` that walks the result graph depth-first. Each recursion receives the candidate parent's *current* ancestor path (`Vec<Rc<HoisterResult>>` exclusive of the parent). After a child's hoist decision is applied, the path passed into the child's recursion reflects its *new* position — a freshly-hoisted child recurses with `[root]`, a child that stayed nested recurses with `parent_path + [parent]`. (An earlier version of this PR used BFS with paths captured at queue time; that path went stale whenever a node was hoisted between being queued and dequeued, leading to over-refused hoists. The recursive form was Copilot's recommendation in code review; the bug regression is pinned by `peer_check_uses_post_hoist_ancestor_path_not_queue_time_path`.)

- `would_shadow_peer` walks that path to decide whether a candidate hoist would change its own peer resolution.

- New `AbsorbDecision::PeerShadow` variant alongside `Free` / `SameNode` / `Conflict`. Fires when:
  1. Root declares the candidate's own name as a peer (root-shadow guard — vacuous today since the wrapper's `.` root has empty `peer_names`, kept for parity).
  2. For each peer name `P` the candidate declares, the closest ancestor providing `P` does so with a different ident than the root's `P`. Promoting the candidate would silently re-resolve the peer.

- The previous `UnsupportedPeerDependency` error variant and `find_first_peer_constrained` upfront scan are gone. The `#[non_exhaustive]` tag stays so future variants can be added without breaking callers.

## DAG-vs-tree caveat

Upstream's `cloneTree` duplicates the work tree into a strict tree per parent path, so each candidate visit has a unique ancestor chain. Pacquet preserves the DAG (its identity-dedup is a feature) and records only the path DFS actually used to reach the candidate. In the rare case where the same `Rc` is reachable through both a peer-compatible and a peer-shadowing path, pacquet refuses to hoist — the layout ends up at most over-nested, never under-nested. The trade-off is documented on `would_shadow_peer`.

## Upstream reference

- [`hoist.ts:414`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L414) — root-shadow guard.
- [`hoist.ts:454-479`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L454-L479) — ancestor-path peer check.
- [`hoist.ts:670`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L670) — `cloneTree`, the per-path-tree shape pacquet skips.

## Test plan

- [x] `peer_constrained_node_stays_under_parent_when_root_provides_different_ident` — `app → widget (peer: react) + react@17`, `root → react@18`. widget cannot hoist because hoisting would change its peer to react@18.
- [x] `peer_constrained_node_hoists_when_ancestor_and_root_agree` — same shape but `app → react@18` matches root's `react@18` (shared `Rc` via wrapper dedup), so widget hoists freely.
- [x] `peer_check_uses_post_hoist_ancestor_path_not_queue_time_path` — regression for the BFS-stale-path bug Copilot caught. `root → app → mid → terminal` (peer: `react`) where `mid` hoists past a conflicting `app.react@17`. Under the previous BFS the stale path `[root, app, mid]` made `terminal`'s peer check trip on `app.react@17 ≠ root.react@18` and refuse the hoist; under DFS the actual post-hoist path `[root, mid]` finds no provider mismatch and `terminal` correctly flattens to root.
- [x] All 10 pre-existing tests still pass (`one_transitive_dep_hoists_to_root`, `diamond_dep_hoists_once_to_root`, `version_conflict_keeps_loser_at_parent`, `deep_chain_flattens_in_one_pass`, `transitive_npm_alias_resolves_target_snapshot`, `non_empty_hoisting_limits_surfaces_unsupported`, `multi_importer_lockfile_surfaces_unsupported_workspace`, `external_dependencies_are_stripped_from_the_result`, `empty_lockfile_yields_empty_root`, `hoist_throws_on_broken_lockfile`).
- [x] The previously-failing `peer_dependency_in_lockfile_surfaces_unsupported` test from pnpm#452 is replaced (peers are no longer an unsupported input).
- [x] All Copilot review threads addressed and resolved (stale ancestor path, misleading comment).
- [x] `just ready` (836 tests pass), `cargo doc --document-private-items`, `taplo format --check`, `just dylint` all clean.
github-actions Bot pushed a commit to Eyalm321/pnpm that referenced this pull request May 18, 2026
## Summary

Replaces the stub `nm_hoist` (landed in pnpm#448) with a working hoister and the surrounding guardrails: BFS over the result graph pulling every eligible descendant up to the root, plus upfront refusal of inputs the algorithm doesn't yet model.

### What the algorithm models

- **Free hoist.** A transitive dep with no name collision at the root surfaces at the root.
- **Identity dedup.** A dep reachable through multiple parents shares one `Rc` thanks to the wrapper's cache; the hoist preserves that identity and strips the duplicate reference at the other parent path.
- **Parent-wins on version conflict.** When two distinct deps share an alias but resolve to different snapshot keys, the first BFS visitor takes the root slot and the other stays under its declaring parent. Visit order matches the wrapper's alias-sorted insertion order, so the outcome is deterministic.
- **Deep chains flatten in one pass.** `root → a → b → c → d` becomes `root → {a, b, c, d}` — each node, once hoisted, is queued for further descent; its own children evaluate against root's slots rather than against the (now-empty) intermediate parent.
- **O(1) root-slot lookup.** A side `HashMap<String, RcByPtr<HoisterResult>>` mirrors root's direct deps, so the per-edge "is this name taken?" check doesn't degrade to O(N²) `IndexSet` scans on flat graphs.

### Fail-fast guards

The algorithm doesn't yet model peers, hoisting limits, or multi-importer (workspace) hoist trees. Rather than emit a layout pnpm would reject, the wrapper refuses these inputs upfront with three new `HoistError` variants:

- `UnsupportedPeerDependency { ident, peers }` — fires when scanning the constructed `HoisterTree` finds any node with non-empty `peer_names` (either `peerDependencies` from the `packages:` map or `transitive_peer_dependencies` on a `snapshots:` entry).
- `UnsupportedHoistingLimits { len }` — non-empty `opts.hoisting_limits`.
- `UnsupportedWorkspace { extra_importers }` — any importer beyond the root `.`.

Each carries enough context for an operator to identify what triggered it. The `UnsupportedWorkspace` help points at `SymlinkDirectDependencies` — workspaces *do* work in pacquet's wider install path (workspace support landed in pnpm#443 for the isolated linker); only the hoister is restricted.

### Rebase pickup

`collect_importer_deps` carries the `Link`-variant skip introduced by pnpm#443 (workspace support) — `spec.version.as_regular()` extracts the snapshot key for `Regular` deps and `continue`s past `Link` deps, since workspace siblings are direct symlinks materialised by `SymlinkDirectDependencies` and have no snapshot to hoist.

### Performance

Nothing in this PR is reachable from `pacquet install` today (`crates/package-manager/src/install*.rs` doesn't import `pacquet-real-hoist` — the crate is dead code from the install pipeline's perspective until the hoisted-linker wiring lands in later slices). The benchmark results bear that out: cold Frozen Lockfile is within CI variance (+3.2% mean, +3.5% median, driven by one outlier), Hot Cache is 6% *faster* (same `stat → lstat` improvement that shipped in slice 1's `import_indexed_dir`), micro is identical. No code path explains a real regression.

## What's deferred

- Peer-dependency-aware hoisting (`peer_names` constraints, peer-promise satisfaction).
- Multi-round convergence — the BFS handles deep chains in one pass, so the cases requiring true multi-round are limited to peer interactions.
- `hoistingLimits` runtime enforcement.
- `dependencyKind` distinctions for workspaces and external soft links (today only `ExternalSoftLink` placeholders are added by the wrapper and stripped post-hoist; `Workspace`-kind nodes are blocked by the `UnsupportedWorkspace` guard upfront).

## Upstream reference

- [`hoist.ts` algorithm overview](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L1-L51) — the recipe pacquet's single-pass BFS approximates.
- [`hoistTo` main loop](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L329) — the structural intent the port mirrors for the subset above.
github-actions Bot pushed a commit to Eyalm321/pnpm that referenced this pull request May 18, 2026
…npm#461)

## Summary

Lifts the previous `UnsupportedPeerDependency` upfront guard and replaces it with the real peer check from upstream's `getNodeHoistInfo`. The hoister now accepts lockfiles whose packages declare peer dependencies and produces the layout pnpm would: a peer-constrained dep only floats up to the root when doing so doesn't change which package its peers resolve to.

## How it works

- `HoisterResult` carries the input `peer_names` set forward. Upstream's `HoisterResult` doesn't (peer info lives on its intermediate `HoisterWorkTree`); pacquet runs the algorithm on `HoisterResult` directly, so the peer set rides along.

- The hoist driver is a recursive `hoist_subtree` that walks the result graph depth-first. Each recursion receives the candidate parent's *current* ancestor path (`Vec<Rc<HoisterResult>>` exclusive of the parent). After a child's hoist decision is applied, the path passed into the child's recursion reflects its *new* position — a freshly-hoisted child recurses with `[root]`, a child that stayed nested recurses with `parent_path + [parent]`. (An earlier version of this PR used BFS with paths captured at queue time; that path went stale whenever a node was hoisted between being queued and dequeued, leading to over-refused hoists. The recursive form was Copilot's recommendation in code review; the bug regression is pinned by `peer_check_uses_post_hoist_ancestor_path_not_queue_time_path`.)

- `would_shadow_peer` walks that path to decide whether a candidate hoist would change its own peer resolution.

- New `AbsorbDecision::PeerShadow` variant alongside `Free` / `SameNode` / `Conflict`. Fires when:
  1. Root declares the candidate's own name as a peer (root-shadow guard — vacuous today since the wrapper's `.` root has empty `peer_names`, kept for parity).
  2. For each peer name `P` the candidate declares, the closest ancestor providing `P` does so with a different ident than the root's `P`. Promoting the candidate would silently re-resolve the peer.

- The previous `UnsupportedPeerDependency` error variant and `find_first_peer_constrained` upfront scan are gone. The `#[non_exhaustive]` tag stays so future variants can be added without breaking callers.

## DAG-vs-tree caveat

Upstream's `cloneTree` duplicates the work tree into a strict tree per parent path, so each candidate visit has a unique ancestor chain. Pacquet preserves the DAG (its identity-dedup is a feature) and records only the path DFS actually used to reach the candidate. In the rare case where the same `Rc` is reachable through both a peer-compatible and a peer-shadowing path, pacquet refuses to hoist — the layout ends up at most over-nested, never under-nested. The trade-off is documented on `would_shadow_peer`.

## Upstream reference

- [`hoist.ts:414`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L414) — root-shadow guard.
- [`hoist.ts:454-479`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L454-L479) — ancestor-path peer check.
- [`hoist.ts:670`](https://github.com/yarnpkg/berry/blob/4287909fa6a0a1ec976a55776bff606864b31990/packages/yarnpkg-nm/sources/hoist.ts#L670) — `cloneTree`, the per-path-tree shape pacquet skips.

## Test plan

- [x] `peer_constrained_node_stays_under_parent_when_root_provides_different_ident` — `app → widget (peer: react) + react@17`, `root → react@18`. widget cannot hoist because hoisting would change its peer to react@18.
- [x] `peer_constrained_node_hoists_when_ancestor_and_root_agree` — same shape but `app → react@18` matches root's `react@18` (shared `Rc` via wrapper dedup), so widget hoists freely.
- [x] `peer_check_uses_post_hoist_ancestor_path_not_queue_time_path` — regression for the BFS-stale-path bug Copilot caught. `root → app → mid → terminal` (peer: `react`) where `mid` hoists past a conflicting `app.react@17`. Under the previous BFS the stale path `[root, app, mid]` made `terminal`'s peer check trip on `app.react@17 ≠ root.react@18` and refuse the hoist; under DFS the actual post-hoist path `[root, mid]` finds no provider mismatch and `terminal` correctly flattens to root.
- [x] All 10 pre-existing tests still pass (`one_transitive_dep_hoists_to_root`, `diamond_dep_hoists_once_to_root`, `version_conflict_keeps_loser_at_parent`, `deep_chain_flattens_in_one_pass`, `transitive_npm_alias_resolves_target_snapshot`, `non_empty_hoisting_limits_surfaces_unsupported`, `multi_importer_lockfile_surfaces_unsupported_workspace`, `external_dependencies_are_stripped_from_the_result`, `empty_lockfile_yields_empty_root`, `hoist_throws_on_broken_lockfile`).
- [x] The previously-failing `peer_dependency_in_lockfile_surfaces_unsupported` test from pnpm#452 is replaced (peers are no longer an unsupported input).
- [x] All Copilot review threads addressed and resolved (stale ancestor path, misleading comment).
- [x] `just ready` (836 tests pass), `cargo doc --document-private-items`, `taplo format --check`, `just dylint` all clean.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants