Code generation error on nested generic bounded type arguments

[KholmatovS]

Code generation throws an error when a nested generic bounded type argument is used. The following code reproduces the issue:

example:

abstract class Worker<T extends Worker<T>> {}
mixin Workers {
  void someWork<T extends Worker<T>>() {
    print('Work on: $T');
  }
}
abstract class Bar<T> with Workers {}
class BackgroundWorker extends Worker<BackgroundWorker> {}
class Foo extends Bar<Foo> {
  void doWork() {
    someWork<BackgroundWorker>();
  }
}

Bad state: T extends Worker<T> not found, scopes: [{}, {T extends Worker<T>: T}]

or simpler example:

class Foo<T> {}
abstract class Bar<T> {
  Iterable<X> m1<X extends Foo<X>>(X Function(T) f);
}
abstract class FooBar<X> extends Bar<X> {}

Bad state: X extends Foo<X> not found, scopes: [{X: X}, {X extends Foo<X>: X1}]

[yanok]

Nice catch! Thanks for reporting it.

But it looks like an analyzer issue to me. Seems like self-referencing type variables have broken equality, note that in both examples it says X extends Foo<X> not found but X extends Foo<X> is actually in the map. This might be intentional, probably analyzer doesn't want to make a loop or something... But I'd like to get a confirmation from the analyzer team first, before looking for workarounds.

@srawlins @scheglov Sam, Konstantin It seems equality is not working as expected for type variables that reference themselves in their bounds, like T extends Foo<T>. Is that intentional? If yes, what's the best way to work it around. If not, would it be hard to fix that? Thanks!

[scheglov]

I don't understand your question to me.

  solo_test_X() async {
    await assertNoErrorsInCode(r'''
class Foo<T> {}
abstract class Bar<T> {
  Iterable<X> m1<X extends Foo<X>>(X Function(T) f);
}
''');

    final X = findElement.typeParameter('X');
    final X1 = X.instantiate(nullabilitySuffix: NullabilitySuffix.none);
    final X2 = X.instantiate(nullabilitySuffix: NullabilitySuffix.none);
    print(X1 == X2);
  }

prints true.

[yanok]

@scheglov My question was "is equality supposed to work for self-referencing type variables, or is it a known limitation?". I guess your answer implies that it is supposed to work.

For the exact failing test case, I didn't try it myself, but judging from the error reported in this bug, I think you have to inherit m1 and then get it via InheritanceManager3.getMember2, like here, but now with T extends Foo<T>.

[scheglov]

My understanding is that type equality is not defined by the language specification. @eernstg

I can only see 20.5 Function Types that says

I would say that two TypeParameterTypes are equal only when the are based on the same TypeParameterElement, not just have the same name. We might have be somewhat lax in the analyzer, and return true even in other cases, but this breaks in other cases.

I don't know what to advise here without getting into details how you use these types.

[eernstg]

I'm pushing for a definition of type equality which is based on this section. The section is specifying equality for Type instances, but it implies a similar notion of type equality for types. I've used that in the proposed updates for null safety, dart-lang/language#2605, but that hasn't yet been landed (pieces of it are under review).

The equality test would then be (ignoring * types because they are pre-3.0): Consider two types S1 and S2, normalize them to get U1 and U2, and then compare U1 and U2 structurally: if they do not have the same structure then they are not equal, if they do have the same structure then they are equal if and only if they are equal at each subterm which is a type, and atomic denotations of a type are equal if they denote the same declaration (e.g., C and prefix.C may be the same type). I'm a little worried about using the phrase 'syntactically equal' to describe this relation, but we all know what's required. ;-)

In any case, type parameters would be subject to this structural comparison, so void Function<X extends Foo<X>>() and void Function<Y extends Foo<Y>>() should be recognized as equal. Seems to work:

class Foo<X> {}

void Function<X extends Foo<X>>() f = <X extends Foo<X>>() {};
void Function<Y extends Foo<Y>>() g = f; // No error.

typedef F = Function<X extends Foo<X>>();
typedef G = Function<Y extends Foo<Y>>();

void main() {
  print(F == G); // 'true'.
}

The case where two distinct type parameters have the same name must of course consider them different because the can have different values (except X extends Never and X extends Never ;-).

class C<X extends Foo<X>> { // F-bound doesn't matter, but let's just keep it.
  late X x1;
  void foo<X extends Foo<X>>(X x2) => x1 = x2; // Error.
}

The error is "A value of type 'X' can't be assigned to a variable of type 'X'" which sounds confusing, but is correct.

[yanok]

@eernstg Thanks for the detailed explanation! That matches my intuitive expectations of how it should work.

