Normalize type masks to use the least upper instantiated subclass/type.

pkg/compiler/lib/src/universe/class_set.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.
 
 library dart2js.world.class_set;
 
 import 'dart:collection' show IterableBase;
 import '../elements/elements.dart' show ClassElement;
 import '../util/util.dart' show Link;
 
@@ skipping 17 matching lines @@
 ///         A
 ///        / \
 ///       B   C
 ///       |
 ///       D
 ///       |
 ///       E
 ///
 class ClassHierarchyNode {
   final ClassElement cls;
+  ClassElement _leastUpperInstantiatedSubclass;
 
   /// `true` if [cls] has been directly instantiated.
   ///
   /// For instance `C` but _not_ `B` in:
   ///   class B {}
   ///   class C extends B {}
   ///   main() => new C();
   ///
   bool isDirectlyInstantiated = false;
 
@@ skipping 46 matching lines @@
        bool includeUninstantiated: true,
        bool strict: false}) {
     return new ClassHierarchyNodeIterable(
         this,
         includeRoot: !strict,
         includeDirectlyInstantiated: includeDirectlyInstantiated,
         includeIndirectlyInstantiated: includeIndirectlyInstantiated,
         includeUninstantiated: includeUninstantiated);
   }
 
+  /// Returns the most specific subclass of [cls] (including [cls]) that is
+  /// directly instantiated or a superclass of all directly instantiated
+  /// subclasses. If [cls] is not instantiated, `null` is returned.
+  ClassElement getLeastUpperInstantiatedSubclass() {

[herhut, 2015/11/04 10:42:20]

This name is very misleading. I know it is long already, but how about

getLeastUpperBoundOfInstantiatedSubclasses

or, to make it shorter

getLubOfInstantiatedSubclasses

Because I don't really know what a least upper instantiated subclass is, and it
may return something that is not directly instantiated but just a upper bound.

[Johnni Winther, 2015/11/06 13:43:23]

getLubOfInstantiatedSubclasses it is.

+    if (!isInstantiated) return null;
+    if (_leastUpperInstantiatedSubclass == null) {
+      _leastUpperInstantiatedSubclass =
+          _computeLeastUpperInstantiatedSubclass();
+    }
+    return _leastUpperInstantiatedSubclass;
+  }
+
+  ClassElement _computeLeastUpperInstantiatedSubclass() {
+    if (isDirectlyInstantiated) {
+      return cls;
+    }
+    ClassHierarchyNode subclass;
+    for (Link<ClassHierarchyNode> link = _directSubclasses;
+         !link.isEmpty;
+         link = link.tail) {
+      if (link.head.isInstantiated) {
+        if (subclass == null) {
+          subclass = link.head;
+        } else {
+          return cls;
+        }
+      }
+    }
+    if (subclass != null) {
+      return subclass.getLeastUpperInstantiatedSubclass();
+    }
+    return cls;
+  }
+
   void printOn(StringBuffer sb, String indentation,
                {bool instantiatedOnly: false,
+                bool sorted: true,
                 ClassElement withRespectTo}) {
 
     bool isRelatedTo(ClassElement subclass) {
-      return subclass.implementsInterface(withRespectTo);
+      return subclass == withRespectTo ||
+          subclass.implementsInterface(withRespectTo);
     }
 
-    sb.write('$indentation$cls');
+    sb.write(indentation);
+    if (cls.isAbstract) {
+      sb.write('abstract ');
+    }
+    sb.write('class ${cls.name}:');
     if (isDirectlyInstantiated) {
       sb.write(' directly');
     }
     if (isIndirectlyInstantiated) {
       sb.write(' indirectly');
     }
     sb.write(' [');
     if (_directSubclasses.isEmpty) {
       sb.write(']');
     } else {
+      var subclasses = _directSubclasses;
+      if (sorted) {
+        subclasses = _directSubclasses.toList()..sort((a, b) {
+          return a.cls.name.compareTo(b.cls.name);
+        });
+      }
       bool needsComma = false;
-      for (Link<ClassHierarchyNode> link = _directSubclasses;
-           !link.isEmpty;
-           link = link.tail) {
-        ClassHierarchyNode child = link.head;
+      for (ClassHierarchyNode child in subclasses) {
         if (instantiatedOnly && !child.isInstantiated) {
           continue;
         }
         if (withRespectTo != null && !child.subclasses().any(isRelatedTo)) {
           continue;
         }
         if (needsComma) {
           sb.write(',\n');
         } else {
           sb.write('\n');
         }
         child.printOn(
             sb,
             '$indentation  ',
             instantiatedOnly: instantiatedOnly,
+            sorted: sorted,
             withRespectTo: withRespectTo);
         needsComma = true;
       }
       if (needsComma) {
         sb.write('\n');
         sb.write('$indentation]');
       } else {
         sb.write(']');
       }
     }
@@ skipping 51 matching lines @@
 /// The subtypes `B` and `E` are not directly modeled because they are implied
 /// by their subclass relation to `A` and `D`, repectively. This can be seen
 /// if we expand the subclass subtrees:
 ///
 ///      A  ->  [C, D, F]
 ///      |          |
 ///      B          E
 ///
 class ClassSet {
   final ClassHierarchyNode node;
+  ClassElement _leastUpperInstantiatedSubtype;
 
   List<ClassHierarchyNode> _directSubtypes;
 
   ClassSet(this.node);
 
   ClassElement get cls => node.cls;
 
   /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
   ///
   /// The directly instantiated, indirectly instantiated and uninstantiated
@@ skipping 80 matching lines @@
           }
         }
       }
       if (!added) {
         newSubtypes.add(subtype);
       }
       _directSubtypes = newSubtypes;
     }
   }
 
