Generate code for recursive generic definitions

[jmesserly]

From @vsmenon on July 10, 2015 1:18

We currently break on code of the following form:

class ElementInjector extends TreeNode<ElementInjector> {
  ...
}

we generate:

class ElementInjector extends TreeNode$(ElementInjector) {

which generates reference error on ElementInjector.

(edit by @jmesserly) a lot of discussion below is obsolete, see my recent comment for proposed solution.

Copied from original issue: dart-archive/dev_compiler#253

[jmesserly]

yeah we don't support recursively bounded quantification. do we want to?

EDIT: see this comment for a solution that will work.

---

If yes, we likely need to change how library cycles are compiled, to deal with pathological cases like:
(edit: removed obsolete code example)

without library cycles, it's not too bad. The safest way to handle this is probably, instead of:

class A extends B$(A) { ... }

generate:

class A {} // forward declare
mergeClass(A, class extends B$(A) { ... });

mergeClass copies instance and static methods, as well as fixing what A extends.

We might be able to just fix up "extends", but I think super bindings might only work if we do it as shown above. Not 100% sure though.

None of this works for lib cycles+incremental compile tho

[jmesserly]

One thing to note: we could take a different approach, and change how reified generics work. We could do a type tagging approach for generic type instances, where each instance points at its runtime type, and from there can get to various generic args. But that brings in a bunch of issues (by un-solving some of the problems the current approach solves).

[jmesserly]

I think we can fix this by extending the lazy-load mechanism that we already use to deal with library cycles. Two parts to this:

• the declaration loader needs to understand and track that elements can refer to themselves. (right now, it understands cycles in library imports, but not in top-level Elements, like static fields/classes.)
• lazyClass needs to handle the case where a class is requested while its being defined, and understand how to hand out a forward declaration, then merge in the members.
• verify that references to the class name from inside itself are generated as qualified names (probably works already.)

[jmesserly]

From @vsmenon on November 9, 2015 21:52

@jmesserly

I think I may have asked you this before, and it didn't work out, but I don't recall why. Could we change the prototype after the fact along these lines?:

Change this:

class A extends B$(T) { ... }  // Where T is unavailable

to:

class A extends B$(dart.dynamic) { ... }
...
A.prototype.__proto__ = B$(T).prototype;  // Once T is available - i.e., immediately if A == T

[jmesserly]

I think the problem is with super being very early bound in JS. So:

// note: slightly simplified compared with real output
let B$ = (T) => class B {
  foo() {
    console.log('B.foo: ' + T.toString());
  }
};
class A extends B$(dart.dynamic) {
  foo() {
    console.log('A.foo: ' + T.toString());
    super.foo();
  }
}
A.prototype.__proto__ = B$(A).prototype; 
 // I think A.foo prints A, but B.foo prints dynamic
new A().foo();

But yeah, if we could mutate the prototype, and it would affect super, then it would work.

We could perhaps avoid super in these cases, but trying to detect when to avoid super and make the dispatch work at runtime is a bit tricky, IIRC. But that's an option.

I guess I was leaning towards something like:

class A {} // forward declare
mergeClass(A, class extends B$(A) { ... });

basically, we have methods that are immutable (at least, w.r.t. super), but we have a class that's mutable, so we initialize the methods in a way that makes them happy, then copy them over to the class.

[jmesserly]

From @leafpetersen on November 9, 2015 23:45

Forward declaration seems promising. Does it work when both are generic?

class A<T> {
  T f(T x) => x;
}

class B<T> extends A<B<T>> {
}

void main () {
  B<int> x = new B<int>();
  x = x.f(x);
} 

[jmesserly]

From @vsmenon on November 10, 2015 0:6

Ahh, right - super - you told me that before....

[jmesserly]

Forward declaration seems promising. Does it work when both are generic?

For that example, yes:

let A$ = dart.generic((T) => class A { ... });
let B$ = dart.generic((T) => {
  class B {}
  return mergeClass(B, class extends A$(B));
});
function main() {
  new B$(core.int)();
}

The harder case is more along the lines of:

class B<T> extends A<C<T>> {}
class C<T> extends A<B<T>> {}

To support those, we'd have to let dart.generic handle the forward initialization & merging process itself. Which it should be able to do. (We might get some side benefits from that, like it's easier to compute signatures inside, since referring to B$(T) becomes generally safe. We had considered it before IIRC).