@scheglov Uh, I should have debugged it a bit myself before asking you. I think in general it works as I expected it to work and as Erik describes it. I was wrong to identify the problem to be equality not working for bounded type variables. It turned out, the problem is sometimes in T extends Foo<T> the two Ts don't refer to the same element. And I think they should, that matters not just for Mockito but also for general correctness of the analysis.

"Sometimes" == if I get an inherited method from a generic class with InheritanceManager3.getMember2 and then apply a substitution (even an empty one) to it. I added some tests in cl/545222226: two tests are passing (one with no inheritance and another one with no type parameters on the classes), but the third one is failing.

[scheglov]

I'm not aware about any error with the correctness of analysis that happens because of this. In the most cases we use subtype operation, and while doing this for FunctionTypes, we make sure that they have the same type parameters.

I updated the failing test to print instead of checking.

  solo_test_getMember_fromGenericSuper_method_parameter_bound_substituion() async {
    await resolveTestCode('''
class Foo<T> {}
abstract class A<XA> {
  TA foo<TA extends Foo<TA>>();
}

abstract class B<XB> extends A<XB> {}
''');
    final B = findElement.classOrMixin('B');
    var foo0 = manager.getMember2(B, Name(null, 'foo'));
    final foo = ExecutableMember.from2(foo0!, Substitution.empty);
    final T = foo.typeParameters.single;
    final otherT = (T.bound as InterfaceType).typeArguments.single;
    // expect(otherT.element, same(T));
    print(identical(otherT.element, same(T)));
    print(typeSystem.runtimeTypesEqual(foo0.type, foo.type));
  }

As you can see, runtimeTypesEqual() returns true.

[yanok]

So, are you claiming this is not a bug? I'm not totally buying this. For the following reasons:

1. Correct me if I'm wrong, but I think substitution works via element equality. So if I start with this broken ExecutableMember foo, where two Ts in the type parameter are not equal, and I will try to substitute the original T, it won't work correctly.
2. Even with runtimeTypesEqual(), it works with the function type indeed, but runtimeTypesEqual(foo.returnType2, otherT) still returns false.

[scheglov]

Yes, when we do substitution, we need to use the type parameters that are used in the type in which we do the substitution, not from any other type that might have type parameters with the same names. This probably works, otherwise we would have much bigger issues.

Yes, when we run runtimeTypesEqual(), we should use the whole FunctionTypes, because they might have type parameters. You will get equality is two return types already use identical type parameters, but it will return false otherwise. The trick is that when we compare FunctionTypes, we do make them use the same type parameters.

[yanok]

Hm... everything that you say does make sense to me, but I fail to see how it matches to the example in question.

Sure, with the analyzer's representation for type variables, one has to be careful while doing substitution and use the matching type parameters. But I'm using an empty substitution, that should hopefully satisfy the condition.

Then, of course, if one starts with two equal FunctionTypes, takes them apart and then compares the corresponding bits, they could be not equal, exactly because of the thing you mention. But in my example I deconstruct a single FunctionType and then compare bits that were equal before the substitution and after the substitution they become non-equal.

Like, if we have two function types A Function<A>(A) and B Function<B>(B), they are equal, but if we would simultaneously compare let's say the result types, then they could be not equal. But if we just compare argument type to the result type for any of them, I expect the comparison to return true, regardless of how type variable is named. Do you agree with this?

[yanok]

Ok, I think I figured this out.

Turns out FunctionTypedElement has typeParameters, returnType and parameters fields, but the same info is also accessible via type field (as type.typeFormals, type.returnType and type.parameters resp). And for the results of getMember/getMember2 calls they don't always agree. type doesn't have this problem of inconsistency between the type parameter and its bound in any of the examples I came up with, and that explains why there is no visible manifestation of this: main analysis code is careful enough to use type where it matters. So, I guess technically you are right and this is not a bug. But for us, mere mortals using analyzer as a library, this is super confusing.

This also paves us a path to fix the Mockito codegen: we just have to use type everywhere. I'll send a fix soon.

So, there is no user visible bug, but a number of suspicious behaviors:

1. Two ways to access seemingly the same bits of information: typeParameters, returnType and parameters are dubbed with type fields.
2. typeParameters don't agree with type.typeFormals; and I mean they are not just different elements (that's fine I guess), but the invariant that holds for type.typeFormals breaks for typeParameters.
3. empty substitution has effects. I think people normally expect it to be no-op.
4. for some examples getMember2 result is ok and getMember result is broken; while for others both are broken, I added some examples in https://dart-review.googlesource.com/c/sdk/+/312401.

@scheglov Do you want me to file a SDK bug for this, or do you think this is all fine?

[yanok]

Had to revert the fix, as it broke some existing tests, looking.

[yanok]

I believe https://dart-review.googlesource.com/c/sdk/+/312401 would allow us to revert the hack on Mockito side.