Make LUB/GLB more useful for generic types

[jmesserly]

consider:

void main() {
  var l = true ? [] : <int>[];
  l.add(42);
  print(l);
}

This l is inferred as EfficientLength

(see dart-archive/dev_compiler#288)

Edit: and also fix GUB, as @leafpetersen notes in this comment.

[jmesserly]

CC @natebosch, who just hit this again (in #26079). @munificent @leafpetersen were we thinking of looking at this in the short term?

[leafpetersen]

It's on the list of things that I really want to fix. A full fix probably takes more time than it's worth in the immediate short term though. If I can find the time in the next few weeks I'll at least try to handle the obvious cases.

[jmesserly]

Ah, something like handling C<T0,...> and C<S0,...> -> C< LUB(T0, S0),... >? That would handle a lot of the common List cases most likely. (edit: and don't need to worry about searching superclass/mixins/interfaces)

[leafpetersen]

Yes, I think a simple heuristic that would be quick to implement and at least be better would be something like:

if (subtype(A, B)) return B;
if (subtype(B, A)) return A;
if (A = C<T0, ...>, B = C<S0, ...> ) return C<LUB(T0, S0), ...>;
return specLub(A, B);

As soon as you start having to search up the inheritance tree, you start having to make decisions about what you mean by least, and you also have the implementation burden of tracking what the generic type arguments for the superclass are. It's doable, but needs some thought and careful work.

[leafpetersen]

The above heuristic plus some fixes for type parameters landed in:

https://codereview.chromium.org/1843453002

This should catch most of the ugly cases we've been seeing.

[eernstg]

Here's a case where the strong mode LUB of List<C> and Set<C> seems to be Object:

class C {}

main() {
  Iterable<C> x;
  x = new Set<C>() ?? <C>[];
  x = true ? new Set<C>() : <C>[];
  print(x);
}

Both assignments to x produce an Unsound implicit cast from Object to Iterable<C> hint.

[leafpetersen]

Yes, I haven't actually implemented a real lub algorithm yet - just added some heuristics to make some of the more common cases behave sanely (specifically the case where one is a supertype of the other, and the case where both are different instances of the same generic type). I'd love to tackle this, but it's somewhat lower priority right now.

I'd also really like to get away from relying on LUB for typing operators like '??' and '? :' where possible. We will give users a much better experience if we check that the sub-expressions are typeable appropriately for the context, rather than first computing a LUB and then doing a subtype check. The only time we should need to compute the LUB is when we are doing inference.

[eernstg]

A representation of the LUB as a list of operands might blow up (there will be pathological cases where that list gets impractically long), but otherwise it could be used to enable exactly that: When asked whether [T1, T2, .. Tk] is a subtype of T, just check that every one of Ti <: T holds. If it fails somewhere we can even tell the user about that concrete failure and never mention the intermediate LUB. We may never need to worry whether anything is a subtype of such a "list based LUB" type, but presumably that would just be "check T <: Ti for all i, say yes if one of them succeeds".

[johnniwinther]

See also language/least_upper_bound_test and language/least_upper_bound_expansive_test for some nasty infinite and infinitely expanding structures that occur if you apply a simple recursive algorithm.

Also see tests/compiler/dart2js/least_upper_bound_test.dart functions 'testInterface1' and 'testInterface2' for cases were a single type (non-intersection) can never be the ideal answer.

[leafpetersen]

cc @nex3 who just ran into the same Set vs List oddness. Strong mode currently just falls back onto spec mode LUB in that case, but I'm not sure why the LUB ends up as Object instead of EfficientLength or Iterable. I've confirmed that the same thing happens in spec mode though.

[leafpetersen]

Closing, tracked at #27525