Give Type a type argument such that T is Type<T>

[eernstg]

This issue is a proposal to change the built-in class Type such that it accepts a single type parameter with no bound, and to change instances of Type that reify a Dart type, such that they satisfy t is Type<T> whenever t reifies T.

Note that this feature has been mentioned in several different discussions, e.g., in connection with abstract static methods and virtual static methods, #356. This issue ensures that we have a specific location where the concept is explicitly proposed.

Motivation

The main motivation for this feature is that it allows for an improved static analysis of reified types.

In particular, we could express something which is similar to static extensions (if we allow int.foo() to call an extension method on a receiver of type Type<int>, otherwise we'd need to use (int).foo()):

extension IntStatics on Type<int> {
  int parseHex(String source, {int onError(String source)?}) =>
      int.parse(source, radix: 16, onError: onError);
}

extension AnyStatics<X> on Type<X> {
  bool isTypeOf(Object? o) => o is X;
}

void main() {
  var i = int.parseHex("0x1F");
  print(String.isTypeOf(1)); // 'false'.
}

Next, it would be possible to determine statically that a type variable satisfies a bound which is stronger than the declared one. For example, we could allow the following:

class A<X> {
  void foo(X x1, X x2) {
    if (X is Type<int>) { // This could promote `X` to `X extends int`.
      // `x1` and `x2` would then have type `X & int`.
      print(x1.isEven == x2.isEven); // OK.
    }
  }
}

Another example usage is dependency injection, that is, factories associated with class hierarchies:

abstract class Animal {}
abstract class Herbivore implements Animal {}
abstract class Carnivore implements Animal {}
class Cow implements Herbivore { toString() => "cow"; }
class Cat implements Carnivore { toString() => "cat"; }
class Human implements Herbivore, Carnivore { toString() => "human"; }

extension AnimalFactory<X extends Animal> on Type<X> {
  static var _factories = {
    // For abstract classes, deliver a default.
    Animal: Cat.new,
    Herbivore: Cow.new,
    Carnivore: Cat.new,
    // Concrete classes, deliver exactly the requested type.
    Cow: Cow.new,
    Cat: Cat.new,
    Human: Human.new,
  };
  X create() => _factories[this]!() as X;
}

// The precise value of the type variable need not be known statically.
X doCreate<X extends Animal>() => X.create();

void main() {
  print(Herbivore.create()); // 'cow'.
  print(Cat.create()); // 'cat'.

  Human human = doCreate();
  print(human); // 'human'.
}

Static Analysis

A type literal t which is statically known to be a reification of a type T is statically known to have type Type<T>. Otherwise, Type<T> is treated just like any other generic type.

An expression of the form X is Type<T> where X is a type variable would promote X to X extends T in the true continuation, in the case where T is a subtype of the bound of X.

Dynamic Semantics

A reified type t that reifies the type T has a run time type such that t is Type<S> is true if and only if T <: S.

[Levi-Lesches]

This would also help quell the many questions of why T is MyType doesn't work, such as #1734, #1756, #1814, #1997, #1971...

[lrhn]

We have considered this before. We decided against making Type generic because we expected that a later "open type" functionality would allow you to access the runtime type arguments of a generic type as a type variable.
Combined with having all Type objects carry their own type as a type, that would allow turning a Type object into a type variable, and severely affect the ability to tree-shake types.

Currently a Type object cannot be reified as a type. The only types that can occur as the types of type variables are types that exist as type arguments in the source (post inference, not necessarily literally) . However, having each Type object carry a real type means that any dynamicVariable.runtimeType can cause every type to exist at runtime as a type variable binding, even if only for the Type object itself. That, by itself, will likely affect tree-shaking.
Allowing "open type" on top will just make the problem completely unmanageable.

For static extension methods, let's do it properly instead! #723. (No, that won't work for AnyStatics.)

For checking the type relations of type variables, do that directly. #459
We'd have to special case to make T is Type<int> promote T to int, and if we are special casing anyway, why not just allow T <: int as an operator, or special-case T is int when T is a type variable. No need to mention Type.

I want people to stop trying to use Type objects for anything, not encourage more uses.

[Levi-Lesches]

