Implement least upper bound.

sdk/lib/_internal/compiler/implementation/resolution/members.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.
 
 part of resolution;
 
 abstract class TreeElements {
   Element get currentElement;
   Setlet<Node> get superUses;
 
@@ skipping 643 matching lines @@
       factory.redirectionTargetType = targetType;
     }
   }
 
   /**
    * 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, Spannable from) {
+  void loadSupertypes(BaseClassElementX cls, Spannable from) {
     compiler.withCurrentElement(cls, () => measure(() {
       if (cls.supertypeLoadState == STATE_DONE) return;
       if (cls.supertypeLoadState == STATE_STARTED) {
         compiler.reportError(from, MessageKind.CYCLIC_CLASS_HIERARCHY,
                                  {'className': cls.name});
         cls.supertypeLoadState = STATE_DONE;
-        cls.allSupertypes = const Link<DartType>().prepend(
-            compiler.objectClass.computeType(compiler));
+        cls.allSupertypesAndSelf =
+            compiler.objectClass.allSupertypesAndSelf.extendClass(
+                cls.computeType(compiler));
         cls.supertype = cls.allSupertypes.head;
+        assert(invariant(from, cls.supertype != null,
+            message: 'Missing supertype on cyclic class $cls.'));
         return;
       }
       cls.supertypeLoadState = STATE_STARTED;
       compiler.withCurrentElement(cls, () {
         // TODO(ahe): Cache the node in cls.
         cls.parseNode(compiler).accept(
             new ClassSupertypeResolver(compiler, cls));
         if (cls.supertypeLoadState != STATE_DONE) {
           cls.supertypeLoadState = STATE_DONE;
         }
@@ skipping 32 matching lines @@
   }
 
   void _ensureClassWillBeResolved(ClassElement element) {
     if (currentlyResolvedClass == null) {
       element.ensureResolved(compiler);
     } else {
       pendingClassesToBeResolved.add(element);
     }
   }
 
-  void resolveClassInternal(ClassElement element, TreeElementMapping mapping) {
+  void resolveClassInternal(BaseClassElementX element,
+                            TreeElementMapping mapping) {
     if (!element.isPatch) {
       compiler.withCurrentElement(element, () => measure(() {
         assert(element.resolutionState == STATE_NOT_STARTED);
         element.resolutionState = STATE_STARTED;
         Node tree = element.parseNode(compiler);
         loadSupertypes(element, tree);
 
         ClassResolverVisitor visitor =
             new ClassResolverVisitor(compiler, element, mapping);
         visitor.visit(tree);
         element.resolutionState = STATE_DONE;
         compiler.onClassResolved(element);
       }));
       if (element.isPatched) {
         // Ensure handling patch after origin.
         element.patch.ensureResolved(compiler);
       }
     } else { // Handle patch classes:
       element.resolutionState = STATE_STARTED;
       // Ensure handling origin before patch.
       element.origin.ensureResolved(compiler);
       // Ensure that the type is computed.
       element.computeType(compiler);
       // Copy class hiearchy from origin.
       element.supertype = element.origin.supertype;
       element.interfaces = element.origin.interfaces;
-      element.allSupertypes = element.origin.allSupertypes;
+      element.allSupertypesAndSelf = element.origin.allSupertypesAndSelf;
       // Stepwise assignment to ensure invariant.
       element.supertypeLoadState = STATE_STARTED;
       element.supertypeLoadState = STATE_DONE;
       element.resolutionState = STATE_DONE;
       // TODO(johnniwinther): Check matching type variables and
       // empty extends/implements clauses.
     }
     for (MetadataAnnotation metadata in element.metadata) {
       metadata.ensureResolved(compiler);
     }
@@ skipping 3169 matching lines @@
     return constructor.name == '' &&
         constructor.computeSignature(compiler).parameterCount == 0;
   }
 
   FunctionElement createForwardingConstructor(FunctionElement target,
                                               ClassElement enclosing) {
     return new SynthesizedConstructorElementX(
         target.name, target, enclosing, false);
   }
 
-  void doApplyMixinTo(MixinApplicationElement mixinApplication,
+  void doApplyMixinTo(MixinApplicationElementX mixinApplication,
                       DartType supertype,
                       DartType mixinType) {
     Node node = mixinApplication.parseNode(compiler);
 
     if (mixinApplication.supertype != null) {
       // [supertype] is not null if there was a cycle.
       assert(invariant(node, compiler.compilationFailed));
       supertype = mixinApplication.supertype;
       assert(invariant(node, supertype.element == compiler.objectClass));
     } else {
       mixinApplication.supertype = supertype;
     }
 
     // Named mixin application may have an 'implements' clause.
     NamedMixinApplication namedMixinApplication =
         node.asNamedMixinApplication();
     Link<DartType> interfaces = (namedMixinApplication != null)
         ? resolveInterfaces(namedMixinApplication.interfaces,
                             namedMixinApplication.superclass)
         : const Link<DartType>();
 
     // The class that is the result of a mixin application implements
     // the interface of the class that was mixed in so always prepend
     // that to the interface list.
+
     interfaces = interfaces.prepend(mixinType);
     assert(mixinApplication.interfaces == null);
     mixinApplication.interfaces = interfaces;
 
+    ClassElement superclass = supertype.element;
     if (mixinType.kind != TypeKind.INTERFACE) {
-      mixinApplication.allSupertypes = const Link<DartType>();
+      mixinApplication.allSupertypesAndSelf = superclass.allSupertypesAndSelf;
       return;
     }
 
     assert(mixinApplication.mixinType == null);
     mixinApplication.mixinType = resolveMixinFor(mixinApplication, mixinType);
 
     // Create forwarding constructors for constructor defined in the superclass
     // because they are now hidden by the mixin application.
-    ClassElement superclass = supertype.element;
     superclass.forEachLocalMember((Element member) {
       if (!member.isGenerativeConstructor()) return;
       FunctionElement forwarder =
           createForwardingConstructor(member, mixinApplication);
       mixinApplication.addConstructor(forwarder);
     });
     calculateAllSupertypes(mixinApplication);
   }
 
   InterfaceType resolveMixinFor(MixinApplicationElement mixinApplication,
@@ skipping 95 matching lines @@
    *
    * For example, for a class `class C extends S implements I1, I2`, we compute
    *   supertypes(C) = [S, I1, I2] ++ supertypes(S) ++ supertypes(I1)
    *                   ++ supertypes(I2),
    * where ++ stands for list concatenation.
    *
    * This order makes sure that if a class implements an interface twice with
    * different type arguments, the type used in the most specific class comes
    * first.
    */
