Refactor chunking algorithm - #2575

I think we need to be doing some colouring for dynamic imports to make this algorithm work properly.

Here is a test case I tried that isn't working correctly:

main.js

import './dep1.js';
console.log('main');

dep1.js

import './dep2.js';
console.log('dep1');

dep2.js

import('./dep1.js');
console.log('dep2');

The dynamic import back to dep1 should be informing a colouring of dep1.js being an entry point chunk effectively.

Instead I got the following output:

main.js

console.log('main');
console.log('dep1');
import('./generated-chunk.js');

generated-chunk.js

console.log('dep2');

The problem with this is that it has broken the execution order invariant that we require dep2 to execute statically and synchronously before dep1 and main.

Here's the key point from #2407 that I feel may have been missed here (correct me if I'm wrong):

it would actually be an improvement to the chunking algorithm if we could work out the common base dependencies of a given dynamic import (the intersection of the static dependency graph of all modules that use this dynamic import)

I am sorry but I cannot follow entirely. Using your test case, I (IMO correctly) get the following two chunks:

// main.js
import './generated-chunk.js';

console.log('main');

// generated-chunk.js
Promise.resolve().then(function () { return dep1; });
console.log('dep2');

console.log('dep1');

var dep1 = /*#__PURE__*/Object.freeze({

});

which looks correct to me. Is there something I am missing. Adding inlineDynamicImports, this all gets folded into one chunk correctly. One could argue that it could have been a single chunk all along but that is another point.

I must admit I also do not understand what you mean with your key point from #2407 . Maybe you can illustrate this with some examples of the form input -> expected output?

I tried this again and you're right it's working correctly - not sure why it wasn't working in my test previously.

Wasn't the chunk.id the same as the chunkName before? How are these two properties different?

chunkName is just the "[name]" part of the chunk id and is also used by generateId() for this purpose. The idea is that the name can be used as a stable way to identify a chunk while the actual id depends on the name pattern and possibly the hash. This name is now attached to the output.

Should this not be replaced with chunk.entryModules.length === 0 or similar to retain the logic?

I am not sure the old logic was correct. Now we no longer have a single chunk as soon as there is more than one chunk no matter for what reason another chunk was created.

Nice refactoring.

Would isFacade not handle this same information, meaning facadeModuleId === imports[0]?

Not necessarily. Having a facadeModuleId does not mean this is a specially created facade but that this chunk has the same interface and purpose as the given module. When only having a single entry and no dynamic imports, the facadeModuleId of the created chunk would be the entry point id. If this does not properly reflect this meaning, maybe another name would be better?

Great to see this file separated.

Could you perhaps explain what this refactoring fixed in the process if there was an underlying fix with this?

Actually there was though I no longer know the precise situation. Before, each module had its own needsTreeshakingPass. Now if a variable is declared in module 'a' but included by module 'b', it could happen that the flag would be set for module 'a' instead of module 'b'. If this module was already processed but no other modules request a new pass, it could happen that no new pass was triggered. Having a shared flag for all modules makes much more sense and fixes this kind of issue.
BTW as part of the refactorings of the other PR, I could get rid of requestTreeshakingPass on the AST context entirely and keep this logic to the module level.

Great to see this all moved out of here.

Nicer name!

Much clearer!

Ah I missed that the dynamic colouring is being done here.

Ok, here's an example of the algorithm I was suggesting (~> means dynamic import, -> means static import):

E1
~> D1 -> F -> T
-> S -> T      
-> R

E2
~> D2 -> G -> R
-> S -> T      
-> R

E3
~> D3 -> H -> S->T
-> S -> T      
-> R

The current colouring algorithm will result in no optimization groups at all in the above, as every module has a unique colouring.

On the other hand, we could get a more optimal chunking since we know that S, T and R are always loaded together despite the dynamic imports being different colours:

E1
~> D1 -> F -> STR
-> STR

E2
~> D2 -> G -> STR
-> STR  

E3
~> D3 -> H -> STR
-> STR

The algorithm is, for each dynamic import, to determine the intersection of the static graph of all of its importers. So for each of D1, D2 and D3 this is STR. Then when doing colouring for those dynamic imports, to skip these shared items when it comes to colouring, as the dynamic import isn't affecting their colours as they are already available.

This algorithm is also the general case of resolving the issue we have with the test case I provided:

Main -> dep1 -> dep2 ~> dep1

dep1 has parent importer static intersection Main, dep1, dep2. Therefore the colouring of dep1 doesn't recolour itself and as a result we get a single chunk.

Perhaps for another day, but glad to be able to verify the logic here. Let me know if that all sounds correct too please!

Note also here that dynamic import facades can be rendered inline:

import('./static-chunk').then(x => ({ get some () { return x.a }, get export () { return x.b }, get names () { return x.c } }));

Thanks a lot, this really helped understand it! Definitely worth adding this in the future!

Note also here that dynamic import facades can be rendered inline

Just a minor question, you are using getters instead of Object.freeze, any particular advantage or disadvantage to doing this? Or is Object.freeze semantically wrong here?

Otherwise this all really makes sense, I'll add it to the other issue.

Ah I see, this is just another alternative to creating a namespace which does not require any changes to the exporting chunk.

I tried this again and you're right it's working correctly - not sure why it wasn't working in my test previously.

This is something I should have done a long time ago, thanks, a much richer representation.