Unwanted Object-inference induced type errors #2

[modulovalue]

This issue presents a similar issue as the one in #3156, but one which can't be addressed with statically checked variance.

Consider the following example:

void main() {
  final bar = [
    ["a"],
    ["a", "b", "c"],
  ].map(
    (final e) {
      if (e.length == 1) {
        return e.single;
      } else {
        return e;
      }
    },
  ).toList()..sort();
  print(bar);
}

The issue here is that the return type of the function passed to map is inferred to be Object. This, in my opinion, is not very helpful and can lead to accidental runtime exceptions:

Unhandled exception:
type 'List<String>' is not a subtype of type 'Comparable<dynamic>' in type cast
#0      ListMixin._compareAny (dart:collection/list.dart:360:50)
#1      Sort._insertionSort (dart:_internal/sort.dart:69:36)
#2      Sort._doSort (dart:_internal/sort.dart:58:7)
#3      Sort.sort (dart:_internal/sort.dart:33:5)
#4      ListMixin.sort (dart:collection/list.dart:356:10)
#5      main (package:humanspec/parser/sine/hele/dart/meta/foo.dart:13:15)
#6      _delayEntrypointInvocation.<anonymous closure> (dart:isolate-patch/isolate_patch.dart:297:19)
#7      _RawReceivePort._handleMessage (dart:isolate-patch/isolate_patch.dart:192:26)

Such mistakes are easy to make, and other languages have made choices that prevent such errors. Consider, for example, Swift, where returning a String and a List leads to an error at compile time.

let bar = [["a"], ["a", "b", "c"]]
  .map { e in
      if e.count == 1 {
          return e[0]
      } else {
          return e
      }
  }
  .sorted()
print(bar)

  error: cannot convert return expression of type '[String]' to return type 'String'

I've alluded to a separate analysis step analogous to implicit-dynamic, but only for Object-related-inferences (e.g. implicit-object) in #3156 which could help prevent such errors. I still think that that is worth considering and could be valuable to Dart users.

[eernstg]

You can get the same error in a simpler way:

void main() {
  ["", 1].sort();
}

The point is simply that sort with no actual argument will use Comparable.compare which will call compareTo on one element with some other element as the actual argument, and that will fail (at run time) if there are two elements such that one of them has a compareTo whose parameter type is not a supertype of the type of some other element. In the example, there is an int, and there is an object whose compareTo requires a String (that is ""), and String is not a supertype of int so the sort throws.

This is also a variance issue, but deeper. In particular, Comparable<T> has a method with signature int compareTo(T other), which means that it should have been declared as Comparable<in T> in order to be statically safe. But then all classes that implement/extend Comparable should pass an actual type argument to Comparable which is invariant or contravariant (and the latter is probably not going to be convenient).

In other words, in order to be statically type safe, comparable generic things should be invariant in the type variables that are relevant to the comparison.

This is probably not going to be practica. It is just too convenient, for a lot of purposes where it's not causing errors, for many classes to be covariant. So let's revisit the current approach briefly:

The current approach is dynamically checked, but many classes are by convention declared to be self-comparable (so an object whose run-time type is A is comparable to other instances of A, and the class has something like implements Comparable<A>). As long as we only sort lists that are homogeneous (e.g., a list that only contains instances of A), it just works.

We could also have a whole hierarchy of types that are comparable to the same common supertype S (a good example is that int and double both are Comparable<num>), and then we can sort any list that only contains instances of S or any if its subtypes.

I think the reasonable summary would be: Dart comparisons (including indirect usages like sort) are built on comparing objects of roughly the same type. Of course, it would be possible to use a strict statically typed approach (e.g., having only invariant type variables), but it's not a good fit for Dart today, so it's probably a better idea to follow the conventions mentioned above to make it safe at run time in practice, even though it isn't statically checked.

[modulovalue]

It might look like I intended this issue to be about this particular example (that is, the sort method causing a crash), but I meant it to only be an example.

What I wanted to point out is that, in cases like these, one can't rely on the type checker to report that type inference "failed", or in other words, it's not possible to encode the constraint that "Object should never be inferred from two unrelated types". This constraint is useful when, for example, type signatures are being migrated, as any reported violation helps with any such migration.

