How should intersection typed receivers be handled during extension method resolution?

[eernstg]

[June 2024: This issue has been clarified by revisiting the specification. The analyzer should report a compile-time error like the one that the CFE currently reports.]

Cf. #52077 for a situation where this question came up. Cf. #52077 (comment) where @lrhn first clarified the situation.

Consider the following program:

class Filterable {}

class Filter<T extends Filterable?> {
  void test(T t) {
    if (t is! Filterable) return; // Should promote `t` to `T & Filterable`.
    t.when(); // Accepted by analyzer. Error from CFE.
  }
}

extension When<T extends Filterable> on T {
  T? when() => null;
}

void main() {}

The type of t at the method invocation t.when() is T & Filterable. In order to invoke the extension method when, the extension needs to receive a type argument, which implies that T & Filterable must be erased to a type which is representable at run time.

If it is erased to T (which is typical for intersection types when reified), the extension does not match, and we should get a compile time error. This appears to be the approach taken in the CFE.

If it is erased to Filterable (possibly after trying T and failing), the invocation can resolve to When.when, and there are no errors. This may be the approach taken by the analyzer—at least, it does not report any errors for this program.

Pragmatically, it seems desirable to try each of the two operands of the intersection type. However, it might create difficulties (say, in terms of an exponential time/space usage) because it is a deviation from the one-pass strategies that we are otherwise using.

So what is the desired approach? @dart-lang/language-team, WDYT?

[lrhn]

An extension applies to a type iff the static type of the extension is a subtype of the on type of the extension, after doing type inference for any type parameters of the extension in the same way we'd do for a constructor of a similar class. That is:

extension Ext<X> on Foo<X> {
  ...
}

applies to a static type T iff ExtClass<X>(e as T) would be valid for:

class ExtClass<X> {
  ExtClass(Foo<X> _);
}

