Analyzer assigns incorrect exact type to set literals

[stereotype441]

According to https://github.com/dart-lang/language/blob/master/accepted/future-releases/set-literals/feature-specification.md, under the heading "Exact Types of Literals":

Currently, the Dart 2 type inference infers an "exact type" for map literals, either Map<K, V> for const literals or LinkedHashMap<K, V> for non-constant literals. The inferred exact type makes it a compile-time error to require a down-cast, since that down-cast is known to fail at runtime. For set literals with element type T, the static type is always Set<T>, but static analysis will reject an assignment of a non-constant set literal to a type that is not a super-type of LinkedHashSet<T> (an implicit down-cast below the type LinkedHashSet<T>), and of a constant set literal to a type that is not a super-type of Set<T> (that is, any implicit down-cast).

I believe this implies the following behaviors:

import 'dart:collection';
abstract class C<T> implements LinkedHashSet<T> {}

LinkedHashSet<Null> s1 = {null}; // ok; `{null}` is guaranteed to be a LinkedHashSet
Set<Null> s2 = {null}; // ok
Object s3 = {null}; // ok
C<Null> s4 = {null}; // compile-time error; LinkedHashMap is not a subtype of C
const LinkedHashSet<Null> s5 = {null}; // compile-time error; `{null}` is only guaranteed to be a Set
const Set<Null> s6 = {null}; // ok
const Object s7 = {null}; // ok
const C<Null> s8 = {null}; // compile-time error; Set is not a subtype of C

However if I feed the above code into the analyzer (passing in --enable-experiment set-literals on the command line), it rejects the assignment to s1, saying The set literal type 'Set<Null>' isn't of expected type 'LinkedHashSet<Null>'. The set's type can be changed with an explicit generic type argument or by changing the element types.

[stereotype441]

FYI @bwilkerson. I've marked it as P1 because it concerns a new feature, but I think it would be ok to wait until the language team decides whether to land dart-lang/language#129 before working on this.

[stereotype441]

@lrhn as of c565d4e, the spec has been changed to avoid specific mention of LinkedHashSet. Does that mean that the notion of the "exact type" of a set literal will be changing as well? What's the status of dart-lang/language#129?

[stereotype441]

@lrhn ping

[lrhn]

I'm not sure what the status of "exact types" is in general (re. #33307).

The run-time type of a non-const map literal is a LinkedHashMap. I'd prefer if the static type is just a Map. You should never have a variable typed as LinkedHashMap<..> anyway, so inferring that is not doing anyone any benefit.
That's obviously not what we are doing, we just use LinkedHashMap as the static type, and mark it exact.

We should do the same thing for Set as we do for Map. There is no reason for those two to be different. Removing the reference to LinkedHashSet from the set-or-map decission rules does not change anything in that regard. The run-time type of a non-const set literal is still LinkedHashSet. The only difference is that the parser doesn't need to know what a LinkedHashSet is in order to parse the program.

Would it be possible for "exact types" to be handled something like:

• An expression has a static type.
• An expression may also have a statically known "exact run-time type".
• A cast of an expression with an exact run-time type to a type that is not a super-type of that exact run-time type, is a compile-time error.