[jmesserly]

Restating this more fundamentally -- it's hard to implement letrec without mutation :)

We currently have a cycle.

the class -> class methods -> superclass methods -> generic type argument (= the class)

I'm picking on the class -> class method link as it's easy to mutate. However we could consider a design change that makes either the the class methods -> superclass linkage mutable, or a design change that makes methods -> generic type argument mutable.

To break method -> super method link, we'd have to avoid ES6 super. Not my first choice, but it's an option.

To break the method -> generic type arg link, we'd have to make T be mutable somehow. For example

let B$ = dart.generic((types) => class B { method() { print(types.T); });

Now we can provide a way to mutate T later. Just not sure if we want to change all generic types. (we don't know which ones someone will create a cycle with until later.) But maybe it's nice looking enough.

[jmesserly]

BTW, to complete that example, it would be like:

let B$ = dart.generic((types) => class B { method() { print(types.T); });

// We assume B$() with no args returns a fresh copy,
// with "undefined" type args, so we can initialize them later.
class A extends B$() { ... }
// gets ahold of the "types" object we stored previously and assigns T
// dart.typesArguments is just a Symbol
// A.prototype is our B$() from before.
A.prototype[dart.typesArguments].T = A;

edit x3: make it more obvious what's going on.

[jmesserly]

also: if dart.generic's function argument takes a "types" array I'm not sure how it would know the type parameter name ("T" in this case). I guess it can figure it out after it makes a type:

let typeArgs = {}; // empty at first
let newType = makeTypeFunction(typeArgs);
// will newType's type info will tell us the name "T", allowing us to set typeArgs['T']?

[jmesserly]

From @vsmenon on November 10, 2015 0:34

@jmesserly

Are you sure on super being early bound? With your example above, super.foo() is printing B (Chrome 45), not dynamic.

If I do the same trick in the following example, it's giving me the same result as the Dart VM:

class A<T> {
  A() {
    print(T);
  }

  T foo(T x) => x;

  Type getType() => T;
}

class B extends A<B> {
  Type getType() => super.getType();
}

void main() {
  A a = new B();
  try {
    print(a.foo("Hello"));
  } catch(e) {
    print(e);
  }
  print(a.getType());
}

[jmesserly]

From @leafpetersen on November 10, 2015 0:59

What about making dart.generic also be a fixed point combinator? Some something like:

let A$ = dart.generic((A$) => (T) => class A { ... });
let B$ = dart.generic((B$) => (T) => class B extends A$(B$(T)) {};
function main() {
  new B$(core.int)();
}

Presumably dart.generic would have to allocate and memoize the "real" class B<T>, and then merge the return value from the constructor into it. Or maybe do that internally, so more like:

let A$ = dart.generic((A$) => (T) => class A { ... });
let B$ = dart.generic((B, B$) => (T) {
  return mergeClass(B, class extends A$(B$(T)));
});
function main() {
  new B$(core.int)();
}

Does that work, or am I confusing myself? Would we ever have to worry about cycling off into la-la land because we're too eager?

[jmesserly]

Are you sure on super being early bound? With your example above, super.foo() is printing B (Chrome 45), not dynamic.

@vsmenon -- yes you are totally right! I followed all the pointers through the spec*, [[HomeObject]] should be set to A.prototype, so mutating its __proto__ will work.

Not sure how I was confused about this. Maybe it used to be different in older Chrome? Not sure. I'd swear I tested it but who knows, maybe was faulty memory. Regardless, this is a nice find, this might help us with super-mixin feature as well.

Well that will make it super easy. We can just adjust A.prototype.__proto__ to handle the cycle case and be done with it.

(* spec notes: ultimately it comes down to MakeMethod in the spec, which is called through a couple of layers of indirection from ClassDefinitionEvaluation. And confirmed by GetSuperBase.)

[jmesserly]

Does that work, or am I confusing myself? Would we ever have to worry about cycling off into la-la land because we're too eager?

@leafpetersen -- not sure you need the extra parameter?

let B$ = dart.generic(/*(B$) => */(T) => class B extends A$(B$(T)) {});

We can have B$(T) return something different (the "real" B$(T), which will need to be merged later with the "fake" one that is returned) when it's called in the middle of a cyclic evaluation. Wouldn't work in an immutable language, but since JS is pretty mutable I think it would.

But yeah, maybe we can use @vsmenon's "patch in the generic type later" approach? Seems easy

[jmesserly]

From @leafpetersen on November 10, 2015 1:35

Ah, didn't realize that JS let was recursively scoped. I'm fine with patching the prototype, just wanted to throw that out there in case it was helpful.

[jmesserly]

Vijay landed a partial fix in dart-archive/dev_compiler@ef3b9cf ... \o/

[jmesserly]

From @vsmenon on April 15, 2016 17:5

Another case popping up in customer code:

class Foo extends Bar with Baz<Foo> { ... }

[jmesserly]

since this was a long discussion I wanted to summarize the solution:

• We should be able to easily detect the self-reference and/or cycle when generating the class heritage. (indeed we already detect the simple case) using ElementLoader,
• We then generate the class without a superclass, and fix it up after (we already do in some cases: dart.setBaseClass), although we will need to have it come later on in the code (so all classes can be declared)

Almost all of the building blocks are in place, so it should be pretty easy (knock on wood) to fix now.

[jmesserly]

Another example:

class C<T> {}
class A extends B {}
class B extends C<A> {}

The point is that the cycle isn't always obvious just by examining the current class, and the fix up cannot happen right after we emit that class. So the existing _hasDeferredSupertype approach will need to be generalized.

[jmesserly]

From @rakudrama on May 6, 2016 19:38

Another example, blocking #257:

abstract class _DoubleLinkedQueueEntry<E>
    extends _DoubleLink<_DoubleLinkedQueueEntry<E>> {

This is the simple self-reference case (the type parameter of _DoubleLink is the class being defined).
I was able to fix this manually:

  collection._DoubleLinkedQueueEntry$ = dart.generic(E => {
    class _DoubleLinkedQueueEntry extends collection._DoubleLink {
      ...
    }
    dart.setBaseClass(_DoubleLinkedQueueEntry,
        collection._DoubleLink$(collection._DoubleLinkedQueueEntry$(E)));
    dart.setSignature(_DoubleLinkedQueueEntry, ...);
    return _DoubleLinkedQueueEntry;
  });

  collection._DoubleLinkedQueueEntry$ = dart.generic(E => {
    class _DoubleLinkedQueueEntry extends collection._DoubleLink {
      ...
    }
    dart.setBaseClass(_DoubleLinkedQueueEntry,
        collection._DoubleLink$(_DoubleLinkedQueueEntry));  // << HERE
    dart.setSignature(_DoubleLinkedQueueEntry, ...);
    return _DoubleLinkedQueueEntry;
  });

[jmesserly]

yeah, self reference is a lot easier to handle (I'm actually surprised @vsmenon 's workaround didn't pick it up...)

[jmesserly]

Oh, I see. The workaround kicked in, but it doesn't help at all if we're currently in a generic type.

Yeah that is part of what makes this one tricky, there are permutations depending on whether the two types involved are generic or not.

Fortunately, for this example dart.generic can handle it in a fairly straightforward manner. I will take a look as soon as I am able.

[jmesserly]

From @vsmenon on May 6, 2016 22:36

Downgrading this in favor of #556

[jmesserly]

https://codereview.chromium.org/2516483002/