esperantojs / esperanto

DEPRECATED: An easier way to convert ES6 modules to AMD and CommonJS
http://esperantojs.org
234 stars 21 forks source link

Ordering of cyclical dependencies #159

Closed Rich-Harris closed 9 years ago

Rich-Harris commented 9 years ago

It didn't take long for the flaws in the module sorting algorithm introduced in https://github.com/esperantojs/esperanto/pull/153 to reveal themselves.

Given a situation like this...

// main.js
import A from './A';
const a = new A();
const b = a.b();
const c = a.c();

// A.js
import B from './B';
import C from './C';

export default class A {
  b () {
    return new B();
  }

  c () {
    return new C();
  }
}

// B.js
import A from './A';
export default class B extends A {}

// C.js
import A from './A';
export default class C extends A {}

...for bundling, we need to sort the modules into either A-B-C-main or A-C-B-main. (Actually, main could go anywhere after A, but let's park that for now.) changed example so that main is required to be at the end, since that's the more realistic scenario

Topological sorting doesn't get us there, because of the cyclicality - most toposort algorithms (AFAICT) just ignore cycles. Before #153, that was the case for esperanto. #153 essentially introduced a distinction between strong and weak dependencies - main, B and C strongly depend on A (they can't execute unless A has been defined), whereas A weakly depends on B and C (i.e. it would be nice for B and C to be defined before A, in case the b or c methods of an A instance are called, but it's less important than A coming before B and C).

Strong dependencies as defined here are easy enough to identify - they're cases where the dependency is referenced outside of any functions (yes, this downgrades IIFEs and upgrades if (false) {...}, but we're not miracle workers).

The #153 algorithm identifies cycles and, given two modules, swaps them if the earlier one has a strong dependency on the later one. But then if you have two modules B and C that depend on A, A will get swapped twice - obviously not the right answer.

My liberal arts degree doesn't help much here, and nor does Google. @eventualbuddha have you been down this road before?