dart-lang / dart-lang/language

Testing whether two `Type` instances reify the same type is expensive

Open
#92 0 comments 0 reactions 0 assignees View on GitHub
request
Dominant language
TeX
Stars
2.9k
Forks
239
Avg merge
2d 18h
Merged PRs (30d)
14

Description

Let us say that an instance of type `Type` _constantly reifies a type_ if and only if it was initially obtained as the result of evaluating a constant expression denoting a type declaration, that is, a type alias (`typedef ...`), a class declaration (`class C ... {}` or `class C ... = ...`), or a mixin declaration (`mixin ...`).

Let us say that an instance of type `Type` _reifies a type_ if it constantly reifies a type, or if it was initially obtained as the result of evaluating a type variable as an expression.

Note that when an instance of type `Type` reifies a type, it was initially obtained as the result of a primitive feature of the language (that is, if we delete that feature from Dart then we cannot reimplement it using Dart code), namely the ability to produce an instance that represents a given denotable type.

As mentioned in https://github.com/dart-lang/sdk/issues/35098#issuecomment-437034065, the language specification does not specify how to create the instances of type `Type` that reify a type.

In particular, it is not specified that such instances are canonicalized, and hence it is not safe to assume that two `Type` instances `t1` and `t2` denote the same type if and only if `identical(t1, t2)`, not even in the case where developers maintain as a coding invariant that `t1` and `t2` are guaranteed to constantly reify a type. It's of course safe to trust the result `true`, but with `false` we may still have a situation where `t1` and `t2` represent the same type.

Another potential source of duplicate representations is type arguments. For instance, consider the following code:

```dart
Type typeOf() => X;

class C {
D dOf() => D();
}

class D {
Type get typeArgument => Y;
}

main() {
final t1 = typeOf>();
final t2 = C>().dOf().typeArgument;
identical(t1, t2);
}
```

It is not currently specified that two distinct invocations of `typeOf()` (be it the same syntactic expression evaluated twice, or two distinct syntactic expressions in the same binding environment) for any given `T` must return a canonicalized result. Similarly, when an instance of `D>` is created in the body of `dOf` as a result of evaluating `D()`, there is no guarantee that the reification of the type argument (here: `List`, and in the body of `D` it is accessed as `Y`) is identical to the reification of the type argument of the receiver (`List` respectively `X` in the body of `C`) for the invocation of `dOf`. Indeed, there is no guarantee that an instance of `Type` that reifies `C>` is an object that has a field whose value is a reification of `List` at all.

In summary, there are several ways in which an implementation is allowed to omit (the extra work of) canonicalizing instances that reify types, and consequently there are many reasons why `identical(t1, t2)` could return false, even though "t1 and t2 are the same type".

In contrast, for any two instances `t1` and `t2` reifying types, we have specified that `t1 == t2` must return true if and only if `t1` and `t2` represent the same type (section 'Dynamic Type System' in dartLangSpec.tex, [here](https://github.com/dart-lang/sdk/blob/47cada07ac7963f2e9abd311ae1a547ef8368b40/docs/language/dartLangSpec.tex#L11230)). But this test is considerably more expensive than `identical(t1, t2)`, at least currently.

It would be helpful if we could provide guarantees that will allow developers to use the cheaper `identical` test, in some well-defined set of situations.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.