and it infers type arguments in the same way (but without any context types being involved, the argument was already inferred, and the constructor invocation itself behaves like it's in receiver position).

So the current correct behavior is defined by how we do inference on a similar constructor. The analyzer is not doing the correct thing.

The error message I get for:

class ExtClass<T extends num> {
  final T foo;
  ExtClass(T this.foo) {
    print("ExtClass<$T>");
  } 
}

void baz<T extends num?>(T value) {
  if (value != null) {
    // Is intersection type, both `T` and `num`.
    T v1 = value;
    num v2 = value;
    print(v1 == v2);
    
    var e = ExtClass(value).foo;
  }
}

is, in dart2js:

lib/main.dart:15:13:
Error: Inferred type argument 'T' doesn't conform to the bound 'num' of the type variable 'T' on 'ExtClass'.
    var e = ExtClass(value);
            ^
lib/main.dart:1:16:
Info: This is the type variable whose bound isn't conformed to.
class ExtClass<T extends num> {
               ^

and in the analyzer:

error line 15 • 'T' doesn't conform to the bound 'num' of the type parameter 'T'.[ (view docs)](https://dart.dev/diagnostics/type_argument_not_matching_bounds)
Try using a type that is or is a subclass of 'num'.
The raw type was instantiated as 'ExtClass<T>', and is not regular-bounded.

In both cases, the inferred type argument is T, it's not a valid type argument for a concrete instantiation of ExtClass, and therefore we get a compile-time error.

The extension method should then do the equivalent type inference, which means inferring T as type argument for the extension.

extension Ext<T extends num> on T {
  T get foo {
    print("$this:$runtimeType @ $T .foo");
    return this;
  }
}

void bar<T extends num?>(T value) {
  if (value != null) {
    var e = value.foo..st<Exactly<T>>();
  }
}

// with the usual:
typedef Exactly<T> = T Function(T);
extension <T> on T {
  T st<X extends Exactly<T>>() {
    print("$this:$runtimeType @ $T");
    return this;
  }
}

Dart2Js gives the error

lib/main.dart:10:19:
Error: The getter 'foo' isn't defined for the class 'num'.
    var e = value.foo;
                  ^^^
Error: Compilation failed.

which is correct, because the inferred type argument being invalid means that the extension is not applicable.
The corresponding explicit extension invocation Ext(value).foo is not valid because it infers T as type argument, and T is not a valid type argument to Ext. Therefore Ext is not applicable for the implicit extension invocation.

The error here is that the analyzer considers Ext.foo applicable, and applies it, and then proceeds to bind T of Ext to a type which is not a valid type parameter.

---

The more interesting question is whether we'd want to change how we choose the projection of an intersection type into a valid type argument.

If an intersection type is inferred as a type argument, and the intersection type satisfies (is a subtype of) the type parameter bound, then at least one of the types of the intersection is a subtype of the bound.

We currently always choose the type variable as the type argument.
We could choose to check whether the type variable is a valid argument, and if not, use the second operand of the intersection instead.
That should apply everywhere we need to massage an intersection type into a type arguments, not just for extensions.

If we're already checking whether the intersection type is a subtype of the bound, then there shouldn't be much extra work in remembering which of the intersected types was that (first) proof of being a subtype.

But that depends on where in the type inference algorithm we remove the intersection.
If we have multiple type parameters, with subtype relations between them, then it might matter for inference of other type arguments whether we reduce T&num to T or num early or late.
If we do it too early, we may not know the bound yet, if the bound depends on other type arguments.
If we do it too late, the T and num types might both have affected the other type arguments, and choosing one of them isn't necessarily enough.

It seems the analyzer has some issues with intersections and type parameters in general. Take:

void foo<V extends num>(V Function(V) f, V v) { f(v); }

void bar<T extends num?>(T v) {
  if (v != null) { // v : T & num
    foo((x) => x, v);
  }
}

where dart2js gives an error because T is not a valid argument to V, but the analyzer says:

error
line 5 • The argument type 'T & num Function(T & num)' can't be assigned to the parameter type 'T Function(T)'.

The function type of (x) => x is inferred to T & num Function(T & num), which only makes sense if that's the context type, which means V is T & num. But the actual parameter type is T Function(T), so erasure happens between creating the context type for the argument expression, and checking that the argument expression's static type is assignable to the parameter type.
(Also, T & num is not a valid function parameter type, just like it's not a valid type argument type.)

[eernstg]

That's a very nice analysis, @lrhn!

However, I don't think we can claim that one or the other erasure is as specified, because inference.md is as far as we've gotten with a specification of inference, and it does not mention erasure of intersection types.

One thing we did specify is that the future type of X & B can be the future type of X (if it has a bound that has a future type), or the future type of B. So in that case we do allow an erasure to the second operand of the intersection.

Otherwise, I agree that implementations generally erase X & B to X when the type must be reified.

We've obviously got an issue if any tool considers a function literal (or indeed any expression) to have the type T & num Function(T & num), but that would be an SDK issue. Cf. #52127.

[lrhn]

We may not be able to say which erasure is required, but we can require the behavior to be consistent.
Every platform agrees on the constructor invocation, so it's more likely that that's the intended behavior.
(And harder to change).

[eernstg]

tl;dr Based on "normal" invocations, we should erase the intersection type to the improved bound, not to the type variable rd;lt

We have already resolved a very similar question in the current language specification when it comes to class/mixin instance members (not extension members):

1. The interface of a type T which is T₀ bounded for some type T₀ is the interface of T₀, cf. this rule.
2. X & B is T₀ bounded if B is T₀ bounded. Cf. this rule.

In other words, a receiver whose static type is T & Filterable has the interface of Filterable (not the interface of T).

When it comes to extension member invocations we have the following (specified here). This seems to be at least somewhat inconsistent relative to the treatment of class/mixin instance members:

Consider an extension application a of the form E(v), where v is a fresh
variable with static type S. It is required that an occurrence of a in the
scope which is the current scope for e is not a compile-time error.

[Commentary] In other words, S must match the on type of E. With type inference, inferred
actual type arguments may be added, yielding E<S1 , . . . , Sk >(v), which is
then required to not be an error. If this inference step fails it is not an error,
it just means that E is not applicable to e.

E is the given extension declaration, e is the receiver (that might be about to invoke an extension member), and S is the static type of e.

This means that until we have a complete specification of type inference we cannot completely determine whether or not the application should succeed (see inference.md), but we can create a program that should behave the same in this respect:

class Filterable {
  void filterableMember() {}
}

class Filter<T extends Filterable?> {
  void test(T t) {
    if (t is! Filterable) return; // Promote `t` to `T & Filterable`.
    t.filterableMember(); // OK, so promotion did happen.
    When(t).when(); // Error from both the CFE and the analyzer.
  }
}

class When<T extends Filterable> {
  final T it;
  When(this.it);
  
  T? when() => null;
}

In this case type inference yields When<T>(t).when(), which is a type error because T doesn't satisfy the bound Filterable of When. This behavior is not surprising because we often erase intersection types to the type variable when it needs to be reified.

However, we would get a behavior which is more consistent with the treatment of class/mixin instance members if we used an erasure to Filterable rather than T when deciding on extension method applicability, because the interface of the promoted bound type Filterable is guaranteed to be at least as rich as the interface of the type variable T (because the former must be a subtype of the bound of the latter), and a normal class/mixin instance member invocation will indeed use the promoted bound type.

So I'd recommend that we erase an intersection type T & B to B in the case where we are determining the applicability of a given extension method.

[lrhn]

I agree that the interface argument suggests that the extension members should be based on the promoted type.

The difference is that while a type variable itself has no members, it gets every member except "The Object 5" from its bound or promotion, where the promotion is known to be a subtype of the bound, extension methods can actually add members to any type.

extension <T> on T {
  List<T> listOf() => [this]; 
}
void foo<T>(T t1, T t2, void Function(List<T>) callback) {
  if (t1 is int && t1 >= 0) {
    callback(t1.listOf());
  } else {
    callback(t2.listOf());
  }
} 

This is a pathological and tortured example, it may very well be that using the promoted bound is always what you want.
It fits shows that it's possible to have extension methods that apply to the base, unbounded and unpromoted type variable type, which won't have any normal interface members.
It's possible.

The most useful approach is the selective one: the extension type applies if either part of the intersection type would satisfy the type constraints, then we erase to the part that actually did.
It means trying both. Maybe even introducing a non-trivial rule for which to choose if both match (which could even be based on context type: if the type variable occurs in the context type, definitely choose it).

The reason for all this complexity is that we've taken away your default override strategy. Doing (x as int).extensionMember will still keep the receiver type of x as T & int.
If we take away the syntax you'd use to avoid the problem, we need to avoid it for you.

[eernstg]

Best of both worlds?

We could reify an intersection type as the run-time type of the value of the promoted variable, as described in dart-lang/language#3831.

[FMorschel]

I'm not entirely sure if this is a new issue (or is intentional) because it still has intersection types being handled, just not during extension method resolution. If it is, please tell me so I can open a new one.

Consider:

mixin M {
  void m();
}

class M1 with M {
  const M1();
  @override
  void m() {}
}

class A<T> {
  const A(this.o);
  final T o;
}

class B<T extends M> extends A<T> with M {
  const B(super.o);
  @override
  void m() => o.m();
}

void foo<T>(T o) {
  late A<T> a;
  if (o is M) {
    a = B<T>(o); // 'T' doesn't conform to the bound 'M' of the type parameter 'T'. Try using a type that is or is a subclass of 'M'.
  } else {
    a = A<T>(o);
  }
}

Edit

Also, if you remove <T> there, another error occurs: The argument type 'T & M' can't be assigned to the parameter type 'Never'.

And if you add <M>: A value of type 'B<M>' can't be assigned to a variable of type 'A<T>'. Try changing the type of the variable, or casting the right-hand type to 'A<T>'.

This case of course has a possible solution, that is adding <M> and making a cast to A<T> (not B<T> because we get the first error) as suggested by the lint but that could maybe be solved the same way, I think.

[eernstg]

It is working as intended when we get a compile-time error at B<T>(o): The type test shows that the run-time type of o is M or a subtype thereof, but T can still be anything, for example Object?. So we can't conclude anything about the value of T.

That's true in general: Promotion says something about the type of a specific object (namely the one which is being tested), and a variable is promotable if we can see at compile time that it will refer to that same object for a while, and then we can give that variable the promoted type. But the type variable has its own value and we can't learn anything about that by testing the type of the object.

[FMorschel]

I see, thanks for explaining!

[FMorschel]

I'd just don't see why in the case where I don't assign any type to B (the second case) it still could not solve.

I think that's what I'm actually asking here.

If your last proposal (#3831) got through, would that solve this as well?

Edit: because I could simply not (or I could not see how to) assign a value to o that would not satisfy both values there as you can see.

[eernstg]

Also, if you remove <T> there, another error occurs: The argument type 'T & M' can't be assigned to the parameter type 'Never'.

The actual type argument S which is chosen by type inference (transforming B(o) to B<S>(o)) had to have the value Never: We must have S <: T (such that B<S> <: A<T>) and we also need S <: M (such that B<S> satisfies the declared bound. The greatest lower bound of T and M is Never (that's basically the only lower bound of those two types).

So we're working on B<Never>(o), doing normal type checking, and o fails to satisfy the requirement, because the static type of o isn't assignable to the type Never.

If you're convinced that the surrounding code will behave well (that is, it will satisfy some constraints that aren't expressible in the type system) then you could achieve the same semantics in a way that is guided by some run-time type checks:

...

void foo<T>(T o) {
  B<S> fooHelper<S extends M>(S o) {
    // In this body the type system knows that `S extends M`,
    // so we can create a `B<S>`.
    return B<S>(o);
  }
  
  late A<T> a;
  if (o is M && <T>[] is List<M>) {
    // At this time we know that `T extends M`. The type system
    // won't recognize that, but we can force it using a dynamic
    // invocation of a generic function.
    a = (fooHelper as Function)<T>(o);
  } else {
    a = A<T>(o);
  }
}

...

The crucial part is that we need to know that T extends M in order to be allowed to create a B<T>, but there is no way we can promote a type variable. So we test this relationship using <T>[] is List<M> (which is true if and only if T extends M), and then we go ahead and act on it: fooHelper<T>(o). However, we can't use that invocation directly, because the type system doesn't understand that T extends M, so we have to do the same thing without compile-time type checking: (fooHelper as Function)<T>(o). This will be checked at run time, but the checks are guaranteed to succeed.

PS: dart-lang/language#3831 was a crazy idea, I dropped it again. ;-)

[FMorschel]

Would it be reasonable if I created an issue to add some type of check to type parameters? Or is it something that the CFE is against in some way?

A way for us to test that so that inside that tested context we could consider T as a subtype of M? Some sort of help/guidance to type solving.

[eernstg]

I think that would be interesting! We've never really explored the idea that type parameters could be subject to type tests or type casts in a way which is similar to the instance operations o is T and o as T, respectively. The most complex part of that effort would probably be to extend the flow analysis such that we don't just get 'true' or 'false' if we evaluate S <: T (strawman syntax), but we're also able to use that piece of information to allow expressions that would otherwise have been type errors.

[eernstg]

To recapitulate: This is an old issue, and we haven't resolved it. I'd recommend that the interface of the promoted type B is used to determine which members of a receiver of type X & B can be invoked, and with which signatures, for any kind of members including extension instance members.

[eernstg]

@dart-lang/language-team, can we move on this?

[leafpetersen]

@dart-lang/language-team, can we move on this?

I skimmed the issue, I don't see what it is we are proposing to move on. My understanding is that the implementations behave consistently, and consistently with the model that we've proposed for thinking about this (treat it as constructor inference). Am I missing something? Is there an inconsistency we need to resolve? Otherwise I think we can close this, I'll go ahead and do. If there's a proposal to make a change, maybe we can pursue it in a clean issue?

[eernstg]

My understanding is that the implementations behave consistently

As I mentioned in the initial message of this issue, we get this response: // Accepted by analyzer. Error from CFE. So we do need to make a choice.

treat it as constructor inference

Ah, of course! It is then an analyzer bug, that is, the analyzer should report an error in the original example. In particular, we do get the error from both tools with this variant:

class Filterable {}

class Filter<T extends Filterable?> {
  void test(T t) {
    if (t is! Filterable) return; // Should promote `t` to `T & Filterable`.
    When(t).when(); // Rejected by the analyzer and the CFE.
  }
}

class When<T extends Filterable> {
  final T t;
  When(this.t);
  T? when() => null;
}

void main() {}

I'll reopen the issue, move it to the SDK, and label it accordingly.

[dart-github-bot]

Labels: area-language, type-question
Summary: The issue concerns how to handle intersection typed receivers during extension method resolution. The question is whether to erase the intersection type to the left operand (T) or the right operand (Filterable) when resolving the extension method when.

[bwilkerson]

@scheglov