cli
cli copied to clipboard
fix(ls): correctly show deduped dependencies
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-nameifdep-nameis a child of some deduped parent then whole tree would be shown till that parent but logicallydep-nameis still the child/grand-child of that. - When deduped nodes are explored further it results in cycle when
dep1is ancestor ofdep2which again depends ondep1creating 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:
- [x] still some cases which might result in Infinite loop and need to discovered those.
- [x] very slow and uses very large memory during run when ran on big repo, need to find out optimizations or better approach
- [x] Fix/add the test cases
- [x] Refactor
Test output
`npm ls child` - before and after
~/workarea/rep/repro $ npm ls child
[email protected] /Users/milaninfy/workarea/rep/repro
└─┬ [email protected]
└─┬ [email protected]
└─┬ [email protected]
└── [email protected]
~/workarea/rep/repro $ lnpm ls child
[email protected] /Users/milaninfy/workarea/rep/repro
├─┬ [email protected]
│ └─┬ [email protected]
│ └─┬ [email protected]
│ └─┬ [email protected]
│ └── [email protected]
└─┬ [email protected]
└─┬ [email protected] deduped
└─┬ [email protected] deduped
└── [email protected] deduped
fixes: https://github.com/npm/cli/issues/7917