How do we handle flow analysis of dead code?

[eernstg]

Thanks to @sgrekhov for bringing up this topic! Consider the following situation:

void f(Never n) {
  final _ = n ? 1 : 2;
  print('Unreachable!');
}

The analyzer accepts this code without any diagnostic messages (Dart SDK 3.8.0-149.0.dev and Flutter SDK 3.30.0-1.0.pre.470).

However, the evaluation of n in the condition of the conditional expression is specified (in the 'variable or getter' case) to make subsequent code unreachable.

We do get 'dead code' warnings in the following case:

void g(Never n) {
  final _ = (throw 0) ? 1 : 2; // Warning on `1` and on `2`.
  print('Unreachable!'); // Warning.
}

The analysis is somewhat tainted by the fact that the entire body of f is dead code (because an invocation could never proceed unless n were bound to an object whose run-time type is Never, and that will never happen, pun intended). This means that any assumption about the properties of the code is sound (we will never need to deliver on those promises).

So how do we manage this freedom to assume arbitrary things? We could determine that a certain amount of code is dead, and then omit any further analysis (because it doesn't make sense anyway, at least not always).

We could also proceed to analyze the dead code relying on conclusions that do not depend on the flow analysis (so we won't assume that any variables have been promoted before the dead code starts running, but we do recognize that code after throw 0 is unreachable, no matter what the control flow has been so far).

The remaining funny quirk is that the evaluation of n in f doesn't count as an event that makes subsequent code unreachable, perhaps because the flow analysis assumes that "we can always evaluate a formal parameter, and it doesn't throw!".

This raises a couple of questions:

• Do we simply have a bug in the treatment of formal parameters of a type T <: Never? Or is it intentional that we treat them as "safely readable, even if the type is Never"?
• Can we perform a static analysis on dead code that disregards all information from flow analysis? Or can we include some flow analysis information without producing absurd results? Should we?

@stereotype441, WDYT?

[bwilkerson]

Do we simply have a bug in the treatment of formal parameters of a type T <: Never?

I'm not sure I can speak to that, but even if the treatment of the parameter is intentional I do think it makes sense to mark the whole body of the function as dead code and explain that the type of the formal parameter n is the reason why the body can never be reached.

Can we perform a static analysis on dead code that disregards all information from flow analysis?

The general principle that we've followed before is to perform as much analysis as possible in the face of invalid code (of which dead code is just a subtype) while minimizing the number of spurious diagnostics.

We do this in order to make it as easy as possible for users to fix problems in their code in the order in which it makes the most sense to them. This is also one reason why we don't just stop doing analysis when we find the first diagnostic. For example, if the dead code contains a reference to a class and the user wants to rename the class before addressing the issue with the type of the parameter, then we'd like to be able to rename the reference to the class even though it's in dead code.

[lrhn]

I don't think it's wrong to assume that reading a definitely initialized local variable is safe.

It is safe. If you ever get to this point in the code it will read a value of type Never from the variable - which just proves that the original cause of dead-code-ness is earlier. The variable hasn't actually been definitely initialized, but all parameters are designated as definitely assigned. So the function hasn't even been called.

That's what makes it so hard to reason about dead code. We can usually assume something about the state before code, for example that it's achievable. For dead code we don't have that. We can't really assume soundness, because we can't assume anything about the value of a variable or other expression when it's evaluated in a state that has no way to be created.
The code is vacuously both sound and unsound at the same time.

Whatever we do, we'll have to make some heuristic decisions about what we assume, what we conclude, and what we let propagate from that, for known dead code.

One heuristic is that non-trivial code is not intended to be dead, not forever.

The current heuristics are actually pretty good. If there is code after a return or throw, we treat it as if control flows past the return.
That's exactly what a user needs if they've temporarily inserted an early return to bisect-debug their function.

The same way, code after a Never-typed expression can choose to assume that the Never-typed expression somehow managed not to throw. It has "a value" with no actual known properties.
If we do Never? x = ...; if (x != null) { dead!; } then the dead code is known to be unreachable, just as surely as if (false) { dead!; }.

Here it gets more tricky, because the condition could promote on the true branch, but we know the true branch won't be taken.
So if we pretend that there is a way, where the condition was true, then we should promote x to Never (I think we'd do that for this example, we just don't do it for int x = ...; if (x == null) { ... } too, if for no other reason than because Never is not a type of interest for an int variable).
I don't know what the right choice is here. Maybe we just need to try and see what is least surprising.

The consistent choice would be to do whatever we would do for the same expression if it was possible, and ignore that we know it's not. Even for Null x = null; if (x != null) { dead(x)!; }, we should just follow the normal rules for promotion, and hope the best.

(And then keep not joining dead paths into live paths, because the state of a dead path may still be garbage, no matter how good our heuristics.)

[stereotype441]

@eernstg

This raises a couple of questions:

• Do we simply have a bug in the treatment of formal parameters of a type T <: Never? Or is it intentional that we treat them as "safely readable, even if the type is Never"?

Good guess! I did some digging and yes, we do have a flow analysis bug. The circumstances necessary to provoke it are that an expression must:

• Have a static type of Never,
• Be associated by flow analysis with an ExpressionInfo object*,
• And be used in a conditional context**,

When these conditions are met, the fact that the code is unreachable is forgotten when analyzing the "true" and "false" branches of the conditional.

*Expressions are associated with an ExpressionInfo object whenever they might require special treatment by flow analysis. This includes reads of local variables (and parameters), property gets, boolean literals, null literals, conditional expressions, the expression this, and any of the expressions produced by ||, &&, is, is!, ==, !=, and prefix !.
**A "conditional context" means the condition of an assert, do, for, if, or while, or a conditional expression, or an operand of ||, &&, or prefix !.

I've filed a separate issue about this (dart-lang/sdk#60265) and I'll work on a bug fix. In principle, the fix might potentially break client code, so I'll need to do some investigation to see whether the fix needs to be language-versioned. But it's hard to imagine anyone having a legitimate reason to use an expression with a static type of Never in a conditional context, so hopefully I'll be able to do just do the fix using the usual breaking change process.

• Can we perform a static analysis on dead code that disregards all information from flow analysis? Or can we include some flow analysis information without producing absurd results? Should we?

I suspect you're filing this issue to gather more input on the topic we discussed in the language team meeting yesterday. Since I already expressed my opinion in that meeting, I'll try to keep my response short.

As far as I'm aware, we currently analyze dead code in exactly the same way we analyze live code, with just one exception: at a control flow join, if one code path is dead and another code path is alive, then flow analysis ignores the dead code path. This is at the heart of how if (x == null) return; promotes x: at the end of the if statement, the "true" branch (which is dead, since it contains return;) is joined with the "false" branch (in which x is promoted); since the "true" branch is dead, the promotion of x is retained.

Note that for the purpose of joins, liveness/deadness is computed relative to the point where the control flow split occurred. So an appearance of if (x == null) return; in a block of code that is already dead will nonetheless still promote x.

I personally think this was a good design choice, and I don't see a compelling reason to change it.

[eernstg]

Sounds good!

With dart-lang/sdk#60265, I think we can conclude something like the following:

• This is tricky.
• What we're already doing today is probably quite reasonable.

Or do you see any obvious improvement opportunities?

[stereotype441]

Sounds good!

With dart-lang/sdk#60265, I think we can conclude something like the following:

• This is tricky.
• What we're already doing today is probably quite reasonable.

Or do you see any obvious improvement opportunities?

Just to be clear, when you say "With dart-lang/sdk#60265", do you mean "in regards to dart-lang/sdk#60265", or "now that dart-lang/sdk#60265 is being addressed elsewhere"?.

I think you mean "now that dart-lang/sdk#60265 is being addressed elsewhere". In which case, yes, I agree 😃.

[eernstg]

I think you mean "now that dart-lang/sdk#60265 is being addressed elsewhere".

Exactly. 😄