The observation that this is not an issue in Swift, (and probably most other mainstream languages, see #3156 (comment)) seems like evidence that this is, in fact, an issue. It appears to definitely go against what most people would have learned to expect.

I agree that adjusting any core libraries to prevent such issues might not be worth the churn that it could cause and I'm not suggesting this should be done. However, It looks like this is an issue that appears to be preventable in a rather simple way with an additional analysis step, as is already being done for other issues via, for example, strict-casts, strict-raw-types or strict-inference.

[eernstg]

As usual, you are raising a very interesting topic!

In this particular case I think the core of the type safety issue is that Comparable.compare accepts two arguments of type Comparable (that is, Comparable<dynamic>), and given that Comparable is optimally wrong with respect to variance, it is not possible to build on that and achieve strict static type checking.

If we get declaration site variance then we can introduce invariance even for classes like List which are not likely to be made invariant (because of the massive breakage that this would cause, but also because it would ... presumably ... be a trade-off which is not that popular).

The observation that this is not an issue in Swift

Swift uses invariant types in the general case. A language which is doing that doesn't have any dynamic type checks associated with variance (because it doesn't exist), so they don't have the problem.

(Actually, Swift collections are treated differently, but they are also copy-on-write, so that's very different; for instance, search for 'only crashes at runtime' on this page.

preventable in a rather simple way with an additional analysis step

I can't immediately see how this could be done in such a way that it would compensate for the inherently type-unsafe Comparable.compare.

[lrhn]

A "don't infer Object" (and likely not Object? either) seems like it could catch mistaken combinations of unrelated types that end up in an upper bound.

I'd normally not be too worried about that, because if you get Object as type, you'll find out soon if you try to use it for anything that isn't allowed on all objects, and if it is allowed on all objects, ... maybe it was what you wanted.

You the point a finger to a painful point in the Dart APIs, where Dart 1 APIs did not migrate safely to the Dart 2 type system (and we have some pre-null safety APIs that didn't migrate safely to the null safe type system too).

List.sort is simply not safe. If you don't pass a comparator, it will assume that all objects are Comparable to each other, and fail at runtime if they aren't. The parameter really should be required.
(It's just so convenient when sorting lists of integers or strings, or comparable objects like DateTime. And we don't have a good way to deprecated the optionality.)

Or, really, sort should be an extension method, not an instance method. Then we can have sort(Comparator<T> on List<T>, but sort([Comparator<T>]) on List<T extends Comparable<T>>.
(And we don't have a good way to deprecate an instance method, and turning it into an extension method, without hitting people with deprecation warnings that they should really be ignoring, because their code will keep working.)

[modulovalue]

(No, really, I'm not trying to highlight any issues with the sort API or statically un-checked variance. I agree that the current API is convenient and I have no issues with the trade-offs that were made.)

---

A "don't infer Object" (and likely not Object? either) seems like it could catch mistaken combinations of unrelated types that end up in an upper bound.

Exactly!

implicit-dynamic

Consider how implicit-dynamic behaves (For context, here's the issue that landed implicit-dynamic: dart-lang/sdk#25573):

If the implicit-dynamic analysis step is not enabled, the following code produces no warnings:

var someList = [];

However, if the implicit-dynamic analysis step is enabled, that code produces the following diagnostic:

// Missing type argument for list literal.
// Try adding an explicit type, or remove implicit-dynamic from your analysis options file.
//             vv
var someList = [];

implicit-object

Now, what if there was an implicit-object that makes Object-related inferences an error in a similar way how implicit-dynamic turns dynamic-related inferences into an error.

So, without implicit-object enabled, the following would be fine:

void main() {
  ["", 1];
}

However, if an implicit-object analysis step is enabled, that code would produce the following diagnostic:

void main() {
// Missing type argument for list literal.
// Try adding an explicit type, or remove implicit-object from your analysis options file.
//vvvvvvv
  ["", 1].sort();
}

I can't immediately see how this could be done in such a way that it would compensate for the inherently type-unsafe Comparable.compare.

an implicit-object analysis step would probably not compensate for all unsafe uses of Comparable.compare, but, I feel like, it could prevent a large amount by emitting diagnostics for code that could lead to unsafe uses. This would be an opportunity to double check why an Object was inferred.

Does that make sense?

[eernstg]

Cf. #2539 (comment). ;-)

[modulovalue]

Cf. #2539 (comment). ;-)

I completely agree with your observation, and I am strongly in favor of having a lint or some analysis step that implements what you have proposed in your comment.