Flow analysis - keep non-nullability on join

[scheglov]

Here ancestor has initially type Element?, so cannot be promoted to either ClassElement or ExtensionElement. But it cannot be null if any of them is true.

    var ancestor = enclosingElement;
    if (ancestor is ClassElement || ancestor is ExtensionElement) {
      if (ancestor.hasDoNotStore) {
        return true;
      }
    }

[leafpetersen]

@stereotype441 Thoughts on this? I think one possible way to enable this would be to add "intermediate" types to the promotion stack when promoting. That is, when promoting from T? to S, if S is definitely non-nullable, push both T and S on the stack instead of just S. That would then make T a demotion candidate (it's already a type of interest).

I feel like this sort of thing came up in a few other places as well, where a promotion moves through several types of interest in one step, resulting an inability to demote to one of the interim types.

[stereotype441]

@stereotype441 Thoughts on this? I think one possible way to enable this would be to add "intermediate" types to the promotion stack when promoting. That is, when promoting from T? to S, if S is definitely non-nullable, push both T and S on the stack instead of just S. That would then make T a demotion candidate (it's already a type of interest).

Yeah, that would certainly do the trick.

There's another way to do it too: instead of speculatively pushing multiple types onto the stack at the time of promotion, we could recognize the situation in join: if the types being popped off the two promotion stacks are both non-nullable, but the type that remains is nullable, then we push a non-nullable version of that type onto the stack. So in Konstantin's example, at the time of joining Element? -> ClassElement with Element? -> ExtensionElement, we would recognize that the types ClassElement and ExtensionElement are both non-nullable, but the type Element? is nullable, so we would produce Element? -> Element.

My intuition is that doing the logic in join is better because we have more information at that time. But I'm having trouble thinking of a concrete case where it would really matter.

[stereotype441]

Looking at this a bit with @kallentu today, we ran across a bit of a thorny question that we should probably think hard about before we dive too deeply into implementing this feature. I'm writing it down here so that we don't forget about it.

The issue is: how do we think of the "declared" type in the case of field promotion where there might be multiple field declarations with different types?

Let's first consider a simple case that doesn't involve field promotion:

void test1(bool b, num? n) {
  if (b) {
    if (n is! int) return;
    // (1)
  } else {
    if (n is! double) return;
    // (2)
  }
  // (3)
  n; // What is the static type of `n`?
}

At (1), n has been promoted to int. At (2), n has been promoted to double. When we join the two control flow paths at (3), what do we want the promoted type of n to be? Obviously it can't be int or double; that would be unsound. Today we just discard both demotions and n reverts back to its declared type of num?. The proposed improvement here is that we would consider num as a possible promoted type, since it's the non-null counterpart to the declared type num?. In my proposed algorithm from https://github.com/dart-lang/language/issues/1377#issuecomment-760223317, the way this would work is that at the time of the join, we look up the declared type (num?), find its non-nullable equivalent (num), and then check whether both int and double are subtypes of it. They are (int <: num and double <: num), therefore we promote n to num.

If instead we think of Leaf's proposed algorithm from https://github.com/dart-lang/language/issues/1377#issuecomment-752805359, we think of it this way: at (1), n has been promoted first to num and then to int. At (2), n has been promoted first to num and then to double. So when we join the promotion chains num -> int and num -> double, we keep the common prefix num.

Ok, now consider this more complex example involving field promotion:

class A {
  final Object? _f;

  A(this._f);
}

class B implements A {
  final num? _f;

  B(this._f);
}

class C implements A {
  final num? _f;

  C(this._f);
}

void test2(A x) {
  if (x is B) {
    if (x._f is! int) return;
    // (4)
  } else {
    if (x._f is! double) return;
    if (x is! C) return;
    // (5)
  }
  // (6)
  x._f; // What is the type of `x._f`?
}

At (4), x has been promoted to B and x._f has been promoted to int. At (5), x has been promoted to C and x._f has been promoted to double. What should happen to x._f when we do the join at (6)?

If we make the analogy to the simpler example, and we assume my proposed algorithm from https://github.com/dart-lang/language/issues/1377#issuecomment-760223317, it seems like the first question we need to ask is: what's the declared type of x._f? Well, that depends. At (4), x has type B, so we might claim that x._f refers to B._f, which has declared type num?. And at (5), x has type C, so we might claim that x._f refers to C._f, which also has declared type num?. But at (6), the promotions of x go away, so x has type A, and A._f has declared type Object?.

If we decide that the declared type of x._f is num?, then (still assuming my proposed algorithm), x._f should be promoted to num. If we decide that the declared type of x._f is Object?, then x._f should be promoted to Object.

Alternatively, if we go with Leaf's proposed algorithm from https://github.com/dart-lang/language/issues/1377#issuecomment-752805359, then I guess at (4), the promotion chain for x._f is num -> int (since at the time x._f was promoted to int, x had type B, and B._f has declared type num?). But at (5), the promotion chain for x._f is Object -> double (since at the time x._f was promoted to double, x had type A, and A._f has declared type Object?). The promotion chains num -> int and Object -> double have no common prefix, so at the join point, the promotion is dropped entirely and x._f reverts back to having type Object?.

So depending on the algorithm we pick and how we think about it, at (6), x._f could have type Object?, Object, or num. 🤔

From the point of view of what's useful to the customer, I suppose it doesn't matter much; this is a really contrived example, and most reasonable cases of field promotion don't have these complexities. But still, I want to take some more time to think about this, and make sure we have a nice coherent story for whatever choice we make, to reduce the risk of painting ourselves into a corner.

[lrhn]

If we treat nullability specially, then:

UP(A, B) :=

• let R = UP'(A, B) -- the one we use today, or better
• if A <: Object and B <: Object and not R <: Object,
  • then let R = NON_NULL(R)
• result is R

We know that R is a type of interest, and therefore so is NON_NULL(R), even if we didn't put it into the promotion chain explicitly.

Alternatively we treat nullability differently in the promotion chain. An entry of Foo counts as both Foo and Foo? when doing intersection. If I've chain of an intersection contains Foo and the other contains Foo?, then the result contains Foo?, and if you promote a variable from nullable or potentially nullable to non-nullable, it promotes the entire chain at that point, converting every entry to NON_NULL of itself. (Which is probably the same as keeping nullability as a bit on the side of the stack.)

Does that answer the question for the field promotion? Don't bother with recognizing the declared type, it's just another type in the promotion chain. (I don't know how field promotion works, hadn't considered how promoting the receiver could influence the variable. I guess that if you promote x to B then the declared type of B._f becomes a type of interest for x._f, and you can promote x._f to that type (or NON_NULL of that type of already non-nullable) if that would be a promotion. What means that the is B+is int would give a promotion chain of int<num<Object, and the is double+is C would just have double<Object, because the is C doesn't promote further than the is double already did. So demote to Object.) Another thing to consider when merging promotion chains is whether a type in one that is a type of interest in the other, and is implied by a later element of the other chain, can be included. Intersecting int<num<Object and double<Object could soundly end up with num. The problem is diamond properties, Never<int<Object and Never<double<Object would be able to do that on both directions, and then it's not a chain. The plain intersection doesn't have that kind of problems, but it does throw away information.