Stronger static typing for implicit casts and generics

[jdonovan]

I am a Google engineer on the Assistant Infrastructure team, and there is an effort underway to migrate part of our infrastructure from C++ to Dart. I have been investigating Dart's type system for this purpose, and I stumbled upon some significant issues with the static type system. These issues are probably nothing new to the Dart Language team, but they are surprising to me and my team. I wrote a detailed doc (PDF: Stronger static typing in Dart) describing these issues and proposing some remedies. The primary audience for this doc was engineers within my own org, so it is somewhat pedantic with its discussion of static typing. I highly encourage you to read it, but I'll attempt to summarize its major recommendations here:

Prohibit implicit casts from a supertype to a subtype

Implicit casts from a subtype to a supertype are always safe, but casts from a supertype to a subtype require a runtime check, and so they should be made explicit using the as keyword. Failure to make the cast explicit should be a static error.

Prohibit casts between generic classes with different type arguments

Both statically and at runtime, it should be an error to cast from, for example, List<String> to List<Object>, as well as from List<Object> to List<String>. Such casts are inherently unsafe because of contravariant types among the method parameters in generic classes.

Support type bounds as arguments to generic classes

If casts between generic classes with different specific type arguments are prohibited, it would prevent certain Dart idioms from working, even after refactoring, without abandoning static type safety entirely. For example, consider the method signature for Future.wait() in Dart's standard library:

static Future<List<T>> wait<T>(Iterable<Future<T>> futures,
    {bool eagerError: false, void cleanUp(T successValue)}) {
  /* ...implementation... */
}

The futures parameter has the type Iterable<Future<T>>. If we prohibit casts from, for example, Future<int> and Future<String> to Future<Object>, a data structure of type Iterable<Object> can contain both a Future<int> and a Future<String>, but an Iterable<Future<Object>> cannot. As such, there is no way to pass futures of both types into Future.wait() with its current type signature (unless of course the iterable is an Iterable<Future<dynamic>>). This restriction breaks the many call sites of Future.wait().

As a remedy, I propose adding a feature similar to Java's wildcards, such that Future.wait() can be refactored as:

static Future<List<T>> wait<T>(Iterable<Future<? extends T>> futures,
    {bool eagerError: false, void cleanUp(T successValue)}) {
  /* ...implementation... */
}

At call sites, lists of the form [Future.value(Foo()), Future.value(Bar())] have deduced type List<Future<? extends Object>>, and passing such a list into this new Future.wait() causes T to be inferred correctly as Object.

Unlike Java's wildcards, I propose that it is only valid to use wildcards as type arguments for generic class types, not as type arguments for generic functions or constructors; types parametrized by a wildcard are fully abstract. The reason is that Dart's runtime system requires that variables have specific runtime types, and wildcards are not themselves types. For example, consider this generic function:

class Rodent {}
class Mouse extends Rodent {}

class Pair<T> {
  Pair(this.first, this.second);
  T first;
  T second;
}

void swap<T>(Pair<T> pair) {
  T temp = pair.first;
  pair.first = pair.second;
  pair.second = temp;
}

The swap function is clearly sound under the assumption that T is a specific type. However, if T were allowed to be a wildcard, it is unsound. For example, if pair is Pair<? extends Rodent>, the runtime type might be Pair<Mouse>. If we assume within the function that T is Rodent, that allows temp to be properly initialized, but then later, the field pair.second, which might be of type Mouse, cannot soundly accept an assignment from an arbitrary Rodent.

The remainder of my attached document lays out some related features for static type inference that would be very helpful to minimize the efforts to refactor existing code to comply with my recommended prohibitions. It also presents an algorithm for determining the types of methods within a generic class, given its specific and/or bounded type arguments.

I thank you for considering these changes to the Dart language. Please let me know if you have any questions for me.

[leafpetersen]

Thanks for the writeup! Some comments:

Prohibit implicit casts from a supertype to a subtype

The upcoming Null Safety release will include this restriction (except when the supertype is dynamic). This will land as an opt-in breaking language change.

Prohibit casts between generic classes with different type arguments

We hope to ship definition site variance in 2020 (most of the implementation was already completed by my fall intern). This allows you to opt your own classes into sound invariance as you describe, but does not address the fact that legacy classes like List are unsoundly covariance.

We have discussed shipping "use site invariance" to provide a way to soundly interact with legacy covariance classes but have not committed to shipping this. Combined with type aliases, this would give you most of what you want here, I think.

Support type bounds as arguments to generic classes

There is ongoing discussion about whether to support this in some form.

