Transitive inference using SCC

lib/src/checker/resolver.dart

 // Copyright (c) 2015, 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.
 
 /// Encapsulates how to invoke the analyzer resolver and overrides how it
 /// computes types on expressions to use our restricted set of types.
 library dev_compiler.src.checker.resolver;
 
 import 'package:analyzer/analyzer.dart';
 import 'package:analyzer/src/generated/ast.dart';
 import 'package:analyzer/src/generated/element.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/error.dart' as analyzer;
 import 'package:analyzer/src/generated/java_io.dart' show JavaFile;
 import 'package:analyzer/src/generated/resolver.dart';
 import 'package:analyzer/src/generated/sdk_io.dart' show DirectoryBasedDartSdk;
 import 'package:analyzer/src/generated/source.dart' show DartUriResolver;
 import 'package:analyzer/src/generated/source.dart' show Source;
 import 'package:analyzer/src/generated/source_io.dart';
 import 'package:analyzer/src/generated/static_type_analyzer.dart';
+import 'package:analyzer/src/generated/utilities_collection.dart'
+    show DirectedGraph;
 import 'package:logging/logging.dart' as logger;
 
 import 'package:dev_compiler/src/options.dart';
 import 'package:dev_compiler/src/report.dart';
 import 'package:dev_compiler/src/utils.dart';
 import 'dart_sdk.dart';
 import 'multi_package_resolver.dart';
 
 final _log = new logger.Logger('dev_compiler.src.resolver');
 
@@ skipping 51 matching lines @@
         if (message.level == logger.Level.SEVERE) failure = true;
         reporter.log(message);
       }
     }
     return failure;
   }
 }
 
 class AnalyzerError extends Message {
   factory AnalyzerError.from(analyzer.AnalysisError error) {
-    var severity = error.errorCode.errorSeverity;
+    var severity = error.errorCode.type.severity;
     var isError = severity == analyzer.ErrorSeverity.ERROR;
     var level = isError ? logger.Level.SEVERE : logger.Level.WARNING;
     int begin = error.offset;
     int end = begin + error.length;
     return new AnalyzerError(error.message, level, begin, end);
   }
 
   const AnalyzerError(String message, logger.Level level, int begin, int end)
       : super('[from analyzer]: $message', level, begin, end);
 }
@@ skipping 15 matching lines @@
   final ResolverOptions _options;
 
   LibraryResolverWithInference(context, this._options) : super(context);
 
   @override
   void resolveReferencesAndTypes() {
     _resolveVariableReferences();
 
     // Run resolution in two stages, skipping method bodies first, so we can run
     // type-inference before we fully analyze methods.
-    _resolveReferencesAndTypes(true);
-    _runInference();
-    _resolveReferencesAndTypes(false);
+    var visitors = _createVisitors();
+    _resolveEverything(visitors);
+    _runInference(visitors);
+
+    visitors.values.forEach((v) => v.skipMethodBodies = false);
+    _resolveEverything(visitors);
   }
 
   // Note: this was split from _resolveReferencesAndTypesInLibrary so we do it
   // only once.
   void _resolveVariableReferences() {
     for (Library library in resolvedLibraries) {
       for (Source source in library.compilationUnitSources) {
         library.getAST(source).accept(
             new VariableResolverVisitor.con1(library, source, typeProvider));
       }
     }
   }
 
   // Note: this was split from _resolveReferencesAndTypesInLibrary so we can do
   // resolution in pieces.
