Cyclic dependency resolution is broken

[grssam]

Consider this example. In cases where I have a single file exporting multiple modules as a single submodule, the output file has reference to the modules before the declaration, i.e. the dependency tree is incorrectly created somehow.

Ignore the incorrectness of the JS. The example is just there to demonstrate the bug.

[grssam]

Any way I can avoid this issue apart from importing directly from the files l2.js and l4.js ?

[thisconnect]

what is your expected result?

[grssam]

@thisconnect Well, the generated JS file should not throw. Since this is strict mode, variable hoisting does not work, so for line 3 var L3 = L4("4") to work, L4 should be declared before line 3.

That is what is written in l3.js as well. l3.js imports L4

[grssam]

@Victorystick Any chances this can be fixed soon? If the devs are not able to pick this one up soon, I can help fix this bug as well, if I can get some pointers on how to debug/contribute etc.

[Victorystick]

@grssam I'm a little out of the loop since the big rewrite (#902). I suggest you create a failing test case in test/function, then start looking at sort in src/Bundle.js and work your way from there.

[grssam]

I debugged a bit using devtools on the rollupjs.org site and found the cause of the issue. I think the whole cycle resolution logic is broken right now.

The example in the original issue has an obvious cycle where l2.js depends on l3.js for module L3, l3.js depends on utils.js for module L4 and then utils.js again depends on l2.js for module L2.

This is detected by this code piece in Bundle.js#L470-L482 :

const visit = module => {
    if ( seen[ module.id ] ) {
        hasCycles = true;
        return;
    }

    seen[ module.id ] = true;

    module.dependencies.forEach( visit );
    ordered.push( module );
};

visit( this.entryModule );

shortly after which, cycle resolution code starts which looks like:

if ( hasCycles ) {
    ordered.forEach( ( a, i ) => {
        for ( i += 1; i < ordered.length; i += 1 ) {
            const b = ordered[i];

            if ( stronglyDependsOn[ a.id ][ b.id ] ) {
            ...
            }
        }
    });
}

So the complete cycle resolution algorithm depends on some 2D boolean map stronglyDependsOn which is populated in these lines. The population of this map in turn depends on the fact that module.strongDependencies is an array of all strong dependencies (whatever that means).

This is the core of the issue that this array (strongDependencies) is never populated inside Module.js or any other file in the final rollup bundle file. Thus, stronglyDependsOn[ a.id ][ b.id ] is always false in line 489 of the cycle resolution algorithm and the execution never goes inside the if block.

@Victorystick / @Rich-Harris : I don't know the real reason of two separate arrays representing the dependency list - strongDependencies and dependencies. Maybe the above information will make the fix real easy for someone more familiar with the code.

[grssam]

I tried the test case on version 0.34.13 which was before the big rewrite. Turns out, even though that version properly applies the cycle resolution algorithm, it does not actually orders the modules correctly. It simply throws a warning asking the user to reshuffle the import order.

What I feel the main issue of this all is that in the below code

const visit = module => {
    if ( seen[ module.id ] ) {
        hasCycles = true;
        return;
    }
    seen[ module.id ] = true;

    module.dependencies.forEach( visit );
    ordered.push( module );
};

Instead of discarding (early return) the current module inside the if ( seen[ module.id ] ) { ... }, we should actually remove the module from the ordered array and push it back on top again. Something like:

const visit = module => {
    if ( seen[ module.id ] ) {
        hasCycles = true;
        ordered.splice( ordered.findIndex( m => m.id == module.id ), 1 );
        ordered.push( module );
        return;
    }
    seen[ module.id ] = true;

    module.dependencies.forEach( visit );
    ordered.push( module );
};

[trusktr]

Cool, looking forward to the solution. Can't really use rollup until fixed.

[grssam]

@trusktr - You can shift your dependencies / import statements until it work for you. You can also use version 0.34 and below to actually get warnings on what all imports to shift

[grssam]

Any plans on fixing this?

[mbostock]

This hit me, too. Here’s another test case.

[grssam]

bump

/cc @Rich-Harris

[Rich-Harris]

Currently working on a completely new tree-shaking approach which (among many other things, if it works out) should in theory make detection of improperly-ordered modules much easier. I need to make one point of clarification though —

even though that version properly applies the cycle resolution algorithm, it does not actually orders the modules correctly

The purpose of that code wasn't to reorder the modules. The order is completely determined by the order of import declarations (per the spec), not what's in your code, and Rollup should not and will not attempt to shuffle code about to make it work. Instead, it will detect when there's a problem and invite the developer to fix it, as it used to before the 0.35 rewrite.

[grssam]

The major thing in this ticket is that cyclic dependencies are not resolved correctly, the module ordering should not be a problem.

If you see the reduced test case in the original comment, you would notice that there is nothing wrong with the import ordering in the various files (individually). Its only when you look at the complete tree, the cycle causes an issue. Now is that something which the spec allows for the compiler (or rollup in this case) to adjust to and order the declaration of the imported modules accordingly, I am not really sure.