+1 for special-casing T is int (I also upvoted #459). It's intuitive and won't cause any confusion because the current behavior of T is int is never what users actually want (not to mention, we shouldn't even have a condition that never does what we want). The notation of T <: int may be well-known in this repo, but I hardly think it'll be the first thing the average user thinks of when they try type-checking.

[eernstg]

@lrhn, we did indeed discuss introducing an existential-open construct several times, e.g., based on type patterns (#170):

void foo(List xs, Object? o) {
  xs as List<var X>; // Guaranteed to not throw; will bind `X` to the actual type argument.
  // `xs` is now promoted to `List<X>`.
  if (o is X) xs.add(o); // No dynamic type check needed.
}

That mechanism will allow programs to access the value of type arguments of existing objects at their run-time type or any superinterface. As soon as a given library has imported List, it's possible to perform a test like xs is List<var X>, and similarly a superinterface like Iterable can be decomposed with xs is Iterable<var Y>.

The ability to extract the actual value of all type arguments of all classes in scope would presumably make it very difficult to erase type parameters, so that's definitely a cost which is associated with existential-open constructs of any kind.

However, changing the built-in Type class to have a type argument does not provide a similar affordance. If you have a reified type t then it was created as an instance of Type in a situation where the representation of the type T that t reifies was available, and this means that creating t as an instance of Type<T> rather than creating it as an instance of T does not require the creation location to have access to any further information than what is required today. It is true that the representation of T may now be propagated to additional contexts, but that's also true if we evaluate <T>[] in the same context, and then pass that list around.

Note also that a Type<T> does not provide the same functionality: For example, it does not help us at all finding the value of the actual type argument for a given list at the type List, not to mention getting access to that actual type argument as a type.

With that in mind, I believe that it is simply irrelevant to think about the properties of existential-open mechanisms in order to say anything about the implications of adding a type argument to Type.

Currently a Type object cannot be reified as a type

Perhaps you could provide an example showing how the addition of a type parameter to Type would give us this capability?

For checking the type relations of type variables, do that directly

I'm not so happy about the syntax T is int because it is a completely new semantics associated with an existing operator. For instance, let's say that o has static type Object, should we then be able to get true as the result of evaluating o is int both when o is 1 and when o is the reified Type for int?

[lrhn]

If the code contains e is SomeType then the compiler knows that it needs to retain the ability to recognize SomeType instances.
If the code contains e is X (X a type variable), then the compiler knows that it needs to retain the ability to recognize any type that X might be bound to. That's currently limited to any type that is actually used as a type argument. If <SomeOtherType> never occurs, then X cannot be bound to SomeOtherType.

If we can open a generic type, like if (e1 is List<var Y>) ... e2 is Y ..., then that doesn't change. The type of Y can only be a type which is already bound to a type variable. (We might be able to do flow-based analysis to further narrow down which type variables can actually be which types, but that's extra.)

If we make Type objects be generic, and we allow .runtimeType to create a Type object from any object, then we can no longer know which types can occur as type variable bindings from only looking at <...> type arguments of the source.
We also have to look at .runtimeType, because that has now become a way to introduce a new type variable binding dynamically, one which doesn't correspond to a type argument in the source.

Without an "open type" or binding run-time type variable pattern match, it's probably not a problem. That's why making Type generic would not itself be a problem, but it would make it much harder to later add an "open type"-like functionality, like binding type patterns.
I'd rather have binding type patterns than generic type objects, though, so that's why I don't want to have generic Type objects.

Now, if we remove .runtimeType, I think it will actually be perfectly fine. Then you can't create a type argument from something which is not already available as a real type, not just a Type object (a type reflection).
Just move runtimeType into dart:mirrors where it belongs.

[eernstg]

If the code contains e is SomeType then the compiler
knows that it needs to retain the ability to recognize SomeType instances.

Indeed, and that is also necessary in order to compile code where a List<SomeType> might be created, and some objects may be added to that list. Also, OO dispatch can only be performed if each object has a representation of its run-time type. So that level of dynamic type support is probably below the requirement threshold: This kind of feature must be available in any Dart program, period, and there is no need to consider is as a special case.

If the code contains e is X (X a type variable) .. [then we must recognize]
any type that is actually used as a type argument

That is again true if the code creates a list (or any other instance of a generic class) where that 'any' type is used as a type argument. Again there's nothing special about is.

If we can open a generic type

.. then we can go further: If a class C<X> never uses X (all superinterfaces where X or a type containing X is passed into also cannot use X) then I suspect that it would be sound to erase the type parameter. However, unused type variables aren't extremely useful, so maybe we don't have many of them. ;-)

However, we don't even do that! For instance, developers could toString the type of an instance of C, and they'd expect to find a textual representation of the type argument in the resulting string.

We also have to look at .runtimeType, because that has now become
a way to introduce a new type variable binding dynamically,

And how would you create an instance whose run-time type is C<T> or where C<T> is some superinterface of the run-time type, without passing T (either directly to the instance creation expression, possibly after inference, or indirectly via superinterface clauses on C)? In other words, if an object has a type argument T then it is already the value of a type variable.

However, the access to an instance of Type<T> is no worse than creating a <T>[], and if you can obtain a List<T> and you have an existential open then you can also get access to T. Same thing if you have access to a C<T>, or any other instance where T is an actual type argument.

So the existential open does make a difference, but that difference exists with or without Type<X>. Type<X> does not make existential open more powerful, or more expensive.

We could of course remove .runtimeType and/or reified types entirely. I know this is a long-standing preference for at least several people, I'm just not convinced that this is a good idea. For instance, we do have millions of lines of code where dependency injection is used, and it's not obvious to me that this was a wrong design decision.

It's a little bit like mutable state: Pure functional languages exist (so-so), but even Haskell uses monads to provide access to effectful computations (and it has unsafe stuff as well). Even if you can write the software you need without a certain (ugly?) language mechanism, it is not necessarily the best trade-off for all developers at all times. And I happen to think that a very low level of support for reified types is likely to be justified; and this proposal is intended to make that feature a bit more statically analyzable.

Just move runtimeType into dart:mirrors where it belongs.

The point is that runtimeType is available on all platforms, and it would be massively breaking to take it away (alternatively: it would cause serious disruption if lots of large programs would then have to start using 'dart:mirrors', to the extent that this is even possible). It might appear to be a pure and beautiful change; I'm just not convinced that it is an improvement.

[lrhn]

And how would you create an instance whose run-time type is C<T> or where C<T> is some superinterface of the run-time type, without passing T (either directly to the instance creation expression, possibly after inference, or indirectly via superinterface clauses on C)? In other words, if an object has a type argument T then it is already the value of a type variable.

