Specify UP on extension types.

[lrhn]

The current definition of the UP ("least-ish upper bound") algorithm is specified by cases on structural type constructs, recursing on subterms in some cases, Then at the bottom, where it hits a pure named type, it uses the old "guess a common superinterface" algorithm, which is currently guaranteed to give at least Object (which may than get a or more ? added on the way back from the recursion).

That algorithm does not account for extension types, and it probably has to. Somehow.

Assume for now that an extension type can implement (declare as supertype) other extension types which share a representation type, and supertypes of the representation type. (And it is still limited to at most one instantiation of any specific generic type in the entire supertype graph.)

Then consider:

extension type Nullable(Object? _) {}
extension type NullableInt(int? _) implements int? {}
extension type Rec((int, int) _) implements (int, int) {}

We need to be able to find:

UP(Nullable, Object)

Must be Object?, since Object is not a supertype of Nullable. We need to be able to find that result,
even though NON_NULL(Nullable) will have to be Nullable again.

Currently, the only type construct where T is nullable and NON_NULLABLE(T) == T is FutureOr<NullableType>.
The FutureOr is handled in its own case in the UP algorithm, and all other nullable types are either special cased (special top types like dynamic or Null itself) or a type of the form S?, which is handled by a structural rule of its own, by recursing on S.

We should make sure that the algorithm will not assume nullability has been handled, and do "If T is nullable, continue with NON_NULL(T)" and go into an infinite regress.

For Nullable, none of those patterns work, and we will reach the final case of the initial UP algorithm with a type which is still nullable.

At that point, we might be able to use the existing algorithm, as long as we add Object? to the types we consider as possible shared supertypes, so we always have at least one shared type to choose.

UP(NullableInt, int?)

This is similar. The current UP cases may peel away the ? from int?, and then we end at the final case with NullableInt and int, which share no declared supertype.

However, int? would be a valid result, so if we can find that as a result, we it will be optimal.

(I don't have a concrete idea for how to do that, haven't had time to look for one, just recognized the problem.)

UP((int, int), Rec)

Here the current algorithm will find one record type, check if the other is a record type with the same shape, and if not it will give up on record types and fall back to (at most) Record. That was safe since there were no subtypes of record types that were not record types themselves.

(Also, can an extension type implement two different record types, like

extension type P((int, int) _) implements (int, num), (num, int) {} // ?

Enquiring minds want to know!)

Summary

The UP algorithm needs to account for extension types somehow.

They are new types. If we allow them to be subtypes of arbitrary supertypes of their representation type, then our existing approach to UP might not work, since it assumes that you can handle structural types first, inherited supertypes second.
When an extension type can have a structural supertype, that gets more complicated.

We can (but I hope we won't) disallow using any non-class type as non-extension-type supertype.

That's fairly restrictive. You cannot declare an extension type on a particular record, and be a subtype of the record type.

It won't allow:

extension type MapEntry<K, V>._(({K key, V value}) _it) implements ({K key, V value}) {
  MapEntry(K key, V value) = this((key, value));
}

And it won't even allow:

extension MaybeString(String? _it) implements String? { ... }

because String? is a structural type. But if your representation type is nullable, all supertypes are nullable, so no extension type on a (potentially or actually) nullable representation type can declare any non-extension type supertype.

On the other hand, UP will work. We'll still need to allow Object? as result, since a nullable extension type does not have Object as supertype, but other than that, when we reach the non-structural step of the algorithm, we can take the nominative superinterfaces (extension type and non-extension type) of the type, and try to "guess a common superinterface" with those, without risking any of those types being structural types that we need to process again.

[eernstg]

Based on these discussions, the proposal in #3182 makes it an error for an extension type to have several kinds of types in its implements list, including record types, function types, top types (covering dynamic, void, and more), Null, and union types (T? and FutureOr<T>).

We can start up using a relatively strict rule here, and then add types like T? if it turns out to be useful and work well (e.g., with some updated version of UP).

[eernstg]

@lrhn, have we already done what we want to do in the upcoming extension types feature? If there's no more information in this issue which is going to be used then it might be useful to close it.

[lrhn]

I believe the specified Up is doing the right thing now, so this is covered.

[eernstg]

Very good! Then I'll close it.