The static type of a set literal with element type T is then always Set<T>. The exact run-time type of a non-const set literal with element type T is LinkedHashSet<T>. This has no effect on inference, it only affects down-cast for that particular expression (or can exact types be propagated?). The exact run-time type of a const se literal with element type T is Set<T>.
(And ditto for maps. For all other expression that has an exact run-time type, it's the same as the static type).

If I can't get this change, then just use LinkedHashSet for non-const set literals, that is what the actual run-time type will be, and it is consistent with maps.

[leafpetersen]

That's obviously not what we are doing, we just use LinkedHashMap as the static type, and mark it exact.

I don't understand why you say this (you said something similar in the proposal document). Every implementation that I've tested uses "Map" as the static type of literals. This I think works out fine except that you therefore can't write LinkedHashMap x = {} because you get an exact type error. You can write LinkedHashMap x = {} as LinkedHashMap, and the runtime cast will succeed.

I'm fine with this, and it sounds like you're fine with it as well? If so, I'd suggest we just make that the specified behavior. Otherwise, I don't see any way of getting around making the spec talk about Linked HashMap. (Implicitly, I think the spec has to talk about LinkedHashMap in order to specify the runtime semantics, even if it chooses to refer to it indirectly, but that's another issue).

[stereotype441]

@leafpetersen So if I'm understanding you correctly, what you're proposing we implement is:

• The static type of a map literal is Map<...>
• The exact type of a map literal is Map<...>
• The static type of a set literal is Set<...>
• The exact type of a set literal is Set<...>

I would be fine with this; in fact I really like it because AIUI it's what the analyzer currently does! The main reason I've been pushing on this thread is because the other proposals we've entertained have the negative consequence that they would require information about the dart:collection library to be plumbed through the bowels of the analyzer, so that the LinkedHash... types will be available for analysis. That's not impossible to do (the analyzer already does similar things for dart:core and dart:async) but it would be a real timesaver for us if we didn't have to do so.

[leafpetersen]

Yes, that is my proposal.

[lrhn]

I'm fine with just using Set/Map as exact type too.

It's slightly icky that LinkedHashMap x = {}; is rejected even though we know it will succeed at run-time. That's the compiler being less smart than necessary. On the other hand, I'd have preferred if LinkedHashMap was not a seprate type, just a way to construct Set objects, so it's no big loss.
Using LinkedHashMap as static type is bad, and splitting the exact type from the static type is probably unnecessarily complicated.

I keep assuming that we changed that because I remember some mail thread about it where there was code written like LinkedHashMap<...> ... = {};. I found it again, and while I suggested to use LinkedHashMap as exact type, there never actually was a decission, and so nothing was changed. (It was my own test code that hit the problem, so no users were harmed in the process).
I'll just have to un-remember that.

The specification is not trying to avoid mentioning LinkedHashMap completely, since it is indeed the object that will be created. I just avoided that the front-end needs to be able to understand and recognize the LinkedHashMap type in order to parse the program. So far, it only requires types from dart:core, but LinkedHashMap is in dart:collection. It seems the analyzer has a similar concern.
Being a subtype of Iterable<Object> is also easier to check than being a supertype of LinkedHashSet<Null>, you just have to search the superinterfaces for Iterable<anything>.

[eernstg]

I suspect that we don't actually need exact types. What we do need is (1) the regular notion of an OO type where the effect of knowing that an expression e has type T is that features defined for T are available on the result of evaluating that expression. For that, we only need an upper bound.

In addition to that we can have (2) a notion of "guaranteed failure" of a downcast. When such a guaranteed failure has been established it makes sense to flag the downcast; this could be an error or it could be a warning (there is no threat to soundness, it's only about a dynamic failure which is guaranteed rather than potential).

So maybe the right concept would be some kind of predicate: For any given expression e, there's not only a static type T but also a predicate P, and if P(S) is true then it is guaranteed that a downcast to S will fail at run time.

This would eliminate the property that we've otherwise struggled with: If an expression (especially a special one like a list/set/map literal) has a type which may be used as the exact type, but we don't really want that specific (secret, platform dependent) type to appear in error messages, then it's tempting to give that expression another "exact type" which flies in the face of that concept; e.g., it just isn't true that the exact type of a map literal is Map<T1, T2> for any T1 and T2, but we could still use Map in a guaranteed-cast-failure predicate: For any type S which is not Map<T1, T2>, if S <: Map<T1, T2> then the associated downcast will fail (because non-core developers cannot express any type S for which that will be untrue).

Error messages don't actually have to tell anything other than the static type of an expression and the result from the predicate, it does make sense to say that MySpecialMap m = {}; will fail without mentioning any exact types, and (I think) that will make sense for developers without mentioning any exact types at all.

[leafpetersen]

Ok, the static type of Set and Map literals will be resolved as Set<E> and Map<K, V> for appropriate E, K, V, and that will be treated as the exact type for the purposes of the exactness check. In other words, the behavior described in this comment. I believe that is what is implemented, so this can probably be closed.

If at a later point we feel that not being able to downcast to LinkedHashXXX is an issue, we will simply remove the exactness check for set and map literals (since they are, in a certain sense, factory constructors).

[stereotype441]

Closing in accordance with Leaf's comment; under the new decision, the behavior of the analyzer is now considered correct.