import { PackageLockPackage } from './types' ; /**
 * Hoist package-lock dependencies in-place
 *
 * This happens in two phases:
 *
 * 1) Move every package into the parent scope (as long as it introduces no conflicts).
 *    This step mutates the dependency tree.
 * 2) Once no more packages can be moved up, clean up the tree. This step mutates the
 *    tree declarations but cannot change versions of required packages. Two cleanups:
 *    2a) Remove duplicates down the tree (same version that is inherited from above)
 *    2b) Remove useless packages that aren't depended upon by anything in that subtree.
 *        To determine whether a package is useful or useless in a tree, we record
 *        each package's original dependencies before we start messing around in the
 *        tree.
 *
 * This two-phase process replaces a proces that did move-and-delete as one step, which
 * sometimes would hoist a package into a place that was previously vacated by a conflicting
 * version, thereby causing the wrong version to be loaded.
 *
 * Hoisting is still rather expensive on a large tree (~100ms), we should find ways to
 * speed it up.
 */ export function hoistDependencies ( packageTree ) { const originalDependencies = new Map < PackageLockPackage , string [ ] > ( ) ; recordOriginalDependencies ( packageTree ) ; moveUp ( packageTree ) ; removeDupes ( packageTree , [ ] ) ; removeUseless ( packageTree ) ; function moveUp ( node , parent ? ) { if ( ! node . dependencies ) { return ; } for ( const child of Object . values ( node . dependencies ) ) { moveUp ( child , node ) ; } if ( parent ) { for ( const [ depName , depPackage ] of Object . entries ( node . dependencies ) ) { if ( ! parent . dependencies ?. [ depName ] ) { parent . dependencies ! [ depName ] = depPackage ; } } } } function removeDupes ( node , rootPath ) { if ( ! node . dependencies ) { return ; } for ( const [ depName , depPackage ] of Object . entries ( node . dependencies ) ) { if ( findInheritedDepVersion ( depName , rootPath ) === depPackage . version ) { delete node . dependencies [ depName ] ; } } for ( const child of Object . values ( node . dependencies ) ) { removeDupes ( child , [ node , ... rootPath ] ) ; } } function removeUseless ( node ) { if ( ! node . dependencies ) { return ; } for ( const [ depName , depPkg ] of Object . entries ( node . dependencies ) ) { if ( ! necessaryInTree ( depName , depPkg . version , node ) ) { delete node . dependencies [ depName ] ; } } for ( const child of Object . values ( node . dependencies ) ) { removeUseless ( child ) ; } if ( Object . keys ( node . dependencies ) . length === 0 ) { delete node . dependencies ; } } function findInheritedDepVersion ( name , parentDependenciesChain ) { for ( const deps of parentDependenciesChain ) { if ( deps . dependencies ?. [ name ] ) { return deps . dependencies [ name ] . version ; } } return undefined ; } function recordOriginalDependencies ( node ) { if ( ! node . dependencies ) { return ; } let list = originalDependencies . get ( node ) ; if ( ! list ) { list = [ ] ; originalDependencies . set ( node , list ) ; } for ( const [ depName , depPkg ] of Object . entries ( node . dependencies ) ) { list . push ( `${ depName }@${ depPkg . version }` ) ; recordOriginalDependencies ( depPkg ) ; } } function necessaryInTree ( name , version , tree ) { if ( originalDependencies . get ( tree ) ?. includes ( `${ name }@${ version }` ) ) { return true ; } if ( ! tree . dependencies ) { return false ; } for ( const depPackage of Object . values ( tree . dependencies ) ) { if ( necessaryInTree ( name , version , depPackage ) ) { return true ; } } return false ; } } export function renderTree ( tree ) { const ret = new Array < string > ( ) ; recurse ( tree . dependencies ?? { } , [ ] ) ; return ret . sort ( compareSplit ) ; function recurse ( n , parts ) { for ( const [ k , v ] of Object . entries ( n ) ) { ret . push ( [ ... parts , k ] . join ( '.' ) + '=' + v . version ) ; recurse ( v . dependencies ?? { } , [ ... parts , k ] ) ; } } function compareSplit ( a , b ) { const as = a . split ( /\.|=/g ) ; const bs = b . split ( /\.|=/g ) ; for ( let i = 0 ; i < as . length && i < bs . length ; i ++ ) { const cmp = as [ i ] . localeCompare ( bs [ i ] ) ; if ( cmp !== 0 ) { return cmp ; } } return as . length - bs . length ; } }