By having an instance of T and doing o.runtimeType, thereby getting a Type<T>, which is exactly of the type C<T> (for C == Type).

If I have a class Foo somewhere in my program, but no occurrences of <Foo> as a type argument anywhere (including no <Foo>[] lists), no is Foo, as Foo or on Foo catch clauses, and all Foo variables are statically determined to be used only soundly (so no runtime checks are necessary), then the compiler can safely omit the ability to do is Foo.

If (Foo() as dynamic).runtimeType has type Type<Foo>, then I can introduce, at runtime, an occurrences of Foo as a type variable anyway. Since we know the Type class doesn't do is T (so far), that alone doesn't break the optimization.

If we can then also do if ((Foo() as dynamic).runtimeType is Type<var X>) { print(o is X); }, then that optimization does break.
Introducing arbitrary type arguments at runtime (one for any type that you have an instance of) and the ability to turn that type argument into a type variable available to arbitrary user code, together prevents the optimization from safely recognizing that a type is never used in a type check.

Now, arguably, if we allow if (x is (var R) Function(var A)) { /// use R and A } then we've probably lost anyway.

[eernstg]

I don't think it's possible to maintain correct OO semantics unless each object has a representation that offers access to a representation of the type of the object. (C++ does it with structs, but they are by design just storage areas with associated non-virtual functions, and I don't think a compiler is going to be able to turn many Dart classes into structs in that sense). So if we have an object whose run-time type is T then we also have a representation of T at run time.

And how would you create an instance whose run-time type is
C<T> or where C<T> is some superinterface of the run-time type,
without passing T

By having an instance of T and doing o.runtimeType

What I'm saying is that you can't have a specific type T as the actual type argument in the run-time type of an instance (or one of its superinterfaces) without passing T when that object is created. So that actual argument is already represented in the heap.

But nobody said that there is an instance of T, e.g., T could be Never. So we can't just take an instance o of T and do o.runtimeType.

But it doesn't actually matter, because there is a representation of every actual type argument of instances in the heap, so there would not be anything new in being able to obtain yet another copy of such a representation.

If I have a class Foo somewhere in my program, but no occurrences
of <Foo> as a type argument anywhere

An instance of Foo still needs to know where to find its methods, and that presumably amounts to a representation of the type Foo.

I do not believe that any particular optimizations will be enabled just because it is known that Foo will never occur as an actual type argument. Which ones would that be, this one?:

the optimization from safely recognizing that a type is never used in a type check.

Most type checks are of the form e is T where T is a constant type expression, and they can be compiled (by the VM) to a very small number of inlined instructions (known techniques would choose a number for each class, and satisfy that there is a subtype relation if the number for the potential subclass divides the number for the potential superclass, or smart things like that). So checking for a known type can be very fast. It could also be a plain graph traversal, of course, but I'm sure we don't do that. ;-)

Checking for a type variable requires more elaborate behavior, and that is, as far as I know, handled by a routine in the runtime of the VM. I don't know if anything can be optimized if we can guarantee that the set of classes where a subtype test can occur is smaller than the set of classes in the program.

It would be more interesting if type parameters could be erased, but, as mentioned, I do not believe we do that, and I suspect that modern Dart would not allow for doing that to any significant extent anyway.

[eernstg]

@mkustermann, @mraleph, we're going completely into the woods here! Perhaps you could comment? ;-)

Does it sound like a serious performance hit if we were to support the change of Type to Type<X>, with the guarantee that T is Type<T>? How about having an existential open construct, alone, or together with Type<X>?

[lrhn]

The "representation of a type" is not a single monolithic thing. Parts of it can be individually tree-shaken, like specific methods that are not used in the program, or even the ability to do is T where T is a type variable bound to that type (which can be treated differently from just a direct is Foo).

It's AoT compiled code that is affected, not the standalone VM, so there is no runtime-call to do the checking.
I don't know if this is still an issue, but at a time, I'm fairly sure it was.

[mraleph]

I think dart2js (/cc @rakudrama) is always more impacted by changes like these, because their type representation is modularised enough for them to treeshake things at finer granularity. VM does not tree-shake things at this level - generic runtime support to construct arbitrary types and type check against them is always included. If C is included (because you construct an instance of C) so is all information about supertypes of C (transitively) and so on.

So the current state of VM tree-shaking does not really care about this change unless I miss something subtle.

dart2js might be negatively, but I let Stephen provide estimations on how bad would that be.

[Silentdoer]

hi, is there any progress on this issue?

[eernstg]

No decision yet, but the issue serves to make the proposal concrete and keeping it in sight.

@rakudrama, the proposal here is to make Type generic and ensure that the run-time type of a reified type based on a type T is a subtype of Type<S> if and only if T <: S, such that Type instances can be given a more precise static typing. Other things are debated here as well (e.g., obtaining a type variable whose value is taken from a reified type, existential open), but for the core proposal, do you think it would disrupt any dart2js optimizations?

[rakudrama]

It is unclear whether the proposal will create types that are currently are equal but not equal with the type parameter Type.T.

.runtimeType canonicalizes the dynamic type of an object to produce a Type object, removing 'star' types.
Can one contrive to get two Type objects for the type String, one having type Type<String> and the other Type<String*>?

dart2js has an optimization that elides type variables from classes and methods when the type variable is used only to inform .runtimeType.toString(). Either they are replaced with dynamic (I think even when there is a bound), or omitted completely.
I think this will still work - the Type<T> object will have a type parameter that breaks the iff invariant, but the object is used only for its toString() method.

Creating constant Type objects for the values of type literals at program startup will be about twice as expensive, since in addition to creating the dynamic representation of, say Foo, the Type instance also needs to store the dynamic representation of Type<Foo>. Type literals are about 7% of the constant pool for some apps, so this will impact proportion of initial program load attributable to the constant pool by about that much.

[eernstg]

Thanks for the input, @rakudrama!

It is unclear whether the proposal will create types that are currently are equal
but not equal with the type parameter Type.T.

If we have two reified types t1 and t2 then they're specified to be == iff the corresponding types T1 respectively T2 are such that NORM(T1) and NORM(T2) are 'syntactically equal up to equivalence of bound variables'.

In particular, the run-time types of t1 and t2 are irrelevant to the computation of ==. I think this implies that there will not be any cases where the result of t1 == t2 changes as a consequence of a change whereby t1 is Type<T1> and t2 is Type<T2> (we'd still have t1 is Type and t2 is Type, of course, where Type means Type<dynamic>).

Can one contrive to get two Type objects for the type String, one having
type Type<String> and the other Type<String*>?

First, == doesn't care (normalization also removes the legacy marker *), so maybe we don't care. Next, if String is not just syntax, but it is actually the null-safe type String, then the corresponding reified type object should have type Type<String>; if it's Type<String*> then we have a bug. On the other hand, if String is syntax in a legacy library, and it actually means String*, then the corresponding reified type should have type Type<String*>. But it would still be == to the reified type for the null-safe type String. In other words, we would still be able to ignore the legacy marker.

dart2js has an optimization that elides type variables from classes and methods when
the type variable is used only to inform .runtimeType.toString() ...
I think this will still work

This is very interesting! I would assume that any reification of a type variable (e.g., Type get g => X where X is a type variable of the enclosing class) would be just as bad as a usage in the creation of an object (List<X> get g2 => <X>[];), because this means that other parts of the program could need access to the value of X.

However, it seems reasonable to say that X can still be elided if it is only used to call .runtimeType.toString(). After all, I don't actually expect toString() on Type<T> to have to mention its type argument—it is probably fine that it just continues to do what it does today, that is, it shows some information about which type it reifies, and that hasn't changed (and in the case where X is elided it probably just evaluates to something like 'Instance of Type', and we can continue to do that without ever creating an instance of Type or Type<...>). From that point of view it's just an accident that the reified type is also the value of the actual type argument of Type in the run-time type of the reified type object, and toString doesn't care.

Creating constant Type objects for the values of type literals at program startup will be about twice as expensive

This is great to know, thanks! This is the first real cost I've seen in relation to Type<T>, so we obviously need to be aware of it.

[Levi-Lesches]

Creating constant Type objects for the values of type literals at program startup will be about twice as expensive

If this is a problem, there is always the option to only special-case T is MyType (#459), which feels more intuitive IMO.

[rakudrama]

On the other hand, if String is syntax in a legacy library, and it actually means String*, then the corresponding reified type should have type Type<String*>. But it would still be == to the reified type for the null-safe type String. In other words, we would still be able to ignore the legacy marker.

The problem here is that there are now two Type objects which differ in the value of the type variable, so const Maps and the current implementation of switch statements which use primitive equality (effectively identity) no longer work properly in a mixed-mode program.

dart2js canonicalizes all along the chain type expression ⟶ T ⟶ NORM(T) ⟶ Type instance.
Without the type parameter, this ensures that equal Type objects are the same object.

If you redefine == or primitive equality to allow two different Type objects to be equal, dart2js and DDC will have to reimplement switch statements to avoid compiling them to JavaScript switch statements in some cases. We don't currently have the machinery to compile a switch statement to an if-then-else chain, but we will have that machinery somewhere after Patterns are implemented.

We could maintain primitive equality if Type<T> has T bound to NORM(T).
Then we would never have Type<String*>.
Would this have the desired properties?

[eernstg]

const Maps and the current implementation of switch statements which use primitive
equality (effectively identity) no longer work properly in a mixed-mode program.

I think that should be covered by the following:

For runtime implementations which implement identity by choosing a canonical representative for the equivalence class of equal instances, the choice of what type object to canonicalize to is arbitrary in that placement of legacy modifiers in type literals is not otherwise observable in the language

So the case expressions and the keys of const Maps are constant expressions and hence they will be the canonical representative of any given type literal (e.g., the reified String could be chosen to represent String and String*), and any constant expression which is used to choose a switch case or look up a value in a constant map would be canonicalized to the same object.

An identity check could fail in the case where we try to use a non-constant reified type to select the case or lookup the map value, but that's true today as well:

var map = Map<Type, int>.identity()..[List<int>] = 1;

Type listOf<X>() => List<X>;

void main() {
  print(map[List<int>]); // '1'.
  print(map[listOf<int>()]); // 'null' on the vm.
}

If you redefine == or primitive equality to allow two different Type objects to be equal...

This is already true in the vm, so the converse is not a property that Dart developers can rely on in general. But I understand that dart2js canonicalizes some reified types even in the case where they are constructed at run time (like listOf<int>() above).

However, the following seems to allow for a solution anyway:

We could maintain primitive equality if Type has T bound to NORM(T).
Then we would never have Type<String*>.
Would this have the desired properties?

That would certainly have the desired properties, it would still true that t is Type<T> when t reifies T and S is NORM(T) and the run-time type of t is Type<S>.

[dcharkes]

Currently a Type object cannot be reified as a type. The only types that can occur as the types of type variables are types that exist as type arguments in the source (post inference, not necessarily literally) . However, having each Type object carry a real type means that any dynamicVariable.runtimeType can cause every type to exist at runtime as a type variable binding, even if only for the Type object itself. That, by itself, will likely affect tree-shaking.

The "hack" that we use in dart:ffi requires the call sites of the type arguments to have const types. This enables replacing all call sites with an inlined body, and still have tree shaking. (If one were to write very large bodies, and/or allow propagating const type arguments to other places requiring const type arguments, forcing recursive inlining, we would probably blow code-size up too much and use an implementation strategy where we propagate a set of all types that flow into every call site in the tree-shaker.)

[eernstg]

Let me repeat an obvious question here:

@lrhn wrote:

Currently a Type object cannot be reified as a type

Perhaps you could provide an example showing how the addition of a type parameter to Type would give us this capability? As long as the veracity of this statement is unsupported, I wouldn't be terribly worried about its implications.

The only cost that actually came up during the discussions in this issue is the following:

Creating constant Type objects for the values of type literals at program startup will be about twice as expensive

It would be interesting to know whether this is typically 500 nanoseconds going to 1 microsecond, or something much bigger.

[lrhn]

In the current language, having Type<T> wouldn't allow you to get to the type T.
If we ever get open-type, fx through type patterns, then case Type<var X>: would provide a way to convert a Type object into a type variable for the same type.
I hope to get that one day, and I don't want a feature like Type<T> getting in the way.

Even without that, there is might still be a need to retain extra type information, if every type in the program an occur as a type parameter to a generic class. There is no limit to the type arguments that can occur in the value of dynamicValue.runtimeType. At least it's an instantiation of Type<T>, not the type itself, so it can only occur to the left of is, not on the right. That would be worse.

[eernstg]

In the current language, having Type wouldn't allow you to get to the type T.

With this proposal, that is still true. You need to assume another feature in order to go beyond that:

If we ever get open-type, fx through type patterns, then case Type<var X>:
would provide a way to convert a Type object into a type variable for the same type.

Oh, I'd like that, too! ;-)

But assume that you have an instance t of type Type which is a reification of any given type T. You have obtained that object by calling .runtimeType on an instance whose dynamic type is T, or you have evaluated an expression S whose value is T (e.g., it could be a type literal like int, or a type variable X whose actual value is T at the time).

If you obtained t from a term that denotes a type (which would be T, when that term was evaluated as an expression) then the program already contains a term at a location L that denotes T, and anything which can be done in the body of the case Type<final X>: could also be done at L.

If you obtained t from o.runtimeType then there is a location L in the program where o was created. Assume that t reifies C<S1, .. Sk>. In this case the program surely already contains a representation of the class C (e.g., if each object performs OO method dispatch based on a class id, or even just because we're calling o.runtimeType on an o whose dynamic type isn't guaranteed to be different from C). However, at location L it is possible to denote each of Sj, j = 1 .. k. Again, anything we could do in the body of the type pattern case Type<final X>: could again be done at L.

Here's a possible counterargument: "OK, but the body of the type pattern is new code, and nobody did the exact same things at L that they are now doing in the body of the type pattern".

We need to consider programs doing the same work (it's not hard to prove that if you edit your program to do new things, it may run more slowly). My point is that you could already do the same things if you create, say, a function literal in the same scope as L, and pass the function object along with o everywhere, and then call it when you reach the point where the case Type<final X>: would otherwise have occurred.

So there's nothing new that you can do, and hence the program without case Type<final X>: can't tree-shake out anything that the program with that type pattern can't also tree-shake.

In other words, there is no new cost for a program that does the same thing (perhaps more conveniently) if we add support for Type<final T> patterns together with Type<T> (and of course also not if we add Type<T> alone).

The only new cost I can see is still that creation of reified types during constant evaluation needs to create instances of Type<T> for each constant type T, not just Type.

[lrhn]

Assume that you can tree-shake the implementation of checking whether a type variable matches a particular type.

Say the expression e is Future<T> where T is a type variable, the implementation of that needs some extra code (or data) for every type which can occur as the value of that T, in order to implement this check.

As things currently are, a type cannot be the value of T unless that type occurs as a type argument somewhere in the program. A type argument is either a literal type, or it's a type variable, and the latter cannot introduce a type which isn't already a type argument. The set of possible type parameter values is restricted to the set of literal type arguments of the same program.

If we can write:

R callWithTypeOf<R>(Object? o, R Function<T>(T value) f) =>
  switch (o.runtimeType) {
     case Type<var T> _ => return f<T>(o as T);  // Exhaustive.
  }

R callWithType<R>(Type type, R Function<T>() f) =>
  switch (o.runtimeType) {
     case Type<var T> _ => return f<T>();  // Exhaustive.
  }

then that closure property goes out the windows. Any type which has an instance, or which occurs as a Type literal, can now also become the type of a type parameter.

And then we can't tree-shake as much of the information needed to do is Future<T>, because we can't limit which Ts might be needed.

It's not about tree-shaking entire classes. It's about tree-shaking some metadata for the class when that meta-data is not used by the program. Dart2js does this today, and would be affected on the compiled size of programs if we make that tree-shaking less efficient.

[eernstg]

The set of possible type parameter values is restricted to the set of literal type arguments of the same program.

This is not true. For example:

void f<X>(int count) {
  print(X);
  if (count > 0) f<List<X>>(count - 1);
}

void main() {
  f<int>(5);
  print('... and so on.');
}

It is true that every possible type argument in a program is of the form T where T is a denotation of a non-generic declaration that introduces a type, or it is of the form T<S1, .. Sk> where T is a generic type accepting k type arguments (including FutureOr), or it's a function type, or it's one of a short finite list of special, non-generic types, but when we consider the parameterized types T<S1, .. Sk> including the type arguments, the set of type arguments of a given program is not bounded by any finite set of types.

[lrhn]

It's true that the concrete types are not limited, but this is about metadata for classes, not types.

For the practical purpose here, we might be able to treat a type argument of List<T> as being the combination of the base type List and another type argument.

The metadata needed to use that type is only the metadata of List plus the metadata of the type argument. No matter how many times you nest List types, that only needs to retain the List class metadata once. In that sense, the current design limits the metadata needed to the declarations whose type actually occur as a type argument somewhere. This example only forces us to retain metadata for List and int, which are exactly the types which actually occur in type argument position in the program.

[eernstg]

I guess the real topic here (in the crusade against Type<T>) is whether the existence of this feature could prevent the ability to tree-shake away the run-time representation of the type arguments of a class which could have been tree-shaken away when the feature does not exist.

If a given class A<X> { int i = 1; } does not use the type argument at all then it seems like it would be a good candidate for this kind of erasure.

One question that arises immediately is whether this program should run without dynamic errors?:

void main() {
  A<int> a = A<String>() as dynamic;
}

We cannot expect to detect statically that the value of the initializing expression has type A<String> at run time (just imagine that it's produced by a non-trivial algorithm). However, if we have eliminated the run-time representation of the type argument then we cannot report a cast failure.

Is that OK, based on the reasoning that there is no soundness issue, because a A<String> behaves exactly like an A<int> in every way (other than direct type tests like this)?

If this is not OK, then I can't really see how a program that contains case Type<A<final X>>: can make a difference: We're obviously talking about two programs which are doing the same thing in some sense (because it's not reasonable to say "if I change this program to do something entirely different then it runs more slowly; hence the feature used to do that different thing should be banned"). The program that does not use the existential open can hardly avoid containing a declared type or a type test for A<T> for some T, and in that case the type argument of A cannot be eliminated in any of the two programs.

Conversely, if the program that doesn't use an existential open also doesn't contain any type annotation or type test with a type of the form A<T> then we may be able to erase the type argument of A, but then we don't need case Type<A<final X>>: at all, because the first program couldn't possibly do anything for which that is needed.

And if we're not looking at the ability/lack-of-ability to eliminate some type arguments at run time, what are we talking about?

[lrhn]

Is that OK ... ?

No.
There was never any attempt to remove the type argument from a class where the type argument is used, and here the type argument of the type and class A is used since there is an (implicit) as A<int> operation in the program. That means both that the type argument of an A instance needs to be retained, and the type argument to the A type is used in a type check (and that int and String are both used as type arguments in the program).

There is no (big) problem with case Type<A<final X>> _: because that at most retains A and whatever type arguments are potentially applied to A. The problem is with cast Type<final X>: can need to retain metadata of every type argument to Type, which is not restricted to those types which occur as type arguments in the source.

The type arguments applied to Type are supplied by the runtime system, and can include any type occurring anywhere in the program, where that type can potentially be turned into a Type object. Which includes at least all the concrete classes that are instantiated, because of Object.runtimeType.

We are talking about retaining some information (maybe metadata, possibly stub code) which is only used in particular code patterns.
Take o is Future<T>. The ability to check whether o is a Future is necessary, but after that, we need to extract the type argument of the runtime type of o at Future, and compare that to T, where T is a type variable.
The ability to do that check, using a type variable, may require metadata for both the type argument of o and the type T.
Such metadata can be omitted for classes which never occur as type arguments in the source code.
That's the level of granularity: Supporting particular code patterns which use a type variable.

[eernstg]

We are talking about retaining some information (maybe metadata,
possibly stub code) which is only used in particular code patterns.

I was trying to find a very concrete situation where there is a cost (instances of some classes need respectively do not need a run-time representation of their actual type arguments). I couldn't see that there will be an added cost for a program using existential open, compared with a program that does something which in some way could be considered to be the same thing.

Could you make that metadata more concrete? It is not obvious to me that it maps to anything that actually exists at run time.

Another thing is that I find it hard to believe that the demands on the representation of a type T based on the fact that the heap may contain an instance of T are any less than the demands on the representation of a type T based on the fact that T may occur as the actual value of a type argument. In other words, having a T in the heap is already just as expensive in terms of type related representation at run time as having an actual type argument whose value is T.

[lrhn]

I have a hard time pointing to a specific such optimization, since I only know about them secondhand. And it was years ago that I heard about it (but I assume we won't remove a functioning optimization, especially on the web).

@rakudrama Is it still true that Dart2js avoids reifying parts of the runtime support for type checks involving type parameters, for types which cannot be type arguments?

(Is it possibly true for other AoT compilers?)

[eernstg]

@rakudrama, it would be great if you could comment on one more thing, in addition to the question from @lrhn:

Consider a class (generic or non-generic) C. Consider situation (1) where it is possible that the heap may contain an instance of C, and the situation (2) where it is possible that a type of the form C (or C<S1 .. Sk> for some types Sj) can be the value of a type argument (which is not optimized away).

If situation (1) exists, would the existence of situation (2) create a need to retain any additional information at run time? Is the information required in situation (2) a subset of the information for situation (1), or a superset, or just a different set?

I'd certainly expect situation (1) to require that we retain information about the implementation of some methods that an instance of C might need to execute, and that's not required just because C is a type argument. But there might also be some information which is needed for the type argument and not for the instance.

[abitofevrything]

For those who need a solution that works now, I've just uploaded a package that provides some of the features a Type<T> would - runtime_type.

However the package is limited and doesn't really solve the issue, just abuses type generics to do type checking in the same way as <X>[] is List<Y>. But it can solve T is int :)

[eernstg]

That's cool, @abitofevrything!

Of course, here is one difference between the situation where the reified type for T has type Type<T> and the situation where package runtime_type is used: With Type<T>, we can obtain the reified type of any given object o as o.runtimeType; with package runtime_type, we'd need to equip o with a RuntimeType at creation time (or at least before we've forgotten the exact type of o), because we can't rediscover the precise value of the type arguments of o if we only have a reference to o whose static type could be a supertype of the run-time type of o.

So let's say that we've handled that issue for all types where we need this feature. The library example.dart does this by having a RuntimeType<T> as an instance variable in a class Value<T>. I guess it could have used final type = RuntimeType<T>();. The actual approach is a bit more flexible, but directly using the value of T of the enclosing Value instance would make sense, too, and clients wouldn't need to know about it:

class Value<X> {
  final XType = RuntimeType<X>();
  ... // Other members (including constructors) same as without RuntimeType.
}

Let's just assume that List<E> has such a RuntimeType<E> named EType. We could then do a lot more than Type<T>. For instance, if we have two lists xs and ys then we can test ys.EType.isSubtypeOf(xs.EType). If that's true then we know that xs.addAll(ys) is safe. It's possible to add methods to RuntimeType freely, because it's just a regular Dart class. The type system won't understand that it is safe, but that's often the case with reified types as well.

However, there's one place where RuntimeType doesn't immediately allow for the same expressive power as some other proposals in this area. In particular, we've discussed having a method that exposes type arguments of a class. Here's an example using a mock List class that just has a dummy add method, plus the method callWithTypeArgument that exposes the type variable of the class:

class List<E> {
  void add(E e) { print('Added $e!'); }
  Y callWithTypeArgument<Y>(Y Function<X>(List<E>) callback) =>
      callback<E>(this);
}

void main() {
  List<num> xs = List<int>();
  xs.callWithTypeArgument<void>(<E>(this_) {
    final newElement = 1;
    if (newElement is E) {
      this_.add(newElement); // Guaranteed to succeed.
    }
  });
}

The package 'runtime_type' does define withInstance which is somewhat similar. It would be interesting to see if withInstance (and possibly some other parts of RuntimeType such as the type parameters) could be rewritten to allow the process argument to have a reference to the enclosing object (like this_), as well as having its type argument(s) in scope.

I actually think that RuntimeType and Type<T> are so different that it makes sense to explore both of them. ;-)

[rubenferreira97]

Given the following code:

T castNum<T extends num>(num number) => number as T;

final cast = castNum(1.0); // infers num
final castToInt = castNum<int>(1.0); // infers int
final castToDouble = castNum<double>(1.0); //infers double
final castToString = castNum<String>(1.0); // compile error

Would this proposal allow something like this?

T castNum<T extends num>(num number, Type<T> type) => number as T; // `as T` or `as type`?
final cast = castNum(1.0); // compile-time error, we could give `type` a default if we really want to
final castToInt = castNum(1.0, int); // infers int
final castToDouble = castNum(1.0, double); //infers double
final castToString = castNum(1.0, String); // compile-time error

For this to work I guess this would need to be allowed:

Type<num> numType = num;
Type<num> intType = int; // Ok, int extends num
Type<num> stringType = String // compile-time error

[lrhn]

@rubenferreira97
Most likely, yes.

The

final castToInt = castNum(1.0, int); // infers int

would have no context type, a type parameter of T extends num and parameters of type num and Type<T> with arguments of type double and Type<int>. The only constraint on T is from the Type<T> :> Type<int>, so we'd infer T to be int.

You can test this today as:

class Typ<T> {}

void main() {
  T castNum<T extends num>(num number, Typ<T> type) {
     print(T);
     return number as T;
  }
  final castToInt = castNum(1.5, Typ<int>());
}

which compiles and at runtime it prints int followed by throwing because 1.5 as int fails.
(Don't use 1.0 and test in DartPad, that's also an int on the web.)

[eernstg]

@rubenferreira97 wrote:

For this to work I guess this would need to be allowed:

Type<num> numType = num;
Type<num> intType = int; // Ok, `int` extends `num`
Type<num> stringType = String; // Compile-time error

Yes, the type argument of Type will be covariant—for now, because we have no other choice, and in the future because that's the appropriate variance: Type<S> <: Type<T> iff S <: T, so we can store an object of type S in a variable of type T if and only if we can store the Type reifying S in a variable of type Type<T>.

// as Toras type?

The proposal in this issue does not involve any support for type tests or type casts on reified types (so we can't use as type or is type). That's a different feature, probably completely independent of Type<T>.

[bradcypert]

I think this may be related, but I ran into a painful issue today and replicated a Dartpad to show the issue:
https://dartpad.dev/?id=bb13e2f585a49ade106fe764e4089af8

In my case, I was expecting to add Types to a list and then check if a variable is of that type. It did not work as expected, but using runtimeType seems to. However, @eernstg and @lrhn pointed out that I may want to avoid runtime type.

[ykmnkmi]

@bradcypert try to use iterable.whereType<T>().

[ykmnkmi]

Angular DI case:

class ClassProvider<T, U extends T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass});
  
  final Type<T> type;
  
  final Type<U> useClass;
}

const ClassProvider(Client, useClass: BrowserClient);

Or if this would be possible:

class ClassProvider<T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass});
  
  final Type<T> type;
  
  final Type<U extends T> useClass;
}