+  /// Returns the most specific subtype of [cls] (including [cls]) that is
+  /// directly instantiated or a superclass of all directly instantiated
+  /// subtypes. If no subtypes of [cls] are instantiated, `null` is returned.
+  ClassElement getLeastUpperInstantiatedSubtype() {

[herhut, 2015/11/04 10:42:20]

Same name comment here, maybe

getLubOfInstantiatedSubtypes

[Johnni Winther, 2015/11/06 13:43:23]

Done.

+    if (_leastUpperInstantiatedSubtype == null) {
+      _leastUpperInstantiatedSubtype = _computeLeastUpperInstantiatedSubtype();
+    }
+    return _leastUpperInstantiatedSubtype;
+  }
+
+  ClassElement _computeLeastUpperInstantiatedSubtype() {
+    if (node.isDirectlyInstantiated) {
+      return cls;
+    }
+    if (_directSubtypes == null) {
+      return node.getLeastUpperInstantiatedSubclass();
+    }
+    ClassHierarchyNode subtype;
+    if (node.isInstantiated) {
+      subtype = node;
+    }
+    for (ClassHierarchyNode subnode in _directSubtypes) {
+      if (subnode.isInstantiated) {
+        if (subtype == null) {
+          subtype = subnode;
+        } else {
+          return cls;
+        }
+      }
+    }
+    if (subtype != null) {
+      return subtype.getLeastUpperInstantiatedSubclass();
+    }
+    return null;
+  }
+
   String toString() {
     StringBuffer sb = new StringBuffer();
     sb.write('[\n');
     node.printOn(sb, '  ');
     sb.write('\n');
     if (_directSubtypes != null) {
       for (ClassHierarchyNode node in _directSubtypes) {
         node.printOn(sb, '  ');
         sb.write('\n');
       }
@@ skipping 185 matching lines @@
           includeDirectlyInstantiated: includeDirectlyInstantiated,
           includeIndirectlyInstantiated: includeIndirectlyInstantiated,
           includeUninstantiated: includeUninstantiated).iterator;
       if (elements.moveNext()) {
         return true;
       }
     }
     return false;
   }
 }