cc @mit-mit @eernstg @lrhn @munificent

[eernstg]

First: Yes, we'd like to give developers better support for static type safety! ;-)

Just a drive-by comment:

it is only valid to use wildcards as type arguments for generic class types, not as type arguments for generic functions or constructors

This rule also exists for the designs of variance that we've considered, and it is actually an error even in Java to use a wildcard as a type argument in an invocation of a constructor:

public class N000<X> {
  public static void main(String[] args) {
    Object o = new N000<? extends Object>(); // 'error: unexpected type'
  }
}

In general, the dynamic type of an instance o of a generic class C with Dart use-site variance would always be of the form C<inout T1, ... inout Tk>, because this is the most specific type T such that o has that type (it is a proper subtype of C<T1,..Tk>). The ability to specify (via use-site variance) that there is some flexibility in the allowed values of the type arguments is simply not relevant for an object, because each object will have been created with a specific choice of type arguments, here T1 .. Tk, and they are explicit and invariant in the dynamic type.

[ayporos]

I'd like to ask if this proposal mitigate the following thing and if not should I create a separate issue?

Let's take a look at the following code:

class A {
  A(this.name);
   String name;
}

class B extends A {
  B(String name): super(name); 
}

void main() {
  var list = generate();
  print(list.runtimeType); // List<B>
}

List<A> generate() { // method returns List<A>
  var list = [B("B 1"), B("B 2")]; // type inference kicks in -> list is List<B>
  list.add(B("B 3"));
  return list; 
  }

In this made up example you can see that actual type would be List<B>. Trying to add A object to this list will lead to TypeError:.. As a proposals can it be that A. compiler will take care of creating "correct" type of var list = [B("B 1"), B("B 2")]; (List in this example) OR B. at least warning on about type mismatch?

As a real life example one can take a look at the following flutter code:

List<Widget> createFrom(List<MyDataItem> items) {
      items
      .map((item) => Expanded(...))
      .toList()
} 

Without changing map to map<Widget> one will not be able to add to this list later on anything except Expanded widget or its subtypes and it's actually hard to find out why (worse if code is not available to you)

Implicit casts from a subtype to a supertype are always safe

Well, that might depend on what exactly is meant by safe. Because of the way Dart's implicit interfaces (meaning the implements keyword) work, up-casting isn't always safe. For example, a function or static method that relies on a private field that the implementing sub-class doesn't have results in a runtime error. Or if the implementing sub-class by chance does have the required private field, but uses it for a completely other purpose, then it is also not safe. That has been the single biggest footgun of Dart so far.

[Levi-Lesches]

@ayporos, I think the way Dart handles it now is better, even if it's unintuitive. It reads through your code line by line, and at each point its decisions make sense. I think it would be worse if changing a line elsewhere (your generate signature, for example) would suddenly change the type of a local variable.

In general, there are perfectly valid reasons to have a list of a subtype and not allow the supertype. This is a bit of a long example, but I hope it demonstrates the point:

import "dart:math" as math;

abstract class Shape {
  double get area;
}

class Square extends Shape { 
  double sideLength;
  Square(this.sideLength);

  @override
  double get area => sideLength * sideLength;

  /// Only applies to squares.
  double get diagonalLength => sideLength * math.pow(2, 1/2);
}

class Circle extends Shape {
  double radius;
  Circle(this.radius);

  @override
  double get area => math.pi * math.pow(radius, 2);

  /// Only applies to circles.
  double get diameter => 2 * radius;
}

List<Shape> getSquares() {
  var result = [Square(1), Square(2)];  // inferred as List<Square>
  for (final Square square in result) {  
    print(square.diagonalLength);  // can't do this with a Circle!
  }
  // This is the error you're talking about. 
  //
  // If Dart looked at this and then typed result as List<Shape>, the for 
  // loop above wouldn't work. So it makes this the error instead of going back.
  result.add(Circle(3));
  return result;
}

void main() {
  List<Shape> shapes = getSquares();
  for (final Shape shape in shapes) {
    print(shape.area);  // this is okay
  }
}

[ayporos]

@Levi-Lesches I think there might be misunderstanding. But allow me to start from the beginning.

I think the way Dart handles it now is better, even if it's unintuitive. I'm not using dart anymore. Does this sentence mean there were some changes after my comment?

Now to your example. Maybe I didn't make it clear but my problem is not that type inference of a line var list = [B("B 1"), B("B 2")]; made list to be List<B>. My problem is that method should return List<A> and not List<B>.

Using your example I don't care what is going on inside getSquares() but I'm expecting the following code to be valid:

