| // 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'; |
| |
| /// Sets of local variables that are potentially assigned in a statement. |
| /// |
| /// These statements are loops, `switch`, and `try` statements. |
| class AssignedVariables<Statement, Variable> { |
| final emptySet = Set<Variable>(); |
| |
| /// Mapping from a [Statement] to the set of local variables that are |
| /// potentially assigned in that statement. |
| final Map<Statement, Set<Variable>> _map = {}; |
| |
| /// The stack of nested statements. |
| final List<Set<Variable>> _stack = []; |
| |
| AssignedVariables(); |
| |
| /// Return the set of variables that are potentially assigned in the |
| /// [statement]. |
| Set<Variable> operator [](Statement statement) { |
| return _map[statement] ?? emptySet; |
| } |
| |
| void beginStatement() { |
| var set = Set<Variable>.identity(); |
| _stack.add(set); |
| } |
| |
| void endStatement(Statement node) { |
| _map[node] = _stack.removeLast(); |
| } |
| |
| void write(Variable variable) { |
| for (var i = 0; i < _stack.length; ++i) { |
| _stack[i].add(variable); |
| } |
| } |
| } |
| |
| class FlowAnalysis<Statement, Expression, Variable, Type> { |
| static bool get _assertionsEnabled { |
| bool result = false; |
| assert(result = true); |
| return result; |
| } |
| |
| final _VariableSet<Variable> _emptySet; |
| |
| /// The [NodeOperations], used to manipulate expressions. |
| final NodeOperations<Expression> nodeOperations; |
| |
| /// The [TypeOperations], used to access types, and check subtyping. |
| final TypeOperations<Variable, Type> typeOperations; |
| |
| /// The enclosing function body, used to check for potential mutations. |
| final FunctionBodyAccess<Variable> functionBody; |
| |
| /// The stack of states of variables that are not definitely assigned. |
| final List<FlowModel<Variable, Type>> _stack = []; |
| |
| /// The mapping from labeled [Statement]s to the index in the [_stack] |
| /// where the first related element is located. The number of elements |
| /// is statement specific. Loops have two elements: `break` and `continue` |
| /// states. |
| final Map<Statement, int> _statementToStackIndex = {}; |
| |
| /// List of all variables passed to [add]. |
| final List<Variable> _addedVariables = []; |
| |
| FlowModel<Variable, Type> _current; |
| |
| /// The last boolean condition, for [_conditionTrue] and [_conditionFalse]. |
| Expression _condition; |
| |
| /// The state when [_condition] evaluates to `true`. |
| FlowModel<Variable, Type> _conditionTrue; |
| |
| /// The state when [_condition] evaluates to `false`. |
| FlowModel<Variable, Type> _conditionFalse; |
| |
| /// If assertions are enabled, keeps track of all variables that have been |
| /// passed into the API (other than through a call to [add]). The [finish] |
| /// method uses this to verify that the caller doesn't forget to pass a |
| /// variable to [add]. |
| /// |
| /// Note: the reason we have to keep track of this set (rather than simply |
| /// checking each variable at the time it is passed into the API) is because |
| /// the client doesn't call `add` until a variable is declared, and in |
| /// erroneous code, it's possible that a variable might be used before its |
| /// declaration. |
| final Set<Variable> _referencedVariables = |
| _assertionsEnabled ? Set<Variable>() : null; |
| |
| factory FlowAnalysis( |
| NodeOperations<Expression> nodeOperations, |
| TypeOperations<Variable, Type> typeOperations, |
| FunctionBodyAccess<Variable> functionBody, |
| ) { |
| var emptySet = FlowModel<Variable, Type>(false).notAssigned; |
| return FlowAnalysis._( |
| nodeOperations, |
| typeOperations, |
| functionBody, |
| emptySet, |
| ); |
| } |
| |
| FlowAnalysis._( |
| this.nodeOperations, |
| this.typeOperations, |
| this.functionBody, |
| this._emptySet, |
| ) { |
| _current = FlowModel<Variable, Type>(true); |
| } |
| |
| /// Return `true` if the current state is reachable. |
| bool get isReachable => _current.reachable; |
| |
| /// Add a new [variable], which might be already [assigned]. |
| void add(Variable variable, {bool assigned: false}) { |
| _addedVariables.add(variable); |
| _current = _current.add(variable, assigned: assigned); |
| } |
| |
| void booleanLiteral(Expression expression, bool value) { |
| _condition = expression; |
| if (value) { |
| _conditionTrue = _current; |
| _conditionFalse = _current.setReachable(false); |
| } else { |
| _conditionTrue = _current.setReachable(false); |
| _conditionFalse = _current; |
| } |
| } |
| |
| void conditional_elseBegin(Expression thenExpression) { |
| var afterThen = _current; |
| var falseCondition = _stack.removeLast(); |
| |
| _conditionalEnd(thenExpression); |
| // Tail of the stack: falseThen, trueThen |
| |
| _stack.add(afterThen); |
| _current = falseCondition; |
| } |
| |
| void conditional_end( |
| Expression conditionalExpression, Expression elseExpression) { |
| var afterThen = _stack.removeLast(); |
| var afterElse = _current; |
| |
| _conditionalEnd(elseExpression); |
| // Tail of the stack: falseThen, trueThen, falseElse, trueElse |
| |
| var trueElse = _stack.removeLast(); |
| var falseElse = _stack.removeLast(); |
| |
| var trueThen = _stack.removeLast(); |
| var falseThen = _stack.removeLast(); |
| |
| var trueResult = _join(trueThen, trueElse); |
| var falseResult = _join(falseThen, falseElse); |
| |
| _condition = conditionalExpression; |
| _conditionTrue = trueResult; |
| _conditionFalse = falseResult; |
| |
| _current = _join(afterThen, afterElse); |
| } |
| |
| void conditional_thenBegin(Expression condition) { |
| _conditionalEnd(condition); |
| // Tail of the stack: falseCondition, trueCondition |
| |
| var trueCondition = _stack.removeLast(); |
| _current = trueCondition; |
| } |
| |
| /// The [binaryExpression] checks that the [variable] is, or is not, equal to |
| /// `null`. |
| void conditionEqNull(Expression binaryExpression, Variable variable, |
| {bool notEqual: false}) { |
| _variableReferenced(variable); |
| if (functionBody.isPotentiallyMutatedInClosure(variable)) { |
| return; |
| } |
| |
| _condition = binaryExpression; |
| var currentPromoted = _current.markNonNullable(typeOperations, variable); |
| if (notEqual) { |
| _conditionTrue = currentPromoted; |
| _conditionFalse = _current; |
| } else { |
| _conditionTrue = _current; |
| _conditionFalse = currentPromoted; |
| } |
| } |
| |
| void doStatement_bodyBegin( |
| Statement doStatement, Set<Variable> loopAssigned) { |
| _variablesReferenced(loopAssigned); |
| _current = _current.removePromotedAll(loopAssigned); |
| |
| _statementToStackIndex[doStatement] = _stack.length; |
| _stack.add(null); // break |
| _stack.add(null); // continue |
| } |
| |
| void doStatement_conditionBegin() { |
| // Tail of the stack: break, continue |
| |
| var continueState = _stack.removeLast(); |
| _current = _join(_current, continueState); |
| } |
| |
| void doStatement_end(Expression condition) { |
| _conditionalEnd(condition); |
| // Tail of the stack: break, falseCondition, trueCondition |
| |
| _stack.removeLast(); // trueCondition |
| var falseCondition = _stack.removeLast(); |
| var breakState = _stack.removeLast(); |
| |
| _current = _join(falseCondition, breakState); |
| } |
| |
| /// This method should be called at the conclusion of flow analysis for a top |
| /// level function or method. Performs assertion checks. |
| void finish() { |
| assert(_stack.isEmpty); |
| assert(() { |
| var variablesNotAdded = |
| _referencedVariables.difference(Set<Variable>.from(_addedVariables)); |
| assert(variablesNotAdded.isEmpty, |
| 'Variables not passed to add: $variablesNotAdded'); |
| return true; |
| }()); |
| } |
| |
| void forEachStatement_bodyBegin(Set<Variable> loopAssigned) { |
| _variablesReferenced(loopAssigned); |
| _stack.add(_current); |
| _current = _current.removePromotedAll(loopAssigned); |
| } |
| |
| void forEachStatement_end() { |
| var afterIterable = _stack.removeLast(); |
| _current = _join(_current, afterIterable); |
| } |
| |
| void forStatement_bodyBegin(Statement node, Expression condition) { |
| _conditionalEnd(condition); |
| // Tail of the stack: falseCondition, trueCondition |
| |
| var trueCondition = _stack.removeLast(); |
| |
| _statementToStackIndex[node] = _stack.length; |
| _stack.add(null); // break |
| _stack.add(null); // continue |
| |
| _current = trueCondition; |
| } |
| |
| void forStatement_conditionBegin(Set<Variable> loopAssigned) { |
| _variablesReferenced(loopAssigned); |
| _current = _current.removePromotedAll(loopAssigned); |
| } |
| |
| void forStatement_end() { |
| // Tail of the stack: falseCondition, break |
| var breakState = _stack.removeLast(); |
| var falseCondition = _stack.removeLast(); |
| |
| _current = _join(falseCondition, breakState); |
| } |
| |
| void forStatement_updaterBegin() { |
| // Tail of the stack: falseCondition, break, continue |
| var afterBody = _current; |
| var continueState = _stack.removeLast(); |
| |
| _current = _join(afterBody, continueState); |
| } |
| |
| void functionExpression_begin() { |
| _stack.add(_current); |
| |
| Set<Variable> notPromoted = null; |
| for (var entry in _current.promoted.entries) { |
| var variable = entry.key; |
| var promotedType = entry.value; |
| if (promotedType != null && |
| functionBody.isPotentiallyMutatedInScope(variable)) { |
| notPromoted ??= Set<Variable>.identity(); |
| notPromoted.add(variable); |
| } |
| } |
| |
| if (notPromoted != null) { |
| _current = _current.removePromotedAll(notPromoted); |
| } |
| } |
| |
| void functionExpression_end() { |
| _current = _stack.removeLast(); |
| } |
| |
| void handleBreak(Statement target) { |
| var breakIndex = _statementToStackIndex[target]; |
| if (breakIndex != null) { |
| _stack[breakIndex] = _join(_stack[breakIndex], _current); |
| } |
| _current = _current.setReachable(false); |
| } |
| |
| void handleContinue(Statement target) { |
| var breakIndex = _statementToStackIndex[target]; |
| if (breakIndex != null) { |
| var continueIndex = breakIndex + 1; |
| _stack[continueIndex] = _join(_stack[continueIndex], _current); |
| } |
| _current = _current.setReachable(false); |
| } |
| |
| /// Register the fact that the current state definitely exists, e.g. returns |
| /// from the body, throws an exception, etc. |
| void handleExit() { |
| _current = _current.setReachable(false); |
| } |
| |
| void ifNullExpression_end() { |
| var afterLeft = _stack.removeLast(); |
| _current = _join(_current, afterLeft); |
| } |
| |
| void ifNullExpression_rightBegin() { |
| _stack.add(_current); // afterLeft |
| } |
| |
| void ifStatement_elseBegin() { |
| var afterThen = _current; |
| var falseCondition = _stack.removeLast(); |
| _stack.add(afterThen); |
| _current = falseCondition; |
| } |
| |
| void ifStatement_end(bool hasElse) { |
| FlowModel<Variable, Type> afterThen; |
| FlowModel<Variable, Type> afterElse; |
| if (hasElse) { |
| afterThen = _stack.removeLast(); |
| afterElse = _current; |
| } else { |
| afterThen = _current; // no `else`, so `then` is still current |
| afterElse = _stack.removeLast(); // `falseCond` is still on the stack |
| } |
| _current = _join(afterThen, afterElse); |
| } |
| |
| void ifStatement_thenBegin(Expression condition) { |
| _conditionalEnd(condition); |
| // Tail of the stack: falseCondition, trueCondition |
| |
| var trueCondition = _stack.removeLast(); |
| _current = trueCondition; |
| } |
| |
| /// Return whether the [variable] is definitely assigned in the current state. |
| bool isAssigned(Variable variable) { |
| _variableReferenced(variable); |
| return !_current.notAssigned.contains(variable); |
| } |
| |
| void isExpression_end( |
| Expression isExpression, Variable variable, bool isNot, Type type) { |
| _variableReferenced(variable); |
| if (functionBody.isPotentiallyMutatedInClosure(variable)) { |
| return; |
| } |
| |
| _condition = isExpression; |
| if (isNot) { |
| _conditionTrue = _current; |
| _conditionFalse = _current.promote(typeOperations, variable, type); |
| } else { |
| _conditionTrue = _current.promote(typeOperations, variable, type); |
| _conditionFalse = _current; |
| } |
| } |
| |
| void logicalBinaryOp_end(Expression wholeExpression, Expression rightOperand, |
| {@required bool isAnd}) { |
| _conditionalEnd(rightOperand); |
| // Tail of the stack: falseLeft, trueLeft, falseRight, trueRight |
| |
| var trueRight = _stack.removeLast(); |
| var falseRight = _stack.removeLast(); |
| |
| var trueLeft = _stack.removeLast(); |
| var falseLeft = _stack.removeLast(); |
| |
| FlowModel<Variable, Type> trueResult; |
| FlowModel<Variable, Type> falseResult; |
| if (isAnd) { |
| trueResult = trueRight; |
| falseResult = _join(falseLeft, falseRight); |
| } else { |
| trueResult = _join(trueLeft, trueRight); |
| falseResult = falseRight; |
| } |
| |
| var afterResult = _join(trueResult, falseResult); |
| |
| _condition = wholeExpression; |
| _conditionTrue = trueResult; |
| _conditionFalse = falseResult; |
| |
| _current = afterResult; |
| } |
| |
| void logicalBinaryOp_rightBegin(Expression leftOperand, |
| {@required bool isAnd}) { |
| _conditionalEnd(leftOperand); |
| // Tail of the stack: falseLeft, trueLeft |
| |
| if (isAnd) { |
| var trueLeft = _stack.last; |
| _current = trueLeft; |
| } else { |
| var falseLeft = _stack[_stack.length - 2]; |
| _current = falseLeft; |
| } |
| } |
| |
| void logicalNot_end(Expression notExpression, Expression operand) { |
| _conditionalEnd(operand); |
| var trueExpr = _stack.removeLast(); |
| var falseExpr = _stack.removeLast(); |
| |
| _condition = notExpression; |
| _conditionTrue = falseExpr; |
| _conditionFalse = trueExpr; |
| } |
| |
| /// Retrieves the type that the [variable] is promoted to, if the [variable] |
| /// is currently promoted. Otherwise returns `null`. |
| Type promotedType(Variable variable) { |
| _variableReferenced(variable); |
| return _current.promoted[variable]; |
| } |
| |
| /// The [notPromoted] set contains all variables that are potentially |
| /// assigned in other cases that might target this with `continue`, so |
| /// these variables might have different types and are "un-promoted" from |
| /// the "afterExpression" state. |
| void switchStatement_beginCase(Set<Variable> notPromoted) { |
| _variablesReferenced(notPromoted); |
| _current = _stack.last.removePromotedAll(notPromoted); |
| } |
| |
| void switchStatement_end(Statement switchStatement, bool hasDefault) { |
| // Tail of the stack: break, continue, afterExpression |
| var afterExpression = _current = _stack.removeLast(); |
| _stack.removeLast(); // continue |
| var breakState = _stack.removeLast(); |
| |
| if (hasDefault) { |
| // breakState should not be null because we should have joined it with |
| // something non-null when handling the default case. |
| assert(breakState != null); |
| _current = breakState; |
| } else { |
| _current = _join(breakState, afterExpression); |
| } |
| } |
| |
| void switchStatement_expressionEnd(Statement switchStatement) { |
| _statementToStackIndex[switchStatement] = _stack.length; |
| _stack.add(null); // break |
| _stack.add(null); // continue |
| _stack.add(_current); // afterExpression |
| } |
| |
| void tryCatchStatement_bodyBegin() { |
| _stack.add(_current); |
| // Tail of the stack: beforeBody |
| } |
| |
| void tryCatchStatement_bodyEnd(Set<Variable> assignedInBody) { |
| _variablesReferenced(assignedInBody); |
| var beforeBody = _stack.removeLast(); |
| var beforeCatch = beforeBody.removePromotedAll(assignedInBody); |
| _stack.add(beforeCatch); |
| _stack.add(_current); // afterBodyAndCatches |
| // Tail of the stack: beforeCatch, afterBodyAndCatches |
| } |
| |
| void tryCatchStatement_catchBegin() { |
| var beforeCatch = _stack[_stack.length - 2]; |
| _current = beforeCatch; |
| } |
| |
| void tryCatchStatement_catchEnd() { |
| var afterBodyAndCatches = _stack.last; |
| _stack.last = _join(afterBodyAndCatches, _current); |
| } |
| |
| void tryCatchStatement_end() { |
| var afterBodyAndCatches = _stack.removeLast(); |
| _stack.removeLast(); // beforeCatch |
| _current = afterBodyAndCatches; |
| } |
| |
| void tryFinallyStatement_bodyBegin() { |
| _stack.add(_current); // beforeTry |
| } |
| |
| void tryFinallyStatement_end(Set<Variable> assignedInFinally) { |
| _variablesReferenced(assignedInFinally); |
| var afterBody = _stack.removeLast(); |
| _current = _current.restrict( |
| typeOperations, |
| _emptySet, |
| afterBody, |
| assignedInFinally, |
| ); |
| } |
| |
| void tryFinallyStatement_finallyBegin(Set<Variable> assignedInBody) { |
| _variablesReferenced(assignedInBody); |
| var beforeTry = _stack.removeLast(); |
| var afterBody = _current; |
| _stack.add(afterBody); |
| _current = _join(afterBody, beforeTry.removePromotedAll(assignedInBody)); |
| } |
| |
| void whileStatement_bodyBegin( |
| Statement whileStatement, Expression condition) { |
| _conditionalEnd(condition); |
| // Tail of the stack: falseCondition, trueCondition |
| |
| var trueCondition = _stack.removeLast(); |
| |
| _statementToStackIndex[whileStatement] = _stack.length; |
| _stack.add(null); // break |
| _stack.add(null); // continue |
| |
| _current = trueCondition; |
| } |
| |
| void whileStatement_conditionBegin(Set<Variable> loopAssigned) { |
| _variablesReferenced(loopAssigned); |
| _current = _current.removePromotedAll(loopAssigned); |
| } |
| |
| void whileStatement_end() { |
| _stack.removeLast(); // continue |
| var breakState = _stack.removeLast(); |
| var falseCondition = _stack.removeLast(); |
| |
| _current = _join(falseCondition, breakState); |
| } |
| |
| /// Register write of the given [variable] in the current state. |
| void write(Variable variable) { |
| _variableReferenced(variable); |
| _current = _current.write(typeOperations, _emptySet, variable); |
| } |
| |
| void _conditionalEnd(Expression condition) { |
| condition = nodeOperations.unwrapParenthesized(condition); |
| if (identical(condition, _condition)) { |
| _stack.add(_conditionFalse); |
| _stack.add(_conditionTrue); |
| } else { |
| _stack.add(_current); |
| _stack.add(_current); |
| } |
| } |
| |
| FlowModel<Variable, Type> _join( |
| FlowModel<Variable, Type> first, FlowModel<Variable, Type> second) => |
| FlowModel.join(typeOperations, first, second); |
| |
| /// If assertions are enabled, records that the given variable has been |
| /// referenced. The [finish] method will verify that all referenced variables |
| /// were eventually passed to [add]. |
| void _variableReferenced(Variable variable) { |
| assert(() { |
| _referencedVariables.add(variable); |
| return true; |
| }()); |
| } |
| |
| /// If assertions are enabled, records that the given variables have been |
| /// referenced. The [finish] method will verify that all referenced variables |
| /// were eventually passed to [add]. |
| void _variablesReferenced(Iterable<Variable> variables) { |
| assert(() { |
| _referencedVariables.addAll(variables); |
| return true; |
| }()); |
| } |
| } |
| |
| /// 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<Variable, Type> { |
| /// Indicates whether this point in the control flow is reachable. |
| final bool reachable; |
| |
| /// The set of variables that are not yet definitely assigned at this point in |
| /// the control flow. |
| final _VariableSet<Variable> notAssigned; |
| |
| /// For each variable being tracked by flow analysis, the variable's promoted |
| /// type, or `null` if the variable's type is not promoted. |
| /// |
| /// 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 and then promoted 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. |
| final Map<Variable, Type> promoted; |
| |
| /// 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(bool reachable) |
| : this._( |
| reachable, |
| _VariableSet<Variable>._(const []), |
| const {}, |
| ); |
| |
| FlowModel._( |
| this.reachable, |
| this.notAssigned, |
| this.promoted, |
| ); |
| |
| /// Updates the state to track a newly declared local [variable]. The |
| /// optional [assigned] boolean indicates whether the variable is assigned at |
| /// the point of declaration. |
| FlowModel<Variable, Type> add(Variable variable, {bool assigned: false}) { |
| var newNotAssigned = assigned ? notAssigned : notAssigned.add(variable); |
| var newPromoted = Map<Variable, Type>.from(promoted); |
| newPromoted[variable] = null; |
| |
| return FlowModel<Variable, Type>._( |
| reachable, |
| newNotAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Updates the state to indicate that the given [variable] has been |
| /// determined to contain a non-null value. |
| /// |
| /// TODO(paulberry): should this method mark the variable as definitely |
| /// assigned? Does it matter? |
| FlowModel<Variable, Type> markNonNullable( |
| TypeOperations<Variable, Type> typeOperations, Variable variable) { |
| var previousType = promoted[variable]; |
| previousType ??= typeOperations.variableType(variable); |
| var type = typeOperations.promoteToNonNull(previousType); |
| |
| if (!typeOperations.isSameType(type, previousType)) { |
| var newPromoted = <Variable, Type>{}..addAll(promoted); |
| newPromoted[variable] = type; |
| return FlowModel<Variable, Type>._( |
| reachable, |
| notAssigned, |
| newPromoted, |
| ); |
| } |
| |
| return this; |
| } |
| |
| /// Updates the state to indicate that the given [variable] has been |
| /// determined to satisfy the given [type], e.g. as a consequence of an `is` |
| /// expression as the condition of an `if` statement. |
| /// |
| /// 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<Variable, Type> promote( |
| TypeOperations<Variable, Type> typeOperations, |
| Variable variable, |
| Type type, |
| ) { |
| var previousType = promoted[variable]; |
| previousType ??= typeOperations.variableType(variable); |
| |
| if (typeOperations.isSubtypeOf(type, previousType) && |
| !typeOperations.isSameType(type, previousType)) { |
| var newPromoted = <Variable, Type>{}..addAll(promoted); |
| newPromoted[variable] = type; |
| return FlowModel<Variable, Type>._( |
| reachable, |
| notAssigned, |
| newPromoted, |
| ); |
| } |
| |
| return this; |
| } |
| |
| /// Updates the state to indicate that the given [variables] are no longer |
| /// promoted; they are presumed to have their declared types. |
| /// |
| /// 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<Variable, Type> removePromotedAll(Set<Variable> variables) { |
| var newPromoted = _removePromotedAll(promoted, variables); |
| |
| if (identical(newPromoted, promoted)) return this; |
| |
| return FlowModel<Variable, Type>._( |
| reachable, |
| notAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Updates the state to reflect a control path that is known to have |
| /// previously passed through some [other] state. |
| /// |
| /// Approximately, this method forms the union of the definite assignments and |
| /// promotions in `this` state and the [other] state. More precisely: |
| /// |
| /// The control flow path is considered reachable if both this state and the |
| /// other state are reachable. Variables are considered definitely assigned |
| /// if they were definitely assigned in either this state or the other state. |
| /// Variable type promotions are taken from this state, unless the promotion |
| /// in the other state is more specific, and the variable is "safe". A |
| /// variable is considered safe if there is no chance that it was assigned |
| /// more recently than the "other" state. |
| /// |
| /// This is used after a `try/finally` statement to combine the promotions and |
| /// definite assignments that occurred in the `try` and `finally` blocks |
| /// (where `this` is the state from the `finally` block and `other` is the |
| /// state from the `try` block). Variables that are assigned in the `finally` |
| /// block are considered "unsafe" because the assignment might have cancelled |
| /// the effect of any promotion that occurred inside the `try` block. |
| FlowModel<Variable, Type> restrict( |
| TypeOperations<Variable, Type> typeOperations, |
| _VariableSet<Variable> emptySet, |
| FlowModel<Variable, Type> other, |
| Set<Variable> unsafe, |
| ) { |
| var newReachable = reachable && other.reachable; |
| var newNotAssigned = notAssigned.intersect( |
| empty: emptySet, |
| other: other.notAssigned, |
| ); |
| if (newNotAssigned.variables.length == notAssigned.variables.length) { |
| newNotAssigned = notAssigned; |
| } else if (newNotAssigned.variables.length == |
| other.notAssigned.variables.length) { |
| newNotAssigned = other.notAssigned; |
| } |
| |
| var newPromoted = <Variable, Type>{}; |
| bool promotedMatchesThis = true; |
| bool promotedMatchesOther = other.promoted.length == promoted.length; |
| for (var entry in promoted.entries) { |
| var variable = entry.key; |
| var thisType = entry.value; |
| var otherType = other.promoted[variable]; |
| if (!unsafe.contains(variable)) { |
| if (otherType != null && |
| (thisType == null || |
| typeOperations.isSubtypeOf(otherType, thisType))) { |
| newPromoted[variable] = otherType; |
| if (promotedMatchesThis && |
| (thisType == null || |
| !typeOperations.isSameType(thisType, otherType))) { |
| promotedMatchesThis = false; |
| } |
| continue; |
| } |
| } |
| if (thisType != null) { |
| newPromoted[variable] = thisType; |
| if (promotedMatchesOther && |
| (otherType == null || |
| !typeOperations.isSameType(thisType, otherType))) { |
| promotedMatchesOther = false; |
| } |
| } else { |
| newPromoted[variable] = null; |
| if (promotedMatchesOther && otherType != null) { |
| promotedMatchesOther = false; |
| } |
| } |
| } |
| assert(promotedMatchesThis == |
| _promotionsEqual(typeOperations, newPromoted, promoted)); |
| assert(promotedMatchesOther == |
| _promotionsEqual(typeOperations, newPromoted, other.promoted)); |
| if (promotedMatchesThis) { |
| newPromoted = promoted; |
| } else if (promotedMatchesOther) { |
| newPromoted = other.promoted; |
| } |
| |
| return _identicalOrNew( |
| this, |
| other, |
| newReachable, |
| newNotAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Updates the state to indicate whether the control flow path is |
| /// [reachable]. |
| FlowModel<Variable, Type> setReachable(bool reachable) { |
| if (this.reachable == reachable) return this; |
| |
| return FlowModel<Variable, Type>._( |
| reachable, |
| notAssigned, |
| promoted, |
| ); |
| } |
| |
| @override |
| String toString() => '($reachable, $notAssigned, $promoted)'; |
| |
| /// Updates the state to indicate that an assignment was made to the given |
| /// [variable]. The variable is marked as definitely assigned, and any |
| /// previous type promotion is removed. |
| /// |
| /// TODO(paulberry): allow for writes that preserve type promotions. |
| FlowModel<Variable, Type> write(TypeOperations<Variable, Type> typeOperations, |
| _VariableSet<Variable> emptySet, Variable variable) { |
| var newNotAssigned = typeOperations.isLocalVariable(variable) |
| ? notAssigned.remove(emptySet, variable) |
| : notAssigned; |
| |
| var newPromoted = _removePromoted(promoted, variable); |
| |
| if (identical(newNotAssigned, notAssigned) && |
| identical(newPromoted, promoted)) { |
| return this; |
| } |
| |
| return FlowModel<Variable, Type>._( |
| reachable, |
| newNotAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Removes a [variable] from a "promoted" [map], treating the map as |
| /// immutable. |
| Map<Variable, Type> _removePromoted( |
| Map<Variable, Type> map, Variable variable) { |
| if (map[variable] == null) return map; |
| |
| var result = Map<Variable, Type>.from(map); |
| result[variable] = null; |
| return result; |
| } |
| |
| /// Removes a set of [variable]s from a "promoted" [map], treating the map as |
| /// immutable. |
| Map<Variable, Type> _removePromotedAll( |
| Map<Variable, Type> map, |
| Set<Variable> variables, |
| ) { |
| if (map.isEmpty) return const {}; |
| if (variables.isEmpty) return map; |
| |
| var result = <Variable, Type>{}; |
| var noChanges = true; |
| for (var entry in map.entries) { |
| var variable = entry.key; |
| var promotedType = entry.value; |
| if (variables.contains(variable) && promotedType != null) { |
| result[variable] = null; |
| noChanges = false; |
| } else { |
| result[variable] = promotedType; |
| } |
| } |
| |
| if (noChanges) return map; |
| if (result.isEmpty) return const {}; |
| return result; |
| } |
| |
| /// 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<Variable, Type> join<Variable, Type>( |
| TypeOperations<Variable, Type> typeOperations, |
| FlowModel<Variable, Type> first, |
| FlowModel<Variable, Type> second, |
| ) { |
| if (first == null) return second; |
| if (second == null) return first; |
| |
| if (first.reachable && !second.reachable) return first; |
| if (!first.reachable && second.reachable) return second; |
| |
| var newReachable = first.reachable || second.reachable; |
| var newNotAssigned = first.notAssigned.union(second.notAssigned); |
| var newPromoted = |
| FlowModel.joinPromoted(typeOperations, first.promoted, second.promoted); |
| |
| return FlowModel._identicalOrNew( |
| first, |
| second, |
| newReachable, |
| newNotAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Joins two "promoted" maps. See [join] for details. |
| @visibleForTesting |
| static Map<Variable, Type> joinPromoted<Variable, Type>( |
| TypeOperations<Variable, Type> typeOperations, |
| Map<Variable, Type> first, |
| Map<Variable, Type> second, |
| ) { |
| if (identical(first, second)) return first; |
| if (first.isEmpty || second.isEmpty) return const {}; |
| |
| var result = <Variable, Type>{}; |
| var alwaysFirst = true; |
| var alwaysSecond = true; |
| for (var entry in first.entries) { |
| var variable = entry.key; |
| if (!second.containsKey(variable)) { |
| alwaysFirst = false; |
| } else { |
| var firstType = entry.value; |
| var secondType = second[variable]; |
| if (identical(firstType, secondType)) { |
| result[variable] = firstType; |
| } else if (firstType == null) { |
| result[variable] = null; |
| alwaysSecond = false; |
| } else if (secondType == null) { |
| result[variable] = null; |
| alwaysFirst = false; |
| } else if (typeOperations.isSubtypeOf(firstType, secondType)) { |
| result[variable] = secondType; |
| alwaysFirst = false; |
| } else if (typeOperations.isSubtypeOf(secondType, firstType)) { |
| result[variable] = firstType; |
| alwaysSecond = false; |
| } else { |
| result[variable] = null; |
| alwaysFirst = false; |
| alwaysSecond = false; |
| } |
| } |
| } |
| |
| if (alwaysFirst) return first; |
| if (alwaysSecond && result.length == second.length) return second; |
| if (result.isEmpty) return const {}; |
| return result; |
| } |
| |
| /// 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<Variable, Type> _identicalOrNew<Variable, Type>( |
| FlowModel<Variable, Type> first, |
| FlowModel<Variable, Type> second, |
| bool newReachable, |
| _VariableSet<Variable> newNotAssigned, |
| Map<Variable, Type> newPromoted, |
| ) { |
| if (first.reachable == newReachable && |
| identical(first.notAssigned, newNotAssigned) && |
| identical(first.promoted, newPromoted)) { |
| return first; |
| } |
| if (second.reachable == newReachable && |
| identical(second.notAssigned, newNotAssigned) && |
| identical(second.promoted, newPromoted)) { |
| return second; |
| } |
| |
| return FlowModel<Variable, Type>._( |
| newReachable, |
| newNotAssigned, |
| newPromoted, |
| ); |
| } |
| |
| /// Determines whether the given "promoted" maps are equivalent. |
| static bool _promotionsEqual<Variable, Type>( |
| TypeOperations<Variable, Type> typeOperations, |
| Map<Variable, Type> p1, |
| Map<Variable, Type> p2) { |
| if (p1.length != p2.length) return false; |
| if (!p1.keys.toSet().containsAll(p2.keys)) return false; |
| for (var entry in p1.entries) { |
| var p1Value = entry.value; |
| var p2Value = p2[entry.key]; |
| if (p1Value == null) { |
| if (p2Value != null) return false; |
| } else { |
| if (p2Value == null) return false; |
| if (!typeOperations.isSameType(p1Value, p2Value)) return false; |
| } |
| } |
| return true; |
| } |
| } |
| |
| /// Accessor for function body information. |
| abstract class FunctionBodyAccess<Variable> { |
| bool isPotentiallyMutatedInClosure(Variable variable); |
| |
| bool isPotentiallyMutatedInScope(Variable variable); |
| } |
| |
| /// Operations on nodes, abstracted from concrete node interfaces. |
| abstract class NodeOperations<Expression> { |
| /// If the [node] is a parenthesized expression, recursively unwrap it. |
| Expression unwrapParenthesized(Expression node); |
| } |
| |
| /// Operations on types, abstracted from concrete type interfaces. |
| abstract class TypeOperations<Variable, Type> { |
| /// Return `true` if the [variable] is a local variable, not a parameter. |
| bool isLocalVariable(Variable variable); |
| |
| /// 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 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); |
| |
| /// Return the static type of the given [variable]. |
| Type variableType(Variable variable); |
| } |
| |
| /// List based immutable set of variables. |
| class _VariableSet<Variable> { |
| final List<Variable> variables; |
| |
| _VariableSet._(this.variables); |
| |
| _VariableSet<Variable> add(Variable addedVariable) { |
| if (contains(addedVariable)) { |
| return this; |
| } |
| |
| var length = variables.length; |
| var newVariables = List<Variable>(length + 1); |
| for (var i = 0; i < length; ++i) { |
| newVariables[i] = variables[i]; |
| } |
| newVariables[length] = addedVariable; |
| return _VariableSet._(newVariables); |
| } |
| |
| _VariableSet<Variable> addAll(Iterable<Variable> variables) { |
| var result = this; |
| for (var variable in variables) { |
| result = result.add(variable); |
| } |
| return result; |
| } |
| |
| bool contains(Variable variable) { |
| var length = variables.length; |
| for (var i = 0; i < length; ++i) { |
| if (identical(variables[i], variable)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| _VariableSet<Variable> intersect({ |
| _VariableSet<Variable> empty, |
| _VariableSet<Variable> other, |
| }) { |
| if (identical(other, empty)) return empty; |
| if (identical(this, other)) return this; |
| |
| // TODO(scheglov) optimize |
| var newVariables = |
| variables.toSet().intersection(other.variables.toSet()).toList(); |
| |
| if (newVariables.isEmpty) return empty; |
| return _VariableSet._(newVariables); |
| } |
| |
| _VariableSet<Variable> remove( |
| _VariableSet<Variable> empty, |
| Variable removedVariable, |
| ) { |
| if (!contains(removedVariable)) { |
| return this; |
| } |
| |
| var length = variables.length; |
| if (length == 1) { |
| return empty; |
| } |
| |
| var newVariables = List<Variable>(length - 1); |
| var newIndex = 0; |
| for (var i = 0; i < length; ++i) { |
| var variable = variables[i]; |
| if (!identical(variable, removedVariable)) { |
| newVariables[newIndex++] = variable; |
| } |
| } |
| |
| return _VariableSet._(newVariables); |
| } |
| |
| @override |
| String toString() => variables.isEmpty ? '{}' : '{ ${variables.join(', ')} }'; |
| |
| _VariableSet<Variable> union(_VariableSet<Variable> other) { |
| if (other.variables.isEmpty) { |
| return this; |
| } |
| |
| var result = this; |
| var otherVariables = other.variables; |
| for (var i = 0; i < otherVariables.length; ++i) { |
| var otherVariable = otherVariables[i]; |
| result = result.add(otherVariable); |
| } |
| return result; |
| } |
| } |