blob: 6a287a8072da4a90dc6fb273caa88bb0ab4477ea [file] [log] [blame]
// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
import 'package:meta/meta.dart';
/// [AssignedVariables] is a helper class capable of computing the set of
/// variables that are potentially written to, and potentially captured by
/// closures, at various locations inside the code being analyzed. This class
/// should be used prior to running flow analysis, to compute the sets of
/// variables to pass in to flow analysis.
///
/// This class is intended to be used in two phases. In the first phase, the
/// client should traverse the source code recursively, making calls to
/// [beginNode] and [endNode] to indicate the constructs in which writes should
/// be tracked, and calls to [write] to indicate when a write is encountered.
/// The order of visiting is not important provided that nesting is respected.
/// This phase is called the "pre-traversal" because it should happen prior to
/// flow analysis.
///
/// Then, in the second phase, the client may make queries using
/// [capturedAnywhere], [writtenInNode], and [capturedInNode].
///
/// We use the term "node" to refer generally to a loop statement, switch
/// statement, try statement, loop collection element, local function, or
/// closure.
class AssignedVariables<Node extends Object, Variable extends Object> {
/// Mapping from a node to the info for that node.
final Map<Node, AssignedVariablesNodeInfo> _info =
new Map<Node, AssignedVariablesNodeInfo>.identity();
/// Info for the variables written or captured anywhere in the code being
/// analyzed.
final AssignedVariablesNodeInfo _anywhere = new AssignedVariablesNodeInfo();
/// Stack of info for nodes that have been entered but not yet left.
final List<AssignedVariablesNodeInfo> _stack = [
new AssignedVariablesNodeInfo()
];
/// When assertions are enabled, the set of info objects that have been
/// retrieved by [deferNode] but not yet sent to [storeNode].
final Set<AssignedVariablesNodeInfo> _deferredInfos =
new Set<AssignedVariablesNodeInfo>.identity();
/// Keeps track of whether [finish] has been called.
bool _isFinished = false;
final PromotionKeyStore<Variable> _promotionKeyStore =
new PromotionKeyStore<Variable>();
/// This method should be called during pre-traversal, to mark the start of a
/// loop statement, switch statement, try statement, loop collection element,
/// local function, closure, or late variable initializer which might need to
/// be queried later.
///
/// The span between the call to [beginNode] and [endNode] should cover any
/// statements and expressions that might be crossed by a backwards jump. So
/// for instance, in a "for" loop, the condition, updaters, and body should be
/// covered, but the initializers should not. Similarly, in a switch
/// statement, the body of the switch statement should be covered, but the
/// switch expression should not.
void beginNode() {
assert(!_isFinished);
_stack.add(new AssignedVariablesNodeInfo());
}
/// This method should be called during pre-traversal, to indicate that the
/// declaration of a variable has been found.
///
/// It is not required for the declaration to be seen prior to its use (this
/// is to allow for error recovery in the analyzer).
void declare(Variable variable) {
assert(!_isFinished);
int variableKey = _promotionKeyStore.keyForVariable(variable);
_stack.last._declared.add(variableKey);
_anywhere._declared.add(variableKey);
}
/// This method may be called during pre-traversal, to mark the end of a
/// loop statement, switch statement, try statement, loop collection element,
/// local function, closure, or late variable initializer which might need to
/// be queried later.
///
/// [isClosureOrLateVariableInitializer] should be true if the node is a local
/// function or closure, or a late variable initializer.
///
/// In contrast to [endNode], this method doesn't store the data gathered for
/// the node for later use; instead it returns it to the caller. At a later
/// time, the caller should pass the returned data to [storeNodeInfo].
///
/// See [beginNode] for more details.
AssignedVariablesNodeInfo deferNode(
{bool isClosureOrLateVariableInitializer: false}) {
assert(!_isFinished);
AssignedVariablesNodeInfo info = _stack.removeLast();
info._read.removeAll(info._declared);
info._written.removeAll(info._declared);
info._readCaptured.removeAll(info._declared);
info._captured.removeAll(info._declared);
AssignedVariablesNodeInfo last = _stack.last;
last._read.addAll(info._read);
last._written.addAll(info._written);
last._readCaptured.addAll(info._readCaptured);
last._captured.addAll(info._captured);
if (isClosureOrLateVariableInitializer) {
last._readCaptured.addAll(info._read);
_anywhere._readCaptured.addAll(info._read);
last._captured.addAll(info._written);
_anywhere._captured.addAll(info._written);
}
// If we have already deferred this info, something has gone horribly wrong.
assert(_deferredInfos.add(info));
return info;
}
/// This method may be called during pre-traversal, to discard the effects of
/// the most recent unmatched call to [beginNode].
///
/// This is necessary because try/catch/finally needs to be desugared into
/// a try/catch nested inside a try/finally, however the pre-traversal phase
/// of the front end happens during parsing, so when a `try` is encountered,
/// it is not known whether it will need to be desugared into two nested
/// `try`s. To cope with this, the front end may call [beginNode] twice upon
/// seeing the two `try`s, and later if it turns out that no desugaring was
/// needed, use [discardNode] to discard the effects of one of the [beginNode]
/// calls.
void discardNode() {
assert(!_isFinished);
AssignedVariablesNodeInfo discarded = _stack.removeLast();
AssignedVariablesNodeInfo last = _stack.last;
last._declared.addAll(discarded._declared);
last._read.addAll(discarded._read);
last._written.addAll(discarded._written);
last._readCaptured.addAll(discarded._readCaptured);
last._captured.addAll(discarded._captured);
}
/// This method should be called during pre-traversal, to mark the end of a
/// loop statement, switch statement, try statement, loop collection element,
/// local function, closure, or late variable initializer which might need to
/// be queried later.
///
/// [isClosureOrLateVariableInitializer] should be true if the node is a local
/// function or closure, or a late variable initializer.
///
/// This is equivalent to a call to [deferNode] followed immediately by a call
/// to [storeInfo].
///
/// See [beginNode] for more details.
void endNode(Node node, {bool isClosureOrLateVariableInitializer: false}) {
assert(!_isFinished);
storeInfo(
node,
deferNode(
isClosureOrLateVariableInitializer:
isClosureOrLateVariableInitializer));
}
/// Call this after visiting the code to be analyzed, to check invariants.
void finish() {
assert(() {
assert(!_isFinished);
assert(
_deferredInfos.isEmpty, "Deferred infos not stored: $_deferredInfos");
assert(_stack.length == 1, "Unexpected stack: $_stack");
AssignedVariablesNodeInfo last = _stack.last;
Set<int> undeclaredReads = last._read.difference(last._declared);
assert(undeclaredReads.isEmpty,
'Variables read from but not declared: $undeclaredReads');
Set<int> undeclaredWrites = last._written.difference(last._declared);
assert(undeclaredWrites.isEmpty,
'Variables written to but not declared: $undeclaredWrites');
Set<int> undeclaredCaptures = last._captured.difference(last._declared);
assert(undeclaredCaptures.isEmpty,
'Variables captured but not declared: $undeclaredCaptures');
return true;
}());
_isFinished = true;
}
/// Call this method between calls to [beginNode] and [endNode]/[deferNode],
/// if it is necessary to temporarily process some code outside the current
/// node. Returns a data structure that should be passed to [pushNode].
///
/// This is used by the front end when building for-elements in lists, maps,
/// and sets; their initializers are partially built after building their
/// loop conditions but before completely building their bodies.
AssignedVariablesNodeInfo popNode() {
assert(!_isFinished);
return _stack.removeLast();
}
/// Call this method to un-do the effect of [popNode].
void pushNode(AssignedVariablesNodeInfo node) {
assert(!_isFinished);
_stack.add(node);
}
void read(Variable variable) {
assert(!_isFinished);
int variableKey = _promotionKeyStore.keyForVariable(variable);
_stack.last._read.add(variableKey);
_anywhere._read.add(variableKey);
}
/// Call this method to register that the node [from] for which information
/// has been stored is replaced by the node [to].
// TODO(johnniwinther): Remove this when unified collections are encoded as
// general elements in the front-end.
void reassignInfo(Node from, Node to) {
assert(!_info.containsKey(to), "Node $to already has info: ${_info[to]}");
AssignedVariablesNodeInfo? info = _info.remove(from);
assert(
info != null,
'No information for $from (${from.hashCode}) in '
'{${_info.keys.map((k) => '$k (${k.hashCode})').join(',')}}');
_info[to] = info!;
}
/// This method may be called at any time between a call to [deferNode] and
/// the call to [finish], to store assigned variable info for the node.
void storeInfo(Node node, AssignedVariablesNodeInfo info) {
assert(!_isFinished);
// Caller should not try to store the same piece of info more than once.
assert(_deferredInfos.remove(info));
_info[node] = info;
}
String toString() {
StringBuffer sb = new StringBuffer();
sb.write('AssignedVariables(');
_printOn(sb);
sb.write(')');
return sb.toString();
}
/// This method should be called during pre-traversal, to mark a write to a
/// variable.
void write(Variable variable) {
assert(!_isFinished);
int variableKey = _promotionKeyStore.keyForVariable(variable);
_stack.last._written.add(variableKey);
_anywhere._written.add(variableKey);
}
/// Queries the information stored for the given [node].
AssignedVariablesNodeInfo _getInfoForNode(Node node) {
return _info[node] ??
(throw new StateError('No information for $node (${node.hashCode}) in '
'{${_info.keys.map((k) => '$k (${k.hashCode})').join(',')}}'));
}
void _printOn(StringBuffer sb) {
sb.write('_info=$_info,');
sb.write('_stack=$_stack,');
sb.write('_anywhere=$_anywhere');
}
}
/// Extension of [AssignedVariables] intended for use in tests. This class
/// exposes the results of the analysis so that they can be tested directly.
/// Not intended to be used by clients of flow analysis.
class AssignedVariablesForTesting<Node extends Object, Variable extends Object>
extends AssignedVariables<Node, Variable> {
Set<int> get capturedAnywhere => _anywhere._captured;
Set<int> get declaredAtTopLevel => _stack.first._declared;
Set<int> get readAnywhere => _anywhere._read;
Set<int> get readCapturedAnywhere => _anywhere._readCaptured;
Set<int> get writtenAnywhere => _anywhere._written;
Set<int> capturedInNode(Node node) => _getInfoForNode(node)._captured;
Set<int> declaredInNode(Node node) => _getInfoForNode(node)._declared;
bool isTracked(Node node) => _info.containsKey(node);
int keyForVariable(Variable variable) =>
_promotionKeyStore.keyForVariable(variable);
Set<int> readCapturedInNode(Node node) => _getInfoForNode(node)._readCaptured;
Set<int> readInNode(Node node) => _getInfoForNode(node)._read;
String toString() {
StringBuffer sb = new StringBuffer();
sb.write('AssignedVariablesForTesting(');
_printOn(sb);
sb.write(')');
return sb.toString();
}
Variable variableForKey(int key) => _promotionKeyStore.variableForKey(key)!;
Set<int> writtenInNode(Node node) => _getInfoForNode(node)._written;
}
/// Information tracked by [AssignedVariables] for a single node.
class AssignedVariablesNodeInfo {
final Set<int> _read = {};
/// The set of local variables that are potentially written in the node.
final Set<int> _written = {};
final Set<int> _readCaptured = {};
/// The set of local variables for which a potential write is captured by a
/// local function or closure inside the node.
final Set<int> _captured = {};
/// The set of local variables that are declared in the node.
final Set<int> _declared = {};
String toString() =>
'AssignedVariablesNodeInfo(_written=$_written, _captured=$_captured, '
'_declared=$_declared)';
}
/// Non-promotion reason describing the situation where a variable was not
/// promoted due to an explicit write to the variable appearing somewhere in the
/// source code.
class DemoteViaExplicitWrite<Variable extends Object>
extends NonPromotionReason {
/// The local variable that was not promoted.
final Variable variable;
/// The node that wrote to the variable; this corresponds to a node that was
/// passed to [FlowAnalysis.write].
final Object node;
DemoteViaExplicitWrite(this.variable, this.node);
@override
String get documentationLink => 'http://dart.dev/go/non-promo-write';
@override
String get shortName => 'explicitWrite';
@override
R accept<R, Node extends Object, Variable extends Object,
Type extends Object>(
NonPromotionReasonVisitor<R, Node, Variable, Type> visitor) =>
visitor.visitDemoteViaExplicitWrite(
this as DemoteViaExplicitWrite<Variable>);
@override
String toString() => 'DemoteViaExplicitWrite($node)';
}
/// Information gathered by flow analysis about an argument to either
/// `identical` or `operator ==`.
class EqualityInfo<Type extends Object> {
/// The [ExpressionInfo] for the expression. This is used to determine
/// whether the expression is a `null` literal.
final ExpressionInfo<Type>? _expressionInfo;
/// The type of the expression on the LHS of `==` or `!=`.
final Type _type;
/// If the LHS of `==` or `!=` is a reference, the thing being referred to.
/// Otherwise `null`.
final ReferenceWithType<Type>? _reference;
EqualityInfo._(this._expressionInfo, this._type, this._reference);
@override
String toString() =>
'EqualityInfo(expressionInfo: $_expressionInfo, type: $_type, reference: '
'$_reference)';
}
/// A collection of flow models representing the possible outcomes of evaluating
/// an expression that are relevant to flow analysis.
class ExpressionInfo<Type extends Object> {
/// The state after the expression evaluates, if we don't care what it
/// evaluates to.
final FlowModel<Type> after;
/// The state after the expression evaluates, if it evaluates to `true`.
final FlowModel<Type> ifTrue;
/// The state after the expression evaluates, if it evaluates to `false`.
final FlowModel<Type> ifFalse;
ExpressionInfo(
{required this.after, required this.ifTrue, required this.ifFalse});
/// Computes a new [ExpressionInfo] based on this one, but with the roles of
/// [ifTrue] and [ifFalse] reversed.
ExpressionInfo<Type> invert() =>
new ExpressionInfo<Type>(after: after, ifTrue: ifFalse, ifFalse: ifTrue);
ExpressionInfo<Type>? rebaseForward(
TypeOperations<Type> typeOperations, FlowModel<Type> base) =>
new ExpressionInfo(
after: base,
ifTrue: ifTrue.rebaseForward(typeOperations, base),
ifFalse: ifFalse.rebaseForward(typeOperations, base));
@override
String toString() =>
'ExpressionInfo(after: $after, _ifTrue: $ifTrue, ifFalse: $ifFalse)';
}
/// Implementation of flow analysis to be shared between the analyzer and the
/// front end.
///
/// The client should create one instance of this class for every method, field,
/// or top level variable to be analyzed, and call the appropriate methods
/// while visiting the code for type inference.
abstract class FlowAnalysis<Node extends Object, Statement extends Node,
Expression extends Object, Variable extends Object, Type extends Object> {
factory FlowAnalysis(Operations<Variable, Type> operations,
AssignedVariables<Node, Variable> assignedVariables,
{required bool respectImplicitlyTypedVarInitializers}) {
return new _FlowAnalysisImpl(operations, assignedVariables,
respectImplicitlyTypedVarInitializers:
respectImplicitlyTypedVarInitializers);
}
factory FlowAnalysis.legacy(Operations<Variable, Type> operations,
AssignedVariables<Node, Variable> assignedVariables) =
_LegacyTypePromotion;
/// Return `true` if the current state is reachable.
bool get isReachable;
TypeOperations<Type> get operations;
/// Call this method after visiting an "as" expression.
///
/// [subExpression] should be the expression to which the "as" check was
/// applied. [type] should be the type being checked.
void asExpression_end(Expression subExpression, Type type);
/// Call this method after visiting the condition part of an assert statement
/// (or assert initializer).
///
/// [condition] should be the assert statement's condition.
///
/// See [assert_begin] for more information.
void assert_afterCondition(Expression condition);
/// Call this method before visiting the condition part of an assert statement
/// (or assert initializer).
///
/// The order of visiting an assert statement with no "message" part should
/// be:
/// - Call [assert_begin]
/// - Visit the condition
/// - Call [assert_afterCondition]
/// - Call [assert_end]
///
/// The order of visiting an assert statement with a "message" part should be:
/// - Call [assert_begin]
/// - Visit the condition
/// - Call [assert_afterCondition]
/// - Visit the message
/// - Call [assert_end]
void assert_begin();
/// Call this method after visiting an assert statement (or assert
/// initializer).
///
/// See [assert_begin] for more information.
void assert_end();
/// Call this method when visiting a boolean literal expression.
void booleanLiteral(Expression expression, bool value);
/// Call this method just before visiting a conditional expression ("?:").
void conditional_conditionBegin();
/// Call this method upon reaching the ":" part of a conditional expression
/// ("?:"). [thenExpression] should be the expression preceding the ":".
void conditional_elseBegin(Expression thenExpression);
/// Call this method when finishing the visit of a conditional expression
/// ("?:"). [elseExpression] should be the expression preceding the ":", and
/// [conditionalExpression] should be the whole conditional expression.
void conditional_end(
Expression conditionalExpression, Expression elseExpression);
/// Call this method upon reaching the "?" part of a conditional expression
/// ("?:"). [condition] should be the expression preceding the "?".
/// [conditionalExpression] should be the entire conditional expression.
void conditional_thenBegin(Expression condition, Node conditionalExpression);
/// Register a declaration of the [variable] in the current state.
/// Should also be called for function parameters.
///
/// A local variable is [initialized] if its declaration has an initializer.
/// A function parameter is always initialized, so [initialized] is `true`.
void declare(Variable variable, bool initialized);
/// Call this method before visiting the body of a "do-while" statement.
/// [doStatement] should be the same node that was passed to
/// [AssignedVariables.endNode] for the do-while statement.
void doStatement_bodyBegin(Statement doStatement);
/// Call this method after visiting the body of a "do-while" statement, and
/// before visiting its condition.
void doStatement_conditionBegin();
/// Call this method after visiting the condition of a "do-while" statement.
/// [condition] should be the condition of the loop.
void doStatement_end(Expression condition);
/// Call this method just after visiting either side of a binary `==` or `!=`
/// expression, or an argument to `identical`.
///
/// Returns information about the expression that will later be needed by
/// [equalityOperation_end].
///
/// Note: the return type is nullable because legacy type promotion doesn't
/// need to record information about equality operands.
EqualityInfo<Type>? equalityOperand_end(Expression operand, Type type);
/// Call this method just after visiting the operands of a binary `==` or `!=`
/// expression, or an invocation of `identical`.
///
/// [leftOperandInfo] and [rightOperandInfo] should be the values returned by
/// [equalityOperand_end].
void equalityOperation_end(Expression wholeExpression,
EqualityInfo<Type>? leftOperandInfo, EqualityInfo<Type>? rightOperandInfo,
{bool notEqual = false});
/// Retrieves the [ExpressionInfo] associated with [target], if known. Will
/// return `null` if (a) no info is associated with [target], or (b) another
/// expression with info has been visited more recently than [target]. For
/// testing only.
ExpressionInfo<Type>? expressionInfoForTesting(Expression target);
/// This method should be called at the conclusion of flow analysis for a top
/// level function or method. Performs assertion checks.
void finish();
/// Call this method just before visiting the body of a conventional "for"
/// statement or collection element. See [for_conditionBegin] for details.
///
/// If a "for" statement is being entered, [node] is an opaque representation
/// of the loop, for use as the target of future calls to [handleBreak] or
/// [handleContinue]. If a "for" collection element is being entered, [node]
/// should be `null`.
///
/// [condition] is an opaque representation of the loop condition; it is
/// matched against expressions passed to previous calls to determine whether
/// the loop condition should cause any promotions to occur. If [condition]
/// is null, the condition is understood to be empty (equivalent to a
/// condition of `true`).
void for_bodyBegin(Statement? node, Expression? condition);
/// Call this method just before visiting the condition of a conventional
/// "for" statement or collection element.
///
/// Note that a conventional "for" statement is a statement of the form
/// `for (initializers; condition; updaters) body`. Statements of the form
/// `for (variable in iterable) body` should use [forEach_bodyBegin]. Similar
/// for "for" collection elements.
///
/// The order of visiting a "for" statement or collection element should be:
/// - Visit the initializers.
/// - Call [for_conditionBegin].
/// - Visit the condition.
/// - Call [for_bodyBegin].
/// - Visit the body.
/// - Call [for_updaterBegin].
/// - Visit the updaters.
/// - Call [for_end].
///
/// [node] should be the same node that was passed to
/// [AssignedVariables.endNode] for the for statement.
void for_conditionBegin(Node node);
/// Call this method just after visiting the updaters of a conventional "for"
/// statement or collection element. See [for_conditionBegin] for details.
void for_end();
/// Call this method just before visiting the updaters of a conventional "for"
/// statement or collection element. See [for_conditionBegin] for details.
void for_updaterBegin();
/// Call this method just before visiting the body of a "for-in" statement or
/// collection element.
///
/// The order of visiting a "for-in" statement or collection element should
/// be:
/// - Visit the iterable expression.
/// - Call [forEach_bodyBegin].
/// - Visit the body.
/// - Call [forEach_end].
///
/// [node] should be the same node that was passed to
/// [AssignedVariables.endNode] for the for statement.
void forEach_bodyBegin(Node node);
/// Call this method just before visiting the body of a "for-in" statement or
/// collection element. See [forEach_bodyBegin] for details.
void forEach_end();
/// Call this method to forward information on [oldExpression] to
/// [newExpression].
///
/// This can be used to preserve promotions through a replacement from
/// [oldExpression] to [newExpression]. For instance when rewriting
///
/// method(int i) {
/// if (i is int) { ... } else { ... }
/// }
///
/// to
///
/// method(int i) {
/// if (i is int || throw ...) { ... } else { ... }
/// }
///
/// the promotion `i is int` can be forwarded to `i is int || throw ...` and
/// there preserved in the surrounding if statement.
void forwardExpression(Expression newExpression, Expression oldExpression);
/// Call this method just before visiting the body of a function expression or
/// local function.
///
/// [node] should be the same node that was passed to
/// [AssignedVariables.endNode] for the function expression.
void functionExpression_begin(Node node);
/// Call this method just after visiting the body of a function expression or
/// local function.
void functionExpression_end();
/// Call this method when visiting a break statement. [target] should be the
/// statement targeted by the break.
void handleBreak(Statement target);
/// Call this method when visiting a continue statement. [target] should be
/// the statement targeted by the continue.
void handleContinue(Statement target);
/// Register the fact that the current state definitely exists, e.g. returns
/// from the body, throws an exception, etc.
///
/// Should also be called if a subexpression's type is Never.
void handleExit();
/// Call this method after visiting the RHS of an if-null expression ("??")
/// or if-null assignment ("??=").
///
/// Note: for an if-null assignment, the call to [write] should occur before
/// the call to [ifNullExpression_end] (since the write only occurs if the
/// read resulted in a null value).
void ifNullExpression_end();
/// Call this method after visiting the LHS of an if-null expression ("??")
/// or if-null assignment ("??=").
void ifNullExpression_rightBegin(
Expression leftHandSide, Type leftHandSideType);
/// Call this method before visiting the condition part of an if statement.
///
/// The order of visiting an if statement with no "else" part should be:
/// - Call [ifStatement_conditionBegin]
/// - Visit the condition
/// - Call [ifStatement_thenBegin]
/// - Visit the "then" statement
/// - Call [ifStatement_end], passing `false` for `hasElse`.
///
/// The order of visiting an if statement with an "else" part should be:
/// - Call [ifStatement_conditionBegin]
/// - Visit the condition
/// - Call [ifStatement_thenBegin]
/// - Visit the "then" statement
/// - Call [ifStatement_elseBegin]
/// - Visit the "else" statement
/// - Call [ifStatement_end], passing `true` for `hasElse`.
void ifStatement_conditionBegin();
/// Call this method after visiting the "then" part of an if statement, and
/// before visiting the "else" part.
void ifStatement_elseBegin();
/// Call this method after visiting an if statement.
void ifStatement_end(bool hasElse);
/// Call this method after visiting the condition part of an if statement.
/// [condition] should be the if statement's condition. [ifNode] should be
/// the entire `if` statement (or the collection literal entry).
void ifStatement_thenBegin(Expression condition, Node ifNode);
/// Call this method after visiting the initializer of a variable declaration.
void initialize(
Variable variable, Type initializerType, Expression initializerExpression,
{required bool isFinal,
required bool isLate,
required bool isImplicitlyTyped});
/// Return whether the [variable] is definitely assigned in the current state.
bool isAssigned(Variable variable);
/// Call this method after visiting the LHS of an "is" expression.
///
/// [isExpression] should be the complete expression. [subExpression] should
/// be the expression to which the "is" check was applied. [isNot] should be
/// a boolean indicating whether this is an "is" or an "is!" expression.
/// [type] should be the type being checked.
void isExpression_end(
Expression isExpression, Expression subExpression, bool isNot, Type type);
/// Return whether the [variable] is definitely unassigned in the current
/// state.
bool isUnassigned(Variable variable);
/// Call this method before visiting a labeled statement.
/// Call [labeledStatement_end] after visiting the statement.
void labeledStatement_begin(Statement node);
/// Call this method after visiting a labeled statement.
void labeledStatement_end();
/// Call this method just before visiting the initializer of a late variable.
void lateInitializer_begin(Node node);
/// Call this method just after visiting the initializer of a late variable.
void lateInitializer_end();
/// Call this method before visiting the LHS of a logical binary operation
/// ("||" or "&&").
void logicalBinaryOp_begin();
/// Call this method after visiting the RHS of a logical binary operation
/// ("||" or "&&").
/// [wholeExpression] should be the whole logical binary expression.
/// [rightOperand] should be the RHS. [isAnd] should indicate whether the
/// logical operator is "&&" or "||".
void logicalBinaryOp_end(Expression wholeExpression, Expression rightOperand,
{required bool isAnd});
/// Call this method after visiting the LHS of a logical binary operation
/// ("||" or "&&").
/// [rightOperand] should be the LHS. [isAnd] should indicate whether the
/// logical operator is "&&" or "||". [wholeExpression] should be the whole
/// logical binary expression.
void logicalBinaryOp_rightBegin(Expression leftOperand, Node wholeExpression,
{required bool isAnd});
/// Call this method after visiting a logical not ("!") expression.
/// [notExpression] should be the complete expression. [operand] should be
/// the subexpression whose logical value is being negated.
void logicalNot_end(Expression notExpression, Expression operand);
/// Call this method just after visiting a non-null assertion (`x!`)
/// expression.
void nonNullAssert_end(Expression operand);
/// Call this method after visiting an expression using `?.`.
void nullAwareAccess_end();
/// Call this method after visiting a null-aware operator such as `?.`,
/// `?..`, `?.[`, or `?..[`.
///
/// [target] should be the expression just before the null-aware operator, or
/// `null` if the null-aware access starts a cascade section.
///
/// [targetType] should be the type of the expression just before the
/// null-aware operator, and should be non-null even if the null-aware access
/// starts a cascade section.
///
/// Note that [nullAwareAccess_end] should be called after the conclusion
/// of any null-shorting that is caused by the `?.`. So, for example, if the
/// code being analyzed is `x?.y?.z(x)`, [nullAwareAccess_rightBegin] should
/// be called once upon reaching each `?.`, but [nullAwareAccess_end] should
/// not be called until after processing the method call to `z(x)`.
void nullAwareAccess_rightBegin(Expression? target, Type targetType);
/// Call this method when encountering an expression that is a `null` literal.
void nullLiteral(Expression expression);
/// Call this method just after visiting a parenthesized expression.
///
/// This is only necessary if the implementation uses a different [Expression]
/// object to represent a parenthesized expression and its contents.
void parenthesizedExpression(
Expression outerExpression, Expression innerExpression);
/// Retrieves the type that the [variable] is promoted to, if the [variable]
/// is currently promoted. Otherwise returns `null`.
Type? promotedType(Variable variable);
/// Call this method just after visiting a property get expression.
/// [wholeExpression] should be the whole property get, [target] should be the
/// expression to the left hand side of the `.`, and [propertyName] should be
/// the identifier to the right hand side of the `.`. [staticType] should be
/// the static type of the value returned by the property get.
///
/// [propertyMember] should be whatever data structure the client uses to keep
/// track of the field or property being accessed. In the event of
/// non-promotion of a property get, this value can be retrieved from
/// [PropertyNotPromoted.propertyMember].
void propertyGet(Expression wholeExpression, Expression target,
String propertyName, Object? propertyMember, Type staticType);
/// Retrieves the SSA node associated with [variable], or `null` if [variable]
/// is not associated with an SSA node because it is write captured. For
/// testing only.
@visibleForTesting
SsaNode<Type>? ssaNodeForTesting(Variable variable);
/// Call this method just before visiting one of the cases in the body of a
/// switch statement. See [switchStatement_expressionEnd] for details.
///
/// [hasLabel] indicates whether the case has any labels.
///
/// [node] should be the same node that was passed to
/// [AssignedVariables.endNode] for the switch statement.
void switchStatement_beginCase(bool hasLabel, Node node);
/// Call this method just after visiting the body of a switch statement. See
/// [switchStatement_expressionEnd] for details.
///
/// [isExhaustive] indicates whether the switch statement had a "default"
/// case, or is based on an enumeration and all the enumeration constants
/// were listed in cases.
void switchStatement_end(bool isExhaustive);
/// Call this method just after visiting the expression part of a switch
/// statement.
///
/// The order of visiting a switch statement should be:
/// - Visit the switch expression.
/// - Call [switchStatement_expressionEnd].
/// - For each switch case (including the default case, if any):
/// - Call [switchStatement_beginCase].
/// - Visit the case.
/// - Call [switchStatement_end].
void switchStatement_expressionEnd(Statement switchStatement);
/// Call this method just after visiting the expression `this` (or the
/// pseudo-expression `super`, in the case of the analyzer, which represents
/// `super.x` as a property get whose target is `super`). [expression] should
/// be the `this` or `super` expression. [staticType] should be the static
/// type of `this`.
void thisOrSuper(Expression expression, Type staticType);
/// Call this method just after visiting an expression that represents a
/// property get on `this` or `super`. This handles situations where there is
/// an implicit reference to `this`, or the case of the front end, where
/// `super.x` is represented by a single expression. [expression] should be
/// the whole property get, and [propertyName] should be the name of the
/// property being read. [staticType] should be the static type of the value
/// returned by the property get.
///
/// [propertyMember] should be whatever data structure the client uses to keep
/// track of the field or property being accessed. In the event of
/// non-promotion of a property get, this value can be retrieved from
/// [PropertyNotPromoted.propertyMember].
void thisOrSuperPropertyGet(Expression expression, String propertyName,
Object? propertyMember, Type staticType);
/// Call this method just before visiting the body of a "try/catch" statement.
///
/// The order of visiting a "try/catch" statement should be:
/// - Call [tryCatchStatement_bodyBegin]
/// - Visit the try block
/// - Call [tryCatchStatement_bodyEnd]
/// - For each catch block:
/// - Call [tryCatchStatement_catchBegin]
/// - Call [initialize] for the exception and stack trace variables
/// - Visit the catch block
/// - Call [tryCatchStatement_catchEnd]
/// - Call [tryCatchStatement_end]
///
/// The order of visiting a "try/catch/finally" statement should be:
/// - Call [tryFinallyStatement_bodyBegin]
/// - Call [tryCatchStatement_bodyBegin]
/// - Visit the try block
/// - Call [tryCatchStatement_bodyEnd]
/// - For each catch block:
/// - Call [tryCatchStatement_catchBegin]
/// - Call [initialize] for the exception and stack trace variables
/// - Visit the catch block
/// - Call [tryCatchStatement_catchEnd]
/// - Call [tryCatchStatement_end]
/// - Call [tryFinallyStatement_finallyBegin]
/// - Visit the finally block
/// - Call [tryFinallyStatement_end]
void tryCatchStatement_bodyBegin();
/// Call this method just after visiting the body of a "try/catch" statement.
/// See [tryCatchStatement_bodyBegin] for details.
///
/// [body] should be the same node that was passed to
/// [AssignedVariables.endNode] for the "try" part of the try/catch statement.
void tryCatchStatement_bodyEnd(Node body);
/// Call this method just before visiting a catch clause of a "try/catch"
/// statement. See [tryCatchStatement_bodyBegin] for details.
///
/// [exceptionVariable] should be the exception variable declared by the catch
/// clause, or `null` if there is no exception variable. Similar for
/// [stackTraceVariable].
void tryCatchStatement_catchBegin(
Variable? exceptionVariable, Variable? stackTraceVariable);
/// Call this method just after visiting a catch clause of a "try/catch"
/// statement. See [tryCatchStatement_bodyBegin] for details.
void tryCatchStatement_catchEnd();
/// Call this method just after visiting a "try/catch" statement. See
/// [tryCatchStatement_bodyBegin] for details.
void tryCatchStatement_end();
/// Call this method just before visiting the body of a "try/finally"
/// statement.
///
/// The order of visiting a "try/finally" statement should be:
/// - Call [tryFinallyStatement_bodyBegin]
/// - Visit the try block
/// - Call [tryFinallyStatement_finallyBegin]
/// - Visit the finally block
/// - Call [tryFinallyStatement_end]
///
/// See [tryCatchStatement_bodyBegin] for the order of visiting a
/// "try/catch/finally" statement.
void tryFinallyStatement_bodyBegin();
/// Call this method just after visiting a "try/finally" statement.
/// See [tryFinallyStatement_bodyBegin] for details.
void tryFinallyStatement_end();
/// Call this method just before visiting the finally block of a "try/finally"
/// statement. See [tryFinallyStatement_bodyBegin] for details.
///
/// [body] should be the same node that was passed to
/// [AssignedVariables.endNode] for the "try" part of the try/finally
/// statement.
void tryFinallyStatement_finallyBegin(Node body);
/// Call this method when encountering an expression that reads the value of
/// a variable.
///
/// If the variable's type is currently promoted, the promoted type is
/// returned. Otherwise `null` is returned.
Type? variableRead(Expression expression, Variable variable);
/// Call this method after visiting the condition part of a "while" statement.
/// [whileStatement] should be the full while statement. [condition] should
/// be the condition part of the while statement.
void whileStatement_bodyBegin(Statement whileStatement, Expression condition);
/// Call this method before visiting the condition part of a "while"
/// statement.
///
/// [node] should be the same node that was passed to
/// [AssignedVariables.endNode] for the while statement.
void whileStatement_conditionBegin(Node node);
/// Call this method after visiting a "while" statement.
void whileStatement_end();
/// Call this method when an error occurs that may be due to a lack of type
/// promotion, to retrieve information about why [target] was not promoted.
/// This call must be made right after visiting [target].
///
/// The returned value is a function yielding a map whose keys are types that
/// the user might have been expecting the target to be promoted to, and whose
/// values are reasons why the corresponding promotion did not occur. The
/// caller is expected to select which non-promotion reason to report to the
/// user by seeing which promotion would have prevented the error. (For
/// example, if an error occurs due to the target having a nullable type, the
/// caller should report a non-promotion reason associated with non-promotion
/// to a non-nullable type).
///
/// This method is expected to execute fairly efficiently; the bulk of the
/// expensive computation is deferred to the function it returns. The reason
/// for this is that in certain cases, it's not possible to know whether "why
/// not promoted" information will be needed until long after visiting a node.
/// (For example, in resolving a call like
/// `(x as Future<T>).then(y, onError: z)`, we don't know whether an error
/// should be reported at `y` until we've inferred the type argument to
/// `then`, which doesn't occur until after visiting `z`). So the caller may
/// freely call this method after any expression for which an error *might*
/// need to be generated, and then defer invoking the returned function until
/// it is determined that an error actually occurred.
Map<Type, NonPromotionReason> Function() whyNotPromoted(Expression target);
/// Call this method when an error occurs that may be due to a lack of type
/// promotion, to retrieve information about why an implicit reference to
/// `this` was not promoted. [staticType] is the (unpromoted) type of `this`.
///
/// The returned value is a function yielding a map whose keys are types that
/// the user might have been expecting `this` to be promoted to, and whose
/// values are reasons why the corresponding promotion did not occur. The
/// caller is expected to select which non-promotion reason to report to the
/// user by seeing which promotion would have prevented the error. (For
/// example, if an error occurs due to the target having a nullable type, the
/// caller should report a non-promotion reason associated with non-promotion
/// to a non-nullable type).
///
/// This method is expected to execute fairly efficiently; the bulk of the
/// expensive computation is deferred to the function it returns. The reason
/// for this is that in certain cases, it's not possible to know whether "why
/// not promoted" information will be needed until long after visiting a node.
/// (For example, in resolving a call like
/// `(x as Future<T>).then(y, onError: z)`, we don't know whether an error
/// should be reported at `y` until we've inferred the type argument to
/// `then`, which doesn't occur until after visiting `z`). So the caller may
/// freely call this method after any expression for which an error *might*
/// need to be generated, and then defer invoking the returned function until
/// it is determined that an error actually occurred.
Map<Type, NonPromotionReason> Function() whyNotPromotedImplicitThis(
Type staticType);
/// Register write of the given [variable] in the current state.
/// [writtenType] should be the type of the value that was written.
/// [node] should be the syntactic construct performing the write.
/// [writtenExpression] should be the expression that was written, or `null`
/// if the expression that was written is not directly represented in the
/// source code (this happens, for example, with compound assignments and with
/// for-each loops).
///
/// This should also be used for the implicit write to a non-final variable in
/// its initializer, to ensure that the type is promoted to non-nullable if
/// necessary; in this case, [viaInitializer] should be `true`.
void write(Node node, Variable variable, Type writtenType,
Expression? writtenExpression);
/// Prints out a summary of the current state of flow analysis, intended for
/// debugging use only.
void _dumpState();
}
/// Alternate implementation of [FlowAnalysis] that prints out inputs and output
/// at the API boundary, for assistance in debugging.
class FlowAnalysisDebug<Node extends Object, Statement extends Node,
Expression extends Object, Variable extends Object, Type extends Object>
implements FlowAnalysis<Node, Statement, Expression, Variable, Type> {
static int _nextCallbackId = 0;
static Expando<String> _description = new Expando<String>();
FlowAnalysis<Node, Statement, Expression, Variable, Type> _wrapped;
bool _exceptionOccurred = false;
factory FlowAnalysisDebug(Operations<Variable, Type> operations,
AssignedVariables<Node, Variable> assignedVariables,
{required bool respectImplicitlyTypedVarInitializers}) {
print('FlowAnalysisDebug()');
return new FlowAnalysisDebug._(new _FlowAnalysisImpl(
operations, assignedVariables,
respectImplicitlyTypedVarInitializers:
respectImplicitlyTypedVarInitializers));
}
factory FlowAnalysisDebug.legacy(Operations<Variable, Type> operations,
AssignedVariables<Node, Variable> assignedVariables) {
print('FlowAnalysisDebug.legacy()');
return new FlowAnalysisDebug._(
new _LegacyTypePromotion(operations, assignedVariables));
}
FlowAnalysisDebug._(this._wrapped);
@override
bool get isReachable =>
_wrap('isReachable', () => _wrapped.isReachable, isQuery: true);
@override
TypeOperations<Type> get operations => _wrapped.operations;
@override
void asExpression_end(Expression subExpression, Type type) {
_wrap('asExpression_end($subExpression, $type)',
() => _wrapped.asExpression_end(subExpression, type));
}
@override
void assert_afterCondition(Expression condition) {
_wrap('assert_afterCondition($condition)',
() => _wrapped.assert_afterCondition(condition));
}
@override
void assert_begin() {
_wrap('assert_begin()', () => _wrapped.assert_begin());
}
@override
void assert_end() {
_wrap('assert_end()', () => _wrapped.assert_end());
}
@override
void booleanLiteral(Expression expression, bool value) {
_wrap('booleanLiteral($expression, $value)',
() => _wrapped.booleanLiteral(expression, value));
}
@override
void conditional_conditionBegin() {
_wrap('conditional_conditionBegin()',
() => _wrapped.conditional_conditionBegin());
}
@override
void conditional_elseBegin(Expression thenExpression) {
_wrap('conditional_elseBegin($thenExpression',
() => _wrapped.conditional_elseBegin(thenExpression));
}
@override
void conditional_end(
Expression conditionalExpression, Expression elseExpression) {
_wrap('conditional_end($conditionalExpression, $elseExpression',
() => _wrapped.conditional_end(conditionalExpression, elseExpression));
}
@override
void conditional_thenBegin(Expression condition, Node conditionalExpression) {
_wrap('conditional_thenBegin($condition, $conditionalExpression)',
() => _wrapped.conditional_thenBegin(condition, conditionalExpression));
}
@override
void declare(Variable variable, bool initialized) {
_wrap('declare($variable, $initialized)',
() => _wrapped.declare(variable, initialized));
}
@override
void doStatement_bodyBegin(Statement doStatement) {
return _wrap('doStatement_bodyBegin($doStatement)',
() => _wrapped.doStatement_bodyBegin(doStatement));
}
@override
void doStatement_conditionBegin() {
return _wrap('doStatement_conditionBegin()',
() => _wrapped.doStatement_conditionBegin());
}
@override
void doStatement_end(Expression condition) {
return _wrap('doStatement_end($condition)',
() => _wrapped.doStatement_end(condition));
}
@override
EqualityInfo<Type>? equalityOperand_end(Expression operand, Type type) =>
_wrap('equalityOperand_end($operand, $type)',
() => _wrapped.equalityOperand_end(operand, type),
isQuery: true);
@override
void equalityOperation_end(Expression wholeExpression,
EqualityInfo<Type>? leftOperandInfo, EqualityInfo<Type>? rightOperandInfo,
{bool notEqual = false}) {
_wrap(
'equalityOperation_end($wholeExpression, $leftOperandInfo, '
'$rightOperandInfo, notEqual: $notEqual)',
() => _wrapped.equalityOperation_end(
wholeExpression, leftOperandInfo, rightOperandInfo,
notEqual: notEqual));
}
@override
ExpressionInfo<Type>? expressionInfoForTesting(Expression target) {
return _wrap('expressionInfoForTesting($target)',
() => _wrapped.expressionInfoForTesting(target),
isQuery: true);
}
@override
void finish() {
if (_exceptionOccurred) {
_wrap('finish() (skipped)', () {}, isPure: true);
} else {
_wrap('finish()', () => _wrapped.finish(), isPure: true);
}
}
@override
void for_bodyBegin(Statement? node, Expression? condition) {
_wrap('for_bodyBegin($node, $condition)',
() => _wrapped.for_bodyBegin(node, condition));
}
@override
void for_conditionBegin(Node node) {
_wrap('for_conditionBegin($node)', () => _wrapped.for_conditionBegin(node));
}
@override
void for_end() {
_wrap('for_end()', () => _wrapped.for_end());
}
@override
void for_updaterBegin() {
_wrap('for_updaterBegin()', () => _wrapped.for_updaterBegin());
}
@override
void forEach_bodyBegin(Node node) {
return _wrap(
'forEach_bodyBegin($node)', () => _wrapped.forEach_bodyBegin(node));
}
@override
void forEach_end() {
return _wrap('forEach_end()', () => _wrapped.forEach_end());
}
@override
void forwardExpression(Expression newExpression, Expression oldExpression) {
return _wrap('forwardExpression($newExpression, $oldExpression)',
() => _wrapped.forwardExpression(newExpression, oldExpression));
}
@override
void functionExpression_begin(Node node) {
_wrap('functionExpression_begin($node)',
() => _wrapped.functionExpression_begin(node));
}
@override
void functionExpression_end() {
_wrap('functionExpression_end()', () => _wrapped.functionExpression_end());
}
@override
void handleBreak(Statement target) {
_wrap('handleBreak($target)', () => _wrapped.handleBreak(target));
}
@override
void handleContinue(Statement target) {
_wrap('handleContinue($target)', () => _wrapped.handleContinue(target));
}
@override
void handleExit() {
_wrap('handleExit()', () => _wrapped.handleExit());
}
@override
void ifNullExpression_end() {
return _wrap(
'ifNullExpression_end()', () => _wrapped.ifNullExpression_end());
}
@override
void ifNullExpression_rightBegin(
Expression leftHandSide, Type leftHandSideType) {
_wrap(
'ifNullExpression_rightBegin($leftHandSide, $leftHandSideType)',
() => _wrapped.ifNullExpression_rightBegin(
leftHandSide, leftHandSideType));
}
@override
void ifStatement_conditionBegin() {
return _wrap('ifStatement_conditionBegin()',
() => _wrapped.ifStatement_conditionBegin());
}
@override
void ifStatement_elseBegin() {
return _wrap(
'ifStatement_elseBegin()', () => _wrapped.ifStatement_elseBegin());
}
@override
void ifStatement_end(bool hasElse) {
_wrap('ifStatement_end($hasElse)', () => _wrapped.ifStatement_end(hasElse));
}
@override
void ifStatement_thenBegin(Expression condition, Node ifNode) {
_wrap('ifStatement_thenBegin($condition, $ifNode)',
() => _wrapped.ifStatement_thenBegin(condition, ifNode));
}
@override
void initialize(
Variable variable, Type initializerType, Expression initializerExpression,
{required bool isFinal,
required bool isLate,
required bool isImplicitlyTyped}) {
_wrap(
'initialize($variable, $initializerType, $initializerExpression, '
'isFinal: $isFinal, isLate: $isLate, '
'isImplicitlyTyped: $isImplicitlyTyped)',
() => _wrapped.initialize(
variable, initializerType, initializerExpression,
isFinal: isFinal,
isLate: isLate,
isImplicitlyTyped: isImplicitlyTyped));
}
@override
bool isAssigned(Variable variable) {
return _wrap('isAssigned($variable)', () => _wrapped.isAssigned(variable),
isQuery: true);
}
@override
void isExpression_end(Expression isExpression, Expression subExpression,
bool isNot, Type type) {
_wrap(
'isExpression_end($isExpression, $subExpression, $isNot, $type)',
() => _wrapped.isExpression_end(
isExpression, subExpression, isNot, type));
}
@override
bool isUnassigned(Variable variable) {
return _wrap(
'isUnassigned($variable)', () => _wrapped.isUnassigned(variable),
isQuery: true);
}
@override
void labeledStatement_begin(Statement node) {
return _wrap('labeledStatement_begin($node)',
() => _wrapped.labeledStatement_begin(node));
}
@override
void labeledStatement_end() {
return _wrap(
'labeledStatement_end()', () => _wrapped.labeledStatement_end());
}
@override
void lateInitializer_begin(Node node) {
_wrap('lateInitializer_begin($node)',
() => _wrapped.lateInitializer_begin(node));
}
@override
void lateInitializer_end() {
_wrap('lateInitializer_end()', () => _wrapped.lateInitializer_end());
}
@override
void logicalBinaryOp_begin() {
_wrap('logicalBinaryOp_begin()', () => _wrapped.logicalBinaryOp_begin());
}
@override
void logicalBinaryOp_end(Expression wholeExpression, Expression rightOperand,
{required bool isAnd}) {
_wrap(
'logicalBinaryOp_end($wholeExpression, $rightOperand, isAnd: $isAnd)',
() => _wrapped.logicalBinaryOp_end(wholeExpression, rightOperand,
isAnd: isAnd));
}
@override
void logicalBinaryOp_rightBegin(Expression leftOperand, Node wholeExpression,
{required bool isAnd}) {
_wrap(
'logicalBinaryOp_rightBegin($leftOperand, $wholeExpression, '
'isAnd: $isAnd)',
() => _wrapped.logicalBinaryOp_rightBegin(leftOperand, wholeExpression,
isAnd: isAnd));
}
@override
void logicalNot_end(Expression notExpression, Expression operand) {
return _wrap('logicalNot_end($notExpression, $operand)',
() => _wrapped.logicalNot_end(notExpression, operand));
}
@override
void nonNullAssert_end(Expression operand) {
return _wrap('nonNullAssert_end($operand)',
() => _wrapped.nonNullAssert_end(operand));
}
@override
void nullAwareAccess_end() {
_wrap('nullAwareAccess_end()', () => _wrapped.nullAwareAccess_end());
}
@override
void nullAwareAccess_rightBegin(Expression? target, Type targetType) {
_wrap('nullAwareAccess_rightBegin($target, $targetType)',
() => _wrapped.nullAwareAccess_rightBegin(target, targetType));
}
@override
void nullLiteral(Expression expression) {
_wrap('nullLiteral($expression)', () => _wrapped.nullLiteral(expression));
}
@override
void parenthesizedExpression(
Expression outerExpression, Expression innerExpression) {
_wrap(
'parenthesizedExpression($outerExpression, $innerExpression)',
() =>
_wrapped.parenthesizedExpression(outerExpression, innerExpression));
}
@override
Type? promotedType(Variable variable) {
return _wrap(
'promotedType($variable)', () => _wrapped.promotedType(variable),
isQuery: true);
}
@override
void propertyGet(Expression wholeExpression, Expression target,
String propertyName, Object? propertyMember, Type staticType) {
_wrap(
'propertyGet($wholeExpression, $target, $propertyName, '
'$propertyMember, $staticType)',
() => _wrapped.propertyGet(
wholeExpression, target, propertyName, propertyMember, staticType));
}
@override
SsaNode<Type>? ssaNodeForTesting(Variable variable) {
return _wrap('ssaNodeForTesting($variable)',
() => _wrapped.ssaNodeForTesting(variable),
isQuery: true);
}
@override
void switchStatement_beginCase(bool hasLabel, Node node) {
_wrap('switchStatement_beginCase($hasLabel, $node)',
() => _wrapped.switchStatement_beginCase(hasLabel, node));
}
@override
void switchStatement_end(bool isExhaustive) {
_wrap('switchStatement_end($isExhaustive)',
() => _wrapped.switchStatement_end(isExhaustive));
}
@override
void switchStatement_expressionEnd(Statement switchStatement) {
_wrap('switchStatement_expressionEnd($switchStatement)',
() => _wrapped.switchStatement_expressionEnd(switchStatement));
}
@override
void thisOrSuper(Expression expression, Type staticType) {
return _wrap('thisOrSuper($expression, $staticType)',
() => _wrapped.thisOrSuper(expression, staticType));
}
@override
void thisOrSuperPropertyGet(Expression expression, String propertyName,
Object? propertyMember, Type staticType) {
_wrap(
'thisOrSuperPropertyGet($expression, $propertyName, $propertyMember, '
'$staticType)',
() => _wrapped.thisOrSuperPropertyGet(
expression, propertyName, propertyMember, staticType));
}
@override
void tryCatchStatement_bodyBegin() {
return _wrap('tryCatchStatement_bodyBegin()',
() => _wrapped.tryCatchStatement_bodyBegin());
}
@override
void tryCatchStatement_bodyEnd(Node body) {
return _wrap('tryCatchStatement_bodyEnd($body)',
() => _wrapped.tryCatchStatement_bodyEnd(body));
}
@override
void tryCatchStatement_catchBegin(
Variable? exceptionVariable, Variable? stackTraceVariable) {
return _wrap(
'tryCatchStatement_catchBegin($exceptionVariable, $stackTraceVariable)',
() => _wrapped.tryCatchStatement_catchBegin(
exceptionVariable, stackTraceVariable));
}
@override
void tryCatchStatement_catchEnd() {
return _wrap('tryCatchStatement_catchEnd()',
() => _wrapped.tryCatchStatement_catchEnd());
}
@override
void tryCatchStatement_end() {
return _wrap(
'tryCatchStatement_end()', () => _wrapped.tryCatchStatement_end());
}
@override
void tryFinallyStatement_bodyBegin() {
return _wrap('tryFinallyStatement_bodyBegin()',
() => _wrapped.tryFinallyStatement_bodyBegin());
}
@override
void tryFinallyStatement_end() {
return _wrap(
'tryFinallyStatement_end()', () => _wrapped.tryFinallyStatement_end());
}
@override
void tryFinallyStatement_finallyBegin(Node body) {
return _wrap('tryFinallyStatement_finallyBegin($body)',
() => _wrapped.tryFinallyStatement_finallyBegin(body));
}
@override
Type? variableRead(Expression expression, Variable variable) {
return _wrap('variableRead($expression, $variable)',
() => _wrapped.variableRead(expression, variable),
isQuery: true, isPure: false);
}
@override
void whileStatement_bodyBegin(
Statement whileStatement, Expression condition) {
return _wrap('whileStatement_bodyBegin($whileStatement, $condition)',
() => _wrapped.whileStatement_bodyBegin(whileStatement, condition));
}
@override
void whileStatement_conditionBegin(Node node) {
return _wrap('whileStatement_conditionBegin($node)',
() => _wrapped.whileStatement_conditionBegin(node));
}
@override
void whileStatement_end() {
return _wrap('whileStatement_end()', () => _wrapped.whileStatement_end());
}
@override
Map<Type, NonPromotionReason> Function() whyNotPromoted(Expression target) {
return _wrap('whyNotPromoted($target)',
() => _trackWhyNotPromoted(_wrapped.whyNotPromoted(target)),
isQuery: true);
}
@override
Map<Type, NonPromotionReason> Function() whyNotPromotedImplicitThis(
Type staticType) {
return _wrap(
'whyNotPromotedImplicitThis($staticType)',
() => _trackWhyNotPromoted(
_wrapped.whyNotPromotedImplicitThis(staticType)),
isQuery: true);
}
@override
void write(Node node, Variable variable, Type writtenType,
Expression? writtenExpression) {
_wrap('write($node, $variable, $writtenType, $writtenExpression)',
() => _wrapped.write(node, variable, writtenType, writtenExpression));
}
@override
void _dumpState() => _wrapped._dumpState();
/// Wraps [callback] so that when it is called, the call (and its return
/// value) will be printed to the console. Also registers the wrapped
/// callback in [_description] so that it will be given a unique identifier
/// when printed to the console.
Map<Type, NonPromotionReason> Function() _trackWhyNotPromoted(
Map<Type, NonPromotionReason> Function() callback) {
String callbackToString = '#CALLBACK${_nextCallbackId++}';
Map<Type, NonPromotionReason> Function() wrappedCallback =
() => _wrap('$callbackToString()', callback, isQuery: true);
_description[wrappedCallback] = callbackToString;
return wrappedCallback;
}
T _wrap<T>(String description, T callback(),
{bool isQuery: false, bool? isPure}) {
isPure ??= isQuery;
print(description);
T result;
try {
result = callback();
} catch (e, st) {
print(' => EXCEPTION $e');
print(' ' + st.toString().replaceAll('\n', '\n '));
_exceptionOccurred = true;
rethrow;
}
if (!isPure) {
_wrapped._dumpState();
}
if (isQuery) {
print(' => ${_describe(result)}');
}
return result;
}
static String _describe(Object? value) {
if (value != null && value is! String && value is! num && value is! bool) {
String? description = _description[value];
if (description != null) return description;
}
return value.toString();
}
}
/// An instance of the [FlowModel] class represents the information gathered by
/// flow analysis at a single point in the control flow of the function or
/// method being analyzed.
///
/// Instances of this class are immutable, so the methods below that "update"
/// the state actually leave `this` unchanged and return a new state object.
@visibleForTesting
class FlowModel<Type extends Object> {
final Reachability reachable;
/// For each promotable thing being tracked by flow analysis, the
/// corresponding model.
///
/// Flow analysis has no awareness of scope, so variables that are out of
/// scope are retained in the map until such time as their declaration no
/// longer dominates the control flow. So, for example, if a variable is
/// declared inside the `then` branch of an `if` statement, and the `else`
/// branch of the `if` statement ends in a `return` statement, then the
/// variable remains in the map after the `if` statement ends, even though the
/// variable is not in scope anymore. This should not have any effect on
/// analysis results for error-free code, because it is an error to refer to a
/// variable that is no longer in scope.
///
/// Keys are the unique integers assigned by
/// [_FlowAnalysisImpl._promotionKeyStore].
final Map<int, VariableModel<Type> /*!*/ > variableInfo;
/// The empty map, used to [join] variables.
final Map<int, VariableModel<Type>> _emptyVariableMap = {};
/// Creates a state object with the given [reachable] status. All variables
/// are assumed to be unpromoted and already assigned, so joining another
/// state with this one will have no effect on it.
FlowModel(Reachability reachable)
: this.withInfo(
reachable,
const {},
);
@visibleForTesting
FlowModel.withInfo(this.reachable, this.variableInfo) {
// ignore:unnecessary_null_comparison
assert(reachable != null);
assert(() {
for (VariableModel<Type> value in variableInfo.values) {
// ignore:unnecessary_null_comparison
assert(value != null);
}
return true;
}());
}
/// Computes the effect of executing a try/finally's `try` and `finally`
/// blocks in sequence. `this` is the flow analysis state from the end of the
/// `try` block; [beforeFinally] and [afterFinally] are the flow analysis
/// states from the top and bottom of the `finally` block, respectively.
///
/// Initially the `finally` block is analyzed under the conservative
/// assumption that the `try` block might have been interrupted at any point
/// by an exception occurring, therefore no variable assignments or promotions
/// that occurred in the `try` block can be relied upon. As a result, when we
/// get to the end of processing the `finally` block, the only promotions and
/// variable assignments accounted for by flow analysis are the ones performed
/// within the `finally` block itself. However, when we analyze code that
/// follows the `finally` block, we know that the `try` block did *not* throw
/// an exception, so we want to reinstate the results of any promotions and
/// assignments that occurred during the `try` block, to the extent that they
/// weren't invalidated by later assignments in the `finally` block.
FlowModel<Type> attachFinally(TypeOperations<Type> typeOperations,
FlowModel<Type> beforeFinally, FlowModel<Type> afterFinally) {
// Code that follows the `try/finally` is reachable iff the end of the `try`
// block is reachable _and_ the end of the `finally` block is reachable.
Reachability newReachable = afterFinally.reachable.rebaseForward(reachable);
// Consider each variable that is common to all three models.
Map<int, VariableModel<Type>> newVariableInfo =
<int, VariableModel<Type>>{};
bool variableInfoMatchesThis = true;
bool variableInfoMatchesAfterFinally = true;
for (MapEntry<int, VariableModel<Type>> entry in variableInfo.entries) {
int promotionKey = entry.key;
VariableModel<Type> thisModel = entry.value;
VariableModel<Type>? beforeFinallyModel =
beforeFinally.variableInfo[promotionKey];
VariableModel<Type>? afterFinallyModel =
afterFinally.variableInfo[promotionKey];
if (beforeFinallyModel == null || afterFinallyModel == null) {
// The variable is in `this` model but not in one of the `finally`
// models. This happens when the variable is declared inside the `try`
// block. We can just drop the variable because it won't be in scope
// after the try/finally statement.
variableInfoMatchesThis = false;
continue;
}
// We can just use the "write captured" state from the `finally` block,
// because any write captures in the `try` block are conservatively
// considered to take effect in the `finally` block too.
List<Type>? newPromotedTypes;
SsaNode<Type>? newSsaNode;
if (beforeFinallyModel.ssaNode == afterFinallyModel.ssaNode) {
// The finally clause doesn't write to the variable, so we want to keep
// all promotions that were done to it in both the try and finally
// blocks.
newPromotedTypes = VariableModel.rebasePromotedTypes(typeOperations,
thisModel.promotedTypes, afterFinallyModel.promotedTypes);
// And we can safely restore the SSA node from the end of the try block.
newSsaNode = thisModel.ssaNode;
} else {
// A write to the variable occurred in the finally block, so promotions
// from the try block aren't necessarily valid.
newPromotedTypes = afterFinallyModel.promotedTypes;
// And we can't safely restore the SSA node from the end of the try
// block; we need to keep the one from the end of the finally block.
newSsaNode = afterFinallyModel.ssaNode;
}
// The `finally` block inherited all tests from the `try` block so we can
// just inherit tests from it.
List<Type> newTested = afterFinallyModel.tested;
// The variable is definitely assigned if it was definitely assigned in
// either the `try` or the `finally` block.
bool newAssigned = thisModel.assigned || afterFinallyModel.assigned;
// The `finally` block inherited the "unassigned" state from the `try`
// block so we can just inherit from it.
bool newUnassigned = afterFinallyModel.unassigned;
VariableModel<Type> newModel = VariableModel._identicalOrNew(
thisModel,
afterFinallyModel,
newPromotedTypes,
newTested,
newAssigned,
newUnassigned,
newSsaNode);
newVariableInfo[promotionKey] = newModel;
if (!identical(newModel, thisModel)) variableInfoMatchesThis = false;
if (!identical(newModel, afterFinallyModel)) {
variableInfoMatchesAfterFinally = false;
}
}
// newVariableInfo is now correct. However, if there are any variables
// present in `afterFinally` that aren't present in `this`, we may
// erroneously think that `newVariableInfo` matches `afterFinally`. If so,
// correct that.
if (variableInfoMatchesAfterFinally) {
for (int promotionKey in afterFinally.variableInfo.keys) {
if (!variableInfo.containsKey(promotionKey)) {
variableInfoMatchesAfterFinally = false;
break;
}
}
}
assert(variableInfoMatchesThis ==
_variableInfosEqual(newVariableInfo, variableInfo));
assert(variableInfoMatchesAfterFinally ==
_variableInfosEqual(newVariableInfo, afterFinally.variableInfo));
if (variableInfoMatchesThis) {
newVariableInfo = variableInfo;
} else if (variableInfoMatchesAfterFinally) {
newVariableInfo = afterFinally.variableInfo;
}
return _identicalOrNew(this, afterFinally, newReachable, newVariableInfo);
}
/// Updates the state to indicate that the given [writtenVariables] are no
/// longer promoted and are no longer definitely unassigned, and the given
/// [capturedVariables] have been captured by closures.
///
/// This is used at the top of loops to conservatively cancel the promotion of
/// variables that are modified within the loop, so that we correctly analyze
/// code like the following:
///
/// if (x is int) {
/// x.isEven; // OK, promoted to int
/// while (true) {
/// x.isEven; // ERROR: promotion lost
/// x = 'foo';
/// }
/// }
///
/// Note that a more accurate analysis would be to iterate to a fixed point,
/// and only remove promotions if it can be shown that they aren't restored
/// later in the loop body. If we switch to a fixed point analysis, we should
/// be able to remove this method.
FlowModel<Type> conservativeJoin(
Iterable<int> writtenVariables, Iterable<int> capturedVariables) {
Map<int, VariableModel<Type>>? newVariableInfo;
for (int variableKey in writtenVariables) {
VariableModel<Type>? info = variableInfo[variableKey];
if (info == null) continue;
VariableModel<Type> newInfo =
info.discardPromotionsAndMarkNotUnassigned();
if (!identical(info, newInfo)) {
(newVariableInfo ??= new Map<int, VariableModel<Type>>.of(
variableInfo))[variableKey] = newInfo;
}
}
for (int variableKey in capturedVariables) {
VariableModel<Type>? info = variableInfo[variableKey];
if (info == null) continue;
if (!info.writeCaptured) {
(newVariableInfo ??= new Map<int, VariableModel<Type>>.of(
variableInfo))[variableKey] = info.writeCapture();
}
}
FlowModel<Type> result = newVariableInfo == null
? this
: new FlowModel<Type>.withInfo(reachable, newVariableInfo);
return result;
}
/// Register a declaration of the variable whose key is [variableKey].
/// Should also be called for function parameters.
///
/// A local variable is [initialized] if its declaration has an initializer.
/// A function parameter is always initialized, so [initialized] is `true`.
FlowModel<Type> declare(int variableKey, bool initialized) {
VariableModel<Type> newInfoForVar =
new VariableModel.fresh(assigned: initialized);
return _updateVariableInfo(variableKey, newInfoForVar);
}
/// Gets the info for the given [promotionKey], creating it if it doesn't
/// exist.
VariableModel<Type> infoFor(int promotionKey) =>
variableInfo[promotionKey] ?? new VariableModel.fresh();
/// Builds a [FlowModel] based on `this`, but extending the `tested` set to
/// include types from [other]. This is used at the bottom of certain kinds
/// of loops, to ensure that types tested within the body of the loop are
/// consistently treated as "of interest" in code that follows the loop,
/// regardless of the type of loop.
@visibleForTesting
FlowModel<Type> inheritTested(
TypeOperations<Type> typeOperations, FlowModel<Type> other) {
Map<int, VariableModel<Type>> newVariableInfo =
<int, VariableModel<Type>>{};
Map<int, VariableModel<Type>> otherVariableInfo = other.variableInfo;
bool changed = false;
for (MapEntry<int, VariableModel<Type>> entry in variableInfo.entries) {
int promotionKey = entry.key;
VariableModel<Type> variableModel = entry.value;
VariableModel<Type>? otherVariableModel = otherVariableInfo[promotionKey];
VariableModel<Type> newVariableModel = otherVariableModel == null
? variableModel
: VariableModel.inheritTested(
typeOperations, variableModel, otherVariableModel.tested);
newVariableInfo[promotionKey] = newVariableModel;
if (!identical(newVariableModel, variableModel)) changed = true;
}
if (changed) {
return new FlowModel<Type>.withInfo(reachable, newVariableInfo);
} else {
return this;
}
}
/// Updates `this` flow model to account for any promotions and assignments
/// present in [base].
///
/// This is called "rebasing" the flow model by analogy to "git rebase"; in
/// effect, it rewinds any flow analysis state present in `this` but not in
/// the history of [base], and then reapplies that state using [base] as a
/// starting point, to the extent possible without creating unsoundness. For
/// example, if a variable is promoted in `this` but not in [base], then it
/// will be promoted in the output model, provided that hasn't been reassigned
/// since then (which would make the promotion unsound).
FlowModel<Type> rebaseForward(
TypeOperations<Type> typeOperations, FlowModel<Type> base) {
// The rebased model is reachable iff both `this` and the new base are
// reachable.
Reachability newReachable = reachable.rebaseForward(base.reachable);
// Consider each variable in the new base model.
Map<int, VariableModel<Type>> newVariableInfo =
<int, VariableModel<Type>>{};
bool variableInfoMatchesThis = true;
bool variableInfoMatchesBase = true;
for (MapEntry<int, VariableModel<Type>> entry
in base.variableInfo.entries) {
int promotionKey = entry.key;
VariableModel<Type> baseModel = entry.value;
VariableModel<Type>? thisModel = variableInfo[promotionKey];
if (thisModel == null) {
// The variable has newly came into scope since `thisModel`, so the
// information in `baseModel` is up to date.
newVariableInfo[promotionKey] = baseModel;
variableInfoMatchesThis = false;
continue;
}
// If the variable was write captured in either `this` or the new base,
// it's captured now.
bool newWriteCaptured =
thisModel.writeCaptured || baseModel.writeCaptured;
List<Type>? newPromotedTypes;
if (newWriteCaptured) {
// Write captured variables can't be promoted.
newPromotedTypes = null;
} else if (baseModel.ssaNode != thisModel.ssaNode) {
// The variable may have been written to since `thisModel`, so we can't
// use any of the promotions from `thisModel`.
newPromotedTypes = baseModel.promotedTypes;
} else {
// The variable hasn't been written to since `thisModel`, so we can keep
// all of the promotions from `thisModel`, provided that we retain the
// usual "promotion chain" invariant (each promoted type is a subtype of
// the previous).
newPromotedTypes = VariableModel.rebasePromotedTypes(
typeOperations, thisModel.promotedTypes, baseModel.promotedTypes);
}
// Tests are kept regardless of whether they are in `this` model or the
// new base model.
List<Type> newTested = VariableModel.joinTested(
thisModel.tested, baseModel.tested, typeOperations);
// The variable is definitely assigned if it was definitely assigned
// either in `this` model or the new base model.
bool newAssigned = thisModel.assigned || baseModel.assigned;
// The variable is definitely unassigned if it was definitely unassigned
// in both `this` model and the new base model.
bool newUnassigned = thisModel.unassigned && baseModel.unassigned;
VariableModel<Type> newModel = VariableModel._identicalOrNew(
thisModel,
baseModel,
newPromotedTypes,
newTested,
newAssigned,
newUnassigned,
newWriteCaptured ? null : baseModel.ssaNode);
newVariableInfo[promotionKey] = newModel;
if (!identical(newModel, thisModel)) variableInfoMatchesThis = false;
if (!identical(newModel, baseModel)) variableInfoMatchesBase = false;
}
// newVariableInfo is now correct. However, if there are any variables
// present in `this` that aren't present in `base`, we may erroneously think
// that `newVariableInfo` matches `this`. If so, correct that.
if (variableInfoMatchesThis) {
for (int promotionKey in variableInfo.keys) {
if (!base.variableInfo.containsKey(promotionKey)) {
variableInfoMatchesThis = false;
break;
}
}
}
assert(variableInfoMatchesThis ==
_variableInfosEqual(newVariableInfo, variableInfo));
assert(variableInfoMatchesBase ==
_variableInfosEqual(newVariableInfo, base.variableInfo));
if (variableInfoMatchesThis) {
newVariableInfo = variableInfo;
} else if (variableInfoMatchesBase) {
newVariableInfo = base.variableInfo;
}
return _identicalOrNew(this, base, newReachable, newVariableInfo);
}
/// Updates the state to indicate that the control flow path is unreachable.
FlowModel<Type> setUnreachable() {
if (!reachable.locallyReachable) return this;
return new FlowModel<Type>.withInfo(
reachable.setUnreachable(), variableInfo);
}
/// Returns a [FlowModel] indicating the result of creating a control flow
/// split. See [Reachability.split] for more information.
FlowModel<Type> split() =>
new FlowModel<Type>.withInfo(reachable.split(), variableInfo);
@override
String toString() => '($reachable, $variableInfo)';
/// Returns an [ExpressionInfo] indicating the result of checking whether the
/// given [reference] is non-null.
///
/// Note that the state is only changed if the previous type of [variable] was
/// potentially nullable.
ExpressionInfo<Type> tryMarkNonNullable(
TypeOperations<Type> typeOperations,
ReferenceWithType<Type> referenceWithType,
PromotionKeyStore<Object> promotionKeyStore) {
VariableModel<Type> info = _getInfo(referenceWithType.promotionKey);
if (info.writeCaptured) {
return new _TrivialExpressionInfo<Type>(this);
}
Type previousType = referenceWithType.type;
Type newType = typeOperations.promoteToNonNull(previousType);
if (typeOperations.isSameType(newType, previousType)) {
return new _TrivialExpressionInfo<Type>(this);
}
assert(typeOperations.isSubtypeOf(newType, previousType));
FlowModel<Type> ifTrue = _finishTypeTest(typeOperations, referenceWithType,
info, null, newType, promotionKeyStore);
return new ExpressionInfo<Type>(after: this, ifTrue: ifTrue, ifFalse: this);
}
/// Returns an [ExpressionInfo] indicating the result of casting the given
/// [referenceWithType] to the given [type], as a consequence of an `as`
/// expression.
///
/// Note that the state is only changed if [type] is a subtype of the
/// variable's previous (possibly promoted) type.
///
/// TODO(paulberry): if the type is non-nullable, should this method mark the
/// variable as definitely assigned? Does it matter?
FlowModel<Type> tryPromoteForTypeCast(
TypeOperations<Type> typeOperations,
ReferenceWithType<Type> referenceWithType,
Type type,
PromotionKeyStore<Object> promotionKeyStore) {
VariableModel<Type> info = _getInfo(referenceWithType.promotionKey);
if (info.writeCaptured) {
return this;
}
Type previousType = referenceWithType.type;
Type? newType = typeOperations.tryPromoteToType(type, previousType);
if (newType == null || typeOperations.isSameType(newType, previousType)) {
return this;
}
assert(typeOperations.isSubtypeOf(newType, previousType),
"Expected $newType to be a subtype of $previousType.");
return _finishTypeTest(typeOperations, referenceWithType, info, type,
newType, promotionKeyStore);
}
/// Returns an [ExpressionInfo] indicating the result of checking whether the
/// given [reference] satisfies the given [type], e.g. as a consequence of an
/// `is` expression as the condition of an `if` statement.
///
/// Note that the "ifTrue" state is only changed if [type] is a subtype of
/// the variable's previous (possibly promoted) type.
///
/// TODO(paulberry): if the type is non-nullable, should this method mark the
/// variable as definitely assigned? Does it matter?
ExpressionInfo<Type> tryPromoteForTypeCheck(
TypeOperations<Type> typeOperations,
ReferenceWithType<Type> referenceWithType,
Type type,
PromotionKeyStore<Object> promotionKeyStore) {
VariableModel<Type> info = _getInfo(referenceWithType.promotionKey);
if (info.writeCaptured) {
return new _TrivialExpressionInfo<Type>(this);
}
Type previousType = referenceWithType.type;
FlowModel<Type> ifTrue = this;
Type? typeIfSuccess = typeOperations.tryPromoteToType(type, previousType);
if (typeIfSuccess != null &&
!typeOperations.isSameType(typeIfSuccess, previousType)) {
assert(typeOperations.isSubtypeOf(typeIfSuccess, previousType),
"Expected $typeIfSuccess to be a subtype of $previousType.");
ifTrue = _finishTypeTest(typeOperations, referenceWithType, info, type,
typeIfSuccess, promotionKeyStore);
}
Type factoredType = typeOperations.factor(previousType, type);
Type? typeIfFalse;
if (typeOperations.isNever(factoredType)) {
// Promoting to `Never` would mark the code as unreachable. But it might
// be reachable due to mixed mode unsoundness. So don't promote.
typeIfFalse = null;
} else if (typeOperations.isSameType(factoredType, previousType)) {
// No change to the type, so don't promote.
typeIfFalse = null;
} else {
typeIfFalse = factoredType;
}
FlowModel<Type> ifFalse = _finishTypeTest(typeOperations, referenceWithType,
info, type, typeIfFalse, promotionKeyStore);
return new ExpressionInfo<Type>(
after: this, ifTrue: ifTrue, ifFalse: ifFalse);
}
/// Returns a [FlowModel] indicating the result of removing a control flow
/// split. See [Reachability.unsplit] for more information.
FlowModel<Type> unsplit() =>
new FlowModel<Type>.withInfo(reachable.unsplit(), variableInfo);
/// Removes control flow splits until a [FlowModel] is obtained whose
/// reachability has the given [parent].
FlowModel<Type> unsplitTo(Reachability parent) {
if (identical(this.reachable.parent, parent)) return this;
Reachability reachable = this.reachable.unsplit();
while (!identical(reachable.parent, parent)) {
reachable = reachable.unsplit();
}
return new FlowModel<Type>.withInfo(reachable, variableInfo);
}
/// Updates the state to indicate that an assignment was made to [variable],
/// whose key is [variableKey]. The variable is marked as definitely
/// assigned, and any previous type promotion is removed.
///
/// If there is any chance that the write will cause a demotion, the caller
/// must pass in a non-null value for [nonPromotionReason] describing the
/// reason for any potential demotion.
FlowModel<Type> write<Variable extends Object>(
NonPromotionReason? nonPromotionReason,
Variable variable,
int variableKey,
Type writtenType,
SsaNode<Type> newSsaNode,
Operations<Variable, Type> operations,
{bool promoteToTypeOfInterest = true}) {
VariableModel<Type>? infoForVar = variableInfo[variableKey];
if (infoForVar == null) return this;
VariableModel<Type> newInfoForVar = infoForVar.write(nonPromotionReason,
variable, variableKey, writtenType, operations, newSsaNode,
promoteToTypeOfInterest: promoteToTypeOfInterest);
if (identical(newInfoForVar, infoForVar)) return this;
return _updateVariableInfo(variableKey, newInfoForVar);
}
/// Common algorithm for [tryMarkNonNullable], [tryPromoteForTypeCast],
/// and [tryPromoteForTypeCheck]. Builds a [FlowModel] object describing the
/// effect of updating the [reference] by adding the [testedType] to the
/// list of tested types (if not `null`, and not there already), adding the
/// [promotedType] to the chain of promoted types.
///
/// Preconditions:
/// - [info] should be the result of calling `infoFor(variable)`
/// - [promotedType] should be a subtype of the currently-promoted type (i.e.
/// no redundant or side-promotions)
/// - The variable should not be write-captured.
FlowModel<Type> _finishTypeTest(
TypeOperations<Type> typeOperations,
ReferenceWithType<Type> reference,
VariableModel<Type> info,
Type? testedType,
Type? promotedType,
PromotionKeyStore<Object> promotionKeyStore) {
List<Type> newTested = info.tested;
if (testedType != null) {
newTested = VariableModel._addTypeToUniqueList(
info.tested, testedType, typeOperations);
}
List<Type>? newPromotedTypes = info.promotedTypes;
Reachability newReachable = reachable;
if (promotedType != null) {
newPromotedTypes =
VariableModel._addToPromotedTypes(info.promotedTypes, promotedType);
if (reference.isPromotable(promotionKeyStore) &&
typeOperations.isNever(promotedType)) {
newReachable = reachable.setUnreachable();
}
}
return identical(newTested, info.tested) &&
identical(newPromotedTypes, info.promotedTypes) &&
newReachable == reachable
? this
: _updateVariableInfo(
reference.promotionKey,
new VariableModel<Type>(
promotedTypes: newPromotedTypes,
tested: newTested,
assigned: info.assigned,
unassigned: info.unassigned,
ssaNode: info.ssaNode,
nonPromotionHistory: info.nonPromotionHistory),
reachable: newReachable);
}
/// Gets the info for [promotionKey] reference, creating it if it doesn't
/// exist.
VariableModel<Type> _getInfo(int promotionKey) =>
variableInfo[promotionKey] ?? new VariableModel<Type>.fresh();
/// Returns a new [FlowModel] where the information for [reference] is
/// replaced with [model].
FlowModel<Type> _updateVariableInfo(
int promotionKey, VariableModel<Type> model,
{Reachability? reachable}) {
reachable ??= this.reachable;
Map<int, VariableModel<Type>> newVariableInfo =
new Map<int, VariableModel<Type>>.of(variableInfo);
newVariableInfo[promotionKey] = model;
return new FlowModel<Type>.withInfo(reachable, newVariableInfo);
}
/// Forms a new state to reflect a control flow path that might have come from
/// either `this` or the [other] state.
///
/// The control flow path is considered reachable if either of the input
/// states is reachable. Variables are considered definitely assigned if they
/// were definitely assigned in both of the input states. Variable promotions
/// are kept only if they are common to both input states; if a variable is
/// promoted to one type in one state and a subtype in the other state, the
/// less specific type promotion is kept.
static FlowModel<Type> join<Type extends Object>(
TypeOperations<Type> typeOperations,
FlowModel<Type>? first,
FlowModel<Type>? second,
Map<int, VariableModel<Type>> emptyVariableMap,
) {
if (first == null) return second!;
if (second == null) return first;
assert(identical(first.reachable.parent, second.reachable.parent));
if (first.reachable.locallyReachable &&
!second.reachable.locallyReachable) {
return first;
}
if (!first.reachable.locallyReachable &&
second.reachable.locallyReachable) {
return second;
}
Reachability newReachable =
Reachability.join(first.reachable, second.reachable);
Map<int, VariableModel<Type>> newVariableInfo = FlowModel.joinVariableInfo(
typeOperations,
first.variableInfo,
second.variableInfo,
emptyVariableMap);
return FlowModel._identicalOrNew(
first, second, newReachable, newVariableInfo);
}
/// Joins two "variable info" maps. See [join] for details.
@visibleForTesting
static Map<int, VariableModel<Type>> joinVariableInfo<Type extends Object>(
TypeOperations<Type> typeOperations,
Map<int, VariableModel<Type>> first,
Map<int, VariableModel<Type>> second,
Map<int, VariableModel<Type>> emptyMap,
) {
if (identical(first, second)) return first;
if (first.isEmpty || second.isEmpty) {
return emptyMap;
}
Map<int, VariableModel<Type>> result = <int, VariableModel<Type>>{};
bool alwaysFirst = true;
bool alwaysSecond = true;
for (MapEntry<int, VariableModel<Type>> entry in first.entries) {
int promotionKey = entry.key;
VariableModel<Type>? secondModel = second[promotionKey];
if (secondModel == null) {
alwaysFirst = false;
} else {
VariableModel<Type> joined =
VariableModel.join<Type>(typeOperations, entry.value, secondModel);
result[promotionKey] = joined;
if (!identical(joined, entry.value)) alwaysFirst = false;
if (!identical(joined, secondModel)) alwaysSecond = false;
}
}
if (alwaysFirst) return first;
if (alwaysSecond && result.length == second.length) return second;
if (result.isEmpty) return emptyMap;
return result;
}
/// Models the result of joining the flow models [first] and [second] at the
/// merge of two control flow paths.
static FlowModel<Type> merge<Type extends Object>(
TypeOperations<Type> typeOperations,
FlowModel<Type>? first,
FlowModel<Type>? second,
Map<int, VariableModel<Type>> emptyVariableMap,
) {
if (first == null) return second!.unsplit();
if (second == null) return first.unsplit();
assert(identical(first.reachable.parent, second.reachable.parent));
if (first.reachable.locallyReachable &&
!second.reachable.locallyReachable) {
return first.unsplit();
}
if (!first.reachable.locallyReachable &&
second.reachable.locallyReachable) {
return second.unsplit();
}
Reachability newReachable =
Reachability.join(first.reachable, second.reachable).unsplit();
Map<int, VariableModel<Type>> newVariableInfo = FlowModel.joinVariableInfo(
typeOperations,
first.variableInfo,
second.variableInfo,
emptyVariableMap);
return FlowModel._identicalOrNew(
first, second, newReachable, newVariableInfo);
}
/// Creates a new [FlowModel] object, unless it is equivalent to either
/// [first] or [second], in which case one of those objects is re-used.
static FlowModel<Type> _identicalOrNew<Type extends Object>(
FlowModel<Type> first,
FlowModel<Type> second,
Reachability newReachable,
Map<int, VariableModel<Type>> newVariableInfo) {
if (first.reachable == newReachable &&
identical(first.variableInfo, newVariableInfo)) {
return first;
}
if (second.reachable == newReachable &&
identical(second.variableInfo, newVariableInfo)) {
return second;
}
return new FlowModel<Type>.withInfo(newReachable, newVariableInfo);
}
/// Determines whether the given "variableInfo" maps are equivalent.
///
/// The equivalence check is shallow; if two variables' models are not
/// identical, we return `false`.
static bool _variableInfosEqual<Type extends Object>(
Map<int, VariableModel<Type>> p1, Map<int, VariableModel<Type>> p2) {
if (p1.length != p2.length) return false;
if (!p1.keys.toSet().containsAll(p2.keys)) return false;
for (MapEntry<int, VariableModel<Type>> entry in p1.entries) {
VariableModel<Type> p1Value = entry.value;
VariableModel<Type>? p2Value = p2[entry.key];
if (!identical(p1Value, p2Value)) {
return false;
}
}
return true;
}
}
/// Linked list node representing a set of reasons why a given expression was
/// not promoted.
///
/// We use a linked list representation because it is very efficient to build;
/// this means that in the "happy path" where no error occurs (so non-promotion
/// history is not needed) we do a minimal amount of work.
class NonPromotionHistory<Type> {
/// The type that was not promoted to.
final Type type;
/// The reason why the promotion didn't occur.
final NonPromotionReason nonPromotionReason;
/// The previous link in the list.
final NonPromotionHistory<Type>? previous;
NonPromotionHistory(this.type, this.nonPromotionReason, this.previous);
@override
String toString() {
List<String> items = <String>[];
for (NonPromotionHistory<Type>? link = this;
link != null;
link = link.previous) {
items.add('${link.type}: ${link.nonPromotionReason}');
}
return items.toString();
}
}
/// Abstract class representing a reason why something was not promoted.
abstract class NonPromotionReason {
/// Link to documentation describing this non-promotion reason; this should be
/// presented to the user as a source of additional information about the
/// error.
String get documentationLink;
/// Short text description of this non-promotion reason; intended for ID
/// testing.
String get shortName;
/// Implementation of the visitor pattern for non-promotion reasons.
R accept<R, Node extends Object, Variable extends Object,
Type extends Object>(
NonPromotionReasonVisitor<R, Node, Variable, Type> visitor);
}
/// Implementation of the visitor pattern for non-promotion reasons.
abstract class NonPromotionReasonVisitor<R, Node extends Object,
Variable extends Object, Type extends Object> {
NonPromotionReasonVisitor._() : assert(false, 'Do not extend this class');
R visitDemoteViaExplicitWrite(DemoteViaExplicitWrite<Variable> reason);
R visitPropertyNotPromoted(PropertyNotPromoted<Type> reason);
R visitThisNotPromoted(ThisNotPromoted reason);
}
/// Operations on types and variables, abstracted from concrete type interfaces.
abstract class Operations<Variable extends Object, Type extends Object>
extends TypeOperations<Type> implements VariableOperations<Variable, Type> {
}
/// This data structure assigns a unique integer identifier to everything that
/// might undergo promotion in the user's code (local variables and properties).
/// An integer identifier is also assigned to `this` (even though `this` is not
/// promotable), because promotable properties can be reached using `this` as a
/// starting point.
@visibleForTesting
class PromotionKeyStore<Variable extends Object> {
@visibleForTesting
/// Special promotion key to represent `this`.
late final int thisPromotionKey = _makeNewKey(null);
final Map<Variable, int> _variableKeys = new Map<Variable, int>.identity();
final List<Variable?> _keyToVariable = [];
/// List of maps indicating the set of properties of each promotable entity
/// being tracked by flow analysis. The list is indexed by the promotion key
/// of the target, and the map is indexed by the property name.
///
/// Null list elements are considered equivalent to an empty map (this allows
/// us so save memory due to the fact that most entries will not be accessed).
final List<Map<String, int>?> _properties = [];
int getProperty(int targetKey, String propertyName) =>
(_properties[targetKey] ??= {})[propertyName] ??= _makeNewKey(null);
@visibleForTesting
int keyForVariable(Variable variable) =>
_variableKeys[variable] ??= _makeNewKey(variable);
@visibleForTesting
Variable? variableForKey(int variableKey) => _keyToVariable[variableKey];
int _makeNewKey(Variable? variable) {
int key = _keyToVariable.length;
_keyToVariable.add(variable);
_properties.add(null);
return key;
}
}
/// Non-promotion reason describing the situation where an expression was not
/// promoted due to the fact that it's a property get.
class PropertyNotPromoted<Type extends Object> extends NonPromotionReason {
/// The name of the property.
final String propertyName;
/// The field or property being accessed. This matches a `propertyMember`
/// value that was passed to either [FlowAnalysis.propertyGet] or
/// [FlowAnalysis.thisOrSuperPropertyGet].
final Object? propertyMember;
/// The static type of the property at the time of the access. This is the
/// type that was passed to [FlowAnalysis.whyNotPromoted]; it is provided to
/// the client as a convenience for ID testing.
final Type staticType;
PropertyNotPromoted(this.propertyName, this.propertyMember, this.staticType);
@override
String get documentationLink => 'http://dart.dev/go/non-promo-property';
@override
String get shortName => 'propertyNotPromoted';
@override
R accept<R, Node extends Object, Variable extends Object,
Type extends Object>(
NonPromotionReasonVisitor<R, Node, Variable, Type> visitor) =>
visitor.visitPropertyNotPromoted(this as PropertyNotPromoted<Type>);
}
/// Immutable data structure modeling the reachability of the given point in the
/// source code. Reachability is tracked relative to checkpoints occurring
/// previously along the control flow path leading up to the current point in
/// the program. A given point is said to be "locally reachable" if it is
/// reachable from the most recent checkpoint, and "overall reachable" if it is
/// reachable from the top of the function.
@visibleForTesting
class Reachability {
/// Model of the initial reachability state of the function being analyzed.
static const Reachability initial = const Reachability._initial();
/// Reachability of the checkpoint this reachability is relative to, or `null`
/// if there is no checkpoint. Reachabilities form a tree structure that
/// mimics the control flow of the code being analyzed, so this is called the
/// "parent".
final Reachability? parent;
/// Whether this point in the source code is considered reachable from the
/// most recent checkpoint.
final bool locallyReachable;
/// Whether this point in the source code is considered reachable from the
/// beginning of the function being analyzed.
final bool overallReachable;
/// The number of `parent` links between this node and [initial].
final int depth;
Reachability._(this.parent, this.locallyReachable, this.overallReachable)
: depth = parent == null ? 0 : parent.depth + 1 {
assert(overallReachable ==
(locallyReachable && (parent?.overallReachable ?? true)));
}
const Reachability._initial()
: parent = null,
locallyReachable = true,
overallReachable = true,
depth = 0;
/// Updates `this` reachability to account for the reachability of [base].
///
/// This is the reachability component of the algorithm in
/// [FlowModel.rebaseForward].
Reachability rebaseForward(Reachability base) {
// If [base] is not reachable, then the result is not reachable.
if (!base.locallyReachable) return base;
// If any of the reachability nodes between `this` and its common ancestor
// with [base] are locally unreachable, that means that there was an exit in
// the flow control path from the point at which `this` and [base] diverged
// up to the current point of `this`; therefore we want to mark [base] as
// unreachable.
Reachability? ancestor = commonAncestor(this, base);
for (Reachability? self = this;
self != null && !identical(self, ancestor);
self = self.parent) {
if (!self.locallyReachable) return base.setUnreachable();
}
// Otherwise, the result is as reachable as [base] was.
return base;
}
/// Returns a reachability with the same checkpoint as `this`, but where the
/// current point in the program is considered locally unreachable.
Reachability setUnreachable() {
if (!locallyReachable) return this;
return new Reachability._(parent, false, false);
}
/// Returns a new reachability whose checkpoint is the current point of
/// execution. This models flow control within a control flow split, e.g.
/// inside an `if` statement.
Reachability split() => new Reachability._(this, true, overallReachable);
@override
String toString() {
List<bool> values = [];
for (Reachability? node = this; node != null; node = node.parent) {
values.add(node.locallyReachable);
}
return '[${values.join(', ')}]';
}
/// Returns a reachability that drops the most recent checkpoint but maintains
/// the same notion of reachability relative to the previous two checkpoints.
Reachability unsplit() {
if (locallyReachable) {
return parent!;
} else {
return parent!.setUnreachable();
}
}
/// Finds the common ancestor node of [r1] and [r2], if any such node exists;
/// otherwise `null`. If [r1] and [r2] are the same node, that node is
/// returned.
static Reachability? commonAncestor(Reachability? r1, Reachability? r2) {
if (r1 == null || r2 == null) return null;
while (r1!.depth > r2.depth) {
r1 = r1.parent!;
}
while (r2!.depth > r1.depth) {
r2 = r2.parent!;
}
while (!identical(r1, r2)) {
r1 = r1!.parent;
r2 = r2!.parent;
}
return r1;
}
/// Combines two reachabilities (both of which must be based on the same
/// checkpoint), where the code is considered reachable from the checkpoint
/// iff either argument is reachable from the checkpoint.
///
/// This is used as part of the "join" operation.
static Reachability join(Reachability r1, Reachability r2) {
assert(identical(r1.parent, r2.parent));
if (r2.locallyReachable) {
return r2;
} else {
return r1;
}
}
/// Combines two reachabilities (both of which must be based on the same
/// checkpoint), where the code is considered reachable from the checkpoint
/// iff both arguments are reachable from the checkpoint.
///
/// This is used as part of the "restrict" operation.
static Reachability restrict(Reachability r1, Reachability r2) {
assert(identical(r1.parent, r2.parent));
if (r2.locallyReachable) {
return r1;
} else {
return r2;
}
}
}
/// Container object combining a [Reference] object with its static type.
@visibleForTesting
class ReferenceWithType<Type extends Object> {
int promotionKey;
final Type type;
ReferenceWithType(this.promotionKey, this.type);
bool isPromotable(PromotionKeyStore<Object> promotionKeyStore) =>
promotionKeyStore.variableForKey(promotionKey) != null;
@override
String toString() => 'ReferenceWithType($promotionKey, $type)';
}
/// Data structure representing a unique value that a variable might take on
/// during execution of the code being analyzed. SSA nodes are immutable (so
/// they can be safety shared among data structures) and have identity (so that
/// it is possible to tell whether one SSA node is the same as another).
///
/// This is similar to the nodes used in traditional single assignment analysis
/// (https://en.wikipedia.org/wiki/Static_single_assignment_form) except that it
/// does not store a complete IR of the code being analyzed.
@visibleForTesting
class SsaNode<Type extends Object> {
/// Expando mapping SSA nodes to debug ids. Only used by `toString`.
static final Expando<int> _debugIds = new Expando<int>();
static int _nextDebugId = 0;
/// Flow analysis information was associated with the expression that
/// produced the value represented by this SSA node, if it was non-trivial.
/// This can be used at a later time to perform promotions if the value is
/// used in a control flow construct.
///
/// We don't bother storing flow analysis information if it's trivial (see
/// [_TrivialExpressionInfo]) because such information does not lead to
/// promotions.
@visibleForTesting
final ExpressionInfo<Type>? expressionInfo;
SsaNode(this.expressionInfo);
@override
String toString() {
int id = _debugIds[this] ??= _nextDebugId++;
return 'ssa$id';
}
}
/// Non-promotion reason describing the situation where an expression was not
/// promoted due to the fact that it's a reference to `this`.
class ThisNotPromoted extends NonPromotionReason {
@override
String get documentationLink => 'http://dart.dev/go/non-promo-this';
@override
String get shortName => 'thisNotPromoted';
@override
R accept<R, Node extends Object, Variable extends Object,
Type extends Object>(
NonPromotionReasonVisitor<R, Node, Variable, Type> visitor) =>
visitor.visitThisNotPromoted(this);
}
/// Enum representing the different classifications of types that can be
/// returned by [TypeOperations.classifyType].
enum TypeClassification {
/// The type is `Null` or an equivalent type (e.g. `Never?`)
nullOrEquivalent,
/// The type is a potentially nullable type, but not equivalent to `Null`
/// (e.g. `int?`, or a type variable whose bound is potentially nullable)
potentiallyNullable,
/// The type is a non-nullable type.
nonNullable,
}
/// Operations on types, abstracted from concrete type interfaces.
abstract class TypeOperations<Type extends Object> {
/// Classifies the given type into one of the three categories defined by
/// the [TypeClassification] enum.
TypeClassification classifyType(Type type);
/// Returns the "remainder" of [from] when [what] has been removed from
/// consideration by an instance check.
Type factor(Type from, Type what);
/// Whether the possible promotion from [from] to [to] should be forced, given
/// the current [promotedTypes], and [newPromotedTypes] resulting from
/// possible demotion.
///
/// It is not expected that any implementation would override this except for
/// the migration engine.
bool forcePromotion(Type to, Type from, List<Type>? promotedTypes,
List<Type>? newPromotedTypes) =>
false;
/// Determines whether the given [type] is equivalent to the `Never` type.
///
/// A type is equivalent to `Never` if it:
/// (a) is the `Never` type itself.
/// (b) is a type variable that extends `Never`, OR
/// (c) is a type variable that has been promoted to `Never`
bool isNever(Type type);
/// Returns `true` if [type1] and [type2] are the same type.
bool isSameType(Type type1, Type type2);
/// Return `true` if the [leftType] is a subtype of the [rightType].
bool isSubtypeOf(Type leftType, Type rightType);
/// Returns `true` if [type] is a reference to a type parameter.
bool isTypeParameterType(Type type);
/// Returns the non-null promoted version of [type].
///
/// Note that some types don't have a non-nullable version (e.g.
/// `FutureOr<int?>`), so [type] may be returned even if it is nullable.
Type /*!*/ promoteToNonNull(Type type);
/// Performs refinements on the [promotedTypes] chain which resulted in
/// intersecting [chain1] and [chain2].
///
/// It is not expected that any implementation would override this except for
/// the migration engine.
List<Type>? refinePromotedTypes(
List<Type>? chain1, List<Type>? chain2, List<Type>? promotedTypes) =>
promotedTypes;
/// Tries to promote to the first type from the second type, and returns the
/// promoted type if it succeeds, otherwise null.
Type? tryPromoteToType(Type to, Type from);
}
/// An instance of the [VariableModel] class represents the information gathered
/// by flow analysis for a single variable at a single point in the control flow
/// of the function or method being analyzed.
///
/// Instances of this class are immutable, so the methods below that "update"
/// the state actually leave `this` unchanged and return a new state object.
@visibleForTesting
class VariableModel<Type extends Object> {
/// Sequence of types that the variable has been promoted to, where each
/// element of the sequence is a subtype of the previous. Null if the
/// variable hasn't been promoted.
final List<Type>? promotedTypes;
/// List of types that the variable has been tested against in all code paths
/// leading to the given point in the source code.
final List<Type> tested;
/// Indicates whether the variable has definitely been assigned.
final bool assigned;
/// Indicates whether the variable is unassigned.
final bool unassigned;
/// SSA node associated with this variable. Every time the variable's value
/// potentially changes (either through an explicit write or a join with a
/// control flow path that contains a write), this field is updated to point
/// to a fresh node. Thus, it can be used to detect whether a variable's
/// value has changed since a time in the past.
///
/// `null` if the variable has been write captured.
final SsaNode<Type>? ssaNode;
/// Non-promotion history of this variable.
final NonPromotionHistory<Type>? nonPromotionHistory;
VariableModel(
{required this.promotedTypes,
required this.tested,
required this.assigned,
required this.unassigned,
required this.ssaNode,
this.nonPromotionHistory}) {
assert(!(assigned && unassigned),
"Can't be both definitely assigned and unassigned");
assert(promotedTypes == null || promotedTypes!.isNotEmpty);
assert(!writeCaptured || promotedTypes == null,
"Write-captured variables can't be promoted");
assert(!(writeCaptured && unassigned),
"Write-captured variables can't be definitely unassigned");
// ignore:unnecessary_null_comparison
assert(tested != null);
}
/// Creates a [VariableModel] representing a variable that's never been seen
/// before.
VariableModel.fresh({this.assigned = false})
: promotedTypes = null,
tested = const [],
unassigned = !assigned,
ssaNode = new SsaNode<Type>(null),
nonPromotionHistory = null;
/// Indicates whether the variable has been write captured.
bool get writeCaptured => ssaNode == null;
/// Returns a new [VariableModel] in which any promotions present have been
/// dropped, and the variable has been marked as "not unassigned".
///
/// Used by [conservativeJoin] to update the state of variables at the top of
/// loops whose bodies write to them.
VariableModel<Type> discardPromotionsAndMarkNotUnassigned() {
return new VariableModel<Type>(
promotedTypes: null,
tested: tested,
assigned: assigned,
unassigned: false,
ssaNode: writeCaptured ? null : new SsaNode<Type>(null));
}
@override
String toString() {
List<String> parts = [ssaNode.toString()];
if (promotedTypes != null) {
parts.add('promotedTypes: $promotedTypes');
}
if (tested.isNotEmpty) {
parts.add('tested: $tested');
}
if (assigned) {
parts.add('assigned: true');
}
if (!unassigned) {
parts.add('unassigned: false');
}
if (writeCaptured) {
parts.add('writeCaptured: true');
}
if (nonPromotionHistory != null) {
parts.add('nonPromotionHistory: $nonPromotionHistory');
}
return 'VariableModel(${parts.join(', ')})';
}
/// Returns a new [VariableModel] reflecting the fact that the variable was
/// just written to.
///
/// If there is any chance that the write will cause a demotion, the caller
/// must pass in a non-null value for [nonPromotionReason] describing the
/// reason for any potential demotion.
VariableModel<Type> write<Variable extends Object>(
NonPromotionReason? nonPromotionReason,
Variable variable,
int variableKey,
Type writtenType,
Operations<Variable, Type> operations,
SsaNode<Type> newSsaNode,
{required bool promoteToTypeOfInterest}) {
if (writeCaptured) {
return new VariableModel<Type>(
promotedTypes: promotedTypes,
tested: tested,
assigned: true,
unassigned: false,
ssaNode: null);
}
_DemotionResult<Type> demotionResult =
_demoteViaAssignment(writtenType, operations, nonPromotionReason);
List<Type>? newPromotedTypes = demotionResult.promotedTypes;
Type declaredType = operations.variableType(variable);
if (promoteToTypeOfInterest) {
newPromotedTypes = _tryPromoteToTypeOfInterest(
operations, declaredType, newPromotedTypes, writtenType);
}
// TODO(paulberry): remove demotions from demotionResult.nonPromotionHistory
// that are no longer in effect due to re-promotion.
if (identical(promotedTypes, newPromotedTypes) && assigned) {
return new VariableModel<Type>(
promotedTypes: promotedTypes,
tested: tested,
assigned: assigned,
unassigned: unassigned,
ssaNode: newSsaNode);
}
List<Type> newTested;
if (newPromotedTypes == null && promotedTypes != null) {
newTested = const [];
} else {
newTested = tested;
}
return new VariableModel<Type>(
promotedTypes: newPromotedTypes,
tested: newTested,
assigned: true,
unassigned: false,
ssaNode: newSsaNode,
nonPromotionHistory: demotionResult.nonPromotionHistory);
}
/// Returns a new [VariableModel] reflecting the fact that the variable has
/// been write-captured.
VariableModel<Type> writeCapture() {
return new VariableModel<Type>(
promotedTypes: null,
tested: const [],
assigned: assigned,
unassigned: false,
ssaNode: null);
}
/// Computes the result of demoting this variable due to writing a value of
/// type [writtenType].
///
/// If there is any chance that the write will cause an actual demotion to
/// occur, the caller must pass in a non-null value for [nonPromotionReason]
/// describing the reason for the potential demotion.
_DemotionResult<Type> _demoteViaAssignment(
Type writtenType,
TypeOperations<Type> typeOperations,
NonPromotionReason? nonPromotionReason) {
List<Type>? promotedTypes = this.promotedTypes;
if (promotedTypes == null) {
return new _DemotionResult<Type>(null, nonPromotionHistory);
}
int numElementsToKeep = promotedTypes.length;
NonPromotionHistory<Type>? newNonPromotionHistory = nonPromotionHistory;
List<Type>? newPromotedTypes;
for (;; numElementsToKeep--) {
if (numElementsToKeep == 0) {
break;
}
Type promoted = promotedTypes[numElementsToKeep - 1];
if (typeOperations.isSubtypeOf(writtenType, promoted)) {
if (numElementsToKeep == promotedTypes.length) {
newPromotedTypes = promotedTypes;
break;
}
newPromotedTypes = promotedTypes.sublist(0, numElementsToKeep);
break;
}
if (nonPromotionReason == null) {
assert(false, 'Demotion occurred but nonPromotionReason is null');
} else {
newNonPromotionHistory = new NonPromotionHistory<Type>(
promoted, nonPromotionReason, newNonPromotionHistory);
}
}
return new _DemotionResult<Type>(newPromotedTypes, newNonPromotionHistory);
}
/// Determines whether a variable with the given [promotedTypes] should be
/// promoted to [writtenType] based on types of interest. If it should,
/// returns an updated promotion chain; otherwise returns [promotedTypes]
/// unchanged.
///
/// Note that since promotion chains are considered immutable, if promotion
/// is required, a new promotion chain will be created and returned.
List<Type>? _tryPromoteToTypeOfInterest(TypeOperations<Type> typeOperations,
Type declaredType, List<Type>? promotedTypes, Type writtenType) {
assert(!writeCaptured);
if (typeOperations.forcePromotion(
writtenType, declaredType, this.promotedTypes, promotedTypes)) {
return _addToPromotedTypes(promotedTypes, writtenType);
}
// Figure out if we have any promotion candidates (types that are a
// supertype of writtenType and a proper subtype of the currently-promoted
// type). If at any point we find an exact match, we take it immediately.
Type? currentlyPromotedType = promotedTypes?.last;
List<Type>? result;
List<Type>? candidates = null;
void handleTypeOfInterest(Type type) {
// The written type must be a subtype of the type.
if (!typeOperations.isSubtypeOf(writtenType, type)) {
return;
}
// Must be more specific that the currently promoted type.
if (currentlyPromotedType != null) {
if (typeOperations.isSameType(type, currentlyPromotedType)) {
return;
}
if (!typeOperations.isSubtypeOf(type, currentlyPromotedType)) {
return;
}
}
// This is precisely the type we want to promote to; take it.
if (typeOperations.isSameType(type, writtenType)) {
result = _addToPromotedTypes(promotedTypes, writtenType);
}
if (candidates == null) {
candidates = [type];
return;
}
// Add only unique candidates.
if (!_typeListContains(typeOperations, candidates!, type)) {
candidates!.add(type);
return;
}
}
// The declared type is always a type of interest, but we never promote
// to the declared type. So, try NonNull of it.
Type declaredTypeNonNull = typeOperations.promoteToNonNull(declaredType);
if (!typeOperations.isSameType(declaredTypeNonNull, declaredType)) {
handleTypeOfInterest(declaredTypeNonNull);
if (result != null) {
return result!;
}
}
for (int i = 0; i < tested.length; i++) {
Type type = tested[i];
handleTypeOfInterest(type);
if (result != null) {
return result!;
}
Type typeNonNull = typeOperations.promoteToNonNull(type);
if (!typeOperations.isSameType(typeNonNull, type)) {
handleTypeOfInterest(typeNonNull);
if (result != null) {
return result!;
}
}
}
List<Type>? candidates2 = candidates;
if (candidates2 != null) {
// Figure out if we have a unique promotion candidate that's a subtype
// of all the others.
Type? promoted;
outer:
for (int i = 0; i < candidates2.length; i++) {
for (int j = 0; j < candidates2.length; j++) {
if (j == i) continue;
if (!typeOperations.isSubtypeOf(candidates2[i], candidates2[j])) {
// Not a subtype of all the others.
continue outer;
}
}
if (promoted != null) {
// Not unique. Do not promote.
return promotedTypes;
} else {
promoted = candidates2[i];
}
}
if (promoted != null) {
return _addToPromotedTypes(promotedTypes, promoted);
}
}
// No suitable promotion found.
return promotedTypes;
}
/// Builds a [VariableModel] based on [model], but extending the [tested] set
/// to include types from [tested]. This is used at the bottom of certain
/// kinds of loops, to ensure that types tested within the body of the loop
/// are consistently treated as "of interest" in code that follows the loop,
/// regardless of the type of loop.
@visibleForTesting
static VariableModel<Type> inheritTested<Type extends Object>(
TypeOperations<Type> typeOperations,
VariableModel<Type> model,
List<Type> tested) {
List<Type> newTested = joinTested(tested, model.tested, typeOperations);
if (identical(newTested, model.tested)) return model;
return new VariableModel<Type>(
promotedTypes: model.promotedTypes,