Skip to content
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

[node-modules] Support reducing trees requiring multiple hoisting passes to a terminal result #2394

Merged
merged 17 commits into from
Feb 5, 2021
Merged

[node-modules] Support reducing trees requiring multiple hoisting passes to a terminal result #2394

Changes from 1 commit
Commits
Show all changes
17 commits
Select commit Hold shift + click to select a range
ac1f725
Improves NM_DEBUG_LEVEL=2 output
larixer Jan 20, 2021
ba9600e
More hoistedFrom details
larixer Jan 20, 2021
e37edef
Do not hide reason when ident is unhoistable
larixer Jan 21, 2021
7407c3f
Don't clone hoistedFrom
larixer Jan 21, 2021
d38fef7
Hopefully finally fix reasons, remove self-refs form the output and s…
larixer Jan 21, 2021
d078946
Shorrten hoistedFrom
larixer Jan 21, 2021
d629c22
Implements multi-pass hoisting (its much slower atm)
larixer Jan 27, 2021
bcf10b3
Speedup used dependencies computation
larixer Jan 27, 2021
03058a9
Dump number of rounds
larixer Jan 27, 2021
bdea387
Cosmetics
larixer Jan 28, 2021
0e672e4
Adds multi-pass unit test
larixer Jan 28, 2021
aae413d
Uses special version of used dependencies computation for zero round …
larixer Jan 29, 2021
d14b15e
Limit the number of rounds to a minimum thanks to shadowed nodes hois…
larixer Jan 30, 2021
ce866cc
Properly track shadowed nodes
larixer Feb 1, 2021
35f45bf
Check for shadowed nodes always
larixer Feb 1, 2021
d1619bc
Add changelog entry
larixer Feb 1, 2021
4576b49
Enable fast lookup
larixer Feb 3, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Properly track shadowed nodes
  • Loading branch information
@larixer
larixer committed Feb 1, 2021
commit ce866ccddd6e390a34a533a40ed202f2c63c1339
34 changes: 20 additions & 14 deletions packages/yarnpkg-pnpify/sources/hoist.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -73,6 +73,8 @@ type HoistInfo = {
reason: string | null
};

type ShadowedNodes = Map<HoisterWorkTree, Set<PackageName>>;

