Ensure supertypes are loaded safely.

dart/lib/compiler/implementation/resolver.dart

 // Copyright (c) 2012, 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.
 
 interface TreeElements {
   Element operator[](Node node);
   Selector getSelector(Send send);
   Type getType(TypeAnnotation annotation);
 }
 
@@ skipping 18 matching lines @@
   Type getType(TypeAnnotation annotation) => types[annotation];
 
   void setSelector(Send send, Selector selector) {
     selectors[send] = selector;
   }
 
   Selector getSelector(Send send) => selectors[send];
 }
 
 class ResolverTask extends CompilerTask {
-  Queue<ClassElement> toResolve;
-
   // Caches the elements of analyzed constructors to make them available
   // for inlining in later tasks.
   Map<FunctionElement, TreeElements> constructorElements;
 
   ResolverTask(Compiler compiler)
-    : super(compiler), toResolve = new Queue<ClassElement>(),
+    : super(compiler),
       constructorElements = new Map<FunctionElement, TreeElements>();
 
   String get name() => 'Resolver';
 
   TreeElements resolve(Element element) {
     return measure(() {
       ElementKind kind = element.kind;
       if (kind === ElementKind.GENERATIVE_CONSTRUCTOR ||
           kind === ElementKind.FUNCTION ||
           kind === ElementKind.GETTER ||
@@ skipping 77 matching lines @@
         FunctionElement redirection =
             resolver.resolveInitializers(element, tree);
         if (redirection !== null) {
           resolveRedirectingConstructor(resolver, tree, element, redirection);
         }
       } else if (tree.initializers != null) {
         error(tree, MessageKind.FUNCTION_WITH_INITIALIZER);
       }
       visitBody(visitor, tree.body);
 
-      // Resolve the type annotations encountered in the method.
-      while (!toResolve.isEmpty()) {
-        ClassElement classElement = toResolve.removeFirst();
-        classElement.ensureResolved(compiler);
-      }
       if (isConstructor) {
         constructorElements[element] = visitor.mapping;
       }
       return visitor.mapping;
     });
   }
 
   void visitBody(ResolverVisitor visitor, Statement body) {
     visitor.visit(body);
   }
 
   void resolveConstructorImplementation(FunctionElement constructor,
                                         FunctionExpression node) {
     if (constructor.defaultImplementation !== constructor) return;
     ClassElement intrface = constructor.getEnclosingClass();
     if (!intrface.isInterface()) return;
     Type defaultType = intrface.defaultClass;
     if (defaultType === null) {
       error(node, MessageKind.NO_DEFAULT_CLASS, [intrface.name]);
     }
     ClassElement defaultClass = defaultType.element;
     defaultClass.ensureResolved(compiler);
+    assert(defaultClass.resolutionState == ClassElement.STATE_DONE);
+    assert(defaultClass.supertypeLoadState == ClassElement.STATE_DONE);
     if (defaultClass.isInterface()) {
       error(node, MessageKind.CANNOT_INSTANTIATE_INTERFACE,
             [defaultClass.name]);
     }
     // We have now established the following:
     // [intrface] is an interface, let's say "MyInterface".
     // [defaultClass] is a class, let's say "MyClass".
 
     // If the default class implements the interface then we must use the
     // default class' name. Otherwise we look for a factory with the name
@@ skipping 37 matching lines @@
     if (annotation === null) return compiler.types.dynamicType;
     ResolverVisitor visitor = new ResolverVisitor(compiler, element);
     Type result = visitor.resolveTypeAnnotation(annotation);
     if (result === null) {
       // TODO(karklose): warning.
       return compiler.types.dynamicType;
     }
     return result;
   }
 
+  /**
+   * Load and resolve the supertypes of [cls].
+   *
+   * Warning: do not call this method directly. It should only be
+   * called by [resolveClass] and [ClassSupertypeResolver].
+   */
+  void loadSupertypes(ClassElement cls, Node from) {
+    compiler.withCurrentElement(cls, () => measure(() {
+      if (cls.supertypeLoadState == ClassElement.STATE_DONE) return;
+      if (cls.supertypeLoadState == ClassElement.STATE_STARTED) {
+        compiler.reportMessage(
+          compiler.spanFromNode(from),
+          MessageKind.CYCLIC_CLASS_HIERARCHY.error([cls.name]),
+          api.Diagnostic.ERROR);
+        cls.supertypeLoadState = ClassElement.STATE_DONE;
+        cls.allSupertypes = const EmptyLink<Type>().prepend(
+            compiler.objectClass.computeType(compiler));
+        return;
+      }
+      cls.supertypeLoadState = ClassElement.STATE_STARTED;
+      compiler.withCurrentElement(cls, () {
+        // TODO(ahe): Cache the node in cls.
+        cls.parseNode(compiler).accept(new ClassSupertypeResolver(compiler,
+                                                                  cls));
+        if (cls.supertypeLoadState != ClassElement.STATE_DONE) {
+          cls.supertypeLoadState = ClassElement.STATE_DONE;
+        }
+      });
+    }));
+  }
+
+  /**
+   * Resolve the class [element].
+   *
+   * Before calling this method, [element] was constructed by the
+   * scanner and most fields are null or empty. This method fills in
+   * these fields and also ensure that the supertypes of [element] are
+   * resolved.
+   *
+   * Warning: Do not call this method directly. Instead use
+   * [:element.ensureResolved(compiler):].
+   */
   void resolveClass(ClassElement element) {
-    if (element.isResolved || element.isBeingResolved) return;
-    element.isBeingResolved = true;
-    measure(() {
+    assert(element.resolutionState == ClassElement.STATE_NOT_STARTED);
+    element.resolutionState = ClassElement.STATE_STARTED;
+    compiler.withCurrentElement(element, () => measure(() {
       ClassNode tree = element.parseNode(compiler);
+      loadSupertypes(element, tree);
+
       ClassResolverVisitor visitor =
         new ClassResolverVisitor(compiler, element);
       visitor.visit(tree);
-      element.isBeingResolved = false;
-      element.isResolved = true;
-
-      while (!toResolve.isEmpty()) {
-        ClassElement classElement = toResolve.removeFirst();
-        classElement.ensureResolved(compiler);
-      }
-
-      checkMembers(element);
-    });
+      element.resolutionState = ClassElement.STATE_DONE;
+    }));
   }
 
-  checkMembers(ClassElement cls) {
+  void checkMembers(ClassElement cls) {
     if (cls === compiler.objectClass) return;
     cls.forEachMember((holder, member) {
       checkAbstractField(member);
       checkValidOverride(member, cls.lookupSuperMember(member.name));
     });
   }
 
   void checkAbstractField(Element member) {
     if (member is !AbstractFieldElement) return;
     if (member.getter === null) return;
@@ skipping 22 matching lines @@
         compiler.spanFromElement(errorneousElement),
         errorMessage.error([contextElement.name,
                             contextElement.getEnclosingClass().name]),
         api.Diagnostic.ERROR);
     compiler.reportMessage(
         compiler.spanFromElement(contextElement),
         contextMessage.error(),
         api.Diagnostic.INFO);
   }
 
-
   void checkValidOverride(Element member, Element superMember) {
     if (superMember === null) return;
     if (member.modifiers.isStatic()) {
       reportErrorWithContext(
           member, MessageKind.NO_STATIC_OVERRIDE,
           superMember, MessageKind.NO_STATIC_OVERRIDE_CONT);
     } else {
       FunctionElement superFunction = superMember.asFunctionElement();
       FunctionElement function = member.asFunctionElement();
       if (superFunction === null || superFunction.isAccessor()) {
@@ skipping 141 matching lines @@
     return result;
   }
 
   void resolveImplicitSuperConstructorSend(FunctionElement constructor,
                                            FunctionExpression functionNode) {
     // If the class has a super resolve the implicit super call.
     ClassElement classElement = constructor.getEnclosingClass();
     ClassElement superClass = classElement.superclass;
     if (classElement != visitor.compiler.objectClass) {
       assert(superClass !== null);
-      assert(superClass.isResolved);
+      assert(superClass.resolutionState == ClassElement.STATE_DONE);
       var element = resolveSuperOrThis(constructor, true, true,
                                        const SourceString(''),
                                        Selector.INVOCATION_0, functionNode);
       visitor.world.registerStaticUse(element);
     }
   }
 
   Element resolveSuperOrThis(FunctionElement constructor,
                              bool isSuperCall,
                              bool isImplicitSuperCall,
@@ skipping 298 matching lines @@
     if (element === null) {
       onFailure(node, MessageKind.CANNOT_RESOLVE_TYPE, [node.typeName]);
     } else if (!element.impliesType()) {
       onFailure(node, MessageKind.NOT_A_TYPE, [node.typeName]);
     } else {
       if (element === compiler.types.voidType.element ||
           element === compiler.types.dynamicType.element) {
         type = element.computeType(compiler);
       } else if (element.isClass()) {
         ClassElement cls = element;
-        if (!cls.isResolved) compiler.resolveClass(cls);
+        cls.ensureResolved(compiler);
         Link<Type> arguments =
             resolveTypeArguments(node, cls.typeVariables, scope,
                                  onFailure, whenResolved);
         if (cls.typeVariables.isEmpty() && arguments.isEmpty()) {
           // Use the canonical type if it has no type parameters.
           type = cls.computeType(compiler);
         } else {
           type = new InterfaceType(cls, arguments);
         }
       } else if (element.isTypedef()) {
@@ skipping 928 matching lines @@
       } else {
         variableElement.bound = compiler.objectClass.computeType(compiler);
       }
       nodeLink = nodeLink.tail;
       typeLink = typeLink.tail;
     }
     assert(typeLink.isEmpty());
   }
 }
 
+/**
+ * The implementation of [ResolverTask.resolveClass].
+ *
+ * This visitor has to be extra careful as it is building the basic
+ * element information, and cannot safely look at other elements as
+ * this may lead to cycles.
+ *
+ * This visitor can assume that the supertypes have already been
+ * resolved, but it cannot call [ResolverTask.resolveClass] directly
+ * or indirectly (through [ClassElement.ensureResolved]) for any other
+ * types.
+ */
 class ClassResolverVisitor extends TypeDefinitionVisitor {
   ClassElement get element() => super.element;
 
   ClassResolverVisitor(Compiler compiler, ClassElement classElement)
     : super(compiler, classElement);
 
   Type visitClassNode(ClassNode node) {
     compiler.ensure(element !== null);
-    compiler.ensure(!element.isResolved);
+    compiler.ensure(element.resolutionState == ClassElement.STATE_STARTED);
 
     InterfaceType type = element.computeType(compiler);
     scope = new TypeDeclarationScope(scope, element);
     // TODO(ahe): It is not safe to call resolveTypeVariableBounds yet.
     // As a side-effect, this may get us back here trying to
     // resolve this class again.
     resolveTypeVariableBounds(node.typeParameters);
 
     // Find super type.
     Type supertype = visit(node.superclass);
     if (supertype !== null && supertype.element.isExtendable()) {
       element.supertype = supertype;
       if (isBlackListed(supertype)) {
         error(node.superclass, MessageKind.CANNOT_EXTEND, [supertype]);
       }
     } else if (supertype !== null) {
       error(node.superclass, MessageKind.TYPE_NAME_EXPECTED);
     }
     final objectElement = compiler.objectClass;
     if (element !== objectElement && element.supertype === null) {
       if (objectElement === null) {
         compiler.internalError("Internal error: cannot resolve Object",
                                node: node);
-      } else if (!objectElement.isResolved) {
-        compiler.resolver.toResolve.add(objectElement);
+      } else {
+        objectElement.ensureResolved(compiler);
       }
       // TODO(ahe): This should be objectElement.computeType(...).
       element.supertype = new InterfaceType(objectElement);
     }
-    if (node.defaultClause !== null) {
-      element.defaultClass = visit(node.defaultClause);
-    }
+    assert(element.interfaces === null);
+    Link<Type> interfaces = const EmptyLink<Type>();
     for (Link<Node> link = node.interfaces.nodes;
          !link.isEmpty();
          link = link.tail) {
       Type interfaceType = visit(link.head);
       if (interfaceType !== null && interfaceType.element.isExtendable()) {
-        element.interfaces =
-            element.interfaces.prepend(interfaceType);
+        interfaces = interfaces.prepend(interfaceType);
         if (isBlackListed(interfaceType)) {
           error(link.head, MessageKind.CANNOT_IMPLEMENT, [interfaceType]);
         }
       } else {
         error(link.head, MessageKind.TYPE_NAME_EXPECTED);
       }
     }
-    calculateAllSupertypes(element, new Set<ClassElement>());
+    element.interfaces = interfaces;
+    calculateAllSupertypes(element);
+
+    if (node.defaultClause !== null) {
+      element.defaultClass = visit(node.defaultClause);
+    }
     addDefaultConstructorIfNeeded(element);
     return element.computeType(compiler);
   }
 
   Type visitTypeAnnotation(TypeAnnotation node) {
     return visit(node.typeName);
   }
 
   Type visitIdentifier(Identifier node) {
     Element element = scope.lookup(node.source);
     if (element === null) {
       error(node, MessageKind.CANNOT_RESOLVE_TYPE, [node]);
       return null;
     } else if (!element.impliesType() && !element.isTypeVariable()) {
       error(node, MessageKind.NOT_A_TYPE, [node]);
       return null;
     } else {
-      if (element.isClass()) {
-        compiler.resolver.toResolve.add(element);
-      }
       if (element.isTypeVariable()) {
         TypeVariableElement variableElement = element;
         return variableElement.type;
       } else if (element.isTypedef()) {
         compiler.unimplemented('visitIdentifier for typedefs', node: node);
       } else {
         // TODO(ngeoffray): Use type variables.
         return element.computeType(compiler);
       }
     }
@@ skipping 14 matching lines @@
     PrefixElement prefixElement = element;
     Identifier selector = node.selector.asIdentifier();
     var e = prefixElement.lookupLocalMember(selector.source);
     if (e === null || !e.impliesType()) {
       error(node.selector, MessageKind.CANNOT_RESOLVE_TYPE, [node.selector]);
       return null;
     }
     return e.computeType(compiler);
   }
 
-  Link<Type> getOrCalculateAllSupertypes(ClassElement cls,
-                                         [Set<ClassElement> seen]) {
-    Link<Type> allSupertypes = cls.allSupertypes;
-    if (allSupertypes !== null) return allSupertypes;
-    if (seen === null) {
-      seen = new Set<ClassElement>();
-    }
-    if (seen.contains(cls)) {
-      error(cls.parseNode(compiler),
-            MessageKind.CYCLIC_CLASS_HIERARCHY,
-            [cls.name]);
-      cls.allSupertypes = const EmptyLink<Type>();
-    } else {
-      cls.ensureResolved(compiler);
-      calculateAllSupertypes(cls, seen);
-    }
-    return cls.allSupertypes;
-  }
-
-  void calculateAllSupertypes(ClassElement cls, Set<ClassElement> seen) {
+  void calculateAllSupertypes(ClassElement cls) {
     // TODO(karlklose): substitute type variables.
     // TODO(karlklose): check if type arguments match, if a classelement occurs
     //                  more than once in the supertypes.
     if (cls.allSupertypes !== null) return;
     final Type supertype = cls.supertype;
-    if (seen.contains(cls)) {
-      error(cls.parseNode(compiler),
-            MessageKind.CYCLIC_CLASS_HIERARCHY,
-            [cls.name]);
-      cls.allSupertypes = const EmptyLink<Type>();
-    } else if (supertype != null) {
-      seen.add(cls);
-      Link<Type> superSupertypes =
-          getOrCalculateAllSupertypes(supertype.element, seen);
+    if (supertype != null) {
+      Link<Type> superSupertypes = supertype.element.allSupertypes;
+      assert(superSupertypes !== null);
       Link<Type> supertypes = new Link<Type>(supertype, superSupertypes);
       for (Link<Type> interfaces = cls.interfaces;
            !interfaces.isEmpty();
            interfaces = interfaces.tail) {
         Element element = interfaces.head.element;
-        Link<Type> interfaceSupertypes =
-            getOrCalculateAllSupertypes(element, seen);
+        Link<Type> interfaceSupertypes = element.allSupertypes;
+        assert(interfaceSupertypes !== null);
         supertypes = supertypes.reversePrependAll(interfaceSupertypes);
         supertypes = supertypes.prepend(interfaces.head);
       }
-      seen.remove(cls);
       cls.allSupertypes = supertypes;
     } else {
+      assert(cls === compiler.objectClass);
       cls.allSupertypes = const EmptyLink<Type>();
     }
   }
 
   /**
    * Add a synthetic nullary constructor if there are no other
    * constructors.
    */
   void addDefaultConstructorIfNeeded(ClassElement element) {
     if (element.constructors.length != 0) return;
@@ skipping 20 matching lines @@
        type.element === compiler.boolClass ||
        type.element === compiler.numClass ||
        type.element === compiler.intClass ||
        type.element === compiler.doubleClass ||
        type.element === compiler.stringClass ||
        type.element === compiler.nullClass ||
        type.element === compiler.functionClass);
   }
 }
 
+class ClassSupertypeResolver extends CommonResolverVisitor {
+  Scope context;
+  ClassElement classElement;
+
+  ClassSupertypeResolver(Compiler compiler, ClassElement cls)
+    : context = new TopScope(cls.getLibrary()),
+      this.classElement = cls,
+      super(compiler);
+
+  void loadSupertype(ClassElement element, Node from) {
+    compiler.resolver.loadSupertypes(element, from);
+    element.ensureResolved(compiler);
+  }
+
+  void visitClassNode(ClassNode node) {
+    if (node.superclass === null) {
+      if (classElement !== compiler.objectClass) {
+        loadSupertype(compiler.objectClass, node);
+      }
+    } else {
+      node.superclass.accept(this);
+    }
+    for (Link<Node> link = node.interfaces.nodes;
+         !link.isEmpty();
+         link = link.tail) {
+      link.head.accept(this);
+    }
+  }
+
+  void visitTypeAnnotation(TypeAnnotation node) {
+    node.typeName.accept(this);
+  }
+
+  void visitIdentifier(Identifier node) {
+    Element element = context.lookup(node.source);
+    if (element === null) {
+      error(node, MessageKind.CANNOT_RESOLVE_TYPE, [node]);
+    } else if (!element.impliesType()) {
+      error(node, MessageKind.NOT_A_TYPE, [node]);
+    } else {
+      if (element.isClass()) {
+        loadSupertype(element, node);
+      } else {
+        compiler.reportMessage(
+          compiler.spanFromNode(node),
+          MessageKind.TYPE_NAME_EXPECTED.error([]),
+          api.Diagnostic.ERROR);
+      }
+    }
+  }
+
+  void visitSend(Send node) {
+    Identifier prefix = node.receiver.asIdentifier();
+    if (prefix === null) {
+      error(node.receiver, MessageKind.NOT_A_PREFIX, [node.receiver]);
+      return;
+    }
+    Element element = context.lookup(prefix.source);
+    if (element === null || element.kind !== ElementKind.PREFIX) {
+      error(node.receiver, MessageKind.NOT_A_PREFIX, [node.receiver]);
+      return;
+    }
+    PrefixElement prefixElement = element;
+    Identifier selector = node.selector.asIdentifier();
+    var e = prefixElement.lookupLocalMember(selector.source);
+    if (e === null || !e.impliesType()) {
+      error(node.selector, MessageKind.CANNOT_RESOLVE_TYPE, [node.selector]);
+      return;
+    }
+    loadSupertype(e, node);
+  }
+}
+
 class VariableDefinitionsVisitor extends CommonResolverVisitor<SourceString> {
   VariableDefinitions definitions;
   ResolverVisitor resolver;
   ElementKind kind;
   VariableListElement variables;
 
   VariableDefinitionsVisitor(Compiler compiler,
                              this.definitions, this.resolver, this.kind)
       : super(compiler) {
     variables = new VariableListElement.node(
@@ skipping 193 matching lines @@
   visitNode(Node node) {
     throw 'not supported';
   }
 
   visitNewExpression(NewExpression node) {
     Node selector = node.send.selector;
     Element e = visit(selector);
     if (e !== null && e.kind === ElementKind.CLASS) {
       ClassElement cls = e;
       cls.ensureResolved(compiler);
-      compiler.resolver.toResolve.add(cls);
       if (cls.isInterface() && (cls.defaultClass === null)) {
         error(selector, MessageKind.CANNOT_INSTANTIATE_INTERFACE, [cls.name]);
       }
       e = cls.lookupConstructor(cls.name);
     }
     return e;
   }
 
   visitTypeAnnotation(TypeAnnotation node) {
     // TODO(ahe): Do not ignore type arguments.
     return visit(node.typeName);
   }
 
   visitSend(Send node) {
     Element e = visit(node.receiver);
     if (e === null) return null; // TODO(ahe): Return erroneous element.
 
     Identifier name = node.selector.asIdentifier();
     if (name === null) internalError(node.selector, 'unexpected node');
 
     if (e.kind === ElementKind.CLASS) {
       ClassElement cls = e;
       cls.ensureResolved(compiler);
-      compiler.resolver.toResolve.add(cls);
       if (cls.isInterface() && (cls.defaultClass === null)) {
         error(node.receiver, MessageKind.CANNOT_INSTANTIATE_INTERFACE,
               [cls.name]);
       }
       SourceString constructorName =
         Elements.constructConstructorName(cls.name, name.source);
       FunctionElement constructor = cls.lookupConstructor(constructorName);
       if (constructor === null) {
         error(name, MessageKind.CANNOT_FIND_CONSTRUCTOR, [name]);
       }
@@ skipping 143 matching lines @@
   TopScope(LibraryElement library) : super(null, library);
   Element lookup(SourceString name) {
     return library.find(name);
   }
 
   Element add(Element newElement) {
     throw "Cannot add an element in the top scope";
   }
   String toString() => '$element';
 }