-  void calculateAllSupertypes(ClassElement cls) {
-    if (cls.allSupertypes != null) return;
+  void calculateAllSupertypes(BaseClassElementX cls) {
+    if (cls.allSupertypesAndSelf != null) return;
     final DartType supertype = cls.supertype;
     if (supertype != null) {
-      Map<Element, DartType> instantiations = new Map<Element, DartType>();
-      LinkBuilder<DartType> allSupertypes = new LinkBuilder<DartType>();
-
-      void addSupertype(DartType type) {
-        DartType existing =
-            instantiations.putIfAbsent(type.element, () => type);
-        if (existing != null && existing != type) {
-          compiler.reportError(cls,
-              MessageKind.MULTI_INHERITANCE,
-              {'thisType': cls.computeType(compiler),
-               'firstType': existing,
-               'secondType': type});
-        }
-        if (type.element != compiler.objectClass) {
-          allSupertypes.addLast(type);
-        }
-      }
-
-      addSupertype(supertype);
-      for (Link<DartType> interfaces = cls.interfaces;
-          !interfaces.isEmpty;
-          interfaces = interfaces.tail) {
-        addSupertype(interfaces.head);
-      }
-      addAllSupertypes(addSupertype, supertype);
+      OrderedTypeSetBuilder allSupertypes = new OrderedTypeSetBuilder(cls);
+      // TODO(15296): Collapse these iterations to one when the order is not
+      // needed.
+      allSupertypes.add(compiler, supertype);
       for (Link<DartType> interfaces = cls.interfaces;
            !interfaces.isEmpty;
            interfaces = interfaces.tail) {
-        addAllSupertypes(addSupertype, interfaces.head);
+        allSupertypes.add(compiler, interfaces.head);
       }
 
-      allSupertypes.addLast(compiler.objectClass.rawType);
-      cls.allSupertypes = allSupertypes.toLink();
+      addAllSupertypes(allSupertypes, supertype);
+      for (Link<DartType> interfaces = cls.interfaces;
+           !interfaces.isEmpty;
+           interfaces = interfaces.tail) {
+        addAllSupertypes(allSupertypes, interfaces.head);
+      }
+      allSupertypes.add(compiler, cls.computeType(compiler));
+      cls.allSupertypesAndSelf = allSupertypes.toTypeSet();
     } else {
       assert(identical(cls, compiler.objectClass));
-      cls.allSupertypes = const Link<DartType>();
+      cls.allSupertypesAndSelf =
+          new OrderedTypeSet.singleton(cls.computeType(compiler));
     }
-  }
+ }
 
   /**
    * Adds [type] and all supertypes of [type] to [allSupertypes] while
    * substituting type variables.
    */
-  void addAllSupertypes(void addSupertype(DartType supertype),
+  void addAllSupertypes(OrderedTypeSetBuilder allSupertypes,
                         InterfaceType type) {
     Link<DartType> typeArguments = type.typeArguments;
     ClassElement classElement = type.element;
     Link<DartType> typeVariables = classElement.typeVariables;
     Link<DartType> supertypes = classElement.allSupertypes;
     assert(invariant(element, supertypes != null,
         message: "Supertypes not computed on $classElement "
                  "during resolution of $element"));
     while (!supertypes.isEmpty) {
       DartType supertype = supertypes.head;
-      if (supertype.element != compiler.objectClass) {
-        DartType substituted = supertype.subst(typeArguments, typeVariables);
-        addSupertype(substituted);
-      }
+      allSupertypes.add(compiler,
+                        supertype.subst(typeArguments, typeVariables));
       supertypes = supertypes.tail;
     }
   }
 
   isBlackListed(DartType type) {
     LibraryElement lib = element.getLibrary();
     return
       !identical(lib, compiler.coreLibrary) &&
       !identical(lib, compiler.jsHelperLibrary) &&
       !identical(lib, compiler.interceptorsLibrary) &&
@@ skipping 581 matching lines @@
     return finishConstructorReference(visit(expression),
                                       expression, expression);
   }
 }
 
 /// Looks up [name] in [scope] and unwraps the result.
 Element lookupInScope(Compiler compiler, Node node,
                       Scope scope, String name) {
   return Elements.unwrap(scope.lookup(name), compiler, node);
 }