const makeLocator = (name: string, reference: string) => `${name}@${reference}`;
const makeIdent = (name: string, reference: string) => {
const hashIdx = reference.indexOf(`#`);
Expand Down Expand Up @@ -126,7 +128,7 @@ export const hoist = (tree: HoisterTree, opts: HoistOptions = {}): HoisterResult
let anotherRoundNeeded = false;
let round = 0;
do {
anotherRoundNeeded = hoistTo(treeCopy, [treeCopy], new Set([treeCopy.locator]), new Set(), options).anotherRoundNeeded;
anotherRoundNeeded = hoistTo(treeCopy, [treeCopy], new Set([treeCopy.locator]), new Map(), options).anotherRoundNeeded;
options.fastLookupPossible = false;
round++;
} while (anotherRoundNeeded);
Expand All @@ -136,7 +138,7 @@ export const hoist = (tree: HoisterTree, opts: HoistOptions = {}): HoisterResult

if (options.debugLevel >= DebugLevel.CHECK) {
const prevTreeDump = dumpDepTree(treeCopy);
const isGraphChanged = hoistTo(treeCopy, [treeCopy], new Set([treeCopy.locator]), new Set(), options).isGraphChanged;
const isGraphChanged = hoistTo(treeCopy, [treeCopy], new Set([treeCopy.locator]), new Map(), options).isGraphChanged;
if (isGraphChanged)
throw new Error(`The hoisting result is not terminal, prev tree:\n${prevTreeDump}, next tree:\n${dumpDepTree(treeCopy)}`);
const checkLog = selfCheck(treeCopy);
Expand Down Expand Up @@ -375,7 +377,7 @@ const getSortedRegularDependencies = (node: HoisterWorkTree): Set<HoisterWorkTre
* @param rootNodePathLocators a set of locators for nodes that lead from the top of the tree up to root node
* @param options hoisting options
*/
const hoistTo = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, rootNodePathLocators: Set<Locator>, shadowedNodes: Set<HoisterWorkTree>, options: InternalHoistOptions, seenNodes: Set<HoisterWorkTree> = new Set()): {anotherRoundNeeded: boolean, isGraphChanged: boolean} => {
const hoistTo = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, rootNodePathLocators: Set<Locator>, parentShadowedNodes: ShadowedNodes, options: InternalHoistOptions, seenNodes: Set<HoisterWorkTree> = new Set()): {anotherRoundNeeded: boolean, isGraphChanged: boolean} => {
const rootNode = rootNodePath[rootNodePath.length - 1];
if (seenNodes.has(rootNode))
return {anotherRoundNeeded: false, isGraphChanged: false};
Expand All @@ -390,12 +392,11 @@ const hoistTo = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, ro

let anotherRoundNeeded = false;
let isGraphChanged = false;
let nextShadowedNodes;

const hoistIdents = new Map(Array.from(hoistIdentMap.entries()).map(([k, v]) => [k, v[0]]));
const shadowedNodes: ShadowedNodes = new Map();
do {
const result = hoistGraph(tree, rootNodePath, rootNodePathLocators, usedDependencies, hoistIdents, hoistIdentMap, shadowedNodes, options);
nextShadowedNodes = result.nextShadowedNodes;
const result = hoistGraph(tree, rootNodePath, rootNodePathLocators, usedDependencies, hoistIdents, hoistIdentMap, parentShadowedNodes, shadowedNodes, options);
if (result.isGraphChanged)
isGraphChanged = true;
if (result.anotherRoundNeeded)
Expand All @@ -415,7 +416,7 @@ const hoistTo = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, ro
for (const dependency of rootNode.dependencies.values()) {
if (!rootNode.peerNames.has(dependency.name) && !rootNodePathLocators.has(dependency.locator)) {
rootNodePathLocators.add(dependency.locator);
const result = hoistTo(tree, [...rootNodePath, dependency], rootNodePathLocators, nextShadowedNodes, options);
const result = hoistTo(tree, [...rootNodePath, dependency], rootNodePathLocators, shadowedNodes, options);
if (result.isGraphChanged)
isGraphChanged = true;
if (result.anotherRoundNeeded)
Expand All @@ -428,7 +429,7 @@ const hoistTo = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, ro
return {anotherRoundNeeded, isGraphChanged};
};

const getNodeHoistInfo = (rootNodePathLocators: Set<Locator>, nodePath: Array<HoisterWorkTree>, node: HoisterWorkTree, usedDependencies: Map<PackageName, HoisterWorkTree>, hoistIdents: Map<PackageName, Ident>, hoistIdentMap: Map<Ident, Array<Ident>>, shadowedNodes: Set<HoisterWorkTree>, {outputReason}: {outputReason: boolean}): HoistInfo => {
const getNodeHoistInfo = (rootNodePathLocators: Set<Locator>, nodePath: Array<HoisterWorkTree>, node: HoisterWorkTree, usedDependencies: Map<PackageName, HoisterWorkTree>, hoistIdents: Map<PackageName, Ident>, hoistIdentMap: Map<Ident, Array<Ident>>, shadowedNodes: ShadowedNodes, {outputReason}: {outputReason: boolean}): HoistInfo => {
let reasonRoot;
let reason: string | null = null;
let dependsOn: Set<HoisterWorkTree> | null = new Set();
Expand Down Expand Up @@ -492,7 +493,12 @@ const getNodeHoistInfo = (rootNodePathLocators: Set<Locator>, nodePath: Array<Ho
const parentDep = parent.dependencies.get(node.name);
if (parentDep && parentDep.ident !== node.ident) {
isNameAvailable = false;
shadowedNodes.add(node);
let shadowedNames = shadowedNodes.get(parentNode);
if (!shadowedNames) {
shadowedNames = new Set();
shadowedNodes.set(parentNode, shadowedNames);
}
shadowedNames.add(node.name);
if (outputReason)
reason = `- filled by ${prettyPrintLocator(parentDep!.locator)} at ${nodePath.slice(0, idx).map(x => prettyPrintLocator(x.locator)).join(`→`)}`;
break;
Expand All @@ -519,12 +525,11 @@ const getNodeHoistInfo = (rootNodePathLocators: Set<Locator>, nodePath: Array<Ho
* @param usedDependencies map of dependency nodes from parents of root node used by root node and its children via parent lookup
* @param hoistIdents idents that should be attempted to be hoisted to the root node
*/
const hoistGraph = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, rootNodePathLocators: Set<Locator>, usedDependencies: Map<PackageName, HoisterWorkTree>, hoistIdents: Map<PackageName, Ident>, hoistIdentMap: Map<Ident, Array<Ident>>, shadowedNodes: Set<HoisterWorkTree>, options: InternalHoistOptions): {anotherRoundNeeded: boolean, isGraphChanged: boolean, nextShadowedNodes: Set<HoisterWorkTree>} => {
const hoistGraph = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>, rootNodePathLocators: Set<Locator>, usedDependencies: Map<PackageName, HoisterWorkTree>, hoistIdents: Map<PackageName, Ident>, hoistIdentMap: Map<Ident, Array<Ident>>, parentShadowedNodes: ShadowedNodes, shadowedNodes: ShadowedNodes, options: InternalHoistOptions): {anotherRoundNeeded: boolean, isGraphChanged: boolean} => {
const rootNode = rootNodePath[rootNodePath.length - 1];
const seenNodes = new Set<HoisterWorkTree>();
let anotherRoundNeeded = false;
let isGraphChanged = false;
const nextShadowedNodes = new Set<HoisterWorkTree>();

const hoistNodeDependencies = (nodePath: Array<HoisterWorkTree>, locatorPath: Array<Locator>, parentNode: HoisterWorkTree, newNodes: Set<HoisterWorkTree>) => {
if (seenNodes.has(parentNode))
Expand All @@ -534,7 +539,7 @@ const hoistGraph = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>,
const dependantTree = new Map<PackageName, Set<PackageName>>();
const hoistInfos = new Map<HoisterWorkTree, HoistInfo>();
for (const subDependency of getSortedRegularDependencies(parentNode)) {
const hoistInfo = getNodeHoistInfo(rootNodePathLocators, [rootNode, ...nodePath, parentNode], subDependency, usedDependencies, hoistIdents, hoistIdentMap, nextShadowedNodes, {outputReason: options.debugLevel >= DebugLevel.REASONS});
const hoistInfo = getNodeHoistInfo(rootNodePathLocators, [rootNode, ...nodePath, parentNode], subDependency, usedDependencies, hoistIdents, hoistIdentMap, shadowedNodes, {outputReason: options.debugLevel >= DebugLevel.REASONS});

hoistInfos.set(subDependency, hoistInfo);
if (hoistInfo.isHoistable === Hoistable.DEPENDS) {
Expand Down Expand Up @@ -564,7 +569,8 @@ const hoistGraph = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>,
for (const node of hoistInfos.keys()) {
if (!unhoistableNodes.has(node)) {
isGraphChanged = true;
if (shadowedNodes.has(node))
const shadowedNames = parentShadowedNodes.get(parentNode);
if (shadowedNames && shadowedNames.has(node.name))
anotherRoundNeeded = true;

parentNode.dependencies.delete(node.name);
Expand Down Expand Up @@ -637,7 +643,7 @@ const hoistGraph = (tree: HoisterWorkTree, rootNodePath: Array<HoisterWorkTree>,
}
} while (nextNewNodes.size > 0);

return {anotherRoundNeeded, isGraphChanged, nextShadowedNodes};
return {anotherRoundNeeded, isGraphChanged};
};

const selfCheck = (tree: HoisterWorkTree): string => {
Expand Down