Make LUB algorithm aware of non-null types

pkg/analyzer/lib/src/generated/type_system.dart

Index: pkg/analyzer/lib/src/generated/type_system.dart
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index 91541323a8df0568de33fadcfa1434d60a80157c..4d36ec9b39c2a8e15229c3e88b5b79d2ce5ca3fa 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -142,6 +142,23 @@ class StrongTypeSystemImpl extends TypeSystem {
   }
 
   /**
+   * Compute the least upper bound of two types.
+   */
+  @override
+  DartType getLeastUpperBound(
+      TypeProvider typeProvider, DartType type1, DartType type2) {
+    // The least upper bound of bottom and any nonnullable type T is dynamic.
+    if (type1.isBottom && isNonNullableType(type2)) {

[Leaf, 2016/08/03 23:45:07]

This depends a bit on exactly what system you are trying to implement, but my
suggestion would be that you start with something like this:

BOT is the true bottom type (uninhabited).  This can't be expressed in Dart, but
it lets us talk about some things.
T? is a nullable T.  It is essentially T or null.
T! is a non-nullable T.  It is essentially T, without null if T is nullable.

Obviously, there is some initial set of types which are either nullable or
non-nullable.  My guess is that you are implementing a system in which the only
user visible types are, in fact, that initial set.

Then in Dart:

bottom =def= BOT?
  - that is, the Dart bottom type is either BOT (i.e. nothing) or null.  i.e.,
BOT? is inhabited only by null.

then the definition of LUB here falls out.

LUB(S?, T?) = LUB(S, T)? 
LUB(S!, T!) = LUB(S, T)!
LUB(S?, T!) = LUB(S, T)?
LUB(S!, T?) = LUB(S, T)?

You don't have actual syntax for ? and !, I presume, but basically its the same
thing - you just have an enumerated list of types which are nullable and
non-nullable.  This means that you can't necessarily construct the direct LUB as
defined above.  For example, if int is your only non-nullable type, and you
don't have a way of writing int?, then LUB(bottom, int) is the least type which
is a supertype of int, but which is nullable.  If num is nullable, then the
answer should be num.  Otherwise probably Object.

Let me know if you want to talk this through offline.

[stanm, 2016/08/04 00:31:15]

Thanks for the detailed explanation.

If by 'My guess is that you are implementing a system in which the only user
visible types are, in fact, that initial set.' you mean that I don't consider
the case of additional types being added to the system at runtime, then your
guess is correct.

I think I just completely ignored the fact we're looking for a **lower** upper
bound. This is what I intent to do:

LUB(S?, T?) = LUB(S, T)?
LUB(S!, T!) = LUB(S, T)!
LUB(S?, T!) = LUB(S?, LNST(T)?) = LUB(S, LNST(T))?
LUB(S!, T?) = LUB(LNST(S)?, T?) = LUB(LNST(S), T)?

where LNST(T)? is the least nullable super type of T. If T? exists for T! then
LNST(T)? is T?. Otherwise, I need to search the set of all super types of T and
return the one that has longest inheritance path to object (borrowed logic from
computeLeastUpperBound).

Do you think that should work?

[Leaf, 2016/08/04 19:40:36]

Looks right to me.  LNST(T)? == LNST(T), I think, but doesn't matter.

+      return typeProvider.dynamicType;
+    }
+    if (type2.isBottom && isNonNullableType(type1)) {
+      return typeProvider.dynamicType;
+    }
+    return super.getLeastUpperBound(typeProvider, type1, type2);
+  }
+
+
+  /**
    * Given a generic function type `F<T0, T1, ... Tn>` and a context type C,
    * infer an instantiation of F, such that `F<S0, S1, ..., Sn>` <: C.
    *