List<Shape> doWhatever() {
  var shapes = getSquares(); // notice that I'm expecting shapes here
  shapes .add(Circle(3)); // this one should work
  return shapes;
}

Point is that signature (API) is saying that by calling getSquares() I will receive List<Shape> not List<Square>. Otherwise I'll be not able to add any other Shape to the received list which is actually the case. Basically I'm expecting this one to work:

List<Shape> getSquares()
...
List<Shape> getCircles()
...
List<Shape> getTriangles()
...
List<Shape> combine() {
     var list = getSquares()+ ggetCircles() + getTriangles();
}

[Levi-Lesches]

Right, so this is a common difficulty across I believe all OOP languages, not just Dart. There's a difference between an object's reference type (or static type), and its object type (or runtime type).

The static type is the one you provide to Dart. List<Shape> getSquares means a static type of List<Shape>, num value = 3.0 means a static type of num. The runtime type is the actual type of the object. In this case, getSquares actually returns a List<Square> and value would have a type of double. The runtime type is allowed to be a subtype of the static type, which is why we can assign a double to a num and a Square to a Shape.

In general, as long as the above condition is true, its always safe to use methods that belong to the static type, but not always those that belong to the object type. For example:

void main() {
  Shape myShape = getSquare();  // static: Shape, runtime: Square
  print(shape.area);  // safe
  print(shape.diagonalLength);  // unsafe, even though it really is a Square. Dart can't tell 
}

With generics, you have a new problem: this compile-time and runtime relationship is not always safe. The shapes example fits, but a much simpler one would be:

void main() {
  List<num> numbers = <int>[1, 2, 3];  // statically List<num>
  print(numbers.runtimeType);  // runtime: List<int>
  numbers.add(4);  // okay, since we're adding an int
  numbers.add(5.5);  // error, since this is a double
}

A List<int> will only accept ints, even though it may have been cast elsewhere to a List<num>. The solution to this issue is called variance, specifically declaration-site variance (so the modification will be made in the definition of List). Here's a detailed write-up on how variance will solve this problem by the Dart intern who started the implementation. The issue for it is #524. Hope that helps

[ayporos]

@Levi-Lesches sorry I have no time to read you answer in full but

Right, so this is a common difficulty across I believe all OOP languages, not just Dart.

is not true. For example it will work in

• Swift (language with a type inference)
• Java (for me it's as OOP as a language can be) I'm not sure about Kotlin (another language with a type inference) but I guess it would work.

EDIT: now I think I'm having a Déjà vu, most likely I've created a separate thread somewhere here and got an answer (don't remember which one) so if you're interesting you can try to find it.

[leafpetersen]

@Levi-Lesches sorry I have no time to read you answer in full but

Right, so this is a common difficulty across I believe all OOP languages, not just Dart.

Dart is somewhat unusual in having covariant (runtime checked) generics. Java has them for arrays only, and Eiffel had them, but most modern object oriented languages (Kotlin, Scala, Java generics (except arrays), C#, etc) use statically sound generics. See here for more exposition.

[ayporos]

What I was trying to say is that in my opinion Dart is not doing enough in preventing the worst error possible, the runtime one. It would be OK to have a compile time error, but unfortunately it's not the case. Even a warning would help a lot too. And what makes things worse in my opinion is that there is a way to "fix" shapes code by eliminating type inference:

abstract class Shape {
  double get area;
}

class Square extends Shape { 
  double sideLength;
  Square(this.sideLength);

  @override
  double get area => 42;
}

class Circle extends Shape {
  double radius;
  Circle(this.radius);

  @override
  double get area => 666;

}

List<Shape> getSquares() {
  List<Shape> result = [Square(1), Square(2)];
  return result;
}

List<Shape> getCircles() {
  List<Shape> result = [Circle(1), Circle(2)];
  return result;
}

List<Shape> combine() {
  var result = getSquares() + getCircles();
  return result;
}

void main() {
  List<Shape> shapes = combine();
  shapes.add(Circle(3));
  for (final Shape shape in shapes) {
    print(shape.area);
  }
}

Try to replace for example List<Shape> result = [Square(1), Square(2)]; with a var result = [Square(1), Square(2)];; and boom, out of nowhere you'll have a runtime error.

[Levi-Lesches]

Right, so variance (#524) sounds like what you're looking for. Dart will still infer the list as List<Square> or List<Circle>, but will then turn around and complain that it cannot return a List<Square> in a function that returns a List<Shape> (if I understand the concept correctly). That error will tell you to explicitly type the list as a List<Shape>, like you pointed out.