-  void _resolveReferencesAndTypes(bool skipMethods) {
+  Map<Source, RestrictedResolverVisitor> _createVisitors() {
+    var visitors = <Source, RestrictedResolverVisitor>{};
     for (Library library in resolvedLibraries) {
       for (Source source in library.compilationUnitSources) {
-        library.getAST(source).accept(new RestrictedResolverVisitor(
-            library, source, typeProvider, _options, skipMethods));
+        var visitor = new RestrictedResolverVisitor(
+            library, source, typeProvider, _options);
+        visitors[source] = visitor;
+      }
+    }
+    return visitors;
+  }
+
+  /// Runs the resolver on the entire library cycle.
+  void _resolveEverything(Map<Source, RestrictedResolverVisitor> visitors) {
+    for (Library library in resolvedLibraries) {
+      for (Source source in library.compilationUnitSources) {
+        library.getAST(source).accept(visitors[source]);
       }
     }
   }
 
-  _runInference() {
-    var consts = [];
-    var statics = [];
-    var classes = [];
+  _runInference(Map<Source, RestrictedResolverVisitor> visitors) {
+    var globals = <VariableDeclaration>[];

[vsm, 2015/03/21 15:52:19]

nit: maybe globals -> globalsAndStatics?

[Siggi Cherem (dart-lang), 2015/03/23 20:06:31]

oh funny, when I was writing this I was thinking that, since statics are globals
too, I could just call them globals. But then I didn't rename the functions
below to just say _inferGlobals instead of _inferGlobalsAndStatics... maybe
because I felt it was more explicit :-)

Not sure if you have a preference either way. For now I added the `AndStatics`,
but I'm good without it too :-)

+    var classes = <ClassDeclaration>[];
 
     // Extract top-level members that are const, statics, or classes.
     for (Library library in resolvedLibraries) {
       for (Source source in library.compilationUnitSources) {
         CompilationUnit ast = library.getAST(source);
         for (var declaration in ast.declarations) {
           if (declaration is TopLevelVariableDeclaration) {
-            if (declaration.variables.isConst) {
-              consts.addAll(declaration.variables.variables);
-            } else {
-              statics.addAll(declaration.variables.variables);
-            }
+            globals.addAll(declaration.variables.variables);
           } else if (declaration is ClassDeclaration) {
             classes.add(declaration);
             for (var member in declaration.members) {
-              if (member is! FieldDeclaration) continue;
-              if (member.fields.isConst) {
-                consts.addAll(member.fields.variables);
-              } else if (member.isStatic) {
-                statics.addAll(member.fields.variables);
+              if (member is FieldDeclaration &&
+                  (member.fields.isConst || member.isStatic)) {
+                globals.addAll(member.fields.variables);
               }
             }
           }
         }
       }
     }
+    _inferGlobalsAndStatics(globals, visitors);
+    _inferInstanceFields(classes, visitors);
+  }
 
-    // TODO(sigmund): consider propagating const types after this layer of
-    // inference, so their types can be used to initialize other members below.
-    _inferVariableFromInitializer(consts);
-    _inferVariableFromInitializer(statics);
+  _inferGlobalsAndStatics(List<VariableDeclaration> globals,
+      Map<Source, RestrictedResolverVisitor> visitors) {
+    var elementToDeclaration = {};
+    for (var c in globals) {
+      elementToDeclaration[c.element] = c;
+    }
+    var constGraph = new DirectedGraph<VariableDeclaration>();
+    globals.forEach(constGraph.addNode);
+    for (var c in globals) {
+      for (var e in _VarExtractor.extract(c.initializer)) {
+        // Note: declaration is null for variables that come from other strongly
+        // connected components.
+        var declaration = elementToDeclaration[e];
+        if (declaration != null) constGraph.addEdge(c, declaration);
+      }
+    }
+
+    for (var component in constGraph.computeTopologicalSort()) {
+      if (_options.inferTransitively) {
+        component.forEach((v) => _reanalizeVar(visitors, v));
+      }
+      _inferVariableFromInitializer(component);
+    }
+  }
+
+  _inferInstanceFields(List<ClassDeclaration> classes,
+      Map<Source, RestrictedResolverVisitor> visitors) {
+    // First propagate what was inferred from globals to all instance fields.
+    if (_options.inferTransitively) {
+      // TODO(sigmund): also do a fine-grain propagation between fields. We want
+      // infer-by-override to take precedence, so we would have to include
+      // classes in the dependency graph and ensure that fields depend on their
+      // class, and classes depend on superclasses.
+      classes
+          .expand((c) => c.members.where(_isInstanceField))
+          .expand((f) => f.fields.variables)
+          .forEach((v) => _reanalizeVar(visitors, v));
+    }
 
     // Track types in this strongly connected component, ensure we visit
     // supertypes before subtypes.
     var typeToDeclaration = <InterfaceType, ClassDeclaration>{};
     classes.forEach((c) => typeToDeclaration[c.element.type] = c);
     var seen = new Set<InterfaceType>();
     visit(ClassDeclaration cls) {
       var element = cls.element;
       var type = element.type;
       if (seen.contains(type)) return;
       for (var supertype in element.allSupertypes) {
         var supertypeClass = typeToDeclaration[supertype];
         if (supertypeClass != null) visit(supertypeClass);
       }
       seen.add(type);
 
-      _isInstanceField(f) =>
-          f is FieldDeclaration && !f.isStatic && !f.fields.isConst;
-
       if (_options.inferFromOverrides) {
         // Infer field types from overrides first, otherwise from initializers.
         var pending = new Set<VariableDeclaration>();
         cls.members
             .where(_isInstanceField)
             .forEach((f) => _inferFieldTypeFromOverride(f, pending));
         if (pending.isNotEmpty) _inferVariableFromInitializer(pending);
 
         // Infer return-types from overrides
         cls.members
             .where((m) => m is MethodDeclaration && !m.isStatic)
             .forEach(_inferMethodReturnTypeFromOverride);
       } else {
         _inferVariableFromInitializer(cls.members
             .where(_isInstanceField)
             .expand((f) => f.fields.variables));
       }
     }
     classes.forEach(visit);
   }
 
+  void _reanalizeVar(Map<Source, RestrictedResolverVisitor> visitors,

[vsm, 2015/03/21 15:52:19]

_reanalize -> _reanalyze

[Siggi Cherem (dart-lang), 2015/03/23 20:06:31]

Done.

+      VariableDeclaration variable) {
+    if (variable.initializer == null) return;
+    var visitor = visitors[(variable.root as CompilationUnit).element.source];
+    visitor.reanalyzeInitializer(variable);
+  }
+
+  static bool _isInstanceField(f) =>
+      f is FieldDeclaration && !f.isStatic && !f.fields.isConst;
+
   /// Attempts to infer the type on [field] from overridden fields or getters if
   /// a type was not specified. If no type could be inferred, but it contains an
   /// initializer, we add it to [pending] so we can try to infer it using the
   /// initializer type instead.
   void _inferFieldTypeFromOverride(
       FieldDeclaration field, Set<VariableDeclaration> pending) {
     var variables = field.fields;
     for (var variable in variables.variables) {
       var varElement = variable.element;
       if (!varElement.type.isDynamic || variables.type != null) continue;
@@ skipping 62 matching lines @@
       // ResolverVisitor.
       element.type = type;
       element.getter.returnType = type;
       if (!element.isFinal && !element.isConst) {
         element.setter.parameters[0].type = type;
       }
     }
   }
 
   bool _canInferFrom(Expression expression) {
+    if (_options.inferTransitively) return true;
     if (expression is Literal) return true;
     if (expression is InstanceCreationExpression) return true;
     if (expression is FunctionExpression) return true;
     if (expression is AsExpression) return true;
     if (expression is CascadeExpression) {
       return _canInferFrom(expression.target);
     }
     if (expression is SimpleIdentifier || expression is PropertyAccess) {
-      return _options.inferTransitively;
+      return false;
     }
     if (expression is PrefixedIdentifier) {
       if (expression.staticElement is PropertyAccessorElement) {
-        return _options.inferTransitively;
+        return false;
       }
       return _canInferFrom(expression.identifier);
     }
     if (expression is MethodInvocation) {
       return _canInferFrom(expression.target);
     }
     if (expression is BinaryExpression) {
       return _canInferFrom(expression.leftOperand);
     }
     if (expression is ConditionalExpression) {
       return _canInferFrom(expression.thenExpression) &&
           _canInferFrom(expression.elseExpression);
     }
     if (expression is PrefixExpression) {
       return _canInferFrom(expression.operand);
     }
     if (expression is PostfixExpression) {
       return _canInferFrom(expression.operand);
     }
     return false;
   }
 }
 
+/// Extracts the [VariableElement]s used in an initializer expression.
+class _VarExtractor extends RecursiveAstVisitor {
+  final elements = <VariableElement>[];
+  visitSimpleIdentifier(SimpleIdentifier node) {
+    var e = node.staticElement;
+    if (e is PropertyAccessorElement) elements.add(e.variable);
+  }
+
+  static List<VariableElement> extract(Expression initializer) {
+    if (initializer == null) return const [];
+    var extractor = new _VarExtractor();
+    initializer.accept(extractor);
+    return extractor.elements;
+  }
+}
+
 /// Overrides the default [ResolverVisitor] to support type inference in
 /// [LibraryResolverWithInference] above.
 ///
 /// Before inference, this visitor is used to resolve top-levels, classes, and
 /// fields, but nothing withihn method bodies. After inference, this visitor is
 /// used again to step into method bodies and complete resolution as a second
 /// phase.
 class RestrictedResolverVisitor extends ResolverVisitor {
   final TypeProvider _typeProvider;
 
   /// Whether to skip resolution within method bodies.
-  final bool skipMethodBodies;
+  bool skipMethodBodies = true;
+
+  /// State of the resolver at the point a field or variable was declared.
+  final _stateAtDeclaration = <AstNode, _ResolverState>{};
+
+  /// Internal tracking of whether a node was skipped while visiting, for
+  /// example, if it contained a function expression with a function body.
+  bool _nodeWasSkipped = false;
+
+  /// Internal state, whether we are revisiting an initializer, so we minimize
+  /// the work being done elsewhere.
+  bool _revisiting = false;
+
+  /// Initializers that have been visited, reanalyzed, and for which no node was
+  /// internally skipped. These initializers are fully resolved and don't need
+  /// to be re-resolved on a sunsequent pass.
+  final _visitedInitializers = new Set<VariableDeclaration>();
 
   RestrictedResolverVisitor(Library library, Source source,
-      TypeProvider typeProvider, ResolverOptions options, this.skipMethodBodies)
+      TypeProvider typeProvider, ResolverOptions options)
       : _typeProvider = typeProvider,
         super.con1(library, source, typeProvider,
             typeAnalyzerFactory: RestrictedStaticTypeAnalyzer.constructor);
 
   @override
   visitCatchClause(CatchClause node) {
     var stack = node.stackTraceParameter;
     if (stack != null) {
       // TODO(jmesserly): analyzer does not correctly associate StackTrace type.
       // It happens too late in TypeResolverVisitor visitCatchClause.
       var element = stack.staticElement;
       if (element is VariableElementImpl && element.type == null) {
         // From the language spec:
         // The static type of p1 is T and the static type of p2 is StackTrace.
         element.type = _typeProvider.stackTraceType;
       }
     }
     return super.visitCatchClause(node);
   }
 
+  reanalyzeInitializer(VariableDeclaration variable) {
+    try {
+      _revisiting = true;
+      _nodeWasSkipped = false;
+      var node = variable.parent.parent;
+      var oldState;
+      var state = _stateAtDeclaration[node];
+      if (state != null) {
+        oldState = new _ResolverState(this);
+        state.restore(this);
+        if (node is FieldDeclaration) {
+          var cls = node.parent;
+          enclosingClass = cls.element;
+        }
+      }
+      visitNode(variable.initializer);
+      if (!_nodeWasSkipped) _visitedInitializers.add(variable);
+      if (oldState != null) oldState.restore(this);
+    } finally {
+      _revisiting = false;
+    }
+  }
+
+  @override
+  Object visitTopLevelVariableDeclaration(TopLevelVariableDeclaration node) {
+    _stateAtDeclaration[node] = new _ResolverState(this);
+    return super.visitTopLevelVariableDeclaration(node);
+  }
+
+  @override
+  Object visitFieldDeclaration(FieldDeclaration node) {
+    _stateAtDeclaration[node] = new _ResolverState(this);
+    return super.visitFieldDeclaration(node);
+  }
+
+  Object visitVariableDeclaration(VariableDeclaration node) {
+    var state = new _ResolverState(this);
+    try {
+      if (_revisiting) {
+        _stateAtDeclaration[node].restore(this);
+      } else {
+        _stateAtDeclaration[node] = state;
+      }
+      return super.visitVariableDeclaration(node);
+    } finally {
+      state.restore(this);
+    }
+  }
+
   @override
   Object visitNode(AstNode node) {
-    if (skipMethodBodies &&
-        (node is FunctionBody ||
-            node is FunctionExpression ||
-            node is FunctionExpressionInvocation ||
-            node is SuperConstructorInvocation ||
-            node is RedirectingConstructorInvocation ||
-            node is Annotation ||
-            node is Comment)) {
+    if (skipMethodBodies && node is FunctionBody) {
+      _nodeWasSkipped = true;
       return null;
     }
+    if (_visitedInitializers.contains(node)) return null;
     assert(node is! Statement || !skipMethodBodies);
     return super.visitNode(node);
   }
 
   @override
   Object visitMethodDeclaration(MethodDeclaration node) {
     if (skipMethodBodies) {
       node.accept(elementResolver_J2DAccessor);
       node.accept(typeAnalyzer_J2DAccessor);
       return null;
@@ skipping 18 matching lines @@
     if (skipMethodBodies) {
       node.accept(elementResolver_J2DAccessor);
       node.accept(typeAnalyzer_J2DAccessor);
       return null;
     } else {
       return super.visitConstructorDeclaration(node);
     }
   }
 }
 
+/// Internal state of the resolver, stored so we can reanalyze portions of the
+/// AST quickly, without recomputing everything from the top.
+class _ResolverState {
+  final TypePromotionManager_TypePromoteScope promotionScope;
+  final TypeOverrideManager_TypeOverrideScope overrideScope;
+  final Scope nameScope;
+
+  _ResolverState(ResolverVisitor visitor)
+      : promotionScope = visitor.promoteManager.currentScope,
+        overrideScope = visitor.overrideManager.currentScope,
+        nameScope = visitor.nameScope;
+
+  void restore(ResolverVisitor visitor) {
+    visitor.promoteManager.currentScope = promotionScope;
+    visitor.overrideManager.currentScope = overrideScope;
+    visitor.nameScope_J2DAccessor = nameScope;
+  }
+}
+
 /// Overrides the default [StaticTypeAnalyzer] to adjust rules that are stricter
 /// in the restricted type system and to infer types for untyped local
 /// variables.
 class RestrictedStaticTypeAnalyzer extends StaticTypeAnalyzer {
   final TypeProvider _typeProvider;
 
   RestrictedStaticTypeAnalyzer(ResolverVisitor r)
       : _typeProvider = r.typeProvider,
         super(r);
 
@@ skipping 72 matching lines @@
     }
   }
 
   // Review note: no longer need to override visitFunctionExpression, this is
   // handled by the analyzer internally.
   // TODO(vsm): in visitbinaryExpression: check computeStaticReturnType result?
   // TODO(vsm): in visitFunctionDeclaration: Should we ever use the expression
   // type in a (...) => expr or just the written type?
 
 }