Flow analysis: store all variables in promoted map.

stereotype441 · commit-bot@chromium.org · commit 7912216cd6ef · 2019-08-07T14:16:11.000Z
Previously we only stored promoted variables. Storing all variables paves the way for expanding the `promoted` map into a map from variable to VariableModel, which will be necessary to bring the implementation in line with dart-lang/language#473. Change-Id: Ief7190b565da03e3c8dc22f8401f96f3e8a1d356 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/112040 Reviewed-by: Johnni Winther <johnniwinther@google.com> Reviewed-by: Konstantin Shcheglov <scheglov@google.com> Commit-Queue: Paul Berry <paulberry@google.com>
diff --git a/pkg/front_end/lib/src/fasta/flow_analysis/flow_analysis.dart b/pkg/front_end/lib/src/fasta/flow_analysis/flow_analysis.dart
@@ -301,8 +301,11 @@ class FlowAnalysis<Statement, Expression, Variable, Type> {
     _stack.add(_current);
 
     Set<Variable> notPromoted = null;
-    for (var variable in _current.promoted.keys) {
-      if (functionBody.isPotentiallyMutatedInScope(variable)) {
+    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);
       }
@@ -644,19 +647,18 @@ class FlowModel<Variable, Type> {
   /// the control flow.
   final _VariableSet<Variable> notAssigned;
 
-  /// For each variable whose type is promoted at this point in the control
-  /// flow, the promoted type.  Variables whose type is not promoted are not
-  /// present in the map.
+  /// 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 promotions would
-  /// have been lost, if their scope had extended to the entire function being
-  /// analyzed.  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 promotion
-  /// remains in the map after the `if` statement ends.  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.
+  /// 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
@@ -680,15 +682,13 @@ class FlowModel<Variable, Type> {
   /// the point of declaration.
   FlowModel<Variable, Type> add(Variable variable, {bool assigned: false}) {
     var newNotAssigned = assigned ? notAssigned : notAssigned.add(variable);
-
-    if (identical(newNotAssigned, notAssigned)) {
-      return this;
-    }
+    var newPromoted = Map<Variable, Type>.from(promoted);
+    newPromoted[variable] = null;
 
     return FlowModel<Variable, Type>._(
       reachable,
       newNotAssigned,
-      promoted,
+      newPromoted,
     );
   }
 
@@ -818,10 +818,10 @@ class FlowModel<Variable, Type> {
 
     var newPromoted = <Variable, Type>{};
     bool promotedMatchesThis = true;
-    bool promotedMatchesOther = true;
-    for (var variable in Set<Variable>.from(promoted.keys)
-      ..addAll(other.promoted.keys)) {
-      var thisType = promoted[variable];
+    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 &&
@@ -844,6 +844,7 @@ class FlowModel<Variable, Type> {
           promotedMatchesOther = false;
         }
       } else {
+        newPromoted[variable] = null;
         if (promotedMatchesOther && otherType != null) {
           promotedMatchesOther = false;
         }
@@ -912,16 +913,10 @@ class FlowModel<Variable, Type> {
   /// immutable.
   Map<Variable, Type> _removePromoted(
       Map<Variable, Type> map, Variable variable) {
-    if (map.isEmpty) return const {};
-
-    var result = <Variable, Type>{};
-    for (var key in map.keys) {
-      if (!identical(key, variable)) {
-        result[key] = map[key];
-      }
-    }
+    if (map[variable] == null) return map;
 
-    if (result.isEmpty) return const {};
+    var result = Map<Variable, Type>.from(map);
+    result[variable] = null;
     return result;
   }
 
@@ -936,11 +931,14 @@ class FlowModel<Variable, Type> {
 
     var result = <Variable, Type>{};
     var noChanges = true;
-    for (var key in map.keys) {
-      if (variables.contains(key)) {
+    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[key] = map[key];
+        result[variable] = promotedType;
       }
     }
 
@@ -996,24 +994,32 @@ class FlowModel<Variable, Type> {
     var result = <Variable, Type>{};
     var alwaysFirst = true;
     var alwaysSecond = true;
-    for (var variable in first.keys) {
-      var firstType = first[variable];
-      var secondType = second[variable];
-      if (secondType != null) {
+    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;
         }
-      } else {
-        alwaysFirst = false;
       }
     }
 
@@ -1060,7 +1066,12 @@ class FlowModel<Variable, Type> {
     for (var entry in p1.entries) {
       var p1Value = entry.value;
       var p2Value = p2[entry.key];
-      if (!typeOperations.isSameType(p1Value, p2Value)) return false;
+      if (p1Value == null) {
+        if (p2Value != null) return false;
+      } else {
+        if (p2Value == null) return false;
+        if (!typeOperations.isSameType(p1Value, p2Value)) return false;
+      }
     }
     return true;
   }
diff --git a/pkg/front_end/test/fasta/flow_analysis/flow_analysis_test.dart b/pkg/front_end/test/fasta/flow_analysis/flow_analysis_test.dart
@@ -159,22 +159,22 @@ main() {
         var s2 = s1.add(intVar);
         expect(s2.notAssigned.contains(intVar), true);
         expect(s2.reachable, true);
-        expect(s2.promoted, same(s1.promoted));
+        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, same(s1.promoted));
+        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, same(s1));
+        expect(s2.promoted, {intVar: null});
       });
     });
 
@@ -279,7 +279,7 @@ main() {
         var s2 = s1.write(h, emptySet, objectQVar);
         expect(s2.reachable, true);
         expect(s2.notAssigned, same(s1.notAssigned));
-        expect(s2.promoted, isEmpty);
+        expect(s2.promoted, {objectQVar: null});
       });
     });
 
@@ -345,7 +345,7 @@ main() {
         expect(s2.reachable, true);
         expect(s2.notAssigned, same(s1.notAssigned));
         _Type.allowComparisons(() {
-          expect(s2.promoted, {objectQVar: _Type('int')});
+          expect(s2.promoted, {objectQVar: _Type('int'), intQVar: null});
         });
       });
     });
@@ -392,7 +392,8 @@ main() {
           var result =
               s1.restrict(h, emptySet, s2, unsafe ? [x].toSet() : Set());
           if (expectedType == null) {
-            expect(result.promoted, isNot(contains(x)));
+            expect(result.promoted, contains(x));
+            expect(result.promoted[x], isNull);
           } else {
             expect(result.promoted[x].type, expectedType);
           }
@@ -411,6 +412,17 @@ main() {
         _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));
+      });
     });
   });
 
@@ -449,8 +461,8 @@ main() {
         var h = _Harness();
         var p1 = {x: intType};
         var p2 = {x: stringType};
-        expect(FlowModel.joinPromoted(h, p1, p2), same(emptyMap));
-        expect(FlowModel.joinPromoted(h, p2, p1), same(emptyMap));
+        expect(FlowModel.joinPromoted(h, p1, p2), {x: null});
+        expect(FlowModel.joinPromoted(h, p2, p1), {x: null});
       });
 
       test('sub-map', () {
