| // 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:front_end/src/fasta/flow_analysis/flow_analysis.dart'; |
| import 'package:test/test.dart'; |
| |
| main() { |
| group('API', () { |
| test('conditionEqNull(notEqual: true) promotes true branch', () { |
| var h = _Harness(); |
| var x = h.addAssignedVar('x', 'int?'); |
| var expr = _Expression(); |
| h.flow.conditionEqNull(expr, x, notEqual: true); |
| h.flow.ifStatement_thenBegin(expr); |
| expect(h.flow.promotedType(x).type, 'int'); |
| h.flow.ifStatement_elseBegin(); |
| expect(h.flow.promotedType(x), isNull); |
| h.flow.ifStatement_end(true); |
| h.flow.finish(); |
| }); |
| |
| test('conditionEqNull(notEqual: false) promotes false branch', () { |
| var h = _Harness(); |
| var x = h.addAssignedVar('x', 'int?'); |
| var expr = _Expression(); |
| h.flow.conditionEqNull(expr, x, notEqual: false); |
| h.flow.ifStatement_thenBegin(expr); |
| expect(h.flow.promotedType(x), isNull); |
| h.flow.ifStatement_elseBegin(); |
| expect(h.flow.promotedType(x).type, 'int'); |
| h.flow.ifStatement_end(true); |
| h.flow.finish(); |
| }); |
| |
| test('finish checks proper nesting', () { |
| var h = _Harness(); |
| var expr = _Expression(); |
| h.flow.ifStatement_thenBegin(expr); |
| expect(() => h.flow.finish(), _asserts); |
| }); |
| |
| test('finish checks for un-added variables', () { |
| var h = _Harness(); |
| var x = _Var('x', _Type('int')); |
| h.flow.isAssigned(x); |
| expect(() => h.flow.finish(), _asserts); |
| }); |
| |
| test('ifStatement_end(false) keeps else branch if then branch exits', () { |
| var h = _Harness(); |
| var x = h.addAssignedVar('x', 'int?'); |
| var expr = _Expression(); |
| h.flow.conditionEqNull(expr, x); |
| h.flow.ifStatement_thenBegin(expr); |
| h.flow.handleExit(); |
| h.flow.ifStatement_end(false); |
| expect(h.flow.promotedType(x).type, 'int'); |
| h.flow.finish(); |
| }); |
| |
| test('Infinite loop does not implicitly assign variables', () { |
| var h = _Harness(); |
| var x = h.addUnassignedVar('x', 'int'); |
| var trueCondition = _Expression(); |
| h.flow.whileStatement_conditionBegin({x}); |
| h.flow.booleanLiteral(trueCondition, true); |
| h.flow.whileStatement_bodyBegin(_Statement(), trueCondition); |
| h.flow.whileStatement_end(); |
| expect(h.flow.isAssigned(x), false); |
| }); |
| |
| void _promote(_Harness h, _Var variable, String type) { |
| // if (variable is! type) { |
| var isExpression = _Expression(); |
| h.flow.isExpression_end(isExpression, variable, true, _Type(type)); |
| h.flow.ifStatement_thenBegin(isExpression); |
| // return; |
| h.flow.handleExit(); |
| // } |
| h.flow.ifStatement_end(false); |
| } |
| |
| test('If(false) does not discard promotions', () { |
| var h = _Harness(); |
| var x = h.addAssignedVar('x', 'Object'); |
| _promote(h, x, 'int'); |
| expect(h.flow.promotedType(x).type, 'int'); |
| // if (false) { |
| var falseExpression = _Expression(); |
| h.flow.booleanLiteral(falseExpression, false); |
| h.flow.ifStatement_thenBegin(falseExpression); |
| expect(h.flow.promotedType(x).type, 'int'); |
| h.flow.ifStatement_end(false); |
| }); |
| |
| void _checkIs(String declaredType, String tryPromoteType, |
| String expectedPromotedType) { |
| var h = _Harness(); |
| var x = h.addAssignedVar('x', 'int?'); |
| var expr = _Expression(); |
| h.flow.isExpression_end(expr, x, false, _Type(tryPromoteType)); |
| h.flow.ifStatement_thenBegin(expr); |
| if (expectedPromotedType == null) { |
| expect(h.flow.promotedType(x), isNull); |
| } else { |
| expect(h.flow.promotedType(x).type, expectedPromotedType); |
| } |
| h.flow.ifStatement_elseBegin(); |
| expect(h.flow.promotedType(x), isNull); |
| h.flow.ifStatement_end(true); |
| h.flow.finish(); |
| } |
| |
| test('isExpression_end promotes to a subtype', () { |
| _checkIs('int?', 'int', 'int'); |
| }); |
| |
| test('isExpression_end does not promote to a supertype', () { |
| _checkIs('int', 'int?', null); |
| }); |
| |
| test('isExpression_end does not promote to an unrelated type', () { |
| _checkIs('int', 'String', null); |
| }); |
| }); |
| |
| group('State', () { |
| var emptySet = FlowModel<_Var, _Type>(true).notAssigned; |
| var intVar = _Var('x', _Type('int')); |
| var intQVar = _Var('x', _Type('int?')); |
| var objectQVar = _Var('x', _Type('Object?')); |
| group('setReachable', () { |
| var unreachable = FlowModel<_Var, _Type>(false); |
| var reachable = FlowModel<_Var, _Type>(true); |
| test('unchanged', () { |
| expect(unreachable.setReachable(false), same(unreachable)); |
| expect(reachable.setReachable(true), same(reachable)); |
| }); |
| |
| test('changed', () { |
| void _check(FlowModel<_Var, _Type> initial, bool newReachability) { |
| var s = initial.setReachable(newReachability); |
| expect(s, isNot(same(initial))); |
| expect(s.reachable, newReachability); |
| expect(s.notAssigned, same(initial.notAssigned)); |
| expect(s.promoted, same(initial.promoted)); |
| } |
| |
| _check(unreachable, true); |
| _check(reachable, false); |
| }); |
| }); |
| |
| group('add', () { |
| test('default', () { |
| // By default, added variables are considered unassigned. |
| var s1 = FlowModel<_Var, _Type>(true); |
| var s2 = s1.add(intVar); |
| expect(s2.notAssigned.contains(intVar), true); |
| expect(s2.reachable, true); |
| expect(s2.promoted, {intVar: null}); |
| }); |
| |
| test('unassigned', () { |
| var s1 = FlowModel<_Var, _Type>(true); |
| var s2 = s1.add(intVar, assigned: false); |
| expect(s2.notAssigned.contains(intVar), true); |
| expect(s2.reachable, true); |
| expect(s2.promoted, {intVar: null}); |
| }); |
| |
| test('assigned', () { |
| var s1 = FlowModel<_Var, _Type>(true); |
| var s2 = s1.add(intVar, assigned: true); |
| expect(s2.notAssigned.contains(intVar), false); |
| expect(s2.promoted, {intVar: null}); |
| }); |
| }); |
| |
| group('promote', () { |
| test('unpromoted -> unchanged (same)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intVar); |
| var s2 = s1.promote(h, intVar, _Type('int')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('unpromoted -> unchanged (supertype)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intVar); |
| var s2 = s1.promote(h, intVar, _Type('Object')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('unpromoted -> unchanged (unrelated)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intVar); |
| var s2 = s1.promote(h, intVar, _Type('String')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('unpromoted -> subtype', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intQVar); |
| var s2 = s1.promote(h, intQVar, _Type('int')); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| _Type.allowComparisons(() { |
| expect(s2.promoted, {intQVar: _Type('int')}); |
| }); |
| }); |
| |
| test('promoted -> unchanged (same)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int')); |
| var s2 = s1.promote(h, objectQVar, _Type('int')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('promoted -> unchanged (supertype)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int')); |
| var s2 = s1.promote(h, objectQVar, _Type('Object')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('promoted -> unchanged (unrelated)', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int')); |
| var s2 = s1.promote(h, objectQVar, _Type('String')); |
| expect(s2, same(s1)); |
| }); |
| |
| test('promoted -> subtype', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int?')); |
| var s2 = s1.promote(h, objectQVar, _Type('int')); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| _Type.allowComparisons(() { |
| expect(s2.promoted, {objectQVar: _Type('int')}); |
| }); |
| }); |
| }); |
| |
| group('write', () { |
| var objectQVar = _Var('x', _Type('Object?')); |
| test('unchanged', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(objectQVar, assigned: true); |
| var s2 = s1.write(h, emptySet, objectQVar); |
| expect(s2, same(s1)); |
| }); |
| |
| test('marks as assigned', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(objectQVar, assigned: false); |
| var s2 = s1.write(h, emptySet, objectQVar); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned.contains(objectQVar), false); |
| expect(s2.promoted, same(s1.promoted)); |
| }); |
| |
| test('un-promotes', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar, assigned: true) |
| .promote(h, objectQVar, _Type('int')); |
| expect(s1.promoted, contains(objectQVar)); |
| var s2 = s1.write(h, emptySet, objectQVar); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| expect(s2.promoted, {objectQVar: null}); |
| }); |
| }); |
| |
| group('markNonNullable', () { |
| test('unpromoted -> unchanged', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intVar); |
| var s2 = s1.markNonNullable(h, intVar); |
| expect(s2, same(s1)); |
| }); |
| |
| test('unpromoted -> promoted', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true).add(intQVar); |
| var s2 = s1.markNonNullable(h, intQVar); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| expect(s2.promoted[intQVar].type, 'int'); |
| }); |
| |
| test('promoted -> unchanged', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int')); |
| var s2 = s1.markNonNullable(h, objectQVar); |
| expect(s2, same(s1)); |
| }); |
| |
| test('promoted -> re-promoted', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .promote(h, objectQVar, _Type('int?')); |
| var s2 = s1.markNonNullable(h, objectQVar); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| _Type.allowComparisons(() { |
| expect(s2.promoted, {objectQVar: _Type('int')}); |
| }); |
| }); |
| }); |
| |
| group('removePromotedAll', () { |
| test('unchanged', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .add(intQVar) |
| .promote(h, objectQVar, _Type('int')); |
| var s2 = s1.removePromotedAll([intQVar].toSet()); |
| expect(s2, same(s1)); |
| }); |
| |
| test('changed', () { |
| var h = _Harness(); |
| var s1 = FlowModel<_Var, _Type>(true) |
| .add(objectQVar) |
| .add(intQVar) |
| .promote(h, objectQVar, _Type('int')) |
| .promote(h, intQVar, _Type('int')); |
| var s2 = s1.removePromotedAll([intQVar].toSet()); |
| expect(s2.reachable, true); |
| expect(s2.notAssigned, same(s1.notAssigned)); |
| _Type.allowComparisons(() { |
| expect(s2.promoted, {objectQVar: _Type('int'), intQVar: null}); |
| }); |
| }); |
| }); |
| |
| group('restrict', () { |
| test('reachability', () { |
| var h = _Harness(); |
| var reachable = FlowModel<_Var, _Type>(true); |
| var unreachable = reachable.setReachable(false); |
| expect( |
| reachable.restrict(h, emptySet, reachable, Set()), same(reachable)); |
| expect(reachable.restrict(h, emptySet, unreachable, Set()), |
| same(unreachable)); |
| expect(unreachable.restrict(h, emptySet, unreachable, Set()), |
| same(unreachable)); |
| expect(unreachable.restrict(h, emptySet, unreachable, Set()), |
| same(unreachable)); |
| }); |
| |
| test('assignments', () { |
| var h = _Harness(); |
| var a = _Var('a', _Type('int')); |
| var b = _Var('b', _Type('int')); |
| var c = _Var('c', _Type('int')); |
| var d = _Var('d', _Type('int')); |
| var s0 = FlowModel<_Var, _Type>(true).add(a).add(b).add(c).add(d); |
| var s1 = s0.write(h, emptySet, a).write(h, emptySet, b); |
| var s2 = s0.write(h, emptySet, a).write(h, emptySet, c); |
| var result = s1.restrict(h, emptySet, s2, Set()); |
| expect(result.notAssigned.contains(a), false); |
| expect(result.notAssigned.contains(b), false); |
| expect(result.notAssigned.contains(c), false); |
| expect(result.notAssigned.contains(d), true); |
| }); |
| |
| test('promotion', () { |
| void _check(String thisType, String otherType, bool unsafe, |
| String expectedType) { |
| var h = _Harness(); |
| var x = _Var('x', _Type('Object?')); |
| var s0 = FlowModel<_Var, _Type>(true).add(x, assigned: true); |
| var s1 = thisType == null ? s0 : s0.promote(h, x, _Type(thisType)); |
| var s2 = otherType == null ? s0 : s0.promote(h, x, _Type(otherType)); |
| var result = |
| s1.restrict(h, emptySet, s2, unsafe ? [x].toSet() : Set()); |
| if (expectedType == null) { |
| expect(result.promoted, contains(x)); |
| expect(result.promoted[x], isNull); |
| } else { |
| expect(result.promoted[x].type, expectedType); |
| } |
| } |
| |
| _check(null, null, false, null); |
| _check(null, null, true, null); |
| _check('int', null, false, 'int'); |
| _check('int', null, true, 'int'); |
| _check(null, 'int', false, 'int'); |
| _check(null, 'int', true, null); |
| _check('int?', 'int', false, 'int'); |
| _check('int', 'int?', false, 'int'); |
| _check('int', 'String', false, 'int'); |
| _check('int?', 'int', true, 'int?'); |
| _check('int', 'int?', true, 'int'); |
| _check('int', 'String', true, 'int'); |
| }); |
| |
| test('variable present in one state but not the other', () { |
| var h = _Harness(); |
| var x = _Var('x', _Type('Object?')); |
| var s0 = FlowModel<_Var, _Type>(true); |
| var s1 = s0.add(x, assigned: true); |
| expect(s0.restrict(h, emptySet, s1, {}), same(s0)); |
| expect(s0.restrict(h, emptySet, s1, {x}), same(s0)); |
| expect(s1.restrict(h, emptySet, s0, {}), same(s1)); |
| expect(s1.restrict(h, emptySet, s0, {x}), same(s1)); |
| }); |
| }); |
| }); |
| |
| group('join', () { |
| group('should re-use an input if possible', () { |
| var x = _Var('x', null); |
| var y = _Var('y', null); |
| var intType = _Type('int'); |
| var intQType = _Type('int?'); |
| var stringType = _Type('String'); |
| const emptyMap = <Null, Null>{}; |
| |
| test('identical inputs', () { |
| var h = _Harness(); |
| var p = {x: intType, y: stringType}; |
| expect(FlowModel.joinPromoted(h, p, p), same(p)); |
| }); |
| |
| test('one input empty', () { |
| var h = _Harness(); |
| var p1 = {x: intType, y: stringType}; |
| var p2 = <_Var, _Type>{}; |
| expect(FlowModel.joinPromoted(h, p1, p2), same(emptyMap)); |
| expect(FlowModel.joinPromoted(h, p2, p1), same(emptyMap)); |
| }); |
| |
| test('related types', () { |
| var h = _Harness(); |
| var p1 = {x: intType}; |
| var p2 = {x: intQType}; |
| expect(FlowModel.joinPromoted(h, p1, p2), same(p2)); |
| expect(FlowModel.joinPromoted(h, p2, p1), same(p2)); |
| }); |
| |
| test('unrelated types', () { |
| var h = _Harness(); |
| var p1 = {x: intType}; |
| var p2 = {x: stringType}; |
| expect(FlowModel.joinPromoted(h, p1, p2), {x: null}); |
| expect(FlowModel.joinPromoted(h, p2, p1), {x: null}); |
| }); |
| |
| test('sub-map', () { |
| var h = _Harness(); |
| var p1 = {x: intType, y: stringType}; |
| var p2 = {x: intType}; |
| expect(FlowModel.joinPromoted(h, p1, p2), same(p2)); |
| expect(FlowModel.joinPromoted(h, p2, p1), same(p2)); |
| }); |
| |
| test('sub-map with matched subtype', () { |
| var h = _Harness(); |
| var p1 = {x: intType, y: stringType}; |
| var p2 = {x: intQType}; |
| expect(FlowModel.joinPromoted(h, p1, p2), same(p2)); |
| expect(FlowModel.joinPromoted(h, p2, p1), same(p2)); |
| }); |
| |
| test('sub-map with mismatched subtype', () { |
| var h = _Harness(); |
| var p1 = {x: intQType, y: stringType}; |
| var p2 = {x: intType}; |
| var join12 = FlowModel.joinPromoted(h, p1, p2); |
| _Type.allowComparisons(() => expect(join12, {x: intQType})); |
| var join21 = FlowModel.joinPromoted(h, p2, p1); |
| _Type.allowComparisons(() => expect(join21, {x: intQType})); |
| }); |
| }); |
| }); |
| } |
| |
| /// Returns the appropriate matcher for expecting an assertion error to be |
| /// thrown or not, based on whether assertions are enabled. |
| Matcher get _asserts { |
| var matcher = throwsA(TypeMatcher<AssertionError>()); |
| bool assertionsEnabled = false; |
| assert(assertionsEnabled = true); |
| if (!assertionsEnabled) { |
| matcher = isNot(matcher); |
| } |
| return matcher; |
| } |
| |
| class _Expression {} |
| |
| class _Harness |
| implements |
| NodeOperations<_Expression>, |
| TypeOperations<_Var, _Type>, |
| FunctionBodyAccess<_Var> { |
| FlowAnalysis<_Statement, _Expression, _Var, _Type> flow; |
| |
| _Harness() { |
| flow = FlowAnalysis<_Statement, _Expression, _Var, _Type>(this, this, this); |
| } |
| |
| _Var addAssignedVar(String name, String type) { |
| var v = _Var(name, _Type(type)); |
| flow.add(v, assigned: true); |
| return v; |
| } |
| |
| _Var addUnassignedVar(String name, String type) { |
| var v = _Var(name, _Type(type)); |
| flow.add(v, assigned: false); |
| return v; |
| } |
| |
| @override |
| bool isLocalVariable(_Var variable) { |
| // TODO(paulberry): make tests where this returns false |
| return true; |
| } |
| |
| @override |
| bool isPotentiallyMutatedInClosure(_Var variable) { |
| // TODO(paulberry): make tests where this returns true |
| return false; |
| } |
| |
| @override |
| bool isPotentiallyMutatedInScope(_Var variable) { |
| throw UnimplementedError('TODO(paulberry)'); |
| } |
| |
| @override |
| bool isSameType(_Type type1, _Type type2) { |
| return type1.type == type2.type; |
| } |
| |
| @override |
| bool isSubtypeOf(_Type leftType, _Type rightType) { |
| const Map<String, bool> _subtypes = const { |
| 'int <: int?': true, |
| 'int <: Object': true, |
| 'int <: Object?': true, |
| 'int <: String': false, |
| 'int? <: int': false, |
| 'int? <: Object?': true, |
| 'Object <: int': false, |
| 'String <: int': false, |
| 'String <: int?': false, |
| 'String <: Object?': true, |
| }; |
| |
| if (leftType.type == rightType.type) return true; |
| var query = '$leftType <: $rightType'; |
| return _subtypes[query] ?? fail('Unknown subtype query: $query'); |
| } |
| |
| @override |
| _Type promoteToNonNull(_Type type) { |
| if (type.type.endsWith('?')) { |
| return _Type(type.type.substring(0, type.type.length - 1)); |
| } else { |
| return type; |
| } |
| } |
| |
| @override |
| _Expression unwrapParenthesized(_Expression node) { |
| // TODO(paulberry): test cases where this matters |
| return node; |
| } |
| |
| @override |
| _Type variableType(_Var variable) { |
| return variable.type; |
| } |
| } |
| |
| class _Statement {} |
| |
| class _Type { |
| static bool _allowingTypeComparisons = false; |
| |
| final String type; |
| |
| _Type(this.type); |
| |
| @override |
| bool operator ==(Object other) { |
| if (_allowingTypeComparisons) { |
| return other is _Type && other.type == this.type; |
| } else { |
| // The flow analysis engine should not compare types using operator==. It |
| // should compare them using TypeOperations. |
| fail('Unexpected use of operator== on types'); |
| } |
| } |
| |
| @override |
| String toString() => type; |
| |
| static T allowComparisons<T>(T callback()) { |
| var oldAllowingTypeComparisons = _allowingTypeComparisons; |
| _allowingTypeComparisons = true; |
| try { |
| return callback(); |
| } finally { |
| _allowingTypeComparisons = oldAllowingTypeComparisons; |
| } |
| } |
| } |
| |
| class _Var { |
| final String name; |
| |
| final _Type type; |
| |
| _Var(this.name, this.type); |
| |
| @override |
| String toString() => '$type $name'; |
| } |