[eernstg]

@bradcypert, considering https://dartpad.dev/?id=bb13e2f585a49ade106fe764e4089af8, it looks like you're maintaining a collection of Type objects ([Slime, Wolf]) and then you'd like to check whether or not any given object (w) has any of the corresponding types.

The feature proposed in this issue won't change the treatment of Type instances, so it still wouldn't be possible to do things like w is t, and doing w.runtimeType == t would still be error-prone (because w should presumably be allowed to have a type which is a subtype of the type that yielded the Type stored in t) and potentially costly (because of the invocation of runtimeType). You'd be much better served by using a proper enhancement of the Type objects using a wrapper class and keeping the type as a type (not a Type):

class Typer<X> {
  const Typer();
  Type get asType => X;
  bool isTypeOf(Object? o) => o is X;
  bool isSubtypeOf<Y>() => <X>[] is List<Y>;
  bool isSupertypeOf<Y>() => <Y>[] is List<X>;
  R callWith<R>(R Function<Z>() callback) => callback<X>();
  bool operator ==(Object other) {
    if (other is! Typer) return false;
    return other.asType == X;
  }
  bool operator <=(Typer other) => other.callWith(<Z>() => isSubtypeOf<Z>());
  bool operator >=(Typer other) => other.callWith(<Z>() => isSupertypeOf<Z>());
  bool operator <(Typer other) => other != this && this <= other;
  bool operator >(Typer other) => other != this && this >= other;
}
 