[Qiu-Kejian]

Hit me too. Waiting for the solution.

[kaarmann]

Hit me too with sepc256k1 and elliptic includes. Has anyone found a temporary workaround? Thanks.

[trusktr]

A workaround for anyone interested in solving cyclic ES6 module dependencies in general is to use "hoisted init functions". See here:

https://esdiscuss.org/topic/how-to-solve-this-basic-es6-module-circular-dependency-problem

The solution (thanks to those awesome people who took the time to read the problem I had) is designed to work around the problem of modules that depend on each other in a circular dependency and who need each other's export at runtime. In particular, it assumes a module needs the export of another module at runtime, but the other module needs the export of the first module at module evaluation time.

When circular dependencies both depend on each other's export at runtime only, then there isn't really a problem, and the circular dependencies should work perfectly fine. It is mainly when circular dependencies depend on each other at module evaluation time that problems arise.

Using the awesome ideas that those people there presented, I was able to solve my circular dependency problems. Read carefully, as there are caveats around the use of let due to limitations of the ES6 module implementations.

After solving circular my problems, I was able to refactor code to eliminate some circular dependencies completely, which is ultimately a better solution when possible. Use circular dependencies only as a last resort if there's no other way.

[olsonpm]

Here's the updated repro link to work with the new site

[olsonpm]

@grssam - I was interested in how this worked and just tested a variant of your code against the chrome dev channel - which supports modules via <script type="module">. The executed output is exactly the same as rollup's:

This is l1.  l2 is "This is l2.  l3 is "This is l3.  l4 is "undefined"""
This is l4

Module evaluation is synchronous, thus your comment

Its only when you look at the complete tree, the cycle causes an issue

doesn't make sense as the dependency tree is separate from import evaluation. I found this section of exploring es6 helpful in understanding what's going on, but for sake of future readers, I'll try to be explicit below.

Lengthy illustration of module evaluation

Using my modified code, we'll start with main.js

import { l1 } from "./l1.js";
import { l4 } from "./utils.js";

console.log(l1);
console.log(l4);

We can illustrate the synchronous evaluation of l1 being imported by replacing the import with the contents of l1.js

-import { l1 } from "./l1.js";
+import { l2 } from "./utils.js";
+export var l1 = `This is l1.  l2 is "${l2}"`;
import { l4 } from "./utils.js"

console.log(l4);
console.log(l4);

now utils is evaluated, so we can again replace the import

-import { l2 } from "./utils.js";
+export * from "./l2.js";
+export * from "./l4.js";
export var l1 = `This is l1.  l2 is "${l2}"`;
import { l4 } from "./utils.js"

console.log(l4);
console.log(l4);

So far we've resolved l1.js and utils.js. Now for l2.js

-export * from "./l2.js";
+import { l3 } from "./l3.js";
+export var l2 = `This is l2.  l3 is "${l3}"`;
export * from "./l4.js";
export var l1 = `This is l1.  l2 is "${l2}"`;
import { l4 } from "./utils.js"

console.log(l4);
console.log(l4);

and l3.js

-import { l3 } from "./l3.js";
+import { l4 } from "./utils.js";
+export var l3 = `This is l3.  l4 is "${l4}"`;
export var l2 = `This is l2.  l3 is "${l3}"`;
export * from "./l4.js";
export var l1 = `This is l1.  l2 is "${l2}"`;
import { l4 } from "./utils.js"

console.log(l4);
console.log(l4);

leaving us with the theoretical synchronous code:

import { l4 } from "./utils.js"; // <--- this line is the gotcha
export var l3 = `This is l3.  l4 is "${l4}"`;
export var l2 = `This is l2.  l3 is "${l3}"`;
export * from "./l4.js";
export var l1 = `This is l1.  l2 is "${l2}"`;
import { l4 } from "./utils.js"

console.log(l4);
console.log(l4);

So at this point, every module except l4.js has been evaluated. Due to this portion of the module spec:

If module.[[Evaluated]] is true, return undefined.

the import { l4 } from "./utils.js" doesn't evaluate utils.js. If it did, this would cause an infinite loop. The following diff represents the remaining imports and translates the exports to their corresponding variables.

-import { l4 } from "./utils.js"; // <--- this line is the gotcha
-export var l3 = `This is l3.  l4 is "${l4}"`;
+var l3 = `This is l3.  l4 is "${l4}"`;
-export var l2 = `This is l2.  l3 is "${l3}"`;
+var l2 = `This is l2.  l3 is "${l3}"`;
-export * from "./l4.js";
+var l4 = `This is l4`
-export var l1 = `This is l1.  l2 is "${l2}"`;
+var l1 = `This is l1.  l2 is "${l2}"`;
-import { l4 } from "./utils.js"

console.log(l1);
console.log(l4);

Which finally results in your rollup output:

