8000 fix(ls): correctly show deduped dependencies by milaninfy · Pull Request #8217 · npm/cli · GitHub
[go: up one dir, main page]
Skip to content

fix(ls): correctly show deduped dependencies #8217

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
wants to merge 1 commit into
base: latest
Choose a base branch
from
Open

fix(ls): correctly show deduped dependencies #8217

wants to merge 1 commit into from
+153 −125

Conversation

milaninfy
Copy link
Contributor
@milaninfy milaninfy commented Apr 9, 2025 •
edited
Loading

Attempt to fix npm ls output

Problem:

  • deduped nodes are cloned when encountered using previously seen nodes set but they are not explored further when we are requesting npm ls dep-name if dep-name is a child of some deduped parent then whole tree would be shown till that parent but logically dep-name is still the child/grand-child of that.
  • When deduped nodes are explored further it results in cycle when dep1 is ancestor of dep2 which again depends on dep1 creating a cycle when explored, also the algorithm used is BFS so it's hard to detect cycle.

Solution:

  • Use DFS like approach with custom cycle detection checks.
    • keep track of how any node is discovered. so each node or parent node will have a list containing all the relevant visited nodes, we check if current node is in that list then it's a cycle and we don't need to explore this node.
  • This solution attempts to explore cloned nodes of deduped nodes and use cached result so that it fixes the output and perform better. since those nodes are deduped and already explored we can use the result.

Progress:

  • still some cases which might result in Infinite loop and need to discovered those.
  • very slow and uses very large memory during run when ran on big repo, need to find out optimizations or better approach
  • Fix/add the test cases
  • Refactor

Test output

`npm ls child` - before and after 
~/workarea/rep/repro $ npm ls child
repro@1.0.0 /Users/milaninfy/workarea/rep/repro
└─┬ relative-p2@1.0.0
  └─┬ grand-p1@1.0.0
    └─┬ parent-p1@1.0.0
      └── child@1.0.0

~/workarea/rep/repro $ lnpm ls child
repro@1.0.0 /Users/milaninfy/workarea/rep/repro
├─┬ relative-p1@1.0.0
│ └─┬ family@1.0.0
│   └─┬ grand-p1@1.0.0
│     └─┬ parent-p1@1.0.0
│       └── child@1.0.0
└─┬ relative-p2@1.0.0
  └─┬ grand-p1@1.0.0 deduped
    └─┬ parent-p1@1.0.0 deduped
      └── child@1.0.0 deduped

fixes: #7917

@milaninfy milaninfy force-pushed the mm/fix-ls branch 3 times, most recently from fb7ba8e to 1ff339c Compare May 8, 2025 16:45
@milaninfy milaninfy marked this pull request as ready for review June 4, 2025 17:17
@milaninfy milaninfy requested a review from a team as a code owner June 4, 2025 17:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

[BUG] npm ls only listing dev dependencies by default
1 participant
@milaninfy
0