class Monster {}

class Slime extends Monster {}

class Wolf extends Monster {}

class WolfImpl extends Wolf {}

final w = WolfImpl();

void main() {
  const typers = [Typer<Slime>(), Typer<Wolf>(), Typer<WolfImpl>()];

  print(typers.any((typer) => typer.isTypeOf(w))); // 'true';.
  var xs = typers[1].callWith(<X>() => <X>[]);
  print(xs.runtimeType); // 'List<Wolf>'.
  print(typers[2] < typers[1]); // `true`, confirming `WolfImpl <: Wolf` and `WolfImpl != Wolf`.
}

If you own all the relevant code then it should be rather easy to use Typer rather than Type everywhere, and that would give you those reflection-ish methods.

[eernstg]

@ykmnkmi, the second version using final Type<U extends T> useClass; would be similar to use-site variance (similar to use-site invariance, but a bit more general) plus some variant of type patterns, so there would be a need to add several non-trivial features in order to allow that. But your first example would be fine:

class ClassProvider<T, U extends T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass});
  
  final Type<T> type; 
  final Type<U> useClass;
}

One thing to keep in mind here is that there is a variance issue: The type system will be perfectly happy with this:

var provider = ClassProvider<Object?, Object?>(int, useClass: String);

However, if we get support for use-site invariance then you could use the following:

class ClassProvider<T, U extends T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass});
  
  final Type<exactly T> type; 
  final Type<U> useClass;
}

This means that if you call the constructor with the first argument int, whose type is Type<exactly T> then type inference would have to set T == int (or the int argument is a type error), and then U extends T and Type<U> useClass will ensure that the useClass will actually be a subtype of the type.

For now (that is, assuming that we have the feature proposed in this issue "now" ;-), you'd have to use a dynamic check to enforce the invariance:

class ClassProvider<T, U extends T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass}) : assert(type == T);
  
  final Type<T> type; 
  final Type<U> useClass;
}

[ykmnkmi]

Perhaps it's irrelevant, but is there any feature proposal for omitting the second type argument here?

class ClassProvider<T, U extends T> extends Provider<T> {}

[eernstg]

Ah, but of course, I didn't think about that:

class ClassProvider<T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass});
  
  final Type<exactly T> type; 
  final Type<T> useClass;
}

So if you do not plan to write any code in ClassProvider where U is needed then there's no need to have it: Presumably it's just required that useClass is a reified type that represents a subtype of T, and being the value of a variable of type Type<T> is sufficient to ensure that.

By the way, one thing you could do would be this:

class ClassProvider<T> extends Provider<T> {
  ClassProvider(this.type, {required this.useClass}) : assert(type == T);
  
  final Type<T> type;
  final Type<T> useClass;
}

This would (when assertions are enabled) cause the construction of a ClassProvider to throw in the case where T isn't the same type as the one which is reified as type. That makes it a dynamic version of the check that we'd get from exactly.