var l3 = `This is l3.  l4 is "${l4}"`;
var l2 = `This is l2.  l3 is "${l3}"`;
var l4 = `This is l4`
var l1 = `This is l1.  l2 is "${l2}"`;

console.log(l1);
console.log(l4);

And when executed, writes

This is l1.  l2 is "This is l2.  l3 is "This is l3.  l4 is "undefined"""
This is l4

[EmielM]

In my attempts to get ReactNative bundled with rollup, I encountered this issue. I still believe this is actually more of a RN bug, but the folks over there seem perfectly happy with their ridiculously complex code base (it's true that a few cyclic dependencies are probably the least of their horrors).

As a work-around, I have created a branch of rollup that allows for the definition of a list of edges called weakDependencies. In rollup's "enhanced topological sort", these dependencies are not accounted for when doing the dfs traversing*. weakDependencies are defined as a list of [moduleA,moduleB] tuples where moduleA should only use moduleB in runtime.

Works pretty well, and wouldn't mind cleaning it up to submit a pull request. However I do agree that a better solution would be completely automatic in some way -- it is pretty tough to wrap your head around. Unfortunately I don't really see how this could be done for the generic case -- especially if you don't really control the code as is the case when compiling RN.

Any thoughts?

*(PS: while doing so, see that the strongDependencies var is still being used and checked, but never actually populated).

[olsonpm]

this issue should be closed as there is no problem with cyclic dependencies. what the OP posted as a problem is exactly the expected behavior per the spec

[EmielM]

Point taken, but it's still annoying as hell for developers, especially when coming from runtime packagers (rn packager, webpack) that work just fine.

Here's a simple broken case.

Some thoughts:

• There is a simple fix for this case, but rollup (or: the spec) doesn't infer it.
• The whole import/export spec feels really declarative, but apparently the order in which you define imports can break the world.
• Conversion from commonjs probably inflates the issue for a lot of npm packages out there.

I see that there is some now-defunc code (works kind-of when using dependsOn instead of strongDependsOn) tried to warn the developer when using circulars. What's the plan for this?

[olsonpm]

what you are suggesting is that rollup behave differently from the spec which would be much worse

[EmielM]

I can imagine this to be configurable or at least extensible through a plugin in some way. Plugins unfortunately have very little influence on this part of rollup (by design I guess, bundle/module instances are serialized and never exposed to plugins*). But let's be honest about that spec. It totally sucks, at least for these cases. It's completely unexpected - especially when coming from other module systems - and will take developers hours of productivity to fathom what is going on. Good error reporting on the side of rollup might help a little here. *aside: I'm also still looking for a normal, maintainable way to declare additional pure functions @ https://github.com/rollup/rollup/blob/master/src/ast/nodes/shared/callHasEffects.js#L81

…

On Sep 13, 2017 00:04, "olsonpm" ***@***.***> wrote: what you are suggesting is that rollup behave differently from the spec which would be much worse — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#995 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAF0FhFHbvt7v6EBbNnrJVguEKMhJGefks5shv_qgaJpZM4KIPHS> .

[grssam]

One thing to note is that the spec is very young at this moment. Only a few browsers support it, no production systems have started relying on it etc. Its not wrong to imagine that as this native module feature gains popularity, devs would start complaining about this limitation.

[olsonpm]

yes a configuration would work. I imagine it being opt in, and the switch would modify the import evaluation algorithm here

as for the spec sucking, keep in mind the impact the spec has. unlike the ephemeral code we all mostly write, specs set standards that have to be adhered to for a long time. One pattern i've noticed with the http spec is they start simple and only evolve when demand is high. Optimization improvements were the most notable for me in terms of complexity being added in later. I definitely think managing circular dependencies should have been out of scope and left for userland to test both the demand and implementation.

Also worth mentioning is node has never supported it - they just throw an awkward "module not found" error that you eventually decrypt to mean "you have a circular dependency".

[guybedford]

Cyclic resolution definitely works correctly. We can possibly create a tracking issue for reenabling warnings on cyclic dependencies though.

[trusktr]

what you are suggesting is that rollup behave differently from the spec which would be much worse

No, actually, it is you fine folks who make Rollup, Webpack, JSPM, etc, who should encourage the spec to change for the better, not the other way around.

Browser makers have done this with web specs all the time (though sometimes not enough).

Clearly, circular dependencies can be very hard to wrap our heads around the way they are spec'd.

If it is completely obvious that module A only depends on module B at runtime (not module evaluation time) then it would be great for the system to automatically resolve circs when possible.

There's no one better to do this than the people who make the module loaders. YOU have the power!

@rauschma I haven't seen any articles on solving circular dependencies using module hoisting yet. That'd be a good one for the people that will keep stumbling here! (My comment above has a link to an esdiscuss thread with some details that are gatherable after wading through the thread, not as nice as an article would be).

[olsonpm]

You're right. We should deviate from the spec so that way when you translate from one bundling software to another, or go back to vanilla browser behavior - you can keep in mind all the edge cases each one brings to the table because they couldn't all agree upon a standard.